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();
Modifier and Type | Field and Description |
---|---|
protected String |
attrName
Name of the attributes added to the graph.
|
protected int |
chromaticNumber
The algorithm's result : the chromatic number.
|
protected Graph |
g
The graph.
|
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(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.
|
protected int chromaticNumber
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(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)
WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses