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