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_dfs.h> |
---|
9 | #include <hugo/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 operator[](typename Graph::Edge e) const { |
---|
24 | return |
---|
25 | (node_name_map[graph.tail(e)]+"->"+node_name_map[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 | EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
---|
92 | |
---|
93 | cout << "bfs and dfs iterator demo on the directed graph" << endl; |
---|
94 | for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { |
---|
95 | cout << node_name[n] << ": "; |
---|
96 | cout << "out edges: "; |
---|
97 | for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) |
---|
98 | cout << edge_name[e] << " "; |
---|
99 | cout << "in edges: "; |
---|
100 | for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) |
---|
101 | cout << edge_name[e] << " "; |
---|
102 | cout << endl; |
---|
103 | } |
---|
104 | |
---|
105 | cout << "bfs from s ..." << endl; |
---|
106 | BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
---|
107 | bfs.pushAndSetReached(s); |
---|
108 | while (!bfs.finished()) { |
---|
109 | //cout << "edge: "; |
---|
110 | if (G.valid(bfs)) { |
---|
111 | cout << edge_name[bfs] << /*endl*/", " << |
---|
112 | node_name[G.aNode(bfs)] << |
---|
113 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
114 | node_name[G.bNode(bfs)] << |
---|
115 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
116 | ": is not newly reached."); |
---|
117 | } else { |
---|
118 | cout << "invalid" << /*endl*/", " << |
---|
119 | node_name[bfs.aNode()] << |
---|
120 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
121 | |
---|
122 | "invalid."; |
---|
123 | } |
---|
124 | cout << endl; |
---|
125 | ++bfs; |
---|
126 | } |
---|
127 | |
---|
128 | cout << " /--> -------------> "<< endl; |
---|
129 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
130 | cout << " / | | / /-> \\ "<< endl; |
---|
131 | cout << " / | | / | ^ \\ "<< endl; |
---|
132 | cout << "s | | / | | \\-> t "<< endl; |
---|
133 | cout << " \\ | | / | | /-> "<< endl; |
---|
134 | cout << " \\ | --/ / | | / "<< endl; |
---|
135 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
136 | cout << " \\--> -------------> "<< endl; |
---|
137 | |
---|
138 | cout << "dfs from s ..." << endl; |
---|
139 | DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G); |
---|
140 | dfs.pushAndSetReached(s); |
---|
141 | while (!dfs.finished()) { |
---|
142 | ++dfs; |
---|
143 | //cout << "edge: "; |
---|
144 | if (G.valid(dfs)) { |
---|
145 | cout << edge_name[dfs] << /*endl*/", " << |
---|
146 | node_name[G.aNode(dfs)] << |
---|
147 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
148 | node_name[G.bNode(dfs)] << |
---|
149 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
150 | ": is not newly reached."); |
---|
151 | } else { |
---|
152 | cout << "invalid" << /*endl*/", " << |
---|
153 | node_name[dfs.aNode()] << |
---|
154 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
155 | |
---|
156 | "invalid."; |
---|
157 | } |
---|
158 | cout << endl; |
---|
159 | } |
---|
160 | } |
---|
161 | |
---|
162 | |
---|
163 | { |
---|
164 | typedef RevGraphWrapper<const Graph> GW; |
---|
165 | GW gw(G); |
---|
166 | |
---|
167 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
168 | |
---|
169 | cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
---|
170 | for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
---|
171 | cout << node_name[GW::Node(n)] << ": "; |
---|
172 | cout << "out edges: "; |
---|
173 | for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
174 | cout << edge_name[e] << " "; |
---|
175 | cout << "in edges: "; |
---|
176 | for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
177 | cout << edge_name[e] << " "; |
---|
178 | cout << endl; |
---|
179 | } |
---|
180 | |
---|
181 | cout << "bfs from t ..." << endl; |
---|
182 | BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
---|
183 | bfs.pushAndSetReached(t); |
---|
184 | while (!bfs.finished()) { |
---|
185 | //cout << "edge: "; |
---|
186 | if (gw.valid(GW::OutEdgeIt(bfs))) { |
---|
187 | cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
---|
188 | node_name[gw.aNode(bfs)] << |
---|
189 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
190 | node_name[gw.bNode(bfs)] << |
---|
191 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
192 | ": is not newly reached."); |
---|
193 | } else { |
---|
194 | cout << "invalid" << /*endl*/", " << |
---|
195 | node_name[bfs.aNode()] << |
---|
196 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
197 | |
---|
198 | "invalid."; |
---|
199 | } |
---|
200 | cout << endl; |
---|
201 | ++bfs; |
---|
202 | } |
---|
203 | |
---|
204 | cout << " /--> -------------> "<< endl; |
---|
205 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
206 | cout << " / | | / /-> \\ "<< endl; |
---|
207 | cout << " / | | / | ^ \\ "<< endl; |
---|
208 | cout << "s | | / | | \\-> t "<< endl; |
---|
209 | cout << " \\ | | / | | /-> "<< endl; |
---|
210 | cout << " \\ | --/ / | | / "<< endl; |
---|
211 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
212 | cout << " \\--> -------------> "<< endl; |
---|
213 | |
---|
214 | cout << "dfs from t ..." << endl; |
---|
215 | DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
---|
216 | dfs.pushAndSetReached(t); |
---|
217 | while (!dfs.finished()) { |
---|
218 | ++dfs; |
---|
219 | //cout << "edge: "; |
---|
220 | if (gw.valid(GW::OutEdgeIt(dfs))) { |
---|
221 | cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
---|
222 | node_name[gw.aNode(dfs)] << |
---|
223 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
224 | node_name[gw.bNode(dfs)] << |
---|
225 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
226 | ": is not newly reached."); |
---|
227 | } else { |
---|
228 | cout << "invalid" << /*endl*/", " << |
---|
229 | node_name[dfs.aNode()] << |
---|
230 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
231 | |
---|
232 | "invalid."; |
---|
233 | } |
---|
234 | cout << endl; |
---|
235 | } |
---|
236 | } |
---|
237 | |
---|
238 | { |
---|
239 | typedef UndirGraphWrapper<const Graph> GW; |
---|
240 | GW gw(G); |
---|
241 | |
---|
242 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
243 | |
---|
244 | cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
---|
245 | for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
---|
246 | cout << node_name[GW::Node(n)] << ": "; |
---|
247 | cout << "out edges: "; |
---|
248 | for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
249 | cout << edge_name[e] << " "; |
---|
250 | cout << "in edges: "; |
---|
251 | for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
252 | cout << edge_name[e] << " "; |
---|
253 | cout << endl; |
---|
254 | } |
---|
255 | // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
---|
256 | // cout << edge_name.get(e) << " "; |
---|
257 | // } |
---|
258 | // cout << endl; |
---|
259 | |
---|
260 | cout << "bfs from t ..." << endl; |
---|
261 | BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
---|
262 | bfs.pushAndSetReached(t); |
---|
263 | while (!bfs.finished()) { |
---|
264 | //cout << "edge: "; |
---|
265 | if (gw.valid(GW::OutEdgeIt(bfs))) { |
---|
266 | cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
---|
267 | node_name[gw.aNode(bfs)] << |
---|
268 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
269 | node_name[gw.bNode(bfs)] << |
---|
270 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
271 | ": is not newly reached."); |
---|
272 | } else { |
---|
273 | cout << "invalid" << /*endl*/", " << |
---|
274 | node_name[bfs.aNode()] << |
---|
275 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
276 | |
---|
277 | "invalid."; |
---|
278 | } |
---|
279 | cout << endl; |
---|
280 | ++bfs; |
---|
281 | } |
---|
282 | |
---|
283 | cout << " /--> -------------> "<< endl; |
---|
284 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
285 | cout << " / | | / /-> \\ "<< endl; |
---|
286 | cout << " / | | / | ^ \\ "<< endl; |
---|
287 | cout << "s | | / | | \\-> t "<< endl; |
---|
288 | cout << " \\ | | / | | /-> "<< endl; |
---|
289 | cout << " \\ | --/ / | | / "<< endl; |
---|
290 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
291 | cout << " \\--> -------------> "<< endl; |
---|
292 | |
---|
293 | cout << "dfs from t ..." << endl; |
---|
294 | DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
---|
295 | dfs.pushAndSetReached(t); |
---|
296 | while (!dfs.finished()) { |
---|
297 | ++dfs; |
---|
298 | //cout << "edge: "; |
---|
299 | if (gw.valid(GW::OutEdgeIt(dfs))) { |
---|
300 | cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
---|
301 | node_name[gw.aNode(dfs)] << |
---|
302 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
303 | node_name[gw.bNode(dfs)] << |
---|
304 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
305 | ": is not newly reached."); |
---|
306 | } else { |
---|
307 | cout << "invalid" << /*endl*/", " << |
---|
308 | node_name[dfs.aNode()] << |
---|
309 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
310 | |
---|
311 | "invalid."; |
---|
312 | } |
---|
313 | cout << endl; |
---|
314 | } |
---|
315 | } |
---|
316 | |
---|
317 | |
---|
318 | |
---|
319 | { |
---|
320 | typedef BidirGraphWrapper<const Graph> GW; |
---|
321 | GW gw(G); |
---|
322 | |
---|
323 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
324 | |
---|
325 | cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
---|
326 | for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
---|
327 | cout << node_name[GW::Node(n)] << ": "; |
---|
328 | cout << "out edges: "; |
---|
329 | for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
330 | cout << edge_name[e] << " "; |
---|
331 | cout << "in edges: "; |
---|
332 | for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
---|
333 | cout << edge_name[e] << " "; |
---|
334 | cout << endl; |
---|
335 | } |
---|
336 | // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
---|
337 | // cout << edge_name.get(e) << " "; |
---|
338 | // } |
---|
339 | // cout << endl; |
---|
340 | |
---|
341 | cout << "bfs from t ..." << endl; |
---|
342 | BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
---|
343 | bfs.pushAndSetReached(t); |
---|
344 | while (!bfs.finished()) { |
---|
345 | //cout << "edge: "; |
---|
346 | if (gw.valid(GW::OutEdgeIt(bfs))) { |
---|
347 | cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
---|
348 | node_name[gw.aNode(bfs)] << |
---|
349 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
350 | node_name[gw.bNode(bfs)] << |
---|
351 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
352 | ": is not newly reached."); |
---|
353 | } else { |
---|
354 | cout << "invalid" << /*endl*/", " << |
---|
355 | node_name[bfs.aNode()] << |
---|
356 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
357 | |
---|
358 | "invalid."; |
---|
359 | } |
---|
360 | cout << endl; |
---|
361 | ++bfs; |
---|
362 | } |
---|
363 | |
---|
364 | cout << " /--> -------------> "<< endl; |
---|
365 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
366 | cout << " / | | / /-> \\ "<< endl; |
---|
367 | cout << " / | | / | ^ \\ "<< endl; |
---|
368 | cout << "s | | / | | \\-> t "<< endl; |
---|
369 | cout << " \\ | | / | | /-> "<< endl; |
---|
370 | cout << " \\ | --/ / | | / "<< endl; |
---|
371 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
372 | cout << " \\--> -------------> "<< endl; |
---|
373 | |
---|
374 | cout << "dfs from t ..." << endl; |
---|
375 | DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
---|
376 | dfs.pushAndSetReached(t); |
---|
377 | while (!dfs.finished()) { |
---|
378 | ++dfs; |
---|
379 | //cout << "edge: "; |
---|
380 | if (gw.valid(GW::OutEdgeIt(dfs))) { |
---|
381 | cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
---|
382 | node_name[gw.aNode(dfs)] << |
---|
383 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
384 | node_name[gw.bNode(dfs)] << |
---|
385 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
386 | ": is not newly reached."); |
---|
387 | } else { |
---|
388 | cout << "invalid" << /*endl*/", " << |
---|
389 | node_name[dfs.aNode()] << |
---|
390 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
391 | |
---|
392 | "invalid."; |
---|
393 | } |
---|
394 | cout << endl; |
---|
395 | } |
---|
396 | } |
---|
397 | |
---|
398 | |
---|
399 | |
---|
400 | return 0; |
---|
401 | } |
---|