public class WelshPowell extends Object implements 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
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.
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 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();
Constructor and Description |
---|
WelshPowell()
New Welsh and Powell coloring algorithm, using "WelshPowell.color" as the
attribute name.
|
WelshPowell(String attrName)
New Welsh and Powell coloring algorithm.
|
Modifier and Type | Method and Description |
---|---|
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.
|
public WelshPowell(String attrName)
attrName
- name of the attribute corresponding to the color allocated by
this algorithm.public WelshPowell()
public int getChromaticNumber()
compute()
public void setAttributeName(String attrName)
attrName
- An attribute name.public void init(org.graphstream.graph.Graph g)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
Copyright © 2015. All rights reserved.