Changes in / [932:773dd96ecdd8:931:f112c18bc304] in lemon-main

Files:

• CMakeLists.txt (modified) (5 diffs)
• LICENSE (modified) (1 diff)
• NEWS (modified) (3 diffs)
• configure.ac (modified) (2 diffs)
• contrib/CMakeLists.txt (deleted)
• doc/CMakeLists.txt (modified) (2 diffs)
• doc/Doxyfile.in (modified) (14 diffs)
• doc/DoxygenLayout.xml (modified) (1 diff)
• doc/coding_style.dox (modified) (1 diff)
• doc/dirs.dox (modified) (1 diff)
• doc/groups.dox (modified) (6 diffs)
• doc/mainpage.dox (added)
• doc/mainpage.dox.in (deleted)
• doc/references.bib (modified) (1 diff)
• lemon/CMakeLists.txt (modified) (2 diffs)
• lemon/Makefile.am (modified) (2 diffs)
• lemon/arg_parser.h (modified) (1 diff)
• lemon/bellman_ford.h (modified) (6 diffs)
• lemon/bits/edge_set_extender.h (modified) (1 diff)
• lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
• lemon/bits/path_dump.h (modified) (2 diffs)
• lemon/capacity_scaling.h (modified) (2 diffs)
• lemon/core.h (modified) (3 diffs)
• lemon/cost_scaling.h (modified) (4 diffs)
• lemon/cycle_canceling.h (modified) (3 diffs)
• lemon/dfs.h (modified) (2 diffs)
• lemon/euler.h (modified) (1 diff)
• lemon/grosso_locatelli_pullan_mc.h (deleted)
• lemon/hao_orlin.h (modified) (7 diffs)
• lemon/hartmann_orlin_mmc.h (modified) (2 diffs)
• lemon/kruskal.h (modified) (1 diff)
• lemon/lemon.pc.cmake (deleted)
• lemon/max_cardinality_search.h (deleted)
• lemon/nagamochi_ibaraki.h (deleted)
• lemon/network_simplex.h (modified) (33 diffs)
• lemon/path.h (modified) (13 diffs)
• lemon/preflow.h (modified) (5 diffs)
• test/CMakeLists.txt (modified) (4 diffs)
• test/Makefile.am (modified) (2 diffs)
• test/bellman_ford_test.cc (modified) (1 diff)
• test/dfs_test.cc (modified) (4 diffs)
• test/graph_copy_test.cc (modified) (9 diffs)
• test/max_cardinality_search_test.cc (deleted)
• test/max_clique_test.cc (deleted)
• test/nagamochi_ibaraki_test.cc (deleted)
• test/preflow_test.cc (modified) (2 diffs)

CMakeLists.txt

@@ -3 +3 @@
 SET(PROJECT_NAME "LEMON")
 PROJECT(${PROJECT_NAME})
-
-INCLUDE(FindPythonInterp)
-INCLUDE(FindWget)
 
 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
@@ -12 +9 @@
   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 +17 @@
   )
   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 +32 @@
 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 -ansi -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 +65 @@
 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")

LICENSE

@@ -2 +2 @@
 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).

NEWS

@@ -1 @@
-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 +73 @@
           ----: 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 +95 @@
 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)

configure.ac

@@ -115 +115 @@
 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 +122 @@
 cmake/version.cmake
 doc/Doxyfile
-doc/mainpage.dox
 lemon/lemon.pc
 ])

doc/CMakeLists.txt

@@ -4 +4 @@
 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 +53 @@
 
 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()

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.7.3
+# Doxyfile 1.5.9
 
 #---------------------------------------------------------------------------
@@ -5 +5 @@
 #---------------------------------------------------------------------------
 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 +30 @@
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
-EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
@@ -58 +55 @@
 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 +71 @@
 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 +90 @@
                          "@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 +112 @@
 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 +138 @@
 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 +154 @@
 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 +176 @@
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
-LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
@@ -252 +224 @@
 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 +238 @@
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
-DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
@@ -284 +255 @@
 DOT_PATH               = 
 DOTFILE_DIRS           = 
-MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
@@ -291 +261 @@
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
+#---------------------------------------------------------------------------
+# Configuration::additions related to the search engine   
+#---------------------------------------------------------------------------
+SEARCHENGINE           = NO

doc/DoxygenLayout.xml

@@ -3 +3 @@
   <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>
 

doc/coding_style.dox

@@ -99 +99 @@
 \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
 

doc/dirs.dox

@@ -32 +32 @@
 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.  */
 
 /**

doc/groups.dox

@@ -264 +264 @@
 
 /**
+@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 +415 @@
    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 +473 @@
 
 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 +548 @@
 
 /**
-@defgroup planar Planar Embedding and Drawing
+@defgroup planar Planarity Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing
@@ -552 +560 @@
 
 /**
-@defgroup approx_algs Approximation Algorithms
+@defgroup approx Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -558 +566 @@
 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.
 */
 

doc/references.bib

@@ -298 +298 @@
   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,
+}

lemon/CMakeLists.txt

@@ -7 +7 @@
   ${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 +67 @@
   COMPONENT headers
 )
-
-INSTALL(
-  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
-  DESTINATION lib/pkgconfig
-)
-

lemon/Makefile.am

@@ -91 +91 @@
         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 +107 @@
         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 \

lemon/arg_parser.h

@@ -36 +36 @@
 
   ///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
     };
 

lemon/bellman_ford.h

@@ -29 +29 @@
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/tolerance.h>
 #include <lemon/path.h>
 
@@ -35 +36 @@
 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 +43 @@
   /// 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 +85 @@
     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 +156 @@
     /// 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 +887 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 

lemon/bits/edge_set_extender.h

@@ -281 +281 @@
     typedef EdgeSetExtender Graph;
 
-    typedef True UndirectedTag;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;

lemon/bits/graph_adaptor_extender.h

@@ -182 +182 @@
     typedef GraphAdaptorExtender Adaptor;
 
-    typedef True UndirectedTag;
-
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;

lemon/bits/path_dump.h

@@ -50 +50 @@
 
     bool empty() const {
-      return predMap[target] == INVALID;
+      return predMap[target] != INVALID;
     }
 
@@ -124 +124 @@
 
     bool empty() const {
-      return predMatrixMap(source, target) == INVALID;
+      return source != target;
     }
 

lemon/capacity_scaling.h

@@ -87 +87 @@
   /// 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 +423 @@
     ///
     /// 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.
     ///

lemon/core.h

@@ -395 +395 @@
       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 +422 @@
       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 +445 @@
 
   }
-
-  /// \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.

lemon/cost_scaling.h

@@ -98 +98 @@
   /// "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 +114 @@
   /// 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 +179 @@
     /// 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()
@@ -452 +448 @@
     ///
     /// 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.
     ///

lemon/cycle_canceling.h

@@ -66 +66 @@
   /// 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 +117 @@
     /// \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 +350 @@
     ///
     /// 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.
     ///

lemon/dfs.h

@@ -566 +566 @@
     void start(Node t)
     {
-      while ( !emptyQueue() && !(*_reached)[t] )
+      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
         processNextArc();
     }
@@ -1513 +1513 @@
     /// with addSource() before using this function.
     void start(Node t) {
-      while ( !emptyQueue() && !(*_reached)[t] )
+      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
         processNextArc();
     }

lemon/euler.h

@@ -37 +37 @@
   ///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.

lemon/hao_orlin.h

@@ -54 +54 @@
   /// 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 +913 @@
     /// 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 +925 @@
     /// 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 +934 @@
     /// \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 +945 @@
     /// \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 +966 @@
     /// \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 +977 @@
     /// \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$).
     ///

lemon/hartmann_orlin_mmc.h

@@ -39 +39 @@
   /// \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 +100 @@
   /// 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).

lemon/kruskal.h

@@ -31 +31 @@
 ///\file
 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree
+///
+///Kruskal's algorithm to compute a minimum cost spanning tree.
+///
 
 namespace lemon {

lemon/network_simplex.h

@@ -48 +48 @@
   /// 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 +64 @@
   /// 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 +126 @@
     /// 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 +167 @@
     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 +177 @@
     };
 
