Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 16 Nov 2010 07:46:01 +0100
changeset 9174980b05606bd
parent 916 70bee017b584
parent 915 234d635ad721
child 918 8583fb74238c
child 921 140c953ad5d1
child 1031 ae0b056593a7
Merge
lemon/Makefile.am
test/CMakeLists.txt
test/Makefile.am
     1.1 --- a/CMakeLists.txt	Mon Nov 15 22:23:35 2010 +0100
     1.2 +++ b/CMakeLists.txt	Tue Nov 16 07:46:01 2010 +0100
     1.3 @@ -4,6 +4,7 @@
     1.4  PROJECT(${PROJECT_NAME})
     1.5  
     1.6  INCLUDE(FindPythonInterp)
     1.7 +INCLUDE(FindWget)
     1.8  
     1.9  IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    1.10    INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     2.1 --- a/doc/CMakeLists.txt	Mon Nov 15 22:23:35 2010 +0100
     2.2 +++ b/doc/CMakeLists.txt	Tue Nov 16 07:46:01 2010 +0100
     2.3 @@ -3,6 +3,8 @@
     2.4  SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
     2.5  SET(abs_top_builddir ${PROJECT_BINARY_DIR})
     2.6  
     2.7 +SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     2.8 +
     2.9  CONFIGURE_FILE(
    2.10    ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    2.11    ${PROJECT_BINARY_DIR}/doc/Doxyfile
    2.12 @@ -52,3 +54,15 @@
    2.13    ENDIF()
    2.14  
    2.15  ENDIF()
    2.16 +
    2.17 +IF(WGET_FOUND)
    2.18 +ADD_CUSTOM_TARGET(update-external-tags
    2.19 +  COMMAND ${CMAKE_COMMAND} -E make_directory dl
    2.20 +  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
    2.21 +  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
    2.22 +  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
    2.23 +  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
    2.24 +  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
    2.25 +  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    2.26 +  )
    2.27 +ENDIF()
     3.1 --- a/doc/Doxyfile.in	Mon Nov 15 22:23:35 2010 +0100
     3.2 +++ b/doc/Doxyfile.in	Tue Nov 16 07:46:01 2010 +0100
     3.3 @@ -70,7 +70,7 @@
     3.4  SHOW_FILES             = YES
     3.5  SHOW_NAMESPACES        = YES
     3.6  FILE_VERSION_FILTER    = 
     3.7 -LAYOUT_FILE            = DoxygenLayout.xml
     3.8 +LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     3.9  #---------------------------------------------------------------------------
    3.10  # configuration options related to warning and progress messages
    3.11  #---------------------------------------------------------------------------
    3.12 @@ -114,7 +114,7 @@
    3.13  #---------------------------------------------------------------------------
    3.14  # configuration options related to source browsing
    3.15  #---------------------------------------------------------------------------
    3.16 -SOURCE_BROWSER         = NO
    3.17 +SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    3.18  INLINE_SOURCES         = NO
    3.19  STRIP_CODE_COMMENTS    = YES
    3.20  REFERENCED_BY_RELATION = NO
    3.21 @@ -225,7 +225,7 @@
    3.22  #---------------------------------------------------------------------------
    3.23  # Options related to the search engine   
    3.24  #---------------------------------------------------------------------------
    3.25 -TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    3.26 +TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    3.27  GENERATE_TAGFILE       = html/lemon.tag
    3.28  ALLEXTERNALS           = NO
    3.29  EXTERNAL_GROUPS        = NO
     4.1 --- a/lemon/CMakeLists.txt	Mon Nov 15 22:23:35 2010 +0100
     4.2 +++ b/lemon/CMakeLists.txt	Tue Nov 16 07:46:01 2010 +0100
     4.3 @@ -8,6 +8,12 @@
     4.4    ${CMAKE_CURRENT_BINARY_DIR}/config.h
     4.5  )
     4.6  
     4.7 +CONFIGURE_FILE(
     4.8 +  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     4.9 +  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    4.10 +  @ONLY
    4.11 +)
    4.12 +
    4.13  SET(LEMON_SOURCES
    4.14    arg_parser.cc
    4.15    base.cc
    4.16 @@ -66,3 +72,9 @@
    4.17    DESTINATION include/lemon
    4.18    COMPONENT headers
    4.19  )
    4.20 +
    4.21 +INSTALL(
    4.22 +  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    4.23 +  DESTINATION lib/pkgconfig
    4.24 +)
    4.25 +
     5.1 --- a/lemon/Makefile.am	Mon Nov 15 22:23:35 2010 +0100
     5.2 +++ b/lemon/Makefile.am	Tue Nov 16 07:46:01 2010 +0100
     5.3 @@ -108,6 +108,7 @@
     5.4  	lemon/math.h \
     5.5  	lemon/min_cost_arborescence.h \
     5.6  	lemon/max_cardinality_search.h \
     5.7 +	lemon/nagamochi_ibaraki.h \
     5.8  	lemon/nauty_reader.h \
     5.9  	lemon/network_simplex.h \
    5.10  	lemon/pairing_heap.h \
     6.1 --- a/lemon/hao_orlin.h	Mon Nov 15 22:23:35 2010 +0100
     6.2 +++ b/lemon/hao_orlin.h	Tue Nov 16 07:46:01 2010 +0100
     6.3 @@ -53,8 +53,8 @@
     6.4    /// minimum cut of \f$ D \f$. The algorithm is a modified
     6.5    /// preflow push-relabel algorithm. Our implementation calculates
     6.6    /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
     6.7 -  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
     6.8 -  /// purpose of such algorithm is e.g. testing network reliability.
     6.9 +  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
    6.10 +  /// use of this algorithm is testing network reliability.
    6.11    ///
    6.12    /// For an undirected graph you can run just the first phase of the
    6.13    /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
    6.14 @@ -912,6 +912,8 @@
    6.15      /// This function calculates a minimum cut with \f$ source \f$ on the
    6.16      /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    6.17      /// \f$ source \in X \f$ and minimal outgoing capacity).
    6.18 +    /// It updates the stored cut if (and only if) the newly found one
    6.19 +    /// is better.
    6.20      ///
    6.21      /// \pre \ref init() must be called before using this function.
    6.22      void calculateOut() {
    6.23 @@ -924,6 +926,8 @@
    6.24      /// This function calculates a minimum cut with \f$ source \f$ on the
    6.25      /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
    6.26      /// \f$ source \notin X \f$ and minimal outgoing capacity).
    6.27 +    /// It updates the stored cut if (and only if) the newly found one
    6.28 +    /// is better.
    6.29      ///
    6.30      /// \pre \ref init() must be called before using this function.
    6.31      void calculateIn() {
    6.32 @@ -933,8 +937,8 @@
    6.33  
    6.34      /// \brief Run the algorithm.
    6.35      ///
    6.36 -    /// This function runs the algorithm. It finds nodes \c source and
    6.37 -    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
    6.38 +    /// This function runs the algorithm. It chooses source node,
    6.39 +    /// then calls \ref init(), \ref calculateOut()
    6.40      /// and \ref calculateIn().
    6.41      void run() {
    6.42        init();
    6.43 @@ -944,9 +948,9 @@
    6.44  
    6.45      /// \brief Run the algorithm.
    6.46      ///
    6.47 -    /// This function runs the algorithm. It uses the given \c source node,
    6.48 -    /// finds a proper \c target node and then calls the \ref init(),
    6.49 -    /// \ref calculateOut() and \ref calculateIn().
    6.50 +    /// This function runs the algorithm. It calls \ref init(),
    6.51 +    /// \ref calculateOut() and \ref calculateIn() with the given
    6.52 +    /// source node.
    6.53      void run(const Node& s) {
    6.54        init(s);
    6.55        calculateOut();
    6.56 @@ -965,7 +969,9 @@
    6.57  
    6.58      /// \brief Return the value of the minimum cut.
    6.59      ///
    6.60 -    /// This function returns the value of the minimum cut.
    6.61 +    /// This function returns the value of the best cut found by the
    6.62 +    /// previously called \ref run(), \ref calculateOut() or \ref
    6.63 +    /// calculateIn().
    6.64      ///
    6.65      /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    6.66      /// must be called before using this function.
    6.67 @@ -976,9 +982,13 @@
    6.68  
    6.69      /// \brief Return a minimum cut.
    6.70      ///
    6.71 -    /// This function sets \c cutMap to the characteristic vector of a
    6.72 -    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
    6.73 -    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
    6.74 +    /// This function gives the best cut found by the
    6.75 +    /// previously called \ref run(), \ref calculateOut() or \ref
    6.76 +    /// calculateIn().
    6.77 +    ///
    6.78 +    /// It sets \c cutMap to the characteristic vector of the found
    6.79 +    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
    6.80 +    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
    6.81      /// for the nodes of \f$ X \f$).
    6.82      ///
    6.83      /// \param cutMap A \ref concepts::WriteMap "writable" node map with
     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/lemon/lemon.pc.cmake	Tue Nov 16 07:46:01 2010 +0100
     7.3 @@ -0,0 +1,10 @@
     7.4 +prefix=@CMAKE_INSTALL_PREFIX@
     7.5 +exec_prefix=@CMAKE_INSTALL_PREFIX@/bin
     7.6 +libdir=@CMAKE_INSTALL_PREFIX@/lib
     7.7 +includedir=@CMAKE_INSTALL_PREFIX@/include
     7.8 +
     7.9 +Name: @PROJECT_NAME@
    7.10 +Description: Library for Efficient Modeling and Optimization in Networks
    7.11 +Version: @PROJECT_VERSION@
    7.12 +Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
    7.13 +Cflags: -I${includedir}
     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/lemon/nagamochi_ibaraki.h	Tue Nov 16 07:46:01 2010 +0100
     8.3 @@ -0,0 +1,697 @@
     8.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     8.5 + *
     8.6 + * This file is a part of LEMON, a generic C++ optimization library.
     8.7 + *
     8.8 + * Copyright (C) 2003-2010
     8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    8.11 + *
    8.12 + * Permission to use, modify and distribute this software is granted
    8.13 + * provided that this copyright notice appears in all copies. For
    8.14 + * precise terms see the accompanying LICENSE file.
    8.15 + *
    8.16 + * This software is provided "AS IS" with no warranty of any kind,
    8.17 + * express or implied, and with no claim as to its suitability for any
    8.18 + * purpose.
    8.19 + *
    8.20 + */
    8.21 +
    8.22 +#ifndef LEMON_NAGAMOCHI_IBARAKI_H
    8.23 +#define LEMON_NAGAMOCHI_IBARAKI_H
    8.24 +
    8.25 +
    8.26 +/// \ingroup min_cut
    8.27 +/// \file
    8.28 +/// \brief Implementation of the Nagamochi-Ibaraki algorithm.
    8.29 +
    8.30 +#include <lemon/core.h>
    8.31 +#include <lemon/bin_heap.h>
    8.32 +#include <lemon/bucket_heap.h>
    8.33 +#include <lemon/maps.h>
    8.34 +#include <lemon/radix_sort.h>
    8.35 +#include <lemon/unionfind.h>
    8.36 +
    8.37 +#include <cassert>
    8.38 +
    8.39 +namespace lemon {
    8.40 +
    8.41 +  /// \brief Default traits class for NagamochiIbaraki class.
    8.42 +  ///
    8.43 +  /// Default traits class for NagamochiIbaraki class.
    8.44 +  /// \param GR The undirected graph type.
    8.45 +  /// \param CM Type of capacity map.
    8.46 +  template <typename GR, typename CM>
    8.47 +  struct NagamochiIbarakiDefaultTraits {
    8.48 +    /// The type of the capacity map.
    8.49 +    typedef typename CM::Value Value;
    8.50 +
    8.51 +    /// The undirected graph type the algorithm runs on.
    8.52 +    typedef GR Graph;
    8.53 +
    8.54 +    /// \brief The type of the map that stores the edge capacities.
    8.55 +    ///
    8.56 +    /// The type of the map that stores the edge capacities.
    8.57 +    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    8.58 +    typedef CM CapacityMap;
    8.59 +
    8.60 +    /// \brief Instantiates a CapacityMap.
    8.61 +    ///
    8.62 +    /// This function instantiates a \ref CapacityMap.
    8.63 +#ifdef DOXYGEN
    8.64 +    static CapacityMap *createCapacityMap(const Graph& graph)
    8.65 +#else
    8.66 +    static CapacityMap *createCapacityMap(const Graph&)
    8.67 +#endif
    8.68 +    {
    8.69 +        LEMON_ASSERT(false, "CapacityMap is not initialized");
    8.70 +        return 0; // ignore warnings
    8.71 +    }
    8.72 +
    8.73 +    /// \brief The cross reference type used by heap.
    8.74 +    ///
    8.75 +    /// The cross reference type used by heap.
    8.76 +    /// Usually \c Graph::NodeMap<int>.
    8.77 +    typedef typename Graph::template NodeMap<int> HeapCrossRef;
    8.78 +
    8.79 +    /// \brief Instantiates a HeapCrossRef.
    8.80 +    ///
    8.81 +    /// This function instantiates a \ref HeapCrossRef.
    8.82 +    /// \param g is the graph, to which we would like to define the
    8.83 +    /// \ref HeapCrossRef.
    8.84 +    static HeapCrossRef *createHeapCrossRef(const Graph& g) {
    8.85 +      return new HeapCrossRef(g);
    8.86 +    }
    8.87 +
    8.88 +    /// \brief The heap type used by NagamochiIbaraki algorithm.
    8.89 +    ///
    8.90 +    /// The heap type used by NagamochiIbaraki algorithm. It has to
    8.91 +    /// maximize the priorities.
    8.92 +    ///
    8.93 +    /// \sa BinHeap
    8.94 +    /// \sa NagamochiIbaraki
    8.95 +    typedef BinHeap<Value, HeapCrossRef, std::greater<Value> > Heap;
    8.96 +
    8.97 +    /// \brief Instantiates a Heap.
    8.98 +    ///
    8.99 +    /// This function instantiates a \ref Heap.
   8.100 +    /// \param r is the cross reference of the heap.
   8.101 +    static Heap *createHeap(HeapCrossRef& r) {
   8.102 +      return new Heap(r);
   8.103 +    }
   8.104 +  };
   8.105 +
   8.106 +  /// \ingroup min_cut
   8.107 +  ///
   8.108 +  /// \brief Calculates the minimum cut in an undirected graph.
   8.109 +  ///
   8.110 +  /// Calculates the minimum cut in an undirected graph with the
   8.111 +  /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
   8.112 +  /// nodes into two partitions with the minimum sum of edge capacities
   8.113 +  /// between the two partitions. The algorithm can be used to test
   8.114 +  /// the network reliability, especially to test how many links have
   8.115 +  /// to be destroyed in the network to split it to at least two
   8.116 +  /// distinict subnetworks.
   8.117 +  ///
   8.118 +  /// The complexity of the algorithm is \f$ O(nm\log(n)) \f$ but with
   8.119 +  /// \ref FibHeap "Fibonacci heap" it can be decreased to
   8.120 +  /// \f$ O(nm+n^2\log(n)) \f$.  When the edges have unit capacities,
   8.121 +  /// \c BucketHeap can be used which yields \f$ O(nm) \f$ time
   8.122 +  /// complexity.
   8.123 +  ///
   8.124 +  /// \warning The value type of the capacity map should be able to
   8.125 +  /// hold any cut value of the graph, otherwise the result can
   8.126 +  /// overflow.
   8.127 +  /// \note This capacity is supposed to be integer type.
   8.128 +#ifdef DOXYGEN
   8.129 +  template <typename GR, typename CM, typename TR>
   8.130 +#else
   8.131 +  template <typename GR,
   8.132 +            typename CM = typename GR::template EdgeMap<int>,
   8.133 +            typename TR = NagamochiIbarakiDefaultTraits<GR, CM> >
   8.134 +#endif
   8.135 +  class NagamochiIbaraki {
   8.136 +  public:
   8.137 +
   8.138 +    typedef TR Traits;
   8.139 +    /// The type of the underlying graph.
   8.140 +    typedef typename Traits::Graph Graph;
   8.141 +
   8.142 +    /// The type of the capacity map.
   8.143 +    typedef typename Traits::CapacityMap CapacityMap;
   8.144 +    /// The value type of the capacity map.
   8.145 +    typedef typename Traits::CapacityMap::Value Value;
   8.146 +
   8.147 +    /// The heap type used by the algorithm.
   8.148 +    typedef typename Traits::Heap Heap;
   8.149 +    /// The cross reference type used for the heap.
   8.150 +    typedef typename Traits::HeapCrossRef HeapCrossRef;
   8.151 +
   8.152 +    ///\name Named template parameters
   8.153 +
   8.154 +    ///@{
   8.155 +
   8.156 +    struct SetUnitCapacityTraits : public Traits {
   8.157 +      typedef ConstMap<typename Graph::Edge, Const<int, 1> > CapacityMap;
   8.158 +      static CapacityMap *createCapacityMap(const Graph&) {
   8.159 +        return new CapacityMap();
   8.160 +      }
   8.161 +    };
   8.162 +
   8.163 +    /// \brief \ref named-templ-param "Named parameter" for setting
   8.164 +    /// the capacity map to a constMap<Edge, int, 1>() instance
   8.165 +    ///
   8.166 +    /// \ref named-templ-param "Named parameter" for setting
   8.167 +    /// the capacity map to a constMap<Edge, int, 1>() instance
   8.168 +    struct SetUnitCapacity
   8.169 +      : public NagamochiIbaraki<Graph, CapacityMap,
   8.170 +                                SetUnitCapacityTraits> {
   8.171 +      typedef NagamochiIbaraki<Graph, CapacityMap,
   8.172 +                               SetUnitCapacityTraits> Create;
   8.173 +    };
   8.174 +
   8.175 +
   8.176 +    template <class H, class CR>
   8.177 +    struct SetHeapTraits : public Traits {
   8.178 +      typedef CR HeapCrossRef;
   8.179 +      typedef H Heap;
   8.180 +      static HeapCrossRef *createHeapCrossRef(int num) {
   8.181 +        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
   8.182 +        return 0; // ignore warnings
   8.183 +      }
   8.184 +      static Heap *createHeap(HeapCrossRef &) {
   8.185 +        LEMON_ASSERT(false, "Heap is not initialized");
   8.186 +        return 0; // ignore warnings
   8.187 +      }
   8.188 +    };
   8.189 +
   8.190 +    /// \brief \ref named-templ-param "Named parameter" for setting
   8.191 +    /// heap and cross reference type
   8.192 +    ///
   8.193 +    /// \ref named-templ-param "Named parameter" for setting heap and
   8.194 +    /// cross reference type. The heap has to maximize the priorities.
   8.195 +    template <class H, class CR = RangeMap<int> >
   8.196 +    struct SetHeap
   8.197 +      : public NagamochiIbaraki<Graph, CapacityMap, SetHeapTraits<H, CR> > {
   8.198 +      typedef NagamochiIbaraki< Graph, CapacityMap, SetHeapTraits<H, CR> >
   8.199 +      Create;
   8.200 +    };
   8.201 +
   8.202 +    template <class H, class CR>
   8.203 +    struct SetStandardHeapTraits : public Traits {
   8.204 +      typedef CR HeapCrossRef;
   8.205 +      typedef H Heap;
   8.206 +      static HeapCrossRef *createHeapCrossRef(int size) {
   8.207 +        return new HeapCrossRef(size);
   8.208 +      }
   8.209 +      static Heap *createHeap(HeapCrossRef &crossref) {
   8.210 +        return new Heap(crossref);
   8.211 +      }
   8.212 +    };
   8.213 +
   8.214 +    /// \brief \ref named-templ-param "Named parameter" for setting
   8.215 +    /// heap and cross reference type with automatic allocation
   8.216 +    ///
   8.217 +    /// \ref named-templ-param "Named parameter" for setting heap and
   8.218 +    /// cross reference type with automatic allocation. They should
   8.219 +    /// have standard constructor interfaces to be able to
   8.220 +    /// automatically created by the algorithm (i.e. the graph should
   8.221 +    /// be passed to the constructor of the cross reference and the
   8.222 +    /// cross reference should be passed to the constructor of the
   8.223 +    /// heap). However, external heap and cross reference objects
   8.224 +    /// could also be passed to the algorithm using the \ref heap()
   8.225 +    /// function before calling \ref run() or \ref init(). The heap
   8.226 +    /// has to maximize the priorities.
   8.227 +    /// \sa SetHeap
   8.228 +    template <class H, class CR = RangeMap<int> >
   8.229 +    struct SetStandardHeap
   8.230 +      : public NagamochiIbaraki<Graph, CapacityMap,
   8.231 +                                SetStandardHeapTraits<H, CR> > {
   8.232 +      typedef NagamochiIbaraki<Graph, CapacityMap,
   8.233 +                               SetStandardHeapTraits<H, CR> > Create;
   8.234 +    };
   8.235 +
   8.236 +    ///@}
   8.237 +
   8.238 +
   8.239 +  private:
   8.240 +
   8.241 +    const Graph &_graph;
   8.242 +    const CapacityMap *_capacity;
   8.243 +    bool _local_capacity; // unit capacity
   8.244 +
   8.245 +    struct ArcData {
   8.246 +      typename Graph::Node target;
   8.247 +      int prev, next;
   8.248 +    };
   8.249 +    struct EdgeData {
   8.250 +      Value capacity;
   8.251 +      Value cut;
   8.252 +    };
   8.253 +
   8.254 +    struct NodeData {
   8.255 +      int first_arc;
   8.256 +      typename Graph::Node prev, next;
   8.257 +      int curr_arc;
   8.258 +      typename Graph::Node last_rep;
   8.259 +      Value sum;
   8.260 +    };
   8.261 +
   8.262 +    typename Graph::template NodeMap<NodeData> *_nodes;
   8.263 +    std::vector<ArcData> _arcs;
   8.264 +    std::vector<EdgeData> _edges;
   8.265 +
   8.266 +    typename Graph::Node _first_node;
   8.267 +    int _node_num;
   8.268 +
   8.269 +    Value _min_cut;
   8.270 +
   8.271 +    HeapCrossRef *_heap_cross_ref;
   8.272 +    bool _local_heap_cross_ref;
   8.273 +    Heap *_heap;
   8.274 +    bool _local_heap;
   8.275 +
   8.276 +    typedef typename Graph::template NodeMap<typename Graph::Node> NodeList;
   8.277 +    NodeList *_next_rep;
   8.278 +
   8.279 +    typedef typename Graph::template NodeMap<bool> MinCutMap;
   8.280 +    MinCutMap *_cut_map;
   8.281 +
   8.282 +    void createStructures() {
   8.283 +      if (!_nodes) {
   8.284 +        _nodes = new (typename Graph::template NodeMap<NodeData>)(_graph);
   8.285 +      }
   8.286 +      if (!_capacity) {
   8.287 +        _local_capacity = true;
   8.288 +        _capacity = Traits::createCapacityMap(_graph);
   8.289 +      }
   8.290 +      if (!_heap_cross_ref) {
   8.291 +        _local_heap_cross_ref = true;
   8.292 +        _heap_cross_ref = Traits::createHeapCrossRef(_graph);
   8.293 +      }
   8.294 +      if (!_heap) {
   8.295 +        _local_heap = true;
   8.296 +        _heap = Traits::createHeap(*_heap_cross_ref);
   8.297 +      }
   8.298 +      if (!_next_rep) {
   8.299 +        _next_rep = new NodeList(_graph);
   8.300 +      }
   8.301 +      if (!_cut_map) {
   8.302 +        _cut_map = new MinCutMap(_graph);
   8.303 +      }
   8.304 +    }
   8.305 +
   8.306 +  public :
   8.307 +
   8.308 +    typedef NagamochiIbaraki Create;
   8.309 +
   8.310 +
   8.311 +    /// \brief Constructor.
   8.312 +    ///
   8.313 +    /// \param graph The graph the algorithm runs on.
   8.314 +    /// \param capacity The capacity map used by the algorithm.
   8.315 +    NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)
   8.316 +      : _graph(graph), _capacity(&capacity), _local_capacity(false),
   8.317 +        _nodes(0), _arcs(), _edges(), _min_cut(),
   8.318 +        _heap_cross_ref(0), _local_heap_cross_ref(false),
   8.319 +        _heap(0), _local_heap(false),
   8.320 +        _next_rep(0), _cut_map(0) {}
   8.321 +
   8.322 +    /// \brief Constructor.
   8.323 +    ///
   8.324 +    /// This constructor can be used only when the Traits class
   8.325 +    /// defines how can the local capacity map be instantiated.
   8.326 +    /// If the SetUnitCapacity used the algorithm automatically
   8.327 +    /// constructs the capacity map.
   8.328 +    ///
   8.329 +    ///\param graph The graph the algorithm runs on.
   8.330 +    NagamochiIbaraki(const Graph& graph)
   8.331 +      : _graph(graph), _capacity(0), _local_capacity(false),
   8.332 +        _nodes(0), _arcs(), _edges(), _min_cut(),
   8.333 +        _heap_cross_ref(0), _local_heap_cross_ref(false),
   8.334 +        _heap(0), _local_heap(false),
   8.335 +        _next_rep(0), _cut_map(0) {}
   8.336 +
   8.337 +    /// \brief Destructor.
   8.338 +    ///
   8.339 +    /// Destructor.
   8.340 +    ~NagamochiIbaraki() {
   8.341 +      if (_local_capacity) delete _capacity;
   8.342 +      if (_nodes) delete _nodes;
   8.343 +      if (_local_heap) delete _heap;
   8.344 +      if (_local_heap_cross_ref) delete _heap_cross_ref;
   8.345 +      if (_next_rep) delete _next_rep;
   8.346 +      if (_cut_map) delete _cut_map;
   8.347 +    }
   8.348 +
   8.349 +    /// \brief Sets the heap and the cross reference used by algorithm.
   8.350 +    ///
   8.351 +    /// Sets the heap and the cross reference used by algorithm.
   8.352 +    /// If you don't use this function before calling \ref run(),
   8.353 +    /// it will allocate one. The destuctor deallocates this
   8.354 +    /// automatically allocated heap and cross reference, of course.
   8.355 +    /// \return <tt> (*this) </tt>
   8.356 +    NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)
   8.357 +    {
   8.358 +      if (_local_heap_cross_ref) {
   8.359 +        delete _heap_cross_ref;
   8.360 +        _local_heap_cross_ref = false;
   8.361 +      }
   8.362 +      _heap_cross_ref = &cr;
   8.363 +      if (_local_heap) {
   8.364 +        delete _heap;
   8.365 +        _local_heap = false;
   8.366 +      }
   8.367 +      _heap = &hp;
   8.368 +      return *this;
   8.369 +    }
   8.370 +
   8.371 +    /// \name Execution control
   8.372 +    /// The simplest way to execute the algorithm is to use
   8.373 +    /// one of the member functions called \c run().
   8.374 +    /// \n
   8.375 +    /// If you need more control on the execution,
   8.376 +    /// first you must call \ref init() and then call the start()
   8.377 +    /// or proper times the processNextPhase() member functions.
   8.378 +
   8.379 +    ///@{
   8.380 +
   8.381 +    /// \brief Initializes the internal data structures.
   8.382 +    ///
   8.383 +    /// Initializes the internal data structures.
   8.384 +    void init() {
   8.385 +      createStructures();
   8.386 +
   8.387 +      int edge_num = countEdges(_graph);
   8.388 +      _edges.resize(edge_num);
   8.389 +      _arcs.resize(2 * edge_num);
   8.390 +
   8.391 +      typename Graph::Node prev = INVALID;
   8.392 +      _node_num = 0;
   8.393 +      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   8.394 +        (*_cut_map)[n] = false;
   8.395 +        (*_next_rep)[n] = INVALID;
   8.396 +        (*_nodes)[n].last_rep = n;
   8.397 +        (*_nodes)[n].first_arc = -1;
   8.398 +        (*_nodes)[n].curr_arc = -1;
   8.399 +        (*_nodes)[n].prev = prev;
   8.400 +        if (prev != INVALID) {
   8.401 +          (*_nodes)[prev].next = n;
   8.402 +        }
   8.403 +        (*_nodes)[n].next = INVALID;
   8.404 +        (*_nodes)[n].sum = 0;
   8.405 +        prev = n;
   8.406 +        ++_node_num;
   8.407 +      }
   8.408 +
   8.409 +      _first_node = typename Graph::NodeIt(_graph);
   8.410 +
   8.411 +      int index = 0;
   8.412 +      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   8.413 +        for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
   8.414 +          typename Graph::Node m = _graph.target(a);
   8.415 +          
   8.416 +          if (!(n < m)) continue;
   8.417 +
   8.418 +          (*_nodes)[n].sum += (*_capacity)[a];
   8.419 +          (*_nodes)[m].sum += (*_capacity)[a];
   8.420 +          
   8.421 +          int c = (*_nodes)[m].curr_arc;
   8.422 +          if (c != -1 && _arcs[c ^ 1].target == n) {
   8.423 +            _edges[c >> 1].capacity += (*_capacity)[a];
   8.424 +          } else {
   8.425 +            _edges[index].capacity = (*_capacity)[a];
   8.426 +            
   8.427 +            _arcs[index << 1].prev = -1;
   8.428 +            if ((*_nodes)[n].first_arc != -1) {
   8.429 +              _arcs[(*_nodes)[n].first_arc].prev = (index << 1);
   8.430 +            }
   8.431 +            _arcs[index << 1].next = (*_nodes)[n].first_arc;
   8.432 +            (*_nodes)[n].first_arc = (index << 1);
   8.433 +            _arcs[index << 1].target = m;
   8.434 +
   8.435 +            (*_nodes)[m].curr_arc = (index << 1);
   8.436 +            
   8.437 +            _arcs[(index << 1) | 1].prev = -1;
   8.438 +            if ((*_nodes)[m].first_arc != -1) {
   8.439 +              _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1);
   8.440 +            }
   8.441 +            _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc;
   8.442 +            (*_nodes)[m].first_arc = ((index << 1) | 1);
   8.443 +            _arcs[(index << 1) | 1].target = n;
   8.444 +            
   8.445 +            ++index;
   8.446 +          }
   8.447 +        }
   8.448 +      }
   8.449 +
   8.450 +      typename Graph::Node cut_node = INVALID;
   8.451 +      _min_cut = std::numeric_limits<Value>::max();
   8.452 +
   8.453 +      for (typename Graph::Node n = _first_node; 
   8.454 +           n != INVALID; n = (*_nodes)[n].next) {
   8.455 +        if ((*_nodes)[n].sum < _min_cut) {
   8.456 +          cut_node = n;
   8.457 +          _min_cut = (*_nodes)[n].sum;
   8.458 +        }
   8.459 +      }
   8.460 +      (*_cut_map)[cut_node] = true;
   8.461 +      if (_min_cut == 0) {
   8.462 +        _first_node = INVALID;
   8.463 +      }
   8.464 +    }
   8.465 +
   8.466 +  public:
   8.467 +
   8.468 +    /// \brief Processes the next phase
   8.469 +    ///
   8.470 +    /// Processes the next phase in the algorithm. It must be called
   8.471 +    /// at most one less the number of the nodes in the graph.
   8.472 +    ///
   8.473 +    ///\return %True when the algorithm finished.
   8.474 +    bool processNextPhase() {
   8.475 +      if (_first_node == INVALID) return true;
   8.476 +
   8.477 +      _heap->clear();
   8.478 +      for (typename Graph::Node n = _first_node; 
   8.479 +           n != INVALID; n = (*_nodes)[n].next) {
   8.480 +        (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
   8.481 +      }
   8.482 +
   8.483 +      std::vector<typename Graph::Node> order;
   8.484 +      order.reserve(_node_num);
   8.485 +      int sep = 0;
   8.486 +
   8.487 +      Value alpha = 0;
   8.488 +      Value pmc = std::numeric_limits<Value>::max();
   8.489 +
   8.490 +      _heap->push(_first_node, static_cast<Value>(0));
   8.491 +      while (!_heap->empty()) {
   8.492 +        typename Graph::Node n = _heap->top();
   8.493 +        Value v = _heap->prio();
   8.494 +
   8.495 +        _heap->pop();
   8.496 +        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
   8.497 +          switch (_heap->state(_arcs[a].target)) {
   8.498 +          case Heap::PRE_HEAP: 
   8.499 +            {
   8.500 +              Value nv = _edges[a >> 1].capacity;
   8.501 +              _heap->push(_arcs[a].target, nv);
   8.502 +              _edges[a >> 1].cut = nv;
   8.503 +            } break;
   8.504 +          case Heap::IN_HEAP:
   8.505 +            {
   8.506 +              Value nv = _edges[a >> 1].capacity + (*_heap)[_arcs[a].target];
   8.507 +              _heap->decrease(_arcs[a].target, nv);
   8.508 +              _edges[a >> 1].cut = nv;
   8.509 +            } break;
   8.510 +          case Heap::POST_HEAP:
   8.511 +            break;
   8.512 +          }
   8.513 +        }
   8.514 +
   8.515 +        alpha += (*_nodes)[n].sum;
   8.516 +        alpha -= 2 * v;
   8.517 +
   8.518 +        order.push_back(n);
   8.519 +        if (!_heap->empty()) {
   8.520 +          if (alpha < pmc) {
   8.521 +            pmc = alpha;
   8.522 +            sep = order.size();
   8.523 +          }
   8.524 +        }
   8.525 +      }
   8.526 +
   8.527 +      if (static_cast<int>(order.size()) < _node_num) {
   8.528 +        _first_node = INVALID;
   8.529 +        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   8.530 +          (*_cut_map)[n] = false;
   8.531 +        }
   8.532 +        for (int i = 0; i < static_cast<int>(order.size()); ++i) {
   8.533 +          typename Graph::Node n = order[i];
   8.534 +          while (n != INVALID) {
   8.535 +            (*_cut_map)[n] = true;
   8.536 +            n = (*_next_rep)[n];
   8.537 +          }
   8.538 +        }
   8.539 +        _min_cut = 0;
   8.540 +        return true;
   8.541 +      }
   8.542 +
   8.543 +      if (pmc < _min_cut) {
   8.544 +        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   8.545 +          (*_cut_map)[n] = false;
   8.546 +        }
   8.547 +        for (int i = 0; i < sep; ++i) {
   8.548 +          typename Graph::Node n = order[i];
   8.549 +          while (n != INVALID) {
   8.550 +            (*_cut_map)[n] = true;
   8.551 +            n = (*_next_rep)[n];
   8.552 +          }
   8.553 +        }
   8.554 +        _min_cut = pmc;
   8.555 +      }
   8.556 +
   8.557 +      for (typename Graph::Node n = _first_node;
   8.558 +           n != INVALID; n = (*_nodes)[n].next) {
   8.559 +        bool merged = false;
   8.560 +        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
   8.561 +          if (!(_edges[a >> 1].cut < pmc)) {
   8.562 +            if (!merged) {
   8.563 +              for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
   8.564 +                (*_nodes)[_arcs[b].target].curr_arc = b;          
   8.565 +              }
   8.566 +              merged = true;
   8.567 +            }
   8.568 +            typename Graph::Node m = _arcs[a].target;
   8.569 +            int nb = 0;
   8.570 +            for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) {
   8.571 +              nb = _arcs[b].next;
   8.572 +              if ((b ^ a) == 1) continue;
   8.573 +              typename Graph::Node o = _arcs[b].target;
   8.574 +              int c = (*_nodes)[o].curr_arc; 
   8.575 +              if (c != -1 && _arcs[c ^ 1].target == n) {
   8.576 +                _edges[c >> 1].capacity += _edges[b >> 1].capacity;
   8.577 +                (*_nodes)[n].sum += _edges[b >> 1].capacity;
   8.578 +                if (_edges[b >> 1].cut < _edges[c >> 1].cut) {
   8.579 +                  _edges[b >> 1].cut = _edges[c >> 1].cut;
   8.580 +                }
   8.581 +                if (_arcs[b ^ 1].prev != -1) {
   8.582 +                  _arcs[_arcs[b ^ 1].prev].next = _arcs[b ^ 1].next;
   8.583 +                } else {
   8.584 +                  (*_nodes)[o].first_arc = _arcs[b ^ 1].next;
   8.585 +                }
   8.586 +                if (_arcs[b ^ 1].next != -1) {
   8.587 +                  _arcs[_arcs[b ^ 1].next].prev = _arcs[b ^ 1].prev;
   8.588 +                }
   8.589 +              } else {
   8.590 +                if (_arcs[a].next != -1) {
   8.591 +                  _arcs[_arcs[a].next].prev = b;
   8.592 +                }
   8.593 +                _arcs[b].next = _arcs[a].next;
   8.594 +                _arcs[b].prev = a;
   8.595 +                _arcs[a].next = b;
   8.596 +                _arcs[b ^ 1].target = n;
   8.597 +
   8.598 +                (*_nodes)[n].sum += _edges[b >> 1].capacity;
   8.599 +                (*_nodes)[o].curr_arc = b;
   8.600 +              }
   8.601 +            }
   8.602 +
   8.603 +            if (_arcs[a].prev != -1) {
   8.604 +              _arcs[_arcs[a].prev].next = _arcs[a].next;
   8.605 +            } else {
   8.606 +              (*_nodes)[n].first_arc = _arcs[a].next;
   8.607 +            }            
   8.608 +            if (_arcs[a].next != -1) {
   8.609 +              _arcs[_arcs[a].next].prev = _arcs[a].prev;
   8.610 +            }
   8.611 +
   8.612 +            (*_nodes)[n].sum -= _edges[a >> 1].capacity;
   8.613 +            (*_next_rep)[(*_nodes)[n].last_rep] = m;
   8.614 +            (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
   8.615 +            
   8.616 +            if ((*_nodes)[m].prev != INVALID) {
   8.617 +              (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
   8.618 +            } else{
   8.619 +              _first_node = (*_nodes)[m].next;
   8.620 +            }
   8.621 +            if ((*_nodes)[m].next != INVALID) {
   8.622 +              (*_nodes)[(*_nodes)[m].next].prev = (*_nodes)[m].prev;
   8.623 +            }
   8.624 +            --_node_num;
   8.625 +          }
   8.626 +        }
   8.627 +      }
   8.628 +
   8.629 +      if (_node_num == 1) {
   8.630 +        _first_node = INVALID;
   8.631 +        return true;
   8.632 +      }
   8.633 +
   8.634 +      return false;
   8.635 +    }
   8.636 +
   8.637 +    /// \brief Executes the algorithm.
   8.638 +    ///
   8.639 +    /// Executes the algorithm.
   8.640 +    ///
   8.641 +    /// \pre init() must be called
   8.642 +    void start() {
   8.643 +      while (!processNextPhase()) {}
   8.644 +    }
   8.645 +
   8.646 +
   8.647 +    /// \brief Runs %NagamochiIbaraki algorithm.
   8.648 +    ///
   8.649 +    /// This method runs the %Min cut algorithm
   8.650 +    ///
   8.651 +    /// \note mc.run(s) is just a shortcut of the following code.
   8.652 +    ///\code
   8.653 +    ///  mc.init();
   8.654 +    ///  mc.start();
   8.655 +    ///\endcode
   8.656 +    void run() {
   8.657 +      init();
   8.658 +      start();
   8.659 +    }
   8.660 +
   8.661 +    ///@}
   8.662 +
   8.663 +    /// \name Query Functions
   8.664 +    ///
   8.665 +    /// The result of the %NagamochiIbaraki
   8.666 +    /// algorithm can be obtained using these functions.\n
   8.667 +    /// Before the use of these functions, either run() or start()
   8.668 +    /// must be called.
   8.669 +
   8.670 +    ///@{
   8.671 +
   8.672 +    /// \brief Returns the min cut value.
   8.673 +    ///
   8.674 +    /// Returns the min cut value if the algorithm finished.
   8.675 +    /// After the first processNextPhase() it is a value of a
   8.676 +    /// valid cut in the graph.
   8.677 +    Value minCutValue() const {
   8.678 +      return _min_cut;
   8.679 +    }
   8.680 +
   8.681 +    /// \brief Returns a min cut in a NodeMap.
   8.682 +    ///
   8.683 +    /// It sets the nodes of one of the two partitions to true and
   8.684 +    /// the other partition to false.
   8.685 +    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   8.686 +    /// \c bool (or convertible) value type.
   8.687 +    template <typename CutMap>
   8.688 +    Value minCutMap(CutMap& cutMap) const {
   8.689 +      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   8.690 +        cutMap.set(n, (*_cut_map)[n]);
   8.691 +      }
   8.692 +      return minCutValue();
   8.693 +    }
   8.694 +
   8.695 +    ///@}
   8.696 +
   8.697 +  };
   8.698 +}
   8.699 +
   8.700 +#endif
     9.1 --- a/test/CMakeLists.txt	Mon Nov 15 22:23:35 2010 +0100
     9.2 +++ b/test/CMakeLists.txt	Tue Nov 16 07:46:01 2010 +0100
     9.3 @@ -36,6 +36,7 @@
     9.4    min_cost_arborescence_test
     9.5    min_cost_flow_test
     9.6    min_mean_cycle_test
     9.7 +  nagamochi_ibaraki_test
     9.8    path_test
     9.9    planarity_test
    9.10    preflow_test
    9.11 @@ -47,7 +48,12 @@
    9.12  )
    9.13  
    9.14  IF(LEMON_HAVE_LP)
    9.15 -  ADD_EXECUTABLE(lp_test lp_test.cc)
    9.16 +  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
    9.17 +    ADD_EXECUTABLE(lp_test lp_test.cc)
    9.18 +  ELSE()
    9.19 +    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
    9.20 +  ENDIF()
    9.21 +
    9.22    SET(LP_TEST_LIBS lemon)
    9.23  
    9.24    IF(LEMON_HAVE_GLPK)
    9.25 @@ -83,7 +89,12 @@
    9.26  ENDIF()
    9.27  
    9.28  IF(LEMON_HAVE_MIP)
    9.29 -  ADD_EXECUTABLE(mip_test mip_test.cc)
    9.30 +  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
    9.31 +    ADD_EXECUTABLE(mip_test mip_test.cc)
    9.32 +  ELSE()
    9.33 +    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
    9.34 +  ENDIF()
    9.35 +
    9.36    SET(MIP_TEST_LIBS lemon)
    9.37  
    9.38    IF(LEMON_HAVE_GLPK)
    10.1 --- a/test/Makefile.am	Mon Nov 15 22:23:35 2010 +0100
    10.2 +++ b/test/Makefile.am	Tue Nov 16 07:46:01 2010 +0100
    10.3 @@ -38,6 +38,7 @@
    10.4  	test/min_cost_arborescence_test \
    10.5  	test/min_cost_flow_test \
    10.6  	test/min_mean_cycle_test \
    10.7 +	test/nagamochi_ibaraki_test \
    10.8  	test/path_test \
    10.9  	test/planarity_test \
   10.10  	test/preflow_test \
   10.11 @@ -91,6 +92,7 @@
   10.12  test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
   10.13  test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
   10.14  test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
   10.15 +test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc
   10.16  test_path_test_SOURCES = test/path_test.cc
   10.17  test_planarity_test_SOURCES = test/planarity_test.cc
   10.18  test_preflow_test_SOURCES = test/preflow_test.cc
    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/test/nagamochi_ibaraki_test.cc	Tue Nov 16 07:46:01 2010 +0100
    11.3 @@ -0,0 +1,141 @@
    11.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
    11.5 + *
    11.6 + * This file is a part of LEMON, a generic C++ optimization library.
    11.7 + *
    11.8 + * Copyright (C) 2003-2010
    11.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   11.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
   11.11 + *
   11.12 + * Permission to use, modify and distribute this software is granted
   11.13 + * provided that this copyright notice appears in all copies. For
   11.14 + * precise terms see the accompanying LICENSE file.
   11.15 + *
   11.16 + * This software is provided "AS IS" with no warranty of any kind,
   11.17 + * express or implied, and with no claim as to its suitability for any
   11.18 + * purpose.
   11.19 + *
   11.20 + */
   11.21 +
   11.22 +#include <sstream>
   11.23 +
   11.24 +#include <lemon/smart_graph.h>
   11.25 +#include <lemon/adaptors.h>
   11.26 +#include <lemon/concepts/graph.h>
   11.27 +#include <lemon/concepts/maps.h>
   11.28 +#include <lemon/lgf_reader.h>
   11.29 +#include <lemon/nagamochi_ibaraki.h>
   11.30 +
   11.31 +#include "test_tools.h"
   11.32 +
   11.33 +using namespace lemon;
   11.34 +using namespace std;
   11.35 +
   11.36 +const std::string lgf =
   11.37 +  "@nodes\n"
   11.38 +  "label\n"
   11.39 +  "0\n"
   11.40 +  "1\n"
   11.41 +  "2\n"
   11.42 +  "3\n"
   11.43 +  "4\n"
   11.44 +  "5\n"
   11.45 +  "@edges\n"
   11.46 +  "     cap1 cap2 cap3\n"
   11.47 +  "0 1  1    1    1   \n"
   11.48 +  "0 2  2    2    4   \n"
   11.49 +  "1 2  4    4    4   \n"
   11.50 +  "3 4  1    1    1   \n"
   11.51 +  "3 5  2    2    4   \n"
   11.52 +  "4 5  4    4    4   \n"
   11.53 +  "2 3  1    6    6   \n";
   11.54 +
   11.55 +void checkNagamochiIbarakiCompile()
   11.56 +{
   11.57 +  typedef int Value;
   11.58 +  typedef concepts::Graph Graph;
   11.59 +
   11.60 +  typedef Graph::Node Node;
   11.61 +  typedef Graph::Edge Edge;
   11.62 +  typedef concepts::ReadMap<Edge, Value> CapMap;
   11.63 +  typedef concepts::WriteMap<Node, bool> CutMap;
   11.64 +
   11.65 +  Graph g;
   11.66 +  Node n;
   11.67 +  CapMap cap;
   11.68 +  CutMap cut;
   11.69 +  Value v;
   11.70 +  bool b;
   11.71 +
   11.72 +  NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
   11.73 +  const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
   11.74 +
   11.75 +  ni_test.init();
   11.76 +  ni_test.start();
   11.77 +  b = ni_test.processNextPhase();
   11.78 +  ni_test.run();
   11.79 +
   11.80 +  v = const_ni_test.minCutValue();
   11.81 +  v = const_ni_test.minCutMap(cut);
   11.82 +}
   11.83 +
   11.84 +template <typename Graph, typename CapMap, typename CutMap>
   11.85 +typename CapMap::Value
   11.86 +  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
   11.87 +{
   11.88 +  typename CapMap::Value sum = 0;
   11.89 +  for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
   11.90 +    if (cut[graph.u(e)] != cut[graph.v(e)]) {
   11.91 +      sum += cap[e];
   11.92 +    }
   11.93 +  }
   11.94 +  return sum;
   11.95 +}
   11.96 +
   11.97 +int main() {
   11.98 +  SmartGraph graph;
   11.99 +  SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
  11.100 +  SmartGraph::NodeMap<bool> cut(graph);
  11.101 +
  11.102 +  istringstream input(lgf);
  11.103 +  graphReader(graph, input)
  11.104 +    .edgeMap("cap1", cap1)
  11.105 +    .edgeMap("cap2", cap2)
  11.106 +    .edgeMap("cap3", cap3)
  11.107 +    .run();
  11.108 +
  11.109 +  {
  11.110 +    NagamochiIbaraki<SmartGraph> ni(graph, cap1);
  11.111 +    ni.run();
  11.112 +    ni.minCutMap(cut);
  11.113 +
  11.114 +    check(ni.minCutValue() == 1, "Wrong cut value");
  11.115 +    check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
  11.116 +  }
  11.117 +  {
  11.118 +    NagamochiIbaraki<SmartGraph> ni(graph, cap2);
  11.119 +    ni.run();
  11.120 +    ni.minCutMap(cut);
  11.121 +
  11.122 +    check(ni.minCutValue() == 3, "Wrong cut value");
  11.123 +    check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
  11.124 +  }
  11.125 +  {
  11.126 +    NagamochiIbaraki<SmartGraph> ni(graph, cap3);
  11.127 +    ni.run();
  11.128 +    ni.minCutMap(cut);
  11.129 +
  11.130 +    check(ni.minCutValue() == 5, "Wrong cut value");
  11.131 +    check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
  11.132 +  }
  11.133 +  {
  11.134 +    NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
  11.135 +    ni.run();
  11.136 +    ni.minCutMap(cut);
  11.137 +
  11.138 +    ConstMap<SmartGraph::Edge, int> cap4(1);
  11.139 +    check(ni.minCutValue() == 1, "Wrong cut value");
  11.140 +    check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
  11.141 +  }
  11.142 +
  11.143 +  return 0;
  11.144 +}