Changes in test/hao_orlin_test.cc [463:88ed40ad0d4f:644:2ca0cdb5f366] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/hao_orlin_test.cc
r463 r644 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(); 109 { 110 HaoOrlin<SmartDigraph> ho(graph, cap1); 111 ho.run(); 112 ho.minCutMap(cut); 113 114 check(ho.minCutValue() == 1, "Wrong cut value"); 115 check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); 116 } 117 { 118 HaoOrlin<SmartDigraph> ho(graph, cap2); 119 ho.run(); 120 ho.minCutMap(cut); 59 121 60 check(ho.minCutValue() == 3, "Wrong cut value"); 122 check(ho.minCutValue() == 1, "Wrong cut value"); 123 check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); 124 } 125 { 126 HaoOrlin<SmartDigraph> ho(graph, cap3); 127 ho.run(); 128 ho.minCutMap(cut); 129 130 check(ho.minCutValue() == 1, "Wrong cut value"); 131 check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); 132 } 133 134 typedef Undirector<SmartDigraph> UGraph; 135 UGraph ugraph(graph); 136 137 { 138 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); 139 ho.run(); 140 ho.minCutMap(cut); 141 142 check(ho.minCutValue() == 2, "Wrong cut value"); 143 check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); 144 } 145 { 146 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); 147 ho.run(); 148 ho.minCutMap(cut); 149 150 check(ho.minCutValue() == 5, "Wrong cut value"); 151 check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); 152 } 153 { 154 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); 155 ho.run(); 156 ho.minCutMap(cut); 157 158 check(ho.minCutValue() == 5, "Wrong cut value"); 159 check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); 160 } 61 161 62 162 return 0;
Note: See TracChangeset
for help on using the changeset viewer.