89 |
89 |
90 { |
90 { |
91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
92 |
92 |
93 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
93 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
94 for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { |
94 for(Graph::NodeIt n(G); n!=INVALID; ++n) { |
95 cout << node_name[n] << ": "; |
95 cout << node_name[n] << ": "; |
96 cout << "out edges: "; |
96 cout << "out edges: "; |
97 for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) |
97 for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e) |
98 cout << edge_name[e] << " "; |
98 cout << edge_name[e] << " "; |
99 cout << "in edges: "; |
99 cout << "in edges: "; |
100 for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) |
100 for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e) |
101 cout << edge_name[e] << " "; |
101 cout << edge_name[e] << " "; |
102 cout << endl; |
102 cout << endl; |
103 } |
103 } |
104 |
104 |
105 cout << "bfs from s ..." << endl; |
105 cout << "bfs from s ..." << endl; |
106 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
106 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
107 bfs.pushAndSetReached(s); |
107 bfs.pushAndSetReached(s); |
108 while (!bfs.finished()) { |
108 while (!bfs.finished()) { |
109 //cout << "edge: "; |
109 //cout << "edge: "; |
110 if (G.valid(bfs)) { |
110 if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) { |
111 cout << edge_name[bfs] << /*endl*/", " << |
111 cout << edge_name[bfs] << /*endl*/", " << |
112 node_name[G.aNode(bfs)] << |
112 node_name[G.tail(bfs)] << |
113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
114 node_name[G.bNode(bfs)] << |
114 node_name[G.head(bfs)] << |
115 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
115 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
116 ": is not newly reached."); |
116 ": is not newly reached."); |
117 } else { |
117 } else { |
118 cout << "invalid" << /*endl*/", " << |
118 cout << "invalid" << /*endl*/", " << |
119 node_name[bfs.aNode()] << |
119 node_name[bfs.aNode()] << |
139 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G); |
139 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G); |
140 dfs.pushAndSetReached(s); |
140 dfs.pushAndSetReached(s); |
141 while (!dfs.finished()) { |
141 while (!dfs.finished()) { |
142 ++dfs; |
142 ++dfs; |
143 //cout << "edge: "; |
143 //cout << "edge: "; |
144 if (G.valid(dfs)) { |
144 if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) { |
145 cout << edge_name[dfs] << /*endl*/", " << |
145 cout << edge_name[dfs] << /*endl*/", " << |
146 node_name[G.aNode(dfs)] << |
146 node_name[G.tail(dfs)] << |
147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
148 node_name[G.bNode(dfs)] << |
148 node_name[G.head(dfs)] << |
149 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
149 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
150 ": is not newly reached."); |
150 ": is not newly reached."); |
151 } else { |
151 } else { |
152 cout << "invalid" << /*endl*/", " << |
152 cout << "invalid" << /*endl*/", " << |
153 node_name[dfs.aNode()] << |
153 node_name[dfs.aNode()] << |
165 GW gw(G); |
165 GW gw(G); |
166 |
166 |
167 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
167 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
168 |
168 |
169 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
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)) { |
170 for(GW::NodeIt n(gw); n!=INVALID; ++n) { |
171 cout << node_name[GW::Node(n)] << ": "; |
171 cout << node_name[GW::Node(n)] << ": "; |
172 cout << "out edges: "; |
172 cout << "out edges: "; |
173 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
173 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) |
174 cout << edge_name[e] << " "; |
174 cout << edge_name[e] << " "; |
175 cout << "in edges: "; |
175 cout << "in edges: "; |
176 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
176 for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) |
177 cout << edge_name[e] << " "; |
177 cout << edge_name[e] << " "; |
178 cout << endl; |
178 cout << endl; |
179 } |
179 } |
180 |
180 |
181 cout << "bfs from t ..." << endl; |
181 cout << "bfs from t ..." << endl; |
182 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
182 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
183 bfs.pushAndSetReached(t); |
183 bfs.pushAndSetReached(t); |
184 while (!bfs.finished()) { |
184 while (!bfs.finished()) { |
185 //cout << "edge: "; |
185 //cout << "edge: "; |
186 if (gw.valid(GW::OutEdgeIt(bfs))) { |
186 if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) { |
187 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
187 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
188 node_name[gw.aNode(bfs)] << |
188 node_name[gw.tail(bfs)] << |
189 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
189 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
190 node_name[gw.bNode(bfs)] << |
190 node_name[gw.head(bfs)] << |
191 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
191 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
192 ": is not newly reached."); |
192 ": is not newly reached."); |
193 } else { |
193 } else { |
194 cout << "invalid" << /*endl*/", " << |
194 cout << "invalid" << /*endl*/", " << |
195 node_name[bfs.aNode()] << |
195 node_name[bfs.aNode()] << |
215 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
215 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
216 dfs.pushAndSetReached(t); |
216 dfs.pushAndSetReached(t); |
217 while (!dfs.finished()) { |
217 while (!dfs.finished()) { |
218 ++dfs; |
218 ++dfs; |
219 //cout << "edge: "; |
219 //cout << "edge: "; |
220 if (gw.valid(GW::OutEdgeIt(dfs))) { |
220 if (GW::OutEdgeIt(dfs)!=INVALID) { |
221 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
221 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
222 node_name[gw.aNode(dfs)] << |
222 node_name[gw.tail(dfs)] << |
223 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
223 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
224 node_name[gw.bNode(dfs)] << |
224 node_name[gw.head(dfs)] << |
225 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
225 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
226 ": is not newly reached."); |
226 ": is not newly reached."); |
227 } else { |
227 } else { |
228 cout << "invalid" << /*endl*/", " << |
228 cout << "invalid" << /*endl*/", " << |
229 node_name[dfs.aNode()] << |
229 node_name[dfs.aNode()] << |
233 } |
233 } |
234 cout << endl; |
234 cout << endl; |
235 } |
235 } |
236 } |
236 } |
237 |
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 |
238 { |
319 { |
239 typedef UndirGraphWrapper<const Graph> GW; |
320 typedef BidirGraphWrapper<const Graph> GW; |
240 GW gw(G); |
321 GW gw(G); |
241 |
322 |
242 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
323 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
243 |
324 |
244 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
325 cout << "bfs and dfs iterator demo on the bidirected graph" << endl; |
245 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { |
326 // for(GW::EdgeIt e(gw); e!=INVALID; ++e) { |
|
327 // cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " "; |
|
328 // } |
|
329 for(GW::NodeIt n(gw); n!=INVALID; ++n) { |
246 cout << node_name[GW::Node(n)] << ": "; |
330 cout << node_name[GW::Node(n)] << ": "; |
247 cout << "out edges: "; |
331 cout << "out edges: "; |
248 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
332 for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) |
249 cout << edge_name[e] << " "; |
333 cout << edge_name[e] << " "; |
250 cout << "in edges: "; |
334 cout << "in edges: "; |
251 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) |
335 for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) |
252 cout << edge_name[e] << " "; |
336 cout << edge_name[e] << " "; |
253 cout << endl; |
337 cout << endl; |
254 } |
338 } |
255 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
339 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
256 // cout << edge_name.get(e) << " "; |
340 // cout << edge_name.get(e) << " "; |
260 cout << "bfs from t ..." << endl; |
344 cout << "bfs from t ..." << endl; |
261 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
345 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
262 bfs.pushAndSetReached(t); |
346 bfs.pushAndSetReached(t); |
263 while (!bfs.finished()) { |
347 while (!bfs.finished()) { |
264 //cout << "edge: "; |
348 //cout << "edge: "; |
265 if (gw.valid(GW::OutEdgeIt(bfs))) { |
349 if (GW::OutEdgeIt(bfs)!=INVALID) { |
266 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
350 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
267 node_name[gw.aNode(bfs)] << |
351 node_name[gw.tail(bfs)] << |
268 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
352 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
269 node_name[gw.bNode(bfs)] << |
353 node_name[gw.head(bfs)] << |
270 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
354 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
271 ": is not newly reached."); |
355 ": is not newly reached."); |
272 } else { |
356 } else { |
273 cout << "invalid" << /*endl*/", " << |
357 cout << "invalid" << /*endl*/", " << |
274 node_name[bfs.aNode()] << |
358 node_name[bfs.aNode()] << |
294 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
378 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
295 dfs.pushAndSetReached(t); |
379 dfs.pushAndSetReached(t); |
296 while (!dfs.finished()) { |
380 while (!dfs.finished()) { |
297 ++dfs; |
381 ++dfs; |
298 //cout << "edge: "; |
382 //cout << "edge: "; |
299 if (gw.valid(GW::OutEdgeIt(dfs))) { |
383 if (GW::OutEdgeIt(dfs)!=INVALID) { |
300 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
384 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
301 node_name[gw.aNode(dfs)] << |
385 node_name[gw.tail(dfs)] << |
302 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
386 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
303 node_name[gw.bNode(dfs)] << |
387 node_name[gw.head(dfs)] << |
304 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
388 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
305 ": is not newly reached."); |
389 ": is not newly reached."); |
306 } else { |
390 } else { |
307 cout << "invalid" << /*endl*/", " << |
391 cout << "invalid" << /*endl*/", " << |
308 node_name[dfs.aNode()] << |
392 node_name[dfs.aNode()] << |
311 "invalid."; |
395 "invalid."; |
312 } |
396 } |
313 cout << endl; |
397 cout << endl; |
314 } |
398 } |
315 } |
399 } |
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 |
400 return 0; |
401 return 0; |
401 } |
402 } |