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

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.

See Also:

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

See Also:

Algorithm.init(Graph)

defaultMessage

public java.lang.String defaultMessage()