-    // 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 +218 @@
     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 +251 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -305 +303 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -344 +342 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -417 +415 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -520 +518 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -573 +571 @@
         // 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 +585 @@
 
         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 +634 @@
     ///
     /// \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 +731 @@
     ///
     /// \return <tt>(*this)</tt>
-    ///
-    /// \sa supplyType()
     template<typename SupplyMap>
     NetworkSimplex& supplyMap(const SupplyMap& map) {
@@ -754 +747 @@
     ///
     /// 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 +914 @@
       _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 +928 @@
       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 +934 @@
           _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 +1078 @@
         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 +1117 @@
           _state[e] = STATE_TREE;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _source[e] = u;
@@ -1131 +1124 @@
             _cost[e] = 0;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _source[e] = _root;
@@ -1151 +1144 @@
           _last_succ[u] = u;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1161 +1154 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _pred[u] = f;
@@ -1192 +1185 @@
           _last_succ[u] = u;
           if (_supply[u] <= 0) {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1202 +1195 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = -ART_COST;
             _pred[u] = f;
@@ -1245 +1238 @@
       // 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 +1247 @@
       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 +1261 @@
         }
       }
-
-      // 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 +1290 @@
         _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 +1308 @@
     // 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 +1314 @@
       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 +1590 @@
       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];

lemon/path.h

@@ -44 +44 @@
   ///
   /// 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 +136 @@
     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 +144 @@
     }
 
-    /// \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 +232 @@
   ///
   /// 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 +328 @@
     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 +335 @@
     }
 
-    /// \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 +396 @@
   ///
   /// 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 +505 @@
     };
 
-    /// \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 +517 @@
     }
 
-    /// \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 +736 @@
   ///
   /// 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 +832 @@
     };
 
-    /// \brief The n-th arc.
+    /// \brief The nth arc.
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -839 +839 @@
     }
 
-    /// \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 +1043 @@
   ///
   /// 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.

lemon/preflow.h

@@ -544 +544 @@
           _flow->set(e, (*_capacity)[e]);
           (*_excess)[u] += rem;
+          if (u != _target && !_level->active(u)) {
+            _level->activate(u);
+          }
         }
       }
@@ -553 +556 @@
           _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 +577 @@
       _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 +648 @@
             _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 +721 @@
             _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;
+        }
+      }
     }
 

test/CMakeLists.txt

@@ -32 +32 @@
   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
@@ -49 +46 @@
 
 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)
 
@@ -90 +82 @@
 
 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)
 
@@ -131 +118 @@
 
 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)
   ADD_TEST(${TEST_NAME} ${TEST_NAME})
-  ADD_DEPENDENCIES(check ${TEST_NAME})
 ENDFOREACH()

test/Makefile.am

@@ -34 +34 @@
         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 +85 @@
 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

test/bellman_ford_test.cc

@@ -105 +105 @@
       ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
       ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
+      ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
       ::Create bf_test(gr,length);
 

test/dfs_test.cc

@@ -51 +51 @@
   "@attributes\n"
   "source 0\n"
-  "target 5\n"
-  "source1 6\n"
-  "target1 3\n";
-
+  "target 5\n";
 
 void checkDfsCompile()
@@ -183 +180 @@
   Digraph G;
   Node s, t;
-  Node s1, t1;
 
   std::istringstream input(test_lgf);
@@ -189 +185 @@
     node("source", s).
     node("target", t).
-    node("source1", s1).
-    node("target1", t1).
     run();
 
@@ -217 +211 @@
 
   {
-  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);

test/graph_copy_test.cc

@@ -19 +19 @@
 #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 +27 @@
 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 +51 @@
     }
   }
-  
-  // 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 +69 @@
     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 +82 @@
   }
 
-  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 +123 @@
   }
 
-  // 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 +144 @@
     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 +168 @@
   }
 
-  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 +181 @@
   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;

test/preflow_test.cc

@@ -157 +157 @@
 }
 
-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 +247 @@
         "The max flow value or the three min cut values are incorrect.");
 
-  initFlowTest();
-  
   return 0;
 }