test/circulation_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 403 940587667b47
child 585 65fbcf2f978a
child 610 dacc2cee2b4c
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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@403
    60
  typedef concepts::ReadMap<Node,VType> DeltaMap;
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@403
    71
  DeltaMap delta;
kpeter@403
    72
  FlowMap flow;
kpeter@403
    73
  BarrierMap bar;
kpeter@403
    74
kpeter@403
    75
  Circulation<Digraph, CapMap, CapMap, DeltaMap>
kpeter@403
    76
    ::SetFlowMap<FlowMap>
kpeter@403
    77
    ::SetElevator<Elev>
kpeter@403
    78
    ::SetStandardElevator<LinkedElev>
kpeter@403
    79
    ::Create circ_test(g,lcap,ucap,delta);
kpeter@403
    80
kpeter@403
    81
  circ_test.lowerCapMap(lcap);
kpeter@403
    82
  circ_test.upperCapMap(ucap);
kpeter@403
    83
  circ_test.deltaMap(delta);
kpeter@403
    84
  flow = circ_test.flowMap();
kpeter@403
    85
  circ_test.flowMap(flow);
kpeter@403
    86
kpeter@403
    87
  circ_test.init();
kpeter@403
    88
  circ_test.greedyInit();
kpeter@403
    89
  circ_test.start();
kpeter@403
    90
  circ_test.run();
kpeter@403
    91
kpeter@403
    92
  circ_test.barrier(n);
kpeter@403
    93
  circ_test.barrierMap(bar);
kpeter@403
    94
  circ_test.flow(a);
kpeter@403
    95
}
kpeter@403
    96
kpeter@403
    97
template <class G, class LM, class UM, class DM>
kpeter@403
    98
void checkCirculation(const G& g, const LM& lm, const UM& um,
kpeter@403
    99
                      const DM& dm, bool find)
kpeter@403
   100
{
kpeter@403
   101
  Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
kpeter@403
   102
  bool ret = circ.run();
kpeter@403
   103
  if (find) {
kpeter@403
   104
    check(ret, "A feasible solution should have been found.");
kpeter@403
   105
    check(circ.checkFlow(), "The found flow is corrupt.");
kpeter@403
   106
    check(!circ.checkBarrier(), "A barrier should not have been found.");
kpeter@403
   107
  } else {
kpeter@403
   108
    check(!ret, "A feasible solution should not have been found.");
kpeter@403
   109
    check(circ.checkBarrier(), "The found barrier is corrupt.");
kpeter@403
   110
  }
kpeter@403
   111
}
alpar@400
   112
alpar@400
   113
int main (int, char*[])
alpar@400
   114
{
kpeter@403
   115
  typedef ListDigraph Digraph;
kpeter@403
   116
  DIGRAPH_TYPEDEFS(Digraph);
alpar@400
   117
kpeter@403
   118
  Digraph g;
kpeter@403
   119
  IntArcMap lo(g), up(g);
kpeter@403
   120
  IntNodeMap delta(g, 0);
kpeter@403
   121
  Node s, t;
alpar@400
   122
kpeter@403
   123
  std::istringstream input(test_lgf);
kpeter@403
   124
  DigraphReader<Digraph>(g,input).
kpeter@403
   125
    arcMap("lcap", lo).
kpeter@403
   126
    arcMap("ucap", up).
kpeter@403
   127
    node("source",s).
kpeter@403
   128
    node("sink",t).
kpeter@403
   129
    run();
alpar@400
   130
kpeter@403
   131
  delta[s] = 7; delta[t] = -7;
kpeter@403
   132
  checkCirculation(g, lo, up, delta, true);
alpar@400
   133
kpeter@403
   134
  delta[s] = 13; delta[t] = -13;
kpeter@403
   135
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   136
kpeter@403
   137
  delta[s] = 6; delta[t] = -6;
kpeter@403
   138
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   139
kpeter@403
   140
  delta[s] = 14; delta[t] = -14;
kpeter@403
   141
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   142
kpeter@403
   143
  delta[s] = 7; delta[t] = -13;
kpeter@403
   144
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   145
kpeter@403
   146
  delta[s] = 5; delta[t] = -15;
kpeter@403
   147
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   148
kpeter@403
   149
  delta[s] = 10; delta[t] = -11;
kpeter@403
   150
  checkCirculation(g, lo, up, delta, true);
kpeter@403
   151
kpeter@403
   152
  delta[s] = 11; delta[t] = -10;
kpeter@403
   153
  checkCirculation(g, lo, up, delta, false);
kpeter@403
   154
kpeter@403
   155
  return 0;
alpar@400
   156
}