[FIXED] python greedy coloring

Issue

I made a script where I generate a graph and then color it with four colors. The colorate graph is then drawn using networkx. The program should not put two colors adjacent to oneanother but when you run the program, you can see it does. I really dont know what the issue is, my best guess is that I pass the generated graph d incorrectly to the function coloring this is my code:

import networkx as nx
import matplotlib.pyplot as plt
from random import sample,  randrange

#function that colors graph with four colors
def coloring(adj, V):
     
    result = [-1] * V
 
   
    result[0] = 0
 
 
    available = [False] * V
 
    
    for u in range(1, V):
         
     
        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = True
        cr = 0
        while cr < V:
            if (available[cr] == False):
                break
             
            cr += 1
             
        result[u] = cr

        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = False

    for u in range(V):
        print("Vertex", u, " --->  Color", result[u])
    global options

    options = {
        'node_color': result,
        'node_size': 4,
        'width': .1,
    }


#creating random graph
q = [0,1,2,3,4]
d = {i: sample([j for j in q if i != j], randrange(1, len(q) -1)) for i in q}

coloring([node for node in d.values()], 5)

G = nx.Graph()


#adding graph d to networkx 
def passToNx():
    for k in d:
        G.add_node(k)
        for j in d[k]:
            G.add_edge(k, j)


passToNx()

#drawing graph
subax1 = plt.subplot(121)
nx.draw(G, **options)
plt.show()

Solution

Your code for coloring is perfectly fine. It seems like your random graph generator is a problem:

d = {i: sample([j for j in q if i != j], randrange(1, len(q) -1)) for i in q}

Following is an example of a graph generated by above code:

{0: [1], 1: [4, 3], 2: [4], 3: [4], 4: [0, 2]}

As you can see, it is not creating a proper adjacency matrix (3 is connected with 1 but 1 is not in its adjancey matrix).

One way to solve the problem is by writing proper graph generator. My solution changes coloring function while keeping same generator:

def coloring(adj, V):
    result = [-1] * V
    result[0] = 0
    available = [False] * V
    # add values to adj matrices
    for y in range(0, V):
        for x in adj[y]:
            if y not in adj[x]:
                adj[x].append(y)

    for u in range(1, V):
        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = True
        cr = 0
        while cr < V:
            if (available[cr] == False):
                break

            cr += 1

        result[u] = cr

        for i in adj[u]:
            if (result[i] != -1):
                available[result[i]] = False

    for u in range(V):
        print("Vertex", u, " --->  Color", result[u])
    global options

    options = {
        'node_color': result,
        'node_size': 100,
        'width': 0.1,
    }

In addition you have to change the coloring of graph as it does not assigns color in order. So manually iterate over all nodes of graph to color the nodes.

q = [0,1,2,3,4]
d = {0: [1], 1: [4, 3], 2: [4], 3: [4], 4: [0, 2]}

coloring([node for node in d.values()], 5)

G = nx.Graph()

color = [x for x in options['node_color']]
color_use = [x for x in color]

#adding graph d to networkx 
def passToNx():
    for k in d:
        G.add_node(k)
        for j in d[k]:
            G.add_edge(k, j)


passToNx()

# add color to nodes
for i, node in enumerate(G):
    color_use[node] = color[i]

#drawing graph
subax1 = plt.subplot(121)
nx.draw(G, node_color= color_use, with_labels = True)
plt.show()

Answered By - FAIZAN SAFDAR ALI