COIN-OR::LEMON - Graph Library

Changeset 1228:45befc97b1bc in lemon for test


Ignore:
Timestamp:
02/28/13 23:44:35 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Merge test files of Preflow and EdmondsKarp? (#177)

Location:
test
Files:
1 deleted
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • test/CMakeLists.txt

    r1224 r1228  
    2626  dim_test
    2727  edge_set_test
    28   edmonds_karp_test
    2928  error_test
    3029  euler_test
     
    4342  max_cardinality_search_test
    4443  max_clique_test
     44  max_flow_test
    4545  min_cost_arborescence_test
    4646  min_cost_flow_test
     
    4949  path_test
    5050  planarity_test
    51   preflow_test
    5251  radix_sort_test
    5352  random_test
  • test/max_flow_test.cc

    r1173 r1228  
    2222#include <lemon/smart_graph.h>
    2323#include <lemon/preflow.h>
     24#include <lemon/edmonds_karp.h>
    2425#include <lemon/concepts/digraph.h>
    2526#include <lemon/concepts/maps.h>
     
    6566  "target 8\n";
    6667
     68
     69// Checks the general interface of a max flow algorithm
     70template <typename GR, typename CAP>
     71struct MaxFlowClassConcept
     72{
     73
     74  template <typename MF>
     75  struct Constraints {
     76
     77    typedef typename GR::Node Node;
     78    typedef typename GR::Arc Arc;
     79    typedef typename CAP::Value Value;
     80    typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
     81    typedef concepts::WriteMap<Node, bool> CutMap;
     82
     83    GR g;
     84    Node n;
     85    Arc e;
     86    CAP cap;
     87    FlowMap flow;
     88    CutMap cut;
     89    Value v;
     90    bool b;
     91
     92    void constraints() {
     93      checkConcept<concepts::Digraph, GR>();
     94
     95      const Constraints& me = *this;
     96
     97      typedef typename MF
     98          ::template SetFlowMap<FlowMap>
     99          ::Create MaxFlowType;
     100      typedef typename MF::Create MaxFlowType2;
     101      MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
     102      const MaxFlowType& const_max_flow = max_flow;
     103
     104      max_flow
     105          .capacityMap(cap)
     106          .flowMap(flow)
     107          .source(n)
     108          .target(n);
     109
     110      typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
     111      max_flow.tolerance(tol);
     112
     113      max_flow.init();
     114      max_flow.init(cap);
     115      max_flow.run();
     116
     117      v = const_max_flow.flowValue();
     118      v = const_max_flow.flow(e);
     119      const FlowMap& fm = const_max_flow.flowMap();
     120
     121      b = const_max_flow.minCut(n);
     122      const_max_flow.minCutMap(cut);
     123
     124      ignore_unused_variable_warning(fm);
     125    }
     126
     127  };
     128
     129};
     130
     131// Checks the specific parts of Preflow's interface
    67132void checkPreflowCompile()
    68133{
    69   typedef int VType;
     134  typedef int Value;
    70135  typedef concepts::Digraph Digraph;
    71 
    72   typedef Digraph::Node Node;
    73   typedef Digraph::Arc Arc;
    74   typedef concepts::ReadMap<Arc,VType> CapMap;
    75   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    76   typedef concepts::WriteMap<Node,bool> CutMap;
    77 
     136  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
    78137  typedef Elevator<Digraph, Digraph::Node> Elev;
    79138  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
    80139
    81140  Digraph g;
    82   Node n;
    83   Arc e;
     141  Digraph::Node n;
    84142  CapMap cap;
    85   FlowMap flow;
    86   CutMap cut;
    87   VType v;
    88   bool b;
    89   ignore_unused_variable_warning(v,b);
    90143
    91144  typedef Preflow<Digraph, CapMap>
    92             ::SetFlowMap<FlowMap>
    93             ::SetElevator<Elev>
    94             ::SetStandardElevator<LinkedElev>
    95             ::Create PreflowType;
     145      ::SetElevator<Elev>
     146      ::SetStandardElevator<LinkedElev>
     147      ::Create PreflowType;
    96148  PreflowType preflow_test(g, cap, n, n);
    97149  const PreflowType& const_preflow_test = preflow_test;
     
    99151  const PreflowType::Elevator& elev = const_preflow_test.elevator();
    100152  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
    101   PreflowType::Tolerance tol = const_preflow_test.tolerance();
    102   preflow_test.tolerance(tol);
    103 
    104   preflow_test
    105     .capacityMap(cap)
    106     .flowMap(flow)
    107     .source(n)
    108     .target(n);
    109 
    110   preflow_test.init();
    111   preflow_test.init(cap);
     153
     154  bool b = preflow_test.init(cap);
    112155  preflow_test.startFirstPhase();
    113156  preflow_test.startSecondPhase();
    114   preflow_test.run();
    115157  preflow_test.runMinCut();
    116158
    117   v = const_preflow_test.flowValue();
    118   v = const_preflow_test.flow(e);
    119   const FlowMap& fm = const_preflow_test.flowMap();
    120   b = const_preflow_test.minCut(n);
    121   const_preflow_test.minCutMap(cut);
    122 
    123   ignore_unused_variable_warning(fm);
    124 }
    125 
    126 int cutValue (const SmartDigraph& g,
     159  ignore_unused_variable_warning(b);
     160}
     161
     162// Checks the specific parts of EdmondsKarp's interface
     163void checkEdmondsKarpCompile()
     164{
     165  typedef int Value;
     166  typedef concepts::Digraph Digraph;
     167  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
     168  typedef Elevator<Digraph, Digraph::Node> Elev;
     169  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
     170
     171  Digraph g;
     172  Digraph::Node n;
     173  CapMap cap;
     174
     175  EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
     176
     177  ek_test.init(cap);
     178  bool b = ek_test.checkedInit(cap);
     179  b = ek_test.augment();
     180  ek_test.start();
     181
     182  ignore_unused_variable_warning(b);
     183}
     184
     185
     186template <typename T>
     187T cutValue (const SmartDigraph& g,
    127188              const SmartDigraph::NodeMap<bool>& cut,
    128               const SmartDigraph::ArcMap<int>& cap) {
    129 
    130   int c=0;
     189              const SmartDigraph::ArcMap<T>& cap) {
     190
     191  T c=0;
    131192  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
    132193    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
     
    135196}
    136197
     198template <typename T>
    137199bool checkFlow(const SmartDigraph& g,
    138                const SmartDigraph::ArcMap<int>& flow,
    139                const SmartDigraph::ArcMap<int>& cap,
     200               const SmartDigraph::ArcMap<T>& flow,
     201               const SmartDigraph::ArcMap<T>& cap,
    140202               SmartDigraph::Node s, SmartDigraph::Node t) {
    141203
     
    146208  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
    147209    if (n == s || n == t) continue;
    148     int sum = 0;
     210    T sum = 0;
    149211    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
    150212      sum += flow[e];
     
    181243}
    182244
    183 
    184 int main() {
    185 
     245template <typename MF, typename SF>
     246void checkMaxFlowAlg() {
    186247  typedef SmartDigraph Digraph;
    187 
    188   typedef Digraph::Node Node;
    189   typedef Digraph::NodeIt NodeIt;
    190   typedef Digraph::ArcIt ArcIt;
    191   typedef Digraph::ArcMap<int> CapMap;
    192   typedef Digraph::ArcMap<int> FlowMap;
    193   typedef Digraph::NodeMap<bool> CutMap;
    194 
    195   typedef Preflow<Digraph, CapMap> PType;
     248  DIGRAPH_TYPEDEFS(Digraph);
     249
     250  typedef typename MF::Value Value;
     251  typedef Digraph::ArcMap<Value> CapMap;
     252  typedef CapMap FlowMap;
     253  typedef BoolNodeMap CutMap;
    196254
    197255  Digraph g;
     
    199257  CapMap cap(g);
    200258  std::istringstream input(test_lgf);
    201   DigraphReader<Digraph>(g,input).
    202     arcMap("capacity", cap).
    203     node("source",s).
    204     node("target",t).
    205     run();
    206 
    207   PType preflow_test(g, cap, s, t);
    208   preflow_test.run();
    209 
    210   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
     259  DigraphReader<Digraph>(g,input)
     260      .arcMap("capacity", cap)
     261      .node("source",s)
     262      .node("target",t)
     263      .run();
     264
     265  MF max_flow(g, cap, s, t);
     266  max_flow.run();
     267
     268  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
    211269        "The flow is not feasible.");
    212270
    213271  CutMap min_cut(g);
    214   preflow_test.minCutMap(min_cut);
    215   int min_cut_value=cutValue(g,min_cut,cap);
    216 
    217   check(preflow_test.flowValue() == min_cut_value,
    218         "The max flow value is not equal to the three min cut values.");
     272  max_flow.minCutMap(min_cut);
     273  Value min_cut_value = cutValue(g, min_cut, cap);
     274
     275  check(max_flow.flowValue() == min_cut_value,
     276        "The max flow value is not equal to the min cut value.");
    219277
    220278  FlowMap flow(g);
    221   for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
    222 
    223   int flow_value=preflow_test.flowValue();
    224 
    225   for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
    226   preflow_test.init(flow);
    227   preflow_test.startFirstPhase();
     279  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
     280
     281  Value flow_value = max_flow.flowValue();
     282
     283  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
     284  max_flow.init(flow);
     285
     286  SF::startFirstPhase(max_flow);       // start first phase of the algorithm
    228287
    229288  CutMap min_cut1(g);
    230   preflow_test.minCutMap(min_cut1);
    231   min_cut_value=cutValue(g,min_cut1,cap);
    232 
    233   check(preflow_test.flowValue() == min_cut_value &&
    234         min_cut_value == 2*flow_value,
     289  max_flow.minCutMap(min_cut1);
     290  min_cut_value = cutValue(g, min_cut1, cap);
     291
     292  check(max_flow.flowValue() == min_cut_value &&
     293        min_cut_value == 2 * flow_value,
    235294        "The max flow value or the min cut value is wrong.");
    236295
    237   preflow_test.startSecondPhase();
    238 
    239   check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
     296  SF::startSecondPhase(max_flow);       // start second phase of the algorithm
     297
     298  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
    240299        "The flow is not feasible.");
    241300
    242301  CutMap min_cut2(g);
    243   preflow_test.minCutMap(min_cut2);
    244   min_cut_value=cutValue(g,min_cut2,cap);
    245 
    246   check(preflow_test.flowValue() == min_cut_value &&
    247         min_cut_value == 2*flow_value,
    248         "The max flow value or the three min cut values were not doubled");
    249 
    250 
    251   preflow_test.flowMap(flow);
    252 
    253   NodeIt tmp1(g,s);
     302  max_flow.minCutMap(min_cut2);
     303  min_cut_value = cutValue(g, min_cut2, cap);
     304
     305  check(max_flow.flowValue() == min_cut_value &&
     306        min_cut_value == 2 * flow_value,
     307        "The max flow value or the min cut value was not doubled");
     308
     309
     310  max_flow.flowMap(flow);
     311
     312  NodeIt tmp1(g, s);
    254313  ++tmp1;
    255   if ( tmp1 != INVALID ) s=tmp1;
    256 
    257   NodeIt tmp2(g,t);
     314  if (tmp1 != INVALID) s = tmp1;
     315
     316  NodeIt tmp2(g, t);
    258317  ++tmp2;
    259   if ( tmp2 != INVALID ) t=tmp2;
    260 
    261   preflow_test.source(s);
    262   preflow_test.target(t);
    263 
    264   preflow_test.run();
     318  if (tmp2 != INVALID) t = tmp2;
     319
     320  max_flow.source(s);
     321  max_flow.target(t);
     322
     323  max_flow.run();
    265324
    266325  CutMap min_cut3(g);
    267   preflow_test.minCutMap(min_cut3);
    268   min_cut_value=cutValue(g,min_cut3,cap);
    269 
    270 
    271   check(preflow_test.flowValue() == min_cut_value,
    272         "The max flow value or the three min cut values are incorrect.");
     326  max_flow.minCutMap(min_cut3);
     327  min_cut_value=cutValue(g, min_cut3, cap);
     328
     329  check(max_flow.flowValue() == min_cut_value,
     330        "The max flow value or the min cut value is wrong.");
     331}
     332
     333// Struct for calling start functions of a general max flow algorithm
     334template <typename MF>
     335struct GeneralStartFunctions {
     336
     337  static void startFirstPhase(MF& mf) {
     338    mf.start();
     339  }
     340
     341  static void startSecondPhase(MF& mf) {
     342    ignore_unused_variable_warning(mf);
     343  }
     344
     345};
     346
     347// Struct for calling start functions of Preflow
     348template <typename MF>
     349struct PreflowStartFunctions {
     350
     351  static void startFirstPhase(MF& mf) {
     352    mf.startFirstPhase();
     353  }
     354
     355  static void startSecondPhase(MF& mf) {
     356    mf.startSecondPhase();
     357  }
     358
     359};
     360
     361int main() {
     362
     363  typedef concepts::Digraph GR;
     364  typedef concepts::ReadMap<GR::Arc, int> CM1;
     365  typedef concepts::ReadMap<GR::Arc, double> CM2;
     366
     367  // Check the interface of Preflow
     368  checkConcept< MaxFlowClassConcept<GR, CM1>,
     369                Preflow<GR, CM1> >();
     370  checkConcept< MaxFlowClassConcept<GR, CM2>,
     371                Preflow<GR, CM2> >();
     372
     373  // Check the interface of EdmondsKarp
     374  checkConcept< MaxFlowClassConcept<GR, CM1>,
     375                EdmondsKarp<GR, CM1> >();
     376  checkConcept< MaxFlowClassConcept<GR, CM2>,
     377                EdmondsKarp<GR, CM2> >();
     378
     379  // Check Preflow
     380  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
     381  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
     382  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
     383  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
     384  initFlowTest();
     385 
     386  // Check EdmondsKarp
     387  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
     388  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
     389  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
     390  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
    273391
    274392  initFlowTest();
Note: See TracChangeset for help on using the changeset viewer.