test/preflow_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 25 Aug 2010 21:34:58 +0200
changeset 742 16d466589b54
parent 577 65fbcf2f978a
child 761 f1398882a928
child 796 7e368d9b67f7
permissions -rw-r--r--
Backport the CMAKE related changesets from the main branch

[e20fecd1945f] Add check target for CMake (#388)
[e74b5db4f2c6] Put the output of chg-len.py in the version string (#389)
[7d166b8b8018] Safer call of ./scripts/chg-len.py on Windows (#389)
[659ba4805a48] Make CMAKE config more consistent with configure.ac (#390)
[63e4468c680e] Add 'Maintainer' CMAKE build type (#388, #390)
[a725503acfe9] Allow CPACK configuration on all platforms
[10242c611190] Create and install lemon.pc (#393)
[48e29534cf03] The deafult target doesn't build lp_test and mip_test (#388)
[0fbbdd578c06] Full path for DoxygenLayout.xml in Doxyfile.in (#395)
[481496e6d71f] SOURCE_BROWSER Doxygen switch is configurable from CMAKE (#395)
[09282720100b] update-external-tags CMAKE target (#395)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 
    21 #include "test_tools.h"
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/preflow.h>
    24 #include <lemon/concepts/digraph.h>
    25 #include <lemon/concepts/maps.h>
    26 #include <lemon/lgf_reader.h>
    27 #include <lemon/elevator.h>
    28 
    29 using namespace lemon;
    30 
    31 char test_lgf[] =
    32   "@nodes\n"
    33   "label\n"
    34   "0\n"
    35   "1\n"
    36   "2\n"
    37   "3\n"
    38   "4\n"
    39   "5\n"
    40   "6\n"
    41   "7\n"
    42   "8\n"
    43   "9\n"
    44   "@arcs\n"
    45   "    label capacity\n"
    46   "0 1 0     20\n"
    47   "0 2 1     0\n"
    48   "1 1 2     3\n"
    49   "1 2 3     8\n"
    50   "1 3 4     8\n"
    51   "2 5 5     5\n"
    52   "3 2 6     5\n"
    53   "3 5 7     5\n"
    54   "3 6 8     5\n"
    55   "4 3 9     3\n"
    56   "5 7 10    3\n"
    57   "5 6 11    10\n"
    58   "5 8 12    10\n"
    59   "6 8 13    8\n"
    60   "8 9 14    20\n"
    61   "8 1 15    5\n"
    62   "9 5 16    5\n"
    63   "@attributes\n"
    64   "source 1\n"
    65   "target 8\n";
    66 
    67 void checkPreflowCompile()
    68 {
    69   typedef int VType;
    70   typedef concepts::Digraph Digraph;
    71 
    72   typedef Digraph::Node Node;
    73   typedef Digraph::Arc Arc;
    74   typedef concepts::ReadMap<Arc,VType> CapMap;
    75   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    76   typedef concepts::WriteMap<Node,bool> CutMap;
    77 
    78   typedef Elevator<Digraph, Digraph::Node> Elev;
    79   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    80 
    81   Digraph g;
    82   Node n;
    83   Arc e;
    84   CapMap cap;
    85   FlowMap flow;
    86   CutMap cut;
    87   VType v;
    88   bool b;
    89 
    90   typedef Preflow<Digraph, CapMap>
    91             ::SetFlowMap<FlowMap>
    92             ::SetElevator<Elev>
    93             ::SetStandardElevator<LinkedElev>
    94             ::Create PreflowType;
    95   PreflowType preflow_test(g, cap, n, n);
    96   const PreflowType& const_preflow_test = preflow_test;
    97 
    98   preflow_test
    99     .capacityMap(cap)
   100     .flowMap(flow)
   101     .source(n)
   102     .target(n);
   103 
   104   preflow_test.init();
   105   preflow_test.init(cap);
   106   preflow_test.startFirstPhase();
   107   preflow_test.startSecondPhase();
   108   preflow_test.run();
   109   preflow_test.runMinCut();
   110 
   111   v = const_preflow_test.flowValue();
   112   v = const_preflow_test.flow(e);
   113   const FlowMap& fm = const_preflow_test.flowMap();
   114   b = const_preflow_test.minCut(n);
   115   const_preflow_test.minCutMap(cut);
   116   
   117   ignore_unused_variable_warning(fm);
   118 }
   119 
   120 int cutValue (const SmartDigraph& g,
   121               const SmartDigraph::NodeMap<bool>& cut,
   122               const SmartDigraph::ArcMap<int>& cap) {
   123 
   124   int c=0;
   125   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
   126     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
   127   }
   128   return c;
   129 }
   130 
   131 bool checkFlow(const SmartDigraph& g,
   132                const SmartDigraph::ArcMap<int>& flow,
   133                const SmartDigraph::ArcMap<int>& cap,
   134                SmartDigraph::Node s, SmartDigraph::Node t) {
   135 
   136   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
   137     if (flow[e] < 0 || flow[e] > cap[e]) return false;
   138   }
   139 
   140   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   141     if (n == s || n == t) continue;
   142     int sum = 0;
   143     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
   144       sum += flow[e];
   145     }
   146     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   147       sum -= flow[e];
   148     }
   149     if (sum != 0) return false;
   150   }
   151   return true;
   152 }
   153 
   154 void initFlowTest()
   155 {
   156   DIGRAPH_TYPEDEFS(SmartDigraph);
   157   
   158   SmartDigraph g;
   159   SmartDigraph::ArcMap<int> cap(g),iflow(g);
   160   Node s=g.addNode(); Node t=g.addNode();
   161   Node n1=g.addNode(); Node n2=g.addNode();
   162   Arc a;
   163   a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
   164   a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
   165   a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
   166 
   167   Preflow<SmartDigraph> pre(g,cap,s,t);
   168   pre.init(iflow);
   169   pre.startFirstPhase();
   170   check(pre.flowValue() == 10, "The incorrect max flow value.");
   171   check(pre.minCut(s), "Wrong min cut (Node s).");
   172   check(pre.minCut(n1), "Wrong min cut (Node n1).");
   173   check(!pre.minCut(n2), "Wrong min cut (Node n2).");
   174   check(!pre.minCut(t), "Wrong min cut (Node t).");
   175 }
   176 
   177 
   178 int main() {
   179 
   180   typedef SmartDigraph Digraph;
   181 
   182   typedef Digraph::Node Node;
   183   typedef Digraph::NodeIt NodeIt;
   184   typedef Digraph::ArcIt ArcIt;
   185   typedef Digraph::ArcMap<int> CapMap;
   186   typedef Digraph::ArcMap<int> FlowMap;
   187   typedef Digraph::NodeMap<bool> CutMap;
   188 
   189   typedef Preflow<Digraph, CapMap> PType;
   190 
   191   Digraph g;
   192   Node s, t;
   193   CapMap cap(g);
   194   std::istringstream input(test_lgf);
   195   DigraphReader<Digraph>(g,input).
   196     arcMap("capacity", cap).
   197     node("source",s).
   198     node("target",t).
   199     run();
   200 
   201   PType preflow_test(g, cap, s, t);
   202   preflow_test.run();
   203 
   204   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   205         "The flow is not feasible.");
   206 
   207   CutMap min_cut(g);
   208   preflow_test.minCutMap(min_cut);
   209   int min_cut_value=cutValue(g,min_cut,cap);
   210 
   211   check(preflow_test.flowValue() == min_cut_value,
   212         "The max flow value is not equal to the three min cut values.");
   213 
   214   FlowMap flow(g);
   215   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
   216 
   217   int flow_value=preflow_test.flowValue();
   218 
   219   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
   220   preflow_test.init(flow);
   221   preflow_test.startFirstPhase();
   222 
   223   CutMap min_cut1(g);
   224   preflow_test.minCutMap(min_cut1);
   225   min_cut_value=cutValue(g,min_cut1,cap);
   226 
   227   check(preflow_test.flowValue() == min_cut_value &&
   228         min_cut_value == 2*flow_value,
   229         "The max flow value or the min cut value is wrong.");
   230 
   231   preflow_test.startSecondPhase();
   232 
   233   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   234         "The flow is not feasible.");
   235 
   236   CutMap min_cut2(g);
   237   preflow_test.minCutMap(min_cut2);
   238   min_cut_value=cutValue(g,min_cut2,cap);
   239 
   240   check(preflow_test.flowValue() == min_cut_value &&
   241         min_cut_value == 2*flow_value,
   242         "The max flow value or the three min cut values were not doubled");
   243 
   244 
   245   preflow_test.flowMap(flow);
   246 
   247   NodeIt tmp1(g,s);
   248   ++tmp1;
   249   if ( tmp1 != INVALID ) s=tmp1;
   250 
   251   NodeIt tmp2(g,t);
   252   ++tmp2;
   253   if ( tmp2 != INVALID ) t=tmp2;
   254 
   255   preflow_test.source(s);
   256   preflow_test.target(t);
   257 
   258   preflow_test.run();
   259 
   260   CutMap min_cut3(g);
   261   preflow_test.minCutMap(min_cut3);
   262   min_cut_value=cutValue(g,min_cut3,cap);
   263 
   264 
   265   check(preflow_test.flowValue() == min_cut_value,
   266         "The max flow value or the three min cut values are incorrect.");
   267 
   268   initFlowTest();
   269   
   270   return 0;
   271 }