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