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