Changeset 2514:57143c09dc20 in lemon-0.x for test
- Timestamp:
- 11/17/07 21:58:11 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/preflow_test.cc
r2391 r2514 29 29 using namespace lemon; 30 30 31 void check _Preflow()31 void checkPreflow() 32 32 { 33 33 typedef int VType; … … 38 38 typedef concepts::ReadMap<Edge,VType> CapMap; 39 39 typedef concepts::ReadWriteMap<Edge,VType> FlowMap; 40 typedef concepts:: ReadWriteMap<Node,bool> CutMap;40 typedef concepts::WriteMap<Node,bool> CutMap; 41 41 42 typedef Preflow<Graph, int, CapMap, FlowMap> PType;43 44 42 Graph g; 45 43 Node n; 44 Edge e; 46 45 CapMap cap; 47 46 FlowMap flow; 48 47 CutMap cut; 49 48 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(); 52 61 preflow_test.run(); 62 preflow_test.runMinCut(); 63 53 64 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 71 int cutValue (const SmartGraph& g, 72 const SmartGraph::NodeMap<bool>& cut, 73 const SmartGraph::EdgeMap<int>& cap) { 69 74 70 75 int c=0; … … 73 78 } 74 79 return c; 80 } 81 82 bool 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; 75 103 } 76 104 … … 86 114 typedef Graph::NodeMap<bool> CutMap; 87 115 88 typedef Preflow<Graph, int> PType;116 typedef Preflow<Graph, CapMap> PType; 89 117 90 118 std::string f_name; … … 103 131 readDimacs(file, g, cap, s, t); 104 132 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(); 111 135 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, 127 144 "The max flow value is not equal to the three min cut values."); 128 145 146 FlowMap flow(g); 147 flow = preflow_test.flowMap(); 148 129 149 int flow_value=preflow_test.flowValue(); 130 150 131 132 133 151 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); 141 158 142 159 check(preflow_test.flowValue() == min_cut_value && … … 144 161 "The max flow value or the min cut value is wrong."); 145 162 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); 151 171 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 159 172 check(preflow_test.flowValue() == min_cut_value && 160 min_cut_value == min_min_cut_value &&161 min_min_cut_value == max_min_cut_value &&162 173 min_cut_value == 2*flow_value, 163 174 "The max flow value or the three min cut values were not doubled"); 164 175 165 166 167 EdgeIt e(g);168 for( int i=1; i==10; ++i ) {169 flow.set(e,0);170 ++e;171 }172 176 173 177 preflow_test.flowMap(flow); … … 186 190 preflow_test.run(); 187 191 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); 191 195 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, 202 198 "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.