The CyMeAlg Software (Release 0.01)
scc.h
Go to the documentation of this file.
1 /// @addtogroup cymealg
2 /// @{
3 
4 /////////////////////////////////////////////////////////////////////////////
5 ///
6 /// @file
7 ///
8 /// This header file contains the implementation of two algorithms
9 /// for the computation of strongly connected path components of a digraph.
10 ///
11 /// @author Pawel Pilarczyk
12 ///
13 /////////////////////////////////////////////////////////////////////////////
14 
15 // Copyright (C) 1997-2020 by Pawel Pilarczyk.
16 //
17 // This file is part of my research software. This is free software:
18 // you can redistribute it and/or modify it under the terms of the GNU
19 // General Public License as published by the Free Software Foundation,
20 // either version 3 of the License, or (at your option) any later version.
21 //
22 // This software is distributed in the hope that it will be useful,
23 // but WITHOUT ANY WARRANTY; without even the implied warranty of
24 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 // GNU General Public License for more details.
26 //
27 // You should have received a copy of the GNU General Public License
28 // along with this software; see the file "license.txt". If not,
29 // please, see <http://www.gnu.org/licenses/>.
30 
31 // Started in January 2006. Last revision: August 23, 2019.
32 
33 
34 #ifndef _CYMEALG_SCC_H_
35 #define _CYMEALG_SCC_H_
36 
37 // include selected standard library header files
38 #include <stack>
39 #include <vector>
40 
41 // include selected header files from the CHomP library
42 #include "chomp/system/config.h"
43 #include "chomp/struct/bitfield.h"
44 
45 // include selected CyMeAlg header files
46 #include "cymealg/transpose.h"
47 #include "cymealg/dfs.h"
48 
49 namespace cymealg {
50 
51 /// Computes strongly connected path components of the graph 'g'. Creates
52 /// the graph 'scc' in which each vertex corresponds to one component.
53 /// The graph 'scc' given as an argument must be initially empty.
54 /// The table 'compVertices' is filled with the numbers of vertices in 'g'
55 /// which form the components, and the indices that end the listing
56 /// for each component are stored in the table 'compEnds'.
57 /// Returns the number of strongly connected components found.
58 template <class wType, class Table1, class Table2>
59 inline int_t SCC (const diGraph<wType> &g, Table1 &compVertices,
60  Table2 &compEnds, diGraph<wType> *scc = 0,
61  diGraph<wType> *transposed = 0, bool copyweights = false)
62 {
63  // prepare two tables
64  int_t nVert = g. countVertices ();
65  int_t *ordered = new int_t [nVert];
66  int_t *tab = new int_t [nVert];
67 
68  // compute the list of vertices in the descending finishing time
69  g. DFSfinishTime (tab);
70  for (int_t i = 0; i < nVert; ++ i)
71  ordered [nVert - tab [i]] = i;
72  delete [] tab;
73 
74  // create the transposed graph
75  diGraph<wType> gT;
76  if (!transposed)
77  transposed = &gT;
78  transpose (g, *transposed, copyweights);
79 
80  // extract the DFS forest of gT in the given order of vertices
81  int_t n = DFSforest (*transposed, ordered, compVertices, compEnds,
82  true, scc);
83 
84  // cleanup memory and return the number of components
85  delete [] ordered;
86  return n;
87 } /* SCC */
88 
89 // --------------------------------------------------
90 
91 /// Computes strongly connected components of the graph 'g'
92 /// using Tarjan's algorithm (as described in the Wikipedia).
93 /// Tha advantage of this approach over the one described in Cormen's
94 /// textbook is that the transposed graph need not be computed.
95 /// However, this algorithm might be slightly slower than the other one.
96 /// The table 'compVertices' is filled with the numbers of vertices in 'g'
97 /// which form the components, and the indices that end the listing
98 /// for each component are stored in the table 'compEnds'.
99 /// Returns the number of strongly connected components found.
100 template <class wType, class Table1, class Table2>
101 inline int_t SCC_Tarjan (const diGraph<wType> &g, Table1 &compVertices,
102  Table2 &compEnds)
103 {
104  // return the obvious result if the graph is empty
105  int_t nVertices = g. countVertices ();
106  if (!nVertices)
107  return 0;
108 
109  // prepare an array of discovery times for all the vertices
110  // (zero == not yet discovered)
111  std::vector<int_t> dfsIndex (nVertices, 0);
112 
113  // prepare an array of the minimal index of a node reachable
114  // from each of the vertices
115  std::vector<int_t> lowLink (nVertices, 0);
116 
117  // prepare an empty stack of nodes
118  std::stack<int_t> s_nodes;
119 
120  // prepare an array of bits indicating whether the vertices are
121  // in the stack of nodes or not
122  chomp::homology::BitField inTheStack;
123  inTheStack. allocate (nVertices);
124  inTheStack. clearall (nVertices);
125 
126  // prepare the number of strongly connected components
127  int_t nComponents = 0;
128 
129  // prepare the current position in the array 'compVertices'
130  int_t posVertices = 0;
131 
132  // remember the next vertex number in the graph to scan
133  // whether this vertex has already been visited or not
134  int_t vertexToScan = 0;
135 
136  // prepare a variable for storing the discovery time in the DFS
137  int_t discoveryTime = 0;
138 
139  // prepare stacks for the DFS recursion
140  std::stack<int_t> s_vertex;
141  std::stack<int_t> s_edge;
142  std::stack<int_t> s_maxedge;
143 
144  // initialize the number of the currently processed vertex
145  int_t vertex = -1;
146 
147  // initialize the range of edges to be visited
148  int_t edge = 0;
149  int_t maxedge = 0;
150 
151  while (1)
152  {
153  // return to the previous recursion level
154  // if all the edges have been checked
155  if (edge >= maxedge)
156  {
157  // extract a strongly connected component
158  if ((vertex >= 0) && (lowLink [vertex] ==
159  dfsIndex [vertex]))
160  {
161  int_t v = 0;
162  do
163  {
164  v = s_nodes. top ();
165  s_nodes. pop ();
166  inTheStack. clear (v);
167  compVertices [posVertices ++] = v;
168  } while (v != vertex);
169  compEnds [nComponents ++] = posVertices;
170  }
171 
172  // if this is the top level of the recursion
173  // then find another unvisited vertex or return
174  if (s_vertex. empty ())
175  {
176  // find an unvisited vertex in the graph
177  while ((vertexToScan < nVertices) &&
178  (dfsIndex [vertexToScan] != 0))
179  {
180  ++ vertexToScan;
181  }
182 
183  // return the result if all visited
184  if (vertexToScan == nVertices)
185  {
186  inTheStack. free ();
187  return nComponents;
188  }
189 
190  // set the new vertex
191  vertex = vertexToScan ++;
192 
193  // mark the current vertex as visited
194  // and initialize its low link
195  dfsIndex [vertex] = ++ discoveryTime;
196  lowLink [vertex] = discoveryTime;
197 
198  // push this vertex on the stack
199  s_nodes. push (vertex);
200  inTheStack. set (vertex);
201 
202  // determine the edges to be visited
203  edge = 0;
204  maxedge = g. countEdges (vertex);
205  }
206 
207  // otherwise trace back to the previous level
208  else
209  {
210  // remember the current low link index
211  int_t lowLink2 = lowLink [vertex];
212 
213  // restore the variables
214  vertex = s_vertex. top ();
215  s_vertex. pop ();
216  edge = s_edge. top ();
217  s_edge. pop ();
218  maxedge = s_maxedge. top ();
219  s_maxedge. pop ();
220 
221  // update the current low link index
222  if (lowLink [vertex] > lowLink2)
223  lowLink [vertex] = lowLink2;
224  }
225  }
226 
227  // analyse the next edge coming out from the current vertex
228  else
229  {
230  // determine the next vertex
231  int_t next = g. getEdge (vertex, edge ++);
232 
233  // go to a deeper recursion level if unvisited
234  if (dfsIndex [next] == 0)
235  {
236  // store the variables at the stacks
237  s_vertex. push (vertex);
238  s_edge. push (edge);
239  s_maxedge. push (maxedge);
240 
241  // set the new vertex
242  vertex = next;
243 
244  // mark the new vertex as visited
245  dfsIndex [vertex] = ++ discoveryTime;
246  lowLink [vertex] = discoveryTime;
247 
248  // push this vertex on the stack
249  s_nodes. push (vertex);
250  inTheStack. set (vertex);
251 
252  // determine the edges to be visited
253  edge = 0;
254  maxedge = g. countEdges (vertex);
255  }
256 
257  // update the low link index if the vertex has been
258  // visited and is currently in the stack of nodes
259  else if (inTheStack. test (next))
260  {
261  if (lowLink [vertex] > dfsIndex [next])
262  lowLink [vertex] = dfsIndex [next];
263  }
264  }
265  }
266 
267  // finalize and return the number of strongly connected components
268  inTheStack. free ();
269  return nComponents;
270 } /* SCC_Tarjan */
271 
272 
273 } // namespace cymealg
274 
275 #endif // _CYMEALG_SCC_H_
276 
277 /// @}
278 
void transpose(const Graph1 &g, Graph2 &result, bool copyweights=false)
Creates a transposed graph.
Definition: transpose.h:43
This header file contains a procedure for computing the transpose graph.
This class defines a weighted directed graph with very limited number of operations.
Definition: digraph.h:75
This header file contains several procedures directly related to the DFS algorithm.
void DFSfinishTime(const Graph &g, Table &tab)
Computes the DFS finishing time for each vertex.
Definition: dfs.h:63
int_t SCC(const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds, diGraph< wType > *scc=0, diGraph< wType > *transposed=0, bool copyweights=false)
Computes strongly connected path components of the graph &#39;g&#39;.
Definition: scc.h:59
int_t SCC_Tarjan(const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds)
Computes strongly connected components of the graph &#39;g&#39; using Tarjan&#39;s algorithm (as described in the...
Definition: scc.h:101
int_t DFSforest(const Graph &g, const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, Graph *sccGraph=0)
Computes the DFS forest.
Definition: dfs.h:104