COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/iterator_bfs_demo.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 16 years ago

Naming changes:

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