# Changeset 1217:7bf489cf624e in lemon

Ignore:
Timestamp:
03/16/13 13:14:35 (7 years ago)
Branch:
default
Phase:
public
Message:

Minor fixes and improvements in the doc (#459)

Files:
13 edited

Unmodified
Removed
• ## doc/groups.dox

 r1206 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". 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). */
• ## lemon/capacity_scaling.h

 r1166 /// \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
• ## lemon/concepts/bpgraph.h

 r1196 /// \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; }
• ## lemon/concepts/digraph.h

 r956 /// \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; }
• ## lemon/concepts/graph.h

 r1186 /// \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; }
• ## lemon/concepts/graph_components.h

 r1196 void next(Arc&) const {} /// \brief Return the first arc incomming to the given node. /// /// This function gives back the first arc incomming to the /// \brief Return the first arc incoming to the given node. /// /// 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. /// /// This function gives back the next arc incomming to the /// \brief Return the next arc incoming to the given node. /// /// This function gives back the next arc incoming to the /// given node. void nextIn(Arc&) const {}
• ## lemon/cost_scaling.h

 r1165 /// 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 _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];
• ## lemon/cycle_canceling.h

 r1179 /// 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".) ///
• ## lemon/hartmann_orlin_mmc.h

 r1164 /// 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. /// /// 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. ///
• ## lemon/howard_mmc.h

 r1178 /// /// 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. ///
• ## lemon/karp_mmc.h

 r1164 /// /// 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. ///
• ## lemon/list_graph.h

 r1193 ///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.
• ## lemon/network_simplex.h

 r1166 } } 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];
Note: See TracChangeset for help on using the changeset viewer.