org.graphstream.algorithm.coloring

## Class WelshPowell

• java.lang.Object
• org.graphstream.algorithm.coloring.WelshPowell
• All Implemented Interfaces:
Algorithm

```public class WelshPowell
extends java.lang.Object
implements Algorithm```
Welsh Powell static graph coloring 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 attribute name.

## Example

import java.io.IOException; import java.io.StringReader; import org.graphstream.algorithm.coloring.WelshPowell; import org.graphstream.graph.ElementNotFoundException; import org.graphstream.graph.Graph; import org.graphstream.graph.Node; import org.graphstream.graph.implementations.DefaultGraph; import org.graphstream.stream.GraphParseException; import org.graphstream.stream.file.FileSourceDGS; public class WelshPowellTest { // B-(1)-C // / \ // (1) (10) // / \ // A F // \ / // (1) (1) // \ / // D-(1)-E static String my_graph = "DGS004\n" + "my 0 0\n" + "an A \n" + "an B \n" + "an C \n" + "an D \n" + "an E \n" + "an F \n" + "ae AB A B weight:1 \n" + "ae AD A D weight:1 \n" + "ae BC B C weight:1 \n" + "ae CF C F weight:10 \n" + "ae DE D E weight:1 \n" + "ae EF E F weight:1 \n" ; public static void main(String[] args) throws IOException, ElementNotFoundException, GraphParseException { Graph graph = new DefaultGraph("Welsh Powell Test"); StringReader reader = new StringReader(my_graph); FileSourceDGS source = new FileSourceDGS(); source.addSink(graph); source.readAll(reader); WelshPowell wp = new WelshPowell("color"); wp.init(graph); wp.compute(); System.out.println("The chromatic number of this graph is : "+wp. getChromaticNumber()); for(Node n : graph){ System.out.println("Node "+n.getId()+ " : color " +n.getAttribute("color")); } } } 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
```

## Extra Feature

Consider you what to display the result of they coloring algorithm on a displayed graph, then adding the following code to the previous example may help you:

``` Color[] cols = new Color[wp.getChromaticNumber()];
for (int i = 0; i < wp.getChromaticNumber(); i++) {
cols[i] = Color.getHSBColor((float) (Math.random()), 0.8f, 0.9f);
}
for (Node n : graph) {
int col = (int) n.getNumber("color");
n.addAttribute("ui.style", "fill-color:rgba(" + cols[col].getRed() + ","
+ cols[col].getGreen() + "," + cols[col].getBlue() + ",200);");
}

graph.display();
```
Version:
0.1 30/08/2007
Author:
Frédéric Guinand, Antoine Dutot, Yoann Pigné
Computational Complexity:
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.
Scientific Reference:
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
• ### Constructor Summary

Constructors
Constructor and Description
`WelshPowell()`
New Welsh and Powell coloring algorithm, using "WelshPowell.color" as the attribute name.
`WelshPowell(java.lang.String attrName)`
New Welsh and Powell coloring algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Run the algorithm.
`java.lang.String` `defaultMessage()`
`int` `getChromaticNumber()`
Return the last computed result of the algorithm.
`void` `init(org.graphstream.graph.Graph g)`
Initialization of the algorithm.
`void` `setAttributeName(java.lang.String attrName)`
Set the name of the attribute to put in the graph if it is modified.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### WelshPowell

`public WelshPowell(java.lang.String attrName)`
New Welsh and Powell coloring algorithm.
Parameters:
`attrName` - name of the attribute corresponding to the color allocated by this algorithm.
• #### WelshPowell

`public WelshPowell()`
New Welsh and Powell coloring algorithm, using "WelshPowell.color" as the attribute name.
• ### Method Detail

• #### getChromaticNumber

`public int getChromaticNumber()`
Return the last computed result of the algorithm.
Returns:
The number of colors.
`compute()`
• #### setAttributeName

`public void setAttributeName(java.lang.String attrName)`
Set the name of the attribute to put in the graph if it is modified.
Parameters:
`attrName` - An attribute name.
• #### init

`public void init(org.graphstream.graph.Graph g)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`g` - The graph this algorithm is using.
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
`Algorithm.init(Graph)`
`public java.lang.String defaultMessage()`