Graph Coloring using Greedy method in Python

In this tutorial, we will learn about the Welsh Powell algorithm, Graph Coloring using the Greedy method in Python. We are given a graph we have to find out the minimum number of colors required to color the graph (also called chromatic number). The vertex coloring follows the rule that no two adjacent vertices can have the same color. Our task is to color the graph with a minimum number of colors.

Algorithm for Graph Coloring using Greedy method

Steps:

1: Sort the graph in descending order i.e. vertices with the most neighbors come first.

2. Pick a vertex and mark the colors of the neighboring vertices as unavailable and assign the chosen vertex the least possible available color.

3. Color the Graph accordingly.

An example where we have to apply graph coloring on a given undirected graph

We will demonstrate Graph Coloring using the Greedy method with the help of this example:

Consider the following graph:

graph = { "a" : ["c", "d", "b"], "b" : ["c", "e", "a"], "c" : ["a", "b"], "d" : ["a","e"], "e" : ["d", "b"], }

Here the vertex is written on the LHS and its adjacent vertices are written as key values. In “a” : [“c”, “d”, “b”], “a” is the vertex and the vertices “c”, “b” and “d” are the adjacent vertices or the neighbouring vertices.

We pick up the vertex “a” and mark all its neighboring vertices’ color as unavailable and give “a” the color 0 (i have chosen 0 to blue) and then move to the next vertex and similarly mark the color of its neighboring vertices as unavailable and choose the lowest available color and assign it.

Finally, b is assigned the color 1 (let color 1 be green), c is assigned the color 2 (let color 2 be orange), d is assigned the color 1 (green) and e is assigned the color 0 (blue).

 

The Colored Graph after applying the Graph Coloring algorithm:

Code:

def colour_vertices(graph):


  vertices = sorted((list(graph.keys())))
  colour_graph = {}

  for vertex in vertices:
    unused_colours = len(vertices) * [True]

    for neighbor in graph[vertex]:
      if neighbor in colour_graph:
        colour = colour_graph[neighbor]
        unused_colours[colour] = False
    for colour, unused in enumerate(unused_colours):
      if unused:
        colour_graph[vertex] = colour
        break

  return colour_graph




graph = { "a" : ["c", "d", "b"],
          "b" : ["c", "e", "a"],
          "c" : ["a", "b"],
          "d" : ["a","e"],
          "e" : ["d", "b"],
         }
result = (colour_vertices(graph))
print(result)

Output:

{'a': 0, 'b': 1, 'c': 2, 'd': 1, 'e': 0}

So, you have to color vertices a and e with color 0, vertices b and d with color 1, and vertex c with color 2.

Also Read: Create A Discord Webhook in Python for a bot