Changes in / [1162:404b98971e1f:1160:00f8d9f9920d] in lemon

Files:

• AUTHORS (modified) (2 diffs)
• CMakeLists.txt (modified) (4 diffs)
• INSTALL (modified) (1 diff)
• LICENSE (modified) (1 diff)
• Makefile.am (added)
• cmake/version.cmake.in (modified) (1 diff)
• configure.ac (added)
• contrib/CMakeLists.txt (deleted)
• demo/Makefile.am (added)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/Doxyfile.in (modified) (1 diff)
• doc/Makefile.am (added)
• doc/coding_style.dox (modified) (1 diff)
• doc/dirs.dox (modified) (1 diff)
• doc/groups.dox (modified) (5 diffs)
• doc/references.bib (modified) (1 diff)
• lemon/CMakeLists.txt (modified) (1 diff)
• lemon/Makefile.am (added)
• lemon/bits/alteration_notifier.h (modified) (3 diffs)
• lemon/bits/lock.h (deleted)
• lemon/bits/windows.cc (modified) (1 diff)
• lemon/bits/windows.h (modified) (1 diff)
• lemon/capacity_scaling.h (modified) (2 diffs)
• lemon/config.h.cmake (added)
• lemon/config.h.in (modified) (1 diff)
• lemon/core.h (modified) (1 diff)
• lemon/cost_scaling.h (modified) (29 diffs)
• lemon/cycle_canceling.h (modified) (3 diffs)
• lemon/euler.h (modified) (1 diff)
• lemon/grosso_locatelli_pullan_mc.h (deleted)
• lemon/hao_orlin.h (modified) (7 diffs)
• lemon/kruskal.h (modified) (1 diff)
• lemon/lemon.pc.cmake (added)
• lemon/lemon.pc.in (modified) (1 diff)
• lemon/max_cardinality_search.h (deleted)
• lemon/nagamochi_ibaraki.h (deleted)
• lemon/network_simplex.h (modified) (36 diffs)
• lemon/path.h (modified) (13 diffs)
• m4/lx_check_coin.m4 (added)
• m4/lx_check_cplex.m4 (added)
• m4/lx_check_glpk.m4 (added)
• m4/lx_check_soplex.m4 (added)
• scripts/Makefile.am (added)
• scripts/bootstrap.sh (added)
• scripts/chg-len.py (added)
• scripts/mk-release.sh (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (added)
• test/graph_copy_test.cc (modified) (8 diffs)
• test/max_cardinality_search_test.cc (deleted)
• test/max_clique_test.cc (deleted)
• test/nagamochi_ibaraki_test.cc (deleted)
• tools/Makefile.am (added)

AUTHORS

@@ -1 @@
-The main developers of release series 1.x are
+The authors of the 1.x series are
 
  * Balazs Dezso <deba@inf.elte.hu>
@@ -6 +6 @@
  * Akos Ladanyi <ladanyi@tmit.bme.hu>
 
-For more complete list of contributors, please visit the history of
-the LEMON source code repository: http://lemon.cs.elte.hu/hg/lemon
+For more details on the actual contribution, please visit the history
+of the main LEMON source repository: http://lemon.cs.elte.hu/hg/lemon
 
-Moreover, this version is heavily based on version 0.x of LEMON. Here
-is the list of people who contributed to those versions.
+Moreover, this version is heavily based on the 0.x series of
+LEMON. Here is the list of people who contributed to those versions.
 
  * Mihaly Barasz <klao@cs.elte.hu>

CMakeLists.txt

@@ -13 +13 @@
 ELSE()
   EXECUTE_PROCESS(
-    COMMAND
-    hg log -r. --template "{latesttag}"
+    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
-    OUTPUT_VARIABLE HG_REVISION_TAG
+    OUTPUT_VARIABLE HG_REVISION_PATH
     ERROR_QUIET
     OUTPUT_STRIP_TRAILING_WHITESPACE
   )
   EXECUTE_PROCESS(
-    COMMAND
-    hg log -r. --template "{latesttagdistance}"
+    COMMAND hg id -i
     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
-    OUTPUT_VARIABLE HG_REVISION_DIST
+    OUTPUT_VARIABLE HG_REVISION
     ERROR_QUIET
     OUTPUT_STRIP_TRAILING_WHITESPACE
   )
-  EXECUTE_PROCESS(
-    COMMAND
-    hg log -r. --template "{node|short}"
-    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
-    OUTPUT_VARIABLE HG_REVISION_ID
-    ERROR_QUIET
-    OUTPUT_STRIP_TRAILING_WHITESPACE
-  )
-
-  IF(HG_REVISION_TAG STREQUAL "")
+  IF(HG_REVISION STREQUAL "")
     SET(HG_REVISION_ID "hg-tip")
   ELSE()
-    IF(HG_REVISION_TAG STREQUAL "null")
-      SET(HG_REVISION_TAG "trunk")
-    ELSEIF(HG_REVISION_TAG MATCHES "^r")
-      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
-    ENDIF()
-    IF(HG_REVISION_DIST STREQUAL "0")
-      SET(HG_REVISION ${HG_REVISION_TAG})
+    IF(HG_REVISION_PATH STREQUAL "")
+      SET(HG_REVISION_ID ${HG_REVISION})
     ELSE()
-      SET(HG_REVISION
-        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
+      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     ENDIF()
   ENDIF()
-
-  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
+  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
 ENDIF()
 
@@ -133 +115 @@
 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 
-INCLUDE(FindThreads)
-
-IF(NOT LEMON_THREADING)
-  IF(CMAKE_USE_PTHREADS_INIT)
-    SET(LEMON_THREADING "Pthread")
-  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
-    SET(LEMON_THREADING "Win32")
-  ELSE()
-    SET(LEMON_THREADING "None")
-  ENDIF()
-ENDIF()
-
-SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
-  "Choose the threading library, options are: Pthread Win32 None."
-  FORCE )
-
-IF(LEMON_THREADING STREQUAL "Pthread")
-  SET(LEMON_USE_PTHREAD TRUE)
-ELSEIF(LEMON_THREADING STREQUAL "Win32")
-  SET(LEMON_USE_WIN32_THREADS TRUE)
-ENDIF()
+INCLUDE(FindPythonInterp)
 
 ENABLE_TESTING()
@@ -165 +127 @@
 ADD_SUBDIRECTORY(lemon)
 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
-  ADD_SUBDIRECTORY(contrib)
   ADD_SUBDIRECTORY(demo)
   ADD_SUBDIRECTORY(tools)
@@ -189 +150 @@
 ENDIF()
 
-CONFIGURE_FILE(
-  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
-  ${PROJECT_BINARY_DIR}/cmake/version.cmake
-  @ONLY
-)
-
-SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
-STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
-SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
-ADD_CUSTOM_TARGET(dist
-  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
-  COMMAND hg archive ${ARCHIVE_NAME}
-  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
-  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
-  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
-  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
-  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
-  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
-  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
-  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
-  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
-  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
-  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
-  DEPENDS html
-  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
-
-# CPACK config (Basically for NSIS)
 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})

