COIN-OR::LEMON - Graph Library

Changeset 1218:5331168bbb18 in lemon-0.x for src/lemon/dfs.h


Ignore:
Timestamp:
03/16/05 08:56:25 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1638
Message:
  • Several updates and clarifications on dijkstra.h
  • bfs.h and dfs.h is synchronized with dijkstra.h
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/dfs.h

    r1164 r1218  
    2020///\ingroup flowalgs
    2121///\file
    22 ///\brief %DFS algorithm.
    23 ///
    24 ///\todo Revise Manual.
    25 
     22///\brief Dfs algorithm.
     23
     24#include <lemon/list_graph.h>
    2625#include <lemon/graph_utils.h>
    2726#include <lemon/invalid.h>
     27#include <lemon/error.h>
     28#include <lemon/maps.h>
    2829
    2930namespace lemon {
    3031
    31 /// \addtogroup flowalgs
    32 /// @{
    33 
     32
     33 
     34  ///Default traits class of Dfs class.
     35
     36  ///Default traits class of Dfs class.
     37  ///\param GR Graph type.
     38  template<class GR>
     39  struct DfsDefaultTraits
     40  {
     41    ///The graph type the algorithm runs on.
     42    typedef GR Graph;
     43    ///\brief The type of the map that stores the last
     44    ///edges of the %DFS paths.
     45    ///
     46    ///The type of the map that stores the last
     47    ///edges of the %DFS paths.
     48    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     49    ///
     50    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
     51    ///Instantiates a PredMap.
     52 
     53    ///This function instantiates a \ref PredMap.
     54    ///\param G is the graph, to which we would like to define the PredMap.
     55    ///\todo The graph alone may be insufficient to initialize
     56    static PredMap *createPredMap(const GR &G)
     57    {
     58      return new PredMap(G);
     59    }
     60//     ///\brief The type of the map that stores the last but one
     61//     ///nodes of the %DFS paths.
     62//     ///
     63//     ///The type of the map that stores the last but one
     64//     ///nodes of the %DFS paths.
     65//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     66//     ///
     67//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     68//     ///Instantiates a PredNodeMap.
     69   
     70//     ///This function instantiates a \ref PredNodeMap.
     71//     ///\param G is the graph, to which
     72//     ///we would like to define the \ref PredNodeMap
     73//     static PredNodeMap *createPredNodeMap(const GR &G)
     74//     {
     75//       return new PredNodeMap();
     76//     }
     77
     78    ///The type of the map that indicates which nodes are processed.
     79 
     80    ///The type of the map that indicates which nodes are processed.
     81    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     82    ///\todo named parameter to set this type, function to read and write.
     83    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     84    ///Instantiates a ProcessedMap.
     85 
     86    ///This function instantiates a \ref ProcessedMap.
     87    ///\param G is the graph, to which
     88    ///we would like to define the \ref ProcessedMap
     89    static ProcessedMap *createProcessedMap(const GR &G)
     90    {
     91      return new ProcessedMap();
     92    }
     93    ///The type of the map that indicates which nodes are reached.
     94 
     95    ///The type of the map that indicates which nodes are reached.
     96    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     97    ///\todo named parameter to set this type, function to read and write.
     98    typedef typename Graph::template NodeMap<bool> ReachedMap;
     99    ///Instantiates a ReachedMap.
     100 
     101    ///This function instantiates a \ref ReachedMap.
     102    ///\param G is the graph, to which
     103    ///we would like to define the \ref ReachedMap.
     104    static ReachedMap *createReachedMap(const GR &G)
     105    {
     106      return new ReachedMap(G);
     107    }
     108    ///The type of the map that stores the dists of the nodes.
     109 
     110    ///The type of the map that stores the dists of the nodes.
     111    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     112    ///
     113    typedef typename Graph::template NodeMap<int> DistMap;
     114    ///Instantiates a DistMap.
     115 
     116    ///This function instantiates a \ref DistMap.
     117    ///\param G is the graph, to which we would like to define the \ref DistMap
     118    static DistMap *createDistMap(const GR &G)
     119    {
     120      return new DistMap(G);
     121    }
     122  };
     123 
    34124  ///%DFS algorithm class.
    35 
    36   ///This class provides an efficient implementation of %DFS algorithm.
     125 
     126  ///\ingroup flowalgs
     127  ///This class provides an efficient implementation of the %DFS algorithm.
    37128  ///
    38   ///\param GR The graph type the algorithm runs on.
     129  ///\param GR The graph type the algorithm runs on. The default value is
     130  ///\ref ListGraph. The value of GR is not used directly by Dfs, it
     131  ///is only passed to \ref DfsDefaultTraits.
     132  ///\param TR Traits class to set various data types used by the algorithm.
     133  ///The default traits class is
     134  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
     135  ///See \ref DfsDefaultTraits for the documentation of
     136  ///a Dfs traits class.
    39137  ///
    40   ///\author Alpar Juttner
     138  ///\author Jacint Szabo and Alpar Juttner
     139  ///\todo A compare object would be nice.
    41140
    42141#ifdef DOXYGEN
    43   template <typename GR>
     142  template <typename GR,
     143            typename TR>
    44144#else
    45   template <typename GR>
     145  template <typename GR=ListGraph,
     146            typename TR=DfsDefaultTraits<GR> >
    46147#endif
    47   class Dfs{
     148  class Dfs {
    48149  public:
     150    /**
     151     * \brief \ref Exception for uninitialized parameters.
     152     *
     153     * This error represents problems in the initialization
     154     * of the parameters of the algorithms.
     155     */
     156    class UninitializedParameter : public lemon::UninitializedParameter {
     157    public:
     158      virtual const char* exceptionName() const {
     159        return "lemon::Dfs::UninitializedParameter";
     160      }
     161    };
     162
     163    typedef TR Traits;
    49164    ///The type of the underlying graph.
    50     typedef GR Graph;
     165    typedef typename TR::Graph Graph;
    51166    ///\e
    52167    typedef typename Graph::Node Node;
     
    59174   
    60175    ///\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 
     176    ///edges of the %DFS paths.
     177    typedef typename TR::PredMap PredMap;
     178//     ///\brief The type of the map that stores the last but one
     179//     ///nodes of the %DFS paths.
     180//     typedef typename TR::PredNodeMap PredNodeMap;
     181    ///The type of the map indicating which nodes are reached.
     182    typedef typename TR::ReachedMap ReachedMap;
     183    ///The type of the map indicating which nodes are processed.
     184    typedef typename TR::ProcessedMap ProcessedMap;
     185    ///The type of the map that stores the dists of the nodes.
     186    typedef typename TR::DistMap DistMap;
    69187  private:
    70188    /// Pointer to the underlying graph.
    71189    const Graph *G;
    72190    ///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;
     191    PredMap *_pred;
     192    ///Indicates if \ref _pred is locally allocated (\c true) or not.
     193    bool local_pred;
     194//     ///Pointer to the map of predecessors nodes.
     195//     PredNodeMap *_predNode;
     196//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
     197//     bool local_predNode;
    80198    ///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 :   
     199    DistMap *_dist;
     200    ///Indicates if \ref _dist is locally allocated (\c true) or not.
     201    bool local_dist;
     202    ///Pointer to the map of reached status of the nodes.
     203    ReachedMap *_reached;
     204    ///Indicates if \ref _reached is locally allocated (\c true) or not.
     205    bool local_reached;
     206    ///Pointer to the map of processed status of the nodes.
     207    ProcessedMap *_processed;
     208    ///Indicates if \ref _processed is locally allocated (\c true) or not.
     209    bool local_processed;
     210
     211    std::vector<typename Graph::OutEdgeIt> _stack;
     212    int _stack_head;
     213//     ///The source node of the last execution.
     214//     Node source;
     215
     216    ///Creates the maps if necessary.
     217   
     218    ///\todo Error if \c G are \c NULL.
     219    ///\todo Better memory allocation (instead of new).
     220    void create_maps()
     221    {
     222      if(!_pred) {
     223        local_pred = true;
     224        _pred = Traits::createPredMap(*G);
     225      }
     226//       if(!_predNode) {
     227//      local_predNode = true;
     228//      _predNode = Traits::createPredNodeMap(*G);
     229//       }
     230      if(!_dist) {
     231        local_dist = true;
     232        _dist = Traits::createDistMap(*G);
     233      }
     234      if(!_reached) {
     235        local_reached = true;
     236        _reached = Traits::createReachedMap(*G);
     237      }
     238      if(!_processed) {
     239        local_processed = true;
     240        _processed = Traits::createProcessedMap(*G);
     241      }
     242    }
     243   
     244  public :
     245 
     246    ///\name Named template parameters
     247
     248    ///@{
     249
     250    template <class T>
     251    struct DefPredMapTraits : public Traits {
     252      typedef T PredMap;
     253      static PredMap *createPredMap(const Graph &G)
     254      {
     255        throw UninitializedParameter();
     256      }
     257    };
     258    ///\ref named-templ-param "Named parameter" for setting PredMap type
     259
     260    ///\ref named-templ-param "Named parameter" for setting PredMap type
     261    ///
     262    template <class T>
     263    class DefPredMap : public Dfs< Graph,
     264                                        DefPredMapTraits<T> > { };
     265   
     266//     template <class T>
     267//     struct DefPredNodeMapTraits : public Traits {
     268//       typedef T PredNodeMap;
     269//       static PredNodeMap *createPredNodeMap(const Graph &G)
     270//       {
     271//      throw UninitializedParameter();
     272//       }
     273//     };
     274//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     275
     276//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     277//     ///
     278//     template <class T>
     279//     class DefPredNodeMap : public Dfs< Graph,
     280//                                          LengthMap,
     281//                                          DefPredNodeMapTraits<T> > { };
     282   
     283    template <class T>
     284    struct DefDistMapTraits : public Traits {
     285      typedef T DistMap;
     286      static DistMap *createDistMap(const Graph &G)
     287      {
     288        throw UninitializedParameter();
     289      }
     290    };
     291    ///\ref named-templ-param "Named parameter" for setting DistMap type
     292
     293    ///\ref named-templ-param "Named parameter" for setting DistMap type
     294    ///
     295    template <class T>
     296    class DefDistMap : public Dfs< Graph,
     297                                   DefDistMapTraits<T> > { };
     298   
     299    template <class T>
     300    struct DefReachedMapTraits : public Traits {
     301      typedef T ReachedMap;
     302      static ReachedMap *createReachedMap(const Graph &G)
     303      {
     304        throw UninitializedParameter();
     305      }
     306    };
     307    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     308
     309    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     310    ///
     311    template <class T>
     312    class DefReachedMap : public Dfs< Graph,
     313                                      DefReachedMapTraits<T> > { };
     314   
     315    struct DefGraphReachedMapTraits : public Traits {
     316      typedef typename Graph::template NodeMap<bool> ReachedMap;
     317      static ReachedMap *createReachedMap(const Graph &G)
     318      {
     319        return new ReachedMap(G);
     320      }
     321    };
     322    template <class T>
     323    struct DefProcessedMapTraits : public Traits {
     324      typedef T ProcessedMap;
     325      static ProcessedMap *createProcessedMap(const Graph &G)
     326      {
     327        throw UninitializedParameter();
     328      }
     329    };
     330    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     331
     332    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     333    ///
     334    template <class T>
     335    class DefProcessedMap : public Dfs< Graph,
     336                                        DefProcessedMapTraits<T> > { };
     337   
     338    struct DefGraphProcessedMapTraits : public Traits {
     339      typedef typename Graph::template NodeMap<bool> ProcessedMap;
     340      static ProcessedMap *createProcessedMap(const Graph &G)
     341      {
     342        return new ProcessedMap(G);
     343      }
     344    };
     345    ///\brief \ref named-templ-param "Named parameter"
     346    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     347    ///
     348    ///\ref named-templ-param "Named parameter"
     349    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     350    ///If you don't set it explicitely, it will be automatically allocated.
     351    template <class T>
     352    class DefProcessedMapToBeDefaultMap :
     353      public Dfs< Graph,
     354                  DefGraphProcessedMapTraits> { };
     355   
     356    ///@}
     357
     358  public:     
     359   
    107360    ///Constructor.
    108361   
     
    111364    Dfs(const Graph& _G) :
    112365      G(&_G),
    113       predecessor(NULL), local_predecessor(false),
    114       pred_node(NULL), local_pred_node(false),
    115       distance(NULL), local_distance(false)
     366      _pred(NULL), local_pred(false),
     367//       _predNode(NULL), local_predNode(false),
     368      _dist(NULL), local_dist(false),
     369      _reached(NULL), local_reached(false),
     370      _processed(NULL), local_processed(false)
    116371    { }
    117372   
     
    119374    ~Dfs()
    120375    {
    121       if(local_predecessor) delete predecessor;
    122       if(local_pred_node) delete pred_node;
    123       if(local_distance) delete distance;
     376      if(local_pred) delete _pred;
     377//       if(local_predNode) delete _predNode;
     378      if(local_dist) delete _dist;
     379      if(local_reached) delete _reached;
     380      if(local_processed) delete _processed;
    124381    }
    125382
     
    131388    ///automatically allocated map, of course.
    132389    ///\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;
     390    Dfs &predMap(PredMap &m)
     391    {
     392      if(local_pred) {
     393        delete _pred;
     394        local_pred=false;
     395      }
     396      _pred = &m;
    140397      return *this;
    141398    }
    142399
    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     }
     400//     ///Sets the map storing the predecessor nodes.
     401
     402//     ///Sets the map storing the predecessor nodes.
     403//     ///If you don't use this function before calling \ref run(),
     404//     ///it will allocate one. The destuctor deallocates this
     405//     ///automatically allocated map, of course.
     406//     ///\return <tt> (*this) </tt>
     407//     Dfs &predNodeMap(PredNodeMap &m)
     408//     {
     409//       if(local_predNode) {
     410//      delete _predNode;
     411//      local_predNode=false;
     412//       }
     413//       _predNode = &m;
     414//       return *this;
     415//     }
    159416
    160417    ///Sets the map storing the distances calculated by the algorithm.
     
    165422    ///automatically allocated map, of course.
    166423    ///\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;
     424    Dfs &distMap(DistMap &m)
     425    {
     426      if(local_dist) {
     427        delete _dist;
     428        local_dist=false;
     429      }
     430      _dist = &m;
    174431      return *this;
    175432    }
    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  
     433
     434  public:
     435    ///\name Execution control
     436    ///The simplest way to execute the algorithm is to use
     437    ///one of the member functions called \c run(...).
     438    ///\n
     439    ///If you need more control on the execution,
     440    ///first you must call \ref init(), then you can add several source nodes
     441    ///with \ref addSource().
     442    ///Finally \ref start() will perform the actual path
     443    ///computation.
     444
     445    ///@{
     446
     447    ///Initializes the internal data structures.
     448
     449    ///Initializes the internal data structures.
     450    ///
     451    void init()
     452    {
     453      create_maps();
     454      _stack.resize(countNodes(*G));
     455      _stack_head=-1;
     456      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
     457        _pred->set(u,INVALID);
     458        // _predNode->set(u,INVALID);
     459        _reached->set(u,false);
     460        _processed->set(u,false);
     461      }
     462    }
     463   
     464    ///Adds a new source node.
     465
     466    ///Adds a new source node to the set of nodes to be processed.
     467    ///
     468    ///\bug dist's are wrong (or at least strange) in case of multiple sources.
     469    void addSource(Node s)
     470    {
     471      if(!(*_reached)[s])
     472        {
     473          _reached->set(s,true);
     474          _pred->set(s,INVALID);
     475          // _predNode->set(u,INVALID);
     476          _stack[++_stack_head]=OutEdgeIt(*G,s);
     477          _dist->set(s,_stack_head);
     478        }
     479    }
     480   
     481    ///Processes the next node.
     482
     483    ///Processes the next node.
     484    ///
     485    ///\warning The stack must not be empty!
     486    void processNextEdge()
     487    {
     488      Node m;
     489      Edge e=_stack[_stack_head];
     490      if(!(*_reached)[m=G->target(e)]) {
     491        _pred->set(m,e);
     492        _reached->set(m,true);
     493        //        _pred_node->set(m,G->source(e));
     494        _stack[++_stack_head] = OutEdgeIt(*G, m);
     495        _dist->set(m,_stack_head);
     496      }
     497      else {
     498        Node n;
     499        while(_stack_head>=0 &&
     500              (n=G->source(_stack[_stack_head]),
     501               ++_stack[_stack_head]==INVALID))
     502          {
     503            _processed->set(n,true);
     504            --_stack_head;
     505          }
     506      }
     507    }
     508     
     509    ///\brief Returns \c false if there are nodes
     510    ///to be processed in the queue
     511    ///
     512    ///Returns \c false if there are nodes
     513    ///to be processed in the queue
     514    bool emptyQueue() { return _stack_head<0; }
     515    ///Returns the number of the nodes to be processed.
     516   
     517    ///Returns the number of the nodes to be processed in the queue.
     518    ///
     519    int queueSize() { return _stack_head+1; }
     520   
     521    ///Executes the algorithm.
     522
     523    ///Executes the algorithm.
     524    ///
     525    ///\pre init() must be called and at least one node should be added
     526    ///with addSource() before using this function.
     527    ///
     528    ///This method runs the %DFS algorithm from the root node(s)
     529    ///in order to
     530    ///compute the
     531    ///%DFS path to each node. The algorithm computes
     532    ///- The %DFS tree.
     533    ///- The distance of each node from the root(s).
     534    ///
     535    void start()
     536    {
     537      while ( !emptyQueue() ) processNextEdge();
     538    }
     539   
     540    ///Executes the algorithm until \c dest is reached.
     541
     542    ///Executes the algorithm until \c dest is reached.
     543    ///
     544    ///\pre init() must be called and at least one node should be added
     545    ///with addSource() before using this function.
     546    ///
     547    ///This method runs the %DFS algorithm from the root node(s)
     548    ///in order to
     549    ///compute the
     550    ///%DFS path to \c dest. The algorithm computes
     551    ///- The %DFS path to \c  dest.
     552    ///- The distance of \c dest from the root(s).
     553    ///
     554    void start(Node dest)
     555    {
     556      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
     557    }
     558   
     559    ///Executes the algorithm until a condition is met.
     560
     561    ///Executes the algorithm until a condition is met.
     562    ///
     563    ///\pre init() must be called and at least one node should be added
     564    ///with addSource() before using this function.
     565    ///
     566    ///\param nm must be a bool (or convertible) node map. The algorithm
     567    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     568    template<class NM>
     569      void start(const NM &nm)
     570      {
     571        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
     572      }
     573   
     574    ///Runs %DFS algorithm from node \c s.
     575   
     576    ///This method runs the %DFS algorithm from a root node \c s
     577    ///in order to
     578    ///compute the
     579    ///%DFS path to each node. The algorithm computes
     580    ///- The %DFS tree.
     581    ///- The distance of each node from the root.
     582    ///
     583    ///\note d.run(s) is just a shortcut of the following code.
     584    ///\code
     585    ///  d.init();
     586    ///  d.addSource(s);
     587    ///  d.start();
     588    ///\endcode
    185589    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.
     590      init();
     591      addSource(s);
     592      start();
     593    }
     594   
     595    ///Finds the %DFS path between \c s and \c t.
     596   
     597    ///Finds the %DFS path between \c s and \c t.
     598    ///
     599    ///\return The length of the %DFS s---t path if there exists one,
     600    ///0 otherwise.
     601    ///\note Apart from the return value, d.run(s) is
     602    ///just a shortcut of the following code.
     603    ///\code
     604    ///  d.init();
     605    ///  d.addSource(s);
     606    ///  d.start(t);
     607    ///\endcode
     608    int run(Node s,Node t) {
     609      init();
     610      addSource(s);
     611      start(t);
     612      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
     613    }
     614   
     615    ///@}
     616
     617    ///\name Query Functions
     618    ///The result of the %DFS algorithm can be obtained using these
     619    ///functions.\n
     620    ///Before the use of these functions,
     621    ///either run() or start() must be called.
     622   
     623    ///@{
     624
     625    ///The distance of a node from the root(s).
     626
     627    ///Returns the distance of a node from the root(s).
    224628    ///\pre \ref run() must be called before using this function.
    225     ///\warning If node \c v in unreachable from the root the return value
     629    ///\warning If node \c v in unreachable from the root(s) the return value
    226630    ///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
     631    int dist(Node v) const { return (*_dist)[v]; }
     632
     633    ///Returns the 'previous edge' of the %DFS tree.
     634
     635    ///For a node \c v it returns the 'previous edge'
     636    ///of the %DFS path,
     637    ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
    233638    ///v. It is \ref INVALID
    234     ///if \c v is unreachable from the root or if \c v=s. The
     639    ///if \c v is unreachable from the root(s) or \c v is a root. The
    235640    ///%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
     641    ///\ref predNode(Node v).
     642    ///\pre Either \ref run() or \ref start() must be called before using
    237643    ///this function.
    238     Edge pred(Node v) const { return (*predecessor)[v]; }
     644    ///\todo predEdge could be a better name.
     645    Edge pred(Node v) const { return (*_pred)[v];}
    239646
    240647    ///Returns the 'previous node' of the %DFS tree.
    241648
    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
     649    ///For a node \c v it returns the 'previous node'
     650    ///of the %DFS tree,
     651    ///i.e. it returns the last but one node from a %DFS path from the
     652    ///root(a) to \c /v.
     653    ///It is INVALID if \c v is unreachable from the root(s) or
     654    ///if \c v itself a root.
     655    ///The %DFS tree used here is equal to the %DFS
     656    ///tree used in \ref pred(Node v).
     657    ///\pre Either \ref run() or \ref start() must be called before
    248658    ///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
     659    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
     660                                  G->source((*_pred)[v]); }
     661   
     662    ///Returns a reference to the NodeMap of distances.
     663
     664    ///Returns a reference to the NodeMap of distances.
     665    ///\pre Either \ref run() or \ref init() must
    255666    ///be called before using this function.
    256     const DistMap &distMap() const { return *distance;}
    257  
    258     ///Returns a reference to the %DFS tree map.
     667    const DistMap &distMap() const { return *_dist;}
     668 
     669    ///Returns a reference to the %DFS edge-tree map.
    259670
    260671    ///Returns a reference to the NodeMap of the edges of the
    261672    ///%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;}
     673    ///\pre Either \ref run() or \ref init()
     674    ///must be called before using this function.
     675    const PredMap &predMap() const { return *_pred;}
     676 
     677//     ///Returns a reference to the map of nodes of %DFS paths.
     678
     679//     ///Returns a reference to the NodeMap of the last but one nodes of the
     680//     ///%DFS tree.
     681//     ///\pre \ref run() must be called before using this function.
     682//     const PredNodeMap &predNodeMap() const { return *_predNode;}
    272683
    273684    ///Checks if a node is reachable from the root.
    274685
    275686    ///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    
     687    ///\warning The source nodes are inditated as unreached.
     688    ///\pre Either \ref run() or \ref start()
     689    ///must be called before using this function.
     690    ///
     691    bool reached(Node v) { return (*_reached)[v]; }
     692   
     693    ///@}
     694  };
     695
     696  ///Default traits class of Dfs function.
     697
     698  ///Default traits class of Dfs function.
     699  ///\param GR Graph type.
     700  template<class GR>
     701  struct DfsWizardDefaultTraits
     702  {
     703    ///The graph type the algorithm runs on.
     704    typedef GR Graph;
     705    ///\brief The type of the map that stores the last
     706    ///edges of the %DFS paths.
     707    ///
     708    ///The type of the map that stores the last
     709    ///edges of the %DFS paths.
     710    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     711    ///
     712    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
     713    ///Instantiates a PredMap.
     714 
     715    ///This function instantiates a \ref PredMap.
     716    ///\param G is the graph, to which we would like to define the PredMap.
     717    ///\todo The graph alone may be insufficient to initialize
     718    static PredMap *createPredMap(const GR &G)
     719    {
     720      return new PredMap();
     721    }
     722//     ///\brief The type of the map that stores the last but one
     723//     ///nodes of the %DFS paths.
     724//     ///
     725//     ///The type of the map that stores the last but one
     726//     ///nodes of the %DFS paths.
     727//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     728//     ///
     729//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     730//     ///Instantiates a PredNodeMap.
     731   
     732//     ///This function instantiates a \ref PredNodeMap.
     733//     ///\param G is the graph, to which
     734//     ///we would like to define the \ref PredNodeMap
     735//     static PredNodeMap *createPredNodeMap(const GR &G)
     736//     {
     737//       return new PredNodeMap();
     738//     }
     739
     740    ///The type of the map that indicates which nodes are processed.
     741 
     742    ///The type of the map that indicates which nodes are processed.
     743    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     744    ///\todo named parameter to set this type, function to read and write.
     745    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     746    ///Instantiates a ProcessedMap.
     747 
     748    ///This function instantiates a \ref ProcessedMap.
     749    ///\param G is the graph, to which
     750    ///we would like to define the \ref ProcessedMap
     751    static ProcessedMap *createProcessedMap(const GR &G)
     752    {
     753      return new ProcessedMap();
     754    }
     755    ///The type of the map that indicates which nodes are reached.
     756 
     757    ///The type of the map that indicates which nodes are reached.
     758    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     759    ///\todo named parameter to set this type, function to read and write.
     760    typedef typename Graph::template NodeMap<bool> ReachedMap;
     761    ///Instantiates a ReachedMap.
     762 
     763    ///This function instantiates a \ref ReachedMap.
     764    ///\param G is the graph, to which
     765    ///we would like to define the \ref ReachedMap.
     766    static ReachedMap *createReachedMap(const GR &G)
     767    {
     768      return new ReachedMap(G);
     769    }
     770    ///The type of the map that stores the dists of the nodes.
     771 
     772    ///The type of the map that stores the dists of the nodes.
     773    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     774    ///
     775    typedef NullMap<typename Graph::Node,int> DistMap;
     776    ///Instantiates a DistMap.
     777 
     778    ///This function instantiates a \ref DistMap.
     779    ///\param G is the graph, to which we would like to define the \ref DistMap
     780    static DistMap *createDistMap(const GR &G)
     781    {
     782      return new DistMap();
     783    }
    282784  };
    283785 
    284 /// @}
     786  /// Default traits used by \ref DfsWizard
     787
     788  /// To make it easier to use Dfs algorithm
     789  ///we have created a wizard class.
     790  /// This \ref DfsWizard class needs default traits,
     791  ///as well as the \ref Dfs class.
     792  /// The \ref DfsWizardBase is a class to be the default traits of the
     793  /// \ref DfsWizard class.
     794  template<class GR>
     795  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     796  {
     797
     798    typedef DfsWizardDefaultTraits<GR> Base;
     799  protected:
     800    /// Type of the nodes in the graph.
     801    typedef typename Base::Graph::Node Node;
     802
     803    /// Pointer to the underlying graph.
     804    void *_g;
     805    ///Pointer to the map of reached nodes.
     806    void *_reached;
     807    ///Pointer to the map of processed nodes.
     808    void *_processed;
     809    ///Pointer to the map of predecessors edges.
     810    void *_pred;
     811//     ///Pointer to the map of predecessors nodes.
     812//     void *_predNode;
     813    ///Pointer to the map of distances.
     814    void *_dist;
     815    ///Pointer to the source node.
     816    Node _source;
     817   
     818    public:
     819    /// Constructor.
     820   
     821    /// This constructor does not require parameters, therefore it initiates
     822    /// all of the attributes to default values (0, INVALID).
     823    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     824//                         _predNode(0),
     825                           _dist(0), _source(INVALID) {}
     826
     827    /// Constructor.
     828   
     829    /// This constructor requires some parameters,
     830    /// listed in the parameters list.
     831    /// Others are initiated to 0.
     832    /// \param g is the initial value of  \ref _g
     833    /// \param s is the initial value of  \ref _source
     834    DfsWizardBase(const GR &g, Node s=INVALID) :
     835      _g((void *)&g), _reached(0), _processed(0), _pred(0),
     836//       _predNode(0),
     837      _dist(0), _source(s) {}
     838
     839  };
    285840 
     841  /// A class to make the usage of Dfs algorithm easier
     842
     843  /// This class is created to make it easier to use Dfs algorithm.
     844  /// It uses the functions and features of the plain \ref Dfs,
     845  /// but it is much simpler to use it.
     846  ///
     847  /// Simplicity means that the way to change the types defined
     848  /// in the traits class is based on functions that returns the new class
     849  /// and not on templatable built-in classes.
     850  /// When using the plain \ref Dfs
     851  /// the new class with the modified type comes from
     852  /// the original class by using the ::
     853  /// operator. In the case of \ref DfsWizard only
     854  /// a function have to be called and it will
     855  /// return the needed class.
     856  ///
     857  /// It does not have own \ref run method. When its \ref run method is called
     858  /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run
     859  /// method of it.
     860  template<class TR>
     861  class DfsWizard : public TR
     862  {
     863    typedef TR Base;
     864
     865    ///The type of the underlying graph.
     866    typedef typename TR::Graph Graph;
     867    //\e
     868    typedef typename Graph::Node Node;
     869    //\e
     870    typedef typename Graph::NodeIt NodeIt;
     871    //\e
     872    typedef typename Graph::Edge Edge;
     873    //\e
     874    typedef typename Graph::OutEdgeIt OutEdgeIt;
     875   
     876    ///\brief The type of the map that stores
     877    ///the reached nodes
     878    typedef typename TR::ReachedMap ReachedMap;
     879    ///\brief The type of the map that stores
     880    ///the processed nodes
     881    typedef typename TR::ProcessedMap ProcessedMap;
     882    ///\brief The type of the map that stores the last
     883    ///edges of the %DFS paths.
     884    typedef typename TR::PredMap PredMap;
     885//     ///\brief The type of the map that stores the last but one
     886//     ///nodes of the %DFS paths.
     887//     typedef typename TR::PredNodeMap PredNodeMap;
     888    ///The type of the map that stores the dists of the nodes.
     889    typedef typename TR::DistMap DistMap;
     890
     891public:
     892    /// Constructor.
     893    DfsWizard() : TR() {}
     894
     895    /// Constructor that requires parameters.
     896
     897    /// Constructor that requires parameters.
     898    /// These parameters will be the default values for the traits class.
     899    DfsWizard(const Graph &g, Node s=INVALID) :
     900      TR(g,s) {}
     901
     902    ///Copy constructor
     903    DfsWizard(const TR &b) : TR(b) {}
     904
     905    ~DfsWizard() {}
     906
     907    ///Runs Dfs algorithm from a given node.
     908   
     909    ///Runs Dfs algorithm from a given node.
     910    ///The node can be given by the \ref source function.
     911    void run()
     912    {
     913      if(Base::_source==INVALID) throw UninitializedParameter();
     914      Dfs<Graph,TR> alg(*(Graph*)Base::_g);
     915      if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
     916      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
     917      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
     918//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
     919      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
     920      alg.run(Base::_source);
     921    }
     922
     923    ///Runs Dfs algorithm from the given node.
     924
     925    ///Runs Dfs algorithm from the given node.
     926    ///\param s is the given source.
     927    void run(Node s)
     928    {
     929      Base::_source=s;
     930      run();
     931    }
     932
     933    template<class T>
     934    struct DefPredMapBase : public Base {
     935      typedef T PredMap;
     936      static PredMap *createPredMap(const Graph &G) { return 0; };
     937      DefPredMapBase(const Base &b) : Base(b) {}
     938    };
     939   
     940    ///\brief \ref named-templ-param "Named parameter"
     941    ///function for setting PredMap type
     942    ///
     943    /// \ref named-templ-param "Named parameter"
     944    ///function for setting PredMap type
     945    ///
     946    template<class T>
     947    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
     948    {
     949      Base::_pred=(void *)&t;
     950      return DfsWizard<DefPredMapBase<T> >(*this);
     951    }
     952   
     953 
     954    template<class T>
     955    struct DefReachedMapBase : public Base {
     956      typedef T ReachedMap;
     957      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
     958      DefReachedMapBase(const Base &b) : Base(b) {}
     959    };
     960   
     961    ///\brief \ref named-templ-param "Named parameter"
     962    ///function for setting ReachedMap
     963    ///
     964    /// \ref named-templ-param "Named parameter"
     965    ///function for setting ReachedMap
     966    ///
     967    template<class T>
     968    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     969    {
     970      Base::_pred=(void *)&t;
     971      return DfsWizard<DefReachedMapBase<T> >(*this);
     972    }
     973   
     974
     975    template<class T>
     976    struct DefProcessedMapBase : public Base {
     977      typedef T ProcessedMap;
     978      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
     979      DefProcessedMapBase(const Base &b) : Base(b) {}
     980    };
     981   
     982    ///\brief \ref named-templ-param "Named parameter"
     983    ///function for setting ProcessedMap
     984    ///
     985    /// \ref named-templ-param "Named parameter"
     986    ///function for setting ProcessedMap
     987    ///
     988    template<class T>
     989    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     990    {
     991      Base::_pred=(void *)&t;
     992      return DfsWizard<DefProcessedMapBase<T> >(*this);
     993    }
     994   
     995
     996//     template<class T>
     997//     struct DefPredNodeMapBase : public Base {
     998//       typedef T PredNodeMap;
     999//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
     1000//       DefPredNodeMapBase(const Base &b) : Base(b) {}
     1001//     };
     1002   
     1003//     ///\brief \ref named-templ-param "Named parameter"
     1004//     ///function for setting PredNodeMap type
     1005//     ///
     1006//     /// \ref named-templ-param "Named parameter"
     1007//     ///function for setting PredNodeMap type
     1008//     ///
     1009//     template<class T>
     1010//     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     1011//     {
     1012//       Base::_predNode=(void *)&t;
     1013//       return DfsWizard<DefPredNodeMapBase<T> >(*this);
     1014//     }
     1015   
     1016    template<class T>
     1017    struct DefDistMapBase : public Base {
     1018      typedef T DistMap;
     1019      static DistMap *createDistMap(const Graph &G) { return 0; };
     1020      DefDistMapBase(const Base &b) : Base(b) {}
     1021    };
     1022   
     1023    ///\brief \ref named-templ-param "Named parameter"
     1024    ///function for setting DistMap type
     1025    ///
     1026    /// \ref named-templ-param "Named parameter"
     1027    ///function for setting DistMap type
     1028    ///
     1029    template<class T>
     1030    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
     1031    {
     1032      Base::_dist=(void *)&t;
     1033      return DfsWizard<DefDistMapBase<T> >(*this);
     1034    }
     1035   
     1036    /// Sets the source node, from which the Dfs algorithm runs.
     1037
     1038    /// Sets the source node, from which the Dfs algorithm runs.
     1039    /// \param s is the source node.
     1040    DfsWizard<TR> &source(Node s)
     1041    {
     1042      Base::_source=s;
     1043      return *this;
     1044    }
     1045   
     1046  };
     1047 
     1048  ///Function type interface for Dfs algorithm.
     1049
     1050  /// \ingroup flowalgs
     1051  ///Function type interface for Dfs algorithm.
     1052  ///
     1053  ///This function also has several
     1054  ///\ref named-templ-func-param "named parameters",
     1055  ///they are declared as the members of class \ref DfsWizard.
     1056  ///The following
     1057  ///example shows how to use these parameters.
     1058  ///\code
     1059  ///  dfs(g,source).predMap(preds).run();
     1060  ///\endcode
     1061  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1062  ///to the end of the parameter list.
     1063  ///\sa DfsWizard
     1064  ///\sa Dfs
     1065  template<class GR>
     1066  DfsWizard<DfsWizardBase<GR> >
     1067  dfs(const GR &g,typename GR::Node s=INVALID)
     1068  {
     1069    return DfsWizard<DfsWizardBase<GR> >(g,s);
     1070  }
     1071
    2861072} //END OF NAMESPACE LEMON
    2871073
    2881074#endif
    2891075
    290 
Note: See TracChangeset for help on using the changeset viewer.