author Peter Kovacs Sat, 16 Mar 2013 13:14:35 +0100 changeset 1217 7bf489cf624e parent 1216 dbaf21739390 child 1218 d9d1cb759951
Minor fixes and improvements in the doc (#459)
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/capacity_scaling.h file | annotate | diff | comparison | revisions lemon/concepts/bpgraph.h file | annotate | diff | comparison | revisions lemon/concepts/digraph.h file | annotate | diff | comparison | revisions lemon/concepts/graph.h file | annotate | diff | comparison | revisions lemon/concepts/graph_components.h file | annotate | diff | comparison | revisions lemon/cost_scaling.h file | annotate | diff | comparison | revisions lemon/cycle_canceling.h file | annotate | diff | comparison | revisions lemon/hartmann_orlin_mmc.h file | annotate | diff | comparison | revisions lemon/howard_mmc.h file | annotate | diff | comparison | revisions lemon/karp_mmc.h file | annotate | diff | comparison | revisions lemon/list_graph.h file | annotate | diff | comparison | revisions lemon/network_simplex.h file | annotate | diff | comparison | revisions
     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.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.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();