test/preflow_test.cc
author alpar
Sat, 19 Apr 2008 13:04:51 +0000
changeset 2608 207efbaea269
parent 2514 57143c09dc20
permissions -rwxr-xr-x
Avoid warning in random.h (backport of chgset 4790635473ef from lemon-1.0)
alpar@906
     1
/* -*- C++ -*-
alpar@906
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906
     8
 *
alpar@906
     9
 * Permission to use, modify and distribute this software is granted
alpar@906
    10
 * provided that this copyright notice appears in all copies. For
alpar@906
    11
 * precise terms see the accompanying LICENSE file.
alpar@906
    12
 *
alpar@906
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    14
 * express or implied, and with no claim as to its suitability for any
alpar@906
    15
 * purpose.
alpar@906
    16
 *
alpar@906
    17
 */
alpar@906
    18
jacint@833
    19
#include <fstream>
klao@858
    20
#include <string>
klao@858
    21
jacint@833
    22
#include "test_tools.h"
alpar@921
    23
#include <lemon/smart_graph.h>
alpar@921
    24
#include <lemon/dimacs.h>
alpar@921
    25
#include <lemon/preflow.h>
alpar@2260
    26
#include <lemon/concepts/graph.h>
alpar@2260
    27
#include <lemon/concepts/maps.h>
alpar@855
    28
alpar@921
    29
using namespace lemon;
jacint@833
    30
deba@2514
    31
void checkPreflow() 
jacint@833
    32
{
jacint@833
    33
  typedef int VType;
alpar@2260
    34
  typedef concepts::Graph Graph;
jacint@833
    35
jacint@833
    36
  typedef Graph::Node Node;
jacint@833
    37
  typedef Graph::Edge Edge;
alpar@2260
    38
  typedef concepts::ReadMap<Edge,VType> CapMap;
alpar@2260
    39
  typedef concepts::ReadWriteMap<Edge,VType> FlowMap;
deba@2514
    40
  typedef concepts::WriteMap<Node,bool> CutMap;
jacint@833
    41
 
marci@940
    42
  Graph g;
jacint@833
    43
  Node n;
deba@2514
    44
  Edge e;
jacint@833
    45
  CapMap cap;
jacint@833
    46
  FlowMap flow;
jacint@833
    47
  CutMap cut;
jacint@833
    48
deba@2514
    49
  Preflow<Graph, CapMap>::DefFlowMap<FlowMap>::Create preflow_test(g,cap,n,n);
jacint@833
    50
deba@2514
    51
  preflow_test.capacityMap(cap);
deba@2514
    52
  flow = preflow_test.flowMap();
deba@2514
    53
  preflow_test.flowMap(flow);
deba@2514
    54
  preflow_test.source(n);
deba@2514
    55
  preflow_test.target(n);
deba@2514
    56
  
deba@2514
    57
  preflow_test.init();
deba@2514
    58
  preflow_test.flowInit(cap);
deba@2514
    59
  preflow_test.startFirstPhase();
deba@2514
    60
  preflow_test.startSecondPhase();
jacint@833
    61
  preflow_test.run();
deba@2514
    62
  preflow_test.runMinCut();
deba@2514
    63
jacint@833
    64
  preflow_test.flowValue();
deba@2514
    65
  preflow_test.minCut(n);
deba@2514
    66
  preflow_test.minCutMap(cut);
deba@2514
    67
  preflow_test.flow(e);
jacint@833
    68
jacint@833
    69
}
jacint@833
    70
deba@2514
    71
int cutValue (const SmartGraph& g, 
deba@2514
    72
	      const SmartGraph::NodeMap<bool>& cut, 
deba@2514
    73
	      const SmartGraph::EdgeMap<int>& cap) {
jacint@833
    74
  
jacint@833
    75
  int c=0;
marci@940
    76
  for(SmartGraph::EdgeIt e(g); e!=INVALID; ++e) {
alpar@986
    77
    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
jacint@833
    78
  }
jacint@833
    79
  return c;
jacint@833
    80
}
jacint@833
    81
deba@2514
    82
bool checkFlow(const SmartGraph& g, 
deba@2514
    83
	       const SmartGraph::EdgeMap<int>& flow, 
deba@2514
    84
	       const SmartGraph::EdgeMap<int>& cap, 
deba@2514
    85
	       SmartGraph::Node s, SmartGraph::Node t) {
deba@2514
    86
deba@2514
    87
  for (SmartGraph::EdgeIt e(g); e != INVALID; ++e) {
deba@2514
    88
    if (flow[e] < 0 || flow[e] > cap[e]) return false;
deba@2514
    89
  }
deba@2514
    90
deba@2514
    91
  for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
deba@2514
    92
    if (n == s || n == t) continue;
deba@2514
    93
    int sum = 0;
deba@2514
    94
    for (SmartGraph::OutEdgeIt e(g, n); e != INVALID; ++e) {
deba@2514
    95
      sum += flow[e];
deba@2514
    96
    }
deba@2514
    97
    for (SmartGraph::InEdgeIt e(g, n); e != INVALID; ++e) {
deba@2514
    98
      sum -= flow[e];
deba@2514
    99
    }
deba@2514
   100
    if (sum != 0) return false;
deba@2514
   101
  }
