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/lgf_reader.h> |
5 #include <lemon/lgf_reader.h> |
6 #include <lemon/gomory_hu_tree.h> |
6 #include <lemon/gomory_hu.h> |
7 #include <cstdlib> |
7 #include <cstdlib> |
8 |
8 |
9 using namespace std; |
9 using namespace std; |
10 using namespace lemon; |
10 using namespace lemon; |
11 |
11 |
58 |
58 |
59 std::istringstream input(test_lgf); |
59 std::istringstream input(test_lgf); |
60 GraphReader<Graph>(graph, input). |
60 GraphReader<Graph>(graph, input). |
61 edgeMap("capacity", capacity).run(); |
61 edgeMap("capacity", capacity).run(); |
62 |
62 |
63 GomoryHuTree<Graph> ght(graph, capacity); |
63 GomoryHu<Graph> ght(graph, capacity); |
64 ght.init(); |
64 ght.init(); |
65 ght.run(); |
65 ght.run(); |
66 |
66 |
67 for (NodeIt u(graph); u != INVALID; ++u) { |
67 for (NodeIt u(graph); u != INVALID; ++u) { |
68 for (NodeIt v(graph); v != u; ++v) { |
68 for (NodeIt v(graph); v != u; ++v) { |
73 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); |
73 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); |
74 check(cm[u] != cm[v], "Wrong cut 3"); |
74 check(cm[u] != cm[v], "Wrong cut 3"); |
75 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); |
75 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); |
76 |
76 |
77 int sum=0; |
77 int sum=0; |
78 for(GomoryHuTree<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
78 for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) |
79 sum+=capacity[a]; |
79 sum+=capacity[a]; |
80 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
80 check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); |
81 |
81 |
82 sum=0; |
82 sum=0; |
83 for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
83 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) |
84 sum++; |
84 sum++; |
85 for(GomoryHuTree<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
85 for(GomoryHu<Graph>::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) |
86 sum++; |
86 sum++; |
87 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
87 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); |
88 |
88 |
89 } |
89 } |
90 } |
90 } |