# HG changeset patch # User Peter Kovacs # 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(n2+e), but the latter one is -typically faster due to the applied early termination scheme. +run in time O(ne) and use space O(n2+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 U 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 K 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(n2e2log(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(n2+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(n2+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::max();