COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [999:00f8d9f9920d:1000:404b98971e1f] in lemon-main


Ignore:
Files:
8 added
17 deleted
28 edited

Legend:

Unmodified
Added
Removed

  • AUTHORS

    r951 r992  
    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

    r998 r1000  
    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

    r824 r992  
    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

    r879 r992  
    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

    r678 r983  
    1 SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
     1SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")

  • doc/CMakeLists.txt

    r964 r983  
    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

    r964 r966  
    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

    r440 r919  
    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

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

    r879 r919  
    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, but the other two algorithms could be faster in special cases.
    411411For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     412\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
    413413*/
    414414
    … …  
    472472  \ref dasdan98minmeancycle.
    473473
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     474In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475475most efficient one, though the best known theoretical bound on its running
    476476time is exponential.
    … …  
    540540
    541541/**
    542 @defgroup planar Planarity Embedding and Drawing
     542@defgroup planar Planar Embedding and Drawing
    543543@ingroup algs
    544544\brief Algorithms for planarity checking, embedding and drawing
    … …  
    552552
    553553/**
    554 @defgroup approx Approximation Algorithms
     554@defgroup approx_algs Approximation Algorithms
    555555@ingroup algs
    556556\brief Approximation algorithms.
    … …  
    558558This group contains the approximation and heuristic algorithms
    559559implemented in LEMON.
     560
     561<b>Maximum Clique Problem</b>
     562  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     563    Grosso, Locatelli, and Pullan.
    560564*/
    561565

  • doc/references.bib

    r755 r904  
    298298  address =      {Dublin, Ireland},
    299299  year =         1991,
    300   month =        sep,
    301 }
     300  month =        sep
     301}
     302
     303%%%%% Other algorithms %%%%%
     304
     305@article{grosso08maxclique,
     306  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
     307  title =        {Simple ingredients leading to very efficient
     308                  heuristics for the maximum clique problem},
     309  journal =      {Journal of Heuristics},
     310  year =         2008,
     311  volume =       14,
     312  number =       6,
     313  pages =        {587--612}
     314}

  • lemon/CMakeLists.txt

    r968 r981  
    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

    r440 r979  
    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

    r941 r979  
    131131#endif
    132132    }
     133
     134    WinLock::WinLock() {
     135#ifdef WIN32
     136      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
     137      InitializeCriticalSection(lock);
     138      _repr = lock;
     139#endif
     140    }
     141   
     142    WinLock::~WinLock() {
     143#ifdef WIN32
     144      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     145      DeleteCriticalSection(lock);
     146      delete lock;
     147#endif
     148    }
     149
     150    void WinLock::lock() {
     151#ifdef WIN32
     152      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     153      EnterCriticalSection(lock);
     154#endif
     155    }
     156
     157    void WinLock::unlock() {
     158#ifdef WIN32
     159      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     160      LeaveCriticalSection(lock);
     161#endif
     162    }
    133163  }
    134164}

  • lemon/bits/windows.h

    r529 r979  
    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

    r877 r985  
    8787  /// consider to use the named template parameters instead.
    8888  ///
    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.
     89  /// \warning Both \c V and \c C must be signed number types.
     90  /// \warning Capacity bounds and supply values must be integer, but
     91  /// arc costs can be arbitrary real numbers.
     92  /// \warning This algorithm does not support negative costs for
     93  /// arcs having infinite upper bound.
    9394#ifdef DOXYGEN
    9495  template <typename GR, typename V, typename C, typename TR>
    … …  
    423424    ///
    424425    /// 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
     426    /// with a map in which \c k is assigned to \c s, \c -k is
    426427    /// assigned to \c t and all other nodes have zero supply value.
    427428    ///

  • lemon/config.h.in

    r678 r981  
    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

    r998 r1000  
    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

    r931 r938  
    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 this problem.
     102  ///
    100103  /// Most of the parameters of the problem (except for the digraph)
    101104  /// can be given using separate functions, and the algorithm can be
    … …  
    114117  /// consider to use the named template parameters instead.
    115118  ///
    116   /// \warning Both number types must be signed and all input data must
     119  /// \warning Both \c V and \c C must be signed number types.
     120  /// \warning All input data (capacities, supply values, and costs) must
    117121  /// be integer.
    118   /// \warning This algorithm does not support negative costs for such
    119   /// arcs that have infinite upper bound.
     122  /// \warning This algorithm does not support negative costs for
     123  /// arcs having infinite upper bound.
    120124  ///
    121125  /// \note %CostScaling provides three different internal methods,
    … …  
    179183    /// relabel operation.
    180184    /// By default, the so called \ref PARTIAL_AUGMENT
    181     /// "Partial Augment-Relabel" method is used, which proved to be
     185    /// "Partial Augment-Relabel" method is used, which turned out to be
    182186    /// the most efficient and the most robust on various test inputs.
    183187    /// However, the other methods can be selected using the \ref run()
    … …  
    234238    };
    235239
    236     typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    237240    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    238241
    … …  
    285288    int _max_rank;
    286289
    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 
    295290  public:
    296291
    … …  
    339334    CostScaling(const GR& graph) :
    340335      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
    341       _cost_map(_cost_vec), _pi_map(_pi),
    342336      INF(std::numeric_limits<Value>::has_infinity ?
    343337          std::numeric_limits<Value>::infinity() :
    … …  
    448442    ///
    449443    /// 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
     444    /// with a map in which \c k is assigned to \c s, \c -k is
    451445    /// assigned to \c t and all other nodes have zero supply value.
    452446    ///
    … …  
    494488    /// \param method The internal method that will be used in the
    495489    /// algorithm. For more information, see \ref Method.
    496     /// \param factor The cost scaling factor. It must be larger than one.
     490    /// \param factor The cost scaling factor. It must be at least two.
    497491    ///
    498492    /// \return \c INFEASIBLE if no feasible flow exists,
    … …  
    508502    /// \see ProblemType, Method
    509503    /// \see resetParams(), reset()
    510     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     504    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
     505      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
    511506      _alpha = factor;
    512507      ProblemType pt = init();
    … …  
    572567    }
    573568
    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.
     569    /// \brief Reset the internal data structures and all the parameters
     570    /// that have been given before.
     571    ///
     572    /// This function resets the internal data structures and all the
     573    /// paramaters that have been given before using functions \ref lowerMap(),
     574    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     575    ///
     576    /// It is useful for multiple \ref run() calls. By default, all the given
     577    /// parameters are kept for the next \ref run() call, unless
     578    /// \ref resetParams() or \ref reset() is used.
     579    /// If the underlying digraph was also modified after the construction
     580    /// of the class or the last \ref reset() call, then the \ref reset()
     581    /// function must be used, otherwise \ref resetParams() is sufficient.
     582    ///
     583    /// See \ref resetParams() for examples.
     584    ///
    585585    /// \return <tt>(*this)</tt>
     586    ///
     587    /// \see resetParams(), run()
    586588    CostScaling& reset() {
    587589      // Resize vectors
    … …  
    608610      _excess.resize(_res_node_num);
    609611      _next_out.resize(_res_node_num);
    610 
    611       _arc_vec.reserve(_res_arc_num);
    612       _cost_vec.reserve(_res_arc_num);
    613612
    614613      // Copy the graph
    … …  
    887886      }
    888887
    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 
    897888      // Initialize data structures for buckets
    898889      _max_rank = _alpha * _res_node_num;
    … …  
    902893      _rank.resize(_res_node_num + 1);
    903894
    904       // Execute the algorithm
     895      return OPTIMAL;
     896    }
     897
     898    // Execute the algorithm and transform the results
     899    void start(Method method) {
     900      const int MAX_PARTIAL_PATH_LENGTH = 4;
     901
    905902      switch (method) {
    906903        case PUSH:
    … …  
    911908          break;
    912909        case PARTIAL_AUGMENT:
    913           startAugment(MAX_PATH_LENGTH);
     910          startAugment(MAX_PARTIAL_PATH_LENGTH);
    914911          break;
    915912      }
    916913
    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();
     914      // Compute node potentials (dual solution)
     915      for (int i = 0; i != _res_node_num; ++i) {
     916        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
     917      }
     918      bool optimal = true;
     919      for (int i = 0; optimal && i != _res_node_num; ++i) {
     920        LargeCost pi_i = _pi[i];
     921        int last_out = _first_out[i+1];
     922        for (int j = _first_out[i]; j != last_out; ++j) {
     923          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
     924            optimal = false;
     925            break;
     926          }
     927        }
     928      }
     929
     930      if (!optimal) {
     931        // Compute node potentials for the original costs with BellmanFord
     932        // (if it is necessary)
     933        typedef std::pair<int, int> IntPair;
     934        StaticDigraph sgr;
     935        std::vector<IntPair> arc_vec;
     936        std::vector<LargeCost> cost_vec;
     937        LargeCostArcMap cost_map(cost_vec);
     938
     939        arc_vec.clear();
     940        cost_vec.clear();
     941        for (int j = 0; j != _res_arc_num; ++j) {
     942          if (_res_cap[j] > 0) {
     943            int u = _source[j], v = _target[j];
     944            arc_vec.push_back(IntPair(u, v));
     945            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
     946          }
     947        }
     948        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
     949
     950        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
     951          bf(sgr, cost_map);
     952        bf.init(0);
     953        bf.start();
     954
     955        for (int i = 0; i != _res_node_num; ++i) {
     956          _pi[i] += bf.dist(sgr.node(i));
     957        }
     958      }
     959
     960      // Shift potentials to meet the requirements of the GEQ type
     961      // optimality conditions
     962      LargeCost max_pot = _pi[_root];
     963      for (int i = 0; i != _res_node_num; ++i) {
     964        if (_pi[i] > max_pot) max_pot = _pi[i];
     965      }
     966      if (max_pot != 0) {
     967        for (int i = 0; i != _res_node_num; ++i) {
     968          _pi[i] -= max_pot;
     969        }
     970      }
    933971
    934972      // Handle non-zero lower bounds
    … …  
    948986        LargeCost pi_u = _pi[u];
    949987        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;
     988          Value delta = _res_cap[a];
     989          if (delta > 0) {
     990            int v = _target[a];
     991            if (_cost[a] + pi_u - _pi[v] < 0) {
     992              _excess[u] -= delta;
     993              _excess[v] += delta;
     994              _res_cap[a] = 0;
     995              _res_cap[_reverse[a]] += delta;
     996            }
    957997          }
    958998        }
    … …  
    9701010    }
    9711011
    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;
     1012    // Price (potential) refinement heuristic
     1013    bool priceRefinement() {
     1014
     1015      // Stack for stroing the topological order
     1016      IntVector stack(_res_node_num);
     1017      int stack_top;
     1018
     1019      // Perform phases
     1020      while (topologicalSort(stack, stack_top)) {
     1021
     1022        // Compute node ranks in the acyclic admissible network and
     1023        // store the nodes in buckets
     1024        for (int i = 0; i != _res_node_num; ++i) {
     1025          _rank[i] = 0;
     1026        }
     1027        const int bucket_end = _root + 1;
     1028        for (int r = 0; r != _max_rank; ++r) {
     1029          _buckets[r] = bucket_end;
     1030        }
     1031        int top_rank = 0;
     1032        for ( ; stack_top >= 0; --stack_top) {
     1033          int u = stack[stack_top], v;
     1034          int rank_u = _rank[u];
     1035
     1036          LargeCost rc, pi_u = _pi[u];
     1037          int last_out = _first_out[u+1];
     1038          for (int a = _first_out[u]; a != last_out; ++a) {
     1039            if (_res_cap[a] > 0) {
     1040              v = _target[a];
     1041              rc = _cost[a] + pi_u - _pi[v];
     1042              if (rc < 0) {
     1043                LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
     1044                if (nrc < LargeCost(_max_rank)) {
     1045                  int new_rank_v = rank_u + static_cast<int>(nrc);
     1046                  if (new_rank_v > _rank[v]) {
     1047                    _rank[v] = new_rank_v;
     1048                  }
     1049                }
     1050              }
     1051            }
     1052          }
     1053
     1054          if (rank_u > 0) {
     1055            top_rank = std::max(top_rank, rank_u);
     1056            int bfirst = _buckets[rank_u];
     1057            _bucket_next[u] = bfirst;
     1058            _bucket_prev[bfirst] = u;
     1059            _buckets[rank_u] = u;
     1060          }
     1061        }
     1062
     1063        // Check if the current flow is epsilon-optimal
     1064        if (top_rank == 0) {
     1065          return true;
     1066        }
     1067
     1068        // Process buckets in top-down order
     1069        for (int rank = top_rank; rank > 0; --rank) {
     1070          while (_buckets[rank] != bucket_end) {
     1071            // Remove the first node from the current bucket
     1072            int u = _buckets[rank];
     1073            _buckets[rank] = _bucket_next[u];
     1074
     1075            // Search the outgoing arcs of u
     1076            LargeCost rc, pi_u = _pi[u];
     1077            int last_out = _first_out[u+1];
     1078            int v, old_rank_v, new_rank_v;
     1079            for (int a = _first_out[u]; a != last_out; ++a) {
     1080              if (_res_cap[a] > 0) {
     1081                v = _target[a];
     1082                old_rank_v = _rank[v];
     1083
     1084                if (old_rank_v < rank) {
     1085
     1086                  // Compute the new rank of node v
     1087                  rc = _cost[a] + pi_u - _pi[v];
     1088                  if (rc < 0) {
     1089                    new_rank_v = rank;
     1090                  } else {
     1091                    LargeCost nrc = rc / _epsilon;
     1092                    new_rank_v = 0;
     1093                    if (nrc < LargeCost(_max_rank)) {
     1094                      new_rank_v = rank - 1 - static_cast<int>(nrc);
     1095                    }
     1096                  }
     1097
     1098                  // Change the rank of node v
     1099                  if (new_rank_v > old_rank_v) {
     1100                    _rank[v] = new_rank_v;
     1101
     1102                    // Remove v from its old bucket
     1103                    if (old_rank_v > 0) {
     1104                      if (_buckets[old_rank_v] == v) {
     1105                        _buckets[old_rank_v] = _bucket_next[v];
     1106                      } else {
     1107                        int pv = _bucket_prev[v], nv = _bucket_next[v];
     1108                        _bucket_next[pv] = nv;
     1109                        _bucket_prev[nv] = pv;
     1110                      }
     1111                    }
     1112
     1113                    // Insert v into its new bucket
     1114                    int nv = _buckets[new_rank_v];
     1115                    _bucket_next[v] = nv;
     1116                    _bucket_prev[nv] = v;
     1117                    _buckets[new_rank_v] = v;
     1118                  }
     1119                }
     1120              }
     1121            }
     1122
     1123            // Refine potential of node u
     1124            _pi[u] -= rank * _epsilon;
     1125          }
     1126        }
     1127
     1128      }
     1129
     1130      return false;
     1131    }
     1132
     1133    // Find and cancel cycles in the admissible network and
     1134    // determine topological order using DFS
     1135    bool topologicalSort(IntVector &stack, int &stack_top) {
     1136      const int MAX_CYCLE_CANCEL = 1;
     1137
     1138      BoolVector reached(_res_node_num, false);
     1139      BoolVector processed(_res_node_num, false);
     1140      IntVector pred(_res_node_num);
     1141      for (int i = 0; i != _res_node_num; ++i) {
     1142        _next_out[i] = _first_out[i];
     1143      }
     1144      stack_top = -1;
     1145
     1146      int cycle_cnt = 0;
     1147      for (int start = 0; start != _res_node_num; ++start) {
     1148        if (reached[start]) continue;
     1149
     1150        // Start DFS search from this start node
     1151        pred[start] = -1;
     1152        int tip = start, v;
     1153        while (true) {
     1154          // Check the outgoing arcs of the current tip node
     1155          reached[tip] = true;
     1156          LargeCost pi_tip = _pi[tip];
     1157          int a, last_out = _first_out[tip+1];
     1158          for (a = _next_out[tip]; a != last_out; ++a) {
     1159            if (_res_cap[a] > 0) {
     1160              v = _target[a];
     1161              if (_cost[a] + pi_tip - _pi[v] < 0) {
     1162                if (!reached[v]) {
     1163                  // A new node is reached
     1164                  reached[v] = true;
     1165                  pred[v] = tip;
     1166                  _next_out[tip] = a;
     1167                  tip = v;
     1168                  a = _next_out[tip];
     1169                  last_out = _first_out[tip+1];
     1170                  break;
     1171                }
     1172                else if (!processed[v]) {
     1173                  // A cycle is found
     1174                  ++cycle_cnt;
     1175                  _next_out[tip] = a;
     1176
     1177                  // Find the minimum residual capacity along the cycle
     1178                  Value d, delta = _res_cap[a];
     1179                  int u, delta_node = tip;
     1180                  for (u = tip; u != v; ) {
     1181                    u = pred[u];
     1182                    d = _res_cap[_next_out[u]];
     1183                    if (d <= delta) {
     1184                      delta = d;
     1185                      delta_node = u;
     1186                    }
     1187                  }
     1188
     1189                  // Augment along the cycle
     1190                  _res_cap[a] -= delta;
     1191                  _res_cap[_reverse[a]] += delta;
     1192                  for (u = tip; u != v; ) {
     1193                    u = pred[u];
     1194                    int ca = _next_out[u];
     1195                    _res_cap[ca] -= delta;
     1196                    _res_cap[_reverse[ca]] += delta;
     1197                  }
     1198
     1199                  // Check the maximum number of cycle canceling
     1200                  if (cycle_cnt >= MAX_CYCLE_CANCEL) {
     1201                    return false;
     1202                  }
     1203
     1204                  // Roll back search to delta_node
     1205                  if (delta_node != tip) {
     1206                    for (u = tip; u != delta_node; u = pred[u]) {
     1207                      reached[u] = false;
     1208                    }
     1209                    tip = delta_node;
     1210                    a = _next_out[tip] + 1;
     1211                    last_out = _first_out[tip+1];
     1212                    break;
     1213                  }
     1214                }
     1215              }
     1216            }
     1217          }
     1218
     1219          // Step back to the previous node
     1220          if (a == last_out) {
     1221            processed[tip] = true;
     1222            stack[++stack_top] = tip;
     1223            tip = pred[tip];
     1224            if (tip < 0) {
     1225              // Finish DFS from the current start node
     1226              break;
     1227            }
     1228            ++_next_out[tip];
     1229          }
     1230        }
     1231
     1232      }
     1233
     1234      return (cycle_cnt == 0);
    9961235    }
    9971236
    9981237    // Global potential update heuristic
    9991238    void globalUpdate() {
    1000       int bucket_end = _root + 1;
     1239      const int bucket_end = _root + 1;
    10011240
    10021241      // Initialize buckets
    … …  
    10051244      }
    10061245      Value total_excess = 0;
     1246      int b0 = bucket_end;
    10071247      for (int i = 0; i != _res_node_num; ++i) {
    10081248        if (_excess[i] < 0) {
    10091249          _rank[i] = 0;
    1010           _bucket_next[i] = _buckets[0];
    1011           _bucket_prev[_buckets[0]] = i;
    1012           _buckets[0] = i;
     1250          _bucket_next[i] = b0;
     1251          _bucket_prev[b0] = i;
     1252          b0 = i;
    10131253        } else {
    10141254          total_excess += _excess[i];
    … …  
    10171257      }
    10181258      if (total_excess == 0) return;
     1259      _buckets[0] = b0;
    10191260
    10201261      // Search the buckets
    … …  
    10381279                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
    10391280                int new_rank_v = old_rank_v;
    1040                 if (nrc < LargeCost(_max_rank))
    1041                   new_rank_v = r + 1 + int(nrc);
     1281                if (nrc < LargeCost(_max_rank)) {
     1282                  new_rank_v = r + 1 + static_cast<int>(nrc);
     1283                }
    10421284
    10431285                // Change the rank of v
    … …  
    10511293                      _buckets[old_rank_v] = _bucket_next[v];
    10521294                    } else {
    1053                       _bucket_next[_bucket_prev[v]] = _bucket_next[v];
    1054                       _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1295                      int pv = _bucket_prev[v], nv = _bucket_next[v];
     1296                      _bucket_next[pv] = nv;
     1297                      _bucket_prev[nv] = pv;
    10551298                    }
    10561299                  }
    10571300
    1058                   // Insert v to its new bucket
    1059                   _bucket_next[v] = _buckets[new_rank_v];
    1060                   _bucket_prev[_buckets[new_rank_v]] = v;
     1301                  // Insert v into its new bucket
     1302                  int nv = _buckets[new_rank_v];
     1303                  _bucket_next[v] = nv;
     1304                  _bucket_prev[nv] = v;
    10611305                  _buckets[new_rank_v] = v;
    10621306                }
    … …  
    10871331    void startAugment(int max_length) {
    10881332      // 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 *
     1333      const int PRICE_REFINEMENT_LIMIT = 2;
     1334      const double GLOBAL_UPDATE_FACTOR = 1.0;
     1335      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    10931336        (_res_node_num + _sup_node_num * _sup_node_num));
    1094       int next_update_limit = global_update_freq;
    1095 
     1337      int next_global_update_limit = global_update_skip;
     1338
     1339      // Perform cost scaling phases
     1340      IntVector path;
     1341      BoolVector path_arc(_res_arc_num, false);
    10961342      int relabel_cnt = 0;
    1097 
    1098       // Perform cost scaling phases
    1099       std::vector<int> path;
     1343      int eps_phase_cnt = 0;
    11001344      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    11011345                                        1 : _epsilon / _alpha )
    11021346      {
    1103         // Early termination heuristic
    1104         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1105           if (earlyTermination()) break;
     1347        ++eps_phase_cnt;
     1348
     1349        // Price refinement heuristic
     1350        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1351          if (priceRefinement()) continue;
    11061352        }
    11071353
    … …  
    11201366
    11211367          // Find an augmenting path from the start node
    1122           path.clear();
    11231368          int tip = start;
    1124           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
     1369          while (int(path.size()) < max_length && _excess[tip] >= 0) {
    11251370            int u;
    1126             LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1371            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
     1372            LargeCost pi_tip = _pi[tip];
    11271373            int last_out = _first_out[tip+1];
    11281374            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;
     1375              if (_res_cap[a] > 0) {
     1376                u = _target[a];
     1377                rc = _cost[a] + pi_tip - _pi[u];
     1378                if (rc < 0) {
     1379                  path.push_back(a);
     1380                  _next_out[tip] = a;
     1381                  if (path_arc[a]) {
     1382                    goto augment;   // a cycle is found, stop path search
     1383                  }
     1384                  tip = u;
     1385                  path_arc[a] = true;
     1386                  goto next_step;
     1387                }
     1388                else if (rc < min_red_cost) {
     1389                  min_red_cost = rc;
     1390                }
    11351391              }
    11361392            }
    11371393
    11381394            // Relabel tip node
    1139             min_red_cost = std::numeric_limits<LargeCost>::max();
    11401395            if (tip != start) {
    11411396              int ra = _reverse[path.back()];
    1142               min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1397              min_red_cost =
     1398                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
    11431399            }
     1400            last_out = _next_out[tip];
    11441401            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;
     1402              if (_res_cap[a] > 0) {
     1403                rc = _cost[a] + pi_tip - _pi[_target[a]];
     1404                if (rc < min_red_cost) {
     1405                  min_red_cost = rc;
     1406                }
    11481407              }
    11491408            }
    … …  
    11541413            // Step back
    11551414            if (tip != start) {
    1156               tip = _source[path.back()];
     1415              int pa = path.back();
     1416              path_arc[pa] = false;
     1417              tip = _source[pa];
    11571418              path.pop_back();
    11581419            }
    … …  
    11621423
    11631424          // Augment along the found path (as much flow as possible)
     1425        augment:
    11641426          Value delta;
    11651427          int pa, u, v = start;
    … …  
    11681430            u = v;
    11691431            v = _target[pa];
     1432            path_arc[pa] = false;
    11701433            delta = std::min(_res_cap[pa], _excess[u]);
    11711434            _res_cap[pa] -= delta;
    … …  
    11731436            _excess[u] -= delta;
    11741437            _excess[v] += delta;
    1175             if (_excess[v] > 0 && _excess[v] <= delta)
     1438            if (_excess[v] > 0 && _excess[v] <= delta) {
    11761439              _active_nodes.push_back(v);
    1177           }
     1440            }
     1441          }
     1442          path.clear();
    11781443
    11791444          // Global update heuristic
    1180           if (relabel_cnt >= next_update_limit) {
     1445          if (relabel_cnt >= next_global_update_limit) {
    11811446            globalUpdate();
    1182             next_update_limit += global_update_freq;
    1183           }
    1184         }
    1185       }
     1447            next_global_update_limit += global_update_skip;
     1448          }
     1449        }
     1450
     1451      }
     1452
    11861453    }
    11871454
    … …  
    11891456    void startPush() {
    11901457      // Paramters for heuristics
    1191       const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1458      const int PRICE_REFINEMENT_LIMIT = 2;
    11921459      const double GLOBAL_UPDATE_FACTOR = 2.0;
    11931460
    1194       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1461      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    11951462        (_res_node_num + _sup_node_num * _sup_node_num));
    1196       int next_update_limit = global_update_freq;
    1197 
    1198       int relabel_cnt = 0;
     1463      int next_global_update_limit = global_update_skip;
    11991464
    12001465      // Perform cost scaling phases
    12011466      BoolVector hyper(_res_node_num, false);
    12021467      LargeCostVector hyper_cost(_res_node_num);
     1468      int relabel_cnt = 0;
     1469      int eps_phase_cnt = 0;
    12031470      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    12041471                                        1 : _epsilon / _alpha )
    12051472      {
    1206         // Early termination heuristic
    1207         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1208           if (earlyTermination()) break;
     1473        ++eps_phase_cnt;
     1474
     1475        // Price refinement heuristic
     1476        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1477          if (priceRefinement()) continue;
    12091478        }
    12101479
    … …  
    12781547               std::numeric_limits<LargeCost>::max();
    12791548            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;
     1549              if (_res_cap[a] > 0) {
     1550                rc = _cost[a] + pi_n - _pi[_target[a]];
     1551                if (rc < min_red_cost) {
     1552                  min_red_cost = rc;
     1553                }
    12831554              }
    12841555            }
    … …  
    12981569
    12991570          // Global update heuristic
    1300           if (relabel_cnt >= next_update_limit) {
     1571          if (relabel_cnt >= next_global_update_limit) {
    13011572            globalUpdate();
    13021573            for (int u = 0; u != _res_node_num; ++u)
    13031574              hyper[u] = false;
    1304             next_update_limit += global_update_freq;
     1575            next_global_update_limit += global_update_skip;
    13051576          }
    13061577        }

  • lemon/cycle_canceling.h

    r877 r922  
    6666  /// algorithm. By default, it is the same as \c V.
    6767  ///
    68   /// \warning Both number types must be signed and all input data must
     68  /// \warning Both \c V and \c C must be signed number types.
     69  /// \warning All input data (capacities, supply values, and costs) must
    6970  /// be integer.
    70   /// \warning This algorithm does not support negative costs for such
    71   /// arcs that have infinite upper bound.
     71  /// \warning This algorithm does not support negative costs for
     72  /// arcs having infinite upper bound.
    7273  ///
    7374  /// \note For more information about the three available methods,
    … …  
    117118    /// \ref CycleCanceling provides three different cycle-canceling
    118119    /// 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    /// is used, which is by far the most efficient and the most robust.
    121121    /// However, the other methods can be selected using the \ref run()
    122122    /// function with the proper parameter.
    … …  
    350350    ///
    351351    /// 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
     352    /// with a map in which \c k is assigned to \c s, \c -k is
    353353    /// assigned to \c t and all other nodes have zero supply value.
    354354    ///

  • lemon/euler.h

    r877 r919  
    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

    r877 r915  
    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/kruskal.h

    r584 r921  
    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

    r658 r981  
    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

    r889 r984  
    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 this problem.
     52  /// Furthermore, this class supports both directions of the supply/demand
     53  /// inequality constraints. For more information, see \ref SupplyType.
    5454  ///
    5555  /// Most of the parameters of the problem (except for the digraph)
    … …  
    6464  /// algorithm. By default, it is the same as \c V.
    6565  ///
    66   /// \warning Both number types must be signed and all input data must
     66  /// \warning Both \c V and \c C must be signed number types.
     67  /// \warning All input data (capacities, supply values, and costs) must
    6768  /// be integer.
    6869  ///
    … …  
    122123    /// the \ref run() function.
    123124    ///
    124     /// \ref NetworkSimplex provides five different pivot rule
    125     /// implementations that significantly affect the running time
     125    /// \ref NetworkSimplex provides five different implementations for
     126    /// the pivot strategy that significantly affects the running time
    126127    /// 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.
     128    /// According to experimental tests conducted on various problem
     129    /// instances, \ref BLOCK_SEARCH "Block Search" and
     130    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
     131    /// to be the most efficient.
     132    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
     133    /// seemed to be slightly more robust, it is used by default.
     134    /// However, another pivot rule can easily be selected using the
     135    /// \ref run() function with the proper parameter.
    132136    enum PivotRule {
    133137
    … …  
    155159      /// The \e Altering \e Candidate \e List pivot rule.
    156160      /// It is a modified version of the Candidate List method.
    157       /// It keeps only the several best eligible arcs from the former
     161      /// It keeps only a few of the best eligible arcs from the former
    158162      /// candidate list and extends this list in every iteration.
    159163      ALTERING_LIST
    … …  
    167171    typedef std::vector<Value> ValueVector;
    168172    typedef std::vector<Cost> CostVector;
    169     typedef std::vector<char> BoolVector;
    170     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     173    typedef std::vector<signed char> CharVector;
     174    // Note: vector<signed char> is used instead of vector<ArcState> and
     175    // vector<ArcDirection> for efficiency reasons
    171176
    172177    // State constants for arcs
    … …  
    177182    };
    178183
    179     typedef std::vector<signed char> StateVector;
    180     // Note: vector<signed char> is used instead of vector<ArcState> for
    181     // efficiency reasons
     184    // Direction constants for tree arcs
     185    enum ArcDirection {
     186      DIR_DOWN = -1,
     187      DIR_UP   =  1
     188    };
    182189
    183190  private:
    … …  
    218225    IntVector _succ_num;
    219226    IntVector _last_succ;
     227    CharVector _pred_dir;
     228    CharVector _state;
    220229    IntVector _dirty_revs;
    221     BoolVector _forward;
    222     StateVector _state;
    223230    int _root;
    224231
    225232    // Temporary data used in the current pivot iteration
    226233    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;
    229234    Value delta;
    230235
    … …  
    251256      const IntVector  &_target;
    252257      const CostVector &_cost;
    253       const StateVector &_state;
     258      const CharVector &_state;
    254259      const CostVector &_pi;
    255260      int &_in_arc;
    … …  
    303308      const IntVector  &_target;
    304309      const CostVector &_cost;
    305       const StateVector &_state;
     310      const CharVector &_state;
    306311      const CostVector &_pi;
    307312      int &_in_arc;
    … …  
    342347      const IntVector  &_target;
    343348      const CostVector &_cost;
    344       const StateVector &_state;
     349      const CharVector &_state;
    345350      const CostVector &_pi;
    346351      int &_in_arc;
    … …  
    415420      const IntVector  &_target;
    416421      const CostVector &_cost;
    417       const StateVector &_state;
     422      const CharVector &_state;
    418423      const CostVector &_pi;
    419424      int &_in_arc;
    … …  
    518523      const IntVector  &_target;
    519524      const CostVector &_cost;
    520       const StateVector &_state;
     525      const CharVector &_state;
    521526      const CostVector &_pi;
    522527      int &_in_arc;
    … …  
    537542        SortFunc(const CostVector &map) : _map(map) {}
    538543        bool operator()(int left, int right) {
    539           return _map[left] > _map[right];
     544          return _map[left] < _map[right];
    540545        }
    541546      };
    … …  
    555560        const double BLOCK_SIZE_FACTOR = 1.0;
    556561        const int MIN_BLOCK_SIZE = 10;
    557         const double HEAD_LENGTH_FACTOR = 0.1;
     562        const double HEAD_LENGTH_FACTOR = 0.01;
    558563        const int MIN_HEAD_LENGTH = 3;
    559564
    … …  
    571576        // Check the current candidate list
    572577        int e;
     578        Cost c;
    573579        for (int i = 0; i != _curr_length; ++i) {
    574580          e = _candidates[i];
    575           _cand_cost[e] = _state[e] *
    576             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    577           if (_cand_cost[e] >= 0) {
     581          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     582          if (c < 0) {
     583            _cand_cost[e] = c;
     584          } else {
    578585            _candidates[i--] = _candidates[--_curr_length];
    579586          }
    … …  
    585592
    586593        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) {
     594          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     595          if (c < 0) {
     596            _cand_cost[e] = c;
    590597            _candidates[_curr_length++] = e;
    591598          }
    … …  
    597604        }
    598605        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) {
     606          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     607          if (c < 0) {
     608            _cand_cost[e] = c;
    602609            _candidates[_curr_length++] = e;
    603610          }
    … …  
    612619      search_end:
    613620
    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
     621        // Perform partial sort operation on the candidate list
     622        int new_length = std::min(_head_length + 1, _curr_length);
     623        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
     624                          _candidates.begin() + _curr_length, _sort_func);
     625
     626        // Select the entering arc and remove it from the list
    619627        _in_arc = _candidates[0];
    620628        _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);
     629        _candidates[0] = _candidates[new_length - 1];
     630        _curr_length = new_length - 1;
    624631        return true;
    625632      }
    … …  
    634641    ///
    635642    /// \param graph The digraph the algorithm runs on.
    636     /// \param arc_mixing Indicate if the arcs have to be stored in a
     643    /// \param arc_mixing Indicate if the arcs will be stored in a
    637644    /// 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) :
     645    /// In general, it leads to similar performance as using the original
     646    /// arc order, but it makes the algorithm more robust and in special
     647    /// cases, even significantly faster. Therefore, it is enabled by default.
     648    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
    641649      _graph(graph), _node_id(graph), _arc_id(graph),
    642650      _arc_mixing(arc_mixing),
    … …  
    731739    ///
    732740    /// \return <tt>(*this)</tt>
     741    ///
     742    /// \sa supplyType()
    733743    template<typename SupplyMap>
    734744    NetworkSimplex& supplyMap(const SupplyMap& map) {
    … …  
    747757    ///
    748758    /// 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
     759    /// with a map in which \c k is assigned to \c s, \c -k is
    750760    /// assigned to \c t and all other nodes have zero supply value.
    751761    ///
    … …  
    914924      _parent.resize(all_node_num);
    915925      _pred.resize(all_node_num);
    916       _forward.resize(all_node_num);
     926      _pred_dir.resize(all_node_num);
    917927      _thread.resize(all_node_num);
    918928      _rev_thread.resize(all_node_num);
    … …  
    928938      if (_arc_mixing) {
    929939        // Store the arcs in a mixed order
    930         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     940        const int skip = std::max(_arc_num / _node_num, 3);
    931941        int i = 0, j = 0;
    932942        for (ArcIt a(_graph); a != INVALID; ++a) {
    … …  
    934944          _source[i] = _node_id[_graph.source(a)];
    935945          _target[i] = _node_id[_graph.target(a)];
    936           if ((i += k) >= _arc_num) i = ++j;
     946          if ((i += skip) >= _arc_num) i = ++j;
    937947        }
    938948      } else {
    … …  
    11171127          _state[e] = STATE_TREE;
    11181128          if (_supply[u] >= 0) {
    1119             _forward[u] = true;
     1129            _pred_dir[u] = DIR_UP;
    11201130            _pi[u] = 0;
    11211131            _source[e] = u;
    … …  
    11241134            _cost[e] = 0;
    11251135          } else {
    1126             _forward[u] = false;
     1136            _pred_dir[u] = DIR_DOWN;
    11271137            _pi[u] = ART_COST;
    11281138            _source[e] = _root;
    … …  
    11441154          _last_succ[u] = u;
    11451155          if (_supply[u] >= 0) {
    1146             _forward[u] = true;
     1156            _pred_dir[u] = DIR_UP;
    11471157            _pi[u] = 0;
    11481158            _pred[u] = e;
    … …  
    11541164            _state[e] = STATE_TREE;
    11551165          } else {
    1156             _forward[u] = false;
     1166            _pred_dir[u] = DIR_DOWN;
    11571167            _pi[u] = ART_COST;
    11581168            _pred[u] = f;
    … …  
    11851195          _last_succ[u] = u;
    11861196          if (_supply[u] <= 0) {
    1187             _forward[u] = false;
     1197            _pred_dir[u] = DIR_DOWN;
    11881198            _pi[u] = 0;
    11891199            _pred[u] = e;
    … …  
    11951205            _state[e] = STATE_TREE;
    11961206          } else {
    1197             _forward[u] = true;
     1207            _pred_dir[u] = DIR_UP;
    11981208            _pi[u] = -ART_COST;
    11991209            _pred[u] = f;
    … …  
    12381248      // Initialize first and second nodes according to the direction
    12391249      // of the cycle
     1250      int first, second;
    12401251      if (_state[in_arc] == STATE_LOWER) {
    12411252        first  = _source[in_arc];
    … …  
    12471258      delta = _cap[in_arc];
    12481259      int result = 0;
    1249       Value d;
     1260      Value c, d;
    12501261      int e;
    12511262
    1252       // Search the cycle along the path form the first node to the root
     1263      // Search the cycle form the first node to the join node
    12531264      for (int u = first; u != join; u = _parent[u]) {
    12541265        e = _pred[u];
    1255         d = _forward[u] ?
    1256           _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
     1266        d = _flow[e];
     1267        if (_pred_dir[u] == DIR_DOWN) {
     1268          c = _cap[e];
     1269          d = c >= MAX ? INF : c - d;
     1270        }
    12571271        if (d < delta) {
    12581272          delta = d;
    … …  
    12611275        }
    12621276      }
    1263       // Search the cycle along the path form the second node to the root
     1277
     1278      // Search the cycle form the second node to the join node
    12641279      for (int u = second; u != join; u = _parent[u]) {
    12651280        e = _pred[u];
    1266         d = _forward[u] ?
    1267           (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
     1281        d = _flow[e];
     1282        if (_pred_dir[u] == DIR_UP) {
     1283          c = _cap[e];
     1284          d = c >= MAX ? INF : c - d;
     1285        }
    12681286        if (d <= delta) {
    12691287          delta = d;
    … …  
    12901308        _flow[in_arc] += val;
    12911309        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    1292           _flow[_pred[u]] += _forward[u] ? -val : val;
     1310          _flow[_pred[u]] -= _pred_dir[u] * val;
    12931311        }
    12941312        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
    1295           _flow[_pred[u]] += _forward[u] ? val : -val;
     1313          _flow[_pred[u]] += _pred_dir[u] * val;
    12961314        }
    12971315      }
    … …  
    13081326    // Update the tree structure
    13091327    void updateTreeStructure() {
    1310       int u, w;
    13111328      int old_rev_thread = _rev_thread[u_out];
    13121329      int old_succ_num = _succ_num[u_out];
    … …  
    13141331      v_out = _parent[u_out];
    13151332
    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]];
     1333      // Check if u_in and u_out coincide
     1334      if (u_in == u_out) {
     1335        // Update _parent, _pred, _pred_dir
     1336        _parent[u_in] = v_in;
     1337        _pred[u_in] = in_arc;
     1338        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1339
     1340        // Update _thread and _rev_thread
     1341        if (_thread[v_in] != u_out) {
     1342          int after = _thread[old_last_succ];
     1343          _thread[old_rev_thread] = after;
     1344          _rev_thread[after] = old_rev_thread;
     1345          after = _thread[v_in];
     1346          _thread[v_in] = u_out;
     1347          _rev_thread[u_out] = v_in;
     1348          _thread[old_last_succ] = after;
     1349          _rev_thread[after] = old_last_succ;
     1350        }
    13231351      } 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;
     1352        // Handle the case when old_rev_thread equals to v_in
     1353        // (it also means that join and v_out coincide)
     1354        int thread_continue = old_rev_thread == v_in ?
     1355          _thread[old_last_succ] : _thread[v_in];
     1356
     1357        // Update _thread and _parent along the stem nodes (i.e. the nodes
     1358        // between u_in and u_out, whose parent have to be changed)
     1359        int stem = u_in;              // the current stem node
     1360        int par_stem = v_in;          // the new parent of stem
     1361        int next_stem;                // the next stem node
     1362        int last = _last_succ[u_in];  // the last successor of stem
     1363        int before, after = _thread[last];
     1364        _thread[v_in] = u_in;
     1365        _dirty_revs.clear();
     1366        _dirty_revs.push_back(v_in);
     1367        while (stem != u_out) {
     1368          // Insert the next stem node into the thread list
     1369          next_stem = _parent[stem];
     1370          _thread[last] = next_stem;
     1371          _dirty_revs.push_back(last);
     1372
     1373          // Remove the subtree of stem from the thread list
     1374          before = _rev_thread[stem];
     1375          _thread[before] = after;
     1376          _rev_thread[after] = before;
     1377
     1378          // Change the parent node and shift stem nodes
     1379          _parent[stem] = par_stem;
     1380          par_stem = stem;
     1381          stem = next_stem;
     1382
     1383          // Update last and after
     1384          last = _last_succ[stem] == _last_succ[par_stem] ?
     1385            _rev_thread[par_stem] : _last_succ[stem];
     1386          after = _thread[last];
     1387        }
     1388        _parent[u_out] = par_stem;
     1389        _thread[last] = thread_continue;
     1390        _rev_thread[thread_continue] = last;
     1391        _last_succ[u_out] = last;
     1392
     1393        // Remove the subtree of u_out from the thread list except for
     1394        // the case when old_rev_thread equals to v_in
     1395        if (old_rev_thread != v_in) {
     1396          _thread[old_rev_thread] = after;
     1397          _rev_thread[after] = old_rev_thread;
     1398        }
     1399
     1400        // Update _rev_thread using the new _thread values
     1401        for (int i = 0; i != int(_dirty_revs.size()); ++i) {
     1402          int u = _dirty_revs[i];
     1403          _rev_thread[_thread[u]] = u;
     1404        }
     1405
     1406        // Update _pred, _pred_dir, _last_succ and _succ_num for the
     1407        // stem nodes from u_out to u_in
     1408        int tmp_sc = 0, tmp_ls = _last_succ[u_out];
     1409        for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
     1410          _pred[u] = _pred[p];
     1411          _pred_dir[u] = -_pred_dir[p];
     1412          tmp_sc += _succ_num[u] - _succ_num[p];
     1413          _succ_num[u] = tmp_sc;
     1414          _last_succ[p] = tmp_ls;
     1415        }
     1416        _pred[u_in] = in_arc;
     1417        _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
     1418        _succ_num[u_in] = old_succ_num;
    13981419      }
    13991420
    14001421      // 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       }
     1422      int up_limit_out = _last_succ[join] == v_in ? join : -1;
     1423      int last_succ_out = _last_succ[u_out];
     1424      for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
     1425        _last_succ[u] = last_succ_out;
     1426      }
     1427
    14051428      // Update _last_succ from v_out towards the root
    14061429      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;
     1430        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14081431             u = _parent[u]) {
    14091432          _last_succ[u] = old_rev_thread;
    14101433        }
    1411       } else {
    1412         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
     1434      }
     1435      else if (last_succ_out != old_last_succ) {
     1436        for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;
    14131437             u = _parent[u]) {
    1414           _last_succ[u] = _last_succ[u_out];
     1438          _last_succ[u] = last_succ_out;
    14151439        }
    14161440      }
    14171441
    14181442      // Update _succ_num from v_in to join
    1419       for (u = v_in; u != join; u = _parent[u]) {
     1443      for (int u = v_in; u != join; u = _parent[u]) {
    14201444        _succ_num[u] += old_succ_num;
    14211445      }
    14221446      // Update _succ_num from v_out to join
    1423       for (u = v_out; u != join; u = _parent[u]) {
     1447      for (int u = v_out; u != join; u = _parent[u]) {
    14241448        _succ_num[u] -= old_succ_num;
    14251449      }
    14261450    }
    14271451
    1428     // Update potentials
     1452    // Update potentials in the subtree that has been moved
    14291453    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
     1454      Cost sigma = _pi[v_in] - _pi[u_in] -
     1455                   _pred_dir[u_in] * _cost[in_arc];
    14341456      int end = _thread[_last_succ[u_in]];
    14351457      for (int u = u_in; u != end; u = _thread[u]) {

  • lemon/path.h

    r998 r1000  
    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

    r998 r1000  
    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

    r893 r894  
    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.