Changeset 643:293551ad254f in lemon for test/hao_orlin_test.cc
 Timestamp:
 04/15/09 09:37:51 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/hao_orlin_test.cc
r463 r643 20 20 21 21 #include <lemon/smart_graph.h> 22 #include <lemon/adaptors.h> 23 #include <lemon/concepts/digraph.h> 24 #include <lemon/concepts/maps.h> 25 #include <lemon/lgf_reader.h> 22 26 #include <lemon/hao_orlin.h> 23 27 24 #include <lemon/lgf_reader.h>25 28 #include "test_tools.h" 26 29 … … 38 41 "5\n" 39 42 "@edges\n" 40 " label capacity\n" 41 "0 1 0 2\n" 42 "1 2 1 2\n" 43 "2 0 2 2\n" 44 "3 4 3 2\n" 45 "4 5 4 2\n" 46 "5 3 5 2\n" 47 "2 3 6 3\n"; 43 " cap1 cap2 cap3\n" 44 "0 1 1 1 1 \n" 45 "0 2 2 2 4 \n" 46 "1 2 4 4 4 \n" 47 "3 4 1 1 1 \n" 48 "3 5 2 2 4 \n" 49 "4 5 4 4 4 \n" 50 "5 4 4 4 4 \n" 51 "2 3 1 6 6 \n" 52 "4 0 1 6 6 \n"; 53 54 void checkHaoOrlinCompile() 55 { 56 typedef int Value; 57 typedef concepts::Digraph Digraph; 58 59 typedef Digraph::Node Node; 60 typedef Digraph::Arc Arc; 61 typedef concepts::ReadMap<Arc, Value> CapMap; 62 typedef concepts::WriteMap<Node, bool> CutMap; 63 64 Digraph g; 65 Node n; 66 CapMap cap; 67 CutMap cut; 68 Value v; 69 70 HaoOrlin<Digraph, CapMap> ho_test(g, cap); 71 const HaoOrlin<Digraph, CapMap>& 72 const_ho_test = ho_test; 73 74 ho_test.init(); 75 ho_test.init(n); 76 ho_test.calculateOut(); 77 ho_test.calculateIn(); 78 ho_test.run(); 79 ho_test.run(n); 80 81 v = const_ho_test.minCutValue(); 82 v = const_ho_test.minCutMap(cut); 83 } 84 85 template <typename Graph, typename CapMap, typename CutMap> 86 typename CapMap::Value 87 cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) 88 { 89 typename CapMap::Value sum = 0; 90 for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { 91 if (cut[graph.source(a)] && !cut[graph.target(a)]) 92 sum += cap[a]; 93 } 94 return sum; 95 } 48 96 49 97 int main() { 50 SmartGraph graph; 51 SmartGraph::EdgeMap<int> capacity(graph); 98 SmartDigraph graph; 99 SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph); 100 SmartDigraph::NodeMap<bool> cut(graph); 52 101 53 istringstream lgfs(lgf); 54 graphReader(graph, lgfs). 55 edgeMap("capacity", capacity).run(); 102 istringstream input(lgf); 103 digraphReader(graph, input) 104 .arcMap("cap1", cap1) 105 .arcMap("cap2", cap2) 106 .arcMap("cap3", cap3) 107 .run(); 56 108 57 HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity); 58 ho.run(); 59 60 check(ho.minCutValue() == 3, "Wrong cut value"); 109 { 110 HaoOrlin<SmartDigraph> ho(graph, cap1); 111 ho.run(); 112 ho.minCutMap(cut); 113 114 // BUG: The cut value should be positive 115 check(ho.minCutValue() == 0, "Wrong cut value"); 116 // BUG: It should work 117 //check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); 118 } 119 { 120 HaoOrlin<SmartDigraph> ho(graph, cap2); 121 ho.run(); 122 ho.minCutMap(cut); 123 124 // BUG: The cut value should be positive 125 check(ho.minCutValue() == 0, "Wrong cut value"); 126 // BUG: It should work 127 //check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); 128 } 129 { 130 HaoOrlin<SmartDigraph> ho(graph, cap3); 131 ho.run(); 132 ho.minCutMap(cut); 133 134 // BUG: The cut value should be positive 135 check(ho.minCutValue() == 0, "Wrong cut value"); 136 // BUG: It should work 137 //check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); 138 } 139 140 typedef Undirector<SmartDigraph> UGraph; 141 UGraph ugraph(graph); 142 143 { 144 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); 145 ho.run(); 146 ho.minCutMap(cut); 147 148 // BUG: The cut value should be 2 149 check(ho.minCutValue() == 1, "Wrong cut value"); 150 // BUG: It should work 151 //check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); 152 } 153 { 154 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); 155 ho.run(); 156 ho.minCutMap(cut); 157 158 // TODO: Check this cut value 159 check(ho.minCutValue() == 4, "Wrong cut value"); 160 // BUG: It should work 161 //check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); 162 } 163 { 164 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); 165 ho.run(); 166 ho.minCutMap(cut); 167 168 // TODO: Check this cut value 169 check(ho.minCutValue() == 5, "Wrong cut value"); 170 // BUG: It should work 171 //check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); 172 } 61 173 62 174 return 0;
Note: See TracChangeset
for help on using the changeset viewer.