COIN-OR::LEMON - Graph Library

Changeset 418:940587667b47 in lemon


Ignore:
Timestamp:
12/01/08 14:23:59 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve test file for Circulation (#175)

  • Bug fix: add a missing #include.
  • Add compile test for various functions and named parameters.
  • Use a smaller digraph with lower bounds.
  • Test eight instances instead of two.
  • Remove the doc that was for the demo file.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/circulation_test.cc

    r415 r418  
    1717 */
    1818
    19 ///\ingroup demos
    20 ///\file
    21 ///\brief Demonstrating the usage of LEMON's General Flow algorithm
    22 ///
    23 /// This demo program reads a general network circulation problem from the
    24 /// file 'circulation-input.lgf', runs the preflow based algorithm for
    25 /// finding a feasible solution and writes the output
    26 /// to 'circulation-input.lgf'
    27 ///
    28 /// \include circulation_demo.cc
    29 
    3019#include <iostream>
    3120
     
    3423#include <lemon/circulation.h>
    3524#include <lemon/lgf_reader.h>
     25#include <lemon/concepts/digraph.h>
     26#include <lemon/concepts/maps.h>
    3627
    3728using namespace lemon;
     
    3930char test_lgf[] =
    4031  "@nodes\n"
    41   "label delta\n"
    42   "0     0\n"
    43   "1     13\n"
    44   "2     0\n"
    45   "3     0\n"
    46   "4     0\n"
    47   "5     0\n"
    48   "6     0\n"
    49   "7     0\n"
    50   "8     -13\n"
    51   "9     0\n"
    52   "@edges\n"
    53   "    label lo_cap up_cap\n"
    54   "0 1 0     0      20\n"
    55   "0 2 1     0      0\n"
    56   "1 1 2     0      3\n"
    57   "1 2 3     0      8\n"
    58   "1 3 4     0      8\n"
    59   "2 5 5     0      5\n"
    60   "3 2 6     0      5\n"
    61   "3 5 7     0      5\n"
    62   "3 6 8     0      5\n"
    63   "4 3 9     0      3\n"
    64   "5 7 10    0      3\n"
    65   "5 6 11    0      10\n"
    66   "5 8 12    0      10\n"
    67   "6 8 13    0      8\n"
    68   "8 9 14    0      20\n"
    69   "8 1 15    0      5\n"
    70   "9 5 16    0      5\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"
    7148  "@attributes\n"
    72   "source 1\n"
    73   "sink   8\n";
     49  "source 0\n"
     50  "sink   5\n";
     51
     52void 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
     97template <class G, class LM, class UM, class DM>
     98void 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}
    74112
    75113int main (int, char*[])
    76114{
     115  typedef ListDigraph Digraph;
     116  DIGRAPH_TYPEDEFS(Digraph);
    77117
    78     typedef ListDigraph Digraph;
    79     typedef Digraph::Node Node;
    80     typedef Digraph::NodeIt NodeIt;
    81     typedef Digraph::Arc Arc;
    82     typedef Digraph::ArcIt ArcIt;
    83     typedef Digraph::ArcMap<int> ArcMap;
    84     typedef Digraph::NodeMap<int> NodeMap;
    85     typedef Digraph::NodeMap<double> DNodeMap;
     118  Digraph g;
     119  IntArcMap lo(g), up(g);
     120  IntNodeMap delta(g, 0);
     121  Node s, t;
    86122
    87     Digraph g;
    88     ArcMap lo(g);
    89     ArcMap up(g);
    90     NodeMap delta(g);
    91     NodeMap nid(g);
    92     ArcMap eid(g);
    93     Node source, sink;
    94    
    95     std::istringstream input(test_lgf);
    96     DigraphReader<Digraph>(g,input).
    97       arcMap("lo_cap", lo).
    98       arcMap("up_cap", up).
    99       nodeMap("delta", delta).
    100       arcMap("label", eid).
    101       nodeMap("label", nid).
    102       node("source",source).
    103       node("sink",sink).
    104       run();
     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();
    105130
    106     Circulation<Digraph> gen(g,lo,up,delta);
    107     bool ret=gen.run();
    108     check(ret,"A feasible solution should have been found.");
    109     check(gen.checkFlow(), "The found flow is corrupt.");
    110    
    111     delta[source]=14;
    112     delta[sink]=-14;
    113    
    114     bool ret2=gen.run();
    115     check(!ret2,"A feasible solution should not have been found.");
    116     check(gen.checkBarrier(), "The found barrier is corrupt.");
     131  delta[s] = 7; delta[t] = -7;
     132  checkCirculation(g, lo, up, delta, true);
    117133
     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;
    118156}
Note: See TracChangeset for help on using the changeset viewer.