COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
8 added
17 deleted
32 edited

Legend:

Unmodified
Added
Removed

  • AUTHORS

    r1072 r1148  
    1 The authors of the 1.x series are
     1The main developers of release series 1.x are
    22
    33 * Balazs Dezso <deba@inf.elte.hu>
    … …  
    66 * Akos Ladanyi <ladanyi@tmit.bme.hu>
    77
    8 For more details on the actual contribution, please visit the history
    9 of the main LEMON source repository: http://lemon.cs.elte.hu/hg/lemon
     8For more complete list of contributors, please visit the history of
     9the LEMON source code repository: http://lemon.cs.elte.hu/hg/lemon
    1010
    11 Moreover, this version is heavily based on the 0.x series of
    12 LEMON. Here is the list of people who contributed to those versions.
     11Moreover, this version is heavily based on version 0.x of LEMON. Here
     12is the list of people who contributed to those versions.
    1313
    1414 * Mihaly Barasz <klao@cs.elte.hu>

  • CMakeLists.txt

    r1159 r1162  
    1313ELSE()
    1414  EXECUTE_PROCESS(
    15     COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     15    COMMAND
     16    hg log -r. --template "{latesttag}"
    1617    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    17     OUTPUT_VARIABLE HG_REVISION_PATH
     18    OUTPUT_VARIABLE HG_REVISION_TAG
    1819    ERROR_QUIET
    1920    OUTPUT_STRIP_TRAILING_WHITESPACE
    2021  )
    2122  EXECUTE_PROCESS(
    22     COMMAND hg id -i
     23    COMMAND
     24    hg log -r. --template "{latesttagdistance}"
    2325    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    24     OUTPUT_VARIABLE HG_REVISION
     26    OUTPUT_VARIABLE HG_REVISION_DIST
    2527    ERROR_QUIET
    2628    OUTPUT_STRIP_TRAILING_WHITESPACE
    2729  )
    28   IF(HG_REVISION STREQUAL "")
     30  EXECUTE_PROCESS(
     31    COMMAND
     32    hg log -r. --template "{node|short}"
     33    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     34    OUTPUT_VARIABLE HG_REVISION_ID
     35    ERROR_QUIET
     36    OUTPUT_STRIP_TRAILING_WHITESPACE
     37  )
     38
     39  IF(HG_REVISION_TAG STREQUAL "")
    2940    SET(HG_REVISION_ID "hg-tip")
    3041  ELSE()
    31     IF(HG_REVISION_PATH STREQUAL "")
    32       SET(HG_REVISION_ID ${HG_REVISION})
     42    IF(HG_REVISION_TAG STREQUAL "null")
     43      SET(HG_REVISION_TAG "trunk")
     44    ELSEIF(HG_REVISION_TAG MATCHES "^r")
     45      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
     46    ENDIF()
     47    IF(HG_REVISION_DIST STREQUAL "0")
     48      SET(HG_REVISION ${HG_REVISION_TAG})
    3349    ELSE()
    34       SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     50      SET(HG_REVISION
     51        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
    3552    ENDIF()
    3653  ENDIF()
    37   SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
     54
     55  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
    3856ENDIF()
    3957
    … …  
    115133SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116134
    117 INCLUDE(FindPythonInterp)
     135INCLUDE(FindThreads)
     136
     137IF(NOT LEMON_THREADING)
     138  IF(CMAKE_USE_PTHREADS_INIT)
     139    SET(LEMON_THREADING "Pthread")
     140  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     141    SET(LEMON_THREADING "Win32")
     142  ELSE()
     143    SET(LEMON_THREADING "None")
     144  ENDIF()
     145ENDIF()
     146
     147SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     148  "Choose the threading library, options are: Pthread Win32 None."
     149  FORCE )
     150
     151IF(LEMON_THREADING STREQUAL "Pthread")
     152  SET(LEMON_USE_PTHREAD TRUE)
     153ELSEIF(LEMON_THREADING STREQUAL "Win32")
     154  SET(LEMON_USE_WIN32_THREADS TRUE)
     155ENDIF()
    118156
    119157ENABLE_TESTING()
    … …  
    127165ADD_SUBDIRECTORY(lemon)
    128166IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     167  ADD_SUBDIRECTORY(contrib)
    129168  ADD_SUBDIRECTORY(demo)
    130169  ADD_SUBDIRECTORY(tools)
    … …  
    150189ENDIF()
    151190
     191CONFIGURE_FILE(
     192  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     193  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     194  @ONLY
     195)
     196
     197SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     198STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     199SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     200ADD_CUSTOM_TARGET(dist
     201  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     202  COMMAND hg archive ${ARCHIVE_NAME}
     203  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     204  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     205  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     206  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     207  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     208  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     209  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     210  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     211  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     212  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     213  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     214  DEPENDS html
     215  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     216
     217# CPACK config (Basically for NSIS)
    152218IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    153219  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})

  • INSTALL

    r890 r1148  
    22=========================
    33
    4 Since you are reading this I assume you already obtained one of the release
    5 tarballs and successfully extracted it. The latest version of LEMON is
    6 available at our web page (http://lemon.cs.elte.hu/).
     4This file contains instructions for building and installing LEMON from
     5source on Linux. The process on Windows is similar.
    76
    8 LEMON provides two different build environments, one is based on "autotool",
    9 while the other is based on "cmake". This file contains instructions only for
    10 the former one, which is the recommended build environment on Linux, Mac OSX
    11 and other unices or if you use Cygwin on Windows. For cmake installation
    12 instructions visit http://lemon.cs.elte.hu.
     7Note that it is not necessary to install LEMON in order to use
     8it. Instead, you can easily integrate it with your own code
     9directly. For instructions, see
     10https://lemon.cs.elte.hu/trac/lemon/wiki/HowToCompile
     11
    1312
    1413In order to install LEMON from the extracted source tarball you have to
    1514issue the following commands:
    1615
    17    1. `cd lemon-x.y.z'
     16   1. Step into the root of the source directory.
    1817
    19       This command changes to the directory which was created when you
    20       extracted the sources. The x.y.z part is a version number.
     18      $ cd lemon-x.y.z
    2119
    22    2. `./configure'
     20   2. Create a build subdirectory and step into it.
    2321
    24       This command runs the configure shell script, which does some checks and
    25       creates the makefiles.
     22      $ mkdir build
     23      $ cd build
    2624
    27    3. `make'
     25   3. Perform system checks and create the makefiles.
    2826
    29       This command compiles the non-template part of LEMON into libemon.a
    30       file. It also compiles the programs in the tools subdirectory by
    31       default.
     27      $ cmake ..
    3228
    33    4. `make check'
     29   4. Build LEMON.
    3430
    35       This step is optional, but recommended. It runs the test programs that
    36       we developed for LEMON to check whether the library works properly on
    37       your platform.
     31      $ make
    3832
    39    5. `make install'
     33      This command compiles the non-template part of LEMON into
     34      libemon.a file. It also compiles the programs in the 'tools' and
     35      'demo' subdirectories.
     36
     37   5. [Optional] Compile and run the self-tests.
     38
     39      $ make check
     40
     41   5. [Optional] Generate the user documentation.
     42
     43      $ make html
     44
     45      The release tarballs already include the documentation.
     46
     47      Note that for this step you need to have the following tools
     48      installed: Python, Doxygen, Graphviz, Ghostscript, LaTeX.
     49
     50   6. [Optional] Install LEMON
     51
     52      $ make install
    4053
    4154      This command installs LEMON under /usr/local (you will need root
    42       privileges to be able to do that). If you want to install it to some
    43       other location, then pass the --prefix=DIRECTORY flag to configure in
    44       step 2. For example: `./configure --prefix=/home/username/lemon'.
    45 
    46    6. `make install-html'
    47 
    48       This command installs the documentation under share/doc/lemon/docs. The
    49       generated documentation is included in the tarball. If you want to
    50       generate it yourself, then run `make html'. Note that for this you need
    51       to have the following programs installed: Doxygen, Graphviz, Ghostscript,
    52       Latex.
    53 
     55      privileges to be able to do that). If you want to install it to
     56      some other location, then pass the
     57      -DCMAKE_INSTALL_PREFIX=DIRECTORY flag to cmake in Step 3.
     58      For example:
     59     
     60      $ cmake -DCMAKE_INSTALL_PREFIX=/home/username/lemon'
    5461
    5562Configure Options and Variables
    5663===============================
    5764
    58 In step 2 you can customize the actions of configure by setting variables
    59 and passing options to it. This can be done like this:
    60 `./configure [OPTION]... [VARIABLE=VALUE]...'
     65In Step 3, you can customize the build process by passing options to CMAKE.
    6166
    62 Below you will find some useful variables and options (see `./configure --help'
    63 for more):
     67$ cmake [OPTIONS] ..
    6468
    65 CXX='comp'
     69You find a list of the most useful options below.
    6670
    67   Change the C++ compiler to 'comp'.
    68 
    69 CXXFLAGS='flags'
    70 
    71   Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'
    72   turns on generation of aggressively optimized Pentium-M specific code.
    73 
    74 --prefix=PREFIX
     71-DCMAKE_INSTALL_PREFIX=PREFIX
    7572
    7673  Set the installation prefix to PREFIX. By default it is /usr/local.
    7774
    78 --enable-tools
     75-DCMAKE_BUILD_TYPE=[Release|Debug|Maintainer|...]
    7976
    80    Build the programs in the tools subdirectory (default).
     77  This sets the compiler options. The choices are the following
    8178
    82 --disable-tools
     79  'Release': A strong optimization is turned on (-O3 with gcc). This
     80    is the default setting and we strongly recommend using this for
     81    the final compilation.
    8382
    84    Do not build the programs in the tools subdirectory.
     83  'Debug': Optimization is turned off and debug info is added (-O0
     84    -ggdb with gcc). If is recommended during the development.
    8585
    86 --with-glpk[=PREFIX]
     86  'Maintainer': The same as 'Debug' but the compiler warnings are
     87    converted to errors (-Werror with gcc). In addition, 'make' will
     88    also automatically compile and execute the test codes. It is the
     89    best way of ensuring that LEMON codebase is clean and safe.
    8790
    88    Enable GLPK support (default). You should specify the prefix too if
    89    you installed GLPK to some non-standard location (e.g. your home
    90    directory). If it is not found, GLPK support will be disabled.
     91  'RelWithDebInfo': Optimized build with debug info.
    9192
    92 --with-glpk-includedir=DIR
     93  'MinSizeRel': Size optimized build (-Os with gcc)
    9394
    94    The directory where the GLPK header files are located. This is only
    95    useful when the GLPK headers and libraries are not under the same
    96    prefix (which is unlikely).
     95-DTEST_WITH_VALGRIND=YES
    9796
    98 --with-glpk-libdir=DIR
     97  Using this, the test codes will be executed using valgrind. It is a
     98  very effective way of identifying indexing problems and memory leaks.
    9999
    100    The directory where the GLPK libraries are located. This is only
    101    useful when the GLPK headers and libraries are not under the same
    102    prefix (which is unlikely).
     100-DCMAKE_CXX_COMPILER=path-to-compiler
    103101
    104 --without-glpk
     102  Change the compiler to be used.
    105103
    106    Disable GLPK support.
     104-DBUILD_SHARED_LIBS=TRUE
    107105
    108 --with-cplex[=PREFIX]
     106  Build shared library instead of static one. Think twice if you
     107  really want to use this option.
    109108
    110    Enable CPLEX support (default). You should specify the prefix too
    111    if you installed CPLEX to some non-standard location
    112    (e.g. /opt/ilog/cplex75). If it is not found, CPLEX support will be
    113    disabled.
     109-DGLPK_ROOT_DIR=DIRECTORY
     110-DCOIN_ROOT_DIR=DIRECTORY
     111-DCPLEX_ROOT_DIR=DIRECTORY
    114112
    115 --with-cplex-includedir=DIR
    116 
    117    The directory where the CPLEX header files are located. This is
    118    only useful when the CPLEX headers and libraries are not under the
    119    same prefix (e.g.  /usr/local/cplex/cplex75/include).
    120 
    121 --with-cplex-libdir=DIR
    122 
    123    The directory where the CPLEX libraries are located. This is only
    124    useful when the CPLEX headers and libraries are not under the same
    125    prefix (e.g.
    126    /usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_pic_mt).
    127 
    128 --without-cplex
    129 
    130    Disable CPLEX support.
    131 
    132 --with-soplex[=PREFIX]
    133 
    134    Enable SoPlex support (default). You should specify the prefix too if
    135    you installed SoPlex to some non-standard location (e.g. your home
    136    directory). If it is not found, SoPlex support will be disabled.
    137 
    138 --with-soplex-includedir=DIR
    139 
    140    The directory where the SoPlex header files are located. This is only
    141    useful when the SoPlex headers and libraries are not under the same
    142    prefix (which is unlikely).
    143 
    144 --with-soplex-libdir=DIR
    145 
    146    The directory where the SoPlex libraries are located. This is only
    147    useful when the SoPlex headers and libraries are not under the same
    148    prefix (which is unlikely).
    149 
    150 --without-soplex
    151 
    152    Disable SoPlex support.
    153 
    154 --with-coin[=PREFIX]
    155 
    156    Enable support for COIN-OR solvers (CLP and CBC). You should
    157    specify the prefix too. (by default, COIN-OR tools install
    158    themselves to the source code directory). This command enables the
    159    solvers that are actually found.
    160 
    161 --with-coin-includedir=DIR
    162 
    163    The directory where the COIN-OR header files are located. This is
    164    only useful when the COIN-OR headers and libraries are not under
    165    the same prefix (which is unlikely).
    166 
    167 --with-coin-libdir=DIR
    168 
    169    The directory where the COIN-OR libraries are located. This is only
    170    useful when the COIN-OR headers and libraries are not under the
    171    same prefix (which is unlikely).
    172 
    173 --without-coin
    174 
    175    Disable COIN-OR support.
    176 
     113  Install root directory prefixes of optional third party libraries.
    177114
    178115Makefile Variables
    179116==================
    180117
    181 Some Makefile variables are reserved by the GNU Coding Standards for
    182 the use of the "user" - the person building the package. For instance,
    183 CXX and CXXFLAGS are such variables, and have the same meaning as
    184 explained in the previous section. These variables can be set on the
    185 command line when invoking `make' like this:
    186 `make [VARIABLE=VALUE]...'
     118make VERBOSE=1
    187119
    188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
    189 to hold several compiler flags related to warnings. Its default value
    190 can be overridden when invoking `make'. For example to disable all
    191 warning flags use `make WARNINGCXXFLAGS='.
    192 
    193 In order to turn off a single flag from the default set of warning
    194 flags, you can use the CXXFLAGS variable, since this is passed after
    195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
    196 used by default when g++ is detected) you can use
    197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
     120   This results in a more verbose output by showing the full
     121   compiler and linker commands.

  • LICENSE

    r959 r1148  
    22copyright/license.
    33
    4 Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
     4Copyright (C) 2003-2012 Egervary Jeno Kombinatorikus Optimalizalasi
    55Kutatocsoport (Egervary Combinatorial Optimization Research Group,
    66EGRES).

  • cmake/version.cmake.in

    r725 r1135  
    1 SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
     1SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")

  • doc/CMakeLists.txt

    r1107 r1135  
    1717  @ONLY
    1818)
     19
     20# Copy doc from source (if exists)
     21IF(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/html AND
     22    NOT EXISTS ${CMAKE_CURRENT_BINARY_DIR}/html/index.html)
     23  MESSAGE(STATUS "Copy doc from source tree")
     24  EXECUTE_PROCESS(
     25    COMMAND cmake -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/html ${CMAKE_CURRENT_BINARY_DIR}/html
     26    )
     27ENDIF()
    1928
    2029IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)

  • doc/Doxyfile.in

    r1107 r1111  
    9696                         "@abs_top_srcdir@/lemon/concepts" \
    9797                         "@abs_top_srcdir@/demo" \
     98                         "@abs_top_srcdir@/contrib" \
    9899                         "@abs_top_srcdir@/tools" \
    99100                         "@abs_top_srcdir@/test/test_tools.h" \

  • doc/coding_style.dox

    r463 r1023  
    9999\subsection pri-loc-var Private member variables
    100100
    101 Private member variables should start with underscore
     101Private member variables should start with underscore.
    102102
    103103\code
    104 _start_with_underscores
     104_start_with_underscore
    105105\endcode
    106106

  • doc/dirs.dox

    r463 r1031  
    3232documentation.
    3333*/
     34
     35/**
     36\dir contrib
     37\brief Directory for user contributed source codes.
     38
     39You can place your own C++ code using LEMON into this directory, which
     40will compile to an executable along with LEMON when you build the
     41library. This is probably the easiest way of compiling short to medium
     42codes, for this does require neither a LEMON installed system-wide nor
     43adding several paths to the compiler.
     44
     45Please have a look at <tt>contrib/CMakeLists.txt</tt> for
     46instruction on how to add your own files into the build process.  */
    3447
    3548/**

  • doc/groups.dox

    r959 r1165  
    407407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    408408
    409 In general NetworkSimplex is the most efficient implementation,
    410 but in special cases other algorithms could be faster.
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     410implementations.
     411\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     412several thousands of nodes) and on dense graphs, while \ref CostScaling is
     413typically more efficient on large graphs (e.g. hundreds of thousands of
     414nodes or above), especially if they are sparse.
     415However, other algorithms could be faster in special cases.
    411416For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     417\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     418
     419These classes are intended to be used with integer-valued input data
     420(capacities, supply values, and costs), except for \ref CapacityScaling,
     421which is capable of handling real-valued arc costs (other numerical
     422data are required to be integer).
    413423*/
    414424
    … …  
    449459
    450460This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     461\ref amo93networkflows, \ref karp78characterization.
    452462
    453463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    … …  
    465475
    466476LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     477- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
    469478- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     479  version of Karp's algorithm \ref hartmann93finding.
    471480- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    473 
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     481  \ref dasdan98minmeancycle, \ref dasdan04experimental.
     482
     483In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475484most efficient one, though the best known theoretical bound on its running
    476485time is exponential.
    … …  
    540549
    541550/**
    542 @defgroup planar Planarity Embedding and Drawing
     551@defgroup planar Planar Embedding and Drawing
    543552@ingroup algs
    544553\brief Algorithms for planarity checking, embedding and drawing
    … …  
    552561
    553562/**
    554 @defgroup approx Approximation Algorithms
     563@defgroup approx_algs Approximation Algorithms
    555564@ingroup algs
    556565\brief Approximation algorithms.
    … …  
    558567This group contains the approximation and heuristic algorithms
    559568implemented in LEMON.
     569
     570<b>Maximum Clique Problem</b>
     571  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     572    Grosso, Locatelli, and Pullan.
    560573*/
    561574

  • doc/min_cost_flow.dox

    r956 r1164  
    102102\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    103103
    104 However if the sum of the supply values is zero, then these two problems
     104However, if the sum of the supply values is zero, then these two problems
    105105are equivalent.
    106106The \ref min_cost_flow_algs "algorithms" in LEMON support the general

  • doc/references.bib

    r802 r1164  
    55  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
    66                  {O}ptimization in {N}etworks},
    7   howpublished = {\url{http://lemon.cs.elte.hu/}},
    8   year =         2009
     7  howpublished = {\url{http://lemon.cs.elte.hu/}}
    98}
    109
    … …  
    212211  volume =       23,
    213212  pages =        {309-311}
     213}
     214
     215@article{hartmann93finding,
     216  author =       {Mark Hartmann and James B. Orlin},
     217  title =        {Finding minimum cost to time ratio cycles with small
     218                  integral transit times},
     219  journal =      {Networks},
     220  year =         1993,
     221  volume =       23,
     222  pages =        {567-574}
    214223}
    215224
    … …  
    226235}
    227236
     237@article{dasdan04experimental,
     238  author =       {Ali Dasdan},
     239  title =        {Experimental analysis of the fastest optimum cycle
     240                  ratio and mean algorithms},
     241  journal =      {ACM Trans. Des. Autom. Electron. Syst.},
     242  year =         2004,
     243  volume =       9,
     244  issue =        4,
     245  pages =        {385-418}
     246}
     247
    228248
    229249%%%%% Minimum cost flow algorithms %%%%%
    … …  
    298318  address =      {Dublin, Ireland},
    299319  year =         1991,
    300   month =        sep,
    301 }
     320  month =        sep
     321}
     322
     323%%%%% Other algorithms %%%%%
     324
     325@article{grosso08maxclique,
     326  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
     327  title =        {Simple ingredients leading to very efficient
     328                  heuristics for the maximum clique problem},
     329  journal =      {Journal of Heuristics},
     330  year =         2008,
     331  volume =       14,
     332  number =       6,
     333  pages =        {587--612}
     334}

  • lemon/CMakeLists.txt

    r1113 r1133  
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.in
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
    99)
    1010
    1111CONFIGURE_FILE(
    12   ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
    1313  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    1414  @ONLY

  • lemon/bits/alteration_notifier.h

    r463 r1131  
    2424
    2525#include <lemon/core.h>
     26#include <lemon/bits/lock.h>
    2627
    2728//\ingroup graphbits
    … …  
    252253    typedef std::list<ObserverBase*> Observers;
    253254    Observers _observers;
    254 
     255    lemon::bits::Lock _lock;
    255256
    256257  public:
    … …  
    333334
    334335    void attach(ObserverBase& observer) {
     336      _lock.lock();
    335337      observer._index = _observers.insert(_observers.begin(), &observer);
    336338      observer._notifier = this;
     339      _lock.unlock();
    337340    }
    338341
    339342    void detach(ObserverBase& observer) {
     343      _lock.lock();
    340344      _observers.erase(observer._index);
    341345      observer._index = _observers.end();
    342346      observer._notifier = 0;
     347      _lock.unlock();
    343348    }
    344349

  • lemon/bits/windows.cc

    r1055 r1163  
    131131#endif
    132132    }
     133
     134    WinLock::WinLock() {
     135#ifdef WIN32
     136      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
     137      InitializeCriticalSection(lock);
     138      _repr = lock;
     139#else
     140      _repr = 0; //Just to avoid 'unused variable' warning with clang
     141#endif
     142    }
     143   
     144    WinLock::~WinLock() {
     145#ifdef WIN32
     146      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     147      DeleteCriticalSection(lock);
     148      delete lock;
     149#endif
     150    }
     151
     152    void WinLock::lock() {
     153#ifdef WIN32
     154      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     155      EnterCriticalSection(lock);
     156#endif
     157    }
     158
     159    void WinLock::unlock() {
     160#ifdef WIN32
     161      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     162      LeaveCriticalSection(lock);
     163#endif
     164    }
    133165  }
    134166}

  • lemon/bits/windows.h

    r576 r1131  
    2929    std::string getWinFormattedDate();
    3030    int getWinRndSeed();
     31
     32    class WinLock {
     33    public:
     34      WinLock();
     35      ~WinLock();
     36      void lock();
     37      void unlock();
     38    private:
     39      void *_repr;
     40    };
    3141  }
    3242}

  • lemon/capacity_scaling.h

    r956 r1166  
    7171  /// solution method.
    7272  ///
     73  /// This algorithm is typically slower than \ref CostScaling and
     74  /// \ref NetworkSimplex, but in special cases, it can be more
     75  /// efficient than them.
     76  /// (For more information, see \ref min_cost_flow_algs "the module page".)
     77  ///
    7378  /// Most of the parameters of the problem (except for the digraph)
    7479  /// can be given using separate functions, and the algorithm can be
    … …  
    8792  /// consider to use the named template parameters instead.
    8893  ///
    89   /// \warning Both number types must be signed and all input data must
    90   /// be integer.
    91   /// \warning This algorithm does not support negative costs for such
    92   /// arcs that have infinite upper bound.
     94  /// \warning Both \c V and \c C must be signed number types.
     95  /// \warning Capacity bounds and supply values must be integer, but
     96  /// arc costs can be arbitrary real numbers.
     97  /// \warning This algorithm does not support negative costs for
     98  /// arcs having infinite upper bound.
    9399#ifdef DOXYGEN
    94100  template <typename GR, typename V, typename C, typename TR>
    … …  
    423429    ///
    424430    /// Using this function has the same effect as using \ref supplyMap()
    425     /// with such a map in which \c k is assigned to \c s, \c -k is
     431    /// with a map in which \c k is assigned to \c s, \c -k is
    426432    /// assigned to \c t and all other nodes have zero supply value.
    427433    ///
    … …  
    676682    }
    677683
    678     /// \brief Return the flow map (the primal solution).
     684    /// \brief Copy the flow values (the primal solution) into the
     685    /// given map.
    679686    ///
    680687    /// This function copies the flow value on each arc into the given
    … …  
    700707    }
    701708
    702     /// \brief Return the potential map (the dual solution).
     709    /// \brief Copy the potential values (the dual solution) into the
     710    /// given map.
    703711    ///
    704712    /// This function copies the potential (dual value) of each node

  • lemon/config.h.in

    r725 r1133  
    1 /* The version string */
    2 #undef LEMON_VERSION
    3 
    4 /* Define to 1 if you have long long */
    5 #undef LEMON_HAVE_LONG_LONG
    6 
    7 /* Define to 1 if you have any LP solver. */
    8 #undef LEMON_HAVE_LP
    9 
    10 /* Define to 1 if you have any MIP solver. */
    11 #undef LEMON_HAVE_MIP
    12 
    13 /* Define to 1 if you have CPLEX. */
    14 #undef LEMON_HAVE_CPLEX
    15 
    16 /* Define to 1 if you have GLPK. */
    17 #undef LEMON_HAVE_GLPK
    18 
    19 /* Define to 1 if you have SOPLEX */
    20 #undef LEMON_HAVE_SOPLEX
    21 
    22 /* Define to 1 if you have CLP */
    23 #undef LEMON_HAVE_CLP
    24 
    25 /* Define to 1 if you have CBC */
    26 #undef LEMON_HAVE_CBC
     1#define LEMON_VERSION "@PROJECT_VERSION@"
     2#cmakedefine LEMON_HAVE_LONG_LONG 1
     3#cmakedefine LEMON_HAVE_LP 1
     4#cmakedefine LEMON_HAVE_MIP 1
     5#cmakedefine LEMON_HAVE_GLPK 1
     6#cmakedefine LEMON_HAVE_CPLEX 1
     7#cmakedefine LEMON_HAVE_CLP 1
     8#cmakedefine LEMON_HAVE_CBC 1
     9#cmakedefine LEMON_USE_PTHREAD 1
     10#cmakedefine LEMON_USE_WIN32_THREADS 1

  • lemon/core.h

    r1159 r1162  
    447447
    448448  }
     449
     450  /// \brief Check whether a graph is undirected.
     451  ///
     452  /// This function returns \c true if the given graph is undirected.
     453#ifdef DOXYGEN
     454  template <typename GR>
     455  bool undirected(const GR& g) { return false; }
     456#else
     457  template <typename GR>
     458  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     459  undirected(const GR&) {
     460    return true;
     461  }
     462  template <typename GR>
     463  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     464  undirected(const GR&) {
     465    return false;
     466  }
     467#endif
    449468
    450469  /// \brief Class to copy a digraph.

  • lemon/cost_scaling.h

    r1041 r1165  
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
    9999  ///
     100  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     101  /// implementations available in LEMON for solving this problem.
     102  /// (For more information, see \ref min_cost_flow_algs "the module page".)
     103  ///
    100104  /// Most of the parameters of the problem (except for the digraph)
    101105  /// can be given using separate functions, and the algorithm can be
    … …  
    114118  /// consider to use the named template parameters instead.
    115119  ///
    116   /// \warning Both number types must be signed and all input data must
     120  /// \warning Both \c V and \c C must be signed number types.
     121  /// \warning All input data (capacities, supply values, and costs) must
    117122  /// be integer.
    118   /// \warning This algorithm does not support negative costs for such
    119   /// arcs that have infinite upper bound.
     123  /// \warning This algorithm does not support negative costs for
     124  /// arcs having infinite upper bound.
    120125  ///
    121126  /// \note %CostScaling provides three different internal methods,
    … …  
    179184    /// relabel operation.
    180185    /// By default, the so called \ref PARTIAL_AUGMENT
    181     /// "Partial Augment-Relabel" method is used, which proved to be
     186    /// "Partial Augment-Relabel" method is used, which turned out to be
    182187    /// the most efficient and the most robust on various test inputs.
    183188    /// However, the other methods can be selected using the \ref run()
    … …  
    234239    };
    235240
    236     typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    237241    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    238242
    … …  
    285289    int _max_rank;
    286290
    287     // Data for a StaticDigraph structure
    288     typedef std::pair<int, int> IntPair;
    289     StaticDigraph _sgr;
    290     std::vector<IntPair> _arc_vec;
    291     std::vector<LargeCost> _cost_vec;
    292     LargeCostArcMap _cost_map;
    293     LargeCostNodeMap _pi_map;
    294 
    295291  public:
    296292
    … …  
    339335    CostScaling(const GR& graph) :
    340336      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
    341       _cost_map(_cost_vec), _pi_map(_pi),
    342337      INF(std::numeric_limits<Value>::has_infinity ?
    343338          std::numeric_limits<Value>::infinity() :
    … …  
    448443    ///
    449444    /// Using this function has the same effect as using \ref supplyMap()
    450     /// with such a map in which \c k is assigned to \c s, \c -k is
     445    /// with a map in which \c k is assigned to \c s, \c -k is
    451446    /// assigned to \c t and all other nodes have zero supply value.
    452447    ///
    … …  
    494489    /// \param method The internal method that will be used in the
    495490    /// algorithm. For more information, see \ref Method.
    496     /// \param factor The cost scaling factor. It must be larger than one.
     491    /// \param factor The cost scaling factor. It must be at least two.
    497492    ///
    498493    /// \return \c INFEASIBLE if no feasible flow exists,
    … …  
    508503    /// \see ProblemType, Method
    509504    /// \see resetParams(), reset()
    510     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     505    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
     506      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
    511507      _alpha = factor;
    512508      ProblemType pt = init();
    … …  
    572568    }
    573569
    574     /// \brief Reset all the parameters that have been given before.
    575     ///
    576     /// This function resets all the paramaters that have been given
    577     /// before using functions \ref lowerMap(), \ref upperMap(),
    578     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    579     ///
    580     /// It is useful for multiple run() calls. If this function is not
    581     /// used, all the parameters given before are kept for the next
    582     /// \ref run() call.
    583     /// However, the underlying digraph must not be modified after this
    584     /// class have been constructed, since it copies and extends the graph.
     570    /// \brief Reset the internal data structures and all the parameters
     571    /// that have been given before.
     572    ///
     573    /// This function resets the internal data structures and all the
     574    /// paramaters that have been given before using functions \ref lowerMap(),
     575    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     576    ///
     577    /// It is useful for multiple \ref run() calls. By default, all the given
     578    /// parameters are kept for the next \ref run() call, unless
     579    /// \ref resetParams() or \ref reset() is used.
     580    /// If the underlying digraph was also modified after the construction
     581    /// of the class or the last \ref reset() call, then the \ref reset()
     582    /// function must be used, otherwise \ref resetParams() is sufficient.
     583    ///
     584    /// See \ref resetParams() for examples.
     585    ///
    585586    /// \return <tt>(*this)</tt>
     587    ///
     588    /// \see resetParams(), run()
    586589    CostScaling& reset() {
    587590      // Resize vectors
    … …  
    608611      _excess.resize(_res_node_num);
    609612      _next_out.resize(_res_node_num);
    610 
    611       _arc_vec.reserve(_res_arc_num);
    612       _cost_vec.reserve(_res_arc_num);
    613613
    614614      // Copy the graph
    … …  
    706706    }
    707707
    708     /// \brief Return the flow map (the primal solution).
     708    /// \brief Copy the flow values (the primal solution) into the
     709    /// given map.
    709710    ///
    710711    /// This function copies the flow value on each arc into the given
    … …  
    730731    }
    731732
    732     /// \brief Return the potential map (the dual solution).
     733    /// \brief Copy the potential values (the dual solution) into the
     734    /// given map.
    733735    ///
    734736    /// This function copies the potential (dual value) of each node
    … …  
    887889      }
    888890
    889       return OPTIMAL;
    890     }
    891 
    892     // Execute the algorithm and transform the results
    893     void start(Method method) {
    894       // Maximum path length for partial augment
    895       const int MAX_PATH_LENGTH = 4;
    896 
    897891      // Initialize data structures for buckets
    898892      _max_rank = _alpha * _res_node_num;
    … …  
    902896      _rank.resize(_res_node_num + 1);
    903897
    904       // Execute the algorithm
     898      return OPTIMAL;
     899    }
     900
     901    // Execute the algorithm and transform the results
     902    void start(Method method) {
     903      const int MAX_PARTIAL_PATH_LENGTH = 4;
     904
    905905      switch (method) {
    906906        case PUSH:
    … …  
    911911          break;
    912912        case PARTIAL_AUGMENT:
    913           startAugment(MAX_PATH_LENGTH);
     913          startAugment(MAX_PARTIAL_PATH_LENGTH);
    914914          break;
    915915      }
    916916
    917       // Compute node potentials for the original costs
    918       _arc_vec.clear();
    919       _cost_vec.clear();
    920       for (int j = 0; j != _res_arc_num; ++j) {
    921         if (_res_cap[j] > 0) {
    922           _arc_vec.push_back(IntPair(_source[j], _target[j]));
    923           _cost_vec.push_back(_scost[j]);
    924         }
    925       }
    926       _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    927 
    928       typename BellmanFord<StaticDigraph, LargeCostArcMap>
    929         ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
    930       bf.distMap(_pi_map);
    931       bf.init(0);
    932       bf.start();
     917      // Compute node potentials (dual solution)
     918      for (int i = 0; i != _res_node_num; ++i) {
     919        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
     920      }
     921      bool optimal = true;
     922      for (int i = 0; optimal && i != _res_node_num; ++i) {
     923        LargeCost pi_i = _pi[i];
     924        int last_out = _first_out[i+1];
     925        for (int j = _first_out[i]; j != last_out; ++j) {
     926          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
     927            optimal = false;
     928            break;
     929          }
     930        }
     931      }
     932
     933      if (!optimal) {
     934        // Compute node potentials for the original costs with BellmanFord
     935        // (if it is necessary)
     936        typedef std::pair<int, int> IntPair;
     937        StaticDigraph sgr;
     938        std::vector<IntPair> arc_vec;
     939        std::vector<LargeCost> cost_vec;
     940        LargeCostArcMap cost_map(cost_vec);
     941
     942        arc_vec.clear();
     943        cost_vec.clear();
     944        for (int j = 0; j != _res_arc_num; ++j) {
     945          if (_res_cap[j] > 0) {
     946            int u = _source[j], v = _target[j];
     947            arc_vec.push_back(IntPair(u, v));
     948            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
     949          }
     950        }
     951        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
     952
     953        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
     954          bf(sgr, cost_map);
     955        bf.init(0);
     956        bf.start();
     957
     958        for (int i = 0; i != _res_node_num; ++i) {
     959          _pi[i] += bf.dist(sgr.node(i));
     960        }
     961      }
     962
     963      // Shift potentials to meet the requirements of the GEQ type
     964      // optimality conditions
     965      LargeCost max_pot = _pi[_root];
     966      for (int i = 0; i != _res_node_num; ++i) {
     967        if (_pi[i] > max_pot) max_pot = _pi[i];
     968      }
     969      if (max_pot != 0) {
     970        for (int i = 0; i != _res_node_num; ++i) {
     971          _pi[i] -= max_pot;
     972        }
     973      }
    933974
    934975      // Handle non-zero lower bounds
    … …  
    948989        LargeCost pi_u = _pi[u];
    949990        for (int a = _first_out[u]; a != last_out; ++a) {
    950           int v = _target[a];
    951           if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
    952             Value delta = _res_cap[a];
    953             _excess[u] -= delta;
    954             _excess[v] += delta;
    955             _res_cap[a] = 0;
    956             _res_cap[_reverse[a]] += delta;
     991          Value delta = _res_cap[a];
     992          if (delta > 0) {
     993            int v = _target[a];
     994            if (_cost[a] + pi_u - _pi[v] < 0) {
     995              _excess[u] -= delta;
     996              _excess[v] += delta;
     997              _res_cap[a] = 0;
     998              _res_cap[_reverse[a]] += delta;
     999            }
    9571000          }
    9581001        }
    … …  
    9701013    }
    9711014
    972     // Early termination heuristic
    973     bool earlyTermination() {
    974       const double EARLY_TERM_FACTOR = 3.0;
    975 
    976       // Build a static residual graph
    977       _arc_vec.clear();
    978       _cost_vec.clear();
    979       for (int j = 0; j != _res_arc_num; ++j) {
    980         if (_res_cap[j] > 0) {
    981           _arc_vec.push_back(IntPair(_source[j], _target[j]));
    982           _cost_vec.push_back(_cost[j] + 1);
    983         }
    984       }
    985       _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
    986 
    987       // Run Bellman-Ford algorithm to check if the current flow is optimal
    988       BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
    989       bf.init(0);
    990       bool done = false;
    991       int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
    992       for (int i = 0; i < K && !done; ++i) {
    993         done = bf.processNextWeakRound();
    994       }
    995       return done;
     1015    // Price (potential) refinement heuristic
     1016    bool priceRefinement() {
     1017
     1018      // Stack for stroing the topological order
     1019      IntVector stack(_res_node_num);
     1020      int stack_top;
     1021
     1022      // Perform phases
     1023      while (topologicalSort(stack, stack_top)) {
     1024
     1025        // Compute node ranks in the acyclic admissible network and
     1026        // store the nodes in buckets
     1027        for (int i = 0; i != _res_node_num; ++i) {
     1028          _rank[i] = 0;
     1029        }
     1030        const int bucket_end = _root + 1;
     1031        for (int r = 0; r != _max_rank; ++r) {
     1032          _buckets[r] = bucket_end;
     1033        }
     1034        int top_rank = 0;
     1035        for ( ; stack_top >= 0; --stack_top) {
     1036          int u = stack[stack_top], v;
     1037          int rank_u = _rank[u];
     1038
     1039          LargeCost rc, pi_u = _pi[u];
     1040          int last_out = _first_out[u+1];
     1041          for (int a = _first_out[u]; a != last_out; ++a) {
     1042            if (_res_cap[a] > 0) {
     1043              v = _target[a];
     1044              rc = _cost[a] + pi_u - _pi[v];
     1045              if (rc < 0) {
     1046                LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
     1047                if (nrc < LargeCost(_max_rank)) {
     1048                  int new_rank_v = rank_u + static_cast<int>(nrc);
     1049                  if (new_rank_v > _rank[v]) {
     1050                    _rank[v] = new_rank_v;
     1051                  }
     1052                }
     1053              }
     1054            }
     1055          }
     1056
     1057          if (rank_u > 0) {
     1058            top_rank = std::max(top_rank, rank_u);
     1059            int bfirst = _buckets[rank_u];
     1060            _bucket_next[u] = bfirst;
     1061            _bucket_prev[bfirst] = u;
     1062            _buckets[rank_u] = u;
     1063          }
     1064        }
     1065
     1066        // Check if the current flow is epsilon-optimal
     1067        if (top_rank == 0) {
     1068          return true;
     1069        }
     1070
     1071        // Process buckets in top-down order
     1072        for (int rank = top_rank; rank > 0; --rank) {
     1073          while (_buckets[rank] != bucket_end) {
     1074            // Remove the first node from the current bucket
     1075            int u = _buckets[rank];
     1076            _buckets[rank] = _bucket_next[u];
     1077
     1078            // Search the outgoing arcs of u
     1079            LargeCost rc, pi_u = _pi[u];
     1080            int last_out = _first_out[u+1];
     1081            int v, old_rank_v, new_rank_v;
     1082            for (int a = _first_out[u]; a != last_out; ++a) {
     1083              if (_res_cap[a] > 0) {
     1084                v = _target[a];
     1085                old_rank_v = _rank[v];
     1086
     1087                if (old_rank_v < rank) {
     1088
     1089                  // Compute the new rank of node v
     1090                  rc = _cost[a] + pi_u - _pi[v];
     1091                  if (rc < 0) {
     1092                    new_rank_v = rank;
     1093                  } else {
     1094                    LargeCost nrc = rc / _epsilon;
     1095                    new_rank_v = 0;
     1096                    if (nrc < LargeCost(_max_rank)) {
     1097                      new_rank_v = rank - 1 - static_cast<int>(nrc);
     1098                    }
     1099                  }
     1100
     1101                  // Change the rank of node v
     1102                  if (new_rank_v > old_rank_v) {
     1103                    _rank[v] = new_rank_v;
     1104
     1105                    // Remove v from its old bucket
     1106                    if (old_rank_v > 0) {
     1107                      if (_buckets[old_rank_v] == v) {
     1108                        _buckets[old_rank_v] = _bucket_next[v];
     1109                      } else {
     1110                        int pv = _bucket_prev[v], nv = _bucket_next[v];
     1111                        _bucket_next[pv] = nv;
     1112                        _bucket_prev[nv] = pv;
     1113                      }
     1114                    }
     1115
     1116                    // Insert v into its new bucket
     1117                    int nv = _buckets[new_rank_v];
     1118                    _bucket_next[v] = nv;
     1119                    _bucket_prev[nv] = v;
     1120                    _buckets[new_rank_v] = v;
     1121                  }
     1122                }
     1123              }
     1124            }
     1125
     1126            // Refine potential of node u
     1127            _pi[u] -= rank * _epsilon;
     1128          }
     1129        }
     1130
     1131      }
     1132
     1133      return false;
     1134    }
     1135
     1136    // Find and cancel cycles in the admissible network and
     1137    // determine topological order using DFS
     1138    bool topologicalSort(IntVector &stack, int &stack_top) {
     1139      const int MAX_CYCLE_CANCEL = 1;
     1140
     1141      BoolVector reached(_res_node_num, false);
     1142      BoolVector processed(_res_node_num, false);
     1143      IntVector pred(_res_node_num);
     1144      for (int i = 0; i != _res_node_num; ++i) {
     1145        _next_out[i] = _first_out[i];
     1146      }
     1147      stack_top = -1;
     1148
     1149      int cycle_cnt = 0;
     1150      for (int start = 0; start != _res_node_num; ++start) {
     1151        if (reached[start]) continue;
     1152
     1153        // Start DFS search from this start node
     1154        pred[start] = -1;
     1155        int tip = start, v;
     1156        while (true) {
     1157          // Check the outgoing arcs of the current tip node
     1158          reached[tip] = true;
     1159          LargeCost pi_tip = _pi[tip];
     1160          int a, last_out = _first_out[tip+1];
     1161          for (a = _next_out[tip]; a != last_out; ++a) {
     1162            if (_res_cap[a] > 0) {
     1163              v = _target[a];
     1164              if (_cost[a] + pi_tip - _pi[v] < 0) {
     1165                if (!reached[v]) {
     1166                  // A new node is reached
     1167                  reached[v] = true;
     1168                  pred[v] = tip;
     1169                  _next_out[tip] = a;
     1170                  tip = v;
     1171                  a = _next_out[tip];
     1172                  last_out = _first_out[tip+1];
     1173                  break;
     1174                }
     1175                else if (!processed[v]) {
     1176                  // A cycle is found
     1177                  ++cycle_cnt;
     1178                  _next_out[tip] = a;
     1179
     1180                  // Find the minimum residual capacity along the cycle
     1181                  Value d, delta = _res_cap[a];
     1182                  int u, delta_node = tip;
     1183                  for (u = tip; u != v; ) {
     1184                    u = pred[u];
     1185                    d = _res_cap[_next_out[u]];
     1186                    if (d <= delta) {
     1187                      delta = d;
     1188                      delta_node = u;
     1189                    }
     1190                  }
     1191
     1192                  // Augment along the cycle
     1193                  _res_cap[a] -= delta;
     1194                  _res_cap[_reverse[a]] += delta;
     1195                  for (u = tip; u != v; ) {
     1196                    u = pred[u];
     1197                    int ca = _next_out[u];
     1198                    _res_cap[ca] -= delta;
     1199                    _res_cap[_reverse[ca]] += delta;
     1200                  }
     1201
     1202                  // Check the maximum number of cycle canceling
     1203                  if (cycle_cnt >= MAX_CYCLE_CANCEL) {
     1204                    return false;
     1205                  }
     1206
     1207                  // Roll back search to delta_node
     1208                  if (delta_node != tip) {
     1209                    for (u = tip; u != delta_node; u = pred[u]) {
     1210                      reached[u] = false;
     1211                    }
     1212                    tip = delta_node;
     1213                    a = _next_out[tip] + 1;
     1214                    last_out = _first_out[tip+1];
     1215                    break;
     1216                  }
     1217                }
     1218              }
     1219            }
     1220          }
     1221
     1222          // Step back to the previous node
     1223          if (a == last_out) {
     1224            processed[tip] = true;
     1225            stack[++stack_top] = tip;
     1226            tip = pred[tip];
     1227            if (tip < 0) {
     1228              // Finish DFS from the current start node
     1229              break;
     1230            }
     1231            ++_next_out[tip];
     1232          }
     1233        }
     1234
     1235      }
     1236
     1237      return (cycle_cnt == 0);
    9961238    }
    9971239
    9981240    // Global potential update heuristic
    9991241    void globalUpdate() {
    1000       int bucket_end = _root + 1;
     1242      const int bucket_end = _root + 1;
    10011243
    10021244      // Initialize buckets
    … …  
    10051247      }
    10061248      Value total_excess = 0;
     1249      int b0 = bucket_end;
    10071250      for (int i = 0; i != _res_node_num; ++i) {
    10081251        if (_excess[i] < 0) {
    10091252          _rank[i] = 0;
    1010           _bucket_next[i] = _buckets[0];
    1011           _bucket_prev[_buckets[0]] = i;
    1012           _buckets[0] = i;
     1253          _bucket_next[i] = b0;
     1254          _bucket_prev[b0] = i;
     1255          b0 = i;
    10131256        } else {
    10141257          total_excess += _excess[i];
    … …  
    10171260      }
    10181261      if (total_excess == 0) return;
     1262      _buckets[0] = b0;
    10191263
    10201264      // Search the buckets
    … …  
    10381282                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
    10391283                int new_rank_v = old_rank_v;
    1040                 if (nrc < LargeCost(_max_rank))
    1041                   new_rank_v = r + 1 + int(nrc);
     1284                if (nrc < LargeCost(_max_rank)) {
     1285                  new_rank_v = r + 1 + static_cast<int>(nrc);
     1286                }
    10421287
    10431288                // Change the rank of v
    … …  
    10511296                      _buckets[old_rank_v] = _bucket_next[v];
    10521297                    } else {
    1053                       _bucket_next[_bucket_prev[v]] = _bucket_next[v];
    1054                       _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1298                      int pv = _bucket_prev[v], nv = _bucket_next[v];
     1299                      _bucket_next[pv] = nv;
     1300                      _bucket_prev[nv] = pv;
    10551301                    }
    10561302                  }
    10571303
    1058                   // Insert v to its new bucket
    1059                   _bucket_next[v] = _buckets[new_rank_v];
    1060                   _bucket_prev[_buckets[new_rank_v]] = v;
     1304                  // Insert v into its new bucket
     1305                  int nv = _buckets[new_rank_v];
     1306                  _bucket_next[v] = nv;
     1307                  _bucket_prev[nv] = v;
    10611308                  _buckets[new_rank_v] = v;
    10621309                }
    … …  
    10871334    void startAugment(int max_length) {
    10881335      // Paramters for heuristics
    1089       const int EARLY_TERM_EPSILON_LIMIT = 1000;
    1090       const double GLOBAL_UPDATE_FACTOR = 3.0;
    1091 
    1092       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1336      const int PRICE_REFINEMENT_LIMIT = 2;
     1337      const double GLOBAL_UPDATE_FACTOR = 1.0;
     1338      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    10931339        (_res_node_num + _sup_node_num * _sup_node_num));
    1094       int next_update_limit = global_update_freq;
    1095 
     1340      int next_global_update_limit = global_update_skip;
     1341
     1342      // Perform cost scaling phases
     1343      IntVector path;
     1344      BoolVector path_arc(_res_arc_num, false);
    10961345      int relabel_cnt = 0;
    1097 
    1098       // Perform cost scaling phases
    1099       std::vector<int> path;
     1346      int eps_phase_cnt = 0;
    11001347      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    11011348                                        1 : _epsilon / _alpha )
    11021349      {
    1103         // Early termination heuristic
    1104         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1105           if (earlyTermination()) break;
     1350        ++eps_phase_cnt;
     1351
     1352        // Price refinement heuristic
     1353        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1354          if (priceRefinement()) continue;
    11061355        }
    11071356
    … …  
    11201369
    11211370          // Find an augmenting path from the start node
    1122           path.clear();
    11231371          int tip = start;
    1124           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
     1372          while (int(path.size()) < max_length && _excess[tip] >= 0) {
    11251373            int u;
    1126             LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1374            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
     1375            LargeCost pi_tip = _pi[tip];
    11271376            int last_out = _first_out[tip+1];
    11281377            for (int a = _next_out[tip]; a != last_out; ++a) {
    1129               u = _target[a];
    1130               if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
    1131                 path.push_back(a);
    1132                 _next_out[tip] = a;
    1133                 tip = u;
    1134                 goto next_step;
     1378              if (_res_cap[a] > 0) {
     1379                u = _target[a];
     1380                rc = _cost[a] + pi_tip - _pi[u];
     1381                if (rc < 0) {
     1382                  path.push_back(a);
     1383                  _next_out[tip] = a;
     1384                  if (path_arc[a]) {
     1385                    goto augment;   // a cycle is found, stop path search
     1386                  }
     1387                  tip = u;
     1388                  path_arc[a] = true;
     1389                  goto next_step;
     1390                }
     1391                else if (rc < min_red_cost) {
     1392                  min_red_cost = rc;
     1393                }
    11351394              }
    11361395            }
    11371396
    11381397            // Relabel tip node
    1139             min_red_cost = std::numeric_limits<LargeCost>::max();
    11401398            if (tip != start) {
    11411399              int ra = _reverse[path.back()];
    1142               min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1400              min_red_cost =
     1401                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
    11431402            }
     1403            last_out = _next_out[tip];
    11441404            for (int a = _first_out[tip]; a != last_out; ++a) {
    1145               rc = _cost[a] + pi_tip - _pi[_target[a]];
    1146               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1147                 min_red_cost = rc;
     1405              if (_res_cap[a] > 0) {
     1406                rc = _cost[a] + pi_tip - _pi[_target[a]];
     1407                if (rc < min_red_cost) {
     1408                  min_red_cost = rc;
     1409                }
    11481410              }
    11491411            }
    … …  
    11541416            // Step back
    11551417            if (tip != start) {
    1156               tip = _source[path.back()];
     1418              int pa = path.back();
     1419              path_arc[pa] = false;
     1420              tip = _source[pa];
    11571421              path.pop_back();
    11581422            }
    … …  
    11621426
    11631427          // Augment along the found path (as much flow as possible)
     1428        augment:
    11641429          Value delta;
    11651430          int pa, u, v = start;
    … …  
    11681433            u = v;
    11691434            v = _target[pa];
     1435            path_arc[pa] = false;
    11701436            delta = std::min(_res_cap[pa], _excess[u]);
    11711437            _res_cap[pa] -= delta;
    … …  
    11731439            _excess[u] -= delta;
    11741440            _excess[v] += delta;
    1175             if (_excess[v] > 0 && _excess[v] <= delta)
     1441            if (_excess[v] > 0 && _excess[v] <= delta) {
    11761442              _active_nodes.push_back(v);
    1177           }
     1443            }
     1444          }
     1445          path.clear();
    11781446
    11791447          // Global update heuristic
    1180           if (relabel_cnt >= next_update_limit) {
     1448          if (relabel_cnt >= next_global_update_limit) {
    11811449            globalUpdate();
    1182             next_update_limit += global_update_freq;
    1183           }
    1184         }
    1185       }
     1450            next_global_update_limit += global_update_skip;
     1451          }
     1452        }
     1453
     1454      }
     1455
    11861456    }
    11871457
    … …  
    11891459    void startPush() {
    11901460      // Paramters for heuristics
    1191       const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1461      const int PRICE_REFINEMENT_LIMIT = 2;
    11921462      const double GLOBAL_UPDATE_FACTOR = 2.0;
    11931463
    1194       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1464      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    11951465        (_res_node_num + _sup_node_num * _sup_node_num));
    1196       int next_update_limit = global_update_freq;
    1197 
    1198       int relabel_cnt = 0;
     1466      int next_global_update_limit = global_update_skip;
    11991467
    12001468      // Perform cost scaling phases
    12011469      BoolVector hyper(_res_node_num, false);
    12021470      LargeCostVector hyper_cost(_res_node_num);
     1471      int relabel_cnt = 0;
     1472      int eps_phase_cnt = 0;
    12031473      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    12041474                                        1 : _epsilon / _alpha )
    12051475      {
    1206         // Early termination heuristic
    1207         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1208           if (earlyTermination()) break;
     1476        ++eps_phase_cnt;
     1477
     1478        // Price refinement heuristic
     1479        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1480          if (priceRefinement()) continue;
    12091481        }
    12101482
    … …  
    12781550               std::numeric_limits<LargeCost>::max();
    12791551            for (int a = _first_out[n]; a != last_out; ++a) {
    1280               rc = _cost[a] + pi_n - _pi[_target[a]];
    1281               if (_res_cap[a] > 0 && rc < min_red_cost) {
    1282                 min_red_cost = rc;
     1552              if (_res_cap[a] > 0) {
     1553                rc = _cost[a] + pi_n - _pi[_target[a]];
     1554                if (rc < min_red_cost) {
     1555                  min_red_cost = rc;
     1556                }
    12831557              }
    12841558            }
    … …  
    12981572
    12991573          // Global update heuristic
    1300           if (relabel_cnt >= next_update_limit) {
     1574          if (relabel_cnt >= next_global_update_limit) {
    13011575            globalUpdate();
    13021576            for (int u = 0; u != _res_node_num; ++u)
    13031577              hyper[u] = false;
    1304             next_update_limit += global_update_freq;
     1578            next_global_update_limit += global_update_skip;
    13051579          }
    13061580        }

  • lemon/cycle_canceling.h

    r956 r1165  
    4949  /// \ref amo93networkflows, \ref klein67primal,
    5050  /// \ref goldberg89cyclecanceling.
    51   /// The most efficent one (both theoretically and practically)
    52   /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
    53   /// thus it is the default method.
    54   /// It is strongly polynomial, but in practice, it is typically much
    55   /// slower than the scaling algorithms and NetworkSimplex.
     51  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
     52  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
     53  /// It runs in strongly polynomial time, but in practice, it is typically
     54  /// orders of magnitude slower than the scaling algorithms and
     55  /// \ref NetworkSimplex.
     56  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5657  ///
    5758  /// Most of the parameters of the problem (except for the digraph)
    … …  
    6667  /// algorithm. By default, it is the same as \c V.
    6768  ///
    68   /// \warning Both number types must be signed and all input data must
     69  /// \warning Both \c V and \c C must be signed number types.
     70  /// \warning All input data (capacities, supply values, and costs) must
    6971  /// be integer.
    70   /// \warning This algorithm does not support negative costs for such
    71   /// arcs that have infinite upper bound.
     72  /// \warning This algorithm does not support negative costs for
     73  /// arcs having infinite upper bound.
    7274  ///
    7375  /// \note For more information about the three available methods,
    … …  
    116118    ///
    117119    /// \ref CycleCanceling provides three different cycle-canceling
    118     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
    119     /// is used, which proved to be the most efficient and the most robust
    120     /// on various test inputs.
     120    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
     121    /// is used, which is by far the most efficient and the most robust.
    121122    /// However, the other methods can be selected using the \ref run()
    122123    /// function with the proper parameter.
    123124    enum Method {
    124125      /// A simple cycle-canceling method, which uses the
    125       /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
    126       /// number for detecting negative cycles in the residual network.
     126      /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
     127      /// cycles in the residual network.
     128      /// The number of Bellman-Ford iterations is bounded by a successively
     129      /// increased limit.
    127130      SIMPLE_CYCLE_CANCELING,
    128131      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    … …  
    130133      /// \ref goldberg89cyclecanceling. It improves along a
    131134      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    132       /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
     135      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
    133136      MINIMUM_MEAN_CYCLE_CANCELING,
    134       /// The "Cancel And Tighten" algorithm, which can be viewed as an
     137      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    135138      /// improved version of the previous method
    136139      /// \ref goldberg89cyclecanceling.
    137140      /// It is faster both in theory and in practice, its running time
    138       /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
     141      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
    139142      CANCEL_AND_TIGHTEN
    140143    };
    … …  
    350353    ///
    351354    /// Using this function has the same effect as using \ref supplyMap()
    352     /// with such a map in which \c k is assigned to \c s, \c -k is
     355    /// with a map in which \c k is assigned to \c s, \c -k is
    353356    /// assigned to \c t and all other nodes have zero supply value.
    354357    ///
    … …  
    611614    }
    612615
    613     /// \brief Return the flow map (the primal solution).
     616    /// \brief Copy the flow values (the primal solution) into the
     617    /// given map.
    614618    ///
    615619    /// This function copies the flow value on each arc into the given
    … …  
    635639    }
    636640
    637     /// \brief Return the potential map (the dual solution).
     641    /// \brief Copy the potential values (the dual solution) into the
     642    /// given map.
    638643    ///
    639644    /// This function copies the potential (dual value) of each node
    … …  
    955960    }
    956961
    957     // Execute the "Cancel And Tighten" method
     962    // Execute the "Cancel-and-Tighten" method
    958963    void startCancelAndTighten() {
    959964      // Constants for the min mean cycle computations

  • lemon/euler.h

    r956 r1023  
    3737  ///Euler tour iterator for digraphs.
    3838
    39   /// \ingroup graph_prop
     39  /// \ingroup graph_properties
    4040  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    4141  ///graph (if there exists) and it converts to the \c Arc type of the digraph.

  • lemon/hao_orlin.h

    r956 r1019  
    5454  /// preflow push-relabel algorithm. Our implementation calculates
    5555  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    56   /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    57   /// purpose of such algorithm is e.g. testing network reliability.
     56  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
     57  /// use of this algorithm is testing network reliability.
    5858  ///
    5959  /// For an undirected graph you can run just the first phase of the
    … …  
    913913    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    914914    /// \f$ source \in X \f$ and minimal outgoing capacity).
     915    /// It updates the stored cut if (and only if) the newly found one
     916    /// is better.
    915917    ///
    916918    /// \pre \ref init() must be called before using this function.
    … …  
    925927    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
    926928    /// \f$ source \notin X \f$ and minimal outgoing capacity).
     929    /// It updates the stored cut if (and only if) the newly found one
     930    /// is better.
    927931    ///
    928932    /// \pre \ref init() must be called before using this function.
    … …  
    934938    /// \brief Run the algorithm.
    935939    ///
    936     /// This function runs the algorithm. It finds nodes \c source and
    937     /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
     940    /// This function runs the algorithm. It chooses source node,
     941    /// then calls \ref init(), \ref calculateOut()
    938942    /// and \ref calculateIn().
    939943    void run() {
    … …  
    945949    /// \brief Run the algorithm.
    946950    ///
    947     /// This function runs the algorithm. It uses the given \c source node,
    948     /// finds a proper \c target node and then calls the \ref init(),
    949     /// \ref calculateOut() and \ref calculateIn().
     951    /// This function runs the algorithm. It calls \ref init(),
     952    /// \ref calculateOut() and \ref calculateIn() with the given
     953    /// source node.
    950954    void run(const Node& s) {
    951955      init(s);
    … …  
    966970    /// \brief Return the value of the minimum cut.
    967971    ///
    968     /// This function returns the value of the minimum cut.
     972    /// This function returns the value of the best cut found by the
     973    /// previously called \ref run(), \ref calculateOut() or \ref
     974    /// calculateIn().
    969975    ///
    970976    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    … …  
    977983    /// \brief Return a minimum cut.
    978984    ///
    979     /// This function sets \c cutMap to the characteristic vector of a
    980     /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
    981     /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
     985    /// This function gives the best cut found by the
     986    /// previously called \ref run(), \ref calculateOut() or \ref
     987    /// calculateIn().
     988    ///
     989    /// It sets \c cutMap to the characteristic vector of the found
     990    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
     991    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
    982992    /// for the nodes of \f$ X \f$).
    983993    ///

  • lemon/hartmann_orlin_mmc.h

    r959 r1164  
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref hartmann93finding, \ref dasdan98minmeancycle.
    102102  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103103  /// it applies an efficient early termination scheme.

  • lemon/howard_mmc.h

    r956 r1164  
    9999  /// This class implements Howard's policy iteration algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
    102102  /// This class provides the most efficient algorithm for the
    103103  /// minimum mean cycle problem, though the best known theoretical

  • lemon/karp_mmc.h

    r956 r1164  
    9999  /// This class implements Karp's algorithm for finding a directed
    100100  /// cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref karp78characterization, \ref dasdan98minmeancycle.
    102102  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    103103  ///

  • lemon/kruskal.h

    r631 r1025  
    3131///\file
    3232///\brief Kruskal's algorithm to compute a minimum cost spanning tree
    33 ///
    34 ///Kruskal's algorithm to compute a minimum cost spanning tree.
    35 ///
    3633
    3734namespace lemon {

  • lemon/lemon.pc.in

    r705 r1133  
    1 prefix=@prefix@
    2 exec_prefix=@exec_prefix@
    3 libdir=@libdir@
    4 includedir=@includedir@
     1prefix=@CMAKE_INSTALL_PREFIX@
     2exec_prefix=@CMAKE_INSTALL_PREFIX@/bin
     3libdir=@CMAKE_INSTALL_PREFIX@/lib
     4includedir=@CMAKE_INSTALL_PREFIX@/include
    55
    6 Name: @PACKAGE_NAME@
     6Name: @PROJECT_NAME@
    77Description: Library for Efficient Modeling and Optimization in Networks
    8 Version: @PACKAGE_VERSION@
     8Version: @PROJECT_VERSION@
    99Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
    1010Cflags: -I${includedir}

  • lemon/network_simplex.h

    r978 r1166  
    4848  /// flow problem.
    4949  ///
    50   /// In general, %NetworkSimplex is the fastest implementation available
    51   /// in LEMON for this problem.
    52   /// Moreover, it supports both directions of the supply/demand inequality
    53   /// constraints. For more information, see \ref SupplyType.
     50  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     51  /// implementations available in LEMON for solving this problem.
     52  /// (For more information, see \ref min_cost_flow_algs "the module page".)
     53  /// Furthermore, this class supports both directions of the supply/demand
     54  /// inequality constraints. For more information, see \ref SupplyType.
    5455  ///
    5556  /// Most of the parameters of the problem (except for the digraph)
    … …  
    6465  /// algorithm. By default, it is the same as \c V.
    6566  ///
    66   /// \warning Both number types must be signed and all input data must
     67  /// \warning Both \c V and \c C must be signed number types.
     68  /// \warning All input data (capacities, supply values, and costs) must
    6769  /// be integer.
    6870  ///
    … …  
    122124    /// the \ref run() function.
    123125    ///
    124     /// \ref NetworkSimplex provides five different pivot rule
    125     /// implementations that significantly affect the running time
     126    /// \ref NetworkSimplex provides five different implementations for
     127    /// the pivot strategy that significantly affects the running time
    126128    /// of the algorithm.
    127     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128     /// proved to be the most efficient and the most robust on various
    129     /// test inputs.
    130     /// However, another pivot rule can be selected using the \ref run()
    131     /// function with the proper parameter.
     129    /// According to experimental tests conducted on various problem
     130    /// instances, \ref BLOCK_SEARCH "Block Search" and
     131    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
     132    /// to be the most efficient.
     133    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
     134    /// seemed to be slightly more robust, it is used by default.
     135    /// However, another pivot rule can easily be selected using the
     136    /// \ref run() function with the proper parameter.
    132137    enum PivotRule {
    133138
    … …  
    155160      /// The \e Altering \e Candidate \e List pivot rule.
    156161      /// It is a modified version of the Candidate List method.
    157       /// It keeps only the several best eligible arcs from the former
     162      /// It keeps only a few of the best eligible arcs from the former
    158163      /// candidate list and extends this list in every iteration.
    159164      ALTERING_LIST
    … …  
    167172    typedef std::vector<Value> ValueVector;
    168173    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<char> BoolVector;
    170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     174    typedef std::vector<signed char> CharVector;
     175    // Note: vector<signed char> is used instead of vector<ArcState> and
     176    // vector<ArcDirection> for efficiency reasons
    171177
    172178    // State constants for arcs
    … …  
    177183    };
    178184
    179     typedef std::vector<signed char> StateVector;
    180     // Note: vector<signed char> is used instead of vector<ArcState> for
    181     // efficiency reasons
     185    // Direction constants for tree arcs
     186    enum ArcDirection {
     187      DIR_DOWN = -1,
     188      DIR_UP   =  1
     189    };
    182190
    183191  private:
    … …  
    218226    IntVector _succ_num;
    219227    IntVector _last_succ;
     228    CharVector _pred_dir;
     229    CharVector _state;
    220230    IntVector _dirty_revs;
    221     BoolVector _forward;
    222     StateVector _state;
    223231    int _root;
    224232
    225233    // Temporary data used in the current pivot iteration
    226234    int in_arc, join, u_in, v_in, u_out, v_out;
    227     int first, second, right, last;
    228     int stem, par_stem, new_stem;
    229235    Value delta;
    230236
    … …  
    251257      const IntVector  &_target;
    252258      const CostVector &_cost;
    253       const StateVector &_state;
     259      const CharVector &_state;
    254260      const CostVector &_pi;
    255261      int &_in_arc;
    … …  
    303309      const IntVector  &_target;
    304310      const CostVector &_cost;
    305       const StateVector &_state;
     311      const CharVector &_state;
    306312      const CostVector &_pi;
    307313      int &_in_arc;
    … …  
    342348      const IntVector  &_target;
    343349      const CostVector &_cost;
    344       const StateVector &_state;
     350      const CharVector &_state;
    345351      const CostVector &_pi;
    346352      int &_in_arc;
    … …  
    415421      const IntVector  &_target;
    416422      const CostVector &_cost;
    417       const StateVector &_state;
     423      const CharVector &_state;
    418424      const CostVector &_pi;
    419425      int &_in_arc;
    … …  
    518524      const IntVector  &_target;
    519525      const CostVector &_cost;
    520       const StateVector &_state;
     526      const CharVector &_state;
    521527      const CostVector &_pi;
    522528      int &_in_arc;
    … …  
    537543        SortFunc(const CostVector &map) : _map(map) {}
    538544        bool operator()(int left, int right) {
    539           return _map[left] > _map[right];
     545          return _map[left] < _map[right];
    540546        }
    541547      };
    … …  
    555561        const double BLOCK_SIZE_FACTOR = 1.0;
    556562        const int MIN_BLOCK_SIZE = 10;
    557         const double HEAD_LENGTH_FACTOR = 0.1;
     563        const double HEAD_LENGTH_FACTOR = 0.01;
    558564        const int MIN_HEAD_LENGTH = 3;
    559565
    … …  
    571577        // Check the current candidate list
    572578        int e;
     579        Cost c;
    573580        for (int i = 0; i != _curr_length; ++i) {
    574581          e = _candidates[i];
    575           _cand_cost[e] = _state[e] *
    576             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    577           if (_cand_cost[e] >= 0) {
     582          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     583          if (c < 0) {
     584            _cand_cost[e] = c;
     585          } else {
    578586            _candidates[i--] = _candidates[--_curr_length];
    579587          }
    … …  
    585593
    586594        for (e = _next_arc; e != _search_arc_num; ++e) {
    587           _cand_cost[e] = _state[e] *
    588             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    589           if (_cand_cost[e] < 0) {
     595          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     596          if (c < 0) {
     597            _cand_cost[e] = c;
    590598            _candidates[_curr_length++] = e;
    591599          }
    … …  
    597605        }
    598606        for (e = 0; e != _next_arc; ++e) {
    599           _cand_cost[e] = _state[e] *
    600             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    601           if (_cand_cost[e] < 0) {
     607          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     608          if (c < 0) {
     609            _cand_cost[e] = c;
    602610            _candidates[_curr_length++] = e;
    603611          }
    … …  
    612620      search_end:
    613621
    614         // Make heap of the candidate list (approximating a partial sort)
    615         make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    616                    _sort_func );
    617 
    618         // Pop the first element of the heap
     622        // Perform partial sort operation on the candidate list
     623        int new_length = std::min(_head_length + 1, _curr_length);
     624        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
     625                          _candidates.begin() + _curr_length, _sort_func);
     626
     627        // Select the entering arc and remove it from the list
    619628        _in_arc = _candidates[0];
    620629        _next_arc = e;
    621         pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    622                   _sort_func );
    623         _curr_length = std::min(_head_length, _curr_length - 1);
     630        _candidates[0] = _candidates[new_length - 1];
     631        _curr_length = new_length - 1;
    624632        return true;
    625633      }
    … …  
    634642    ///
    635643    /// \param graph The digraph the algorithm runs on.
    636     /// \param arc_mixing Indicate if the arcs have to be stored in a
     644    /// \param arc_mixing Indicate if the arcs will be stored in a
    637645    /// mixed order in the internal data structure.
    638     /// In special cases, it could lead to better overall performance,
    639     /// but it is usually slower. Therefore it is disabled by default.
    640     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
     646    /// In general, it leads to similar performance as using the original
     647    /// arc order, but it makes the algorithm more robust and in special
     648    /// cases, even significantly faster. Therefore, it is enabled by default.
     649    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
    641650      _graph(graph), _node_id(graph), _arc_id(graph),
    642651      _arc_mixing(arc_mixing),
    … …  
    731740    ///
    732741    /// \return <tt>(*this)</tt>
     742    ///
     743    /// \sa supplyType()
    733744    template<typename SupplyMap>
    734745    NetworkSimplex& supplyMap(const SupplyMap& map) {
    … …  
    747758    ///
    748759    /// Using this function has the same effect as using \ref supplyMap()
    749     /// with such a map in which \c k is assigned to \c s, \c -k is
     760    /// with a map in which \c k is assigned to \c s, \c -k is
    750761    /// assigned to \c t and all other nodes have zero supply value.
    751762    ///
    … …  
    914925      _parent.resize(all_node_num);
    915926      _pred.resize(all_node_num);
    916       _forward.resize(all_node_num);
     927      _pred_dir.resize(all_node_num);
    917928      _thread.resize(all_node_num);
    918929      _rev_thread.resize(all_node_num);
    … …  
    928939      if (_arc_mixing) {
    929940        // Store the arcs in a mixed order
    930         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     941        const int skip = std::max(_arc_num / _node_num, 3);
    931942        int i = 0, j = 0;
    932943        for (ArcIt a(_graph); a != INVALID; ++a) {
    … …  
    934945          _source[i] = _node_id[_graph.source(a)];
    935946          _target[i] = _node_id[_graph.target(a)];
    936           if ((i += k) >= _arc_num) i = ++j;
     947          if ((i += skip) >= _arc_num) i = ++j;
    937948        }
    938949      } else {
    … …  
    10001011    }
    10011012
    1002     /// \brief Return the flow map (the primal solution).
     1013    /// \brief Copy the flow values (the primal solution) into the
     1014    /// given map.
    10031015    ///
    10041016    /// This function copies the flow value on each arc into the given
    … …  
    10241036    }
    10251037
    1026     /// \brief Return the potential map (the dual solution).
     1038    /// \brief Copy the potential values (the dual solution) into the
     1039    /// given map.
    10271040    ///
    10281041    /// This function copies the potential (dual value) of each node
    … …  
    11171130          _state[e] = STATE_TREE;
    11181131          if (_supply[u] >= 0) {
    1119             _forward[u] = true;
     1132            _pred_dir[u] = DIR_UP;
    11201133            _pi[u] = 0;
    11211134            _source[e] = u;
    … …  
    11241137            _cost[e] = 0;
    11251138          } else {
    1126             _forward[u] = false;
     1139            _pred_dir[u] = DIR_DOWN;
    11271140            _pi[u] = ART_COST;
    11281141            _source[e] = _root;
    … …  
    11441157          _last_succ[u] = u;
    11451158          if (_supply[u] >= 0) {
    1146             _forward[u] = true;
     1159            _pred_dir[u] = DIR_UP;
    11471160            _pi[u] = 0;
    11481161            _pred[u] = e;
    … …  
    11541167            _state[e] = STATE_TREE;
    11551168          } else {
    1156             _forward[u] = false;
     1169            _pred_dir[u] = DIR_DOWN;
    11571170            _pi[u] = ART_COST;
    11581171            _pred[u] = f;
    … …  
    11851198          _last_succ[u] = u;
    11861199          if (_supply[u] <= 0) {
    1187             _forward[u] = false;
     1200            _pred_dir[u] = DIR_DOWN;
    11881201            _pi[u] = 0;
    11891202            _pred[u] = e;
    … …  
    11951208            _state[e] = STATE_TREE;
    11961209          } else {
    1197             _forward[u] = true;
     1210            _pred_dir[u] = DIR_UP;
    11981211            _pi[u] = -ART_COST;
    11991212            _pred[u] = f;
    … …  
    12381251      // Initialize first and second nodes according to the direction
    12391252      // of the cycle
     1253      int first, second;
    12401254      if (_state[in_arc] == STATE_LOWER) {
    12411255        first  = _source[in_arc];
    … …  
    12471261      delta = _cap[in_arc];
    12481262      int result = 0;
    1249       Value d;
     1263      Value c, d;
    12501264      int e;
    12511265
    1252       // Search the cycle along the path form the first node to the root
     1266      // Search the cycle form the first node to the join node
    12531267      for (int u = first; u != join; u = _parent[u]) {
    12541268        e = _pred[u];
    1255         d = _forward[u] ?
    1256           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1269        d = _flow[e];
     1270        if (_pred_dir[u] == DIR_DOWN) {
     1271          c = _cap[e];
     1272          d = c >= MAX ? INF : c - d;
     1273        }
    12571274        if (d < delta) {
    12581275          delta = d;
    … …  
    12611278        }
    12621279      }
    1263       // Search the cycle along the path form the second node to the root
     1280
     1281      // Search the cycle form the second node to the join node
    12641282      for (int u = second; u != join; u = _parent[u]) {
    12651283        e = _pred[u];
    1266         d = _forward[u] ?
    1267           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1284        d = _flow[e];
     1285        if (_pred_dir[u] == DIR_UP) {
     1286          c = _cap[e];
     1287          d = c >= MAX ? INF : c - d;
     1288        }
    12681289        if (d <= delta) {
    12691290          delta = d;
    … …  
    12901311        _flow[in_arc] += val;
    12911312        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1292           _flow[_pred[u]] += _forward[u] ? -val : val;
     1313          _flow[_pred[u]] -= _pred_dir[u] * val;
    12931314        }
    12941315        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1295           _flow[_pred[u]] += _forward[u] ? val : -val;
     1316          _flow[_pred[u]] += _pred_dir[u] * val;
    12961317        }
    12971318      }
    … …  
    13081329    // Update the tree structure
    13091330    void updateTreeStructure() {
    1310       int u, w;
    13111331      int old_rev_thread = _rev_thread[u_out];
    13121332      int old_succ_num = _succ_num[u_out];
    … …  
    13141334      v_out = _parent[u_out];
    13151335
    1316       u = _last_succ[u_in];  // the last successor of u_in
    1317       right = _thread[u];    // the node after it
    1318 
    1319       // Handle the case when old_rev_thread equals to v_in
    1320       // (it also means that join and v_out coincide)
    1321       if (old_rev_thread == v_in) {
    1322         last = _thread[_last_succ[u_out]];
     1336      // Check if u_in and u_out coincide
     1337      if (u_in == u_out) {
     1338        // Update _parent, _pred, _pred_dir
     1339        _parent[u_in] = v_in;
     1340        _pred[u_in] = in_arc;
     1341        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1342
     1343        // Update _thread and _rev_thread
     1344        if (_thread[v_in] != u_out) {
     1345          int after = _thread[old_last_succ];
     1346          _thread[old_rev_thread] = after;
     1347          _rev_thread[after] = old_rev_thread;
     1348          after = _thread[v_in];
     1349          _thread[v_in] = u_out;
     1350          _rev_thread[u_out] = v_in;
     1351          _thread[old_last_succ] = after;
     1352          _rev_thread[after] = old_last_succ;
     1353        }
    13231354      } else {
    1324         last = _thread[v_in];
    1325       }
    1326 
    1327       // Update _thread and _parent along the stem nodes (i.e. the nodes
    1328       // between u_in and u_out, whose parent have to be changed)
    1329       _thread[v_in] = stem = u_in;
    1330       _dirty_revs.clear();
    1331       _dirty_revs.push_back(v_in);
    1332       par_stem = v_in;
    1333       while (stem != u_out) {
    1334         // Insert the next stem node into the thread list
    1335         new_stem = _parent[stem];
    1336         _thread[u] = new_stem;
    1337         _dirty_revs.push_back(u);
    1338 
    1339         // Remove the subtree of stem from the thread list
    1340         w = _rev_thread[stem];
    1341         _thread[w] = right;
    1342         _rev_thread[right] = w;
    1343 
    1344         // Change the parent node and shift stem nodes
    1345         _parent[stem] = par_stem;
    1346         par_stem = stem;
    1347         stem = new_stem;
    1348 
    1349         // Update u and right
    1350         u = _last_succ[stem] == _last_succ[par_stem] ?
    1351           _rev_thread[par_stem] : _last_succ[stem];
    1352         right = _thread[u];
    1353       }
    1354       _parent[u_out] = par_stem;
    1355       _thread[u] = last;
    1356       _rev_thread[last] = u;
    1357       _last_succ[u_out] = u;
    1358 
    1359       // Remove the subtree of u_out from the thread list except for
    1360       // the case when old_rev_thread equals to v_in
    1361       // (it also means that join and v_out coincide)
    1362       if (old_rev_thread != v_in) {
    1363         _thread[old_rev_thread] = right;
    1364         _rev_thread[right] = old_rev_thread;
    1365       }
    1366 
    1367       // Update _rev_thread using the new _thread values
    1368       for (int i = 0; i != int(_dirty_revs.size()); ++i) {
    1369         u = _dirty_revs[i];
    1370         _rev_thread[_thread[u]] = u;
    1371       }
    1372 
    1373       // Update _pred, _forward, _last_succ and _succ_num for the
    1374       // stem nodes from u_out to u_in
    1375       int tmp_sc = 0, tmp_ls = _last_succ[u_out];
    1376       u = u_out;
    1377       while (u != u_in) {
    1378         w = _parent[u];
    1379         _pred[u] = _pred[w];
    1380         _forward[u] = !_forward[w];
    1381         tmp_sc += _succ_num[u] - _succ_num[w];
    1382         _succ_num[u] = tmp_sc;
    1383         _last_succ[w] = tmp_ls;
    1384         u = w;
    1385       }
    1386       _pred[u_in] = in_arc;
    1387       _forward[u_in] = (u_in == _source[in_arc]);
    1388       _succ_num[u_in] = old_succ_num;
    1389 
    1390       // Set limits for updating _last_succ form v_in and v_out
    1391       // towards the root
    1392       int up_limit_in = -1;
    1393       int up_limit_out = -1;
    1394       if (_last_succ[join] == v_in) {
    1395         up_limit_out = join;
    1396       } else {
    1397         up_limit_in = join;
     1355        // Handle the case when old_rev_thread equals to v_in
     1356        // (it also means that join and v_out coincide)
     1357        int thread_continue = old_rev_thread == v_in ?
     1358          _thread[old_last_succ] : _thread[v_in];
     1359
     1360        // Update _thread and _parent along the stem nodes (i.e. the nodes
     1361        // between u_in and u_out, whose parent have to be changed)
     1362        int stem = u_in;              // the current stem node
     1363        int par_stem = v_in;          // the new parent of stem
     1364        int next_stem;                // the next stem node
     1365        int last = _last_succ[u_in];  // the last successor of stem
     1366        int before, after = _thread[last];
     1367        _thread[v_in] = u_in;
     1368        _dirty_revs.clear();
     1369        _dirty_revs.push_back(v_in);
     1370        while (stem != u_out) {
     1371          // Insert the next stem node into the thread list
     1372          next_stem = _parent[stem];
     1373          _thread[last] = next_stem;
     1374          _dirty_revs.push_back(last);
     1375
     1376          // Remove the subtree of stem from the thread list
     1377          before = _rev_thread[stem];
     1378          _thread[before] = after;
     1379          _rev_thread[after] = before;
     1380
     1381          // Change the parent node and shift stem nodes
     1382          _parent[stem] = par_stem;
     1383          par_stem = stem;
     1384          stem = next_stem;
     1385
     1386          // Update last and after
     1387          last = _last_succ[stem] == _last_succ[par_stem] ?
     1388            _rev_thread[par_stem] : _last_succ[stem];
     1389          after = _thread[last];
     1390        }
     1391        _parent[u_out] = par_stem;
     1392        _thread[last] = thread_continue;
     1393        _rev_thread[thread_continue] = last;
     1394        _last_succ[u_out] = last;
     1395
     1396        // Remove the subtree of u_out from the thread list except for
     1397        // the case when old_rev_thread equals to v_in
     1398        if (old_rev_thread != v_in) {
     1399          _thread[old_rev_thread] = after;
     1400          _rev_thread[after] = old_rev_thread;
     1401        }
     1402
     1403        // Update _rev_thread using the new _thread values
     1404        for (int i = 0; i != int(_dirty_revs.size()); ++i) {
     1405          int u = _dirty_revs[i];
     1406          _rev_thread[_thread[u]] = u;
     1407        }
     1408
     1409        // Update _pred, _pred_dir, _last_succ and _succ_num for the
     1410        // stem nodes from u_out to u_in
     1411        int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1412        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
     1413          _pred[u] = _pred[p];
     1414          _pred_dir[u] = -_pred_dir[p];
     1415          tmp_sc += _succ_num[u] - _succ_num[p];
     1416          _succ_num[u] = tmp_sc;
     1417          _last_succ[p] = tmp_ls;
     1418        }
     1419        _pred[u_in] = in_arc;
     1420        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1421        _succ_num[u_in] = old_succ_num;
    13981422      }
    13991423
    14001424      // Update _last_succ from v_in towards the root
    1401       for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;
    1402            u = _parent[u]) {
    1403         _last_succ[u] = _last_succ[u_out];
    1404       }
     1425      int up_limit_out = _last_succ[join] == v_in ? join : -1;
     1426      int last_succ_out = _last_succ[u_out];
     1427      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
     1428        _last_succ[u] = last_succ_out;
     1429      }
     1430
    14051431      // Update _last_succ from v_out towards the root
    14061432      if (join != old_rev_thread && v_in != old_rev_thread) {
    1407         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1433        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14081434             u = _parent[u]) {
    14091435          _last_succ[u] = old_rev_thread;
    14101436        }
    1411       } else {
    1412         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1437      }
     1438      else if (last_succ_out != old_last_succ) {
     1439        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14131440             u = _parent[u]) {
    1414           _last_succ[u] = _last_succ[u_out];
     1441          _last_succ[u] = last_succ_out;
    14151442        }
    14161443      }
    14171444
    14181445      // Update _succ_num from v_in to join
    1419       for (u = v_in; u != join; u = _parent[u]) {
     1446      for (int u = v_in; u != join; u = _parent[u]) {
    14201447        _succ_num[u] += old_succ_num;
    14211448      }
    14221449      // Update _succ_num from v_out to join
    1423       for (u = v_out; u != join; u = _parent[u]) {
     1450      for (int u = v_out; u != join; u = _parent[u]) {
    14241451        _succ_num[u] -= old_succ_num;
    14251452      }
    14261453    }
    14271454
    1428     // Update potentials
     1455    // Update potentials in the subtree that has been moved
    14291456    void updatePotential() {
    1430       Cost sigma = _forward[u_in] ?
    1431         _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    1432         _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];
    1433       // Update potentials in the subtree, which has been moved
     1457      Cost sigma = _pi[v_in] - _pi[u_in] -
     1458                   _pred_dir[u_in] * _cost[in_arc];
    14341459      int end = _thread[_last_succ[u_in]];
    14351460      for (int u = u_in; u != end; u = _thread[u]) {

  • lemon/path.h

    r1146 r1162  
    4444  ///
    4545  /// In a sense, the path can be treated as a list of arcs. The
    46   /// lemon path type stores just this list. As a consequence, it
     46  /// LEMON path type stores just this list. As a consequence, it
    4747  /// cannot enumerate the nodes of the path and the source node of
    4848  /// a zero length path is undefined.
    … …  
    149149    void clear() { head.clear(); tail.clear(); }
    150150
    151     /// \brief The nth arc.
     151    /// \brief The n-th arc.
    152152    ///
    153153    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    157157    }
    158158
    159     /// \brief Initialize arc iterator to point to the nth arc
     159    /// \brief Initialize arc iterator to point to the n-th arc
    160160    ///
    161161    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    245245  ///
    246246  /// In a sense, the path can be treated as a list of arcs. The
    247   /// lemon path type stores just this list. As a consequence it
     247  /// LEMON path type stores just this list. As a consequence it
    248248  /// cannot enumerate the nodes in the path and the zero length paths
    249249  /// cannot store the source.
    … …  
    354354    void clear() { data.clear(); }
    355355
    356     /// \brief The nth arc.
     356    /// \brief The n-th arc.
    357357    ///
    358358    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    361361    }
    362362
    363     /// \brief  Initializes arc iterator to point to the nth arc.
     363    /// \brief  Initializes arc iterator to point to the n-th arc.
    364364    ArcIt nthIt(int n) const {
    365365      return ArcIt(*this, n);
    … …  
    422422  ///
    423423  /// In a sense, the path can be treated as a list of arcs. The
    424   /// lemon path type stores just this list. As a consequence it
     424  /// LEMON path type stores just this list. As a consequence it
    425425  /// cannot enumerate the nodes in the path and the zero length paths
    426426  /// cannot store the source.
    … …  
    544544    };
    545545
    546     /// \brief The nth arc.
    547     ///
    548     /// This function looks for the nth arc in O(n) time.
     546    /// \brief The n-th arc.
     547    ///
     548    /// This function looks for the n-th arc in O(n) time.
    549549    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    550550    const Arc& nth(int n) const {
    … …  
    556556    }
    557557
    558     /// \brief Initializes arc iterator to point to the nth arc.
     558    /// \brief Initializes arc iterator to point to the n-th arc.
    559559    ArcIt nthIt(int n) const {
    560560      Node *node = first;
    … …  
    775775  ///
    776776  /// In a sense, the path can be treated as a list of arcs. The
    777   /// lemon path type stores just this list. As a consequence it
     777  /// LEMON path type stores just this list. As a consequence it
    778778  /// cannot enumerate the nodes in the path and the source node of
    779779  /// a zero length path is undefined.
    … …  
    884884    };
    885885
    886     /// \brief The nth arc.
     886    /// \brief The n-th arc.
    887887    ///
    888888    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    891891    }
    892892
    893     /// \brief The arc iterator pointing to the nth arc.
     893    /// \brief The arc iterator pointing to the n-th arc.
    894894    ArcIt nthIt(int n) const {
    895895      return ArcIt(*this, n);
    … …  
    10951095  ///
    10961096  /// In a sense, the path can be treated as a list of arcs. The
    1097   /// lemon path type stores only this list. As a consequence, it
     1097  /// LEMON path type stores only this list. As a consequence, it
    10981098  /// cannot enumerate the nodes in the path and the zero length paths
    10991099  /// cannot have a source node.

  • test/CMakeLists.txt

    r1159 r1162  
    3838  maps_test
    3939  matching_test
     40  max_cardinality_search_test
     41  max_clique_test
    4042  min_cost_arborescence_test
    4143  min_cost_flow_test
    4244  min_mean_cycle_test
     45  nagamochi_ibaraki_test
    4346  path_test
    4447  planarity_test

  • test/graph_copy_test.cc

    r984 r989  
    1919#include <lemon/smart_graph.h>
    2020#include <lemon/list_graph.h>
     21#include <lemon/static_graph.h>
    2122#include <lemon/lgf_reader.h>
    2223#include <lemon/error.h>
    … …  
    2728using namespace lemon;
    2829
     30template <typename GR>
    2931void digraph_copy_test() {
    3032  const int nn = 10;
    … …  
    5254    }
    5355  }
    54 
     56 
    5557  // Test digraph copy
    56   ListDigraph to;
    57   ListDigraph::NodeMap<int> tnm(to);
    58   ListDigraph::ArcMap<int> tam(to);
    59   ListDigraph::Node tn;
    60   ListDigraph::Arc ta;
    61 
    62   SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
    63   SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
    64 
    65   ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
    66   ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
     58  GR to;
     59  typename GR::template NodeMap<int> tnm(to);
     60  typename GR::template ArcMap<int> tam(to);
     61  typename GR::Node tn;
     62  typename GR::Arc ta;
     63
     64  SmartDigraph::NodeMap<typename GR::Node> nr(from);
     65  SmartDigraph::ArcMap<typename GR::Arc> er(from);
     66
     67  typename GR::template NodeMap<SmartDigraph::Node> ncr(to);
     68  typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);
    6769
    6870  digraphCopy(from, to).
    … …  
    8789  }
    8890
    89   for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
     91  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
    9092    check(nr[ncr[it]] == it, "Wrong copy.");
    9193  }
    9294
    93   for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
     95  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
    9496    check(er[ecr[it]] == it, "Wrong copy.");
    9597  }
    … …  
    104106}
    105107
     108template <typename GR>
    106109void graph_copy_test() {
    107110  const int nn = 10;
    … …  
    136139
    137140  // Test graph copy
    138   ListGraph to;
    139   ListGraph::NodeMap<int> tnm(to);
    140   ListGraph::ArcMap<int> tam(to);
    141   ListGraph::EdgeMap<int> tem(to);
    142   ListGraph::Node tn;
    143   ListGraph::Arc ta;
    144   ListGraph::Edge te;
    145 
    146   SmartGraph::NodeMap<ListGraph::Node> nr(from);
    147   SmartGraph::ArcMap<ListGraph::Arc> ar(from);
    148   SmartGraph::EdgeMap<ListGraph::Edge> er(from);
    149 
    150   ListGraph::NodeMap<SmartGraph::Node> ncr(to);
    151   ListGraph::ArcMap<SmartGraph::Arc> acr(to);
    152   ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
     141  GR to;
     142  typename GR::template NodeMap<int> tnm(to);
     143  typename GR::template ArcMap<int> tam(to);
     144  typename GR::template EdgeMap<int> tem(to);
     145  typename GR::Node tn;
     146  typename GR::Arc ta;
     147  typename GR::Edge te;
     148
     149  SmartGraph::NodeMap<typename GR::Node> nr(from);
     150  SmartGraph::ArcMap<typename GR::Arc> ar(from);
     151  SmartGraph::EdgeMap<typename GR::Edge> er(from);
     152
     153  typename GR::template NodeMap<SmartGraph::Node> ncr(to);
     154  typename GR::template ArcMap<SmartGraph::Arc> acr(to);
     155  typename GR::template EdgeMap<SmartGraph::Edge> ecr(to);
    153156
    154157  graphCopy(from, to).
    … …  
    185188  }
    186189
    187   for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
     190  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
    188191    check(nr[ncr[it]] == it, "Wrong copy.");
    189192  }
    190193
    191   for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
     194  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
    192195    check(ar[acr[it]] == it, "Wrong copy.");
    193196  }
    194   for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
     197  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
    195198    check(er[ecr[it]] == it, "Wrong copy.");
    196199  }
    … …  
    209212
    210213int main() {
    211   digraph_copy_test();
    212   graph_copy_test();
     214  digraph_copy_test<SmartDigraph>();
     215  digraph_copy_test<ListDigraph>();
     216  digraph_copy_test<StaticDigraph>();
     217  graph_copy_test<SmartGraph>();
     218  graph_copy_test<ListGraph>();
    213219
    214220  return 0;
Note: See TracChangeset for help on using the changeset viewer.