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@440:  * Copyright (C) 2003-2009
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>
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@394: void checkPreflowCompile()
alpar@389: {
alpar@389:   typedef int VType;
alpar@389:   typedef concepts::Digraph Digraph;
alpar@389: 
alpar@389:   typedef Digraph::Node Node;
alpar@389:   typedef Digraph::Arc Arc;
alpar@389:   typedef concepts::ReadMap<Arc,VType> CapMap;
alpar@389:   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
alpar@389:   typedef concepts::WriteMap<Node,bool> CutMap;
alpar@389: 
kpeter@394:   typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@394:   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@394: 
alpar@389:   Digraph g;
alpar@389:   Node n;
alpar@389:   Arc e;
alpar@389:   CapMap cap;
alpar@389:   FlowMap flow;
alpar@389:   CutMap cut;
kpeter@585:   VType v;
kpeter@585:   bool b;
alpar@389: 
kpeter@585:   typedef Preflow<Digraph, CapMap>
kpeter@585:             ::SetFlowMap<FlowMap>
kpeter@585:             ::SetElevator<Elev>
kpeter@585:             ::SetStandardElevator<LinkedElev>
kpeter@585:             ::Create PreflowType;
kpeter@585:   PreflowType preflow_test(g, cap, n, n);
kpeter@585:   const PreflowType& const_preflow_test = preflow_test;
alpar@389: 
kpeter@585:   preflow_test
kpeter@585:     .capacityMap(cap)
kpeter@585:     .flowMap(flow)
kpeter@585:     .source(n)
kpeter@585:     .target(n);
alpar@389: 
alpar@389:   preflow_test.init();
kpeter@392:   preflow_test.init(cap);
alpar@389:   preflow_test.startFirstPhase();
alpar@389:   preflow_test.startSecondPhase();
alpar@389:   preflow_test.run();
alpar@389:   preflow_test.runMinCut();
alpar@389: 
kpeter@585:   v = const_preflow_test.flowValue();
kpeter@585:   v = const_preflow_test.flow(e);
kpeter@585:   const FlowMap& fm = const_preflow_test.flowMap();
kpeter@585:   b = const_preflow_test.minCut(n);
kpeter@585:   const_preflow_test.minCutMap(cut);
kpeter@585:   
kpeter@585:   ignore_unused_variable_warning(fm);
alpar@389: }
alpar@389: 
alpar@389: int cutValue (const SmartDigraph& g,
alpar@389:               const SmartDigraph::NodeMap<bool>& cut,
alpar@389:               const SmartDigraph::ArcMap<int>& cap) {
alpar@389: 
alpar@389:   int 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: 
alpar@389: bool checkFlow(const SmartDigraph& g,
alpar@389:                const SmartDigraph::ArcMap<int>& flow,
alpar@389:                const SmartDigraph::ArcMap<int>& 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;
alpar@389:     int 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: 
alpar@923: 
alpar@389: int main() {
alpar@389: 
alpar@389:   typedef SmartDigraph Digraph;
alpar@389: 
alpar@389:   typedef Digraph::Node Node;
alpar@389:   typedef Digraph::NodeIt NodeIt;
alpar@389:   typedef Digraph::ArcIt ArcIt;
alpar@389:   typedef Digraph::ArcMap<int> CapMap;
alpar@389:   typedef Digraph::ArcMap<int> FlowMap;
alpar@389:   typedef Digraph::NodeMap<bool> CutMap;
alpar@389: 
alpar@389:   typedef Preflow<Digraph, CapMap> PType;
alpar@389: 
alpar@389:   Digraph g;
alpar@389:   Node s, t;
alpar@389:   CapMap cap(g);
alpar@423:   std::istringstream input(test_lgf);
alpar@423:   DigraphReader<Digraph>(g,input).
alpar@389:     arcMap("capacity", cap).
alpar@389:     node("source",s).
alpar@389:     node("target",t).
alpar@389:     run();
alpar@389: 
alpar@389:   PType preflow_test(g, cap, s, t);
alpar@389:   preflow_test.run();
alpar@389: 
alpar@389:   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
alpar@389:         "The flow is not feasible.");
alpar@389: 
alpar@389:   CutMap min_cut(g);
alpar@389:   preflow_test.minCutMap(min_cut);
alpar@389:   int min_cut_value=cutValue(g,min_cut,cap);
alpar@389: 
alpar@389:   check(preflow_test.flowValue() == min_cut_value,
alpar@389:         "The max flow value is not equal to the three min cut values.");
alpar@389: 
alpar@389:   FlowMap flow(g);
alpar@389:   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
alpar@389: 
alpar@389:   int flow_value=preflow_test.flowValue();
alpar@389: 
alpar@389:   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
kpeter@392:   preflow_test.init(flow);
alpar@389:   preflow_test.startFirstPhase();
alpar@389: 
alpar@389:   CutMap min_cut1(g);
alpar@389:   preflow_test.minCutMap(min_cut1);
alpar@389:   min_cut_value=cutValue(g,min_cut1,cap);
alpar@389: 
alpar@389:   check(preflow_test.flowValue() == min_cut_value &&
alpar@389:         min_cut_value == 2*flow_value,
alpar@389:         "The max flow value or the min cut value is wrong.");
alpar@389: 
alpar@389:   preflow_test.startSecondPhase();
alpar@389: 
alpar@389:   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
alpar@389:         "The flow is not feasible.");
alpar@389: 
alpar@389:   CutMap min_cut2(g);
alpar@389:   preflow_test.minCutMap(min_cut2);
alpar@389:   min_cut_value=cutValue(g,min_cut2,cap);
alpar@389: 
alpar@389:   check(preflow_test.flowValue() == min_cut_value &&
alpar@389:         min_cut_value == 2*flow_value,
alpar@389:         "The max flow value or the three min cut values were not doubled");
alpar@389: 
alpar@389: 
alpar@389:   preflow_test.flowMap(flow);
alpar@389: 
alpar@389:   NodeIt tmp1(g,s);
alpar@389:   ++tmp1;
alpar@389:   if ( tmp1 != INVALID ) s=tmp1;
alpar@389: 
alpar@389:   NodeIt tmp2(g,t);
alpar@389:   ++tmp2;
alpar@389:   if ( tmp2 != INVALID ) t=tmp2;
alpar@389: 
alpar@389:   preflow_test.source(s);
alpar@389:   preflow_test.target(t);
alpar@389: 
alpar@389:   preflow_test.run();
alpar@389: 
alpar@389:   CutMap min_cut3(g);
alpar@389:   preflow_test.minCutMap(min_cut3);
alpar@389:   min_cut_value=cutValue(g,min_cut3,cap);
alpar@389: 
alpar@389: 
alpar@389:   check(preflow_test.flowValue() == min_cut_value,
alpar@389:         "The max flow value or the three min cut values are incorrect.");
alpar@389: 
alpar@923:   initFlowTest();
alpar@923:   
alpar@389:   return 0;
alpar@389: }