thoneyvazul@1056: /* -*- mode: C++; indent-tabs-mode: nil; -*-
thoneyvazul@1056:  *
thoneyvazul@1056:  * This file is a part of LEMON, a generic C++ optimization library.
thoneyvazul@1056:  *
thoneyvazul@1056:  * Copyright (C) 2003-2010
thoneyvazul@1056:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
thoneyvazul@1056:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
thoneyvazul@1056:  *
thoneyvazul@1056:  * Permission to use, modify and distribute this software is granted
thoneyvazul@1056:  * provided that this copyright notice appears in all copies. For
thoneyvazul@1056:  * precise terms see the accompanying LICENSE file.
thoneyvazul@1056:  *
thoneyvazul@1056:  * This software is provided "AS IS" with no warranty of any kind,
thoneyvazul@1056:  * express or implied, and with no claim as to its suitability for any
thoneyvazul@1056:  * purpose.
thoneyvazul@1056:  *
thoneyvazul@1056:  */
thoneyvazul@1056: 
thoneyvazul@1056: #include<iostream>
thoneyvazul@1056: 
thoneyvazul@1056: #include "test_tools.h"
thoneyvazul@1056: #include<lemon/smart_graph.h>
thoneyvazul@1056: #include<lemon/edmonds_karp.h>
thoneyvazul@1056: #include <lemon/concepts/digraph.h>
thoneyvazul@1056: #include <lemon/concepts/maps.h>
thoneyvazul@1056: #include <lemon/lgf_reader.h>
thoneyvazul@1056: 
thoneyvazul@1056: using namespace lemon;
thoneyvazul@1056: 
thoneyvazul@1056: char test_lgf[] =
thoneyvazul@1056:   "@nodes\n"
thoneyvazul@1056:   "label\n"
thoneyvazul@1056:   "0\n"
thoneyvazul@1056:   "1\n"
thoneyvazul@1056:   "2\n"
thoneyvazul@1056:   "3\n"
thoneyvazul@1056:   "4\n"
thoneyvazul@1056:   "5\n"
thoneyvazul@1056:   "6\n"
thoneyvazul@1056:   "7\n"
thoneyvazul@1056:   "8\n"
thoneyvazul@1056:   "9\n"
thoneyvazul@1056:   "@arcs\n"
thoneyvazul@1056:   "    label capacity\n"
thoneyvazul@1056:   "0 1 0     20\n"
thoneyvazul@1056:   "0 2 1     0\n"
thoneyvazul@1056:   "1 1 2     3\n"
thoneyvazul@1056:   "1 2 3     8\n"
thoneyvazul@1056:   "1 3 4     8\n"
thoneyvazul@1056:   "2 5 5     5\n"
thoneyvazul@1056:   "3 2 6     5\n"
thoneyvazul@1056:   "3 5 7     5\n"
thoneyvazul@1056:   "3 6 8     5\n"
thoneyvazul@1056:   "4 3 9     3\n"
thoneyvazul@1056:   "5 7 10    3\n"
thoneyvazul@1056:   "5 6 11    10\n"
thoneyvazul@1056:   "5 8 12    10\n"
thoneyvazul@1056:   "6 8 13    8\n"
thoneyvazul@1056:   "8 9 14    20\n"
thoneyvazul@1056:   "8 1 15    5\n"
thoneyvazul@1056:   "9 5 16    5\n"
thoneyvazul@1056:   "@attributes\n"
thoneyvazul@1056:   "source 1\n"
thoneyvazul@1056:   "target 8\n";
thoneyvazul@1056: 
thoneyvazul@1056: void checkEdmondKarpCompile() {
thoneyvazul@1056:   typedef int VType;
thoneyvazul@1056:   typedef concepts::Digraph Digraph;
thoneyvazul@1056: 
thoneyvazul@1056:   typedef Digraph::Node Node;
thoneyvazul@1056:   typedef Digraph::Arc Arc;
thoneyvazul@1056:   typedef concepts::ReadMap<Arc,VType> CapMap;
thoneyvazul@1056:   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
thoneyvazul@1056:   typedef concepts::WriteMap<Node,bool> CutMap;
thoneyvazul@1056: 
thoneyvazul@1056:   Digraph g;
thoneyvazul@1056:   Node n;
thoneyvazul@1056:   Arc e;
thoneyvazul@1056:   CapMap cap;
thoneyvazul@1056:   FlowMap flow;
thoneyvazul@1056:   CutMap cut;
thoneyvazul@1056:   VType v;
thoneyvazul@1056:   bool b;
thoneyvazul@1056:   ignore_unused_variable_warning(v,b);
thoneyvazul@1056:   typedef EdmondsKarp<Digraph, CapMap>
thoneyvazul@1056:               ::DefFlowMap<FlowMap>
thoneyvazul@1056:               ::Create EKType;
thoneyvazul@1056:   EKType ek_test(g, cap, n, n);
thoneyvazul@1056:   const EKType& const_ek_test = ek_test;
thoneyvazul@1056: 
thoneyvazul@1056:   EKType::Tolerance tol = const_ek_test.tolerance();
thoneyvazul@1056:   ek_test.tolerance(tol);
thoneyvazul@1056: 
thoneyvazul@1056:   ek_test
thoneyvazul@1056:     .capacityMap(cap)
thoneyvazul@1056:     .flowMap(flow)
thoneyvazul@1056:     .source(n)
thoneyvazul@1056:     .target(n);
thoneyvazul@1056: 
thoneyvazul@1056:   ek_test.init();
thoneyvazul@1056:   ek_test.start();
thoneyvazul@1056: 
thoneyvazul@1056:   v = const_ek_test.flowValue();
thoneyvazul@1056:   v = const_ek_test.flow(e);
thoneyvazul@1056: 
thoneyvazul@1056:   const FlowMap& fm = const_ek_test.flowMap();
thoneyvazul@1056:   b = const_ek_test.minCut(n);
thoneyvazul@1056:   const_ek_test.minCutMap(cut);
thoneyvazul@1056: 
thoneyvazul@1056:   ignore_unused_variable_warning(fm);
thoneyvazul@1056: }
thoneyvazul@1056: 
thoneyvazul@1056: int cutValue (const SmartDigraph& g,
thoneyvazul@1056:               const SmartDigraph::NodeMap<bool>& cut,
thoneyvazul@1056:               const SmartDigraph::ArcMap<int>& cap) {
thoneyvazul@1056: 
thoneyvazul@1056:   int c=0;
thoneyvazul@1056:   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
thoneyvazul@1056:     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
thoneyvazul@1056:   }
thoneyvazul@1056:   return c;
thoneyvazul@1056: }
thoneyvazul@1056: 
thoneyvazul@1056: bool checkFlow(const SmartDigraph& g,
thoneyvazul@1056:                const SmartDigraph::ArcMap<int>& flow,
thoneyvazul@1056:                const SmartDigraph::ArcMap<int>& cap,
thoneyvazul@1056:                SmartDigraph::Node s, SmartDigraph::Node t) {
thoneyvazul@1056: 
thoneyvazul@1056:   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
thoneyvazul@1056:     if (flow[e] < 0 || flow[e] > cap[e]) return false;
thoneyvazul@1056:   }
thoneyvazul@1056: 
thoneyvazul@1056:   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
thoneyvazul@1056:     if (n == s || n == t) continue;
thoneyvazul@1056:     int sum = 0;
thoneyvazul@1056:     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
thoneyvazul@1056:       sum += flow[e];
thoneyvazul@1056:     }
thoneyvazul@1056:     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
thoneyvazul@1056:       sum -= flow[e];
thoneyvazul@1056:     }
thoneyvazul@1056:     if (sum != 0) return false;
thoneyvazul@1056:   }
thoneyvazul@1056:   return true;
thoneyvazul@1056: }
thoneyvazul@1056: 
thoneyvazul@1056: int main() {
thoneyvazul@1056: 
thoneyvazul@1056:   typedef SmartDigraph Digraph;
thoneyvazul@1056: 
thoneyvazul@1056:   typedef Digraph::Node Node;
thoneyvazul@1056:   typedef Digraph::NodeIt NodeIt;
thoneyvazul@1056:   typedef Digraph::ArcIt ArcIt;
thoneyvazul@1056:   typedef Digraph::ArcMap<int> CapMap;
thoneyvazul@1056:   typedef Digraph::ArcMap<int> FlowMap;
thoneyvazul@1056:   typedef Digraph::NodeMap<bool> CutMap;
thoneyvazul@1056: 
thoneyvazul@1056:   typedef EdmondsKarp<Digraph, CapMap> EKType;
thoneyvazul@1056: 
thoneyvazul@1056:   Digraph g;
thoneyvazul@1056:   Node s, t;
thoneyvazul@1056:   CapMap cap(g);
thoneyvazul@1056:   std::istringstream input(test_lgf);
thoneyvazul@1056:   DigraphReader<Digraph>(g,input).
thoneyvazul@1056:     arcMap("capacity", cap).
thoneyvazul@1056:     node("source",s).
thoneyvazul@1056:     node("target",t).
thoneyvazul@1056:     run();
thoneyvazul@1056: 
thoneyvazul@1056:   EKType ek_test(g, cap, s, t);
thoneyvazul@1056:   ek_test.run();
thoneyvazul@1056: 
thoneyvazul@1056:   check(checkFlow(g, ek_test.flowMap(), cap, s, t),
thoneyvazul@1056:         "The flow is not feasible.");
thoneyvazul@1056: 
thoneyvazul@1056:   CutMap min_cut(g);
thoneyvazul@1056:   ek_test.minCutMap(min_cut);
thoneyvazul@1056:   int min_cut_value=cutValue(g,min_cut,cap);
thoneyvazul@1056: 
thoneyvazul@1056:   check(ek_test.flowValue() == min_cut_value,
thoneyvazul@1056:         "The max flow value is not equal to the three min cut values.");
thoneyvazul@1056: 
thoneyvazul@1056:   FlowMap flow(g);
thoneyvazul@1056:   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = ek_test.flowMap()[e];
thoneyvazul@1056: 
thoneyvazul@1056:   int flow_value=ek_test.flowValue();
thoneyvazul@1056: 
thoneyvazul@1056:   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
thoneyvazul@1056:   ek_test.flowInit(flow);
thoneyvazul@1056:   ek_test.start();
thoneyvazul@1056: 
thoneyvazul@1056:   CutMap min_cut1(g);
thoneyvazul@1056:   ek_test.minCutMap(min_cut1);
thoneyvazul@1056:   min_cut_value=cutValue(g,min_cut1,cap);
thoneyvazul@1056: 
thoneyvazul@1056:   check(ek_test.flowValue() == min_cut_value &&
thoneyvazul@1056:         min_cut_value == 2*flow_value,
thoneyvazul@1056:         "The max flow value or the min cut value is wrong.");
thoneyvazul@1056: 
thoneyvazul@1056:   check(checkFlow(g, ek_test.flowMap(), cap, s, t),
thoneyvazul@1056:         "The flow is not feasible.");
thoneyvazul@1056: 
thoneyvazul@1056:   CutMap min_cut2(g);
thoneyvazul@1056:   ek_test.minCutMap(min_cut2);
thoneyvazul@1056:   min_cut_value=cutValue(g,min_cut2,cap);
thoneyvazul@1056: 
thoneyvazul@1056:   check(ek_test.flowValue() == min_cut_value &&
thoneyvazul@1056:         min_cut_value == 2*flow_value,
thoneyvazul@1056:         "The max flow value or the three min cut values were not doubled.");
thoneyvazul@1056: 
thoneyvazul@1056: 
thoneyvazul@1056:   ek_test.flowMap(flow);
thoneyvazul@1056: 
thoneyvazul@1056:   NodeIt tmp1(g,s);
thoneyvazul@1056:   ++tmp1;
thoneyvazul@1056:   if ( tmp1 != INVALID ) s=tmp1;
thoneyvazul@1056: 
thoneyvazul@1056:   NodeIt tmp2(g,t);
thoneyvazul@1056:   ++tmp2;
thoneyvazul@1056:   if ( tmp2 != INVALID ) t=tmp2;
thoneyvazul@1056: 
thoneyvazul@1056:   ek_test.source(s);
thoneyvazul@1056:   ek_test.target(t);
thoneyvazul@1056: 
thoneyvazul@1056:   ek_test.run();
thoneyvazul@1056: 
thoneyvazul@1056:   CutMap min_cut3(g);
thoneyvazul@1056:   ek_test.minCutMap(min_cut3);
thoneyvazul@1056:   min_cut_value=cutValue(g,min_cut3,cap);
thoneyvazul@1056: 
thoneyvazul@1056: 
thoneyvazul@1056:   check(ek_test.flowValue() == min_cut_value,
thoneyvazul@1056:         "The max flow value or the three min cut values are incorrect.");
thoneyvazul@1056: 
thoneyvazul@1056:   return 0;
thoneyvazul@1056: }