src/lemon/dfs.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 986 e997802b855c
child 1218 5331168bbb18
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
     1 /* -*- C++ -*-
     2  * src/lemon/dfs.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 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 
    29 namespace 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