Coloring

This demonstrates Spectral Coloring as proposed in B. Aspvall and J. Gilbert. Graph coloring using eigenvalue decomposition.. Basically, the eigenvectors of the adjacency matrix are used in ascending order. The algorithm uses the signs of the eigenvectors' entries to separate two verices if necessary.



In [1]:

    
import networkit
G = networkit.generators.ErdosRenyiGenerator(30, 0.2).generate()

Compute a coloring and display it:



In [2]:

    
coloring = networkit.coloring.SpectralColoring(G)
coloring.run()
networkit.viztasks.drawGraph(G, coloring=coloring.getColoring())



In [3]:

    
print("Number of needed colors: {}".format(len(coloring.colors)))









    



Number of needed colors: 10

Here, coloring is combined with spectral drawing (see separate notebook):



In [4]:

    
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, coloring=coloring.getColoring(), layout=layout)



In [5]:

    
G = networkit.graph.Graph(100)
vertices = {}
        
for i in range(0, 10):
    for j in range(0,10):
        # Top
        if j > 0:
            G.addEdge((i * 10 + j), (i * 10 + j - 1))
        # left
        if i > 0:
            G.addEdge((i * 10 + j), ((i - 1) * 10 + j))
            
coloring = networkit.coloring.SpectralColoring(G)
coloring.run()
layout = networkit.viztools.layout.SpectralLayout()
networkit.viztasks.drawGraph(G, coloring=coloring.getColoring(), layout=layout)



In [5]: