test/nagamochi_ibaraki_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 04 Mar 2011 12:18:38 +0100
changeset 930 8e39ccaabf48
child 1011 9a6c9d4ee77b
permissions -rw-r--r--
Merge #404
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <sstream>
    20 
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/adaptors.h>
    23 #include <lemon/concepts/graph.h>
    24 #include <lemon/concepts/maps.h>
    25 #include <lemon/lgf_reader.h>
    26 #include <lemon/nagamochi_ibaraki.h>
    27 
    28 #include "test_tools.h"
    29 
    30 using namespace lemon;
    31 using namespace std;
    32 
    33 const std::string lgf =
    34   "@nodes\n"
    35   "label\n"
    36   "0\n"
    37   "1\n"
    38   "2\n"
    39   "3\n"
    40   "4\n"
    41   "5\n"
    42   "@edges\n"
    43   "     cap1 cap2 cap3\n"
    44   "0 1  1    1    1   \n"
    45   "0 2  2    2    4   \n"
    46   "1 2  4    4    4   \n"
    47   "3 4  1    1    1   \n"
    48   "3 5  2    2    4   \n"
    49   "4 5  4    4    4   \n"
    50   "2 3  1    6    6   \n";
    51 
    52 void checkNagamochiIbarakiCompile()
    53 {
    54   typedef int Value;
    55   typedef concepts::Graph Graph;
    56 
    57   typedef Graph::Node Node;
    58   typedef Graph::Edge Edge;
    59   typedef concepts::ReadMap<Edge, Value> CapMap;
    60   typedef concepts::WriteMap<Node, bool> CutMap;
    61 
    62   Graph g;
    63   Node n;
    64   CapMap cap;
    65   CutMap cut;
    66   Value v;
    67   bool b;
    68 
    69   NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
    70   const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
    71 
    72   ni_test.init();
    73   ni_test.start();
    74   b = ni_test.processNextPhase();
    75   ni_test.run();
    76 
    77   v = const_ni_test.minCutValue();
    78   v = const_ni_test.minCutMap(cut);
    79 }
    80 
    81 template <typename Graph, typename CapMap, typename CutMap>
    82 typename CapMap::Value
    83   cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
    84 {
    85   typename CapMap::Value sum = 0;
    86   for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
    87     if (cut[graph.u(e)] != cut[graph.v(e)]) {
    88       sum += cap[e];
    89     }
    90   }
    91   return sum;
    92 }
    93 
    94 int main() {
    95   SmartGraph graph;
    96   SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
    97   SmartGraph::NodeMap<bool> cut(graph);
    98 
    99   istringstream input(lgf);
   100   graphReader(graph, input)
   101     .edgeMap("cap1", cap1)
   102     .edgeMap("cap2", cap2)
   103     .edgeMap("cap3", cap3)
   104     .run();
   105 
   106   {
   107     NagamochiIbaraki<SmartGraph> ni(graph, cap1);
   108     ni.run();
   109     ni.minCutMap(cut);
   110 
   111     check(ni.minCutValue() == 1, "Wrong cut value");
   112     check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
   113   }
   114   {
   115     NagamochiIbaraki<SmartGraph> ni(graph, cap2);
   116     ni.run();
   117     ni.minCutMap(cut);
   118 
   119     check(ni.minCutValue() == 3, "Wrong cut value");
   120     check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
   121   }
   122   {
   123     NagamochiIbaraki<SmartGraph> ni(graph, cap3);
   124     ni.run();
   125     ni.minCutMap(cut);
   126 
   127     check(ni.minCutValue() == 5, "Wrong cut value");
   128     check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
   129   }
   130   {
   131     NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
   132     ni.run();
   133     ni.minCutMap(cut);
   134 
   135     ConstMap<SmartGraph::Edge, int> cap4(1);
   136     check(ni.minCutValue() == 1, "Wrong cut value");
   137     check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
   138   }
   139 
   140   return 0;
   141 }