# source:lemon-0.x/src/hugo/bfs.h@780:e06d0d16595f

Last change on this file since 780:e06d0d16595f was 780:e06d0d16595f, checked in by Alpar Juttner, 17 years ago
• DFS class (bfs.h and bfs_test.cc) added
• Bugfixes in Dijkstra and Bfs
File size: 8.6 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  ///The edge lengths are passed to the algorithm using a
23  ///\ref ReadMapSkeleton "readable map",
24  ///so it is easy to change it to any kind of length.
25  ///
26  ///The type of the length is determined by the \c ValueType of the length map.
27  ///
28  ///It is also possible to change the underlying priority heap.
29  ///
30  ///\param GR The graph type the algorithm runs on.
31  ///\param LM This read-only
32  ///EdgeMap
33  ///determines the
34  ///lengths of the edges. It is read once for each edge, so the map
35  ///may involve in relatively time consuming process to compute the edge
36  ///length if it is necessary. The default map type is
37  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
38  ///\param Heap The heap type used by the %Bfs
39  ///algorithm. The default
40  ///is using \ref BinHeap "binary heap".
41  ///
42  ///\author Jacint Szabo and Alpar Juttner
43  ///\todo We need a typedef-names should be standardized. (-:
44  ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
45  ///should not be fixed. (Problematic to solve).
46
47#ifdef DOXYGEN
48  template <typename GR>
49#else
50  template <typename GR>
51#endif
52  class Bfs{
53  public:
54    ///The type of the underlying graph.
55    typedef GR Graph;
56    typedef typename Graph::Node Node;
57    typedef typename Graph::NodeIt NodeIt;
58    typedef typename Graph::Edge Edge;
59    typedef typename Graph::OutEdgeIt OutEdgeIt;
60
61    ///\brief The type of the map that stores the last
62    ///edges of the shortest paths.
63    typedef typename Graph::template NodeMap<Edge> PredMap;
64    ///\brief The type of the map that stores the last but one
65    ///nodes of the shortest paths.
66    typedef typename Graph::template NodeMap<Node> PredNodeMap;
67    ///The type of the map that stores the dists of the nodes.
68    typedef typename Graph::template NodeMap<int> DistMap;
69
70  private:
71    const Graph *G;
72    PredMap *predecessor;
73    bool local_predecessor;
74    PredNodeMap *pred_node;
75    bool local_pred_node;
76    DistMap *distance;
77    bool local_distance;
78
79    //The source node of the last execution.
80    Node source;
81
82
83    ///Initialize maps.
84
85    ///\todo Error if \c G or are \c NULL.
86    ///\todo Better memory allocation (instead of new).
87    void init_maps()
88    {
89//       if(!length) {
90//      local_length = true;
91//      length = new LM(G);
92//       }
93      if(!predecessor) {
94        local_predecessor = true;
95        predecessor = new PredMap(*G);
96      }
97      if(!pred_node) {
98        local_pred_node = true;
99        pred_node = new PredNodeMap(*G);
100      }
101      if(!distance) {
102        local_distance = true;
103        distance = new DistMap(*G);
104      }
105    }
106
107  public :
108    Bfs(const Graph& _G) :
109      G(&_G),
110      predecessor(NULL), local_predecessor(false),
111      pred_node(NULL), local_pred_node(false),
112      distance(NULL), local_distance(false)
113    { }
114
115    ~Bfs()
116    {
117      //      if(local_length) delete length;
118      if(local_predecessor) delete predecessor;
119      if(local_pred_node) delete pred_node;
120      if(local_distance) delete distance;
121    }
122
123    ///Sets the graph the algorithm will run on.
124
125    ///Sets the graph the algorithm will run on.
126    ///\return <tt> (*this) </tt>
127    Bfs &setGraph(const Graph &_G)
128    {
129      G = &_G;
130      return *this;
131    }
132    ///Sets the length map.
133
134    ///Sets the map storing the predecessor edges.
135
136    ///Sets the map storing the predecessor edges.
137    ///If you don't use this function before calling \ref run(),
138    ///it will allocate one. The destuctor deallocates this
139    ///automatically allocated map, of course.
140    ///\return <tt> (*this) </tt>
141    Bfs &setPredMap(PredMap &m)
142    {
143      if(local_predecessor) {
144        delete predecessor;
145        local_predecessor=false;
146      }
147      predecessor = &m;
148      return *this;
149    }
150
151    ///Sets the map storing the predecessor nodes.
152
153    ///Sets the map storing the predecessor nodes.
154    ///If you don't use this function before calling \ref run(),
155    ///it will allocate one. The destuctor deallocates this
156    ///automatically allocated map, of course.
157    ///\return <tt> (*this) </tt>
158    Bfs &setPredNodeMap(PredNodeMap &m)
159    {
160      if(local_pred_node) {
161        delete pred_node;
162        local_pred_node=false;
163      }
164      pred_node = &m;
165      return *this;
166    }
167
168    ///Sets the map storing the distances calculated by the algorithm.
169
170    ///Sets the map storing the distances calculated by the algorithm.
171    ///If you don't use this function before calling \ref run(),
172    ///it will allocate one. The destuctor deallocates this
173    ///automatically allocated map, of course.
174    ///\return <tt> (*this) </tt>
175    Bfs &setDistMap(DistMap &m)
176    {
177      if(local_distance) {
178        delete distance;
179        local_distance=false;
180      }
181      distance = &m;
182      return *this;
183    }
184
185  ///Runs %BFS algorithm from node \c s.
186
187  ///This method runs the %BFS algorithm from a root node \c s
188  ///in order to
189  ///compute the
190  ///shortest path to each node. The algorithm computes
191  ///- The shortest path tree.
192  ///- The distance of each node from the root.
193
194    void run(Node s) {
195
196      init_maps();
197
198      source = s;
199
200      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
201        predecessor->set(u,INVALID);
202        pred_node->set(u,INVALID);
203      }
204
205      int N=G->nodeNum();
206      std::vector<typename Graph::Node> Q(N);
207      int Qh=0;
208      int Qt=0;
209
210      Q[Qh++]=source;
211      distance->set(s, 0);
212      do {
213        Node m;
214        Node n=Q[Qt++];
215        int d= (*distance)[n]+1;
216
217        for(OutEdgeIt e(*G,n);e!=INVALID;++e)
218          if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
219            Q[Qh++]=m;
220            predecessor->set(m,e);
221            pred_node->set(m,n);
222            distance->set(m,d);
223          }
224      } while(Qt!=Qh);
225    }
226
227    ///The distance of a node from the root.
228
229    ///Returns the distance of a node from the root.
230    ///\pre \ref run() must be called before using this function.
231    ///\warning If node \c v in unreachable from the root the return value
232    ///of this funcion is undefined.
233    int dist(Node v) const { return (*distance)[v]; }
234
235    ///Returns the 'previous edge' of the shortest path tree.
236
237    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
238    ///i.e. it returns the last edge from a shortest path from the root to \c
239    ///v. It is \ref INVALID
240    ///if \c v is unreachable from the root or if \c v=s. The
241    ///shortest path tree used here is equal to the shortest path tree used in
242    ///\ref predNode(Node v).  \pre \ref run() must be called before using
243    ///this function.
244    Edge pred(Node v) const { return (*predecessor)[v]; }
245
246    ///Returns the 'previous node' of the shortest path tree.
247
248    ///For a node \c v it returns the 'previous node' of the shortest path tree,
249    ///i.e. it returns the last but one node from a shortest path from the
250    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
251    ///\c v=s. The shortest path tree used here is equal to the shortest path
252    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
253    ///using this function.
254    Node predNode(Node v) const { return (*pred_node)[v]; }
255
256    ///Returns a reference to the NodeMap of distances.
257
258    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
259    ///be called before using this function.
260    const DistMap &distMap() const { return *distance;}
261
262    ///Returns a reference to the shortest path tree map.
263
264    ///Returns a reference to the NodeMap of the edges of the
265    ///shortest path tree.
266    ///\pre \ref run() must be called before using this function.
267    const PredMap &predMap() const { return *predecessor;}
268
269    ///Returns a reference to the map of nodes of shortest paths.
270
271    ///Returns a reference to the NodeMap of the last but one nodes of the
272    ///shortest path tree.
273    ///\pre \ref run() must be called before using this function.
274    const PredNodeMap &predNodeMap() const { return *pred_node;}
275
276    ///Checks if a node is reachable from the root.
277
278    ///Returns \c true if \c v is reachable from the root.
279    ///\warning The root node is reported to be reached!
280    ///
281    ///\pre \ref run() must be called before using this function.
282    ///
283    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
284
285  };
286
287
288  // **********************************************************************
289  //  IMPLEMENTATIONS
290  // **********************************************************************
291
292/// @}
293
294} //END OF NAMESPACE HUGO
295
296#endif
297
298
Note: See TracBrowser for help on using the repository browser.