Diff [d3dcc49e64033041370e77c0c7488499bbf7241f:a2d142bb5d3c8b382e0530d3253fe19dbe6883dd] for / – LEMON

AUTHORS

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

CMakeLists.txt

-                      r912
+                      r1017
 ELSE()
   EXECUTE_PROCESS(
+    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
+    COMMAND
+    hg log -r. --template "{latesttag}"
     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     OUTPUT_VARIABLE HG_REVISION_PATH
+    OUTPUT_VARIABLE HG_REVISION_TAG
     ERROR_QUIET
     OUTPUT_STRIP_TRAILING_WHITESPACE
+  )
   EXECUTE_PROCESS(
+    COMMAND hg id -i
+    COMMAND
+    hg log -r. --template "{latesttagdistance}"
     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     OUTPUT_VARIABLE HG_REVISION
+    OUTPUT_VARIABLE HG_REVISION_DIST
     ERROR_QUIET
     OUTPUT_STRIP_TRAILING_WHITESPACE
+  )
+  IF(HG_REVISION STREQUAL "")
+  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 "")
     SET(HG_REVISION_ID "hg-tip")
   ELSE()
+    IF(HG_REVISION_PATH STREQUAL "")
+      SET(HG_REVISION_ID ${HG_REVISION})
+    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})
     ELSE()
+      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
+      SET(HG_REVISION
+        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
     ENDIF()
   ENDIF()
+  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
+  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
 ENDIF()
 …
 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(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
 …
     # C4996: 'function': was declared deprecated
   ELSE()
     SET(CXX_WARNING "-Wall -W")
+    SET(CXX_WARNING "-Wall")
   ENDIF()
 ENDIF()
 …
 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
+SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
+IF(MSVC)
+  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     "Flags used by the C++ compiler during maintainer builds."
     FORCE )
 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
+    )
+  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     "Flags used by the C compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    )
+  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
+    "Flags used for linking binaries during maintainer builds."
+    )
+  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
+    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
+    "Flags used by the shared libraries linker during maintainer builds."
+    )
+ELSE()
+  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
+    "Flags used by the C++ compiler during maintainer builds."
+    )
+  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
+    "Flags used by the C compiler during maintainer builds."
+    )
+  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
+    )
+  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 )
+    )
+ENDIF()
 MARK_AS_ADVANCED(
     CMAKE_CXX_FLAGS_MAINTAINER
 …
 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()
 ENABLE_TESTING()
 …
 ADD_SUBDIRECTORY(lemon)
 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+  ADD_SUBDIRECTORY(contrib)
   ADD_SUBDIRECTORY(demo)
   ADD_SUBDIRECTORY(tools)
 …
 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

-                      r824
+                      r992
 =========================
+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/).
+This file contains instructions for building and installing LEMON from
+source on Linux. The process on Windows is similar.
+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.
+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
 In order to install LEMON from the extracted source tarball you have to
 issue the following commands:
 . `cd lemon-x.y.z'
+. Step into the root of the source directory.
+      This command changes to the directory which was created when you
+      extracted the sources. The x.y.z part is a version number.
+      $ cd lemon-x.y.z
 . `./configure'
+. Create a build subdirectory and step into it.
       This command runs the configure shell script, which does some checks and
       creates the makefiles.
+      $ mkdir build
+      $ cd build
 . `make'
+. Perform system checks and create the makefiles.
+      This command compiles the non-template part of LEMON into libemon.a
+      file. It also compiles the programs in the tools subdirectory by
+      default.
+      $ cmake ..
 . `make check'
+. Build LEMON.
+      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.
+      $ make
+. `make install'
+      This command compiles the non-template part of LEMON into
+      libemon.a file. It also compiles the programs in the 'tools' and
+      'demo' subdirectories.
+. [Optional] Compile and run the self-tests.
+      $ make check
+. [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.
+. [Optional] Install LEMON
+      $ 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 --prefix=DIRECTORY flag to configure in
+      step 2. For example: `./configure --prefix=/home/username/lemon'.
+. `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.
+      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'
 Configure Options and Variables
 ===============================
+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]...'
+In Step 3, you can customize the build process by passing options to CMAKE.
+Below you will find some useful variables and options (see `./configure --help'
+for more):
+$ cmake [OPTIONS] ..
+CXX='comp'
+You find a list of the most useful options below.
+  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
+-DCMAKE_INSTALL_PREFIX=PREFIX
   Set the installation prefix to PREFIX. By default it is /usr/local.
 --enable-tools
+-DCMAKE_BUILD_TYPE=[Release|Debug|Maintainer|...]
    Build the programs in the tools subdirectory (default).
+  This sets the compiler options. The choices are the following
+--disable-tools
+  '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.
+   Do not build the programs in the tools subdirectory.
+  'Debug': Optimization is turned off and debug info is added (-O0
+    -ggdb with gcc). If is recommended during the development.
+--with-glpk[=PREFIX]
+  '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.
+   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.
+  'RelWithDebInfo': Optimized build with debug info.
+--with-glpk-includedir=DIR
+  'MinSizeRel': Size optimized build (-Os with gcc)
+   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).
+-DTEST_WITH_VALGRIND=YES
+--with-glpk-libdir=DIR
+  Using this, the test codes will be executed using valgrind. It is a
+  very effective way of identifying indexing problems and memory leaks.
+   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).
+-DCMAKE_CXX_COMPILER=path-to-compiler
+--without-glpk
+  Change the compiler to be used.
+   Disable GLPK support.
+-DBUILD_SHARED_LIBS=TRUE
+--with-cplex[=PREFIX]
+  Build shared library instead of static one. Think twice if you
+  really want to use this option.
+   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.
+-DGLPK_ROOT_DIR=DIRECTORY
+-DCOIN_ROOT_DIR=DIRECTORY
+-DCPLEX_ROOT_DIR=DIRECTORY
+--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.
+  Install root directory prefixes of optional third party libraries.
 Makefile Variables
 ==================
+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]...'
+make VERBOSE=1
+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"'.
+   This results in a more verbose output by showing the full
+   compiler and linker commands.

LICENSE

r879	r992
2	2	copyright/license.
3	3
4		Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
	4	Copyright (C) 2003-2012 Egervary Jeno Kombinatorikus Optimalizalasi
5	5	Kutatocsoport (Egervary Combinatorial Optimization Research Group,
6	6	EGRES).

cmake/FindCOIN.cmake

-                      r634
+                      r973
 FIND_LIBRARY(COIN_CBC_LIBRARY
   NAMES Cbc libCbc
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
   NAMES CbcSolver libCbcSolver
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_CGL_LIBRARY
   NAMES Cgl libCgl
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_CLP_LIBRARY
   NAMES Clp libClp
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
   NAMES CoinUtils libCoinUtils
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_OSI_LIBRARY
   NAMES Osi libOsi
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
   NAMES OsiCbc libOsiCbc
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
   NAMES OsiClp libOsiClp
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
   NAMES OsiVol libOsiVol
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 FIND_LIBRARY(COIN_VOL_LIBRARY
   NAMES Vol libVol
+  HINTS ${COIN_ROOT_DIR}/lib/coin
+  HINTS ${COIN_ROOT_DIR}/lib
+)
+FIND_LIBRARY(COIN_ZLIB_LIBRARY
+  NAMES z libz
+  HINTS ${COIN_ROOT_DIR}/lib/coin
+  HINTS ${COIN_ROOT_DIR}/lib
+)
+FIND_LIBRARY(COIN_BZ2_LIBRARY
+  NAMES bz2 libbz2
+  HINTS ${COIN_ROOT_DIR}/lib/coin
   HINTS ${COIN_ROOT_DIR}/lib
+)
 …
   COIN_OSI_CBC_LIBRARY
   COIN_OSI_CLP_LIBRARY
   COIN_OSI_VOL_LIBRARY
   COIN_VOL_LIBRARY
+  # COIN_OSI_VOL_LIBRARY
+  # COIN_VOL_LIBRARY
+)
 IF(COIN_FOUND)
   SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
+  SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")
+  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
+  SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
+  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_ZLIB_LIBRARY};${COIN_BZ2_LIBRARY}")
+  IF(COIN_ZLIB_LIBRARY)
+    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_ZLIB_LIBRARY}")
+  ENDIF(COIN_ZLIB_LIBRARY)
+   IF(COIN_BZ2_LIBRARY)
+    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_BZ2_LIBRARY}")
+  ENDIF(COIN_BZ2_LIBRARY)
+  SET(COIN_CBC_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_ZLIB_LIBRARY};${COIN_BZ2_LIBRARY};${COIN_CLP_LIBRARIES}")
+  SET(COIN_LIBRARIES ${COIN_CBC_LIBRARIES})
 ENDIF(COIN_FOUND)
 …
   COIN_OSI_VOL_LIBRARY
   COIN_VOL_LIBRARY
+  COIN_ZLIB_LIBRARY
+  COIN_BZ2_LIBRARY
+)

cmake/FindCPLEX.cmake

-                      r636
+                      r972
 FIND_PATH(CPLEX_INCLUDE_DIR
   ilcplex/cplex.h
   PATHS "C:/ILOG/CPLEX91/include"
   PATHS "/opt/ilog/cplex91/include"
+  PATHS "C:/ILOG/CPLEX/include"
+  PATHS "/opt/ilog/cplex/include"
   HINTS ${CPLEX_ROOT_DIR}/include
+)
 FIND_LIBRARY(CPLEX_LIBRARY
   cplex91
   PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda"
   PATHS "/opt/ilog/cplex91/bin"
+  cplex
+  PATHS "C:/ILOG/CPLEX/lib/msvc7/stat_mda"
+  PATHS "/opt/ilog/cplex/bin"
   HINTS ${CPLEX_ROOT_DIR}/bin
+  HINTS ${CPLEX_ROOT_DIR}/lib
+)
 …
 FIND_PATH(CPLEX_BIN_DIR
+  cplex91.dll
+  PATHS "C:/ILOG/CPLEX91/bin/x86_win32"
+  cplex.dll
+  PATHS "C:/ILOG/CPLEX/bin/x86_win32"
+  HINTS ${CPLEX_ROOT_DIR}/bin
+)

cmake/version.cmake.in

r678	r983
1		SET(LEMON_VERSION "@~~PACKAGE~~_VERSION@" CACHE STRING "LEMON version string.")
	1	SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")

doc/CMakeLists.txt

-                      r1032
+                      r1038
   @ONLY
+)
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
+  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
+  @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

-                      r912
+                      r966
 # Doxyfile 1.5.9
+# Doxyfile 1.7.3
 #---------------------------------------------------------------------------
 …
 #---------------------------------------------------------------------------
 DOXYFILE_ENCODING      = UTF-8
+PROJECT_NAME           = @PACKAGE_NAME@
+PROJECT_NUMBER         = @PACKAGE_VERSION@
+PROJECT_NAME           =
+PROJECT_NUMBER         =
+PROJECT_BRIEF          =
+PROJECT_LOGO           =
 OUTPUT_DIRECTORY       =
 CREATE_SUBDIRS         = NO
 …
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
+EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
 …
 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
 …
                          "@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
 …
 FILTER_PATTERNS        =
 FILTER_SOURCE_FILES    = NO
+FILTER_SOURCE_PATTERNS =
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 …
 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  = NO
+HTML_DYNAMIC_SECTIONS  = YES
 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               =
 …
 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
 …
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
+LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
 …
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
 # Options related to the search engine
+# Configuration::additions related to external references
 #---------------------------------------------------------------------------
 TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 …
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
+DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
 …
 DOT_PATH               =
 DOTFILE_DIRS           =
+MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
 …
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
-#---------------------------------------------------------------------------
-# Configuration::additions related to the search engine
-#---------------------------------------------------------------------------
-SEARCHENGINE           = NO

doc/DoxygenLayout.xml

-                      r316
+                      r928
   <navindex>
     <tab type="mainpage" visible="yes" title=""/>
     <tab type="modules" visible="yes" title=""/>
+    <tab type="modules" visible="yes" title="" intro=""/>
     <tab type="classes" visible="yes" title="">
       <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 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>
     <tab type="namespaces" visible="yes" title="">
       <tab type="namespaces" visible="yes" title=""/>
       <tab type="namespacemembers" visible="yes" title=""/>
+      <tab type="namespaces" visible="yes" title="" intro=""/>
+      <tab type="namespacemembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="files" visible="yes" title="">
       <tab type="files" visible="yes" title=""/>
       <tab type="globals" visible="yes" title=""/>
+      <tab type="files" visible="yes" title="" intro=""/>
+      <tab type="globals" visible="yes" title="" intro=""/>
     </tab>
     <tab type="dirs" visible="yes" title=""/>
     <tab type="examples" visible="yes" title=""/>
     <tab type="pages" visible="yes" title=""/>
+    <tab type="dirs" visible="yes" title="" intro=""/>
+    <tab type="examples" visible="yes" title="" intro=""/>
+    <tab type="pages" visible="yes" title="" intro=""/>
   </navindex>

doc/coding_style.dox

-                      r440
+                      r919
 \subsection pri-loc-var Private member variables
 Private member variables should start with underscore
+Private member variables should start with underscore.
 \code
 _start_with_underscores
+_start_with_underscore
 \endcode

doc/dirs.dox

-                      r440
+                      r925
 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

-                      r1036
+                      r1038
    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
+In general NetworkSimplex is the most efficient implementation,
+but in special cases other algorithms could be faster.
+In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
+implementations.
+\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
+several thousands of nodes) and on dense graphs, while \ref CostScaling is
+typically more efficient on large graphs (e.g. hundreds of thousands of
+nodes or above), especially if they are sparse.
+However, other algorithms could be faster in special cases.
 For example, if the total supply and/or capacities are rather small,
+CapacityScaling is usually the fastest algorithm (without effective scaling).
+\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
+These classes are intended to be used with integer-valued input data
+(capacities, supply values, and costs), except for \ref CapacityScaling,
+which is capable of handling real-valued arc costs (other numerical
+data are required to be integer).
 */
 …
 This group contains the algorithms for finding minimum mean cycles
 \ref clrs01algorithms, \ref amo93networkflows.
+\ref amo93networkflows, \ref karp78characterization.
 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
 …
 LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
+  \ref dasdan98minmeancycle.
+- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
   version of Karp's algorithm \ref dasdan98minmeancycle.
+  version of Karp's algorithm \ref hartmann93finding.
 - \ref HowardMmc Howard's policy iteration algorithm
   \ref dasdan98minmeancycle.
 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+  \ref dasdan98minmeancycle, \ref dasdan04experimental.
