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@440: * Copyright (C) 2003-2009 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@596: #include kpeter@596: #include kpeter@596: #include kpeter@596: #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@596: " cap1 cap2 cap3\n" kpeter@596: "0 1 1 1 1 \n" kpeter@596: "0 2 2 2 4 \n" kpeter@596: "1 2 4 4 4 \n" kpeter@596: "3 4 1 1 1 \n" kpeter@596: "3 5 2 2 4 \n" kpeter@596: "4 5 4 4 4 \n" kpeter@596: "5 4 4 4 4 \n" kpeter@596: "2 3 1 6 6 \n" kpeter@596: "4 0 1 6 6 \n"; kpeter@596: kpeter@596: void checkHaoOrlinCompile() kpeter@596: { kpeter@596: typedef int Value; kpeter@596: typedef concepts::Digraph Digraph; kpeter@596: kpeter@596: typedef Digraph::Node Node; kpeter@596: typedef Digraph::Arc Arc; kpeter@596: typedef concepts::ReadMap CapMap; kpeter@596: typedef concepts::WriteMap CutMap; kpeter@596: kpeter@596: Digraph g; kpeter@596: Node n; kpeter@596: CapMap cap; kpeter@596: CutMap cut; kpeter@596: Value v; alpar@1007: ignore_unused_variable_warning(v); kpeter@596: kpeter@596: HaoOrlin ho_test(g, cap); kpeter@596: const HaoOrlin& kpeter@596: const_ho_test = ho_test; kpeter@596: kpeter@596: ho_test.init(); kpeter@596: ho_test.init(n); kpeter@596: ho_test.calculateOut(); kpeter@596: ho_test.calculateIn(); kpeter@596: ho_test.run(); kpeter@596: ho_test.run(n); kpeter@596: kpeter@596: v = const_ho_test.minCutValue(); kpeter@596: v = const_ho_test.minCutMap(cut); kpeter@596: } kpeter@596: kpeter@596: template kpeter@596: typename CapMap::Value kpeter@596: cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) kpeter@596: { kpeter@596: typename CapMap::Value sum = 0; kpeter@596: for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { kpeter@596: if (cut[graph.source(a)] && !cut[graph.target(a)]) kpeter@596: sum += cap[a]; kpeter@596: } kpeter@596: return sum; kpeter@596: } deba@410: deba@410: int main() { kpeter@596: SmartDigraph graph; kpeter@596: SmartDigraph::ArcMap cap1(graph), cap2(graph), cap3(graph); kpeter@596: SmartDigraph::NodeMap cut(graph); deba@410: kpeter@596: istringstream input(lgf); kpeter@596: digraphReader(graph, input) kpeter@596: .arcMap("cap1", cap1) kpeter@596: .arcMap("cap2", cap2) kpeter@596: .arcMap("cap3", cap3) kpeter@596: .run(); deba@410: kpeter@596: { kpeter@596: HaoOrlin ho(graph, cap1); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); kpeter@596: deba@597: check(ho.minCutValue() == 1, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); kpeter@596: } kpeter@596: { kpeter@596: HaoOrlin ho(graph, cap2); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); deba@597: deba@597: check(ho.minCutValue() == 1, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); kpeter@596: } kpeter@596: { kpeter@596: HaoOrlin ho(graph, cap3); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); kpeter@596: deba@597: check(ho.minCutValue() == 1, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); kpeter@596: } kpeter@596: kpeter@596: typedef Undirector UGraph; kpeter@596: UGraph ugraph(graph); kpeter@596: kpeter@596: { kpeter@596: HaoOrlin > ho(ugraph, cap1); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); kpeter@596: deba@597: check(ho.minCutValue() == 2, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); kpeter@596: } kpeter@596: { kpeter@596: HaoOrlin > ho(ugraph, cap2); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); kpeter@596: deba@597: check(ho.minCutValue() == 5, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); kpeter@596: } kpeter@596: { kpeter@596: HaoOrlin > ho(ugraph, cap3); kpeter@596: ho.run(); kpeter@596: ho.minCutMap(cut); kpeter@596: kpeter@596: check(ho.minCutValue() == 5, "Wrong cut value"); deba@597: check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); kpeter@596: } deba@410: deba@410: return 0; deba@410: }