Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt	(revision 1016)
+++ CMakeLists.txt	(revision 997)
@@ -5,5 +5,4 @@
 
 INCLUDE(FindPythonInterp)
-INCLUDE(FindWget)
 
 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt	(revision 1016)
+++ doc/CMakeLists.txt	(revision 943)
@@ -3,6 +3,4 @@
 SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
-
-SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
 
 CONFIGURE_FILE(
@@ -55,14 +53,2 @@
 
 ENDIF()
-
-IF(WGET_FOUND)
-ADD_CUSTOM_TARGET(update-external-tags
-  COMMAND ${CMAKE_COMMAND} -E make_directory dl
-  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
-  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
-  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
-  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
-  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
-  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
-  )
-ENDIF()
Index: doc/Doxyfile.in
===================================================================
--- doc/Doxyfile.in	(revision 1016)
+++ doc/Doxyfile.in	(revision 803)
@@ -71,5 +71,5 @@
 SHOW_NAMESPACES        = YES
 FILE_VERSION_FILTER    = 
-LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
+LAYOUT_FILE            = DoxygenLayout.xml
 #---------------------------------------------------------------------------
 # configuration options related to warning and progress messages
@@ -115,5 +115,5 @@
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
-SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
+SOURCE_BROWSER         = NO
 INLINE_SOURCES         = NO
 STRIP_CODE_COMMENTS    = YES
@@ -226,5 +226,5 @@
 # Options related to the search engine   
 #---------------------------------------------------------------------------
-TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 GENERATE_TAGFILE       = html/lemon.tag
 ALLEXTERNALS           = NO
Index: lemon/CMakeLists.txt
===================================================================
--- lemon/CMakeLists.txt	(revision 1012)
+++ lemon/CMakeLists.txt	(revision 726)
@@ -7,10 +7,4 @@
   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
   ${CMAKE_CURRENT_BINARY_DIR}/config.h
-)
-
-CONFIGURE_FILE(
-  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
-  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
-  @ONLY
 )
 
@@ -73,8 +67,2 @@
   COMPONENT headers
 )
-
-INSTALL(
-  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
-  DESTINATION lib/pkgconfig
-)
-
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 1017)
+++ lemon/Makefile.am	(revision 1020)
@@ -108,5 +108,5 @@
 	lemon/math.h \
 	lemon/min_cost_arborescence.h \
-	lemon/nagamochi_ibaraki.h \
+	lemon/max_cardinality_search.h \
 	lemon/nauty_reader.h \
 	lemon/network_simplex.h \
Index: lemon/hao_orlin.h
===================================================================
--- lemon/hao_orlin.h	(revision 1019)
+++ lemon/hao_orlin.h	(revision 956)
@@ -54,6 +54,6 @@
   /// preflow push-relabel algorithm. Our implementation calculates
   /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
-  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
-  /// use of this algorithm is testing network reliability.
+  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
+  /// purpose of such algorithm is e.g. testing network reliability.
   ///
   /// For an undirected graph you can run just the first phase of the
@@ -913,6 +913,4 @@
     /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
     /// \f$ source \in X \f$ and minimal outgoing capacity).
-    /// It updates the stored cut if (and only if) the newly found one
-    /// is better.
     ///
     /// \pre \ref init() must be called before using this function.
@@ -927,6 +925,4 @@
     /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
     /// \f$ source \notin X \f$ and minimal outgoing capacity).
-    /// It updates the stored cut if (and only if) the newly found one
-    /// is better.
     ///
     /// \pre \ref init() must be called before using this function.
@@ -938,6 +934,6 @@
     /// \brief Run the algorithm.
     ///
