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/experiment/iterator_bfs_demo_1.cc @ 281:3fefabfd00b7

Last change on this file since 281:3fefabfd00b7 was 281:3fefabfd00b7, checked in by marci, 21 years ago

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