test/preflow_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 01 Dec 2008 14:18:40 +0000
changeset 404 59d3aa4f921f
parent 392 db3251947eba
child 423 ff48c2738fb2
permissions -rw-r--r--
Merge
     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-2008
     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 <fstream>
    20 #include <string>
    21 
    22 #include "test_tools.h"
    23 #include <lemon/smart_graph.h>
    24 #include <lemon/preflow.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concepts/maps.h>
    27 #include <lemon/lgf_reader.h>
    28 #include <lemon/elevator.h>
    29 
    30 using namespace lemon;
    31 
    32 void checkPreflowCompile()
    33 {
    34   typedef int VType;
    35   typedef concepts::Digraph Digraph;
    36 
    37   typedef Digraph::Node Node;
    38   typedef Digraph::Arc Arc;
    39   typedef concepts::ReadMap<Arc,VType> CapMap;
    40   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    41   typedef concepts::WriteMap<Node,bool> CutMap;
    42 
    43   typedef Elevator<Digraph, Digraph::Node> Elev;
    44   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    45 
    46   Digraph g;
    47   Node n;
    48   Arc e;
    49   CapMap cap;
    50   FlowMap flow;
    51   CutMap cut;
    52 
    53   Preflow<Digraph, CapMap>
    54     ::SetFlowMap<FlowMap>
    55     ::SetElevator<Elev>
    56     ::SetStandardElevator<LinkedElev>
    57     ::Create preflow_test(g,cap,n,n);
    58 
    59   preflow_test.capacityMap(cap);
    60   flow = preflow_test.flowMap();
    61   preflow_test.flowMap(flow);
    62   preflow_test.source(n);
    63   preflow_test.target(n);
    64 
    65   preflow_test.init();
    66   preflow_test.init(cap);
    67   preflow_test.startFirstPhase();
    68   preflow_test.startSecondPhase();
    69   preflow_test.run();
    70   preflow_test.runMinCut();
    71 
    72   preflow_test.flowValue();
    73   preflow_test.minCut(n);
    74   preflow_test.minCutMap(cut);
    75   preflow_test.flow(e);
    76 
    77 }
    78 
    79 int cutValue (const SmartDigraph& g,
    80               const SmartDigraph::NodeMap<bool>& cut,
    81               const SmartDigraph::ArcMap<int>& cap) {
    82 
    83   int c=0;
    84   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
    85     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
    86   }
    87   return c;
    88 }
    89 
    90 bool checkFlow(const SmartDigraph& g,
    91                const SmartDigraph::ArcMap<int>& flow,
    92                const SmartDigraph::ArcMap<int>& cap,
    93                SmartDigraph::Node s, SmartDigraph::Node t) {
    94 
    95   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    96     if (flow[e] < 0 || flow[e] > cap[e]) return false;
    97   }
    98 
    99   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   100     if (n == s || n == t) continue;
   101     int sum = 0;
   102     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
   103       sum += flow[e];
   104     }
   105     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   106       sum -= flow[e];
   107     }
   108     if (sum != 0) return false;
   109   }
   110   return true;
   111 }
   112 
   113 int main() {
   114 
   115   typedef SmartDigraph Digraph;
   116 
   117   typedef Digraph::Node Node;
   118   typedef Digraph::NodeIt NodeIt;
   119   typedef Digraph::ArcIt ArcIt;
   120   typedef Digraph::ArcMap<int> CapMap;
   121   typedef Digraph::ArcMap<int> FlowMap;
   122   typedef Digraph::NodeMap<bool> CutMap;
   123 
   124   typedef Preflow<Digraph, CapMap> PType;
   125 
   126   std::string f_name;
   127   if( getenv("srcdir") )
   128     f_name = std::string(getenv("srcdir"));
   129   else f_name = ".";
   130   f_name += "/test/preflow_graph.lgf";
   131 
   132   std::ifstream file(f_name.c_str());
   133 
   134   check(file, "Input file '" << f_name << "' not found.");
   135 
   136   Digraph g;
   137   Node s, t;
   138   CapMap cap(g);
   139   DigraphReader<Digraph>(g,file).
   140     arcMap("capacity", cap).
   141     node("source",s).
   142     node("target",t).
   143     run();
   144 
   145   PType preflow_test(g, cap, s, t);
   146   preflow_test.run();
   147 
   148   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   149         "The flow is not feasible.");
   150 
   151   CutMap min_cut(g);
   152   preflow_test.minCutMap(min_cut);
   153   int min_cut_value=cutValue(g,min_cut,cap);
   154 
   155   check(preflow_test.flowValue() == min_cut_value,
   156         "The max flow value is not equal to the three min cut values.");
   157 
   158   FlowMap flow(g);
   159   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
   160 
   161   int flow_value=preflow_test.flowValue();
   162 
   163   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
   164   preflow_test.init(flow);
   165   preflow_test.startFirstPhase();
   166 
   167   CutMap min_cut1(g);
   168   preflow_test.minCutMap(min_cut1);
   169   min_cut_value=cutValue(g,min_cut1,cap);
   170 
   171   check(preflow_test.flowValue() == min_cut_value &&
   172         min_cut_value == 2*flow_value,
   173         "The max flow value or the min cut value is wrong.");
   174 
   175   preflow_test.startSecondPhase();
   176 
   177   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   178         "The flow is not feasible.");
   179 
   180   CutMap min_cut2(g);
   181   preflow_test.minCutMap(min_cut2);
   182   min_cut_value=cutValue(g,min_cut2,cap);
   183 
   184   check(preflow_test.flowValue() == min_cut_value &&
   185         min_cut_value == 2*flow_value,
   186         "The max flow value or the three min cut values were not doubled");
   187 
   188 
   189   preflow_test.flowMap(flow);
   190 
   191   NodeIt tmp1(g,s);
   192   ++tmp1;
   193   if ( tmp1 != INVALID ) s=tmp1;
   194 
   195   NodeIt tmp2(g,t);
   196   ++tmp2;
   197   if ( tmp2 != INVALID ) t=tmp2;
   198 
   199   preflow_test.source(s);
   200   preflow_test.target(t);
   201 
   202   preflow_test.run();
   203 
   204   CutMap min_cut3(g);
   205   preflow_test.minCutMap(min_cut3);
   206   min_cut_value=cutValue(g,min_cut3,cap);
   207 
   208 
   209   check(preflow_test.flowValue() == min_cut_value,
   210         "The max flow value or the three min cut values are incorrect.");
   211 
   212   return 0;
   213 }