test/preflow_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 30 Nov 2008 00:50:31 +0100
changeset 393 37054b67d807
parent 391 624e673efa76
child 394 e7707b3069f1
permissions -rw-r--r--
Many doc improvements for Preflow (#176)

- More precise doc for members.
- Add doc for public types.
- Hide the doc of the traits class parameter.
- Removing \author comments.
- Use \tparam for template parameters.
     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 
    29 using namespace lemon;
    30 
    31 void checkPreflow()
    32 {
    33   typedef int VType;
    34   typedef concepts::Digraph Digraph;
    35 
    36   typedef Digraph::Node Node;
    37   typedef Digraph::Arc Arc;
    38   typedef concepts::ReadMap<Arc,VType> CapMap;
    39   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    40   typedef concepts::WriteMap<Node,bool> CutMap;
    41 
    42   Digraph g;
    43   Node n;
    44   Arc e;
    45   CapMap cap;
    46   FlowMap flow;
    47   CutMap cut;
    48 
    49   Preflow<Digraph, CapMap>::SetFlowMap<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.init(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 SmartDigraph& g,
    72               const SmartDigraph::NodeMap<bool>& cut,
    73               const SmartDigraph::ArcMap<int>& cap) {
    74 
    75   int c=0;
    76   for(SmartDigraph::ArcIt 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 SmartDigraph& g,
    83                const SmartDigraph::ArcMap<int>& flow,
    84                const SmartDigraph::ArcMap<int>& cap,
    85                SmartDigraph::Node s, SmartDigraph::Node t) {
    86 
    87   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
    88     if (flow[e] < 0 || flow[e] > cap[e]) return false;
    89   }
    90 
    91   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
    92     if (n == s || n == t) continue;
    93     int sum = 0;
    94     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
    95       sum += flow[e];
    96     }
    97     for (SmartDigraph::InArcIt 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 SmartDigraph Digraph;
   108 
   109   typedef Digraph::Node Node;
   110   typedef Digraph::NodeIt NodeIt;
   111   typedef Digraph::ArcIt ArcIt;
   112   typedef Digraph::ArcMap<int> CapMap;
   113   typedef Digraph::ArcMap<int> FlowMap;
   114   typedef Digraph::NodeMap<bool> CutMap;
   115 
   116   typedef Preflow<Digraph, 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.lgf";
   123 
   124   std::ifstream file(f_name.c_str());
   125 
   126   check(file, "Input file '" << f_name << "' not found.");
   127 
   128   Digraph g;
   129   Node s, t;
   130   CapMap cap(g);
   131   DigraphReader<Digraph>(g,file).
   132     arcMap("capacity", cap).
   133     node("source",s).
   134     node("target",t).
   135     run();
   136 
   137   PType preflow_test(g, cap, s, t);
   138   preflow_test.run();
   139 
   140   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   141         "The flow is not feasible.");
   142 
   143   CutMap min_cut(g);
   144   preflow_test.minCutMap(min_cut);
   145   int min_cut_value=cutValue(g,min_cut,cap);
   146 
   147   check(preflow_test.flowValue() == min_cut_value,
   148         "The max flow value is not equal to the three min cut values.");
   149 
   150   FlowMap flow(g);
   151   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
   152 
   153   int flow_value=preflow_test.flowValue();
   154 
   155   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
   156   preflow_test.init(flow);
   157   preflow_test.startFirstPhase();
   158 
   159   CutMap min_cut1(g);
   160   preflow_test.minCutMap(min_cut1);
   161   min_cut_value=cutValue(g,min_cut1,cap);
   162 
   163   check(preflow_test.flowValue() == min_cut_value &&
   164         min_cut_value == 2*flow_value,
   165         "The max flow value or the min cut value is wrong.");
   166 
   167   preflow_test.startSecondPhase();
   168 
   169   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   170         "The flow is not feasible.");
   171 
   172   CutMap min_cut2(g);
   173   preflow_test.minCutMap(min_cut2);
   174   min_cut_value=cutValue(g,min_cut2,cap);
   175 
   176   check(preflow_test.flowValue() == min_cut_value &&
   177         min_cut_value == 2*flow_value,
   178         "The max flow value or the three min cut values were not doubled");
   179 
   180 
   181   preflow_test.flowMap(flow);
   182 
   183   NodeIt tmp1(g,s);
   184   ++tmp1;
   185   if ( tmp1 != INVALID ) s=tmp1;
   186 
   187   NodeIt tmp2(g,t);
   188   ++tmp2;
   189   if ( tmp2 != INVALID ) t=tmp2;
   190 
   191   preflow_test.source(s);
   192   preflow_test.target(t);
   193 
   194   preflow_test.run();
   195 
   196   CutMap min_cut3(g);
   197   preflow_test.minCutMap(min_cut3);
   198   min_cut_value=cutValue(g,min_cut3,cap);
   199 
   200 
   201   check(preflow_test.flowValue() == min_cut_value,
   202         "The max flow value or the three min cut values are incorrect.");
   203 
   204   return 0;
   205 }