1.1 --- a/lemon/capacity_scaling.h Fri Feb 29 15:55:39 2008 +0000
1.2 +++ b/lemon/capacity_scaling.h Fri Feb 29 15:57:52 2008 +0000
1.3 @@ -25,8 +25,6 @@
1.4 /// \brief Capacity scaling algorithm for finding a minimum cost flow.
1.5
1.6 #include <vector>
1.7 -
1.8 -#include <lemon/graph_adaptor.h>
1.9 #include <lemon/bin_heap.h>
1.10
1.11 namespace lemon {
1.12 @@ -90,9 +88,6 @@
1.13 /// distance of the nodes.
1.14 class ResidualDijkstra
1.15 {
1.16 - typedef typename Graph::template NodeMap<Cost> CostNodeMap;
1.17 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.18 -
1.19 typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.20 typedef BinHeap<Cost, HeapCrossRef> Heap;
1.21
1.22 @@ -109,7 +104,7 @@
1.23 PotentialMap &_potential;
1.24
1.25 // The distance map
1.26 - CostNodeMap _dist;
1.27 + PotentialMap _dist;
1.28 // The pred edge map
1.29 PredMap &_pred;
1.30 // The processed (i.e. permanently labeled) nodes
1.31 @@ -131,7 +126,7 @@
1.32 {}
1.33
1.34 /// Runs the algorithm from the given source node.
1.35 - Node run(Node s, Capacity delta) {
1.36 + Node run(Node s, Capacity delta = 1) {
1.37 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
1.38 Heap heap(heap_cross_ref);
1.39 heap.push(s, 0);
1.40 @@ -454,18 +449,18 @@
1.41 return *_potential;
1.42 }
1.43
1.44 - /// \brief Returns the flow on the edge.
1.45 + /// \brief Returns the flow on the given edge.
1.46 ///
1.47 - /// Returns the flow on the edge.
1.48 + /// Returns the flow on the given edge.
1.49 ///
1.50 /// \pre \ref run() must be called before using this function.
1.51 Capacity flow(const Edge& edge) const {
1.52 return (*_flow)[edge];
1.53 }
1.54
1.55 - /// \brief Returns the potential of the node.
1.56 + /// \brief Returns the potential of the given node.
1.57 ///
1.58 - /// Returns the potential of the node.
1.59 + /// Returns the potential of the given node.
1.60 ///
1.61 /// \pre \ref run() must be called before using this function.
1.62 Cost potential(const Node& node) const {
1.63 @@ -517,7 +512,11 @@
1.64 if ( _supply[n] > max_sup) max_sup = _supply[n];
1.65 if (-_supply[n] > max_dem) max_dem = -_supply[n];
1.66 }
1.67 - if (max_dem < max_sup) max_sup = max_dem;
1.68 + Capacity max_cap = 0;
1.69 + for (EdgeIt e(_graph); e != INVALID; ++e) {
1.70 + if (_capacity[e] > max_cap) max_cap = _capacity[e];
1.71 + }
1.72 + max_sup = std::min(std::min(max_sup, max_dem), max_cap);
1.73 _phase_num = 0;
1.74 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
1.75 ++_phase_num;
1.76 @@ -595,7 +594,7 @@
1.77 }
1.78
1.79 // Augmenting along a shortest path from s to t.
1.80 - Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
1.81 + Capacity d = std::min(_excess[s], -_excess[t]);
1.82 Node u = t;
1.83 Edge e;
1.84 if (d > _delta) {
1.85 @@ -657,23 +656,24 @@
1.86 {
1.87 // Running Dijkstra
1.88 s = _excess_nodes[next_node];
1.89 - if ((t = _dijkstra->run(s, 1)) == INVALID)
1.90 - return false;
1.91 + if ((t = _dijkstra->run(s)) == INVALID) break;
1.92
1.93 // Augmenting along a shortest path from s to t
1.94 - Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
1.95 + Capacity d = std::min(_excess[s], -_excess[t]);
1.96 Node u = t;
1.97 Edge e;
1.98 - while ((e = _pred[u]) != INVALID) {
1.99 - Capacity rc;
1.100 - if (u == _graph.target(e)) {
1.101 - rc = _res_cap[e];
1.102 - u = _graph.source(e);
1.103 - } else {
1.104 - rc = (*_flow)[e];
1.105 - u = _graph.target(e);
1.106 + if (d > 1) {
1.107 + while ((e = _pred[u]) != INVALID) {
1.108 + Capacity rc;
1.109 + if (u == _graph.target(e)) {
1.110 + rc = _res_cap[e];
1.111 + u = _graph.source(e);
1.112 + } else {
1.113 + rc = (*_flow)[e];
1.114 + u = _graph.target(e);
1.115 + }
1.116 + if (rc < d) d = rc;
1.117 }
1.118 - if (rc < d) d = rc;
1.119 }
1.120 u = t;
1.121 while ((e = _pred[u]) != INVALID) {
2.1 --- a/lemon/cost_scaling.h Fri Feb 29 15:55:39 2008 +0000
2.2 +++ b/lemon/cost_scaling.h Fri Feb 29 15:57:52 2008 +0000
2.3 @@ -399,18 +399,18 @@
2.4 return *_potential;
2.5 }
2.6
2.7 - /// \brief Returns the flow on the edge.
2.8 + /// \brief Returns the flow on the given edge.
2.9 ///
2.10 - /// Returns the flow on the edge.
2.11 + /// Returns the flow on the given edge.
2.12 ///
2.13 /// \pre \ref run() must be called before using this function.
2.14 Capacity flow(const Edge& edge) const {
2.15 return (*_flow)[edge];
2.16 }
2.17
2.18 - /// \brief Returns the potential of the node.
2.19 + /// \brief Returns the potential of the given node.
2.20 ///
2.21 - /// Returns the potential of the node.
2.22 + /// Returns the potential of the given node.
2.23 ///
2.24 /// \pre \ref run() must be called before using this function.
2.25 Cost potential(const Node& node) const {
3.1 --- a/lemon/cycle_canceling.h Fri Feb 29 15:55:39 2008 +0000
3.2 +++ b/lemon/cycle_canceling.h Fri Feb 29 15:57:52 2008 +0000
3.3 @@ -355,18 +355,18 @@
3.4 return *_potential;
3.5 }
3.6
3.7 - /// \brief Returns the flow on the edge.
3.8 + /// \brief Returns the flow on the given edge.
3.9 ///
3.10 - /// Returns the flow on the edge.
3.11 + /// Returns the flow on the given edge.
3.12 ///
3.13 /// \pre \ref run() must be called before using this function.
3.14 Capacity flow(const Edge& edge) const {
3.15 return (*_flow)[edge];
3.16 }
3.17
3.18 - /// \brief Returns the potential of the node.
3.19 + /// \brief Returns the potential of the given node.
3.20 ///
3.21 - /// Returns the potential of the node.
3.22 + /// Returns the potential of the given node.
3.23 ///
3.24 /// \pre \ref run() must be called before using this function.
3.25 Cost potential(const Node& node) const {
4.1 --- a/lemon/min_cost_flow.h Fri Feb 29 15:55:39 2008 +0000
4.2 +++ b/lemon/min_cost_flow.h Fri Feb 29 15:57:52 2008 +0000
4.3 @@ -44,10 +44,10 @@
4.4 ///
4.5 /// There are four implementations for the minimum cost flow problem,
4.6 /// which can be used exactly the same way.
4.7 - /// - \ref CapacityScaling The capacity scaling algorithm.
4.8 - /// - \ref CostScaling The cost scaling algorithm.
4.9 - /// - \ref CycleCanceling A cycle-canceling algorithm.
4.10 - /// - \ref NetworkSimplex The network simplex algorithm.
4.11 + /// - \ref CapacityScaling
4.12 + /// - \ref CostScaling
4.13 + /// - \ref CycleCanceling
4.14 + /// - \ref NetworkSimplex
4.15 ///
4.16 /// \tparam Graph The directed graph type the algorithm runs on.
4.17 /// \tparam LowerMap The type of the lower bound map.
5.1 --- a/lemon/min_mean_cycle.h Fri Feb 29 15:55:39 2008 +0000
5.2 +++ b/lemon/min_mean_cycle.h Fri Feb 29 15:57:52 2008 +0000
5.3 @@ -134,7 +134,8 @@
5.4 }
5.5
5.6 /// \name Execution control
5.7 - /// The simplest way to execute the algorithm is to call run().
5.8 + /// The simplest way to execute the algorithm is to call the run()
5.9 + /// function.
5.10 /// \n
5.11 /// If you only need the minimum mean value, you may call init()
5.12 /// and findMinMean().
5.13 @@ -237,7 +238,7 @@
5.14 /// \name Query Functions
5.15 /// The result of the algorithm can be obtained using these
5.16 /// functions.
5.17 - /// \n run() must be called before using them.
5.18 + /// \n The algorithm should be executed before using them.
5.19
5.20 /// @{
5.21
6.1 --- a/lemon/network_simplex.h Fri Feb 29 15:55:39 2008 +0000
6.2 +++ b/lemon/network_simplex.h Fri Feb 29 15:57:52 2008 +0000
6.3 @@ -776,18 +776,18 @@
6.4 return *_potential_result;
6.5 }
6.6
6.7 - /// \brief Returns the flow on the edge.
6.8 + /// \brief Returns the flow on the given edge.
6.9 ///
6.10 - /// Returns the flow on the edge.
6.11 + /// Returns the flow on the given edge.
6.12 ///
6.13 /// \pre \ref run() must be called before using this function.
6.14 Capacity flow(const typename Graph::Edge& edge) const {
6.15 return (*_flow_result)[edge];
6.16 }
6.17
6.18 - /// \brief Returns the potential of the node.
6.19 + /// \brief Returns the potential of the given node.
6.20 ///
6.21 - /// Returns the potential of the node.
6.22 + /// Returns the potential of the given node.
6.23 ///
6.24 /// \pre \ref run() must be called before using this function.
6.25 Cost potential(const typename Graph::Node& node) const {