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