Changeset 1217:7bf489cf624e in lemon for lemon
- Timestamp:
- 03/16/13 13:14:35 (11 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/capacity_scaling.h
r1166 r1217 69 69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, 70 70 /// \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. 72 74 /// 73 75 /// This algorithm is typically slower than \ref CostScaling and -
lemon/concepts/bpgraph.h
r1196 r1217 998 998 /// \brief The base node of the iterator. 999 999 /// 1000 /// Returns the base node of the given incom ming arc iterator1000 /// Returns the base node of the given incoming arc iterator 1001 1001 /// (i.e. the target node of the corresponding arc). 1002 1002 Node baseNode(InArcIt) const { return INVALID; } … … 1004 1004 /// \brief The running node of the iterator. 1005 1005 /// 1006 /// Returns the running node of the given incom ming arc iterator1006 /// Returns the running node of the given incoming arc iterator 1007 1007 /// (i.e. the source node of the corresponding arc). 1008 1008 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/digraph.h
r956 r1217 410 410 /// \brief The base node of the iterator. 411 411 /// 412 /// Returns the base node of the given incom ming arc iterator412 /// Returns the base node of the given incoming arc iterator 413 413 /// (i.e. the target node of the corresponding arc). 414 414 Node baseNode(InArcIt) const { return INVALID; } … … 416 416 /// \brief The running node of the iterator. 417 417 /// 418 /// Returns the running node of the given incom ming arc iterator418 /// Returns the running node of the given incoming arc iterator 419 419 /// (i.e. the source node of the corresponding arc). 420 420 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/graph.h
r1186 r1217 758 758 /// \brief The base node of the iterator. 759 759 /// 760 /// Returns the base node of the given incom ming arc iterator760 /// Returns the base node of the given incoming arc iterator 761 761 /// (i.e. the target node of the corresponding arc). 762 762 Node baseNode(InArcIt) const { return INVALID; } … … 764 764 /// \brief The running node of the iterator. 765 765 /// 766 /// Returns the running node of the given incom ming arc iterator766 /// Returns the running node of the given incoming arc iterator 767 767 /// (i.e. the source node of the corresponding arc). 768 768 Node runningNode(InArcIt) const { return INVALID; } -
lemon/concepts/graph_components.h
r1196 r1217 876 876 void next(Arc&) const {} 877 877 878 /// \brief Return the first arc incom ming to the given node.879 /// 880 /// This function gives back the first arc incom ming to the878 /// \brief Return the first arc incoming to the given node. 879 /// 880 /// This function gives back the first arc incoming to the 881 881 /// given node. 882 882 void firstIn(Arc&, const Node&) const {} 883 883 884 /// \brief Return the next arc incom ming to the given node.885 /// 886 /// This function gives back the next arc incom ming to the884 /// \brief Return the next arc incoming to the given node. 885 /// 886 /// This function gives back the next arc incoming to the 887 887 /// given node. 888 888 void nextIn(Arc&) const {} -
lemon/cost_scaling.h
r1165 r1217 97 97 /// can be viewed as the generalization of the \ref Preflow 98 98 /// "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. 99 101 /// 100 102 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest … … 1270 1272 _buckets[r] = _bucket_next[u]; 1271 1273 1272 // Search the incom ming arcs of u1274 // Search the incoming arcs of u 1273 1275 LargeCost pi_u = _pi[u]; 1274 1276 int last_out = _first_out[u+1]; -
lemon/cycle_canceling.h
r1179 r1217 52 52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 53 53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 54 /// It runs in strongly polynomial time , but in practice, it is typically55 /// orders of magnitude slower than the scaling algorithms and56 /// \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. 57 57 /// (For more information, see \ref min_cost_flow_algs "the module page".) 58 58 /// -
lemon/hartmann_orlin_mmc.h
r1164 r1217 100 100 /// a directed cycle of minimum mean cost in a digraph 101 101 /// \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). 105 106 /// 106 107 /// \tparam GR The type of the digraph the algorithm runs on. … … 275 276 /// 276 277 /// 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 automatically278 /// \ref findCycleMean(), a local \ref Path "path" structure 279 /// will be allocated. The destuctor deallocates this automatically 279 280 /// allocated object, of course. 280 281 /// -
lemon/howard_mmc.h
r1178 r1217 283 283 /// 284 284 /// 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 automatically285 /// \ref findCycleMean(), a local \ref Path "path" structure 286 /// will be allocated. The destuctor deallocates this automatically 287 287 /// allocated object, of course. 288 288 /// -
lemon/karp_mmc.h
r1164 r1217 271 271 /// 272 272 /// 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 automatically273 /// \ref findCycleMean(), a local \ref Path "path" structure 274 /// will be allocated. The destuctor deallocates this automatically 275 275 /// allocated object, of course. 276 276 /// -
lemon/list_graph.h
r1193 r1217 446 446 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 447 447 ///invalidated for the outgoing arcs of node \c v and \c InArcIt 448 ///iterators are invalidated for the incom ming arcs of \c v.448 ///iterators are invalidated for the incoming arcs of \c v. 449 449 ///Moreover all iterators referencing node \c v or the removed 450 450 ///loops are also invalidated. Other iterators remain valid. -
lemon/network_simplex.h
r1166 r1217 1504 1504 } 1505 1505 } else { 1506 // Find the min. cost incom ming arc for each demand node1506 // Find the min. cost incoming arc for each demand node 1507 1507 for (int i = 0; i != int(demand_nodes.size()); ++i) { 1508 1508 Node v = demand_nodes[i];
Note: See TracChangeset
for help on using the changeset viewer.