COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_demo.cc @ 249:0b0bdf24d00c

Last change on this file since 249:0b0bdf24d00c was 238:ad3bdd78f4f6, checked in by marci, 20 years ago

.

File size: 10.5 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 gw(G);
82
83//   cout << "bfs and dfs demo on the directed graph" << endl;
84//   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
85//     cout << n << ": ";
86//     cout << "out edges: ";
87//     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
88//       cout << e << " ";
89//     cout << "in edges: ";
90//     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
91//       cout << e << " ";
92//     cout << endl;
93//   }
94
95  {
96    typedef TrivGraphWrapper<const Graph> GW;
97    GW gw(G);
98
99    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
100   
101    cout << "bfs and dfs iterator demo on the directed graph" << endl;
102    for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) {
103      cout << node_name.get(n) << ": ";
104      cout << "out edges: ";
105      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
106        cout << edge_name.get(e) << " ";
107      cout << "in edges: ";
108      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.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(gw);
115    bfs.pushAndSetReached(s);
116    while (!bfs.finished()) {
117      //cout << "edge: ";
118      if (gw.valid(bfs)) {
119        cout << edge_name.get(bfs) << /*endl*/", " <<
120          node_name.get(gw.aNode(bfs)) <<
121          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
122          node_name.get(gw.bNode(bfs)) <<
123          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
124           ": is not newly reached.");
125      } else {
126        cout << "invalid" << /*endl*/", " <<
127          node_name.get(bfs.aNode()) <<
128          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
129         
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(gw);
148    dfs.pushAndSetReached(s);
149    while (!dfs.finished()) {
150      ++dfs;
151      //cout << "edge: ";
152      if (gw.valid(dfs)) {
153        cout << edge_name.get(dfs) << /*endl*/", " <<
154          node_name.get(gw.aNode(dfs)) <<
155          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
156          node_name.get(gw.bNode(dfs)) <<
157          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
158           ": is not newly reached.");
159      } else {
160        cout << "invalid" << /*endl*/", " <<
161          node_name.get(dfs.aNode()) <<
162          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
163         
164          "invalid.";
165      }
166      cout << endl;
167    }
168  }
169
170
171  {
172    typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
173    GW gw(G);
174   
175    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
176   
177    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
178    for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) {
179      cout << node_name.get(n) << ": ";
180      cout << "out edges: ";
181      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
182        cout << edge_name.get(e) << " ";
183      cout << "in edges: ";
184      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.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(gw);
191    bfs.pushAndSetReached(t);
192    while (!bfs.finished()) {
193      //cout << "edge: ";
194      if (gw.valid(bfs)) {
195        cout << edge_name.get(bfs) << /*endl*/", " <<
196          node_name.get(gw.aNode(bfs)) <<
197          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
198          node_name.get(gw.bNode(bfs)) <<
199          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
200           ": is not newly reached.");
201      } else {
202        cout << "invalid" << /*endl*/", " <<
203          node_name.get(bfs.aNode()) <<
204          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
205         
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(gw);
224    dfs.pushAndSetReached(t);
225    while (!dfs.finished()) {
226      ++dfs;
227      //cout << "edge: ";
228      if (gw.valid(dfs)) {
229        cout << edge_name.get(dfs) << /*endl*/", " <<
230          node_name.get(gw.aNode(dfs)) <<
231          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
232          node_name.get(gw.bNode(dfs)) <<
233          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
234           ": is not newly reached.");
235      } else {
236        cout << "invalid" << /*endl*/", " <<
237          node_name.get(dfs.aNode()) <<
238          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
239         
240          "invalid.";
241      }
242      cout << endl;
243    }
244  }
245
246  {
247    //typedef UndirGraphWrapper<const Graph> GW;
248    typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
249    GW gw(G);
250   
251    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
252   
253    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
254    for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) {
255      cout << node_name.get(n) << ": ";
256      cout << "out edges: ";
257      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
258        cout << edge_name.get(e) << " ";
259      cout << "in edges: ";
260      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e))
261        cout << edge_name.get(e) << " ";
262      cout << endl;
263    }
264//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
265//       cout << edge_name.get(e) << " ";
266//     }
267//     cout << endl;
268
269    cout << "bfs from t ..." << endl;
270    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
271    bfs.pushAndSetReached(t);
272    while (!bfs.finished()) {
273      //cout << "edge: ";
274      if (gw.valid(GW::OutEdgeIt(bfs))) {
275        cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
276          node_name.get(gw.aNode(bfs)) <<
277          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
278          node_name.get(gw.bNode(bfs)) <<
279          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
280           ": is not newly reached.");
281      } else {
282        cout << "invalid" << /*endl*/", " <<
283          node_name.get(bfs.aNode()) <<
284          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
285         
286          "invalid.";
287      }
288      cout << endl;
289      ++bfs;
290    }
291
292    cout << "    /-->    ------------->            "<< endl;
293    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
294    cout << "  / |          |    /  /->     \\     "<< endl;
295    cout << " /  |          |   /  |    ^    \\  "<< endl;
296    cout << "s   |          |  /   |    |     \\->  t "<< endl;
297    cout << " \\  |          | /    |    |     /->  "<< endl;
298    cout << "  \\ |       --/ /     |    |    /     "<< endl;
299    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
300    cout << "    \\-->    ------------->         "<< endl;
301   
302    cout << "dfs from t ..." << endl;
303    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
304    dfs.pushAndSetReached(t);
305    while (!dfs.finished()) {
306      ++dfs;
307      //cout << "edge: ";
308      if (gw.valid(GW::OutEdgeIt(dfs))) {
309        cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
310          node_name.get(gw.aNode(dfs)) <<
311          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
312          node_name.get(gw.bNode(dfs)) <<
313          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
314           ": is not newly reached.");
315      } else {
316        cout << "invalid" << /*endl*/", " <<
317          node_name.get(dfs.aNode()) <<
318          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
319         
320          "invalid.";
321      }
322      cout << endl;
323    }
324  }
325
326  return 0;
327}
Note: See TracBrowser for help on using the repository browser.