Check if a random graph coloring is correct (Python)

Question

So i'm trying a different approach to graph coloring, what i did basically is assign randomly colors to the nodes of a graph and what i want to do is, after assigning those colors, check if that coloring is correct (no adjacent nodes having the same color) in other words, going through the nodes and their respective colors and make sure no adjacent nodes have that same color.

Here is what i've done so far :

def approx_color(graph):
      colors = [1,2,3,4,5,6,7,8,9]
      xr = random.randint(0, len(graph.nodes))
      s_c = []
      for i in range(len(graph.nodes)):
          s_c.append(random.choice(colors))
      colored = dict(zip(graph.nodes,s_c))
      print(colored)

EDIT :

The "graph" variable is a graph generated by networkx library, and graph.nodes() graph.edges() being a list of the nodes and edges of the graph

This question is not clear. What is the graph variable? What do you meant by wanting to "check"? What do you mean by "coloring is correct"? Please take a look at stackoverflow.com/help/how-to-ask and stackoverflow.com/help/mcve. These pages may help you formulate the questions better. — zvone
Cool, it is now clear what you are asking :) However, it is still not clear where your problem lies. Now you need to go through the nodes again and compare them with their adjacent nodes. — zvone

abc abc · Accepted Answer · 2019-01-20T14:09:36

For the first part you can directly use random.choices()

def approx_color(graph):
    colors = [1,2,3,4,5,6,7,8,9]
    s_c = random.choices(colors, k=graph.order())
    colored = dict(zip(graph.nodes(), s_c))

A graph coloring is correct if no two adjacent vertices are of the same color. So you just have to iterate over the nodes and check their neighbors.
So you can just define a function that check for the condition to be valid.

for u in graph.nodes():
    for v in graph.neighbors(u):
        if colored[u] == colored[v]:
            return False
return True

Check if a random graph coloring is correct (Python)

1 Answers