1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/gomory_hu_test.cc Fri Feb 20 17:17:17 2009 +0100
1.3 @@ -0,0 +1,85 @@
1.4 +#include <iostream>
1.5 +
1.6 +#include "test_tools.h"
1.7 +#include <lemon/smart_graph.h>
1.8 +#include <lemon/adaptors.h>
1.9 +#include <lemon/lgf_reader.h>
1.10 +#include <lemon/lgf_writer.h>
1.11 +#include <lemon/dimacs.h>
1.12 +#include <lemon/time_measure.h>
1.13 +#include <lemon/gomory_hu_tree.h>
1.14 +#include <cstdlib>
1.15 +
1.16 +using namespace std;
1.17 +using namespace lemon;
1.18 +
1.19 +typedef SmartGraph Graph;
1.20 +
1.21 +char test_lgf[] =
1.22 + "@nodes\n"
1.23 + "label\n"
1.24 + "0\n"
1.25 + "1\n"
1.26 + "2\n"
1.27 + "3\n"
1.28 + "4\n"
1.29 + "@arcs\n"
1.30 + " label capacity\n"
1.31 + "0 1 0 1\n"
1.32 + "1 2 1 1\n"
1.33 + "2 3 2 1\n"
1.34 + "0 3 4 5\n"
1.35 + "0 3 5 10\n"
1.36 + "0 3 6 7\n"
1.37 + "4 2 7 1\n"
1.38 + "@attributes\n"
1.39 + "source 0\n"
1.40 + "target 3\n";
1.41 +
1.42 +GRAPH_TYPEDEFS(Graph);
1.43 +typedef Graph::EdgeMap<int> IntEdgeMap;
1.44 +typedef Graph::NodeMap<bool> BoolNodeMap;
1.45 +
1.46 +int cutValue(const Graph& graph, const BoolNodeMap& cut,
1.47 + const IntEdgeMap& capacity) {
1.48 +
1.49 + int sum = 0;
1.50 + for (EdgeIt e(graph); e != INVALID; ++e) {
1.51 + Node s = graph.u(e);
1.52 + Node t = graph.v(e);
1.53 +
1.54 + if (cut[s] != cut[t]) {
1.55 + sum += capacity[e];
1.56 + }
1.57 + }
1.58 + return sum;
1.59 +}
1.60 +
1.61 +
1.62 +int main() {
1.63 + Graph graph;
1.64 + IntEdgeMap capacity(graph);
1.65 +
1.66 + std::istringstream input(test_lgf);
1.67 + GraphReader<Graph>(graph, input).
1.68 + edgeMap("capacity", capacity).run();
1.69 +
1.70 + GomoryHuTree<Graph> ght(graph, capacity);
1.71 + ght.init();
1.72 + ght.run();
1.73 +
1.74 + for (NodeIt u(graph); u != INVALID; ++u) {
1.75 + for (NodeIt v(graph); v != u; ++v) {
1.76 + Preflow<Graph, IntEdgeMap> pf(graph, capacity, u, v);
1.77 + pf.runMinCut();
1.78 + BoolNodeMap cm(graph);
1.79 + ght.minCutMap(u, v, cm);
1.80 + check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
1.81 + check(cm[u] != cm[v], "Wrong cut 3");
1.82 + check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
1.83 +
1.84 + }
1.85 + }
1.86 +
1.87 + return 0;
1.88 +}