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/iterator_bfs_demo.cc @ 160:f1a7005e9dff

Last change on this file since 160:f1a7005e9dff was 158:4f54d89fa9d2, checked in by marci, 21 years ago

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