org.graphstream.algorithm.coloring
Class WelshPowell

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

public class WelshPowell
extends 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:

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 #getLastComputedResult() 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
WelshPowell()
          New Welsh and Powell coloring algorithm, using "WelshPowell.color" as the attribute name.
WelshPowell(String attrName)
          New Welsh and Powell coloring algorithm.
 
Method Summary
 void compute()
          Run the algorithm.
 int getChromaticNumber()
          Return the last computed result of the algorithm.
 void init(org.graphstream.graph.Graph g)
          Initialization of the algorithm.
 void setAttributeName(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(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(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)


Copyright © 2011. All Rights Reserved.