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/leda_bfs_dfs.cc @ 1305:c3dc75d4af24

Last change on this file since 1305:c3dc75d4af24 was 986:e997802b855c, checked in by Alpar Juttner, 20 years ago

Naming changes:

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