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