INSTALL

@@ -2 +2 @@
 =========================
 
-This file contains instructions for building and installing LEMON from
-source on Linux. The process on Windows is similar.
+Since you are reading this I assume you already obtained one of the release
+tarballs and successfully extracted it. The latest version of LEMON is
+available at our web page (http://lemon.cs.elte.hu/).
 
-Note that it is not necessary to install LEMON in order to use
-it. Instead, you can easily integrate it with your own code
-directly. For instructions, see
-https://lemon.cs.elte.hu/trac/lemon/wiki/HowToCompile
-
+LEMON provides two different build environments, one is based on "autotool",
+while the other is based on "cmake". This file contains instructions only for
+the former one, which is the recommended build environment on Linux, Mac OSX
+and other unices or if you use Cygwin on Windows. For cmake installation
+instructions visit http://lemon.cs.elte.hu.
 
 In order to install LEMON from the extracted source tarball you have to
 issue the following commands:
 
-   1. Step into the root of the source directory.
+   1. `cd lemon-x.y.z'
 
-      $ cd lemon-x.y.z
+      This command changes to the directory which was created when you
+      extracted the sources. The x.y.z part is a version number.
 
-   2. Create a build subdirectory and step into it.
+   2. `./configure'
 
-      $ mkdir build
-      $ cd build
+      This command runs the configure shell script, which does some checks and
+      creates the makefiles.
 
-   3. Perform system checks and create the makefiles.
+   3. `make'
 
-      $ cmake ..
+      This command compiles the non-template part of LEMON into libemon.a
+      file. It also compiles the programs in the tools subdirectory by
+      default.
 
-   4. Build LEMON.
+   4. `make check'
 
-      $ make 
+      This step is optional, but recommended. It runs the test programs that
+      we developed for LEMON to check whether the library works properly on
+      your platform.
 
-      This command compiles the non-template part of LEMON into
-      libemon.a file. It also compiles the programs in the 'tools' and
-      'demo' subdirectories.
-
-   5. [Optional] Compile and run the self-tests.
-
-      $ make check
-
-   5. [Optional] Generate the user documentation.
-
-      $ make html
-
-      The release tarballs already include the documentation.
-
-      Note that for this step you need to have the following tools
-      installed: Python, Doxygen, Graphviz, Ghostscript, LaTeX.
-
-   6. [Optional] Install LEMON
-
-      $ make install
+   5. `make install'
 
       This command installs LEMON under /usr/local (you will need root
-      privileges to be able to do that). If you want to install it to
-      some other location, then pass the
-      -DCMAKE_INSTALL_PREFIX=DIRECTORY flag to cmake in Step 3.
-      For example:
-      
-      $ cmake -DCMAKE_INSTALL_PREFIX=/home/username/lemon'
+      privileges to be able to do that). If you want to install it to some
+      other location, then pass the --prefix=DIRECTORY flag to configure in
+      step 2. For example: `./configure --prefix=/home/username/lemon'.
+
+   6. `make install-html'
+
+      This command installs the documentation under share/doc/lemon/docs. The
+      generated documentation is included in the tarball. If you want to
+      generate it yourself, then run `make html'. Note that for this you need
+      to have the following programs installed: Doxygen, Graphviz, Ghostscript,
+      Latex.
+
 
 Configure Options and Variables
 ===============================
 
-In Step 3, you can customize the build process by passing options to CMAKE.
+In step 2 you can customize the actions of configure by setting variables
+and passing options to it. This can be done like this:
+`./configure [OPTION]... [VARIABLE=VALUE]...'
 
-$ cmake [OPTIONS] ..
+Below you will find some useful variables and options (see `./configure --help'
+for more):
 
-You find a list of the most useful options below.
+CXX='comp'
 
--DCMAKE_INSTALL_PREFIX=PREFIX
+  Change the C++ compiler to 'comp'.
+
+CXXFLAGS='flags'
+
+  Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'
+  turns on generation of aggressively optimized Pentium-M specific code.
+
+--prefix=PREFIX
 
   Set the installation prefix to PREFIX. By default it is /usr/local.
 
--DCMAKE_BUILD_TYPE=[Release|Debug|Maintainer|...]
+--enable-tools
 
-  This sets the compiler options. The choices are the following
+   Build the programs in the tools subdirectory (default).
 
-  'Release': A strong optimization is turned on (-O3 with gcc). This
-    is the default setting and we strongly recommend using this for
-    the final compilation.
+--disable-tools
 
-  'Debug': Optimization is turned off and debug info is added (-O0
-    -ggdb with gcc). If is recommended during the development.
+   Do not build the programs in the tools subdirectory.
 
-  'Maintainer': The same as 'Debug' but the compiler warnings are
-    converted to errors (-Werror with gcc). In addition, 'make' will
-    also automatically compile and execute the test codes. It is the
-    best way of ensuring that LEMON codebase is clean and safe.
+--with-glpk[=PREFIX]
 
-  'RelWithDebInfo': Optimized build with debug info.
+   Enable GLPK support (default). You should specify the prefix too if
+   you installed GLPK to some non-standard location (e.g. your home
+   directory). If it is not found, GLPK support will be disabled.
 
-  'MinSizeRel': Size optimized build (-Os with gcc)
+--with-glpk-includedir=DIR
 
--DTEST_WITH_VALGRIND=YES
+   The directory where the GLPK header files are located. This is only
+   useful when the GLPK headers and libraries are not under the same
+   prefix (which is unlikely).
 
-  Using this, the test codes will be executed using valgrind. It is a
-  very effective way of identifying indexing problems and memory leaks.
+--with-glpk-libdir=DIR
 
--DCMAKE_CXX_COMPILER=path-to-compiler
+   The directory where the GLPK libraries are located. This is only
+   useful when the GLPK headers and libraries are not under the same
+   prefix (which is unlikely).
 
-  Change the compiler to be used.
+--without-glpk
 
--DBUILD_SHARED_LIBS=TRUE
+   Disable GLPK support.
 
