COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/dfs.h @ 781:d4d182ab75bd

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