# HG changeset patch
# User deba
# Date 1181918184 0
# Node ID 8c791ee69a451b19896bc521379b27cd9668886f
# Parent 717a5134ddeb6b07e882180a37e913dd1af0b2ca
Improvments in min cost flow algorithms
- improved cycle cancelling
diff -r 717a5134ddeb -r 8c791ee69a45 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/capacity_scaling.h Fri Jun 15 14:36:24 2007 +0000
@@ -31,13 +31,15 @@
#define WITH_SCALING
+//#define _DEBUG_ITER_
+
namespace lemon {
/// \addtogroup min_cost_flow
/// @{
/// \brief Implementation of the capacity scaling version of the
- /// succesive shortest path algorithm for finding a minimum cost flow.
+ /// successive shortest path algorithm for finding a minimum cost flow.
///
/// \ref lemon::CapacityScaling "CapacityScaling" implements a
/// capacity scaling algorithm for finding a minimum cost flow.
@@ -299,6 +301,9 @@
/// \brief Map for identifing deficit nodes.
DeficitBoolMap delta_deficit;
+ /// \brief The deficit nodes.
+ std::vector<ResNode> deficit_nodes;
+
#else //WITHOUT_CAPACITY_SCALING
typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
ResDijkstra;
@@ -510,9 +515,9 @@
return c;
}
- /// \brief Runs the successive shortest path algorithm.
+ /// \brief Runs the algorithm.
///
- /// Runs the successive shortest path algorithm.
+ /// Runs the algorithm.
///
/// \return \c true if a feasible flow can be found.
bool run() {
@@ -531,11 +536,13 @@
#ifdef WITH_SCALING
// Initilaizing delta value
- Capacity max_cap = 0;
- for (EdgeIt e(graph); e != INVALID; ++e) {
- if (capacity[e] > max_cap) max_cap = capacity[e];
+ Supply max_sup = 0, max_dem = 0;
+ for (NodeIt n(graph); n != INVALID; ++n) {
+ if (supply[n] > max_sup) max_sup = supply[n];
+ if (supply[n] < -max_dem) max_dem = -supply[n];
}
- for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
+ if (max_dem < max_sup) max_sup = max_dem;
+ for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
#endif
return true;
}
@@ -546,6 +553,9 @@
bool start() {
typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
typedef typename DeltaResGraph::Edge DeltaResEdge;
+#ifdef _DEBUG_ITER_
+ int dijk_num = 0;
+#endif
// Processing capacity scaling phases
ResNode s, t;
@@ -564,18 +574,35 @@
// Finding excess nodes
excess_nodes.clear();
+ deficit_nodes.clear();
for (ResNodeIt n(res_graph); n != INVALID; ++n) {
- if (imbalance[n] >= delta) excess_nodes.push_back(n);
+ if (imbalance[n] >= delta) excess_nodes.push_back(n);
+ if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
}
next_node = 0;
- // Finding successive shortest paths
+ // Finding shortest paths
while (next_node < excess_nodes.size()) {
+ // Checking deficit nodes
+ if (delta > 1) {
+ bool delta_def = false;
+ for (int i = 0; i < deficit_nodes.size(); ++i) {
+ if (imbalance[deficit_nodes[i]] <= -delta) {
+ delta_def = true;
+ break;
+ }
+ }
+ if (!delta_def) break;
+ }
+
// Running Dijkstra
s = excess_nodes[next_node];
updater.init();
dijkstra.init();
dijkstra.addSource(s);
+#ifdef _DEBUG_ITER_
+ ++dijk_num;
+#endif
if ((t = dijkstra.start(delta_deficit)) == INVALID) {
if (delta > 1) {
++next_node;
@@ -608,6 +635,10 @@
if (imbalance[s] < delta) ++next_node;
}
}
+#ifdef _DEBUG_ITER_
+ std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
+ << dijk_num << " times." << std::endl;
+#endif
// Handling nonzero lower bounds
if (lower) {
@@ -628,7 +659,7 @@
if (excess_nodes.size() == 0) return true;
next_node = 0;
- // Finding successive shortest paths
+ // Finding shortest paths
ResNode s, t;
while ( imbalance[excess_nodes[next_node]] > 0 ||
++next_node < excess_nodes.size() )
diff -r 717a5134ddeb -r 8c791ee69a45 lemon/cycle_canceling.h
--- a/lemon/cycle_canceling.h Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/cycle_canceling.h Fri Jun 15 14:36:24 2007 +0000
@@ -22,13 +22,13 @@
/// \ingroup min_cost_flow
///
/// \file
-/// \brief A cycle canceling algorithm for finding a minimum cost flow.
+/// \brief A cycle-canceling algorithm for finding a minimum cost flow.
#include <vector>
#include <lemon/circulation.h>
#include <lemon/graph_adaptor.h>
-/// \brief The used cycle canceling method.
+/// \brief The used cycle-canceling method.
#define LIMITED_CYCLE_CANCELING
//#define MIN_MEAN_CYCLE_CANCELING
@@ -36,17 +36,21 @@
#include <lemon/bellman_ford.h>
/// \brief The maximum number of iterations for the first execution
/// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
+ /// It should be at least 2.
#define STARTING_LIMIT 2
/// \brief The iteration limit for the
/// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
- /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+ /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+ /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
#define ALPHA_MUL 3
/// \brief The iteration limit for the
/// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
- /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
+ /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round.
+ /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1.
#define ALPHA_DIV 2
//#define _ONLY_ONE_CYCLE_
+//#define _NO_BACK_STEP_
//#define _DEBUG_ITER_
#endif
@@ -60,11 +64,11 @@
/// \addtogroup min_cost_flow
/// @{
- /// \brief Implementation of a cycle canceling algorithm for finding
+ /// \brief Implementation of a cycle-canceling algorithm for finding
/// a minimum cost flow.
///
- /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
- /// canceling algorithm for finding a minimum cost flow.
+ /// \ref lemon::CycleCanceling "CycleCanceling" implements a
+ /// cycle-canceling algorithm for finding a minimum cost flow.
///
/// \param Graph The directed graph type the algorithm runs on.
/// \param LowerMap The type of the lower bound map.
@@ -118,26 +122,6 @@
protected:
- /// \brief Map adaptor class for demand map.
- class DemandMap : public MapBase<Node, Supply>
- {
- private:
-
- const SupplyMap *map;
-
- public:
-
- typedef typename MapBase<Node, Supply>::Value Value;
- typedef typename MapBase<Node, Supply>::Key Key;
-
- DemandMap(const SupplyMap &_map) : map(&_map) {}
-
- Value operator[](const Key &e) const {
- return -(*map)[e];
- }
-
- }; //class DemandMap
-
/// \brief Map adaptor class for handling residual edge costs.
class ResCostMap : public MapBase<ResEdge, Cost>
{
@@ -170,8 +154,6 @@
const CostMap &cost;
/// \brief The modified supply map.
SupplyRefMap supply;
- /// \brief The modified demand map.
- DemandMap demand;
/// \brief The sum of supply values equals zero.
bool valid_supply;
@@ -199,7 +181,7 @@
const CostMap &_cost,
const SupplyMap &_supply ) :
graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
- supply(_graph), demand(supply), flow(_graph, 0),
+ supply(_graph), flow(_graph, 0),
res_graph(_graph, capacity, flow), res_cost(cost)
{
// Removing nonzero lower bounds
@@ -229,7 +211,7 @@
const CostMap &_cost,
const SupplyMap &_supply ) :
graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
- supply(_supply), demand(supply), flow(_graph, 0),
+ supply(_supply), flow(_graph, 0),
res_graph(_graph, capacity, flow), res_cost(cost)
{
// Checking the sum of supply values
@@ -259,7 +241,7 @@
Node _s, Node _t,
Supply _flow_value ) :
graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
- supply(_graph), demand(supply), flow(_graph, 0),
+ supply(_graph), flow(_graph, 0),
res_graph(_graph, capacity, flow), res_cost(cost)
{
// Removing nonzero lower bounds
@@ -295,7 +277,7 @@
Node _s, Node _t,
Supply _flow_value ) :
graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
- supply(_graph, 0), demand(supply), flow(_graph, 0),
+ supply(_graph, 0), flow(_graph, 0),
res_graph(_graph, capacity, flow), res_cost(cost)
{
supply[_s] = _flow_value;
@@ -345,14 +327,14 @@
// Finding a feasible flow
Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
- CapacityRefMap, DemandMap >
+ CapacityRefMap, SupplyMap >
circulation( graph, constMap<Edge>((Capacity)0),
- capacity, demand, flow );
+ capacity, supply, flow );
return circulation.run() == -1;
}
#ifdef LIMITED_CYCLE_CANCELING
- /// \brief Executes a cycle canceling algorithm using
+ /// \brief Executes a cycle-canceling algorithm using
/// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
/// iteration count.
bool start() {
@@ -373,8 +355,13 @@
int iter_num = 0;
bool cycle_found = false;
while (!cycle_found) {
+#ifdef _NO_BACK_STEP_
+ int curr_iter_num = length_bound <= node_num ?
+ length_bound - iter_num : node_num - iter_num;
+#else
int curr_iter_num = iter_num + length_bound <= node_num ?
length_bound : node_num - iter_num;
+#endif
iter_num += curr_iter_num;
int real_iter_num = curr_iter_num;
for (int i = 0; i < curr_iter_num; ++i) {
@@ -432,7 +419,7 @@
}
#ifdef _DEBUG_ITER_
- std::cout << "Limited cycle canceling algorithm finished. "
+ std::cout << "Limited cycle-canceling algorithm finished. "
<< "Found " << cycle_num << " negative cycles."
<< std::endl;
#endif
@@ -447,7 +434,7 @@
#endif
#ifdef MIN_MEAN_CYCLE_CANCELING
- /// \brief Executes the minimum mean cycle canceling algorithm
+ /// \brief Executes the minimum mean cycle-canceling algorithm
/// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
bool start() {
typedef Path<ResGraph> ResPath;
@@ -486,7 +473,7 @@
}
#ifdef _DEBUG_ITER_
- std::cout << "Minimum mean cycle canceling algorithm finished. "
+ std::cout << "Minimum mean cycle-canceling algorithm finished. "
<< "Found " << cycle_num << " negative cycles."
<< std::endl;
#endif
diff -r 717a5134ddeb -r 8c791ee69a45 lemon/network_simplex.h
--- a/lemon/network_simplex.h Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/network_simplex.h Fri Jun 15 14:36:24 2007 +0000
@@ -275,6 +275,8 @@
if (!(valid_supply = sum == 0)) return;
// Copying graph_ref to graph
+ graph.reserveNode(countNodes(graph_ref) + 1);
+ graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref));
copyGraph(graph, graph_ref)
.edgeMap(cost, _cost)
.nodeRef(node_ref)
@@ -477,7 +479,9 @@
root = graph.addNode();
parent[root] = INVALID;
pred_edge[root] = INVALID;
- depth[root] = supply[root] = potential[root] = 0;
+ depth[root] = 0;
+ supply[root] = 0;
+ potential[root] = 0;
// Adding artificial edges to the graph and initializing the node
// maps of the spanning tree data structure
@@ -513,7 +517,7 @@
#ifdef EDGE_BLOCK_PIVOT
// Initializing block_size for the edge block pivot rule
int edge_num = countEdges(graph);
- block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
+ block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
#endif
#ifdef CANDIDATE_LIST_PIVOT