34 #ifndef _CYMEALG_VARIOUS_H_ 35 #define _CYMEALG_VARIOUS_H_ 38 #include "chomp/system/config.h" 43 template <
class wType>
45 const int_t *newNum, int_t cur, int_t *srcVert,
48 int_t nEdges = g. countEdges (vertex);
50 for (int_t edge = 0; edge < nEdges; ++ edge)
53 int_t dest = newNum [g. getEdge (vertex, edge)];
59 if (srcVert [dest] == cur)
65 result. addEdge (dest);
75 template <
class wType,
class Table1,
class Table2>
77 int_t compNum, Table1 &compVertices, Table2 &compEnds,
81 int_t nVert = g. countVertices ();
87 int_t *newNum = newNumbers ? newNumbers :
new int_t [nVert];
88 for (int_t i = 0; i < nVert; ++ i)
94 int_t posEnd = compEnds [cur];
96 newNum [compVertices [pos ++]] = cur;
99 for (int_t i = 0; i < nVert; ++ i)
107 int_t newVert = nVert - (compNum ? compEnds [compNum - 1] :
108 static_cast<int_t
> (0)) + compNum;
111 throw "DEBUG: Wrong numbers.";
112 int_t *srcVert =
new int_t [newVert];
113 for (int_t i = 0; i < newVert; ++ i)
119 while (cur < compNum)
122 result. addVertex ();
124 int_t posEnd = compEnds [cur];
128 int_t vertex = compVertices [pos ++];
136 for (int_t vertex = 0; vertex < nVert; ++ vertex)
139 if (newNum [vertex] > cur)
140 throw "DEBUG: Wrong order.";
142 if (newNum [vertex] != cur)
145 result. addVertex ();
158 template <
class wType,
class TabSets>
160 const int_t *newNum, TabSets &numSets,
163 int_t nEdges = g. countEdges (vertex);
166 for (int_t edge = 0; edge < nEdges; ++ edge)
169 int_t destNumber = newNum [g. getEdge (vertex, edge)];
172 int_t destSize = (destNumber < 0) ?
173 numSets [-destNumber]. size () :
174 static_cast<int_t
> (1);
175 for (int_t i = 0; i < destSize; ++ i)
178 int_t dest = (destNumber < 0) ?
179 numSets [-destNumber] [i] : destNumber;
187 if (srcVert [dest] == cur)
191 result. addEdge (dest);
201 template <
class wType,
class Table1,
class Table2>
203 int_t compNum, Table1 &compVertices, Table2 &compEnds,
207 int_t nVert = g. countVertices ();
215 int_t *newNum =
new int_t [nVert];
216 for (int_t i = 0; i < nVert; ++ i)
221 chomp::homology::multitable<chomp::homology::hashedset<int_t> >
228 while (cur < compNum)
230 int_t posEnd = compEnds [cur];
233 int_t number = compVertices [pos ++];
234 if (newNum [number] == -1)
235 newNum [number] = cur;
236 else if (newNum [number] < 0)
237 numSets [-newNum [number]]. add (cur);
240 numSets [numSetCur]. add (newNum [number]);
241 numSets [numSetCur]. add (cur);
242 newNum [number] = -(numSetCur ++);
247 for (int_t i = 0; i < nVert; ++ i)
249 if (newNum [i] == -1)
256 int_t *srcVert =
new int_t [newVert];
257 for (int_t i = 0; i < newVert; ++ i)
264 while (cur < compNum)
267 result. addVertex ();
270 int_t posEnd = compEnds [cur];
274 int_t vertex = compVertices [pos ++];
284 for (int_t vertex = 0; vertex < nVert; ++ vertex)
287 if (newNum [vertex] > cur)
288 throw "DEBUG: Wrong order 2.";
291 if (newNum [vertex] != cur)
295 result. addVertex ();
315 template <
class wType>
320 int_t nVertG = g. countVertices ();
325 chomp::homology::BitField visited;
326 visited. allocate (nVertG);
327 visited. clearall (nVertG);
330 for (int_t startVertex = 0; startVertex < nVert; ++ startVertex)
333 result. addVertex ();
337 std::stack<int_t> s_visited;
340 std::stack<int_t> s_vertex;
341 std::stack<int_t> s_edge;
344 visited.
set (startVertex);
345 s_visited. push (startVertex);
349 int_t vertex = startVertex;
355 if (edge >= g. countEdges (vertex))
359 if (s_vertex. empty ())
363 vertex = s_vertex. top ();
365 edge = s_edge. top ();
371 int_t next = g. getEdge (vertex, edge ++);
374 if (!visited. test (next))
378 result. addEdge (next);
381 s_vertex. push (vertex);
389 visited.
set (vertex);
390 s_visited. push (vertex);
396 if (startVertex == nVert - 1)
400 if (nVisited > (nVertG >> 6))
402 visited. clearall (nVertG);
406 while (!s_visited. empty ())
408 int_t vertex = s_visited. top ();
410 visited. clear (vertex);
425 template <
class GraphType>
429 int_t nVertG = g. countVertices ();
434 std::vector<int_t> visited (nVertG, 0);
438 std::stack<int_t> s_vertex;
439 std::stack<int_t> s_edge;
453 if (edge >= g. countEdges (vertex))
456 if (s_vertex. empty ())
460 vertex = s_vertex. top ();
462 edge = s_edge. top ();
469 int_t next = g. getEdge (vertex, edge ++);
475 int_t newPeriod = visited [next] - level - 1;
477 newPeriod = -newPeriod;
500 s_vertex. push (vertex);
509 visited [vertex] = level;
522 template <
class wType>
527 int_t nVertG = g. countVertices ();
532 chomp::homology::BitField visited;
533 visited. allocate (nVertG);
534 visited. clearall (nVertG);
537 chomp::homology::BitSets lists (nVertG, nVert);
540 std::stack<int_t> s_vertex;
541 std::stack<int_t> s_edge;
544 int_t startVertex = 0;
547 visited.
set (vertex);
552 if (edge >= g. countEdges (vertex))
556 if (s_vertex. empty ())
558 while ((startVertex < nVertG) &&
559 (visited. test (startVertex)))
561 if (startVertex >= nVertG)
563 vertex = startVertex;
565 visited.
set (vertex);
570 int_t prev = s_vertex. top ();
576 lists. addset (prev, vertex);
581 edge = s_edge. top ();
587 int_t next = g. getEdge (vertex, edge ++);
591 lists. add (vertex, next);
594 if (!visited. test (next))
597 s_vertex. push (vertex);
603 visited.
set (vertex);
609 else if (next >= nVert)
611 lists. addset (vertex, next);
616 for (int_t vertex = 0; vertex < nVert; ++ vertex)
618 result. addVertex ();
619 int_t edge = lists.
get (vertex);
622 result. addEdge (edge);
623 edge = lists.
get (vertex, edge + 1);
642 template<
class wType,
class TConn>
647 int_t nVertG = g. countVertices ();
652 chomp::homology::BitField visited;
653 visited. allocate (nVertG);
654 visited. clearall (nVertG);
657 chomp::homology::BitSets forwardlists (nVertG, nVert);
660 std::stack<int_t> s_vertex;
661 std::stack<int_t> s_edge;
664 int_t startVertex = 0;
667 visited.
set (vertex);
672 if (edge >= g. countEdges (vertex))
676 if (s_vertex. empty ())
678 while ((startVertex < nVertG) &&
679 (visited. test (startVertex)))
681 if (startVertex >= nVertG)
683 vertex = startVertex;
685 visited.
set (vertex);
690 int_t prev = s_vertex. top ();
696 forwardlists. addset (prev, vertex);
701 edge = s_edge. top ();
707 int_t next = g. getEdge (vertex, edge ++);
711 forwardlists. add (vertex, next);
714 if (!visited. test (next))
717 s_vertex. push (vertex);
723 visited.
set (vertex);
729 else if (next >= nVert)
731 forwardlists. addset (vertex, next);
738 chomp::homology::BitSets backlists (nVertG, nVert);
744 if (!s_vertex. empty () || !s_edge. empty ())
745 throw "DEBUG: Nonempty stacks in 'inclusionGraph'.";
748 visited. clearall (nVertG);
754 visited.
set (vertex);
759 if (edge >= gT. countEdges (vertex))
763 if (s_vertex. empty ())
765 while ((startVertex < nVertG) &&
766 (visited. test (startVertex)))
768 if (startVertex >= nVertG)
770 vertex = startVertex;
772 visited.
set (vertex);
777 int_t prev = s_vertex. top ();
783 backlists. addset (prev, vertex);
788 edge = s_edge. top ();
794 int_t next = gT. getEdge (vertex, edge ++);
798 backlists. add (vertex, next);
801 if (!visited. test (next))
804 s_vertex. push (vertex);
810 visited.
set (vertex);
816 else if (next >= nVert)
818 backlists. addset (vertex, next);
825 for (int_t v = nVert; v < nVertG; ++ v)
827 int_t bvertex = backlists.
get (v);
830 int_t fvertex = forwardlists.
get (v);
833 connections (bvertex, fvertex, v);
834 fvertex = forwardlists.
get (v, fvertex + 1);
836 bvertex = backlists.
get (v, bvertex + 1);
843 for (int_t vertex = 0; vertex < nVert; ++ vertex)
845 result. addVertex ();
846 int_t edge = forwardlists.
get (vertex);
849 result. addEdge (edge);
850 edge = forwardlists.
get (vertex, edge + 1);
864 template <
class wType,
class matrix>
867 int_t nVert = g. countVertices ();
868 for (int_t v = 0; v < nVert; ++ v)
870 int_t nEdges = g. countEdges (v);
871 for (int_t e = 0; e < nEdges; ++ e)
873 int_t w = g. getEdge (v, e);
884 template <
class wType,
class matrix>
887 for (int_t v = 0; v < n; ++ v)
890 for (int_t w = 0; w < n; ++ w)
902 template <
class matrix>
905 for (int_t k = 0; k < n; ++ k)
907 for (int_t i = 0; i < n; ++ i)
909 for (int_t j = 0; j < n; ++ j)
911 if (m [i] [k] && m [k] [j])
926 template <
class matrix>
929 for (int_t k = n - 1; k >= 0; -- k)
931 for (int_t i = 0; i < n; ++ i)
933 for (int_t j = 0; j < n; ++ j)
935 if (m [i] [k] && m [k] [j])
945 template <
class wType>
949 int_t nVert = g. countVertices ();
952 chomp::homology::flatMatrix<char> m (nVert);
964 #endif // _CYMEALG_VARIOUS_H_ int_t collapseVertices(const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result, int_t *newNumbers=0)
Collapses disjoint subsets of vertices to single vertices and creates a corresponding graph in which ...
void graph2matrix(const diGraph< wType > &g, matrix &m)
Creates the adjacency matrix of the given graph.
void transpose(const Graph1 &g, Graph2 &result, bool copyweights=false)
Creates a transposed graph.
int_t connectionGraph(const diGraph< wType > &g, int_t nVert, diGraph< wType > &result)
Computes the graph that represents connections between a number of the first vertices in the given gr...
This class defines a weighted directed graph with very limited number of operations.
int_t addRenumEdges2(const diGraph< wType > &g, int_t vertex, const int_t *newNum, TabSets &numSets, int_t cur, int_t *srcVert, diGraph< wType > &result)
A helper function for "collapseVertices2".
int_t computePeriod(const GraphType &g)
Computes the period of a strongly connected graph.
int_t inclusionGraph(const diGraph< wType > &g, int_t nVert, diGraph< wType > &result)
Computes the graph that represents flow-induced relations on Morse sets.
int_t collapseVertices2(const diGraph< wType > &g, int_t compNum, Table1 &compVertices, Table2 &compEnds, diGraph< wType > &result)
Collapses (possibly non-disjoint) subsets of vertices to single vertices and creates a corresponding ...
int_t addRenumEdges(const diGraph< wType > &g, int_t vertex, const int_t *newNum, int_t cur, int_t *srcVert, diGraph< wType > &result)
A helper function for "collapseVertices".
void transitiveReduction(matrix &m, int_t n)
Computes the transitive reduction of a CLOSED acyclic graph defined by its adjacency matrix...
void transitiveClosure(matrix &m, int_t n)
Computes the transitive closure of an acyclic graph defined by its adjacency matrix, using the Warshall's algorithm: S.
void matrix2graph(const matrix &m, int_t n, diGraph< wType > &g)
Creates a graph based on the given adjacency matrix.