312 } |
312 } |
313 cout << endl; |
313 cout << endl; |
314 } |
314 } |
315 } |
315 } |
316 |
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 |
317 return 0; |
400 return 0; |
318 } |
401 } |