1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/circulation_test.cc	Thu Dec 10 17:05:35 2009 +0100
     1.3 @@ -0,0 +1,163 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <iostream>
    1.23 +
    1.24 +#include "test_tools.h"
    1.25 +#include <lemon/list_graph.h>
    1.26 +#include <lemon/circulation.h>
    1.27 +#include <lemon/lgf_reader.h>
    1.28 +#include <lemon/concepts/digraph.h>
    1.29 +#include <lemon/concepts/maps.h>
    1.30 +
    1.31 +using namespace lemon;
    1.32 +
    1.33 +char test_lgf[] =
    1.34 +  "@nodes\n"
    1.35 +  "label\n"
    1.36 +  "0\n"
    1.37 +  "1\n"
    1.38 +  "2\n"
    1.39 +  "3\n"
    1.40 +  "4\n"
    1.41 +  "5\n"
    1.42 +  "@arcs\n"
    1.43 +  "     lcap  ucap\n"
    1.44 +  "0 1  2  10\n"
    1.45 +  "0 2  2  6\n"
    1.46 +  "1 3  4  7\n"
    1.47 +  "1 4  0  5\n"
    1.48 +  "2 4  1  3\n"
    1.49 +  "3 5  3  8\n"
    1.50 +  "4 5  3  7\n"
    1.51 +  "@attributes\n"
    1.52 +  "source 0\n"
    1.53 +  "sink   5\n";
    1.54 +
    1.55 +void checkCirculationCompile()
    1.56 +{
    1.57 +  typedef int VType;
    1.58 +  typedef concepts::Digraph Digraph;
    1.59 +
    1.60 +  typedef Digraph::Node Node;
    1.61 +  typedef Digraph::Arc Arc;
    1.62 +  typedef concepts::ReadMap<Arc,VType> CapMap;
    1.63 +  typedef concepts::ReadMap<Node,VType> SupplyMap;
    1.64 +  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    1.65 +  typedef concepts::WriteMap<Node,bool> BarrierMap;
    1.66 +
    1.67 +  typedef Elevator<Digraph, Digraph::Node> Elev;
    1.68 +  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    1.69 +
    1.70 +  Digraph g;
    1.71 +  Node n;
    1.72 +  Arc a;
    1.73 +  CapMap lcap, ucap;
    1.74 +  SupplyMap supply;
    1.75 +  FlowMap flow;
    1.76 +  BarrierMap bar;
    1.77 +  VType v;
    1.78 +  bool b;
    1.79 +
    1.80 +  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
    1.81 +            ::SetFlowMap<FlowMap>
    1.82 +            ::SetElevator<Elev>
    1.83 +            ::SetStandardElevator<LinkedElev>
    1.84 +            ::Create CirculationType;
    1.85 +  CirculationType circ_test(g, lcap, ucap, supply);
    1.86 +  const CirculationType& const_circ_test = circ_test;
    1.87 +   
    1.88 +  circ_test
    1.89 +    .lowerMap(lcap)
    1.90 +    .upperMap(ucap)
    1.91 +    .supplyMap(supply)
    1.92 +    .flowMap(flow);
    1.93 +
    1.94 +  circ_test.init();
    1.95 +  circ_test.greedyInit();
    1.96 +  circ_test.start();
    1.97 +  circ_test.run();
    1.98 +
    1.99 +  v = const_circ_test.flow(a);
   1.100 +  const FlowMap& fm = const_circ_test.flowMap();
   1.101 +  b = const_circ_test.barrier(n);
   1.102 +  const_circ_test.barrierMap(bar);
   1.103 +  
   1.104 +  ignore_unused_variable_warning(fm);
   1.105 +}
   1.106 +
   1.107 +template <class G, class LM, class UM, class DM>
   1.108 +void checkCirculation(const G& g, const LM& lm, const UM& um,
   1.109 +                      const DM& dm, bool find)
   1.110 +{
   1.111 +  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
   1.112 +  bool ret = circ.run();
   1.113 +  if (find) {
   1.114 +    check(ret, "A feasible solution should have been found.");
   1.115 +    check(circ.checkFlow(), "The found flow is corrupt.");
   1.116 +    check(!circ.checkBarrier(), "A barrier should not have been found.");
   1.117 +  } else {
   1.118 +    check(!ret, "A feasible solution should not have been found.");
   1.119 +    check(circ.checkBarrier(), "The found barrier is corrupt.");
   1.120 +  }
   1.121 +}
   1.122 +
   1.123 +int main (int, char*[])
   1.124 +{
   1.125 +  typedef ListDigraph Digraph;
   1.126 +  DIGRAPH_TYPEDEFS(Digraph);
   1.127 +
   1.128 +  Digraph g;
   1.129 +  IntArcMap lo(g), up(g);
   1.130 +  IntNodeMap delta(g, 0);
   1.131 +  Node s, t;
   1.132 +
   1.133 +  std::istringstream input(test_lgf);
   1.134 +  DigraphReader<Digraph>(g,input).
   1.135 +    arcMap("lcap", lo).
   1.136 +    arcMap("ucap", up).
   1.137 +    node("source",s).
   1.138 +    node("sink",t).
   1.139 +    run();
   1.140 +
   1.141 +  delta[s] = 7; delta[t] = -7;
   1.142 +  checkCirculation(g, lo, up, delta, true);
   1.143 +
   1.144 +  delta[s] = 13; delta[t] = -13;
   1.145 +  checkCirculation(g, lo, up, delta, true);
   1.146 +
   1.147 +  delta[s] = 6; delta[t] = -6;
   1.148 +  checkCirculation(g, lo, up, delta, false);
   1.149 +
   1.150 +  delta[s] = 14; delta[t] = -14;
   1.151 +  checkCirculation(g, lo, up, delta, false);
   1.152 +
   1.153 +  delta[s] = 7; delta[t] = -13;
   1.154 +  checkCirculation(g, lo, up, delta, true);
   1.155 +
   1.156 +  delta[s] = 5; delta[t] = -15;
   1.157 +  checkCirculation(g, lo, up, delta, true);
   1.158 +
   1.159 +  delta[s] = 10; delta[t] = -11;
   1.160 +  checkCirculation(g, lo, up, delta, true);
   1.161 +
   1.162 +  delta[s] = 11; delta[t] = -10;
   1.163 +  checkCirculation(g, lo, up, delta, false);
   1.164 +
   1.165 +  return 0;
   1.166 +}