1 #include <iostream> |
1 #include <iostream> |
2 |
2 |
3 #include "test_tools.h" |
3 #include "test_tools.h" |
4 #include <lemon/smart_graph.h> |
4 #include <lemon/smart_graph.h> |
|
5 #include <lemon/concepts/graph.h> |
|
6 #include <lemon/concepts/maps.h> |
5 #include <lemon/lgf_reader.h> |
7 #include <lemon/lgf_reader.h> |
6 #include <lemon/gomory_hu.h> |
8 #include <lemon/gomory_hu.h> |
7 #include <cstdlib> |
9 #include <cstdlib> |
8 |
10 |
9 using namespace std; |
11 using namespace std; |
30 "4 2 7 1\n" |
32 "4 2 7 1\n" |
31 "@attributes\n" |
33 "@attributes\n" |
32 "source 0\n" |
34 "source 0\n" |
33 "target 3\n"; |
35 "target 3\n"; |
34 |
36 |
|
37 void checkGomoryHuCompile() |
|
38 { |
|
39 typedef int Value; |
|
40 typedef concepts::Graph Graph; |
|
41 |
|
42 typedef Graph::Node Node; |
|
43 typedef Graph::Edge Edge; |
|
44 typedef concepts::ReadMap<Edge, Value> CapMap; |
|
45 typedef concepts::ReadWriteMap<Node, bool> CutMap; |
|
46 |
|
47 Graph g; |
|
48 Node n; |
|
49 CapMap cap; |
|
50 CutMap cut; |
|
51 Value v; |
|
52 int d; |
|
53 |
|
54 GomoryHu<Graph, CapMap> gh_test(g, cap); |
|
55 const GomoryHu<Graph, CapMap>& |
|
56 const_gh_test = gh_test; |
|
57 |
|
58 gh_test.run(); |
|
59 |
|
60 n = const_gh_test.predNode(n); |
|
61 v = const_gh_test.predValue(n); |
|
62 d = const_gh_test.rootDist(n); |
|
63 v = const_gh_test.minCutValue(n, n); |
|
64 v = const_gh_test.minCutMap(n, n, cut); |
|
65 } |
|
66 |
35 GRAPH_TYPEDEFS(Graph); |
67 GRAPH_TYPEDEFS(Graph); |
36 typedef Graph::EdgeMap<int> IntEdgeMap; |
68 typedef Graph::EdgeMap<int> IntEdgeMap; |
37 typedef Graph::NodeMap<bool> BoolNodeMap; |
69 typedef Graph::NodeMap<bool> BoolNodeMap; |
38 |
70 |
39 int cutValue(const Graph& graph, const BoolNodeMap& cut, |
71 int cutValue(const Graph& graph, const BoolNodeMap& cut, |
68 Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v); |
100 Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v); |
69 pf.runMinCut(); |
101 pf.runMinCut(); |
70 BoolNodeMap cm(graph); |
102 BoolNodeMap cm(graph); |
71 ght.minCutMap(u, v, cm); |
103 ght.minCutMap(u, v, cm); |
72 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); |
104 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); |
73 check(cm[u] != cm[v], "Wrong cut 3"); |
105 check(cm[u] != cm[v], "Wrong cut 2"); |
74 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); |
106 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); |
75 |
107 |
76 int sum=0; |
108 int sum=0; |
77 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
109 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
78 sum+=capacity[a]; |
110 sum+=capacity[a]; |
79 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
111 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
82 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
114 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
83 sum++; |
115 sum++; |
84 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
116 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
85 sum++; |
117 sum++; |
86 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
118 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
87 |
|
88 } |
119 } |
89 } |
120 } |
90 |
121 |
91 return 0; |
122 return 0; |
92 } |
123 } |