001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.algorithm.coloring; 033 034import java.util.LinkedList; 035 036import org.graphstream.algorithm.Algorithm; 037import org.graphstream.algorithm.util.FibonacciHeap; 038import org.graphstream.graph.Graph; 039import org.graphstream.graph.Node; 040 041/** 042 * Welsh Powell static graph coloring algorithm. 043 * 044 * <p> 045 * This class is intended to implement the Welsh-Powell algorithm for the 046 * problem of graph coloring. It provides a greedy algorithm that runs on a 047 * static graph. 048 * </p> 049 * 050 * <p> 051 * This is an iterative greedy algorithm: 052 * <ul> 053 * <li>Step 1: All vertices are sorted according to the decreasing value of 054 * their degree in a list V. 055 * <li>Step 2: Colors are ordered in a list C. 056 * <li>Step 3: The first non colored vertex v in V is colored with the first 057 * available color in C. <i>available</i> means a color that was not previously 058 * used by the algorithm. 059 * <li>Step 4: The remaining part of the ordered list V is traversed and the 060 * same color is allocated to every vertex for which no adjacent vertex has the 061 * same color. 062 * <li>Step 5: Steps 3 and 4 are applied iteratively until all the vertices have 063 * been colored. 064 * </ul> 065 * <p> 066 * 067 * <p> 068 * Note that the given colors are not real colors. Instead they are positive 069 * integers starting 0. So, for instance, if a colored graph's chromatic number 070 * is 3, then nodes will be "colored" with one of 0, 1 or 2. 071 * </p> 072 * 073 * 074 * <p> 075 * After computation (using {@link #compute()}, the algorithm result for the 076 * computation, the chromatic number, is accessible with the 077 * {@link #getChromaticNumber()} method. Colors (of "Integer" type) are stored 078 * in the graph as attributes (one for each node). By default the attribute name 079 * is "WelshPowell.color", but you can optional choose the attribute name. 080 * </p> 081 * 082 * 083 * 084 * <h2>Example</h2> import java.io.IOException; import java.io.StringReader; 085 * 086 * import org.graphstream.algorithm.coloring.WelshPowell; import 087 * org.graphstream.graph.ElementNotFoundException; import 088 * org.graphstream.graph.Graph; import org.graphstream.graph.Node; import 089 * org.graphstream.graph.implementations.DefaultGraph; import 090 * org.graphstream.stream.GraphParseException; import 091 * org.graphstream.stream.file.FileSourceDGS; 092 * 093 * public class WelshPowellTest { // B-(1)-C // / \ // (1) (10) // / \ // A F // 094 * \ / // (1) (1) // \ / // D-(1)-E static String my_graph = "DGS004\n" + 095 * "my 0 0\n" + "an A \n" + "an B \n" + "an C \n" + "an D \n" + "an E \n" + 096 * "an F \n" + "ae AB A B weight:1 \n" + "ae AD A D weight:1 \n" + 097 * "ae BC B C weight:1 \n" + "ae CF C F weight:10 \n" + "ae DE D E weight:1 \n" 098 * + "ae EF E F weight:1 \n" ; public static void main(String[] args) throws 099 * IOException, ElementNotFoundException, GraphParseException { Graph graph = 100 * new DefaultGraph("Welsh Powell Test"); StringReader reader = new 101 * StringReader(my_graph); 102 * 103 * FileSourceDGS source = new FileSourceDGS(); source.addSink(graph); 104 * source.readAll(reader); 105 * 106 * WelshPowell wp = new WelshPowell("color"); wp.init(graph); wp.compute(); 107 * 108 * System.out.println("The chromatic number of this graph is : "+wp. 109 * getChromaticNumber()); for(Node n : graph){ 110 * System.out.println("Node "+n.getId()+ " : color " +n.getAttribute("color")); 111 * } } } </pre> 112 * 113 * This shall return: 114 * 115 * <pre> 116 * The chromatic number of this graph is : 3 117 * Node D : color 0 118 * Node E : color 2 119 * Node F : color 1 120 * Node A : color 2 121 * Node B : color 1 122 * Node C : color 0 123 * </pre> 124 * 125 * 126 * <h2>Extra Feature</h2> 127 * 128 * <p> 129 * Consider you what to display the result of they coloring algorithm on a 130 * displayed graph, then adding the following code to the previous example may 131 * help you: 132 * </p> 133 * 134 * <pre> 135 * Color[] cols = new Color[wp.getChromaticNumber()]; 136 * for (int i = 0; i < wp.getChromaticNumber(); i++) { 137 * cols[i] = Color.getHSBColor((float) (Math.random()), 0.8f, 0.9f); 138 * } 139 * for (Node n : graph) { 140 * int col = (int) n.getNumber("color"); 141 * n.addAttribute("ui.style", "fill-color:rgba(" + cols[col].getRed() + "," 142 * + cols[col].getGreen() + "," + cols[col].getBlue() + ",200);"); 143 * } 144 * 145 * graph.display(); 146 * </pre> 147 * 148 * 149 * 150 * @complexity This algorithm is known to use at most d(G)+1 colors where d(G) 151 * represents the largest value of the degree in the graph G. 152 * 153 * @reference Welsh, D. J. A.; Powell, M. B. (1967), 154 * "An upper bound for the chromatic number of a graph and its application to timetabling problems" 155 * , The Computer Journal 10 (1): 85–86, doi:10.1093/comjnl/10.1.85 156 * 157 * @version 0.1 30/08/2007 158 * @author Frédéric Guinand 159 * @author Antoine Dutot 160 * @author Yoann Pigné 161 */ 162public class WelshPowell implements Algorithm { 163 164 /** 165 * Name of the attributes added to the graph. 166 */ 167 protected String attrName = "WelshPowell.color"; 168 169 /** 170 * The graph. 171 */ 172 protected Graph g; 173 174 /** 175 * The algorithm's result : the chromatic number. 176 */ 177 protected int chromaticNumber; 178 179 // Constructors 180 181 /** 182 * New Welsh and Powell coloring algorithm. 183 * 184 * @param attrName 185 * name of the attribute corresponding to the color allocated by 186 * this algorithm. 187 */ 188 public WelshPowell(String attrName) { 189 this.attrName = attrName; 190 } 191 192 /** 193 * New Welsh and Powell coloring algorithm, using "WelshPowell.color" as the 194 * attribute name. 195 * 196 */ 197 public WelshPowell() { 198 } 199 200 // Accessors 201 202 /** 203 * Return the last computed result of the algorithm. 204 * 205 * @return The number of colors. 206 * @see #compute() 207 */ 208 public int getChromaticNumber() { 209 return chromaticNumber; 210 } 211 212 // Commands 213 214 /** 215 * Set the name of the attribute to put in the graph if it is modified. 216 * 217 * @param attrName 218 * An attribute name. 219 */ 220 public void setAttributeName(String attrName) { 221 this.attrName = attrName; 222 } 223 224 /* 225 * (non-Javadoc) 226 * 227 * @see 228 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 229 */ 230 public void init(Graph g) { 231 this.g = g; 232 } 233 234 /* 235 * (non-Javadoc) 236 * 237 * @see org.graphstream.algorithm.Algorithm#compute() 238 */ 239 public void compute() { 240 String attributeName = "WelshPowell.color"; 241 242 if (attrName != null) 243 attributeName = attrName; 244 245 // ------- STEP 1 ----------- 246 // the algorithm requires the use of a sorted list using 247 // degree values for sorting them. 248 249 LinkedList<Node> sortedNodes = new LinkedList<Node>(); 250 FibonacciHeap<Integer, Node> heap = new FibonacciHeap<Integer, Node>(); 251 252 for (int i = 0; i < g.getNodeCount(); i++) { 253 Node n = g.getNode(i); 254 heap.add(n.getDegree(), n); 255 } 256 257 while (!heap.isEmpty()) 258 sortedNodes.addFirst(heap.extractMin()); 259 260 heap = null; 261 262 // ------ STEP 2 -------- 263 // color initialization 264 265 int nbColors = 0; 266 267 // ------- STEP 3 -------- 268 269 while (sortedNodes.size() > 0) { 270 Node root = sortedNodes.poll(); 271 LinkedList<Node> myGroup = new LinkedList<Node>(); 272 myGroup.add(root); 273 274 root.addAttribute(attributeName, nbColors); 275 276 for (int i = 0; i < sortedNodes.size();) { 277 Node p = sortedNodes.get(i); 278 boolean conflict = false; 279 280 for (int j = 0; !conflict && j < myGroup.size(); j++) 281 conflict = p.getEdgeBetween(myGroup.get(j).getIndex()) != null; 282 283 if (conflict) 284 i++; 285 else { 286 p.addAttribute(attributeName, nbColors); 287 myGroup.add(p); 288 sortedNodes.remove(i); 289 } 290 } 291 292 myGroup.clear(); 293 nbColors++; 294 } 295 296 chromaticNumber = nbColors; 297 } 298}