-    /// This function runs the algorithm. It chooses source node,
-    /// then calls \ref init(), \ref calculateOut()
+    /// This function runs the algorithm. It finds nodes \c source and
+    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
     /// and \ref calculateIn().
     void run() {
@@ -949,7 +945,7 @@
     /// \brief Run the algorithm.
     ///
-    /// This function runs the algorithm. It calls \ref init(),
-    /// \ref calculateOut() and \ref calculateIn() with the given
-    /// source node.
+    /// This function runs the algorithm. It uses the given \c source node,
+    /// finds a proper \c target node and then calls the \ref init(),
+    /// \ref calculateOut() and \ref calculateIn().
     void run(const Node& s) {
       init(s);
@@ -970,7 +966,5 @@
     /// \brief Return the value of the minimum cut.
     ///
-    /// This function returns the value of the best cut found by the
-    /// previously called \ref run(), \ref calculateOut() or \ref
-    /// calculateIn().
+    /// This function returns the value of the minimum cut.
     ///
     /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
@@ -983,11 +977,7 @@
     /// \brief Return a minimum cut.
     ///
-    /// This function gives the best cut found by the
-    /// previously called \ref run(), \ref calculateOut() or \ref
-    /// calculateIn().
-    ///
-    /// It sets \c cutMap to the characteristic vector of the found
-    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
-    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
+    /// This function sets \c cutMap to the characteristic vector of a
+    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
+    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
     /// for the nodes of \f$ X \f$).
     ///
Index: mon/lemon.pc.cmake
===================================================================
--- lemon/lemon.pc.cmake	(revision 1012)
+++ 	(revision )
@@ -1,10 +1,0 @@
-prefix=@CMAKE_INSTALL_PREFIX@
-exec_prefix=@CMAKE_INSTALL_PREFIX@/bin
-libdir=@CMAKE_INSTALL_PREFIX@/lib
-includedir=@CMAKE_INSTALL_PREFIX@/include
-
-Name: @PROJECT_NAME@
-Description: Library for Efficient Modeling and Optimization in Networks
-Version: @PROJECT_VERSION@
-Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
-Cflags: -I${includedir}
Index: lemon/max_cardinality_search.h
===================================================================
--- lemon/max_cardinality_search.h	(revision 1020)
+++ lemon/max_cardinality_search.h	(revision 1020)
@@ -0,0 +1,786 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_MAX_CARDINALITY_SEARCH_H
+#define LEMON_MAX_CARDINALITY_SEARCH_H
+
+
+/// \ingroup search
+/// \file 
+/// \brief Maximum cardinality search in undirected digraphs.
+
+#include <lemon/bin_heap.h>
+#include <lemon/bucket_heap.h>
+
+#include <lemon/error.h>
+#include <lemon/maps.h>
+
+#include <functional>
+
+namespace lemon {
+
+  /// \brief Default traits class of MaxCardinalitySearch class.
+  ///
+  /// Default traits class of MaxCardinalitySearch class.
+  /// \param Digraph Digraph type.
+  /// \param CapacityMap Type of capacity map.
+  template <typename GR, typename CAP>
+  struct MaxCardinalitySearchDefaultTraits {
+    /// The digraph type the algorithm runs on. 
+    typedef GR Digraph;
+
+    template <typename CM>
+    struct CapMapSelector {
+
+      typedef CM CapacityMap;
+
+      static CapacityMap *createCapacityMap(const Digraph& g) {
+	return new CapacityMap(g);
+      }
+    };
+
+    template <typename CM>
+    struct CapMapSelector<ConstMap<CM, Const<int, 1> > > {
+
+      typedef ConstMap<CM, Const<int, 1> > CapacityMap;
+
+      static CapacityMap *createCapacityMap(const Digraph&) {
+	return new CapacityMap;
+      }
+    };
+
+    /// \brief The type of the map that stores the arc capacities.
+    ///
+    /// The type of the map that stores the arc capacities.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    typedef typename CapMapSelector<CAP>::CapacityMap CapacityMap;
+
+    /// \brief The type of the capacity of the arcs.
+    typedef typename CapacityMap::Value Value;
+
+    /// \brief Instantiates a CapacityMap.
+    ///
+    /// This function instantiates a \ref CapacityMap.
+    /// \param digraph is the digraph, to which we would like to define
+    /// the CapacityMap.
+    static CapacityMap *createCapacityMap(const Digraph& digraph) {
+      return CapMapSelector<CapacityMap>::createCapacityMap(digraph);
+    }
+
+    /// \brief The cross reference type used by heap.
+    ///
+    /// The cross reference type used by heap.
+    /// Usually it is \c Digraph::NodeMap<int>.
+    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
+
+    /// \brief Instantiates a HeapCrossRef.
+    ///
+    /// This function instantiates a \ref HeapCrossRef. 
+    /// \param digraph is the digraph, to which we would like to define the 
+    /// HeapCrossRef.
+    static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
+      return new HeapCrossRef(digraph);
+    }
+    
+    template <typename CapacityMap>
+    struct HeapSelector {
+      template <typename Value, typename Ref>
+      struct Selector { 
+        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
+      };
+    };
+
+    template <typename CapacityKey>
+    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
+      template <typename Value, typename Ref>
+      struct Selector {
+        typedef BucketHeap<Ref, false > Heap;
+      };
+    };
+
+    /// \brief The heap type used by MaxCardinalitySearch algorithm.
+    ///
+    /// The heap type used by MaxCardinalitySearch algorithm. It should
+    /// maximalize the priorities. The default heap type is
+    /// the \ref BinHeap, but it is specialized when the
+    /// CapacityMap is ConstMap<Digraph::Node, Const<int, 1> >
+    /// to BucketHeap.
+    ///
+    /// \sa MaxCardinalitySearch
+    typedef typename HeapSelector<CapacityMap>
+    ::template Selector<Value, HeapCrossRef>
+    ::Heap Heap;
+
+    /// \brief Instantiates a Heap.
+    ///
+    /// This function instantiates a \ref Heap. 
+    /// \param crossref The cross reference of the heap.
+    static Heap *createHeap(HeapCrossRef& crossref) {
+      return new Heap(crossref);
+    }
+
+    /// \brief The type of the map that stores whether a node is processed.
+    ///
+    /// The type of the map that stores whether a node is processed.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    /// By default it is a NullMap.
+    typedef NullMap<typename Digraph::Node, bool> ProcessedMap;
+
+    /// \brief Instantiates a ProcessedMap.
+    ///
+    /// This function instantiates a \ref ProcessedMap. 
+    /// \param digraph is the digraph, to which
+    /// we would like to define the \ref ProcessedMap
+#ifdef DOXYGEN
+    static ProcessedMap *createProcessedMap(const Digraph &digraph)
+#else
+    static ProcessedMap *createProcessedMap(const Digraph &)
+#endif
+    {
+      return new ProcessedMap();
+    }
+
+    /// \brief The type of the map that stores the cardinalities of the nodes.
+    /// 
+    /// The type of the map that stores the cardinalities of the nodes.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    typedef typename Digraph::template NodeMap<Value> CardinalityMap;
+
+    /// \brief Instantiates a CardinalityMap.
+    ///
+    /// This function instantiates a \ref CardinalityMap. 
+    /// \param digraph is the digraph, to which we would like to define the \ref 
+    /// CardinalityMap
+    static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
+      return new CardinalityMap(digraph);
+    }
+
+
+  };
+  
+  /// \ingroup search
+  ///
+  /// \brief Maximum Cardinality Search algorithm class.
+  ///
+  /// This class provides an efficient implementation of Maximum Cardinality 
+  /// Search algorithm. The maximum cardinality search first chooses any 
+  /// node of the digraph. Then every time it chooses one unprocessed node
+  /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
+  /// which were previusly processed.
+  /// If there is a cut in the digraph the algorithm should choose
+  /// again any unprocessed node of the digraph.
+
+  /// The arc capacities are passed to the algorithm using a
+  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
+  /// kind of capacity.
+  ///
+  /// The type of the capacity is determined by the \ref 
+  /// concepts::ReadMap::Value "Value" of the capacity map.
+  ///
+  /// It is also possible to change the underlying priority heap.
+  ///
+  ///
+  /// \param GR The digraph type the algorithm runs on. The value of
+  /// Digraph is not used directly by the search algorithm, it 
+  /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
+  /// \param CAP This read-only ArcMap determines the capacities of 
+  /// the arcs. It is read once for each arc, so the map may involve in
+  /// relatively time consuming process to compute the arc capacity if
+  /// it is necessary. The default map type is \ref
+  /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
+  /// of CapacityMap is not used directly by search algorithm, it is only 
+  /// passed to \ref MaxCardinalitySearchDefaultTraits.  
+  /// \param TR Traits class to set various data types used by the 
+  /// algorithm.  The default traits class is 
+  /// \ref MaxCardinalitySearchDefaultTraits 
+  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".  
+  /// See \ref MaxCardinalitySearchDefaultTraits 
+  /// for the documentation of a MaxCardinalitySearch traits class.
+
+#ifdef DOXYGEN
+  template <typename GR, typename CAP, typename TR>
+#else
+  template <typename GR, typename CAP = 
+	    ConstMap<typename GR::Arc, Const<int,1> >,
+	    typename TR = 
+            MaxCardinalitySearchDefaultTraits<GR, CAP> >
+#endif
+  class MaxCardinalitySearch {
+  public:
+
+    typedef TR Traits;
+    ///The type of the underlying digraph.
+    typedef typename Traits::Digraph Digraph;
+    
+    ///The type of the capacity of the arcs.
+    typedef typename Traits::CapacityMap::Value Value;
+    ///The type of the map that stores the arc capacities.
+    typedef typename Traits::CapacityMap CapacityMap;
+    ///The type of the map indicating if a node is processed.
+    typedef typename Traits::ProcessedMap ProcessedMap;
+    ///The type of the map that stores the cardinalities of the nodes.
+    typedef typename Traits::CardinalityMap CardinalityMap;
+    ///The cross reference type used for the current heap.
+    typedef typename Traits::HeapCrossRef HeapCrossRef;
+    ///The heap type used by the algorithm. It maximizes the priorities.
+    typedef typename Traits::Heap Heap;
+  private:
+    // Pointer to the underlying digraph.
+    const Digraph *_graph;
+    // Pointer to the capacity map
+    const CapacityMap *_capacity;
+    // Indicates if \ref _capacity is locally allocated (\c true) or not.
+    bool local_capacity;
+    // Pointer to the map of cardinality.
+    CardinalityMap *_cardinality;
+    // Indicates if \ref _cardinality is locally allocated (\c true) or not.
+    bool local_cardinality;
+    // Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    // Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+    // Pointer to the heap cross references.
+    HeapCrossRef *_heap_cross_ref;
+    // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
+    bool local_heap_cross_ref;
+    // Pointer to the heap.
+    Heap *_heap;
+    // Indicates if \ref _heap is locally allocated (\c true) or not.
+    bool local_heap;
+
+  public :
+
+    typedef MaxCardinalitySearch Create;
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefCapacityMapTraits : public Traits {
+      typedef T CapacityMap;
+      static CapacityMap *createCapacityMap(const Digraph &) {
+       	LEMON_ASSERT(false,"Uninitialized parameter.");
+	return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// CapacityMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting CapacityMap type
+    /// for the algorithm.
+    template <class T>
+    struct SetCapacityMap 
+      : public MaxCardinalitySearch<Digraph, CapacityMap, 
+                                    DefCapacityMapTraits<T> > { 
+      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+                                   DefCapacityMapTraits<T> > Create;
+    };
+
+    template <class T>
+    struct DefCardinalityMapTraits : public Traits {
+      typedef T CardinalityMap;
+      static CardinalityMap *createCardinalityMap(const Digraph &) 
+      {
+	LEMON_ASSERT(false,"Uninitialized parameter.");
+	return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// CardinalityMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
+    /// type for the algorithm.
+    template <class T>
+    struct SetCardinalityMap 
+      : public MaxCardinalitySearch<Digraph, CapacityMap, 
+                                    DefCardinalityMapTraits<T> > { 
+      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+                                   DefCardinalityMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Digraph &) {
+       	LEMON_ASSERT(false,"Uninitialized parameter.");
+	return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// ProcessedMap type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
+    /// for the algorithm.
+    template <class T>
+    struct SetProcessedMap 
+      : public MaxCardinalitySearch<Digraph, CapacityMap, 
+                                    DefProcessedMapTraits<T> > { 
+      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+                                   DefProcessedMapTraits<T> > Create;
+    };
+    
+    template <class H, class CR>
+    struct DefHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
+     	LEMON_ASSERT(false,"Uninitialized parameter.");
+	return 0;
+      }
+      static Heap *createHeap(HeapCrossRef &) {
+       	LEMON_ASSERT(false,"Uninitialized parameter.");
+	return 0;
+      }
+    };
+    /// \brief \ref named-templ-param "Named parameter" for setting heap 
+    /// and cross reference type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting heap and cross 
+    /// reference type for the algorithm.
+    template <class H, class CR = typename Digraph::template NodeMap<int> >
+    struct SetHeap
+      : public MaxCardinalitySearch<Digraph, CapacityMap, 
+                                    DefHeapTraits<H, CR> > { 
+      typedef MaxCardinalitySearch< Digraph, CapacityMap, 
+                                    DefHeapTraits<H, CR> > Create;
+    };
+
+    template <class H, class CR>
+    struct DefStandardHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
+	return new HeapCrossRef(digraph);
+      }
+      static Heap *createHeap(HeapCrossRef &crossref) {
+	return new Heap(crossref);
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
+    /// cross reference type with automatic allocation
+    ///
+    /// \ref named-templ-param "Named parameter" for setting heap and cross 
+    /// reference type. It can allocate the heap and the cross reference 
+    /// object if the cross reference's constructor waits for the digraph as 
+    /// parameter and the heap's constructor waits for the cross reference.
+    template <class H, class CR = typename Digraph::template NodeMap<int> >
+    struct SetStandardHeap
+      : public MaxCardinalitySearch<Digraph, CapacityMap, 
+                                    DefStandardHeapTraits<H, CR> > { 
+      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
+                                   DefStandardHeapTraits<H, CR> > 
+      Create;
+    };
+    
+    ///@}
+
+
+  protected:
+
+    MaxCardinalitySearch() {}
+
+  public:      
+    
+    /// \brief Constructor.
+    ///
+    ///\param digraph the digraph the algorithm will run on.
+    ///\param capacity the capacity map used by the algorithm.
+    ///When no capacity map given, a constant 1 capacity map will
+    ///be allocated.
+#ifdef DOXYGEN
+    MaxCardinalitySearch(const Digraph& digraph,
+			 const CapacityMap& capacity=0 ) :
+#else
+    MaxCardinalitySearch(const Digraph& digraph,
+			 const CapacityMap& capacity=*static_cast<const CapacityMap*>(0) ) :
+#endif
+      _graph(&digraph),
+      _capacity(&capacity), local_capacity(false),
+      _cardinality(0), local_cardinality(false),
+      _processed(0), local_processed(false),
+      _heap_cross_ref(0), local_heap_cross_ref(false),
+      _heap(0), local_heap(false)
+    { }
+
+    /// \brief Destructor.
+    ~MaxCardinalitySearch() {
+      if(local_capacity) delete _capacity;
+      if(local_cardinality) delete _cardinality;
+      if(local_processed) delete _processed;
+      if(local_heap_cross_ref) delete _heap_cross_ref;
+      if(local_heap) delete _heap;
+    }
+
+    /// \brief Sets the capacity map.
+    ///
+    /// Sets the capacity map.
+    /// \return <tt> (*this) </tt>
+    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
+      if (local_capacity) {
+	delete _capacity;
+	local_capacity=false;
+      }
+      _capacity=&m;
+      return *this;
+    }
+
+    /// \brief Returns a const reference to the capacity map.
+    ///
+    /// Returns a const reference to the capacity map used by
+    /// the algorithm.
+    const CapacityMap &capacityMap() const {
+      return *_capacity;
+    }
+
+    /// \brief Sets the map storing the cardinalities calculated by the 
+    /// algorithm.
+    ///
+    /// Sets the map storing the cardinalities calculated by the algorithm.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return <tt> (*this) </tt>
+    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
+      if(local_cardinality) {
+	delete _cardinality;
+	local_cardinality=false;
+      }
+      _cardinality = &m;
+      return *this;
+    }
+
+    /// \brief Sets the map storing the processed nodes.
+    ///
+    /// Sets the map storing the processed nodes.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return <tt> (*this) </tt>
+    MaxCardinalitySearch &processedMap(ProcessedMap &m) 
+    {
+      if(local_processed) {
+	delete _processed;
+	local_processed=false;
+      }
+      _processed = &m;
+      return *this;
+    }
+
+    /// \brief Returns a const reference to the cardinality map.
+    ///
+    /// Returns a const reference to the cardinality map used by
+    /// the algorithm.
+    const ProcessedMap &processedMap() const {
+      return *_processed;
+    }
+
+    /// \brief Sets the heap and the cross reference used by algorithm.
+    ///
+    /// Sets the heap and the cross reference used by algorithm.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return <tt> (*this) </tt>
+    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
+      if(local_heap_cross_ref) {
+	delete _heap_cross_ref;
+	local_heap_cross_ref = false;
+      }
+      _heap_cross_ref = &cr;
+      if(local_heap) {
+	delete _heap;
+	local_heap = false;
+      }
+      _heap = &hp;
+      return *this;
+    }
+
+    /// \brief Returns a const reference to the heap.
+    ///
+    /// Returns a const reference to the heap used by
+    /// the algorithm.
+    const Heap &heap() const {
+      return *_heap;
+    }
+
+    /// \brief Returns a const reference to the cross reference.
+    ///
+    /// Returns a const reference to the cross reference
+    /// of the heap.
+    const HeapCrossRef &heapCrossRef() const {
+      return *_heap_cross_ref;
+    }
+
+  private:
+
+    typedef typename Digraph::Node Node;
+    typedef typename Digraph::NodeIt NodeIt;
+    typedef typename Digraph::Arc Arc;
+    typedef typename Digraph::InArcIt InArcIt;
+
+    void create_maps() {
+      if(!_capacity) {
+	local_capacity = true;
+	_capacity = Traits::createCapacityMap(*_graph);
+      }
+      if(!_cardinality) {
+	local_cardinality = true;
+	_cardinality = Traits::createCardinalityMap(*_graph);
+      }
+      if(!_processed) {
+	local_processed = true;
+	_processed = Traits::createProcessedMap(*_graph);
+      }
+      if (!_heap_cross_ref) {
+	local_heap_cross_ref = true;
+	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
+      }
+      if (!_heap) {
+	local_heap = true;
+	_heap = Traits::createHeap(*_heap_cross_ref);
+      }
+    }
+    
+    void finalizeNodeData(Node node, Value capacity) {
+      _processed->set(node, true);
+      _cardinality->set(node, capacity);
+    }
+
+  public:
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \ref run().
+    /// \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then you can add several source nodes
+    /// with \ref addSource().
+    /// Finally \ref start() will perform the computation.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    ///
+    /// Initializes the internal data structures, and clears the heap.
+    void init() {
+      create_maps();
+      _heap->clear();
+      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
+	_processed->set(it, false);
+	_heap_cross_ref->set(it, Heap::PRE_HEAP);
+      }
+    }
+    
+    /// \brief Adds a new source node.
+    /// 
+    /// Adds a new source node to the priority heap.
+    ///
+    /// It checks if the node has not yet been added to the heap.
+    void addSource(Node source, Value capacity = 0) {
+      if(_heap->state(source) == Heap::PRE_HEAP) {
+	_heap->push(source, capacity);
+      } 
+    }
+    
+    /// \brief Processes the next node in the priority heap
+    ///
+    /// Processes the next node in the priority heap.
+    ///
+    /// \return The processed node.
+    ///
+    /// \warning The priority heap must not be empty!
+    Node processNextNode() {
+      Node node = _heap->top(); 
+      finalizeNodeData(node, _heap->prio());
+      _heap->pop();
+      
+      for (InArcIt it(*_graph, node); it != INVALID; ++it) {
+	Node source = _graph->source(it);
+	switch (_heap->state(source)) {
+	case Heap::PRE_HEAP:
+	  _heap->push(source, (*_capacity)[it]);
+	  break;
+	case Heap::IN_HEAP:
+	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
+	  break;
+	case Heap::POST_HEAP:
+	  break;
+	}
+      }
+      return node;
+    }
+
+    /// \brief Next node to be processed.
+    ///
+    /// Next node to be processed.
+    ///
+    /// \return The next node to be processed or INVALID if the 
+    /// priority heap is empty.
+    Node nextNode() { 
+      return !_heap->empty() ? _heap->top() : INVALID;
+    }
+ 
+    /// \brief Returns \c false if there are nodes
+    /// to be processed in the priority heap
+    ///
+    /// Returns \c false if there are nodes
+    /// to be processed in the priority heap
+    bool emptyQueue() { return _heap->empty(); }
+    /// \brief Returns the number of the nodes to be processed 
+    /// in the priority heap
+    ///
+    /// Returns the number of the nodes to be processed in the priority heap
+    int emptySize() { return _heap->size(); }
+    
+    /// \brief Executes the algorithm.
+    ///
+    /// Executes the algorithm.
+    ///
+    ///\pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// This method runs the Maximum Cardinality Search algorithm from the 
+    /// source node(s).
+    void start() {
+      while ( !_heap->empty() ) processNextNode();
+    }
+    
+    /// \brief Executes the algorithm until \c dest is reached.
+    ///
+    /// Executes the algorithm until \c dest is reached.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// This method runs the %MaxCardinalitySearch algorithm from the source 
+    /// nodes.
+    void start(Node dest) {
+      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
+      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
+    }
+    
+    /// \brief Executes the algorithm until a condition is met.
+    ///
+    /// Executes the algorithm until a condition is met.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// \param nm must be a bool (or convertible) node map. The algorithm
+    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    template <typename NodeBoolMap>
+    void start(const NodeBoolMap &nm) {
+      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
+      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
+    }
+    
+    /// \brief Runs the maximum cardinality search algorithm from node \c s.
+    ///
+    /// This method runs the %MaxCardinalitySearch algorithm from a root 
+    /// node \c s.
+    ///
+    ///\note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+
+    /// \brief Runs the maximum cardinality search algorithm for the 
+    /// whole digraph.
+    ///
+    /// This method runs the %MaxCardinalitySearch algorithm from all 
+    /// unprocessed node of the digraph.
+    ///
+    ///\note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
+    ///    if (!d.reached(it)) {
+    ///      d.addSource(s);
+    ///      d.start();
+    ///    }
+    ///  }
+    ///\endcode
+    void run() {
+      init();
+      for (NodeIt it(*_graph); it != INVALID; ++it) {
+        if (!reached(it)) {
+          addSource(it);
+          start();
+        }
+      }
+    }
+    
+    ///@}
+
+    /// \name Query Functions
+    /// The results of the maximum cardinality search algorithm can be 
+    /// obtained using these functions.
+    /// \n
+    /// Before the use of these functions, either run() or start() must be 
+    /// called.
+    
+    ///@{
+
+    /// \brief The cardinality of a node.
+    ///
+    /// Returns the cardinality of a node.
+    /// \pre \ref run() must be called before using this function.
+    /// \warning If node \c v in unreachable from the root the return value
+    /// of this funcion is undefined.
+    Value cardinality(Node node) const { return (*_cardinality)[node]; }
+
+    /// \brief The current cardinality of a node.
+    ///
+    /// Returns the current cardinality of a node.
+    /// \pre the given node should be reached but not processed
+    Value currentCardinality(Node node) const { return (*_heap)[node]; }
+
+    /// \brief Returns a reference to the NodeMap of cardinalities.
+    ///
+    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
+    /// must be called before using this function.
+    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
+ 
+    /// \brief Checks if a node is reachable from the root.
+    ///
+    /// Returns \c true if \c v is reachable from the root.
+    /// \warning The source nodes are initated as unreached.
+    /// \pre \ref run() must be called before using this function.
+    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
+
+    /// \brief Checks if a node is processed.
+    ///
+    /// Returns \c true if \c v is processed, i.e. the shortest
+    /// path to \c v has already found.
+    /// \pre \ref run() must be called before using this function.
+    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
+    
+    ///@}
+  };
+
+}
+
+#endif
Index: mon/nagamochi_ibaraki.h
===================================================================
--- lemon/nagamochi_ibaraki.h	(revision 1017)
+++ 	(revision )
@@ -1,697 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_NAGAMOCHI_IBARAKI_H
-#define LEMON_NAGAMOCHI_IBARAKI_H
-
-
-/// \ingroup min_cut
-/// \file
-/// \brief Implementation of the Nagamochi-Ibaraki algorithm.
-
-#include <lemon/core.h>
-#include <lemon/bin_heap.h>
-#include <lemon/bucket_heap.h>
-#include <lemon/maps.h>
-#include <lemon/radix_sort.h>
-#include <lemon/unionfind.h>
-
-#include <cassert>
-
-namespace lemon {
-
-  /// \brief Default traits class for NagamochiIbaraki class.
-  ///
-  /// Default traits class for NagamochiIbaraki class.
-  /// \param GR The undirected graph type.
-  /// \param CM Type of capacity map.
-  template <typename GR, typename CM>
-  struct NagamochiIbarakiDefaultTraits {
-    /// The type of the capacity map.
-    typedef typename CM::Value Value;
-
-    /// The undirected graph type the algorithm runs on.
-    typedef GR Graph;
-
-    /// \brief The type of the map that stores the edge capacities.
-    ///
-    /// The type of the map that stores the edge capacities.
-    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef CM CapacityMap;
-
-    /// \brief Instantiates a CapacityMap.
-    ///
-    /// This function instantiates a \ref CapacityMap.
-#ifdef DOXYGEN
-    static CapacityMap *createCapacityMap(const Graph& graph)
-#else
-    static CapacityMap *createCapacityMap(const Graph&)
-#endif
-    {
-        LEMON_ASSERT(false, "CapacityMap is not initialized");
-        return 0; // ignore warnings
-    }
-
-    /// \brief The cross reference type used by heap.
-    ///
-    /// The cross reference type used by heap.
-    /// Usually \c Graph::NodeMap<int>.
-    typedef typename Graph::template NodeMap<int> HeapCrossRef;
-
-    /// \brief Instantiates a HeapCrossRef.
-    ///
-    /// This function instantiates a \ref HeapCrossRef.
-    /// \param g is the graph, to which we would like to define the
-    /// \ref HeapCrossRef.
-    static HeapCrossRef *createHeapCrossRef(const Graph& g) {
-      return new HeapCrossRef(g);
-    }
-
-    /// \brief The heap type used by NagamochiIbaraki algorithm.
-    ///
-    /// The heap type used by NagamochiIbaraki algorithm. It has to
-    /// maximize the priorities.
-    ///
-    /// \sa BinHeap
-    /// \sa NagamochiIbaraki
-    typedef BinHeap<Value, HeapCrossRef, std::greater<Value> > Heap;
-
-    /// \brief Instantiates a Heap.
-    ///
-    /// This function instantiates a \ref Heap.
-    /// \param r is the cross reference of the heap.
-    static Heap *createHeap(HeapCrossRef& r) {
-      return new Heap(r);
-    }
-  };
-
-  /// \ingroup min_cut
-  ///
-  /// \brief Calculates the minimum cut in an undirected graph.
-  ///
-  /// Calculates the minimum cut in an undirected graph with the
-  /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
-  /// nodes into two partitions with the minimum sum of edge capacities
-  /// between the two partitions. The algorithm can be used to test
-  /// the network reliability, especially to test how many links have
-  /// to be destroyed in the network to split it to at least two
-  /// distinict subnetworks.
-  ///
-  /// The complexity of the algorithm is \f$ O(nm\log(n)) \f$ but with
-  /// \ref FibHeap "Fibonacci heap" it can be decreased to
-  /// \f$ O(nm+n^2\log(n)) \f$.  When the edges have unit capacities,
-  /// \c BucketHeap can be used which yields \f$ O(nm) \f$ time
-  /// complexity.
-  ///
-  /// \warning The value type of the capacity map should be able to
-  /// hold any cut value of the graph, otherwise the result can
-  /// overflow.
-  /// \note This capacity is supposed to be integer type.
-#ifdef DOXYGEN
-  template <typename GR, typename CM, typename TR>
-#else
-  template <typename GR,
-            typename CM = typename GR::template EdgeMap<int>,
-            typename TR = NagamochiIbarakiDefaultTraits<GR, CM> >
-#endif
-  class NagamochiIbaraki {
-  public:
-
-    typedef TR Traits;
-    /// The type of the underlying graph.
-    typedef typename Traits::Graph Graph;
-
-    /// The type of the capacity map.
-    typedef typename Traits::CapacityMap CapacityMap;
-    /// The value type of the capacity map.
-    typedef typename Traits::CapacityMap::Value Value;
-
-    /// The heap type used by the algorithm.
-    typedef typename Traits::Heap Heap;
-    /// The cross reference type used for the heap.
-    typedef typename Traits::HeapCrossRef HeapCrossRef;
-
-    ///\name Named template parameters
-
-    ///@{
-
-    struct SetUnitCapacityTraits : public Traits {
-      typedef ConstMap<typename Graph::Edge, Const<int, 1> > CapacityMap;
-      static CapacityMap *createCapacityMap(const Graph&) {
-        return new CapacityMap();
-      }
-    };
-
-    /// \brief \ref named-templ-param "Named parameter" for setting
-    /// the capacity map to a constMap<Edge, int, 1>() instance
-    ///
-    /// \ref named-templ-param "Named parameter" for setting
-    /// the capacity map to a constMap<Edge, int, 1>() instance
-    struct SetUnitCapacity
-      : public NagamochiIbaraki<Graph, CapacityMap,
-                                SetUnitCapacityTraits> {
-      typedef NagamochiIbaraki<Graph, CapacityMap,
-                               SetUnitCapacityTraits> Create;
-    };
-
-
-    template <class H, class CR>
-    struct SetHeapTraits : public Traits {
-      typedef CR HeapCrossRef;
-      typedef H Heap;
-      static HeapCrossRef *createHeapCrossRef(int num) {
-        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
-        return 0; // ignore warnings
-      }
-      static Heap *createHeap(HeapCrossRef &) {
-        LEMON_ASSERT(false, "Heap is not initialized");
-        return 0; // ignore warnings
-      }
-    };
-
-    /// \brief \ref named-templ-param "Named parameter" for setting
-    /// heap and cross reference type
-    ///
-    /// \ref named-templ-param "Named parameter" for setting heap and
-    /// cross reference type. The heap has to maximize the priorities.
-    template <class H, class CR = RangeMap<int> >
-    struct SetHeap
-      : public NagamochiIbaraki<Graph, CapacityMap, SetHeapTraits<H, CR> > {
-      typedef NagamochiIbaraki< Graph, CapacityMap, SetHeapTraits<H, CR> >
-      Create;
-    };
-
-    template <class H, class CR>
-    struct SetStandardHeapTraits : public Traits {
-      typedef CR HeapCrossRef;
-      typedef H Heap;
-      static HeapCrossRef *createHeapCrossRef(int size) {
-        return new HeapCrossRef(size);
-      }
-      static Heap *createHeap(HeapCrossRef &crossref) {
-        return new Heap(crossref);
-      }
-    };
-
-    /// \brief \ref named-templ-param "Named parameter" for setting
-    /// heap and cross reference type with automatic allocation
-    ///
-    /// \ref named-templ-param "Named parameter" for setting heap and
-    /// cross reference type with automatic allocation. They should
-    /// have standard constructor interfaces to be able to
-    /// automatically created by the algorithm (i.e. the graph should
-    /// be passed to the constructor of the cross reference and the
-    /// cross reference should be passed to the constructor of the
-    /// heap). However, external heap and cross reference objects
-    /// could also be passed to the algorithm using the \ref heap()
-    /// function before calling \ref run() or \ref init(). The heap
-    /// has to maximize the priorities.
-    /// \sa SetHeap
-    template <class H, class CR = RangeMap<int> >
-    struct SetStandardHeap
-      : public NagamochiIbaraki<Graph, CapacityMap,
-                                SetStandardHeapTraits<H, CR> > {
-      typedef NagamochiIbaraki<Graph, CapacityMap,
-                               SetStandardHeapTraits<H, CR> > Create;
-    };
-
-    ///@}
-
-
-  private:
-
-    const Graph &_graph;
-    const CapacityMap *_capacity;
-    bool _local_capacity; // unit capacity
-
-    struct ArcData {
-      typename Graph::Node target;
-      int prev, next;
-    };
-    struct EdgeData {
-      Value capacity;
-      Value cut;
-    };
-
-    struct NodeData {
-      int first_arc;
-      typename Graph::Node prev, next;
-      int curr_arc;
-      typename Graph::Node last_rep;
-      Value sum;
-    };
-
-    typename Graph::template NodeMap<NodeData> *_nodes;
-    std::vector<ArcData> _arcs;
-    std::vector<EdgeData> _edges;
-
-    typename Graph::Node _first_node;
-    int _node_num;
-
-    Value _min_cut;
-
-    HeapCrossRef *_heap_cross_ref;
-    bool _local_heap_cross_ref;
-    Heap *_heap;
-    bool _local_heap;
-
-    typedef typename Graph::template NodeMap<typename Graph::Node> NodeList;
-    NodeList *_next_rep;
-
-    typedef typename Graph::template NodeMap<bool> MinCutMap;
-    MinCutMap *_cut_map;
-
-    void createStructures() {
-      if (!_nodes) {
-        _nodes = new (typename Graph::template NodeMap<NodeData>)(_graph);
-      }
-      if (!_capacity) {
-        _local_capacity = true;
-        _capacity = Traits::createCapacityMap(_graph);
-      }
-      if (!_heap_cross_ref) {
-        _local_heap_cross_ref = true;
-        _heap_cross_ref = Traits::createHeapCrossRef(_graph);
-      }
-      if (!_heap) {
-        _local_heap = true;
-        _heap = Traits::createHeap(*_heap_cross_ref);
-      }
-      if (!_next_rep) {
-        _next_rep = new NodeList(_graph);
-      }
-      if (!_cut_map) {
-        _cut_map = new MinCutMap(_graph);
-      }
-    }
-
-  public :
-
-    typedef NagamochiIbaraki Create;
-
-
-    /// \brief Constructor.
-    ///
-    /// \param graph The graph the algorithm runs on.
-    /// \param capacity The capacity map used by the algorithm.
-    NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)
-      : _graph(graph), _capacity(&capacity), _local_capacity(false),
-        _nodes(0), _arcs(), _edges(), _min_cut(),
-        _heap_cross_ref(0), _local_heap_cross_ref(false),
-        _heap(0), _local_heap(false),
-        _next_rep(0), _cut_map(0) {}
-
-    /// \brief Constructor.
-    ///
-    /// This constructor can be used only when the Traits class
-    /// defines how can the local capacity map be instantiated.
-    /// If the SetUnitCapacity used the algorithm automatically
-    /// constructs the capacity map.
-    ///
-    ///\param graph The graph the algorithm runs on.
-    NagamochiIbaraki(const Graph& graph)
-      : _graph(graph), _capacity(0), _local_capacity(false),
-        _nodes(0), _arcs(), _edges(), _min_cut(),
-        _heap_cross_ref(0), _local_heap_cross_ref(false),
-        _heap(0), _local_heap(false),
-        _next_rep(0), _cut_map(0) {}
-
-    /// \brief Destructor.
-    ///
-    /// Destructor.
-    ~NagamochiIbaraki() {
-      if (_local_capacity) delete _capacity;
-      if (_nodes) delete _nodes;
-      if (_local_heap) delete _heap;
-      if (_local_heap_cross_ref) delete _heap_cross_ref;
-      if (_next_rep) delete _next_rep;
-      if (_cut_map) delete _cut_map;
-    }
-
-    /// \brief Sets the heap and the cross reference used by algorithm.
-    ///
-    /// Sets the heap and the cross reference used by algorithm.
-    /// If you don't use this function before calling \ref run(),
-    /// it will allocate one. The destuctor deallocates this
-    /// automatically allocated heap and cross reference, of course.
-    /// \return <tt> (*this) </tt>
-    NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)
-    {
-      if (_local_heap_cross_ref) {
-        delete _heap_cross_ref;
-        _local_heap_cross_ref = false;
-      }
-      _heap_cross_ref = &cr;
-      if (_local_heap) {
-        delete _heap;
-        _local_heap = false;
-      }
-      _heap = &hp;
-      return *this;
-    }
-
-    /// \name Execution control
-    /// The simplest way to execute the algorithm is to use
-    /// one of the member functions called \c run().
-    /// \n
-    /// If you need more control on the execution,
-    /// first you must call \ref init() and then call the start()
-    /// or proper times the processNextPhase() member functions.
-
-    ///@{
-
-    /// \brief Initializes the internal data structures.
-    ///
-    /// Initializes the internal data structures.
-    void init() {
-      createStructures();
-
-      int edge_num = countEdges(_graph);
-      _edges.resize(edge_num);
-      _arcs.resize(2 * edge_num);
-
-      typename Graph::Node prev = INVALID;
-      _node_num = 0;
-      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
-        (*_cut_map)[n] = false;
-        (*_next_rep)[n] = INVALID;
-        (*_nodes)[n].last_rep = n;
-        (*_nodes)[n].first_arc = -1;
-        (*_nodes)[n].curr_arc = -1;
-        (*_nodes)[n].prev = prev;
-        if (prev != INVALID) {
-          (*_nodes)[prev].next = n;
-        }
-        (*_nodes)[n].next = INVALID;
-        (*_nodes)[n].sum = 0;
-        prev = n;
-        ++_node_num;
-      }
-
-      _first_node = typename Graph::NodeIt(_graph);
-
-      int index = 0;
-      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
-        for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
-          typename Graph::Node m = _graph.target(a);
-          
-          if (!(n < m)) continue;
-
-          (*_nodes)[n].sum += (*_capacity)[a];
-          (*_nodes)[m].sum += (*_capacity)[a];
-          
-          int c = (*_nodes)[m].curr_arc;
-          if (c != -1 && _arcs[c ^ 1].target == n) {
-            _edges[c >> 1].capacity += (*_capacity)[a];
-          } else {
-            _edges[index].capacity = (*_capacity)[a];
-            
-            _arcs[index << 1].prev = -1;
-            if ((*_nodes)[n].first_arc != -1) {
-              _arcs[(*_nodes)[n].first_arc].prev = (index << 1);
-            }
-            _arcs[index << 1].next = (*_nodes)[n].first_arc;
-            (*_nodes)[n].first_arc = (index << 1);
-            _arcs[index << 1].target = m;
-
-            (*_nodes)[m].curr_arc = (index << 1);
-            
-            _arcs[(index << 1) | 1].prev = -1;
-            if ((*_nodes)[m].first_arc != -1) {
-              _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1);
-            }
-            _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc;
-            (*_nodes)[m].first_arc = ((index << 1) | 1);
-            _arcs[(index << 1) | 1].target = n;
-            
-            ++index;
-          }
-        }
-      }
-
-      typename Graph::Node cut_node = INVALID;
-      _min_cut = std::numeric_limits<Value>::max();
-
-      for (typename Graph::Node n = _first_node; 
-           n != INVALID; n = (*_nodes)[n].next) {
-        if ((*_nodes)[n].sum < _min_cut) {
-          cut_node = n;
-          _min_cut = (*_nodes)[n].sum;
-        }
-      }
-      (*_cut_map)[cut_node] = true;
-      if (_min_cut == 0) {
-        _first_node = INVALID;
-      }
-    }
-
-  public:
-
-    /// \brief Processes the next phase
-    ///
-    /// Processes the next phase in the algorithm. It must be called
-    /// at most one less the number of the nodes in the graph.
-    ///
-    ///\return %True when the algorithm finished.
-    bool processNextPhase() {
-      if (_first_node == INVALID) return true;
-
-      _heap->clear();
-      for (typename Graph::Node n = _first_node; 
-           n != INVALID; n = (*_nodes)[n].next) {
-        (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
-      }
-
-      std::vector<typename Graph::Node> order;
-      order.reserve(_node_num);
-      int sep = 0;
-
-      Value alpha = 0;
-      Value pmc = std::numeric_limits<Value>::max();
-
-      _heap->push(_first_node, static_cast<Value>(0));
-      while (!_heap->empty()) {
-        typename Graph::Node n = _heap->top();
-        Value v = _heap->prio();
-
-        _heap->pop();
-        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
-          switch (_heap->state(_arcs[a].target)) {
-          case Heap::PRE_HEAP: 
-            {
-              Value nv = _edges[a >> 1].capacity;
-              _heap->push(_arcs[a].target, nv);
-              _edges[a >> 1].cut = nv;
-            } break;
-          case Heap::IN_HEAP:
-            {
-              Value nv = _edges[a >> 1].capacity + (*_heap)[_arcs[a].target];
-              _heap->decrease(_arcs[a].target, nv);
-              _edges[a >> 1].cut = nv;
-            } break;
-          case Heap::POST_HEAP:
-            break;
-          }
-        }
-
-        alpha += (*_nodes)[n].sum;
-        alpha -= 2 * v;
-
-        order.push_back(n);
-        if (!_heap->empty()) {
-          if (alpha < pmc) {
-            pmc = alpha;
-            sep = order.size();
-          }
-        }
-      }
-
-      if (static_cast<int>(order.size()) < _node_num) {
-        _first_node = INVALID;
-        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
-          (*_cut_map)[n] = false;
-        }
-        for (int i = 0; i < static_cast<int>(order.size()); ++i) {
-          typename Graph::Node n = order[i];
-          while (n != INVALID) {
-            (*_cut_map)[n] = true;
-            n = (*_next_rep)[n];
-          }
-        }
-        _min_cut = 0;
-        return true;
-      }
-
-      if (pmc < _min_cut) {
-        for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
-          (*_cut_map)[n] = false;
-        }
-        for (int i = 0; i < sep; ++i) {
-          typename Graph::Node n = order[i];
-          while (n != INVALID) {
-            (*_cut_map)[n] = true;
-            n = (*_next_rep)[n];
-          }
-        }
-        _min_cut = pmc;
-      }
-
-      for (typename Graph::Node n = _first_node;
-           n != INVALID; n = (*_nodes)[n].next) {
-        bool merged = false;
-        for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
-          if (!(_edges[a >> 1].cut < pmc)) {
-            if (!merged) {
-              for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
-                (*_nodes)[_arcs[b].target].curr_arc = b;          
-              }
-              merged = true;
-            }
-            typename Graph::Node m = _arcs[a].target;
-            int nb = 0;
-            for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) {
-              nb = _arcs[b].next;
-              if ((b ^ a) == 1) continue;
-              typename Graph::Node o = _arcs[b].target;
-              int c = (*_nodes)[o].curr_arc; 
-              if (c != -1 && _arcs[c ^ 1].target == n) {
-                _edges[c >> 1].capacity += _edges[b >> 1].capacity;
-                (*_nodes)[n].sum += _edges[b >> 1].capacity;
-                if (_edges[b >> 1].cut < _edges[c >> 1].cut) {
-                  _edges[b >> 1].cut = _edges[c >> 1].cut;
-                }
-                if (_arcs[b ^ 1].prev != -1) {
-                  _arcs[_arcs[b ^ 1].prev].next = _arcs[b ^ 1].next;
-                } else {
-                  (*_nodes)[o].first_arc = _arcs[b ^ 1].next;
-                }
-                if (_arcs[b ^ 1].next != -1) {
-                  _arcs[_arcs[b ^ 1].next].prev = _arcs[b ^ 1].prev;
-                }
-              } else {
-                if (_arcs[a].next != -1) {
-                  _arcs[_arcs[a].next].prev = b;
-                }
-                _arcs[b].next = _arcs[a].next;
-                _arcs[b].prev = a;
-                _arcs[a].next = b;
-                _arcs[b ^ 1].target = n;
-
-                (*_nodes)[n].sum += _edges[b >> 1].capacity;
-                (*_nodes)[o].curr_arc = b;
-              }
-            }
-
-            if (_arcs[a].prev != -1) {
-              _arcs[_arcs[a].prev].next = _arcs[a].next;
-            } else {
-              (*_nodes)[n].first_arc = _arcs[a].next;
-            }            
-            if (_arcs[a].next != -1) {
-              _arcs[_arcs[a].next].prev = _arcs[a].prev;
-            }
-
-            (*_nodes)[n].sum -= _edges[a >> 1].capacity;
-            (*_next_rep)[(*_nodes)[n].last_rep] = m;
-            (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
-            
-            if ((*_nodes)[m].prev != INVALID) {
-              (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
-            } else{
-              _first_node = (*_nodes)[m].next;
-            }
-            if ((*_nodes)[m].next != INVALID) {
-              (*_nodes)[(*_nodes)[m].next].prev = (*_nodes)[m].prev;
-            }
-            --_node_num;
-          }
-        }
-      }
-
-      if (_node_num == 1) {
-        _first_node = INVALID;
-        return true;
-      }
-
-      return false;
-    }
-
-    /// \brief Executes the algorithm.
-    ///
-    /// Executes the algorithm.
-    ///
-    /// \pre init() must be called
-    void start() {
-      while (!processNextPhase()) {}
-    }
-
-
-    /// \brief Runs %NagamochiIbaraki algorithm.
-    ///
-    /// This method runs the %Min cut algorithm
-    ///
-    /// \note mc.run(s) is just a shortcut of the following code.
-    ///\code
-    ///  mc.init();
-    ///  mc.start();
-    ///\endcode
-    void run() {
-      init();
-      start();
-    }
-
-    ///@}
-
-    /// \name Query Functions
-    ///
-    /// The result of the %NagamochiIbaraki
-    /// algorithm can be obtained using these functions.\n
-    /// Before the use of these functions, either run() or start()
-    /// must be called.
-
-    ///@{
-
-    /// \brief Returns the min cut value.
-    ///
-    /// Returns the min cut value if the algorithm finished.
-    /// After the first processNextPhase() it is a value of a
-    /// valid cut in the graph.
-    Value minCutValue() const {
-      return _min_cut;
-    }
-
-    /// \brief Returns a min cut in a NodeMap.
-    ///
-    /// It sets the nodes of one of the two partitions to true and
-    /// the other partition to false.
-    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
-    /// \c bool (or convertible) value type.
-    template <typename CutMap>
-    Value minCutMap(CutMap& cutMap) const {
-      for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
-        cutMap.set(n, (*_cut_map)[n]);
-      }
-      return minCutValue();
-    }
-
-    ///@}
-
-  };
-}
-
-#endif
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 1018)
+++ test/CMakeLists.txt	(revision 1020)
@@ -32,9 +32,9 @@
   maps_test
   matching_test
