34 #ifndef _CYMEALG_SCC_H_ 35 #define _CYMEALG_SCC_H_ 42 #include "chomp/system/config.h" 43 #include "chomp/struct/bitfield.h" 58 template <
class wType,
class Table1,
class Table2>
64 int_t nVert = g. countVertices ();
65 int_t *ordered =
new int_t [nVert];
66 int_t *tab =
new int_t [nVert];
70 for (int_t i = 0; i < nVert; ++ i)
71 ordered [nVert - tab [i]] = i;
81 int_t n =
DFSforest (*transposed, ordered, compVertices, compEnds,
100 template <
class wType,
class Table1,
class Table2>
105 int_t nVertices = g. countVertices ();
111 std::vector<int_t> dfsIndex (nVertices, 0);
115 std::vector<int_t> lowLink (nVertices, 0);
118 std::stack<int_t> s_nodes;
122 chomp::homology::BitField inTheStack;
123 inTheStack. allocate (nVertices);
124 inTheStack. clearall (nVertices);
127 int_t nComponents = 0;
130 int_t posVertices = 0;
134 int_t vertexToScan = 0;
137 int_t discoveryTime = 0;
140 std::stack<int_t> s_vertex;
141 std::stack<int_t> s_edge;
142 std::stack<int_t> s_maxedge;
158 if ((vertex >= 0) && (lowLink [vertex] ==
166 inTheStack. clear (v);
167 compVertices [posVertices ++] = v;
168 }
while (v != vertex);
169 compEnds [nComponents ++] = posVertices;
174 if (s_vertex. empty ())
177 while ((vertexToScan < nVertices) &&
178 (dfsIndex [vertexToScan] != 0))
184 if (vertexToScan == nVertices)
191 vertex = vertexToScan ++;
195 dfsIndex [vertex] = ++ discoveryTime;
196 lowLink [vertex] = discoveryTime;
199 s_nodes. push (vertex);
200 inTheStack.
set (vertex);
204 maxedge = g. countEdges (vertex);
211 int_t lowLink2 = lowLink [vertex];
214 vertex = s_vertex. top ();
216 edge = s_edge. top ();
218 maxedge = s_maxedge. top ();
222 if (lowLink [vertex] > lowLink2)
223 lowLink [vertex] = lowLink2;
231 int_t next = g. getEdge (vertex, edge ++);
234 if (dfsIndex [next] == 0)
237 s_vertex. push (vertex);
239 s_maxedge. push (maxedge);
245 dfsIndex [vertex] = ++ discoveryTime;
246 lowLink [vertex] = discoveryTime;
249 s_nodes. push (vertex);
250 inTheStack.
set (vertex);
254 maxedge = g. countEdges (vertex);
259 else if (inTheStack. test (next))
261 if (lowLink [vertex] > dfsIndex [next])
262 lowLink [vertex] = dfsIndex [next];
275 #endif // _CYMEALG_SCC_H_ void transpose(const Graph1 &g, Graph2 &result, bool copyweights=false)
Creates a transposed graph.
This header file contains a procedure for computing the transpose graph.
This class defines a weighted directed graph with very limited number of operations.
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.
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 'g'.
int_t SCC_Tarjan(const diGraph< wType > &g, Table1 &compVertices, Table2 &compEnds)
Computes strongly connected components of the graph 'g' using Tarjan's algorithm (as described in the...
int_t DFSforest(const Graph &g, const Table1 &ordered, Table2 &compVertices, Table3 &compEnds, bool nontrivial=false, Graph *sccGraph=0)
Computes the DFS forest.