The Welsh-Powell Algorithm
This class is intended to implement the Welsh-Powell algorithm for the problem of graph coloring. It provides a greedy algorithm that runs on a static graph.
This is an iterative greedy algorithm:
- Step 1: All vertices are sorted according to the decreasing value of their degree in a list V.
- Step 2: Colors are ordered in a list C.
- Step 3: The first non colored vertex v in V is colored with the first available color in C. available means a color that was not previously used by the algorithm.
- Step 4: The remaining part of the ordered list V is traversed and the same color is allocated to every vertex for which no adjacent vertex has the same color.
- Step 5: Steps 3 and 4 are applied iteratively until all the vertices have been colored.
Note that the given colors are not real colors. Instead they are positive integers starting 0. So, for instance, if a colored graph’s chromatic number is 3, then nodes will be “colored” with one of 0, 1 or 2.
After computation using
compute(), the algorithm result for the
computation, the chromatic number, is accessible with the
getChromaticNumber() method. Colors (of “Integer” type) are stored in the graph as attributes (one for each node).
By default the attribute name is “WelshPowell.color”, but you can optional choose the
This shall return:
The chromatic number of this graph is : 3 Node D : color 0 Node E : color 2 Node F : color 1 Node A : color 2 Node B : color 1 Node C : color 0
Consider you what to display the result of the coloring algorithm on a displayed graph, then adding the following code to the previous example may help you:
This algorithm is known to use at most d(G)+1 colors where d(G) represents the largest value of the degree in the graph G.
- Welsh, D. J. A.; Powell, M. B. (1967), “An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal 10 (1): 85–86, doi:10.1093/comjnl/10.1.85