COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/dfs.h

    r252 r319  
    2828#include <lemon/core.h>
    2929#include <lemon/error.h>
    30 #include <lemon/assert.h>
    3130#include <lemon/maps.h>
     31#include <lemon/path.h>
    3232
    3333namespace lemon {
    … …  
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \ref PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
     56    ///PredMap.
    5857    static PredMap *createPredMap(const Digraph &g)
    5958    {
    … …  
    6564    ///The type of the map that indicates which nodes are processed.
    6665    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     ///By default it is a NullMap.
    6866    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    69     ///Instantiates a \ref ProcessedMap.
    70 
    71     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7270    ///\param g is the digraph, to which
    73     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7472#ifdef DOXYGEN
    7573    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8684    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8785    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    88     ///Instantiates a \ref ReachedMap.
    89 
    90     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    9189    ///\param g is the digraph, to which
    92     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the ReachedMap.
    9391    static ReachedMap *createReachedMap(const Digraph &g)
    9492    {
    … …  
    10199    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    102100    typedef typename Digraph::template NodeMap<int> DistMap;
    103     ///Instantiates a \ref DistMap.
    104 
    105     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    106104    ///\param g is the digraph, to which we would like to define the
    107     ///\ref DistMap.
     105    ///DistMap.
    108106    static DistMap *createDistMap(const Digraph &g)
    109107    {
    … …  
    117115  ///This class provides an efficient implementation of the %DFS algorithm.
    118116  ///
    119   ///There is also a \ref dfs() "function type interface" for the DFS
     117  ///There is also a \ref dfs() "function-type interface" for the DFS
    120118  ///algorithm, which is convenient in the simplier cases and it can be
    121119  ///used easier.
    … …  
    138136  class Dfs {
    139137  public:
    140     ///\ref Exception for uninitialized parameters.
    141 
    142     ///This error represents problems in the initialization of the
    143     ///parameters of the algorithm.
    144     class UninitializedParameter : public lemon::UninitializedParameter {
    145     public:
    146       virtual const char* what() const throw() {
    147         return "lemon::Dfs::UninitializedParameter";
    148       }
    149     };
    150138
    151139    ///The type of the digraph the algorithm runs on.
    … …  
    196184    int _stack_head;
    197185
    198     ///Creates the maps if necessary.
    199     ///\todo Better memory allocation (instead of new).
     186    //Creates the maps if necessary.
    200187    void create_maps()
    201188    {
    … …  
    231218
    232219    template <class T>
    233     struct DefPredMapTraits : public Traits {
     220    struct SetPredMapTraits : public Traits {
    234221      typedef T PredMap;
    235222      static PredMap *createPredMap(const Digraph &)
    236223      {
    237         throw UninitializedParameter();
     224        LEMON_ASSERT(false, "PredMap is not initialized");
     225        return 0; // ignore warnings
    238226      }
    239227    };
    240228    ///\brief \ref named-templ-param "Named parameter" for setting
    241     ///\ref PredMap type.
     229    ///PredMap type.
    242230    ///
    243231    ///\ref named-templ-param "Named parameter" for setting
    244     ///\ref PredMap type.
     232    ///PredMap type.
    245233    template <class T>
    246     struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
    247       typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
     234    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     235      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
    248236    };
    249237
    250238    template <class T>
    251     struct DefDistMapTraits : public Traits {
     239    struct SetDistMapTraits : public Traits {
    252240      typedef T DistMap;
    253241      static DistMap *createDistMap(const Digraph &)
    254242      {
    255         throw UninitializedParameter();
     243        LEMON_ASSERT(false, "DistMap is not initialized");
     244        return 0; // ignore warnings
    256245      }
    257246    };
    258247    ///\brief \ref named-templ-param "Named parameter" for setting
    259     ///\ref DistMap type.
     248    ///DistMap type.
    260249    ///
    261250    ///\ref named-templ-param "Named parameter" for setting
    262     ///\ref DistMap type.
     251    ///DistMap type.
    263252    template <class T>
    264     struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
    265       typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
     253    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     254      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
    266255    };
    267256
    268257    template <class T>
    269     struct DefReachedMapTraits : public Traits {
     258    struct SetReachedMapTraits : public Traits {
    270259      typedef T ReachedMap;
    271260      static ReachedMap *createReachedMap(const Digraph &)
    272261      {
    273         throw UninitializedParameter();
     262        LEMON_ASSERT(false, "ReachedMap is not initialized");
     263        return 0; // ignore warnings
    274264      }
    275265    };
    276266    ///\brief \ref named-templ-param "Named parameter" for setting
    277     ///\ref ReachedMap type.
     267    ///ReachedMap type.
    278268    ///
    279269    ///\ref named-templ-param "Named parameter" for setting
    280     ///\ref ReachedMap type.
     270    ///ReachedMap type.
    281271    template <class T>
    282     struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
    283       typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
     272    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     273      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
    284274    };
    285275
    286276    template <class T>
    287     struct DefProcessedMapTraits : public Traits {
     277    struct SetProcessedMapTraits : public Traits {
    288278      typedef T ProcessedMap;
    289279      static ProcessedMap *createProcessedMap(const Digraph &)
    290280      {
    291         throw UninitializedParameter();
     281        LEMON_ASSERT(false, "ProcessedMap is not initialized");
     282        return 0; // ignore warnings
    292283      }
    293284    };
    294285    ///\brief \ref named-templ-param "Named parameter" for setting
    295     ///\ref ProcessedMap type.
     286    ///ProcessedMap type.
    296287    ///
    297288    ///\ref named-templ-param "Named parameter" for setting
    298     ///\ref ProcessedMap type.
     289    ///ProcessedMap type.
    299290    template <class T>
    300     struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
    301       typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
    302     };
    303 
    304     struct DefDigraphProcessedMapTraits : public Traits {
     291    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     292      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
     293    };
     294
     295    struct SetStandardProcessedMapTraits : public Traits {
    305296      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    306297      static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    310301    };
    311302    ///\brief \ref named-templ-param "Named parameter" for setting
    312     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    313304    ///
    314305    ///\ref named-templ-param "Named parameter" for setting
    315     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    316307    ///If you don't set it explicitly, it will be automatically allocated.
    317     template <class T>
    318     struct DefProcessedMapToBeDefaultMap :
    319       public Dfs< Digraph, DefDigraphProcessedMapTraits> {
    320       typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
     308    struct SetStandardProcessedMap :
     309      public Dfs< Digraph, SetStandardProcessedMapTraits > {
     310      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
    321311    };
    322312
    … …  
    559549    ///
    560550    ///This method runs the %DFS algorithm from the root node
    561     ///in order to compute the DFS path to \c dest.
     551    ///in order to compute the DFS path to \c t.
    562552    ///
    563553    ///The algorithm computes
    564     ///- the %DFS path to \c dest,
    565     ///- the distance of \c dest from the root in the %DFS tree.
     554    ///- the %DFS path to \c t,
     555    ///- the distance of \c t from the root in the %DFS tree.
    566556    ///
    567557    ///\pre init() must be called and a root node should be
    568558    ///added with addSource() before using this function.
    569     void start(Node dest)
    570     {
    571       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     559    void start(Node t)
     560    {
     561      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
    572562        processNextArc();
    573563    }
    … …  
    599589    }
    600590
    601     ///Runs the algorithm from the given node.
     591    ///Runs the algorithm from the given source node.
    602592
    603593    ///This method runs the %DFS algorithm from node \c s
    … …  
    623613
    624614    ///This method runs the %DFS algorithm from node \c s
    625     ///in order to compute the DFS path to \c t.
    626     ///
    627     ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    628     ///if \c t is reachable form \c s, \c 0 otherwise.
     615    ///in order to compute the DFS path to node \c t
     616    ///(it stops searching when \c t is processed)
     617    ///
     618    ///\return \c true if \c t is reachable form \c s.
    629619    ///
    630620    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
    … …  
    635625    ///  d.start(t);
    636626    ///\endcode
    637     int run(Node s,Node t) {
     627    bool run(Node s,Node t) {
    638628      init();
    639629      addSource(s);
    640630      start(t);
    641       return reached(t)?_stack_head+1:0;
     631      return reached(t);
    642632    }
    643633
    … …  
    777767    ///arcs of the %DFS paths.
    778768    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    779     ///
    780     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
    781     ///Instantiates a \ref PredMap.
    782 
    783     ///This function instantiates a \ref PredMap.
     769    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     770    ///Instantiates a PredMap.
     771
     772    ///This function instantiates a PredMap.
    784773    ///\param g is the digraph, to which we would like to define the
    785     ///\ref PredMap.
    786     ///\todo The digraph alone may be insufficient to initialize
    787 #ifdef DOXYGEN
     774    ///PredMap.
    788775    static PredMap *createPredMap(const Digraph &g)
    789 #else
    790     static PredMap *createPredMap(const Digraph &)
    791 #endif
    792     {
    793       return new PredMap();
     776    {
     777      return new PredMap(g);
    794778    }
    795779
    … …  
    798782    ///The type of the map that indicates which nodes are processed.
    799783    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     784    ///By default it is a NullMap.
    800785    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    801     ///Instantiates a \ref ProcessedMap.
    802 
    803     ///This function instantiates a \ref ProcessedMap.
     786    ///Instantiates a ProcessedMap.
     787
     788    ///This function instantiates a ProcessedMap.
    804789    ///\param g is the digraph, to which
    805     ///we would like to define the \ref ProcessedMap.
     790    ///we would like to define the ProcessedMap.
    806791#ifdef DOXYGEN
    807792    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    818803    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    819804    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    820     ///Instantiates a \ref ReachedMap.
    821 
    822     ///This function instantiates a \ref ReachedMap.
     805    ///Instantiates a ReachedMap.
     806
     807    ///This function instantiates a ReachedMap.
    823808    ///\param g is the digraph, to which
    824     ///we would like to define the \ref ReachedMap.
     809    ///we would like to define the ReachedMap.
    825810    static ReachedMap *createReachedMap(const Digraph &g)
    826811    {
    … …  
    832817    ///The type of the map that stores the distances of the nodes.
    833818    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    834     ///
    835     typedef NullMap<typename Digraph::Node,int> DistMap;
    836     ///Instantiates a \ref DistMap.
    837 
    838     ///This function instantiates a \ref DistMap.
     819    typedef typename Digraph::template NodeMap<int> DistMap;
     820    ///Instantiates a DistMap.
     821
     822    ///This function instantiates a DistMap.
    839823    ///\param g is the digraph, to which we would like to define
    840     ///the \ref DistMap
    841 #ifdef DOXYGEN
     824    ///the DistMap
    842825    static DistMap *createDistMap(const Digraph &g)
    843 #else
    844     static DistMap *createDistMap(const Digraph &)
    845 #endif
    846     {
    847       return new DistMap();
    848     }
     826    {
     827      return new DistMap(g);
     828    }
     829
     830    ///The type of the DFS paths.
     831
     832    ///The type of the DFS paths.
     833    ///It must meet the \ref concepts::Path "Path" concept.
     834    typedef lemon::Path<Digraph> Path;
    849835  };
    850836
    851   /// Default traits class used by \ref DfsWizard
     837  /// Default traits class used by DfsWizard
    852838
    853839  /// To make it easier to use Dfs algorithm
    … …  
    876862    //Pointer to the map of distances.
    877863    void *_dist;
    878     //Pointer to the source node.
    879     Node _source;
     864    //Pointer to the DFS path to the target node.
     865    void *_path;
     866    //Pointer to the distance of the target node.
     867    int *_di;
    880868
    881869    public:
    … …  
    883871
    884872    /// This constructor does not require parameters, therefore it initiates
    885     /// all of the attributes to default values (0, INVALID).
     873    /// all of the attributes to \c 0.
    886874    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    887                       _dist(0), _source(INVALID) {}
     875                      _dist(0), _path(0), _di(0) {}
    888876
    889877    /// Constructor.
    890878
    891     /// This constructor requires some parameters,
    892     /// listed in the parameters list.
    893     /// Others are initiated to 0.
     879    /// This constructor requires one parameter,
     880    /// others are initiated to \c 0.
    894881    /// \param g The digraph the algorithm runs on.
    895     /// \param s The source node.
    896     DfsWizardBase(const GR &g, Node s=INVALID) :
     882    DfsWizardBase(const GR &g) :
    897883      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    898       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     884      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    899885
    900886  };
    901887
    902   /// Auxiliary class for the function type interface of DFS algorithm.
    903 
    904   /// This auxiliary class is created to implement the function type
    905   /// interface of \ref Dfs algorithm. It uses the functions and features
    906   /// of the plain \ref Dfs, but it is much simpler to use it.
    907   /// It should only be used through the \ref dfs() function, which makes
    908   /// it easier to use the algorithm.
     888  /// Auxiliary class for the function-type interface of DFS algorithm.
     889
     890  /// This auxiliary class is created to implement the
     891  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
     892  /// It does not have own \ref run() method, it uses the functions
     893  /// and features of the plain \ref Dfs.
    909894  ///
    910   /// Simplicity means that the way to change the types defined
    911   /// in the traits class is based on functions that returns the new class
    912   /// and not on templatable built-in classes.
    913   /// When using the plain \ref Dfs
    914   /// the new class with the modified type comes from
    915   /// the original class by using the ::
    916   /// operator. In the case of \ref DfsWizard only
    917   /// a function have to be called, and it will
    918   /// return the needed class.
    919   ///
    920   /// It does not have own \ref run() method. When its \ref run() method
    921   /// is called, it initiates a plain \ref Dfs object, and calls the
    922   /// \ref Dfs::run() method of it.
     895  /// This class should only be used through the \ref dfs() function,
     896  /// which makes it easier to use the algorithm.
    923897  template<class TR>
    924898  class DfsWizard : public TR
    … …  
    935909
    936910    ///\brief The type of the map that stores the predecessor
    937     ///arcs of the shortest paths.
     911    ///arcs of the DFS paths.
    938912    typedef typename TR::PredMap PredMap;
    939913    ///\brief The type of the map that stores the distances of the nodes.
    … …  
    943917    ///\brief The type of the map that indicates which nodes are processed.
    944918    typedef typename TR::ProcessedMap ProcessedMap;
     919    ///The type of the DFS paths
     920    typedef typename TR::Path Path;
    945921
    946922  public:
    … …  
    953929    /// Constructor that requires parameters.
    954930    /// These parameters will be the default values for the traits class.
    955     DfsWizard(const Digraph &g, Node s=INVALID) :
    956       TR(g,s) {}
     931    /// \param g The digraph the algorithm runs on.
     932    DfsWizard(const Digraph &g) :
     933      TR(g) {}
    957934
    958935    ///Copy constructor
    … …  
    961938    ~DfsWizard() {}
    962939
    963     ///Runs DFS algorithm from a source node.
    964 
    965     ///Runs DFS algorithm from a source node.
    966     ///The node can be given with the \ref source() function.
     940    ///Runs DFS algorithm from the given source node.
     941
     942    ///This method runs DFS algorithm from node \c s
     943    ///in order to compute the DFS path to each node.
     944    void run(Node s)
     945    {
     946      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     947      if (Base::_pred)
     948        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     949      if (Base::_dist)
     950        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     951      if (Base::_reached)
     952        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     953      if (Base::_processed)
     954        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     955      if (s!=INVALID)
     956        alg.run(s);
     957      else
     958        alg.run();
     959    }
     960
     961    ///Finds the DFS path between \c s and \c t.
     962
     963    ///This method runs DFS algorithm from node \c s
     964    ///in order to compute the DFS path to node \c t
     965    ///(it stops searching when \c t is processed).
     966    ///
     967    ///\return \c true if \c t is reachable form \c s.
     968    bool run(Node s, Node t)
     969    {
     970      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     971      if (Base::_pred)
     972        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     973      if (Base::_dist)
     974        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     975      if (Base::_reached)
     976        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     977      if (Base::_processed)
     978        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     979      alg.run(s,t);
     980      if (Base::_path)
     981        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     982      if (Base::_di)
     983        *Base::_di = alg.dist(t);
     984      return alg.reached(t);
     985      }
     986
     987    ///Runs DFS algorithm to visit all nodes in the digraph.
     988
     989    ///This method runs DFS algorithm in order to compute
     990    ///the DFS path to each node.
    967991    void run()
    968992    {
    969       if(Base::_source==INVALID) throw UninitializedParameter();
    970       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    971       if(Base::_reached)
    972         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    973       if(Base::_processed)
    974         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    975       if(Base::_pred)
    976         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    977       if(Base::_dist)
    978         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    979       alg.run(Base::_source);
    980     }
    981 
    982     ///Runs DFS algorithm from the given node.
    983 
    984     ///Runs DFS algorithm from the given node.
    985     ///\param s is the given source.
    986     void run(Node s)
    987     {
    988       Base::_source=s;
    989       run();
    990     }
    991 
    992     /// Sets the source node, from which the Dfs algorithm runs.
    993 
    994     /// Sets the source node, from which the Dfs algorithm runs.
    995     /// \param s is the source node.
    996     DfsWizard<TR> &source(Node s)
    997     {
    998       Base::_source=s;
    999       return *this;
     993      run(INVALID);
    1000994    }
    1001995
    1002996    template<class T>
    1003     struct DefPredMapBase : public Base {
     997    struct SetPredMapBase : public Base {
    1004998      typedef T PredMap;
    1005999      static PredMap *createPredMap(const Digraph &) { return 0; };
    1006       DefPredMapBase(const TR &b) : TR(b) {}
    1007     };
    1008     ///\brief \ref named-templ-param "Named parameter"
    1009     ///for setting \ref PredMap object.
    1010     ///
    1011     ///\ref named-templ-param "Named parameter"
    1012     ///for setting \ref PredMap object.
     1000      SetPredMapBase(const TR &b) : TR(b) {}
     1001    };
     1002    ///\brief \ref named-func-param "Named parameter"
     1003    ///for setting PredMap object.
     1004    ///
     1005    ///\ref named-func-param "Named parameter"
     1006    ///for setting PredMap object.
    10131007    template<class T>
    1014     DfsWizard<DefPredMapBase<T> > predMap(const T &t)
     1008    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
    10151009    {
    10161010      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    1017       return DfsWizard<DefPredMapBase<T> >(*this);
     1011      return DfsWizard<SetPredMapBase<T> >(*this);
    10181012    }
    10191013
    10201014    template<class T>
    1021     struct DefReachedMapBase : public Base {
     1015    struct SetReachedMapBase : public Base {
    10221016      typedef T ReachedMap;
    10231017      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
    1024       DefReachedMapBase(const TR &b) : TR(b) {}
    1025     };
    1026     ///\brief \ref named-templ-param "Named parameter"
    1027     ///for setting \ref ReachedMap object.
    1028     ///
    1029     /// \ref named-templ-param "Named parameter"
    1030     ///for setting \ref ReachedMap object.
     1018      SetReachedMapBase(const TR &b) : TR(b) {}
     1019    };
     1020    ///\brief \ref named-func-param "Named parameter"
     1021    ///for setting ReachedMap object.
     1022    ///
     1023    /// \ref named-func-param "Named parameter"
     1024    ///for setting ReachedMap object.
    10311025    template<class T>
    1032     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1026    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    10331027    {
    10341028      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    1035       return DfsWizard<DefReachedMapBase<T> >(*this);
     1029      return DfsWizard<SetReachedMapBase<T> >(*this);
    10361030    }
    10371031
    10381032    template<class T>
    1039     struct DefProcessedMapBase : public Base {
     1033    struct SetDistMapBase : public Base {
     1034      typedef T DistMap;
     1035      static DistMap *createDistMap(const Digraph &) { return 0; };
     1036      SetDistMapBase(const TR &b) : TR(b) {}
     1037    };
     1038    ///\brief \ref named-func-param "Named parameter"
     1039    ///for setting DistMap object.
     1040    ///
     1041    /// \ref named-func-param "Named parameter"
     1042    ///for setting DistMap object.
     1043    template<class T>
     1044    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1045    {
     1046      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1047      return DfsWizard<SetDistMapBase<T> >(*this);
     1048    }
     1049
     1050    template<class T>
     1051    struct SetProcessedMapBase : public Base {
    10401052      typedef T ProcessedMap;
    10411053      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
    1042       DefProcessedMapBase(const TR &b) : TR(b) {}
    1043     };
    1044     ///\brief \ref named-templ-param "Named parameter"
    1045     ///for setting \ref ProcessedMap object.
    1046     ///
    1047     /// \ref named-templ-param "Named parameter"
    1048     ///for setting \ref ProcessedMap object.
     1054      SetProcessedMapBase(const TR &b) : TR(b) {}
     1055    };
     1056    ///\brief \ref named-func-param "Named parameter"
     1057    ///for setting ProcessedMap object.
     1058    ///
     1059    /// \ref named-func-param "Named parameter"
     1060    ///for setting ProcessedMap object.
    10491061    template<class T>
    1050     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1062    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    10511063    {
    10521064      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    1053       return DfsWizard<DefProcessedMapBase<T> >(*this);
     1065      return DfsWizard<SetProcessedMapBase<T> >(*this);
    10541066    }
    10551067
    10561068    template<class T>
    1057     struct DefDistMapBase : public Base {
    1058       typedef T DistMap;
    1059       static DistMap *createDistMap(const Digraph &) { return 0; };
    1060       DefDistMapBase(const TR &b) : TR(b) {}
    1061     };
    1062     ///\brief \ref named-templ-param "Named parameter"
    1063     ///for setting \ref DistMap object.
    1064     ///
    1065     ///\ref named-templ-param "Named parameter"
    1066     ///for setting \ref DistMap object.
     1069    struct SetPathBase : public Base {
     1070      typedef T Path;
     1071      SetPathBase(const TR &b) : TR(b) {}
     1072    };
     1073    ///\brief \ref named-func-param "Named parameter"
     1074    ///for getting the DFS path to the target node.
     1075    ///
     1076    ///\ref named-func-param "Named parameter"
     1077    ///for getting the DFS path to the target node.
    10671078    template<class T>
    1068     DfsWizard<DefDistMapBase<T> > distMap(const T &t)
    1069     {
    1070       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1071       return DfsWizard<DefDistMapBase<T> >(*this);
     1079    DfsWizard<SetPathBase<T> > path(const T &t)
     1080    {
     1081      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1082      return DfsWizard<SetPathBase<T> >(*this);
     1083    }
     1084
     1085    ///\brief \ref named-func-param "Named parameter"
     1086    ///for getting the distance of the target node.
     1087    ///
     1088    ///\ref named-func-param "Named parameter"
     1089    ///for getting the distance of the target node.
     1090    DfsWizard dist(const int &d)
     1091    {
     1092      Base::_di=const_cast<int*>(&d);
     1093      return *this;
    10721094    }
    10731095
    10741096  };
    10751097
    1076   ///Function type interface for Dfs algorithm.
     1098  ///Function-type interface for DFS algorithm.
    10771099
    10781100  ///\ingroup search
    1079   ///Function type interface for Dfs algorithm.
     1101  ///Function-type interface for DFS algorithm.
    10801102  ///
    1081   ///This function also has several
    1082   ///\ref named-templ-func-param "named parameters",
     1103  ///This function also has several \ref named-func-param "named parameters",
    10831104  ///they are declared as the members of class \ref DfsWizard.
    1084   ///The following
    1085   ///example shows how to use these parameters.
     1105  ///The following examples show how to use these parameters.
    10861106  ///\code
    1087   ///  dfs(g,source).predMap(preds).run();
     1107  ///  // Compute the DFS tree
     1108  ///  dfs(g).predMap(preds).distMap(dists).run(s);
     1109  ///
     1110  ///  // Compute the DFS path from s to t
     1111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    10881112  ///\endcode
     1113
    10891114  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
    10901115  ///to the end of the parameter list.
    … …  
    10931118  template<class GR>
    10941119  DfsWizard<DfsWizardBase<GR> >
    1095   dfs(const GR &g,typename GR::Node s=INVALID)
     1120  dfs(const GR &digraph)
    10961121  {
    1097     return DfsWizard<DfsWizardBase<GR> >(g,s);
     1122    return DfsWizard<DfsWizardBase<GR> >(digraph);
    10981123  }
    10991124
    … …  
    11881213    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    11891214
    1190     /// \brief Instantiates a \ref ReachedMap.
    1191     ///
    1192     /// This function instantiates a \ref ReachedMap.
     1215    /// \brief Instantiates a ReachedMap.
     1216    ///
     1217    /// This function instantiates a ReachedMap.
    11931218    /// \param digraph is the digraph, to which
    1194     /// we would like to define the \ref ReachedMap.
     1219    /// we would like to define the ReachedMap.
    11951220    static ReachedMap *createReachedMap(const Digraph &digraph) {
    11961221      return new ReachedMap(digraph);
    … …  
    12331258  template <typename _Digraph = ListDigraph,
    12341259            typename _Visitor = DfsVisitor<_Digraph>,
    1235             typename _Traits = DfsDefaultTraits<_Digraph> >
     1260            typename _Traits = DfsVisitDefaultTraits<_Digraph> >
    12361261#endif
    12371262  class DfsVisit {
    12381263  public:
    1239 
    1240     /// \brief \ref Exception for uninitialized parameters.
    1241     ///
    1242     /// This error represents problems in the initialization
    1243     /// of the parameters of the algorithm.
    1244     class UninitializedParameter : public lemon::UninitializedParameter {
    1245     public:
    1246       virtual const char* what() const throw()
    1247       {
    1248         return "lemon::DfsVisit::UninitializedParameter";
    1249       }
    1250     };
    12511264
    12521265    ///The traits class.
    … …  
    12811294    int _stack_head;
    12821295
    1283     ///Creates the maps if necessary.
    1284     ///\todo Better memory allocation (instead of new).
     1296    //Creates the maps if necessary.
    12851297    void create_maps() {
    12861298      if(!_reached) {
    … …  
    13021314    ///@{
    13031315    template <class T>
    1304     struct DefReachedMapTraits : public Traits {
     1316    struct SetReachedMapTraits : public Traits {
    13051317      typedef T ReachedMap;
    13061318      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1307         throw UninitializedParameter();
     1319        LEMON_ASSERT(false, "ReachedMap is not initialized");
     1320        return 0; // ignore warnings
    13081321      }
    13091322    };
    … …  
    13131326    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    13141327    template <class T>
    1315     struct DefReachedMap : public DfsVisit< Digraph, Visitor,
    1316                                             DefReachedMapTraits<T> > {
    1317       typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
     1328    struct SetReachedMap : public DfsVisit< Digraph, Visitor,
     1329                                            SetReachedMapTraits<T> > {
     1330      typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
    13181331    };
    13191332    ///@}
    … …  
    14901503    ///
    14911504    /// This method runs the %DFS algorithm from the root node
    1492     /// in order to compute the DFS path to \c dest.
     1505    /// in order to compute the DFS path to \c t.
    14931506    ///
    14941507    /// The algorithm computes
    1495     /// - the %DFS path to \c dest,
    1496     /// - the distance of \c dest from the root in the %DFS tree.
     1508    /// - the %DFS path to \c t,
     1509    /// - the distance of \c t from the root in the %DFS tree.
    14971510    ///
    14981511    /// \pre init() must be called and a root node should be added
    14991512    /// with addSource() before using this function.
    1500     void start(Node dest) {
    1501       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
     1513    void start(Node t) {
     1514      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
    15021515        processNextArc();
    15031516    }
    … …  
    15281541    }
    15291542
    1530     /// \brief Runs the algorithm from the given node.
     1543    /// \brief Runs the algorithm from the given source node.
    15311544    ///
    15321545    /// This method runs the %DFS algorithm from node \c s.
    … …  
    15521565
    15531566    /// This method runs the %DFS algorithm from node \c s
    1554     /// in order to compute the DFS path to \c t.
    1555     ///
    1556     /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    1557     /// if \c t is reachable form \c s, \c 0 otherwise.
     1567    /// in order to compute the DFS path to node \c t
     1568    /// (it stops searching when \c t is processed).
     1569    ///
     1570    /// \return \c true if \c t is reachable form \c s.
    15581571    ///
    15591572    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
    … …  
    15641577    ///   d.start(t);
    15651578    ///\endcode
    1566     int run(Node s,Node t) {
     1579    bool run(Node s,Node t) {
    15671580      init();
    15681581      addSource(s);
    15691582      start(t);
    1570       return reached(t)?_stack_head+1:0;
     1583      return reached(t);
    15711584    }
    15721585
Note: See TracChangeset for help on using the changeset viewer.