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