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