test/preflow_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 423 ff48c2738fb2
child 585 65fbcf2f978a
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
alpar@389
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@389
     2
 *
alpar@389
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@389
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@389
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@389
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@389
     8
 *
alpar@389
     9
 * Permission to use, modify and distribute this software is granted
alpar@389
    10
 * provided that this copyright notice appears in all copies. For
alpar@389
    11
 * precise terms see the accompanying LICENSE file.
alpar@389
    12
 *
alpar@389
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@389
    14
 * express or implied, and with no claim as to its suitability for any
alpar@389
    15
 * purpose.
alpar@389
    16
 *
alpar@389
    17
 */
alpar@389
    18
alpar@423
    19
#include <iostream>
alpar@389
    20
alpar@389
    21
#include "test_tools.h"
alpar@389
    22
#include <lemon/smart_graph.h>
alpar@389
    23
#include <lemon/preflow.h>
alpar@389
    24
#include <lemon/concepts/digraph.h>
alpar@389
    25
#include <lemon/concepts/maps.h>
alpar@389
    26
#include <lemon/lgf_reader.h>
kpeter@394
    27
#include <lemon/elevator.h>
alpar@389
    28
alpar@389
    29
using namespace lemon;
alpar@389
    30
alpar@423
    31
char test_lgf[] =
alpar@423
    32
  "@nodes\n"
alpar@423
    33
  "label\n"
alpar@423
    34
  "0\n"
alpar@423
    35
  "1\n"
alpar@423
    36
  "2\n"
alpar@423
    37
  "3\n"
alpar@423
    38
  "4\n"
alpar@423
    39
  "5\n"
alpar@423
    40
  "6\n"
alpar@423
    41
  "7\n"
alpar@423
    42
  "8\n"
alpar@423
    43
  "9\n"
alpar@423
    44
  "@arcs\n"
alpar@423
    45
  "    label capacity\n"
alpar@423
    46
  "0 1 0     20\n"
alpar@423
    47
  "0 2 1     0\n"
alpar@423
    48
  "1 1 2     3\n"
alpar@423
    49
  "1 2 3     8\n"
alpar@423
    50
  "1 3 4     8\n"
alpar@423
    51
  "2 5 5     5\n"
alpar@423
    52
  "3 2 6     5\n"
alpar@423
    53
  "3 5 7     5\n"
alpar@423
    54
  "3 6 8     5\n"
alpar@423
    55
  "4 3 9     3\n"
alpar@423
    56
  "5 7 10    3\n"
alpar@423
    57
  "5 6 11    10\n"
alpar@423
    58
  "5 8 12    10\n"
alpar@423
    59
  "6 8 13    8\n"
alpar@423
    60
  "8 9 14    20\n"
alpar@423
    61
  "8 1 15    5\n"
alpar@423
    62
  "9 5 16    5\n"
alpar@423
    63
  "@attributes\n"
alpar@423
    64
  "source 1\n"
alpar@423
    65
  "target 8\n";
alpar@423
    66
kpeter@394
    67
void checkPreflowCompile()
alpar@389
    68
{
alpar@389
    69
  typedef int VType;
alpar@389
    70
  typedef concepts::Digraph Digraph;
alpar@389
    71
alpar@389
    72
  typedef Digraph::Node Node;
alpar@389
    73
  typedef Digraph::Arc Arc;
alpar@389
    74
  typedef concepts::ReadMap<Arc,VType> CapMap;
alpar@389
    75
  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
alpar@389
    76
  typedef concepts::WriteMap<Node,bool> CutMap;
alpar@389
    77
kpeter@394
    78
  typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@394
    79
  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@394
    80
alpar@389
    81
  Digraph g;
alpar@389
    82
  Node n;
alpar@389
    83
  Arc e;
alpar@389
    84
  CapMap cap;
alpar@389
    85
  FlowMap flow;
alpar@389
    86
  CutMap cut;
alpar@389
    87
kpeter@394
    88
  Preflow<Digraph, CapMap>
kpeter@394
    89
    ::SetFlowMap<FlowMap>
kpeter@394
    90
    ::SetElevator<Elev>
kpeter@394
    91
    ::SetStandardElevator<LinkedElev>
kpeter@394
    92
    ::Create preflow_test(g,cap,n,n);
alpar@389
    93
alpar@389
    94
  preflow_test.capacityMap(cap);
alpar@389
    95
  flow = preflow_test.flowMap();
alpar@389
    96
  preflow_test.flowMap(flow);
alpar@389
    97
  preflow_test.source(n);
alpar@389
    98
  preflow_test.target(n);
alpar@389
    99
alpar@389
   100
  preflow_test.init();
kpeter@392
   101
  preflow_test.init(cap);
alpar@389
   102
  preflow_test.startFirstPhase();
alpar@389
   103
  preflow_test.startSecondPhase();
alpar@389
   104
  preflow_test.run();
alpar@389
   105
  preflow_test.runMinCut();
alpar@389
   106
alpar@389
   107
  preflow_test.flowValue();
alpar@389
   108
  preflow_test.minCut(n);
alpar@389
   109
  preflow_test.minCutMap(cut);
alpar@389
   110
  preflow_test.flow(e);
alpar@389
   111
alpar@389
   112
}
alpar@389
   113
alpar@389
   114
int cutValue (const SmartDigraph& g,
alpar@389
   115
              const SmartDigraph::NodeMap<bool>& cut,
alpar@389
   116
              const SmartDigraph::ArcMap<int>& cap) {
alpar@389
   117
alpar@389
   118
  int c=0;
alpar@389
   119
  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
alpar@389
   120
    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
alpar@389
   121
  }
alpar@389
   122
  return c;
