Changeset 1049:7bf489cf624e in lemon-main
- Timestamp:
- 03/16/13 13:14:35 (12 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 13 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1038 r1049 393 393 This group contains the algorithms for finding minimum cost flows and 394 394 circulations \ref amo93networkflows. For more information about this 395 problem and its dual solution, see \ref min_cost_flow395 problem and its dual solution, see: \ref min_cost_flow 396 396 "Minimum Cost Flow Problem". 397 397 … … 485 485 time is exponential. 486 486 Both \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. 487 run in time O(ne) and use space O(n<sup>2</sup>+e). 489 488 */ 490 489 -
lemon/capacity_scaling.h
r1004 r1049 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
r1028 r1049 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
r877 r1049 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
r1018 r1049 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
r1028 r1049 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
r1003 r1049 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
r1013 r1049 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
r1002 r1049 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
r1012 r1049 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
r1002 r1049 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
r1025 r1049 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
r1004 r1049 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.