COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_dfs_demo.cc @ 941:186aa53d2802

Last change on this file since 941:186aa53d2802 was 921:818510fa3d99, checked in by Alpar Juttner, 20 years ago

hugo -> lemon

File size: 9.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 lemon;
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    std::cout << "iterator bfs demo 2 ..." << std::endl;
186    //ListGraph::NodeMap<bool> reached(G, false);
187    //reached.set(s, true);
188    //std::queue<ListGraph::OutEdgeIt> bfs_queue;
189    //bfs_queue.push(G.first<OutEdgeIt>(s));
190    BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
191    bfs.pushAndSetReached(s);
192    while (!bfs.finished()) {
193      if (OutEdgeIt(bfs).valid()) {
194        std::cout << "OutEdgeIt: " << bfs;
195        std::cout << " aNode: " << G.aNode(bfs);
196        std::cout << " bNode: " << G.bNode(bfs) << " ";
197      } else {
198        std::cout << "OutEdgeIt: " << "invalid";
199        std::cout << " aNode: " << G.aNode(bfs);
200        std::cout << " bNode: " << "invalid" << " ";
201      }
202      if (bfs.isBNodeNewlyReached()) {
203        std::cout << "bNodeIsNewlyReached ";
204      } else {
205        std::cout << "bNodeIsNotNewlyReached ";
206      }
207      if (bfs.isANodeExamined()) {
208        std::cout << "aNodeIsExamined ";
209      } else {
210        std::cout << "aNodeIsNotExamined ";
211      }
212      std::cout<<std::endl;
213      ++bfs;
214    }
215  }
216 
217
218
219
220  {
221    std::cout << "iterator dfs demo 1..." << std::endl;
222    ListGraph::NodeMap<bool> reached(G, false);
223    reached.set(s, true);
224    std::stack<ListGraph::OutEdgeIt> dfs_stack;
225    dfs_stack.push(G.first<OutEdgeIt>(s));
226    DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
227    do {
228      dfs.next();
229      if (OutEdgeIt(dfs).valid()) {
230        std::cout << "OutEdgeIt: " << dfs;
231        std::cout << " aNode: " << G.aNode(dfs);
232        std::cout << " bNode: " << G.bNode(dfs) << " ";
233      } else {
234        std::cout << "OutEdgeIt: " << "invalid";
235        std::cout << " aNode: " << G.aNode(dfs);
236        std::cout << " bNode: " << "invalid" << " ";
237      }
238      if (dfs.bNodeIsNewlyReached()) {
239        std::cout << "bNodeIsNewlyReached ";
240      } else {
241        std::cout << "bNodeIsNotNewlyReached ";
242      }
243      if (dfs.aNodeIsLeaved()) {
244        std::cout << "aNodeIsLeaved ";
245      } else {
246        std::cout << "aNodeIsNotLeaved ";
247      }
248      std::cout<<std::endl;
249    } while (!dfs.finished());
250  }
251
252
253  {
254    std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
255    ListGraph::NodeMap<bool> reached(G, false);
256    reached.set(t, true);
257    std::queue<ListGraph::InEdgeIt> bfs_queue;
258    bfs_queue.push(G.first<InEdgeIt>(t));
259    BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
260    while (!bfs.finished()) {
261      if (InEdgeIt(bfs).valid()) {
262        std::cout << "InEdgeIt: " << bfs;
263        std::cout << " aNode: " << G.aNode(bfs);
264        std::cout << " bNode: " << G.bNode(bfs) << " ";
265      } else {
266        std::cout << "InEdgeIt: " << "invalid";
267        std::cout << " aNode: " << G.aNode(bfs);
268        std::cout << " bNode: " << "invalid" << " ";
269      }
270      if (bfs.bNodeIsNewlyReached()) {
271        std::cout << "bNodeIsNewlyReached ";
272      } else {
273        std::cout << "bNodeIsNotNewlyReached ";
274      }
275      if (bfs.aNodeIsExamined()) {
276        std::cout << "aNodeIsExamined ";
277      } else {
278        std::cout << "aNodeIsNotExamined ";
279      }
280      std::cout<<std::endl;
281      bfs.next();
282    }
283  }
284 
285
286  {
287    std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
288    ListGraph::NodeMap<bool> reached(G, false);
289    reached.set(t, true);
290    std::queue<ListGraph::SymEdgeIt> bfs_queue;
291    bfs_queue.push(G.first<SymEdgeIt>(t));
292    BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
293    while (!bfs.finished()) {
294      if (SymEdgeIt(bfs).valid()) {
295        std::cout << "SymEdgeIt: " << bfs;
296        std::cout << " aNode: " << G.aNode(bfs);
297        std::cout << " bNode: " << G.bNode(bfs) << " ";
298      } else {
299        std::cout << "SymEdgeIt: " << "invalid";
300        std::cout << " aNode: " << G.aNode(bfs);
301        std::cout << " bNode: " << "invalid" << " ";
302      }
303      if (bfs.bNodeIsNewlyReached()) {
304        std::cout << "bNodeIsNewlyReached ";
305      } else {
306        std::cout << "bNodeIsNotNewlyReached ";
307      }
308      if (bfs.aNodeIsExamined()) {
309        std::cout << "aNodeIsExamined ";
310      } else {
311        std::cout << "aNodeIsNotExamined ";
312      }
313      std::cout<<std::endl;
314      bfs.next();
315    }
316  }
317
318  return 0;
319}
Note: See TracBrowser for help on using the repository browser.