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.HashMap;
035import java.util.Stack;
036
037import org.graphstream.graph.Edge;
038import org.graphstream.graph.Graph;
039import org.graphstream.graph.Node;
040
041/**
042 * Tarjan's Algorithm is a graph theory algorithm for finding the strongly
043 * connected components of a graph.
044 * 
045 * <h2>Overview from <a href=
046 * "http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm"
047 * >Wikipedia</a></h2>
048 * 
049 * <p>
050 * The algorithm takes a directed graph as input, and produces a partition of
051 * the graph's vertices into the graph's strongly connected components. Every
052 * vertex of the graph appears in a single strongly connected component, even if
053 * it means a vertex appears in a strongly connected component by itself (as is
054 * the case with tree-like parts of the graph, as well as any vertex with no
055 * successor or no predecessor).
056 * </p>
057 * 
058 * <p>
059 * The basic idea of the algorithm is this: a depth-first search begins from an
060 * arbitrary start node (and subsequent depth-first searches are conducted on
061 * any nodes that have not yet been found). The search does not explore any node
062 * that has already been explored. The strongly connected components form the
063 * subtrees of the search tree, the roots of which are the roots of the strongly
064 * connected components.
065 * </p>
066 * 
067 * <p>
068 * The nodes are placed on a stack in the order in which they are visited. When
069 * the search returns from a subtree, the nodes are taken from the stack and it
070 * is determined whether each node is the root of a strongly connected
071 * component. If a node is the root of a strongly connected component, then it
072 * and all of the nodes taken off before it form that strongly connected
073 * component.
074 * </p>
075 * 
076 * <h2>Usage</h2>
077 * 
078 * <p>
079 * This algorithm use an attribute to store the component's index of each node.
080 * This attribute can be customized using {@link #setSCCIndexAttribute(String)}.
081 * Index is generate with an index generator that can be customized using
082 * {@link #setIndexGenerator(IndexGenerator)}
083 * </p>
084 * 
085 * @reference Tarjan, R. E. (1972),
086 *            "Depth-first search and linear graph algorithms", SIAM Journal on
087 *            Computing 1 (2): 146–160, doi:10.1137/0201010
088 * @complexity O( | V | + | E | )
089 * 
090 */
091public class TarjanStronglyConnectedComponents implements Algorithm {
092
093        /**
094         * Associate some data with each node. Each node has an index and a low
095         * link.
096         */
097        protected HashMap<Node, NodeData> data;
098        /**
099         * The current index.
100         */
101        protected int index;
102        /**
103         * Stack used in computation.
104         */
105        protected Stack<Node> S;
106        /**
107         * Object used to generate component indexes.
108         */
109        protected IndexGenerator sccIndex;
110        /**
111         * Attribute key defining where component index is stored in node.
112         */
113        protected String sccAttribute;
114        /**
115         * Graph uses in computation. It is set when {@link #init(Graph)} is called.
116         */
117        protected Graph graph;
118
119        /**
120         * Build a new Tarjan algorithm.
121         */
122        public TarjanStronglyConnectedComponents() {
123                this.data = new HashMap<Node, NodeData>();
124                this.S = new Stack<Node>();
125                this.sccIndex = new IntegerIndexGenerator();
126                this.sccAttribute = "scc";
127        }
128
129        /*
130         * (non-Javadoc)
131         * 
132         * @see
133         * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph)
134         */
135        public void init(Graph graph) {
136                this.graph = graph;
137        }
138
139        /*
140         * (non-Javadoc)
141         * 
142         * @see org.graphstream.algorithm.Algorithm#compute()
143         */
144        public void compute() {
145                data.clear();
146                index = 0;
147                S.clear();
148
149                for (Node v : graph.getEachNode()) {
150                        if (!data.containsKey(v))
151                                strongConnect(v);
152                }
153        }
154
155        /**
156         * Set the generator of components indexes.
157         * 
158         * @param gen
159         *            the new generator
160         */
161        public void setIndexGenerator(IndexGenerator gen) {
162                if (gen == null)
163                        throw new NullPointerException();
164
165                this.sccIndex = gen;
166        }
167
168        /**
169         * Set the node attribute key where component index is stored.
170         * 
171         * @param key
172         *            attribute key of component index
173         */
174        public void setSCCIndexAttribute(String key) {
175                if (key == null)
176                        throw new NullPointerException();
177
178                this.sccAttribute = key;
179        }
180
181        /**
182         * Get the node attribute key where component index is stored.
183         * 
184         * @return the attribute key
185         */
186        public String getSCCIndexAttribute() {
187                return this.sccAttribute;
188        }
189
190        /**
191         * Internal method call in computation.
192         * 
193         * @param v
194         */
195        protected void strongConnect(Node v) {
196                NodeData nd = new NodeData();
197                data.put(v, nd);
198
199                nd.index = index;
200                nd.lowlink = index;
201
202                index++;
203                S.push(v);
204
205                for (Edge vw : v.getEachLeavingEdge()) {
206                        Node w = vw.getOpposite(v);
207
208                        if (!data.containsKey(w)) {
209                                strongConnect(w);
210                                nd.lowlink = Math.min(nd.lowlink, data.get(w).lowlink);
211                        } else if (S.contains(w)) {
212                                nd.lowlink = Math.min(nd.lowlink, data.get(w).index);
213                        }
214                }
215
216                if (nd.index == nd.lowlink) {
217                        Node w;
218                        Object currentSCCIndex = sccIndex.nextIndex();
219
220                        do {
221                                w = S.pop();
222                                w.setAttribute(sccAttribute, currentSCCIndex);
223                        } while (w != v);
224                }
225        }
226
227        /**
228         * Internal data associated to nodes in computation.
229         */
230        protected static class NodeData {
231                int index;
232                int lowlink;
233        }
234
235        /**
236         * Defines objects able to generator index.
237         */
238        public static interface IndexGenerator {
239                /**
240                 * Create a new index.
241                 * 
242                 * @return a new index object that has to be unique according to
243                 *         previous indexes.
244                 */
245                Object nextIndex();
246        }
247
248        /**
249         * Defines an index generator producing a sequence of integer as indexes.
250         * 
251         */
252        public static class IntegerIndexGenerator implements IndexGenerator {
253                private int index;
254
255                public IntegerIndexGenerator() {
256                        index = 0;
257                }
258
259                public Object nextIndex() {
260                        return Integer.valueOf(index++);
261                }
262        }
263}