COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/iterator_bfs_demo.cc @ 272:6179d85566e4

Last change on this file since 272:6179d85566e4 was 265:bf7aea53635a, checked in by marci, 17 years ago

GraphWrappers?

File size: 10.6 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>();
103        gw.valid(n);
104        gw.next(n)) {
105      cout << node_name.get(n) << ": ";
106      cout << "out edges: ";
107      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
108        cout << edge_name.get(e) << " ";
109      cout << "in edges: ";
110      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e))
111        cout << edge_name.get(e) << " ";
112      cout << endl;
113    }
114
115    cout << "bfs from s ..." << endl;
116    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
117    bfs.pushAndSetReached(s);
118    while (!bfs.finished()) {
119      //cout << "edge: ";
120      if (gw.valid(bfs)) {
121        cout << edge_name.get(bfs) << /*endl*/", " <<
122          node_name.get(gw.aNode(bfs)) <<
123          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
124          node_name.get(gw.bNode(bfs)) <<
125          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
126           ": is not newly reached.");
127      } else {
128        cout << "invalid" << /*endl*/", " <<
129          node_name.get(bfs.aNode()) <<
130          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
131         
132          "invalid.";
133      }
134      cout << endl;
135      ++bfs;
136    }
137
138    cout << "    /-->    ------------->            "<< endl;
139    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
140    cout << "  / |          |    /  /->     \\     "<< endl;
141    cout << " /  |          |   /  |    ^    \\  "<< endl;
142    cout << "s   |          |  /   |    |     \\->  t "<< endl;
143    cout << " \\  |          | /    |    |     /->  "<< endl;
144    cout << "  \\ |       --/ /     |    |    /     "<< endl;
145    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
146    cout << "    \\-->    ------------->         "<< endl;
147
148    cout << "dfs from s ..." << endl;
149    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
150    dfs.pushAndSetReached(s);
151    while (!dfs.finished()) {
152      ++dfs;
153      //cout << "edge: ";
154      if (gw.valid(dfs)) {
155        cout << edge_name.get(dfs) << /*endl*/", " <<
156          node_name.get(gw.aNode(dfs)) <<
157          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
158          node_name.get(gw.bNode(dfs)) <<
159          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
160           ": is not newly reached.");
161      } else {
162        cout << "invalid" << /*endl*/", " <<
163          node_name.get(dfs.aNode()) <<
164          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
165         
166          "invalid.";
167      }
168      cout << endl;
169    }
170  }
171
172
173  {
174    typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
175    GW gw(G);
176   
177    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
178   
179    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
180    for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) {
181      cout << node_name.get(n) << ": ";
182      cout << "out edges: ";
183      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
184        cout << edge_name.get(e) << " ";
185      cout << "in edges: ";
186      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e))
187        cout << edge_name.get(e) << " ";
188      cout << endl;
189    }
190
191    cout << "bfs from t ..." << endl;
192    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
193    bfs.pushAndSetReached(t);
194    while (!bfs.finished()) {
195      //cout << "edge: ";
196      if (gw.valid(bfs)) {
197        cout << edge_name.get(bfs) << /*endl*/", " <<
198          node_name.get(gw.aNode(bfs)) <<
199          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
200          node_name.get(gw.bNode(bfs)) <<
201          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
202           ": is not newly reached.");
203      } else {
204        cout << "invalid" << /*endl*/", " <<
205          node_name.get(bfs.aNode()) <<
206          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
207         
208          "invalid.";
209      }
210      cout << endl;
211      ++bfs;
212    }
213
214    cout << "    /-->    ------------->            "<< endl;
215    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
216    cout << "  / |          |    /  /->     \\     "<< endl;
217    cout << " /  |          |   /  |    ^    \\  "<< endl;
218    cout << "s   |          |  /   |    |     \\->  t "<< endl;
219    cout << " \\  |          | /    |    |     /->  "<< endl;
220    cout << "  \\ |       --/ /     |    |    /     "<< endl;
221    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
222    cout << "    \\-->    ------------->         "<< endl;
223   
224    cout << "dfs from t ..." << endl;
225    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
226    dfs.pushAndSetReached(t);
227    while (!dfs.finished()) {
228      ++dfs;
229      //cout << "edge: ";
230      if (gw.valid(dfs)) {
231        cout << edge_name.get(dfs) << /*endl*/", " <<
232          node_name.get(gw.aNode(dfs)) <<
233          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
234          node_name.get(gw.bNode(dfs)) <<
235          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
236           ": is not newly reached.");
237      } else {
238        cout << "invalid" << /*endl*/", " <<
239          node_name.get(dfs.aNode()) <<
240          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
241         
242          "invalid.";
243      }
244      cout << endl;
245    }
246  }
247
248  {
249    //typedef UndirGraphWrapper<const Graph> GW;
250    typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
251    GW gw(G);
252   
253    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
254   
255    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
256    for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) {
257      cout << node_name.get(n) << ": ";
258      cout << "out edges: ";
259      for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e))
260        cout << edge_name.get(e) << " ";
261      cout << "in edges: ";
262      for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e))
263        cout << edge_name.get(e) << " ";
264      cout << endl;
265    }
266//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
267//       cout << edge_name.get(e) << " ";
268//     }
269//     cout << endl;
270
271    cout << "bfs from t ..." << endl;
272    BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
273    bfs.pushAndSetReached(t);
274    while (!bfs.finished()) {
275      //cout << "edge: ";
276      if (gw.valid(GW::OutEdgeIt(bfs))) {
277        cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
278          node_name.get(gw.aNode(bfs)) <<
279          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
280          node_name.get(gw.bNode(bfs)) <<
281          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
282           ": is not newly reached.");
283      } else {
284        cout << "invalid" << /*endl*/", " <<
285          node_name.get(bfs.aNode()) <<
286          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
287         
288          "invalid.";
289      }
290      cout << endl;
291      ++bfs;
292    }
293
294    cout << "    /-->    ------------->            "<< endl;
295    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
296    cout << "  / |          |    /  /->     \\     "<< endl;
297    cout << " /  |          |   /  |    ^    \\  "<< endl;
298    cout << "s   |          |  /   |    |     \\->  t "<< endl;
299    cout << " \\  |          | /    |    |     /->  "<< endl;
300    cout << "  \\ |       --/ /     |    |    /     "<< endl;
301    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
302    cout << "    \\-->    ------------->         "<< endl;
303   
304    cout << "dfs from t ..." << endl;
305    DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
306    dfs.pushAndSetReached(t);
307    while (!dfs.finished()) {
308      ++dfs;
309      //cout << "edge: ";
310      if (gw.valid(GW::OutEdgeIt(dfs))) {
311        cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
312          node_name.get(gw.aNode(dfs)) <<
313          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
314          node_name.get(gw.bNode(dfs)) <<
315          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
316           ": is not newly reached.");
317      } else {
318        cout << "invalid" << /*endl*/", " <<
319          node_name.get(dfs.aNode()) <<
320          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
321         
322          "invalid.";
323      }
324      cout << endl;
325    }
326  }
327
328  return 0;
329}
Note: See TracBrowser for help on using the repository browser.