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