The CyMeAlg Software (Release 0.01)
dfs.h
Go to the documentation of this file.
1 /// @addtogroup cymealg
2 /// @{
3 
4 /////////////////////////////////////////////////////////////////////////////
5 ///
6 /// @file
7 ///
8 /// This header file contains several procedures directly related
9 /// to the DFS algorithm.
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_DFS_H_
35 #define _CYMEALG_DFS_H_
36 
37 // include selected header files from the CHomP library
38 #include "chomp/system/config.h"
39 
40 namespace cymealg {
41 
42 /// The recurrent procedure for DFSfinishTime.
43 template <class Graph, class Table>
44 inline void DFSfinishTimeRecurrent (const Graph &g, Table &tab,
45  int_t vertex, int_t &counter)
46 {
47  g. DFSfinishTimeRecurrent (tab, vertex, counter);
48  return;
49 } /* DFSfinishTimeRecurrent */
50 
51 /// A stack version of the recurrent procedure for DFSfinishTime.
52 template <class Graph, class Table>
53 inline void DFSfinishTimeStack (const Graph &g, Table &tab,
54  int_t vertex, int_t &counter)
55 {
56  g. DFSfinishTimeStack (tab, vertex, counter);
57  return;
58 } /* DFSfinishTimeStack */
59 
60 /// Computes the DFS finishing time for each vertex.
61 /// Note: The time begins with 1, not with 0.
62 template <class Graph, class Table>
63 inline void DFSfinishTime (const Graph &g, Table &tab)
64 {
65  g. DFSfinishTime (tab);
66  return;
67 } /* DFSfinishTime */
68 
69 /// The recurrent procedure for DFSforest.
70 /// Returns true iff there is a loop within the tree found.
71 template <class Graph, class Table1, class Table2>
72 inline bool DFSforestRecurrent (const Graph &g, Table1 &tab, Table1 &ntab,
73  int_t vertex, int_t treeNumber, int_t countTrees,
74  Table2 &compVertices, int_t &curVertex,
75  Graph *sccGraph, int_t *sccEdgeAdded)
76 {
77  return g. DFSforestRecurrent (tab, ntab, vertex,
78  treeNumber, countTrees, compVertices,
79  curVertex, sccGraph, sccEdgeAdded);
80 } /* DFSforestRecurrent */
81 
82 /// A stack version of the recurrent procedure for DFSforest.
83 template <class Graph, class Table1, class Table2>
84 inline bool DFSforestStack (const Graph &g, Table1 &tab, Table1 &ntab,
85  int_t vertex, int_t treeNumber, int_t countTrees,
86  Table2 &compVertices, int_t &curVertex,
87  Graph *sccGraph, int_t *sccEdgeAdded)
88 {
89  return g. DFSforestStack (g, tab, ntab, vertex,
90  treeNumber, countTrees, compVertices,
91  curVertex, sccGraph, sccEdgeAdded);
92 } /* DFSforestStack */
93 
94 /// Computes the DFS forest.
95 /// Considers the vertices in the given order.
96 /// Saves the numbers of vertices of each tree in 'compVertices',
97 /// and keeps the one-beyond-the-end offsets of the trees in the
98 /// table 'compEnds'. Records the connections between the trees
99 /// in 'scc' (which must be empty when this function is called).
100 /// If requested, only those single-vertex trees are counted
101 /// which have an edge that loops back to themselves.
102 /// Returns the number of trees in the computed forest.
103 template <class Graph, class Table1, class Table2, class Table3>
104 inline int_t DFSforest (const Graph &g, const Table1 &ordered,
105  Table2 &compVertices, Table3 &compEnds, bool nontrivial = false,
106  Graph *sccGraph = 0)
107 {
108  return g. DFSforest (ordered, compVertices, compEnds, nontrivial,
109  sccGraph);
110 } /* DFSforest */
111 
112 /// The recurrent procedure for DFScolor.
113 template <class Graph, class Table, class Color>
114 inline void DFScolorRecurrent (const Graph &g, Table &tab,
115  const Color &color, int_t vertex = 0)
116 {
117  g. DFScolorRecurrent (tab, color, vertex);
118  return;
119 } /* DFScolorRecurrent */
120 
121 /// A stack version of the recurrent procedure for DFScolor.
122 template <class Graph, class Table, class Color>
123 inline void DFScolorStack (const Graph &g, Table &tab, const Color &color,
124  int_t vertex = 0)
125 {
126  g. DFScolorStack (tab, color, vertex);
127  return;
128 } /* DFScolorStack */
129 
130 /// Marks each vertex visited by DFS with the given color,
131 /// starting with the given vertex. Runs for one component only.
132 /// The initial color in 'tab' must be different than the given one.
133 template <class Graph, class Table, class Color>
134 inline void DFScolor (const Graph &g, Table &tab, const Color &color,
135  int_t vertex = 0)
136 {
137  g. DFScolor (tab, color, vertex);
138  return;
139 } /* DFScolor */
140 
141 
142 } // namespace cymealg
143 
144 #endif // _CYMEALG_DFS_H_
145 
146 /// @}
147 
void DFScolorStack(const Graph &g, Table &tab, const Color &color, int_t vertex=0)
A stack version of the recurrent procedure for DFScolor.
Definition: dfs.h:123
void DFScolor(const Graph &g, Table &tab, const Color &color, int_t vertex=0)
Marks each vertex visited by DFS with the given color, starting with the given vertex.
Definition: dfs.h:134
void DFSfinishTime(const Graph &g, Table &tab)
Computes the DFS finishing time for each vertex.
Definition: dfs.h:63
void DFSfinishTimeStack(const Graph &g, Table &tab, int_t vertex, int_t &counter)
A stack version of the recurrent procedure for DFSfinishTime.
Definition: dfs.h:53
void DFSfinishTimeRecurrent(const Graph &g, Table &tab, int_t vertex, int_t &counter)
The recurrent procedure for DFSfinishTime.
Definition: dfs.h:44
bool DFSforestStack(const Graph &g, Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, Graph *sccGraph, int_t *sccEdgeAdded)
A stack version of the recurrent procedure for DFSforest.
Definition: dfs.h:84
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
bool DFSforestRecurrent(const Graph &g, Table1 &tab, Table1 &ntab, int_t vertex, int_t treeNumber, int_t countTrees, Table2 &compVertices, int_t &curVertex, Graph *sccGraph, int_t *sccEdgeAdded)
The recurrent procedure for DFSforest.
Definition: dfs.h:72
void DFScolorRecurrent(const Graph &g, Table &tab, const Color &color, int_t vertex=0)
The recurrent procedure for DFScolor.
Definition: dfs.h:114