COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/bfs-named-param.cc @ 1022:567f392d1d2e

Last change on this file since 1022:567f392d1d2e was 986:e997802b855c, checked in by Alpar Juttner, 20 years ago

Naming changes:

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