COIN-OR::LEMON - Graph Library

Changeset 1217:7bf489cf624e in lemon for 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)

Location:
lemon
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • 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.