COIN-OR::LEMON - Graph Library

Changeset 1217:7bf489cf624e in lemon


Ignore:
Timestamp:
03/16/13 13:14:35 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Minor fixes and improvements in the doc (#459)

Files:
13 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1206 r1217  
    393393This group contains the algorithms for finding minimum cost flows and
    394394circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     395problem and its dual solution, see: \ref min_cost_flow
    396396"Minimum Cost Flow Problem".
    397397
     
    485485time is exponential.
    486486Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    487 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    488 typically faster due to the applied early termination scheme.
     487run in time O(ne) and use space O(n<sup>2</sup>+e).
    489488*/
    490489
  • lemon/capacity_scaling.h

    r1166 r1217  
    6969  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    7070  /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
    7274  ///
    7375  /// This algorithm is typically slower than \ref CostScaling and
  • lemon/concepts/bpgraph.h

    r1196 r1217  
    998998      /// \brief The base node of the iterator.
    999999      ///
    1000       /// Returns the base node of the given incomming arc iterator
     1000      /// Returns the base node of the given incoming arc iterator
    10011001      /// (i.e. the target node of the corresponding arc).
    10021002      Node baseNode(InArcIt) const { return INVALID; }
     
    10041004      /// \brief The running node of the iterator.
    10051005      ///
    1006       /// Returns the running node of the given incomming arc iterator
     1006      /// Returns the running node of the given incoming arc iterator
    10071007      /// (i.e. the source node of the corresponding arc).
    10081008      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/digraph.h

    r956 r1217  
    410410      /// \brief The base node of the iterator.
    411411      ///
    412       /// Returns the base node of the given incomming arc iterator
     412      /// Returns the base node of the given incoming arc iterator
    413413      /// (i.e. the target node of the corresponding arc).
    414414      Node baseNode(InArcIt) const { return INVALID; }
     
    416416      /// \brief The running node of the iterator.
    417417      ///
    418       /// Returns the running node of the given incomming arc iterator
     418      /// Returns the running node of the given incoming arc iterator
    419419      /// (i.e. the source node of the corresponding arc).
    420420      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r1186 r1217  
    758758      /// \brief The base node of the iterator.
    759759      ///
    760       /// Returns the base node of the given incomming arc iterator
     760      /// Returns the base node of the given incoming arc iterator
    761761      /// (i.e. the target node of the corresponding arc).
    762762      Node baseNode(InArcIt) const { return INVALID; }
     
    764764      /// \brief The running node of the iterator.
    765765      ///
    766       /// Returns the running node of the given incomming arc iterator
     766      /// Returns the running node of the given incoming arc iterator
    767767      /// (i.e. the source node of the corresponding arc).
    768768      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1196 r1217  
    876876      void next(Arc&) const {}
    877877
    878       /// \brief Return the first arc incomming to the given node.
    879       ///
    880       /// This function gives back the first arc incomming to the
     878      /// \brief Return the first arc incoming to the given node.
     879      ///
     880      /// This function gives back the first arc incoming to the
    881881      /// given node.
    882882      void firstIn(Arc&, const Node&) const {}
    883883
    884       /// \brief Return the next arc incomming to the given node.
    885       ///
    886       /// This function gives back the next arc incomming to the
     884      /// \brief Return the next arc incoming to the given node.
     885      ///
     886      /// This function gives back the next arc incoming to the
    887887      /// given node.
    888888      void nextIn(Arc&) const {}
  • lemon/cost_scaling.h

    r1165 r1217  
    9797  /// can be viewed as the generalization of the \ref Preflow
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
     99  /// It is a polynomial algorithm, its running time complexity is
     100  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99101  ///
    100102  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     
    12701272          _buckets[r] = _bucket_next[u];
    12711273
    1272           // Search the incomming arcs of u
     1274          // Search the incoming arcs of u
    12731275          LargeCost pi_u = _pi[u];
    12741276          int last_out = _first_out[u+1];
  • lemon/cycle_canceling.h

    r1179 r1217  
    5252  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    5353  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time, but in practice, it is typically
    55   /// orders of magnitude slower than the scaling algorithms and
    56   /// \ref NetworkSimplex.
     54  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
    5757  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5858  ///
  • lemon/hartmann_orlin_mmc.h

    r1164 r1217  
    100100  /// a directed cycle of minimum mean cost in a digraph
    101101  /// \ref hartmann93finding, \ref dasdan98minmeancycle.
    102   /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103   /// it applies an efficient early termination scheme.
    104   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
     102  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
     103  /// applies an early termination scheme. It makes the algorithm
     104  /// significantly faster for some problem instances, but slower for others.
     105  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    105106  ///
    106107  /// \tparam GR The type of the digraph the algorithm runs on.
     
    275276    ///
    276277    /// If you don't call this function before calling \ref run() or
    277     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    278     /// structure. The destuctor deallocates this automatically
     278    /// \ref findCycleMean(), a local \ref Path "path" structure
     279    /// will be allocated. The destuctor deallocates this automatically
    279280    /// allocated object, of course.
    280281    ///
  • lemon/howard_mmc.h

    r1178 r1217  
    283283    ///
    284284    /// If you don't call this function before calling \ref run() or
    285     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    286     /// structure. The destuctor deallocates this automatically
     285    /// \ref findCycleMean(), a local \ref Path "path" structure
     286    /// will be allocated. The destuctor deallocates this automatically
    287287    /// allocated object, of course.
    288288    ///
  • lemon/karp_mmc.h

    r1164 r1217  
    271271    ///
    272272    /// If you don't call this function before calling \ref run() or
    273     /// \ref findCycleMean(), it will allocate a local \ref Path "path"
    274     /// structure. The destuctor deallocates this automatically
     273    /// \ref findCycleMean(), a local \ref Path "path" structure
     274    /// will be allocated. The destuctor deallocates this automatically
    275275    /// allocated object, of course.
    276276    ///
  • lemon/list_graph.h

    r1193 r1217  
    446446    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
    447447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    448     ///iterators are invalidated for the incomming arcs of \c v.
     448    ///iterators are invalidated for the incoming arcs of \c v.
    449449    ///Moreover all iterators referencing node \c v or the removed
    450450    ///loops are also invalidated. Other iterators remain valid.
  • lemon/network_simplex.h

    r1166 r1217  
    15041504          }
    15051505        } else {
    1506           // Find the min. cost incomming arc for each demand node
     1506          // Find the min. cost incoming arc for each demand node
    15071507          for (int i = 0; i != int(demand_nodes.size()); ++i) {
    15081508            Node v = demand_nodes[i];
Note: See TracChangeset for help on using the changeset viewer.