+  max_cardinality_search_test
   max_clique_test
   min_cost_arborescence_test
   min_cost_flow_test
   min_mean_cycle_test
-  nagamochi_ibaraki_test
   path_test
   planarity_test
@@ -48,10 +48,5 @@
 
 IF(LEMON_HAVE_LP)
-  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
-    ADD_EXECUTABLE(lp_test lp_test.cc)
-  ELSE()
-    ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc)
-  ENDIF()
-
+  ADD_EXECUTABLE(lp_test lp_test.cc)
   SET(LP_TEST_LIBS lemon)
 
@@ -89,10 +84,5 @@
 
 IF(LEMON_HAVE_MIP)
-  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
-    ADD_EXECUTABLE(mip_test mip_test.cc)
-  ELSE()
-    ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc)
-  ENDIF()
-
+  ADD_EXECUTABLE(mip_test mip_test.cc)
   SET(MIP_TEST_LIBS lemon)
 
Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 1017)
+++ test/Makefile.am	(revision 1020)
@@ -34,9 +34,9 @@
 	test/maps_test \
 	test/matching_test \
+	test/max_cardinality_search_test \
 	test/max_clique_test \
 	test/min_cost_arborescence_test \
 	test/min_cost_flow_test \
 	test/min_mean_cycle_test \
-	test/nagamochi_ibaraki_test \
 	test/path_test \
 	test/planarity_test \
