# source:lemon-0.x/src/hugo/bfs.h@802:bc0c74eeb151

Last change on this file since 802:bc0c74eeb151 was 802:bc0c74eeb151, checked in by Alpar Juttner, 20 years ago
• Changes in doc
• setGraph(...) finally removed from Dijkstra, Bfs and Dfs.
File size: 7.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
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    ///.
38    typedef typename Graph::Node Node;
39    ///.
40    typedef typename Graph::NodeIt NodeIt;
41    ///.
42    typedef typename Graph::Edge Edge;
43    ///.
44    typedef typename Graph::OutEdgeIt OutEdgeIt;
45
46    ///\brief The type of the map that stores the last
47    ///edges of the shortest paths.
48    typedef typename Graph::template NodeMap<Edge> PredMap;
49    ///\brief The type of the map that stores the last but one
50    ///nodes of the shortest paths.
51    typedef typename Graph::template NodeMap<Node> PredNodeMap;
52    ///The type of the map that stores the dists of the nodes.
53    typedef typename Graph::template NodeMap<int> DistMap;
54
55  private:
56    /// Pointer to the underlying graph.
57    const Graph *G;
58    ///Pointer to the map of predecessors edges.
59    PredMap *predecessor;
60    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
61    bool local_predecessor;
62    ///Pointer to the map of predecessors nodes.
63    PredNodeMap *pred_node;
64    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
65    bool local_pred_node;
66    ///Pointer to the map of distances.
67    DistMap *distance;
68    ///Indicates if \ref distance is locally allocated (\c true) or not.
69    bool local_distance;
70
71    ///The source node of the last execution.
72    Node source;
73
74
75    ///Initializes the maps.
76    void init_maps()
77    {
78      if(!predecessor) {
79        local_predecessor = true;
80        predecessor = new PredMap(*G);
81      }
82      if(!pred_node) {
83        local_pred_node = true;
84        pred_node = new PredNodeMap(*G);
85      }
86      if(!distance) {
87        local_distance = true;
88        distance = new DistMap(*G);
89      }
90    }
91
92  public :
93    ///Constructor.
94
95    ///\param _G the graph the algorithm will run on.
96    Bfs(const Graph& _G) :
97      G(&_G),
98      predecessor(NULL), local_predecessor(false),
99      pred_node(NULL), local_pred_node(false),
100      distance(NULL), local_distance(false)
101    { }
102
103    ///Destructor.
104    ~Bfs()
105    {
106      if(local_predecessor) delete predecessor;
107      if(local_pred_node) delete pred_node;
108      if(local_distance) delete distance;
109    }
110
111    ///Sets the map storing the predecessor edges.
112
113    ///Sets the map storing the predecessor edges.
114    ///If you don't use this function before calling \ref run(),
115    ///it will allocate one. The destuctor deallocates this
116    ///automatically allocated map, of course.
117    ///\return <tt> (*this) </tt>
118    Bfs &setPredMap(PredMap &m)
119    {
120      if(local_predecessor) {
121        delete predecessor;
122        local_predecessor=false;
123      }
124      predecessor = &m;
125      return *this;
126    }
127
128    ///Sets the map storing the predecessor nodes.
129
130    ///Sets the map storing the predecessor nodes.
131    ///If you don't use this function before calling \ref run(),
132    ///it will allocate one. The destuctor deallocates this
133    ///automatically allocated map, of course.
134    ///\return <tt> (*this) </tt>
135    Bfs &setPredNodeMap(PredNodeMap &m)
136    {
137      if(local_pred_node) {
138        delete pred_node;
139        local_pred_node=false;
140      }
141      pred_node = &m;
142      return *this;
143    }
144
145    ///Sets the map storing the distances calculated by the algorithm.
146
147    ///Sets the map storing the distances calculated by the algorithm.
148    ///If you don't use this function before calling \ref run(),
149    ///it will allocate one. The destuctor deallocates this
150    ///automatically allocated map, of course.
151    ///\return <tt> (*this) </tt>
152    Bfs &setDistMap(DistMap &m)
153    {
154      if(local_distance) {
155        delete distance;
156        local_distance=false;
157      }
158      distance = &m;
159      return *this;
160    }
161
162  ///Runs %BFS algorithm from node \c s.
163
164  ///This method runs the %BFS algorithm from a root node \c s
165  ///in order to
166  ///compute a
167  ///shortest path to each node. The algorithm computes
168  ///- The %BFS tree.
169  ///- The distance of each node from the root.
170
171    void run(Node s) {
172
173      init_maps();
174
175      source = s;
176
177      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
178        predecessor->set(u,INVALID);
179        pred_node->set(u,INVALID);
180      }
181
182      int N=G->nodeNum();
183      std::vector<typename Graph::Node> Q(N);
184      int Qh=0;
185      int Qt=0;
186
187      Q[Qh++]=source;
188      distance->set(s, 0);
189      do {
190        Node m;
191        Node n=Q[Qt++];
192        int d= (*distance)[n]+1;
193
194        for(OutEdgeIt e(*G,n);e!=INVALID;++e)
196            Q[Qh++]=m;
197            predecessor->set(m,e);
198            pred_node->set(m,n);
199            distance->set(m,d);
200          }
201      } while(Qt!=Qh);
202    }
203
204    ///The distance of a node from the root.
205
206    ///Returns the distance of a node from the root.
207    ///\pre \ref run() must be called before using this function.
208    ///\warning If node \c v in unreachable from the root the return value
209    ///of this funcion is undefined.
210    int dist(Node v) const { return (*distance)[v]; }
211
212    ///Returns the 'previous edge' of the %BFS path tree.
213
214    ///For a node \c v it returns the 'previous edge' of the %BFS tree,
215    ///i.e. it returns the last edge of a shortest path from the root to \c
216    ///v. It is \ref INVALID
217    ///if \c v is unreachable from the root or if \c v=s. The
218    ///%BFS tree used here is equal to the %BFS tree used in
219    ///\ref predNode(Node v).  \pre \ref run() must be called before using
220    ///this function.
221    Edge pred(Node v) const { return (*predecessor)[v]; }
222
223    ///Returns the 'previous node' of the %BFS tree.
224
225    ///For a node \c v it returns the 'previous node' on the %BFS tree,
226    ///i.e. it returns the last but one node from a shortest path from the
227    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
228    ///\c v=s. The shortest path tree used here is equal to the %BFS
229    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
230    ///using this function.
231    Node predNode(Node v) const { return (*pred_node)[v]; }
232
233    ///Returns a reference to the NodeMap of distances.
234
235    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
236    ///be called before using this function.
237    const DistMap &distMap() const { return *distance;}
238
239    ///Returns a reference to the %BFS tree map.
240
241    ///Returns a reference to the NodeMap of the edges of the
242    ///%BFS tree.
243    ///\pre \ref run() must be called before using this function.
244    const PredMap &predMap() const { return *predecessor;}
245
246    ///Returns a reference to the map of last but one nodes of shortest paths.
247
248    ///Returns a reference to the NodeMap of the last but one nodes on the
249    ///%BFS tree.
250    ///\pre \ref run() must be called before using this function.
251    const PredNodeMap &predNodeMap() const { return *pred_node;}
252
253    ///Checks if a node is reachable from the root.
254
255    ///Returns \c true if \c v is reachable from the root.
256    ///\note The root node is reported to be reached!
257    ///
258    ///\pre \ref run() must be called before using this function.
259    ///
260    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
261
262  };
263
264/// @}
265
266} //END OF NAMESPACE HUGO
267
268#endif
269
270
Note: See TracBrowser for help on using the repository browser.