Page MenuHome
Differential D5594 Diff 18104 extern/quadriflow/3rd/lemon-1.3.1/test/max_flow_test.cc

Changeset View

Standalone View

View Options

extern/quadriflow/3rd/lemon-1.3.1/test/max_flow_test.cc

  • This file was added.
/* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2013
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#include <iostream>
#include "test_tools.h"
#include <lemon/smart_graph.h>
#include <lemon/preflow.h>
#include <lemon/edmonds_karp.h>
#include <lemon/concepts/digraph.h>
#include <lemon/concepts/maps.h>
#include <lemon/lgf_reader.h>
#include <lemon/elevator.h>
using namespace lemon;
char test_lgf[] =
"@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"
" label capacity\n"
"0 1 0 20\n"
"0 2 1 0\n"
"1 1 2 3\n"
"1 2 3 8\n"
"1 3 4 8\n"
"2 5 5 5\n"
"3 2 6 5\n"
"3 5 7 5\n"
"3 6 8 5\n"
"4 3 9 3\n"
"5 7 10 3\n"
"5 6 11 10\n"
"5 8 12 10\n"
"6 8 13 8\n"
"8 9 14 20\n"
"8 1 15 5\n"
"9 5 16 5\n"
"@attributes\n"
"source 1\n"
"target 8\n";
// Checks the general interface of a max flow algorithm
template <typename GR, typename CAP>
struct MaxFlowClassConcept
{
template <typename MF>
struct Constraints {
typedef typename GR::Node Node;
typedef typename GR::Arc Arc;
typedef typename CAP::Value Value;
typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
typedef concepts::WriteMap<Node, bool> CutMap;
GR g;
Node n;
Arc e;
CAP cap;
FlowMap flow;
CutMap cut;
Value v;
bool b;
void constraints() {
checkConcept<concepts::Digraph, GR>();
const Constraints& me = *this;
typedef typename MF
::template SetFlowMap<FlowMap>
::Create MaxFlowType;
typedef typename MF::Create MaxFlowType2;
MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
const MaxFlowType& const_max_flow = max_flow;
max_flow
.capacityMap(cap)
.flowMap(flow)
.source(n)
.target(n);
typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
max_flow.tolerance(tol);
max_flow.init();
max_flow.init(cap);
max_flow.run();
v = const_max_flow.flowValue();
v = const_max_flow.flow(e);
const FlowMap& fm = const_max_flow.flowMap();
b = const_max_flow.minCut(n);
const_max_flow.minCutMap(cut);
::lemon::ignore_unused_variable_warning(fm);
}
};
};
// Checks the specific parts of Preflow's interface
void checkPreflowCompile()
{
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;
CapMap cap;
typedef Preflow<Digraph, CapMap>
::SetElevator<Elev>
::SetStandardElevator<LinkedElev>
::Create PreflowType;
PreflowType preflow_test(g, cap, n, n);
const PreflowType& const_preflow_test = preflow_test;
const PreflowType::Elevator& elev = const_preflow_test.elevator();
preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
bool b = preflow_test.init(cap);
preflow_test.startFirstPhase();
preflow_test.startSecondPhase();
preflow_test.runMinCut();
::lemon::ignore_unused_variable_warning(b);
}
// Checks the specific parts of EdmondsKarp's interface
void checkEdmondsKarpCompile()
{
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;
CapMap cap;
EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
ek_test.init(cap);
bool b = ek_test.checkedInit(cap);
b = ek_test.augment();
ek_test.start();
::lemon::ignore_unused_variable_warning(b);
}
template <typename T>
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];
}
return c;
}
template <typename T>
bool checkFlow(const SmartDigraph& g,
const SmartDigraph::ArcMap<T>& flow,
const SmartDigraph::ArcMap<T>& cap,
SmartDigraph::Node s, SmartDigraph::Node t) {
for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
if (flow[e] < 0 || flow[e] > cap[e]) return false;
}
for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
if (n == s || n == t) continue;
T sum = 0;
for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
sum += flow[e];
}
for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
sum -= flow[e];
}
if (sum != 0) return false;
}
return true;
}
void initFlowTest()
{
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();
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;
Preflow<SmartDigraph> pre(g,cap,s,t);
pre.init(iflow);
pre.startFirstPhase();
check(pre.flowValue() == 10, "The 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).");
check(!pre.minCut(t), "Wrong min cut (Node t).");
}
template <typename MF, typename SF>
void checkMaxFlowAlg() {
typedef SmartDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
typedef typename MF::Value Value;
typedef Digraph::ArcMap<Value> CapMap;
typedef CapMap FlowMap;
typedef BoolNodeMap CutMap;
Digraph g;
Node s, t;
CapMap cap(g);
std::istringstream input(test_lgf);
DigraphReader<Digraph>(g,input)
.arcMap("capacity", cap)
.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),
"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.");
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];
max_flow.init(flow);
SF::startFirstPhase(max_flow); // start first phase of the algorithm
CutMap min_cut1(g);
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.");
SF::startSecondPhase(max_flow); // start second phase of the algorithm
check(checkFlow(g, max_flow.flowMap(), cap, s, t),
"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");
max_flow.flowMap(flow);
NodeIt tmp1(g, s);
++tmp1;
if (tmp1 != INVALID) s = tmp1;
NodeIt tmp2(g, t);
++tmp2;
if (tmp2 != INVALID) t = tmp2;
max_flow.source(s);
max_flow.target(t);
max_flow.run();
CutMap min_cut3(g);
max_flow.minCutMap(min_cut3);
min_cut_value=cutValue(g, min_cut3, cap);
check(max_flow.flowValue() == min_cut_value,
"The max flow value or the min cut value is wrong.");
}
// Struct for calling start functions of a general max flow algorithm
template <typename MF>
struct GeneralStartFunctions {
static void startFirstPhase(MF& mf) {
mf.start();
}
static void startSecondPhase(MF& mf) {
::lemon::ignore_unused_variable_warning(mf);
}
};
// Struct for calling start functions of Preflow
template <typename MF>
struct PreflowStartFunctions {
static void startFirstPhase(MF& mf) {
mf.startFirstPhase();
}
static void startSecondPhase(MF& mf) {
mf.startSecondPhase();
}
};
int main() {
typedef concepts::Digraph GR;
typedef concepts::ReadMap<GR::Arc, int> CM1;
typedef concepts::ReadMap<GR::Arc, double> CM2;
// Check the interface of Preflow
checkConcept< MaxFlowClassConcept<GR, CM1>,
Preflow<GR, CM1> >();
checkConcept< MaxFlowClassConcept<GR, CM2>,
Preflow<GR, CM2> >();
// Check the interface of EdmondsKarp
checkConcept< MaxFlowClassConcept<GR, CM1>,
EdmondsKarp<GR, CM1> >();
checkConcept< MaxFlowClassConcept<GR, CM2>,
EdmondsKarp<GR, CM2> >();
// 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();
// Check EdmondsKarp
typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
initFlowTest();
return 0;
}