COIN-OR::LEMON - Graph Library

Changeset 1009:c85f53572941 in lemon


Ignore:
Timestamp:
09/22/10 09:26:01 (9 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Parents:
1004:d0e5734fc48e (diff), 1007: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 to branch 1.1

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/dfs.h

    r631 r1009  
    558558    void start(Node t)
    559559    {
    560       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
     560      while ( !emptyQueue() && !(*_reached)[t] )
    561561        processNextArc();
    562562    }
     
    15101510    /// with addSource() before using this function.
    15111511    void start(Node t) {
    1512       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
     1512      while ( !emptyQueue() && !(*_reached)[t] )
    15131513        processNextArc();
    15141514    }
  • lemon/dfs.h

    r1007 r1009  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5050    ///It must meet 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    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap.
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    120120  ///
    121121  ///\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.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    213207    typedef Dfs Create;
    214208
    215     ///\name Named template parameters
     209    ///\name Named Template Parameters
    216210
    217211    ///@{
     
    227221    };
    228222    ///\brief \ref named-templ-param "Named parameter" for setting
    229     ///PredMap type.
     223    ///\c PredMap type.
    230224    ///
    231225    ///\ref named-templ-param "Named parameter" for setting
    232     ///PredMap type.
     226    ///\c PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    246241    };
    247242    ///\brief \ref named-templ-param "Named parameter" for setting
    248     ///DistMap type.
     243    ///\c DistMap type.
    249244    ///
    250245    ///\ref named-templ-param "Named parameter" for setting
    251     ///DistMap type.
     246    ///\c DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265261    };
    266262    ///\brief \ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
     263    ///\c ReachedMap type.
    268264    ///
    269265    ///\ref named-templ-param "Named parameter" for setting
    270     ///ReachedMap type.
     266    ///\c ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    284281    };
    285282    ///\brief \ref named-templ-param "Named parameter" for setting
    286     ///ProcessedMap type.
     283    ///\c ProcessedMap type.
    287284    ///
    288285    ///\ref named-templ-param "Named parameter" for setting
    289     ///ProcessedMap type.
     286    ///\c ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    301299    };
    302300    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     301    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304302    ///
    305303    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307305    ///If you don't set it explicitly, it will be automatically allocated.
    308306    struct SetStandardProcessedMap :
     
    339337
    340338    ///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.
     339    ///If you don't use this function before calling \ref run(Node) "run()"
     340    ///or \ref init(), an instance will be allocated automatically.
     341    ///The destructor deallocates this automatically allocated map,
     342    ///of course.
    344343    ///\return <tt> (*this) </tt>
    345344    Dfs &predMap(PredMap &m)
     
    356355
    357356    ///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.
     357    ///If you don't use this function before calling \ref run(Node) "run()"
     358    ///or \ref init(), an instance will be allocated automatically.
     359    ///The destructor deallocates this automatically allocated map,
     360    ///of course.
    361361    ///\return <tt> (*this) </tt>
    362362    Dfs &reachedMap(ReachedMap &m)
     
    373373
    374374    ///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.
     375    ///If you don't use this function before calling \ref run(Node) "run()"
     376    ///or \ref init(), an instance will be allocated automatically.
     377    ///The destructor deallocates this automatically allocated map,
     378    ///of course.
    378379    ///\return <tt> (*this) </tt>
    379380    Dfs &processedMap(ProcessedMap &m)
     
    391392    ///Sets the map that stores the distances of the nodes calculated by
    392393    ///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.
     394    ///If you don't use this function before calling \ref run(Node) "run()"
     395    ///or \ref init(), an instance will be allocated automatically.
     396    ///The destructor deallocates this automatically allocated map,
     397    ///of course.
    396398    ///\return <tt> (*this) </tt>
    397399    Dfs &distMap(DistMap &m)
     
    407409  public:
    408410
    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.
     411    ///\name Execution Control
     412    ///The simplest way to execute the DFS algorithm is to use one of the
     413    ///member functions called \ref run(Node) "run()".\n
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
     416    ///and perform the actual computation with \ref start().
     417    ///This procedure can be repeated if there are nodes that have not
     418    ///been reached.
    418419
    419420    ///@{
    420421
     422    ///\brief Initializes the internal data structures.
     423    ///
    421424    ///Initializes the internal data structures.
    422 
    423     ///Initializes the internal data structures.
    424     ///
    425425    void init()
    426426    {
     
    439439    ///Adds a new source node to the set of nodes to be processed.
    440440    ///
    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.
     441    ///\pre The stack must be empty. Otherwise the algorithm gives
     442    ///wrong results. (One of the outgoing arcs of all the source nodes
     443    ///except for the last one will not be visited and distances will
     444    ///also be wrong.)
    446445    void addSource(Node s)
    447446    {
     
    507506    }
    508507
    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).
     508    ///Returns \c false if there are nodes to be processed.
     509
     510    ///Returns \c false if there are nodes to be processed
     511    ///in the queue (stack).
    514512    bool emptyQueue() const { return _stack_head<0; }
    515513
    516514    ///Returns the number of the nodes to be processed.
    517515
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     516    ///Returns the number of the nodes to be processed
     517    ///in the queue (stack).
    519518    int queueSize() const { return _stack_head+1; }
    520519
     
    638637    ///
    639638    ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     639    ///- the %DFS tree (forest),
     640    ///- the distance of each node from the root(s) in the %DFS tree.
    642641    ///
    643642    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664663
    665664    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     665    ///The results of the DFS algorithm can be obtained using these
    667666    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     667    ///Either \ref run(Node) "run()" or \ref start() should be called
     668    ///before using them.
    670669
    671670    ///@{
     
    675674    ///Returns the DFS path to a node.
    676675    ///
    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    ///\warning \c t should be reached from the root(s).
     677    ///
     678    ///\pre Either \ref run(Node) "run()" or \ref init()
     679    ///must be called before using this function.
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    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
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
     685    ///
     686    ///\warning If node \c v is not reached from the root(s), then
    688687    ///the return value of this function is undefined.
    689688    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     689    ///\pre Either \ref run(Node) "run()" or \ref init()
     690    ///must be called before using this function.
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
     
    695694
    696695    ///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.
     696    ///node \c v, i.e. it returns the last arc of a %DFS path from a
     697    ///root to \c v. It is \c INVALID if \c v is not reached from the
     698    ///root(s) or if \c v is a root.
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702701    ///\ref predNode().
    703702    ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     703    ///\pre Either \ref run(Node) "run()" or \ref init()
     704    ///must be called before using this function.
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
     
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///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.
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716715    ///\ref predArc().
    717716    ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     717    ///\pre Either \ref run(Node) "run()" or \ref init()
     718    ///must be called before using this function.
    720719    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721720                                  G->source((*_pred)[v]); }
     
    727726    ///distances of the nodes calculated by the algorithm.
    728727    ///
    729     ///\pre Either \ref run() or \ref init()
     728    ///\pre Either \ref run(Node) "run()" or \ref init()
    730729    ///must be called before using this function.
    731730    const DistMap &distMap() const { return *_dist;}
     
    737736    ///arcs, which form the DFS tree.
    738737    ///
    739     ///\pre Either \ref run() or \ref init()
     738    ///\pre Either \ref run(Node) "run()" or \ref init()
    740739    ///must be called before using this function.
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    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()
     742    ///Checks if a node is reached from the root(s).
     743
     744    ///Returns \c true if \c v is reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
    747747    ///must be called before using this function.
    748748    bool reached(Node v) const { return (*_reached)[v]; }
     
    890890  /// This auxiliary class is created to implement the
    891891  /// \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.
     892  /// It does not have own \ref run(Node) "run()" method, it uses the
     893  /// functions and features of the plain \ref Dfs.
    894894  ///
    895895  /// This class should only be used through the \ref dfs() function,
     
    11111111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121112  ///\endcode
    1113 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1113  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151114  ///to the end of the parameter list.
    11161115  ///\sa DfsWizard
     
    11281127  /// This class defines the interface of the DfsVisit events, and
    11291128  /// it could be the base of a real visitor class.
    1130   template <typename _Digraph>
     1129  template <typename GR>
    11311130  struct DfsVisitor {
    1132     typedef _Digraph Digraph;
     1131    typedef GR Digraph;
    11331132    typedef typename Digraph::Arc Arc;
    11341133    typedef typename Digraph::Node Node;
     
    11661165  };
    11671166#else
    1168   template <typename _Digraph>
     1167  template <typename GR>
    11691168  struct DfsVisitor {
    1170     typedef _Digraph Digraph;
     1169    typedef GR Digraph;
    11711170    typedef typename Digraph::Arc Arc;
    11721171    typedef typename Digraph::Node Node;
     
    12011200  /// Default traits class of DfsVisit class.
    12021201  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1203   template<class _Digraph>
     1202  template<class GR>
    12041203  struct DfsVisitDefaultTraits {
    12051204
    12061205    /// \brief The type of the digraph the algorithm runs on.
    1207     typedef _Digraph Digraph;
     1206    typedef GR Digraph;
    12081207
    12091208    /// \brief The type of the map that indicates which nodes are reached.
     
    12261225  /// \ingroup search
    12271226  ///
    1228   /// \brief %DFS algorithm class with visitor interface.
     1227  /// \brief DFS algorithm class with visitor interface.
    12291228  ///
    1230   /// This class provides an efficient implementation of the %DFS algorithm
     1229  /// This class provides an efficient implementation of the DFS algorithm
    12311230  /// with visitor interface.
    12321231  ///
    1233   /// The %DfsVisit class provides an alternative interface to the Dfs
     1232  /// The DfsVisit class provides an alternative interface to the Dfs
    12341233  /// class. It works with callback mechanism, the DfsVisit object calls
    12351234  /// the member functions of the \c Visitor class on every DFS event.
     
    12401239  /// instead.
    12411240  ///
    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
     1241  /// \tparam GR The type of the digraph the algorithm runs on.
     1242  /// The default type is \ref ListDigraph.
     1243  /// The value of GR is not used directly by \ref DfsVisit,
     1244  /// it is only passed to \ref DfsVisitDefaultTraits.
     1245  /// \tparam VS The Visitor type that is used by the algorithm.
     1246  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
    12481247  /// does not observe the DFS events. If you want to observe the DFS
    12491248  /// events, you should implement your own visitor class.
    1250   /// \tparam _Traits Traits class to set various data types used by the
     1249  /// \tparam TR Traits class to set various data types used by the
    12511250  /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
     1251  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    12531252  /// See \ref DfsVisitDefaultTraits for the documentation of
    12541253  /// a DFS visit traits class.
    12551254#ifdef DOXYGEN
    1256   template <typename _Digraph, typename _Visitor, typename _Traits>
     1255  template <typename GR, typename VS, typename TR>
    12571256#else
    1258   template <typename _Digraph = ListDigraph,
    1259             typename _Visitor = DfsVisitor<_Digraph>,
    1260             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
     1257  template <typename GR = ListDigraph,
     1258            typename VS = DfsVisitor<GR>,
     1259            typename TR = DfsVisitDefaultTraits<GR> >
    12611260#endif
    12621261  class DfsVisit {
     
    12641263
    12651264    ///The traits class.
    1266     typedef _Traits Traits;
     1265    typedef TR Traits;
    12671266
    12681267    ///The type of the digraph the algorithm runs on.
     
    12701269
    12711270    ///The visitor type used by the algorithm.
    1272     typedef _Visitor Visitor;
     1271    typedef VS Visitor;
    12731272
    12741273    ///The type of the map that indicates which nodes are reached.
     
    13101309    typedef DfsVisit Create;
    13111310
    1312     /// \name Named template parameters
     1311    /// \name Named Template Parameters
    13131312
    13141313    ///@{
     
    13521351    ///
    13531352    /// 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.
     1353    /// If you don't use this function before calling \ref run(Node) "run()"
     1354    /// or \ref init(), an instance will be allocated automatically.
     1355    /// The destructor deallocates this automatically allocated map,
     1356    /// of course.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    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.
     1369    /// \name Execution Control
     1370    /// The simplest way to execute the DFS algorithm is to use one of the
     1371    /// member functions called \ref run(Node) "run()".\n
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
     1374    /// and perform the actual computation with \ref start().
     1375    /// This procedure can be repeated if there are nodes that have not
     1376    /// been reached.
    13791377
    13801378    /// @{
     
    13921390    }
    13931391
    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.
     1392    /// \brief Adds a new source node.
     1393    ///
     1394    /// Adds a new source node to the set of nodes to be processed.
     1395    ///
     1396    /// \pre The stack must be empty. Otherwise the algorithm gives
     1397    /// wrong results. (One of the outgoing arcs of all the source nodes
     1398    /// except for the last one will not be visited and distances will
     1399    /// also be wrong.)
    14031400    void addSource(Node s)
    14041401    {
     
    14141411          } else {
    14151412            _visitor->leave(s);
     1413            _visitor->stop(s);
    14161414          }
    14171415        }
     
    15901588    ///
    15911589    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1590    /// - the %DFS tree (forest),
     1591    /// - the distance of each node from the root(s) in the %DFS tree.
    15941592    ///
    15951593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161614
    16171615    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1616    /// The results of the DFS algorithm can be obtained using these
    16191617    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1618    /// Either \ref run(Node) "run()" or \ref start() should be called
     1619    /// before using them.
     1620
    16231621    ///@{
    16241622
    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()
     1623    /// \brief Checks if a node is reached from the root(s).
     1624    ///
     1625    /// Returns \c true if \c v is reached from the root(s).
     1626    ///
     1627    /// \pre Either \ref run(Node) "run()" or \ref init()
    16291628    /// must be called before using this function.
    1630     bool reached(Node v) { return (*_reached)[v]; }
     1629    bool reached(Node v) const { return (*_reached)[v]; }
    16311630
    16321631    ///@}
  • test/dfs_test.cc

    r632 r1009  
    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

    r1007 r1009  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    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.