COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/bfs.h @ 784:a48964a87141

Last change on this file since 784:a48964a87141 was 781:d4d182ab75bd, checked in by Alpar Juttner, 20 years ago

Changes in the doc.

File size: 7.3 KB
Line 
1// -*- C++ -*-
2#ifndef HUGO_BFS_H
3#define HUGO_BFS_H
4
5///\ingroup flowalgs
6///\file
7///\brief Bfs algorithm.
8///
9///\todo Revise Manual.
10
11#include <hugo/bin_heap.h>
12#include <hugo/invalid.h>
13
14namespace hugo {
15
16/// \addtogroup flowalgs
17/// @{
18
19  ///%BFS algorithm class.
20
21  ///This class provides an efficient implementation of %BFS algorithm.
22  ///\param GR The graph type the algorithm runs on.
23  ///This class does the same as Dijkstra does with constant 1 edge length,
24  ///but it is faster.
25  ///
26  ///\author Alpar Juttner
27
28#ifdef DOXYGEN
29  template <typename GR>
30#else
31  template <typename GR>
32#endif
33  class Bfs{
34  public:
35    ///The type of the underlying graph.
36    typedef GR Graph;
37    typedef typename Graph::Node Node;
38    typedef typename Graph::NodeIt NodeIt;
39    typedef typename Graph::Edge Edge;
40    typedef typename Graph::OutEdgeIt OutEdgeIt;
41   
42    ///\brief The type of the map that stores the last
43    ///edges of the shortest paths.
44    typedef typename Graph::template NodeMap<Edge> PredMap;
45    ///\brief The type of the map that stores the last but one
46    ///nodes of the shortest paths.
47    typedef typename Graph::template NodeMap<Node> PredNodeMap;
48    ///The type of the map that stores the dists of the nodes.
49    typedef typename Graph::template NodeMap<int> DistMap;
50
51  private:
52    const Graph *G;
53    PredMap *predecessor;
54    bool local_predecessor;
55    PredNodeMap *pred_node;
56    bool local_pred_node;
57    DistMap *distance;
58    bool local_distance;
59
60    //The source node of the last execution.
61    Node source;
62
63
64    ///Initializes the maps.
65    void init_maps()
66    {
67      if(!predecessor) {
68        local_predecessor = true;
69        predecessor = new PredMap(*G);
70      }
71      if(!pred_node) {
72        local_pred_node = true;
73        pred_node = new PredNodeMap(*G);
74      }
75      if(!distance) {
76        local_distance = true;
77        distance = new DistMap(*G);
78      }
79    }
80   
81  public :   
82    Bfs(const Graph& _G) :
83      G(&_G),
84      predecessor(NULL), local_predecessor(false),
85      pred_node(NULL), local_pred_node(false),
86      distance(NULL), local_distance(false)
87    { }
88   
89    ~Bfs()
90    {
91      if(local_predecessor) delete predecessor;
92      if(local_pred_node) delete pred_node;
93      if(local_distance) delete distance;
94    }
95
96    ///Sets the graph the algorithm will run on.
97
98    ///Sets the graph the algorithm will run on.
99    ///\return <tt> (*this) </tt>
100    ///\bug What about maps?
101    ///\todo It may be unnecessary
102    Bfs &setGraph(const Graph &_G)
103    {
104      G = &_G;
105      return *this;
106    }
107    ///Sets the map storing the predecessor edges.
108
109    ///Sets the map storing the predecessor edges.
110    ///If you don't use this function before calling \ref run(),
111    ///it will allocate one. The destuctor deallocates this
112    ///automatically allocated map, of course.
113    ///\return <tt> (*this) </tt>
114    Bfs &setPredMap(PredMap &m)
115    {
116      if(local_predecessor) {
117        delete predecessor;
118        local_predecessor=false;
119      }
120      predecessor = &m;
121      return *this;
122    }
123
124    ///Sets the map storing the predecessor nodes.
125
126    ///Sets the map storing the predecessor nodes.
127    ///If you don't use this function before calling \ref run(),
128    ///it will allocate one. The destuctor deallocates this
129    ///automatically allocated map, of course.
130    ///\return <tt> (*this) </tt>
131    Bfs &setPredNodeMap(PredNodeMap &m)
132    {
133      if(local_pred_node) {
134        delete pred_node;
135        local_pred_node=false;
136      }
137      pred_node = &m;
138      return *this;
139    }
140
141    ///Sets the map storing the distances calculated by the algorithm.
142
143    ///Sets the map storing the distances calculated by the algorithm.
144    ///If you don't use this function before calling \ref run(),
145    ///it will allocate one. The destuctor deallocates this
146    ///automatically allocated map, of course.
147    ///\return <tt> (*this) </tt>
148    Bfs &setDistMap(DistMap &m)
149    {
150      if(local_distance) {
151        delete distance;
152        local_distance=false;
153      }
154      distance = &m;
155      return *this;
156    }
157   
158  ///Runs %BFS algorithm from node \c s.
159
160  ///This method runs the %BFS algorithm from a root node \c s
161  ///in order to
162  ///compute a
163  ///shortest path to each node. The algorithm computes
164  ///- The %BFS tree.
165  ///- The distance of each node from the root.
166 
167    void run(Node s) {
168     
169      init_maps();
170     
171      source = s;
172     
173      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
174        predecessor->set(u,INVALID);
175        pred_node->set(u,INVALID);
176      }
177     
178      int N=G->nodeNum();
179      std::vector<typename Graph::Node> Q(N);
180      int Qh=0;
181      int Qt=0;
182     
183      Q[Qh++]=source;
184      distance->set(s, 0);
185      do {
186        Node m;
187        Node n=Q[Qt++];
188        int d= (*distance)[n]+1;
189       
190        for(OutEdgeIt e(*G,n);e!=INVALID;++e)
191          if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
192            Q[Qh++]=m;
193            predecessor->set(m,e);
194            pred_node->set(m,n);
195            distance->set(m,d);
196          }
197      } while(Qt!=Qh);
198    }
199   
200    ///The distance of a node from the root.
201
202    ///Returns the distance of a node from the root.
203    ///\pre \ref run() must be called before using this function.
204    ///\warning If node \c v in unreachable from the root the return value
205    ///of this funcion is undefined.
206    int dist(Node v) const { return (*distance)[v]; }
207
208    ///Returns the 'previous edge' of the %BFS path tree.
209
210    ///For a node \c v it returns the 'previous edge' of the %BFS tree,
211    ///i.e. it returns the last edge of a shortest path from the root to \c
212    ///v. It is \ref INVALID
213    ///if \c v is unreachable from the root or if \c v=s. The
214    ///%BFS tree used here is equal to the %BFS tree used in
215    ///\ref predNode(Node v).  \pre \ref run() must be called before using
216    ///this function.
217    Edge pred(Node v) const { return (*predecessor)[v]; }
218
219    ///Returns the 'previous node' of the %BFS tree.
220
221    ///For a node \c v it returns the 'previous node' on the %BFS tree,
222    ///i.e. it returns the last but one node from a shortest path from the
223    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
224    ///\c v=s. The shortest path tree used here is equal to the %BFS
225    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
226    ///using this function.
227    Node predNode(Node v) const { return (*pred_node)[v]; }
228   
229    ///Returns a reference to the NodeMap of distances.
230   
231    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
232    ///be called before using this function.
233    const DistMap &distMap() const { return *distance;}
234 
235    ///Returns a reference to the %BFS tree map.
236
237    ///Returns a reference to the NodeMap of the edges of the
238    ///%BFS tree.
239    ///\pre \ref run() must be called before using this function.
240    const PredMap &predMap() const { return *predecessor;}
241 
242    ///Returns a reference to the map of last but one nodes of shortest paths.
243
244    ///Returns a reference to the NodeMap of the last but one nodes on the
245    ///%BFS tree.
246    ///\pre \ref run() must be called before using this function.
247    const PredNodeMap &predNodeMap() const { return *pred_node;}
248
249    ///Checks if a node is reachable from the root.
250
251    ///Returns \c true if \c v is reachable from the root.
252    ///\warning The root node is reported to be reached!
253    ///
254    ///\pre \ref run() must be called before using this function.
255    ///
256    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
257   
258  };
259 
260/// @}
261 
262} //END OF NAMESPACE HUGO
263
264#endif
265
266
Note: See TracBrowser for help on using the repository browser.