# HG changeset patch
# User kpeter
# Date 1204300672 0
# Node ID 4d3bc1d04c1d0299817d8e5ade93ab4c779824f5
# Parent 061be2e64ecac10d881623c4eb6d0337e2ee2db4
Small improvements in min cost flow files.
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/capacity_scaling.h Fri Feb 29 15:57:52 2008 +0000
@@ -25,8 +25,6 @@
/// \brief Capacity scaling algorithm for finding a minimum cost flow.
#include <vector>
-
-#include <lemon/graph_adaptor.h>
#include <lemon/bin_heap.h>
namespace lemon {
@@ -90,9 +88,6 @@
/// distance of the nodes.
class ResidualDijkstra
{
- typedef typename Graph::template NodeMap<Cost> CostNodeMap;
- typedef typename Graph::template NodeMap<Edge> PredMap;
-
typedef typename Graph::template NodeMap<int> HeapCrossRef;
typedef BinHeap<Cost, HeapCrossRef> Heap;
@@ -109,7 +104,7 @@
PotentialMap &_potential;
// The distance map
- CostNodeMap _dist;
+ PotentialMap _dist;
// The pred edge map
PredMap &_pred;
// The processed (i.e. permanently labeled) nodes
@@ -131,7 +126,7 @@
{}
/// Runs the algorithm from the given source node.
- Node run(Node s, Capacity delta) {
+ Node run(Node s, Capacity delta = 1) {
HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
Heap heap(heap_cross_ref);
heap.push(s, 0);
@@ -454,18 +449,18 @@
return *_potential;
}
- /// \brief Returns the flow on the edge.
+ /// \brief Returns the flow on the given edge.
///
- /// Returns the flow on the edge.
+ /// Returns the flow on the given edge.
///
/// \pre \ref run() must be called before using this function.
Capacity flow(const Edge& edge) const {
return (*_flow)[edge];
}
- /// \brief Returns the potential of the node.
+ /// \brief Returns the potential of the given node.
///
- /// Returns the potential of the node.
+ /// Returns the potential of the given node.
///
/// \pre \ref run() must be called before using this function.
Cost potential(const Node& node) const {
@@ -517,7 +512,11 @@
if ( _supply[n] > max_sup) max_sup = _supply[n];
if (-_supply[n] > max_dem) max_dem = -_supply[n];
}
- if (max_dem < max_sup) max_sup = max_dem;
+ Capacity max_cap = 0;
+ for (EdgeIt e(_graph); e != INVALID; ++e) {
+ if (_capacity[e] > max_cap) max_cap = _capacity[e];
+ }
+ max_sup = std::min(std::min(max_sup, max_dem), max_cap);
_phase_num = 0;
for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
++_phase_num;
@@ -595,7 +594,7 @@
}
// Augmenting along a shortest path from s to t.
- Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+ Capacity d = std::min(_excess[s], -_excess[t]);
Node u = t;
Edge e;
if (d > _delta) {
@@ -657,23 +656,24 @@
{
// Running Dijkstra
s = _excess_nodes[next_node];
- if ((t = _dijkstra->run(s, 1)) == INVALID)
- return false;
+ if ((t = _dijkstra->run(s)) == INVALID) break;
// Augmenting along a shortest path from s to t
- Capacity d = _excess[s] < -_excess[t] ? _excess[s] : -_excess[t];
+ Capacity d = std::min(_excess[s], -_excess[t]);
Node u = t;
Edge e;
- while ((e = _pred[u]) != INVALID) {
- Capacity rc;
- if (u == _graph.target(e)) {
- rc = _res_cap[e];
- u = _graph.source(e);
- } else {
- rc = (*_flow)[e];
- u = _graph.target(e);
+ if (d > 1) {
+ while ((e = _pred[u]) != INVALID) {
+ Capacity rc;
+ if (u == _graph.target(e)) {
+ rc = _res_cap[e];
+ u = _graph.source(e);
+ } else {
+ rc = (*_flow)[e];
+ u = _graph.target(e);
+ }
+ if (rc < d) d = rc;
}
- if (rc < d) d = rc;
}
u = t;
while ((e = _pred[u]) != INVALID) {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/cost_scaling.h
--- a/lemon/cost_scaling.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/cost_scaling.h Fri Feb 29 15:57:52 2008 +0000
@@ -399,18 +399,18 @@
return *_potential;
}
- /// \brief Returns the flow on the edge.
+ /// \brief Returns the flow on the given edge.
///
- /// Returns the flow on the edge.
+ /// Returns the flow on the given edge.
///
/// \pre \ref run() must be called before using this function.
Capacity flow(const Edge& edge) const {
return (*_flow)[edge];
}
- /// \brief Returns the potential of the node.
+ /// \brief Returns the potential of the given node.
///
- /// Returns the potential of the node.
+ /// Returns the potential of the given node.
///
/// \pre \ref run() must be called before using this function.
Cost potential(const Node& node) const {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/cycle_canceling.h Fri Feb 29 15:57:52 2008 +0000
@@ -355,18 +355,18 @@
return *_potential;
}
- /// \brief Returns the flow on the edge.
+ /// \brief Returns the flow on the given edge.
///
- /// Returns the flow on the edge.
+ /// Returns the flow on the given edge.
///
/// \pre \ref run() must be called before using this function.
Capacity flow(const Edge& edge) const {
return (*_flow)[edge];
}
- /// \brief Returns the potential of the node.
+ /// \brief Returns the potential of the given node.
///
- /// Returns the potential of the node.
+ /// Returns the potential of the given node.
///
/// \pre \ref run() must be called before using this function.
Cost potential(const Node& node) const {
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/min_cost_flow.h
--- a/lemon/min_cost_flow.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/min_cost_flow.h Fri Feb 29 15:57:52 2008 +0000
@@ -44,10 +44,10 @@
///
/// There are four implementations for the minimum cost flow problem,
/// which can be used exactly the same way.
- /// - \ref CapacityScaling The capacity scaling algorithm.
- /// - \ref CostScaling The cost scaling algorithm.
- /// - \ref CycleCanceling A cycle-canceling algorithm.
- /// - \ref NetworkSimplex The network simplex algorithm.
+ /// - \ref CapacityScaling
+ /// - \ref CostScaling
+ /// - \ref CycleCanceling
+ /// - \ref NetworkSimplex
///
/// \tparam Graph The directed graph type the algorithm runs on.
/// \tparam LowerMap The type of the lower bound map.
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/min_mean_cycle.h Fri Feb 29 15:57:52 2008 +0000
@@ -134,7 +134,8 @@
}
/// \name Execution control
- /// The simplest way to execute the algorithm is to call run().
+ /// The simplest way to execute the algorithm is to call the run()
+ /// function.
/// \n
/// If you only need the minimum mean value, you may call init()
/// and findMinMean().
@@ -237,7 +238,7 @@
/// \name Query Functions
/// The result of the algorithm can be obtained using these
/// functions.
- /// \n run() must be called before using them.
+ /// \n The algorithm should be executed before using them.
/// @{
diff -r 061be2e64eca -r 4d3bc1d04c1d lemon/network_simplex.h
--- a/lemon/network_simplex.h Fri Feb 29 15:55:39 2008 +0000
+++ b/lemon/network_simplex.h Fri Feb 29 15:57:52 2008 +0000
@@ -776,18 +776,18 @@
return *_potential_result;
}
- /// \brief Returns the flow on the edge.
+ /// \brief Returns the flow on the given edge.
///
- /// Returns the flow on the edge.
+ /// Returns the flow on the given edge.
///
/// \pre \ref run() must be called before using this function.
Capacity flow(const typename Graph::Edge& edge) const {
return (*_flow_result)[edge];
}
- /// \brief Returns the potential of the node.
+ /// \brief Returns the potential of the given node.
///
- /// Returns the potential of the node.
+ /// Returns the potential of the given node.
///
/// \pre \ref run() must be called before using this function.
Cost potential(const typename Graph::Node& node) const {