1 #ifndef GRAPH_CALLBACK_H 2 #define GRAPH_CALLBACK_H 25 virtual bool Stop() {
return false; }
56 virtual bool Stop() {
return found; }
57 virtual void Visit(
Node n) {
if(n == node) found =
true; }
67 depth[j] = depth[i]+1;
71 std::vector<int> depth;
88 std::map<Node,int> startTime, finishTime;
95 :time(0),startTime(numNodes,-1),finishTime(numNodes,-1)
97 virtual void Visit(
int n) { startTime[n] = time++; }
98 virtual void PostVisit(
int n) { finishTime[n] = time++; }
100 std::vector<int> startTime, finishTime;
104 template <
class Node>
108 virtual bool Stop() {
return hasCycle; }
114 template <
class Node>
118 virtual bool Stop() {
return hasCycle; }
121 std::list<Node> list;
126 template <
class Node>
131 std::map<Node,Node> parents;
138 virtual bool ForwardEdge(
int i,
int j) { parents[j]=i;
return true; }
139 std::vector<int> parents;
144 template <
class Node>
148 virtual bool Stop() {
return found; }
149 virtual void Visit(
Node n) {
if(n == node) found =
true; }
153 std::map<Node,Node> parents;
159 PathIntCallback(
int numNodes,
int n) :node(n),found(
false),parents(numNodes,-1) {}
160 virtual bool Stop() {
return found; }
161 virtual void Visit(
int n) {
if(n == node) found =
true; }
162 virtual bool ForwardEdge(
int i,
int j) { assert(parents[j]==-1); parents[j]=i;
return true; }
165 std::vector<int> parents;
173 :parents(numNodes,-1),depth(numNodes,INT_MAX)
175 depth[startNode] = 0;
179 assert(parents[j]==-1);
181 depth[j] = depth[i]+1;
184 std::vector<int> parents;
185 std::vector<int> depth;
193 :cComponents(numNodes), numComponents(0) {}
197 { cComponents[node] = numComponents-1; }
199 std::vector<int> cComponents;
Same as above, but for indexed graphs.
Definition: Callback.h:92
Same as above, but for indexed graphs.
Definition: Callback.h:157
virtual void Visit(Node n)
Called when a node is first visited.
Definition: Callback.h:79
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:118
Same as above, but for indexed graphs.
Definition: Callback.h:135
virtual void PostVisit(Node n)
Called after a node has been visited.
Definition: Callback.h:119
virtual bool ForwardEdge(int i, int j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:138
virtual void NewComponent(Node)
Called when a new component is visited.
Definition: Callback.h:39
virtual void PostVisit(int n)
Called after a node has been visited.
Definition: Callback.h:98
virtual void Visit(Node n)
Called when a node is first visited.
Definition: Callback.h:47
virtual void Visit(Node n)
Called when a node is first visited.
Definition: Callback.h:149
virtual void PostVisit(Node)
Called after a node has been visited.
Definition: Callback.h:31
A template base class for a graph traversal.
Definition: Callback.h:21
virtual void PostVisit(Node n)
Called after a node has been visited.
Definition: Callback.h:83
virtual bool ForwardEdge(Node i, Node j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:130
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:160
virtual bool ForwardEdge(int i, int j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:177
virtual void Visit(int node)
Called when a node is first visited.
Definition: Callback.h:196
Compute if the graph has a cycle.
Definition: Callback.h:105
Definition: Callback.h:145
virtual void BackEdge(Node i, Node j)
Called on traversal of edges from i to previously visited j.
Definition: Callback.h:120
Definition: Callback.h:170
virtual void CrossEdge(Node i, Node j)
Called on traversal of edges from i to currently visiting j.
Definition: Callback.h:35
virtual void Visit(Node n)
Called when a node is first visited.
Definition: Callback.h:57
Definition: Callback.h:190
Compute the traversal graph of a traversal.
Definition: Callback.h:127
Count the number of nodes traversed.
Definition: Callback.h:44
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:56
A tree graph structure, represented directly at the node level.
Definition: Tree.h:25
virtual void Visit(int n)
Called when a node is first visited.
Definition: Callback.h:97
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:148
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:25
Get the depth of all nodes (in an indexed graph, such as Graph)
Definition: Callback.h:63
virtual bool Stop()
Return true to halt the traversal.
Definition: Callback.h:108
virtual bool ForwardEdge(Node i, Node j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:33
Get the start/finish time of a traversal.
Definition: Callback.h:76
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7
virtual void NewComponent(int node)
Called when a new component is visited.
Definition: Callback.h:194
Perform topological sort, when used with DFS.
Definition: Callback.h:115
virtual bool ForwardEdge(int i, int j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:162
virtual bool Descend(Node)
Return true to visit the node's adjacencies.
Definition: Callback.h:29
virtual bool ForwardEdge(int i, int j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:66
virtual void BackEdge(Node i, Node j)
Called on traversal of edges from i to previously visited j.
Definition: Callback.h:37
virtual void Visit(Node)
Called when a node is first visited.
Definition: Callback.h:27
virtual void BackEdge(Node i, Node j)
Called on traversal of edges from i to previously visited j.
Definition: Callback.h:109
virtual bool ForwardEdge(Node i, Node j)
Called on traversal of edges from i to unvisited j.
Definition: Callback.h:150
Find a particular node.
Definition: Callback.h:53
virtual void Visit(int n)
Called when a node is first visited.
Definition: Callback.h:161