test/circulation_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 403 940587667b47
child 585 65fbcf2f978a
child 610 dacc2cee2b4c
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.
     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/list_graph.h>
    23 #include <lemon/circulation.h>
    24 #include <lemon/lgf_reader.h>
    25 #include <lemon/concepts/digraph.h>
    26 #include <lemon/concepts/maps.h>
    27 
    28 using namespace lemon;
    29 
    30 char test_lgf[] =
    31   "@nodes\n"
    32   "label\n"
    33   "0\n"
    34   "1\n"
    35   "2\n"
    36   "3\n"
    37   "4\n"
    38   "5\n"
    39   "@arcs\n"
    40   "     lcap  ucap\n"
    41   "0 1  2  10\n"
    42   "0 2  2  6\n"
    43   "1 3  4  7\n"
    44   "1 4  0  5\n"
    45   "2 4  1  3\n"
    46   "3 5  3  8\n"
    47   "4 5  3  7\n"
    48   "@attributes\n"
    49   "source 0\n"
    50   "sink   5\n";
    51 
    52 void checkCirculationCompile()
    53 {
    54   typedef int VType;
    55   typedef concepts::Digraph Digraph;
    56 
    57   typedef Digraph::Node Node;
    58   typedef Digraph::Arc Arc;
    59   typedef concepts::ReadMap<Arc,VType> CapMap;
    60   typedef concepts::ReadMap<Node,VType> DeltaMap;
    61   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    62   typedef concepts::WriteMap<Node,bool> BarrierMap;
    63 
    64   typedef Elevator<Digraph, Digraph::Node> Elev;
    65   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    66 
    67   Digraph g;
    68   Node n;
    69   Arc a;
    70   CapMap lcap, ucap;
    71   DeltaMap delta;
    72   FlowMap flow;
    73   BarrierMap bar;
    74 
    75   Circulation<Digraph, CapMap, CapMap, DeltaMap>
    76     ::SetFlowMap<FlowMap>
    77     ::SetElevator<Elev>
    78     ::SetStandardElevator<LinkedElev>
    79     ::Create circ_test(g,lcap,ucap,delta);
    80 
    81   circ_test.lowerCapMap(lcap);
    82   circ_test.upperCapMap(ucap);
    83   circ_test.deltaMap(delta);
    84   flow = circ_test.flowMap();
    85   circ_test.flowMap(flow);
    86 
    87   circ_test.init();
    88   circ_test.greedyInit();
    89   circ_test.start();
    90   circ_test.run();
    91 
    92   circ_test.barrier(n);
    93   circ_test.barrierMap(bar);
    94   circ_test.flow(a);
    95 }
    96 
    97 template <class G, class LM, class UM, class DM>
    98 void checkCirculation(const G& g, const LM& lm, const UM& um,
    99                       const DM& dm, bool find)
   100 {
   101   Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
   102   bool ret = circ.run();
   103   if (find) {
   104     check(ret, "A feasible solution should have been found.");
   105     check(circ.checkFlow(), "The found flow is corrupt.");
   106     check(!circ.checkBarrier(), "A barrier should not have been found.");
   107   } else {
   108     check(!ret, "A feasible solution should not have been found.");
   109     check(circ.checkBarrier(), "The found barrier is corrupt.");
   110   }
   111 }
   112 
   113 int main (int, char*[])
   114 {
   115   typedef ListDigraph Digraph;
   116   DIGRAPH_TYPEDEFS(Digraph);
   117 
   118   Digraph g;
   119   IntArcMap lo(g), up(g);
   120   IntNodeMap delta(g, 0);
   121   Node s, t;
   122 
   123   std::istringstream input(test_lgf);
   124   DigraphReader<Digraph>(g,input).
   125     arcMap("lcap", lo).
   126     arcMap("ucap", up).
   127     node("source",s).
   128     node("sink",t).
   129     run();
   130 
   131   delta[s] = 7; delta[t] = -7;
   132   checkCirculation(g, lo, up, delta, true);
   133 
   134   delta[s] = 13; delta[t] = -13;
   135   checkCirculation(g, lo, up, delta, true);
   136 
   137   delta[s] = 6; delta[t] = -6;
   138   checkCirculation(g, lo, up, delta, false);
   139 
   140   delta[s] = 14; delta[t] = -14;
   141   checkCirculation(g, lo, up, delta, false);
   142 
   143   delta[s] = 7; delta[t] = -13;
   144   checkCirculation(g, lo, up, delta, true);
   145 
   146   delta[s] = 5; delta[t] = -15;
   147   checkCirculation(g, lo, up, delta, true);
   148 
   149   delta[s] = 10; delta[t] = -11;
   150   checkCirculation(g, lo, up, delta, true);
   151 
   152   delta[s] = 11; delta[t] = -10;
   153   checkCirculation(g, lo, up, delta, false);
   154 
   155   return 0;
   156 }