COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_demo.cc @ 209:9a37b8d02d74

Last change on this file since 209:9a37b8d02d74 was 174:44700ed9ffaa, checked in by marci, 20 years ago

towards on ListGraph?, SmartGraph? compatibility

File size: 10.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_iterator.h>
9#include <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 get(typename Graph::Edge e) const {
24    return
25      (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(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  //typedef Graph::NodeIt NodeIt;
37  //typedef Graph::EdgeIt EdgeIt;
38  //typedef Graph::OutEdgeIt OutEdgeIt;
39  //typedef Graph::InEdgeIt InEdgeIt;
40  //typedef Graph::SymEdgeIt SymEdgeIt;
41 
42  Graph G;
43
44  Node s=G.addNode();
45  Node v1=G.addNode();
46  Node v2=G.addNode();
47  Node v3=G.addNode();
48  Node v4=G.addNode();
49  Node t=G.addNode();
50 
51  Graph::NodeMap<string> node_name(G);
52  node_name.set(s, "s");
53  node_name.set(v1, "v1");
54  node_name.set(v2, "v2");
55  node_name.set(v3, "v3");
56  node_name.set(v4, "v4");
57  node_name.set(t, "t");
58
59  G.addEdge(s, v1);
60  G.addEdge(s, v2);
61  G.addEdge(v1, v2);
62  G.addEdge(v2, v1);
63  G.addEdge(v1, v3);
64  G.addEdge(v3, v2);
65  G.addEdge(v2, v4);
66  G.addEdge(v4, v3);
67  G.addEdge(v3, t);
68  G.addEdge(v4, t);
69
70  cout << "    /-->    ------------->            "<< endl;
71  cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
72  cout << "  / |          |    /  /->     \\     "<< endl;
73  cout << " /  |          |   /  |    ^    \\  "<< endl;
74  cout << "s   |          |  /   |    |     \\->  t "<< endl;
75  cout << " \\  |          | /    |    |     /->  "<< endl;
76  cout << "  \\ |       --/ /     |    |    /     "<< endl;
77  cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
78  cout << "    \\-->    ------------->         "<< endl;
79 
80//   typedef TrivGraphWrapper<const Graph> CGW;
81//   CGW wG(G);
82
83//   cout << "bfs and dfs demo on the directed graph" << endl;
84//   for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {
85//     cout << n << ": ";
86//     cout << "out edges: ";
87//     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
88//       cout << e << " ";
89//     cout << "in edges: ";
90//     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)
91//       cout << e << " ";
92//     cout << endl;
93//   }
94
95  {
96    typedef TrivGraphWrapper<const Graph> GW;
97    GW wG(G);
98
99    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
100   
101    cout << "bfs and dfs iterator demo on the directed graph" << endl;
102    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
103      cout << node_name.get(n) << ": ";
104      cout << "out edges: ";
105      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
106        cout << edge_name.get(e) << " ";
107      cout << "in edges: ";
108      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
109        cout << edge_name.get(e) << " ";
110      cout << endl;
111    }
112
113    cout << "bfs from s ..." << endl;
114    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
115    bfs.pushAndSetReached(s);
116    while (!bfs.finished()) {
117      //cout << "edge: ";
118      if (wG.valid(bfs)) {
119        cout << edge_name.get(bfs) << /*endl*/", " <<
120          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
121          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
122          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
123          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
124           ": is not newly reached.");
125      } else {
126        cout << "invalid" << /*endl*/", " <<
127          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
128          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
129          /*" bNode: " <<*/
130          "invalid.";
131      }
132      cout << endl;
133      ++bfs;
134    }
135
136    cout << "    /-->    ------------->            "<< endl;
137    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
138    cout << "  / |          |    /  /->     \\     "<< endl;
139    cout << " /  |          |   /  |    ^    \\  "<< endl;
140    cout << "s   |          |  /   |    |     \\->  t "<< endl;
141    cout << " \\  |          | /    |    |     /->  "<< endl;
142    cout << "  \\ |       --/ /     |    |    /     "<< endl;
143    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
144    cout << "    \\-->    ------------->         "<< endl;
145
146    cout << "dfs from s ..." << endl;
147    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
148    dfs.pushAndSetReached(s);
149    while (!dfs.finished()) {
150      ++dfs;
151      //cout << "edge: ";
152      if (wG.valid(dfs)) {
153        cout << edge_name.get(dfs) << /*endl*/", " <<
154          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
155          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
156          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
157          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
158           ": is not newly reached.");
159      } else {
160        cout << "invalid" << /*endl*/", " <<
161          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
162          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
163          /*" bNode: " <<*/
164          "invalid.";
165      }
166      cout << endl;
167    }
168  }
169
170
171  {
172    typedef RevGraphWrapper<const Graph> GW;
173    GW wG(G);
174   
175    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
176   
177    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
178    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
179      cout << node_name.get(n) << ": ";
180      cout << "out edges: ";
181      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
182        cout << edge_name.get(e) << " ";
183      cout << "in edges: ";
184      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
185        cout << edge_name.get(e) << " ";
186      cout << endl;
187    }
188
189    cout << "bfs from t ..." << endl;
190    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
191    bfs.pushAndSetReached(t);
192    while (!bfs.finished()) {
193      //cout << "edge: ";
194      if (wG.valid(bfs)) {
195        cout << edge_name.get(bfs) << /*endl*/", " <<
196          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
197          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
198          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
199          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
200           ": is not newly reached.");
201      } else {
202        cout << "invalid" << /*endl*/", " <<
203          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
204          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
205          /*" bNode: " <<*/
206          "invalid.";
207      }
208      cout << endl;
209      ++bfs;
210    }
211
212    cout << "    /-->    ------------->            "<< endl;
213    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
214    cout << "  / |          |    /  /->     \\     "<< endl;
215    cout << " /  |          |   /  |    ^    \\  "<< endl;
216    cout << "s   |          |  /   |    |     \\->  t "<< endl;
217    cout << " \\  |          | /    |    |     /->  "<< endl;
218    cout << "  \\ |       --/ /     |    |    /     "<< endl;
219    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
220    cout << "    \\-->    ------------->         "<< endl;
221   
222    cout << "dfs from t ..." << endl;
223    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
224    dfs.pushAndSetReached(t);
225    while (!dfs.finished()) {
226      ++dfs;
227      //cout << "edge: ";
228      if (wG.valid(dfs)) {
229        cout << edge_name.get(dfs) << /*endl*/", " <<
230          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
231          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
232          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
233          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
234           ": is not newly reached.");
235      } else {
236        cout << "invalid" << /*endl*/", " <<
237          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
238          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
239          /*" bNode: " <<*/
240          "invalid.";
241      }
242      cout << endl;
243    }
244  }
245
246  {
247    typedef UndirGraphWrapper<const Graph> GW;
248    GW wG(G);
249   
250    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
251   
252    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
253    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
254      cout << node_name.get(n) << ": ";
255      cout << "out edges: ";
256      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
257        cout << edge_name.get(e) << " ";
258      cout << "in edges: ";
259      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
260        cout << edge_name.get(e) << " ";
261      cout << endl;
262    }
263
264    cout << "bfs from t ..." << endl;
265    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
266    bfs.pushAndSetReached(t);
267    while (!bfs.finished()) {
268      //cout << "edge: ";
269      if (wG.valid(GW::OutEdgeIt(bfs))) {
270        cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
271          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
272          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
273          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
274          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
275           ": is not newly reached.");
276      } else {
277        cout << "invalid" << /*endl*/", " <<
278          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
279          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
280          /*" bNode: " <<*/
281          "invalid.";
282      }
283      cout << endl;
284      ++bfs;
285    }
286
287    cout << "    /-->    ------------->            "<< endl;
288    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
289    cout << "  / |          |    /  /->     \\     "<< endl;
290    cout << " /  |          |   /  |    ^    \\  "<< endl;
291    cout << "s   |          |  /   |    |     \\->  t "<< endl;
292    cout << " \\  |          | /    |    |     /->  "<< endl;
293    cout << "  \\ |       --/ /     |    |    /     "<< endl;
294    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
295    cout << "    \\-->    ------------->         "<< endl;
296   
297    cout << "dfs from t ..." << endl;
298    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
299    dfs.pushAndSetReached(t);
300    while (!dfs.finished()) {
301      ++dfs;
302      //cout << "edge: ";
303      if (wG.valid(GW::OutEdgeIt(dfs))) {
304        cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
305          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
306          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
307          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
308          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
309           ": is not newly reached.");
310      } else {
311        cout << "invalid" << /*endl*/", " <<
312          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
313          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
314          /*" bNode: " <<*/
315          "invalid.";
316      }
317      cout << endl;
318    }
319  }
320
321  return 0;
322}
Note: See TracBrowser for help on using the repository browser.