COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_dfs_demo.cc @ 45:8fe92d6829e8

Last change on this file since 45:8fe92d6829e8 was 45:8fe92d6829e8, checked in by marci, 20 years ago

iterator style bfs, dfs

File size: 8.5 KB
Line 
1#include <iostream>
2#include <vector>
3#include <string>
4
5#include <list_graph.hh>
6#include <bfs_iterator.hh>
7
8using namespace marci;
9
10int main (int, char*[])
11{
12  typedef ListGraph::NodeIt NodeIt;
13  typedef ListGraph::EdgeIt EdgeIt;
14  typedef ListGraph::EachNodeIt EachNodeIt;
15  typedef ListGraph::EachEdgeIt EachEdgeIt;
16  typedef ListGraph::OutEdgeIt OutEdgeIt;
17  typedef ListGraph::InEdgeIt InEdgeIt;
18  typedef ListGraph::SymEdgeIt SymEdgeIt;
19 
20  ListGraph G;
21
22  NodeIt s=G.addNode();
23  NodeIt v1=G.addNode();
24  NodeIt v2=G.addNode();
25  NodeIt v3=G.addNode();
26  NodeIt v4=G.addNode();
27  NodeIt t=G.addNode();
28 
29  G.addEdge(s, v1);
30  G.addEdge(s, v2);
31  G.addEdge(v1, v2);
32  G.addEdge(v2, v1);
33  G.addEdge(v1, v3);
34  G.addEdge(v3, v2);
35  G.addEdge(v2, v4);
36  G.addEdge(v4, v3);
37  G.addEdge(v3, t);
38  G.addEdge(v4, t);
39
40  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
41  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
42    std::cout << i << ": ";
43    std::cout << "out edges: ";
44    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
45      std::cout << j << " ";
46    std::cout << "in edges: ";
47    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
48      std::cout << j << " ";
49    std::cout << std::endl;
50  }
51
52  //std::cout << std::endl;
53  //EachNodeIt u1=G.first<EachNodeIt>();
54  //EachEdgeIt u=G.first<EachEdgeIt>();
55  //OutEdgeIt u=G.first<OutEdgeIt>(s);
56  //InEdgeIt u=G.first<InEdgeIt>(s);
57  //SymEdgeIt u=G.first<SymEdgeIt>(s);
58  //OutEdgeIt u=G.first<OutEdgeIt>(s);
59  //EachNodeIt u=G.first<EachNodeIt>();
60  //EachEdgeIt u=G.first<EachEdgeIt>();
61  //OutEdgeIt u=G.first<OutEdgeIt>(s);
62  //InEdgeIt u=G.first<InEdgeIt>(s);
63  //SymEdgeIt u=G.first<SymEdgeIt>(s);
64  //u=G.first(s);
65  //u=G.first_ize(s, OutEdgeIt());
66  //std::cout << "ize " << u << std::endl;
67
68  /*
69  {
70    std::cout << "iterator bfs demo..." << std::endl;
71    NodePropertyVector<ListGraph, bool> reached(G, false);
72    reached.set(s, true);
73    std::queue<ListGraph::OutEdgeIt> bfs_queue;
74    bfs_queue.push(G.firstOutEdge(G.firstNode()));
75    BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached);
76    for ( ; !bfs.finished(); ++bfs) {
77      if (OutEdgeIt(bfs).valid()) {
78        std::cout << "OutEdgeIt: " << bfs;
79        std::cout << " aNode: " << G.aNode(bfs);
80        std::cout << " bNode: " << G.bNode(bfs) << " ";
81      } else {
82        std::cout << "OutEdgeIt: " << "invalid";
83        std::cout << " aNode: " << G.aNode(bfs);
84        std::cout << " bNode: " << "invalid" << " ";
85      }
86      if (bfs.bNodeIsNewlyReached()) {
87        std::cout << "bNodeIsNewlyReached ";
88      } else {
89        std::cout << "bNodeIsNotNewlyReached ";
90      }
91      if (bfs.aNodeIsExamined()) {
92        std::cout << "aNodeIsExamined ";
93      } else {
94        std::cout << "aNodeIsNotExamined ";
95      }
96      std::cout<<std::endl;
97    }
98  }
99
100  {
101    std::cout << "iterator dfs demo..." << std::endl;
102    NodePropertyVector<ListGraph, bool> reached(G, false);
103    reached.set(s, true);
104    std::stack<ListGraph::OutEdgeIt> dfs_stack;
105    dfs_stack.push(G.firstOutEdge(G.firstNode()));
106    DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached);
107    for(; !dfs.finished(); ++dfs) {
108      if (OutEdgeIt(dfs).valid()) {
109        std::cout << "OutEdgeIt: " << dfs;
110        std::cout << " aNode: " << G.aNode(dfs);
111        std::cout << " bNode: " << G.bNode(dfs) << " ";
112      } else {
113        std::cout << "OutEdgeIt: " << "invalid";
114        std::cout << " aNode: " << G.aNode(dfs);
115        std::cout << " bNode: " << "invalid" << " ";
116      }
117      if (dfs.bNodeIsNewlyReached()) {
118        std::cout << "bNodeIsNewlyReached ";
119      } else {
120        std::cout << "bNodeIsNotNewlyReached ";
121      }
122      if (dfs.aNodeIsLeaved()) {
123        std::cout << "aNodeIsLeaved ";
124      } else {
125        std::cout << "aNodeIsNotLeaved ";
126      }
127      std::cout<<std::endl;
128    }
129    if (OutEdgeIt(dfs).valid()) {
130      std::cout << "OutEdgeIt: " << dfs;
131      std::cout << " aNode: " << G.aNode(dfs);
132      std::cout << " bNode: " << G.bNode(dfs) << " ";
133    } else {
134      std::cout << "OutEdgeIt: " << "invalid";
135      std::cout << " aNode: " << G.aNode(dfs);
136      std::cout << " bNode: " << "invalid" << " ";
137    }
138    if (dfs.bNodeIsNewlyReached()) {
139      std::cout << "bNodeIsNewlyReached ";
140    } else {
141      std::cout << "bNodeIsNotNewlyReached ";
142    }
143    if (dfs.aNodeIsLeaved()) {
144      std::cout << "aNodeIsLeaved ";
145    } else {
146      std::cout << "aNodeIsNotLeaved ";
147    }
148    std::cout<<std::endl;
149  }
150  */
151
152  {
153    std::cout << "iterator bfs demo 1 ..." << std::endl;
154    ListGraph::NodeMap<bool> reached(G, false);
155    reached.set(s, true);
156    std::queue<ListGraph::OutEdgeIt> bfs_queue;
157    bfs_queue.push(G.first<OutEdgeIt>(s));
158    BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
159    while (!bfs.finished()) {
160      if (OutEdgeIt(bfs).valid()) {
161        std::cout << "OutEdgeIt: " << bfs;
162        std::cout << " aNode: " << G.aNode(bfs);
163        std::cout << " bNode: " << G.bNode(bfs) << " ";
164      } else {
165        std::cout << "OutEdgeIt: " << "invalid";
166        std::cout << " aNode: " << G.aNode(bfs);
167        std::cout << " bNode: " << "invalid" << " ";
168      }
169      if (bfs.bNodeIsNewlyReached()) {
170        std::cout << "bNodeIsNewlyReached ";
171      } else {
172        std::cout << "bNodeIsNotNewlyReached ";
173      }
174      if (bfs.aNodeIsExamined()) {
175        std::cout << "aNodeIsExamined ";
176      } else {
177        std::cout << "aNodeIsNotExamined ";
178      }
179      std::cout<<std::endl;
180      bfs.next();
181    }
182  }
183 
184
185  {
186    std::cout << "iterator dfs demo 1..." << std::endl;
187    ListGraph::NodeMap<bool> reached(G, false);
188    reached.set(s, true);
189    std::stack<ListGraph::OutEdgeIt> dfs_stack;
190    dfs_stack.push(G.first<OutEdgeIt>(s));
191    DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
192    do {
193      dfs.next();
194      if (OutEdgeIt(dfs).valid()) {
195        std::cout << "OutEdgeIt: " << dfs;
196        std::cout << " aNode: " << G.aNode(dfs);
197        std::cout << " bNode: " << G.bNode(dfs) << " ";
198      } else {
199        std::cout << "OutEdgeIt: " << "invalid";
200        std::cout << " aNode: " << G.aNode(dfs);
201        std::cout << " bNode: " << "invalid" << " ";
202      }
203      if (dfs.bNodeIsNewlyReached()) {
204        std::cout << "bNodeIsNewlyReached ";
205      } else {
206        std::cout << "bNodeIsNotNewlyReached ";
207      }
208      if (dfs.aNodeIsLeaved()) {
209        std::cout << "aNodeIsLeaved ";
210      } else {
211        std::cout << "aNodeIsNotLeaved ";
212      }
213      std::cout<<std::endl;
214    } while (!dfs.finished());
215  }
216
217
218  {
219    std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
220    ListGraph::NodeMap<bool> reached(G, false);
221    reached.set(t, true);
222    std::queue<ListGraph::InEdgeIt> bfs_queue;
223    bfs_queue.push(G.first<InEdgeIt>(t));
224    BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
225    while (!bfs.finished()) {
226      if (InEdgeIt(bfs).valid()) {
227        std::cout << "InEdgeIt: " << bfs;
228        std::cout << " aNode: " << G.aNode(bfs);
229        std::cout << " bNode: " << G.bNode(bfs) << " ";
230      } else {
231        std::cout << "InEdgeIt: " << "invalid";
232        std::cout << " aNode: " << G.aNode(bfs);
233        std::cout << " bNode: " << "invalid" << " ";
234      }
235      if (bfs.bNodeIsNewlyReached()) {
236        std::cout << "bNodeIsNewlyReached ";
237      } else {
238        std::cout << "bNodeIsNotNewlyReached ";
239      }
240      if (bfs.aNodeIsExamined()) {
241        std::cout << "aNodeIsExamined ";
242      } else {
243        std::cout << "aNodeIsNotExamined ";
244      }
245      std::cout<<std::endl;
246      bfs.next();
247    }
248  }
249 
250
251  {
252    std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
253    ListGraph::NodeMap<bool> reached(G, false);
254    reached.set(t, true);
255    std::queue<ListGraph::SymEdgeIt> bfs_queue;
256    bfs_queue.push(G.first<SymEdgeIt>(t));
257    BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
258    while (!bfs.finished()) {
259      if (SymEdgeIt(bfs).valid()) {
260        std::cout << "SymEdgeIt: " << bfs;
261        std::cout << " aNode: " << G.aNode(bfs);
262        std::cout << " bNode: " << G.bNode(bfs) << " ";
263      } else {
264        std::cout << "SymEdgeIt: " << "invalid";
265        std::cout << " aNode: " << G.aNode(bfs);
266        std::cout << " bNode: " << "invalid" << " ";
267      }
268      if (bfs.bNodeIsNewlyReached()) {
269        std::cout << "bNodeIsNewlyReached ";
270      } else {
271        std::cout << "bNodeIsNotNewlyReached ";
272      }
273      if (bfs.aNodeIsExamined()) {
274        std::cout << "aNodeIsExamined ";
275      } else {
276        std::cout << "aNodeIsNotExamined ";
277      }
278      std::cout<<std::endl;
279      bfs.next();
280    }
281  }
282
283  return 0;
284}
Note: See TracBrowser for help on using the repository browser.