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

Last change on this file since 780:e06d0d16595f was 780:e06d0d16595f, checked in by Alpar Juttner, 18 years ago
• DFS class (bfs.h and bfs_test.cc) added
• Bugfixes in Dijkstra and Bfs
File size: 8.7 KB
Line
1// -*- C++ -*-
2#ifndef HUGO_DFS_H
3#define HUGO_DFS_H
4
5///\ingroup flowalgs
6///\file
7///\brief Dfs 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  ///%Dfs algorithm class.
20
21  ///This class provides an efficient implementation of %Dfs algorithm.
22  ///The edge lengths are passed to the algorithm using a
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.
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 %Dfs
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 Dfs{
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    Dfs(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    ~Dfs()
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    Dfs &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    Dfs &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    Dfs &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    Dfs &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 %DFS algorithm from node \c s.
186
187  ///This method runs the %DFS 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::OutEdgeIt> Q(N);
207
208      int Qh=0;
209
210      G->first(Q[Qh],s);
211      distance->set(s, 0);
212
213      Node n=s;
214      Node m;
215      OutEdgeIt e;
216      do {
217        if((e=Q[Qh])!=INVALID)
219            predecessor->set(m,e);
220            pred_node->set(m,n);
221            G->first(Q[++Qh],m);
222            distance->set(m,Qh);
223            n=m;
224          }
225          else ++Q[Qh];
226        else if(--Qh>=0) n=G->tail(Q[Qh]);
227      } while(Qh>=0);
228    }
229
230    ///The distance of a node from the root.
231
232    ///Returns the distance of a node from the root.
233    ///\pre \ref run() must be called before using this function.
234    ///\warning If node \c v in unreachable from the root the return value
235    ///of this funcion is undefined.
236    int dist(Node v) const { return (*distance)[v]; }
237
238    ///Returns the 'previous edge' of the shortest path tree.
239
240    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
241    ///i.e. it returns the last edge from a shortest path from the root to \c
242    ///v. It is \ref INVALID
243    ///if \c v is unreachable from the root or if \c v=s. The
244    ///shortest path tree used here is equal to the shortest path tree used in
245    ///\ref predNode(Node v).  \pre \ref run() must be called before using
246    ///this function.
247    Edge pred(Node v) const { return (*predecessor)[v]; }
248
249    ///Returns the 'previous node' of the shortest path tree.
250
251    ///For a node \c v it returns the 'previous node' of the shortest path tree,
252    ///i.e. it returns the last but one node from a shortest path from the
253    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
254    ///\c v=s. The shortest path tree used here is equal to the shortest path
255    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
256    ///using this function.
257    Node predNode(Node v) const { return (*pred_node)[v]; }
258
259    ///Returns a reference to the NodeMap of distances.
260
261    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
262    ///be called before using this function.
263    const DistMap &distMap() const { return *distance;}
264
265    ///Returns a reference to the shortest path tree map.
266
267    ///Returns a reference to the NodeMap of the edges of the
268    ///shortest path tree.
269    ///\pre \ref run() must be called before using this function.
270    const PredMap &predMap() const { return *predecessor;}
271
272    ///Returns a reference to the map of nodes of shortest paths.
273
274    ///Returns a reference to the NodeMap of the last but one nodes of the
275    ///shortest path tree.
276    ///\pre \ref run() must be called before using this function.
277    const PredNodeMap &predNodeMap() const { return *pred_node;}
278
279    ///Checks if a node is reachable from the root.
280
281    ///Returns \c true if \c v is reachable from the root.
282    ///\warning The root node is reported to be reached!
283    ///
284    ///\pre \ref run() must be called before using this function.
285    ///
286    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
287
288  };
289
290
291  // **********************************************************************
292  //  IMPLEMENTATIONS
293  // **********************************************************************
294
295/// @}
296
297} //END OF NAMESPACE HUGO
298
299#endif
300
301
Note: See TracBrowser for help on using the repository browser.