COIN-OR::LEMON - Graph Library

Changeset 1218:5331168bbb18 in lemon-0.x


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
Location:
src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bfs.h

    r1164 r1218  
    2121///\file
    2222///\brief Bfs algorithm.
    23 ///
    24 ///\todo Revise Manual.
    25 
    26 #include <lemon/bin_heap.h>
     23
     24#include <lemon/list_graph.h>
     25#include <lemon/graph_utils.h>
    2726#include <lemon/invalid.h>
    28 #include <lemon/graph_utils.h>
     27#include <lemon/error.h>
     28#include <lemon/maps.h>
    2929
    3030namespace lemon {
    3131
    32 /// \addtogroup flowalgs
    33 /// @{
    34 
     32
     33 
     34  ///Default traits class of Bfs class.
     35
     36  ///Default traits class of Bfs class.
     37  ///\param GR Graph type.
     38  template<class GR>
     39  struct BfsDefaultTraits
     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 shortest paths.
     45    ///
     46    ///The type of the map that stores the last
     47    ///edges of the shortest 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 shortest paths.
     62//     ///
     63//     ///The type of the map that stores the last but one
     64//     ///nodes of the shortest 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 
    35124  ///%BFS algorithm class.
    36 
    37   ///This class provides an efficient implementation of %BFS algorithm.
    38   ///\param GR The graph type the algorithm runs on.
    39   ///This class does the same as Dijkstra does with constant 1 edge length,
    40   ///but it is faster.
     125 
     126  ///\ingroup flowalgs
     127  ///This class provides an efficient implementation of the %BFS algorithm.
    41128  ///
    42   ///\author Alpar Juttner
     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 Bfs, it
     131  ///is only passed to \ref BfsDefaultTraits.
     132  ///\param TR Traits class to set various data types used by the algorithm.
     133  ///The default traits class is
     134  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
     135  ///See \ref BfsDefaultTraits for the documentation of
     136  ///a Bfs traits class.
     137  ///
     138  ///\author Jacint Szabo and Alpar Juttner
     139  ///\todo A compare object would be nice.
    43140
    44141#ifdef DOXYGEN
    45   template <typename GR>
     142  template <typename GR,
     143            typename TR>
    46144#else
    47   template <typename GR>
     145  template <typename GR=ListGraph,
     146            typename TR=BfsDefaultTraits<GR> >
    48147#endif
    49   class Bfs{
     148  class Bfs {
    50149  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::Bfs::UninitializedParameter";
     160      }
     161    };
     162
     163    typedef TR Traits;
    51164    ///The type of the underlying graph.
    52     typedef GR Graph;
     165    typedef typename TR::Graph Graph;
    53166    ///\e
    54167    typedef typename Graph::Node Node;
     
    62175    ///\brief The type of the map that stores the last
    63176    ///edges of the shortest paths.
    64     typedef typename Graph::template NodeMap<Edge> PredMap;
    65     ///\brief The type of the map that stores the last but one
    66     ///nodes of the shortest paths.
    67     typedef typename Graph::template NodeMap<Node> PredNodeMap;
     177    typedef typename TR::PredMap PredMap;
     178//     ///\brief The type of the map that stores the last but one
     179//     ///nodes of the shortest 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;
    68185    ///The type of the map that stores the dists of the nodes.
    69     typedef typename Graph::template NodeMap<int> DistMap;
    70 
     186    typedef typename TR::DistMap DistMap;
    71187  private:
    72188    /// Pointer to the underlying graph.
    73189    const Graph *G;
    74190    ///Pointer to the map of predecessors edges.
    75     PredMap *predecessor;
    76     ///Indicates if \ref predecessor is locally allocated (\c true) or not.
    77     bool local_predecessor;
    78     ///Pointer to the map of predecessors nodes.
    79     PredNodeMap *pred_node;
    80     ///Indicates if \ref pred_node is locally allocated (\c true) or not.
    81     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;
    82198    ///Pointer to the map of distances.
    83     DistMap *distance;
    84     ///Indicates if \ref distance is locally allocated (\c true) or not.
    85     bool local_distance;
    86 
    87     ///The source node of the last execution.
    88     Node source;
    89 
    90 
    91     ///Initializes the maps.
    92     void init_maps()
    93     {
    94       if(!predecessor) {
    95         local_predecessor = true;
    96         predecessor = new PredMap(*G);
    97       }
    98       if(!pred_node) {
    99         local_pred_node = true;
    100         pred_node = new PredNodeMap(*G);
    101       }
    102       if(!distance) {
    103         local_distance = true;
    104         distance = new DistMap(*G);
    105       }
    106     }
    107    
    108   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::Node> _queue;
     212    int _queue_head,_queue_tail,_queue_next_dist;
     213    int _curr_dist;
     214//     ///The source node of the last execution.
     215//     Node source;
     216
     217    ///Creates the maps if necessary.
     218   
     219    ///\todo Error if \c G are \c NULL.
     220    ///\todo Better memory allocation (instead of new).
     221    void create_maps()
     222    {
     223      if(!_pred) {
     224        local_pred = true;
     225        _pred = Traits::createPredMap(*G);
     226      }
     227//       if(!_predNode) {
     228//      local_predNode = true;
     229//      _predNode = Traits::createPredNodeMap(*G);
     230//       }
     231      if(!_dist) {
     232        local_dist = true;
     233        _dist = Traits::createDistMap(*G);
     234      }
     235      if(!_reached) {
     236        local_reached = true;
     237        _reached = Traits::createReachedMap(*G);
     238      }
     239      if(!_processed) {
     240        local_processed = true;
     241        _processed = Traits::createProcessedMap(*G);
     242      }
     243    }
     244   
     245  public :
     246 
     247    ///\name Named template parameters
     248
     249    ///@{
     250
     251    template <class T>
     252    struct DefPredMapTraits : public Traits {
     253      typedef T PredMap;
     254      static PredMap *createPredMap(const Graph &G)
     255      {
     256        throw UninitializedParameter();
     257      }
     258    };
     259    ///\ref named-templ-param "Named parameter" for setting PredMap type
     260
     261    ///\ref named-templ-param "Named parameter" for setting PredMap type
     262    ///
     263    template <class T>
     264    class DefPredMap : public Bfs< Graph,
     265                                        DefPredMapTraits<T> > { };
     266   
     267//     template <class T>
     268//     struct DefPredNodeMapTraits : public Traits {
     269//       typedef T PredNodeMap;
     270//       static PredNodeMap *createPredNodeMap(const Graph &G)
     271//       {
     272//      throw UninitializedParameter();
     273//       }
     274//     };
     275//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     276
     277//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     278//     ///
     279//     template <class T>
     280//     class DefPredNodeMap : public Bfs< Graph,
     281//                                          LengthMap,
     282//                                          DefPredNodeMapTraits<T> > { };
     283   
     284    template <class T>
     285    struct DefDistMapTraits : public Traits {
     286      typedef T DistMap;
     287      static DistMap *createDistMap(const Graph &G)
     288      {
     289        throw UninitializedParameter();
     290      }
     291    };
     292    ///\ref named-templ-param "Named parameter" for setting DistMap type
     293
     294    ///\ref named-templ-param "Named parameter" for setting DistMap type
     295    ///
     296    template <class T>
     297    class DefDistMap : public Bfs< Graph,
     298                                   DefDistMapTraits<T> > { };
     299   
     300    template <class T>
     301    struct DefReachedMapTraits : public Traits {
     302      typedef T ReachedMap;
     303      static ReachedMap *createReachedMap(const Graph &G)
     304      {
     305        throw UninitializedParameter();
     306      }
     307    };
     308    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     309
     310    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     311    ///
     312    template <class T>
     313    class DefReachedMap : public Bfs< Graph,
     314                                      DefReachedMapTraits<T> > { };
     315   
     316    struct DefGraphReachedMapTraits : public Traits {
     317      typedef typename Graph::template NodeMap<bool> ReachedMap;
     318      static ReachedMap *createReachedMap(const Graph &G)
     319      {
     320        return new ReachedMap(G);
     321      }
     322    };
     323    template <class T>
     324    struct DefProcessedMapTraits : public Traits {
     325      typedef T ProcessedMap;
     326      static ProcessedMap *createProcessedMap(const Graph &G)
     327      {
     328        throw UninitializedParameter();
     329      }
     330    };
     331    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     332
     333    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     334    ///
     335    template <class T>
     336    class DefProcessedMap : public Bfs< Graph,
     337                                        DefProcessedMapTraits<T> > { };
     338   
     339    struct DefGraphProcessedMapTraits : public Traits {
     340      typedef typename Graph::template NodeMap<bool> ProcessedMap;
     341      static ProcessedMap *createProcessedMap(const Graph &G)
     342      {
     343        return new ProcessedMap(G);
     344      }
     345    };
     346    ///\brief \ref named-templ-param "Named parameter"
     347    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     348    ///
     349    ///\ref named-templ-param "Named parameter"
     350    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     351    ///If you don't set it explicitely, it will be automatically allocated.
     352    template <class T>
     353    class DefProcessedMapToBeDefaultMap :
     354      public Bfs< Graph,
     355                  DefGraphProcessedMapTraits> { };
     356   
     357    ///@}
     358
     359  public:     
     360   
    109361    ///Constructor.
    110362   
     
    113365    Bfs(const Graph& _G) :
    114366      G(&_G),
    115       predecessor(NULL), local_predecessor(false),
    116       pred_node(NULL), local_pred_node(false),
    117       distance(NULL), local_distance(false)
     367      _pred(NULL), local_pred(false),
     368//       _predNode(NULL), local_predNode(false),
     369      _dist(NULL), local_dist(false),
     370      _reached(NULL), local_reached(false),
     371      _processed(NULL), local_processed(false)
    118372    { }
    119373   
     
    121375    ~Bfs()
    122376    {
    123       if(local_predecessor) delete predecessor;
    124       if(local_pred_node) delete pred_node;
    125       if(local_distance) delete distance;
     377      if(local_pred) delete _pred;
     378//       if(local_predNode) delete _predNode;
     379      if(local_dist) delete _dist;
     380      if(local_reached) delete _reached;
     381      if(local_processed) delete _processed;
    126382    }
    127383
     
    133389    ///automatically allocated map, of course.
    134390    ///\return <tt> (*this) </tt>
    135     Bfs &setPredMap(PredMap &m)
    136     {
    137       if(local_predecessor) {
    138         delete predecessor;
    139         local_predecessor=false;
    140       }
    141       predecessor = &m;
     391    Bfs &predMap(PredMap &m)
     392    {
     393      if(local_pred) {
     394        delete _pred;
     395        local_pred=false;
     396      }
     397      _pred = &m;
    142398      return *this;
    143399    }
    144400
    145     ///Sets the map storing the predecessor nodes.
    146 
    147     ///Sets the map storing the predecessor nodes.
     401    ///Sets the map indicating the reached nodes.
     402
     403    ///Sets the map indicating the reached nodes.
    148404    ///If you don't use this function before calling \ref run(),
    149405    ///it will allocate one. The destuctor deallocates this
    150406    ///automatically allocated map, of course.
    151407    ///\return <tt> (*this) </tt>
    152     Bfs &setPredNodeMap(PredNodeMap &m)
    153     {
    154       if(local_pred_node) {
    155         delete pred_node;
    156         local_pred_node=false;
    157       }
    158       pred_node = &m;
     408    Bfs &reachedMap(ReachedMap &m)
     409    {
     410      if(local_reached) {
     411        delete _reached;
     412        local_reached=false;
     413      }
     414      _reached = &m;
    159415      return *this;
    160416    }
     417
     418    ///Sets the map indicating the processed nodes.
     419
     420    ///Sets the map indicating the processed nodes.
     421    ///If you don't use this function before calling \ref run(),
     422    ///it will allocate one. The destuctor deallocates this
     423    ///automatically allocated map, of course.
     424    ///\return <tt> (*this) </tt>
     425    Bfs &processedMap(ProcessedMap &m)
     426    {
     427      if(local_processed) {
     428        delete _processed;
     429        local_processed=false;
     430      }
     431      _processed = &m;
     432      return *this;
     433    }
     434
     435//     ///Sets the map storing the predecessor nodes.
     436
     437//     ///Sets the map storing the predecessor nodes.
     438//     ///If you don't use this function before calling \ref run(),
     439//     ///it will allocate one. The destuctor deallocates this
     440//     ///automatically allocated map, of course.
     441//     ///\return <tt> (*this) </tt>
     442//     Bfs &predNodeMap(PredNodeMap &m)
     443//     {
     444//       if(local_predNode) {
     445//      delete _predNode;
     446//      local_predNode=false;
     447//       }
     448//       _predNode = &m;
     449//       return *this;
     450//     }
    161451
    162452    ///Sets the map storing the distances calculated by the algorithm.
     
    167457    ///automatically allocated map, of course.
    168458    ///\return <tt> (*this) </tt>
    169     Bfs &setDistMap(DistMap &m)
    170     {
    171       if(local_distance) {
    172         delete distance;
    173         local_distance=false;
    174       }
    175       distance = &m;
     459    Bfs &distMap(DistMap &m)
     460    {
     461      if(local_dist) {
     462        delete _dist;
     463        local_dist=false;
     464      }
     465      _dist = &m;
    176466      return *this;
    177467    }
    178    
    179   ///Runs %BFS algorithm from node \c s.
    180 
    181   ///This method runs the %BFS algorithm from a root node \c s
    182   ///in order to
    183   ///compute a
    184   ///shortest path to each node. The algorithm computes
    185   ///- The %BFS tree.
    186   ///- The distance of each node from the root.
    187  
     468
     469  public:
     470    ///\name Execution control
     471    ///The simplest way to execute the algorithm is to use
     472    ///one of the member functions called \c run(...).
     473    ///\n
     474    ///If you need more control on the execution,
     475    ///first you must call \ref init(), then you can add several source nodes
     476    ///with \ref addSource().
     477    ///Finally \ref start() will perform the actual path
     478    ///computation.
     479
     480    ///@{
     481
     482    ///Initializes the internal data structures.
     483
     484    ///Initializes the internal data structures.
     485    ///
     486    void init()
     487    {
     488      create_maps();
     489      _queue.resize(countNodes(*G));
     490      _queue_head=_queue_tail=0;
     491      _curr_dist=1;
     492      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
     493        _pred->set(u,INVALID);
     494//      _predNode->set(u,INVALID);
     495        _reached->set(u,false);
     496        _processed->set(u,false);
     497      }
     498    }
     499   
     500    ///Adds a new source node.
     501
     502    ///Adds a new source node to the set of nodes to be processed.
     503    ///
     504    void addSource(Node s)
     505    {
     506      if(!(*_reached)[s])
     507        {
     508          _reached->set(s,true);
     509          _pred->set(s,INVALID);
     510          _dist->set(s,0);
     511          _queue[_queue_head++]=s;
     512          _queue_next_dist=_queue_head;
     513        }
     514    }
     515   
     516    ///Processes the next node.
     517
     518    ///Processes the next node.
     519    ///
     520    ///\warning The queue must not be empty!
     521    void processNextNode()
     522    {
     523      if(_queue_tail==_queue_next_dist) {
     524        _curr_dist++;
     525        _queue_next_dist=_queue_head;
     526      }
     527      Node n=_queue[_queue_tail++];
     528      _processed->set(n,true);
     529      Node m;
     530      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
     531        if(!(*_reached)[m=G->target(e)]) {
     532          _queue[_queue_head++]=m;
     533          _reached->set(m,true);
     534          _pred->set(m,e);
     535//        _pred_node->set(m,n);
     536          _dist->set(m,_curr_dist);
     537        }
     538    }
     539     
     540    ///\brief Returns \c false if there are nodes
     541    ///to be processed in the queue
     542    ///
     543    ///Returns \c false if there are nodes
     544    ///to be processed in the queue
     545    bool emptyQueue() { return _queue_tail==_queue_head; }
     546    ///Returns the number of the nodes to be processed.
     547   
     548    ///Returns the number of the nodes to be processed in the queue.
     549    ///
     550    int queueSize() { return _queue_head-_queue_tail; }
     551   
     552    ///Executes the algorithm.
     553
     554    ///Executes the algorithm.
     555    ///
     556    ///\pre init() must be called and at least one node should be added
     557    ///with addSource() before using this function.
     558    ///
     559    ///This method runs the %BFS algorithm from the root node(s)
     560    ///in order to
     561    ///compute the
     562    ///shortest path to each node. The algorithm computes
     563    ///- The shortest path tree.
     564    ///- The distance of each node from the root(s).
     565    ///
     566    void start()
     567    {
     568      while ( !emptyQueue() ) processNextNode();
     569    }
     570   
     571    ///Executes the algorithm until \c dest is reached.
     572
     573    ///Executes the algorithm until \c dest is reached.
     574    ///
     575    ///\pre init() must be called and at least one node should be added
     576    ///with addSource() before using this function.
     577    ///
     578    ///This method runs the %BFS algorithm from the root node(s)
     579    ///in order to
     580    ///compute the
     581    ///shortest path to \c dest. The algorithm computes
     582    ///- The shortest path to \c  dest.
     583    ///- The distance of \c dest from the root(s).
     584    ///
     585    void start(Node dest)
     586    {
     587      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
     588    }
     589   
     590    ///Executes the algorithm until a condition is met.
     591
     592    ///Executes the algorithm until a condition is met.
     593    ///
     594    ///\pre init() must be called and at least one node should be added
     595    ///with addSource() before using this function.
     596    ///
     597    ///\param nm must be a bool (or convertible) node map. The algorithm
     598    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     599    template<class NM>
     600      void start(const NM &nm)
     601      {
     602        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
     603      }
     604   
     605    ///Runs %BFS algorithm from node \c s.
     606   
     607    ///This method runs the %BFS algorithm from a root node \c s
     608    ///in order to
     609    ///compute the
     610    ///shortest path to each node. The algorithm computes
     611    ///- The shortest path tree.
     612    ///- The distance of each node from the root.
     613    ///
     614    ///\note d.run(s) is just a shortcut of the following code.
     615    ///\code
     616    ///  d.init();
     617    ///  d.addSource(s);
     618    ///  d.start();
     619    ///\endcode
    188620    void run(Node s) {
    189      
    190       init_maps();
    191      
    192       source = s;
    193      
    194       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    195         predecessor->set(u,INVALID);
    196         pred_node->set(u,INVALID);
    197       }
    198      
    199       int N = countNodes(*G);
    200       std::vector<typename Graph::Node> Q(N);
    201       int Qh=0;
    202       int Qt=0;
    203      
    204       Q[Qh++]=source;
    205       distance->set(s, 0);
    206       do {
    207         Node m;
    208         Node n=Q[Qt++];
    209         int d= (*distance)[n]+1;
    210        
    211         for(OutEdgeIt e(*G,n);e!=INVALID;++e)
    212           if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
    213             Q[Qh++]=m;
    214             predecessor->set(m,e);
    215             pred_node->set(m,n);
    216             distance->set(m,d);
    217           }
    218       } while(Qt!=Qh);
    219     }
    220    
    221     ///The distance of a node from the root.
    222 
    223     ///Returns the distance of a node from the root.
     621      init();
     622      addSource(s);
     623      start();
     624    }
     625   
     626    ///Finds the shortest path between \c s and \c t.
     627   
     628    ///Finds the shortest path between \c s and \c t.
     629    ///
     630    ///\return The length of the shortest s---t path if there exists one,
     631    ///0 otherwise.
     632    ///\note Apart from the return value, d.run(s) is
     633    ///just a shortcut of the following code.
     634    ///\code
     635    ///  d.init();
     636    ///  d.addSource(s);
     637    ///  d.start(t);
     638    ///\endcode
     639    int run(Node s,Node t) {
     640      init();
     641      addSource(s);
     642      start(t);
     643      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
     644    }
     645   
     646    ///@}
     647
     648    ///\name Query Functions
     649    ///The result of the %BFS algorithm can be obtained using these
     650    ///functions.\n
     651    ///Before the use of these functions,
     652    ///either run() or start() must be called.
     653   
     654    ///@{
     655
     656    ///The distance of a node from the root(s).
     657
     658    ///Returns the distance of a node from the root(s).
    224659    ///\pre \ref run() must be called before using this function.
    225     ///\warning If node \c v in unreachable from the root the return value
     660    ///\warning If node \c v in unreachable from the root(s) the return value
    226661    ///of this funcion is undefined.
    227     int dist(Node v) const { return (*distance)[v]; }
    228 
    229     ///Returns the 'previous edge' of the %BFS path tree.
    230 
    231     ///For a node \c v it returns the 'previous edge' of the %BFS tree,
    232     ///i.e. it returns the last edge of a shortest path from the root to \c
     662    int dist(Node v) const { return (*_dist)[v]; }
     663
     664    ///Returns the 'previous edge' of the shortest path tree.
     665
     666    ///For a node \c v it returns the 'previous edge'
     667    ///of the shortest path tree,
     668    ///i.e. it returns the last edge of a shortest path from the root(s) to \c
    233669    ///v. It is \ref INVALID
    234     ///if \c v is unreachable from the root or if \c v=s. The
    235     ///%BFS tree used here is equal to the %BFS tree used in
    236     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     670    ///if \c v is unreachable from the root(s) or \c v is a root. The
     671    ///shortest path tree used here is equal to the shortest path tree used in
     672    ///\ref predNode(Node v).
     673    ///\pre Either \ref run() or \ref start() must be called before using
    237674    ///this function.
    238     Edge pred(Node v) const { return (*predecessor)[v]; }
    239 
    240     ///Returns the 'previous node' of the %BFS tree.
    241 
    242     ///For a node \c v it returns the 'previous node' on the %BFS tree,
     675    ///\todo predEdge could be a better name.
     676    Edge pred(Node v) const { return (*_pred)[v];}
     677
     678    ///Returns the 'previous node' of the shortest path tree.
     679
     680    ///For a node \c v it returns the 'previous node'
     681    ///of the shortest path tree,
    243682    ///i.e. it returns the last but one node from a shortest path from the
    244     ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
    245     ///\c v=s. The shortest path tree used here is equal to the %BFS
    246     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
     683    ///root(a) to \c /v.
     684    ///It is INVALID if \c v is unreachable from the root(s) or
     685    ///if \c v itself a root.
     686    ///The shortest path tree used here is equal to the shortest path
     687    ///tree used in \ref pred(Node v).
     688    ///\pre Either \ref run() or \ref start() must be called before
    247689    ///using this function.
    248     Node predNode(Node v) const { return (*pred_node)[v]; }
     690    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
     691                                  G->source((*_pred)[v]); }
    249692   
    250693    ///Returns a reference to the NodeMap of distances.
    251    
    252     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
     694
     695    ///Returns a reference to the NodeMap of distances.
     696    ///\pre Either \ref run() or \ref init() must
    253697    ///be called before using this function.
    254     const DistMap &distMap() const { return *distance;}
    255  
    256     ///Returns a reference to the %BFS tree map.
     698    const DistMap &distMap() const { return *_dist;}
     699 
     700    ///Returns a reference to the shortest path tree map.
    257701
    258702    ///Returns a reference to the NodeMap of the edges of the
    259     ///%BFS tree.
    260     ///\pre \ref run() must be called before using this function.
    261     const PredMap &predMap() const { return *predecessor;}
    262  
    263     ///Returns a reference to the map of last but one nodes of shortest paths.
    264 
    265     ///Returns a reference to the NodeMap of the last but one nodes on the
    266     ///%BFS tree.
    267     ///\pre \ref run() must be called before using this function.
    268     const PredNodeMap &predNodeMap() const { return *pred_node;}
     703    ///shortest path tree.
     704    ///\pre Either \ref run() or \ref init()
     705    ///must be called before using this function.
     706    const PredMap &predMap() const { return *_pred;}
     707 
     708//     ///Returns a reference to the map of nodes of shortest paths.
     709
     710//     ///Returns a reference to the NodeMap of the last but one nodes of the
     711//     ///shortest path tree.
     712//     ///\pre \ref run() must be called before using this function.
     713//     const PredNodeMap &predNodeMap() const { return *_predNode;}
    269714
    270715    ///Checks if a node is reachable from the root.
    271716
    272717    ///Returns \c true if \c v is reachable from the root.
    273     ///\note The root node is reported to be reached!
    274     ///
    275     ///\pre \ref run() must be called before using this function.
    276     ///
    277     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
    278    
     718    ///\warning The source nodes are inditated as unreached.
     719    ///\pre Either \ref run() or \ref start()
     720    ///must be called before using this function.
     721    ///
     722    bool reached(Node v) { return (*_reached)[v]; }
     723   
     724    ///@}
     725  };
     726
     727  ///Default traits class of Bfs function.
     728
     729  ///Default traits class of Bfs function.
     730  ///\param GR Graph type.
     731  template<class GR>
     732  struct BfsWizardDefaultTraits
     733  {
     734    ///The graph type the algorithm runs on.
     735    typedef GR Graph;
     736    ///\brief The type of the map that stores the last
     737    ///edges of the shortest paths.
     738    ///
     739    ///The type of the map that stores the last
     740    ///edges of the shortest paths.
     741    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     742    ///
     743    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
     744    ///Instantiates a PredMap.
     745 
     746    ///This function instantiates a \ref PredMap.
     747    ///\param G is the graph, to which we would like to define the PredMap.
     748    ///\todo The graph alone may be insufficient to initialize
     749    static PredMap *createPredMap(const GR &G)
     750    {
     751      return new PredMap();
     752    }
     753//     ///\brief The type of the map that stores the last but one
     754//     ///nodes of the shortest paths.
     755//     ///
     756//     ///The type of the map that stores the last but one
     757//     ///nodes of the shortest paths.
     758//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     759//     ///
     760//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     761//     ///Instantiates a PredNodeMap.
     762   
     763//     ///This function instantiates a \ref PredNodeMap.
     764//     ///\param G is the graph, to which
     765//     ///we would like to define the \ref PredNodeMap
     766//     static PredNodeMap *createPredNodeMap(const GR &G)
     767//     {
     768//       return new PredNodeMap();
     769//     }
     770
     771    ///The type of the map that indicates which nodes are processed.
     772 
     773    ///The type of the map that indicates which nodes are processed.
     774    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     775    ///\todo named parameter to set this type, function to read and write.
     776    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     777    ///Instantiates a ProcessedMap.
     778 
     779    ///This function instantiates a \ref ProcessedMap.
     780    ///\param G is the graph, to which
     781    ///we would like to define the \ref ProcessedMap
     782    static ProcessedMap *createProcessedMap(const GR &G)
     783    {
     784      return new ProcessedMap();
     785    }
     786    ///The type of the map that indicates which nodes are reached.
     787 
     788    ///The type of the map that indicates which nodes are reached.
     789    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     790    ///\todo named parameter to set this type, function to read and write.
     791    typedef typename Graph::template NodeMap<bool> ReachedMap;
     792    ///Instantiates a ReachedMap.
     793 
     794    ///This function instantiates a \ref ReachedMap.
     795    ///\param G is the graph, to which
     796    ///we would like to define the \ref ReachedMap.
     797    static ReachedMap *createReachedMap(const GR &G)
     798    {
     799      return new ReachedMap(G);
     800    }
     801    ///The type of the map that stores the dists of the nodes.
     802 
     803    ///The type of the map that stores the dists of the nodes.
     804    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     805    ///
     806    typedef NullMap<typename Graph::Node,int> DistMap;
     807    ///Instantiates a DistMap.
     808 
     809    ///This function instantiates a \ref DistMap.
     810    ///\param G is the graph, to which we would like to define the \ref DistMap
     811    static DistMap *createDistMap(const GR &G)
     812    {
     813      return new DistMap();
     814    }
    279815  };
    280816 
    281 /// @}
     817  /// Default traits used by \ref BfsWizard
     818
     819  /// To make it easier to use Bfs algorithm
     820  ///we have created a wizard class.
     821  /// This \ref BfsWizard class needs default traits,
     822  ///as well as the \ref Bfs class.
     823  /// The \ref BfsWizardBase is a class to be the default traits of the
     824  /// \ref BfsWizard class.
     825  template<class GR>
     826  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     827  {
     828
     829    typedef BfsWizardDefaultTraits<GR> Base;
     830  protected:
     831    /// Type of the nodes in the graph.
     832    typedef typename Base::Graph::Node Node;
     833
     834    /// Pointer to the underlying graph.
     835    void *_g;
     836    ///Pointer to the map of reached nodes.
     837    void *_reached;
     838    ///Pointer to the map of processed nodes.
     839    void *_processed;
     840    ///Pointer to the map of predecessors edges.
     841    void *_pred;
     842//     ///Pointer to the map of predecessors nodes.
     843//     void *_predNode;
     844    ///Pointer to the map of distances.
     845    void *_dist;
     846    ///Pointer to the source node.
     847    Node _source;
     848   
     849    public:
     850    /// Constructor.
     851   
     852    /// This constructor does not require parameters, therefore it initiates
     853    /// all of the attributes to default values (0, INVALID).
     854    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     855//                         _predNode(0),
     856                           _dist(0), _source(INVALID) {}
     857
     858    /// Constructor.
     859   
     860    /// This constructor requires some parameters,
     861    /// listed in the parameters list.
     862    /// Others are initiated to 0.
     863    /// \param g is the initial value of  \ref _g
     864    /// \param s is the initial value of  \ref _source
     865    BfsWizardBase(const GR &g, Node s=INVALID) :
     866      _g((void *)&g), _reached(0), _processed(0), _pred(0),
     867//       _predNode(0),
     868      _dist(0), _source(s) {}
     869
     870  };
    282871 
     872  /// A class to make the usage of Bfs algorithm easier
     873
     874  /// This class is created to make it easier to use Bfs algorithm.
     875  /// It uses the functions and features of the plain \ref Bfs,
     876  /// but it is much simpler to use it.
     877  ///
     878  /// Simplicity means that the way to change the types defined
     879  /// in the traits class is based on functions that returns the new class
     880  /// and not on templatable built-in classes.
     881  /// When using the plain \ref Bfs
     882  /// the new class with the modified type comes from
     883  /// the original class by using the ::
     884  /// operator. In the case of \ref BfsWizard only
     885  /// a function have to be called and it will
     886  /// return the needed class.
     887  ///
     888  /// It does not have own \ref run method. When its \ref run method is called
     889  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
     890  /// method of it.
     891  template<class TR>
     892  class BfsWizard : public TR
     893  {
     894    typedef TR Base;
     895
     896    ///The type of the underlying graph.
     897    typedef typename TR::Graph Graph;
     898    //\e
     899    typedef typename Graph::Node Node;
     900    //\e
     901    typedef typename Graph::NodeIt NodeIt;
     902    //\e
     903    typedef typename Graph::Edge Edge;
     904    //\e
     905    typedef typename Graph::OutEdgeIt OutEdgeIt;
     906   
     907    ///\brief The type of the map that stores
     908    ///the reached nodes
     909    typedef typename TR::ReachedMap ReachedMap;
     910    ///\brief The type of the map that stores
     911    ///the processed nodes
     912    typedef typename TR::ProcessedMap ProcessedMap;
     913    ///\brief The type of the map that stores the last
     914    ///edges of the shortest paths.
     915    typedef typename TR::PredMap PredMap;
     916//     ///\brief The type of the map that stores the last but one
     917//     ///nodes of the shortest paths.
     918//     typedef typename TR::PredNodeMap PredNodeMap;
     919    ///The type of the map that stores the dists of the nodes.
     920    typedef typename TR::DistMap DistMap;
     921
     922public:
     923    /// Constructor.
     924    BfsWizard() : TR() {}
     925
     926    /// Constructor that requires parameters.
     927
     928    /// Constructor that requires parameters.
     929    /// These parameters will be the default values for the traits class.
     930    BfsWizard(const Graph &g, Node s=INVALID) :
     931      TR(g,s) {}
     932
     933    ///Copy constructor
     934    BfsWizard(const TR &b) : TR(b) {}
     935
     936    ~BfsWizard() {}
     937
     938    ///Runs Bfs algorithm from a given node.
     939   
     940    ///Runs Bfs algorithm from a given node.
     941    ///The node can be given by the \ref source function.
     942    void run()
     943    {
     944      if(Base::_source==INVALID) throw UninitializedParameter();
     945      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
     946      if(Base::_reached)
     947        alg.reachedMap(*(ReachedMap*)Base::_reached);
     948      if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
     949      if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
     950//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
     951      if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
     952      alg.run(Base::_source);
     953    }
     954
     955    ///Runs Bfs algorithm from the given node.
     956
     957    ///Runs Bfs algorithm from the given node.
     958    ///\param s is the given source.
     959    void run(Node s)
     960    {
     961      Base::_source=s;
     962      run();
     963    }
     964
     965    template<class T>
     966    struct DefPredMapBase : public Base {
     967      typedef T PredMap;
     968      static PredMap *createPredMap(const Graph &G) { return 0; };
     969      DefPredMapBase(const Base &b) : Base(b) {}
     970    };
     971   
     972    ///\brief \ref named-templ-param "Named parameter"
     973    ///function for setting PredMap
     974    ///
     975    /// \ref named-templ-param "Named parameter"
     976    ///function for setting PredMap
     977    ///
     978    template<class T>
     979    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     980    {
     981      Base::_pred=(void *)&t;
     982      return BfsWizard<DefPredMapBase<T> >(*this);
     983    }
     984   
     985 
     986    template<class T>
     987    struct DefReachedMapBase : public Base {
     988      typedef T ReachedMap;
     989      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
     990      DefReachedMapBase(const Base &b) : Base(b) {}
     991    };
     992   
     993    ///\brief \ref named-templ-param "Named parameter"
     994    ///function for setting ReachedMap
     995    ///
     996    /// \ref named-templ-param "Named parameter"
     997    ///function for setting ReachedMap
     998    ///
     999    template<class T>
     1000    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1001    {
     1002      Base::_pred=(void *)&t;
     1003      return BfsWizard<DefReachedMapBase<T> >(*this);
     1004    }
     1005   
     1006
     1007    template<class T>
     1008    struct DefProcessedMapBase : public Base {
     1009      typedef T ProcessedMap;
     1010      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
     1011      DefProcessedMapBase(const Base &b) : Base(b) {}
     1012    };
     1013   
     1014    ///\brief \ref named-templ-param "Named parameter"
     1015    ///function for setting ProcessedMap
     1016    ///
     1017    /// \ref named-templ-param "Named parameter"
     1018    ///function for setting ProcessedMap
     1019    ///
     1020    template<class T>
     1021    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1022    {
     1023      Base::_pred=(void *)&t;
     1024      return BfsWizard<DefProcessedMapBase<T> >(*this);
     1025    }
     1026   
     1027
     1028//     template<class T>
     1029//     struct DefPredNodeMapBase : public Base {
     1030//       typedef T PredNodeMap;
     1031//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
     1032//       DefPredNodeMapBase(const Base &b) : Base(b) {}
     1033//     };
     1034   
     1035//     ///\brief \ref named-templ-param "Named parameter"
     1036//     ///function for setting PredNodeMap type
     1037//     ///
     1038//     /// \ref named-templ-param "Named parameter"
     1039//     ///function for setting PredNodeMap type
     1040//     ///
     1041//     template<class T>
     1042//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     1043//     {
     1044//       Base::_predNode=(void *)&t;
     1045//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
     1046//     }
     1047   
     1048    template<class T>
     1049    struct DefDistMapBase : public Base {
     1050      typedef T DistMap;
     1051      static DistMap *createDistMap(const Graph &G) { return 0; };
     1052      DefDistMapBase(const Base &b) : Base(b) {}
     1053    };
     1054   
     1055    ///\brief \ref named-templ-param "Named parameter"
     1056    ///function for setting DistMap type
     1057    ///
     1058    /// \ref named-templ-param "Named parameter"
     1059    ///function for setting DistMap type
     1060    ///
     1061    template<class T>
     1062    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
     1063    {
     1064      Base::_dist=(void *)&t;
     1065      return BfsWizard<DefDistMapBase<T> >(*this);
     1066    }
     1067   
     1068    /// Sets the source node, from which the Bfs algorithm runs.
     1069
     1070    /// Sets the source node, from which the Bfs algorithm runs.
     1071    /// \param s is the source node.
     1072    BfsWizard<TR> &source(Node s)
     1073    {
     1074      Base::_source=s;
     1075      return *this;
     1076    }
     1077   
     1078  };
     1079 
     1080  ///Function type interface for Bfs algorithm.
     1081
     1082  /// \ingroup flowalgs
     1083  ///Function type interface for Bfs algorithm.
     1084  ///
     1085  ///This function also has several
     1086  ///\ref named-templ-func-param "named parameters",
     1087  ///they are declared as the members of class \ref BfsWizard.
     1088  ///The following
     1089  ///example shows how to use these parameters.
     1090  ///\code
     1091  ///  bfs(g,source).predMap(preds).run();
     1092  ///\endcode
     1093  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1094  ///to the end of the parameter list.
     1095  ///\sa BfsWizard
     1096  ///\sa Bfs
     1097  template<class GR>
     1098  BfsWizard<BfsWizardBase<GR> >
     1099  bfs(const GR &g,typename GR::Node s=INVALID)
     1100  {
     1101    return BfsWizard<BfsWizardBase<GR> >(g,s);
     1102  }
     1103
    2831104} //END OF NAMESPACE LEMON
    2841105
    2851106#endif
    2861107
    287 
  • 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 
  • src/lemon/dijkstra.h

    r1201 r1218  
    7777      return new PredMap(G);
    7878    }
    79     ///\brief The type of the map that stores the last but one
    80     ///nodes of the shortest paths.
    81     ///
    82     ///The type of the map that stores the last but one
    83     ///nodes of the shortest paths.
    84     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    85     ///
    86     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
    87     ///Instantiates a PredNodeMap.
    88    
    89     ///This function instantiates a \ref PredNodeMap.
    90     ///\param G is the graph, to which
    91     ///we would like to define the \ref PredNodeMap
    92     static PredNodeMap *createPredNodeMap(const GR &G)
    93     {
    94       return new PredNodeMap();
    95     }
    96 
    97     ///The type of the map that stores whether a nodes is reached.
    98  
    99     ///The type of the map that stores whether a nodes is reached.
     79//     ///\brief The type of the map that stores the last but one
     80//     ///nodes of the shortest paths.
     81//     ///
     82//     ///The type of the map that stores the last but one
     83//     ///nodes of the shortest paths.
     84//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     85//     ///
     86//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
     87//     ///Instantiates a PredNodeMap.
     88   
     89//     ///This function instantiates a \ref PredNodeMap.
     90//     ///\param G is the graph, to which
     91//     ///we would like to define the \ref PredNodeMap
     92//     static PredNodeMap *createPredNodeMap(const GR &G)
     93//     {
     94//       return new PredNodeMap();
     95//     }
     96
     97    ///The type of the map that stores whether a nodes is processed.
     98 
     99    ///The type of the map that stores whether a nodes is processed.
    100100    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    101101    ///By default it is a NullMap.
    102     ///\todo If it is set to a real map, Dijkstra::reached() should read this.
     102    ///\todo If it is set to a real map,
     103    ///Dijkstra::processed() should read this.
    103104    ///\todo named parameter to set this type, function to read and write.
    104     typedef NullMap<typename Graph::Node,bool> ReachedMap;
    105     ///Instantiates a ReachedMap.
    106  
    107     ///This function instantiates a \ref ReachedMap.
     105    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     106    ///Instantiates a ProcessedMap.
     107 
     108    ///This function instantiates a \ref ProcessedMap.
    108109    ///\param G is the graph, to which
    109     ///we would like to define the \ref ReachedMap
    110     static ReachedMap *createReachedMap(const GR &G)
    111     {
    112       return new ReachedMap();
     110    ///we would like to define the \ref ProcessedMap
     111    static ProcessedMap *createProcessedMap(const GR &G)
     112    {
     113      return new ProcessedMap();
    113114    }
    114115    ///The type of the map that stores the dists of the nodes.
     
    141142  ///It is also possible to change the underlying priority heap.
    142143  ///
    143   ///\param GR The graph type the algorithm runs on. The default value is
    144   ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
    145   ///is only passed to \ref DijkstraDefaultTraits.
    146   ///\param LM This read-only
    147   ///EdgeMap
    148   ///determines the
    149   ///lengths of the edges. It is read once for each edge, so the map
    150   ///may involve in relatively time consuming process to compute the edge
    151   ///length if it is necessary. The default map type is
    152   ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
    153   ///The value of LM is not used directly by Dijkstra, it
    154   ///is only passed to \ref DijkstraDefaultTraits.
    155   ///\param TR Traits class to set various data types used by the algorithm.
    156   ///The default traits class is
    157   ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
    158   ///See \ref DijkstraDefaultTraits for the documentation of
    159   ///a Dijkstra traits class.
     144  ///\param GR The graph type the algorithm runs on. The default value
     145  ///is \ref ListGraph. The value of GR is not used directly by
     146  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
     147  ///\param LM This read-only EdgeMap determines the lengths of the
     148  ///edges. It is read once for each edge, so the map may involve in
     149  ///relatively time consuming process to compute the edge length if
     150  ///it is necessary. The default map type is \ref
     151  ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
     152  ///of LM is not used directly by Dijkstra, it is only passed to \ref
     153  ///DijkstraDefaultTraits.  \param TR Traits class to set
     154  ///various data types used by the algorithm.  The default traits
     155  ///class is \ref DijkstraDefaultTraits
     156  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
     157  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
     158  ///class.
    160159  ///
    161160  ///\author Jacint Szabo and Alpar Juttner
     
    182181    public:
    183182      virtual const char* exceptionName() const {
    184         return "lemon::Dijsktra::UninitializedParameter";
     183        return "lemon::Dijkstra::UninitializedParameter";
    185184      }
    186185    };
     
    205204    ///edges of the shortest paths.
    206205    typedef typename TR::PredMap PredMap;
    207     ///\brief The type of the map that stores the last but one
    208     ///nodes of the shortest paths.
    209     typedef typename TR::PredNodeMap PredNodeMap;
    210     ///The type of the map indicating if a node is reached.
    211     typedef typename TR::ReachedMap ReachedMap;
     206//     ///\brief The type of the map that stores the last but one
     207//     ///nodes of the shortest paths.
     208//     typedef typename TR::PredNodeMap PredNodeMap;
     209    ///The type of the map indicating if a node is processed.
     210    typedef typename TR::ProcessedMap ProcessedMap;
    212211    ///The type of the map that stores the dists of the nodes.
    213212    typedef typename TR::DistMap DistMap;
     
    223222    ///Indicates if \ref _pred is locally allocated (\c true) or not.
    224223    bool local_pred;
    225     ///Pointer to the map of predecessors nodes.
    226     PredNodeMap *_predNode;
    227     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
    228     bool local_predNode;
     224//     ///Pointer to the map of predecessors nodes.
     225//     PredNodeMap *_predNode;
     226//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
     227//     bool local_predNode;
    229228    ///Pointer to the map of distances.
    230229    DistMap *_dist;
    231230    ///Indicates if \ref _dist is locally allocated (\c true) or not.
    232231    bool local_dist;
    233     ///Pointer to the map of reached status of the nodes.
    234     ReachedMap *_reached;
    235     ///Indicates if \ref _reached is locally allocated (\c true) or not.
    236     bool local_reached;
    237 
    238     ///The source node of the last execution.
    239     Node source;
     232    ///Pointer to the map of processed status of the nodes.
     233    ProcessedMap *_processed;
     234    ///Indicates if \ref _processed is locally allocated (\c true) or not.
     235    bool local_processed;
     236
     237//     ///The source node of the last execution.
     238//     Node source;
    240239
    241240    ///Creates the maps if necessary.
     
    249248        _pred = Traits::createPredMap(*G);
    250249      }
    251       if(!_predNode) {
    252         local_predNode = true;
    253         _predNode = Traits::createPredNodeMap(*G);
    254       }
     250//       if(!_predNode) {
     251//      local_predNode = true;
     252//      _predNode = Traits::createPredNodeMap(*G);
     253//       }
    255254      if(!_dist) {
    256255        local_dist = true;
    257256        _dist = Traits::createDistMap(*G);
    258257      }
    259       if(!_reached) {
    260         local_reached = true;
    261         _reached = Traits::createReachedMap(*G);
     258      if(!_processed) {
     259        local_processed = true;
     260        _processed = Traits::createProcessedMap(*G);
    262261      }
    263262    }
     
    286285                                        DefPredMapTraits<T> > { };
    287286   
    288     template <class T>
    289     struct DefPredNodeMapTraits : public Traits {
    290       typedef T PredNodeMap;
    291       static PredNodeMap *createPredNodeMap(const Graph &G)
    292       {
    293         throw UninitializedParameter();
    294       }
    295     };
    296     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
    297 
    298     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
    299     ///
    300     template <class T>
    301     class DefPredNodeMap : public Dijkstra< Graph,
    302                                             LengthMap,
    303                                             DefPredNodeMapTraits<T> > { };
     287//     template <class T>
     288//     struct DefPredNodeMapTraits : public Traits {
     289//       typedef T PredNodeMap;
     290//       static PredNodeMap *createPredNodeMap(const Graph &G)
     291//       {
     292//      throw UninitializedParameter();
     293//       }
     294//     };
     295//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     296
     297//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     298//     ///
     299//     template <class T>
     300//     class DefPredNodeMap : public Dijkstra< Graph,
     301//                                          LengthMap,
     302//                                          DefPredNodeMapTraits<T> > { };
    304303   
    305304    template <class T>
     
    321320   
    322321    template <class T>
    323     struct DefReachedMapTraits : public Traits {
    324       typedef T ReachedMap;
    325       static ReachedMap *createReachedMap(const Graph &G)
     322    struct DefProcessedMapTraits : public Traits {
     323      typedef T ProcessedMap;
     324      static ProcessedMap *createProcessedMap(const Graph &G)
    326325      {
    327326        throw UninitializedParameter();
    328327      }
    329328    };
    330     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
    331 
    332     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     329    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     330
     331    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
    333332    ///
    334333    template <class T>
    335     class DefReachedMap : public Dijkstra< Graph,
     334    class DefProcessedMap : public Dijkstra< Graph,
    336335                                        LengthMap,
    337                                         DefReachedMapTraits<T> > { };
    338    
    339     struct DefGraphReachedMapTraits : public Traits {
    340       typedef typename Graph::template NodeMap<bool> ReachedMap;
    341       static ReachedMap *createReachedMap(const Graph &G)
     336                                        DefProcessedMapTraits<T> > { };
     337   
     338    struct DefGraphProcessedMapTraits : public Traits {
     339      typedef typename Graph::template NodeMap<bool> ProcessedMap;
     340      static ProcessedMap *createProcessedMap(const Graph &G)
    342341      {
    343         return new ReachedMap(G);
     342        return new ProcessedMap(G);
    344343      }
    345344    };
    346345    ///\brief \ref named-templ-param "Named parameter"
    347     ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     346    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
    348347    ///
    349348    ///\ref named-templ-param "Named parameter"
    350     ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     349    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
    351350    ///If you don't set it explicitely, it will be automatically allocated.
    352351    template <class T>
    353     class DefReachedMapToBeDefaultMap :
     352    class DefProcessedMapToBeDefaultMap :
    354353      public Dijkstra< Graph,
    355354                       LengthMap,
    356                        DefGraphReachedMapTraits> { };
     355                       DefGraphProcessedMapTraits> { };
    357356   
    358357    ///@}
     
    371370      G(&_G), length(&_length),
    372371      _pred(NULL), local_pred(false),
    373       _predNode(NULL), local_predNode(false),
     372//       _predNode(NULL), local_predNode(false),
    374373      _dist(NULL), local_dist(false),
    375       _reached(NULL), local_reached(false),
     374      _processed(NULL), local_processed(false),
    376375      _heap_map(*G,-1),_heap(_heap_map)
    377376    { }
     
    381380    {
    382381      if(local_pred) delete _pred;
    383       if(local_predNode) delete _predNode;
     382//       if(local_predNode) delete _predNode;
    384383      if(local_dist) delete _dist;
    385       if(local_reached) delete _reached;
     384      if(local_processed) delete _processed;
    386385    }
    387386
     
    413412    }
    414413
    415     ///Sets the map storing the predecessor nodes.
    416 
    417     ///Sets the map storing the predecessor nodes.
    418     ///If you don't use this function before calling \ref run(),
    419     ///it will allocate one. The destuctor deallocates this
    420     ///automatically allocated map, of course.
    421     ///\return <tt> (*this) </tt>
    422     Dijkstra &predNodeMap(PredNodeMap &m)
    423     {
    424       if(local_predNode) {
    425         delete _predNode;
    426         local_predNode=false;
    427       }
    428       _predNode = &m;
    429       return *this;
    430     }
     414//     ///Sets the map storing the predecessor nodes.
     415
     416//     ///Sets the map storing the predecessor nodes.
     417//     ///If you don't use this function before calling \ref run(),
     418//     ///it will allocate one. The destuctor deallocates this
     419//     ///automatically allocated map, of course.
     420//     ///\return <tt> (*this) </tt>
     421//     Dijkstra &predNodeMap(PredNodeMap &m)
     422//     {
     423//       if(local_predNode) {
     424//      delete _predNode;
     425//      local_predNode=false;
     426//       }
     427//       _predNode = &m;
     428//       return *this;
     429//     }
    431430
    432431    ///Sets the map storing the distances calculated by the algorithm.
     
    450449    void finalizeNodeData(Node v,Value dst)
    451450    {
    452       _reached->set(v,true);
     451      _processed->set(v,true);
    453452      _dist->set(v, dst);
    454       if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
     453//       if((*_pred)[v]!=INVALID)
     454//       _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
    455455    }
    456456
    457457  public:
    458     ///\name Excetution control
     458    ///\name Execution control
    459459    ///The simplest way to execute the algorithm is to use
    460460    ///one of the member functions called \c run(...).
    461461    ///\n
    462     ///It you need more control on the execution,
     462    ///If you need more control on the execution,
    463463    ///first you must call \ref init(), then you can add several source nodes
    464     ///with \ref addSource(). Finally \ref start() will perform the actual path
     464    ///with \ref addSource().
     465    ///Finally \ref start() will perform the actual path
    465466    ///computation.
    466467
     
    478479      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    479480        _pred->set(u,INVALID);
    480         _predNode->set(u,INVALID);
    481         ///\todo *_reached is not set to false.
     481//      _predNode->set(u,INVALID);
     482        _processed->set(u,false);
    482483        _heap_map.set(u,Heap::PRE_HEAP);
    483484      }
     
    495496    void addSource(Node s,Value dst=0)
    496497    {
    497       source = s;
     498//       source = s;
    498499      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
    499500      else if(_heap[s]<dst) {
     
    536537    }
    537538
    538     ///Returns \c false if there are nodes to be processed in the priority heap
    539 
    540     ///Returns \c false if there are nodes to be processed in the priority heap
    541     ///
    542     bool emptyHeap() { return _heap.empty(); }
     539    ///\brief Returns \c false if there are nodes
     540    ///to be processed in the priority heap
     541    ///
     542    ///Returns \c false if there are nodes
     543    ///to be processed in the priority heap
     544    bool emptyQueue() { return _heap.empty(); }
    543545    ///Returns the number of the nodes to be processed in the priority heap
    544546
    545547    ///Returns the number of the nodes to be processed in the priority heap
    546548    ///
    547     int heapSize() { return _heap.size(); }
     549    int queueSize() { return _heap.size(); }
    548550   
    549551    ///Executes the algorithm.
     
    697699    const PredMap &predMap() const { return *_pred;}
    698700 
    699     ///Returns a reference to the map of nodes of shortest paths.
    700 
    701     ///Returns a reference to the NodeMap of the last but one nodes of the
    702     ///shortest path tree.
     701//     ///Returns a reference to the map of nodes of shortest paths.
     702
     703//     ///Returns a reference to the NodeMap of the last but one nodes of the
     704//     ///shortest path tree.
     705//     ///\pre \ref run() must be called before using this function.
     706//     const PredNodeMap &predNodeMap() const { return *_predNode;}
     707
     708    ///Checks if a node is reachable from the root.
     709
     710    ///Returns \c true if \c v is reachable from the root.
     711    ///\warning The source nodes are inditated as unreached.
    703712    ///\pre \ref run() must be called before using this function.
    704     const PredNodeMap &predNodeMap() const { return *_predNode;}
    705 
    706     ///Checks if a node is reachable from the root.
    707 
    708     ///Returns \c true if \c v is reachable from the root.
    709     ///\warning If the algorithm is started from multiple nodes,
    710     ///this function may give false result for the source nodes.
    711     ///\pre \ref run() must be called before using this function.
    712     ///
    713     bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
     713    ///
     714    bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
    714715   
    715716    ///@}
    716717  };
    717718
     719
     720
     721
     722 
     723  ///Default traits class of Dijkstra function.
     724
     725  ///Default traits class of Dijkstra function.
     726  ///\param GR Graph type.
     727  ///\param LM Type of length map.
     728  template<class GR, class LM>
     729  struct DijkstraWizardDefaultTraits
     730  {
     731    ///The graph type the algorithm runs on.
     732    typedef GR Graph;
     733    ///The type of the map that stores the edge lengths.
     734
     735    ///The type of the map that stores the edge lengths.
     736    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
     737    typedef LM LengthMap;
     738    //The type of the length of the edges.
     739    typedef typename LM::Value Value;
     740    ///The heap type used by Dijkstra algorithm.
     741
     742    ///The heap type used by Dijkstra algorithm.
     743    ///
     744    ///\sa BinHeap
     745    ///\sa Dijkstra
     746    typedef BinHeap<typename Graph::Node,
     747                    typename LM::Value,
     748                    typename GR::template NodeMap<int>,
     749                    std::less<Value> > Heap;
     750
     751    ///\brief The type of the map that stores the last
     752    ///edges of the shortest paths.
     753    ///
     754    ///The type of the map that stores the last
     755    ///edges of the shortest paths.
     756    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     757    ///
     758    typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
     759    ///Instantiates a PredMap.
     760 
     761    ///This function instantiates a \ref PredMap.
     762    ///\param G is the graph, to which we would like to define the PredMap.
     763    ///\todo The graph alone may be insufficient for the initialization
     764    static PredMap *createPredMap(const GR &G)
     765    {
     766      return new PredMap();
     767    }
     768    ///The type of the map that stores whether a nodes is processed.
     769 
     770    ///The type of the map that stores whether a nodes is processed.
     771    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     772    ///By default it is a NullMap.
     773    ///\todo If it is set to a real map,
     774    ///Dijkstra::processed() should read this.
     775    ///\todo named parameter to set this type, function to read and write.
     776    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
     777    ///Instantiates a ProcessedMap.
     778 
     779    ///This function instantiates a \ref ProcessedMap.
     780    ///\param G is the graph, to which
     781    ///we would like to define the \ref ProcessedMap
     782    static ProcessedMap *createProcessedMap(const GR &G)
     783    {
     784      return new ProcessedMap();
     785    }
     786    ///The type of the map that stores the dists of the nodes.
     787 
     788    ///The type of the map that stores the dists of the nodes.
     789    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     790    ///
     791    typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
     792    ///Instantiates a DistMap.
     793 
     794    ///This function instantiates a \ref DistMap.
     795    ///\param G is the graph, to which we would like to define the \ref DistMap
     796    static DistMap *createDistMap(const GR &G)
     797    {
     798      return new DistMap();
     799    }
     800  };
     801 
    718802  /// Default traits used by \ref DijkstraWizard
    719803
     
    725809  /// \ref DijkstraWizard class.
    726810  template<class GR,class LM>
    727   class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
     811  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
    728812  {
    729813
    730     typedef DijkstraDefaultTraits<GR,LM> Base;
     814    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
    731815  protected:
    732816    /// Type of the nodes in the graph.
     
    739823    ///Pointer to the map of predecessors edges.
    740824    void *_pred;
    741     ///Pointer to the map of predecessors nodes.
    742     void *_predNode;
     825//     ///Pointer to the map of predecessors nodes.
     826//     void *_predNode;
    743827    ///Pointer to the map of distances.
    744828    void *_dist;
     
    751835    /// This constructor does not require parameters, therefore it initiates
    752836    /// all of the attributes to default values (0, INVALID).
    753     DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
    754                        _dist(0), _source(INVALID) {}
     837    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
     838//                         _predNode(0),
     839                           _dist(0), _source(INVALID) {}
    755840
    756841    /// Constructor.
     
    763848    /// \param s is the initial value of  \ref _source
    764849    DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
    765       _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
    766                   _dist(0), _source(s) {}
     850      _g((void *)&g), _length((void *)&l), _pred(0),
     851//       _predNode(0),
     852      _dist(0), _source(s) {}
    767853
    768854  };
     
    770856  /// A class to make easier the usage of Dijkstra algorithm
    771857
    772   /// \ingroup flowalgs
    773858  /// This class is created to make it easier to use Dijkstra algorithm.
    774859  /// It uses the functions and features of the plain \ref Dijkstra,
     
    811896    ///edges of the shortest paths.
    812897    typedef typename TR::PredMap PredMap;
    813     ///\brief The type of the map that stores the last but one
    814     ///nodes of the shortest paths.
    815     typedef typename TR::PredNodeMap PredNodeMap;
     898//     ///\brief The type of the map that stores the last but one
     899//     ///nodes of the shortest paths.
     900//     typedef typename TR::PredNodeMap PredNodeMap;
    816901    ///The type of the map that stores the dists of the nodes.
    817902    typedef typename TR::DistMap DistMap;
     
    845930        Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
    846931      if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
    847       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
     932//       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
    848933      if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
    849934      Dij.run(Base::_source);
     
    881966   
    882967
    883     template<class T>
    884     struct DefPredNodeMapBase : public Base {
    885       typedef T PredNodeMap;
    886       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
    887       DefPredNodeMapBase(const Base &b) : Base(b) {}
    888     };
    889    
    890     ///\brief \ref named-templ-param "Named parameter"
    891     ///function for setting PredNodeMap type
    892     ///
    893     /// \ref named-templ-param "Named parameter"
    894     ///function for setting PredNodeMap type
    895     ///
    896     template<class T>
    897     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
    898     {
    899       Base::_predNode=(void *)&t;
    900       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
    901     }
     968//     template<class T>
     969//     struct DefPredNodeMapBase : public Base {
     970//       typedef T PredNodeMap;
     971//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
     972//       DefPredNodeMapBase(const Base &b) : Base(b) {}
     973//     };
     974   
     975//     ///\brief \ref named-templ-param "Named parameter"
     976//     ///function for setting PredNodeMap type
     977//     ///
     978//     /// \ref named-templ-param "Named parameter"
     979//     ///function for setting PredNodeMap type
     980//     ///
     981//     template<class T>
     982//     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
     983//     {
     984//       Base::_predNode=(void *)&t;
     985//       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
     986//     }
    902987   
    903988    template<class T>
     
    9331018  };
    9341019 
    935   ///\e
     1020  ///Function type interface for Dijkstra algorithm.
    9361021
    9371022  /// \ingroup flowalgs
    938   ///\todo Please document...
     1023  ///Function type interface for Dijkstra algorithm.
    9391024  ///
     1025  ///This function also has several
     1026  ///\ref named-templ-func-param "named parameters",
     1027  ///they are declared as the members of class \ref DijkstraWizard.
     1028  ///The following
     1029  ///example shows how to use these parameters.
     1030  ///\code
     1031  ///  dijkstra(g,length,source).predMap(preds).run();
     1032  ///\endcode
     1033  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1034  ///to the end of the parameter list.
     1035  ///\sa DijkstraWizard
     1036  ///\sa Dijkstra
    9401037  template<class GR, class LM>
    9411038  DijkstraWizard<DijkstraWizardBase<GR,LM> >
     
    9451042  }
    9461043
    947 /// @}
    948  
    9491044} //END OF NAMESPACE LEMON
    9501045
  • src/test/bfs_test.cc

    r1164 r1218  
    4343  BType::DistMap d(G);
    4444  BType::PredMap p(G);
    45   BType::PredNodeMap pn(G);
     45  //  BType::PredNodeMap pn(G);
    4646 
    4747  BType bfs_test(G);
     
    5454  d  = bfs_test.distMap();
    5555  p  = bfs_test.predMap();
    56   pn = bfs_test.predNodeMap();
     56  //  pn = bfs_test.predNodeMap();
    5757  b  = bfs_test.reached(n);
    5858
  • src/test/dfs_test.cc

    r1164 r1218  
    4343  DType::DistMap d(G);
    4444  DType::PredMap p(G);
    45   DType::PredNodeMap pn(G);
     45  //  DType::PredNodeMap pn(G);
    4646 
    4747  DType dfs_test(G);
     
    5454  d  = dfs_test.distMap();
    5555  p  = dfs_test.predMap();
    56   pn = dfs_test.predNodeMap();
     56  //  pn = dfs_test.predNodeMap();
    5757  b  = dfs_test.reached(n);
    5858
  • src/test/dijkstra_test.cc

    r1164 r1218  
    120120 
    121121  {
    122     NullMap<Node,Node> myPredNodeMap;
    123     dijkstra(G,cap).predNodeMap(myPredNodeMap).run(s);
     122    NullMap<Node,Edge> myPredMap;
     123    dijkstra(G,cap).predMap(myPredMap).run(s);
    124124  }
    125125  return 0;
Note: See TracChangeset for help on using the changeset viewer.