test/preflow_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 423 ff48c2738fb2
child 585 65fbcf2f978a
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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-2009
     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 <iostream>
    20 
    21 #include "test_tools.h"
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/preflow.h>
    24 #include <lemon/concepts/digraph.h>
    25 #include <lemon/concepts/maps.h>
    26 #include <lemon/lgf_reader.h>
    27 #include <lemon/elevator.h>
    28 
    29 using namespace lemon;
    30 
    31 char test_lgf[] =
    32   "@nodes\n"
    33   "label\n"
    34   "0\n"
    35   "1\n"
    36   "2\n"
    37   "3\n"
    38   "4\n"
    39   "5\n"
    40   "6\n"
    41   "7\n"
    42   "8\n"
    43   "9\n"
    44   "@arcs\n"
    45   "    label capacity\n"
    46   "0 1 0     20\n"
    47   "0 2 1     0\n"
    48   "1 1 2     3\n"
    49   "1 2 3     8\n"
    50   "1 3 4     8\n"
    51   "2 5 5     5\n"
    52   "3 2 6     5\n"
    53   "3 5 7     5\n"
    54   "3 6 8     5\n"
    55   "4 3 9     3\n"
    56   "5 7 10    3\n"
    57   "5 6 11    10\n"
    58   "5 8 12    10\n"
    59   "6 8 13    8\n"
    60   "8 9 14    20\n"
    61   "8 1 15    5\n"
    62   "9 5 16    5\n"
    63   "@attributes\n"
    64   "source 1\n"
    65   "target 8\n";
    66 
    67 void checkPreflowCompile()
    68 {
    69   typedef int VType;
    70   typedef concepts::Digraph Digraph;
    71 
    72   typedef Digraph::Node Node;
    73   typedef Digraph::Arc Arc;
    74   typedef concepts::ReadMap<Arc,VType> CapMap;
    75   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    76   typedef concepts::WriteMap<Node,bool> CutMap;
    77 
    78   typedef Elevator<Digraph, Digraph::Node> Elev;
    79   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    80 
    81   Digraph g;
    82   Node n;
    83   Arc e;
    84   CapMap cap;
    85   FlowMap flow;
    86   CutMap cut;
    87 
    88   Preflow<Digraph, CapMap>
    89     ::SetFlowMap<FlowMap>
    90     ::SetElevator<Elev>
    91     ::SetStandardElevator<LinkedElev>
    92     ::Create preflow_test(g,cap,n,n);
    93 
    94   preflow_test.capacityMap(cap);
    95   flow = preflow_test.flowMap();
    96   preflow_test.flowMap(flow);
    97   preflow_test.source(n);
    98   preflow_test.target(n);
    99 
   100   preflow_test.init();
   101   preflow_test.init(cap);
   102   preflow_test.startFirstPhase();
   103   preflow_test.startSecondPhase();
   104   preflow_test.run();
   105   preflow_test.runMinCut();
   106 
   107   preflow_test.flowValue();
   108   preflow_test.minCut(n);
   109   preflow_test.minCutMap(cut);
   110   preflow_test.flow(e);
   111 
   112 }
   113 
   114 int cutValue (const SmartDigraph& g,
   115               const SmartDigraph::NodeMap<bool>& cut,
   116               const SmartDigraph::ArcMap<int>& cap) {
   117 
   118   int c=0;
   119   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
   120     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
   121   }
   122   return c;
   123 }
   124 
   125 bool checkFlow(const SmartDigraph& g,
   126                const SmartDigraph::ArcMap<int>& flow,
   127                const SmartDigraph::ArcMap<int>& cap,
   128                SmartDigraph::Node s, SmartDigraph::Node t) {
   129 
   130   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
   131     if (flow[e] < 0 || flow[e] > cap[e]) return false;
   132   }
   133 
   134   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
   135     if (n == s || n == t) continue;
   136     int sum = 0;
   137     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
   138       sum += flow[e];
   139     }
   140     for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
   141       sum -= flow[e];
   142     }
   143     if (sum != 0) return false;
   144   }
   145   return true;
   146 }
   147 
   148 int main() {
   149 
   150   typedef SmartDigraph Digraph;
   151 
   152   typedef Digraph::Node Node;
   153   typedef Digraph::NodeIt NodeIt;
   154   typedef Digraph::ArcIt ArcIt;
   155   typedef Digraph::ArcMap<int> CapMap;
   156   typedef Digraph::ArcMap<int> FlowMap;
   157   typedef Digraph::NodeMap<bool> CutMap;
   158 
   159   typedef Preflow<Digraph, CapMap> PType;
   160 
   161   Digraph g;
   162   Node s, t;
   163   CapMap cap(g);
   164   std::istringstream input(test_lgf);
   165   DigraphReader<Digraph>(g,input).
   166     arcMap("capacity", cap).
   167     node("source",s).
   168     node("target",t).
   169     run();
   170 
   171   PType preflow_test(g, cap, s, t);
   172   preflow_test.run();
   173 
   174   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   175         "The flow is not feasible.");
   176 
   177   CutMap min_cut(g);
   178   preflow_test.minCutMap(min_cut);
   179   int min_cut_value=cutValue(g,min_cut,cap);
   180 
   181   check(preflow_test.flowValue() == min_cut_value,
   182         "The max flow value is not equal to the three min cut values.");
   183 
   184   FlowMap flow(g);
   185   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
   186 
   187   int flow_value=preflow_test.flowValue();
   188 
   189   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
   190   preflow_test.init(flow);
   191   preflow_test.startFirstPhase();
   192 
   193   CutMap min_cut1(g);
   194   preflow_test.minCutMap(min_cut1);
   195   min_cut_value=cutValue(g,min_cut1,cap);
   196 
   197   check(preflow_test.flowValue() == min_cut_value &&
   198         min_cut_value == 2*flow_value,
   199         "The max flow value or the min cut value is wrong.");
   200 
   201   preflow_test.startSecondPhase();
   202 
   203   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
   204         "The flow is not feasible.");
   205 
   206   CutMap min_cut2(g);
   207   preflow_test.minCutMap(min_cut2);
   208   min_cut_value=cutValue(g,min_cut2,cap);
   209 
   210   check(preflow_test.flowValue() == min_cut_value &&
   211         min_cut_value == 2*flow_value,
   212         "The max flow value or the three min cut values were not doubled");
   213 
   214 
   215   preflow_test.flowMap(flow);
   216 
   217   NodeIt tmp1(g,s);
   218   ++tmp1;
   219   if ( tmp1 != INVALID ) s=tmp1;
   220 
   221   NodeIt tmp2(g,t);
   222   ++tmp2;
   223   if ( tmp2 != INVALID ) t=tmp2;
   224 
   225   preflow_test.source(s);
   226   preflow_test.target(t);
   227 
   228   preflow_test.run();
   229 
   230   CutMap min_cut3(g);
   231   preflow_test.minCutMap(min_cut3);
   232   min_cut_value=cutValue(g,min_cut3,cap);
   233 
   234 
   235   check(preflow_test.flowValue() == min_cut_value,
   236         "The max flow value or the three min cut values are incorrect.");
   237 
   238   return 0;
   239 }