/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include "test_tools.h" #include #include #include #include #include #include using namespace std; using namespace lemon; typedef SmartGraph Graph; char test_lgf[] = "@nodes\n" "label\n" "0\n" "1\n" "2\n" "3\n" "4\n" "@arcs\n" " label capacity\n" "0 1 0 1\n" "1 2 1 1\n" "2 3 2 1\n" "0 3 4 5\n" "0 3 5 10\n" "0 3 6 7\n" "4 2 7 1\n" "@attributes\n" "source 0\n" "target 3\n"; void checkGomoryHuCompile() { typedef int Value; typedef concepts::Graph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; typedef concepts::ReadMap CapMap; typedef concepts::ReadWriteMap CutMap; Graph g; Node n; CapMap cap; CutMap cut; Value v; int d; GomoryHu gh_test(g, cap); const GomoryHu& const_gh_test = gh_test; gh_test.run(); n = const_gh_test.predNode(n); v = const_gh_test.predValue(n); d = const_gh_test.rootDist(n); v = const_gh_test.minCutValue(n, n); v = const_gh_test.minCutMap(n, n, cut); } GRAPH_TYPEDEFS(Graph); typedef Graph::EdgeMap IntEdgeMap; typedef Graph::NodeMap BoolNodeMap; int cutValue(const Graph& graph, const BoolNodeMap& cut, const IntEdgeMap& capacity) { int sum = 0; for (EdgeIt e(graph); e != INVALID; ++e) { Node s = graph.u(e); Node t = graph.v(e); if (cut[s] != cut[t]) { sum += capacity[e]; } } return sum; } int main() { Graph graph; IntEdgeMap capacity(graph); std::istringstream input(test_lgf); GraphReader(graph, input). edgeMap("capacity", capacity).run(); GomoryHu ght(graph, capacity); ght.run(); for (NodeIt u(graph); u != INVALID; ++u) { for (NodeIt v(graph); v != u; ++v) { Preflow pf(graph, capacity, u, v); pf.runMinCut(); BoolNodeMap cm(graph); ght.minCutMap(u, v, cm); check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); check(cm[u] != cm[v], "Wrong cut 2"); check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); int sum=0; for(GomoryHu::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) sum+=capacity[a]; check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt"); sum=0; for(GomoryHu::MinCutNodeIt n(ght, u, v,true);n!=INVALID;++n) sum++; for(GomoryHu::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) sum++; check(sum == countNodes(graph), "Problem with MinCutNodeIt"); } } return 0; }