python greedy coloring

Question

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()

score 0 · Accepted Answer · answered Jan 25 '22 at 19:06

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()

thank you, I would also like to know how i could fix the graph generation as with the code that you have provided me with it does still sometimes generate a graph that has vertices that have the same color and are adjacent. To be clear, if you run the program with the graph generator a few times, you will stumble upon a graph that when colored has vertices adjacent to oneanother — Emilio, Jan 25 '22 at 20:06
It must be the coloring scheme of `nx.draw`. For the graph that shows wrong coloring, I would suggest to draw that graph yourself on paper and try to match it with the `result` array directly. Meanwhile, let me see if we can fix the graph generation. — FAIZAN SAFDAR ALI, Jan 26 '22 at 00:23
Thank you, could you suggest a way to draw a graph without using networkx? — Emilio, Jan 26 '22 at 06:02
If you haven't managed to find a solution yet, check out this other question I've asked in the meantime and you might get a better understanding on how you can help me https://stackoverflow.com/questions/70863696/generating-a-random-dictionary-and-coloring-associated-graph — Emilio, Jan 26 '22 at 20:50

python greedy coloring

1 Answers1