COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/iterator_bfs_demo.cc @ 602:580b329c2a0c

Last change on this file since 602:580b329c2a0c was 602:580b329c2a0c, checked in by marci, 20 years ago

bfs_iterator -> bfs_dfs.h, some docs

File size: 12.7 KB
RevLine 
[301]1// -*- c++ -*-
2#include <iostream>
3#include <vector>
4#include <string>
5
6#include <list_graph.h>
[389]7//#include <smart_graph.h>
[602]8#include <bfs_dfs.h>
[557]9#include <hugo/graph_wrapper.h>
[301]10
11using namespace hugo;
12using std::cout;
13using std::endl;
14using std::string;
15
16template <typename Graph, typename NodeNameMap>
17class EdgeNameMap {
18  Graph& graph;
19  NodeNameMap& node_name_map;
20public:
21  EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
22    graph(_graph), node_name_map(_node_name_map) { }
[304]23  string operator[](typename Graph::Edge e) const {
[301]24    return
[304]25      (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);
[301]26  }
27};
28
29int main (int, char*[])
30{
31  //typedef SmartGraph Graph;
32  typedef ListGraph Graph;
33
34  typedef Graph::Node Node;
35  typedef Graph::Edge Edge;
36 
37  Graph G;
38
39  Node s=G.addNode();
40  Node v1=G.addNode();
41  Node v2=G.addNode();
42  Node v3=G.addNode();
43  Node v4=G.addNode();
44  Node t=G.addNode();
45 
46  Graph::NodeMap<string> node_name(G);
47  node_name.set(s, "s");
48  node_name.set(v1, "v1");
49  node_name.set(v2, "v2");
50  node_name.set(v3, "v3");
51  node_name.set(v4, "v4");
52  node_name.set(t, "t");
53
54  G.addEdge(s, v1);
55  G.addEdge(s, v2);
56  G.addEdge(v1, v2);
57  G.addEdge(v2, v1);
58  G.addEdge(v1, v3);
59  G.addEdge(v3, v2);
60  G.addEdge(v2, v4);
61  G.addEdge(v4, v3);
62  G.addEdge(v3, t);
63  G.addEdge(v4, t);
64
65  cout << "    /-->    ------------->            "<< endl;
66  cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
67  cout << "  / |          |    /  /->     \\     "<< endl;
68  cout << " /  |          |   /  |    ^    \\  "<< endl;
69  cout << "s   |          |  /   |    |     \\->  t "<< endl;
70  cout << " \\  |          | /    |    |     /->  "<< endl;
71  cout << "  \\ |       --/ /     |    |    /     "<< endl;
72  cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
73  cout << "    \\-->    ------------->         "<< endl;
74 
75//   typedef TrivGraphWrapper<const Graph> CGW;
76//   CGW gw(G);
77
78//   cout << "bfs and dfs demo on the directed graph" << endl;
79//   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
80//     cout << n << ": ";
81//     cout << "out edges: ";
82//     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
83//       cout << e << " ";
84//     cout << "in edges: ";
85//     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
86//       cout << e << " ";
87//     cout << endl;
88//   }
89
90  {
[312]91    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
[301]92   
93    cout << "bfs and dfs iterator demo on the directed graph" << endl;
[312]94    for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
[304]95      cout << node_name[n] << ": ";
[301]96      cout << "out edges: ";
[312]97      for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
[304]98        cout << edge_name[e] << " ";
[301]99      cout << "in edges: ";
[312]100      for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
[304]101        cout << edge_name[e] << " ";
[301]102      cout << endl;
103    }
104
105    cout << "bfs from s ..." << endl;
[360]106    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
[301]107    bfs.pushAndSetReached(s);
108    while (!bfs.finished()) {
109      //cout << "edge: ";
[312]110      if (G.valid(bfs)) {
[304]111        cout << edge_name[bfs] << /*endl*/", " <<
[312]112          node_name[G.aNode(bfs)] <<
[301]113          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[312]114          node_name[G.bNode(bfs)] <<
[301]115          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
116           ": is not newly reached.");
117      } else {
118        cout << "invalid" << /*endl*/", " <<
[304]119          node_name[bfs.aNode()] <<
[301]120          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
121         
122          "invalid.";
123      }
124      cout << endl;
125      ++bfs;
126    }
127
128    cout << "    /-->    ------------->            "<< endl;
129    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
130    cout << "  / |          |    /  /->     \\     "<< endl;
131    cout << " /  |          |   /  |    ^    \\  "<< endl;
132    cout << "s   |          |  /   |    |     \\->  t "<< endl;
133    cout << " \\  |          | /    |    |     /->  "<< endl;
134    cout << "  \\ |       --/ /     |    |    /     "<< endl;
135    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
136    cout << "    \\-->    ------------->         "<< endl;
137
138    cout << "dfs from s ..." << endl;
[360]139    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
[301]140    dfs.pushAndSetReached(s);
141    while (!dfs.finished()) {
142      ++dfs;
143      //cout << "edge: ";
[312]144      if (G.valid(dfs)) {
[304]145        cout << edge_name[dfs] << /*endl*/", " <<
[312]146          node_name[G.aNode(dfs)] <<
[301]147          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[312]148          node_name[G.bNode(dfs)] <<
[301]149          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
150           ": is not newly reached.");
151      } else {
152        cout << "invalid" << /*endl*/", " <<
[304]153          node_name[dfs.aNode()] <<
[301]154          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
155         
156          "invalid.";
157      }
158      cout << endl;
159    }
160  }
161
162
163  {
[312]164    typedef RevGraphWrapper<const Graph> GW;
[301]165    GW gw(G);
166   
167    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
168   
169    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
170    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
[317]171      cout << node_name[GW::Node(n)] << ": ";
[301]172      cout << "out edges: ";
173      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
[304]174        cout << edge_name[e] << " ";
[301]175      cout << "in edges: ";
176      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
[304]177        cout << edge_name[e] << " ";
[301]178      cout << endl;
179    }
180
181    cout << "bfs from t ..." << endl;
[360]182    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
[301]183    bfs.pushAndSetReached(t);
184    while (!bfs.finished()) {
185      //cout << "edge: ";
[317]186      if (gw.valid(GW::OutEdgeIt(bfs))) {
187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
[304]188          node_name[gw.aNode(bfs)] <<
[301]189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[304]190          node_name[gw.bNode(bfs)] <<
[301]191          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
192           ": is not newly reached.");
193      } else {
194        cout << "invalid" << /*endl*/", " <<
[304]195          node_name[bfs.aNode()] <<
[301]196          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
197         
198          "invalid.";
199      }
200      cout << endl;
201      ++bfs;
202    }
203
204    cout << "    /-->    ------------->            "<< endl;
205    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
206    cout << "  / |          |    /  /->     \\     "<< endl;
207    cout << " /  |          |   /  |    ^    \\  "<< endl;
208    cout << "s   |          |  /   |    |     \\->  t "<< endl;
209    cout << " \\  |          | /    |    |     /->  "<< endl;
210    cout << "  \\ |       --/ /     |    |    /     "<< endl;
211    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
212    cout << "    \\-->    ------------->         "<< endl;
213   
214    cout << "dfs from t ..." << endl;
[360]215    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
[301]216    dfs.pushAndSetReached(t);
217    while (!dfs.finished()) {
218      ++dfs;
219      //cout << "edge: ";
[317]220      if (gw.valid(GW::OutEdgeIt(dfs))) {
221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
[304]222          node_name[gw.aNode(dfs)] <<
[301]223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[304]224          node_name[gw.bNode(dfs)] <<
[301]225          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
226           ": is not newly reached.");
227      } else {
228        cout << "invalid" << /*endl*/", " <<
[304]229          node_name[dfs.aNode()] <<
[301]230          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
231         
232          "invalid.";
233      }
234      cout << endl;
235    }
236  }
237
238  {
[312]239    typedef UndirGraphWrapper<const Graph> GW;
[301]240    GW gw(G);
241   
242    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
243   
244    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
245    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
[317]246      cout << node_name[GW::Node(n)] << ": ";
[301]247      cout << "out edges: ";
248      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
[304]249        cout << edge_name[e] << " ";
[301]250      cout << "in edges: ";
251      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
[304]252        cout << edge_name[e] << " ";
[301]253      cout << endl;
254    }
255//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
256//       cout << edge_name.get(e) << " ";
257//     }
258//     cout << endl;
259
260    cout << "bfs from t ..." << endl;
[360]261    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
[301]262    bfs.pushAndSetReached(t);
263    while (!bfs.finished()) {
264      //cout << "edge: ";
265      if (gw.valid(GW::OutEdgeIt(bfs))) {
[304]266        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
267          node_name[gw.aNode(bfs)] <<
[301]268          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[304]269          node_name[gw.bNode(bfs)] <<
[301]270          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
271           ": is not newly reached.");
272      } else {
273        cout << "invalid" << /*endl*/", " <<
[304]274          node_name[bfs.aNode()] <<
[301]275          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
276         
277          "invalid.";
278      }
279      cout << endl;
280      ++bfs;
281    }
282
283    cout << "    /-->    ------------->            "<< endl;
284    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
285    cout << "  / |          |    /  /->     \\     "<< endl;
286    cout << " /  |          |   /  |    ^    \\  "<< endl;
287    cout << "s   |          |  /   |    |     \\->  t "<< endl;
288    cout << " \\  |          | /    |    |     /->  "<< endl;
289    cout << "  \\ |       --/ /     |    |    /     "<< endl;
290    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
291    cout << "    \\-->    ------------->         "<< endl;
292   
293    cout << "dfs from t ..." << endl;
[360]294    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
[301]295    dfs.pushAndSetReached(t);
296    while (!dfs.finished()) {
297      ++dfs;
298      //cout << "edge: ";
299      if (gw.valid(GW::OutEdgeIt(dfs))) {
[304]300        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
301          node_name[gw.aNode(dfs)] <<
[301]302          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[304]303          node_name[gw.bNode(dfs)] <<
[301]304          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
305           ": is not newly reached.");
306      } else {
307        cout << "invalid" << /*endl*/", " <<
[304]308          node_name[dfs.aNode()] <<
[301]309          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
310         
311          "invalid.";
312      }
313      cout << endl;
314    }
315  }
316
[569]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
[301]400  return 0;
401}
Note: See TracBrowser for help on using the repository browser.