deba@410: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@410: * deba@410: * This file is a part of LEMON, a generic C++ optimization library. deba@410: * alpar@761: * Copyright (C) 2003-2011 deba@410: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@410: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@410: * deba@410: * Permission to use, modify and distribute this software is granted deba@410: * provided that this copyright notice appears in all copies. For deba@410: * precise terms see the accompanying LICENSE file. deba@410: * deba@410: * This software is provided "AS IS" with no warranty of any kind, deba@410: * express or implied, and with no claim as to its suitability for any deba@410: * purpose. deba@410: * deba@410: */ deba@410: deba@410: #include deba@410: deba@410: #include kpeter@588: #include kpeter@588: #include kpeter@588: #include kpeter@588: #include deba@410: #include deba@410: deba@410: #include "test_tools.h" deba@410: deba@410: using namespace lemon; deba@410: using namespace std; deba@410: deba@410: const std::string lgf = deba@410: "@nodes\n" deba@410: "label\n" deba@410: "0\n" deba@410: "1\n" deba@410: "2\n" deba@410: "3\n" deba@410: "4\n" deba@410: "5\n" deba@410: "@edges\n" kpeter@588: " cap1 cap2 cap3\n" kpeter@588: "0 1 1 1 1 \n" kpeter@588: "0 2 2 2 4 \n" kpeter@588: "1 2 4 4 4 \n" kpeter@588: "3 4 1 1 1 \n" kpeter@588: "3 5 2 2 4 \n" kpeter@588: "4 5 4 4 4 \n" kpeter@588: "5 4 4 4 4 \n" kpeter@588: "2 3 1 6 6 \n" kpeter@588: "4 0 1 6 6 \n"; kpeter@588: kpeter@588: void checkHaoOrlinCompile() kpeter@588: { kpeter@588: typedef int Value; kpeter@588: typedef concepts::Digraph Digraph; kpeter@588: kpeter@588: typedef Digraph::Node Node; kpeter@588: typedef Digraph::Arc Arc; kpeter@588: typedef concepts::ReadMap CapMap; kpeter@588: typedef concepts::WriteMap CutMap; kpeter@588: kpeter@588: Digraph g; kpeter@588: Node n; kpeter@588: CapMap cap; kpeter@588: CutMap cut; kpeter@588: Value v; kpeter@588: kpeter@588: HaoOrlin ho_test(g, cap); kpeter@588: const HaoOrlin& kpeter@588: const_ho_test = ho_test; kpeter@588: kpeter@588: ho_test.init(); kpeter@588: ho_test.init(n); kpeter@588: ho_test.calculateOut(); kpeter@588: ho_test.calculateIn(); kpeter@588: ho_test.run(); kpeter@588: ho_test.run(n); kpeter@588: kpeter@588: v = const_ho_test.minCutValue(); kpeter@588: v = const_ho_test.minCutMap(cut); kpeter@588: } kpeter@588: kpeter@588: template alpar@761: typename CapMap::Value kpeter@588: cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) kpeter@588: { kpeter@588: typename CapMap::Value sum = 0; kpeter@588: for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { kpeter@588: if (cut[graph.source(a)] && !cut[graph.target(a)]) kpeter@588: sum += cap[a]; kpeter@588: } kpeter@588: return sum; kpeter@588: } deba@410: deba@410: int main() { kpeter@588: SmartDigraph graph; kpeter@588: SmartDigraph::ArcMap cap1(graph), cap2(graph), cap3(graph); kpeter@588: SmartDigraph::NodeMap cut(graph); deba@410: kpeter@588: istringstream input(lgf); kpeter@588: digraphReader(graph, input) kpeter@588: .arcMap("cap1", cap1) kpeter@588: .arcMap("cap2", cap2) kpeter@588: .arcMap("cap3", cap3) kpeter@588: .run(); deba@410: kpeter@588: { kpeter@588: HaoOrlin ho(graph, cap1); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); alpar@761: deba@589: check(ho.minCutValue() == 1, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); kpeter@588: } kpeter@588: { kpeter@588: HaoOrlin ho(graph, cap2); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); deba@589: deba@589: check(ho.minCutValue() == 1, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); kpeter@588: } kpeter@588: { kpeter@588: HaoOrlin ho(graph, cap3); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); alpar@761: deba@589: check(ho.minCutValue() == 1, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); kpeter@588: } alpar@761: kpeter@588: typedef Undirector UGraph; kpeter@588: UGraph ugraph(graph); alpar@761: kpeter@588: { kpeter@588: HaoOrlin > ho(ugraph, cap1); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); alpar@761: deba@589: check(ho.minCutValue() == 2, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); kpeter@588: } kpeter@588: { kpeter@588: HaoOrlin > ho(ugraph, cap2); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); alpar@761: deba@589: check(ho.minCutValue() == 5, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); kpeter@588: } kpeter@588: { kpeter@588: HaoOrlin > ho(ugraph, cap3); kpeter@588: ho.run(); kpeter@588: ho.minCutMap(cut); alpar@761: kpeter@588: check(ho.minCutValue() == 5, "Wrong cut value"); deba@589: check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); kpeter@588: } deba@410: deba@410: return 0; deba@410: }