COIN-OR::LEMON - Graph Library

Changeset 2514:57143c09dc20 in lemon-0.x for test


Ignore:
Timestamp:
11/17/07 21:58:11 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
Message:

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/preflow_test.cc

    r2391 r2514  
    2929using namespace lemon;
    3030
    31 void check_Preflow()
     31void checkPreflow()
    3232{
    3333  typedef int VType;
     
    3838  typedef concepts::ReadMap<Edge,VType> CapMap;
    3939  typedef concepts::ReadWriteMap<Edge,VType> FlowMap;
    40   typedef concepts::ReadWriteMap<Node,bool> CutMap;
     40  typedef concepts::WriteMap<Node,bool> CutMap;
    4141 
    42   typedef Preflow<Graph, int, CapMap, FlowMap> PType;
    43 
    4442  Graph g;
    4543  Node n;
     44  Edge e;
    4645  CapMap cap;
    4746  FlowMap flow;
    4847  CutMap cut;
    4948
    50   PType preflow_test(g,n,n,cap,flow);
    51 
     49  Preflow<Graph, CapMap>::DefFlowMap<FlowMap>::Create preflow_test(g,cap,n,n);
     50
     51  preflow_test.capacityMap(cap);
     52  flow = preflow_test.flowMap();
     53  preflow_test.flowMap(flow);
     54  preflow_test.source(n);
     55  preflow_test.target(n);
     56 
     57  preflow_test.init();
     58  preflow_test.flowInit(cap);
     59  preflow_test.startFirstPhase();
     60  preflow_test.startSecondPhase();
    5261  preflow_test.run();
     62  preflow_test.runMinCut();
     63
    5364  preflow_test.flowValue();
    54   preflow_test.source(n);
    55   preflow_test.flowMap(flow);
    56 
    57   preflow_test.phase1(PType::NO_FLOW);
    58   preflow_test.minCut(cut);
    59 
    60   preflow_test.phase2();
    61   preflow_test.target(n);
    62   preflow_test.capacityMap(cap);
    63   preflow_test.minMinCut(cut);
    64   preflow_test.maxMinCut(cut);
    65 }
    66 
    67 int cut_value ( SmartGraph& g, SmartGraph::NodeMap<bool>& cut,
    68                 SmartGraph::EdgeMap<int>& cap) {
     65  preflow_test.minCut(n);
     66  preflow_test.minCutMap(cut);
     67  preflow_test.flow(e);
     68
     69}
     70
     71int cutValue (const SmartGraph& g,
     72              const SmartGraph::NodeMap<bool>& cut,
     73              const SmartGraph::EdgeMap<int>& cap) {
    6974 
    7075  int c=0;
     
    7378  }
    7479  return c;
     80}
     81
     82bool checkFlow(const SmartGraph& g,
     83               const SmartGraph::EdgeMap<int>& flow,
     84               const SmartGraph::EdgeMap<int>& cap,
     85               SmartGraph::Node s, SmartGraph::Node t) {
     86
     87  for (SmartGraph::EdgeIt e(g); e != INVALID; ++e) {
     88    if (flow[e] < 0 || flow[e] > cap[e]) return false;
     89  }
     90
     91  for (SmartGraph::NodeIt n(g); n != INVALID; ++n) {
     92    if (n == s || n == t) continue;
     93    int sum = 0;
     94    for (SmartGraph::OutEdgeIt e(g, n); e != INVALID; ++e) {
     95      sum += flow[e];
     96    }
     97    for (SmartGraph::InEdgeIt e(g, n); e != INVALID; ++e) {
     98      sum -= flow[e];
     99    }
     100    if (sum != 0) return false;
     101  }
     102  return true;
    75103}
    76104
     
    86114  typedef Graph::NodeMap<bool> CutMap;
    87115
    88   typedef Preflow<Graph, int> PType;
     116  typedef Preflow<Graph, CapMap> PType;
    89117
    90118  std::string f_name;
     
    103131  readDimacs(file, g, cap, s, t);
    104132
    105   FlowMap flow(g,0);
    106 
    107  
    108 
    109   PType preflow_test(g, s, t, cap, flow);
    110   preflow_test.run(PType::ZERO_FLOW);
     133  PType preflow_test(g, cap, s, t);
     134  preflow_test.run();
    111135   
    112   CutMap min_cut(g,false);
    113   preflow_test.minCut(min_cut);
    114   int min_cut_value=cut_value(g,min_cut,cap);
    115    
    116   CutMap min_min_cut(g,false);
    117   preflow_test.minMinCut(min_min_cut);
    118   int min_min_cut_value=cut_value(g,min_min_cut,cap);
    119    
    120   CutMap max_min_cut(g,false);
    121   preflow_test.maxMinCut(max_min_cut);
    122   int max_min_cut_value=cut_value(g,max_min_cut,cap);
    123 
    124   check(preflow_test.flowValue() == min_cut_value &&
    125         min_cut_value == min_min_cut_value &&
    126         min_min_cut_value == max_min_cut_value,
     136  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
     137        "The flow is not feasible.");
     138
     139  CutMap min_cut(g);
     140  preflow_test.minCutMap(min_cut);
     141  int min_cut_value=cutValue(g,min_cut,cap);
     142 
     143  check(preflow_test.flowValue() == min_cut_value,
    127144        "The max flow value is not equal to the three min cut values.");
    128145
     146  FlowMap flow(g);
     147  flow = preflow_test.flowMap();
     148
    129149  int flow_value=preflow_test.flowValue();
    130150
    131 
    132 
    133151  for(EdgeIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
    134   preflow_test.capacityMap(cap); 
    135 
    136   preflow_test.phase1(PType::PRE_FLOW);
    137 
    138   CutMap min_cut1(g,false);
    139   preflow_test.minCut(min_cut1);
    140   min_cut_value=cut_value(g,min_cut1,cap);
     152  preflow_test.flowInit(flow);
     153  preflow_test.startFirstPhase();
     154
     155  CutMap min_cut1(g);
     156  preflow_test.minCutMap(min_cut1);
     157  min_cut_value=cutValue(g,min_cut1,cap);
    141158   
    142159  check(preflow_test.flowValue() == min_cut_value &&
     
    144161        "The max flow value or the min cut value is wrong.");
    145162
    146   preflow_test.phase2();
    147 
    148   CutMap min_cut2(g,false);
    149   preflow_test.minCut(min_cut2);
    150   min_cut_value=cut_value(g,min_cut2,cap);
     163  preflow_test.startSecondPhase();
     164
     165  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
     166        "The flow is not feasible.");
     167
     168  CutMap min_cut2(g);
     169  preflow_test.minCutMap(min_cut2);
     170  min_cut_value=cutValue(g,min_cut2,cap);
    151171   
    152   CutMap min_min_cut2(g,false);
    153   preflow_test.minMinCut(min_min_cut2);
    154   min_min_cut_value=cut_value(g,min_min_cut2,cap);
    155  
    156   preflow_test.maxMinCut(max_min_cut);
    157   max_min_cut_value=cut_value(g,max_min_cut,cap);
    158 
    159172  check(preflow_test.flowValue() == min_cut_value &&
    160         min_cut_value == min_min_cut_value &&
    161         min_min_cut_value == max_min_cut_value &&
    162173        min_cut_value == 2*flow_value,
    163174        "The max flow value or the three min cut values were not doubled");
    164175
    165 
    166 
    167   EdgeIt e(g);
    168   for( int i=1; i==10; ++i ) {
    169     flow.set(e,0);
    170     ++e;
    171   }
    172176
    173177  preflow_test.flowMap(flow);
     
    186190  preflow_test.run();
    187191
    188   CutMap min_cut3(g,false);
    189   preflow_test.minCut(min_cut3);
    190   min_cut_value=cut_value(g,min_cut3,cap);
     192  CutMap min_cut3(g);
     193  preflow_test.minCutMap(min_cut3);
     194  min_cut_value=cutValue(g,min_cut3,cap);
    191195   
    192   CutMap min_min_cut3(g,false);
    193   preflow_test.minMinCut(min_min_cut3);
    194   min_min_cut_value=cut_value(g,min_min_cut3,cap);
    195    
    196   preflow_test.maxMinCut(max_min_cut);
    197   max_min_cut_value=cut_value(g,max_min_cut,cap);
    198 
    199   check(preflow_test.flowValue() == min_cut_value &&
    200         min_cut_value == min_min_cut_value &&
    201         min_min_cut_value == max_min_cut_value,
     196
     197  check(preflow_test.flowValue() == min_cut_value,
    202198        "The max flow value or the three min cut values are incorrect.");
    203 }
     199 
     200  return 0;
     201}
Note: See TracChangeset for help on using the changeset viewer.