deba@1017: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@1017: * deba@1017: * This file is a part of LEMON, a generic C++ optimization library. deba@1017: * deba@1017: * Copyright (C) 2003-2010 deba@1017: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1017: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1017: * deba@1017: * Permission to use, modify and distribute this software is granted deba@1017: * provided that this copyright notice appears in all copies. For deba@1017: * precise terms see the accompanying LICENSE file. deba@1017: * deba@1017: * This software is provided "AS IS" with no warranty of any kind, deba@1017: * express or implied, and with no claim as to its suitability for any deba@1017: * purpose. deba@1017: * deba@1017: */ deba@1017: deba@1017: #include deba@1017: deba@1017: #include deba@1017: #include deba@1017: #include deba@1017: #include deba@1017: #include deba@1017: #include deba@1017: deba@1017: #include "test_tools.h" deba@1017: deba@1017: using namespace lemon; deba@1017: using namespace std; deba@1017: deba@1017: const std::string lgf = deba@1017: "@nodes\n" deba@1017: "label\n" deba@1017: "0\n" deba@1017: "1\n" deba@1017: "2\n" deba@1017: "3\n" deba@1017: "4\n" deba@1017: "5\n" deba@1017: "@edges\n" deba@1017: " cap1 cap2 cap3\n" deba@1017: "0 1 1 1 1 \n" deba@1017: "0 2 2 2 4 \n" deba@1017: "1 2 4 4 4 \n" deba@1017: "3 4 1 1 1 \n" deba@1017: "3 5 2 2 4 \n" deba@1017: "4 5 4 4 4 \n" deba@1017: "2 3 1 6 6 \n"; deba@1017: deba@1017: void checkNagamochiIbarakiCompile() deba@1017: { deba@1017: typedef int Value; deba@1017: typedef concepts::Graph Graph; deba@1017: deba@1017: typedef Graph::Node Node; deba@1017: typedef Graph::Edge Edge; deba@1017: typedef concepts::ReadMap CapMap; deba@1017: typedef concepts::WriteMap CutMap; deba@1017: deba@1017: Graph g; deba@1017: Node n; deba@1017: CapMap cap; deba@1017: CutMap cut; deba@1017: Value v; deba@1017: bool b; deba@1017: deba@1017: NagamochiIbaraki ni_test(g, cap); deba@1017: const NagamochiIbaraki& const_ni_test = ni_test; deba@1017: deba@1017: ni_test.init(); deba@1017: ni_test.start(); deba@1017: b = ni_test.processNextPhase(); deba@1017: ni_test.run(); deba@1017: deba@1017: v = const_ni_test.minCutValue(); deba@1017: v = const_ni_test.minCutMap(cut); deba@1017: } deba@1017: deba@1017: template deba@1017: typename CapMap::Value deba@1017: cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) deba@1017: { deba@1017: typename CapMap::Value sum = 0; deba@1017: for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) { deba@1017: if (cut[graph.u(e)] != cut[graph.v(e)]) { deba@1017: sum += cap[e]; deba@1017: } deba@1017: } deba@1017: return sum; deba@1017: } deba@1017: deba@1017: int main() { deba@1017: SmartGraph graph; deba@1017: SmartGraph::EdgeMap cap1(graph), cap2(graph), cap3(graph); deba@1017: SmartGraph::NodeMap cut(graph); deba@1017: deba@1017: istringstream input(lgf); deba@1017: graphReader(graph, input) deba@1017: .edgeMap("cap1", cap1) deba@1017: .edgeMap("cap2", cap2) deba@1017: .edgeMap("cap3", cap3) deba@1017: .run(); deba@1017: deba@1017: { deba@1017: NagamochiIbaraki ni(graph, cap1); deba@1017: ni.run(); deba@1017: ni.minCutMap(cut); deba@1017: deba@1017: check(ni.minCutValue() == 1, "Wrong cut value"); deba@1017: check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); deba@1017: } deba@1017: { deba@1017: NagamochiIbaraki ni(graph, cap2); deba@1017: ni.run(); deba@1017: ni.minCutMap(cut); deba@1017: deba@1017: check(ni.minCutValue() == 3, "Wrong cut value"); deba@1017: check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); deba@1017: } deba@1017: { deba@1017: NagamochiIbaraki ni(graph, cap3); deba@1017: ni.run(); deba@1017: ni.minCutMap(cut); deba@1017: deba@1017: check(ni.minCutValue() == 5, "Wrong cut value"); deba@1017: check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); deba@1017: } deba@1017: { deba@1017: NagamochiIbaraki::SetUnitCapacity::Create ni(graph); deba@1017: ni.run(); deba@1017: ni.minCutMap(cut); deba@1017: deba@1017: ConstMap cap4(1); deba@1017: check(ni.minCutValue() == 1, "Wrong cut value"); deba@1017: check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value"); deba@1017: } deba@1017: deba@1017: return 0; deba@1017: }