test/circulation_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 25 Aug 2010 21:34:58 +0200
changeset 742 16d466589b54
parent 577 65fbcf2f978a
parent 602 dacc2cee2b4c
child 761 f1398882a928
child 796 7e368d9b67f7
permissions -rw-r--r--
Backport the CMAKE related changesets from the main branch

[e20fecd1945f] Add check target for CMake (#388)
[e74b5db4f2c6] Put the output of chg-len.py in the version string (#389)
[7d166b8b8018] Safer call of ./scripts/chg-len.py on Windows (#389)
[659ba4805a48] Make CMAKE config more consistent with configure.ac (#390)
[63e4468c680e] Add 'Maintainer' CMAKE build type (#388, #390)
[a725503acfe9] Allow CPACK configuration on all platforms
[10242c611190] Create and install lemon.pc (#393)
[48e29534cf03] The deafult target doesn't build lp_test and mip_test (#388)
[0fbbdd578c06] Full path for DoxygenLayout.xml in Doxyfile.in (#395)
[481496e6d71f] SOURCE_BROWSER Doxygen switch is configurable from CMAKE (#395)
[09282720100b] update-external-tags CMAKE target (#395)
alpar@400
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@400
     2
 *
alpar@400
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@400
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@400
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@400
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@400
     8
 *
alpar@400
     9
 * Permission to use, modify and distribute this software is granted
alpar@400
    10
 * provided that this copyright notice appears in all copies. For
alpar@400
    11
 * precise terms see the accompanying LICENSE file.
alpar@400
    12
 *
alpar@400
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@400
    14
 * express or implied, and with no claim as to its suitability for any
alpar@400
    15
 * purpose.
alpar@400
    16
 *
alpar@400
    17
 */
alpar@400
    18
alpar@400
    19
#include <iostream>
alpar@400
    20
alpar@400
    21
#include "test_tools.h"
alpar@400
    22
#include <lemon/list_graph.h>
alpar@400
    23
#include <lemon/circulation.h>
alpar@400
    24
#include <lemon/lgf_reader.h>
kpeter@403
    25
#include <lemon/concepts/digraph.h>
kpeter@403
    26
#include <lemon/concepts/maps.h>
alpar@400
    27
alpar@400
    28
using namespace lemon;
alpar@400
    29
alpar@400
    30
char test_lgf[] =
alpar@400
    31
  "@nodes\n"
kpeter@403
    32
  "label\n"
kpeter@403
    33
  "0\n"
kpeter@403
    34
  "1\n"
kpeter@403
    35
  "2\n"
kpeter@403
    36
  "3\n"
kpeter@403
    37
  "4\n"
kpeter@403
    38
  "5\n"
kpeter@403
    39
  "@arcs\n"
kpeter@403
    40
  "     lcap  ucap\n"
kpeter@403
    41
  "0 1  2  10\n"
kpeter@403
    42
  "0 2  2  6\n"
kpeter@403
    43
  "1 3  4  7\n"
kpeter@403
    44
  "1 4  0  5\n"
kpeter@403
    45
  "2 4  1  3\n"
kpeter@403
    46
  "3 5  3  8\n"
kpeter@403
    47
  "4 5  3  7\n"
alpar@400
    48
  "@attributes\n"
kpeter@403
    49
  "source 0\n"
kpeter@403
    50
  "sink   5\n";
kpeter@403
    51
kpeter@403
    52
void checkCirculationCompile()
kpeter@403
    53
{
kpeter@403
    54
  typedef int VType;
kpeter@403
    55
  typedef concepts::Digraph Digraph;
kpeter@403
    56
kpeter@403
    57
  typedef Digraph::Node Node;
kpeter@403
    58
  typedef Digraph::Arc Arc;
kpeter@403
    59
  typedef concepts::ReadMap<Arc,VType> CapMap;
kpeter@602
    60
  typedef concepts::ReadMap<Node,VType> SupplyMap;
kpeter@403
    61
  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
kpeter@403
    62
  typedef concepts::WriteMap<Node,bool> BarrierMap;
kpeter@403
    63
kpeter@403
    64
  typedef Elevator<Digraph, Digraph::Node> Elev;
kpeter@403
    65
  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
kpeter@403
    66
kpeter@403
    67
  Digraph g;
kpeter@403
    68
  Node n;
kpeter@403
    69
  Arc a;
kpeter@403
    70
  CapMap lcap, ucap;
kpeter@602
    71
  SupplyMap supply;
kpeter@403
    72
  FlowMap flow;
kpeter@403
    73
  BarrierMap bar;
kpeter@577
    74
  VType v;
kpeter@577
    75
  bool b;
kpeter@403
    76
alpar@603
    77
  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
kpeter@577
    78
            ::SetFlowMap<FlowMap>
kpeter@577
    79
            ::SetElevator<Elev>
kpeter@577
    80
            ::SetStandardElevator<LinkedElev>
kpeter@577
    81
            ::Create CirculationType;
alpar@603
    82
  CirculationType circ_test(g, lcap, ucap, supply);
kpeter@577
    83
  const CirculationType& const_circ_test = circ_test;
kpeter@577
    84
   
kpeter@577
    85
  circ_test
alpar@603
    86
    .lowerMap(lcap)
alpar@603
    87
    .upperMap(ucap)
alpar@603
    88
    .supplyMap(supply)
kpeter@577
    89
    .flowMap(flow);
kpeter@403
    90
kpeter@403
    91
  circ_test.init();
kpeter@403
    92
  circ_test.greedyInit();
kpeter@403
    93
  circ_test.start();
kpeter@403
    94
  circ_test.run();
kpeter@403
    95
kpeter@577
    96
  v = const_circ_test.flow(a);
kpeter@577
    97
  const FlowMap& fm = const_circ_test.flowMap();
kpeter@577
    98
  b = const_circ_test.barrier(n);
kpeter@577
    99
  const_circ_test.barrierMap(bar);
kpeter@577
   100
  
kpeter@577
   101
  ignore_unused_variable_warning(fm);
kpeter@403
   102
}
kpeter@403
   103
kpeter@403
   104
template <class G, class LM, class UM, class DM>
kpeter@403
   105
void checkCirculation(const G& g, const LM& lm, const UM& um,
kpeter@403
   106
                      const DM& dm, bool find)
kpeter@403
   107
{
kpeter@403
   108
  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
kpeter@403
   109
  bool ret = circ.run();
kpeter@403
   110
  if (find) {
kpeter@403
   111
    check(ret, "A feasible solution should have been found.");
kpeter@403
   112
    check(circ.checkFlow(), "The found flow is corrupt.");
kpeter@403
   113
    check(!circ.checkBarrier(), "A barrier should not have been found.");
kpeter@403
   114
  } else {
kpeter@403
   115
    check(!ret, "A feasible solution should not have been found.");
kpeter@403
   116
    check(circ.checkBarrier(), "The found barrier is corrupt.");
kpeter@403
   117
  }
kpeter@403
   118
}
alpar@400
   119
alpar@400
   120
int main (int, char*[])
alpar@400
   121
{
kpeter@403
   122
  typedef ListDigraph Digraph;
kpeter@403
   123
  DIGRAPH_TYPEDEFS(Digraph);
alpar@400
   124
kpeter@403
   125
  Digraph g;
kpeter@403
   126
  IntArcMap lo(g), up(g);
kpeter@403
   127
  IntNodeMap delta(g, 0);
kpeter@403
   128
  Node s, t;
alpar@400
   129
kpeter@403
   130
  std::istringstream input(test_lgf);
kpeter@403
   131
  DigraphReader<Digraph>(g,input).
kpeter@403
   132
    arcMap("lcap", lo).
kpeter@403
   133
    arcMap("ucap", up).
kpeter@403
   134
    node("source",s).
kpeter@403
   135
    node("sink",t).
kpeter@403
   136
    run();
alpar@400
   137
kpeter@403
   138
  delta[s] = 7; delta[t] = -7;
kpeter@403
   139
  checkCirculation(g, lo, up, delta, true);
alpar@400
   140
kpeter@403
   141
  delta[s] = 13; delta[t] = -13;
kpeter@403
   142
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   143
kpeter@403
   144
  delta[s] = 6; delta[t] = -6;
kpeter@403
   145
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   146
kpeter@403
   147
  delta[s] = 14; delta[t] = -14;
kpeter@403
   148
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   149
kpeter@403
   150
  delta[s] = 7; delta[t] = -13;
kpeter@403
   151
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   152
kpeter@403
   153
  delta[s] = 5; delta[t] = -15;
kpeter@403
   154
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   155
kpeter@403
   156
  delta[s] = 10; delta[t] = -11;
kpeter@403
   157
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   158
kpeter@403
   159
  delta[s] = 11; delta[t] = -10;
kpeter@403
   160
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   161
kpeter@403
   162
  return 0;
alpar@400
   163
}