@@ -87,9 +87,9 @@
 test_mip_test_SOURCES = test/mip_test.cc
 test_matching_test_SOURCES = test/matching_test.cc
+test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc
 test_max_clique_test_SOURCES = test/max_clique_test.cc
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
-test_nagamochi_ibaraki_test_SOURCES = test/nagamochi_ibaraki_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_planarity_test_SOURCES = test/planarity_test.cc
Index: test/max_cardinality_search_test.cc
===================================================================
--- test/max_cardinality_search_test.cc	(revision 1020)
+++ test/max_cardinality_search_test.cc	(revision 1020)
@@ -0,0 +1,162 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+
+#include "test_tools.h"
+#include <lemon/smart_graph.h>
+#include <lemon/max_cardinality_search.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/concepts/heap.h>
+#include <lemon/lgf_reader.h>
+
+using namespace lemon;
+using namespace std;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "@arcs\n"
+  "    label capacity\n"
+  "0 1 0     2\n"
+  "1 0 1     2\n"
+  "2 1 2     1\n"
+  "2 3 3     3\n"
+  "3 2 4     3\n"
+  "3 1 5     5\n"
+  "@attributes\n"
+  "s 0\n"
+  "x 1\n"
+  "y 2\n"
+  "z 3\n";
+
+void checkMaxCardSearchCompile() {
+
+  typedef concepts::Digraph Digraph;
+  typedef int Value;
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
+  typedef concepts::ReadMap<Arc,Value> CapMap;
+  typedef concepts::ReadWriteMap<Node,Value> CardMap;
+  typedef concepts::ReadWriteMap<Node,bool> ProcMap;
+  typedef Digraph::NodeMap<int> HeapCrossRef;
+
+  Digraph g;
+  Node n,s;
+  CapMap cap;
+  CardMap card;
+  ProcMap proc;
+  HeapCrossRef crossref(g);
+  
+  typedef MaxCardinalitySearch<Digraph,CapMap>
+    ::SetCapacityMap<CapMap>
+    ::SetCardinalityMap<CardMap>
+    ::SetProcessedMap<ProcMap>
+    ::SetStandardHeap<BinHeap<Value,HeapCrossRef> >
+    ::Create MaxCardType;
+
+  MaxCardType maxcard(g,cap);
+  const MaxCardType& const_maxcard = maxcard;
+
+  const MaxCardType::Heap& heap_const = const_maxcard.heap();
+  MaxCardType::Heap& heap = const_cast<MaxCardType::Heap&>(heap_const);
+  maxcard.heap(heap,crossref);
+  
+  maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc);
+
+  maxcard.init();
+  maxcard.addSource(s);
+  n = maxcard.nextNode();
+   maxcard.processNextNode();
+   maxcard.start();
+   maxcard.run(s);
+   maxcard.run();
+ }
+
+ void checkWithIntMap( std::istringstream& input)
+ {
+   typedef SmartDigraph Digraph;
+   typedef Digraph::Node Node;
+   typedef Digraph::ArcMap<int> CapMap;
+
+   Digraph g;
+   Node s,x,y,z,a;
+   CapMap cap(g);
+
+   DigraphReader<Digraph>(g,input).
+     arcMap("capacity", cap).
+     node("s",s).
+     node("x",x).
+     node("y",y).
+     node("z",z).
+     run();
+
+   MaxCardinalitySearch<Digraph,CapMap> maxcard(g,cap);
+
+   maxcard.init();
+   maxcard.addSource(s);
+   maxcard.start(x);
+
+   check(maxcard.processed(s) and !maxcard.processed(x) and
+         !maxcard.processed(y), "Wrong processed()!");
+
+   a=maxcard.nextNode();
+   check(maxcard.processNextNode()==a,
+         "Wrong nextNode() or processNextNode() return value!");
+
+   check(maxcard.processed(a), "Wrong processNextNode()!");
+
+   maxcard.start();
+   check(maxcard.cardinality(x)==2 and maxcard.cardinality(y)>=4,
+         "Wrong cardinalities!");
+ }
+
+ void checkWithConst1Map(std::istringstream &input) {
+   typedef SmartDigraph Digraph;
+   typedef Digraph::Node Node;
+
+   Digraph g;
+   Node s,x,y,z;
+
+  DigraphReader<Digraph>(g,input).
+    node("s",s).
+    node("x",x).
+    node("y",y).
+    node("z",z).
+    run();
+
+  MaxCardinalitySearch<Digraph> maxcard(g);
+  maxcard.run(s);
+  check(maxcard.cardinality(x)==1 &&
+        maxcard.cardinality(y)+maxcard.cardinality(z)==3,
+        "Wrong cardinalities!");
+}
+
+int main() {
+
+  std::istringstream input1(test_lgf);
+  checkWithIntMap(input1);
+
+  std::istringstream input2(test_lgf);
+  checkWithConst1Map(input2);
+}
Index: st/nagamochi_ibaraki_test.cc
===================================================================
--- test/nagamochi_ibaraki_test.cc	(revision 1017)
+++ 	(revision )
@@ -1,141 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2010
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <sstream>
-
-#include <lemon/smart_graph.h>
-#include <lemon/adaptors.h>
-#include <lemon/concepts/graph.h>
-#include <lemon/concepts/maps.h>
-#include <lemon/lgf_reader.h>
-#include <lemon/nagamochi_ibaraki.h>
-
-#include "test_tools.h"
-
-using namespace lemon;
-using namespace std;
-
-const std::string lgf =
-  "@nodes\n"
-  "label\n"
-  "0\n"
-  "1\n"
-  "2\n"
-  "3\n"
-  "4\n"
-  "5\n"
-  "@edges\n"
-  "     cap1 cap2 cap3\n"
-  "0 1  1    1    1   \n"
-  "0 2  2    2    4   \n"
-  "1 2  4    4    4   \n"
-  "3 4  1    1    1   \n"
-  "3 5  2    2    4   \n"
-  "4 5  4    4    4   \n"
-  "2 3  1    6    6   \n";
-
-void checkNagamochiIbarakiCompile()
-{
-  typedef int Value;
-  typedef concepts::Graph Graph;
-
-  typedef Graph::Node Node;
-  typedef Graph::Edge Edge;
-  typedef concepts::ReadMap<Edge, Value> CapMap;
-  typedef concepts::WriteMap<Node, bool> CutMap;
-
-  Graph g;
-  Node n;
-  CapMap cap;
-  CutMap cut;
-  Value v;
-  bool b;
-
-  NagamochiIbaraki<Graph, CapMap> ni_test(g, cap);
-  const NagamochiIbaraki<Graph, CapMap>& const_ni_test = ni_test;
-
-  ni_test.init();
-  ni_test.start();
-  b = ni_test.processNextPhase();
-  ni_test.run();
-
-  v = const_ni_test.minCutValue();
-  v = const_ni_test.minCutMap(cut);
-}
-
-template <typename Graph, typename CapMap, typename CutMap>
-typename CapMap::Value
-  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
-{
-  typename CapMap::Value sum = 0;
-  for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) {
-    if (cut[graph.u(e)] != cut[graph.v(e)]) {
-      sum += cap[e];
-    }
-  }
-  return sum;
-}
-
-int main() {
-  SmartGraph graph;
-  SmartGraph::EdgeMap<int> cap1(graph), cap2(graph), cap3(graph);
-  SmartGraph::NodeMap<bool> cut(graph);
-
-  istringstream input(lgf);
-  graphReader(graph, input)
-    .edgeMap("cap1", cap1)
-    .edgeMap("cap2", cap2)
-    .edgeMap("cap3", cap3)
-    .run();
-
-  {
-    NagamochiIbaraki<SmartGraph> ni(graph, cap1);
-    ni.run();
-    ni.minCutMap(cut);
-
-    check(ni.minCutValue() == 1, "Wrong cut value");
-    check(ni.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
-  }
-  {
-    NagamochiIbaraki<SmartGraph> ni(graph, cap2);
-    ni.run();
-    ni.minCutMap(cut);
-
-    check(ni.minCutValue() == 3, "Wrong cut value");
-    check(ni.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
-  }
-  {
-    NagamochiIbaraki<SmartGraph> ni(graph, cap3);
-    ni.run();
-    ni.minCutMap(cut);
-
-    check(ni.minCutValue() == 5, "Wrong cut value");
-    check(ni.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
-  }
-  {
-    NagamochiIbaraki<SmartGraph>::SetUnitCapacity::Create ni(graph);
-    ni.run();
-    ni.minCutMap(cut);
-
-    ConstMap<SmartGraph::Edge, int> cap4(1);
-    check(ni.minCutValue() == 1, "Wrong cut value");
-    check(ni.minCutValue() == cutValue(graph, cap4, cut), "Wrong cut value");
-  }
-
-  return 0;
-}
