COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_demo.cc @ 99:f26897fb91fd

Last change on this file since 99:f26897fb91fd was 99:f26897fb91fd, checked in by marci, 20 years ago

dfs iterator: DfsIterator4 improved version

File size: 4.3 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  {
83    std::cout << "iterator dfs demo 4 ..." << std::endl;
84    DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
85    dfs.pushAndSetReached(s);
86    while (!dfs.finished()) {
87      ++dfs;
88      if (OutEdgeIt(dfs).valid()) {
89        std::cout << "OutEdgeIt: " << dfs;
90        std::cout << " aNode: " << G.aNode(dfs);
91        std::cout << " bNode: " << G.bNode(dfs) << " ";
92      } else {
93        std::cout << "OutEdgeIt: " << "invalid";
94        std::cout << " aNode: " << dfs.aNode();
95        std::cout << " bNode: " << "invalid" << " ";
96      }
97      if (dfs.isBNodeNewlyReached()) {
98        std::cout << "bNodeIsNewlyReached ";
99      } else {
100        std::cout << "bNodeIsNotNewlyReached ";
101      }
102      if (dfs.isANodeExamined()) {
103        std::cout << "aNodeIsExamined ";
104      } else {
105        std::cout << "aNodeIsNotExamined ";
106      }
107      std::cout<<std::endl;
108      //++dfs;
109    }
110  }
111
112
113  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
114  CTGW wG(G);
115
116  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
117  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) {
118    std::cout << i << ": ";
119    std::cout << "out edges: ";
120    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j)
121      std::cout << j << " ";
122    std::cout << "in edges: ";
123    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j)
124      std::cout << j << " ";
125    std::cout << std::endl;
126  }
127
128
129  {
130    std::cout << "iterator bfs demo 5 ..." << std::endl;
131    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
132    bfs.pushAndSetReached(s);
133    while (!bfs.finished()) {
134      if (OutEdgeIt(bfs).valid()) {
135        std::cout << "OutEdgeIt: " << bfs;
136        std::cout << " aNode: " << wG.aNode(bfs);
137        std::cout << " bNode: " << wG.bNode(bfs) << " ";
138      } else {
139        std::cout << "OutEdgeIt: " << "invalid";
140        std::cout << " aNode: " << bfs.aNode();
141        std::cout << " bNode: " << "invalid" << " ";
142      }
143      if (bfs.isBNodeNewlyReached()) {
144        std::cout << "bNodeIsNewlyReached ";
145      } else {
146        std::cout << "bNodeIsNotNewlyReached ";
147      }
148      if (bfs.isANodeExamined()) {
149        std::cout << "aNodeIsExamined ";
150      } else {
151        std::cout << "aNodeIsNotExamined ";
152      }
153      std::cout<<std::endl;
154      ++bfs;
155    }
156  }
157
158
159  return 0;
160}
Note: See TracBrowser for help on using the repository browser.