COIN-OR::LEMON - Graph Library

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