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}