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 @ 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: 12.4 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <vector>
4#include <string>
5
6#include <sage_graph.h>
7#include <lemon/smart_graph.h>
8#include <bfs_dfs.h>
9#include <lemon/graph_wrapper.h>
10
11using namespace lemon;
12
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) { }
24  string operator[](typename Graph::Edge e) const {
25    return
26      (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);
27  }
28};
29
30int main (int, char*[])
31{
32  typedef SmartGraph Graph;
33  //typedef SageGraph Graph;
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  {
77    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
78   
79    cout << "bfs and dfs iterator demo on the directed graph" << endl;
80    for(Graph::NodeIt n(G); n!=INVALID; ++n) {
81      cout << node_name[n] << ": ";
82      cout << "out edges: ";
83      for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
84        cout << edge_name[e] << " ";
85      cout << "in edges: ";
86      for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
87        cout << edge_name[e] << " ";
88      cout << endl;
89    }
90
91    cout << "bfs from s ..." << endl;
92    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
93    bfs.pushAndSetReached(s);
94    while (!bfs.finished()) {
95      //cout << "edge: ";
96      if (Graph::Edge(bfs)!=INVALID) {
97        cout << edge_name[bfs] << /*endl*/", " <<
98          node_name[G.tail(bfs)] <<
99          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
100          node_name[G.head(bfs)] <<
101          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
102           ": is not newly reached.");
103      } else {
104        cout << "invalid" << /*endl*/", " <<
105          node_name[bfs.tail()] <<
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;
125    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
126    dfs.pushAndSetReached(s);
127    while (!dfs.finished()) {
128      ++dfs;
129      //cout << "edge: ";
130      if (Graph::Edge(dfs)!=INVALID) {
131        cout << edge_name[dfs] << /*endl*/", " <<
132          node_name[G.tail(dfs)] <<
133          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
134          node_name[G.head(dfs)] <<
135          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
136           ": is not newly reached.");
137      } else {
138        cout << "invalid" << /*endl*/", " <<
139          node_name[dfs.tail()] <<
140          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
141         
142          "invalid.";
143      }
144      cout << endl;
145    }
146  }
147
148
149  {
150    typedef RevGraphWrapper<const Graph> GW;
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;
156    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
157      cout << node_name[GW::Node(n)] << ": ";
158      cout << "out edges: ";
159      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
160        cout << edge_name[e] << " ";
161      cout << "in edges: ";
162      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
163        cout << edge_name[e] << " ";
164      cout << endl;
165    }
166
167    cout << "bfs from t ..." << endl;
168    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
169    bfs.pushAndSetReached(t);
170    while (!bfs.finished()) {
171      //cout << "edge: ";
172      if (GW::Edge(bfs)!=INVALID) {
173        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
174          node_name[gw.tail(bfs)] <<
175          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
176          node_name[gw.head(bfs)] <<
177          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
178           ": is not newly reached.");
179      } else {
180        cout << "invalid" << /*endl*/", " <<
181          node_name[bfs.tail()] <<
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;
201    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
202    dfs.pushAndSetReached(t);
203    while (!dfs.finished()) {
204      ++dfs;
205      //cout << "edge: ";
206      if (GW::Edge(dfs)!=INVALID) {
207        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
208          node_name[gw.tail(dfs)] <<
209          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
210          node_name[gw.head(dfs)] <<
211          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
212           ": is not newly reached.");
213      } else {
214        cout << "invalid" << /*endl*/", " <<
215          node_name[dfs.tail()] <<
216          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
217         
218          "invalid.";
219      }
220      cout << endl;
221    }
222  }
223
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
305  {
306    typedef BidirGraphWrapper<const Graph> GW;
307    GW gw(G);
308   
309    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
310   
311    cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
312//     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
313//       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
314//     }
315    for(GW::NodeIt n(gw); n!=INVALID; ++n) {
316      cout << node_name[GW::Node(n)] << ": ";
317      cout << "out edges: ";
318      for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
319        cout << edge_name[e] << " ";
320      cout << "in edges: ";
321      for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
322        cout << edge_name[e] << " ";
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;
331    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
332    bfs.pushAndSetReached(t);
333    while (!bfs.finished()) {
334      //cout << "edge: ";
335      if (GW::Edge(bfs)!=INVALID) {
336        cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
337          node_name[gw.tail(bfs)] <<
338          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
339          node_name[gw.head(bfs)] <<
340          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
341           ": is not newly reached.");
342      } else {
343        cout << "invalid" << /*endl*/", " <<
344          node_name[bfs.tail()] <<
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;
364    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
365    dfs.pushAndSetReached(t);
366    while (!dfs.finished()) {
367      ++dfs;
368      //cout << "edge: ";
369      if (GW::Edge(dfs)!=INVALID) {
370        cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
371          node_name[gw.tail(dfs)] <<
372          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
373          node_name[gw.head(dfs)] <<
374          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
375           ": is not newly reached.");
376      } else {
377        cout << "invalid" << /*endl*/", " <<
378          node_name[dfs.tail()] <<
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.