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();