Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt	(revision 1056)
+++ CMakeLists.txt	(revision 791)
@@ -3,7 +3,4 @@
 SET(PROJECT_NAME "LEMON")
 PROJECT(${PROJECT_NAME})
-
-INCLUDE(FindPythonInterp)
-INCLUDE(FindWget)
 
 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
@@ -12,11 +9,4 @@
   SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
 ELSE()
-  EXECUTE_PROCESS(
-    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
-    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
-    OUTPUT_VARIABLE HG_REVISION_PATH
-    ERROR_QUIET
-    OUTPUT_STRIP_TRAILING_WHITESPACE
-  )
   EXECUTE_PROCESS(
     COMMAND hg id -i
@@ -27,13 +17,7 @@
   )
   IF(HG_REVISION STREQUAL "")
-    SET(HG_REVISION_ID "hg-tip")
-  ELSE()
-    IF(HG_REVISION_PATH STREQUAL "")
-      SET(HG_REVISION_ID ${HG_REVISION})
-    ELSE()
-      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
-    ENDIF()
+    SET(HG_REVISION "hg-tip")
   ENDIF()
-  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
+  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
 ENDIF()
 
@@ -48,82 +32,14 @@
 FIND_PACKAGE(COIN)
 
-IF(DEFINED ENV{LEMON_CXX_WARNING})
-  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
-ELSE()
-  IF(CMAKE_COMPILER_IS_GNUCXX)
-    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
-    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
-    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
-  ELSEIF(MSVC)
-    # This part is unnecessary 'casue the same is set by the lemon/core.h.
-    # Still keep it as an example.
-    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
-    # Suppressed warnings:
-    # C4250: 'class1' : inherits 'class2::member' via dominance
-    # C4355: 'this' : used in base member initializer list
-    # C4503: 'function' : decorated name length exceeded, name was truncated
-    # C4800: 'type' : forcing value to bool 'true' or 'false'
-    #        (performance warning)
-    # C4996: 'function': was declared deprecated
-  ELSE()
-    SET(CXX_WARNING "-Wall -W")
-  ENDIF()
-ENDIF()
-SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
-
-SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
-
-SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
-    "Flags used by the C++ compiler during maintainer builds."
-    FORCE )
-SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
-    "Flags used by the C compiler during maintainer builds."
-    FORCE )
-SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
-    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
-    "Flags used for linking binaries during maintainer builds."
-    FORCE )
-SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
-    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
-    "Flags used by the shared libraries linker during maintainer builds."
-    FORCE )
-MARK_AS_ADVANCED(
-    CMAKE_CXX_FLAGS_MAINTAINER
-    CMAKE_C_FLAGS_MAINTAINER
-    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
-    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
-
-IF(CMAKE_CONFIGURATION_TYPES)
-  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
-  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
-  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
-      "Add the configurations that we need"
-      FORCE)
- endif()
-
-IF(NOT CMAKE_BUILD_TYPE)
-  SET(CMAKE_BUILD_TYPE "Release")
-ENDIF()
-
-SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
-    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
-    FORCE )
-
-
 INCLUDE(CheckTypeSize)
 CHECK_TYPE_SIZE("long long" LONG_LONG)
 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 
+INCLUDE(FindPythonInterp)
+
 ENABLE_TESTING()
-
-IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
-  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
-ELSE()
-  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
-ENDIF()
 
 ADD_SUBDIRECTORY(lemon)
 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
-  ADD_SUBDIRECTORY(contrib)
   ADD_SUBDIRECTORY(demo)
   ADD_SUBDIRECTORY(tools)
@@ -149,5 +65,5 @@
 ENDIF()
 
-IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
   SET(CPACK_PACKAGE_VENDOR "EGRES")
Index: LICENSE
===================================================================
--- LICENSE	(revision 959)
+++ LICENSE	(revision 600)
@@ -2,5 +2,5 @@
 copyright/license.
 
-Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
+Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 EGRES).
Index: NEWS
===================================================================
--- NEWS	(revision 962)
+++ NEWS	(revision 712)
@@ -1,82 +1,2 @@
-2010-03-19 Version 1.2 released
-
-        This is major feature release
-
-        * New algorithms
-          * Bellman-Ford algorithm (#51)
-          * Minimum mean cycle algorithms (#179)
-            * Karp, Hartman-Orlin and Howard algorithms
-          * New minimum cost flow algorithms (#180)
-            * Cost Scaling algorithms
-            * Capacity Scaling algorithm
-            * Cycle-Canceling algorithms
-          * Planarity related algorithms (#62)
-            * Planarity checking algorithm
-            * Planar embedding algorithm
-            * Schnyder's planar drawing algorithm
-            * Coloring planar graphs with five or six colors
-          * Fractional matching algorithms (#314)
-        * New data structures
-          * StaticDigraph structure (#68)
-          * Several new priority queue structures (#50, #301)
-            * Fibonacci, Radix, Bucket, Pairing, Binomial
-              D-ary and fourary heaps (#301)
-          * Iterable map structures (#73)
-        * Other new tools and functionality
-          * Map utility functions (#320)
-          * Reserve functions are added to ListGraph and SmartGraph (#311)
-          * A resize() function is added to HypercubeGraph (#311)
-          * A count() function is added to CrossRefMap (#302)
-          * Support for multiple targets in Suurballe using fullInit() (#181)
-          * Traits class and named parameters for Suurballe (#323)
-          * Separate reset() and resetParams() functions in NetworkSimplex
-            to handle graph changes (#327)
-          * tolerance() functions are added to HaoOrlin (#306)
-        * Implementation improvements
-          * Improvements in weighted matching algorithms (#314)
-            * Jumpstart initialization
-          * ArcIt iteration is based on out-arc lists instead of in-arc lists
-            in ListDigraph (#311)
-          * Faster add row operation in CbcMip (#203)
-          * Better implementation for split() in ListDigraph (#311)
-          * ArgParser can also throw exception instead of exit(1) (#332)
-        * Miscellaneous
-          * A simple interactive bootstrap script
-          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
-                #316,#319)
-            * BibTeX references in the doc (#184)
-          * Optionally use valgrind when running tests
-          * Also check ReferenceMapTag in concept checks (#312)
-          * dimacs-solver uses long long type by default.
-        * Several bugfixes (compared to release 1.1):
-          #295: Suppress MSVC warnings using pragmas
-          ----: Various CMAKE related improvements
-                * Remove duplications from doc/CMakeLists.txt
-                * Rename documentation install folder from 'docs' to 'html'
-                * Add tools/CMakeLists.txt to the tarball
-                * Generate and install LEMONConfig.cmake
-                * Change the label of the html project in Visual Studio
-                * Fix the check for the 'long long' type
-                * Put the version string into config.h
-                * Minor CMake improvements
-                * Set the version to 'hg-tip' if everything fails
-          #311: Add missing 'explicit' keywords
-          #302: Fix the implementation and doc of CrossRefMap
-          #308: Remove duplicate list_graph.h entry from source list
-          #307: Bugfix in Preflow and Circulation
-          #305: Bugfix and extension in the rename script
-          #312: Also check ReferenceMapTag in concept checks
-          #250: Bugfix in pathSource() and pathTarget()
-          #321: Use pathCopy(from,to) instead of copyPath(to,from)
-          #322: Distribure LEMONConfig.cmake.in
-          #330: Bug fix in map_extender.h
-          #336: Fix the date field comment of graphToEps() output
-          #323: Bug fix in Suurballe
-          #335: Fix clear() function in ExtendFindEnum
-          #337: Use void* as the LPX object pointer
-          #317: Fix (and improve) error message in mip_test.cc
-                Remove unnecessary OsiCbc dependency
-          #356: Allow multiple executions of weighted matching algorithms (#356)
-
 2009-05-13 Version 1.1 released
 
@@ -153,5 +73,5 @@
           ----: Add missing unistd.h include to time_measure.h
           #204: Compilation bug fixed in graph_to_eps.h with VS2005
-          #214,#215: windows.h should never be included by LEMON headers
+          #214,#215: windows.h should never be included by lemon headers
           #230: Build systems check the availability of 'long long' type
           #229: Default implementation of Tolerance<> is used for integer types
@@ -175,50 +95,50 @@
 2008-10-13 Version 1.0 released
 
-        This is the first stable release of LEMON. Compared to the 0.x
-        release series, it features a considerably smaller but more
-        matured set of tools. The API has also completely revised and
-        changed in several places.
+	This is the first stable release of LEMON. Compared to the 0.x
+	release series, it features a considerably smaller but more
+	matured set of tools. The API has also completely revised and
+	changed in several places.
 
-        * The major name changes compared to the 0.x series (see the
+	* The major name changes compared to the 0.x series (see the
           Migration Guide in the doc for more details)
           * Graph -> Digraph, UGraph -> Graph
           * Edge -> Arc, UEdge -> Edge
-          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
-        * Other improvements
-          * Better documentation
-          * Reviewed and cleaned up codebase
-          * CMake based build system (along with the autotools based one)
-        * Contents of the library (ported from 0.x)
-          * Algorithms
-            * breadth-first search (bfs.h)
-            * depth-first search (dfs.h)
-            * Dijkstra's algorithm (dijkstra.h)
-            * Kruskal's algorithm (kruskal.h)
-          * Data structures
-            * graph data structures (list_graph.h, smart_graph.h)
-            * path data structures (path.h)
-            * binary heap data structure (bin_heap.h)
-            * union-find data structures (unionfind.h)
-            * miscellaneous property maps (maps.h)
-            * two dimensional vector and bounding box (dim2.h)
+	  * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
+	* Other improvements
+	  * Better documentation
+	  * Reviewed and cleaned up codebase
+	  * CMake based build system (along with the autotools based one)
+	* Contents of the library (ported from 0.x)
+	  * Algorithms
+       	    * breadth-first search (bfs.h)
+       	    * depth-first search (dfs.h)
+       	    * Dijkstra's algorithm (dijkstra.h)
+       	    * Kruskal's algorithm (kruskal.h)
+    	  * Data structures
+       	    * graph data structures (list_graph.h, smart_graph.h)
+       	    * path data structures (path.h)
+       	    * binary heap data structure (bin_heap.h)
+       	    * union-find data structures (unionfind.h)
+       	    * miscellaneous property maps (maps.h)
+       	    * two dimensional vector and bounding box (dim2.h)
           * Concepts
-            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
+       	    * graph structure concepts (concepts/digraph.h, concepts/graph.h,
               concepts/graph_components.h)
-            * concepts for other structures (concepts/heap.h, concepts/maps.h,
-              concepts/path.h)
-          * Tools
-            * Mersenne twister random number generator (random.h)
-            * tools for measuring cpu and wall clock time (time_measure.h)
-            * tools for counting steps and events (counter.h)
-            * tool for parsing command line arguments (arg_parser.h)
-            * tool for visualizing graphs (graph_to_eps.h)
-            * tools for reading and writing data in LEMON Graph Format
+       	    * concepts for other structures (concepts/heap.h, concepts/maps.h,
+	      concepts/path.h)
+    	  * Tools
+       	    * Mersenne twister random number generator (random.h)
+       	    * tools for measuring cpu and wall clock time (time_measure.h)
+       	    * tools for counting steps and events (counter.h)
+       	    * tool for parsing command line arguments (arg_parser.h)
+       	    * tool for visualizing graphs (graph_to_eps.h)
+       	    * tools for reading and writing data in LEMON Graph Format
               (lgf_reader.h, lgf_writer.h)
             * tools to handle the anomalies of calculations with
-              floating point numbers (tolerance.h)
+	      floating point numbers (tolerance.h)
             * tools to manage RGB colors (color.h)
-          * Infrastructure
-            * extended assertion handling (assert.h)
-            * exception classes and error handling (error.h)
-            * concept checking (concept_check.h)
-            * commonly used mathematical constants (math.h)
+    	  * Infrastructure
+       	    * extended assertion handling (assert.h)
+       	    * exception classes and error handling (error.h)
+      	    * concept checking (concept_check.h)
+       	    * commonly used mathematical constants (math.h)
Index: configure.ac
===================================================================
--- configure.ac	(revision 1039)
+++ configure.ac	(revision 840)
@@ -115,5 +115,5 @@
 dnl Add dependencies on files generated by configure.
 AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
-  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
+  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
 
 AC_CONFIG_FILES([
@@ -122,5 +122,4 @@
 cmake/version.cmake
 doc/Doxyfile
-doc/mainpage.dox
 lemon/lemon.pc
 ])
Index: ntrib/CMakeLists.txt
===================================================================
--- contrib/CMakeLists.txt	(revision 1031)
+++ 	(revision )
@@ -1,19 +1,0 @@
-INCLUDE_DIRECTORIES(
-  ${PROJECT_SOURCE_DIR}
-  ${PROJECT_BINARY_DIR}
-)
-
-LINK_DIRECTORIES(
-  ${PROJECT_BINARY_DIR}/lemon
-)
-
-# Uncomment (and adjust) the following two lines. 'myprog' is the name
-# of the final executable ('.exe' will automatically be added to the
-# name on Windows) and 'myprog-main.cc' is the source code it is
-# compiled from. You can add more source files separated by
-# whitespaces. Moreover, you can add multiple similar blocks if you
-# want to build more than one executables.
-
-# ADD_EXECUTABLE(myprog myprog-main.cc)
-# TARGET_LINK_LIBRARIES(myprog lemon)
-
Index: doc/CMakeLists.txt
===================================================================
--- doc/CMakeLists.txt	(revision 1040)
+++ doc/CMakeLists.txt	(revision 943)
@@ -4,15 +4,7 @@
 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 
-SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
-
 CONFIGURE_FILE(
   ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
   ${PROJECT_BINARY_DIR}/doc/Doxyfile
-  @ONLY
-)
-
-CONFIGURE_FILE(
-  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
-  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
   @ONLY
 )
@@ -61,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 1040)
+++ doc/Doxyfile.in	(revision 803)
@@ -1,3 +1,3 @@
-# Doxyfile 1.7.3
+# Doxyfile 1.5.9
 
 #---------------------------------------------------------------------------
@@ -5,8 +5,6 @@
 #---------------------------------------------------------------------------
 DOXYFILE_ENCODING      = UTF-8
-PROJECT_NAME           = 
-PROJECT_NUMBER         = 
-PROJECT_BRIEF          =
-PROJECT_LOGO           =
+PROJECT_NAME           = @PACKAGE_NAME@
+PROJECT_NUMBER         = @PACKAGE_VERSION@
 OUTPUT_DIRECTORY       = 
 CREATE_SUBDIRS         = NO
@@ -32,5 +30,4 @@
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
-EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
@@ -58,12 +55,9 @@
 HIDE_SCOPE_NAMES       = YES
 SHOW_INCLUDE_FILES     = YES
-FORCE_LOCAL_INCLUDES   = NO
 INLINE_INFO            = YES
 SORT_MEMBER_DOCS       = NO
 SORT_BRIEF_DOCS        = NO
-SORT_MEMBERS_CTORS_1ST = NO
 SORT_GROUP_NAMES       = NO
 SORT_BY_SCOPE_NAME     = NO
-STRICT_PROTO_MATCHING  = NO
 GENERATE_TODOLIST      = YES
 GENERATE_TESTLIST      = YES
@@ -77,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
@@ -96,8 +90,6 @@
                          "@abs_top_srcdir@/lemon/concepts" \
                          "@abs_top_srcdir@/demo" \
-                         "@abs_top_srcdir@/contrib" \
                          "@abs_top_srcdir@/tools" \
                          "@abs_top_srcdir@/test/test_tools.h" \
-                         "@abs_top_builddir@/doc/mainpage.dox" \
                          "@abs_top_builddir@/doc/references.dox"
 INPUT_ENCODING         = UTF-8
@@ -120,9 +112,8 @@
 FILTER_PATTERNS        = 
 FILTER_SOURCE_FILES    = NO
-FILTER_SOURCE_PATTERNS =
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
-SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
+SOURCE_BROWSER         = NO
 INLINE_SOURCES         = NO
 STRIP_CODE_COMMENTS    = YES
@@ -147,15 +138,9 @@
 HTML_FOOTER            = 
 HTML_STYLESHEET        = 
-HTML_COLORSTYLE_HUE    = 220
-HTML_COLORSTYLE_SAT    = 100
-HTML_COLORSTYLE_GAMMA  = 80
-HTML_TIMESTAMP         = YES
 HTML_ALIGN_MEMBERS     = YES
-HTML_DYNAMIC_SECTIONS  = YES
+HTML_DYNAMIC_SECTIONS  = NO
 GENERATE_DOCSET        = NO
 DOCSET_FEEDNAME        = "Doxygen generated docs"
 DOCSET_BUNDLE_ID       = org.doxygen.Project
-DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
-DOCSET_PUBLISHER_NAME  = Publisher
 GENERATE_HTMLHELP      = NO
 CHM_FILE               = 
@@ -169,22 +154,10 @@
 QHP_NAMESPACE          = org.doxygen.Project
 QHP_VIRTUAL_FOLDER     = doc
-QHP_CUST_FILTER_NAME   =
-QHP_CUST_FILTER_ATTRS  =
-QHP_SECT_FILTER_ATTRS  =
 QHG_LOCATION           = 
-GENERATE_ECLIPSEHELP   = NO
-ECLIPSE_DOC_ID         = org.doxygen.Project
 DISABLE_INDEX          = NO
 ENUM_VALUES_PER_LINE   = 4
 GENERATE_TREEVIEW      = NO
-USE_INLINE_TREES       = NO
 TREEVIEW_WIDTH         = 250
-EXT_LINKS_IN_WINDOW    = NO
 FORMULA_FONTSIZE       = 10
-FORMULA_TRANSPARENT    = YES
-USE_MATHJAX            = NO
-MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
-SEARCHENGINE           = YES
-SERVER_BASED_SEARCH    = NO
 #---------------------------------------------------------------------------
 # configuration options related to the LaTeX output
@@ -203,5 +176,4 @@
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
-LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
@@ -252,7 +224,7 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Configuration::additions related to external references
-#---------------------------------------------------------------------------
-TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+# Options related to the search engine   
+#---------------------------------------------------------------------------
+TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 GENERATE_TAGFILE       = html/lemon.tag
 ALLEXTERNALS           = NO
@@ -266,5 +238,4 @@
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
-DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
@@ -284,5 +255,4 @@
 DOT_PATH               = 
 DOTFILE_DIRS           = 
-MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
@@ -291,2 +261,6 @@
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
+#---------------------------------------------------------------------------
+# Configuration::additions related to the search engine   
+#---------------------------------------------------------------------------
+SEARCHENGINE           = NO
Index: doc/DoxygenLayout.xml
===================================================================
--- doc/DoxygenLayout.xml	(revision 1036)
+++ doc/DoxygenLayout.xml	(revision 316)
@@ -3,22 +3,22 @@
   <navindex>
     <tab type="mainpage" visible="yes" title=""/>
-    <tab type="modules" visible="yes" title="" intro=""/>
+    <tab type="modules" visible="yes" title=""/>
     <tab type="classes" visible="yes" title="">
-      <tab type="classes" visible="yes" title="" intro=""/>
-      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
-      <tab type="hierarchy" visible="yes" title="" intro=""/>
-      <tab type="classmembers" visible="yes" title="" intro=""/>
+      <tab type="classes" visible="yes" title=""/>
+      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
+      <tab type="hierarchy" visible="yes" title=""/>
+      <tab type="classmembers" visible="yes" title=""/>
     </tab>
     <tab type="namespaces" visible="yes" title="">
-      <tab type="namespaces" visible="yes" title="" intro=""/>
-      <tab type="namespacemembers" visible="yes" title="" intro=""/>
+      <tab type="namespaces" visible="yes" title=""/>
+      <tab type="namespacemembers" visible="yes" title=""/>
     </tab>
     <tab type="files" visible="yes" title="">
-      <tab type="files" visible="yes" title="" intro=""/>
-      <tab type="globals" visible="yes" title="" intro=""/>
+      <tab type="files" visible="yes" title=""/>
+      <tab type="globals" visible="yes" title=""/>
     </tab>
-    <tab type="dirs" visible="yes" title="" intro=""/>
-    <tab type="examples" visible="yes" title="" intro=""/>
-    <tab type="pages" visible="yes" title="" intro=""/>
+    <tab type="dirs" visible="yes" title=""/>
+    <tab type="examples" visible="yes" title=""/>  
+    <tab type="pages" visible="yes" title=""/>
   </navindex>
 
Index: doc/coding_style.dox
===================================================================
--- doc/coding_style.dox	(revision 1023)
+++ doc/coding_style.dox	(revision 463)
@@ -99,8 +99,8 @@
 \subsection pri-loc-var Private member variables
 
-Private member variables should start with underscore.
+Private member variables should start with underscore
 
 \code
-_start_with_underscore
+_start_with_underscores
 \endcode
 
Index: doc/dirs.dox
===================================================================
--- doc/dirs.dox	(revision 1031)
+++ doc/dirs.dox	(revision 463)
@@ -32,17 +32,4 @@
 documentation.
 */
-
-/**
-\dir contrib
-\brief Directory for user contributed source codes.
-
-You can place your own C++ code using LEMON into this directory, which
-will compile to an executable along with LEMON when you build the
-library. This is probably the easiest way of compiling short to medium
-codes, for this does require neither a LEMON installed system-wide nor
-adding several paths to the compiler.
-
-Please have a look at <tt>contrib/CMakeLists.txt</tt> for
-instruction on how to add your own files into the build process.  */
 
 /**
Index: doc/groups.dox
===================================================================
--- doc/groups.dox	(revision 1023)
+++ doc/groups.dox	(revision 956)
@@ -264,4 +264,12 @@
 
 /**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup auxdat Auxiliary Data Structures
 @ingroup datas
@@ -407,8 +415,8 @@
    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 
-In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
-implementations, but the other two algorithms could be faster in special cases.
+In general NetworkSimplex is the most efficient implementation,
+but in special cases other algorithms could be faster.
 For example, if the total supply and/or capacities are rather small,
-\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
+CapacityScaling is usually the fastest algorithm (without effective scaling).
 */
 
@@ -465,17 +473,17 @@
 
 LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
+- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
   \ref dasdan98minmeancycle.
-- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
   version of Karp's algorithm \ref dasdan98minmeancycle.
-- \ref HowardMmc Howard's policy iteration algorithm
+- \ref Howard "Howard"'s policy iteration algorithm
   \ref dasdan98minmeancycle.
 
-In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
-most efficient one, though the best known theoretical bound on its running
-time is exponential.
-Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
-run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
-typically faster due to the applied early termination scheme.
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
 */
 
@@ -540,5 +548,5 @@
 
 /**
-@defgroup planar Planar Embedding and Drawing
+@defgroup planar Planarity Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing
@@ -552,5 +560,5 @@
 
 /**
-@defgroup approx_algs Approximation Algorithms
+@defgroup approx Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -558,8 +566,4 @@
 This group contains the approximation and heuristic algorithms
 implemented in LEMON.
-
-<b>Maximum Clique Problem</b>
-  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
-    Grosso, Locatelli, and Pullan.
 */
 
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox	(revision 956)
+++ doc/mainpage.dox	(revision 956)
@@ -0,0 +1,61 @@
+/* -*- 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.
+ *
+ */
+
+/**
+\mainpage LEMON Documentation
+
+\section intro Introduction
+
+<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
+and <b>O</b>ptimization in <b>N</b>etworks</i>.
+It is a C++ template library providing efficient implementations of common
+data structures and algorithms with focus on combinatorial optimization
+tasks connected mainly with graphs and networks.
+
+<b>
+LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
+project.
+You are free to use it in your commercial or
+non-commercial applications under very permissive
+\ref license "license terms".
+</b>
+
+The project is maintained by the
+<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
+Combinatorial Optimization</a> \ref egres
+at the Operations Research Department of the
+<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
+Budapest, Hungary.
+LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
+initiative \ref coinor.
+
+\section howtoread How to Read the Documentation
+
+If you would like to get to know the library, see
+<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
+
+If you are interested in starting to use the library, see the <a class="el"
+href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
+Guide</a>.
+
+If you know what you are looking for, then try to find it under the
+<a class="el" href="modules.html">Modules</a> section.
+
+If you are a user of the old (0.x) series of LEMON, please check out the
+\ref migration "Migration Guide" for the backward incompatibilities.
+*/
Index: c/mainpage.dox.in
===================================================================
--- doc/mainpage.dox.in	(revision 1039)
+++ 	(revision )
@@ -1,61 +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.
- *
- */
-
-/**
-\mainpage @PACKAGE_NAME@ @PACKAGE_VERSION@ Documentation
-
-\section intro Introduction
-
-<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
-and <b>O</b>ptimization in <b>N</b>etworks</i>.
-It is a C++ template library providing efficient implementations of common
-data structures and algorithms with focus on combinatorial optimization
-tasks connected mainly with graphs and networks.
-
-<b>
-LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
-project.
-You are free to use it in your commercial or
-non-commercial applications under very permissive
-\ref license "license terms".
-</b>
-
-The project is maintained by the
-<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
-Combinatorial Optimization</a> \ref egres
-at the Operations Research Department of the
-<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
-Budapest, Hungary.
-LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
-initiative \ref coinor.
-
-\section howtoread How to Read the Documentation
-
-If you would like to get to know the library, see
-<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
-
-If you are interested in starting to use the library, see the <a class="el"
-href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
-Guide</a>.
-
-If you know what you are looking for, then try to find it under the
-<a class="el" href="modules.html">Modules</a> section.
-
-If you are a user of the old (0.x) series of LEMON, please check out the
-\ref migration "Migration Guide" for the backward incompatibilities.
-*/
Index: doc/references.bib
===================================================================
--- doc/references.bib	(revision 999)
+++ doc/references.bib	(revision 802)
@@ -298,17 +298,4 @@
   address =      {Dublin, Ireland},
   year =         1991,
-  month =        sep
-}
-
-%%%%% Other algorithms %%%%%
-
-@article{grosso08maxclique,
-  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
-  title =        {Simple ingredients leading to very efficient
-                  heuristics for the maximum clique problem},
-  journal =      {Journal of Heuristics},
-  year =         2008,
-  volume =       14,
-  number =       6,
-  pages =        {587--612}
-}
+  month =        sep,
+}
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 1021)
+++ lemon/Makefile.am	(revision 953)
@@ -91,5 +91,4 @@
 	lemon/graph_to_eps.h \
 	lemon/grid_graph.h \
-	lemon/grosso_locatelli_pullan_mc.h \
 	lemon/hartmann_orlin_mmc.h \
 	lemon/howard_mmc.h \
@@ -108,6 +107,4 @@
 	lemon/math.h \
 	lemon/min_cost_arborescence.h \
-	lemon/max_cardinality_search.h \
-	lemon/nagamochi_ibaraki.h \
 	lemon/nauty_reader.h \
 	lemon/network_simplex.h \
Index: lemon/arg_parser.h
===================================================================
--- lemon/arg_parser.h	(revision 959)
+++ lemon/arg_parser.h	(revision 956)
@@ -36,17 +36,10 @@
 
   ///Exception used by ArgParser
-
-  ///Exception used by ArgParser.
-  ///
   class ArgParserException : public Exception {
   public:
-    /// Reasons for failure
-
-    /// Reasons for failure.
-    ///
     enum Reason {
-      HELP,         ///< <tt>--help</tt> option was given.
-      UNKNOWN_OPT,  ///< Unknown option was given.
-      INVALID_OPT   ///< Invalid combination of options.
+      HELP,         /// <tt>--help</tt> option was given
+      UNKNOWN_OPT,  /// Unknown option was given
+      INVALID_OPT   /// Invalid combination of options
     };
 
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h	(revision 960)
+++ lemon/bellman_ford.h	(revision 956)
@@ -29,4 +29,5 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/tolerance.h>
 #include <lemon/path.h>
 
@@ -35,5 +36,5 @@
 namespace lemon {
 
-  /// \brief Default OperationTraits for the BellmanFord algorithm class.
+  /// \brief Default operation traits for the BellmanFord algorithm class.
   ///
   /// This operation traits class defines all computational operations
@@ -42,9 +43,11 @@
   /// If the numeric type does not have infinity value, then the maximum
   /// value is used as extremal infinity value.
+  ///
+  /// \see BellmanFordToleranceOperationTraits
   template <
     typename V,
     bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
-    /// \e
+    /// \brief Value type for the algorithm.
     typedef V Value;
     /// \brief Gives back the zero value of the type.
@@ -82,4 +85,49 @@
     static bool less(const Value& left, const Value& right) {
       return left < right;
+    }
+  };
+
+  /// \brief Operation traits for the BellmanFord algorithm class
+  /// using tolerance.
+  ///
+  /// This operation traits class defines all computational operations
+  /// and constants that are used in the Bellman-Ford algorithm.
+  /// The only difference between this implementation and
+  /// \ref BellmanFordDefaultOperationTraits is that this class uses
+  /// the \ref Tolerance "tolerance technique" in its \ref less()
+  /// function.
+  ///
+  /// \tparam V The value type.
+  /// \tparam eps The epsilon value for the \ref less() function.
+  /// By default, it is the epsilon value used by \ref Tolerance
+  /// "Tolerance<V>".
+  ///
+  /// \see BellmanFordDefaultOperationTraits
+#ifdef DOXYGEN
+  template <typename V, V eps>
+#else
+  template <
+    typename V,
+    V eps = Tolerance<V>::def_epsilon>
+#endif
+  struct BellmanFordToleranceOperationTraits {
+    /// \brief Value type for the algorithm.
+    typedef V Value;
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the positive infinity value of the type.
+    static Value infinity() {
+      return std::numeric_limits<Value>::infinity();
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return left + right;
+    }
+    /// \brief Gives back \c true only if the first value is less than
+    /// the second.
+    static bool less(const Value& left, const Value& right) {
+      return left + eps < right;
     }
   };
@@ -108,5 +156,6 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
@@ -838,5 +887,6 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h	(revision 968)
+++ lemon/bits/edge_set_extender.h	(revision 956)
@@ -281,6 +281,4 @@
     typedef EdgeSetExtender Graph;
 
-    typedef True UndirectedTag;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
Index: lemon/bits/graph_adaptor_extender.h
===================================================================
--- lemon/bits/graph_adaptor_extender.h	(revision 965)
+++ lemon/bits/graph_adaptor_extender.h	(revision 664)
@@ -182,6 +182,4 @@
     typedef GraphAdaptorExtender Adaptor;
 
-    typedef True UndirectedTag;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
Index: lemon/bits/path_dump.h
===================================================================
--- lemon/bits/path_dump.h	(revision 973)
+++ lemon/bits/path_dump.h	(revision 576)
@@ -50,5 +50,5 @@
 
     bool empty() const {
-      return predMap[target] == INVALID;
+      return predMap[target] != INVALID;
     }
 
@@ -124,5 +124,5 @@
 
     bool empty() const {
-      return predMatrixMap(source, target) == INVALID;
+      return source != target;
     }
 
Index: lemon/bits/windows.cc
===================================================================
--- lemon/bits/windows.cc	(revision 1055)
+++ lemon/bits/windows.cc	(revision 956)
@@ -41,7 +41,5 @@
 #include <unistd.h>
 #include <ctime>
-#ifndef WIN32
 #include <sys/times.h>
-#endif
 #include <sys/time.h>
 #endif
Index: lemon/capacity_scaling.h
===================================================================
--- lemon/capacity_scaling.h	(revision 1026)
+++ lemon/capacity_scaling.h	(revision 956)
@@ -87,9 +87,8 @@
   /// consider to use the named template parameters instead.
   ///
-  /// \warning Both \c V and \c C must be signed number types.
-  /// \warning All input data (capacities, supply values, and costs) must
+  /// \warning Both number types must be signed and all input data must
   /// be integer.
-  /// \warning This algorithm does not support negative costs for
-  /// arcs having infinite upper bound.
+  /// \warning This algorithm does not support negative costs for such
+  /// arcs that have infinite upper bound.
 #ifdef DOXYGEN
   template <typename GR, typename V, typename C, typename TR>
@@ -424,5 +423,5 @@
     ///
     /// Using this function has the same effect as using \ref supplyMap()
-    /// with a map in which \c k is assigned to \c s, \c -k is
+    /// with such a map in which \c k is assigned to \c s, \c -k is
     /// assigned to \c t and all other nodes have zero supply value.
     ///
Index: lemon/core.h
===================================================================
--- lemon/core.h	(revision 1023)
+++ lemon/core.h	(revision 956)
@@ -395,5 +395,4 @@
       static void copy(const From& from, Digraph &to,
                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
-        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();
@@ -423,5 +422,4 @@
       static void copy(const From& from, Graph &to,
                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
-        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();
@@ -447,23 +445,4 @@
 
   }
-
-  /// \brief Check whether a graph is undirected.
-  ///
-  /// This function returns \c true if the given graph is undirected.
-#ifdef DOXYGEN
-  template <typename GR>
-  bool undirected(const GR& g) { return false; }
-#else
-  template <typename GR>
-  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
-  undirected(const GR&) {
-    return true;
-  }
-  template <typename GR>
-  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
-  undirected(const GR&) {
-    return false;
-  }
-#endif
 
   /// \brief Class to copy a digraph.
Index: lemon/cost_scaling.h
===================================================================
--- lemon/cost_scaling.h	(revision 1049)
+++ lemon/cost_scaling.h	(revision 1041)
@@ -98,7 +98,4 @@
   /// "preflow push-relabel" algorithm for the maximum flow problem.
   ///
-  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
-  /// implementations available in LEMON for this problem.
-  ///
   /// Most of the parameters of the problem (except for the digraph)
   /// can be given using separate functions, and the algorithm can be
@@ -117,9 +114,8 @@
   /// consider to use the named template parameters instead.
   ///
-  /// \warning Both \c V and \c C must be signed number types.
-  /// \warning All input data (capacities, supply values, and costs) must
+  /// \warning Both number types must be signed and all input data must
   /// be integer.
-  /// \warning This algorithm does not support negative costs for
-  /// arcs having infinite upper bound.
+  /// \warning This algorithm does not support negative costs for such
+  /// arcs that have infinite upper bound.
   ///
   /// \note %CostScaling provides three different internal methods,
@@ -183,5 +179,5 @@
     /// relabel operation.
     /// By default, the so called \ref PARTIAL_AUGMENT
-    /// "Partial Augment-Relabel" method is used, which turned out to be
+    /// "Partial Augment-Relabel" method is used, which proved to be
     /// the most efficient and the most robust on various test inputs.
     /// However, the other methods can be selected using the \ref run()
@@ -238,4 +234,5 @@
     };
 
+    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
     typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 
@@ -288,4 +285,12 @@
     int _max_rank;
 
+    // Data for a StaticDigraph structure
+    typedef std::pair<int, int> IntPair;
+    StaticDigraph _sgr;
+    std::vector<IntPair> _arc_vec;
+    std::vector<LargeCost> _cost_vec;
+    LargeCostArcMap _cost_map;
+    LargeCostNodeMap _pi_map;
+
   public:
 
@@ -334,4 +339,5 @@
     CostScaling(const GR& graph) :
       _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
+      _cost_map(_cost_vec), _pi_map(_pi),
       INF(std::numeric_limits<Value>::has_infinity ?
           std::numeric_limits<Value>::infinity() :
@@ -442,5 +448,5 @@
     ///
     /// Using this function has the same effect as using \ref supplyMap()
-    /// with a map in which \c k is assigned to \c s, \c -k is
+    /// with such a map in which \c k is assigned to \c s, \c -k is
     /// assigned to \c t and all other nodes have zero supply value.
     ///
@@ -488,5 +494,5 @@
     /// \param method The internal method that will be used in the
     /// algorithm. For more information, see \ref Method.
-    /// \param factor The cost scaling factor. It must be at least two.
+    /// \param factor The cost scaling factor. It must be larger than one.
     ///
     /// \return \c INFEASIBLE if no feasible flow exists,
@@ -502,6 +508,5 @@
     /// \see ProblemType, Method
     /// \see resetParams(), reset()
-    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
-      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
       _alpha = factor;
       ProblemType pt = init();
@@ -567,23 +572,16 @@
     }
 
-    /// \brief Reset the internal data structures and all the parameters
-    /// that have been given before.
-    ///
-    /// This function resets the internal data structures and all the
-    /// paramaters that have been given before using functions \ref lowerMap(),
-    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
-    ///
-    /// It is useful for multiple \ref run() calls. By default, all the given
-    /// parameters are kept for the next \ref run() call, unless
-    /// \ref resetParams() or \ref reset() is used.
-    /// If the underlying digraph was also modified after the construction
-    /// of the class or the last \ref reset() call, then the \ref reset()
-    /// function must be used, otherwise \ref resetParams() is sufficient.
-    ///
-    /// See \ref resetParams() for examples.
-    ///
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
     /// \return <tt>(*this)</tt>
-    ///
-    /// \see resetParams(), run()
     CostScaling& reset() {
       // Resize vectors
@@ -610,4 +608,7 @@
       _excess.resize(_res_node_num);
       _next_out.resize(_res_node_num);
+
+      _arc_vec.reserve(_res_arc_num);
+      _cost_vec.reserve(_res_arc_num);
 
       // Copy the graph
@@ -886,4 +887,12 @@
       }
 
+      return OPTIMAL;
+    }
+
+    // Execute the algorithm and transform the results
+    void start(Method method) {
+      // Maximum path length for partial augment
+      const int MAX_PATH_LENGTH = 4;
+
       // Initialize data structures for buckets
       _max_rank = _alpha * _res_node_num;
@@ -893,11 +902,5 @@
       _rank.resize(_res_node_num + 1);
 
-      return OPTIMAL;
-    }
-
-    // Execute the algorithm and transform the results
-    void start(Method method) {
-      const int MAX_PARTIAL_PATH_LENGTH = 4;
-
+      // Execute the algorithm
       switch (method) {
         case PUSH:
@@ -908,65 +911,24 @@
           break;
         case PARTIAL_AUGMENT:
-          startAugment(MAX_PARTIAL_PATH_LENGTH);
+          startAugment(MAX_PATH_LENGTH);
           break;
       }
 
-      // Compute node potentials (dual solution)
-      for (int i = 0; i != _res_node_num; ++i) {
-        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
-      }
-      bool optimal = true;
-      for (int i = 0; optimal && i != _res_node_num; ++i) {
-        LargeCost pi_i = _pi[i];
-        int last_out = _first_out[i+1];
-        for (int j = _first_out[i]; j != last_out; ++j) {
-          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
-            optimal = false;
-            break;
-          }
-        }
-      }
-
-      if (!optimal) {
-        // Compute node potentials for the original costs with BellmanFord
-        // (if it is necessary)
-        typedef std::pair<int, int> IntPair;
-        StaticDigraph sgr;
-        std::vector<IntPair> arc_vec;
-        std::vector<LargeCost> cost_vec;
-        LargeCostArcMap cost_map(cost_vec);
-
-        arc_vec.clear();
-        cost_vec.clear();
-        for (int j = 0; j != _res_arc_num; ++j) {
-          if (_res_cap[j] > 0) {
-            int u = _source[j], v = _target[j];
-            arc_vec.push_back(IntPair(u, v));
-            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
-          }
-        }
-        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
-
-        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
-          bf(sgr, cost_map);
-        bf.init(0);
-        bf.start();
-
-        for (int i = 0; i != _res_node_num; ++i) {
-          _pi[i] += bf.dist(sgr.node(i));
-        }
-      }
-
-      // Shift potentials to meet the requirements of the GEQ type
-      // optimality conditions
-      LargeCost max_pot = _pi[_root];
-      for (int i = 0; i != _res_node_num; ++i) {
-        if (_pi[i] > max_pot) max_pot = _pi[i];
-      }
-      if (max_pot != 0) {
-        for (int i = 0; i != _res_node_num; ++i) {
-          _pi[i] -= max_pot;
-        }
-      }
+      // Compute node potentials for the original costs
+      _arc_vec.clear();
+      _cost_vec.clear();
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_res_cap[j] > 0) {
+          _arc_vec.push_back(IntPair(_source[j], _target[j]));
+          _cost_vec.push_back(_scost[j]);
+        }
+      }
+      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+
+      typename BellmanFord<StaticDigraph, LargeCostArcMap>
+        ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
+      bf.distMap(_pi_map);
+      bf.init(0);
+      bf.start();
 
       // Handle non-zero lower bounds
@@ -986,13 +948,11 @@
         LargeCost pi_u = _pi[u];
         for (int a = _first_out[u]; a != last_out; ++a) {
-          Value delta = _res_cap[a];
-          if (delta > 0) {
-            int v = _target[a];
-            if (_cost[a] + pi_u - _pi[v] < 0) {
-              _excess[u] -= delta;
-              _excess[v] += delta;
-              _res_cap[a] = 0;
-              _res_cap[_reverse[a]] += delta;
-            }
+          int v = _target[a];
+          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
+            Value delta = _res_cap[a];
+            _excess[u] -= delta;
+            _excess[v] += delta;
+            _res_cap[a] = 0;
+            _res_cap[_reverse[a]] += delta;
           }
         }
@@ -1010,232 +970,33 @@
     }
 
-    // Price (potential) refinement heuristic
-    bool priceRefinement() {
-
-      // Stack for stroing the topological order
-      IntVector stack(_res_node_num);
-      int stack_top;
-
-      // Perform phases
-      while (topologicalSort(stack, stack_top)) {
-
-        // Compute node ranks in the acyclic admissible network and
-        // store the nodes in buckets
-        for (int i = 0; i != _res_node_num; ++i) {
-          _rank[i] = 0;
-        }
-        const int bucket_end = _root + 1;
-        for (int r = 0; r != _max_rank; ++r) {
-          _buckets[r] = bucket_end;
-        }
-        int top_rank = 0;
-        for ( ; stack_top >= 0; --stack_top) {
-          int u = stack[stack_top], v;
-          int rank_u = _rank[u];
-
-          LargeCost rc, pi_u = _pi[u];
-          int last_out = _first_out[u+1];
-          for (int a = _first_out[u]; a != last_out; ++a) {
-            if (_res_cap[a] > 0) {
-              v = _target[a];
-              rc = _cost[a] + pi_u - _pi[v];
-              if (rc < 0) {
-                LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
-                if (nrc < LargeCost(_max_rank)) {
-                  int new_rank_v = rank_u + static_cast<int>(nrc);
-                  if (new_rank_v > _rank[v]) {
-                    _rank[v] = new_rank_v;
-                  }
-                }
-              }
-            }
-          }
-
-          if (rank_u > 0) {
-            top_rank = std::max(top_rank, rank_u);
-            int bfirst = _buckets[rank_u];
-            _bucket_next[u] = bfirst;
-            _bucket_prev[bfirst] = u;
-            _buckets[rank_u] = u;
-          }
-        }
-
-        // Check if the current flow is epsilon-optimal
-        if (top_rank == 0) {
-          return true;
-        }
-
-        // Process buckets in top-down order
-        for (int rank = top_rank; rank > 0; --rank) {
-          while (_buckets[rank] != bucket_end) {
-            // Remove the first node from the current bucket
-            int u = _buckets[rank];
-            _buckets[rank] = _bucket_next[u];
-
-            // Search the outgoing arcs of u
-            LargeCost rc, pi_u = _pi[u];
-            int last_out = _first_out[u+1];
-            int v, old_rank_v, new_rank_v;
-            for (int a = _first_out[u]; a != last_out; ++a) {
-              if (_res_cap[a] > 0) {
-                v = _target[a];
-                old_rank_v = _rank[v];
-
-                if (old_rank_v < rank) {
-
-                  // Compute the new rank of node v
-                  rc = _cost[a] + pi_u - _pi[v];
-                  if (rc < 0) {
-                    new_rank_v = rank;
-                  } else {
-                    LargeCost nrc = rc / _epsilon;
-                    new_rank_v = 0;
-                    if (nrc < LargeCost(_max_rank)) {
-                      new_rank_v = rank - 1 - static_cast<int>(nrc);
-                    }
-                  }
-
-                  // Change the rank of node v
-                  if (new_rank_v > old_rank_v) {
-                    _rank[v] = new_rank_v;
-
-                    // Remove v from its old bucket
-                    if (old_rank_v > 0) {
-                      if (_buckets[old_rank_v] == v) {
-                        _buckets[old_rank_v] = _bucket_next[v];
-                      } else {
-                        int pv = _bucket_prev[v], nv = _bucket_next[v];
-                        _bucket_next[pv] = nv;
-                        _bucket_prev[nv] = pv;
-                      }
-                    }
-
-                    // Insert v into its new bucket
-                    int nv = _buckets[new_rank_v];
-                    _bucket_next[v] = nv;
-                    _bucket_prev[nv] = v;
-                    _buckets[new_rank_v] = v;
-                  }
-                }
-              }
-            }
-
-            // Refine potential of node u
-            _pi[u] -= rank * _epsilon;
-          }
-        }
-
-      }
-
-      return false;
-    }
-
-    // Find and cancel cycles in the admissible network and
-    // determine topological order using DFS
-    bool topologicalSort(IntVector &stack, int &stack_top) {
-      const int MAX_CYCLE_CANCEL = 1;
-
-      BoolVector reached(_res_node_num, false);
-      BoolVector processed(_res_node_num, false);
-      IntVector pred(_res_node_num);
-      for (int i = 0; i != _res_node_num; ++i) {
-        _next_out[i] = _first_out[i];
-      }
-      stack_top = -1;
-
-      int cycle_cnt = 0;
-      for (int start = 0; start != _res_node_num; ++start) {
-        if (reached[start]) continue;
-
-        // Start DFS search from this start node
-        pred[start] = -1;
-        int tip = start, v;
-        while (true) {
-          // Check the outgoing arcs of the current tip node
-          reached[tip] = true;
-          LargeCost pi_tip = _pi[tip];
-          int a, last_out = _first_out[tip+1];
-          for (a = _next_out[tip]; a != last_out; ++a) {
-            if (_res_cap[a] > 0) {
-              v = _target[a];
-              if (_cost[a] + pi_tip - _pi[v] < 0) {
-                if (!reached[v]) {
-                  // A new node is reached
-                  reached[v] = true;
-                  pred[v] = tip;
-                  _next_out[tip] = a;
-                  tip = v;
-                  a = _next_out[tip];
-                  last_out = _first_out[tip+1];
-                  break;
-                }
-                else if (!processed[v]) {
-                  // A cycle is found
-                  ++cycle_cnt;
-                  _next_out[tip] = a;
-
-                  // Find the minimum residual capacity along the cycle
-                  Value d, delta = _res_cap[a];
-                  int u, delta_node = tip;
-                  for (u = tip; u != v; ) {
-                    u = pred[u];
-                    d = _res_cap[_next_out[u]];
-                    if (d <= delta) {
-                      delta = d;
-                      delta_node = u;
-                    }
-                  }
-
-                  // Augment along the cycle
-                  _res_cap[a] -= delta;
-                  _res_cap[_reverse[a]] += delta;
-                  for (u = tip; u != v; ) {
-                    u = pred[u];
-                    int ca = _next_out[u];
-                    _res_cap[ca] -= delta;
-                    _res_cap[_reverse[ca]] += delta;
-                  }
-
-                  // Check the maximum number of cycle canceling
-                  if (cycle_cnt >= MAX_CYCLE_CANCEL) {
-                    return false;
-                  }
-
-                  // Roll back search to delta_node
-                  if (delta_node != tip) {
-                    for (u = tip; u != delta_node; u = pred[u]) {
-                      reached[u] = false;
-                    }
-                    tip = delta_node;
-                    a = _next_out[tip] + 1;
-                    last_out = _first_out[tip+1];
-                    break;
-                  }
-                }
-              }
-            }
-          }
-
-          // Step back to the previous node
-          if (a == last_out) {
-            processed[tip] = true;
-            stack[++stack_top] = tip;
-            tip = pred[tip];
-            if (tip < 0) {
-              // Finish DFS from the current start node
-              break;
-            }
-            ++_next_out[tip];
-          }
-        }
-
-      }
-
-      return (cycle_cnt == 0);
+    // Early termination heuristic
+    bool earlyTermination() {
+      const double EARLY_TERM_FACTOR = 3.0;
+
+      // Build a static residual graph
+      _arc_vec.clear();
+      _cost_vec.clear();
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_res_cap[j] > 0) {
+          _arc_vec.push_back(IntPair(_source[j], _target[j]));
+          _cost_vec.push_back(_cost[j] + 1);
+        }
+      }
+      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+
+      // Run Bellman-Ford algorithm to check if the current flow is optimal
+      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
+      bf.init(0);
+      bool done = false;
+      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
+      for (int i = 0; i < K && !done; ++i) {
+        done = bf.processNextWeakRound();
+      }
+      return done;
     }
 
     // Global potential update heuristic
     void globalUpdate() {
-      const int bucket_end = _root + 1;
+      int bucket_end = _root + 1;
 
       // Initialize buckets
@@ -1244,11 +1005,10 @@
       }
       Value total_excess = 0;
-      int b0 = bucket_end;
       for (int i = 0; i != _res_node_num; ++i) {
         if (_excess[i] < 0) {
           _rank[i] = 0;
-          _bucket_next[i] = b0;
-          _bucket_prev[b0] = i;
-          b0 = i;
+          _bucket_next[i] = _buckets[0];
+          _bucket_prev[_buckets[0]] = i;
+          _buckets[0] = i;
         } else {
           total_excess += _excess[i];
@@ -1257,5 +1017,4 @@
       }
       if (total_excess == 0) return;
-      _buckets[0] = b0;
 
       // Search the buckets
@@ -1279,7 +1038,6 @@
                 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
                 int new_rank_v = old_rank_v;
-                if (nrc < LargeCost(_max_rank)) {
-                  new_rank_v = r + 1 + static_cast<int>(nrc);
-                }
+                if (nrc < LargeCost(_max_rank))
+                  new_rank_v = r + 1 + int(nrc);
 
                 // Change the rank of v
@@ -1293,14 +1051,12 @@
                       _buckets[old_rank_v] = _bucket_next[v];
                     } else {
-                      int pv = _bucket_prev[v], nv = _bucket_next[v];
-                      _bucket_next[pv] = nv;
-                      _bucket_prev[nv] = pv;
+                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
+                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
                     }
                   }
 
-                  // Insert v into its new bucket
-                  int nv = _buckets[new_rank_v];
-                  _bucket_next[v] = nv;
-                  _bucket_prev[nv] = v;
+                  // Insert v to its new bucket
+                  _bucket_next[v] = _buckets[new_rank_v];
+                  _bucket_prev[_buckets[new_rank_v]] = v;
                   _buckets[new_rank_v] = v;
                 }
@@ -1331,23 +1087,21 @@
     void startAugment(int max_length) {
       // Paramters for heuristics
-      const int PRICE_REFINEMENT_LIMIT = 2;
-      const double GLOBAL_UPDATE_FACTOR = 1.0;
-      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 3.0;
+
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
         (_res_node_num + _sup_node_num * _sup_node_num));
-      int next_global_update_limit = global_update_skip;
+      int next_update_limit = global_update_freq;
+
+      int relabel_cnt = 0;
 
       // Perform cost scaling phases
-      IntVector path;
-      BoolVector path_arc(_res_arc_num, false);
-      int relabel_cnt = 0;
-      int eps_phase_cnt = 0;
+      std::vector<int> path;
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
                                         1 : _epsilon / _alpha )
       {
-        ++eps_phase_cnt;
-
-        // Price refinement heuristic
-        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
-          if (priceRefinement()) continue;
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
         }
 
@@ -1366,43 +1120,30 @@
 
           // Find an augmenting path from the start node
+          path.clear();
           int tip = start;
-          while (int(path.size()) < max_length && _excess[tip] >= 0) {
+          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
             int u;
-            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
-            LargeCost pi_tip = _pi[tip];
+            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
             int last_out = _first_out[tip+1];
             for (int a = _next_out[tip]; a != last_out; ++a) {
-              if (_res_cap[a] > 0) {
-                u = _target[a];
-                rc = _cost[a] + pi_tip - _pi[u];
-                if (rc < 0) {
-                  path.push_back(a);
-                  _next_out[tip] = a;
-                  if (path_arc[a]) {
-                    goto augment;   // a cycle is found, stop path search
-                  }
-                  tip = u;
-                  path_arc[a] = true;
-                  goto next_step;
-                }
-                else if (rc < min_red_cost) {
-                  min_red_cost = rc;
-                }
+              u = _target[a];
+              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
+                path.push_back(a);
+                _next_out[tip] = a;
+                tip = u;
+                goto next_step;
               }
             }
 
             // Relabel tip node
+            min_red_cost = std::numeric_limits<LargeCost>::max();
             if (tip != start) {
               int ra = _reverse[path.back()];
-              min_red_cost =
-                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
+              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
             }
-            last_out = _next_out[tip];
             for (int a = _first_out[tip]; a != last_out; ++a) {
-              if (_res_cap[a] > 0) {
-                rc = _cost[a] + pi_tip - _pi[_target[a]];
-                if (rc < min_red_cost) {
-                  min_red_cost = rc;
-                }
+              rc = _cost[a] + pi_tip - _pi[_target[a]];
+              if (_res_cap[a] > 0 && rc < min_red_cost) {
+                min_red_cost = rc;
               }
             }
@@ -1413,7 +1154,5 @@
             // Step back
             if (tip != start) {
-              int pa = path.back();
-              path_arc[pa] = false;
-              tip = _source[pa];
+              tip = _source[path.back()];
               path.pop_back();
             }
@@ -1423,5 +1162,4 @@
 
           // Augment along the found path (as much flow as possible)
-        augment:
           Value delta;
           int pa, u, v = start;
@@ -1430,5 +1168,4 @@
             u = v;
             v = _target[pa];
-            path_arc[pa] = false;
             delta = std::min(_res_cap[pa], _excess[u]);
             _res_cap[pa] -= delta;
@@ -1436,19 +1173,15 @@
             _excess[u] -= delta;
             _excess[v] += delta;
-            if (_excess[v] > 0 && _excess[v] <= delta) {
+            if (_excess[v] > 0 && _excess[v] <= delta)
               _active_nodes.push_back(v);
-            }
           }
-          path.clear();
 
           // Global update heuristic
-          if (relabel_cnt >= next_global_update_limit) {
+          if (relabel_cnt >= next_update_limit) {
             globalUpdate();
-            next_global_update_limit += global_update_skip;
+            next_update_limit += global_update_freq;
           }
         }
-
-      }
-
+      }
     }
 
@@ -1456,24 +1189,22 @@
     void startPush() {
       // Paramters for heuristics
-      const int PRICE_REFINEMENT_LIMIT = 2;
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
       const double GLOBAL_UPDATE_FACTOR = 2.0;
 
-      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
         (_res_node_num + _sup_node_num * _sup_node_num));
-      int next_global_update_limit = global_update_skip;
+      int next_update_limit = global_update_freq;
+
+      int relabel_cnt = 0;
 
       // Perform cost scaling phases
       BoolVector hyper(_res_node_num, false);
       LargeCostVector hyper_cost(_res_node_num);
-      int relabel_cnt = 0;
-      int eps_phase_cnt = 0;
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
                                         1 : _epsilon / _alpha )
       {
-        ++eps_phase_cnt;
-
-        // Price refinement heuristic
-        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
-          if (priceRefinement()) continue;
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
         }
 
@@ -1547,9 +1278,7 @@
                std::numeric_limits<LargeCost>::max();
             for (int a = _first_out[n]; a != last_out; ++a) {
-              if (_res_cap[a] > 0) {
-                rc = _cost[a] + pi_n - _pi[_target[a]];
-                if (rc < min_red_cost) {
-                  min_red_cost = rc;
-                }
+              rc = _cost[a] + pi_n - _pi[_target[a]];
+              if (_res_cap[a] > 0 && rc < min_red_cost) {
+                min_red_cost = rc;
               }
             }
@@ -1569,9 +1298,9 @@
 
           // Global update heuristic
-          if (relabel_cnt >= next_global_update_limit) {
+          if (relabel_cnt >= next_update_limit) {
             globalUpdate();
             for (int u = 0; u != _res_node_num; ++u)
               hyper[u] = false;
-            next_global_update_limit += global_update_skip;
+            next_update_limit += global_update_freq;
           }
         }
Index: lemon/cycle_canceling.h
===================================================================
--- lemon/cycle_canceling.h	(revision 1026)
+++ lemon/cycle_canceling.h	(revision 956)
@@ -66,9 +66,8 @@
   /// algorithm. By default, it is the same as \c V.
   ///
-  /// \warning Both \c V and \c C must be signed number types.
-  /// \warning All input data (capacities, supply values, and costs) must
+  /// \warning Both number types must be signed and all input data must
   /// be integer.
-  /// \warning This algorithm does not support negative costs for
-  /// arcs having infinite upper bound.
+  /// \warning This algorithm does not support negative costs for such
+  /// arcs that have infinite upper bound.
   ///
   /// \note For more information about the three available methods,
@@ -118,5 +117,6 @@
     /// \ref CycleCanceling provides three different cycle-canceling
     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
-    /// is used, which is by far the most efficient and the most robust.
+    /// is used, which proved to be the most efficient and the most robust
+    /// on various test inputs.
     /// However, the other methods can be selected using the \ref run()
     /// function with the proper parameter.
@@ -350,5 +350,5 @@
     ///
     /// Using this function has the same effect as using \ref supplyMap()
-    /// with a map in which \c k is assigned to \c s, \c -k is
+    /// with such a map in which \c k is assigned to \c s, \c -k is
     /// assigned to \c t and all other nodes have zero supply value.
     ///
Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h	(revision 1010)
+++ lemon/dfs.h	(revision 956)
@@ -566,5 +566,5 @@
     void start(Node t)
     {
-      while ( !emptyQueue() && !(*_reached)[t] )
+      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
         processNextArc();
     }
@@ -1513,5 +1513,5 @@
     /// with addSource() before using this function.
     void start(Node t) {
-      while ( !emptyQueue() && !(*_reached)[t] )
+      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
         processNextArc();
     }
Index: lemon/euler.h
===================================================================
--- lemon/euler.h	(revision 1023)
+++ lemon/euler.h	(revision 956)
@@ -37,5 +37,5 @@
   ///Euler tour iterator for digraphs.
 
-  /// \ingroup graph_properties
+  /// \ingroup graph_prop
   ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
   ///graph (if there exists) and it converts to the \c Arc type of the digraph.
Index: mon/grosso_locatelli_pullan_mc.h
===================================================================
--- lemon/grosso_locatelli_pullan_mc.h	(revision 1022)
+++ 	(revision )
@@ -1,840 +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_GROSSO_LOCATELLI_PULLAN_MC_H
-#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
-
-/// \ingroup approx_algs
-///
-/// \file
-/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
-/// for the maximum clique problem
-
-#include <vector>
-#include <limits>
-#include <lemon/core.h>
-#include <lemon/random.h>
-
-namespace lemon {
-
-  /// \addtogroup approx_algs
-  /// @{
-
-  /// \brief Implementation of the iterated local search algorithm of Grosso,
-  /// Locatelli, and Pullan for the maximum clique problem
-  ///
-  /// \ref GrossoLocatelliPullanMc implements the iterated local search
-  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
-  /// \e clique \e problem \ref grosso08maxclique.
-  /// It is to find the largest complete subgraph (\e clique) in an
-  /// undirected graph, i.e., the largest set of nodes where each
-  /// pair of nodes is connected.
-  ///
-  /// This class provides a simple but highly efficient and robust heuristic
-  /// method that quickly finds a quite large clique, but not necessarily the
-  /// largest one.
-  /// The algorithm performs a certain number of iterations to find several
-  /// cliques and selects the largest one among them. Various limits can be
-  /// specified to control the running time and the effectiveness of the
-  /// search process.
-  ///
-  /// \tparam GR The undirected graph type the algorithm runs on.
-  ///
-  /// \note %GrossoLocatelliPullanMc provides three different node selection
-  /// rules, from which the most powerful one is used by default.
-  /// For more information, see \ref SelectionRule.
-  template <typename GR>
-  class GrossoLocatelliPullanMc
-  {
-  public:
-
-    /// \brief Constants for specifying the node selection rule.
-    ///
-    /// Enum type containing constants for specifying the node selection rule
-    /// for the \ref run() function.
-    ///
-    /// During the algorithm, nodes are selected for addition to the current
-    /// clique according to the applied rule.
-    /// In general, the PENALTY_BASED rule turned out to be the most powerful
-    /// and the most robust, thus it is the default option.
-    /// However, another selection rule can be specified using the \ref run()
-    /// function with the proper parameter.
-    enum SelectionRule {
-
-      /// A node is selected randomly without any evaluation at each step.
-      RANDOM,
-
-      /// A node of maximum degree is selected randomly at each step.
-      DEGREE_BASED,
-
-      /// A node of minimum penalty is selected randomly at each step.
-      /// The node penalties are updated adaptively after each stage of the
-      /// search process.
-      PENALTY_BASED
-    };
-
-    /// \brief Constants for the causes of search termination.
-    ///
-    /// Enum type containing constants for the different causes of search
-    /// termination. The \ref run() function returns one of these values.
-    enum TerminationCause {
-
-      /// The iteration count limit is reached.
-      ITERATION_LIMIT,
-
-      /// The step count limit is reached.
-      STEP_LIMIT,
-
-      /// The clique size limit is reached.
-      SIZE_LIMIT
-    };
-
-  private:
-
-    TEMPLATE_GRAPH_TYPEDEFS(GR);
-
-    typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
-    typedef std::vector<BoolVector> BoolMatrix;
-    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
-
-    // The underlying graph
-    const GR &_graph;
-    IntNodeMap _id;
-
-    // Internal matrix representation of the graph
-    BoolMatrix _gr;
-    int _n;
-    
-    // Search options
-    bool _delta_based_restart;
-    int _restart_delta_limit;
- 
-    // Search limits
-    int _iteration_limit;
-    int _step_limit;
-    int _size_limit;
-
-    // The current clique
-    BoolVector _clique;
-    int _size;
-
-    // The best clique found so far
-    BoolVector _best_clique;
-    int _best_size;
-
-    // The "distances" of the nodes from the current clique.
-    // _delta[u] is the number of nodes in the clique that are
-    // not connected with u.
-    IntVector _delta;
-
-    // The current tabu set
-    BoolVector _tabu;
-
-    // Random number generator
-    Random _rnd;
-
-  private:
-
-    // Implementation of the RANDOM node selection rule.
-    class RandomSelectionRule
-    {
-    private:
-
-      // References to the algorithm instance
-      const BoolVector &_clique;
-      const IntVector  &_delta;
-      const BoolVector &_tabu;
-      Random &_rnd;
-
-      // Pivot rule data
-      int _n;
-
-    public:
-
-      // Constructor
-      RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
-        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
-        _rnd(mc._rnd), _n(mc._n)
-      {}
-
-      // Return a node index for a feasible add move or -1 if no one exists
-      int nextFeasibleAddNode() const {
-        int start_node = _rnd[_n];
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0 && !_tabu[i]) return i;
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0 && !_tabu[i]) return i;
-        }
-        return -1;
-      }
-
-      // Return a node index for a feasible swap move or -1 if no one exists
-      int nextFeasibleSwapNode() const {
-        int start_node = _rnd[_n];
-        for (int i = start_node; i != _n; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
-        }
-        return -1;
-      }
-
-      // Return a node index for an add move or -1 if no one exists
-      int nextAddNode() const {
-        int start_node = _rnd[_n];
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0) return i;
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0) return i;
-        }
-        return -1;
-      }
-
-      // Update internal data structures between stages (if necessary)
-      void update() {}
-
-    }; //class RandomSelectionRule
-
-
-    // Implementation of the DEGREE_BASED node selection rule.
-    class DegreeBasedSelectionRule
-    {
-    private:
-
-      // References to the algorithm instance
-      const BoolVector &_clique;
-      const IntVector  &_delta;
-      const BoolVector &_tabu;
-      Random &_rnd;
-
-      // Pivot rule data
-      int _n;
-      IntVector _deg;
-
-    public:
-
-      // Constructor
-      DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
-        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
-        _rnd(mc._rnd), _n(mc._n), _deg(_n)
-      {
-        for (int i = 0; i != _n; i++) {
-          int d = 0;
-          BoolVector &row = mc._gr[i];
-          for (int j = 0; j != _n; j++) {
-            if (row[j]) d++;
-          }
-          _deg[i] = d;
-        }
-      }
-
-      // Return a node index for a feasible add move or -1 if no one exists
-      int nextFeasibleAddNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, max_deg = -1;
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        return node;
-      }
-
-      // Return a node index for a feasible swap move or -1 if no one exists
-      int nextFeasibleSwapNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, max_deg = -1;
-        for (int i = start_node; i != _n; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
-              _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
-              _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        return node;
-      }
-
-      // Return a node index for an add move or -1 if no one exists
-      int nextAddNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, max_deg = -1;
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0 && _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0 && _deg[i] > max_deg) {
-            node = i;
-            max_deg = _deg[i];
-          }
-        }
-        return node;
-      }
-
-      // Update internal data structures between stages (if necessary)
-      void update() {}
-
-    }; //class DegreeBasedSelectionRule
-
-
-    // Implementation of the PENALTY_BASED node selection rule.
-    class PenaltyBasedSelectionRule
-    {
-    private:
-
-      // References to the algorithm instance
-      const BoolVector &_clique;
-      const IntVector  &_delta;
-      const BoolVector &_tabu;
-      Random &_rnd;
-
-      // Pivot rule data
-      int _n;
-      IntVector _penalty;
-
-    public:
-
-      // Constructor
-      PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
-        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
-        _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
-      {}
-
-      // Return a node index for a feasible add move or -1 if no one exists
-      int nextFeasibleAddNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, min_p = std::numeric_limits<int>::max();
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        return node;
-      }
-
-      // Return a node index for a feasible swap move or -1 if no one exists
-      int nextFeasibleSwapNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, min_p = std::numeric_limits<int>::max();
-        for (int i = start_node; i != _n; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
-              _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
-              _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        return node;
-      }
-
-      // Return a node index for an add move or -1 if no one exists
-      int nextAddNode() const {
-        int start_node = _rnd[_n];
-        int node = -1, min_p = std::numeric_limits<int>::max();
-        for (int i = start_node; i != _n; i++) {
-          if (_delta[i] == 0 && _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        for (int i = 0; i != start_node; i++) {
-          if (_delta[i] == 0 && _penalty[i] < min_p) {
-            node = i;
-            min_p = _penalty[i];
-          }
-        }
-        return node;
-      }
-
-      // Update internal data structures between stages (if necessary)
-      void update() {}
-
-    }; //class PenaltyBasedSelectionRule
-
-  public:
-
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// The global \ref rnd "random number generator instance" is used
-    /// during the algorithm.
-    ///
-    /// \param graph The undirected graph the algorithm runs on.
-    GrossoLocatelliPullanMc(const GR& graph) :
-      _graph(graph), _id(_graph), _rnd(rnd)
-    {
-      initOptions();
-    }
-
-    /// \brief Constructor with random seed.
-    ///
-    /// Constructor with random seed.
-    ///
-    /// \param graph The undirected graph the algorithm runs on.
-    /// \param seed Seed value for the internal random number generator
-    /// that is used during the algorithm.
-    GrossoLocatelliPullanMc(const GR& graph, int seed) :
-      _graph(graph), _id(_graph), _rnd(seed)
-    {
-      initOptions();
-    }
-
-    /// \brief Constructor with random number generator.
-    ///
-    /// Constructor with random number generator.
-    ///
-    /// \param graph The undirected graph the algorithm runs on.
-    /// \param random A random number generator that is used during the
-    /// algorithm.
-    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
-      _graph(graph), _id(_graph), _rnd(random)
-    {
-      initOptions();
-    }
-
-    /// \name Execution Control
-    /// The \ref run() function can be used to execute the algorithm.\n
-    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and 
-    /// \ref sizeLimit(int) can be used to specify various limits for the
-    /// search process.
-    
-    /// @{
-    
-    /// \brief Sets the maximum number of iterations.
-    ///
-    /// This function sets the maximum number of iterations.
-    /// Each iteration of the algorithm finds a maximal clique (but not
-    /// necessarily the largest one) by performing several search steps
-    /// (node selections).
-    ///
-    /// This limit controls the running time and the success of the
-    /// algorithm. For larger values, the algorithm runs slower, but it more
-    /// likely finds larger cliques. For smaller values, the algorithm is
-    /// faster but probably gives worse results.
-    /// 
-    /// The default value is \c 1000.
-    /// \c -1 means that number of iterations is not limited.
-    ///
-    /// \warning You should specify a reasonable limit for the number of
-    /// iterations and/or the number of search steps.
-    ///
-    /// \return <tt>(*this)</tt>
-    ///
-    /// \sa stepLimit(int)
-    /// \sa sizeLimit(int)
-    GrossoLocatelliPullanMc& iterationLimit(int limit) {
-      _iteration_limit = limit;
-      return *this;
-    }
-    
-    /// \brief Sets the maximum number of search steps.
-    ///
-    /// This function sets the maximum number of elementary search steps.
-    /// Each iteration of the algorithm finds a maximal clique (but not
-    /// necessarily the largest one) by performing several search steps
-    /// (node selections).
-    ///
-    /// This limit controls the running time and the success of the
-    /// algorithm. For larger values, the algorithm runs slower, but it more
-    /// likely finds larger cliques. For smaller values, the algorithm is
-    /// faster but probably gives worse results.
-    /// 
-    /// The default value is \c -1, which means that number of steps
-    /// is not limited explicitly. However, the number of iterations is
-    /// limited and each iteration performs a finite number of search steps.
-    ///
-    /// \warning You should specify a reasonable limit for the number of
-    /// iterations and/or the number of search steps.
-    ///
-    /// \return <tt>(*this)</tt>
-    ///
-    /// \sa iterationLimit(int)
-    /// \sa sizeLimit(int)
-    GrossoLocatelliPullanMc& stepLimit(int limit) {
-      _step_limit = limit;
-      return *this;
-    }
-    
-    /// \brief Sets the desired clique size.
-    ///
-    /// This function sets the desired clique size that serves as a search
-    /// limit. If a clique of this size (or a larger one) is found, then the
-    /// algorithm terminates.
-    /// 
-    /// This function is especially useful if you know an exact upper bound
-    /// for the size of the cliques in the graph or if any clique above 
-    /// a certain size limit is sufficient for your application.
-    /// 
-    /// The default value is \c -1, which means that the size limit is set to
-    /// the number of nodes in the graph.
-    ///
-    /// \return <tt>(*this)</tt>
-    ///
-    /// \sa iterationLimit(int)
-    /// \sa stepLimit(int)
-    GrossoLocatelliPullanMc& sizeLimit(int limit) {
-      _size_limit = limit;
-      return *this;
-    }
-    
-    /// \brief The maximum number of iterations.
-    ///
-    /// This function gives back the maximum number of iterations.
-    /// \c -1 means that no limit is specified.
-    ///
-    /// \sa iterationLimit(int)
-    int iterationLimit() const {
-      return _iteration_limit;
-    }
-    
-    /// \brief The maximum number of search steps.
-    ///
-    /// This function gives back the maximum number of search steps.
-    /// \c -1 means that no limit is specified.
-    ///
-    /// \sa stepLimit(int)
-    int stepLimit() const {
-      return _step_limit;
-    }
-    
-    /// \brief The desired clique size.
-    ///
-    /// This function gives back the desired clique size that serves as a
-    /// search limit. \c -1 means that this limit is set to the number of
-    /// nodes in the graph.
-    ///
-    /// \sa sizeLimit(int)
-    int sizeLimit() const {
-      return _size_limit;
-    }
-
-    /// \brief Runs the algorithm.
-    ///
-    /// This function runs the algorithm. If one of the specified limits
-    /// is reached, the search process terminates.
-    ///
-    /// \param rule The node selection rule. For more information, see
-    /// \ref SelectionRule.
-    ///
-    /// \return The termination cause of the search. For more information,
-    /// see \ref TerminationCause.
-    TerminationCause run(SelectionRule rule = PENALTY_BASED)
-    {
-      init();
-      switch (rule) {
-        case RANDOM:
-          return start<RandomSelectionRule>();
-        case DEGREE_BASED:
-          return start<DegreeBasedSelectionRule>();
-        default:
-          return start<PenaltyBasedSelectionRule>();
-      }
-    }
-
-    /// @}
-
-    /// \name Query Functions
-    /// The results of the algorithm can be obtained using these functions.\n
-    /// The run() function must be called before using them. 
-
-    /// @{
-
-    /// \brief The size of the found clique
-    ///
-    /// This function returns the size of the found clique.
-    ///
-    /// \pre run() must be called before using this function.
-    int cliqueSize() const {
-      return _best_size;
-    }
-
-    /// \brief Gives back the found clique in a \c bool node map
-    ///
-    /// This function gives back the characteristic vector of the found
-    /// clique in the given node map.
-    /// It must be a \ref concepts::WriteMap "writable" node map with
-    /// \c bool (or convertible) value type.
-    ///
-    /// \pre run() must be called before using this function.
-    template <typename CliqueMap>
-    void cliqueMap(CliqueMap &map) const {
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-        map[n] = static_cast<bool>(_best_clique[_id[n]]);
-      }
-    }
-
-    /// \brief Iterator to list the nodes of the found clique
-    ///
-    /// This iterator class lists the nodes of the found clique.
-    /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
-    /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
-    ///
-    /// The following example prints out the IDs of the nodes in the found
-    /// clique.
-    /// \code
-    ///   GrossoLocatelliPullanMc<Graph> mc(g);
-    ///   mc.run();
-    ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
-    ///        n != INVALID; ++n)
-    ///   {
-    ///     std::cout << g.id(n) << std::endl;
-    ///   }
-    /// \endcode
-    class CliqueNodeIt
-    {
-    private:
-      NodeIt _it;
-      BoolNodeMap _map;
-
-    public:
-
-      /// Constructor
-
-      /// Constructor.
-      /// \param mc The algorithm instance.
-      CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
-       : _map(mc._graph)
-      {
-        mc.cliqueMap(_map);
-        for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
-      }
-
-      /// Conversion to \c Node
-      operator Node() const { return _it; }
-
-      bool operator==(Invalid) const { return _it == INVALID; }
-      bool operator!=(Invalid) const { return _it != INVALID; }
-
-      /// Next node
-      CliqueNodeIt &operator++() {
-        for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
-        return *this;
-      }
-
-      /// Postfix incrementation
-
-      /// Postfix incrementation.
-      ///
-      /// \warning This incrementation returns a \c Node, not a
-      /// \c CliqueNodeIt as one may expect.
-      typename GR::Node operator++(int) {
-        Node n=*this;
-        ++(*this);
-        return n;
-      }
-
-    };
-
-    /// @}
-
-  private:
-  
-    // Initialize search options and limits
-    void initOptions() {
-      // Search options
-      _delta_based_restart = true;
-      _restart_delta_limit = 4;
-     
-      // Search limits
-      _iteration_limit = 1000;
-      _step_limit = -1;             // this is disabled by default
-      _size_limit = -1;             // this is disabled by default
-    }
-
-    // Adds a node to the current clique
-    void addCliqueNode(int u) {
-      if (_clique[u]) return;
-      _clique[u] = true;
-      _size++;
-      BoolVector &row = _gr[u];
-      for (int i = 0; i != _n; i++) {
-        if (!row[i]) _delta[i]++;
-      }
-    }
-
-    // Removes a node from the current clique
-    void delCliqueNode(int u) {
-      if (!_clique[u]) return;
-      _clique[u] = false;
-      _size--;
-      BoolVector &row = _gr[u];
-      for (int i = 0; i != _n; i++) {
-        if (!row[i]) _delta[i]--;
-      }
-    }
-
-    // Initialize data structures
-    void init() {
-      _n = countNodes(_graph);
-      int ui = 0;
-      for (NodeIt u(_graph); u != INVALID; ++u) {
-        _id[u] = ui++;
-      }
-      _gr.clear();
-      _gr.resize(_n, BoolVector(_n, false));
-      ui = 0;
-      for (NodeIt u(_graph); u != INVALID; ++u) {
-        for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
-          int vi = _id[_graph.runningNode(e)];
-          _gr[ui][vi] = true;
-          _gr[vi][ui] = true;
-        }
-        ++ui;
-      }
-
-      _clique.clear();
-      _clique.resize(_n, false);
-      _size = 0;
-      _best_clique.clear();
-      _best_clique.resize(_n, false);
-      _best_size = 0;
-      _delta.clear();
-      _delta.resize(_n, 0);
-      _tabu.clear();
-      _tabu.resize(_n, false);
-    }
-
-    // Executes the algorithm
-    template <typename SelectionRuleImpl>
-    TerminationCause start() {
-      if (_n == 0) return SIZE_LIMIT;
-      if (_n == 1) {
-        _best_clique[0] = true;
-        _best_size = 1;
-        return SIZE_LIMIT;
-      }
-
-      // Iterated local search algorithm
-      const int max_size = _size_limit >= 0 ? _size_limit : _n;
-      const int max_restart = _iteration_limit >= 0 ?
-        _iteration_limit : std::numeric_limits<int>::max();
-      const int max_select = _step_limit >= 0 ?
-        _step_limit : std::numeric_limits<int>::max();
-
-      SelectionRuleImpl sel_method(*this);
-      int select = 0, restart = 0;
-      IntVector restart_nodes;
-      while (select < max_select && restart < max_restart) {
-
-        // Perturbation/restart
-        restart++;
-        if (_delta_based_restart) {
-          restart_nodes.clear();
-          for (int i = 0; i != _n; i++) {
-            if (_delta[i] >= _restart_delta_limit)
-              restart_nodes.push_back(i);
-          }
-        }
-        int rs_node = -1;
-        if (restart_nodes.size() > 0) {
-          rs_node = restart_nodes[_rnd[restart_nodes.size()]];
-        } else {
-          rs_node = _rnd[_n];
-        }
-        BoolVector &row = _gr[rs_node];
-        for (int i = 0; i != _n; i++) {
-          if (_clique[i] && !row[i]) delCliqueNode(i);
-        }
-        addCliqueNode(rs_node);
-
-        // Local search
-        _tabu.clear();
-        _tabu.resize(_n, false);
-        bool tabu_empty = true;
-        int max_swap = _size;
-        while (select < max_select) {
-          select++;
-          int u;
-          if ((u = sel_method.nextFeasibleAddNode()) != -1) {
-            // Feasible add move
-            addCliqueNode(u);
-            if (tabu_empty) max_swap = _size;
-          }
-          else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
-            // Feasible swap move
-            int v = -1;
-            BoolVector &row = _gr[u];
-            for (int i = 0; i != _n; i++) {
-              if (_clique[i] && !row[i]) {
-                v = i;
-                break;
-              }
-            }
-            addCliqueNode(u);
-            delCliqueNode(v);
-            _tabu[v] = true;
-            tabu_empty = false;
-            if (--max_swap <= 0) break;
-          }
-          else if ((u = sel_method.nextAddNode()) != -1) {
-            // Non-feasible add move
-            addCliqueNode(u);
-          }
-          else break;
-        }
-        if (_size > _best_size) {
-          _best_clique = _clique;
-          _best_size = _size;
-          if (_best_size >= max_size) return SIZE_LIMIT;
-        }
-        sel_method.update();
-      }
-
-      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
-    }
-
-  }; //class GrossoLocatelliPullanMc
-
-  ///@}
-
-} //namespace lemon
-
-#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_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: lemon/hartmann_orlin_mmc.h
===================================================================
--- lemon/hartmann_orlin_mmc.h	(revision 959)
+++ lemon/hartmann_orlin_mmc.h	(revision 956)
@@ -39,5 +39,5 @@
   /// \tparam GR The type of the digraph.
   /// \tparam CM The type of the cost map.
