COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci/iterator_bfs_demo.cc @ 774:4297098d9677

Last change on this file since 774:4297098d9677 was 774:4297098d9677, checked in by Alpar Juttner, 20 years ago

Merge back the whole branches/hugo++ to trunk.
File size: 13.0 KB
RevLine 
[301]1// -*- c++ -*-
2#include <iostream>
3#include <vector>
4#include <string>
5
[642]6#include <sage_graph.h>
[774]7#include <hugo/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{
[774]31  typedef SmartGraph Graph;
32  //typedef SageGraph Graph;
[301]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;
[774]94    for(Graph::NodeIt n(G); n!=INVALID; ++n) {
[304]95      cout << node_name[n] << ": ";
[301]96      cout << "out edges: ";
[774]97      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
[304]98        cout << edge_name[e] << " ";
[301]99      cout << "in edges: ";
[774]100      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++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: ";
[774]110      if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
[304]111        cout << edge_name[bfs] << /*endl*/", " <<
[774]112          node_name[G.tail(bfs)] <<
[301]113          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]114          node_name[G.head(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: ";
[774]144      if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
[304]145        cout << edge_name[dfs] << /*endl*/", " <<
[774]146          node_name[G.tail(dfs)] <<
[301]147          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]148          node_name[G.head(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;
[774]170    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
[317]171      cout << node_name[GW::Node(n)] << ": ";
[301]172      cout << "out edges: ";
[774]173      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
[304]174        cout << edge_name[e] << " ";
[301]175      cout << "in edges: ";
[774]176      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++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: ";
[774]186      if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
[317]187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
[774]188          node_name[gw.tail(bfs)] <<
[301]189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]190          node_name[gw.head(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: ";
[774]220      if (GW::OutEdgeIt(dfs)!=INVALID) {
[317]221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
[774]222          node_name[gw.tail(dfs)] <<
[301]223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]224          node_name[gw.head(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
[774]238//   {
239//     typedef UndirGraphWrapper<const Graph> GW;
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)) {
246//       cout << node_name[GW::Node(n)] << ": ";
247//       cout << "out edges: ";
248//       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
249//      cout << edge_name[e] << " ";
250//       cout << "in edges: ";
251//       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
252//      cout << edge_name[e] << " ";
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;
261//     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
262//     bfs.pushAndSetReached(t);
263//     while (!bfs.finished()) {
264//       //cout << "edge: ";
265//       if (gw.valid(GW::OutEdgeIt(bfs))) {
266//      cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
267//        node_name[gw.aNode(bfs)] <<
268//        (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
269//        node_name[gw.bNode(bfs)] <<
270//        (bfs.isBNodeNewlyReached() ? ": is newly reached." :
271//         ": is not newly reached.");
272//       } else {
273//      cout << "invalid" << /*endl*/", " <<
274//        node_name[bfs.aNode()] <<
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;
294//     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
295//     dfs.pushAndSetReached(t);
296//     while (!dfs.finished()) {
297//       ++dfs;
298//       //cout << "edge: ";
299//       if (gw.valid(GW::OutEdgeIt(dfs))) {
300//      cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
301//        node_name[gw.aNode(dfs)] <<
302//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
303//        node_name[gw.bNode(dfs)] <<
304//        (dfs.isBNodeNewlyReached() ? ": is newly reached." :
305//         ": is not newly reached.");
306//       } else {
307//      cout << "invalid" << /*endl*/", " <<
308//        node_name[dfs.aNode()] <<
309//        (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
310         
311//        "invalid.";
312//       }
313//       cout << endl;
314//     }
315//   }
316
317
318
[301]319  {
[774]320    typedef BidirGraphWrapper<const Graph> GW;
[301]321    GW gw(G);
322   
323    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
324   
[774]325    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
326//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
327//       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
328//     }
329    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
[317]330      cout << node_name[GW::Node(n)] << ": ";
[301]331      cout << "out edges: ";
[774]332      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
[304]333        cout << edge_name[e] << " ";
[301]334      cout << "in edges: ";
[774]335      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
[304]336        cout << edge_name[e] << " ";
[301]337      cout << endl;
338    }
339//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
340//       cout << edge_name.get(e) << " ";
341//     }
342//     cout << endl;
343
344    cout << "bfs from t ..." << endl;
[360]345    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
[301]346    bfs.pushAndSetReached(t);
347    while (!bfs.finished()) {
348      //cout << "edge: ";
[774]349      if (GW::OutEdgeIt(bfs)!=INVALID) {
[304]350        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
[774]351          node_name[gw.tail(bfs)] <<
[301]352          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]353          node_name[gw.head(bfs)] <<
[301]354          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
355           ": is not newly reached.");
356      } else {
357        cout << "invalid" << /*endl*/", " <<
[304]358          node_name[bfs.aNode()] <<
[301]359          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
360         
361          "invalid.";
362      }
363      cout << endl;
364      ++bfs;
365    }
366
367    cout << "    /-->    ------------->            "<< endl;
368    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
369    cout << "  / |          |    /  /->     \\     "<< endl;
370    cout << " /  |          |   /  |    ^    \\  "<< endl;
371    cout << "s   |          |  /   |    |     \\->  t "<< endl;
372    cout << " \\  |          | /    |    |     /->  "<< endl;
373    cout << "  \\ |       --/ /     |    |    /     "<< endl;
374    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
375    cout << "    \\-->    ------------->         "<< endl;
376   
377    cout << "dfs from t ..." << endl;
[360]378    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
[301]379    dfs.pushAndSetReached(t);
380    while (!dfs.finished()) {
381      ++dfs;
382      //cout << "edge: ";
[774]383      if (GW::OutEdgeIt(dfs)!=INVALID) {
[304]384        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
[774]385          node_name[gw.tail(dfs)] <<
[301]386          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
[774]387          node_name[gw.head(dfs)] <<
[301]388          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
389           ": is not newly reached.");
390      } else {
391        cout << "invalid" << /*endl*/", " <<
[304]392          node_name[dfs.aNode()] <<
[301]393          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
394         
395          "invalid.";
396      }
397      cout << endl;
398    }
399  }
400
401  return 0;
402}
Note: See TracBrowser for help on using the repository browser.