deba@2514
   102
  return true;
deba@2514
   103
}
deba@2514
   104
jacint@833
   105
int main() {
jacint@833
   106
jacint@833
   107
  typedef SmartGraph Graph;
jacint@833
   108
  
alpar@842
   109
  typedef Graph::Node Node;
jacint@833
   110
  typedef Graph::NodeIt NodeIt;
jacint@833
   111
  typedef Graph::EdgeIt EdgeIt;
jacint@833
   112
  typedef Graph::EdgeMap<int> CapMap;
jacint@833
   113
  typedef Graph::EdgeMap<int> FlowMap;
jacint@833
   114
  typedef Graph::NodeMap<bool> CutMap;
jacint@833
   115
deba@2514
   116
  typedef Preflow<Graph, CapMap> PType;
jacint@833
   117
klao@859
   118
  std::string f_name;
alpar@1215
   119
  if( getenv("srcdir") )
alpar@1215
   120
    f_name = std::string(getenv("srcdir"));
alpar@1215
   121
  else f_name = ".";
ladanyi@2108
   122
  f_name += "/test/preflow_graph.dim";
alpar@855
   123
  
klao@858
   124
  std::ifstream file(f_name.c_str());
alpar@855
   125
  
klao@858
   126
  check(file, "Input file '" << f_name << "' not found.");
jacint@833
   127
  
marci@940
   128
  Graph g;
alpar@842
   129
  Node s, t;
marci@940
   130
  CapMap cap(g);
marci@940
   131
  readDimacs(file, g, cap, s, t);
jacint@833
   132
deba@2514
   133
  PType preflow_test(g, cap, s, t);
deba@2514
   134
  preflow_test.run();
deba@2514
   135
    
deba@2514
   136
  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
deba@2514
   137
	"The flow is not feasible.");
jacint@887
   138
deba@2514
   139
  CutMap min_cut(g);
deba@2514
   140
  preflow_test.minCutMap(min_cut); 
deba@2514
   141
  int min_cut_value=cutValue(g,min_cut,cap);
deba@2514
   142
  
deba@2514
   143
  check(preflow_test.flowValue() == min_cut_value,
deba@2514
   144
	"The max flow value is not equal to the three min cut values.");
jacint@887
   145
deba@2514
   146
  FlowMap flow(g);
deba@2514
   147
  flow = preflow_test.flowMap();
jacint@833
   148
jacint@833
   149
  int flow_value=preflow_test.flowValue();
jacint@833
   150
deba@2514
   151
  for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e]; 
deba@2514
   152
  preflow_test.flowInit(flow);
deba@2514
   153
  preflow_test.startFirstPhase();
jacint@833
   154
deba@2514
   155
  CutMap min_cut1(g);
deba@2514
   156
  preflow_test.minCutMap(min_cut1); 
deba@2514
   157
  min_cut_value=cutValue(g,min_cut1,cap);
jacint@833
   158
   
jacint@833
   159
  check(preflow_test.flowValue() == min_cut_value &&
jacint@833
   160
	min_cut_value == 2*flow_value,
jacint@833
   161
	"The max flow value or the min cut value is wrong.");
jacint@833
   162
deba@2514
   163
  preflow_test.startSecondPhase();
jacint@833
   164
deba@2514
   165
  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
deba@2514
   166
	"The flow is not feasible.");
deba@2514
   167
deba@2514
   168
  CutMap min_cut2(g);
deba@2514
   169
  preflow_test.minCutMap(min_cut2); 
deba@2514
   170
  min_cut_value=cutValue(g,min_cut2,cap);
jacint@833
   171
   
jacint@833
   172
  check(preflow_test.flowValue() == min_cut_value &&
jacint@833
   173
	min_cut_value == 2*flow_value,
jacint@833
   174
	"The max flow value or the three min cut values were not doubled");
jacint@833
   175
jacint@887
   176
alpar@1222
   177
  preflow_test.flowMap(flow); 
jacint@887
   178
marci@940
   179
  NodeIt tmp1(g,s);
jacint@887
   180
  ++tmp1;
jacint@887
   181
  if ( tmp1 != INVALID ) s=tmp1;
jacint@887
   182
marci@940
   183
  NodeIt tmp2(g,t);
jacint@887
   184
  ++tmp2;
jacint@887
   185
  if ( tmp2 != INVALID ) t=tmp2;
jacint@887
   186
alpar@1222
   187
  preflow_test.source(s);
alpar@1222
   188
  preflow_test.target(t); 
jacint@887
   189
  
jacint@833
   190
  preflow_test.run();
jacint@833
   191
deba@2514
   192
  CutMap min_cut3(g);
deba@2514
   193
  preflow_test.minCutMap(min_cut3); 
deba@2514
   194
  min_cut_value=cutValue(g,min_cut3,cap);
jacint@833
   195
   
jacint@833
   196
deba@2514
   197
  check(preflow_test.flowValue() == min_cut_value,
jacint@833
   198
	"The max flow value or the three min cut values are incorrect.");
deba@2514
   199
  
deba@2514
   200
  return 0;
jacint@833
   201
}