-  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
 #ifdef DOXYGEN
   template <typename GR, typename CM>
@@ -100,5 +100,5 @@
   /// a directed cycle of minimum mean cost in a digraph
   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
-  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
+  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
   /// it applies an efficient early termination scheme.
   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
Index: lemon/kruskal.h
===================================================================
--- lemon/kruskal.h	(revision 1025)
+++ lemon/kruskal.h	(revision 631)
@@ -31,4 +31,7 @@
 ///\file
 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree
+///
+///Kruskal's algorithm to compute a minimum cost spanning tree.
+///
 
 namespace lemon {
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/maps.h
===================================================================
--- lemon/maps.h	(revision 956)
+++ lemon/maps.h	(revision 1057)
@@ -3253,5 +3253,5 @@
     virtual void add(const Key& key) {
       Parent::add(key);
-      unlace(key);
+      lace(key);
     }
 
Index: mon/max_cardinality_search.h
===================================================================
--- lemon/max_cardinality_search.h	(revision 1020)
+++ 	(revision )
@@ -1,786 +1,0 @@
-/* -*- 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: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 1026)
+++ lemon/network_simplex.h	(revision 956)
@@ -48,8 +48,8 @@
   /// flow problem.
   ///
-  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
-  /// implementations available in LEMON for this problem.
-  /// Furthermore, this class supports both directions of the supply/demand
-  /// inequality constraints. For more information, see \ref SupplyType.
+  /// In general, %NetworkSimplex is the fastest implementation available
+  /// in LEMON for this problem.
+  /// Moreover, it supports both directions of the supply/demand inequality
+  /// constraints. For more information, see \ref SupplyType.
   ///
   /// Most of the parameters of the problem (except for the digraph)
@@ -64,6 +64,5 @@
   /// algorithm. By default, it is the same as \c V.
   ///
-  /// \warning Both \c V and \c C must be signed number types.
-  /// \warning All input data (capacities, supply values, and costs) must
+  /// \warning Both number types must be signed and all input data must
   /// be integer.
   ///
@@ -127,5 +126,5 @@
     /// of the algorithm.
     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
-    /// turend out to be the most efficient and the most robust on various
+    /// proved to be the most efficient and the most robust on various
     /// test inputs.
     /// However, another pivot rule can be selected using the \ref run()
@@ -168,7 +167,6 @@
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
-    typedef std::vector<signed char> CharVector;
-    // Note: vector<signed char> is used instead of vector<ArcState> and
-    // vector<ArcDirection> for efficiency reasons
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 
     // State constants for arcs
@@ -179,9 +177,7 @@
     };
 
-    // Direction constants for tree arcs
-    enum ArcDirection {
-      DIR_DOWN = -1,
-      DIR_UP   =  1
-    };
+    typedef std::vector<signed char> StateVector;
+    // Note: vector<signed char> is used instead of vector<ArcState> for
+    // efficiency reasons
 
   private:
@@ -222,11 +218,13 @@
     IntVector _succ_num;
     IntVector _last_succ;
-    CharVector _pred_dir;
-    CharVector _state;
     IntVector _dirty_revs;
+    BoolVector _forward;
+    StateVector _state;
     int _root;
 
     // Temporary data used in the current pivot iteration
     int in_arc, join, u_in, v_in, u_out, v_out;
+    int first, second, right, last;
+    int stem, par_stem, new_stem;
     Value delta;
 
@@ -253,5 +251,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -305,5 +303,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -344,5 +342,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -417,5 +415,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -520,5 +518,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -573,11 +571,9 @@
         // Check the current candidate list
         int e;
-        Cost c;
         for (int i = 0; i != _curr_length; ++i) {
           e = _candidates[i];
-          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-          if (c < 0) {
-            _cand_cost[e] = c;
-          } else {
+          _cand_cost[e] = _state[e] *
+            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+          if (_cand_cost[e] >= 0) {
             _candidates[i--] = _candidates[--_curr_length];
           }
@@ -589,7 +585,7 @@
 
         for (e = _next_arc; e != _search_arc_num; ++e) {
-          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-          if (c < 0) {
-            _cand_cost[e] = c;
+          _cand_cost[e] = _state[e] *
+            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+          if (_cand_cost[e] < 0) {
             _candidates[_curr_length++] = e;
           }
@@ -638,10 +634,9 @@
     ///
     /// \param graph The digraph the algorithm runs on.
-    /// \param arc_mixing Indicate if the arcs will be stored in a
+    /// \param arc_mixing Indicate if the arcs have to be stored in a
     /// mixed order in the internal data structure.
-    /// In general, it leads to similar performance as using the original
-    /// arc order, but it makes the algorithm more robust and in special
-    /// cases, even significantly faster. Therefore, it is enabled by default.
-    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
+    /// In special cases, it could lead to better overall performance,
+    /// but it is usually slower. Therefore it is disabled by default.
+    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
       _graph(graph), _node_id(graph), _arc_id(graph),
       _arc_mixing(arc_mixing),
@@ -736,6 +731,4 @@
     ///
     /// \return <tt>(*this)</tt>
-    ///
-    /// \sa supplyType()
     template<typename SupplyMap>
     NetworkSimplex& supplyMap(const SupplyMap& map) {
@@ -754,5 +747,5 @@
     ///
     /// Using this function has the same effect as using \ref supplyMap()
-    /// with a map in which \c k is assigned to \c s, \c -k is
+    /// with such a map in which \c k is assigned to \c s, \c -k is
     /// assigned to \c t and all other nodes have zero supply value.
     ///
@@ -921,5 +914,5 @@
       _parent.resize(all_node_num);
       _pred.resize(all_node_num);
-      _pred_dir.resize(all_node_num);
+      _forward.resize(all_node_num);
       _thread.resize(all_node_num);
       _rev_thread.resize(all_node_num);
@@ -935,5 +928,5 @@
       if (_arc_mixing) {
         // Store the arcs in a mixed order
-        const int skip = std::max(_arc_num / _node_num, 3);
+        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
         int i = 0, j = 0;
         for (ArcIt a(_graph); a != INVALID; ++a) {
@@ -941,5 +934,5 @@
           _source[i] = _node_id[_graph.source(a)];
           _target[i] = _node_id[_graph.target(a)];
-          if ((i += skip) >= _arc_num) i = ++j;
+          if ((i += k) >= _arc_num) i = ++j;
         }
       } else {
@@ -1085,5 +1078,5 @@
         ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
       } else {
-        ART_COST = 0;
+        ART_COST = std::numeric_limits<Cost>::min();
         for (int i = 0; i != _arc_num; ++i) {
           if (_cost[i] > ART_COST) ART_COST = _cost[i];
@@ -1124,5 +1117,5 @@
           _state[e] = STATE_TREE;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _source[e] = u;
@@ -1131,5 +1124,5 @@
             _cost[e] = 0;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _source[e] = _root;
@@ -1151,5 +1144,5 @@
           _last_succ[u] = u;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1161,5 +1154,5 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _pred[u] = f;
@@ -1192,5 +1185,5 @@
           _last_succ[u] = u;
           if (_supply[u] <= 0) {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1202,5 +1195,5 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = -ART_COST;
             _pred[u] = f;
@@ -1245,5 +1238,4 @@
       // Initialize first and second nodes according to the direction
       // of the cycle
-      int first, second;
       if (_state[in_arc] == STATE_LOWER) {
         first  = _source[in_arc];
@@ -1255,15 +1247,12 @@
       delta = _cap[in_arc];
       int result = 0;
-      Value c, d;
+      Value d;
       int e;
 
-      // Search the cycle form the first node to the join node
+      // Search the cycle along the path form the first node to the root
       for (int u = first; u != join; u = _parent[u]) {
         e = _pred[u];
-        d = _flow[e];
-        if (_pred_dir[u] == DIR_DOWN) {
-          c = _cap[e];
-          d = c >= MAX ? INF : c - d;
-        }
+        d = _forward[u] ?
+          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
         if (d < delta) {
           delta = d;
@@ -1272,13 +1261,9 @@
         }
       }
-
-      // Search the cycle form the second node to the join node
+      // Search the cycle along the path form the second node to the root
       for (int u = second; u != join; u = _parent[u]) {
         e = _pred[u];
-        d = _flow[e];
-        if (_pred_dir[u] == DIR_UP) {
-          c = _cap[e];
-          d = c >= MAX ? INF : c - d;
-        }
+        d = _forward[u] ?
+          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
         if (d <= delta) {
           delta = d;
@@ -1305,8 +1290,8 @@
         _flow[in_arc] += val;
         for (int u = _source[in_arc]; u != join; u = _parent[u]) {
-          _flow[_pred[u]] -= _pred_dir[u] * val;
+          _flow[_pred[u]] += _forward[u] ? -val : val;
         }
         for (int u = _target[in_arc]; u != join; u = _parent[u]) {
-          _flow[_pred[u]] += _pred_dir[u] * val;
+          _flow[_pred[u]] += _forward[u] ? val : -val;
         }
       }
@@ -1323,4 +1308,5 @@
     // Update the tree structure
     void updateTreeStructure() {
+      int u, w;
       int old_rev_thread = _rev_thread[u_out];
       int old_succ_num = _succ_num[u_out];
@@ -1328,127 +1314,122 @@
       v_out = _parent[u_out];
 
-      // Check if u_in and u_out coincide
-      if (u_in == u_out) {
-        // Update _parent, _pred, _pred_dir
-        _parent[u_in] = v_in;
-        _pred[u_in] = in_arc;
-        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
-
-        // Update _thread and _rev_thread
-        if (_thread[v_in] != u_out) {
-          int after = _thread[old_last_succ];
-          _thread[old_rev_thread] = after;
-          _rev_thread[after] = old_rev_thread;
-          after = _thread[v_in];
-          _thread[v_in] = u_out;
-          _rev_thread[u_out] = v_in;
-          _thread[old_last_succ] = after;
-          _rev_thread[after] = old_last_succ;
-        }
+      u = _last_succ[u_in];  // the last successor of u_in
+      right = _thread[u];    // the node after it
+
+      // Handle the case when old_rev_thread equals to v_in
+      // (it also means that join and v_out coincide)
+      if (old_rev_thread == v_in) {
+        last = _thread[_last_succ[u_out]];
       } else {
-        // Handle the case when old_rev_thread equals to v_in
-        // (it also means that join and v_out coincide)
-        int thread_continue = old_rev_thread == v_in ?
-          _thread[old_last_succ] : _thread[v_in];
-
-        // Update _thread and _parent along the stem nodes (i.e. the nodes
-        // between u_in and u_out, whose parent have to be changed)
-        int stem = u_in;              // the current stem node
-        int par_stem = v_in;          // the new parent of stem
-        int next_stem;                // the next stem node
-        int last = _last_succ[u_in];  // the last successor of stem
-        int before, after = _thread[last];
-        _thread[v_in] = u_in;
-        _dirty_revs.clear();
-        _dirty_revs.push_back(v_in);
-        while (stem != u_out) {
-          // Insert the next stem node into the thread list
-          next_stem = _parent[stem];
-          _thread[last] = next_stem;
-          _dirty_revs.push_back(last);
-
-          // Remove the subtree of stem from the thread list
-          before = _rev_thread[stem];
-          _thread[before] = after;
-          _rev_thread[after] = before;
-
-          // Change the parent node and shift stem nodes
-          _parent[stem] = par_stem;
-          par_stem = stem;
-          stem = next_stem;
-
-          // Update last and after
-          last = _last_succ[stem] == _last_succ[par_stem] ?
-            _rev_thread[par_stem] : _last_succ[stem];
-          after = _thread[last];
-        }
-        _parent[u_out] = par_stem;
-        _thread[last] = thread_continue;
-        _rev_thread[thread_continue] = last;
-        _last_succ[u_out] = last;
-
-        // Remove the subtree of u_out from the thread list except for
-        // the case when old_rev_thread equals to v_in
-        if (old_rev_thread != v_in) {
-          _thread[old_rev_thread] = after;
-          _rev_thread[after] = old_rev_thread;
-        }
-
-        // Update _rev_thread using the new _thread values
-        for (int i = 0; i != int(_dirty_revs.size()); ++i) {
-          int u = _dirty_revs[i];
-          _rev_thread[_thread[u]] = u;
-        }
-
-        // Update _pred, _pred_dir, _last_succ and _succ_num for the
-        // stem nodes from u_out to u_in
-        int tmp_sc = 0, tmp_ls = _last_succ[u_out];
-        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
-          _pred[u] = _pred[p];
-          _pred_dir[u] = -_pred_dir[p];
-          tmp_sc += _succ_num[u] - _succ_num[p];
-          _succ_num[u] = tmp_sc;
-          _last_succ[p] = tmp_ls;
-        }
-        _pred[u_in] = in_arc;
-        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
-        _succ_num[u_in] = old_succ_num;
+        last = _thread[v_in];
+      }
+
+      // Update _thread and _parent along the stem nodes (i.e. the nodes
+      // between u_in and u_out, whose parent have to be changed)
+      _thread[v_in] = stem = u_in;
+      _dirty_revs.clear();
+      _dirty_revs.push_back(v_in);
+      par_stem = v_in;
+      while (stem != u_out) {
+        // Insert the next stem node into the thread list
+        new_stem = _parent[stem];
+        _thread[u] = new_stem;
+        _dirty_revs.push_back(u);
+
+        // Remove the subtree of stem from the thread list
+        w = _rev_thread[stem];
+        _thread[w] = right;
+        _rev_thread[right] = w;
+
+        // Change the parent node and shift stem nodes
+        _parent[stem] = par_stem;
+        par_stem = stem;
+        stem = new_stem;
+
+        // Update u and right
+        u = _last_succ[stem] == _last_succ[par_stem] ?
+          _rev_thread[par_stem] : _last_succ[stem];
+        right = _thread[u];
+      }
+      _parent[u_out] = par_stem;
+      _thread[u] = last;
+      _rev_thread[last] = u;
+      _last_succ[u_out] = u;
+
+      // Remove the subtree of u_out from the thread list except for
+      // the case when old_rev_thread equals to v_in
+      // (it also means that join and v_out coincide)
+      if (old_rev_thread != v_in) {
+        _thread[old_rev_thread] = right;
+        _rev_thread[right] = old_rev_thread;
+      }
+
+      // Update _rev_thread using the new _thread values
+      for (int i = 0; i != int(_dirty_revs.size()); ++i) {
+        u = _dirty_revs[i];
+        _rev_thread[_thread[u]] = u;
+      }
+
+      // Update _pred, _forward, _last_succ and _succ_num for the
+      // stem nodes from u_out to u_in
+      int tmp_sc = 0, tmp_ls = _last_succ[u_out];
+      u = u_out;
+      while (u != u_in) {
+        w = _parent[u];
+        _pred[u] = _pred[w];
+        _forward[u] = !_forward[w];
+        tmp_sc += _succ_num[u] - _succ_num[w];
+        _succ_num[u] = tmp_sc;
+        _last_succ[w] = tmp_ls;
+        u = w;
+      }
+      _pred[u_in] = in_arc;
+      _forward[u_in] = (u_in == _source[in_arc]);
+      _succ_num[u_in] = old_succ_num;
+
+      // Set limits for updating _last_succ form v_in and v_out
+      // towards the root
+      int up_limit_in = -1;
+      int up_limit_out = -1;
+      if (_last_succ[join] == v_in) {
+        up_limit_out = join;
+      } else {
+        up_limit_in = join;
       }
 
       // Update _last_succ from v_in towards the root
-      int up_limit_out = _last_succ[join] == v_in ? join : -1;
-      int last_succ_out = _last_succ[u_out];
-      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
-        _last_succ[u] = last_succ_out;
-      }
-
+      for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
+           u = _parent[u]) {
+        _last_succ[u] = _last_succ[u_out];
+      }
       // Update _last_succ from v_out towards the root
       if (join != old_rev_thread && v_in != old_rev_thread) {
-        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
+        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
              u = _parent[u]) {
           _last_succ[u] = old_rev_thread;
         }
-      }
-      else if (last_succ_out != old_last_succ) {
-        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
+      } else {
+        for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
              u = _parent[u]) {
-          _last_succ[u] = last_succ_out;
+          _last_succ[u] = _last_succ[u_out];
         }
       }
 
       // Update _succ_num from v_in to join
-      for (int u = v_in; u != join; u = _parent[u]) {
+      for (u = v_in; u != join; u = _parent[u]) {
         _succ_num[u] += old_succ_num;
       }
       // Update _succ_num from v_out to join
-      for (int u = v_out; u != join; u = _parent[u]) {
+      for (u = v_out; u != join; u = _parent[u]) {
         _succ_num[u] -= old_succ_num;
       }
     }
 
-    // Update potentials in the subtree that has been moved
+    // Update potentials
     void updatePotential() {
-      Cost sigma = _pi[v_in] - _pi[u_in] -
-                   _pred_dir[u_in] * _cost[in_arc];
+      Cost sigma = _forward[u_in] ?
+        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
+        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
+      // Update potentials in the subtree, which has been moved
       int end = _thread[_last_succ[u_in]];
       for (int u = u_in; u != end; u = _thread[u]) {
@@ -1609,5 +1590,5 @@
       if (_sum_supply == 0) {
         if (_stype == GEQ) {
-          Cost max_pot = -std::numeric_limits<Cost>::max();
+          Cost max_pot = std::numeric_limits<Cost>::min();
           for (int i = 0; i != _node_num; ++i) {
             if (_pi[i] > max_pot) max_pot = _pi[i];
Index: lemon/path.h
===================================================================
--- lemon/path.h	(revision 1024)
+++ lemon/path.h	(revision 956)
@@ -44,5 +44,5 @@
   ///
   /// In a sense, the path can be treated as a list of arcs. The
-  /// LEMON path type stores just this list. As a consequence, it
+  /// lemon path type stores just this list. As a consequence, it
   /// cannot enumerate the nodes of the path and the source node of
   /// a zero length path is undefined.
@@ -136,5 +136,5 @@
     void clear() { head.clear(); tail.clear(); }
 
-    /// \brief The n-th arc.
+    /// \brief The nth arc.
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -144,5 +144,5 @@
     }
 
-    /// \brief Initialize arc iterator to point to the n-th arc
+    /// \brief Initialize arc iterator to point to the nth arc
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -232,5 +232,5 @@
   ///
   /// In a sense, the path can be treated as a list of arcs. The
-  /// LEMON path type stores just this list. As a consequence it
+  /// lemon path type stores just this list. As a consequence it
   /// cannot enumerate the nodes in the path and the zero length paths
   /// cannot store the source.
@@ -328,5 +328,5 @@
     void clear() { data.clear(); }
 
-    /// \brief The n-th arc.
+    /// \brief The nth arc.
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -335,5 +335,5 @@
     }
 
-    /// \brief  Initializes arc iterator to point to the n-th arc.
+    /// \brief  Initializes arc iterator to point to the nth arc.
     ArcIt nthIt(int n) const {
       return ArcIt(*this, n);
@@ -396,5 +396,5 @@
   ///
   /// In a sense, the path can be treated as a list of arcs. The
-  /// LEMON path type stores just this list. As a consequence it
+  /// lemon path type stores just this list. As a consequence it
   /// cannot enumerate the nodes in the path and the zero length paths
   /// cannot store the source.
@@ -505,7 +505,7 @@
     };
 
-    /// \brief The n-th arc.
-    ///
-    /// This function looks for the n-th arc in O(n) time.
+    /// \brief The nth arc.
+    ///
+    /// This function looks for the nth arc in O(n) time.
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
     const Arc& nth(int n) const {
@@ -517,5 +517,5 @@
     }
 
-    /// \brief Initializes arc iterator to point to the n-th arc.
+    /// \brief Initializes arc iterator to point to the nth arc.
     ArcIt nthIt(int n) const {
       Node *node = first;
@@ -736,5 +736,5 @@
   ///
   /// In a sense, the path can be treated as a list of arcs. The
-  /// LEMON path type stores just this list. As a consequence it
+  /// lemon path type stores just this list. As a consequence it
   /// cannot enumerate the nodes in the path and the source node of
   /// a zero length path is undefined.
@@ -832,5 +832,5 @@
     };
 
-    /// \brief The n-th arc.
+    /// \brief The nth arc.
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -839,5 +839,5 @@
     }
 
-    /// \brief The arc iterator pointing to the n-th arc.
+    /// \brief The arc iterator pointing to the nth arc.
     ArcIt nthIt(int n) const {
       return ArcIt(*this, n);
@@ -1043,5 +1043,5 @@
   ///
   /// In a sense, the path can be treated as a list of arcs. The
-  /// LEMON path type stores only this list. As a consequence, it
+  /// lemon path type stores only this list. As a consequence, it
   /// cannot enumerate the nodes in the path and the zero length paths
   /// cannot have a source node.
Index: lemon/preflow.h
===================================================================
--- lemon/preflow.h	(revision 1029)
+++ lemon/preflow.h	(revision 956)
@@ -544,4 +544,7 @@
           _flow->set(e, (*_capacity)[e]);
           (*_excess)[u] += rem;
+          if (u != _target && !_level->active(u)) {
+            _level->activate(u);
+          }
         }
       }
@@ -553,10 +556,9 @@
           _flow->set(e, 0);
           (*_excess)[v] += rem;
-        }
-      }
-      for (NodeIt n(_graph); n != INVALID; ++n) 
-        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
-          _level->activate(n);
-          
+          if (v != _target && !_level->active(v)) {
+            _level->activate(v);
+          }
+        }
+      }
       return true;
     }
@@ -575,16 +577,10 @@
       _phase = true;
 
-      while (true) {
+      Node n = _level->highestActive();
+      int level = _level->highestActiveLevel();
+      while (n != INVALID) {
         int num = _node_num;
 
-        Node n = INVALID;
-        int level = -1;
-
-        while (num > 0) {
-          n = _level->highestActive();
-          if (n == INVALID) goto first_phase_done;
-          level = _level->highestActiveLevel();
-          --num;
-          
+        while (num > 0 && n != INVALID) {
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
@@ -652,20 +648,12 @@
             _level->deactivate(n);
           }
+
+          n = _level->highestActive();
+          level = _level->highestActiveLevel();
+          --num;
         }
 
         num = _node_num * 20;
-        while (num > 0) {
-          while (level >= 0 && _level->activeFree(level)) {
-            --level;
-          }
-          if (level == -1) {
-            n = _level->highestActive();
-            level = _level->highestActiveLevel();
-            if (n == INVALID) goto first_phase_done;
-          } else {
-            n = _level->activeOn(level);
-          }
-          --num;
-
+        while (num > 0 && n != INVALID) {
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
@@ -733,7 +721,17 @@
             _level->deactivate(n);
           }
-        }
-      }
-    first_phase_done:;
+
+          while (level >= 0 && _level->activeFree(level)) {
+            --level;
+          }
+          if (level == -1) {
+            n = _level->highestActive();
+            level = _level->highestActiveLevel();
+          } else {
+            n = _level->activeOn(level);
+          }
+          --num;
+        }
+      }
     }
 
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 1050)
+++ test/CMakeLists.txt	(revision 953)
@@ -7,8 +7,4 @@
   ${PROJECT_BINARY_DIR}/lemon
 )
-
-SET(TEST_WITH_VALGRIND "NO" CACHE STRING
-  "Run the test with valgrind (YES/NO).")
-SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.")
 
 SET(TESTS
@@ -36,10 +32,7 @@
   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
@@ -53,10 +46,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)
 
@@ -94,10 +82,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)
 
@@ -135,17 +118,6 @@
 
 FOREACH(TEST_NAME ${TESTS})
-  IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
-    ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
-  ELSE()
-    ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc)
-  ENDIF()
+  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
   TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
-    IF(TEST_WITH_VALGRIND)
-      ADD_TEST(${TEST_NAME}
-        valgrind --error-exitcode=1 ${VALGRIND_FLAGS}
-        ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} )
-    ELSE()
-      ADD_TEST(${TEST_NAME} ${TEST_NAME})
-    ENDIF()
-  ADD_DEPENDENCIES(check ${TEST_NAME})
+  ADD_TEST(${TEST_NAME} ${TEST_NAME})
 ENDFOREACH()
Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 1021)
+++ test/Makefile.am	(revision 953)
@@ -34,10 +34,7 @@
 	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 \
@@ -88,10 +85,7 @@
 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/bellman_ford_test.cc
===================================================================
--- test/bellman_ford_test.cc	(revision 960)
+++ test/bellman_ford_test.cc	(revision 956)
@@ -105,4 +105,5 @@
       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
       ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
+      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
       ::Create bf_test(gr,length);
 
Index: test/dfs_test.cc
===================================================================
--- test/dfs_test.cc	(revision 1010)
+++ test/dfs_test.cc	(revision 956)
@@ -51,8 +51,5 @@
   "@attributes\n"
   "source 0\n"
-  "target 5\n"
-  "source1 6\n"
-  "target1 3\n";
-
+  "target 5\n";
 
 void checkDfsCompile()
@@ -183,5 +180,4 @@
   Digraph G;
   Node s, t;
-  Node s1, t1;
 
   std::istringstream input(test_lgf);
@@ -189,6 +185,4 @@
     node("source", s).
     node("target", t).
-    node("source1", s1).
-    node("target1", t1).
     run();
 
@@ -217,9 +211,4 @@
 
   {
-  Dfs<Digraph> dfs(G);
-  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
-  }
-  
-  {
     NullMap<Node,Arc> myPredMap;
     dfs(G).predMap(myPredMap).run(s);
Index: test/graph_copy_test.cc
===================================================================
--- test/graph_copy_test.cc	(revision 989)
+++ test/graph_copy_test.cc	(revision 463)
@@ -19,5 +19,4 @@
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
-#include <lemon/static_graph.h>
 #include <lemon/lgf_reader.h>
 #include <lemon/error.h>
@@ -28,9 +27,7 @@
 using namespace lemon;
 
-template <typename GR>
 void digraph_copy_test() {
   const int nn = 10;
 
-  // Build a digraph
   SmartDigraph from;
   SmartDigraph::NodeMap<int> fnm(from);
@@ -54,17 +51,16 @@
     }
   }
-  
-  // Test digraph copy
-  GR to;
-  typename GR::template NodeMap<int> tnm(to);
-  typename GR::template ArcMap<int> tam(to);
-  typename GR::Node tn;
-  typename GR::Arc ta;
 
-  SmartDigraph::NodeMap<typename GR::Node> nr(from);
-  SmartDigraph::ArcMap<typename GR::Arc> er(from);
+  ListDigraph to;
+  ListDigraph::NodeMap<int> tnm(to);
+  ListDigraph::ArcMap<int> tam(to);
+  ListDigraph::Node tn;
+  ListDigraph::Arc ta;
 
-  typename GR::template NodeMap<SmartDigraph::Node> ncr(to);
-  typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);
+  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
+  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
+
+  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
+  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
 
   digraphCopy(from, to).
@@ -73,7 +69,4 @@
     nodeCrossRef(ncr).arcCrossRef(ecr).
     node(fn, tn).arc(fa, ta).run();
-  
-  check(countNodes(from) == countNodes(to), "Wrong copy.");
-  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
@@ -89,26 +82,18 @@
   }
 
-  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
+  for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
     check(nr[ncr[it]] == it, "Wrong copy.");
   }
 
-  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
+  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
     check(er[ecr[it]] == it, "Wrong copy.");
   }
   check(tn == nr[fn], "Wrong copy.");
   check(ta == er[fa], "Wrong copy.");
-
-  // Test repeated copy
-  digraphCopy(from, to).run();
-  
-  check(countNodes(from) == countNodes(to), "Wrong copy.");
-  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 
-template <typename GR>
 void graph_copy_test() {
   const int nn = 10;
 
-  // Build a graph
   SmartGraph from;
   SmartGraph::NodeMap<int> fnm(from);
@@ -138,20 +123,19 @@
   }
 
-  // Test graph copy
-  GR to;
-  typename GR::template NodeMap<int> tnm(to);
-  typename GR::template ArcMap<int> tam(to);
-  typename GR::template EdgeMap<int> tem(to);
-  typename GR::Node tn;
-  typename GR::Arc ta;
-  typename GR::Edge te;
+  ListGraph to;
+  ListGraph::NodeMap<int> tnm(to);
+  ListGraph::ArcMap<int> tam(to);
+  ListGraph::EdgeMap<int> tem(to);
+  ListGraph::Node tn;
+  ListGraph::Arc ta;
+  ListGraph::Edge te;
 
-  SmartGraph::NodeMap<typename GR::Node> nr(from);
-  SmartGraph::ArcMap<typename GR::Arc> ar(from);
-  SmartGraph::EdgeMap<typename GR::Edge> er(from);
+  SmartGraph::NodeMap<ListGraph::Node> nr(from);
+  SmartGraph::ArcMap<ListGraph::Arc> ar(from);
+  SmartGraph::EdgeMap<ListGraph::Edge> er(from);
 
-  typename GR::template NodeMap<SmartGraph::Node> ncr(to);
-  typename GR::template ArcMap<SmartGraph::Arc> acr(to);
-  typename GR::template EdgeMap<SmartGraph::Edge> ecr(to);
+  ListGraph::NodeMap<SmartGraph::Node> ncr(to);
+  ListGraph::ArcMap<SmartGraph::Arc> acr(to);
+  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
 
   graphCopy(from, to).
@@ -160,8 +144,4 @@
     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
     node(fn, tn).arc(fa, ta).edge(fe, te).run();
-
-  check(countNodes(from) == countNodes(to), "Wrong copy.");
-  check(countEdges(from) == countEdges(to), "Wrong copy.");
-  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
@@ -188,12 +168,12 @@
   }
 
-  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
+  for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
     check(nr[ncr[it]] == it, "Wrong copy.");
   }
 
-  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
+  for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
     check(ar[acr[it]] == it, "Wrong copy.");
   }
-  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
+  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
     check(er[ecr[it]] == it, "Wrong copy.");
   }
@@ -201,20 +181,10 @@
   check(ta == ar[fa], "Wrong copy.");
   check(te == er[fe], "Wrong copy.");
-
-  // Test repeated copy
-  graphCopy(from, to).run();
-  
-  check(countNodes(from) == countNodes(to), "Wrong copy.");
-  check(countEdges(from) == countEdges(to), "Wrong copy.");
-  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 
 
 int main() {
-  digraph_copy_test<SmartDigraph>();
-  digraph_copy_test<ListDigraph>();
-  digraph_copy_test<StaticDigraph>();
-  graph_copy_test<SmartGraph>();
-  graph_copy_test<ListGraph>();
+  digraph_copy_test();
+  graph_copy_test();
 
   return 0;
Index: test/maps_test.cc
===================================================================
--- test/maps_test.cc	(revision 956)
+++ test/maps_test.cc	(revision 1057)
@@ -642,4 +642,5 @@
     const int num = 10;
     Graph g;
+    Ibm map0(g, true);
     std::vector<Item> items;
     for (int i = 0; i < num; ++i) {
@@ -723,4 +724,5 @@
     const int num = 10;
     Graph g;
+    Iim map0(g, 0);
     std::vector<Item> items;
     for (int i = 0; i < num; ++i) {
@@ -773,4 +775,5 @@
     const int num = 10;
     Graph g;
+    Ivm map0(g, 0.0);
     std::vector<Item> items;
     for (int i = 0; i < num; ++i) {
Index: st/max_cardinality_search_test.cc
===================================================================
--- test/max_cardinality_search_test.cc	(revision 1020)
+++ 	(revision )
@@ -1,162 +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 <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/max_clique_test.cc
===================================================================
--- test/max_clique_test.cc	(revision 1022)
+++ 	(revision )
@@ -1,188 +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/list_graph.h>
-#include <lemon/full_graph.h>
-#include <lemon/grid_graph.h>
-#include <lemon/lgf_reader.h>
-#include <lemon/grosso_locatelli_pullan_mc.h>
-
-#include "test_tools.h"
-
-using namespace lemon;
-
-char test_lgf[] =
-  "@nodes\n"
-  "label max_clique\n"
-  "1     0\n"
-  "2     0\n"
-  "3     0\n"
-  "4     1\n"
-  "5     1\n"
-  "6     1\n"
-  "7     1\n"
-  "@edges\n"
-  "    label\n"
-  "1 2     1\n"
-  "1 3     2\n"
-  "1 4     3\n"
-  "1 6     4\n"
-  "2 3     5\n"
-  "2 5     6\n"
-  "2 7     7\n"
-  "3 4     8\n"
-  "3 5     9\n"
-  "4 5    10\n"
-  "4 6    11\n"
-  "4 7    12\n"
-  "5 6    13\n"
-  "5 7    14\n"
-  "6 7    15\n";
-      
-
-// Check with general graphs
-template <typename Param>
-void checkMaxCliqueGeneral(Param rule) {
-  typedef ListGraph GR;
-  typedef GrossoLocatelliPullanMc<GR> McAlg;
-  typedef McAlg::CliqueNodeIt CliqueIt;
-  
-  // Basic tests
-  {
-    GR g;
-    GR::NodeMap<bool> map(g);
-    McAlg mc(g);
-    mc.iterationLimit(50);
-    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == 0, "Wrong clique size");
-    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
-
-    GR::Node u = g.addNode();
-    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == 1, "Wrong clique size");
-    mc.cliqueMap(map);
-    check(map[u], "Wrong clique map");
-    CliqueIt it1(mc);
-    check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
-          "Wrong CliqueNodeIt");
-    
-    GR::Node v = g.addNode();
-    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == 1, "Wrong clique size");
-    mc.cliqueMap(map);
-    check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
-    CliqueIt it2(mc);
-    check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
-
-    g.addEdge(u, v);
-    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == 2, "Wrong clique size");
-    mc.cliqueMap(map);
-    check(map[u] && map[v], "Wrong clique map");
-    CliqueIt it3(mc);
-    check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
-          "Wrong CliqueNodeIt");
-  }
-
-  // Test graph
-  {
-    GR g;
-    GR::NodeMap<bool> max_clique(g);
-    GR::NodeMap<bool> map(g);
-    std::istringstream input(test_lgf);
-    graphReader(g, input)
-      .nodeMap("max_clique", max_clique)
-      .run();
-    
-    McAlg mc(g);
-    mc.iterationLimit(50);
-    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == 4, "Wrong clique size");
-    mc.cliqueMap(map);
-    for (GR::NodeIt n(g); n != INVALID; ++n) {
-      check(map[n] == max_clique[n], "Wrong clique map");
-    }
-    int cnt = 0;
-    for (CliqueIt n(mc); n != INVALID; ++n) {
-      cnt++;
-      check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
-    }
-    check(cnt == 4, "Wrong CliqueNodeIt");
-  }
-}
-
-// Check with full graphs
-template <typename Param>
-void checkMaxCliqueFullGraph(Param rule) {
-  typedef FullGraph GR;
-  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
-  typedef McAlg::CliqueNodeIt CliqueIt;
-  
-  for (int size = 0; size <= 40; size = size * 3 + 1) {
-    GR g(size);
-    GR::NodeMap<bool> map(g);
-    McAlg mc(g);
-    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
-    check(mc.cliqueSize() == size, "Wrong clique size");
-    mc.cliqueMap(map);
-    for (GR::NodeIt n(g); n != INVALID; ++n) {
-      check(map[n], "Wrong clique map");
-    }
-    int cnt = 0;
-    for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
-    check(cnt == size, "Wrong CliqueNodeIt");
-  }
-}
-
-// Check with grid graphs
-template <typename Param>
-void checkMaxCliqueGridGraph(Param rule) {
-  GridGraph g(5, 7);
-  GridGraph::NodeMap<char> map(g);
-  GrossoLocatelliPullanMc<GridGraph> mc(g);
-  
-  mc.iterationLimit(100);
-  check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
-  check(mc.cliqueSize() == 2, "Wrong clique size");
-
-  mc.stepLimit(100);
-  check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
-  check(mc.cliqueSize() == 2, "Wrong clique size");
-
-  mc.sizeLimit(2);
-  check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
-  check(mc.cliqueSize() == 2, "Wrong clique size");
-}
-
-
-int main() {
-  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
-  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
-  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
-
-  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
-  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
-  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
-                       
-  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
-  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
-  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
-                       
-  return 0;
-}
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;
-}
Index: test/preflow_test.cc
===================================================================
--- test/preflow_test.cc	(revision 1029)
+++ test/preflow_test.cc	(revision 956)
@@ -157,28 +157,4 @@
 }
 
-void initFlowTest()
-{
-  DIGRAPH_TYPEDEFS(SmartDigraph);
-  
-  SmartDigraph g;
-  SmartDigraph::ArcMap<int> cap(g),iflow(g);
-  Node s=g.addNode(); Node t=g.addNode();
-  Node n1=g.addNode(); Node n2=g.addNode();
-  Arc a;
-  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
-  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
-  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
-
-  Preflow<SmartDigraph> pre(g,cap,s,t);
-  pre.init(iflow);
-  pre.startFirstPhase();
-  check(pre.flowValue() == 10, "The incorrect max flow value.");
-  check(pre.minCut(s), "Wrong min cut (Node s).");
-  check(pre.minCut(n1), "Wrong min cut (Node n1).");
-  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
-  check(!pre.minCut(t), "Wrong min cut (Node t).");
-}
-
-
 int main() {
 
@@ -271,6 +247,4 @@
         "The max flow value or the three min cut values are incorrect.");
 
-  initFlowTest();
-  
   return 0;
 }