alpar@389
   123
}
alpar@389
   124
alpar@389
   125
bool checkFlow(const SmartDigraph& g,
alpar@389
   126
               const SmartDigraph::ArcMap<int>& flow,
alpar@389
   127
               const SmartDigraph::ArcMap<int>& cap,
alpar@389
   128
               SmartDigraph::Node s, SmartDigraph::Node t) {
alpar@389
   129
alpar@389
   130
  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
alpar@389
   131
    if (flow[e] < 0 || flow[e] > cap[e]) return false;
alpar@389
   132
  }
alpar@389
   133
alpar@389
   134
  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
alpar@389
   135
    if (n == s || n == t) continue;
alpar@389
   136
    int sum = 0;
alpar@389
   137
    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
alpar@389
   138
      sum += flow[e];
alpar@389
   139
    }
alpar@389
   140
    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
alpar@389
   141
      sum -= flow[e];
alpar@389
   142
    }
alpar@389
   143
    if (sum != 0) return false;
alpar@389
   144
  }
alpar@389
   145
  return true;
alpar@389
   146
}
alpar@389
   147
alpar@389
   148
int main() {
alpar@389
   149
alpar@389
   150
  typedef SmartDigraph Digraph;
alpar@389
   151
alpar@389
   152
  typedef Digraph::Node Node;
alpar@389
   153
  typedef Digraph::NodeIt NodeIt;
alpar@389
   154
  typedef Digraph::ArcIt ArcIt;
alpar@389
   155
  typedef Digraph::ArcMap<int> CapMap;
alpar@389
   156
  typedef Digraph::ArcMap<int> FlowMap;
alpar@389
   157
  typedef Digraph::NodeMap<bool> CutMap;
alpar@389
   158
alpar@389
   159
  typedef Preflow<Digraph, CapMap> PType;
alpar@389
   160
alpar@389
   161
  Digraph g;
alpar@389
   162
  Node s, t;
alpar@389
   163
  CapMap cap(g);
alpar@423
   164
  std::istringstream input(test_lgf);
alpar@423
   165
  DigraphReader<Digraph>(g,input).
alpar@389
   166
    arcMap("capacity", cap).
alpar@389
   167
    node("source",s).
alpar@389
   168
    node("target",t).
alpar@389
   169
    run();
alpar@389
   170
alpar@389
   171
  PType preflow_test(g, cap, s, t);
alpar@389
   172
  preflow_test.run();
alpar@389
   173
alpar@389
   174
  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
alpar@389
   175
        "The flow is not feasible.");
alpar@389
   176
alpar@389
   177
  CutMap min_cut(g);
alpar@389
   178
  preflow_test.minCutMap(min_cut);
alpar@389
   179
  int min_cut_value=cutValue(g,min_cut,cap);
alpar@389
   180
alpar@389
   181
  check(preflow_test.flowValue() == min_cut_value,
alpar@389
   182
        "The max flow value is not equal to the three min cut values.");
alpar@389
   183
alpar@389
   184
  FlowMap flow(g);
alpar@389
   185
  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
alpar@389
   186
alpar@389
   187
  int flow_value=preflow_test.flowValue();
alpar@389
   188
alpar@389
   189
  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
kpeter@392
   190
  preflow_test.init(flow);
alpar@389
   191
  preflow_test.startFirstPhase();
alpar@389
   192
alpar@389
   193
  CutMap min_cut1(g);
alpar@389
   194
  preflow_test.minCutMap(min_cut1);
alpar@389
   195
  min_cut_value=cutValue(g,min_cut1,cap);
alpar@389
   196
alpar@389
   197
  check(preflow_test.flowValue() == min_cut_value &&
alpar@389
   198
        min_cut_value == 2*flow_value,
alpar@389
   199
        "The max flow value or the min cut value is wrong.");
alpar@389
   200
alpar@389
   201
  preflow_test.startSecondPhase();
alpar@389
   202
alpar@389
   203
  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
alpar@389
   204
        "The flow is not feasible.");
alpar@389
   205
alpar@389
   206
  CutMap min_cut2(g);
alpar@389
   207
  preflow_test.minCutMap(min_cut2);
alpar@389
   208
  min_cut_value=cutValue(g,min_cut2,cap);
alpar@389
   209
alpar@389
   210
  check(preflow_test.flowValue() == min_cut_value &&
alpar@389
   211
        min_cut_value == 2*flow_value,
alpar@389
   212
        "The max flow value or the three min cut values were not doubled");
alpar@389
   213
alpar@389
   214
alpar@389
   215
  preflow_test.flowMap(flow);
alpar@389
   216
alpar@389
   217
  NodeIt tmp1(g,s);
alpar@389
   218
  ++tmp1;
alpar@389
   219
  if ( tmp1 != INVALID ) s=tmp1;
alpar@389
   220
alpar@389
   221
  NodeIt tmp2(g,t);
alpar@389
   222
  ++tmp2;
alpar@389
   223
  if ( tmp2 != INVALID ) t=tmp2;
alpar@389
   224
alpar@389
   225
  preflow_test.source(s);
alpar@389
   226
  preflow_test.target(t);
alpar@389
   227
alpar@389
   228
  preflow_test.run();
alpar@389
   229
alpar@389
   230
  CutMap min_cut3(g);
alpar@389
   231
  preflow_test.minCutMap(min_cut3);
alpar@389
   232
  min_cut_value=cutValue(g,min_cut3,cap);
alpar@389
   233
alpar@389
   234
alpar@389
   235
  check(preflow_test.flowValue() == min_cut_value,
alpar@389
   236
        "The max flow value or the three min cut values are incorrect.");
alpar@389
   237
alpar@389
   238
  return 0;
alpar@389
   239
}