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}