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.LinkedList; 035 036import org.graphstream.algorithm.util.FibonacciHeap; 037import org.graphstream.graph.Edge; 038import org.graphstream.graph.Node; 039 040/** 041 * Compute a spanning tree using the Prim algorithm. 042 * 043 * <p> 044 * Prim's algorithm is an algorithm which allows to find a minimal spanning tree 045 * in a weighted connected graph. More informations on <a 046 * href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Wikipedia</a>. 047 * </p> 048 * 049 * <h2>Example</h2> 050 * 051 * The following example generates a graph with the Dorogovtsev-Mendes generator 052 * and then compute a spanning-tree using the Prim algorithm. The generator 053 * creates random weights for edges that will be used by the Prim algorithm. 054 * 055 * If no weight is present, algorithm considers that all weights are set to 1. 056 * 057 * When an edge is in the spanning tree, the algorithm will set its "ui.class" 058 * attribute to "intree", else the attribute is set to "notintree". According to 059 * the css stylesheet that is defined, spanning will be displayed with thick 060 * black lines while edges not in the spanning tree will be displayed with thin 061 * gray lines. 062 * 063 * <pre> 064 * import org.graphstream.graph.Graph; 065 * import org.graphstream.graph.implementations.DefaultGraph; 066 * 067 * import org.graphstream.algorithm.Prim; 068 * import org.graphstream.algorithm.generator.DorogovtsevMendesGenerator; 069 * 070 * public class PrimTest { 071 * 072 * public static void main(String... args) { 073 * DorogovtsevMendesGenerator gen = new DorogovtsevMendesGenerator(); 074 * Graph graph = new DefaultGraph("Prim Test"); 075 * 076 * String css = "edge .notintree {size:1px;fill-color:gray;} " 077 * + "edge .intree {size:3px;fill-color:black;}"; 078 * 079 * graph.addAttribute("ui.stylesheet", css); 080 * graph.display(); 081 * 082 * gen.addEdgeAttribute("weight"); 083 * gen.setEdgeAttributesRange(1, 100); 084 * gen.addSink(graph); 085 * gen.begin(); 086 * for (int i = 0; i < 100 && gen.nextEvents(); i++) 087 * ; 088 * gen.end(); 089 * 090 * Prim prim = new Prim("ui.class", "intree", "notintree"); 091 * 092 * prim.init(graph); 093 * prim.compute(); 094 * } 095 * } 096 * </pre> 097 * 098 * @complexity 0(m + n log n), where m is the number of edges and n is the 099 * number of nodes in the graph 100 * @reference R. C. Prim: Shortest connection networks and some generalizations. 101 * In: Bell System Technical Journal, 36 (1957), pp. 1389–1401 102 * @see org.graphstream.algorithm.AbstractSpanningTree 103 * 104 */ 105public class Prim extends Kruskal { 106 107 /** 108 * Create a new Prim's algorithm. Uses the default weight attribute and 109 * does not tag the edges. 110 */ 111 public Prim() { 112 super(); 113 } 114 115 /** 116 * Create a new Prim's algorithm. The value of the flag attribute is 117 * {@code true} for the tree edges and false for the non-tree edges. 118 * 119 * @param weightAttribute 120 * attribute used to compare edges 121 * @param flagAttribute 122 * attribute used to set if an edge is in the spanning tree 123 */ 124 public Prim(String weightAttribute, String flagAttribute) { 125 super(weightAttribute, flagAttribute); 126 } 127 128 /** 129 * Create a new Prim's algorithm. Uses the default weight attribute. 130 * 131 * @param flagAttribute 132 * attribute used to set if an edge is in the spanning tree 133 * @param flagOn 134 * value of the <i>flagAttribute</i> if edge is in the spanning 135 * tree 136 * @param flagOff 137 * value of the <i>flagAttribute</i> if edge is not in the 138 * spanning tree 139 */ 140 public Prim(String flagAttribute, Object flagOn, Object flagOff) { 141 super(flagAttribute, flagOn, flagOff); 142 } 143 144 /** 145 * Create a new Prim's algorithm. 146 * 147 * @param weightAttribute 148 * attribute used to compare edges 149 * @param flagAttribute 150 * attribute used to set if an edge is in the spanning tree 151 * @param flagOn 152 * value of the <i>flagAttribute</i> if edge is in the spanning 153 * tree 154 * @param flagOff 155 * value of the <i>flagAttribute</i> if edge is not in the 156 * spanning tree 157 */ 158 public Prim(String weightAttribute, String flagAttribute, Object flagOn, 159 Object flagOff) { 160 super(weightAttribute, flagAttribute, flagOn, flagOff); 161 } 162 163 @Override 164 protected void makeTree() { 165 if (treeEdges == null) 166 treeEdges = new LinkedList<Edge>(); 167 else 168 treeEdges.clear(); 169 170 int n = graph.getNodeCount(); 171 Data[] data = new Data[n]; 172 FibonacciHeap<Double, Node> heap = new FibonacciHeap<Double, Node>(); 173 for (int i = 0; i < n; i++) { 174 data[i] = new Data(); 175 data[i].edgeToTree = null; 176 data[i].fn = heap.add(Double.POSITIVE_INFINITY, graph.getNode(i)); 177 } 178 179 treeWeight = 0; 180 while (!heap.isEmpty()) { 181 Node u = heap.extractMin(); 182 Data dataU = data[u.getIndex()]; 183 data[u.getIndex()] = null; 184 if (dataU.edgeToTree != null) { 185 treeEdges.add(dataU.edgeToTree); 186 edgeOn(dataU.edgeToTree); 187 treeWeight += dataU.fn.getKey(); 188 dataU.edgeToTree = null; 189 } 190 dataU.fn = null; 191 for (Edge e : u) { 192 Node v = e.getOpposite(u); 193 Data dataV = data[v.getIndex()]; 194 if (dataV == null) 195 continue; 196 double w = getWeight(e); 197 if (w < dataV.fn.getKey()) { 198 heap.decreaseKey(dataV.fn, w); 199 dataV.edgeToTree = e; 200 } 201 } 202 } 203 } 204 205 protected static class Data { 206 Edge edgeToTree; 207 FibonacciHeap<Double, Node>.Node fn; 208 } 209}