+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.
 …
 /**
 @defgroup planar Planarity Embedding and Drawing
+@defgroup planar Planar Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing

doc/lgf.dox

-                      r440
+                      r1024
 \endcode
+The \e LGF files can also contain bipartite graphs, in this case a
+\c @red_nodes and a \c @blue_nodes sections describe the node set of the
+graph. If a map is in both of these sections, then it can be used as a
+regular node map.
+\code
+ @red_nodes
+ label  only_red_map   name
+      "cherry"       "John"
+      "Santa Claus"  "Jack"
+      "blood"        "Jason"
+ @blue_nodes
+ label  name
+      "Elisabeth"
+      "Eve"
+\endcode
 The \c \@arcs section is very similar to the \c \@nodes section,
 it again starts with a header line describing the names of the maps,
 …
 \endcode
+If there is no map in the \c \@arcs section at all, then it must be
+indicated by a sole '-' sign in the first line.
+\code
+ @arcs
+         -
+   2
+   3
+   3
+\endcode
 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
 also store the edge set of an undirected graph. In such case there is
 a conventional method for store arc maps in the file, if two columns
 has the same caption with \c '+' and \c '-' prefix, then these columns
+have the same caption with \c '+' and \c '-' prefix, then these columns
 can be regarded as the values of an arc map.

doc/min_cost_flow.dox

r877	r1002
102	102	\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
103	103
104		However if the sum of the supply values is zero, then these two problems
	104	However, if the sum of the supply values is zero, then these two problems
105	105	are equivalent.
106	106	The \ref min_cost_flow_algs "algorithms" in LEMON support the general

doc/references.bib

-                      r904
+                      r1002
   title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
                   {O}ptimization in {N}etworks},
+  howpublished = {\url{http://lemon.cs.elte.hu/}},
+  year =         2009
+  howpublished = {\url{http://lemon.cs.elte.hu/}}
+}
 …
   volume =       23,
   pages =        {309-311}
+}
+@article{hartmann93finding,
+  author =       {Mark Hartmann and James B. Orlin},
+  title =        {Finding minimum cost to time ratio cycles with small
+                  integral transit times},
+  journal =      {Networks},
+  year =         1993,
+  volume =       23,
+  pages =        {567-574}
+}
 …
+}
+@article{dasdan04experimental,
+  author =       {Ali Dasdan},
+  title =        {Experimental analysis of the fastest optimum cycle
+                  ratio and mean algorithms},
+  journal =      {ACM Trans. Des. Autom. Electron. Syst.},
+  year =         2004,
+  volume =       9,
+  issue =        4,
+  pages =        {385-418}
+}
 %%%%% Minimum cost flow algorithms %%%%%

lemon/CMakeLists.txt

-                      r908
+                      r981
 CONFIGURE_FILE(
   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
+  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.in
   ${CMAKE_CURRENT_BINARY_DIR}/config.h
+)
 CONFIGURE_FILE(
   ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
+  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
   ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
   @ONLY
 …
   TARGETS lemon
   ARCHIVE DESTINATION lib
+  LIBRARY DESTINATION lib
   COMPONENT library
+)

lemon/adaptors.h

-                      r877
+                      r998
     /// and edge filter maps.
     SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
       initialize(graph, node_filter, edge_filter);
+      this->initialize(graph, node_filter, edge_filter);
+    }
 …
     /// Creates an undirected graph from the given digraph.
     Undirector(DGR& digraph) {
       initialize(digraph);
+      this->initialize(digraph);
+    }

lemon/bfs.h

r877	r976
1252	1252	}
1253	1253	_Visitor& visitor;
	1254	Constraints() {}
1254	1255	};
1255	1256	};

lemon/bits/alteration_notifier.h

-                      r440
+                      r979
 #include <lemon/core.h>
+#include <lemon/bits/lock.h>
 //\ingroup graphbits
 …
     typedef std::list<ObserverBase*> Observers;
     Observers _observers;
+    lemon::bits::Lock _lock;
   public:
 …
     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/bezier.h

r440	r997
160	160	const Point d=(a+b)/2;
161	161	const Point e=(b+c)/2;
162		const Point f=(d+e)/2;
	162	// const Point f=(d+e)/2;
163	163	R f1=_f(Bezier3(p1,a,d,e),_d);
164	164	R f2=_f(Bezier3(e,d,c,p4),_d);

lemon/bits/edge_set_extender.h

-                      r884
+                      r1000
     // Returns the base node of the iterator
     Node baseNode(const IncEdgeIt &e) const {
       return e.direction ? u(e) : v(e);
+      return e.direction ? this->u(e) : this->v(e);
+    }
     // Running node of the iterator
 …
     // Returns the running node of the iterator
     Node runningNode(const IncEdgeIt &e) const {
       return e.direction ? v(e) : u(e);
+      return e.direction ? this->v(e) : this->u(e);
+    }

lemon/bits/graph_extender.h

-                      r778
+                      r1027
     // Returns the base node of the iterator
     Node baseNode(const IncEdgeIt &edge) const {
       return edge._direction ? u(edge) : v(edge);
+      return edge._direction ? this->u(edge) : this->v(edge);
+    }
     // Running node of the iterator
 …
     // Returns the running node of the iterator
     Node runningNode(const IncEdgeIt &edge) const {
       return edge._direction ? v(edge) : u(edge);
+      return edge._direction ? this->v(edge) : this->u(edge);
+    }
 …
   };
+  // \ingroup _graphbits
+  //
+  // \brief Extender for the BpGraphs
+  template <typename Base>
+  class BpGraphExtender : public Base {
+    typedef Base Parent;
+  public:
+    typedef BpGraphExtender BpGraph;
+    typedef True UndirectedTag;
+    typedef typename Parent::Node Node;
+    typedef typename Parent::RedNode RedNode;
+    typedef typename Parent::BlueNode BlueNode;
+    typedef typename Parent::Arc Arc;
+    typedef typename Parent::Edge Edge;
+    // BpGraph extension
+    using Parent::first;
+    using Parent::next;
+    using Parent::id;
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+    int maxId(RedNode) const {
+      return Parent::maxRedId();
+    }
+    int maxId(BlueNode) const {
+      return Parent::maxBlueId();
+    }
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+    static Node fromId(int id, Node) {
+      return Parent::nodeFromId(id);
+    }
+    static Arc fromId(int id, Arc) {
+      return Parent::arcFromId(id);
+    }
+    static Edge fromId(int id, Edge) {
+      return Parent::edgeFromId(id);
+    }
+    Node u(Edge e) const { return this->redNode(e); }
+    Node v(Edge e) const { return this->blueNode(e); }
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if( n == u(e))
+        return v(e);
+      else if( n == v(e))
+        return u(e);
+      else
+        return INVALID;
+    }
+    Arc oppositeArc(const Arc &arc) const {
+      return Parent::direct(arc, !Parent::direction(arc));
+    }
+    using Parent::direct;
+    Arc direct(const Edge &edge, const Node &node) const {
+      return Parent::direct(edge, Parent::redNode(edge) == node);
+    }
+    RedNode asRedNode(const Node& node) const {
+      if (node == INVALID || Parent::blue(node)) {
+        return INVALID;
+      } else {
+        return Parent::asRedNodeUnsafe(node);
+      }
+    }
+    BlueNode asBlueNode(const Node& node) const {
+      if (node == INVALID || Parent::red(node)) {
+        return INVALID;
+      } else {
+        return Parent::asBlueNodeUnsafe(node);
+      }
+    }
+    // Alterable extension
+    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
+    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
+    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
+    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
+  protected:
+    mutable NodeNotifier node_notifier;
+    mutable RedNodeNotifier red_node_notifier;
+    mutable BlueNodeNotifier blue_node_notifier;
+    mutable ArcNotifier arc_notifier;
+    mutable EdgeNotifier edge_notifier;
+  public:
+    NodeNotifier& notifier(Node) const {
+      return node_notifier;
+    }
+    RedNodeNotifier& notifier(RedNode) const {
+      return red_node_notifier;
+    }
+    BlueNodeNotifier& notifier(BlueNode) const {
+      return blue_node_notifier;
+    }
+    ArcNotifier& notifier(Arc) const {
+      return arc_notifier;
+    }
+    EdgeNotifier& notifier(Edge) const {
+      return edge_notifier;
+    }
+    class NodeIt : public Node {
+      const BpGraph* _graph;
+    public:
+      NodeIt() {}
+      NodeIt(Invalid i) : Node(i) { }
+      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Node&>(*this));
+      }
+      NodeIt(const BpGraph& graph, const Node& node)
+        : Node(node), _graph(&graph) {}
+      NodeIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+    };
+    class RedNodeIt : public RedNode {
+      const BpGraph* _graph;
+    public:
+      RedNodeIt() {}
+      RedNodeIt(Invalid i) : RedNode(i) { }
+      explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<RedNode&>(*this));
+      }
+      RedNodeIt(const BpGraph& graph, const RedNode& node)
+        : RedNode(node), _graph(&graph) {}
+      RedNodeIt& operator++() {
+        _graph->next(static_cast<RedNode&>(*this));
+        return *this;
+      }
+    };
+    class BlueNodeIt : public BlueNode {
+      const BpGraph* _graph;
+    public:
+      BlueNodeIt() {}
+      BlueNodeIt(Invalid i) : BlueNode(i) { }
+      explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<BlueNode&>(*this));
+      }
+      BlueNodeIt(const BpGraph& graph, const BlueNode& node)
+        : BlueNode(node), _graph(&graph) {}
+      BlueNodeIt& operator++() {
+        _graph->next(static_cast<BlueNode&>(*this));
+        return *this;
+      }
+    };
+    class ArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+      ArcIt() { }
+      ArcIt(Invalid i) : Arc(i) { }
+      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Arc&>(*this));
+      }
+      ArcIt(const BpGraph& graph, const Arc& arc) :
+        Arc(arc), _graph(&graph) { }
+      ArcIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+    };
+    class OutArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+      OutArcIt() { }
+      OutArcIt(Invalid i) : Arc(i) { }
+      OutArcIt(const BpGraph& graph, const Node& node)
+        : _graph(&graph) {
+        _graph->firstOut(*this, node);
+      }
+      OutArcIt(const BpGraph& graph, const Arc& arc)
+        : Arc(arc), _graph(&graph) {}
+      OutArcIt& operator++() {
+        _graph->nextOut(*this);
+        return *this;
+      }
+    };
+    class InArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+      InArcIt() { }
+      InArcIt(Invalid i) : Arc(i) { }
+      InArcIt(const BpGraph& graph, const Node& node)
+        : _graph(&graph) {
+        _graph->firstIn(*this, node);
+      }
+      InArcIt(const BpGraph& graph, const Arc& arc) :
+        Arc(arc), _graph(&graph) {}
+      InArcIt& operator++() {
+        _graph->nextIn(*this);
+        return *this;
+      }
+    };
+    class EdgeIt : public Parent::Edge {
+      const BpGraph* _graph;
+    public:
+      EdgeIt() { }
+      EdgeIt(Invalid i) : Edge(i) { }
+      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Edge&>(*this));
+      }
+      EdgeIt(const BpGraph& graph, const Edge& edge) :
+        Edge(edge), _graph(&graph) { }
+      EdgeIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+    };
+    class IncEdgeIt : public Parent::Edge {
+      friend class BpGraphExtender;
+      const BpGraph* _graph;
+      bool _direction;
+    public:
+      IncEdgeIt() { }
+      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
+      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
+        _graph->firstInc(*this, _direction, node);
+      }
+      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
+        : _graph(&graph), Edge(edge) {
+        _direction = (_graph->source(edge) == node);
+      }
+      IncEdgeIt& operator++() {
+        _graph->nextInc(*this, _direction);
+        return *this;
+      }
+    };
+    // \brief Base node of the iterator
+    //
+    // Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+    // \brief Running node of the iterator
+    //
+    // Returns the running node (ie. the target in this case) of the
+    // iterator
+    Node runningNode(const OutArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+    // \brief Base node of the iterator
+    //
+    // Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+    // \brief Running node of the iterator
+    //
+    // Returns the running node (ie. the source in this case) of the
+    // iterator
+    Node runningNode(const InArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+    // Base node of the iterator
+    //
+    // Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &edge) const {
+      return edge._direction ? this->u(edge) : this->v(edge);
+    }
+    // Running node of the iterator
+    //
+    // Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &edge) const {
+      return edge._direction ? this->v(edge) : this->u(edge);
+    }
+    // Mappable extension
+    template <typename _Value>
+    class NodeMap
+      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
+    public:
+      explicit NodeMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      NodeMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+    private:
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+    template <typename _Value>
+    class RedNodeMap
+      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
+    public:
+      explicit RedNodeMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      RedNodeMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+    private:
+      RedNodeMap& operator=(const RedNodeMap& cmap) {
+        return operator=<RedNodeMap>(cmap);
+      }
+      template <typename CMap>
+      RedNodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+    template <typename _Value>
+    class BlueNodeMap
+      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
+    public:
+      explicit BlueNodeMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+    private:
+      BlueNodeMap& operator=(const BlueNodeMap& cmap) {
+        return operator=<BlueNodeMap>(cmap);
+      }
+      template <typename CMap>
+      BlueNodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+    template <typename _Value>
+    class ArcMap
+      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
+    public:
+      explicit ArcMap(const BpGraph& graph)
+        : Parent(graph) {}
+      ArcMap(const BpGraph& graph, const _Value& value)
+        : Parent(graph, value) {}
+    private:
+      ArcMap& operator=(const ArcMap& cmap) {
+        return operator=<ArcMap>(cmap);
+      }
+      template <typename CMap>
+      ArcMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+    template <typename _Value>
+    class EdgeMap
+      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
+    public:
+      explicit EdgeMap(const BpGraph& graph)
+        : Parent(graph) {}
+      EdgeMap(const BpGraph& graph, const _Value& value)
+        : Parent(graph, value) {}
+    private:
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+    // Alteration extension
+    RedNode addRedNode() {
+      RedNode node = Parent::addRedNode();
+      notifier(RedNode()).add(node);
+      notifier(Node()).add(node);
+      return node;
+    }
+    BlueNode addBlueNode() {
+      BlueNode node = Parent::addBlueNode();
+      notifier(BlueNode()).add(node);
+      notifier(Node()).add(node);
+      return node;
+    }
+    Edge addEdge(const RedNode& from, const BlueNode& to) {
+      Edge edge = Parent::addEdge(from, to);
+      notifier(Edge()).add(edge);
+      std::vector<Arc> av;
+      av.push_back(Parent::direct(edge, true));
+      av.push_back(Parent::direct(edge, false));
+      notifier(Arc()).add(av);
+      return edge;
+    }
+    void clear() {
+      notifier(Arc()).clear();
+      notifier(Edge()).clear();
+      notifier(Node()).clear();
+      notifier(BlueNode()).clear();
+      notifier(RedNode()).clear();
+      Parent::clear();
+    }
+    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
+    void build(const BpGraph& graph, NodeRefMap& nodeRef,
+               EdgeRefMap& edgeRef) {
+      Parent::build(graph, nodeRef, edgeRef);
+      notifier(RedNode()).build();
+      notifier(BlueNode()).build();
+      notifier(Node()).build();
+      notifier(Edge()).build();
+      notifier(Arc()).build();
+    }
+    void erase(const Node& node) {
+      Arc arc;
+      Parent::firstOut(arc, node);
+      while (arc != INVALID ) {
+        erase(arc);
+        Parent::firstOut(arc, node);
+      }
+      Parent::firstIn(arc, node);
+      while (arc != INVALID ) {
+        erase(arc);
+        Parent::firstIn(arc, node);
+      }
+      if (Parent::red(node)) {
+        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
+      } else {
+        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
+      }
+      notifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+    void erase(const Edge& edge) {
+      std::vector<Arc> av;
+      av.push_back(Parent::direct(edge, true));
+      av.push_back(Parent::direct(edge, false));
+      notifier(Arc()).erase(av);
+      notifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+    BpGraphExtender() {
+      red_node_notifier.setContainer(*this);
+      blue_node_notifier.setContainer(*this);
+      node_notifier.setContainer(*this);
+      arc_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+    }
+    ~BpGraphExtender() {
+      edge_notifier.clear();
+      arc_notifier.clear();
+      node_notifier.clear();
+      blue_node_notifier.clear();
+      red_node_notifier.clear();
+    }
+  };
+}

lemon/bits/solver_bits.h

r877	r989
45	45	void clear() {
46	46	first_item = -1;
	47	last_item = -1;
47	48	first_free_item = -1;
48	49	items.clear();

lemon/bits/traits.h

-                      r616
+                      r1026
         : Parent(_digraph, _value) {}
     };
+  };
+  template <typename GR, typename Enable = void>
+  struct RedNodeNotifierIndicator {
+    typedef InvalidType Type;
+  };
+  template <typename GR>
+  struct RedNodeNotifierIndicator<
+    GR,
+    typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::RedNodeNotifier Type;
+  };
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::RedNode> {
+  public:
+    typedef GR BpGraph;
+    typedef GR Graph;
+    typedef GR Digraph;
+    typedef typename GR::RedNode Item;
+    typedef typename GR::RedNodeIt ItemIt;
+    typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
+    template <typename V>
+    class Map : public GR::template RedNodeMap<V> {
+      typedef typename GR::template RedNodeMap<V> Parent;
+    public:
+      typedef typename GR::template RedNodeMap<V> Type;
+      typedef typename Parent::Value Value;
+      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
+      Map(const GR& _bpgraph, const Value& _value)
+        : Parent(_bpgraph, _value) {}
+     };
+  };
+  template <typename GR, typename Enable = void>
+  struct BlueNodeNotifierIndicator {
+    typedef InvalidType Type;
+  };
+  template <typename GR>
+  struct BlueNodeNotifierIndicator<
+    GR,
+    typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::BlueNodeNotifier Type;
+  };
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::BlueNode> {
+  public:
+    typedef GR BpGraph;
+    typedef GR Graph;
+    typedef GR Digraph;
+    typedef typename GR::BlueNode Item;
+    typedef typename GR::BlueNodeIt ItemIt;
+    typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
+    template <typename V>
+    class Map : public GR::template BlueNodeMap<V> {
+      typedef typename GR::template BlueNodeMap<V> Parent;
+    public:
+      typedef typename GR::template BlueNodeMap<V> Type;
+      typedef typename Parent::Value Value;
+      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
+      Map(const GR& _bpgraph, const Value& _value)
+        : Parent(_bpgraph, _value) {}
+     };
   };

lemon/bits/windows.cc

-                      r877
+                      r1001
 #include <unistd.h>
 #include <ctime>
+#ifndef WIN32
 #include <sys/times.h>
+#endif
 #include <sys/time.h>
 #endif
 …
 #endif
+    }
+    WinLock::WinLock() {
+#ifdef WIN32
+      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
+      InitializeCriticalSection(lock);
+      _repr = lock;
+#else
+      _repr = 0; //Just to avoid 'unused variable' warning with clang
+#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

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

lemon/capacity_scaling.h

-                      r877
+                      r1004
   /// solution method.
   ///
+  /// This algorithm is typically slower than \ref CostScaling and
+  /// \ref NetworkSimplex, but in special cases, it can be more
+  /// efficient than them.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
+  ///
   /// Most of the parameters of the problem (except for the digraph)
   /// can be given using separate functions, and the algorithm can be
 …
   /// consider to use the named template parameters instead.
   ///
+  /// \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.
+  /// \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.
 #ifdef DOXYGEN
   template <typename GR, typename V, typename C, typename TR>
 …
     ///
     /// Using this function has the same effect as using \ref supplyMap()
     /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// with 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.
     ///
 …
+    }
+    /// \brief Return the flow map (the primal solution).
+    /// \brief Copy the flow values (the primal solution) into the
+    /// given map.
     ///
     /// This function copies the flow value on each arc into the given
 …
+    }
+    /// \brief Return the potential map (the dual solution).
+    /// \brief Copy the potential values (the dual solution) into the
+    /// given map.
     ///
     /// This function copies the potential (dual value) of each node

lemon/cbc.cc

-                      r746
+                      r1000
 #include <coin/OsiSolverInterface.hpp>
-#ifdef COIN_HAS_CLP
 #include "coin/OsiClpSolverInterface.hpp"
-#endif
-#ifdef COIN_HAS_OSL
-#include "coin/OsiOslSolverInterface.hpp"
-#endif
 #include "coin/CbcCutGenerator.hpp"
 …
       delete _osi_solver;
+    }
-#ifdef COIN_HAS_CLP
     _osi_solver = new OsiClpSolverInterface();
-#elif COIN_HAS_OSL
-    _osi_solver = new OsiOslSolverInterface();
-#else
-#error Cannot instantiate Osi solver
-#endif
     _osi_solver->loadFromCoinModel(*_prob);
 …
       _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
-#ifdef COIN_HAS_CLP
       OsiClpSolverInterface* osiclp =
         dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver());
 …
         osiclp->setupForRepeatedUse(2, 0);
+      }
-#endif
       CbcRounding heuristic1(*_cbc_model);
 …
     _prob = new CoinModel();
-    rows.clear();
-    cols.clear();
+  }

lemon/circulation.h

r877	r998
573	573
574	574	Node act;
575		~~Node bact=INVALID;~~
576		~~Node last_activated=INVALID;~~
577	575	while((act=_level->highestActive())!=INVALID) {
578	576	int actlevel=(*_level)[act];

lemon/clp.cc

r877	r989
438	438	delete _prob;
439	439	_prob = new ClpSimplex();
440		~~rows.clear();~~
441		~~cols.clear();~~
442	440	_col_names_ref.clear();
443	441	_clear_temporals();

lemon/concept_check.h

-                      r440
+                      r997
   template <class T> inline void ignore_unused_variable_warning(const T&) { }
+  template <class T1, class T2>
+  inline void ignore_unused_variable_warning(const T1&, const T2&) { }
+  template <class T1, class T2, class T3>
+  inline void ignore_unused_variable_warning(const T1&, const T2&,
+                                             const T3&) { }
+  template <class T1, class T2, class T3, class T4>
+  inline void ignore_unused_variable_warning(const T1&, const T2&,
+                                             const T3&, const T4&) { }
+  template <class T1, class T2, class T3, class T4, class T5>
+  inline void ignore_unused_variable_warning(const T1&, const T2&,
+                                             const T3&, const T4&,
+                                             const T5&) { }
+  template <class T1, class T2, class T3, class T4, class T5, class T6>
+  inline void ignore_unused_variable_warning(const T1&, const T2&,
+                                             const T3&, const T4&,
+                                             const T5&, const T6&) { }
   ///\e

lemon/concepts/graph.h

-                      r877
+                      r1018
     class Graph {
     private:
       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+      /// Graphs are \e not copy constructible. Use GraphCopy instead.
       Graph(const Graph&) {}
       /// \brief Assignment of a graph to another one is \e not allowed.
       /// Use DigraphCopy instead.
+      /// Use GraphCopy instead.
       void operator=(const Graph&) {}

lemon/concepts/graph_components.h

-                      r877
+                      r1028
           bool b;
+          ignore_unused_variable_warning(b);
           b = (ia == ib) && (ia != ib);
           b = (ia == INVALID) && (ib != INVALID);
 …
         const _GraphItem &ia;
         const _GraphItem &ib;
+        Constraints() {}
       };
     };
 …
         const _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         const _Graph& graph;
+      Constraints() {}
+      };
+    };
+    /// \brief Base skeleton class for undirected bipartite graphs.
+    ///
+    /// This class describes the base interface of undirected
+    /// bipartite graph types.  All bipartite graph %concepts have to
+    /// conform to this class.  It extends the interface of \ref
+    /// BaseGraphComponent with an \c Edge type and functions to get
+    /// the end nodes of edges, to convert from arcs to edges and to
+    /// get both direction of edges.
+    class BaseBpGraphComponent : public BaseGraphComponent {
+    public:
+      typedef BaseBpGraphComponent BpGraph;
+      typedef BaseDigraphComponent::Node Node;
+      typedef BaseDigraphComponent::Arc Arc;
+      /// \brief Class to represent red nodes.
+      ///
+      /// This class represents the red nodes of the graph. The red
+      /// nodes can also be used as normal nodes.
+      class RedNode : public Node {
+        typedef Node Parent;
+      public:
+        /// \brief Default constructor.
+        ///
+        /// Default constructor.
+        /// \warning The default constructor is not required to set
+        /// the item to some well-defined value. So you should consider it
+        /// as uninitialized.
+        RedNode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        RedNode(const RedNode &) : Parent() {}
+        /// \brief Constructor for conversion from \c INVALID.
+        ///
+        /// Constructor for conversion from \c INVALID.
+        /// It initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        RedNode(Invalid) {}
+      };
+      /// \brief Class to represent blue nodes.
+      ///
+      /// This class represents the blue nodes of the graph. The blue
+      /// nodes can also be used as normal nodes.
+      class BlueNode : public Node {
+        typedef Node Parent;
+      public:
+        /// \brief Default constructor.
+        ///
+        /// Default constructor.
+        /// \warning The default constructor is not required to set
+        /// the item to some well-defined value. So you should consider it
+        /// as uninitialized.
+        BlueNode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        BlueNode(const BlueNode &) : Parent() {}
+        /// \brief Constructor for conversion from \c INVALID.
+        ///
+        /// Constructor for conversion from \c INVALID.
+        /// It initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        BlueNode(Invalid) {}
+        /// \brief Constructor for conversion from a node.
+        ///
+        /// Constructor for conversion from a node. The conversion can
+        /// be invalid, since the Node can be member of the red
+        /// set.
+        BlueNode(const Node&) {}
+      };
+      /// \brief Gives back %true for red nodes.
+      ///
+      /// Gives back %true for red nodes.
+      bool red(const Node&) const { return true; }
+      /// \brief Gives back %true for blue nodes.
+      ///
+      /// Gives back %true for blue nodes.
+      bool blue(const Node&) const { return true; }
+      /// \brief Gives back the red end node of the edge.
+      ///
+      /// Gives back the red end node of the edge.
+      RedNode redNode(const Edge&) const { return RedNode(); }
+      /// \brief Gives back the blue end node of the edge.
+      ///
+      /// Gives back the blue end node of the edge.
+      BlueNode blueNode(const Edge&) const { return BlueNode(); }
+      /// \brief Converts the node to red node object.
+      ///
+      /// This function converts unsafely the node to red node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This function converts unsafely the node to blue node
+      /// object. It should be called only if the node is from the red
+      /// partition or INVALID.
+      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
+      /// \brief Converts the node to red node object.
+      ///
+      /// This function converts safely the node to red node
+      /// object. If the node is not from the red partition, then it
+      /// returns INVALID.
+      RedNode asRedNode(const Node&) const { return RedNode(); }
+      /// \brief Converts the node to blue node object.
+      ///
+      /// This function converts unsafely the node to blue node
+      /// object. If the node is not from the blue partition, then it
+      /// returns INVALID.
+      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
+      template <typename _BpGraph>
+      struct Constraints {
+        typedef typename _BpGraph::Node Node;
+        typedef typename _BpGraph::RedNode RedNode;
+        typedef typename _BpGraph::BlueNode BlueNode;
+        typedef typename _BpGraph::Arc Arc;
+        typedef typename _BpGraph::Edge Edge;
+        void constraints() {
+          checkConcept<BaseGraphComponent, _BpGraph>();
+          checkConcept<GraphItem<'n'>, RedNode>();
+          checkConcept<GraphItem<'n'>, BlueNode>();
+          {
+            Node n;
+            RedNode rn;
+            BlueNode bn;
+            Node rnan = rn;
+            Node bnan = bn;
+            Edge e;
+            bool b;
+            b = bpgraph.red(rnan);
+            b = bpgraph.blue(bnan);
+            rn = bpgraph.redNode(e);
+            bn = bpgraph.blueNode(e);
+            rn = bpgraph.asRedNodeUnsafe(rnan);
+            bn = bpgraph.asBlueNodeUnsafe(bnan);
+            rn = bpgraph.asRedNode(rnan);
+            bn = bpgraph.asBlueNode(bnan);
+            ignore_unused_variable_warning(b);
+          }
+        }
+        const _BpGraph& bpgraph;
       };
 …
         const _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         const _Graph& graph;
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for \e idable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of \e idable undirected
+    /// bipartite graphs. It extends \ref IDableGraphComponent with
+    /// the core ID functions of undirected bipartite graphs. Beside
+    /// the regular node ids, this class also provides ids within the
+    /// the red and blue sets of the nodes. This concept is part of
+    /// the BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
+    public:
+      typedef BAS Base;
+      typedef IDableGraphComponent<BAS> Parent;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      using Parent::id;
+      /// \brief Return a unique integer id for the given node in the red set.
+      ///
+      /// Return a unique integer id for the given node in the red set.
+      int id(const RedNode&) const { return -1; }
+      /// \brief Return a unique integer id for the given node in the blue set.
+      ///
+      /// Return a unique integer id for the given node in the blue set.
+      int id(const BlueNode&) const { return -1; }
+      /// \brief Return an integer greater or equal to the maximum
+      /// node id in the red set.
+      ///
+      /// Return an integer greater or equal to the maximum
+      /// node id in the red set.
+      int maxRedId() const { return -1; }
+      /// \brief Return an integer greater or equal to the maximum
+      /// node id in the blue set.
+      ///
+      /// Return an integer greater or equal to the maximum
+      /// node id in the blue set.
+      int maxBlueId() const { return -1; }
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
+          typename _BpGraph::Node node;
+          typename _BpGraph::RedNode red;
+          typename _BpGraph::BlueNode blue;
+          int rid = bpgraph.id(red);
+          int bid = bpgraph.id(blue);
+          rid = bpgraph.maxRedId();
+          bid = bpgraph.maxBlueId();
+          ignore_unused_variable_warning(rid);
+          ignore_unused_variable_warning(bid);
+        }
+        const _BpGraph& bpgraph;
       };
     };
 …
           _GraphItemIt it3 = it1;
           _GraphItemIt it4 = INVALID;
+          ignore_unused_variable_warning(it3);
+          ignore_unused_variable_warning(it4);
           it2 = ++it1;
 …
+        }
         const GR& g;
+        Constraints() {}
       };
     };
 …
           _GraphIncIt it3 = it1;
           _GraphIncIt it4 = INVALID;
+          ignore_unused_variable_warning(it3);
+          ignore_unused_variable_warning(it4);
           it2 = ++it1;
 …
         const Base& node;
         const GR& graph;
+        Constraints() {}
       };
     };
 …
         const _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         const _Graph& graph;
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for iterable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of iterable undirected
+    /// bipartite graphs. It extends \ref IterableGraphComponent with
+    /// the core iterable interface of undirected bipartite graphs.
+    /// This concept is part of the BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
+    public:
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      typedef typename Base::Arc Arc;
+      typedef typename Base::Edge Edge;
+      typedef IterableBpGraphComponent BpGraph;
+      using IterableGraphComponent<BAS>::first;
+      using IterableGraphComponent<BAS>::next;
+      /// \name Base Iteration
+      ///
+      /// This interface provides functions for iteration on red and blue nodes.
+      ///
+      /// @{
+      /// \brief Return the first red node.
+      ///
+      /// This function gives back the first red node in the iteration order.
+      void first(RedNode&) const {}
+      /// \brief Return the next red node.
+      ///
+      /// This function gives back the next red node in the iteration order.
+      void next(RedNode&) const {}
+      /// \brief Return the first blue node.
+      ///
+      /// This function gives back the first blue node in the iteration order.
+      void first(BlueNode&) const {}
+      /// \brief Return the next blue node.
+      ///
+      /// This function gives back the next blue node in the iteration order.
+      void next(BlueNode&) const {}
+      /// @}
+      /// \name Class Based Iteration
+      ///
+      /// This interface provides iterator classes for red and blue nodes.
+      ///
+      /// @{
+      /// \brief This iterator goes through each red node.
+      ///
+      /// This iterator goes through each red node.
+      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
+      /// \brief This iterator goes through each blue node.
+      ///
+      /// This iterator goes through each blue node.
+      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
+      /// @}
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
+          typename _BpGraph::RedNode rn(INVALID);
+          bpgraph.first(rn);
+          bpgraph.next(rn);
+          typename _BpGraph::BlueNode bn(INVALID);
+          bpgraph.first(bn);
+          bpgraph.next(bn);
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
+            typename _BpGraph::RedNodeIt>();
+          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
+            typename _BpGraph::BlueNodeIt>();
+        }
+        const _BpGraph& bpgraph;
       };
     };
 …
       ArcNotifier;
+      mutable NodeNotifier node_notifier;
+      mutable ArcNotifier arc_notifier;
       /// \brief Return the node alteration notifier.
       ///
       /// This function gives back the node alteration notifier.
       NodeNotifier& notifier(Node) const {
          return NodeNotifier();
+        return node_notifier;
+      }
 …
       /// This function gives back the arc alteration notifier.
       ArcNotifier& notifier(Arc) const {
         return ArcNotifier();
+        return arc_notifier;
+      }
 …
         const _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
       typedef BAS Base;
+      typedef AlterableDigraphComponent<Base> Parent;
       typedef typename Base::Edge Edge;
 …
       EdgeNotifier;
+      mutable EdgeNotifier edge_notifier;
+      using Parent::notifier;
       /// \brief Return the edge alteration notifier.
       ///
       /// This function gives back the edge alteration notifier.
       EdgeNotifier& notifier(Edge) const {
         return EdgeNotifier();
+        return edge_notifier;
+      }
 …
         const _Graph& graph;
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for alterable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of alterable undirected
+    /// bipartite graphs. It extends \ref AlterableGraphComponent with
+    /// the alteration notifier interface of bipartite graphs. It
+    /// implements an observer-notifier pattern for the red and blue
+    /// nodes. More obsevers can be registered into the notifier and
+    /// whenever an alteration occured in the graph all the observers
+    /// will be notified about it.
+    template <typename BAS = BaseBpGraphComponent>
+    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
+    public:
+      typedef BAS Base;
+      typedef AlterableGraphComponent<Base> Parent;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      /// Red node alteration notifier class.
+      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
+      RedNodeNotifier;
+      /// Blue node alteration notifier class.
+      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
+      BlueNodeNotifier;
+      mutable RedNodeNotifier red_node_notifier;
+      mutable BlueNodeNotifier blue_node_notifier;
+      using Parent::notifier;
+      /// \brief Return the red node alteration notifier.
+      ///
+      /// This function gives back the red node alteration notifier.
+      RedNodeNotifier& notifier(RedNode) const {
+        return red_node_notifier;
+      }
+      /// \brief Return the blue node alteration notifier.
+      ///
+      /// This function gives back the blue node alteration notifier.
+      BlueNodeNotifier& notifier(BlueNode) const {
+        return blue_node_notifier;
+      }
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
+          typename _BpGraph::RedNodeNotifier& rnn
+            = bpgraph.notifier(typename _BpGraph::RedNode());
+          typename _BpGraph::BlueNodeNotifier& bnn
+            = bpgraph.notifier(typename _BpGraph::BlueNode());
+          ignore_unused_variable_warning(rnn);
+          ignore_unused_variable_warning(bnn);
+        }
+        const _BpGraph& bpgraph;
       };
     };
 …
         const GR &g;
         const typename GraphMap::Value &t;
+        Constraints() {}
       };
 …
         const _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         const _Graph& graph;
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for mappable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of mappable undirected
+    /// bipartite graphs.  It extends \ref MappableGraphComponent with
+    /// the standard graph map class for red and blue nodes (\c
+    /// RedNodeMap and BlueNodeMap). This concept is part of the
+    /// BpGraph concept.
+    template <typename BAS = BaseBpGraphComponent>
+    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
+    public:
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef MappableBpGraphComponent BpGraph;
+      /// \brief Standard graph map for the red nodes.
+      ///
+      /// Standard graph map for the red nodes.
+      /// It conforms to the ReferenceMap concept.
+      template <typename V>
+      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
+        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
+      public:
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        explicit RedNodeMap(const MappableBpGraphComponent& graph)
+          : Parent(graph) {}
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalize the values.
+        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
+          : Parent(graph, value) {}
+      private:
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
+        /// \brief Assignment operator.
+        ///
+        /// Assignment operator.
+        template <typename CMap>
+        RedNodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, V>, CMap>();
+          return *this;
+        }
+      };
+      /// \brief Standard graph map for the blue nodes.
+      ///
+      /// Standard graph map for the blue nodes.
+      /// It conforms to the ReferenceMap concept.
+      template <typename V>
+      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
+        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
+      public:
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
+          : Parent(graph) {}
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalize the values.
+        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
+          : Parent(graph, value) {}
+      private:
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
+        /// \brief Assignment operator.
+        ///
+        /// Assignment operator.
+        template <typename CMap>
+        BlueNodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, V>, CMap>();
+          return *this;
+        }
+      };
+      template <typename _BpGraph>
+      struct Constraints {
+        struct Dummy {
+          int value;
+          Dummy() : value(0) {}
+          Dummy(int _v) : value(_v) {}
+        };
+        void constraints() {
+          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
+          { // int map test
+            typedef typename _BpGraph::template RedNodeMap<int>
+              IntRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
+              IntRedNodeMap >();
+          } { // bool map test
+            typedef typename _BpGraph::template RedNodeMap<bool>
+              BoolRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
+              BoolRedNodeMap >();
+          } { // Dummy map test
+            typedef typename _BpGraph::template RedNodeMap<Dummy>
+              DummyRedNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
+              DummyRedNodeMap >();
+          }
+          { // int map test
+            typedef typename _BpGraph::template BlueNodeMap<int>
+              IntBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
+              IntBlueNodeMap >();
+          } { // bool map test
+            typedef typename _BpGraph::template BlueNodeMap<bool>
+              BoolBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
+              BoolBlueNodeMap >();
+          } { // Dummy map test
+            typedef typename _BpGraph::template BlueNodeMap<Dummy>
+              DummyBlueNodeMap;
+            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
+              DummyBlueNodeMap >();
+          }
+        }
+        const _BpGraph& bpgraph;
       };
     };
 …
         _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         _Graph& graph;
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for extendable undirected bipartite graphs.
+    ///
+    /// This class describes the interface of extendable undirected
+    /// bipartite graphs. It extends \ref BaseGraphComponent with
+    /// functions for adding nodes and edges to the graph. This
+    /// concept requires \ref AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ExtendableBpGraphComponent : public BAS {
+    public:
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::RedNode RedNode;
+      typedef typename Base::BlueNode BlueNode;
+      typedef typename Base::Edge Edge;
+      /// \brief Add a new red node to the digraph.
+      ///
+      /// This function adds a red new node to the digraph.
+      RedNode addRedNode() {
+        return INVALID;
+      }
+      /// \brief Add a new blue node to the digraph.
+      ///
+      /// This function adds a blue new node to the digraph.
+      BlueNode addBlueNode() {
+        return INVALID;
+      }
+      /// \brief Add a new edge connecting the given two nodes.
+      ///
+      /// This function adds a new edge connecting the given two nodes
+      /// of the graph. The first node has to be a red node, and the
+      /// second one a blue node.
+      Edge addEdge(const RedNode&, const BlueNode&) {
+        return INVALID;
+      }
+      Edge addEdge(const BlueNode&, const RedNode&) {
+        return INVALID;
+      }
+      template <typename _BpGraph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<Base, _BpGraph>();
+          typename _BpGraph::RedNode red_node;
+          typename _BpGraph::BlueNode blue_node;
+          red_node = bpgraph.addRedNode();
+          blue_node = bpgraph.addBlueNode();
+          typename _BpGraph::Edge edge;
+          edge = bpgraph.addEdge(red_node, blue_node);
+          edge = bpgraph.addEdge(blue_node, red_node);
+        }
+        _BpGraph& bpgraph;
       };
     };
 …
         _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
         _Graph& graph;
+      };
+    };
+        Constraints() {}
+      };
+    };
+    /// \brief Skeleton class for erasable undirected graphs.
+    ///
+    /// This class describes the interface of erasable undirected
+    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
+    /// functions for removing nodes and edges from the graph. This
+    /// concept requires \ref AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
     /// \brief Skeleton class for clearable directed graphs.
 …
         _Digraph& digraph;
+        Constraints() {}
       };
     };
 …
     /// This concept requires \ref AlterableGraphComponent.
     template <typename BAS = BaseGraphComponent>
+    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
+    public:
+      typedef BAS Base;
+      /// \brief Erase all nodes and edges from the graph.
+      ///
+      /// This function erases all nodes and edges from the graph.
+      void clear() {}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<Base, _Graph>();
+          graph.clear();
+        }
+        _Graph& graph;
+      };
+    };
+    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
+    /// \brief Skeleton class for clearable undirected biparite graphs.
+    ///
+    /// This class describes the interface of clearable undirected
+    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
+    /// function for clearing the graph.  This concept requires \ref
+    /// AlterableBpGraphComponent.
+    template <typename BAS = BaseBpGraphComponent>
+    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
+  }

lemon/concepts/heap.h

r877	r976
315	315	_Heap& heap;
316	316	ItemIntMap& map;
	317	Constraints() {}
317	318	};
318	319	};

lemon/concepts/maps.h

-                      r718
+                      r997
       /// Returns the value associated with the given key.
       Value operator[](const Key &) const {
         return *static_cast<Value *>(0);
+        return *(static_cast<Value *>(0)+1);
+      }
 …
         const typename _ReadMap::Key& own_key;
         const _ReadMap& m;
+        Constraints() {}
       };
 …
         const typename _WriteMap::Value& own_val;
         _WriteMap& m;
+        Constraints() {}
       };
     };
 …
       /// Returns the value associated with the given key.
       Value operator[](const Key &) const {
+        return *static_cast<Value *>(0);
+        Value *r = 0;
+        return *r;
+      }
 …
       /// Returns a reference to the value associated with the given key.
       Reference operator[](const Key &) {
+        return *static_cast<Value *>(0);
+        Value *r = 0;
+        return *r;
+      }
       /// Returns a const reference to the value associated with the given key.
       ConstReference operator[](const Key &) const {
+        return *static_cast<Value *>(0);
+        Value *r = 0;
+        return *r;
+      }
 …
         typename _ReferenceMap::ConstReference own_cref;
         _ReferenceMap& m;
+        Constraints() {}
       };
     };

lemon/concepts/path.h

-                      r785
+                      r976
+        }
         _Path& p;
+        PathDumperConstraints() {}
       };
 …
+        }
         _Path& p;
+        PathDumperConstraints() {}
       };

lemon/config.h.in

-                      r678
+                      r981
+/* 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
+#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

lemon/core.h

-                      r893
+                      r1027
   typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
+  ///Create convenience typedefs for the bipartite graph types and iterators
+  ///This \c \#define creates the same convenient type definitions as
+  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
+  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
+  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
+  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
+  ///
+  ///\note If the graph type is a dependent type, ie. the graph type depend
+  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
+  ///macro.
+#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
+  GRAPH_TYPEDEFS(BpGraph);                                              \
+  typedef BpGraph::RedNode RedNode;                                     \
+  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
+  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
+  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
+  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
+  typedef BpGraph::BlueNode BlueNode;                                   \
+  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
+  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
+  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
+  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
+  ///Create convenience typedefs for the bipartite graph types and iterators
+  ///\see BPGRAPH_TYPEDEFS
+  ///
+  ///\note Use this macro, if the graph type is a dependent type,
+  ///ie. the graph type depend on a template parameter.
+#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
+  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
+  typedef typename BpGraph::RedNode RedNode;                                \
+  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
+  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
+  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
+  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
+  typedef typename BpGraph::BlueNode BlueNode;                              \
+  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
+  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
+  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
+  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
   /// \brief Function to count the items in a graph.
   ///
 …
+  }
+  namespace _graph_utils_bits {
+    template <typename Graph, typename Enable = void>
+    struct CountRedNodesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::RedNode>(g);
+      }
+    };
+    template <typename Graph>
+    struct CountRedNodesSelector<
+      Graph, typename
+      enable_if<typename Graph::NodeNumTag, void>::type>
+    {
+      static int count(const Graph &g) {
+        return g.redNum();
+      }
+    };
+  }
+  /// \brief Function to count the red nodes in the graph.
+  ///
+  /// This function counts the red nodes in the graph.
+  /// The complexity of the function is O(n) but for some
+  /// graph structures it is specialized to run in O(1).
+  ///
+  /// If the graph contains a \e redNum() member function and a
+  /// \e NodeNumTag tag then this function calls directly the member
+  /// function to query the cardinality of the node set.
+  template <typename Graph>
+  inline int countRedNodes(const Graph& g) {
+    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
+  }
+  namespace _graph_utils_bits {
+    template <typename Graph, typename Enable = void>
+    struct CountBlueNodesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::BlueNode>(g);
+      }
+    };
+    template <typename Graph>
+    struct CountBlueNodesSelector<
+      Graph, typename
+      enable_if<typename Graph::NodeNumTag, void>::type>
+    {
+      static int count(const Graph &g) {
+        return g.blueNum();
+      }
+    };
+  }
+  /// \brief Function to count the blue nodes in the graph.
+  ///
+  /// This function counts the blue nodes in the graph.
+  /// The complexity of the function is O(n) but for some
+  /// graph structures it is specialized to run in O(1).
+  ///
+  /// If the graph contains a \e blueNum() member function and a
+  /// \e NodeNumTag tag then this function calls directly the member
+  /// function to query the cardinality of the node set.
+  template <typename Graph>
+  inline int countBlueNodes(const Graph& g) {
+    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
+  }
   // Arc counting:
 …
       template <typename From, typename NodeRefMap, typename EdgeRefMap>
       static void copy(const From& from, Graph &to,
+                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+                       NodeRefMap& nodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
         to.build(from, nodeRefMap, edgeRefMap);
+      }
     };
+    template <typename BpGraph, typename Enable = void>
+    struct BpGraphCopySelector {
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
+      static void copy(const From& from, BpGraph &to,
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
+        to.clear();
+        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
+          redNodeRefMap[it] = to.addRedNode();
+        }
+        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
+          blueNodeRefMap[it] = to.addBlueNode();
+        }
+        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
+          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
+                                      blueNodeRefMap[from.blueNode(it)]);
+        }
+      }
+    };
+    template <typename BpGraph>
+    struct BpGraphCopySelector<
+      BpGraph,
+      typename enable_if<typename BpGraph::BuildTag, void>::type>
+    {
+      template <typename From, typename RedNodeRefMap,
+                typename BlueNodeRefMap, typename EdgeRefMap>
+      static void copy(const From& from, BpGraph &to,
+                       RedNodeRefMap& redNodeRefMap,
+                       BlueNodeRefMap& blueNodeRefMap,
+                       EdgeRefMap& edgeRefMap) {
+        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
+      }
+    };
+  }
   /// Check whether a graph is undirected.
+  /// \brief Check whether a graph is undirected.
   ///
   /// This function returns \c true if the given graph is undirected.
 …
   graphCopy(const From& from, To& to) {
     return GraphCopy<From, To>(from, to);
+  }
+  /// \brief Class to copy a bipartite graph.
+  ///
+  /// Class to copy a bipartite graph to another graph (duplicate a
+  /// graph). The simplest way of using it is through the
+  /// \c bpGraphCopy() function.
+  ///
+  /// This class not only make a copy of a bipartite graph, but it can
+  /// create references and cross references between the nodes, edges
+  /// and arcs of the two graphs, and it can copy maps for using with
+  /// the newly created graph.
+  ///
+  /// To make a copy from a graph, first an instance of BpGraphCopy
+  /// should be created, then the data belongs to the graph should
+  /// assigned to copy. In the end, the \c run() member should be
+  /// called.
+  ///
+  /// The next code copies a graph with several data:
+  ///\code
+  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
+  ///  // Create references for the nodes
+  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
+  ///  cg.nodeRef(nr);
+  ///  // Create cross references (inverse) for the edges
+  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
+  ///  cg.edgeCrossRef(ecr);
+  ///  // Copy a red node map
+  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
+  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
+  ///  cg.redNodeMap(ormap, nrmap);
+  ///  // Copy a node
+  ///  OrigBpGraph::Node on;
+  ///  NewBpGraph::Node nn;
+  ///  cg.node(on, nn);
+  ///  // Execute copying
+  ///  cg.run();
+  ///\endcode
+  template <typename From, typename To>
+  class BpGraphCopy {
+  private:
+    typedef typename From::Node Node;
+    typedef typename From::RedNode RedNode;
+    typedef typename From::BlueNode BlueNode;
+    typedef typename From::NodeIt NodeIt;
+    typedef typename From::Arc Arc;
+    typedef typename From::ArcIt ArcIt;
+    typedef typename From::Edge Edge;
+    typedef typename From::EdgeIt EdgeIt;
+    typedef typename To::Node TNode;
+    typedef typename To::RedNode TRedNode;
+    typedef typename To::BlueNode TBlueNode;
+    typedef typename To::Arc TArc;
+    typedef typename To::Edge TEdge;
+    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
+    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
+    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
+    struct NodeRefMap {
+      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
+                 const BlueNodeRefMap& blue_node_ref)
+        : _from(from), _red_node_ref(red_node_ref),
+          _blue_node_ref(blue_node_ref) {}
+      typedef typename From::Node Key;
+      typedef typename To::Node Value;
+      Value operator[](const Key& key) const {
+        if (_from.red(key)) {
+          return _red_node_ref[_from.asRedNodeUnsafe(key)];
+        } else {
+          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
+        }
+      }
+      const From& _from;
+      const RedNodeRefMap& _red_node_ref;
+      const BlueNodeRefMap& _blue_node_ref;
+    };
+    struct ArcRefMap {
+      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
+        : _from(from), _to(to), _edge_ref(edge_ref) {}
+      typedef typename From::Arc Key;
+      typedef typename To::Arc Value;
+      Value operator[](const Key& key) const {
+        return _to.direct(_edge_ref[key], _from.direction(key));
+      }
+      const From& _from;
+      const To& _to;
+      const EdgeRefMap& _edge_ref;
+    };
+  public:
+    /// \brief Constructor of BpGraphCopy.
+    ///
+    /// Constructor of BpGraphCopy for copying the content of the
+    /// \c from graph into the \c to graph.
+    BpGraphCopy(const From& from, To& to)
+      : _from(from), _to(to) {}
+    /// \brief Destructor of BpGraphCopy
+    ///
+    /// Destructor of BpGraphCopy.
+    ~BpGraphCopy() {
+      for (int i = 0; i < int(_node_maps.size()); ++i) {
+        delete _node_maps[i];
+      }
+      for (int i = 0; i < int(_red_maps.size()); ++i) {
+        delete _red_maps[i];
+      }
+      for (int i = 0; i < int(_blue_maps.size()); ++i) {
+        delete _blue_maps[i];
+      }
+      for (int i = 0; i < int(_arc_maps.size()); ++i) {
+        delete _arc_maps[i];
+      }
+      for (int i = 0; i < int(_edge_maps.size()); ++i) {
+        delete _edge_maps[i];
+      }
+    }
+    /// \brief Copy the node references into the given map.
+    ///
+    /// This function copies the node references into the given map.
+    /// The parameter should be a map, whose key type is the Node type of
+    /// the source graph, while the value type is the Node type of the
+    /// destination graph.
+    template <typename NodeRef>
+    BpGraphCopy& nodeRef(NodeRef& map) {
+      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
+                           NodeRefMap, NodeRef>(map));
+      return *this;
+    }
+    /// \brief Copy the node cross references into the given map.
+    ///
+    /// This function copies the node cross references (reverse references)
+    /// into the given map. The parameter should be a map, whose key type
+    /// is the Node type of the destination graph, while the value type is
+    /// the Node type of the source graph.
+    template <typename NodeCrossRef>
+    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
+      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
+                           NodeRefMap, NodeCrossRef>(map));
+      return *this;
+    }
+    /// \brief Make a copy of the given node map.
+    ///
+    /// This function makes a copy of the given node map for the newly
+    /// created graph.
+    /// The key type of the new map \c tmap should be the Node type of the
+    /// destination graph, and the key type of the original map \c map
+    /// should be the Node type of the source graph.
+    template <typename FromMap, typename ToMap>
+    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
+      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
+                           NodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+    /// \brief Make a copy of the given node.
+    ///
+    /// This function makes a copy of the given node.
+    BpGraphCopy& node(const Node& node, TNode& tnode) {
+      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
+                           NodeRefMap, TNode>(node, tnode));
+      return *this;
+    }
+    /// \brief Copy the red node references into the given map.
+    ///
+    /// This function copies the red node references into the given
+    /// map.  The parameter should be a map, whose key type is the
+    /// Node type of the source graph with the red item set, while the
+    /// value type is the Node type of the destination graph.
+    template <typename RedRef>
+    BpGraphCopy& redRef(RedRef& map) {
+      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
+                          RedNodeRefMap, RedRef>(map));
+      return *this;
+    }
+    /// \brief Copy the red node cross references into the given map.
+    ///
+    /// This function copies the red node cross references (reverse
+    /// references) into the given map. The parameter should be a map,
+    /// whose key type is the Node type of the destination graph with
+    /// the red item set, while the value type is the Node type of the
+    /// source graph.
+    template <typename RedCrossRef>
+    BpGraphCopy& redCrossRef(RedCrossRef& map) {
+      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
+                          RedNodeRefMap, RedCrossRef>(map));
+      return *this;
+    }
+    /// \brief Make a copy of the given red node map.
+    ///
+    /// This function makes a copy of the given red node map for the newly
+    /// created graph.
+    /// The key type of the new map \c tmap should be the Node type of
+    /// the destination graph with the red items, and the key type of
+    /// the original map \c map should be the Node type of the source
+    /// graph.
+    template <typename FromMap, typename ToMap>
+    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
+      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
+                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+    /// \brief Make a copy of the given red node.
+    ///
+    /// This function makes a copy of the given red node.
+    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
+      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
+                          RedNodeRefMap, TRedNode>(node, tnode));
+      return *this;
+    }
+    /// \brief Copy the blue node references into the given map.
+    ///
+    /// This function copies the blue node references into the given
+    /// map.  The parameter should be a map, whose key type is the
+    /// Node type of the source graph with the blue item set, while the
+    /// value type is the Node type of the destination graph.
+    template <typename BlueRef>
+    BpGraphCopy& blueRef(BlueRef& map) {
+      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
+                           BlueNodeRefMap, BlueRef>(map));
+      return *this;
+    }
+    /// \brief Copy the blue node cross references into the given map.
+    ///
+    /// This function copies the blue node cross references (reverse
+    /// references) into the given map. The parameter should be a map,
+    /// whose key type is the Node type of the destination graph with
+    /// the blue item set, while the value type is the Node type of the
+    /// source graph.
+    template <typename BlueCrossRef>
+    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
+      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
+                           BlueNodeRefMap, BlueCrossRef>(map));
+      return *this;
+    }
+    /// \brief Make a copy of the given blue node map.
+    ///
+    /// This function makes a copy of the given blue node map for the newly
+    /// created graph.
+    /// The key type of the new map \c tmap should be the Node type of
+    /// the destination graph with the blue items, and the key type of
+    /// the original map \c map should be the Node type of the source
+    /// graph.
+    template <typename FromMap, typename ToMap>
+    BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
+      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
+                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+    /// \brief Make a copy of the given blue node.
+    ///
+    /// This function makes a copy of the given blue node.
+    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
+      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
+                           BlueNodeRefMap, TBlueNode>(node, tnode));
+      return *this;
+    }
+    /// \brief Copy the arc references into the given map.
+    ///
+    /// This function copies the arc references into the given map.
+    /// The parameter should be a map, whose key type is the Arc type of
+    /// the source graph, while the value type is the Arc type of the
+    /// destination graph.
+    template <typename ArcRef>
+    BpGraphCopy& arcRef(ArcRef& map) {
+      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
+                          ArcRefMap, ArcRef>(map));
+      return *this;
+    }
+    /// \brief Copy the arc cross references into the given map.
+    ///
+    /// This function copies the arc cross references (reverse references)
+    /// into the given map. The parameter should be a map, whose key type
+    /// is the Arc type of the destination graph, while the value type is
+    /// the Arc type of the source graph.
+    template <typename ArcCrossRef>
+    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
+      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
+                          ArcRefMap, ArcCrossRef>(map));
+      return *this;
+    }
+    /// \brief Make a copy of the given arc map.
+    ///
+    /// This function makes a copy of the given arc map for the newly
+    /// created graph.
+    /// The key type of the new map \c tmap should be the Arc type of the
+    /// destination graph, and the key type of the original map \c map
+    /// should be the Arc type of the source graph.
+    template <typename FromMap, typename ToMap>
+    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
+      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
+                          ArcRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+    /// \brief Make a copy of the given arc.
+    ///
+    /// This function makes a copy of the given arc.
+    BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
+      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
+                          ArcRefMap, TArc>(arc, tarc));
+      return *this;
+    }
+    /// \brief Copy the edge references into the given map.
+    ///
+    /// This function copies the edge references into the given map.
+    /// The parameter should be a map, whose key type is the Edge type of
+    /// the source graph, while the value type is the Edge type of the
+    /// destination graph.
+    template <typename EdgeRef>
+    BpGraphCopy& edgeRef(EdgeRef& map) {
+      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
+                           EdgeRefMap, EdgeRef>(map));
+      return *this;
+    }
+    /// \brief Copy the edge cross references into the given map.
+    ///
+    /// This function copies the edge cross references (reverse references)
+    /// into the given map. The parameter should be a map, whose key type
+    /// is the Edge type of the destination graph, while the value type is
+    /// the Edge type of the source graph.
+    template <typename EdgeCrossRef>
+    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
+      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
+                           Edge, EdgeRefMap, EdgeCrossRef>(map));
+      return *this;
+    }
+    /// \brief Make a copy of the given edge map.
+    ///
+    /// This function makes a copy of the given edge map for the newly
+    /// created graph.
+    /// The key type of the new map \c tmap should be the Edge type of the
+    /// destination graph, and the key type of the original map \c map
+    /// should be the Edge type of the source graph.
+    template <typename FromMap, typename ToMap>
+    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
+      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
+                           EdgeRefMap, FromMap, ToMap>(map, tmap));
+      return *this;
+    }
+    /// \brief Make a copy of the given edge.
+    ///
+    /// This function makes a copy of the given edge.
+    BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
+      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
+                           EdgeRefMap, TEdge>(edge, tedge));
+      return *this;
+    }
+    /// \brief Execute copying.
+    ///
+    /// This function executes the copying of the graph along with the
+    /// copying of the assigned data.
+    void run() {
+      RedNodeRefMap redNodeRefMap(_from);
+      BlueNodeRefMap blueNodeRefMap(_from);
+      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
+      EdgeRefMap edgeRefMap(_from);
+      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
+      _core_bits::BpGraphCopySelector<To>::
+        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
+      for (int i = 0; i < int(_node_maps.size()); ++i) {
+        _node_maps[i]->copy(_from, nodeRefMap);
+      }
+      for (int i = 0; i < int(_red_maps.size()); ++i) {
+        _red_maps[i]->copy(_from, redNodeRefMap);
+      }
+      for (int i = 0; i < int(_blue_maps.size()); ++i) {
+        _blue_maps[i]->copy(_from, blueNodeRefMap);
+      }
+      for (int i = 0; i < int(_edge_maps.size()); ++i) {
+        _edge_maps[i]->copy(_from, edgeRefMap);
+      }
+      for (int i = 0; i < int(_arc_maps.size()); ++i) {
+        _arc_maps[i]->copy(_from, arcRefMap);
+      }
+    }
+  private:
+    const From& _from;
+    To& _to;
+    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
+      _node_maps;
+    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
+      _red_maps;
+    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
+      _blue_maps;
+    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
+      _arc_maps;
+    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
+      _edge_maps;
+  };
+  /// \brief Copy a graph to another graph.
+  ///
+  /// This function copies a graph to another graph.
+  /// The complete usage of it is detailed in the BpGraphCopy class,
+  /// but a short example shows a basic work:
+  ///\code
+  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
+  ///\endcode
+  ///
+  /// After the copy the \c nr map will contain the mapping from the
+  /// nodes of the \c from graph to the nodes of the \c to graph and
+  /// \c ecr will contain the mapping from the edges of the \c to graph
+  /// to the edges of the \c from graph.
+  ///
+  /// \see BpGraphCopy
+  template <typename From, typename To>
+  BpGraphCopy<From, To>
+  bpGraphCopy(const From& from, To& to) {
+    return BpGraphCopy<From, To>(from, to);
+  }
 …
     /// The Digraph type
     typedef GR Digraph;
   protected:
 …
     ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
     ///
+#ifdef DOXYGEN
+    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
+#else
+    using ArcLookUp<GR>::operator() ;
+    Arc operator()(Node s, Node t, Arc prev) const
+    Arc operator()(Node s, Node t, Arc prev=INVALID) const
+    {
+      return prev==INVALID?(*this)(s,t):_next[prev];
+    }
+      if(prev==INVALID)
+        {
+          Arc f=INVALID;
+          Arc e;
+          for(e=_head[s];
+              e!=INVALID&&_g.target(e)!=t;
+              e = t < _g.target(e)?_left[e]:_right[e]) ;
+          while(e!=INVALID)
+            if(_g.target(e)==t)
+              {
+                f = e;
+                e = _left[e];
+              }
+            else e = _right[e];
+          return f;
+        }
+      else return _next[prev];
+    }
+  };
+  /// @}
+} //namespace lemon
 #endif
-  };
-  /// @}
-} //namespace lemon
-#endif

lemon/cost_scaling.h

-                      r877
+                      r1003
   /// "preflow push-relabel" algorithm for the maximum flow problem.
   ///
+  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
+  /// implementations available in LEMON for solving this problem.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
+  ///
   /// Most of the parameters of the problem (except for the digraph)
   /// can be given using separate functions, and the algorithm can be
 …
   /// consider to use the named template parameters instead.
   ///
+  /// \warning Both number types must be signed and all input data must
+  /// \warning Both \c V and \c C must be signed number types.
+  /// \warning All input data (capacities, supply values, and costs) must
   /// be integer.
   /// \warning This algorithm does not support negative costs for such
   /// arcs that have infinite upper bound.
+  /// \warning This algorithm does not support negative costs for
+  /// arcs having infinite upper bound.
   ///
   /// \note %CostScaling provides three different internal methods,
 …
     /// relabel operation.
     /// By default, the so called \ref PARTIAL_AUGMENT
     /// "Partial Augment-Relabel" method is used, which proved to be
+    /// "Partial Augment-Relabel" method is used, which turned out to be
     /// the most efficient and the most robust on various test inputs.
     /// However, the other methods can be selected using the \ref run()
 …
     };
-    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
     typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 …
     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:
 …
     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() :
 …
     ///
     /// Using this function has the same effect as using \ref supplyMap()
     /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// with 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.
     ///
 …
     /// \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 larger than one.
+    /// \param factor The cost scaling factor. It must be at least two.
     ///
     /// \return \c INFEASIBLE if no feasible flow exists,
 …
     /// \see ProblemType, Method
     /// \see resetParams(), reset()
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
+      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
       _alpha = factor;
       ProblemType pt = init();
 …
+    }
+    /// \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.
+    /// \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.
+    ///
     /// \return <tt>(*this)</tt>
+    ///
+    /// \see resetParams(), run()
     CostScaling& reset() {
       // Resize vectors
 …
       _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
 …
+    }
+    /// \brief Return the flow map (the primal solution).
+    /// \brief Copy the flow values (the primal solution) into the
+    /// given map.
     ///
     /// This function copies the flow value on each arc into the given
 …
+    }
+    /// \brief Return the potential map (the dual solution).
+    /// \brief Copy the potential values (the dual solution) into the
+    /// given map.
     ///
     /// This function copies the potential (dual value) of each node
 …
+      }
-      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;
 …
       _rank.resize(_res_node_num + 1);
+      // Execute the algorithm
+      return OPTIMAL;
+    }
+    // Execute the algorithm and transform the results
+    void start(Method method) {
+      const int MAX_PARTIAL_PATH_LENGTH = 4;
       switch (method) {
         case PUSH:
 …
           break;
         case AUGMENT:
           startAugment();
+          startAugment(_res_node_num - 1);
           break;
         case PARTIAL_AUGMENT:
           startAugment(MAX_PATH_LENGTH);
+          startAugment(MAX_PARTIAL_PATH_LENGTH);
           break;
+      }
+      // 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();
+      // 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;
+        }
+      }
       // Handle non-zero lower bounds
 …
         LargeCost pi_u = _pi[u];
         for (int a = _first_out[u]; a != last_out; ++a) {
+          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;
+          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;
+            }
+          }
+        }
 …
+    }
+    // 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;
+    // 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);
+    }
     // Global potential update heuristic
     void globalUpdate() {
       int bucket_end = _root + 1;
+      const int bucket_end = _root + 1;
       // Initialize buckets
 …
+      }
       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] = _buckets[0];
           _bucket_prev[_buckets[0]] = i;
           _buckets[0] = i;
+          _bucket_next[i] = b0;
+          _bucket_prev[b0] = i;
+          b0 = i;
         } else {
           total_excess += _excess[i];
 …
+      }
       if (total_excess == 0) return;
+      _buckets[0] = b0;
       // Search the buckets
 …
                 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 + int(nrc);
+                if (nrc < LargeCost(_max_rank)) {
+                  new_rank_v = r + 1 + static_cast<int>(nrc);
+                }
                 // Change the rank of v
 …
                       _buckets[old_rank_v] = _bucket_next[v];
                     } else {
+                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
+                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
+                      int pv = _bucket_prev[v], nv = _bucket_next[v];
+                      _bucket_next[pv] = nv;
+                      _bucket_prev[nv] = pv;
+                    }
+                  }
+                  // Insert v to its new bucket
+                  _bucket_next[v] = _buckets[new_rank_v];
+                  _bucket_prev[_buckets[new_rank_v]] = v;
+                  // 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;
+                }
 …
     /// Execute the algorithm performing augment and relabel operations
     void startAugment(int max_length = std::numeric_limits<int>::max()) {
+    void startAugment(int max_length) {
       // Paramters for heuristics
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 3.0;
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+      const int PRICE_REFINEMENT_LIMIT = 2;
+      const double GLOBAL_UPDATE_FACTOR = 1.0;
+      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
         (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+      int next_global_update_limit = global_update_skip;
+      // Perform cost scaling phases
+      IntVector path;
+      BoolVector path_arc(_res_arc_num, false);
       int relabel_cnt = 0;
+      // Perform cost scaling phases
+      std::vector<int> path;
+      int eps_phase_cnt = 0;
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+      {
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
+        ++eps_phase_cnt;
+        // Price refinement heuristic
+        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
+          if (priceRefinement()) continue;
+        }
 …
           // Find an augmenting path from the start node
-          path.clear();
           int tip = start;
           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
+          while (int(path.size()) < max_length && _excess[tip] >= 0) {
             int u;
+            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
+            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
+            LargeCost pi_tip = _pi[tip];
             int last_out = _first_out[tip+1];
             for (int a = _next_out[tip]; a != last_out; ++a) {
+              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;
+              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;
+                }
+              }
+            }
             // Relabel tip node
-            min_red_cost = std::numeric_limits<LargeCost>::max();
             if (tip != start) {
               int ra = _reverse[path.back()];
+              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
+              min_red_cost =
+                std::min(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) {
+              rc = _cost[a] + pi_tip - _pi[_target[a]];
+              if (_res_cap[a] > 0 && rc < min_red_cost) {
+                min_red_cost = rc;
+              if (_res_cap[a] > 0) {
+                rc = _cost[a] + pi_tip - _pi[_target[a]];
+                if (rc < min_red_cost) {
+                  min_red_cost = rc;
+                }
+              }
+            }
 …
             // Step back
             if (tip != start) {
+              tip = _source[path.back()];
+              int pa = path.back();
+              path_arc[pa] = false;
+              tip = _source[pa];
               path.pop_back();
+            }
 …
           // Augment along the found path (as much flow as possible)
+        augment:
           Value delta;
           int pa, u, v = start;
 …
             u = v;
             v = _target[pa];
+            path_arc[pa] = false;
             delta = std::min(_res_cap[pa], _excess[u]);
             _res_cap[pa] -= delta;
 …
             _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_update_limit) {
+          if (relabel_cnt >= next_global_update_limit) {
             globalUpdate();
+            next_update_limit += global_update_freq;
+          }
+        }
+      }
+            next_global_update_limit += global_update_skip;
+          }
+        }
+      }
+    }
 …
     void startPush() {
       // Paramters for heuristics
       const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const int PRICE_REFINEMENT_LIMIT = 2;
       const double GLOBAL_UPDATE_FACTOR = 2.0;
       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
         (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+      int relabel_cnt = 0;
+      int next_global_update_limit = global_update_skip;
       // 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 ?
 : _epsilon / _alpha )
+      {
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
+        ++eps_phase_cnt;
+        // Price refinement heuristic
+        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
+          if (priceRefinement()) continue;
+        }
 …
                std::numeric_limits<LargeCost>::max();
             for (int a = _first_out[n]; a != last_out; ++a) {
+              rc = _cost[a] + pi_n - _pi[_target[a]];
+              if (_res_cap[a] > 0 && rc < min_red_cost) {
+                min_red_cost = rc;
+              if (_res_cap[a] > 0) {
+                rc = _cost[a] + pi_n - _pi[_target[a]];
+                if (rc < min_red_cost) {
+                  min_red_cost = rc;
+                }
+              }
+            }
 …
           // Global update heuristic
           if (relabel_cnt >= next_update_limit) {
+          if (relabel_cnt >= next_global_update_limit) {
             globalUpdate();
             for (int u = 0; u != _res_node_num; ++u)
               hyper[u] = false;
             next_update_limit += global_update_freq;
+            next_global_update_limit += global_update_skip;
+          }
+        }

lemon/cplex.cc

-                      r877
+                      r1016
     int status;
     _cnt = new int;
+    (*_cnt) = 1;
     _env = CPXopenCPLEX(&status);
     if (_env == 0) {
 …
     int status;
     _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
-    rows.clear();
-    cols.clear();
+  }

lemon/cycle_canceling.h

-                      r877
+                      r1013
 #include <lemon/bellman_ford.h>
 #include <lemon/howard_mmc.h>
+#include <lemon/hartmann_orlin_mmc.h>
 namespace lemon {
 …
   /// \ref amo93networkflows, \ref klein67primal,
   /// \ref goldberg89cyclecanceling.
+  /// The most efficent one (both theoretically and practically)
+  /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
+  /// thus it is the default method.
+  /// It is strongly polynomial, but in practice, it is typically much
+  /// slower than the scaling algorithms and NetworkSimplex.
+  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
+  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
+  /// It runs in strongly polynomial time, but in practice, it is typically
+  /// orders of magnitude slower than the scaling algorithms and
+  /// \ref NetworkSimplex.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
   /// Most of the parameters of the problem (except for the digraph)
 …
   /// algorithm. By default, it is the same as \c V.
   ///
+  /// \warning Both number types must be signed and all input data must
+  /// \warning Both \c V and \c C must be signed number types.
+  /// \warning All input data (capacities, supply values, and costs) must
   /// be integer.
   /// \warning This algorithm does not support negative costs for such
   /// arcs that have infinite upper bound.
+  /// \warning This algorithm does not support negative costs for
+  /// arcs having infinite upper bound.
   ///
   /// \note For more information about the three available methods,
 …
     ///
     /// \ref CycleCanceling provides three different cycle-canceling
+    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
+    /// is used, which proved to be the most efficient and the most robust
+    /// on various test inputs.
+    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
+    /// is used, which is by far the most efficient and the most robust.
     /// However, the other methods can be selected using the \ref run()
     /// function with the proper parameter.
     enum Method {
       /// A simple cycle-canceling method, which uses the
+      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
+      /// number for detecting negative cycles in the residual network.
+      /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
+      /// cycles in the residual network.
+      /// The number of Bellman-Ford iterations is bounded by a successively
+      /// increased limit.
       SIMPLE_CYCLE_CANCELING,
       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
 …
       /// \ref goldberg89cyclecanceling. It improves along a
       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
       /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
+      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
       MINIMUM_MEAN_CYCLE_CANCELING,
       /// The "Cancel And Tighten" algorithm, which can be viewed as an
+      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
       /// improved version of the previous method
       /// \ref goldberg89cyclecanceling.
       /// It is faster both in theory and in practice, its running time
       /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
+      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
       CANCEL_AND_TIGHTEN
     };
 …
     ///
     /// Using this function has the same effect as using \ref supplyMap()
     /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// with 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.
     ///
 …
+    }
+    /// \brief Return the flow map (the primal solution).
+    /// \brief Copy the flow values (the primal solution) into the
+    /// given map.
     ///
     /// This function copies the flow value on each arc into the given
 …
+    }
+    /// \brief Return the potential map (the dual solution).
+    /// \brief Copy the potential values (the dual solution) into the
+    /// given map.
     ///
     /// This function copies the potential (dual value) of each node
 …
     // Execute the "Minimum Mean Cycle Canceling" method
     void startMinMeanCycleCanceling() {
       typedef SimplePath<StaticDigraph> SPath;
+      typedef Path<StaticDigraph> SPath;
       typedef typename SPath::ArcIt SPathArcIt;
       typedef typename HowardMmc<StaticDigraph, CostArcMap>
+        ::template SetPath<SPath>::Create MMC;
+        ::template SetPath<SPath>::Create HwMmc;
+      typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap>
+        ::template SetPath<SPath>::Create HoMmc;
+      const double HW_ITER_LIMIT_FACTOR = 1.0;
+      const int HW_ITER_LIMIT_MIN_VALUE = 5;
+      const int hw_iter_limit =
+          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
+                   HW_ITER_LIMIT_MIN_VALUE);
       SPath cycle;
       MMC mmc(_sgr, _cost_map);
       mmc.cycle(cycle);
+      HwMmc hw_mmc(_sgr, _cost_map);
+      hw_mmc.cycle(cycle);
       buildResidualNetwork();
+      while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
+        // Find the cycle
+        mmc.findCycle();
+      while (true) {
+        typename HwMmc::TerminationCause hw_tc =
+            hw_mmc.findCycleMean(hw_iter_limit);
+        if (hw_tc == HwMmc::ITERATION_LIMIT) {
+          // Howard's algorithm reached the iteration limit, start a
+          // strongly polynomial algorithm instead
+          HoMmc ho_mmc(_sgr, _cost_map);
+          ho_mmc.cycle(cycle);
+          // Find a minimum mean cycle (Hartmann-Orlin algorithm)
+          if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break;
+          ho_mmc.findCycle();
+        } else {
+          // Find a minimum mean cycle (Howard algorithm)
+          if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break;
+          hw_mmc.findCycle();
+        }
         // Compute delta value
         Value delta = INF;
 …
+    }
     // Execute the "Cancel And Tighten" method
+    // Execute the "Cancel-and-Tighten" method
     void startCancelAndTighten() {
       // Constants for the min mean cycle computations
       const double LIMIT_FACTOR = 1.0;
       const int MIN_LIMIT = 5;
+      const double HW_ITER_LIMIT_FACTOR = 1.0;
+      const int HW_ITER_LIMIT_MIN_VALUE = 5;
+      const int hw_iter_limit =
+          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
+                   HW_ITER_LIMIT_MIN_VALUE);
       // Contruct auxiliary data vectors
 …
+          }
         } else {
+          typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
+          typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc;
+          typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc;
           typedef typename BellmanFord<StaticDigraph, CostArcMap>
             ::template SetDistMap<CostNodeMap>::Create BF;
           // Set epsilon to the minimum cycle mean
+          Cost cycle_cost = 0;
+          int cycle_size = 1;
           buildResidualNetwork();
+          MMC mmc(_sgr, _cost_map);
+          mmc.findCycleMean();
+          epsilon = -mmc.cycleMean();
+          Cost cycle_cost = mmc.cycleCost();
+          int cycle_size = mmc.cycleSize();
+          HwMmc hw_mmc(_sgr, _cost_map);
+          if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) {
+            // Howard's algorithm reached the iteration limit, start a
+            // strongly polynomial algorithm instead
+            HoMmc ho_mmc(_sgr, _cost_map);
+            ho_mmc.findCycleMean();
+            epsilon = -ho_mmc.cycleMean();
+            cycle_cost = ho_mmc.cycleCost();
+            cycle_size = ho_mmc.cycleSize();
+          } else {
+            // Set epsilon
+            epsilon = -hw_mmc.cycleMean();
+            cycle_cost = hw_mmc.cycleCost();
+            cycle_size = hw_mmc.cycleSize();
+          }
           // Compute feasible potentials for the current epsilon

lemon/dfs.h

r907	r1000
1194	1194	}
1195	1195	_Visitor& visitor;
	1196	Constraints() {}
1196	1197	};
1197	1198	};

lemon/euler.h

r877	r919
37	37	///Euler tour iterator for digraphs.
38	38
39		/// \ingroup graph_prop
	39	/// \ingroup graph_properties
40	40	///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
41	41	///graph (if there exists) and it converts to the \c Arc type of the digraph.

lemon/full_graph.h

-                      r877
+                      r1025
   };
+  class FullBpGraphBase {
+  protected:
+    int _red_num, _blue_num;
+    int _node_num, _edge_num;
+  public:
+    typedef FullBpGraphBase Graph;
+    class Node;
+    class Arc;
+    class Edge;
+    class Node {
+      friend class FullBpGraphBase;
+    protected:
+      int _id;
+      explicit Node(int id) { _id = id;}
+    public:
+      Node() {}
+      Node (Invalid) { _id = -1; }
+      bool operator==(const Node& node) const {return _id == node._id;}
+      bool operator!=(const Node& node) const {return _id != node._id;}
+      bool operator<(const Node& node) const {return _id < node._id;}
+    };
+    class RedNode : public Node {
+      friend class FullBpGraphBase;
+    protected:
+      explicit RedNode(int pid) : Node(pid) {}
+    public:
+      RedNode() {}
+      RedNode(const RedNode& node) : Node(node) {}
+      RedNode(Invalid) : Node(INVALID){}
+    };
+    class BlueNode : public Node {
+      friend class FullBpGraphBase;
+    protected:
+      explicit BlueNode(int pid) : Node(pid) {}
+    public:
+      BlueNode() {}
+      BlueNode(const BlueNode& node) : Node(node) {}
+      BlueNode(Invalid) : Node(INVALID){}
+    };
+    class Edge {
+      friend class FullBpGraphBase;
+    protected:
+      int _id;
+      explicit Edge(int id) { _id = id;}
+    public:
+      Edge() {}
+      Edge (Invalid) { _id = -1; }
+      bool operator==(const Edge& arc) const {return _id == arc._id;}
+      bool operator!=(const Edge& arc) const {return _id != arc._id;}
+      bool operator<(const Edge& arc) const {return _id < arc._id;}
+    };
+    class Arc {
+      friend class FullBpGraphBase;
+    protected:
+      int _id;
+      explicit Arc(int id) { _id = id;}
+    public:
+      operator Edge() const {
+        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
+      }
+      Arc() {}
+      Arc (Invalid) { _id = -1; }
+      bool operator==(const Arc& arc) const {return _id == arc._id;}
+      bool operator!=(const Arc& arc) const {return _id != arc._id;}
+      bool operator<(const Arc& arc) const {return _id < arc._id;}
+    };
+  protected:
+    FullBpGraphBase()
+      : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {}
+    void construct(int redNum, int blueNum) {
+      _red_num = redNum; _blue_num = blueNum;
+      _node_num = redNum + blueNum; _edge_num = redNum * blueNum;
+    }
+  public:
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+    typedef True ArcNumTag;
+    int nodeNum() const { return _node_num; }
+    int redNum() const { return _red_num; }
+    int blueNum() const { return _blue_num; }
+    int edgeNum() const { return _edge_num; }
+    int arcNum() const { return 2 * _edge_num; }
+    int maxNodeId() const { return _node_num - 1; }
+    int maxRedId() const { return _red_num - 1; }
+    int maxBlueId() const { return _blue_num - 1; }
+    int maxEdgeId() const { return _edge_num - 1; }
+    int maxArcId() const { return 2 * _edge_num - 1; }
+    bool red(Node n) const { return n._id < _red_num; }
+    bool blue(Node n) const { return n._id >= _red_num; }
+    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
+    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
+    Node source(Arc a) const {
+      if (a._id & 1) {
+        return Node((a._id >> 1) % _red_num);
+      } else {
+        return Node((a._id >> 1) / _red_num + _red_num);
+      }
+    }
+    Node target(Arc a) const {
+      if (a._id & 1) {
+        return Node((a._id >> 1) / _red_num + _red_num);
+      } else {
+        return Node((a._id >> 1) % _red_num);
+      }
+    }
+    RedNode redNode(Edge e) const {
+      return RedNode(e._id % _red_num);
+    }
+    BlueNode blueNode(Edge e) const {
+      return BlueNode(e._id / _red_num + _red_num);
+    }
+    static bool direction(Arc a) {
+      return (a._id & 1) == 1;
+    }
+    static Arc direct(Edge e, bool d) {
+      return Arc(e._id * 2 + (d ? 1 : 0));
+    }
+    void first(Node& node) const {
+      node._id = _node_num - 1;
+    }
+    static void next(Node& node) {
+      --node._id;
+    }
+    void first(RedNode& node) const {
+      node._id = _red_num - 1;
+    }
+    static void next(RedNode& node) {
+      --node._id;
+    }
+    void first(BlueNode& node) const {
+      if (_red_num == _node_num) node._id = -1;
+      else node._id = _node_num - 1;
+    }
+    void next(BlueNode& node) const {
+      if (node._id == _red_num) node._id = -1;
+      else --node._id;
+    }
+    void first(Arc& arc) const {
+      arc._id = 2 * _edge_num - 1;
+    }
+    static void next(Arc& arc) {
+      --arc._id;
+    }
+    void first(Edge& arc) const {
+      arc._id = _edge_num - 1;
+    }
+    static void next(Edge& arc) {
+      --arc._id;
+    }
+    void firstOut(Arc &a, const Node& v) const {
+      if (v._id < _red_num) {
+        a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1;
+      } else {
+        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num));
+      }
+    }
+    void nextOut(Arc &a) const {
+      if (a._id & 1) {
+        a._id -= 2 * _red_num;
+        if (a._id < 0) a._id = -1;
+      } else {
+        if (a._id % (2 * _red_num) == 0) a._id = -1;
+        else a._id -= 2;
+      }
+    }
+    void firstIn(Arc &a, const Node& v) const {
+      if (v._id < _red_num) {
+        a._id = 2 * (v._id + _red_num * (_blue_num - 1));
+      } else {
+        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1;
+      }
+    }
+    void nextIn(Arc &a) const {
+      if (a._id & 1) {
+        if (a._id % (2 * _red_num) == 1) a._id = -1;
+        else a._id -= 2;
+      } else {
+        a._id -= 2 * _red_num;
+        if (a._id < 0) a._id = -1;
+      }
+    }
+    void firstInc(Edge &e, bool& d, const Node& v) const {
+      if (v._id < _red_num) {
+        d = true;
+        e._id = v._id + _red_num * (_blue_num - 1);
+      } else {
+        d = false;
+        e._id = _red_num - 1 + _red_num * (v._id - _red_num);
+      }
+    }
+    void nextInc(Edge &e, bool& d) const {
+      if (d) {
+        e._id -= _red_num;
+        if (e._id < 0) e._id = -1;
+      } else {
+        if (e._id % _red_num == 0) e._id = -1;
+        else --e._id;
+      }
+    }
+    static int id(const Node& v) { return v._id; }
+    int id(const RedNode& v) const { return v._id; }
+    int id(const BlueNode& v) const { return v._id - _red_num; }
+    static int id(Arc e) { return e._id; }
+    static int id(Edge e) { return e._id; }
+    static Node nodeFromId(int id) { return Node(id);}
+    static Arc arcFromId(int id) { return Arc(id);}
+    static Edge edgeFromId(int id) { return Edge(id);}
+    bool valid(Node n) const {
+      return n._id >= 0 && n._id < _node_num;
+    }
+    bool valid(Arc a) const {
+      return a._id >= 0 && a._id < 2 * _edge_num;
+    }
+    bool valid(Edge e) const {
+      return e._id >= 0 && e._id < _edge_num;
+    }
+    RedNode redNode(int index) const {
+      return RedNode(index);
+    }
+    int index(RedNode n) const {
+      return n._id;
+    }
+    BlueNode blueNode(int index) const {
+      return BlueNode(index + _red_num);
+    }
+    int index(BlueNode n) const {
+      return n._id - _red_num;
+    }
+    void clear() {
+      _red_num = 0; _blue_num = 0;
+      _node_num = 0; _edge_num = 0;
+    }
+    Edge edge(const Node& u, const Node& v) const {
+      if (u._id < _red_num) {
+        if (v._id < _red_num) {
+          return Edge(-1);
+        } else {
+          return Edge(u._id + _red_num * (v._id - _red_num));
+        }
+      } else {
+        if (v._id < _red_num) {
+          return Edge(v._id + _red_num * (u._id - _red_num));
+        } else {
+          return Edge(-1);
+        }
+      }
+    }
+    Arc arc(const Node& u, const Node& v) const {
+      if (u._id < _red_num) {
+        if (v._id < _red_num) {
+          return Arc(-1);
+        } else {
+          return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1);
+        }
+      } else {
+        if (v._id < _red_num) {
+          return Arc(2 * (v._id + _red_num * (u._id - _red_num)));
+        } else {
+          return Arc(-1);
+        }
+      }
+    }
+    typedef True FindEdgeTag;
+    typedef True FindArcTag;
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      return prev != INVALID ? INVALID : edge(u, v);
+    }
+    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
+      return prev != INVALID ? INVALID : arc(s, t);
+    }
+  };
+  typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase;
+  /// \ingroup graphs
+  ///
+  /// \brief An undirected full bipartite graph class.
+  ///
+  /// FullBpGraph is a simple and fast implmenetation of undirected
+  /// full bipartite graphs. It contains an edge between every
+  /// red-blue pairs of nodes, therefore the number of edges is
+  /// <tt>nr*nb</tt>.  This class is completely static and it needs
+  /// constant memory space.  Thus you can neither add nor delete
+  /// nodes or edges, however the structure can be resized using
+  /// resize().
+  ///
+  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
+  ///
+  /// \sa FullGraph
+  class FullBpGraph : public ExtendedFullBpGraphBase {
+  public:
+    typedef ExtendedFullBpGraphBase Parent;
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and edges will be zero.
+    FullBpGraph() { construct(0, 0); }
+    /// \brief Constructor
+    ///
+    /// Constructor.
+    /// \param redNum The number of the red nodes.
+    /// \param blueNum The number of the blue nodes.
+    FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); }
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
+    void resize(int redNum, int blueNum) {
+      Parent::notifier(Arc()).clear();
+      Parent::notifier(Edge()).clear();
+      Parent::notifier(Node()).clear();
+      Parent::notifier(BlueNode()).clear();
+      Parent::notifier(RedNode()).clear();
+      construct(redNum, blueNum);
+      Parent::notifier(RedNode()).build();
+      Parent::notifier(BlueNode()).build();
+      Parent::notifier(Node()).build();
+      Parent::notifier(Edge()).build();
+      Parent::notifier(Arc()).build();
+    }
+    using Parent::redNode;
+    using Parent::blueNode;
+    /// \brief Returns the red node with the given index.
+    ///
+    /// Returns the red node with the given index. Since this
+    /// structure is completely static, the red nodes can be indexed
+    /// with integers from the range <tt>[0..redNum()-1]</tt>.
+    /// \sa redIndex()
+    RedNode redNode(int index) const { return Parent::redNode(index); }
+    /// \brief Returns the index of the given red node.
+    ///
+    /// Returns the index of the given red node. Since this structure
+    /// is completely static, the red nodes can be indexed with
+    /// integers from the range <tt>[0..redNum()-1]</tt>.
+    ///
+    /// \sa operator()()
+    int index(RedNode node) const { return Parent::index(node); }
+    /// \brief Returns the blue node with the given index.
+    ///
+    /// Returns the blue node with the given index. Since this
+    /// structure is completely static, the blue nodes can be indexed
+    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
+    /// \sa blueIndex()
+    BlueNode blueNode(int index) const { return Parent::blueNode(index); }
+    /// \brief Returns the index of the given blue node.
+    ///
+    /// Returns the index of the given blue node. Since this structure
+    /// is completely static, the blue nodes can be indexed with
+    /// integers from the range <tt>[0..blueNum()-1]</tt>.
+    ///
+    /// \sa operator()()
+    int index(BlueNode node) const { return Parent::index(node); }
+    /// \brief Returns the edge which connects the given nodes.
+    ///
+    /// Returns the edge which connects the given nodes.
+    Edge edge(const Node& u, const Node& v) const {
+      return Parent::edge(u, v);
+    }
+    /// \brief Returns the arc which connects the given nodes.
+    ///
+    /// Returns the arc which connects the given nodes.
+    Arc arc(const Node& u, const Node& v) const {
+      return Parent::arc(u, v);
+    }
+    /// \brief Number of nodes.
+    int nodeNum() const { return Parent::nodeNum(); }
+    /// \brief Number of red nodes.
+    int redNum() const { return Parent::redNum(); }
+    /// \brief Number of blue nodes.
+    int blueNum() const { return Parent::blueNum(); }
+    /// \brief Number of arcs.
+    int arcNum() const { return Parent::arcNum(); }
+    /// \brief Number of edges.
+    int edgeNum() const { return Parent::edgeNum(); }
+  };
 } //namespace lemon

lemon/glpk.cc

r877	r989
557	557	void GlpkBase::_clear() {
558	558	glp_erase_prob(lp);
559		~~rows.clear();~~
560		~~cols.clear();~~
561	559	}
562	560

lemon/graph_to_eps.h

r877	r998
223	223	using T::_copyright;
224	224
225		using T::NodeTextColorType;
	225	using typename T::NodeTextColorType;
226	226	using T::CUST_COL;
227	227	using T::DIST_COL;

lemon/grosso_locatelli_pullan_mc.h

-                      r904
+                      r918
   ///
   /// This class provides a simple but highly efficient and robust heuristic
   /// method that quickly finds a large clique, but not necessarily the
+  /// method that quickly finds a quite large clique, but not necessarily the
   /// largest one.
+  /// The algorithm performs a certain number of iterations to find several
+  /// cliques and selects the largest one among them. Various limits can be
+  /// specified to control the running time and the effectiveness of the
+  /// search process.
   ///
   /// \tparam GR The undirected graph type the algorithm runs on.
 …
     };
+    /// \brief Constants for the causes of search termination.
+    ///
+    /// Enum type containing constants for the different causes of search
+    /// termination. The \ref run() function returns one of these values.
+    enum TerminationCause {
+      /// The iteration count limit is reached.
+      ITERATION_LIMIT,
+      /// The step count limit is reached.
+      STEP_LIMIT,
+      /// The clique size limit is reached.
+      SIZE_LIMIT
+    };
   private:
 …
     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
+    // The underlying graph
     const GR &_graph;
     IntNodeMap _id;
 …
     BoolMatrix _gr;
     int _n;
+    // Search options
+    bool _delta_based_restart;
+    int _restart_delta_limit;
+    // Search limits
+    int _iteration_limit;
+    int _step_limit;
+    int _size_limit;
     // The current clique
 …
     GrossoLocatelliPullanMc(const GR& graph) :
       _graph(graph), _id(_graph), _rnd(rnd)
+    {}
+    {
+      initOptions();
+    }
     /// \brief Constructor with random seed.
 …
     GrossoLocatelliPullanMc(const GR& graph, int seed) :
       _graph(graph), _id(_graph), _rnd(seed)
+    {}
+    {
+      initOptions();
+    }
     /// \brief Constructor with random number generator.
 …
     GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
       _graph(graph), _id(_graph), _rnd(random)
+    {}
+    {
+      initOptions();
+    }
     /// \name Execution Control
+    /// The \ref run() function can be used to execute the algorithm.\n
+    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
+    /// \ref sizeLimit(int) can be used to specify various limits for the
+    /// search process.
     /// @{
+    /// \brief Runs the algorithm.
+    ///
+    /// This function runs the algorithm.
+    ///
+    /// \param step_num The maximum number of node selections (steps)
+    /// during the search process.
+    /// This parameter controls the running time and the success of the
+    /// algorithm. For larger values, the algorithm runs slower but it more
+    /// \brief Sets the maximum number of iterations.
+    ///
+    /// This function sets the maximum number of iterations.
+    /// Each iteration of the algorithm finds a maximal clique (but not
+    /// necessarily the largest one) by performing several search steps
+    /// (node selections).
+    ///
+    /// This limit controls the running time and the success of the
+    /// algorithm. For larger values, the algorithm runs slower, but it more
     /// likely finds larger cliques. For smaller values, the algorithm is
     /// faster but probably gives worse results.
+    ///
+    /// The default value is \c 1000.
+    /// \c -1 means that number of iterations is not limited.
+    ///
+    /// \warning You should specify a reasonable limit for the number of
+    /// iterations and/or the number of search steps.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \sa stepLimit(int)
+    /// \sa sizeLimit(int)
+    GrossoLocatelliPullanMc& iterationLimit(int limit) {
+      _iteration_limit = limit;
+      return *this;
+    }
+    /// \brief Sets the maximum number of search steps.
+    ///
+    /// This function sets the maximum number of elementary search steps.
+    /// Each iteration of the algorithm finds a maximal clique (but not
+    /// necessarily the largest one) by performing several search steps
+    /// (node selections).
+    ///
+    /// This limit controls the running time and the success of the
+    /// algorithm. For larger values, the algorithm runs slower, but it more
+    /// likely finds larger cliques. For smaller values, the algorithm is
+    /// faster but probably gives worse results.
+    ///
+    /// The default value is \c -1, which means that number of steps
+    /// is not limited explicitly. However, the number of iterations is
+    /// limited and each iteration performs a finite number of search steps.
+    ///
+    /// \warning You should specify a reasonable limit for the number of
+    /// iterations and/or the number of search steps.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \sa iterationLimit(int)
+    /// \sa sizeLimit(int)
+    GrossoLocatelliPullanMc& stepLimit(int limit) {
+      _step_limit = limit;
+      return *this;
+    }
+    /// \brief Sets the desired clique size.
+    ///
+    /// This function sets the desired clique size that serves as a search
+    /// limit. If a clique of this size (or a larger one) is found, then the
+    /// algorithm terminates.
+    ///
+    /// This function is especially useful if you know an exact upper bound
+    /// for the size of the cliques in the graph or if any clique above
+    /// a certain size limit is sufficient for your application.
+    ///
+    /// The default value is \c -1, which means that the size limit is set to
+    /// the number of nodes in the graph.
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \sa iterationLimit(int)
+    /// \sa stepLimit(int)
+    GrossoLocatelliPullanMc& sizeLimit(int limit) {
+      _size_limit = limit;
+      return *this;
+    }
+    /// \brief The maximum number of iterations.
+    ///
+    /// This function gives back the maximum number of iterations.
+    /// \c -1 means that no limit is specified.
+    ///
+    /// \sa iterationLimit(int)
+    int iterationLimit() const {
+      return _iteration_limit;
+    }
+    /// \brief The maximum number of search steps.
+    ///
+    /// This function gives back the maximum number of search steps.
+    /// \c -1 means that no limit is specified.
+    ///
+    /// \sa stepLimit(int)
+    int stepLimit() const {
+      return _step_limit;
+    }
+    /// \brief The desired clique size.
+    ///
+    /// This function gives back the desired clique size that serves as a
+    /// search limit. \c -1 means that this limit is set to the number of
+    /// nodes in the graph.
+    ///
+    /// \sa sizeLimit(int)
+    int sizeLimit() const {
+      return _size_limit;
+    }
+    /// \brief Runs the algorithm.
+    ///
+    /// This function runs the algorithm. If one of the specified limits
+    /// is reached, the search process terminates.
+    ///
     /// \param rule The node selection rule. For more information, see
     /// \ref SelectionRule.
     ///
     /// \return The size of the found clique.
     int run(int step_num = 100000,
             SelectionRule rule = PENALTY_BASED)
+    /// \return The termination cause of the search. For more information,
+    /// see \ref TerminationCause.
+    TerminationCause run(SelectionRule rule = PENALTY_BASED)
+    {
       init();
       switch (rule) {
         case RANDOM:
           return start<RandomSelectionRule>(step_num);
+          return start<RandomSelectionRule>();
         case DEGREE_BASED:
+          return start<DegreeBasedSelectionRule>(step_num);
+        case PENALTY_BASED:
+          return start<PenaltyBasedSelectionRule>(step_num);
+      }
+      return 0; // avoid warning
+          return start<DegreeBasedSelectionRule>();
+        default:
+          return start<PenaltyBasedSelectionRule>();
+      }
+    }
 …
     /// \name Query Functions
+    /// The results of the algorithm can be obtained using these functions.\n
+    /// The run() function must be called before using them.
     /// @{
 …
   private:
+    // Initialize search options and limits
+    void initOptions() {
+      // Search options
+      _delta_based_restart = true;
+      _restart_delta_limit = 4;
+      // Search limits
+      _iteration_limit = 1000;
+      _step_limit = -1;             // this is disabled by default
+      _size_limit = -1;             // this is disabled by default
+    }
     // Adds a node to the current clique
 …
     // Executes the algorithm
     template <typename SelectionRuleImpl>
+    int start(int max_select) {
+      // Options for the restart rule
+      const bool delta_based_restart = true;
+      const int restart_delta_limit = 4;
+      if (_n == 0) return 0;
+    TerminationCause start() {
+      if (_n == 0) return SIZE_LIMIT;
       if (_n == 1) {
         _best_clique[0] = true;
         _best_size = 1;
+        return _best_size;
+      }
+      // Iterated local search
+        return SIZE_LIMIT;
+      }
+      // Iterated local search algorithm
+      const int max_size = _size_limit >= 0 ? _size_limit : _n;
+      const int max_restart = _iteration_limit >= 0 ?
+        _iteration_limit : std::numeric_limits<int>::max();
+      const int max_select = _step_limit >= 0 ?
+        _step_limit : std::numeric_limits<int>::max();
       SelectionRuleImpl sel_method(*this);
       int select = 0;
+      int select = 0, restart = 0;
       IntVector restart_nodes;
+      while (select < max_select) {
+      while (select < max_select && restart < max_restart) {
         // Perturbation/restart
+        if (delta_based_restart) {
+        restart++;
+        if (_delta_based_restart) {
           restart_nodes.clear();
           for (int i = 0; i != _n; i++) {
             if (_delta[i] >= restart_delta_limit)
+            if (_delta[i] >= _restart_delta_limit)
               restart_nodes.push_back(i);
+          }
 …
           _best_clique = _clique;
           _best_size = _size;
           if (_best_size == _n) return _best_size;
+          if (_best_size >= max_size) return SIZE_LIMIT;
+        }
         sel_method.update();
+      }
       return _best_size;
+      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
+    }

lemon/hartmann_orlin_mmc.h

r879	r1002
99	99	/// This class implements the Hartmann-Orlin algorithm for finding
100	100	/// a directed cycle of minimum mean cost in a digraph
101		/// \ref ~~amo93networkflows~~, \ref dasdan98minmeancycle.
	101	/// \ref hartmann93finding, \ref dasdan98minmeancycle.
102	102	/// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
103	103	/// it applies an efficient early termination scheme.

lemon/howard_mmc.h

-                      r877
+                      r1012
   /// This class implements Howard's policy iteration algorithm for finding
   /// a directed cycle of minimum mean cost in a digraph
   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
   /// This class provides the most efficient algorithm for the
   /// minimum mean cycle problem, though the best known theoretical
 …
     typedef TR Traits;
+    /// \brief Constants for the causes of search termination.
+    ///
+    /// Enum type containing constants for the different causes of search
+    /// termination. The \ref findCycleMean() function returns one of
+    /// these values.
+    enum TerminationCause {
+      /// No directed cycle can be found in the digraph.
+      NO_CYCLE = 0,
+      /// Optimal solution (minimum cycle mean) is found.
+      OPTIMAL = 1,
+      /// The iteration count limit is reached.
+      ITERATION_LIMIT
+    };
   private:
 …
+    }
     /// \brief Find the minimum cycle mean.
+    /// \brief Find the minimum cycle mean (or an upper bound).
     ///
     /// This function finds the minimum mean cost of the directed
+    /// cycles in the digraph.
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    bool findCycleMean() {
+    /// cycles in the digraph (or an upper bound for it).
+    ///
+    /// By default, the function finds the exact minimum cycle mean,
+    /// but an optional limit can also be specified for the number of
+    /// iterations performed during the search process.
+    /// The return value indicates if the optimal solution is found
+    /// or the iteration limit is reached. In the latter case, an
+    /// approximate solution is provided, which corresponds to a directed
+    /// cycle whose mean cost is relatively small, but not necessarily
+    /// minimal.
+    ///
+    /// \param limit  The maximum allowed number of iterations during
+    /// the search process. Its default value implies that the algorithm
+    /// runs until it finds the exact optimal solution.
+    ///
+    /// \return The termination cause of the search process.
+    /// For more information, see \ref TerminationCause.
+    TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
       // Initialize and find strongly connected components
       init();
 …
       // Find the minimum cycle mean in the components
+      int iter_count = 0;
+      bool iter_limit_reached = false;
       for (int comp = 0; comp < _comp_num; ++comp) {
         // Find the minimum mean cycle in the current component
         if (!buildPolicyGraph(comp)) continue;
         while (true) {
+          if (++iter_count > limit) {
+            iter_limit_reached = true;
+            break;
+          }
           findPolicyCycle();
           if (!computeNodeDistances()) break;
+        }
         // Update the best cycle (global minimum mean cycle)
         if ( _curr_found && (!_best_found ||
 …
           _best_node = _curr_node;
+        }
+      }
+      return _best_found;
+        if (iter_limit_reached) break;
+      }
+      if (iter_limit_reached) {
+        return ITERATION_LIMIT;
+      } else {
+        return _best_found ? OPTIMAL : NO_CYCLE;
+      }
+    }

lemon/karp_mmc.h

r877	r1002
99	99	/// This class implements Karp's algorithm for finding a directed
100	100	/// cycle of minimum mean cost in a digraph
101		/// \ref ~~amo93networkflows~~, \ref dasdan98minmeancycle.
	101	/// \ref karp78characterization, \ref dasdan98minmeancycle.
102	102	/// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
103	103	///

lemon/kruskal.h

-                      r584
+                      r921
 ///\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

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

lemon/lgf_reader.h

r8

Context Navigation

Changes in / [1037:d3dcc49e6403:1038:a2d142bb5d3c] in lemon-main

Legend: