# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1363436075 -3600
# Node ID 7bf489cf624efd8023bb1a9ba91302a12415fea0
# Parent dbaf21739390aee540985c2ce919f3025bff545e
Minor fixes and improvements in the doc (#459)
diff -r dbaf21739390 -r 7bf489cf624e doc/groups.dox
--- a/doc/groups.dox Fri Mar 15 17:19:17 2013 +0100
+++ b/doc/groups.dox Sat Mar 16 13:14:35 2013 +0100
@@ -392,7 +392,7 @@
This group contains the algorithms for finding minimum cost flows and
circulations \ref amo93networkflows. For more information about this
-problem and its dual solution, see \ref min_cost_flow
+problem and its dual solution, see: \ref min_cost_flow
"Minimum Cost Flow Problem".
LEMON contains several algorithms for this problem.
@@ -484,8 +484,7 @@
most efficient one, though the best known theoretical bound on its running
time is exponential.
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
-run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
-typically faster due to the applied early termination scheme.
+run in time O(ne) and use space O(n<sup>2</sup>+e).
*/
/**
diff -r dbaf21739390 -r 7bf489cf624e lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/capacity_scaling.h Sat Mar 16 13:14:35 2013 +0100
@@ -68,7 +68,9 @@
/// of the successive shortest path algorithm for finding a
/// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
/// \ref edmondskarp72theoretical. It is an efficient dual
- /// solution method.
+ /// solution method, which runs in polynomial time
+ /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
+ /// of node supply and arc capacity values.
///
/// This algorithm is typically slower than \ref CostScaling and
/// \ref NetworkSimplex, but in special cases, it can be more
diff -r dbaf21739390 -r 7bf489cf624e lemon/concepts/bpgraph.h
--- a/lemon/concepts/bpgraph.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/concepts/bpgraph.h Sat Mar 16 13:14:35 2013 +0100
@@ -997,13 +997,13 @@
/// \brief The base node of the iterator.
///
- /// Returns the base node of the given incomming arc iterator
+ /// Returns the base node of the given incoming arc iterator
/// (i.e. the target node of the corresponding arc).
Node baseNode(InArcIt) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Returns the running node of the given incomming arc iterator
+ /// Returns the running node of the given incoming arc iterator
/// (i.e. the source node of the corresponding arc).
Node runningNode(InArcIt) const { return INVALID; }
diff -r dbaf21739390 -r 7bf489cf624e lemon/concepts/digraph.h
--- a/lemon/concepts/digraph.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/concepts/digraph.h Sat Mar 16 13:14:35 2013 +0100
@@ -409,13 +409,13 @@
/// \brief The base node of the iterator.
///
- /// Returns the base node of the given incomming arc iterator
+ /// Returns the base node of the given incoming arc iterator
/// (i.e. the target node of the corresponding arc).
Node baseNode(InArcIt) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Returns the running node of the given incomming arc iterator
+ /// Returns the running node of the given incoming arc iterator
/// (i.e. the source node of the corresponding arc).
Node runningNode(InArcIt) const { return INVALID; }
diff -r dbaf21739390 -r 7bf489cf624e lemon/concepts/graph.h
--- a/lemon/concepts/graph.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/concepts/graph.h Sat Mar 16 13:14:35 2013 +0100
@@ -757,13 +757,13 @@
/// \brief The base node of the iterator.
///
- /// Returns the base node of the given incomming arc iterator
+ /// Returns the base node of the given incoming arc iterator
/// (i.e. the target node of the corresponding arc).
Node baseNode(InArcIt) const { return INVALID; }
/// \brief The running node of the iterator.
///
- /// Returns the running node of the given incomming arc iterator
+ /// Returns the running node of the given incoming arc iterator
/// (i.e. the source node of the corresponding arc).
Node runningNode(InArcIt) const { return INVALID; }
diff -r dbaf21739390 -r 7bf489cf624e lemon/concepts/graph_components.h
--- a/lemon/concepts/graph_components.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/concepts/graph_components.h Sat Mar 16 13:14:35 2013 +0100
@@ -875,15 +875,15 @@
/// This function gives back the next arc in the iteration order.
void next(Arc&) const {}
- /// \brief Return the first arc incomming to the given node.
+ /// \brief Return the first arc incoming to the given node.
///
- /// This function gives back the first arc incomming to the
+ /// This function gives back the first arc incoming to the
/// given node.
void firstIn(Arc&, const Node&) const {}
- /// \brief Return the next arc incomming to the given node.
+ /// \brief Return the next arc incoming to the given node.
///
- /// This function gives back the next arc incomming to the
+ /// This function gives back the next arc incoming to the
/// given node.
void nextIn(Arc&) const {}
diff -r dbaf21739390 -r 7bf489cf624e lemon/cost_scaling.h
--- a/lemon/cost_scaling.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/cost_scaling.h Sat Mar 16 13:14:35 2013 +0100
@@ -96,6 +96,8 @@
/// It is a highly efficient primal-dual solution method, which
/// can be viewed as the generalization of the \ref Preflow
/// "preflow push-relabel" algorithm for the maximum flow problem.
+ /// It is a polynomial algorithm, its running time complexity is
+ /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
///
/// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
/// implementations available in LEMON for solving this problem.
@@ -1269,7 +1271,7 @@
int u = _buckets[r];
_buckets[r] = _bucket_next[u];
- // Search the incomming arcs of u
+ // Search the incoming arcs of u
LargeCost pi_u = _pi[u];
int last_out = _first_out[u+1];
for (int a = _first_out[u]; a != last_out; ++a) {
diff -r dbaf21739390 -r 7bf489cf624e lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/cycle_canceling.h Sat Mar 16 13:14:35 2013 +0100
@@ -51,9 +51,9 @@
/// \ref goldberg89cyclecanceling.
/// The most efficent one is the \ref CANCEL_AND_TIGHTEN
/// "Cancel-and-Tighten" algorithm, thus it is the default method.
- /// It runs in strongly polynomial time, but in practice, it is typically
- /// orders of magnitude slower than the scaling algorithms and
- /// \ref NetworkSimplex.
+ /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
+ /// but in practice, it is typically orders of magnitude slower than
+ /// the scaling algorithms and \ref NetworkSimplex.
/// (For more information, see \ref min_cost_flow_algs "the module page".)
///
/// Most of the parameters of the problem (except for the digraph)
diff -r dbaf21739390 -r 7bf489cf624e lemon/hartmann_orlin_mmc.h
--- a/lemon/hartmann_orlin_mmc.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/hartmann_orlin_mmc.h Sat Mar 16 13:14:35 2013 +0100
@@ -99,9 +99,10 @@
/// This class implements the Hartmann-Orlin algorithm for finding
/// a directed cycle of minimum mean cost in a digraph
/// \ref hartmann93finding, \ref dasdan98minmeancycle.
- /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
- /// it applies an efficient early termination scheme.
- /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
+ /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
+ /// applies an early termination scheme. It makes the algorithm
+ /// significantly faster for some problem instances, but slower for others.
+ /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
///
/// \tparam GR The type of the digraph the algorithm runs on.
/// \tparam CM The type of the cost map. The default
@@ -274,8 +275,8 @@
/// found cycle.
///
/// If you don't call this function before calling \ref run() or
- /// \ref findCycleMean(), it will allocate a local \ref Path "path"
- /// structure. The destuctor deallocates this automatically
+ /// \ref findCycleMean(), a local \ref Path "path" structure
+ /// will be allocated. The destuctor deallocates this automatically
/// allocated object, of course.
///
/// \note The algorithm calls only the \ref lemon::Path::addFront()
diff -r dbaf21739390 -r 7bf489cf624e lemon/howard_mmc.h
--- a/lemon/howard_mmc.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/howard_mmc.h Sat Mar 16 13:14:35 2013 +0100
@@ -282,8 +282,8 @@
/// found cycle.
///
/// If you don't call this function before calling \ref run() or
- /// \ref findCycleMean(), it will allocate a local \ref Path "path"
- /// structure. The destuctor deallocates this automatically
+ /// \ref findCycleMean(), a local \ref Path "path" structure
+ /// will be allocated. The destuctor deallocates this automatically
/// allocated object, of course.
///
/// \note The algorithm calls only the \ref lemon::Path::addBack()
diff -r dbaf21739390 -r 7bf489cf624e lemon/karp_mmc.h
--- a/lemon/karp_mmc.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/karp_mmc.h Sat Mar 16 13:14:35 2013 +0100
@@ -270,8 +270,8 @@
/// found cycle.
///
/// If you don't call this function before calling \ref run() or
- /// \ref findCycleMean(), it will allocate a local \ref Path "path"
- /// structure. The destuctor deallocates this automatically
+ /// \ref findCycleMean(), a local \ref Path "path" structure
+ /// will be allocated. The destuctor deallocates this automatically
/// allocated object, of course.
///
/// \note The algorithm calls only the \ref lemon::Path::addFront()
diff -r dbaf21739390 -r 7bf489cf624e lemon/list_graph.h
--- a/lemon/list_graph.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/list_graph.h Sat Mar 16 13:14:35 2013 +0100
@@ -445,7 +445,7 @@
///\note The moved arcs are joined to node \c u using changeSource()
///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
///invalidated for the outgoing arcs of node \c v and \c InArcIt
- ///iterators are invalidated for the incomming arcs of \c v.
+ ///iterators are invalidated for the incoming arcs of \c v.
///Moreover all iterators referencing node \c v or the removed
///loops are also invalidated. Other iterators remain valid.
///
diff -r dbaf21739390 -r 7bf489cf624e lemon/network_simplex.h
--- a/lemon/network_simplex.h Fri Mar 15 17:19:17 2013 +0100
+++ b/lemon/network_simplex.h Sat Mar 16 13:14:35 2013 +0100
@@ -1503,7 +1503,7 @@
}
}
} else {
- // Find the min. cost incomming arc for each demand node
+ // Find the min. cost incoming arc for each demand node
for (int i = 0; i != int(demand_nodes.size()); ++i) {
Node v = demand_nodes[i];
Cost c, min_cost = std::numeric_limits<Cost>::max();