COIN-OR::LEMON - Graph Library

Changes in / [417:6ff53afe98b5:418:ad483acf1654] in lemon-main


Ignore:
Files:
4 added
9 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r416 r418  
    1616 *
    1717 */
     18
     19namespace lemon {
    1820
    1921/**
     
    162164
    163165This group describes maps that are specifically designed to assign
    164 values to the nodes and arcs of graphs.
     166values to the nodes and arcs/edges of graphs.
     167
     168If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     169\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    165170*/
    166171
     
    173178maps from other maps.
    174179
    175 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     180Most of them are \ref concepts::ReadMap "read-only maps".
    176181They can make arithmetic and logical operations between one or two maps
    177182(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    275280\brief Common graph search algorithms.
    276281
    277 This group describes the common graph search algorithms like
    278 Breadth-First Search (BFS) and Depth-First Search (DFS).
     282This group describes the common graph search algorithms, namely
     283\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    279284*/
    280285
     
    284289\brief Algorithms for finding shortest paths.
    285290
    286 This group describes the algorithms for finding shortest paths in graphs.
     291This group describes the algorithms for finding shortest paths in digraphs.
     292
     293 - \ref Dijkstra algorithm for finding shortest paths from a source node
     294   when all arc lengths are non-negative.
     295 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     296   from a source node when arc lenghts can be either positive or negative,
     297   but the digraph should not contain directed cycles with negative total
     298   length.
     299 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     300   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     301   lenghts can be either positive or negative, but the digraph should
     302   not contain directed cycles with negative total length.
     303 - \ref Suurballe A successive shortest path algorithm for finding
     304   arc-disjoint paths between two nodes having minimum total length.
    287305*/
    288306
     
    295313feasible circulations.
    296314
    297 The maximum flow problem is to find a flow between a single source and
    298 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    299 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    300 function and given \f$s, t \in V\f$ source and target node. The
    301 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    302 
    303 \f[ 0 \le f_a \le c_a \f]
    304 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    305 \qquad \forall u \in V \setminus \{s,t\}\f]
    306 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     315The \e maximum \e flow \e problem is to find a flow of maximum value between
     316a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     317digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     318\f$s, t \in V\f$ source and target nodes.
     319A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     320following optimization problem.
     321
     322\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
     323\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
     324    \qquad \forall v\in V\setminus\{s,t\} \f]
     325\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
    307326
    308327LEMON contains several algorithms for solving maximum flow problems:
    309 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    310 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    311 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    312 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    313 
    314 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    315 fastest method to compute the maximum flow. All impelementations
    316 provides functions to query the minimum cut, which is the dual linear
    317 programming problem of the maximum flow.
     328- \ref EdmondsKarp Edmonds-Karp algorithm.
     329- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     330- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     331- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     332
     333In most cases the \ref Preflow "Preflow" algorithm provides the
     334fastest method for computing a maximum flow. All implementations
     335provides functions to also query the minimum cut, which is the dual
     336problem of the maximum flow.
    318337*/
    319338
     
    326345This group describes the algorithms for finding minimum cost flows and
    327346circulations.
     347
     348The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     349minimum total cost from a set of supply nodes to a set of demand nodes
     350in a network with capacity constraints and arc costs.
     351Formally, let \f$G=(V,A)\f$ be a digraph,
     352\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     353upper bounds for the flow values on the arcs,
     354\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     355on the arcs, and
     356\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     357of the nodes.
     358A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     359the following optimization problem.
     360
     361\f[ \min\sum_{a\in A} f(a) cost(a) \f]
     362\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
     363    supply(v) \qquad \forall v\in V \f]
     364\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
     365
     366LEMON contains several algorithms for solving minimum cost flow problems:
     367 - \ref CycleCanceling Cycle-canceling algorithms.
     368 - \ref CapacityScaling Successive shortest path algorithm with optional
     369   capacity scaling.
     370 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
     371   cost scaling.
     372 - \ref NetworkSimplex Primal network simplex algorithm with various
     373   pivot strategies.
    328374*/
    329375
     
    336382This group describes the algorithms for finding minimum cut in graphs.
    337383
    338 The minimum cut problem is to find a non-empty and non-complete
    339 \f$X\f$ subset of the vertices with minimum overall capacity on
    340 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    341 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     384The \e minimum \e cut \e problem is to find a non-empty and non-complete
     385\f$X\f$ subset of the nodes with minimum overall capacity on
     386outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     387\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    342388cut is the \f$X\f$ solution of the next optimization problem:
    343389
    344390\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    345 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     391    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    346392
    347393LEMON contains several algorithms related to minimum cut problems:
    348394
    349 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    350   in directed graphs
    351 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    352   calculate minimum cut in undirected graphs
    353 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    354   pairs minimum cut in undirected graphs
     395- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     396  in directed graphs.
     397- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     398  calculating minimum cut in undirected graphs.
     399- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     400  all-pairs minimum cut in undirected graphs.
    355401
    356402If you want to find minimum cut just between two distinict nodes,
    357 please see the \ref max_flow "Maximum Flow page".
     403see the \ref max_flow "maximum flow problem".
    358404*/
    359405
     
    394440graphs.  The matching problems in bipartite graphs are generally
    395441easier than in general graphs. The goal of the matching optimization
    396 can be the finding maximum cardinality, maximum weight or minimum cost
     442can be finding maximum cardinality, maximum weight or minimum cost
    397443matching. The search can be constrained to find perfect or
    398444maximum cardinality matching.
    399445
    400 LEMON contains the next algorithms:
    401 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    402   augmenting path algorithm for calculate maximum cardinality matching in
    403   bipartite graphs
    404 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    405   algorithm for calculate maximum cardinality matching in bipartite graphs
    406 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    407   Successive shortest path algorithm for calculate maximum weighted matching
    408   and maximum weighted bipartite matching in bipartite graph
    409 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    410   Successive shortest path algorithm for calculate minimum cost maximum
    411   matching in bipartite graph
    412 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    413   for calculate maximum cardinality matching in general graph
    414 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    415   shrinking algorithm for calculate maximum weighted matching in general
    416   graph
    417 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    418   Edmond's blossom shrinking algorithm for calculate maximum weighted
    419   perfect matching in general graph
     446The matching algorithms implemented in LEMON:
     447- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     448  for calculating maximum cardinality matching in bipartite graphs.
     449- \ref PrBipartiteMatching Push-relabel algorithm
     450  for calculating maximum cardinality matching in bipartite graphs.
     451- \ref MaxWeightedBipartiteMatching
     452  Successive shortest path algorithm for calculating maximum weighted
     453  matching and maximum weighted bipartite matching in bipartite graphs.
     454- \ref MinCostMaxBipartiteMatching
     455  Successive shortest path algorithm for calculating minimum cost maximum
     456  matching in bipartite graphs.
     457- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     458  maximum cardinality matching in general graphs.
     459- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     460  maximum weighted matching in general graphs.
     461- \ref MaxWeightedPerfectMatching
     462  Edmond's blossom shrinking algorithm for calculating maximum weighted
     463  perfect matching in general graphs.
    420464
    421465\image html bipartite_matching.png
     
    429473
    430474This group describes the algorithms for finding a minimum cost spanning
    431 tree in a graph
     475tree in a graph.
    432476*/
    433477
     
    620664\anchor demoprograms
    621665
    622 @defgroup demos Demo programs
     666@defgroup demos Demo Programs
    623667
    624668Some demo programs are listed here. Their full source codes can be found in
     
    630674
    631675/**
    632 @defgroup tools Standalone utility applications
     676@defgroup tools Standalone Utility Applications
    633677
    634678Some utility applications are listed here.
     
    638682*/
    639683
     684}
  • lemon/Makefile.am

    r416 r418  
    2222        lemon/bfs.h \
    2323        lemon/bin_heap.h \
     24        lemon/circulation.h \
    2425        lemon/color.h \
    2526        lemon/concept_check.h \
     
    3738        lemon/hypercube_graph.h \
    3839        lemon/kruskal.h \
     40        lemon/hao_orlin.h \
    3941        lemon/lgf_reader.h \
    4042        lemon/lgf_writer.h \
  • lemon/bfs.h

    r329 r405  
    5252    ///Instantiates a PredMap.
    5353
    54     ///This function instantiates a PredMap. 
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///PredMap.
     
    8181    ///The type of the map that indicates which nodes are reached.
    8282
    83     ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8485    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8586    ///Instantiates a ReachedMap.
     
    119120  ///
    120121  ///\tparam GR The type of the digraph the algorithm runs on.
    121   ///The default value is \ref ListDigraph. The value of GR is not used
    122   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    123   ///\tparam TR Traits class to set various data types used by the algorithm.
    124   ///The default traits class is
    125   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    126   ///See \ref BfsDefaultTraits for the documentation of
    127   ///a Bfs traits class.
     122  ///The default type is \ref ListDigraph.
    128123#ifdef DOXYGEN
    129124  template <typename GR,
     
    151146    typedef PredMapPath<Digraph, PredMap> Path;
    152147
    153     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    154149    typedef TR Traits;
    155150
     
    213208    typedef Bfs Create;
    214209
    215     ///\name Named template parameters
     210    ///\name Named Template Parameters
    216211
    217212    ///@{
     
    231226    ///\ref named-templ-param "Named parameter" for setting
    232227    ///PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233229    template <class T>
    234230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    250246    ///\ref named-templ-param "Named parameter" for setting
    251247    ///DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252249    template <class T>
    253250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    269266    ///\ref named-templ-param "Named parameter" for setting
    270267    ///ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271269    template <class T>
    272270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    288286    ///\ref named-templ-param "Named parameter" for setting
    289287    ///ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290289    template <class T>
    291290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    340339
    341340    ///Sets the map that stores the predecessor arcs.
    342     ///If you don't use this function before calling \ref run(),
    343     ///it will allocate one. The destructor deallocates this
    344     ///automatically allocated map, of course.
     341    ///If you don't use this function before calling \ref run(Node) "run()"
     342    ///or \ref init(), an instance will be allocated automatically.
     343    ///The destructor deallocates this automatically allocated map,
     344    ///of course.
    345345    ///\return <tt> (*this) </tt>
    346346    Bfs &predMap(PredMap &m)
     
    357357
    358358    ///Sets the map that indicates which nodes are reached.
    359     ///If you don't use this function before calling \ref run(),
    360     ///it will allocate one. The destructor deallocates this
    361     ///automatically allocated map, of course.
     359    ///If you don't use this function before calling \ref run(Node) "run()"
     360    ///or \ref init(), an instance will be allocated automatically.
     361    ///The destructor deallocates this automatically allocated map,
     362    ///of course.
    362363    ///\return <tt> (*this) </tt>
    363364    Bfs &reachedMap(ReachedMap &m)
     
    374375
    375376    ///Sets the map that indicates which nodes are processed.
    376     ///If you don't use this function before calling \ref run(),
    377     ///it will allocate one. The destructor deallocates this
    378     ///automatically allocated map, of course.
     377    ///If you don't use this function before calling \ref run(Node) "run()"
     378    ///or \ref init(), an instance will be allocated automatically.
     379    ///The destructor deallocates this automatically allocated map,
     380    ///of course.
    379381    ///\return <tt> (*this) </tt>
    380382    Bfs &processedMap(ProcessedMap &m)
     
    392394    ///Sets the map that stores the distances of the nodes calculated by
    393395    ///the algorithm.
    394     ///If you don't use this function before calling \ref run(),
    395     ///it will allocate one. The destructor deallocates this
    396     ///automatically allocated map, of course.
     396    ///If you don't use this function before calling \ref run(Node) "run()"
     397    ///or \ref init(), an instance will be allocated automatically.
     398    ///The destructor deallocates this automatically allocated map,
     399    ///of course.
    397400    ///\return <tt> (*this) </tt>
    398401    Bfs &distMap(DistMap &m)
     
    408411  public:
    409412
    410     ///\name Execution control
    411     ///The simplest way to execute the algorithm is to use
    412     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    413     ///\n
    414     ///If you need more control on the execution, first you must call
    415     ///\ref lemon::Bfs::init() "init()", then you can add several source
    416     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    417     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    418     ///actual path computation.
     413    ///\name Execution Control
     414    ///The simplest way to execute the BFS algorithm is to use one of the
     415    ///member functions called \ref run(Node) "run()".\n
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
     418    ///\ref addSource(). Finally the actual path computation can be
     419    ///performed with one of the \ref start() functions.
    419420
    420421    ///@{
    421422
     423    ///\brief Initializes the internal data structures.
     424    ///
    422425    ///Initializes the internal data structures.
    423 
    424     ///Initializes the internal data structures.
    425     ///
    426426    void init()
    427427    {
     
    557557    }
    558558
    559     ///\brief Returns \c false if there are nodes
    560     ///to be processed.
    561     ///
    562     ///Returns \c false if there are nodes
    563     ///to be processed in the queue.
     559    ///Returns \c false if there are nodes to be processed.
     560
     561    ///Returns \c false if there are nodes to be processed
     562    ///in the queue.
    564563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    565564
    566565    ///Returns the number of the nodes to be processed.
    567566
    568     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    569569    int queueSize() const { return _queue_head-_queue_tail; }
    570570
     
    731731
    732732    ///\name Query Functions
    733     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    734734    ///functions.\n
    735     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    736     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    737737
    738738    ///@{
     
    742742    ///Returns the shortest path to a node.
    743743    ///
    744     ///\warning \c t should be reachable from the root(s).
    745     ///
    746     ///\pre Either \ref run() or \ref start() must be called before
    747     ///using this function.
     744    ///\warning \c t should be reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
     747    ///must be called before using this function.
    748748    Path path(Node t) const { return Path(*G, *_pred, t); }
    749749
     
    752752    ///Returns the distance of a node from the root(s).
    753753    ///
    754     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    755755    ///the return value of this function is undefined.
    756756    ///
    757     ///\pre Either \ref run() or \ref start() must be called before
    758     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    759759    int dist(Node v) const { return (*_dist)[v]; }
    760760
     
    763763    ///This function returns the 'previous arc' of the shortest path
    764764    ///tree for the node \c v, i.e. it returns the last arc of a
    765     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    766     ///is not reachable from the root(s) or if \c v is a root.
     765    ///shortest path from a root to \c v. It is \c INVALID if \c v
     766    ///is not reached from the root(s) or if \c v is a root.
    767767    ///
    768768    ///The shortest path tree used here is equal to the shortest path
    769769    ///tree used in \ref predNode().
    770770    ///
    771     ///\pre Either \ref run() or \ref start() must be called before
    772     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    773773    Arc predArc(Node v) const { return (*_pred)[v];}
    774774
     
    777777    ///This function returns the 'previous node' of the shortest path
    778778    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    780     ///if \c v is not reachable from the root(s) or if \c v is a root.
     779    ///from a shortest path from a root to \c v. It is \c INVALID
     780    ///if \c v is not reached from the root(s) or if \c v is a root.
    781781    ///
    782782    ///The shortest path tree used here is equal to the shortest path
    783783    ///tree used in \ref predArc().
    784784    ///
    785     ///\pre Either \ref run() or \ref start() must be called before
    786     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    787787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    788788                                  G->source((*_pred)[v]); }
     
    794794    ///of the nodes calculated by the algorithm.
    795795    ///
    796     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    797797    ///must be called before using this function.
    798798    const DistMap &distMap() const { return *_dist;}
     
    804804    ///arcs, which form the shortest path tree.
    805805    ///
    806     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    807807    ///must be called before using this function.
    808808    const PredMap &predMap() const { return *_pred;}
    809809
    810     ///Checks if a node is reachable from the root(s).
    811 
    812     ///Returns \c true if \c v is reachable from the root(s).
    813     ///\pre Either \ref run() or \ref start()
     810    ///Checks if a node is reached from the root(s).
     811
     812    ///Returns \c true if \c v is reached from the root(s).
     813    ///
     814    ///\pre Either \ref run(Node) "run()" or \ref init()
    814815    ///must be called before using this function.
    815816    bool reached(Node v) const { return (*_reached)[v]; }
     
    957958  /// This auxiliary class is created to implement the
    958959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    959   /// It does not have own \ref run() method, it uses the functions
    960   /// and features of the plain \ref Bfs.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions and features of the plain \ref Bfs.
    961962  ///
    962963  /// This class should only be used through the \ref bfs() function,
     
    11781179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11791180  ///\endcode
    1180   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11811182  ///to the end of the parameter list.
    11821183  ///\sa BfsWizard
     
    13641365    typedef BfsVisit Create;
    13651366
    1366     /// \name Named template parameters
     1367    /// \name Named Template Parameters
    13671368
    13681369    ///@{
     
    14061407    ///
    14071408    /// Sets the map that indicates which nodes are reached.
    1408     /// If you don't use this function before calling \ref run(),
    1409     /// it will allocate one. The destructor deallocates this
    1410     /// automatically allocated map, of course.
     1409    /// If you don't use this function before calling \ref run(Node) "run()"
     1410    /// or \ref init(), an instance will be allocated automatically.
     1411    /// The destructor deallocates this automatically allocated map,
     1412    /// of course.
    14111413    /// \return <tt> (*this) </tt>
    14121414    BfsVisit &reachedMap(ReachedMap &m) {
     
    14211423  public:
    14221424
    1423     /// \name Execution control
    1424     /// The simplest way to execute the algorithm is to use
    1425     /// one of the member functions called \ref lemon::BfsVisit::run()
    1426     /// "run()".
    1427     /// \n
    1428     /// If you need more control on the execution, first you must call
    1429     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1430     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1431     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1432     /// actual path computation.
     1425    /// \name Execution Control
     1426    /// The simplest way to execute the BFS algorithm is to use one of the
     1427    /// member functions called \ref run(Node) "run()".\n
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
     1430    /// \ref addSource(). Finally the actual path computation can be
     1431    /// performed with one of the \ref start() functions.
    14331432
    14341433    /// @{
     
    17301729
    17311730    /// \name Query Functions
    1732     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17331732    /// functions.\n
    1734     /// Either \ref lemon::BfsVisit::run() "run()" or
    1735     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1736     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17371736    ///@{
    17381737
    1739     /// \brief Checks if a node is reachable from the root(s).
    1740     ///
    1741     /// Returns \c true if \c v is reachable from the root(s).
    1742     /// \pre Either \ref run() or \ref start()
     1738    /// \brief Checks if a node is reached from the root(s).
     1739    ///
     1740    /// Returns \c true if \c v is reached from the root(s).
     1741    ///
     1742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17431743    /// must be called before using this function.
    17441744    bool reached(Node v) { return (*_reached)[v]; }
  • lemon/dfs.h

    r319 r405  
    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
     
    231225    ///\ref named-templ-param "Named parameter" for setting
    232226    ///PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    250245    ///\ref named-templ-param "Named parameter" for setting
    251246    ///DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    269265    ///\ref named-templ-param "Named parameter" for setting
    270266    ///ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    288285    ///\ref named-templ-param "Named parameter" for setting
    289286    ///ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    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
     
    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    {
     
    15901587    ///
    15911588    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1589    /// - the %DFS tree (forest),
     1590    /// - the distance of each node from the root(s) in the %DFS tree.
    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 a 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.
    16301628    bool reached(Node v) { return (*_reached)[v]; }
  • lemon/dijkstra.h

    r313 r408  
    5555  };
    5656
    57   /// \brief Widest path operation traits for the Dijkstra algorithm class.
    58   ///
    59   /// This operation traits class defines all computational operations and
    60   /// constants which are used in the Dijkstra algorithm for widest path
    61   /// computation.
    62   ///
    63   /// \see DijkstraDefaultOperationTraits
    64   template <typename Value>
    65   struct DijkstraWidestPathOperationTraits {
    66     /// \brief Gives back the maximum value of the type.
    67     static Value zero() {
    68       return std::numeric_limits<Value>::max();
    69     }
    70     /// \brief Gives back the minimum of the given two elements.
    71     static Value plus(const Value& left, const Value& right) {
    72       return std::min(left, right);
    73     }
    74     /// \brief Gives back true only if the first value is less than the second.
    75     static bool less(const Value& left, const Value& right) {
    76       return left < right;
    77     }
    78   };
    79 
    8057  ///Default traits class of Dijkstra class.
    8158
     
    203180  ///
    204181  ///\tparam GR The type of the digraph the algorithm runs on.
    205   ///The default value is \ref ListDigraph.
    206   ///The value of GR is not used directly by \ref Dijkstra, it is only
    207   ///passed to \ref DijkstraDefaultTraits.
    208   ///\tparam LM A readable arc map that determines the lengths of the
    209   ///arcs. It is read once for each arc, so the map may involve in
     182  ///The default type is \ref ListDigraph.
     183  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
     184  ///the lengths of the arcs.
     185  ///It is read once for each arc, so the map may involve in
    210186  ///relatively time consuming process to compute the arc lengths if
    211187  ///it is necessary. The default map type is \ref
    212   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    213   ///The value of LM is not used directly by \ref Dijkstra, it is only
    214   ///passed to \ref DijkstraDefaultTraits.
    215   ///\tparam TR Traits class to set various data types used by the algorithm.
    216   ///The default traits class is \ref DijkstraDefaultTraits
    217   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    218   ///for the documentation of a Dijkstra traits class.
     188  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    219189#ifdef DOXYGEN
    220190  template <typename GR, typename LM, typename TR>
     
    250220    typedef typename TR::OperationTraits OperationTraits;
    251221
    252     ///The traits class.
     222    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    253223    typedef TR Traits;
    254224
     
    332302    ///\ref named-templ-param "Named parameter" for setting
    333303    ///PredMap type.
     304    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    334305    template <class T>
    335306    struct SetPredMap
     
    352323    ///\ref named-templ-param "Named parameter" for setting
    353324    ///DistMap type.
     325    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    354326    template <class T>
    355327    struct SetDistMap
     
    372344    ///\ref named-templ-param "Named parameter" for setting
    373345    ///ProcessedMap type.
     346    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    374347    template <class T>
    375348    struct SetProcessedMap
     
    412385    };
    413386    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference type
     387    ///heap and cross reference types
    415388    ///
    416389    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference type.
     390    ///reference types. If this named parameter is used, then external
     391    ///heap and cross reference objects must be passed to the algorithm
     392    ///using the \ref heap() function before calling \ref run(Node) "run()"
     393    ///or \ref init().
     394    ///\sa SetStandardHeap
    418395    template <class H, class CR = typename Digraph::template NodeMap<int> >
    419396    struct SetHeap
     
    435412    };
    436413    ///\brief \ref named-templ-param "Named parameter" for setting
    437     ///heap and cross reference type with automatic allocation
     414    ///heap and cross reference types with automatic allocation
    438415    ///
    439416    ///\ref named-templ-param "Named parameter" for setting heap and cross
    440     ///reference type. It can allocate the heap and the cross reference
    441     ///object if the cross reference's constructor waits for the digraph as
    442     ///parameter and the heap's constructor waits for the cross reference.
     417    ///reference types with automatic allocation.
     418    ///They should have standard constructor interfaces to be able to
     419    ///automatically created by the algorithm (i.e. the digraph should be
     420    ///passed to the constructor of the cross reference and the cross
     421    ///reference should be passed to the constructor of the heap).
     422    ///However external heap and cross reference objects could also be
     423    ///passed to the algorithm using the \ref heap() function before
     424    ///calling \ref run(Node) "run()" or \ref init().
     425    ///\sa SetHeap
    443426    template <class H, class CR = typename Digraph::template NodeMap<int> >
    444427    struct SetStandardHeap
     
    510493
    511494    ///Sets the map that stores the predecessor arcs.
    512     ///If you don't use this function before calling \ref run(),
    513     ///it will allocate one. The destructor deallocates this
    514     ///automatically allocated map, of course.
     495    ///If you don't use this function before calling \ref run(Node) "run()"
     496    ///or \ref init(), an instance will be allocated automatically.
     497    ///The destructor deallocates this automatically allocated map,
     498    ///of course.
    515499    ///\return <tt> (*this) </tt>
    516500    Dijkstra &predMap(PredMap &m)
     
    527511
    528512    ///Sets the map that indicates which nodes are processed.
    529     ///If you don't use this function before calling \ref run(),
    530     ///it will allocate one. The destructor deallocates this
    531     ///automatically allocated map, of course.
     513    ///If you don't use this function before calling \ref run(Node) "run()"
     514    ///or \ref init(), an instance will be allocated automatically.
     515    ///The destructor deallocates this automatically allocated map,
     516    ///of course.
    532517    ///\return <tt> (*this) </tt>
    533518    Dijkstra &processedMap(ProcessedMap &m)
     
    545530    ///Sets the map that stores the distances of the nodes calculated by the
    546531    ///algorithm.
    547     ///If you don't use this function before calling \ref run(),
    548     ///it will allocate one. The destructor deallocates this
    549     ///automatically allocated map, of course.
     532    ///If you don't use this function before calling \ref run(Node) "run()"
     533    ///or \ref init(), an instance will be allocated automatically.
     534    ///The destructor deallocates this automatically allocated map,
     535    ///of course.
    550536    ///\return <tt> (*this) </tt>
    551537    Dijkstra &distMap(DistMap &m)
     
    562548
    563549    ///Sets the heap and the cross reference used by algorithm.
    564     ///If you don't use this function before calling \ref run(),
    565     ///it will allocate one. The destructor deallocates this
    566     ///automatically allocated heap and cross reference, of course.
     550    ///If you don't use this function before calling \ref run(Node) "run()"
     551    ///or \ref init(), heap and cross reference instances will be
     552    ///allocated automatically.
     553    ///The destructor deallocates these automatically allocated objects,
     554    ///of course.
    567555    ///\return <tt> (*this) </tt>
    568556    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    591579  public:
    592580
    593     ///\name Execution control
    594     ///The simplest way to execute the algorithm is to use one of the
    595     ///member functions called \ref lemon::Dijkstra::run() "run()".
    596     ///\n
    597     ///If you need more control on the execution, first you must call
    598     ///\ref lemon::Dijkstra::init() "init()", then you can add several
    599     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
    600     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
    601     ///actual path computation.
     581    ///\name Execution Control
     582    ///The simplest way to execute the %Dijkstra algorithm is to use
     583    ///one of the member functions called \ref run(Node) "run()".\n
     584    ///If you need more control on the execution, first you have to call
     585    ///\ref init(), then you can add several source nodes with
     586    ///\ref addSource(). Finally the actual path computation can be
     587    ///performed with one of the \ref start() functions.
    602588
    603589    ///@{
    604590
     591    ///\brief Initializes the internal data structures.
     592    ///
    605593    ///Initializes the internal data structures.
    606 
    607     ///Initializes the internal data structures.
    608     ///
    609594    void init()
    610595    {
     
    682667    }
    683668
    684     ///\brief Returns \c false if there are nodes
    685     ///to be processed.
    686     ///
    687     ///Returns \c false if there are nodes
    688     ///to be processed in the priority heap.
     669    ///Returns \c false if there are nodes to be processed.
     670
     671    ///Returns \c false if there are nodes to be processed
     672    ///in the priority heap.
    689673    bool emptyQueue() const { return _heap->empty(); }
    690674
    691     ///Returns the number of the nodes to be processed in the priority heap
    692 
    693     ///Returns the number of the nodes to be processed in the priority heap.
    694     ///
     675    ///Returns the number of the nodes to be processed.
     676
     677    ///Returns the number of the nodes to be processed
     678    ///in the priority heap.
    695679    int queueSize() const { return _heap->size(); }
    696680
     
    813797
    814798    ///\name Query Functions
    815     ///The result of the %Dijkstra algorithm can be obtained using these
     799    ///The results of the %Dijkstra algorithm can be obtained using these
    816800    ///functions.\n
    817     ///Either \ref lemon::Dijkstra::run() "run()" or
    818     ///\ref lemon::Dijkstra::start() "start()" must be called before
    819     ///using them.
     801    ///Either \ref run(Node) "run()" or \ref start() should be called
     802    ///before using them.
    820803
    821804    ///@{
     
    825808    ///Returns the shortest path to a node.
    826809    ///
    827     ///\warning \c t should be reachable from the root(s).
    828     ///
    829     ///\pre Either \ref run() or \ref start() must be called before
    830     ///using this function.
     810    ///\warning \c t should be reached from the root(s).
     811    ///
     812    ///\pre Either \ref run(Node) "run()" or \ref init()
     813    ///must be called before using this function.
    831814    Path path(Node t) const { return Path(*G, *_pred, t); }
    832815
     
    835818    ///Returns the distance of a node from the root(s).
    836819    ///
    837     ///\warning If node \c v is not reachable from the root(s), then
     820    ///\warning If node \c v is not reached from the root(s), then
    838821    ///the return value of this function is undefined.
    839822    ///
    840     ///\pre Either \ref run() or \ref start() must be called before
    841     ///using this function.
     823    ///\pre Either \ref run(Node) "run()" or \ref init()
     824    ///must be called before using this function.
    842825    Value dist(Node v) const { return (*_dist)[v]; }
    843826
     
    846829    ///This function returns the 'previous arc' of the shortest path
    847830    ///tree for the node \c v, i.e. it returns the last arc of a
    848     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    849     ///is not reachable from the root(s) or if \c v is a root.
     831    ///shortest path from a root to \c v. It is \c INVALID if \c v
     832    ///is not reached from the root(s) or if \c v is a root.
    850833    ///
    851834    ///The shortest path tree used here is equal to the shortest path
    852835    ///tree used in \ref predNode().
    853836    ///
    854     ///\pre Either \ref run() or \ref start() must be called before
    855     ///using this function.
     837    ///\pre Either \ref run(Node) "run()" or \ref init()
     838    ///must be called before using this function.
    856839    Arc predArc(Node v) const { return (*_pred)[v]; }
    857840
     
    860843    ///This function returns the 'previous node' of the shortest path
    861844    ///tree for the node \c v, i.e. it returns the last but one node
    862     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    863     ///if \c v is not reachable from the root(s) or if \c v is a root.
     845    ///from a shortest path from a root to \c v. It is \c INVALID
     846    ///if \c v is not reached from the root(s) or if \c v is a root.
    864847    ///
    865848    ///The shortest path tree used here is equal to the shortest path
    866849    ///tree used in \ref predArc().
    867850    ///
    868     ///\pre Either \ref run() or \ref start() must be called before
    869     ///using this function.
     851    ///\pre Either \ref run(Node) "run()" or \ref init()
     852    ///must be called before using this function.
    870853    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    871854                                  G->source((*_pred)[v]); }
     
    877860    ///of the nodes calculated by the algorithm.
    878861    ///
    879     ///\pre Either \ref run() or \ref init()
     862    ///\pre Either \ref run(Node) "run()" or \ref init()
    880863    ///must be called before using this function.
    881864    const DistMap &distMap() const { return *_dist;}
     
    887870    ///arcs, which form the shortest path tree.
    888871    ///
    889     ///\pre Either \ref run() or \ref init()
     872    ///\pre Either \ref run(Node) "run()" or \ref init()
    890873    ///must be called before using this function.
    891874    const PredMap &predMap() const { return *_pred;}
    892875
    893     ///Checks if a node is reachable from the root(s).
    894 
    895     ///Returns \c true if \c v is reachable from the root(s).
    896     ///\pre Either \ref run() or \ref start()
     876    ///Checks if a node is reached from the root(s).
     877
     878    ///Returns \c true if \c v is reached from the root(s).
     879    ///
     880    ///\pre Either \ref run(Node) "run()" or \ref init()
    897881    ///must be called before using this function.
    898882    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    903887    ///Returns \c true if \c v is processed, i.e. the shortest
    904888    ///path to \c v has already found.
    905     ///\pre Either \ref run() or \ref init()
     889    ///
     890    ///\pre Either \ref run(Node) "run()" or \ref init()
    906891    ///must be called before using this function.
    907892    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    912897    ///Returns the current distance of a node from the root(s).
    913898    ///It may be decreased in the following processes.
    914     ///\pre Either \ref run() or \ref init()
     899    ///
     900    ///\pre Either \ref run(Node) "run()" or \ref init()
    915901    ///must be called before using this function and
    916902    ///node \c v must be reached but not necessarily processed.
     
    10951081  /// This auxiliary class is created to implement the
    10961082  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1097   /// It does not have own \ref run() method, it uses the functions
    1098   /// and features of the plain \ref Dijkstra.
     1083  /// It does not have own \ref run(Node) "run()" method, it uses the
     1084  /// functions and features of the plain \ref Dijkstra.
    10991085  ///
    11001086  /// This class should only be used through the \ref dijkstra() function,
     
    12911277  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12921278  ///\endcode
    1293   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1279  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12941280  ///to the end of the parameter list.
    12951281  ///\sa DijkstraWizard
  • scripts/unify-sources.sh

    r341 r396  
    131131    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    132132
    133     if [ $FAILED_FILES -gt 0 ]
    134     then
    135         return 1
    136     elif [ $WARNED_FILES -gt 0 ]
     133    if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ]
    137134    then
    138135        if [ "$WARNING" == 'INTERACTIVE' ]
    139136        then
    140             echo -n "Are the files with warnings acceptable? (yes/no) "
     137            echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    141138            while read answer
    142139            do
     
    148145                    return 1
    149146                fi
    150                 echo -n "Are the files with warnings acceptable? (yes/no) "
     147                echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    151148            done
    152149        elif [ "$WARNING" == 'WERROR' ]
  • test/CMakeLists.txt

    r327 r410  
    1414  graph_test
    1515  graph_utils_test
     16  hao_orlin_test
    1617  heap_test
    1718  kruskal_test
  • test/Makefile.am

    r414 r418  
    1010check_PROGRAMS += \
    1111        test/bfs_test \
     12        test/circulation_test \
    1213        test/counter_test \
    1314        test/dfs_test \
     
    2223        test/heap_test \
    2324        test/kruskal_test \
     25        test/hao_orlin_test \
    2426        test/maps_test \
    2527        test/max_matching_test \
     
    3739
    3840test_bfs_test_SOURCES = test/bfs_test.cc
     41test_circulation_test_SOURCES = test/circulation_test.cc
    3942test_counter_test_SOURCES = test/counter_test.cc
    4043test_dfs_test_SOURCES = test/dfs_test.cc
     
    4952test_heap_test_SOURCES = test/heap_test.cc
    5053test_kruskal_test_SOURCES = test/kruskal_test.cc
     54test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
    5155test_maps_test_SOURCES = test/maps_test.cc
    5256test_max_matching_test_SOURCES = test/max_matching_test.cc
  • test/dijkstra_test.cc

    r293 r397  
    9090      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    9191      ::SetStandardProcessedMap
    92       ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
     92      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
    9393      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    9494      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
Note: See TracChangeset for help on using the changeset viewer.