|
1 #include <iostream> |
|
2 |
|
3 #include "test_tools.h" |
|
4 #include <lemon/smart_graph.h> |
|
5 #include <lemon/adaptors.h> |
|
6 #include <lemon/lgf_reader.h> |
|
7 #include <lemon/lgf_writer.h> |
|
8 #include <lemon/dimacs.h> |
|
9 #include <lemon/time_measure.h> |
|
10 #include <lemon/gomory_hu_tree.h> |
|
11 #include <cstdlib> |
|
12 |
|
13 using namespace std; |
|
14 using namespace lemon; |
|
15 |
|
16 typedef SmartGraph Graph; |
|
17 |
|
18 char test_lgf[] = |
|
19 "@nodes\n" |
|
20 "label\n" |
|
21 "0\n" |
|
22 "1\n" |
|
23 "2\n" |
|
24 "3\n" |
|
25 "4\n" |
|
26 "@arcs\n" |
|
27 " label capacity\n" |
|
28 "0 1 0 1\n" |
|
29 "1 2 1 1\n" |
|
30 "2 3 2 1\n" |
|
31 "0 3 4 5\n" |
|
32 "0 3 5 10\n" |
|
33 "0 3 6 7\n" |
|
34 "4 2 7 1\n" |
|
35 "@attributes\n" |
|
36 "source 0\n" |
|
37 "target 3\n"; |
|
38 |
|
39 GRAPH_TYPEDEFS(Graph); |
|
40 typedef Graph::EdgeMap<int> IntEdgeMap; |
|
41 typedef Graph::NodeMap<bool> BoolNodeMap; |
|
42 |
|
43 int cutValue(const Graph& graph, const BoolNodeMap& cut, |
|
44 const IntEdgeMap& capacity) { |
|
45 |
|
46 int sum = 0; |
|
47 for (EdgeIt e(graph); e != INVALID; ++e) { |
|
48 Node s = graph.u(e); |
|
49 Node t = graph.v(e); |
|
50 |
|
51 if (cut[s] != cut[t]) { |
|
52 sum += capacity[e]; |
|
53 } |
|
54 } |
|
55 return sum; |
|
56 } |
|
57 |
|
58 |
|
59 int main() { |
|
60 Graph graph; |
|
61 IntEdgeMap capacity(graph); |
|
62 |
|
63 std::istringstream input(test_lgf); |
|
64 GraphReader<Graph>(graph, input). |
|
65 edgeMap("capacity", capacity).run(); |
|
66 |
|
67 GomoryHuTree<Graph> ght(graph, capacity); |
|
68 ght.init(); |
|
69 ght.run(); |
|
70 |
|
71 for (NodeIt u(graph); u != INVALID; ++u) { |
|
72 for (NodeIt v(graph); v != u; ++v) { |
|
73 Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v); |
|
74 pf.runMinCut(); |
|
75 BoolNodeMap cm(graph); |
|
76 ght.minCutMap(u, v, cm); |
|
77 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); |
|
78 check(cm[u] != cm[v], "Wrong cut 3"); |
|
79 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); |
|
80 |
|
81 } |
|
82 } |
|
83 |
|
84 return 0; |
|
85 } |