COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/bfs-named-param.cc @ 944:4f064aff855e

Last change on this file since 944:4f064aff855e was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

File size: 4.9 KB
Line 
1// -*- mode:C++ -*-
2
3#include <lemon/smart_graph.h>
4#include <lemon/maps.h>
5#include <vector>
6#include <iostream>
7
8using namespace lemon;
9
10struct _BFS_DEFAULT_VIS {};
11struct _BFS_CUSTOM_VIS {};
12
13template<class GT,class VT,class DVT,class PNT,class PET,class PT >
14class _BFS
15{
16 public:
17  typedef GT Graph;
18  typedef VT Visited;
19  typedef PNT PredNode;
20  typedef PET PredEdge;
21  typedef PT Priority;
22  //  typedef QDT QueueData;
23 
24  typedef typename Graph::Node Node;
25  typedef typename Graph::OutEdgeIt OutEdgeIt;
26
27  typedef DVT DefaultVisitedTag;
28 
29  const Graph &_graph;
30
31  Node _source;
32 
33  Visited *_visited;
34  PredNode _predNode;
35  PredEdge _predEdge;
36  Priority _priority;
37
38  _BFS(const Graph &g,
39       Node s,
40       Visited *v,
41       PredNode &pn,
42       PredEdge &pe,
43       Priority &pr) :_graph(g), _source(s),
44                     _visited(v),
45                     _predNode(pn), _predEdge(pe), _priority(pr) { }
46
47 
48  int run(const _BFS_CUSTOM_VIS &)
49  {
50    using namespace std;
51   
52    int N=_graph.nodeNum();
53    vector<Node> Q(N);
54    int Qh=0;
55    int Qt=0;
56   
57    for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
58      _visited->set(n,false);
59
60    Q[Qh++]=_source;
61    _visited->set(_source,true);
62    do {
63      Node m;
64      Node n=Q[Qt++];
65      for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
66        if(!(*_visited)[m=_graph.head(e)]) {
67          Q[Qh++]=m;
68          _visited->set(m,true);
69          _predNode.set(m,n);
70          _predEdge.set(m,e);     
71        }
72    } while(Qt!=Qh);
73
74    return 1; //Why return 1?
75  }
76  int run(const _BFS_DEFAULT_VIS &)
77  {
78    _visited= new Visited(_graph);
79    int r = run(_BFS_CUSTOM_VIS());
80    delete _visited;
81    return r;
82  }
83  int run() { return run(DefaultVisitedTag());}
84
85  template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
86  setVisitMap(T &t)
87  {
88    return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
89      (_graph,_source,&t,_predNode,_predEdge,_priority);
90  }
91
92  template<class T>
93  _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
94  setPredNodeMap(T &t)
95  {
96    return _BFS<Graph,Visited,DefaultVisitedTag,T,PredEdge,Priority>
97      (_graph,_source,
98       _visited,
99       t,_predEdge,_priority);
100  }
101
102  template<class T>
103  _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
104  setPredEdgeMap(T &t)
105  {
106    return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,T,Priority>
107      (_graph,_source,
108       _visited,
109      _predNode,t,_priority);
110  }
111
112  _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
113  setNothing()
114  {
115    return _BFS<Graph,Visited,DefaultVisitedTag,PredNode,PredEdge,Priority>
116      (_graph,_source,
117       _visited,
118       _predNode,_predEdge,_priority);
119  }
120};
121
122
123template<class G>
124_BFS<G,
125     typename G::template NodeMap<bool>,
126     _BFS_DEFAULT_VIS,
127     NullMap<typename G::Node,typename G::Node>,
128     NullMap<typename G::Node,typename G::Edge>,
129     NullMap<typename G::Node,int> >
130bfs(const G &g,typename G::Node s)
131{
132  //  typename G::template NodeMap<bool> v(g);
133
134  return _BFS < G,
135    typename G::template NodeMap<bool>,
136    _BFS_DEFAULT_VIS,
137     NullMap<typename G::Node,typename G::Node>,
138     NullMap<typename G::Node,typename G::Edge>,
139    NullMap<typename G::Node,int> >
140    (g,s,
141     (typename G::template NodeMap<bool>*)(NULL),
142     *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
143     *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
144     *((NullMap<typename G::Node,int> *)(NULL))
145     );
146}
147
148
149class MyVisitedMap : public SmartGraph::NodeMap<bool>
150{
151  const SmartGraph &_G;
152public:
153  MyVisitedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {}
154  void set(SmartGraph::Node n,bool b)
155  {
156    SmartGraph::NodeMap<bool>::set(n,b);
157    if(b) std::cout << _G.id(n) << std::endl;
158  }
159};
160
161
162int main()
163{
164  SmartGraph G;
165  SmartGraph::Node s=G.addNode();
166  SmartGraph::Node n1=G.addNode();
167  SmartGraph::Node n2=G.addNode();
168  SmartGraph::Node n3=G.addNode();
169  SmartGraph::Node n4=G.addNode();
170  SmartGraph::Node n5=G.addNode();
171  SmartGraph::Node n6=G.addNode();
172  SmartGraph::Node n7=G.addNode();
173
174  G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3);
175  G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5);
176  G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s);
177
178 
179 
180  SmartGraph::NodeMap<SmartGraph::Node> m(G);
181  SmartGraph::NodeMap<SmartGraph::Edge> em(G);
182
183  MyVisitedMap vm(G);
184
185
186  //Runs BFS on graph 'G' from node 's'.
187  //(It practically does nothing, for it throws away its result.)
188  bfs(G,s).run();
189
190  //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'.
191  bfs(G,s).setPredNodeMap(m).run();
192
193  //Runs BFS on graph 'G' from node 's'.
194  //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'.
195  bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run();
196
197  //Runs BFS on graph 'G' from node 's'.
198  //It uses a scpecial 'visited map' that prints out the reached nodes.
199  bfs(G,s).setVisitMap(vm).run();
200
201}
Note: See TracBrowser for help on using the repository browser.