test/nagamochi_ibaraki_test.cc
changeset 917 4980b05606bd
child 1011 9a6c9d4ee77b
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/nagamochi_ibaraki_test.cc	Tue Nov 16 07:46:01 2010 +0100
     1.3 @@ -0,0 +1,141 @@
     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-2010
     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 +
    1.72 +  NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
    1.73 +  const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
    1.74 +
    1.75 +  ni_test.init();
    1.76 +  ni_test.start();
    1.77 +  b = ni_test.processNextPhase();
    1.78 +  ni_test.run();
    1.79 +
    1.80 +  v = const_ni_test.minCutValue();
    1.81 +  v = const_ni_test.minCutMap(cut);
    1.82 +}
    1.83 +
    1.84 +template <typename Graph, typename CapMap, typename CutMap>
    1.85 +typename CapMap::Value
    1.86 +  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    1.87 +{
    1.88 +  typename CapMap::Value sum = 0;
    1.89 +  for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
    1.90 +    if (cut[graph.u(e)] != cut[graph.v(e)]) {
    1.91 +      sum += cap[e];
    1.92 +    }
    1.93 +  }
    1.94 +  return sum;
    1.95 +}
    1.96 +
    1.97 +int main() {
    1.98 +  SmartGraph graph;
    1.99 +  SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
   1.100 +  SmartGraph::NodeMap<bool> cut(graph);
   1.101 +
   1.102 +  istringstream input(lgf);
   1.103 +  graphReader(graph, input)
   1.104 +    .edgeMap("cap1", cap1)
   1.105 +    .edgeMap("cap2", cap2)
   1.106 +    .edgeMap("cap3", cap3)
   1.107 +    .run();
   1.108 +
   1.109 +  {
   1.110 +    NagamochiIbaraki<SmartGraph> ni(graph, cap1);
   1.111 +    ni.run();
   1.112 +    ni.minCutMap(cut);
   1.113 +
   1.114 +    check(ni.minCutValue() == 1, "Wrong cut value");
   1.115 +    check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   1.116 +  }
   1.117 +  {
   1.118 +    NagamochiIbaraki<SmartGraph> ni(graph, cap2);
   1.119 +    ni.run();
   1.120 +    ni.minCutMap(cut);
   1.121 +
   1.122 +    check(ni.minCutValue() == 3, "Wrong cut value");
   1.123 +    check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   1.124 +  }
   1.125 +  {
   1.126 +    NagamochiIbaraki<SmartGraph> ni(graph, cap3);
   1.127 +    ni.run();
   1.128 +    ni.minCutMap(cut);
   1.129 +
   1.130 +    check(ni.minCutValue() == 5, "Wrong cut value");
   1.131 +    check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   1.132 +  }
   1.133 +  {
   1.134 +    NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
   1.135 +    ni.run();
   1.136 +    ni.minCutMap(cut);
   1.137 +
   1.138 +    ConstMap<SmartGraph::Edge, int> cap4(1);
   1.139 +    check(ni.minCutValue() == 1, "Wrong cut value");
   1.140 +    check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
   1.141 +  }
   1.142 +
   1.143 +  return 0;
   1.144 +}