COIN-OR::LEMON - Graph Library

Changeset 907:1937b6455b7d in lemon-main


Ignore:
Timestamp:
09/22/10 09:38:23 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
908:10242c611190, 913:5087694945e4, 916:70bee017b584
Parents:
905:de428ebb47ab (diff), 906:e24922c56bc2 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #392

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/dfs.h

    r877 r907  
    566566    void start(Node t)
    567567    {
    568       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     568      while ( !emptyQueue() && !(*_reached)[t] )
    569569        processNextArc();
    570570    }
     
    15131513    /// with addSource() before using this function.
    15141514    void start(Node t) {
    1515       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1515      while ( !emptyQueue() && !(*_reached)[t] )
    15161516        processNextArc();
    15171517    }
  • lemon/dfs.h

    r906 r907  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     68    ///Instantiates a \c ProcessedMap.
     69
     70    ///This function instantiates a \ref ProcessedMap.
    7071    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     72    ///we would like to define the \ref ProcessedMap.
    7273#ifdef DOXYGEN
    7374    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     88    ///Instantiates a \c ReachedMap.
     89
     90    ///This function instantiates a \ref ReachedMap.
    8991    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     92    ///we would like to define the \ref ReachedMap.
    9193    static ReachedMap *createReachedMap(const Digraph &g)
    9294    {
     
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     103    ///Instantiates a \c DistMap.
     104
     105    ///This function instantiates a \ref DistMap.
    104106    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     107    ///\ref DistMap.
    106108    static DistMap *createDistMap(const Digraph &g)
    107109    {
     
    120122  ///
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    127   ///See \ref DfsDefaultTraits for the documentation of
    128   ///a Dfs traits class.
     124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref DfsDefaultTraits
     127  ///"DfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    129130#ifdef DOXYGEN
    130131  template <typename GR,
     
    152153    typedef PredMapPath<Digraph, PredMap> Path;
    153154
    154     ///The traits class.
     155    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155156    typedef TR Traits;
    156157
     
    213214    typedef Dfs Create;
    214215
    215     ///\name Named template parameters
     216    ///\name Named Template Parameters
    216217
    217218    ///@{
     
    227228    };
    228229    ///\brief \ref named-templ-param "Named parameter" for setting
    229     ///PredMap type.
     230    ///\c PredMap type.
    230231    ///
    231232    ///\ref named-templ-param "Named parameter" for setting
    232     ///PredMap type.
     233    ///\c PredMap type.
     234    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    233235    template <class T>
    234236    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    246248    };
    247249    ///\brief \ref named-templ-param "Named parameter" for setting
    248     ///DistMap type.
     250    ///\c DistMap type.
    249251    ///
    250252    ///\ref named-templ-param "Named parameter" for setting
    251     ///DistMap type.
     253    ///\c DistMap type.
     254    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    252255    template <class T>
    253256    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265268    };
    266269    ///\brief \ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
     270    ///\c ReachedMap type.
    268271    ///
    269272    ///\ref named-templ-param "Named parameter" for setting
    270     ///ReachedMap type.
     273    ///\c ReachedMap type.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271276    template <class T>
    272277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    284289    };
    285290    ///\brief \ref named-templ-param "Named parameter" for setting
    286     ///ProcessedMap type.
     291    ///\c ProcessedMap type.
    287292    ///
    288293    ///\ref named-templ-param "Named parameter" for setting
    289     ///ProcessedMap type.
     294    ///\c ProcessedMap type.
     295    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    290296    template <class T>
    291297    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    301307    };
    302308    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     309    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304310    ///
    305311    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     312    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307313    ///If you don't set it explicitly, it will be automatically allocated.
    308314    struct SetStandardProcessedMap :
     
    339345
    340346    ///Sets the map that stores the predecessor arcs.
    341     ///If you don't use this function before calling \ref run(),
    342     ///it will allocate one. The destructor deallocates this
    343     ///automatically allocated map, of course.
     347    ///If you don't use this function before calling \ref run(Node) "run()"
     348    ///or \ref init(), an instance will be allocated automatically.
     349    ///The destructor deallocates this automatically allocated map,
     350    ///of course.
    344351    ///\return <tt> (*this) </tt>
    345352    Dfs &predMap(PredMap &m)
     
    356363
    357364    ///Sets the map that indicates which nodes are reached.
    358     ///If you don't use this function before calling \ref run(),
    359     ///it will allocate one. The destructor deallocates this
    360     ///automatically allocated map, of course.
     365    ///If you don't use this function before calling \ref run(Node) "run()"
     366    ///or \ref init(), an instance will be allocated automatically.
     367    ///The destructor deallocates this automatically allocated map,
     368    ///of course.
    361369    ///\return <tt> (*this) </tt>
    362370    Dfs &reachedMap(ReachedMap &m)
     
    373381
    374382    ///Sets the map that indicates which nodes are processed.
    375     ///If you don't use this function before calling \ref run(),
    376     ///it will allocate one. The destructor deallocates this
    377     ///automatically allocated map, of course.
     383    ///If you don't use this function before calling \ref run(Node) "run()"
     384    ///or \ref init(), an instance will be allocated automatically.
     385    ///The destructor deallocates this automatically allocated map,
     386    ///of course.
    378387    ///\return <tt> (*this) </tt>
    379388    Dfs &processedMap(ProcessedMap &m)
     
    391400    ///Sets the map that stores the distances of the nodes calculated by
    392401    ///the algorithm.
    393     ///If you don't use this function before calling \ref run(),
    394     ///it will allocate one. The destructor deallocates this
    395     ///automatically allocated map, of course.
     402    ///If you don't use this function before calling \ref run(Node) "run()"
     403    ///or \ref init(), an instance will be allocated automatically.
     404    ///The destructor deallocates this automatically allocated map,
     405    ///of course.
    396406    ///\return <tt> (*this) </tt>
    397407    Dfs &distMap(DistMap &m)
     
    407417  public:
    408418
    409     ///\name Execution control
    410     ///The simplest way to execute the algorithm is to use
    411     ///one of the member functions called \ref lemon::Dfs::run() "run()".
    412     ///\n
    413     ///If you need more control on the execution, first you must call
    414     ///\ref lemon::Dfs::init() "init()", then you can add a source node
    415     ///with \ref lemon::Dfs::addSource() "addSource()".
    416     ///Finally \ref lemon::Dfs::start() "start()" will perform the
    417     ///actual path computation.
     419    ///\name Execution Control
     420    ///The simplest way to execute the DFS algorithm is to use one of the
     421    ///member functions called \ref run(Node) "run()".\n
     422    ///If you need better control on the execution, you have to call
     423    ///\ref init() first, then you can add a source node with \ref addSource()
     424    ///and perform the actual computation with \ref start().
     425    ///This procedure can be repeated if there are nodes that have not
     426    ///been reached.
    418427
    419428    ///@{
    420429
     430    ///\brief Initializes the internal data structures.
     431    ///
    421432    ///Initializes the internal data structures.
    422 
    423     ///Initializes the internal data structures.
    424     ///
    425433    void init()
    426434    {
     
    439447    ///Adds a new source node to the set of nodes to be processed.
    440448    ///
    441     ///\pre The stack must be empty. (Otherwise the algorithm gives
    442     ///false results.)
    443     ///
    444     ///\warning Distances will be wrong (or at least strange) in case of
    445     ///multiple sources.
     449    ///\pre The stack must be empty. Otherwise the algorithm gives
     450    ///wrong results. (One of the outgoing arcs of all the source nodes
     451    ///except for the last one will not be visited and distances will
     452    ///also be wrong.)
    446453    void addSource(Node s)
    447454    {
     
    507514    }
    508515
    509     ///\brief Returns \c false if there are nodes
    510     ///to be processed.
    511     ///
    512     ///Returns \c false if there are nodes
    513     ///to be processed in the queue (stack).
     516    ///Returns \c false if there are nodes to be processed.
     517
     518    ///Returns \c false if there are nodes to be processed
     519    ///in the queue (stack).
    514520    bool emptyQueue() const { return _stack_head<0; }
    515521
    516522    ///Returns the number of the nodes to be processed.
    517523
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     524    ///Returns the number of the nodes to be processed
     525    ///in the queue (stack).
    519526    int queueSize() const { return _stack_head+1; }
    520527
     
    634641    ///Runs the algorithm to visit all nodes in the digraph.
    635642
    636     ///This method runs the %DFS algorithm in order to compute the
    637     ///%DFS path to each node.
    638     ///
    639     ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     643    ///This method runs the %DFS algorithm in order to visit all nodes
     644    ///in the digraph.
    642645    ///
    643646    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664667
    665668    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     669    ///The results of the DFS algorithm can be obtained using these
    667670    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     671    ///Either \ref run(Node) "run()" or \ref start() should be called
     672    ///before using them.
    670673
    671674    ///@{
    672675
    673     ///The DFS path to a node.
    674 
    675     ///Returns the DFS path to a node.
    676     ///
    677     ///\warning \c t should be reachable from the root.
    678     ///
    679     ///\pre Either \ref run() or \ref start() must be called before
    680     ///using this function.
     676    ///The DFS path to the given node.
     677
     678    ///Returns the DFS path to the given node from the root(s).
     679    ///
     680    ///\warning \c t should be reached from the root(s).
     681    ///
     682    ///\pre Either \ref run(Node) "run()" or \ref init()
     683    ///must be called before using this function.
    681684    Path path(Node t) const { return Path(*G, *_pred, t); }
    682685
    683     ///The distance of a node from the root.
    684 
    685     ///Returns the distance of a node from the root.
    686     ///
    687     ///\warning If node \c v is not reachable from the root, then
     686    ///The distance of the given node from the root(s).
     687
     688    ///Returns the distance of the given node from the root(s).
     689    ///
     690    ///\warning If node \c v is not reached from the root(s), then
    688691    ///the return value of this function is undefined.
    689692    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     693    ///\pre Either \ref run(Node) "run()" or \ref init()
     694    ///must be called before using this function.
    692695    int dist(Node v) const { return (*_dist)[v]; }
    693696
    694     ///Returns the 'previous arc' of the %DFS tree for a node.
     697    ///Returns the 'previous arc' of the %DFS tree for the given node.
    695698
    696699    ///This function returns the 'previous arc' of the %DFS tree for the
    697     ///node \c v, i.e. it returns the last arc of a %DFS path from the
    698     ///root to \c v. It is \c INVALID
    699     ///if \c v is not reachable from the root(s) or if \c v is a root.
     700    ///node \c v, i.e. it returns the last arc of a %DFS path from a
     701    ///root to \c v. It is \c INVALID if \c v is not reached from the
     702    ///root(s) or if \c v is a root.
    700703    ///
    701704    ///The %DFS tree used here is equal to the %DFS tree used in
    702     ///\ref predNode().
    703     ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     705    ///\ref predNode() and \ref predMap().
     706    ///
     707    ///\pre Either \ref run(Node) "run()" or \ref init()
     708    ///must be called before using this function.
    706709    Arc predArc(Node v) const { return (*_pred)[v];}
    707710
    708     ///Returns the 'previous node' of the %DFS tree.
     711    ///Returns the 'previous node' of the %DFS tree for the given node.
    709712
    710713    ///This function returns the 'previous node' of the %DFS
    711714    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///from a %DFS path from the root to \c v. It is \c INVALID
    713     ///if \c v is not reachable from the root(s) or if \c v is a root.
     715    ///of a %DFS path from a root to \c v. It is \c INVALID
     716    ///if \c v is not reached from the root(s) or if \c v is a root.
    714717    ///
    715718    ///The %DFS tree used here is equal to the %DFS tree used in
    716     ///\ref predArc().
    717     ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     719    ///\ref predArc() and \ref predMap().
     720    ///
     721    ///\pre Either \ref run(Node) "run()" or \ref init()
     722    ///must be called before using this function.
    720723    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721724                                  G->source((*_pred)[v]); }
     
    727730    ///distances of the nodes calculated by the algorithm.
    728731    ///
    729     ///\pre Either \ref run() or \ref init()
     732    ///\pre Either \ref run(Node) "run()" or \ref init()
    730733    ///must be called before using this function.
    731734    const DistMap &distMap() const { return *_dist;}
     
    735738    ///
    736739    ///Returns a const reference to the node map that stores the predecessor
    737     ///arcs, which form the DFS tree.
    738     ///
    739     ///\pre Either \ref run() or \ref init()
     740    ///arcs, which form the DFS tree (forest).
     741    ///
     742    ///\pre Either \ref run(Node) "run()" or \ref init()
    740743    ///must be called before using this function.
    741744    const PredMap &predMap() const { return *_pred;}
    742745
    743     ///Checks if a node is reachable from the root(s).
    744 
    745     ///Returns \c true if \c v is reachable from the root(s).
    746     ///\pre Either \ref run() or \ref start()
     746    ///Checks if the given node. node is reached from the root(s).
     747
     748    ///Returns \c true if \c v is reached from the root(s).
     749    ///
     750    ///\pre Either \ref run(Node) "run()" or \ref init()
    747751    ///must be called before using this function.
    748752    bool reached(Node v) const { return (*_reached)[v]; }
     
    766770    ///The type of the map that stores the predecessor
    767771    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     772    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769773    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770774    ///Instantiates a PredMap.
     
    781785
    782786    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    784     ///By default it is a NullMap.
     787    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     788    ///By default, it is a NullMap.
    785789    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    786790    ///Instantiates a ProcessedMap.
     
    801805
    802806    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805810    ///Instantiates a ReachedMap.
     
    816821
    817822    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     823    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819824    typedef typename Digraph::template NodeMap<int> DistMap;
    820825    ///Instantiates a DistMap.
     
    831836
    832837    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     838    ///It must conform to the \ref concepts::Path "Path" concept.
    834839    typedef lemon::Path<Digraph> Path;
    835840  };
     
    837842  /// Default traits class used by DfsWizard
    838843
    839   /// To make it easier to use Dfs algorithm
    840   /// we have created a wizard class.
    841   /// This \ref DfsWizard class needs default traits,
    842   /// as well as the \ref Dfs class.
    843   /// The \ref DfsWizardBase is a class to be the default traits of the
    844   /// \ref DfsWizard class.
     844  /// Default traits class used by DfsWizard.
     845  /// \tparam GR The type of the digraph.
    845846  template<class GR>
    846847  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870871    /// Constructor.
    871872
    872     /// This constructor does not require parameters, therefore it initiates
     873    /// This constructor does not require parameters, it initiates
    873874    /// all of the attributes to \c 0.
    874875    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    890891  /// This auxiliary class is created to implement the
    891892  /// \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.
     893  /// It does not have own \ref run(Node) "run()" method, it uses the
     894  /// functions and features of the plain \ref Dfs.
    894895  ///
    895896  /// This class should only be used through the \ref dfs() function,
    896897  /// which makes it easier to use the algorithm.
     898  ///
     899  /// \tparam TR The traits class that defines various types used by the
     900  /// algorithm.
    897901  template<class TR>
    898902  class DfsWizard : public TR
     
    900904    typedef TR Base;
    901905
    902     ///The type of the digraph the algorithm runs on.
    903906    typedef typename TR::Digraph Digraph;
    904907
     
    908911    typedef typename Digraph::OutArcIt OutArcIt;
    909912
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912913    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914914    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916915    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918916    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920917    typedef typename TR::Path Path;
    921918
     
    987984    ///Runs DFS algorithm to visit all nodes in the digraph.
    988985
    989     ///This method runs DFS algorithm in order to compute
    990     ///the DFS path to each node.
     986    ///This method runs DFS algorithm in order to visit all nodes
     987    ///in the digraph.
    991988    void run()
    992989    {
     
    1000997      SetPredMapBase(const TR &b) : TR(b) {}
    1001998    };
    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.
     999
     1000    ///\brief \ref named-templ-param "Named parameter" for setting
     1001    ///the predecessor map.
     1002    ///
     1003    ///\ref named-templ-param "Named parameter" function for setting
     1004    ///the map that stores the predecessor arcs of the nodes.
    10071005    template<class T>
    10081006    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181016      SetReachedMapBase(const TR &b) : TR(b) {}
    10191017    };
    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.
     1018
     1019    ///\brief \ref named-templ-param "Named parameter" for setting
     1020    ///the reached map.
     1021    ///
     1022    ///\ref named-templ-param "Named parameter" function for setting
     1023    ///the map that indicates which nodes are reached.
    10251024    template<class T>
    10261025    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361035      SetDistMapBase(const TR &b) : TR(b) {}
    10371036    };
    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.
     1037
     1038    ///\brief \ref named-templ-param "Named parameter" for setting
     1039    ///the distance map.
     1040    ///
     1041    ///\ref named-templ-param "Named parameter" function for setting
     1042    ///the map that stores the distances of the nodes calculated
     1043    ///by the algorithm.
    10431044    template<class T>
    10441045    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541055      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551056    };
    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.
     1057
     1058    ///\brief \ref named-func-param "Named parameter" for setting
     1059    ///the processed map.
     1060    ///
     1061    ///\ref named-templ-param "Named parameter" function for setting
     1062    ///the map that indicates which nodes are processed.
    10611063    template<class T>
    10621064    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    11111113  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121114  ///\endcode
    1113 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1115  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151116  ///to the end of the parameter list.
    11161117  ///\sa DfsWizard
     
    11281129  /// This class defines the interface of the DfsVisit events, and
    11291130  /// it could be the base of a real visitor class.
    1130   template <typename _Digraph>
     1131  template <typename GR>
    11311132  struct DfsVisitor {
    1132     typedef _Digraph Digraph;
     1133    typedef GR Digraph;
    11331134    typedef typename Digraph::Arc Arc;
    11341135    typedef typename Digraph::Node Node;
     
    11661167  };
    11671168#else
    1168   template <typename _Digraph>
     1169  template <typename GR>
    11691170  struct DfsVisitor {
    1170     typedef _Digraph Digraph;
     1171    typedef GR Digraph;
    11711172    typedef typename Digraph::Arc Arc;
    11721173    typedef typename Digraph::Node Node;
     
    12011202  /// Default traits class of DfsVisit class.
    12021203  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1203   template<class _Digraph>
     1204  template<class GR>
    12041205  struct DfsVisitDefaultTraits {
    12051206
    12061207    /// \brief The type of the digraph the algorithm runs on.
    1207     typedef _Digraph Digraph;
     1208    typedef GR Digraph;
    12081209
    12091210    /// \brief The type of the map that indicates which nodes are reached.
    12101211    ///
    12111212    /// The type of the map that indicates which nodes are reached.
    1212     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1213    /// It must conform to the
     1214    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12131215    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12141216
     
    12261228  /// \ingroup search
    12271229  ///
    1228   /// \brief %DFS algorithm class with visitor interface.
     1230  /// \brief DFS algorithm class with visitor interface.
    12291231  ///
    1230   /// This class provides an efficient implementation of the %DFS algorithm
     1232  /// This class provides an efficient implementation of the DFS algorithm
    12311233  /// with visitor interface.
    12321234  ///
    1233   /// The %DfsVisit class provides an alternative interface to the Dfs
     1235  /// The DfsVisit class provides an alternative interface to the Dfs
    12341236  /// class. It works with callback mechanism, the DfsVisit object calls
    12351237  /// the member functions of the \c Visitor class on every DFS event.
     
    12401242  /// instead.
    12411243  ///
    1242   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1243   /// The default value is
    1244   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1245   /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
    1246   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1247   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
     1244  /// \tparam GR The type of the digraph the algorithm runs on.
     1245  /// The default type is \ref ListDigraph.
     1246  /// The value of GR is not used directly by \ref DfsVisit,
     1247  /// it is only passed to \ref DfsVisitDefaultTraits.
     1248  /// \tparam VS The Visitor type that is used by the algorithm.
     1249  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
    12481250  /// does not observe the DFS events. If you want to observe the DFS
    12491251  /// events, you should implement your own visitor class.
    1250   /// \tparam _Traits Traits class to set various data types used by the
    1251   /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
    1253   /// See \ref DfsVisitDefaultTraits for the documentation of
    1254   /// a DFS visit traits class.
     1252  /// \tparam TR The traits class that defines various types used by the
     1253  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
     1254  /// "DfsVisitDefaultTraits<GR>".
     1255  /// In most cases, this parameter should not be set directly,
     1256  /// consider to use the named template parameters instead.
    12551257#ifdef DOXYGEN
    1256   template <typename _Digraph, typename _Visitor, typename _Traits>
     1258  template <typename GR, typename VS, typename TR>
    12571259#else
    1258   template <typename _Digraph = ListDigraph,
    1259             typename _Visitor = DfsVisitor<_Digraph>,
    1260             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
     1260  template <typename GR = ListDigraph,
     1261            typename VS = DfsVisitor<GR>,
     1262            typename TR = DfsVisitDefaultTraits<GR> >
    12611263#endif
    12621264  class DfsVisit {
     
    12641266
    12651267    ///The traits class.
    1266     typedef _Traits Traits;
     1268    typedef TR Traits;
    12671269
    12681270    ///The type of the digraph the algorithm runs on.
     
    12701272
    12711273    ///The visitor type used by the algorithm.
    1272     typedef _Visitor Visitor;
     1274    typedef VS Visitor;
    12731275
    12741276    ///The type of the map that indicates which nodes are reached.
     
    13101312    typedef DfsVisit Create;
    13111313
    1312     /// \name Named template parameters
     1314    /// \name Named Template Parameters
    13131315
    13141316    ///@{
     
    13521354    ///
    13531355    /// Sets the map that indicates which nodes are reached.
    1354     /// If you don't use this function before calling \ref run(),
    1355     /// it will allocate one. The destructor deallocates this
    1356     /// automatically allocated map, of course.
     1356    /// If you don't use this function before calling \ref run(Node) "run()"
     1357    /// or \ref init(), an instance will be allocated automatically.
     1358    /// The destructor deallocates this automatically allocated map,
     1359    /// of course.
    13571360    /// \return <tt> (*this) </tt>
    13581361    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671370  public:
    13681371
    1369     /// \name Execution control
    1370     /// The simplest way to execute the algorithm is to use
    1371     /// one of the member functions called \ref lemon::DfsVisit::run()
    1372     /// "run()".
    1373     /// \n
    1374     /// If you need more control on the execution, first you must call
    1375     /// \ref lemon::DfsVisit::init() "init()", then you can add several
    1376     /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
    1377     /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
    1378     /// actual path computation.
     1372    /// \name Execution Control
     1373    /// The simplest way to execute the DFS algorithm is to use one of the
     1374    /// member functions called \ref run(Node) "run()".\n
     1375    /// If you need better control on the execution, you have to call
     1376    /// \ref init() first, then you can add a source node with \ref addSource()
     1377    /// and perform the actual computation with \ref start().
     1378    /// This procedure can be repeated if there are nodes that have not
     1379    /// been reached.
    13791380
    13801381    /// @{
     
    13921393    }
    13931394
    1394     ///Adds a new source node.
    1395 
    1396     ///Adds a new source node to the set of nodes to be processed.
    1397     ///
    1398     ///\pre The stack must be empty. (Otherwise the algorithm gives
    1399     ///false results.)
    1400     ///
    1401     ///\warning Distances will be wrong (or at least strange) in case of
    1402     ///multiple sources.
     1395    /// \brief Adds a new source node.
     1396    ///
     1397    /// Adds a new source node to the set of nodes to be processed.
     1398    ///
     1399    /// \pre The stack must be empty. Otherwise the algorithm gives
     1400    /// wrong results. (One of the outgoing arcs of all the source nodes
     1401    /// except for the last one will not be visited and distances will
     1402    /// also be wrong.)
    14031403    void addSource(Node s)
    14041404    {
     
    14141414          } else {
    14151415            _visitor->leave(s);
     1416            _visitor->stop(s);
    14161417          }
    14171418        }
     
    15861587    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15871588
    1588     /// This method runs the %DFS algorithm in order to
    1589     /// compute the %DFS path to each node.
    1590     ///
    1591     /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1589    /// This method runs the %DFS algorithm in order to visit all nodes
     1590    /// in the digraph.
    15941591    ///
    15951592    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161613
    16171614    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1615    /// The results of the DFS algorithm can be obtained using these
    16191616    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1617    /// Either \ref run(Node) "run()" or \ref start() should be called
     1618    /// before using them.
     1619
    16231620    ///@{
    16241621
    1625     /// \brief Checks if a node is reachable from the root(s).
    1626     ///
    1627     /// Returns \c true if \c v is reachable from the root(s).
    1628     /// \pre Either \ref run() or \ref start()
     1622    /// \brief Checks if the given node is reached from the root(s).
     1623    ///
     1624    /// Returns \c true if \c v is reached from the root(s).
     1625    ///
     1626    /// \pre Either \ref run(Node) "run()" or \ref init()
    16291627    /// must be called before using this function.
    1630     bool reached(Node v) { return (*_reached)[v]; }
     1628    bool reached(Node v) const { return (*_reached)[v]; }
    16311629
    16321630    ///@}
  • test/dfs_test.cc

    r877 r907  
    5151  "@attributes\n"
    5252  "source 0\n"
    53   "target 5\n";
     53  "target 5\n"
     54  "source1 6\n"
     55  "target1 3\n";
     56
    5457
    5558void checkDfsCompile()
     
    180183  Digraph G;
    181184  Node s, t;
     185  Node s1, t1;
    182186
    183187  std::istringstream input(test_lgf);
     
    185189    node("source", s).
    186190    node("target", t).
     191    node("source1", s1).
     192    node("target1", t1).
    187193    run();
    188194
     
    211217
    212218  {
     219  Dfs<Digraph> dfs(G);
     220  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
     221  }
     222 
     223  {
    213224    NullMap<Node,Arc> myPredMap;
    214225    dfs(G).predMap(myPredMap).run(s);
  • test/dfs_test.cc

    r906 r907  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6666  Node s, t;
    6767  Arc e;
    68   int l;
     68  int l, i;
    6969  bool b;
    7070  DType::DistMap d(G);
    7171  DType::PredMap p(G);
    7272  Path<Digraph> pp;
     73  concepts::ReadMap<Arc,bool> am;
    7374
    7475  {
    7576    DType dfs_test(G);
     77    const DType& const_dfs_test = dfs_test;
    7678
    7779    dfs_test.run(s);
     
    7981    dfs_test.run();
    8082
    81     l  = dfs_test.dist(t);
    82     e  = dfs_test.predArc(t);
    83     s  = dfs_test.predNode(t);
    84     b  = dfs_test.reached(t);
    85     d  = dfs_test.distMap();
    86     p  = dfs_test.predMap();
    87     pp = dfs_test.path(t);
     83    dfs_test.init();
     84    dfs_test.addSource(s);
     85    e = dfs_test.processNextArc();
     86    e = const_dfs_test.nextArc();
     87    b = const_dfs_test.emptyQueue();
     88    i = const_dfs_test.queueSize();
     89
     90    dfs_test.start();
     91    dfs_test.start(t);
     92    dfs_test.start(am);
     93
     94    l  = const_dfs_test.dist(t);
     95    e  = const_dfs_test.predArc(t);
     96    s  = const_dfs_test.predNode(t);
     97    b  = const_dfs_test.reached(t);
     98    d  = const_dfs_test.distMap();
     99    p  = const_dfs_test.predMap();
     100    pp = const_dfs_test.path(t);
    88101  }
    89102  {
     
    92105      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
    93106      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
     107      ::SetStandardProcessedMap
    94108      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    95       ::SetStandardProcessedMap
    96109      ::Create dfs_test(G);
     110
     111    concepts::ReadWriteMap<Node,Arc> pred_map;
     112    concepts::ReadWriteMap<Node,int> dist_map;
     113    concepts::ReadWriteMap<Node,bool> reached_map;
     114    concepts::WriteMap<Node,bool> processed_map;
     115
     116    dfs_test
     117      .predMap(pred_map)
     118      .distMap(dist_map)
     119      .reachedMap(reached_map)
     120      .processedMap(processed_map);
    97121
    98122    dfs_test.run(s);
    99123    dfs_test.run(s,t);
    100124    dfs_test.run();
     125    dfs_test.init();
     126
     127    dfs_test.addSource(s);
     128    e = dfs_test.processNextArc();
     129    e = dfs_test.nextArc();
     130    b = dfs_test.emptyQueue();
     131    i = dfs_test.queueSize();
     132
     133    dfs_test.start();
     134    dfs_test.start(t);
     135    dfs_test.start(am);
    101136
    102137    l  = dfs_test.dist(t);
Note: See TracChangeset for help on using the changeset viewer.