1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/nagamochi_ibaraki_test.cc Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,142 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2013
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <sstream>
1.23 +
1.24 +#include <lemon/smart_graph.h>
1.25 +#include <lemon/adaptors.h>
1.26 +#include <lemon/concepts/graph.h>
1.27 +#include <lemon/concepts/maps.h>
1.28 +#include <lemon/lgf_reader.h>
1.29 +#include <lemon/nagamochi_ibaraki.h>
1.30 +
1.31 +#include "test_tools.h"
1.32 +
1.33 +using namespace lemon;
1.34 +using namespace std;
1.35 +
1.36 +const std::string lgf =
1.37 + "@nodes\n"
1.38 + "label\n"
1.39 + "0\n"
1.40 + "1\n"
1.41 + "2\n"
1.42 + "3\n"
1.43 + "4\n"
1.44 + "5\n"
1.45 + "@edges\n"
1.46 + " cap1 cap2 cap3\n"
1.47 + "0 1 1 1 1 \n"
1.48 + "0 2 2 2 4 \n"
1.49 + "1 2 4 4 4 \n"
1.50 + "3 4 1 1 1 \n"
1.51 + "3 5 2 2 4 \n"
1.52 + "4 5 4 4 4 \n"
1.53 + "2 3 1 6 6 \n";
1.54 +
1.55 +void checkNagamochiIbarakiCompile()
1.56 +{
1.57 + typedef int Value;
1.58 + typedef concepts::Graph Graph;
1.59 +
1.60 + typedef Graph::Node Node;
1.61 + typedef Graph::Edge Edge;
1.62 + typedef concepts::ReadMap<Edge, Value> CapMap;
1.63 + typedef concepts::WriteMap<Node, bool> CutMap;
1.64 +
1.65 + Graph g;
1.66 + Node n;
1.67 + CapMap cap;
1.68 + CutMap cut;
1.69 + Value v;
1.70 + bool b;
1.71 + ::lemon::ignore_unused_variable_warning(v,b);
1.72 +
1.73 + NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
1.74 + const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
1.75 +
1.76 + ni_test.init();
1.77 + ni_test.start();
1.78 + b = ni_test.processNextPhase();
1.79 + ni_test.run();
1.80 +
1.81 + v = const_ni_test.minCutValue();
1.82 + v = const_ni_test.minCutMap(cut);
1.83 +}
1.84 +
1.85 +template <typename Graph, typename CapMap, typename CutMap>
1.86 +typename CapMap::Value
1.87 + cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
1.88 +{
1.89 + typename CapMap::Value sum = 0;
1.90 + for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
1.91 + if (cut[graph.u(e)] != cut[graph.v(e)]) {
1.92 + sum += cap[e];
1.93 + }
1.94 + }
1.95 + return sum;
1.96 +}
1.97 +
1.98 +int main() {
1.99 + SmartGraph graph;
1.100 + SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
1.101 + SmartGraph::NodeMap<bool> cut(graph);
1.102 +
1.103 + istringstream input(lgf);
1.104 + graphReader(graph, input)
1.105 + .edgeMap("cap1", cap1)
1.106 + .edgeMap("cap2", cap2)
1.107 + .edgeMap("cap3", cap3)
1.108 + .run();
1.109 +
1.110 + {
1.111 + NagamochiIbaraki<SmartGraph> ni(graph, cap1);
1.112 + ni.run();
1.113 + ni.minCutMap(cut);
1.114 +
1.115 + check(ni.minCutValue() == 1, "Wrong cut value");
1.116 + check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
1.117 + }
1.118 + {
1.119 + NagamochiIbaraki<SmartGraph> ni(graph, cap2);
1.120 + ni.run();
1.121 + ni.minCutMap(cut);
1.122 +
1.123 + check(ni.minCutValue() == 3, "Wrong cut value");
1.124 + check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
1.125 + }
1.126 + {
1.127 + NagamochiIbaraki<SmartGraph> ni(graph, cap3);
1.128 + ni.run();
1.129 + ni.minCutMap(cut);
1.130 +
1.131 + check(ni.minCutValue() == 5, "Wrong cut value");
1.132 + check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
1.133 + }
1.134 + {
1.135 + NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
1.136 + ni.run();
1.137 + ni.minCutMap(cut);
1.138 +
1.139 + ConstMap<SmartGraph::Edge, int> cap4(1);
1.140 + check(ni.minCutValue() == 1, "Wrong cut value");
1.141 + check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
1.142 + }
1.143 +
1.144 + return 0;
1.145 +}