COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_demo.cc @ 75:87623302a68f

Last change on this file since 75:87623302a68f was 75:87623302a68f, checked in by marci, 17 years ago

.

File size: 3.4 KB
Line 
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
9using namespace marci;
10
11int main (int, char*[])
12{
13  typedef ListGraph::NodeIt NodeIt;
14  typedef ListGraph::EdgeIt EdgeIt;
15  typedef ListGraph::EachNodeIt EachNodeIt;
16  typedef ListGraph::EachEdgeIt EachEdgeIt;
17  typedef ListGraph::OutEdgeIt OutEdgeIt;
18  typedef ListGraph::InEdgeIt InEdgeIt;
19  typedef ListGraph::SymEdgeIt SymEdgeIt;
20 
21  ListGraph G;
22
23  NodeIt s=G.addNode();
24  NodeIt v1=G.addNode();
25  NodeIt v2=G.addNode();
26  NodeIt v3=G.addNode();
27  NodeIt v4=G.addNode();
28  NodeIt t=G.addNode();
29 
30  G.addEdge(s, v1);
31  G.addEdge(s, v2);
32  G.addEdge(v1, v2);
33  G.addEdge(v2, v1);
34  G.addEdge(v1, v3);
35  G.addEdge(v3, v2);
36  G.addEdge(v2, v4);
37  G.addEdge(v4, v3);
38  G.addEdge(v3, t);
39  G.addEdge(v4, t);
40
41  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
42  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
43    std::cout << i << ": ";
44    std::cout << "out edges: ";
45    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
46      std::cout << j << " ";
47    std::cout << "in edges: ";
48    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
49      std::cout << j << " ";
50    std::cout << std::endl;
51  }
52 
53  {
54    std::cout << "iterator bfs demo 4 ..." << std::endl;
55    BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
56    bfs.pushAndSetReached(s);
57    while (!bfs.finished()) {
58      if (OutEdgeIt(bfs).valid()) {
59        std::cout << "OutEdgeIt: " << bfs;
60        std::cout << " aNode: " << G.aNode(bfs);
61        std::cout << " bNode: " << G.bNode(bfs) << " ";
62      } else {
63        std::cout << "OutEdgeIt: " << "invalid";
64        std::cout << " aNode: " << bfs.aNode();
65        std::cout << " bNode: " << "invalid" << " ";
66      }
67      if (bfs.isBNodeNewlyReached()) {
68        std::cout << "bNodeIsNewlyReached ";
69      } else {
70        std::cout << "bNodeIsNotNewlyReached ";
71      }
72      if (bfs.isANodeExamined()) {
73        std::cout << "aNodeIsExamined ";
74      } else {
75        std::cout << "aNodeIsNotExamined ";
76      }
77      std::cout<<std::endl;
78      ++bfs;
79    }
80  }
81
82  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
83  CTGW wG(G);
84
85  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
86  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) {
87    std::cout << i << ": ";
88    std::cout << "out edges: ";
89    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j)
90      std::cout << j << " ";
91    std::cout << "in edges: ";
92    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j)
93      std::cout << j << " ";
94    std::cout << std::endl;
95  }
96
97
98  {
99    std::cout << "iterator bfs demo 5 ..." << std::endl;
100    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
101    bfs.pushAndSetReached(s);
102    while (!bfs.finished()) {
103      if (OutEdgeIt(bfs).valid()) {
104        std::cout << "OutEdgeIt: " << bfs;
105        std::cout << " aNode: " << wG.aNode(bfs);
106        std::cout << " bNode: " << wG.bNode(bfs) << " ";
107      } else {
108        std::cout << "OutEdgeIt: " << "invalid";
109        std::cout << " aNode: " << bfs.aNode();
110        std::cout << " bNode: " << "invalid" << " ";
111      }
112      if (bfs.isBNodeNewlyReached()) {
113        std::cout << "bNodeIsNewlyReached ";
114      } else {
115        std::cout << "bNodeIsNotNewlyReached ";
116      }
117      if (bfs.isANodeExamined()) {
118        std::cout << "aNodeIsExamined ";
119      } else {
120        std::cout << "aNodeIsNotExamined ";
121      }
122      std::cout<<std::endl;
123      ++bfs;
124    }
125  }
126
127
128  return 0;
129}
Note: See TracBrowser for help on using the repository browser.