Minor fixes and improvements in the doc (#459)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 13:14:35 +0100
changeset 10497bf489cf624e
parent 1048 dbaf21739390
child 1050 d9d1cb759951
Minor fixes and improvements in the doc (#459)
doc/groups.dox
lemon/capacity_scaling.h
lemon/concepts/bpgraph.h
lemon/concepts/digraph.h
lemon/concepts/graph.h
lemon/concepts/graph_components.h
lemon/cost_scaling.h
lemon/cycle_canceling.h
lemon/hartmann_orlin_mmc.h
lemon/howard_mmc.h
lemon/karp_mmc.h
lemon/list_graph.h
lemon/network_simplex.h
     1.1 --- a/doc/groups.dox	Fri Mar 15 17:19:17 2013 +0100
     1.2 +++ b/doc/groups.dox	Sat Mar 16 13:14:35 2013 +0100
     1.3 @@ -392,7 +392,7 @@
     1.4  
     1.5  This group contains the algorithms for finding minimum cost flows and
     1.6  circulations \ref amo93networkflows. For more information about this
     1.7 -problem and its dual solution, see \ref min_cost_flow
     1.8 +problem and its dual solution, see: \ref min_cost_flow
     1.9  "Minimum Cost Flow Problem".
    1.10  
    1.11  LEMON contains several algorithms for this problem.
    1.12 @@ -484,8 +484,7 @@
    1.13  most efficient one, though the best known theoretical bound on its running
    1.14  time is exponential.
    1.15  Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    1.16 -run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    1.17 -typically faster due to the applied early termination scheme.
    1.18 +run in time O(ne) and use space O(n<sup>2</sup>+e).
    1.19  */
    1.20  
    1.21  /**
     2.1 --- a/lemon/capacity_scaling.h	Fri Mar 15 17:19:17 2013 +0100
     2.2 +++ b/lemon/capacity_scaling.h	Sat Mar 16 13:14:35 2013 +0100
     2.3 @@ -68,7 +68,9 @@
     2.4    /// of the successive shortest path algorithm for finding a
     2.5    /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
     2.6    /// \ref edmondskarp72theoretical. It is an efficient dual
     2.7 -  /// solution method.
     2.8 +  /// solution method, which runs in polynomial time
     2.9 +  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
    2.10 +  /// of node supply and arc capacity values.
    2.11    ///
    2.12    /// This algorithm is typically slower than \ref CostScaling and
    2.13    /// \ref NetworkSimplex, but in special cases, it can be more
     3.1 --- a/lemon/concepts/bpgraph.h	Fri Mar 15 17:19:17 2013 +0100
     3.2 +++ b/lemon/concepts/bpgraph.h	Sat Mar 16 13:14:35 2013 +0100
     3.3 @@ -997,13 +997,13 @@
     3.4  
     3.5        /// \brief The base node of the iterator.
     3.6        ///
     3.7 -      /// Returns the base node of the given incomming arc iterator
     3.8 +      /// Returns the base node of the given incoming arc iterator
     3.9        /// (i.e. the target node of the corresponding arc).
    3.10        Node baseNode(InArcIt) const { return INVALID; }
    3.11  
    3.12        /// \brief The running node of the iterator.
    3.13        ///
    3.14 -      /// Returns the running node of the given incomming arc iterator
    3.15 +      /// Returns the running node of the given incoming arc iterator
    3.16        /// (i.e. the source node of the corresponding arc).
    3.17        Node runningNode(InArcIt) const { return INVALID; }
    3.18  
     4.1 --- a/lemon/concepts/digraph.h	Fri Mar 15 17:19:17 2013 +0100
     4.2 +++ b/lemon/concepts/digraph.h	Sat Mar 16 13:14:35 2013 +0100
     4.3 @@ -409,13 +409,13 @@
     4.4  
     4.5        /// \brief The base node of the iterator.
     4.6        ///
     4.7 -      /// Returns the base node of the given incomming arc iterator
     4.8 +      /// Returns the base node of the given incoming arc iterator
     4.9        /// (i.e. the target node of the corresponding arc).
    4.10        Node baseNode(InArcIt) const { return INVALID; }
    4.11  
    4.12        /// \brief The running node of the iterator.
    4.13        ///
    4.14 -      /// Returns the running node of the given incomming arc iterator
    4.15 +      /// Returns the running node of the given incoming arc iterator
    4.16        /// (i.e. the source node of the corresponding arc).
    4.17        Node runningNode(InArcIt) const { return INVALID; }
    4.18  
     5.1 --- a/lemon/concepts/graph.h	Fri Mar 15 17:19:17 2013 +0100
     5.2 +++ b/lemon/concepts/graph.h	Sat Mar 16 13:14:35 2013 +0100
     5.3 @@ -757,13 +757,13 @@
     5.4  
     5.5        /// \brief The base node of the iterator.
     5.6        ///
     5.7 -      /// Returns the base node of the given incomming arc iterator
     5.8 +      /// Returns the base node of the given incoming arc iterator
     5.9        /// (i.e. the target node of the corresponding arc).
    5.10        Node baseNode(InArcIt) const { return INVALID; }
    5.11  
    5.12        /// \brief The running node of the iterator.
    5.13        ///
    5.14 -      /// Returns the running node of the given incomming arc iterator
    5.15 +      /// Returns the running node of the given incoming arc iterator
    5.16        /// (i.e. the source node of the corresponding arc).
    5.17        Node runningNode(InArcIt) const { return INVALID; }
    5.18  
     6.1 --- a/lemon/concepts/graph_components.h	Fri Mar 15 17:19:17 2013 +0100
     6.2 +++ b/lemon/concepts/graph_components.h	Sat Mar 16 13:14:35 2013 +0100
     6.3 @@ -875,15 +875,15 @@
     6.4        /// This function gives back the next arc in the iteration order.
     6.5        void next(Arc&) const {}
     6.6  
     6.7 -      /// \brief Return the first arc incomming to the given node.
     6.8 +      /// \brief Return the first arc incoming to the given node.
     6.9        ///
    6.10 -      /// This function gives back the first arc incomming to the
    6.11 +      /// This function gives back the first arc incoming to the
    6.12        /// given node.
    6.13        void firstIn(Arc&, const Node&) const {}
    6.14  
    6.15 -      /// \brief Return the next arc incomming to the given node.
    6.16 +      /// \brief Return the next arc incoming to the given node.
    6.17        ///
    6.18 -      /// This function gives back the next arc incomming to the
    6.19 +      /// This function gives back the next arc incoming to the
    6.20        /// given node.
    6.21        void nextIn(Arc&) const {}
    6.22  
     7.1 --- a/lemon/cost_scaling.h	Fri Mar 15 17:19:17 2013 +0100
     7.2 +++ b/lemon/cost_scaling.h	Sat Mar 16 13:14:35 2013 +0100
     7.3 @@ -96,6 +96,8 @@
     7.4    /// It is a highly efficient primal-dual solution method, which
     7.5    /// can be viewed as the generalization of the \ref Preflow
     7.6    /// "preflow push-relabel" algorithm for the maximum flow problem.
     7.7 +  /// It is a polynomial algorithm, its running time complexity is
     7.8 +  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
     7.9    ///
    7.10    /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    7.11    /// implementations available in LEMON for solving this problem.
    7.12 @@ -1269,7 +1271,7 @@
    7.13            int u = _buckets[r];
    7.14            _buckets[r] = _bucket_next[u];
    7.15  
    7.16 -          // Search the incomming arcs of u
    7.17 +          // Search the incoming arcs of u
    7.18            LargeCost pi_u = _pi[u];
    7.19            int last_out = _first_out[u+1];
    7.20            for (int a = _first_out[u]; a != last_out; ++a) {
     8.1 --- a/lemon/cycle_canceling.h	Fri Mar 15 17:19:17 2013 +0100
     8.2 +++ b/lemon/cycle_canceling.h	Sat Mar 16 13:14:35 2013 +0100
     8.3 @@ -51,9 +51,9 @@
     8.4    /// \ref goldberg89cyclecanceling.
     8.5    /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
     8.6    /// "Cancel-and-Tighten" algorithm, thus it is the default method.
     8.7 -  /// It runs in strongly polynomial time, but in practice, it is typically
     8.8 -  /// orders of magnitude slower than the scaling algorithms and
     8.9 -  /// \ref NetworkSimplex.
    8.10 +  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
    8.11 +  /// but in practice, it is typically orders of magnitude slower than
    8.12 +  /// the scaling algorithms and \ref NetworkSimplex.
    8.13    /// (For more information, see \ref min_cost_flow_algs "the module page".)
    8.14    ///
    8.15    /// Most of the parameters of the problem (except for the digraph)
     9.1 --- a/lemon/hartmann_orlin_mmc.h	Fri Mar 15 17:19:17 2013 +0100
     9.2 +++ b/lemon/hartmann_orlin_mmc.h	Sat Mar 16 13:14:35 2013 +0100
     9.3 @@ -99,9 +99,10 @@
     9.4    /// This class implements the Hartmann-Orlin algorithm for finding
     9.5    /// a directed cycle of minimum mean cost in a digraph
     9.6    /// \ref hartmann93finding, \ref dasdan98minmeancycle.
     9.7 -  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
     9.8 -  /// it applies an efficient early termination scheme.
     9.9 -  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    9.10 +  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
    9.11 +  /// applies an early termination scheme. It makes the algorithm
    9.12 +  /// significantly faster for some problem instances, but slower for others.
    9.13 +  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    9.14    ///
    9.15    /// \tparam GR The type of the digraph the algorithm runs on.
    9.16    /// \tparam CM The type of the cost map. The default
    9.17 @@ -274,8 +275,8 @@
    9.18      /// found cycle.
    9.19      ///
    9.20      /// If you don't call this function before calling \ref run() or
    9.21 -    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    9.22 -    /// structure. The destuctor deallocates this automatically
    9.23 +    /// \ref findCycleMean(), a local \ref Path "path" structure
    9.24 +    /// will be allocated. The destuctor deallocates this automatically
    9.25      /// allocated object, of course.
    9.26      ///
    9.27      /// \note The algorithm calls only the \ref lemon::Path::addFront()
    10.1 --- a/lemon/howard_mmc.h	Fri Mar 15 17:19:17 2013 +0100
    10.2 +++ b/lemon/howard_mmc.h	Sat Mar 16 13:14:35 2013 +0100
    10.3 @@ -282,8 +282,8 @@
    10.4      /// found cycle.
    10.5      ///
    10.6      /// If you don't call this function before calling \ref run() or
    10.7 -    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    10.8 -    /// structure. The destuctor deallocates this automatically
    10.9 +    /// \ref findCycleMean(), a local \ref Path "path" structure
   10.10 +    /// will be allocated. The destuctor deallocates this automatically
   10.11      /// allocated object, of course.
   10.12      ///
   10.13      /// \note The algorithm calls only the \ref lemon::Path::addBack()
    11.1 --- a/lemon/karp_mmc.h	Fri Mar 15 17:19:17 2013 +0100
    11.2 +++ b/lemon/karp_mmc.h	Sat Mar 16 13:14:35 2013 +0100
    11.3 @@ -270,8 +270,8 @@
    11.4      /// found cycle.
    11.5      ///
    11.6      /// If you don't call this function before calling \ref run() or
    11.7 -    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    11.8 -    /// structure. The destuctor deallocates this automatically
    11.9 +    /// \ref findCycleMean(), a local \ref Path "path" structure
   11.10 +    /// will be allocated. The destuctor deallocates this automatically
   11.11      /// allocated object, of course.
   11.12      ///
   11.13      /// \note The algorithm calls only the \ref lemon::Path::addFront()
    12.1 --- a/lemon/list_graph.h	Fri Mar 15 17:19:17 2013 +0100
    12.2 +++ b/lemon/list_graph.h	Sat Mar 16 13:14:35 2013 +0100
    12.3 @@ -445,7 +445,7 @@
    12.4      ///\note The moved arcs are joined to node \c u using changeSource()
    12.5      ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
    12.6      ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    12.7 -    ///iterators are invalidated for the incomming arcs of \c v.
    12.8 +    ///iterators are invalidated for the incoming arcs of \c v.
    12.9      ///Moreover all iterators referencing node \c v or the removed
   12.10      ///loops are also invalidated. Other iterators remain valid.
   12.11      ///
    13.1 --- a/lemon/network_simplex.h	Fri Mar 15 17:19:17 2013 +0100
    13.2 +++ b/lemon/network_simplex.h	Sat Mar 16 13:14:35 2013 +0100
    13.3 @@ -1503,7 +1503,7 @@
    13.4              }
    13.5            }
    13.6          } else {
    13.7 -          // Find the min. cost incomming arc for each demand node
    13.8 +          // Find the min. cost incoming arc for each demand node
    13.9            for (int i = 0; i != int(demand_nodes.size()); ++i) {
   13.10              Node v = demand_nodes[i];
   13.11              Cost c, min_cost = std::numeric_limits<Cost>::max();