test/preflow_test.cc
author alpar
Thu, 23 Oct 2008 16:49:06 +0000
changeset 2626 324cfbf66a12
parent 2514 57143c09dc20
permissions -rwxr-xr-x
Adapt the doc generation to the hg repo
     1 /* -*- C++ -*-
     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/dimacs.h>
    25 #include <lemon/preflow.h>
    26 #include <lemon/concepts/graph.h>
    27 #include <lemon/concepts/maps.h>
    28 
    29 using namespace lemon;
    30 
    31 void checkPreflow() 
    32 {
    33   typedef int VType;
    34   typedef concepts::Graph Graph;
    35 
    36   typedef Graph::Node Node;
    37   typedef Graph::Edge Edge;
    38   typedef concepts::ReadMap<Edge,VType> CapMap;
    39   typedef concepts::ReadWriteMap<Edge,VType> FlowMap;
    40   typedef concepts::WriteMap<Node,bool> CutMap;
    41  
    42   Graph g;
    43   Node n;
    44   Edge e;
    45   CapMap cap;
    46   FlowMap flow;
    47   CutMap cut;
    48 
    49   Preflow<Graph, CapMap>::DefFlowMap<FlowMap>::Create preflow_test(g,cap,n,n);
    50 
    51   preflow_test.capacityMap(cap);
    52   flow = preflow_test.flowMap();
    53   preflow_test.flowMap(flow);
    54   preflow_test.source(n);
    55   preflow_test.target(n);
    56   
    57   preflow_test.init();
    58   preflow_test.flowInit(cap);
    59   preflow_test.startFirstPhase();
    60   preflow_test.startSecondPhase();
    61   preflow_test.run();
    62   preflow_test.runMinCut();
    63 
    64   preflow_test.flowValue();
    65   preflow_test.minCut(n);
    66   preflow_test.minCutMap(cut);
    67   preflow_test.flow(e);
    68 
    69 }
    70 
    71 int cutValue (const SmartGraph& g, 
    72 	      const SmartGraph::NodeMap<bool>& cut, 
    73 	      const SmartGraph::EdgeMap<int>& cap) {
    74   
    75   int c=0;
    76   for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
    77     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
    78   }
    79   return c;
    80 }
    81 
    82 bool checkFlow(const SmartGraph& g, 
    83 	       const SmartGraph::EdgeMap<int>& flow, 
    84 	       const SmartGraph::EdgeMap<int>& cap, 
    85 	       SmartGraph::Node s, SmartGraph::Node t) {
    86 
    87   for (SmartGraph::EdgeIt e(g); e != INVALID; ++e) {
    88     if (flow[e] < 0 || flow[e] > cap[e]) return false;
    89   }
    90 
    91   for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
    92     if (n == s || n == t) continue;
    93     int sum = 0;
    94     for (SmartGraph::OutEdgeIt e(g, n); e != INVALID; ++e) {
    95       sum += flow[e];
    96     }
    97     for (SmartGraph::InEdgeIt e(g, n); e != INVALID; ++e) {
    98       sum -= flow[e];
    99     }
   100     if (sum != 0) return false;
   101   }
   102   return true;
   103 }
   104 
   105 int main() {
   106 
   107   typedef SmartGraph Graph;
   108   
   109   typedef Graph::Node Node;
   110   typedef Graph::NodeIt NodeIt;
   111   typedef Graph::EdgeIt EdgeIt;
   112   typedef Graph::EdgeMap<int> CapMap;
   113   typedef Graph::EdgeMap<int> FlowMap;
   114   typedef Graph::NodeMap<bool> CutMap;
   115 
   116   typedef Preflow<Graph, CapMap> PType;
   117 
   118   std::string f_name;
   119   if( getenv("srcdir") )
   120     f_name = std::string(getenv("srcdir"));
   121   else f_name = ".";
   122   f_name += "/test/preflow_graph.dim";
   123   
   124   std::ifstream file(f_name.c_str());
   125   
   126   check(file, "Input file '" << f_name << "' not found.");
   127   
   128   Graph g;
   129   Node s, t;
   130   CapMap cap(g);
   131   readDimacs(file, g, cap, s, t);
   132 
   133   PType preflow_test(g, cap, s, t);
   134   preflow_test.run();
   135     
   136   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   137 	"The flow is not feasible.");
   138 
   139   CutMap min_cut(g);
   140   preflow_test.minCutMap(min_cut); 
   141   int min_cut_value=cutValue(g,min_cut,cap);
   142   
   143   check(preflow_test.flowValue() == min_cut_value,
   144 	"The max flow value is not equal to the three min cut values.");
   145 
   146   FlowMap flow(g);
   147   flow = preflow_test.flowMap();
   148 
   149   int flow_value=preflow_test.flowValue();
   150 
   151   for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
   152   preflow_test.flowInit(flow);
   153   preflow_test.startFirstPhase();
   154 
   155   CutMap min_cut1(g);
   156   preflow_test.minCutMap(min_cut1); 
   157   min_cut_value=cutValue(g,min_cut1,cap);
   158    
   159   check(preflow_test.flowValue() == min_cut_value &&
   160 	min_cut_value == 2*flow_value,
   161 	"The max flow value or the min cut value is wrong.");
   162 
   163   preflow_test.startSecondPhase();
   164 
   165   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   166 	"The flow is not feasible.");
   167 
   168   CutMap min_cut2(g);
   169   preflow_test.minCutMap(min_cut2); 
   170   min_cut_value=cutValue(g,min_cut2,cap);
   171    
   172   check(preflow_test.flowValue() == min_cut_value &&
   173 	min_cut_value == 2*flow_value,
   174 	"The max flow value or the three min cut values were not doubled");
   175 
   176 
   177   preflow_test.flowMap(flow); 
   178 
   179   NodeIt tmp1(g,s);
   180   ++tmp1;
   181   if ( tmp1 != INVALID ) s=tmp1;
   182 
   183   NodeIt tmp2(g,t);
   184   ++tmp2;
   185   if ( tmp2 != INVALID ) t=tmp2;
   186 
   187   preflow_test.source(s);
   188   preflow_test.target(t); 
   189   
   190   preflow_test.run();
   191 
   192   CutMap min_cut3(g);
   193   preflow_test.minCutMap(min_cut3); 
   194   min_cut_value=cutValue(g,min_cut3,cap);
   195    
   196 
   197   check(preflow_test.flowValue() == min_cut_value,
   198 	"The max flow value or the three min cut values are incorrect.");
   199   
   200   return 0;
   201 }