1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <vector> |
|
4 #include <string> |
|
5 |
|
6 #include <list_graph.h> |
|
7 #include <smart_graph.h> |
|
8 #include <bfs_iterator.h> |
|
9 #include <graph_wrapper.h> |
|
10 |
|
11 using namespace hugo; |
|
12 using std::cout; |
|
13 using std::endl; |
|
14 using std::string; |
|
15 |
|
16 template <typename Graph, typename NodeNameMap> |
|
17 class EdgeNameMap { |
|
18 Graph& graph; |
|
19 NodeNameMap& node_name_map; |
|
20 public: |
|
21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
|
22 graph(_graph), node_name_map(_node_name_map) { } |
|
23 string get(typename Graph::Edge e) const { |
|
24 return |
|
25 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); |
|
26 } |
|
27 }; |
|
28 |
|
29 int main (int, char*[]) |
|
30 { |
|
31 //typedef SmartGraph Graph; |
|
32 typedef ListGraph Graph; |
|
33 |
|
34 typedef Graph::Node Node; |
|
35 typedef Graph::Edge Edge; |
|
36 |
|
37 Graph G; |
|
38 |
|
39 Node s=G.addNode(); |
|
40 Node v1=G.addNode(); |
|
41 Node v2=G.addNode(); |
|
42 Node v3=G.addNode(); |
|
43 Node v4=G.addNode(); |
|
44 Node t=G.addNode(); |
|
45 |
|
46 Graph::NodeMap<string> node_name(G); |
|
47 node_name.set(s, "s"); |
|
48 node_name.set(v1, "v1"); |
|
49 node_name.set(v2, "v2"); |
|
50 node_name.set(v3, "v3"); |
|
51 node_name.set(v4, "v4"); |
|
52 node_name.set(t, "t"); |
|
53 |
|
54 G.addEdge(s, v1); |
|
55 G.addEdge(s, v2); |
|
56 G.addEdge(v1, v2); |
|
57 G.addEdge(v2, v1); |
|
58 G.addEdge(v1, v3); |
|
59 G.addEdge(v3, v2); |
|
60 G.addEdge(v2, v4); |
|
61 G.addEdge(v4, v3); |
|
62 G.addEdge(v3, t); |
|
63 G.addEdge(v4, t); |
|
64 |
|
65 cout << " /--> -------------> "<< endl; |
|
66 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
|
67 cout << " / | | / /-> \\ "<< endl; |
|
68 cout << " / | | / | ^ \\ "<< endl; |
|
69 cout << "s | | / | | \\-> t "<< endl; |
|
70 cout << " \\ | | / | | /-> "<< endl; |
|
71 cout << " \\ | --/ / | | / "<< endl; |
|
72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
|
73 cout << " \\--> -------------> "<< endl; |
|
74 |
|
75 // typedef TrivGraphWrapper<const Graph> CGW; |
|
76 // CGW gw(G); |
|
77 |
|
78 // cout << "bfs and dfs demo on the directed graph" << endl; |
|
79 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { |
|
80 // cout << n << ": "; |
|
81 // cout << "out edges: "; |
|
82 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
|
83 // cout << e << " "; |
|
84 // cout << "in edges: "; |
|
85 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
|
86 // cout << e << " "; |
|
87 // cout << endl; |
|
88 // } |
|
89 |
|
90 { |
|
91 typedef TrivGraphWrapper<const Graph> GW; |
|
92 GW gw(G); |
|
93 |
|
94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
|
95 |
|
96 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
|
97 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
|
98 cout << node_name.get(n) << ": "; |
|
99 cout << "out edges: "; |
|
100 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
101 cout << edge_name.get(e) << " "; |
|
102 cout << "in edges: "; |
|
103 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
104 cout << edge_name.get(e) << " "; |
|
105 cout << endl; |
|
106 } |
|
107 |
|
108 cout << "bfs from s ..." << endl; |
|
109 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
|
110 bfs.pushAndSetReached(s); |
|
111 while (!bfs.finished()) { |
|
112 //cout << "edge: "; |
|
113 if (gw.valid(bfs)) { |
|
114 cout << edge_name.get(bfs) << /*endl*/", " << |
|
115 node_name.get(gw.aNode(bfs)) << |
|
116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
117 node_name.get(gw.bNode(bfs)) << |
|
118 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
119 ": is not newly reached."); |
|
120 } else { |
|
121 cout << "invalid" << /*endl*/", " << |
|
122 node_name.get(bfs.aNode()) << |
|
123 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
124 |
|
125 "invalid."; |
|
126 } |
|
127 cout << endl; |
|
128 ++bfs; |
|
129 } |
|
130 |
|
131 cout << " /--> -------------> "<< endl; |
|
132 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
|
133 cout << " / | | / /-> \\ "<< endl; |
|
134 cout << " / | | / | ^ \\ "<< endl; |
|
135 cout << "s | | / | | \\-> t "<< endl; |
|
136 cout << " \\ | | / | | /-> "<< endl; |
|
137 cout << " \\ | --/ / | | / "<< endl; |
|
138 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
|
139 cout << " \\--> -------------> "<< endl; |
|
140 |
|
141 cout << "dfs from s ..." << endl; |
|
142 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
|
143 dfs.pushAndSetReached(s); |
|
144 while (!dfs.finished()) { |
|
145 ++dfs; |
|
146 //cout << "edge: "; |
|
147 if (gw.valid(dfs)) { |
|
148 cout << edge_name.get(dfs) << /*endl*/", " << |
|
149 node_name.get(gw.aNode(dfs)) << |
|
150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
151 node_name.get(gw.bNode(dfs)) << |
|
152 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
153 ": is not newly reached."); |
|
154 } else { |
|
155 cout << "invalid" << /*endl*/", " << |
|
156 node_name.get(dfs.aNode()) << |
|
157 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
158 |
|
159 "invalid."; |
|
160 } |
|
161 cout << endl; |
|
162 } |
|
163 } |
|
164 |
|
165 |
|
166 { |
|
167 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
|
168 GW gw(G); |
|
169 |
|
170 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
|
171 |
|
172 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
|
173 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
|
174 cout << node_name.get(n) << ": "; |
|
175 cout << "out edges: "; |
|
176 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
177 cout << edge_name.get(e) << " "; |
|
178 cout << "in edges: "; |
|
179 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
180 cout << edge_name.get(e) << " "; |
|
181 cout << endl; |
|
182 } |
|
183 |
|
184 cout << "bfs from t ..." << endl; |
|
185 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
|
186 bfs.pushAndSetReached(t); |
|
187 while (!bfs.finished()) { |
|
188 //cout << "edge: "; |
|
189 if (gw.valid(bfs)) { |
|
190 cout << edge_name.get(bfs) << /*endl*/", " << |
|
191 node_name.get(gw.aNode(bfs)) << |
|
192 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
193 node_name.get(gw.bNode(bfs)) << |
|
194 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
195 ": is not newly reached."); |
|
196 } else { |
|
197 cout << "invalid" << /*endl*/", " << |
|
198 node_name.get(bfs.aNode()) << |
|
199 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
200 |
|
201 "invalid."; |
|
202 } |
|
203 cout << endl; |
|
204 ++bfs; |
|
205 } |
|
206 |
|
207 cout << " /--> -------------> "<< endl; |
|
208 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
|
209 cout << " / | | / /-> \\ "<< endl; |
|
210 cout << " / | | / | ^ \\ "<< endl; |
|
211 cout << "s | | / | | \\-> t "<< endl; |
|
212 cout << " \\ | | / | | /-> "<< endl; |
|
213 cout << " \\ | --/ / | | / "<< endl; |
|
214 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
|
215 cout << " \\--> -------------> "<< endl; |
|
216 |
|
217 cout << "dfs from t ..." << endl; |
|
218 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
|
219 dfs.pushAndSetReached(t); |
|
220 while (!dfs.finished()) { |
|
221 ++dfs; |
|
222 //cout << "edge: "; |
|
223 if (gw.valid(dfs)) { |
|
224 cout << edge_name.get(dfs) << /*endl*/", " << |
|
225 node_name.get(gw.aNode(dfs)) << |
|
226 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
227 node_name.get(gw.bNode(dfs)) << |
|
228 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
229 ": is not newly reached."); |
|
230 } else { |
|
231 cout << "invalid" << /*endl*/", " << |
|
232 node_name.get(dfs.aNode()) << |
|
233 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
234 |
|
235 "invalid."; |
|
236 } |
|
237 cout << endl; |
|
238 } |
|
239 } |
|
240 |
|
241 { |
|
242 //typedef UndirGraphWrapper<const Graph> GW; |
|
243 typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
|
244 GW gw(G); |
|
245 |
|
246 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
|
247 |
|
248 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
|
249 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
|
250 cout << node_name.get(n) << ": "; |
|
251 cout << "out edges: "; |
|
252 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
253 cout << edge_name.get(e) << " "; |
|
254 cout << "in edges: "; |
|
255 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
|
256 cout << edge_name.get(e) << " "; |
|
257 cout << endl; |
|
258 } |
|
259 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
|
260 // cout << edge_name.get(e) << " "; |
|
261 // } |
|
262 // cout << endl; |
|
263 |
|
264 cout << "bfs from t ..." << endl; |
|
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
|
266 bfs.pushAndSetReached(t); |
|
267 while (!bfs.finished()) { |
|
268 //cout << "edge: "; |
|
269 if (gw.valid(GW::OutEdgeIt(bfs))) { |
|
270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
|
271 node_name.get(gw.aNode(bfs)) << |
|
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
273 node_name.get(gw.bNode(bfs)) << |
|
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
275 ": is not newly reached."); |
|
276 } else { |
|
277 cout << "invalid" << /*endl*/", " << |
|
278 node_name.get(bfs.aNode()) << |
|
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
280 |
|
281 "invalid."; |
|
282 } |
|
283 cout << endl; |
|
284 ++bfs; |
|
285 } |
|
286 |
|
287 cout << " /--> -------------> "<< endl; |
|
288 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
|
289 cout << " / | | / /-> \\ "<< endl; |
|
290 cout << " / | | / | ^ \\ "<< endl; |
|
291 cout << "s | | / | | \\-> t "<< endl; |
|
292 cout << " \\ | | / | | /-> "<< endl; |
|
293 cout << " \\ | --/ / | | / "<< endl; |
|
294 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
|
295 cout << " \\--> -------------> "<< endl; |
|
296 |
|
297 cout << "dfs from t ..." << endl; |
|
298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
|
299 dfs.pushAndSetReached(t); |
|
300 while (!dfs.finished()) { |
|
301 ++dfs; |
|
302 //cout << "edge: "; |
|
303 if (gw.valid(GW::OutEdgeIt(dfs))) { |
|
304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
|
305 node_name.get(gw.aNode(dfs)) << |
|
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
307 node_name.get(gw.bNode(dfs)) << |
|
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
|
309 ": is not newly reached."); |
|
310 } else { |
|
311 cout << "invalid" << /*endl*/", " << |
|
312 node_name.get(dfs.aNode()) << |
|
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
|
314 |
|
315 "invalid."; |
|
316 } |
|
317 cout << endl; |
|
318 } |
|
319 } |
|
320 |
|
321 return 0; |
|
322 } |
|