# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1521817767 -3600
# Node ID 411819b8702c7fdb328049de5607e916155fa8ef
# Parent f0f15d07bf51daff7fa1a76bb77d81ecdea51fb0# Parent 8db773f19586549b6df21c715965f16113267092
Merge bugfix #608 to branch 1.3
diff -r f0f15d07bf51 -r 411819b8702c lemon/preflow.h
--- a/lemon/preflow.h Fri Mar 23 16:09:06 2018 +0100
+++ b/lemon/preflow.h Fri Mar 23 16:09:27 2018 +0100
@@ -476,7 +476,7 @@
/// Initializes the internal data structures and sets the initial
/// flow to the given \c flowMap. The \c flowMap should contain a
/// flow or at least a preflow, i.e. at each node excluding the
- /// source node the incoming flow should greater or equal to the
+ /// source node the incoming flow should be greater or equal to the
/// outgoing flow.
/// \return \c false if the given \c flowMap is not a preflow.
template <typename FlowMap>
@@ -495,7 +495,7 @@
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
excess -= (*_flow)[e];
}
- if (excess < 0 && n != _source) return false;
+ if (_tolerance.negative(excess) && n != _source) return false;
(*_excess)[n] = excess;
}
@@ -639,7 +639,7 @@
(*_excess)[n] = excess;
- if (excess != 0) {
+ if (_tolerance.nonZero(excess)) {
if (new_level + 1 < _level->maxLevel()) {
_level->liftHighestActive(new_level + 1);
} else {
@@ -720,7 +720,7 @@
(*_excess)[n] = excess;
- if (excess != 0) {
+ if (_tolerance.nonZero(excess)) {
if (new_level + 1 < _level->maxLevel()) {
_level->liftActiveOn(level, new_level + 1);
} else {
@@ -791,7 +791,7 @@
for (NodeIt n(_graph); n != INVALID; ++n) {
if (!reached[n]) {
_level->dirtyTopButOne(n);
- } else if ((*_excess)[n] > 0 && _target != n) {
+ } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
_level->activate(n);
}
}
@@ -852,7 +852,7 @@
(*_excess)[n] = excess;
- if (excess != 0) {
+ if (_tolerance.nonZero(excess)) {
if (new_level + 1 < _level->maxLevel()) {
_level->liftHighestActive(new_level + 1);
} else {
diff -r f0f15d07bf51 -r 411819b8702c test/max_flow_test.cc
--- a/test/max_flow_test.cc Fri Mar 23 16:09:06 2018 +0100
+++ b/test/max_flow_test.cc Fri Mar 23 16:09:27 2018 +0100
@@ -26,6 +26,7 @@
#include <lemon/concepts/maps.h>
#include <lemon/lgf_reader.h>
#include <lemon/elevator.h>
+#include <lemon/tolerance.h>
using namespace lemon;
@@ -65,6 +66,37 @@
"source 1\n"
"target 8\n";
+char test_lgf_float[] =
+ "@nodes\n"
+ "label\n"
+ "0\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "6\n"
+ "7\n"
+ "8\n"
+ "9\n"
+ "@arcs\n"
+ " capacity\n"
+ "0 1 0.1\n"
+ "0 2 0.1\n"
+ "0 3 0.1\n"
+ "1 4 0.1\n"
+ "2 4 0.1\n"
+ "3 4 0.1\n"
+ "4 5 0.3\n"
+ "5 6 0.1\n"
+ "5 7 0.1\n"
+ "5 8 0.1\n"
+ "6 9 0.1\n"
+ "7 9 0.1\n"
+ "8 9 0.1\n"
+ "@attributes\n"
+ "source 0\n"
+ "target 9\n";
// Checks the general interface of a max flow algorithm
template <typename GR, typename CAP>
@@ -165,8 +197,6 @@
typedef int Value;
typedef concepts::Digraph Digraph;
typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
- typedef Elevator<Digraph, Digraph::Node> Elev;
- typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
Digraph g;
Digraph::Node n;
@@ -184,13 +214,13 @@
template <typename T>
-T cutValue (const SmartDigraph& g,
- const SmartDigraph::NodeMap<bool>& cut,
- const SmartDigraph::ArcMap<T>& cap) {
+T cutValue(const SmartDigraph& g,
+ const SmartDigraph::NodeMap<bool>& cut,
+ const SmartDigraph::ArcMap<T>& cap) {
- T c=0;
- for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
- if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
+ T c = 0;
+ for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
+ if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
}
return c;
}
@@ -199,10 +229,11 @@
bool checkFlow(const SmartDigraph& g,
const SmartDigraph::ArcMap<T>& flow,
const SmartDigraph::ArcMap<T>& cap,
- SmartDigraph::Node s, SmartDigraph::Node t) {
+ SmartDigraph::Node s, SmartDigraph::Node t,
+ const Tolerance<T>& tol) {
for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
- if (flow[e] < 0 || flow[e] > cap[e]) return false;
+ if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
}
for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
@@ -214,28 +245,29 @@
for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
sum -= flow[e];
}
- if (sum != 0) return false;
+ if (tol.nonZero(sum)) return false;
}
return true;
}
-void initFlowTest()
+void checkInitPreflow()
{
DIGRAPH_TYPEDEFS(SmartDigraph);
SmartDigraph g;
- SmartDigraph::ArcMap<int> cap(g),iflow(g);
- Node s=g.addNode(); Node t=g.addNode();
- Node n1=g.addNode(); Node n2=g.addNode();
+ SmartDigraph::ArcMap<int> cap(g), iflow(g);
+ Node s = g.addNode(); Node t = g.addNode();
+ Node n1 = g.addNode(); Node n2 = g.addNode();
Arc a;
- a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
- a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
- a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
+ a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
+ a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
+ a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
- Preflow<SmartDigraph> pre(g,cap,s,t);
+ Preflow<SmartDigraph> pre(g, cap, s, t);
pre.init(iflow);
pre.startFirstPhase();
- check(pre.flowValue() == 10, "The incorrect max flow value.");
+
+ check(pre.flowValue() == 10, "Incorrect max flow value.");
check(pre.minCut(s), "Wrong min cut (Node s).");
check(pre.minCut(n1), "Wrong min cut (Node n1).");
check(!pre.minCut(n2), "Wrong min cut (Node n2).");
@@ -243,7 +275,7 @@
}
template <typename MF, typename SF>
-void checkMaxFlowAlg() {
+void checkMaxFlowAlg(const char *input_lgf, typename MF::Value expected) {
typedef SmartDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
@@ -252,35 +284,36 @@
typedef CapMap FlowMap;
typedef BoolNodeMap CutMap;
+ Tolerance<Value> tol;
+
Digraph g;
Node s, t;
CapMap cap(g);
- std::istringstream input(test_lgf);
- DigraphReader<Digraph>(g,input)
+ std::istringstream input(input_lgf);
+ DigraphReader<Digraph>(g, input)
.arcMap("capacity", cap)
- .node("source",s)
- .node("target",t)
+ .node("source", s)
+ .node("target", t)
.run();
MF max_flow(g, cap, s, t);
max_flow.run();
- check(checkFlow(g, max_flow.flowMap(), cap, s, t),
+ check(!tol.different(expected, max_flow.flowValue()),
+ "Incorrect max flow value.");
+ check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
"The flow is not feasible.");
CutMap min_cut(g);
max_flow.minCutMap(min_cut);
Value min_cut_value = cutValue(g, min_cut, cap);
- check(max_flow.flowValue() == min_cut_value,
- "The max flow value is not equal to the min cut value.");
+ check(!tol.different(expected, min_cut_value),
+ "Incorrect min cut value.");
FlowMap flow(g);
- for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
-
- Value flow_value = max_flow.flowValue();
-
- for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
+ for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
+ for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
max_flow.init(flow);
SF::startFirstPhase(max_flow); // start first phase of the algorithm
@@ -289,23 +322,24 @@
max_flow.minCutMap(min_cut1);
min_cut_value = cutValue(g, min_cut1, cap);
- check(max_flow.flowValue() == min_cut_value &&
- min_cut_value == 2 * flow_value,
- "The max flow value or the min cut value is wrong.");
+ check(!tol.different(17 * expected, max_flow.flowValue()),
+ "Incorrect max flow value.");
+ check(!tol.different(17 * expected, min_cut_value),
+ "Incorrect min cut value.");
SF::startSecondPhase(max_flow); // start second phase of the algorithm
- check(checkFlow(g, max_flow.flowMap(), cap, s, t),
+ check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
"The flow is not feasible.");
CutMap min_cut2(g);
max_flow.minCutMap(min_cut2);
min_cut_value = cutValue(g, min_cut2, cap);
- check(max_flow.flowValue() == min_cut_value &&
- min_cut_value == 2 * flow_value,
- "The max flow value or the min cut value was not doubled");
-
+ check(!tol.different(17 * expected, max_flow.flowValue()),
+ "Incorrect max flow value.");
+ check(!tol.different(17 * expected, min_cut_value),
+ "Incorrect min cut value.");
max_flow.flowMap(flow);
@@ -324,9 +358,9 @@
CutMap min_cut3(g);
max_flow.minCutMap(min_cut3);
- min_cut_value=cutValue(g, min_cut3, cap);
+ min_cut_value = cutValue(g, min_cut3, cap);
- check(max_flow.flowValue() == min_cut_value,
+ check(!tol.different(max_flow.flowValue(), min_cut_value),
"The max flow value or the min cut value is wrong.");
}
@@ -379,17 +413,28 @@
// Check Preflow
typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
- checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
- checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
- initFlowTest();
+ typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
+
+ checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
+ checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
+ checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
+
+ checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
+ checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
+
+ checkInitPreflow();
// Check EdmondsKarp
typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
- checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
- checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
+ typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
- initFlowTest();
+ checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
+ checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
+ checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
+
+ checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
+ checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
return 0;
}