1 | #include <iostream> |
---|
2 | #include <vector> |
---|
3 | #include <string> |
---|
4 | |
---|
5 | #include <list_graph.hh> |
---|
6 | #include <bfs_iterator.hh> |
---|
7 | #include <graph_wrapper.h> |
---|
8 | |
---|
9 | using namespace hugo; |
---|
10 | using std::cout; |
---|
11 | using std::endl; |
---|
12 | using std::string; |
---|
13 | |
---|
14 | template <typename Graph, typename NodeNameMap> |
---|
15 | class EdgeNameMap { |
---|
16 | Graph& graph; |
---|
17 | NodeNameMap& node_name_map; |
---|
18 | public: |
---|
19 | EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
---|
20 | graph(_graph), node_name_map(_node_name_map) { } |
---|
21 | string get(typename Graph::EdgeIt e) const { |
---|
22 | return |
---|
23 | (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); |
---|
24 | } |
---|
25 | }; |
---|
26 | |
---|
27 | int main (int, char*[]) |
---|
28 | { |
---|
29 | typedef ListGraph::NodeIt NodeIt; |
---|
30 | typedef ListGraph::EdgeIt EdgeIt; |
---|
31 | //typedef ListGraph::EachNodeIt EachNodeIt; |
---|
32 | //typedef ListGraph::EachEdgeIt EachEdgeIt; |
---|
33 | //typedef ListGraph::OutEdgeIt OutEdgeIt; |
---|
34 | //typedef ListGraph::InEdgeIt InEdgeIt; |
---|
35 | //typedef ListGraph::SymEdgeIt SymEdgeIt; |
---|
36 | |
---|
37 | ListGraph G; |
---|
38 | |
---|
39 | NodeIt s=G.addNode(); |
---|
40 | NodeIt v1=G.addNode(); |
---|
41 | NodeIt v2=G.addNode(); |
---|
42 | NodeIt v3=G.addNode(); |
---|
43 | NodeIt v4=G.addNode(); |
---|
44 | NodeIt t=G.addNode(); |
---|
45 | |
---|
46 | ListGraph::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 | /* |
---|
76 | { |
---|
77 | cout << "iterator bfs demo 4 ..." << endl; |
---|
78 | BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); |
---|
79 | bfs.pushAndSetReached(s); |
---|
80 | while (!bfs.finished()) { |
---|
81 | if (OutEdgeIt(bfs).valid()) { |
---|
82 | cout << "OutEdgeIt: " << bfs; |
---|
83 | cout << " aNode: " << G.aNode(bfs); |
---|
84 | cout << " bNode: " << G.bNode(bfs) << " "; |
---|
85 | } else { |
---|
86 | cout << "OutEdgeIt: " << "invalid"; |
---|
87 | cout << " aNode: " << bfs.aNode(); |
---|
88 | cout << " bNode: " << "invalid" << " "; |
---|
89 | } |
---|
90 | if (bfs.isBNodeNewlyReached()) { |
---|
91 | cout << "bNodeIsNewlyReached "; |
---|
92 | } else { |
---|
93 | cout << "bNodeIsNotNewlyReached "; |
---|
94 | } |
---|
95 | if (bfs.isANodeExamined()) { |
---|
96 | cout << "aNodeIsExamined "; |
---|
97 | } else { |
---|
98 | cout << "aNodeIsNotExamined "; |
---|
99 | } |
---|
100 | cout << endl; |
---|
101 | ++bfs; |
---|
102 | } |
---|
103 | } |
---|
104 | |
---|
105 | { |
---|
106 | cout << "iterator dfs demo 4 ..." << endl; |
---|
107 | DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); |
---|
108 | dfs.pushAndSetReached(s); |
---|
109 | while (!dfs.finished()) { |
---|
110 | ++dfs; |
---|
111 | if (OutEdgeIt(dfs).valid()) { |
---|
112 | cout << "OutEdgeIt: " << dfs; |
---|
113 | cout << " aNode: " << G.aNode(dfs); |
---|
114 | cout << " bNode: " << G.bNode(dfs) << " "; |
---|
115 | } else { |
---|
116 | cout << "OutEdgeIt: " << "invalid"; |
---|
117 | cout << " aNode: " << dfs.aNode(); |
---|
118 | cout << " bNode: " << "invalid" << " "; |
---|
119 | } |
---|
120 | if (dfs.isBNodeNewlyReached()) { |
---|
121 | cout << "bNodeIsNewlyReached "; |
---|
122 | } else { |
---|
123 | cout << "bNodeIsNotNewlyReached "; |
---|
124 | } |
---|
125 | if (dfs.isANodeExamined()) { |
---|
126 | cout << "aNodeIsExamined "; |
---|
127 | } else { |
---|
128 | cout << "aNodeIsNotExamined "; |
---|
129 | } |
---|
130 | cout << endl; |
---|
131 | //++dfs; |
---|
132 | } |
---|
133 | } |
---|
134 | */ |
---|
135 | |
---|
136 | // typedef TrivGraphWrapper<const ListGraph> CGW; |
---|
137 | // CGW wG(G); |
---|
138 | |
---|
139 | // cout << "bfs and dfs demo on the directed graph" << endl; |
---|
140 | // for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { |
---|
141 | // cout << n << ": "; |
---|
142 | // cout << "out edges: "; |
---|
143 | // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
---|
144 | // cout << e << " "; |
---|
145 | // cout << "in edges: "; |
---|
146 | // for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
---|
147 | // cout << e << " "; |
---|
148 | // cout << endl; |
---|
149 | // } |
---|
150 | |
---|
151 | { |
---|
152 | typedef TrivGraphWrapper<const ListGraph> GW; |
---|
153 | GW wG(G); |
---|
154 | |
---|
155 | EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); |
---|
156 | |
---|
157 | cout << "bfs and dfs iterator demo on the directed graph" << endl; |
---|
158 | for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { |
---|
159 | cout << node_name.get(n) << ": "; |
---|
160 | cout << "out edges: "; |
---|
161 | for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
162 | cout << edge_name.get(e) << " "; |
---|
163 | cout << "in edges: "; |
---|
164 | for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
165 | cout << edge_name.get(e) << " "; |
---|
166 | cout << endl; |
---|
167 | } |
---|
168 | |
---|
169 | cout << "bfs from s ..." << endl; |
---|
170 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
---|
171 | bfs.pushAndSetReached(s); |
---|
172 | while (!bfs.finished()) { |
---|
173 | //cout << "edge: "; |
---|
174 | if (wG.valid(bfs)) { |
---|
175 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
176 | /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
---|
177 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
178 | /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
---|
179 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
180 | ": is not newly reached."); |
---|
181 | } else { |
---|
182 | cout << "invalid" << /*endl*/", " << |
---|
183 | /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
---|
184 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
185 | /*" bNode: " <<*/ |
---|
186 | "invalid."; |
---|
187 | } |
---|
188 | cout << endl; |
---|
189 | ++bfs; |
---|
190 | } |
---|
191 | |
---|
192 | cout << " /--> -------------> "<< endl; |
---|
193 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
194 | cout << " / | | / /-> \\ "<< endl; |
---|
195 | cout << " / | | / | ^ \\ "<< endl; |
---|
196 | cout << "s | | / | | \\-> t "<< endl; |
---|
197 | cout << " \\ | | / | | /-> "<< endl; |
---|
198 | cout << " \\ | --/ / | | / "<< endl; |
---|
199 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
200 | cout << " \\--> -------------> "<< endl; |
---|
201 | |
---|
202 | cout << "dfs from s ..." << endl; |
---|
203 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
---|
204 | dfs.pushAndSetReached(s); |
---|
205 | while (!dfs.finished()) { |
---|
206 | ++dfs; |
---|
207 | //cout << "edge: "; |
---|
208 | if (wG.valid(dfs)) { |
---|
209 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
210 | /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
---|
211 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
212 | /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
---|
213 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
214 | ": is not newly reached."); |
---|
215 | } else { |
---|
216 | cout << "invalid" << /*endl*/", " << |
---|
217 | /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
---|
218 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
219 | /*" bNode: " <<*/ |
---|
220 | "invalid."; |
---|
221 | } |
---|
222 | cout << endl; |
---|
223 | } |
---|
224 | } |
---|
225 | |
---|
226 | |
---|
227 | { |
---|
228 | typedef RevGraphWrapper<const ListGraph> GW; |
---|
229 | GW wG(G); |
---|
230 | |
---|
231 | EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); |
---|
232 | |
---|
233 | cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
---|
234 | for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { |
---|
235 | cout << node_name.get(n) << ": "; |
---|
236 | cout << "out edges: "; |
---|
237 | for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
238 | cout << edge_name.get(e) << " "; |
---|
239 | cout << "in edges: "; |
---|
240 | for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
241 | cout << edge_name.get(e) << " "; |
---|
242 | cout << endl; |
---|
243 | } |
---|
244 | |
---|
245 | cout << "bfs from t ..." << endl; |
---|
246 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
---|
247 | bfs.pushAndSetReached(t); |
---|
248 | while (!bfs.finished()) { |
---|
249 | //cout << "edge: "; |
---|
250 | if (wG.valid(bfs)) { |
---|
251 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
252 | /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
---|
253 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
254 | /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
---|
255 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
256 | ": is not newly reached."); |
---|
257 | } else { |
---|
258 | cout << "invalid" << /*endl*/", " << |
---|
259 | /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
---|
260 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
261 | /*" bNode: " <<*/ |
---|
262 | "invalid."; |
---|
263 | } |
---|
264 | cout << endl; |
---|
265 | ++bfs; |
---|
266 | } |
---|
267 | |
---|
268 | cout << " /--> -------------> "<< endl; |
---|
269 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
270 | cout << " / | | / /-> \\ "<< endl; |
---|
271 | cout << " / | | / | ^ \\ "<< endl; |
---|
272 | cout << "s | | / | | \\-> t "<< endl; |
---|
273 | cout << " \\ | | / | | /-> "<< endl; |
---|
274 | cout << " \\ | --/ / | | / "<< endl; |
---|
275 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
276 | cout << " \\--> -------------> "<< endl; |
---|
277 | |
---|
278 | cout << "dfs from t ..." << endl; |
---|
279 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
---|
280 | dfs.pushAndSetReached(t); |
---|
281 | while (!dfs.finished()) { |
---|
282 | ++dfs; |
---|
283 | //cout << "edge: "; |
---|
284 | if (wG.valid(dfs)) { |
---|
285 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
286 | /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
---|
287 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
288 | /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
---|
289 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
290 | ": is not newly reached."); |
---|
291 | } else { |
---|
292 | cout << "invalid" << /*endl*/", " << |
---|
293 | /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
---|
294 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
295 | /*" bNode: " <<*/ |
---|
296 | "invalid."; |
---|
297 | } |
---|
298 | cout << endl; |
---|
299 | } |
---|
300 | } |
---|
301 | |
---|
302 | { |
---|
303 | typedef UndirGraphWrapper<const ListGraph> GW; |
---|
304 | GW wG(G); |
---|
305 | |
---|
306 | EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); |
---|
307 | |
---|
308 | cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
---|
309 | for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { |
---|
310 | cout << node_name.get(n) << ": "; |
---|
311 | cout << "out edges: "; |
---|
312 | for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
313 | cout << edge_name.get(e) << " "; |
---|
314 | cout << "in edges: "; |
---|
315 | for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
---|
316 | cout << edge_name.get(e) << " "; |
---|
317 | cout << endl; |
---|
318 | } |
---|
319 | |
---|
320 | cout << "bfs from t ..." << endl; |
---|
321 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
---|
322 | bfs.pushAndSetReached(t); |
---|
323 | while (!bfs.finished()) { |
---|
324 | //cout << "edge: "; |
---|
325 | if (wG.valid(GW::OutEdgeIt(bfs))) { |
---|
326 | cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
---|
327 | /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
---|
328 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
329 | /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
---|
330 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
331 | ": is not newly reached."); |
---|
332 | } else { |
---|
333 | cout << "invalid" << /*endl*/", " << |
---|
334 | /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
---|
335 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
336 | /*" bNode: " <<*/ |
---|
337 | "invalid."; |
---|
338 | } |
---|
339 | cout << endl; |
---|
340 | ++bfs; |
---|
341 | } |
---|
342 | |
---|
343 | cout << " /--> -------------> "<< endl; |
---|
344 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
345 | cout << " / | | / /-> \\ "<< endl; |
---|
346 | cout << " / | | / | ^ \\ "<< endl; |
---|
347 | cout << "s | | / | | \\-> t "<< endl; |
---|
348 | cout << " \\ | | / | | /-> "<< endl; |
---|
349 | cout << " \\ | --/ / | | / "<< endl; |
---|
350 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
351 | cout << " \\--> -------------> "<< endl; |
---|
352 | |
---|
353 | cout << "dfs from t ..." << endl; |
---|
354 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
---|
355 | dfs.pushAndSetReached(t); |
---|
356 | while (!dfs.finished()) { |
---|
357 | ++dfs; |
---|
358 | //cout << "edge: "; |
---|
359 | if (wG.valid(GW::OutEdgeIt(dfs))) { |
---|
360 | cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
---|
361 | /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
---|
362 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
363 | /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
---|
364 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
365 | ": is not newly reached."); |
---|
366 | } else { |
---|
367 | cout << "invalid" << /*endl*/", " << |
---|
368 | /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
---|
369 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
370 | /*" bNode: " <<*/ |
---|
371 | "invalid."; |
---|
372 | } |
---|
373 | cout << endl; |
---|
374 | } |
---|
375 | } |
---|
376 | |
---|
377 | return 0; |
---|
378 | } |
---|