-  Build shared library instead of static one. Think twice if you
-  really want to use this option.
+--with-cplex[=PREFIX]
 
--DGLPK_ROOT_DIR=DIRECTORY
--DCOIN_ROOT_DIR=DIRECTORY
--DCPLEX_ROOT_DIR=DIRECTORY
+   Enable CPLEX support (default). You should specify the prefix too
+   if you installed CPLEX to some non-standard location
+   (e.g. /opt/ilog/cplex75). If it is not found, CPLEX support will be
+   disabled.
 
-  Install root directory prefixes of optional third party libraries.
+--with-cplex-includedir=DIR
+
+   The directory where the CPLEX header files are located. This is
+   only useful when the CPLEX headers and libraries are not under the
+   same prefix (e.g.  /usr/local/cplex/cplex75/include).
+
+--with-cplex-libdir=DIR
+
+   The directory where the CPLEX libraries are located. This is only
+   useful when the CPLEX headers and libraries are not under the same
+   prefix (e.g.
+   /usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_pic_mt).
+
+--without-cplex
+
+   Disable CPLEX support.
+
+--with-soplex[=PREFIX]
+
+   Enable SoPlex support (default). You should specify the prefix too if
+   you installed SoPlex to some non-standard location (e.g. your home
+   directory). If it is not found, SoPlex support will be disabled.
+
+--with-soplex-includedir=DIR
+
+   The directory where the SoPlex header files are located. This is only
+   useful when the SoPlex headers and libraries are not under the same
+   prefix (which is unlikely).
+
+--with-soplex-libdir=DIR
+
+   The directory where the SoPlex libraries are located. This is only
+   useful when the SoPlex headers and libraries are not under the same
+   prefix (which is unlikely).
+
+--without-soplex
+
+   Disable SoPlex support.
+
+--with-coin[=PREFIX]
+
+   Enable support for COIN-OR solvers (CLP and CBC). You should
+   specify the prefix too. (by default, COIN-OR tools install
+   themselves to the source code directory). This command enables the
+   solvers that are actually found.
+
+--with-coin-includedir=DIR
+
+   The directory where the COIN-OR header files are located. This is
+   only useful when the COIN-OR headers and libraries are not under
+   the same prefix (which is unlikely).
+
+--with-coin-libdir=DIR
+
+   The directory where the COIN-OR libraries are located. This is only
+   useful when the COIN-OR headers and libraries are not under the
+   same prefix (which is unlikely).
+
+--without-coin
+
+   Disable COIN-OR support.
+
 
 Makefile Variables
 ==================
 
-make VERBOSE=1
+Some Makefile variables are reserved by the GNU Coding Standards for
+the use of the "user" - the person building the package. For instance,
+CXX and CXXFLAGS are such variables, and have the same meaning as
+explained in the previous section. These variables can be set on the
+command line when invoking `make' like this:
+`make [VARIABLE=VALUE]...'
 
