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; 033 034import java.util.ArrayList; 035import java.util.Collections; 036import java.util.Comparator; 037import java.util.Iterator; 038import java.util.LinkedList; 039import java.util.List; 040 041import org.graphstream.algorithm.util.DisjointSets; 042import org.graphstream.graph.Edge; 043import org.graphstream.graph.Node; 044 045/** 046 * Compute a spanning tree using the Kruskal algorithm. 047 * 048 * <p> 049 * Kruskal's algorithm is a greedy algorithm which allows to find a minimal 050 * spanning tree in a weighted connected graph. More informations on <a 051 * href="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm">Wikipedia</a>. 052 * </p> 053 * 054 * <h2>Example</h2> 055 * 056 * The following example generates a graph with the Dorogovtsev-Mendes generator 057 * and then computes a spanning-tree using the Kruskal algorithm. The generator 058 * creates random weights for edges that will be used by the Kruskal algorithm. 059 * 060 * If no weight is present, algorithm considers that all weights are set to 1. 061 * 062 * When an edge is in the spanning tree, the algorithm will set its "ui.class" 063 * attribute to "intree", else the attribute is set to "notintree". According to 064 * the css stylesheet that is defined, spanning will be displayed with thick 065 * black lines while edges not in the spanning tree will be displayed with thin 066 * gray lines. 067 * 068 * <pre> 069 * import org.graphstream.graph.Graph; 070 * import org.graphstream.graph.implementations.DefaultGraph; 071 * 072 * import org.graphstream.algorithm.Kruskal; 073 * import org.graphstream.algorithm.generator.DorogovtsevMendesGenerator; 074 * 075 * public class KruskalTest { 076 * 077 * public static void main(String .. args) { 078 * DorogovtsevMendesGenerator gen = new DorogovtsevMendesGenerator(); 079 * Graph graph = new DefaultGraph("Kruskal Test"); 080 * 081 * String css = "edge .notintree {size:1px;fill-color:gray;} " + 082 * "edge .intree {size:3px;fill-color:black;}"; 083 * 084 * graph.addAttribute("ui.stylesheet", css); 085 * graph.display(); 086 * 087 * gen.addEdgeAttribute("weight"); 088 * gen.setEdgeAttributesRange(1, 100); 089 * gen.addSink(graph); 090 * gen.begin(); 091 * for (int i = 0; i < 100 && gen.nextEvents(); i++) 092 * ; 093 * gen.end(); 094 * 095 * Kruskal kruskal = new Kruskal("ui.class", "intree", "notintree"); 096 * 097 * kruskal.init(g); 098 * kruskal.compute(); 099 * } 100 * } 101 * </pre> 102 * 103 * @complexity O(m log n) where m is the number of edges and n is the number of 104 * nodes of the graph 105 * @reference Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph 106 * and the Traveling Salesman Problem. In: Proceedings of the 107 * American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50 108 * @see org.graphstream.algorithm.AbstractSpanningTree 109 * 110 */ 111public class Kruskal extends AbstractSpanningTree { 112 /** 113 * Default weight attribute 114 */ 115 public static final String DEFAULT_WEIGHT_ATTRIBUTE = "weight"; 116 117 /** 118 * Attribute where the weights of the edges are stored 119 */ 120 protected String weightAttribute; 121 122 /** 123 * List of the tree edges. Used by the iterator. 124 */ 125 protected List<Edge> treeEdges; 126 127 /** 128 * The weight of the spanning tree 129 */ 130 protected double treeWeight; 131 132 /** 133 * Create a new Kruskal's algorithm. Uses the default weight attribute and 134 * does not tag the edges. 135 */ 136 public Kruskal() { 137 this(DEFAULT_WEIGHT_ATTRIBUTE, null); 138 } 139 140 /** 141 * Create a new Kruskal's algorithm. The value of the flag attribute is 142 * {@code true} for the tree edges and false for the non-tree edges. 143 * 144 * @param weightAttribute 145 * attribute used to compare edges 146 * @param flagAttribute 147 * attribute used to set if an edge is in the spanning tree 148 */ 149 public Kruskal(String weightAttribute, String flagAttribute) { 150 this(weightAttribute, flagAttribute, true, false); 151 } 152 153 /** 154 * Create a new Kruskal's algorithm. Uses the default weight attribute. 155 * 156 * @param flagAttribute 157 * attribute used to set if an edge is in the spanning tree 158 * @param flagOn 159 * value of the <i>flagAttribute</i> if edge is in the spanning 160 * tree 161 * @param flagOff 162 * value of the <i>flagAttribute</i> if edge is not in the 163 * spanning tree 164 */ 165 public Kruskal(String flagAttribute, Object flagOn, Object flagOff) { 166 this(DEFAULT_WEIGHT_ATTRIBUTE, flagAttribute, flagOn, flagOff); 167 } 168 169 /** 170 * Create a new Kruskal's algorithm. 171 * 172 * @param weightAttribute 173 * attribute used to compare edges 174 * @param flagAttribute 175 * attribute used to set if an edge is in the spanning tree 176 * @param flagOn 177 * value of the <i>flagAttribute</i> if edge is in the spanning 178 * tree 179 * @param flagOff 180 * value of the <i>flagAttribute</i> if edge is not in the 181 * spanning tree 182 */ 183 public Kruskal(String weightAttribute, String flagAttribute, Object flagOn, 184 Object flagOff) { 185 super(flagAttribute, flagOn, flagOff); 186 187 this.weightAttribute = weightAttribute; 188 } 189 190 /** 191 * Get weight attribute used to compare edges. 192 * 193 * @return weight attribute 194 */ 195 public String getWeightAttribute() { 196 return weightAttribute; 197 } 198 199 /** 200 * Set the weight attribute. 201 * 202 * @param newWeightAttribute 203 * new attribute used 204 */ 205 public void setWeightAttribute(String newWeightAttribute) { 206 this.weightAttribute = newWeightAttribute; 207 } 208 209 @Override 210 protected void makeTree() { 211 if (treeEdges == null) 212 treeEdges = new LinkedList<Edge>(); 213 else 214 treeEdges.clear(); 215 216 List<Edge> sortedEdges = new ArrayList<Edge>(graph.getEdgeSet()); 217 Collections.sort(sortedEdges, new EdgeComparator()); 218 219 DisjointSets<Node> components = new DisjointSets<Node>( 220 graph.getNodeCount()); 221 for (Node node : graph) 222 components.add(node); 223 224 treeWeight = 0; 225 for (Edge edge : sortedEdges) 226 if (components.union(edge.getNode0(), edge.getNode1())) { 227 treeEdges.add(edge); 228 edgeOn(edge); 229 treeWeight += getWeight(edge); 230 if (treeEdges.size() == graph.getNodeCount() - 1) 231 break; 232 } 233 sortedEdges.clear(); 234 components.clear(); 235 } 236 237 @Override 238 public <T extends Edge> Iterator<T> getTreeEdgesIterator() { 239 return new TreeIterator<T>(); 240 } 241 242 @Override 243 public void clear() { 244 super.clear(); 245 treeEdges.clear(); 246 } 247 248 /** 249 * Returns the total weight of the minimum spanning tree 250 * 251 * @return The sum of the weights of the edges in the spanning tree 252 */ 253 public double getTreeWeight() { 254 return treeWeight; 255 } 256 257 // helpers 258 259 protected double getWeight(Edge e) { 260 if (weightAttribute == null) 261 return 1.0; 262 double w = e.getNumber(weightAttribute); 263 if (Double.isNaN(w)) 264 return 1; 265 return w; 266 } 267 268 protected class EdgeComparator implements Comparator<Edge> { 269 public int compare(Edge arg0, Edge arg1) { 270 double w0 = getWeight(arg0); 271 double w1 = getWeight(arg1); 272 if (w0 < w1) 273 return -1; 274 if (w0 > w1) 275 return 1; 276 return 0; 277 } 278 } 279 280 protected class TreeIterator<T extends Edge> implements Iterator<T> { 281 282 protected Iterator<Edge> it = treeEdges.iterator(); 283 284 public boolean hasNext() { 285 return it.hasNext(); 286 } 287 288 @SuppressWarnings("unchecked") 289 public T next() { 290 return (T) it.next(); 291 } 292 293 public void remove() { 294 throw new UnsupportedOperationException( 295 "This iterator does not support remove."); 296 } 297 } 298}