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 @ 628:a3a53d7cedc2

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

bfs_iterator -> bfs_dfs.h, some docs
File size: 12.7 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <vector>
4#include <string>
5
6#include <list_graph.h>
7//#include <smart_graph.h>
8#include <bfs_dfs.h>
9#include <hugo/graph_wrapper.h>
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) { }
23  string operator[](typename Graph::Edge e) const {
24    return
25      (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);
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  {
91    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
92   
93    cout << "bfs and dfs iterator demo on the directed graph" << endl;
94    for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
95      cout << node_name[n] << ": ";
96      cout << "out edges: ";
97      for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
98        cout << edge_name[e] << " ";
99      cout << "in edges: ";
100      for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
101        cout << edge_name[e] << " ";
102      cout << endl;
103    }
104
105    cout << "bfs from s ..." << endl;
106    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
107    bfs.pushAndSetReached(s);
108    while (!bfs.finished()) {
109      //cout << "edge: ";
110      if (G.valid(bfs)) {
111        cout << edge_name[bfs] << /*endl*/", " <<
112          node_name[G.aNode(bfs)] <<
113          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
114          node_name[G.bNode(bfs)] <<
115          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
116           ": is not newly reached.");
117      } else {
118        cout << "invalid" << /*endl*/", " <<
119          node_name[bfs.aNode()] <<
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;
139    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
140    dfs.pushAndSetReached(s);
141    while (!dfs.finished()) {
142      ++dfs;
143      //cout << "edge: ";
144      if (G.valid(dfs)) {
145        cout << edge_name[dfs] << /*endl*/", " <<
146          node_name[G.aNode(dfs)] <<
147          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
148          node_name[G.bNode(dfs)] <<
149          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
150           ": is not newly reached.");
151      } else {
152        cout << "invalid" << /*endl*/", " <<
153          node_name[dfs.aNode()] <<
154          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
155         
156          "invalid.";
157      }
158      cout << endl;
159    }
160  }
161
162
163  {
164    typedef RevGraphWrapper<const Graph> GW;
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)) {
171      cout << node_name[GW::Node(n)] << ": ";
172      cout << "out edges: ";
173      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
174        cout << edge_name[e] << " ";
175      cout << "in edges: ";
176      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
177        cout << edge_name[e] << " ";
178      cout << endl;
179    }
180
181    cout << "bfs from t ..." << endl;
182    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
183    bfs.pushAndSetReached(t);
184    while (!bfs.finished()) {
185      //cout << "edge: ";
186      if (gw.valid(GW::OutEdgeIt(bfs))) {
187        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
188          node_name[gw.aNode(bfs)] <<
189          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
190          node_name[gw.bNode(bfs)] <<
191          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
192           ": is not newly reached.");
193      } else {
194        cout << "invalid" << /*endl*/", " <<
195          node_name[bfs.aNode()] <<
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;
215    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
216    dfs.pushAndSetReached(t);
217    while (!dfs.finished()) {
218      ++dfs;
219      //cout << "edge: ";
220      if (gw.valid(GW::OutEdgeIt(dfs))) {
221        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
222          node_name[gw.aNode(dfs)] <<
223          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
224          node_name[gw.bNode(dfs)] <<
225          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
226           ": is not newly reached.");
227      } else {
228        cout << "invalid" << /*endl*/", " <<
229          node_name[dfs.aNode()] <<
230          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
231         
232          "invalid.";
233      }
234      cout << endl;
235    }
236  }
237
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
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
400  return 0;
401}
Note: See TracBrowser for help on using the repository browser.