COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/bfs-named-param.cc @ 741:aa700e5c47b5

Last change on this file since 741:aa700e5c47b5 was 741:aa700e5c47b5, checked in by Alpar Juttner, 18 years ago

A very flexible bfs function using named parameters and impicit map types.

File size: 3.6 KB
Line 
1// -*- mode:C++ -*-
2
3#include <hugo/smart_graph.h>
4#include <hugo/maps.h>
5#include <vector>
6
7using namespace hugo;
8
9struct _BFS_DEFAULT_VIS {};
10struct _BFS_CUSTOM_VIS {};
11
12template<class GT,class VT,class DVT,class PNT,class PET,class PT >
13class _BFS
14{
15 public:
16  typedef GT Graph;
17  typedef VT Visited;
18  typedef PNT PredNode;
19  typedef PET PredEdge;
20  typedef PT Priority;
21  //  typedef QDT QueueData;
22 
23  typedef typename Graph::Node Node;
24  typedef typename Graph::OutEdgeIt OutEdgeIt;
25
26  typedef DVT DefaultVisitedTag;
27 
28  const Graph &_graph;
29
30  Node _source;
31 
32  Visited *_visited;
33  PredNode _predNode;
34  PredEdge _predEdge;
35  Priority _priority;
36
37  _BFS(const Graph &g,
38       Node s,
39       Visited *v,
40       PredNode &pn,
41       PredEdge &pe,
42       Priority &pr) :_graph(g), _source(s),
43                     _visited(v),
44                     _predNode(pn), _predEdge(pe), _priority(pr) { }
45
46 
47  int run(const _BFS_CUSTOM_VIS &)
48  {
49    using namespace std;
50   
51    int N=_graph.nodeNum();
52    vector<Node> Q(N);
53    int Qh=0;
54    int Qt=0;
55   
56    for(typename Graph::NodeIt n(_graph);_graph.valid(n);_graph.next(n))
57      _visited->set(n,false);
58
59    Q[Qh++]=_source;
60    _visited->set(_source,true);
61    do {
62      Node m;
63      Node n=Q[Qt++];
64      for(OutEdgeIt e(_graph,n);_graph.valid(e);_graph.next(e))
65        if(!(*_visited)[m=_graph.head(e)]) {
66          Q[Qh++]=m;
67          _visited->set(m,true);
68          _predNode.set(m,n);
69          _predEdge.set(m,e);     
70        }
71    } while(Qt!=Qh);
72
73    return 1; //Why return 1?
74  }
75  int run(const _BFS_DEFAULT_VIS &)
76  {
77    _visited= new Visited(_graph);
78    int r = run(_BFS_CUSTOM_VIS());
79    delete _visited;
80    return r;
81  }
82  int run() { return run(DefaultVisitedTag());}
83
84  template<class T> _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
85  setVisitMap(T &t)
86  {
87    return _BFS<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
88      (_graph,_source,&t,_predNode,_predEdge,_priority);
89  }
90
91  template<class T>
92  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
93  setPredNodeMap(T &t)
94  {
95    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,T,PredEdge,Priority>
96      (_graph,_source,
97       _visited,
98       t,_predEdge,_priority);
99  }
100
101  template<class T>
102  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
103  setPredEdgeMap(T &t)
104  {
105    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,T,Priority>
106      (_graph,_source,
107       _visited,
108      _predNode,t,_priority);
109  }
110
111  _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
112  setNothing()
113  {
114    return _BFS<Graph,Visited,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority>
115      (_graph,_source,
116       _visited,
117       _predNode,_predEdge,_priority);
118  }
119};
120
121
122template<class G>
123_BFS<G,
124     typename G::template NodeMap<bool>,
125     _BFS_DEFAULT_VIS,
126     NullMap<typename G::Node,typename G::Node>,
127     NullMap<typename G::Node,typename G::Edge>,
128     NullMap<typename G::Node,int> >
129bfs(const G &g,typename G::Node s)
130{
131  //  typename G::template NodeMap<bool> v(g);
132
133  return _BFS < G,
134    typename G::template NodeMap<bool>,
135    _BFS_DEFAULT_VIS,
136     NullMap<typename G::Node,typename G::Node>,
137     NullMap<typename G::Node,typename G::Edge>,
138    NullMap<typename G::Node,int> >
139    (g,s,
140     (typename G::template NodeMap<bool>*)(NULL),
141     *((NullMap<typename G::Node,typename G::Node>*)(NULL)),
142     *((NullMap<typename G::Node,typename G::Edge> *)(NULL)),
143     *((NullMap<typename G::Node,int> *)(NULL))
144     );
145}
146
147
148int main()
149{
150  SmartGraph G;
151  SmartGraph::NodeIt n(G);
152  SmartGraph::NodeMap<SmartGraph::Node> m(G);
153  SmartGraph::NodeMap<SmartGraph::Edge> em(G);
154 
155  bfs(G,n).run();
156  bfs(G,n).setPredNodeMap(m).run();
157  bfs(G,n).setPredNodeMap(m).setPredEdgeMap(em).run();
158
159}
Note: See TracBrowser for help on using the repository browser.