COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/dfs.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 8.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/dfs.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_DFS_H
18#define LEMON_DFS_H
19
20///\ingroup flowalgs
21///\file
22///\brief %DFS algorithm.
23///
24///\todo Revise Manual.
25
26#include <lemon/graph_utils.h>
27#include <lemon/invalid.h>
28
29namespace lemon {
30
31/// \addtogroup flowalgs
32/// @{
33
34  ///%DFS algorithm class.
35
36  ///This class provides an efficient implementation of %DFS algorithm.
37  ///
38  ///\param GR The graph type the algorithm runs on.
39  ///
40  ///\author Alpar Juttner
41
42#ifdef DOXYGEN
43  template <typename GR>
44#else
45  template <typename GR>
46#endif
47  class Dfs{
48  public:
49    ///The type of the underlying graph.
50    typedef GR Graph;
51    ///\e
52    typedef typename Graph::Node Node;
53    ///\e
54    typedef typename Graph::NodeIt NodeIt;
55    ///\e
56    typedef typename Graph::Edge Edge;
57    ///\e
58    typedef typename Graph::OutEdgeIt OutEdgeIt;
59   
60    ///\brief The type of the map that stores the last
61    ///edges of the paths on the %DFS tree.
62    typedef typename Graph::template NodeMap<Edge> PredMap;
63    ///\brief The type of the map that stores the last but one
64    ///nodes of the paths on the %DFS tree.
65    typedef typename Graph::template NodeMap<Node> PredNodeMap;
66    ///The type of the map that stores the dists of the nodes on the %DFS tree.
67    typedef typename Graph::template NodeMap<int> DistMap;
68
69  private:
70    /// Pointer to the underlying graph.
71    const Graph *G;
72    ///Pointer to the map of predecessors edges.
73    PredMap *predecessor;
74    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
75    bool local_predecessor;
76    ///Pointer to the map of predecessors nodes.
77    PredNodeMap *pred_node;
78    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
79    bool local_pred_node;
80    ///Pointer to the map of distances.
81    DistMap *distance;
82    ///Indicates if \ref distance is locally allocated (\c true) or not.
83    bool local_distance;
84
85    ///The source node of the last execution.
86    Node source;
87
88
89    ///Initializes the maps.
90    void init_maps()
91    {
92      if(!predecessor) {
93        local_predecessor = true;
94        predecessor = new PredMap(*G);
95      }
96      if(!pred_node) {
97        local_pred_node = true;
98        pred_node = new PredNodeMap(*G);
99      }
100      if(!distance) {
101        local_distance = true;
102        distance = new DistMap(*G);
103      }
104    }
105   
106  public :   
107    ///Constructor.
108   
109    ///\param _G the graph the algorithm will run on.
110    ///
111    Dfs(const Graph& _G) :
112      G(&_G),
113      predecessor(NULL), local_predecessor(false),
114      pred_node(NULL), local_pred_node(false),
115      distance(NULL), local_distance(false)
116    { }
117   
118    ///Destructor.
119    ~Dfs()
120    {
121      if(local_predecessor) delete predecessor;
122      if(local_pred_node) delete pred_node;
123      if(local_distance) delete distance;
124    }
125
126    ///Sets the map storing the predecessor edges.
127
128    ///Sets the map storing the predecessor edges.
129    ///If you don't use this function before calling \ref run(),
130    ///it will allocate one. The destuctor deallocates this
131    ///automatically allocated map, of course.
132    ///\return <tt> (*this) </tt>
133    Dfs &setPredMap(PredMap &m)
134    {
135      if(local_predecessor) {
136        delete predecessor;
137        local_predecessor=false;
138      }
139      predecessor = &m;
140      return *this;
141    }
142
143    ///Sets the map storing the predecessor nodes.
144
145    ///Sets the map storing the predecessor nodes.
146    ///If you don't use this function before calling \ref run(),
147    ///it will allocate one. The destuctor deallocates this
148    ///automatically allocated map, of course.
149    ///\return <tt> (*this) </tt>
150    Dfs &setPredNodeMap(PredNodeMap &m)
151    {
152      if(local_pred_node) {
153        delete pred_node;
154        local_pred_node=false;
155      }
156      pred_node = &m;
157      return *this;
158    }
159
160    ///Sets the map storing the distances calculated by the algorithm.
161
162    ///Sets the map storing the distances calculated by the algorithm.
163    ///If you don't use this function before calling \ref run(),
164    ///it will allocate one. The destuctor deallocates this
165    ///automatically allocated map, of course.
166    ///\return <tt> (*this) </tt>
167    Dfs &setDistMap(DistMap &m)
168    {
169      if(local_distance) {
170        delete distance;
171        local_distance=false;
172      }
173      distance = &m;
174      return *this;
175    }
176   
177  ///Runs %DFS algorithm from node \c s.
178
179  ///This method runs the %DFS algorithm from a root node \c s
180  ///in order to
181  ///compute
182  ///- a %DFS tree and
183  ///- the distance of each node from the root on this tree.
184 
185    void run(Node s) {
186     
187      init_maps();
188     
189      source = s;
190     
191      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
192        predecessor->set(u,INVALID);
193        pred_node->set(u,INVALID);
194      }
195     
196      int N = countNodes(*G);
197      std::vector<typename Graph::OutEdgeIt> Q(N);
198
199      int Qh=0;
200     
201      Q[Qh] = OutEdgeIt(*G, s);
202      distance->set(s, 0);
203
204      Node n=s;
205      Node m;
206      OutEdgeIt e;
207      do {
208        if((e=Q[Qh])!=INVALID)
209          if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
210            predecessor->set(m,e);
211            pred_node->set(m,n);
212            Q[++Qh] = OutEdgeIt(*G, m);
213            distance->set(m,Qh);
214            n=m;
215          }
216          else ++Q[Qh];
217        else if(--Qh>=0) n=G->source(Q[Qh]);
218      } while(Qh>=0);
219    }
220   
221    ///The distance of a node from the root on the %DFS tree.
222
223    ///Returns the distance of a node from the root on the %DFS tree.
224    ///\pre \ref run() must be called before using this function.
225    ///\warning If node \c v in unreachable from the root the return value
226    ///of this funcion is undefined.
227    int dist(Node v) const { return (*distance)[v]; }
228
229    ///Returns the 'previous edge' of the %DFS path tree.
230
231    ///For a node \c v it returns the last edge of the path on the %DFS tree
232    ///from the root to \c
233    ///v. It is \ref INVALID
234    ///if \c v is unreachable from the root or if \c v=s. The
235    ///%DFS tree used here is equal to the %DFS tree used in
236    ///\ref predNode(Node v).  \pre \ref run() must be called before using
237    ///this function.
238    Edge pred(Node v) const { return (*predecessor)[v]; }
239
240    ///Returns the 'previous node' of the %DFS tree.
241
242    ///For a node \c v it returns the 'previous node' on the %DFS tree,
243    ///i.e. it returns the last but one node of the path from the
244    ///root to \c /v on the %DFS tree.
245    ///It is INVALID if \c v is unreachable from the root or if
246    ///\c v=s.
247    ///\pre \ref run() must be called before
248    ///using this function.
249    Node predNode(Node v) const { return (*pred_node)[v]; }
250   
251    ///Returns a reference to the NodeMap of distances on the %DFS tree.
252   
253    ///Returns a reference to the NodeMap of distances on the %DFS tree.
254    ///\pre \ref run() must
255    ///be called before using this function.
256    const DistMap &distMap() const { return *distance;}
257 
258    ///Returns a reference to the %DFS tree map.
259
260    ///Returns a reference to the NodeMap of the edges of the
261    ///%DFS tree.
262    ///\pre \ref run() must be called before using this function.
263    const PredMap &predMap() const { return *predecessor;}
264 
265    ///Returns a reference to the map of last but one nodes of the %DFS tree.
266
267    ///Returns a reference to the NodeMap of the last but one nodes of the paths
268    ///on the
269    ///%DFS tree.
270    ///\pre \ref run() must be called before using this function.
271    const PredNodeMap &predNodeMap() const { return *pred_node;}
272
273    ///Checks if a node is reachable from the root.
274
275    ///Returns \c true if \c v is reachable from the root.
276    ///\note The root node is reported to be reached!
277    ///
278    ///\pre \ref run() must be called before using this function.
279    ///
280    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
281   
282  };
283 
284/// @}
285 
286} //END OF NAMESPACE LEMON
287
288#endif
289
290
Note: See TracBrowser for help on using the repository browser.