-   This results in a more verbose output by showing the full
-   compiler and linker commands.
+WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
+to hold several compiler flags related to warnings. Its default value
+can be overridden when invoking `make'. For example to disable all
+warning flags use `make WARNINGCXXFLAGS='.
+
+In order to turn off a single flag from the default set of warning
+flags, you can use the CXXFLAGS variable, since this is passed after
+WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
+used by default when g++ is detected) you can use
+`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

LICENSE

@@ -2 +2 @@
 copyright/license.
 
-Copyright (C) 2003-2012 Egervary Jeno Kombinatorikus Optimalizalasi
+Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 EGRES).

cmake/version.cmake.in

@@ -1 @@
-SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")
+SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")

doc/CMakeLists.txt

@@ -17 +17 @@
   @ONLY
 )
-
-# Copy doc from source (if exists)
-IF(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/html AND 
-    NOT EXISTS ${CMAKE_CURRENT_BINARY_DIR}/html/index.html)
-  MESSAGE(STATUS "Copy doc from source tree")
-  EXECUTE_PROCESS(
-    COMMAND cmake -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/html ${CMAKE_CURRENT_BINARY_DIR}/html
-    )
-ENDIF()
 
 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)

doc/Doxyfile.in

@@ -96 +96 @@
                          "@abs_top_srcdir@/lemon/concepts" \
                          "@abs_top_srcdir@/demo" \
-                         "@abs_top_srcdir@/contrib" \
                          "@abs_top_srcdir@/tools" \
                          "@abs_top_srcdir@/test/test_tools.h" \

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

@@ -407 +407 @@
    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).
 */
 
@@ -472 +472 @@
   \ref dasdan98minmeancycle.
 
-In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
+In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
 most efficient one, though the best known theoretical bound on its running
 time is exponential.
@@ -540 +540 @@
 
 /**
-@defgroup planar Planar Embedding and Drawing
+@defgroup planar Planarity Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing
@@ -552 +552 @@
 
 /**
-@defgroup approx_algs Approximation Algorithms
+@defgroup approx Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -558 +558 @@
 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

@@ -5 +5 @@
 
 CONFIGURE_FILE(
-  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.in
+  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
   ${CMAKE_CURRENT_BINARY_DIR}/config.h
 )
 
 CONFIGURE_FILE(
-  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
+  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
   ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
   @ONLY

lemon/bits/alteration_notifier.h

@@ -24 +24 @@
 
 #include <lemon/core.h>
-#include <lemon/bits/lock.h>
 
 //\ingroup graphbits
@@ -253 +252 @@
     typedef std::list<ObserverBase*> Observers;
     Observers _observers;
-    lemon::bits::Lock _lock;
+
 
   public:
@@ -334 +333 @@
 
     void attach(ObserverBase& observer) {
-      _lock.lock();
       observer._index = _observers.insert(_observers.begin(), &observer);
       observer._notifier = this;
-      _lock.unlock();
     }
 
     void detach(ObserverBase& observer) {
-      _lock.lock();
       _observers.erase(observer._index);
       observer._index = _observers.end();
       observer._notifier = 0;
-      _lock.unlock();
     }
 

lemon/bits/windows.cc

@@ -131 +131 @@
 #endif
     }
-
-    WinLock::WinLock() {
-#ifdef WIN32
-      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
-      InitializeCriticalSection(lock);
-      _repr = lock;
-#endif
-    }
-    
-    WinLock::~WinLock() {
-#ifdef WIN32
-      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
-      DeleteCriticalSection(lock);
-      delete lock;
-#endif
-    }
-
-    void WinLock::lock() {
-#ifdef WIN32
-      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
-      EnterCriticalSection(lock);
-#endif
-    }
-
-    void WinLock::unlock() {
-#ifdef WIN32
-      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
-      LeaveCriticalSection(lock);
-#endif
-    }
   }
 }

lemon/bits/windows.h

@@ -29 +29 @@
     std::string getWinFormattedDate();
     int getWinRndSeed();
-
-    class WinLock {
-    public:
-      WinLock();
-      ~WinLock();
-      void lock();
-      void unlock();
-    private:
-      void *_repr;
-    };
   }
 }

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 Capacity bounds and supply values must be integer, but
-  /// arc costs can be arbitrary real numbers.
-  /// \warning This algorithm does not support negative costs for
-  /// arcs having infinite upper bound.
+  /// \warning Both number types must be signed and all input data must
+  /// be integer.
+  /// \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/config.h.in

@@ -1 @@
-#define LEMON_VERSION "@PROJECT_VERSION@"
-#cmakedefine LEMON_HAVE_LONG_LONG 1
-#cmakedefine LEMON_HAVE_LP 1
-#cmakedefine LEMON_HAVE_MIP 1
-#cmakedefine LEMON_HAVE_GLPK 1
-#cmakedefine LEMON_HAVE_CPLEX 1
-#cmakedefine LEMON_HAVE_CLP 1
-#cmakedefine LEMON_HAVE_CBC 1
-#cmakedefine LEMON_USE_PTHREAD 1
-#cmakedefine LEMON_USE_WIN32_THREADS 1
+/* The version string */
+#undef LEMON_VERSION
+
+/* Define to 1 if you have long long */
+#undef LEMON_HAVE_LONG_LONG
+
+/* Define to 1 if you have any LP solver. */
+#undef LEMON_HAVE_LP
+
+/* Define to 1 if you have any MIP solver. */
+#undef LEMON_HAVE_MIP
+
+/* Define to 1 if you have CPLEX. */
+#undef LEMON_HAVE_CPLEX
+
+/* Define to 1 if you have GLPK. */
+#undef LEMON_HAVE_GLPK
+
+/* Define to 1 if you have SOPLEX */
+#undef LEMON_HAVE_SOPLEX
+
+/* Define to 1 if you have CLP */
+#undef LEMON_HAVE_CLP
+
+/* Define to 1 if you have CBC */
+#undef LEMON_HAVE_CBC

lemon/core.h

@@ -447 +447 @@
 
   }
-
-  /// \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()
@@ -238 +234 @@
     };
 
+    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
     typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 
@@ -288 +285 @@
     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 +339 @@
     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 +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.
     ///
@@ -488 +494 @@
     /// \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 +508 @@
     /// \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 +572 @@
     }
 
-    /// \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 +608 @@
       _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 +887 @@
       }
 
+      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 +902 @@
       _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 +911 @@
           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 +948 @@
         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 +970 @@
     }
 
-    // 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 +1005 @@
       }
       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 +1017 @@
       }
       if (total_excess == 0) return;
-      _buckets[0] = b0;
 
       // Search the buckets
@@ -1279 +1038 @@
                 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 +1051 @@
                       _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 +1087 @@
     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 +1120 @@
 
           // 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 +1154 @@
             // Step back
             if (tip != start) {
-              int pa = path.back();
-              path_arc[pa] = false;
-              tip = _source[pa];
+              tip = _source[path.back()];
               path.pop_back();
             }
@@ -1423 +1162 @@
 
           // Augment along the found path (as much flow as possible)
-        augment:
           Value delta;
           int pa, u, v = start;
@@ -1430 +1168 @@
             u = v;
             v = _target[pa];
-            path_arc[pa] = false;
             delta = std::min(_res_cap[pa], _excess[u]);
             _res_cap[pa] -= delta;
@@ -1436 +1173 @@
             _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 +1189 @@
     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 +1278 @@
                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 +1298 @@
 
           // 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;
           }
         }

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/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/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/lemon.pc.in

@@ -1 @@
-prefix=@CMAKE_INSTALL_PREFIX@
-exec_prefix=@CMAKE_INSTALL_PREFIX@/bin
-libdir=@CMAKE_INSTALL_PREFIX@/lib
-includedir=@CMAKE_INSTALL_PREFIX@/include
+prefix=@prefix@
+exec_prefix=@exec_prefix@
+libdir=@libdir@
+includedir=@includedir@
 
-Name: @PROJECT_NAME@
+Name: @PACKAGE_NAME@
 Description: Library for Efficient Modeling and Optimization in Networks
-Version: @PROJECT_VERSION@
+Version: @PACKAGE_VERSION@
 Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
 Cflags: -I${includedir}

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.
   ///
@@ -123 +122 @@
     /// the \ref run() function.
     ///
-    /// \ref NetworkSimplex provides five different implementations for
-    /// the pivot strategy that significantly affects the running time
+    /// \ref NetworkSimplex provides five different pivot rule
+    /// implementations that significantly affect the running time
     /// of the algorithm.
-    /// According to experimental tests conducted on various problem
-    /// instances, \ref BLOCK_SEARCH "Block Search" and
-    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
-    /// to be the most efficient.
-    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
-    /// seemed to be slightly more robust, it is used by default.
-    /// However, another pivot rule can easily be selected using the
-    /// \ref run() function with the proper parameter.
+    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
+    /// 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()
+    /// function with the proper parameter.
     enum PivotRule {
 
@@ -159 +155 @@
       /// The \e Altering \e Candidate \e List pivot rule.
       /// It is a modified version of the Candidate List method.
-      /// It keeps only a few of the best eligible arcs from the former
+      /// It keeps only the several best eligible arcs from the former
       /// candidate list and extends this list in every iteration.
       ALTERING_LIST
@@ -171 +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
@@ -182 +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:
@@ -225 +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;
 
@@ -256 +251 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -308 +303 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -347 +342 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -420 +415 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -523 +518 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const CharVector &_state;
+      const StateVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -542 +537 @@
         SortFunc(const CostVector &map) : _map(map) {}
         bool operator()(int left, int right) {
-          return _map[left] < _map[right];
+          return _map[left] > _map[right];
         }
       };
@@ -560 +555 @@
         const double BLOCK_SIZE_FACTOR = 1.0;
         const int MIN_BLOCK_SIZE = 10;
-        const double HEAD_LENGTH_FACTOR = 0.01;
+        const double HEAD_LENGTH_FACTOR = 0.1;
         const int MIN_HEAD_LENGTH = 3;
 
@@ -576 +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];
           }
@@ -592 +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;
           }
@@ -604 +597 @@
         }
         for (e = 0; e != _next_arc; ++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;
           }
@@ -619 +612 @@
       search_end:
 
-        // Perform partial sort operation on the candidate list
-        int new_length = std::min(_head_length + 1, _curr_length);
-        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
-                          _candidates.begin() + _curr_length, _sort_func);
-
-        // Select the entering arc and remove it from the list
+        // Make heap of the candidate list (approximating a partial sort)
+        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
+                   _sort_func );
+
+        // Pop the first element of the heap
         _in_arc = _candidates[0];
         _next_arc = e;
-        _candidates[0] = _candidates[new_length - 1];
-        _curr_length = new_length - 1;
+        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
+                  _sort_func );
+        _curr_length = std::min(_head_length, _curr_length - 1);
         return true;
       }
@@ -641 +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),
@@ -739 +731 @@
     ///
     /// \return <tt>(*this)</tt>
-    ///
-    /// \sa supplyType()
     template<typename SupplyMap>
     NetworkSimplex& supplyMap(const SupplyMap& map) {
@@ -757 +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.
     ///
@@ -924 +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);
@@ -938 +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) {
@@ -944 +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 {
@@ -1127 +1117 @@
           _state[e] = STATE_TREE;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _source[e] = u;
@@ -1134 +1124 @@
             _cost[e] = 0;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _source[e] = _root;
@@ -1154 +1144 @@
           _last_succ[u] = u;
           if (_supply[u] >= 0) {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1164 +1154 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = ART_COST;
             _pred[u] = f;
@@ -1195 +1185 @@
           _last_succ[u] = u;
           if (_supply[u] <= 0) {
-            _pred_dir[u] = DIR_DOWN;
+            _forward[u] = false;
             _pi[u] = 0;
             _pred[u] = e;
@@ -1205 +1195 @@
             _state[e] = STATE_TREE;
           } else {
-            _pred_dir[u] = DIR_UP;
+            _forward[u] = true;
             _pi[u] = -ART_COST;
             _pred[u] = f;
@@ -1248 +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];
@@ -1258 +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;
@@ -1275 +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;
@@ -1308 +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;
         }
       }
@@ -1326 +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];
@@ -1331 +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]) {

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.
@@ -149 +149 @@
     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.
@@ -157 +157 @@
     }
 
-    /// \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.
@@ -245 +245 @@
   ///
   /// 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.
@@ -354 +354 @@
     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.
@@ -361 +361 @@
     }
 
-    /// \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);
@@ -422 +422 @@
   ///
   /// 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.
@@ -544 +544 @@
     };
 
-    /// \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 {
@@ -556 +556 @@
     }
 
-    /// \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;
@@ -775 +775 @@
   ///
   /// 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.
@@ -884 +884 @@
     };
 
-    /// \brief The n-th arc.
+    /// \brief The nth arc.
     ///
     /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
@@ -891 +891 @@
     }
 
-    /// \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);
@@ -1095 +1095 @@
   ///
   /// 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.

test/CMakeLists.txt

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

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;
@@ -54 +52 @@
     }
   }
-  
+
   // 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);
-
-  typename GR::template NodeMap<SmartDigraph::Node> ncr(to);
-  typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);
+  ListDigraph to;
+  ListDigraph::NodeMap<int> tnm(to);
+  ListDigraph::ArcMap<int> tam(to);
+  ListDigraph::Node tn;
+  ListDigraph::Arc ta;
+
+  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).
@@ -89 +87 @@
   }
 
-  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.");
   }
@@ -106 +104 @@
 }
 
-template <typename GR>
 void graph_copy_test() {
   const int nn = 10;
@@ -139 +136 @@
 
   // 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;
-
-  SmartGraph::NodeMap<typename GR::Node> nr(from);
-  SmartGraph::ArcMap<typename GR::Arc> ar(from);
-  SmartGraph::EdgeMap<typename GR::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 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<ListGraph::Node> nr(from);
+  SmartGraph::ArcMap<ListGraph::Arc> ar(from);
+  SmartGraph::EdgeMap<ListGraph::Edge> er(from);
+
+  ListGraph::NodeMap<SmartGraph::Node> ncr(to);
+  ListGraph::ArcMap<SmartGraph::Arc> acr(to);
+  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
 
   graphCopy(from, to).
@@ -188 +185 @@
   }
 
-  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.");
   }
@@ -212 +209 @@
 
 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;