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>
14 using namespace lemon;
16 typedef SmartGraph Graph;
39 GRAPH_TYPEDEFS(Graph);
40 typedef Graph::EdgeMap<int> IntEdgeMap;
41 typedef Graph::NodeMap<bool> BoolNodeMap;
43 int cutValue(const Graph& graph, const BoolNodeMap& cut,
44 const IntEdgeMap& capacity) {
47 for (EdgeIt e(graph); e != INVALID; ++e) {
51 if (cut[s] != cut[t]) {
61 IntEdgeMap capacity(graph);
63 std::istringstream input(test_lgf);
64 GraphReader<Graph>(graph, input).
65 edgeMap("capacity", capacity).run();
67 GomoryHuTree<Graph> ght(graph, capacity);
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);
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");