KrisLibrary  1.0.0
Callback.h
1 #ifndef GRAPH_CALLBACK_H
2 #define GRAPH_CALLBACK_H
3 
4 #include <list>
5 #include <map>
6 #include <vector>
7 #include <assert.h>
8 #include <limits.h>
9 
10 namespace Graph {
11 
14 
20 template<class Node>
22 {
23  virtual ~CallbackBase() {}
25  virtual bool Stop() { return false; }
27  virtual void Visit(Node) {}
29  virtual bool Descend(Node) { return true; }
31  virtual void PostVisit(Node) {}
33  virtual bool ForwardEdge(Node i,Node j) { return true; }
35  virtual void CrossEdge(Node i,Node j) {}
37  virtual void BackEdge(Node i,Node j) {}
39  virtual void NewComponent(Node) {}
40 };
41 
43 template <class Node>
44 struct CountCallback : public CallbackBase<Node>
45 {
46  CountCallback() :count(0) {}
47  virtual void Visit(Node n) { count++; }
48  int count;
49 };
50 
52 template <class Node>
53 struct FindCallback : public CallbackBase<Node>
54 {
55  FindCallback(Node n) :node(n),found(false) {}
56  virtual bool Stop() { return found; }
57  virtual void Visit(Node n) { if(n == node) found = true; }
58  Node node;
59  bool found;
60 };
61 
63 struct DepthIntCallback : public CallbackBase<int>
64 {
65  DepthIntCallback(int numNodes):depth(numNodes,0) {}
66  virtual bool ForwardEdge(int i,int j) {
67  depth[j] = depth[i]+1;
68  return true;
69  }
70 
71  std::vector<int> depth;
72 };
73 
75 template <class Node>
76 struct TimeCallback : public CallbackBase<Node>
77 {
78  TimeCallback() :time(0) {}
79  virtual void Visit(Node n) {
80  time++;
81  startTime[n] = time;
82  }
83  virtual void PostVisit(Node n) {
84  time++;
85  finishTime[n] = time;
86  }
87  int time;
88  std::map<Node,int> startTime, finishTime;
89 };
90 
92 struct TimeIntCallback : public CallbackBase<int>
93 {
94  TimeIntCallback(int numNodes)
95  :time(0),startTime(numNodes,-1),finishTime(numNodes,-1)
96  {}
97  virtual void Visit(int n) { startTime[n] = time++; }
98  virtual void PostVisit(int n) { finishTime[n] = time++; }
99  int time;
100  std::vector<int> startTime, finishTime;
101 };
102 
104 template <class Node>
105 struct CycleCallback : public CallbackBase<Node>
106 {
107  CycleCallback() : hasCycle(false) {}
108  virtual bool Stop() { return hasCycle; }
109  virtual void BackEdge(Node i,Node j) { hasCycle = true; }
110  bool hasCycle;
111 };
112 
114 template <class Node>
116 {
117  TopologicalSortCallback() :hasCycle(false) {}
118  virtual bool Stop() { return hasCycle; }
119  virtual void PostVisit(Node n) { list.push_front(n); }
120  virtual void BackEdge(Node i,Node j) { hasCycle = true; }
121  std::list<Node> list;
122  bool hasCycle;
123 };
124 
126 template <class Node>
128 {
130  virtual bool ForwardEdge(Node i,Node j) { parents[j]=i; return true; }
131  std::map<Node,Node> parents;
132 };
133 
136 {
137  TraversalGraphIntCallback(int numNodes):parents(numNodes,-1) {}
138  virtual bool ForwardEdge(int i,int j) { parents[j]=i; return true; }
139  std::vector<int> parents;
140 };
141 
144 template <class Node>
145 struct PathCallback : public CallbackBase<Node>
146 {
147  PathCallback(Node n) :node(n),found(false) {}
148  virtual bool Stop() { return found; }
149  virtual void Visit(Node n) { if(n == node) found = true; }
150  virtual bool ForwardEdge(Node i,Node j) { parents[j]=i; return true; }
151  Node node;
152  bool found;
153  std::map<Node,Node> parents;
154 };
155 
157 struct PathIntCallback : public CallbackBase<int>
158 {
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; }
163  int node;
164  bool found;
165  std::vector<int> parents;
166 };
167 
171 {
172  ShortestPathsIntCallback(int numNodes,int startNode)
173  :parents(numNodes,-1),depth(numNodes,INT_MAX)
174  {
175  depth[startNode] = 0;
176  }
177  virtual bool ForwardEdge(int i,int j)
178  {
179  assert(parents[j]==-1);
180  parents[j] = i;
181  depth[j] = depth[i]+1;
182  return true;
183  }
184  std::vector<int> parents;
185  std::vector<int> depth;
186 };
187 
191 {
192  ComponentIntCallback(int numNodes)
193  :cComponents(numNodes), numComponents(0) {}
194  virtual void NewComponent(int node)
195  { numComponents++; }
196  virtual void Visit(int node)
197  { cComponents[node] = numComponents-1; }
198 
199  std::vector<int> cComponents;
200  int numComponents;
201 };
202 
204 } //namespace Graph
205 
206 #endif
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&#39;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