COIN-OR::LEMON - Graph Library

Ignore:
Files:
24 added
20 deleted
81 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

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

    r1159 r1234  
    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
     
    4462FIND_PACKAGE(Doxygen)
    4563FIND_PACKAGE(Ghostscript)
    46 FIND_PACKAGE(GLPK 4.33)
    47 FIND_PACKAGE(CPLEX)
    48 FIND_PACKAGE(COIN)
     64
     65SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     66SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     67SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     68
     69IF(LEMON_ENABLE_GLPK)
     70  FIND_PACKAGE(GLPK 4.33)
     71ENDIF(LEMON_ENABLE_GLPK)
     72IF(LEMON_ENABLE_ILOG)
     73  FIND_PACKAGE(ILOG)
     74ENDIF(LEMON_ENABLE_ILOG)
     75IF(LEMON_ENABLE_COIN)
     76  FIND_PACKAGE(COIN)
     77ENDIF(LEMON_ENABLE_COIN)
     78
     79IF(GLPK_FOUND)
     80  SET(LEMON_HAVE_LP TRUE)
     81  SET(LEMON_HAVE_MIP TRUE)
     82  SET(LEMON_HAVE_GLPK TRUE)
     83ENDIF(GLPK_FOUND)
     84IF(ILOG_FOUND)
     85  SET(LEMON_HAVE_LP TRUE)
     86  SET(LEMON_HAVE_MIP TRUE)
     87  SET(LEMON_HAVE_CPLEX TRUE)
     88ENDIF(ILOG_FOUND)
     89IF(COIN_FOUND)
     90  SET(LEMON_HAVE_LP TRUE)
     91  SET(LEMON_HAVE_MIP TRUE)
     92  SET(LEMON_HAVE_CLP TRUE)
     93  SET(LEMON_HAVE_CBC TRUE)
     94ENDIF(COIN_FOUND)
     95
     96IF(ILOG_FOUND)
     97  SET(DEFAULT_LP "CPLEX")
     98  SET(DEFAULT_MIP "CPLEX")
     99ELSEIF(COIN_FOUND)
     100  SET(DEFAULT_LP "CLP")
     101  SET(DEFAULT_MIP "CBC")
     102ELSEIF(GLPK_FOUND)
     103  SET(DEFAULT_LP "GLPK")
     104  SET(DEFAULT_MIP "GLPK")
     105ENDIF()
     106
     107IF(NOT LEMON_DEFAULT_LP OR
     108    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     109    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     110    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")))
     111  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     112    "Default LP solver backend (GLPK, CPLEX or CLP)" FORCE)
     113ENDIF()
     114IF(NOT LEMON_DEFAULT_MIP OR
     115    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     116    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     117    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     118  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     119    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     120ENDIF()
     121
    49122
    50123IF(DEFINED ENV{LEMON_CXX_WARNING})
     
    74147SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    75148
    76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     149IF(MSVC)
     150  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    77151    "Flags used by the C++ compiler during maintainer builds."
    78     FORCE )
    79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     152    )
     153  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    80154    "Flags used by the C compiler during maintainer builds."
    81     FORCE )
    82 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     155    )
     156  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     157    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     158    "Flags used for linking binaries during maintainer builds."
     159    )
     160  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     161    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     162    "Flags used by the shared libraries linker during maintainer builds."
     163    )
     164ELSE()
     165  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     166    "Flags used by the C++ compiler during maintainer builds."
     167    )
     168  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     169    "Flags used by the C compiler during maintainer builds."
     170    )
     171  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    83172    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    84173    "Flags used for linking binaries during maintainer builds."
    85     FORCE )
    86 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     174    )
     175  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    87176    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    88177    "Flags used by the shared libraries linker during maintainer builds."
    89     FORCE )
     178    )
     179ENDIF()
     180
    90181MARK_AS_ADVANCED(
    91182    CMAKE_CXX_FLAGS_MAINTAINER
     
    115206SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116207
    117 INCLUDE(FindPythonInterp)
     208INCLUDE(FindThreads)
     209
     210IF(NOT LEMON_THREADING)
     211  IF(CMAKE_USE_PTHREADS_INIT)
     212    SET(LEMON_THREADING "Pthread")
     213  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     214    SET(LEMON_THREADING "Win32")
     215  ELSE()
     216    SET(LEMON_THREADING "None")
     217  ENDIF()
     218ENDIF()
     219
     220SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     221  "Choose the threading library, options are: Pthread Win32 None."
     222  FORCE )
     223
     224IF(LEMON_THREADING STREQUAL "Pthread")
     225  SET(LEMON_USE_PTHREAD TRUE)
     226ELSEIF(LEMON_THREADING STREQUAL "Win32")
     227  SET(LEMON_USE_WIN32_THREADS TRUE)
     228ENDIF()
    118229
    119230ENABLE_TESTING()
     
    127238ADD_SUBDIRECTORY(lemon)
    128239IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     240  ADD_SUBDIRECTORY(contrib)
    129241  ADD_SUBDIRECTORY(demo)
    130242  ADD_SUBDIRECTORY(tools)
     
    150262ENDIF()
    151263
     264CONFIGURE_FILE(
     265  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     266  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     267  @ONLY
     268)
     269
     270SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     271STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     272SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     273ADD_CUSTOM_TARGET(dist
     274  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     275  COMMAND hg archive ${ARCHIVE_NAME}
     276  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     277  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     278  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     279  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     280  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     281  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     282  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     283  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     284  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     285  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     286  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     287  DEPENDS html
     288  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     289
     290# CPACK config (Basically for NSIS)
    152291IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    153292  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
  • INSTALL

    r890 r1233  
    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-DLEMON_DOC_SOURCE_BROWSER=YES
    114110
    115 --with-cplex-includedir=DIR
     111  Include the browsable cross referenced LEMON source code into the
     112  doc. It makes the doc quite bloated, but may be useful for
     113  developing LEMON itself.
    116114
    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).
     115-DLEMON_DOC_USE_MATHJAX=YES
    120116
    121 --with-cplex-libdir=DIR
     117  Use MathJax (http://mathjax.org) for rendering the math formulae in
     118  the doc.  It of much higher quality compared to the default LaTeX
     119  generated static images and it allows copy&paste of the formulae to
     120  LaTeX, Open Office, MS Word etc. documents.
    122121
    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).
     122  On the other hand, it needs either Internet access or a locally
     123  installed version of MathJax to properly render the doc.
    127124
    128 --without-cplex
     125-DLEMON_DOC_MATHJAX_RELPATH=DIRECTORY
     126 
     127  The location of the MathJax library. It defaults to
     128  http://www.mathjax.org/mathjax, which necessitates Internet access
     129  for proper rendering. The easiest way to make it usable offline is
     130  to set this parameter to 'mathjax' and copy all files of the MathJax
     131  library into the 'doc/html/mathjax' subdirectory of the build
     132  location.
    129133
    130    Disable CPLEX support.
     134  See http://docs.mathjax.org/en/latest/installation.html for more details.
    131135
    132 --with-soplex[=PREFIX]
     136 
     137-DLEMON_ENABLE_GLPK=NO
     138-DLEMON_ENABLE_COIN=NO
     139-DLEMON_ENABLE_ILOG=NO
    133140
    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.
     141  Enable optional third party libraries. They are all enabled by default.
    137142
    138 --with-soplex-includedir=DIR
     143-DLEMON_DEFAULT_LP=GLPK
    139144
    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).
     145  Sets the default LP solver backend. The supported values are
     146  CPLEX, CLP and GLPK. By default, it is set to the first one which
     147  is enabled and succesfully discovered.
    143148
    144 --with-soplex-libdir=DIR
     149-DLEMON_DEFAULT_MIP=GLPK
    145150
    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).
     151  Sets the default MIP solver backend. The supported values are
     152  CPLEX, CBC and GLPK. By default, it is set to the first one which
     153  is enabled and succesfully discovered.
    149154
    150 --without-soplex
     155-DGLPK_ROOT_DIR=DIRECTORY
     156-DCOIN_ROOT_DIR=DIRECTORY
     157-DILOG_ROOT_DIR=DIRECTORY
    151158
    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 
     159  Root directory prefixes of optional third party libraries.
    177160
    178161Makefile Variables
    179162==================
    180163
    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]...'
     164make VERBOSE=1
    187165
    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"'.
     166   This results in a more verbose output by showing the full
     167   compiler and linker commands.
  • LICENSE

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

    r1120 r1232  
    109109  COIN_BZ2_LIBRARY
    110110)
    111 
    112 IF(COIN_FOUND)
    113   SET(LEMON_HAVE_LP TRUE)
    114   SET(LEMON_HAVE_MIP TRUE)
    115   SET(LEMON_HAVE_CLP TRUE)
    116   SET(LEMON_HAVE_CBC TRUE)
    117 ENDIF(COIN_FOUND)
  • cmake/FindGLPK.cmake

    r685 r1232  
    5454
    5555MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
    56 
    57 IF(GLPK_FOUND)
    58   SET(LEMON_HAVE_LP TRUE)
    59   SET(LEMON_HAVE_MIP TRUE)
    60   SET(LEMON_HAVE_GLPK TRUE)
    61 ENDIF(GLPK_FOUND)
  • cmake/version.cmake.in

    r725 r1135  
    1 SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
     1SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")
  • doc/CMakeLists.txt

    r1107 r1251  
    55
    66SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     7SET(LEMON_DOC_USE_MATHJAX "NO" CACHE STRING "Use MathJax to display math formulae (YES/NO).")
     8SET(LEMON_DOC_MATHJAX_RELPATH "http://www.mathjax.org/mathjax" CACHE STRING "MathJax library location.")
     9
     10SET(LEMON_DOC_LIBSTDC++_URL
     11  "http://gcc.gnu.org/onlinedocs/gcc-4.7.3/libstdc++/api"
     12  CACHE STRING "GCC libstdc++ doxygen doc url.")
     13
    714
    815CONFIGURE_FILE(
     
    1825)
    1926
     27# Copy doc from source (if exists)
     28IF(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/html AND
     29    NOT EXISTS ${CMAKE_CURRENT_BINARY_DIR}/html/index.html)
     30  MESSAGE(STATUS "Copy doc from source tree")
     31  EXECUTE_PROCESS(
     32    COMMAND cmake -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/html ${CMAKE_CURRENT_BINARY_DIR}/html
     33    )
     34ENDIF()
     35
    2036IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    2137  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     
    2440    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    2541    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    26     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
    27     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
    28     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
    29     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    30     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    31     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    32     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    33     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    34     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    35     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    36     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    37     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    38     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    39     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     42    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     43    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
     44    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     45    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     46    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     47    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     48    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     50    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     51    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     52    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     53    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     54    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     55    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     56    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     57    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    4058    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    41     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    4259    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    4360    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     
    6481IF(WGET_FOUND)
    6582ADD_CUSTOM_TARGET(update-external-tags
    66   COMMAND ${CMAKE_COMMAND} -E make_directory dl
    67   # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
    68   COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
    69   COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
    70   COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
    71   COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     83  COMMAND ${WGET_EXECUTABLE} -N ${LEMON_DOC_LIBSTDC++_URL}/libstdc++.tag
    7284  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    7385  )
  • doc/Doxyfile.in

    r1107 r1251  
    7878FILE_VERSION_FILTER    =
    7979LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     80CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    8081#---------------------------------------------------------------------------
    8182# configuration options related to warning and progress messages
     
    9697                         "@abs_top_srcdir@/lemon/concepts" \
    9798                         "@abs_top_srcdir@/demo" \
     99                         "@abs_top_srcdir@/contrib" \
    98100                         "@abs_top_srcdir@/tools" \
    99101                         "@abs_top_srcdir@/test/test_tools.h" \
    100                          "@abs_top_builddir@/doc/mainpage.dox" \
    101                          "@abs_top_builddir@/doc/references.dox"
     102                         "@abs_top_builddir@/doc/mainpage.dox"
    102103INPUT_ENCODING         = UTF-8
    103104FILE_PATTERNS          = *.h \
     
    182183FORMULA_FONTSIZE       = 10
    183184FORMULA_TRANSPARENT    = YES
    184 USE_MATHJAX            = NO
    185 MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     185USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
     186MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
    186187SEARCHENGINE           = YES
    187188SERVER_BASED_SEARCH    = NO
     
    253254# Configuration::additions related to external references
    254255#---------------------------------------------------------------------------
    255 TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     256TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
    256257GENERATE_TAGFILE       = html/lemon.tag
    257258ALLEXTERNALS           = NO
  • doc/DoxygenLayout.xml

    r1036 r1251  
    1818      <tab type="globals" visible="yes" title="" intro=""/>
    1919    </tab>
    20     <tab type="dirs" visible="yes" title="" intro=""/>
    2120    <tab type="examples" visible="yes" title="" intro=""/>
    2221    <tab type="pages" visible="yes" title="" intro=""/>
  • doc/coding_style.dox

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

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

    r959 r1254  
    113113detailed documentation of particular adaptors.
    114114
     115Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
     116an adaptor can even be applied to another one.
     117The following image illustrates a situation when a \ref SubDigraph adaptor
     118is applied on a digraph and \ref Undirector is applied on the subgraph.
     119
     120\image html adaptors2.png
     121\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
     122
    115123The behavior of graph adaptors can be very different. Some of them keep
    116124capabilities of the original graph while in other cases this would be
     
    310318This group contains the common graph search algorithms, namely
    311319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \ref clrs01algorithms.
     320\cite clrs01algorithms.
    313321*/
    314322
     
    319327
    320328This group contains the algorithms for finding shortest paths in digraphs
    321 \ref clrs01algorithms.
     329\cite clrs01algorithms.
    322330
    323331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    341349
    342350This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     351trees and arborescences \cite clrs01algorithms.
    344352*/
    345353
     
    350358
    351359This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    353361
    354362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    366374LEMON contains several algorithms for solving maximum flow problems:
    367375- \ref EdmondsKarp Edmonds-Karp algorithm
    368   \ref edmondskarp72theoretical.
     376  \cite edmondskarp72theoretical.
    369377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    370   \ref goldberg88newapproach.
     378  \cite goldberg88newapproach.
    371379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    372   \ref dinic70algorithm, \ref sleator83dynamic.
     380  \cite dinic70algorithm, \cite sleator83dynamic.
    373381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    374   \ref goldberg88newapproach, \ref sleator83dynamic.
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
    375383
    376384In most cases the \ref Preflow algorithm provides the
     
    392400
    393401This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     402circulations \cite amo93networkflows. For more information about this
     403problem and its dual solution, see: \ref min_cost_flow
    396404"Minimum Cost Flow Problem".
    397405
    398406LEMON contains several algorithms for this problem.
    399407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    400    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    401409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    402    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    403    \ref bunnagel98efficient.
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
    404412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    405    shortest path method \ref edmondskarp72theoretical.
     413   shortest path method \cite edmondskarp72theoretical.
    406414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    407    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    408 
    409 In general NetworkSimplex is the most efficient implementation,
    410 but in special cases other algorithms could be faster.
     415   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
     416
     417In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     418implementations.
     419\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     420several thousands of nodes) and on dense graphs, while \ref CostScaling is
     421typically more efficient on large graphs (e.g. hundreds of thousands of
     422nodes or above), especially if they are sparse.
     423However, other algorithms could be faster in special cases.
    411424For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     425\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     426
     427These classes are intended to be used with integer-valued input data
     428(capacities, supply values, and costs), except for \ref CapacityScaling,
     429which is capable of handling real-valued arc costs (other numerical
     430data are required to be integer).
     431
     432For more details about these implementations and for a comprehensive
     433experimental study, see the paper \cite KiralyKovacs12MCF.
     434It also compares these codes to other publicly available
     435minimum cost flow solvers.
    413436*/
    414437
     
    449472
    450473This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     474\cite amo93networkflows, \cite karp78characterization.
    452475
    453476The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    465488
    466489LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     490- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
    469491- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     492  version of Karp's algorithm \cite hartmann93finding.
    471493- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    473 
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     494  \cite dasdan98minmeancycle, \cite dasdan04experimental.
     495
     496In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475497most efficient one, though the best known theoretical bound on its running
    476498time is exponential.
    477499Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    479 typically faster due to the applied early termination scheme.
     500run in time O(nm) and use space O(n<sup>2</sup>+m).
    480501*/
    481502
     
    540561
    541562/**
    542 @defgroup planar Planarity Embedding and Drawing
     563@defgroup planar Planar Embedding and Drawing
    543564@ingroup algs
    544565\brief Algorithms for planarity checking, embedding and drawing
     
    550571\image latex planar.eps "Plane graph" width=\textwidth
    551572*/
    552 
    553 /**
    554 @defgroup approx Approximation Algorithms
     573 
     574/**
     575@defgroup tsp Traveling Salesman Problem
     576@ingroup algs
     577\brief Algorithms for the symmetric traveling salesman problem
     578
     579This group contains basic heuristic algorithms for the the symmetric
     580\e traveling \e salesman \e problem (TSP).
     581Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     582the problem is to find a shortest possible tour that visits each node exactly
     583once (i.e. the minimum cost Hamiltonian cycle).
     584
     585These TSP algorithms are intended to be used with a \e metric \e cost
     586\e function, i.e. the edge costs should satisfy the triangle inequality.
     587Otherwise the algorithms could yield worse results.
     588
     589LEMON provides five well-known heuristics for solving symmetric TSP:
     590 - \ref NearestNeighborTsp Neareast neighbor algorithm
     591 - \ref GreedyTsp Greedy algorithm
     592 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     593 - \ref ChristofidesTsp Christofides algorithm
     594 - \ref Opt2Tsp 2-opt algorithm
     595
     596\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     597solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     598
     599\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     600approximation factor: 3/2.
     601
     602\ref Opt2Tsp usually provides the best results in practice, but
     603it is the slowest method. It can also be used to improve given tours,
     604for example, the results of other algorithms.
     605
     606\image html tsp.png
     607\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     608*/
     609
     610/**
     611@defgroup approx_algs Approximation Algorithms
    555612@ingroup algs
    556613\brief Approximation algorithms.
     
    558615This group contains the approximation and heuristic algorithms
    559616implemented in LEMON.
     617
     618<b>Maximum Clique Problem</b>
     619  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     620    Grosso, Locatelli, and Pullan.
    560621*/
    561622
     
    587648high-level interface.
    588649
    589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    590 \ref cplex, \ref soplex.
     650The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     651\cite cplex, \cite soplex.
    591652*/
    592653
     
    675736This group contains general \c EPS drawing methods and special
    676737graph exporting tools.
     738
     739\image html graph_to_eps.png
    677740*/
    678741
  • doc/images/bipartite_partitions.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Tue Nov 15 16:51:43 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
    57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
    62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
    63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
    64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
    65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
    66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
    67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
    68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
    69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
    70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
    71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
    72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
    73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
    78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
    79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
    80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
    81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
    82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
    83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
    84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
     56513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 7.00153 lb
     57513.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
     58393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
     59393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
     60393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
     61869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
     62869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 7.00153 lb
     63-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 7.00153 lb
     64-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 7.00153 lb
     65-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 7.00153 lb
     66-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 7.00153 lb
     67-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 7.00153 lb
     68-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 7.00153 lb
     69-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 7.00153 lb
     70-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 7.00153 lb
     71-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 7.00153 lb
     72-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 7.00153 lb
     73-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 7.00153 lb
     7479.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
     75637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
     76205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
     77399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
     78399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 7.00153 lb
     79-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 7.00153 lb
     80-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 7.00153 lb
     81-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 7.00153 lb
     82-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 7.00153 lb
     83-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 7.00153 lb
     84-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 7.00153 lb
     85120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
    8686grestore
    8787%Nodes:
    8888gsave
    89 -274 -131 20 1 0 0 nc
    90 -607.82 -246.651 20 1 0 0 nc
    91 -484.494 328.869 20 0 0 1 nc
    92 108.644 334.741 20 0 0 1 nc
    93 120.389 -129.198 20 0 0 1 nc
    94 -99.8351 99.8351 20 1 0 0 nc
    95 -211.415 -452.194 20 1 0 0 nc
    96 -860.344 -29.3633 20 0 0 1 nc
    97 -842.726 243.715 20 0 0 1 nc
    98 399.34 88.0898 20 1 0 0 nc
    99 205.543 -322.996 20 1 0 0 nc
    100 637.183 -184.989 20 0 0 1 nc
    101 79.2808 -528.539 20 0 0 1 nc
    102 -499.175 -499.175 20 0 0 1 nc
    103 -880.898 -528.539 20 0 0 1 nc
    104 -1177.47 -234.906 20 1 0 0 nc
    105 -1077.63 161.498 20 1 0 0 nc
    106 -663.61 546.157 20 1 0 0 nc
    107 -82.2171 593.138 20 0 0 1 nc
    108 596.074 302.442 20 0 0 1 nc
    109 869.153 52.8539 20 1 0 0 nc
    110 393.468 566.711 20 1 0 0 nc
    111 513.857 -446.322 20 1 0 0 nc
     89-274 -131 23.3384 1 0 0 nc
     90-607.82 -246.651 23.3384 1 0 0 nc
     91-484.494 328.869 23.3384 0 0 1 nc
     92108.644 334.741 23.3384 0 0 1 nc
     93120.389 -129.198 23.3384 0 0 1 nc
     94-99.8351 99.8351 23.3384 1 0 0 nc
     95-211.415 -452.194 23.3384 1 0 0 nc
     96-860.344 -29.3633 23.3384 0 0 1 nc
     97-842.726 243.715 23.3384 0 0 1 nc
     98399.34 88.0898 23.3384 1 0 0 nc
     99205.543 -322.996 23.3384 1 0 0 nc
     100637.183 -184.989 23.3384 0 0 1 nc
     10179.2808 -528.539 23.3384 0 0 1 nc
     102-499.175 -499.175 23.3384 0 0 1 nc
     103-880.898 -528.539 23.3384 0 0 1 nc
     104-1177.47 -234.906 23.3384 1 0 0 nc
     105-1077.63 161.498 23.3384 1 0 0 nc
     106-663.61 546.157 23.3384 1 0 0 nc
     107-82.2171 593.138 23.3384 0 0 1 nc
     108596.074 302.442 23.3384 0 0 1 nc
     109869.153 52.8539 23.3384 1 0 0 nc
     110393.468 566.711 23.3384 1 0 0 nc
     111513.857 -446.322 23.3384 1 0 0 nc
    112112grestore
    113113grestore
  • doc/images/connected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 0 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 0 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 1 0 0 nc
    117 588.113 544.499 20 1 0 0 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 1 0 nc
    120 -132.697 451.748 20 0 1 0 nc
    121 -416.25 345.746 20 0 1 0 nc
    122 -180.397 245.045 20 0 1 0 nc
    123 -13.4452 133.743 20 0 1 0 nc
    124 -262.548 107.243 20 0 1 0 nc
    125 201.208 38.3422 20 0 1 0 nc
    126 116.407 -173.66 20 0 1 0 nc
    127 -26.6953 -19.9585 20 0 1 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 0 0 1 nc
    131 -67.9734 -347.42 20 0 0 1 nc
    132 415.393 -289.516 20 0 0 1 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 0 0 1 nc
    135 762.812 -17.6227 20 0 0 1 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 0 0 1 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 0 0 1 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 1 1 0 nc
    147 277.311 -252.33 20 1 1 0 nc
    148 271.13 -175.058 20 1 1 0 nc
    149 366.947 -110.15 20 1 1 0 nc
    150 397.855 -196.694 20 1 1 0 nc
    151 438.037 -88.514 20 1 1 0 nc
    152 286.584 -48.3327 20 1 1 0 nc
    153 212.403 -23.6057 20 1 1 0 nc
    154 280.402 10.3938 20 1 1 0 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 1 0 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 1 0 0 nc
     117588.113 544.499 20.8452 1 0 0 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 1 0 nc
     120-132.697 451.748 20.8452 0 1 0 nc
     121-416.25 345.746 20.8452 0 1 0 nc
     122-180.397 245.045 20.8452 0 1 0 nc
     123-13.4452 133.743 20.8452 0 1 0 nc
     124-262.548 107.243 20.8452 0 1 0 nc
     125201.208 38.3422 20.8452 0 1 0 nc
     126116.407 -173.66 20.8452 0 1 0 nc
     127-26.6953 -19.9585 20.8452 0 1 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 0 0 1 nc
     131-67.9734 -347.42 20.8452 0 0 1 nc
     132415.393 -289.516 20.8452 0 0 1 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 0 0 1 nc
     135762.812 -17.6227 20.8452 0 0 1 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 0 0 1 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 0 0 1 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 1 1 0 nc
     147277.311 -252.33 20.8452 1 1 0 nc
     148271.13 -175.058 20.8452 1 1 0 nc
     149366.947 -110.15 20.8452 1 1 0 nc
     150397.855 -196.694 20.8452 1 1 0 nc
     151438.037 -88.514 20.8452 1 1 0 nc
     152286.584 -48.3327 20.8452 1 1 0 nc
     153212.403 -23.6057 20.8452 1 1 0 nc
     154280.402 10.3938 20.8452 1 1 0 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 1 0 0 nc
    157157grestore
    158158grestore
  • doc/images/edge_biconnected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
    101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
    102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
    109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
    110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 0 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 0 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 1 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 1 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 0 nc
    115 -689.204 -237.261 20 0 0 0 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 0 0 1 nc
    119 -371.2 568.349 20 1 1 0 nc
    120 -132.697 451.748 20 1 1 0 nc
    121 -416.25 345.746 20 1 1 0 nc
    122 -180.397 245.045 20 1 1 0 nc
    123 -13.4452 133.743 20 1 1 0 nc
    124 -262.548 107.243 20 1 1 0 nc
    125 201.208 38.3422 20 1 1 0 nc
    126 116.407 -173.66 20 1 1 0 nc
    127 -26.6953 -19.9585 20 1 1 0 nc
    128 -539.894 -262.64 20 0 0.5 0 nc
    129 -323.543 -433.964 20 0 0.5 0 nc
    130 -309.657 -57.9033 20 0 0.5 0 nc
    131 -67.9734 -347.42 20 0 0.5 0 nc
    132 415.393 -289.516 20 0.5 0 0 nc
    133 730.084 -307.139 20 0.5 0 0 nc
    134 526.164 32.7279 20 0.5 0 0 nc
    135 762.812 -17.6227 20 0.5 0 0 nc
    136 -67.9734 319.727 20 0.5 0 0 nc
    137 329.797 314.692 20 0.5 0 0 nc
    138 -5.03507 561.41 20 0.5 0 0 nc
    139 422.945 521.129 20 0.5 0 0 nc
    140 -470.779 158.605 20 0 1 1 nc
    141 986.873 -115.807 20 0.5 0 0 nc
    142 906.312 201.403 20 0.5 0 0 nc
    143 -767.847 113.289 20 0 1 1 nc
    144 -579.033 445.603 20 0 1 1 nc
    145 -840.856 -246.718 20 1 0 1 nc
    146 206.221 -205.967 20 0 0 0.5 nc
    147 277.311 -252.33 20 0 0 0.5 nc
    148 271.13 -175.058 20 0 0 0.5 nc
    149 366.947 -110.15 20 0 0 0.5 nc
    150 397.855 -196.694 20 0 0 0.5 nc
    151 438.037 -88.514 20 0 0 0.5 nc
    152 286.584 -48.3327 20 0 0 0.5 nc
    153 212.403 -23.6057 20 0 0 0.5 nc
    154 280.402 10.3938 20 0 0 0.5 nc
    155 694.579 115.483 20 1 0 0 nc
    156 574.035 177.301 20 0 1 0 nc
     114-567.302 43.6423 20.8452 0 0 0 nc
     115-689.204 -237.261 20.8452 0 0 0 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 0 0 1 nc
     119-371.2 568.349 20.8452 1 1 0 nc
     120-132.697 451.748 20.8452 1 1 0 nc
     121-416.25 345.746 20.8452 1 1 0 nc
     122-180.397 245.045 20.8452 1 1 0 nc
     123-13.4452 133.743 20.8452 1 1 0 nc
     124-262.548 107.243 20.8452 1 1 0 nc
     125201.208 38.3422 20.8452 1 1 0 nc
     126116.407 -173.66 20.8452 1 1 0 nc
     127-26.6953 -19.9585 20.8452 1 1 0 nc
     128-539.894 -262.64 20.8452 0 0.5 0 nc
     129-323.543 -433.964 20.8452 0 0.5 0 nc
     130-309.657 -57.9033 20.8452 0 0.5 0 nc
     131-67.9734 -347.42 20.8452 0 0.5 0 nc
     132415.393 -289.516 20.8452 0.5 0 0 nc
     133730.084 -307.139 20.8452 0.5 0 0 nc
     134526.164 32.7279 20.8452 0.5 0 0 nc
     135762.812 -17.6227 20.8452 0.5 0 0 nc
     136-67.9734 319.727 20.8452 0.5 0 0 nc
     137329.797 314.692 20.8452 0.5 0 0 nc
     138-5.03507 561.41 20.8452 0.5 0 0 nc
     139422.945 521.129 20.8452 0.5 0 0 nc
     140-470.779 158.605 20.8452 0 1 1 nc
     141986.873 -115.807 20.8452 0.5 0 0 nc
     142906.312 201.403 20.8452 0.5 0 0 nc
     143-767.847 113.289 20.8452 0 1 1 nc
     144-579.033 445.603 20.8452 0 1 1 nc
     145-840.856 -246.718 20.8452 1 0 1 nc
     146206.221 -205.967 20.8452 0 0 0.5 nc
     147277.311 -252.33 20.8452 0 0 0.5 nc
     148271.13 -175.058 20.8452 0 0 0.5 nc
     149366.947 -110.15 20.8452 0 0 0.5 nc
     150397.855 -196.694 20.8452 0 0 0.5 nc
     151438.037 -88.514 20.8452 0 0 0.5 nc
     152286.584 -48.3327 20.8452 0 0 0.5 nc
     153212.403 -23.6057 20.8452 0 0 0.5 nc
     154280.402 10.3938 20.8452 0 0 0.5 nc
     155694.579 115.483 20.8452 1 0 0 nc
     156574.035 177.301 20.8452 0 1 0 nc
    157157grestore
    158158grestore
  • doc/images/node_biconnected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:18:43 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
    100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
    101 -180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
    102 -180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
    103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
    104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
    105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
    108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
    109 -689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
    110 -689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
     56574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 6.25356 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
     69277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 6.25356 lb
     70-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 6.25356 lb
     71-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 6.25356 lb
     72-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 6.25356 lb
     73-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 6.25356 lb
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     76986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 6.25356 lb
     77-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 6.25356 lb
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
     80422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 6.25356 lb
     81-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     82329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 6.25356 lb
     83-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 6.25356 lb
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
     88415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 6.25356 lb
     89-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 6.25356 lb
     90-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 6.25356 lb
     91-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     92-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 6.25356 lb
     93-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 6.25356 lb
     94-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 6.25356 lb
     95-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 6.25356 lb
     96-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 6.25356 lb
     97116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 6.25356 lb
     98-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 6.25356 lb
     99-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 6.25356 lb
     100-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 6.25356 lb
     101-180.397 245.045 -113.509 338.465 -132.697 451.748 0 1 1 6.25356 lb
     102-180.397 245.045 -199.585 358.328 -132.697 451.748 0 1 1 6.25356 lb
     103-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 6.25356 lb
     104-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 6.25356 lb
     105-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 6.25356 lb
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
     108588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 6.25356 lb
     109-689.204 -237.261 -587.735 -114.393 -567.302 43.6423 0 0 0 6.25356 lb
     110-689.204 -237.261 -668.771 -79.2259 -567.302 43.6423 0 0 0 6.25356 lb
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20 0 0 1 nc
    115 -689.204 -237.261 20 0 0 1 nc
    116 924.667 409.347 20 0 0 1 nc
    117 588.113 544.499 20 0 0 1 nc
    118 670.264 274.195 20 1 0 0 nc
    119 -371.2 568.349 20 0 0 1 nc
    120 -132.697 451.748 20 1 0 0 nc
    121 -416.25 345.746 20 0 0 1 nc
    122 -180.397 245.045 20 1 0 0 nc
    123 -13.4452 133.743 20 0 0 1 nc
    124 -262.548 107.243 20 0 0 1 nc
    125 201.208 38.3422 20 0 0 1 nc
    126 116.407 -173.66 20 0 0 1 nc
    127 -26.6953 -19.9585 20 1 0 0 nc
    128 -539.894 -262.64 20 0 0 1 nc
    129 -323.543 -433.964 20 0 0 1 nc
    130 -309.657 -57.9033 20 1 0 0 nc
    131 -67.9734 -347.42 20 1 0 0 nc
    132 415.393 -289.516 20 1 0 0 nc
    133 730.084 -307.139 20 0 0 1 nc
    134 526.164 32.7279 20 1 0 0 nc
    135 762.812 -17.6227 20 1 0 0 nc
    136 -67.9734 319.727 20 0 0 1 nc
    137 329.797 314.692 20 0 0 1 nc
    138 -5.03507 561.41 20 0 0 1 nc
    139 422.945 521.129 20 0 0 1 nc
    140 -470.779 158.605 20 1 0 0 nc
    141 986.873 -115.807 20 0 0 1 nc
    142 906.312 201.403 20 0 0 1 nc
    143 -767.847 113.289 20 1 0 0 nc
    144 -579.033 445.603 20 0 0 1 nc
    145 -840.856 -246.718 20 0 0 1 nc
    146 206.221 -205.967 20 0 0 1 nc
    147 277.311 -252.33 20 0 0 1 nc
    148 271.13 -175.058 20 1 0 0 nc
    149 366.947 -110.15 20 1 0 0 nc
    150 397.855 -196.694 20 0 0 1 nc
    151 438.037 -88.514 20 0 0 1 nc
    152 286.584 -48.3327 20 1 0 0 nc
    153 212.403 -23.6057 20 0 0 1 nc
    154 280.402 10.3938 20 0 0 1 nc
    155 694.579 115.483 20 0 0 1 nc
    156 574.035 177.301 20 0 0 1 nc
     114-567.302 43.6423 20.8452 0 0 1 nc
     115-689.204 -237.261 20.8452 0 0 1 nc
     116924.667 409.347 20.8452 0 0 1 nc
     117588.113 544.499 20.8452 0 0 1 nc
     118670.264 274.195 20.8452 1 0 0 nc
     119-371.2 568.349 20.8452 0 0 1 nc
     120-132.697 451.748 20.8452 1 0 0 nc
     121-416.25 345.746 20.8452 0 0 1 nc
     122-180.397 245.045 20.8452 1 0 0 nc
     123-13.4452 133.743 20.8452 0 0 1 nc
     124-262.548 107.243 20.8452 0 0 1 nc
     125201.208 38.3422 20.8452 0 0 1 nc
     126116.407 -173.66 20.8452 0 0 1 nc
     127-26.6953 -19.9585 20.8452 1 0 0 nc
     128-539.894 -262.64 20.8452 0 0 1 nc
     129-323.543 -433.964 20.8452 0 0 1 nc
     130-309.657 -57.9033 20.8452 1 0 0 nc
     131-67.9734 -347.42 20.8452 1 0 0 nc
     132415.393 -289.516 20.8452 1 0 0 nc
     133730.084 -307.139 20.8452 0 0 1 nc
     134526.164 32.7279 20.8452 1 0 0 nc
     135762.812 -17.6227 20.8452 1 0 0 nc
     136-67.9734 319.727 20.8452 0 0 1 nc
     137329.797 314.692 20.8452 0 0 1 nc
     138-5.03507 561.41 20.8452 0 0 1 nc
     139422.945 521.129 20.8452 0 0 1 nc
     140-470.779 158.605 20.8452 1 0 0 nc
     141986.873 -115.807 20.8452 0 0 1 nc
     142906.312 201.403 20.8452 0 0 1 nc
     143-767.847 113.289 20.8452 1 0 0 nc
     144-579.033 445.603 20.8452 0 0 1 nc
     145-840.856 -246.718 20.8452 0 0 1 nc
     146206.221 -205.967 20.8452 0 0 1 nc
     147277.311 -252.33 20.8452 0 0 1 nc
     148271.13 -175.058 20.8452 1 0 0 nc
     149366.947 -110.15 20.8452 1 0 0 nc
     150397.855 -196.694 20.8452 0 0 1 nc
     151438.037 -88.514 20.8452 0 0 1 nc
     152286.584 -48.3327 20.8452 1 0 0 nc
     153212.403 -23.6057 20.8452 0 0 1 nc
     154280.402 10.3938 20.8452 0 0 1 nc
     155694.579 115.483 20.8452 0 0 1 nc
     156574.035 177.301 20.8452 0 0 1 nc
    157157grestore
    158158grestore
  • doc/images/strongly_connected_components.eps

    r634 r1213  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Nov  4 13:47:12 2005
     3%%CreationDate: Fri Mar  8 00:22:15 2013
    44%%BoundingBox: 0 0 842 596
    55%%EndComments
     
    5454%Edges:
    5555gsave
    56 2 setlinewidth 0 0 1 setrgbcolor newpath
     564.56973 setlinewidth 0 0 1 setrgbcolor newpath
    5757218.178 27.2723 moveto
    58 192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
    59 newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
    60 2 setlinewidth 0 0 1 setrgbcolor newpath
     58195.849 -31.0725 190.033 -46.2697 176.306 -82.1369 curveto stroke
     59newpath 163.235 -116.291 moveto 165.206 -77.8889 lineto 187.405 -86.3849 lineto closepath fill
     604.56973 setlinewidth 0 0 1 setrgbcolor newpath
    616144.8044 15.5841 moveto
    62 119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
    63 newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
    64 2 setlinewidth 1 0 0 setrgbcolor newpath
     62109.705 19.9594 126.016 21.0591 166.493 23.7879 curveto stroke
     63newpath 202.98 26.2477 moveto 167.292 11.9299 lineto 165.694 35.6458 lineto closepath fill
     644.56973 setlinewidth 1 0 0 setrgbcolor newpath
    6565218.178 27.2723 moveto
    66 285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
    67 newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
    68 2 setlinewidth 0 0 1 setrgbcolor newpath
     66281.264 -80.3935 289.87 -95.0808 338.092 -177.379 curveto stroke
     67newpath 356.579 -208.932 moveto 327.837 -183.388 lineto 348.346 -171.371 lineto closepath fill
     684.56973 setlinewidth 0 0 1 setrgbcolor newpath
    6969157.79 -130.517 moveto
    70 108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
    71 newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
    72 2 setlinewidth 1 0 0 setrgbcolor newpath
     70114.446 -74.4692 104.358 -61.4239 76.4943 -25.394 curveto stroke
     71newpath 54.1228 3.53455 moveto 85.8959 -18.1234 lineto 67.0928 -32.6646 lineto closepath fill
     724.56973 setlinewidth 1 0 0 setrgbcolor newpath
    7373-105.193 -261.035 moveto
    74 -35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
    75 newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
    76 2 setlinewidth 0 0 1 setrgbcolor newpath
     74-39.4801 -139.85 -31.344 -124.846 20.1113 -29.9539 curveto stroke
     75newpath 37.5434 2.19358 moveto 30.559 -35.6192 lineto 9.66361 -24.2886 lineto closepath fill
     764.56973 setlinewidth 0 0 1 setrgbcolor newpath
    7777-465.576 -42.8564 moveto
    78 -559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
    79 newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
    80 2 setlinewidth 0 0 1 setrgbcolor newpath
     78-550.335 -27.1603 -566.8 -24.1113 -625.027 -13.3286 curveto stroke
     79newpath -660.985 -6.66971 moveto -622.863 -1.64245 lineto -627.191 -25.0148 lineto closepath fill
     804.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8181-574.666 -153.893 moveto
    82 -528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
    83 newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
    84 2 setlinewidth 1 0 0 setrgbcolor newpath
     82-535.911 -114.447 -524.692 -103.027 -501.88 -79.8085 curveto stroke
     83newpath -476.251 -53.7222 moveto -493.402 -88.1377 lineto -510.358 -71.4793 lineto closepath fill
     844.56973 setlinewidth 1 0 0 setrgbcolor newpath
    8585-490.901 120.777 moveto
    86 -480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
    87 newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
    88 2 setlinewidth 0 0 1 setrgbcolor newpath
     86-481.623 60.8277 -479.143 44.8049 -473.499 8.33636 curveto stroke
     87newpath -467.906 -27.8032 moveto -485.244 6.51862 lineto -461.754 10.1541 lineto closepath fill
     884.56973 setlinewidth 0 0 1 setrgbcolor newpath
    8989-675.963 -3.89604 moveto
    90 -632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
    91 newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
    92 2 setlinewidth 0 0 1 setrgbcolor newpath
     90-637.405 -60.9909 -628.201 -74.6206 -603.658 -110.963 curveto stroke
     91newpath -583.191 -141.27 moveto -613.507 -117.615 lineto -593.808 -104.312 lineto closepath fill
     924.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9393-490.901 120.777 moveto
    94 -435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
    95 newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
    96 2 setlinewidth 0 0 1 setrgbcolor newpath
     94-439.75 208.465 -431.238 223.057 -394.278 286.417 curveto stroke
     95newpath -375.851 318.006 moveto -384.012 280.429 lineto -404.543 292.406 lineto closepath fill
     964.56973 setlinewidth 0 0 1 setrgbcolor newpath
    9797-266.879 114.933 moveto
    98 -367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
    99 newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
    100 2 setlinewidth 0 0 1 setrgbcolor newpath
     98-358.311 117.318 -375.109 117.756 -439.117 119.426 curveto stroke
     99newpath -475.674 120.38 moveto -438.807 131.307 lineto -439.426 107.545 lineto closepath fill
     1004.56973 setlinewidth 0 0 1 setrgbcolor newpath
    101101-368.176 331.163 moveto
    102 -322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
    103 newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
    104 2 setlinewidth 1 0 0 setrgbcolor newpath
     102-326.156 241.466 -318.997 226.186 -288.855 161.843 curveto stroke
     103newpath -273.341 128.727 moveto -299.617 156.801 lineto -278.092 166.885 lineto closepath fill
     1044.56973 setlinewidth 1 0 0 setrgbcolor newpath
    105105-266.879 114.933 moveto
    106 -224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
    107 newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
    108 2 setlinewidth 0 0 1 setrgbcolor newpath
     106-226.764 227.755 -221.069 243.774 -190.728 329.107 curveto stroke
     107newpath -178.477 363.564 moveto -179.53 325.126 lineto -201.926 333.089 lineto closepath fill
     1084.56973 setlinewidth 0 0 1 setrgbcolor newpath
    109109-251.294 -335.059 moveto
    110 -189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
    111 newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
    112 2 setlinewidth 0 0 1 setrgbcolor newpath
     110-198.044 -308.079 -183.61 -300.766 -151.402 -284.448 curveto stroke
     111newpath -118.781 -267.92 moveto -146.031 -295.049 lineto -156.774 -273.846 lineto closepath fill
     1124.56973 setlinewidth 0 0 1 setrgbcolor newpath
    113113-389.604 -136.361 moveto
    114 -327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
    115 newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
    116 2 setlinewidth 1 0 0 setrgbcolor newpath
     114-332.039 -219.059 -322.392 -232.919 -280.889 -292.543 curveto stroke
     115newpath -259.996 -322.557 moveto -290.643 -299.333 lineto -271.134 -285.753 lineto closepath fill
     1164.56973 setlinewidth 1 0 0 setrgbcolor newpath
    1171175.84406 175.322 moveto
    118 -76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
    119 newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
    120 2 setlinewidth 0 0 1 setrgbcolor newpath
     118-70.5724 261.706 -81.8227 274.423 -139.051 339.116 curveto stroke
     119newpath -163.281 366.507 moveto -130.149 346.991 lineto -147.953 331.242 lineto closepath fill
     1204.56973 setlinewidth 0 0 1 setrgbcolor newpath
    121121169.478 311.683 moveto
    122 96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
    123 newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
    124 2 setlinewidth 0 0 1 setrgbcolor newpath
     122103.641 256.819 90.7821 246.103 45.6398 208.485 curveto stroke
     123newpath 17.546 185.074 moveto 38.0313 217.615 lineto 53.2483 199.355 lineto closepath fill
     1244.56973 setlinewidth 0 0 1 setrgbcolor newpath
    125125342.851 111.037 moveto
    126 263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke
    127 newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
    128 2 setlinewidth 0 0 1 setrgbcolor newpath
     126269.224 196.246 258.132 209.083 203.347 272.486 curveto stroke
     127newpath 179.437 300.157 moveto 212.34 280.257 lineto 194.354 264.716 lineto closepath fill
     1284.56973 setlinewidth 0 0 1 setrgbcolor newpath
    1291295.84406 175.322 moveto
    130 163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke
    131 newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
    132 2 setlinewidth 0 0 1 setrgbcolor newpath
     130155.419 146.79 172.221 143.585 291.966 120.743 curveto stroke
     131newpath 327.888 113.891 moveto 289.739 109.069 lineto 294.193 132.418 lineto closepath fill
     1324.56973 setlinewidth 0 0 1 setrgbcolor newpath
    133133342.851 111.037 moveto
    134 497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
    135 newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
    136 2 setlinewidth 0 0 1 setrgbcolor newpath
     134490.978 6.99574 505.015 -2.86383 627.727 -89.0547 curveto stroke
     135newpath 657.653 -110.074 moveto 620.896 -98.7802 lineto 634.558 -79.3291 lineto closepath fill
     1364.56973 setlinewidth 0 0 1 setrgbcolor newpath
    137137364.28 -222.074 moveto
    138 354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
    139 newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
    140 2 setlinewidth 0 0 1 setrgbcolor newpath
     138354.807 -74.8128 353.709 -57.7536 346.177 59.3416 curveto stroke
     139newpath 343.829 95.836 moveto 358.037 60.1045 lineto 334.316 58.5786 lineto closepath fill
     1404.56973 setlinewidth 0 0 1 setrgbcolor newpath
    141141670.118 -118.829 moveto
    142 528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
    143 newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
    144 2 setlinewidth 1 0 0 setrgbcolor newpath
     142535.595 -164.241 519.412 -169.704 413.361 -205.505 curveto stroke
     143newpath 378.712 -217.202 moveto 409.559 -194.245 lineto 417.162 -216.766 lineto closepath fill
     1444.56973 setlinewidth 1 0 0 setrgbcolor newpath
    145145-105.193 -261.035 moveto
    146 118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
    147 newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
    148 2 setlinewidth 0 0 1 setrgbcolor newpath
     146110.939 -243.099 128.069 -241.677 312.655 -226.358 curveto stroke
     147newpath 349.1 -223.334 moveto 313.638 -238.202 lineto 311.672 -214.514 lineto closepath fill
     1484.56973 setlinewidth 0 0 1 setrgbcolor newpath
    149149-105.193 -261.035 moveto
    150 -160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
    151 newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
    152 2 setlinewidth 0 0 1 setrgbcolor newpath
     150-156.746 -168.566 -164.987 -153.784 -202.693 -86.1539 curveto stroke
     151newpath -220.5 -54.2129 moveto -192.312 -80.3665 lineto -213.073 -91.9413 lineto closepath fill
     1524.56973 setlinewidth 0 0 1 setrgbcolor newpath
    153153-227.918 -40.9084 moveto
    154 -298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
    155 newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
     154-290.327 -77.7521 -304.558 -86.1532 -344.995 -110.026 curveto stroke
     155newpath -376.487 -128.617 moveto -351.037 -99.7914 lineto -338.953 -120.26 lineto closepath fill
    156156grestore
    157157%Nodes:
    158158gsave
    159 -389.604 -136.361 20 0 1 0 nc
    160 -227.918 -40.9084 20 0 1 0 nc
    161 -105.193 -261.035 20 0 1 0 nc
    162 364.28 -222.074 20 1 1 0 nc
    163 670.118 -118.829 20 1 1 0 nc
    164 342.851 111.037 20 1 1 0 nc
    165 5.84406 175.322 20 1 1 0 nc
    166 169.478 311.683 20 1 1 0 nc
    167 -173.374 377.916 20 1 0 1 nc
    168 -251.294 -335.059 20 0 1 0 nc
    169 -266.879 114.933 20 0 0 0 nc
    170 -368.176 331.163 20 0 0 0 nc
    171 -490.901 120.777 20 0 0 0 nc
    172 -574.666 -153.893 20 1 0 0 nc
    173 -675.963 -3.89604 20 1 0 0 nc
    174 -465.576 -42.8564 20 1 0 0 nc
    175 44.8044 15.5841 20 0 0 1 nc
    176 157.79 -130.517 20 0 0 1 nc
    177 218.178 27.2723 20 0 0 1 nc
     159-389.604 -136.361 15.2324 0 1 0 nc
     160-227.918 -40.9084 15.2324 0 1 0 nc
     161-105.193 -261.035 15.2324 0 1 0 nc
     162364.28 -222.074 15.2324 1 1 0 nc
     163670.118 -118.829 15.2324 1 1 0 nc
     164342.851 111.037 15.2324 1 1 0 nc
     1655.84406 175.322 15.2324 1 1 0 nc
     166169.478 311.683 15.2324 1 1 0 nc
     167-173.374 377.916 15.2324 1 0 1 nc
     168-251.294 -335.059 15.2324 0 1 0 nc
     169-266.879 114.933 15.2324 0 0 0 nc
     170-368.176 331.163 15.2324 0 0 0 nc
     171-490.901 120.777 15.2324 0 0 0 nc
     172-574.666 -153.893 15.2324 1 0 0 nc
     173-675.963 -3.89604 15.2324 1 0 0 nc
     174-465.576 -42.8564 15.2324 1 0 0 nc
     17544.8044 15.5841 15.2324 0 0 1 nc
     176157.79 -130.517 15.2324 0 0 1 nc
     177218.178 27.2723 15.2324 0 0 1 nc
    178178grestore
    179179grestore
  • doc/lgf.dox

    r1069 r1250  
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section, it
    67 again starts with a header line describing the names of the maps, but
    68 the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are the source
    70 and the target node of the arc, respectively, then come the map
     66The \e LGF files can also contain bipartite graphs, in this case a
     67\c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
     68graph. If a map is in both of these sections, then it can be used as a
     69regular node map.
     70
     71\code
     72 @red_nodes
     73 label  only_red_map   name
     74 1      "cherry"       "John"
     75 2      "Santa Claus"  "Jack"
     76 3      "blood"        "Jason"
     77 @blue_nodes
     78 label  name
     79 4      "Elisabeth"
     80 5      "Eve"
     81\endcode
     82
     83The \c \@arcs section is very similar to the \c \@nodes section,
     84it again starts with a header line describing the names of the maps,
     85but the \c "label" map is not obligatory here. The following lines
     86describe the arcs. The first two tokens of each line are
     87the source and the target node of the arc, respectively, then come the map
    7188values. The source and target tokens must be node labels.
    7289
  • doc/mainpage.dox.in

    r1039 r1221  
    2626It is a C++ template library providing efficient implementations of common
    2727data structures and algorithms with focus on combinatorial optimization
    28 tasks connected mainly with graphs and networks.
     28tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon.
    2929
    3030<b>
     
    3838The project is maintained by the
    3939<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    40 Combinatorial Optimization</a> \ref egres
     40Combinatorial Optimization</a> \cite egres
    4141at the Operations Research Department of the
    4242<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
    4343Budapest, Hungary.
    4444LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
    45 initiative \ref coinor.
     45initiative \cite coinor.
    4646
    4747\section howtoread How to Read the Documentation
  • doc/min_cost_flow.dox

    r956 r1221  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs \cite amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
     
    102102\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    103103
    104 However if the sum of the supply values is zero, then these two problems
     104However, if the sum of the supply values is zero, then these two problems
    105105are equivalent.
    106106The \ref min_cost_flow_algs "algorithms" in LEMON support the general
  • doc/references.bib

    r802 r1219  
    55  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
    66                  {O}ptimization in {N}etworks},
    7   howpublished = {\url{http://lemon.cs.elte.hu/}},
    8   year =         2009
     7  howpublished = {\url{http://lemon.cs.elte.hu/}}
    98}
    109
     
    2120                  {O}perations {R}esearch},
    2221  url =          {http://www.coin-or.org/}
     22}
     23
     24
     25%%%%% Papers related to LEMON %%%%%
     26
     27@article{DezsoJuttnerKovacs11Lemon,
     28  author =       {B. Dezs{\H o} and A. J\"uttner and P. Kov\'acs},
     29  title =        {{LEMON} -- an open source {C++} graph template library},
     30  journal =      {Electronic Notes in Theoretical Computer Science},
     31  volume =       {264},
     32  pages =        {23--45},
     33  year =         {2011},
     34  note =         {Proc. 2nd Workshop on Generative Technologies}
     35}
     36
     37@article{KiralyKovacs12MCF,
     38  author =       {Z. Kir\'aly and P. Kov\'acs},
     39  title =        {Efficient implementations of minimum-cost flow algorithms},
     40  journal =      {Acta Universitatis Sapientiae, Informatica},
     41  year =         {2012},
     42  volume =       {4},
     43  pages =        {67--118}
    2344}
    2445
     
    212233  volume =       23,
    213234  pages =        {309-311}
     235}
     236
     237@article{hartmann93finding,
     238  author =       {Mark Hartmann and James B. Orlin},
     239  title =        {Finding minimum cost to time ratio cycles with small
     240                  integral transit times},
     241  journal =      {Networks},
     242  year =         1993,
     243  volume =       23,
     244  pages =        {567-574}
    214245}
    215246
     
    226257}
    227258
     259@article{dasdan04experimental,
     260  author =       {Ali Dasdan},
     261  title =        {Experimental analysis of the fastest optimum cycle
     262                  ratio and mean algorithms},
     263  journal =      {ACM Trans. Des. Autom. Electron. Syst.},
     264  year =         2004,
     265  volume =       9,
     266  issue =        4,
     267  pages =        {385-418}
     268}
     269
    228270
    229271%%%%% Minimum cost flow algorithms %%%%%
     
    298340  address =      {Dublin, Ireland},
    299341  year =         1991,
    300   month =        sep,
    301 }
     342  month =        sep
     343}
     344
     345%%%%% Other algorithms %%%%%
     346
     347@article{grosso08maxclique,
     348  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
     349  title =        {Simple ingredients leading to very efficient
     350                  heuristics for the maximum clique problem},
     351  journal =      {Journal of Heuristics},
     352  year =         2008,
     353  volume =       14,
     354  number =       6,
     355  pages =        {587--612}
     356}
  • lemon/CMakeLists.txt

    r1113 r1230  
    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
     
    3737IF(LEMON_HAVE_CPLEX)
    3838  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    39   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     39  INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
    4040ENDIF()
    4141
  • lemon/assert.h

    r463 r1242  
    200200                             ::lemon::_assert_bits::cstringify(msg),    \
    201201                             #exp), 0)))
    202 #    if LEMON_ENABLE_DEBUG
     202#    if defined LEMON_ENABLE_DEBUG
    203203#      define LEMON_DEBUG(exp, msg)                                     \
    204204         (static_cast<void> (!!(exp) ? 0 : (                            \
  • lemon/base.cc

    r554 r1222  
    2222#include<lemon/tolerance.h>
    2323#include<lemon/core.h>
     24#include<lemon/time_measure.h>
    2425namespace lemon {
    2526
     
    3233#endif
    3334
     35  TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
     36
    3437} //namespace lemon
  • lemon/bellman_ford.h

    r960 r1254  
    150150  /// This class provides an efficient implementation of the Bellman-Ford
    151151  /// algorithm. The maximum time complexity of the algorithm is
    152   /// <tt>O(ne)</tt>.
     152  /// <tt>O(nm)</tt>.
    153153  ///
    154154  /// The Bellman-Ford algorithm solves the single-source shortest path
     
    201201    /// The type of the paths.
    202202    typedef PredMapPath<Digraph, PredMap> Path;
    203     ///\brief The \ref BellmanFordDefaultOperationTraits
     203    ///\brief The \ref lemon::BellmanFordDefaultOperationTraits
    204204    /// "operation traits class" of the algorithm.
    205205    typedef typename TR::OperationTraits OperationTraits;
    206206
    207     ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
     207    ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
     208    ///of the algorithm.
    208209    typedef TR Traits;
    209210
  • lemon/bfs.h

    r1127 r1250  
    153153    typedef PredMapPath<Digraph, PredMap> Path;
    154154
    155     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
    156156    typedef TR Traits;
    157157
  • lemon/bits/alteration_notifier.h

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

    r1159 r1195  
    747747  };
    748748
     749  // \ingroup _graphbits
     750  //
     751  // \brief Extender for the BpGraphs
     752  template <typename Base>
     753  class BpGraphExtender : public Base {
     754    typedef Base Parent;
     755
     756  public:
     757
     758    typedef BpGraphExtender BpGraph;
     759
     760    typedef True UndirectedTag;
     761
     762    typedef typename Parent::Node Node;
     763    typedef typename Parent::RedNode RedNode;
     764    typedef typename Parent::BlueNode BlueNode;
     765    typedef typename Parent::Arc Arc;
     766    typedef typename Parent::Edge Edge;
     767
     768    // BpGraph extension
     769
     770    using Parent::first;
     771    using Parent::next;
     772    using Parent::id;
     773
     774    int maxId(Node) const {
     775      return Parent::maxNodeId();
     776    }
     777
     778    int maxId(RedNode) const {
     779      return Parent::maxRedId();
     780    }
     781
     782    int maxId(BlueNode) const {
     783      return Parent::maxBlueId();
     784    }
     785
     786    int maxId(Arc) const {
     787      return Parent::maxArcId();
     788    }
     789
     790    int maxId(Edge) const {
     791      return Parent::maxEdgeId();
     792    }
     793
     794    static Node fromId(int id, Node) {
     795      return Parent::nodeFromId(id);
     796    }
     797
     798    static Arc fromId(int id, Arc) {
     799      return Parent::arcFromId(id);
     800    }
     801
     802    static Edge fromId(int id, Edge) {
     803      return Parent::edgeFromId(id);
     804    }
     805
     806    Node u(Edge e) const { return this->redNode(e); }
     807    Node v(Edge e) const { return this->blueNode(e); }
     808
     809    Node oppositeNode(const Node &n, const Edge &e) const {
     810      if( n == u(e))
     811        return v(e);
     812      else if( n == v(e))
     813        return u(e);
     814      else
     815        return INVALID;
     816    }
     817
     818    Arc oppositeArc(const Arc &arc) const {
     819      return Parent::direct(arc, !Parent::direction(arc));
     820    }
     821
     822    using Parent::direct;
     823    Arc direct(const Edge &edge, const Node &node) const {
     824      return Parent::direct(edge, Parent::redNode(edge) == node);
     825    }
     826
     827    RedNode asRedNode(const Node& node) const {
     828      if (node == INVALID || Parent::blue(node)) {
     829        return INVALID;
     830      } else {
     831        return Parent::asRedNodeUnsafe(node);
     832      }
     833    }
     834
     835    BlueNode asBlueNode(const Node& node) const {
     836      if (node == INVALID || Parent::red(node)) {
     837        return INVALID;
     838      } else {
     839        return Parent::asBlueNodeUnsafe(node);
     840      }
     841    }
     842
     843    // Alterable extension
     844
     845    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
     846    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
     847    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
     848    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
     849    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
     850
     851
     852  protected:
     853
     854    mutable NodeNotifier node_notifier;
     855    mutable RedNodeNotifier red_node_notifier;
     856    mutable BlueNodeNotifier blue_node_notifier;
     857    mutable ArcNotifier arc_notifier;
     858    mutable EdgeNotifier edge_notifier;
     859
     860  public:
     861
     862    NodeNotifier& notifier(Node) const {
     863      return node_notifier;
     864    }
     865
     866    RedNodeNotifier& notifier(RedNode) const {
     867      return red_node_notifier;
     868    }
     869
     870    BlueNodeNotifier& notifier(BlueNode) const {
     871      return blue_node_notifier;
     872    }
     873
     874    ArcNotifier& notifier(Arc) const {
     875      return arc_notifier;
     876    }
     877
     878    EdgeNotifier& notifier(Edge) const {
     879      return edge_notifier;
     880    }
     881
     882
     883
     884    class NodeIt : public Node {
     885      const BpGraph* _graph;
     886    public:
     887
     888      NodeIt() {}
     889
     890      NodeIt(Invalid i) : Node(i) { }
     891
     892      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
     893        _graph->first(static_cast<Node&>(*this));
     894      }
     895
     896      NodeIt(const BpGraph& graph, const Node& node)
     897        : Node(node), _graph(&graph) {}
     898
     899      NodeIt& operator++() {
     900        _graph->next(*this);
     901        return *this;
     902      }
     903
     904    };
     905
     906    class RedNodeIt : public RedNode {
     907      const BpGraph* _graph;
     908    public:
     909
     910      RedNodeIt() {}
     911
     912      RedNodeIt(Invalid i) : RedNode(i) { }
     913
     914      explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
     915        _graph->first(static_cast<RedNode&>(*this));
     916      }
     917
     918      RedNodeIt(const BpGraph& graph, const RedNode& node)
     919        : RedNode(node), _graph(&graph) {}
     920
     921      RedNodeIt& operator++() {
     922        _graph->next(static_cast<RedNode&>(*this));
     923        return *this;
     924      }
     925
     926    };
     927
     928    class BlueNodeIt : public BlueNode {
     929      const BpGraph* _graph;
     930    public:
     931
     932      BlueNodeIt() {}
     933
     934      BlueNodeIt(Invalid i) : BlueNode(i) { }
     935
     936      explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
     937        _graph->first(static_cast<BlueNode&>(*this));
     938      }
     939
     940      BlueNodeIt(const BpGraph& graph, const BlueNode& node)
     941        : BlueNode(node), _graph(&graph) {}
     942
     943      BlueNodeIt& operator++() {
     944        _graph->next(static_cast<BlueNode&>(*this));
     945        return *this;
     946      }
     947
     948    };
     949
     950
     951    class ArcIt : public Arc {
     952      const BpGraph* _graph;
     953    public:
     954
     955      ArcIt() { }
     956
     957      ArcIt(Invalid i) : Arc(i) { }
     958
     959      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
     960        _graph->first(static_cast<Arc&>(*this));
     961      }
     962
     963      ArcIt(const BpGraph& graph, const Arc& arc) :
     964        Arc(arc), _graph(&graph) { }
     965
     966      ArcIt& operator++() {
     967        _graph->next(*this);
     968        return *this;
     969      }
     970
     971    };
     972
     973
     974    class OutArcIt : public Arc {
     975      const BpGraph* _graph;
     976    public:
     977
     978      OutArcIt() { }
     979
     980      OutArcIt(Invalid i) : Arc(i) { }
     981
     982      OutArcIt(const BpGraph& graph, const Node& node)
     983        : _graph(&graph) {
     984        _graph->firstOut(*this, node);
     985      }
     986
     987      OutArcIt(const BpGraph& graph, const Arc& arc)
     988        : Arc(arc), _graph(&graph) {}
     989
     990      OutArcIt& operator++() {
     991        _graph->nextOut(*this);
     992        return *this;
     993      }
     994
     995    };
     996
     997
     998    class InArcIt : public Arc {
     999      const BpGraph* _graph;
     1000    public:
     1001
     1002      InArcIt() { }
     1003
     1004      InArcIt(Invalid i) : Arc(i) { }
     1005
     1006      InArcIt(const BpGraph& graph, const Node& node)
     1007        : _graph(&graph) {
     1008        _graph->firstIn(*this, node);
     1009      }
     1010
     1011      InArcIt(const BpGraph& graph, const Arc& arc) :
     1012        Arc(arc), _graph(&graph) {}
     1013
     1014      InArcIt& operator++() {
     1015        _graph->nextIn(*this);
     1016        return *this;
     1017      }
     1018
     1019    };
     1020
     1021
     1022    class EdgeIt : public Parent::Edge {
     1023      const BpGraph* _graph;
     1024    public:
     1025
     1026      EdgeIt() { }
     1027
     1028      EdgeIt(Invalid i) : Edge(i) { }
     1029
     1030      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
     1031        _graph->first(static_cast<Edge&>(*this));
     1032      }
     1033
     1034      EdgeIt(const BpGraph& graph, const Edge& edge) :
     1035        Edge(edge), _graph(&graph) { }
     1036
     1037      EdgeIt& operator++() {
     1038        _graph->next(*this);
     1039        return *this;
     1040      }
     1041
     1042    };
     1043
     1044    class IncEdgeIt : public Parent::Edge {
     1045      friend class BpGraphExtender;
     1046      const BpGraph* _graph;
     1047      bool _direction;
     1048    public:
     1049
     1050      IncEdgeIt() { }
     1051
     1052      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
     1053
     1054      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
     1055        _graph->firstInc(*this, _direction, node);
     1056      }
     1057
     1058      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
     1059        : _graph(&graph), Edge(edge) {
     1060        _direction = (_graph->source(edge) == node);
     1061      }
     1062
     1063      IncEdgeIt& operator++() {
     1064        _graph->nextInc(*this, _direction);
     1065        return *this;
     1066      }
     1067    };
     1068
     1069    // \brief Base node of the iterator
     1070    //
     1071    // Returns the base node (ie. the source in this case) of the iterator
     1072    Node baseNode(const OutArcIt &arc) const {
     1073      return Parent::source(static_cast<const Arc&>(arc));
     1074    }
     1075    // \brief Running node of the iterator
     1076    //
     1077    // Returns the running node (ie. the target in this case) of the
     1078    // iterator
     1079    Node runningNode(const OutArcIt &arc) const {
     1080      return Parent::target(static_cast<const Arc&>(arc));
     1081    }
     1082
     1083    // \brief Base node of the iterator
     1084    //
     1085    // Returns the base node (ie. the target in this case) of the iterator
     1086    Node baseNode(const InArcIt &arc) const {
     1087      return Parent::target(static_cast<const Arc&>(arc));
     1088    }
     1089    // \brief Running node of the iterator
     1090    //
     1091    // Returns the running node (ie. the source in this case) of the
     1092    // iterator
     1093    Node runningNode(const InArcIt &arc) const {
     1094      return Parent::source(static_cast<const Arc&>(arc));
     1095    }
     1096
     1097    // Base node of the iterator
     1098    //
     1099    // Returns the base node of the iterator
     1100    Node baseNode(const IncEdgeIt &edge) const {
     1101      return edge._direction ? this->u(edge) : this->v(edge);
     1102    }
     1103    // Running node of the iterator
     1104    //
     1105    // Returns the running node of the iterator
     1106    Node runningNode(const IncEdgeIt &edge) const {
     1107      return edge._direction ? this->v(edge) : this->u(edge);
     1108    }
     1109
     1110    // Mappable extension
     1111
     1112    template <typename _Value>
     1113    class NodeMap
     1114      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
     1115      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
     1116
     1117    public:
     1118      explicit NodeMap(const BpGraph& bpgraph)
     1119        : Parent(bpgraph) {}
     1120      NodeMap(const BpGraph& bpgraph, const _Value& value)
     1121        : Parent(bpgraph, value) {}
     1122
     1123    private:
     1124      NodeMap& operator=(const NodeMap& cmap) {
     1125        return operator=<NodeMap>(cmap);
     1126      }
     1127
     1128      template <typename CMap>
     1129      NodeMap& operator=(const CMap& cmap) {
     1130        Parent::operator=(cmap);
     1131        return *this;
     1132      }
     1133
     1134    };
     1135
     1136    template <typename _Value>
     1137    class RedNodeMap
     1138      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
     1139      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
     1140
     1141    public:
     1142      explicit RedNodeMap(const BpGraph& bpgraph)
     1143        : Parent(bpgraph) {}
     1144      RedNodeMap(const BpGraph& bpgraph, const _Value& value)
     1145        : Parent(bpgraph, value) {}
     1146
     1147    private:
     1148      RedNodeMap& operator=(const RedNodeMap& cmap) {
     1149        return operator=<RedNodeMap>(cmap);
     1150      }
     1151
     1152      template <typename CMap>
     1153      RedNodeMap& operator=(const CMap& cmap) {
     1154        Parent::operator=(cmap);
     1155        return *this;
     1156      }
     1157
     1158    };
     1159
     1160    template <typename _Value>
     1161    class BlueNodeMap
     1162      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
     1163      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
     1164
     1165    public:
     1166      explicit BlueNodeMap(const BpGraph& bpgraph)
     1167        : Parent(bpgraph) {}
     1168      BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
     1169        : Parent(bpgraph, value) {}
     1170
     1171    private:
     1172      BlueNodeMap& operator=(const BlueNodeMap& cmap) {
     1173        return operator=<BlueNodeMap>(cmap);
     1174      }
     1175
     1176      template <typename CMap>
     1177      BlueNodeMap& operator=(const CMap& cmap) {
     1178        Parent::operator=(cmap);
     1179        return *this;
     1180      }
     1181
     1182    };
     1183
     1184    template <typename _Value>
     1185    class ArcMap
     1186      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
     1187      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
     1188
     1189    public:
     1190      explicit ArcMap(const BpGraph& graph)
     1191        : Parent(graph) {}
     1192      ArcMap(const BpGraph& graph, const _Value& value)
     1193        : Parent(graph, value) {}
     1194
     1195    private:
     1196      ArcMap& operator=(const ArcMap& cmap) {
     1197        return operator=<ArcMap>(cmap);
     1198      }
     1199
     1200      template <typename CMap>
     1201      ArcMap& operator=(const CMap& cmap) {
     1202        Parent::operator=(cmap);
     1203        return *this;
     1204      }
     1205    };
     1206
     1207
     1208    template <typename _Value>
     1209    class EdgeMap
     1210      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
     1211      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
     1212
     1213    public:
     1214      explicit EdgeMap(const BpGraph& graph)
     1215        : Parent(graph) {}
     1216
     1217      EdgeMap(const BpGraph& graph, const _Value& value)
     1218        : Parent(graph, value) {}
     1219
     1220    private:
     1221      EdgeMap& operator=(const EdgeMap& cmap) {
     1222        return operator=<EdgeMap>(cmap);
     1223      }
     1224
     1225      template <typename CMap>
     1226      EdgeMap& operator=(const CMap& cmap) {
     1227        Parent::operator=(cmap);
     1228        return *this;
     1229      }
     1230
     1231    };
     1232
     1233    // Alteration extension
     1234
     1235    RedNode addRedNode() {
     1236      RedNode node = Parent::addRedNode();
     1237      notifier(RedNode()).add(node);
     1238      notifier(Node()).add(node);
     1239      return node;
     1240    }
     1241
     1242    BlueNode addBlueNode() {
     1243      BlueNode node = Parent::addBlueNode();
     1244      notifier(BlueNode()).add(node);
     1245      notifier(Node()).add(node);
     1246      return node;
     1247    }
     1248
     1249    Edge addEdge(const RedNode& from, const BlueNode& to) {
     1250      Edge edge = Parent::addEdge(from, to);
     1251      notifier(Edge()).add(edge);
     1252      std::vector<Arc> av;
     1253      av.push_back(Parent::direct(edge, true));
     1254      av.push_back(Parent::direct(edge, false));
     1255      notifier(Arc()).add(av);
     1256      return edge;
     1257    }
     1258
     1259    void clear() {
     1260      notifier(Arc()).clear();
     1261      notifier(Edge()).clear();
     1262      notifier(Node()).clear();
     1263      notifier(BlueNode()).clear();
     1264      notifier(RedNode()).clear();
     1265      Parent::clear();
     1266    }
     1267
     1268    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
     1269    void build(const BpGraph& graph, NodeRefMap& nodeRef,
     1270               EdgeRefMap& edgeRef) {
     1271      Parent::build(graph, nodeRef, edgeRef);
     1272      notifier(RedNode()).build();
     1273      notifier(BlueNode()).build();
     1274      notifier(Node()).build();
     1275      notifier(Edge()).build();
     1276      notifier(Arc()).build();
     1277    }
     1278
     1279    void erase(const Node& node) {
     1280      Arc arc;
     1281      Parent::firstOut(arc, node);
     1282      while (arc != INVALID ) {
     1283        erase(arc);
     1284        Parent::firstOut(arc, node);
     1285      }
     1286
     1287      Parent::firstIn(arc, node);
     1288      while (arc != INVALID ) {
     1289        erase(arc);
     1290        Parent::firstIn(arc, node);
     1291      }
     1292
     1293      if (Parent::red(node)) {
     1294        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
     1295      } else {
     1296        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
     1297      }
     1298
     1299      notifier(Node()).erase(node);
     1300      Parent::erase(node);
     1301    }
     1302
     1303    void erase(const Edge& edge) {
     1304      std::vector<Arc> av;
     1305      av.push_back(Parent::direct(edge, true));
     1306      av.push_back(Parent::direct(edge, false));
     1307      notifier(Arc()).erase(av);
     1308      notifier(Edge()).erase(edge);
     1309      Parent::erase(edge);
     1310    }
     1311
     1312    BpGraphExtender() {
     1313      red_node_notifier.setContainer(*this);
     1314      blue_node_notifier.setContainer(*this);
     1315      node_notifier.setContainer(*this);
     1316      arc_notifier.setContainer(*this);
     1317      edge_notifier.setContainer(*this);
     1318    }
     1319
     1320    ~BpGraphExtender() {
     1321      edge_notifier.clear();
     1322      arc_notifier.clear();
     1323      node_notifier.clear();
     1324      blue_node_notifier.clear();
     1325      red_node_notifier.clear();
     1326    }
     1327
     1328  };
     1329
    7491330}
    7501331
  • lemon/bits/traits.h

    r663 r1194  
    149149        : Parent(_digraph, _value) {}
    150150    };
     151
     152  };
     153
     154  template <typename GR, typename Enable = void>
     155  struct RedNodeNotifierIndicator {
     156    typedef InvalidType Type;
     157  };
     158  template <typename GR>
     159  struct RedNodeNotifierIndicator<
     160    GR,
     161    typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type
     162  > {
     163    typedef typename GR::RedNodeNotifier Type;
     164  };
     165
     166  template <typename GR>
     167  class ItemSetTraits<GR, typename GR::RedNode> {
     168  public:
     169
     170    typedef GR BpGraph;
     171    typedef GR Graph;
     172    typedef GR Digraph;
     173
     174    typedef typename GR::RedNode Item;
     175    typedef typename GR::RedNodeIt ItemIt;
     176
     177    typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
     178
     179    template <typename V>
     180    class Map : public GR::template RedNodeMap<V> {
     181      typedef typename GR::template RedNodeMap<V> Parent;
     182
     183    public:
     184      typedef typename GR::template RedNodeMap<V> Type;
     185      typedef typename Parent::Value Value;
     186
     187      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     188      Map(const GR& _bpgraph, const Value& _value)
     189        : Parent(_bpgraph, _value) {}
     190
     191     };
     192
     193  };
     194
     195  template <typename GR, typename Enable = void>
     196  struct BlueNodeNotifierIndicator {
     197    typedef InvalidType Type;
     198  };
     199  template <typename GR>
     200  struct BlueNodeNotifierIndicator<
     201    GR,
     202    typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
     203  > {
     204    typedef typename GR::BlueNodeNotifier Type;
     205  };
     206
     207  template <typename GR>
     208  class ItemSetTraits<GR, typename GR::BlueNode> {
     209  public:
     210
     211    typedef GR BpGraph;
     212    typedef GR Graph;
     213    typedef GR Digraph;
     214
     215    typedef typename GR::BlueNode Item;
     216    typedef typename GR::BlueNodeIt ItemIt;
     217
     218    typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
     219
     220    template <typename V>
     221    class Map : public GR::template BlueNodeMap<V> {
     222      typedef typename GR::template BlueNodeMap<V> Parent;
     223
     224    public:
     225      typedef typename GR::template BlueNodeMap<V> Type;
     226      typedef typename Parent::Value Value;
     227
     228      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
     229      Map(const GR& _bpgraph, const Value& _value)
     230        : Parent(_bpgraph, _value) {}
     231
     232     };
    151233
    152234  };
  • lemon/bits/windows.cc

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

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

    r956 r1254  
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
     74  ///
     75  /// This algorithm is typically slower than \ref CostScaling and
     76  /// \ref NetworkSimplex, but in special cases, it can be more
     77  /// efficient than them.
     78  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7279  ///
    7380  /// Most of the parameters of the problem (except for the digraph)
     
    8794  /// consider to use the named template parameters instead.
    8895  ///
    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.
     96  /// \warning Both \c V and \c C must be signed number types.
     97  /// \warning Capacity bounds and supply values must be integer, but
     98  /// arc costs can be arbitrary real numbers.
     99  /// \warning This algorithm does not support negative costs for
     100  /// arcs having infinite upper bound.
    93101#ifdef DOXYGEN
    94102  template <typename GR, typename V, typename C, typename TR>
     
    111119    typedef typename TR::Heap Heap;
    112120
    113     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     121    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     122    /// of the algorithm
    114123    typedef TR Traits;
    115124
     
    423432    ///
    424433    /// 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
     434    /// with a map in which \c k is assigned to \c s, \c -k is
    426435    /// assigned to \c t and all other nodes have zero supply value.
    427436    ///
     
    638647    ///
    639648    /// This function returns the total cost of the found flow.
    640     /// Its complexity is O(e).
     649    /// Its complexity is O(m).
    641650    ///
    642651    /// \note The return type of the function can be specified as a
     
    676685    }
    677686
    678     /// \brief Return the flow map (the primal solution).
     687    /// \brief Copy the flow values (the primal solution) into the
     688    /// given map.
    679689    ///
    680690    /// This function copies the flow value on each arc into the given
     
    700710    }
    701711
    702     /// \brief Return the potential map (the dual solution).
     712    /// \brief Copy the potential values (the dual solution) into the
     713    /// given map.
    703714    ///
    704715    /// This function copies the potential (dual value) of each node
     
    729740      }
    730741      if (_sum_supply > 0) return INFEASIBLE;
     742
     743      // Check lower and upper bounds
     744      LEMON_DEBUG(checkBoundMaps(),
     745          "Upper bounds must be greater or equal to the lower bounds");
     746
    731747
    732748      // Initialize vectors
     
    822838
    823839      return OPTIMAL;
     840    }
     841   
     842    // Check if the upper bound is greater or equal to the lower bound
     843    // on each arc.
     844    bool checkBoundMaps() {
     845      for (int j = 0; j != _res_arc_num; ++j) {
     846        if (_upper[j] < _lower[j]) return false;
     847      }
     848      return true;
    824849    }
    825850
  • lemon/cbc.h

    r956 r1232  
    1717 */
    1818
    19 // -*- C++ -*-
    2019#ifndef LEMON_CBC_H
    2120#define LEMON_CBC_H
  • lemon/circulation.h

    r1159 r1250  
    196196  public:
    197197
    198     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
     198    /// \brief The \ref lemon::CirculationDefaultTraits "traits class"
     199    /// of the algorithm.
    199200    typedef TR Traits;
    200201    ///The type of the digraph the algorithm runs on.
  • lemon/concepts/digraph.h

    r1259 r1261  
    410410      /// \brief The base node of the iterator.
    411411      ///
    412       /// Returns the base node of the given incomming arc iterator
     412      /// Returns the base node of the given incoming arc iterator
    413413      /// (i.e. the target node of the corresponding arc).
    414414      Node baseNode(InArcIt) const { return INVALID; }
     
    416416      /// \brief The running node of the iterator.
    417417      ///
    418       /// Returns the running node of the given incomming arc iterator
     418      /// Returns the running node of the given incoming arc iterator
    419419      /// (i.e. the source node of the corresponding arc).
    420420      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r1259 r1261  
    7373    class Graph {
    7474    private:
    75       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use GraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
     78      /// Use GraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080
     
    758758      /// \brief The base node of the iterator.
    759759      ///
    760       /// Returns the base node of the given incomming arc iterator
     760      /// Returns the base node of the given incoming arc iterator
    761761      /// (i.e. the target node of the corresponding arc).
    762762      Node baseNode(InArcIt) const { return INVALID; }
     
    764764      /// \brief The running node of the iterator.
    765765      ///
    766       /// Returns the running node of the given incomming arc iterator
     766      /// Returns the running node of the given incoming arc iterator
    767767      /// (i.e. the source node of the corresponding arc).
    768768      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1259 r1261  
    300300    };
    301301
     302    /// \brief Base skeleton class for undirected bipartite graphs.
     303    ///
     304    /// This class describes the base interface of undirected
     305    /// bipartite graph types.  All bipartite graph %concepts have to
     306    /// conform to this class.  It extends the interface of \ref
     307    /// BaseGraphComponent with an \c Edge type and functions to get
     308    /// the end nodes of edges, to convert from arcs to edges and to
     309    /// get both direction of edges.
     310    class BaseBpGraphComponent : public BaseGraphComponent {
     311    public:
     312
     313      typedef BaseBpGraphComponent BpGraph;
     314
     315      typedef BaseDigraphComponent::Node Node;
     316      typedef BaseDigraphComponent::Arc Arc;
     317
     318      /// \brief Class to represent red nodes.
     319      ///
     320      /// This class represents the red nodes of the graph. The red
     321      /// nodes can also be used as normal nodes.
     322      class RedNode : public Node {
     323        typedef Node Parent;
     324
     325      public:
     326        /// \brief Default constructor.
     327        ///
     328        /// Default constructor.
     329        /// \warning The default constructor is not required to set
     330        /// the item to some well-defined value. So you should consider it
     331        /// as uninitialized.
     332        RedNode() {}
     333
     334        /// \brief Copy constructor.
     335        ///
     336        /// Copy constructor.
     337        RedNode(const RedNode &) : Parent() {}
     338
     339        /// \brief Constructor for conversion from \c INVALID.
     340        ///
     341        /// Constructor for conversion from \c INVALID.
     342        /// It initializes the item to be invalid.
     343        /// \sa Invalid for more details.
     344        RedNode(Invalid) {}
     345      };
     346
     347      /// \brief Class to represent blue nodes.
     348      ///
     349      /// This class represents the blue nodes of the graph. The blue
     350      /// nodes can also be used as normal nodes.
     351      class BlueNode : public Node {
     352        typedef Node Parent;
     353
     354      public:
     355        /// \brief Default constructor.
     356        ///
     357        /// Default constructor.
     358        /// \warning The default constructor is not required to set
     359        /// the item to some well-defined value. So you should consider it
     360        /// as uninitialized.
     361        BlueNode() {}
     362
     363        /// \brief Copy constructor.
     364        ///
     365        /// Copy constructor.
     366        BlueNode(const BlueNode &) : Parent() {}
     367
     368        /// \brief Constructor for conversion from \c INVALID.
     369        ///
     370        /// Constructor for conversion from \c INVALID.
     371        /// It initializes the item to be invalid.
     372        /// \sa Invalid for more details.
     373        BlueNode(Invalid) {}
     374
     375        /// \brief Constructor for conversion from a node.
     376        ///
     377        /// Constructor for conversion from a node. The conversion can
     378        /// be invalid, since the Node can be member of the red
     379        /// set.
     380        BlueNode(const Node&) {}
     381      };
     382
     383      /// \brief Gives back %true for red nodes.
     384      ///
     385      /// Gives back %true for red nodes.
     386      bool red(const Node&) const { return true; }
     387
     388      /// \brief Gives back %true for blue nodes.
     389      ///
     390      /// Gives back %true for blue nodes.
     391      bool blue(const Node&) const { return true; }
     392
     393      /// \brief Gives back the red end node of the edge.
     394      ///
     395      /// Gives back the red end node of the edge.
     396      RedNode redNode(const Edge&) const { return RedNode(); }
     397
     398      /// \brief Gives back the blue end node of the edge.
     399      ///
     400      /// Gives back the blue end node of the edge.
     401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
     402
     403      /// \brief Converts the node to red node object.
     404      ///
     405      /// This function converts unsafely the node to red node
     406      /// object. It should be called only if the node is from the red
     407      /// partition or INVALID.
     408      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
     409
     410      /// \brief Converts the node to blue node object.
     411      ///
     412      /// This function converts unsafely the node to blue node
     413      /// object. It should be called only if the node is from the red
     414      /// partition or INVALID.
     415      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
     416
     417      /// \brief Converts the node to red node object.
     418      ///
     419      /// This function converts safely the node to red node
     420      /// object. If the node is not from the red partition, then it
     421      /// returns INVALID.
     422      RedNode asRedNode(const Node&) const { return RedNode(); }
     423
     424      /// \brief Converts the node to blue node object.
     425      ///
     426      /// This function converts unsafely the node to blue node
     427      /// object. If the node is not from the blue partition, then it
     428      /// returns INVALID.
     429      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
     430
     431      template <typename _BpGraph>
     432      struct Constraints {
     433        typedef typename _BpGraph::Node Node;
     434        typedef typename _BpGraph::RedNode RedNode;
     435        typedef typename _BpGraph::BlueNode BlueNode;
     436        typedef typename _BpGraph::Arc Arc;
     437        typedef typename _BpGraph::Edge Edge;
     438
     439        void constraints() {
     440          checkConcept<BaseGraphComponent, _BpGraph>();
     441          checkConcept<GraphItem<'n'>, RedNode>();
     442          checkConcept<GraphItem<'n'>, BlueNode>();
     443          {
     444            Node n;
     445            RedNode rn;
     446            BlueNode bn;
     447            Node rnan = rn;
     448            Node bnan = bn;
     449            Edge e;
     450            bool b;
     451            b = bpgraph.red(rnan);
     452            b = bpgraph.blue(bnan);
     453            rn = bpgraph.redNode(e);
     454            bn = bpgraph.blueNode(e);
     455            rn = bpgraph.asRedNodeUnsafe(rnan);
     456            bn = bpgraph.asBlueNodeUnsafe(bnan);
     457            rn = bpgraph.asRedNode(rnan);
     458            bn = bpgraph.asBlueNode(bnan);
     459            ignore_unused_variable_warning(b);
     460          }
     461        }
     462
     463        const _BpGraph& bpgraph;
     464      };
     465
     466    };
     467
    302468    /// \brief Skeleton class for \e idable directed graphs.
    303469    ///
     
    432598    };
    433599
     600    /// \brief Skeleton class for \e idable undirected bipartite graphs.
     601    ///
     602    /// This class describes the interface of \e idable undirected
     603    /// bipartite graphs. It extends \ref IDableGraphComponent with
     604    /// the core ID functions of undirected bipartite graphs. Beside
     605    /// the regular node ids, this class also provides ids within the
     606    /// the red and blue sets of the nodes. This concept is part of
     607    /// the BpGraph concept.
     608    template <typename BAS = BaseBpGraphComponent>
     609    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
     610    public:
     611
     612      typedef BAS Base;
     613      typedef IDableGraphComponent<BAS> Parent;
     614      typedef typename Base::Node Node;
     615      typedef typename Base::RedNode RedNode;
     616      typedef typename Base::BlueNode BlueNode;
     617
     618      using Parent::id;
     619
     620      /// \brief Return a unique integer id for the given node in the red set.
     621      ///
     622      /// Return a unique integer id for the given node in the red set.
     623      int id(const RedNode&) const { return -1; }
     624
     625      /// \brief Return a unique integer id for the given node in the blue set.
     626      ///
     627      /// Return a unique integer id for the given node in the blue set.
     628      int id(const BlueNode&) const { return -1; }
     629
     630      /// \brief Return an integer greater or equal to the maximum
     631      /// node id in the red set.
     632      ///
     633      /// Return an integer greater or equal to the maximum
     634      /// node id in the red set.
     635      int maxRedId() const { return -1; }
     636
     637      /// \brief Return an integer greater or equal to the maximum
     638      /// node id in the blue set.
     639      ///
     640      /// Return an integer greater or equal to the maximum
     641      /// node id in the blue set.
     642      int maxBlueId() const { return -1; }
     643
     644      template <typename _BpGraph>
     645      struct Constraints {
     646
     647        void constraints() {
     648          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
     649          typename _BpGraph::Node node;
     650          typename _BpGraph::RedNode red;
     651          typename _BpGraph::BlueNode blue;
     652          int rid = bpgraph.id(red);
     653          int bid = bpgraph.id(blue);
     654          rid = bpgraph.maxRedId();
     655          bid = bpgraph.maxBlueId();
     656          ignore_unused_variable_warning(rid);
     657          ignore_unused_variable_warning(bid);
     658        }
     659
     660        const _BpGraph& bpgraph;
     661      };
     662    };
     663
    434664    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    435665    ///
     
    646876      void next(Arc&) const {}
    647877
    648       /// \brief Return the first arc incomming to the given node.
    649       ///
    650       /// This function gives back the first arc incomming to the
     878      /// \brief Return the first arc incoming to the given node.
     879      ///
     880      /// This function gives back the first arc incoming to the
    651881      /// given node.
    652882      void firstIn(Arc&, const Node&) const {}
    653883
    654       /// \brief Return the next arc incomming to the given node.
    655       ///
    656       /// This function gives back the next arc incomming to the
     884      /// \brief Return the next arc incoming to the given node.
     885      ///
     886      /// This function gives back the next arc incoming to the
    657887      /// given node.
    658888      void nextIn(Arc&) const {}
     
    9051135    };
    9061136
     1137    /// \brief Skeleton class for iterable undirected bipartite graphs.
     1138    ///
     1139    /// This class describes the interface of iterable undirected
     1140    /// bipartite graphs. It extends \ref IterableGraphComponent with
     1141    /// the core iterable interface of undirected bipartite graphs.
     1142    /// This concept is part of the BpGraph concept.
     1143    template <typename BAS = BaseBpGraphComponent>
     1144    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
     1145    public:
     1146
     1147      typedef BAS Base;
     1148      typedef typename Base::Node Node;
     1149      typedef typename Base::RedNode RedNode;
     1150      typedef typename Base::BlueNode BlueNode;
     1151      typedef typename Base::Arc Arc;
     1152      typedef typename Base::Edge Edge;
     1153     
     1154      typedef IterableBpGraphComponent BpGraph;
     1155
     1156      using IterableGraphComponent<BAS>::first;
     1157      using IterableGraphComponent<BAS>::next;
     1158
     1159      /// \name Base Iteration
     1160      ///
     1161      /// This interface provides functions for iteration on red and blue nodes.
     1162      ///
     1163      /// @{
     1164
     1165      /// \brief Return the first red node.
     1166      ///
     1167      /// This function gives back the first red node in the iteration order.
     1168      void first(RedNode&) const {}
     1169
     1170      /// \brief Return the next red node.
     1171      ///
     1172      /// This function gives back the next red node in the iteration order.
     1173      void next(RedNode&) const {}
     1174
     1175      /// \brief Return the first blue node.
     1176      ///
     1177      /// This function gives back the first blue node in the iteration order.
     1178      void first(BlueNode&) const {}
     1179
     1180      /// \brief Return the next blue node.
     1181      ///
     1182      /// This function gives back the next blue node in the iteration order.
     1183      void next(BlueNode&) const {}
     1184
     1185
     1186      /// @}
     1187
     1188      /// \name Class Based Iteration
     1189      ///
     1190      /// This interface provides iterator classes for red and blue nodes.
     1191      ///
     1192      /// @{
     1193
     1194      /// \brief This iterator goes through each red node.
     1195      ///
     1196      /// This iterator goes through each red node.
     1197      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
     1198
     1199      /// \brief This iterator goes through each blue node.
     1200      ///
     1201      /// This iterator goes through each blue node.
     1202      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
     1203
     1204      /// @}
     1205
     1206      template <typename _BpGraph>
     1207      struct Constraints {
     1208        void constraints() {
     1209          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
     1210
     1211          typename _BpGraph::RedNode rn(INVALID);
     1212          bpgraph.first(rn);
     1213          bpgraph.next(rn);
     1214          typename _BpGraph::BlueNode bn(INVALID);
     1215          bpgraph.first(bn);
     1216          bpgraph.next(bn);
     1217
     1218          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
     1219            typename _BpGraph::RedNodeIt>();
     1220          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
     1221            typename _BpGraph::BlueNodeIt>();
     1222        }
     1223
     1224        const _BpGraph& bpgraph;
     1225      };
     1226    };
     1227
    9071228    /// \brief Skeleton class for alterable directed graphs.
    9081229    ///
     
    9301251      ArcNotifier;
    9311252
     1253      mutable NodeNotifier node_notifier;
     1254      mutable ArcNotifier arc_notifier;
     1255
    9321256      /// \brief Return the node alteration notifier.
    9331257      ///
    9341258      /// This function gives back the node alteration notifier.
    9351259      NodeNotifier& notifier(Node) const {
    936          return NodeNotifier();
     1260        return node_notifier;
    9371261      }
    9381262
     
    9411265      /// This function gives back the arc alteration notifier.
    9421266      ArcNotifier& notifier(Arc) const {
    943         return ArcNotifier();
     1267        return arc_notifier;
    9441268      }
    9451269
     
    9771301
    9781302      typedef BAS Base;
     1303      typedef AlterableDigraphComponent<Base> Parent;
    9791304      typedef typename Base::Edge Edge;
    9801305
     
    9841309      EdgeNotifier;
    9851310
     1311      mutable EdgeNotifier edge_notifier;
     1312
     1313      using Parent::notifier;
     1314
    9861315      /// \brief Return the edge alteration notifier.
    9871316      ///
    9881317      /// This function gives back the edge alteration notifier.
    9891318      EdgeNotifier& notifier(Edge) const {
    990         return EdgeNotifier();
     1319        return edge_notifier;
    9911320      }
    9921321
     
    10021331        const _Graph& graph;
    10031332        Constraints() {}
     1333      };
     1334    };
     1335
     1336    /// \brief Skeleton class for alterable undirected bipartite graphs.
     1337    ///
     1338    /// This class describes the interface of alterable undirected
     1339    /// bipartite graphs. It extends \ref AlterableGraphComponent with
     1340    /// the alteration notifier interface of bipartite graphs. It
     1341    /// implements an observer-notifier pattern for the red and blue
     1342    /// nodes. More obsevers can be registered into the notifier and
     1343    /// whenever an alteration occured in the graph all the observers
     1344    /// will be notified about it.
     1345    template <typename BAS = BaseBpGraphComponent>
     1346    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
     1347    public:
     1348
     1349      typedef BAS Base;
     1350      typedef AlterableGraphComponent<Base> Parent;
     1351      typedef typename Base::RedNode RedNode;
     1352      typedef typename Base::BlueNode BlueNode;
     1353
     1354
     1355      /// Red node alteration notifier class.
     1356      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
     1357      RedNodeNotifier;
     1358
     1359      /// Blue node alteration notifier class.
     1360      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
     1361      BlueNodeNotifier;
     1362
     1363      mutable RedNodeNotifier red_node_notifier;
     1364      mutable BlueNodeNotifier blue_node_notifier;
     1365
     1366      using Parent::notifier;
     1367
     1368      /// \brief Return the red node alteration notifier.
     1369      ///
     1370      /// This function gives back the red node alteration notifier.
     1371      RedNodeNotifier& notifier(RedNode) const {
     1372        return red_node_notifier;
     1373      }
     1374
     1375      /// \brief Return the blue node alteration notifier.
     1376      ///
     1377      /// This function gives back the blue node alteration notifier.
     1378      BlueNodeNotifier& notifier(BlueNode) const {
     1379        return blue_node_notifier;
     1380      }
     1381
     1382      template <typename _BpGraph>
     1383      struct Constraints {
     1384        void constraints() {
     1385          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
     1386          typename _BpGraph::RedNodeNotifier& rnn
     1387            = bpgraph.notifier(typename _BpGraph::RedNode());
     1388          typename _BpGraph::BlueNodeNotifier& bnn
     1389            = bpgraph.notifier(typename _BpGraph::BlueNode());
     1390          ignore_unused_variable_warning(rnn);
     1391          ignore_unused_variable_warning(bnn);
     1392        }
     1393
     1394        const _BpGraph& bpgraph;
    10041395      };
    10051396    };
     
    13081699    };
    13091700
     1701    /// \brief Skeleton class for mappable undirected bipartite graphs.
     1702    ///
     1703    /// This class describes the interface of mappable undirected
     1704    /// bipartite graphs.  It extends \ref MappableGraphComponent with
     1705    /// the standard graph map class for red and blue nodes (\c
     1706    /// RedNodeMap and BlueNodeMap). This concept is part of the
     1707    /// BpGraph concept.
     1708    template <typename BAS = BaseBpGraphComponent>
     1709    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
     1710    public:
     1711
     1712      typedef BAS Base;
     1713      typedef typename Base::Node Node;
     1714
     1715      typedef MappableBpGraphComponent BpGraph;
     1716
     1717      /// \brief Standard graph map for the red nodes.
     1718      ///
     1719      /// Standard graph map for the red nodes.
     1720      /// It conforms to the ReferenceMap concept.
     1721      template <typename V>
     1722      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1723        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1724
     1725      public:
     1726        /// \brief Construct a new map.
     1727        ///
     1728        /// Construct a new map for the graph.
     1729        explicit RedNodeMap(const MappableBpGraphComponent& graph)
     1730          : Parent(graph) {}
     1731
     1732        /// \brief Construct a new map with default value.
     1733        ///
     1734        /// Construct a new map for the graph and initalize the values.
     1735        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
     1736          : Parent(graph, value) {}
     1737
     1738      private:
     1739        /// \brief Copy constructor.
     1740        ///
     1741        /// Copy Constructor.
     1742        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
     1743
     1744        /// \brief Assignment operator.
     1745        ///
     1746        /// Assignment operator.
     1747        template <typename CMap>
     1748        RedNodeMap& operator=(const CMap&) {
     1749          checkConcept<ReadMap<Node, V>, CMap>();
     1750          return *this;
     1751        }
     1752
     1753      };
     1754
     1755      /// \brief Standard graph map for the blue nodes.
     1756      ///
     1757      /// Standard graph map for the blue nodes.
     1758      /// It conforms to the ReferenceMap concept.
     1759      template <typename V>
     1760      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
     1761        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
     1762
     1763      public:
     1764        /// \brief Construct a new map.
     1765        ///
     1766        /// Construct a new map for the graph.
     1767        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
     1768          : Parent(graph) {}
     1769
     1770        /// \brief Construct a new map with default value.
     1771        ///
     1772        /// Construct a new map for the graph and initalize the values.
     1773        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
     1774          : Parent(graph, value) {}
     1775
     1776      private:
     1777        /// \brief Copy constructor.
     1778        ///
     1779        /// Copy Constructor.
     1780        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
     1781
     1782        /// \brief Assignment operator.
     1783        ///
     1784        /// Assignment operator.
     1785        template <typename CMap>
     1786        BlueNodeMap& operator=(const CMap&) {
     1787          checkConcept<ReadMap<Node, V>, CMap>();
     1788          return *this;
     1789        }
     1790
     1791      };
     1792
     1793
     1794      template <typename _BpGraph>
     1795      struct Constraints {
     1796
     1797        struct Dummy {
     1798          int value;
     1799          Dummy() : value(0) {}
     1800          Dummy(int _v) : value(_v) {}
     1801        };
     1802
     1803        void constraints() {
     1804          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
     1805
     1806          { // int map test
     1807            typedef typename _BpGraph::template RedNodeMap<int>
     1808              IntRedNodeMap;
     1809            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
     1810              IntRedNodeMap >();
     1811          } { // bool map test
     1812            typedef typename _BpGraph::template RedNodeMap<bool>
     1813              BoolRedNodeMap;
     1814            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
     1815              BoolRedNodeMap >();
     1816          } { // Dummy map test
     1817            typedef typename _BpGraph::template RedNodeMap<Dummy>
     1818              DummyRedNodeMap;
     1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
     1820              DummyRedNodeMap >();
     1821          }
     1822
     1823          { // int map test
     1824            typedef typename _BpGraph::template BlueNodeMap<int>
     1825              IntBlueNodeMap;
     1826            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
     1827              IntBlueNodeMap >();
     1828          } { // bool map test
     1829            typedef typename _BpGraph::template BlueNodeMap<bool>
     1830              BoolBlueNodeMap;
     1831            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
     1832              BoolBlueNodeMap >();
     1833          } { // Dummy map test
     1834            typedef typename _BpGraph::template BlueNodeMap<Dummy>
     1835              DummyBlueNodeMap;
     1836            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
     1837              DummyBlueNodeMap >();
     1838          }
     1839        }
     1840
     1841        const _BpGraph& bpgraph;
     1842      };
     1843    };
     1844
    13101845    /// \brief Skeleton class for extendable directed graphs.
    13111846    ///
     
    13981933    };
    13991934
     1935    /// \brief Skeleton class for extendable undirected bipartite graphs.
     1936    ///
     1937    /// This class describes the interface of extendable undirected
     1938    /// bipartite graphs. It extends \ref BaseGraphComponent with
     1939    /// functions for adding nodes and edges to the graph. This
     1940    /// concept requires \ref AlterableBpGraphComponent.
     1941    template <typename BAS = BaseBpGraphComponent>
     1942    class ExtendableBpGraphComponent : public BAS {
     1943    public:
     1944
     1945      typedef BAS Base;
     1946      typedef typename Base::Node Node;
     1947      typedef typename Base::RedNode RedNode;
     1948      typedef typename Base::BlueNode BlueNode;
     1949      typedef typename Base::Edge Edge;
     1950
     1951      /// \brief Add a new red node to the digraph.
     1952      ///
     1953      /// This function adds a red new node to the digraph.
     1954      RedNode addRedNode() {
     1955        return INVALID;
     1956      }
     1957
     1958      /// \brief Add a new blue node to the digraph.
     1959      ///
     1960      /// This function adds a blue new node to the digraph.
     1961      BlueNode addBlueNode() {
     1962        return INVALID;
     1963      }
     1964
     1965      /// \brief Add a new edge connecting the given two nodes.
     1966      ///
     1967      /// This function adds a new edge connecting the given two nodes
     1968      /// of the graph. The first node has to be a red node, and the
     1969      /// second one a blue node.
     1970      Edge addEdge(const RedNode&, const BlueNode&) {
     1971        return INVALID;
     1972      }
     1973      Edge addEdge(const BlueNode&, const RedNode&) {
     1974        return INVALID;
     1975      }
     1976
     1977      template <typename _BpGraph>
     1978      struct Constraints {
     1979        void constraints() {
     1980          checkConcept<Base, _BpGraph>();
     1981          typename _BpGraph::RedNode red_node;
     1982          typename _BpGraph::BlueNode blue_node;
     1983          red_node = bpgraph.addRedNode();
     1984          blue_node = bpgraph.addBlueNode();
     1985          typename _BpGraph::Edge edge;
     1986          edge = bpgraph.addEdge(red_node, blue_node);
     1987          edge = bpgraph.addEdge(blue_node, red_node);
     1988        }
     1989
     1990        _BpGraph& bpgraph;
     1991      };
     1992    };
     1993
    14001994    /// \brief Skeleton class for erasable directed graphs.
    14011995    ///
     
    14782072    };
    14792073
     2074    /// \brief Skeleton class for erasable undirected graphs.
     2075    ///
     2076    /// This class describes the interface of erasable undirected
     2077    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
     2078    /// functions for removing nodes and edges from the graph. This
     2079    /// concept requires \ref AlterableBpGraphComponent.
     2080    template <typename BAS = BaseBpGraphComponent>
     2081    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
     2082
    14802083    /// \brief Skeleton class for clearable directed graphs.
    14812084    ///
     
    15142117    /// This concept requires \ref AlterableGraphComponent.
    15152118    template <typename BAS = BaseGraphComponent>
    1516     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1517     public:
    1518 
    1519       typedef BAS Base;
    1520 
    1521       /// \brief Erase all nodes and edges from the graph.
    1522       ///
    1523       /// This function erases all nodes and edges from the graph.
    1524       void clear() {}
    1525 
    1526       template <typename _Graph>
    1527       struct Constraints {
    1528         void constraints() {
    1529           checkConcept<Base, _Graph>();
    1530           graph.clear();
    1531         }
    1532 
    1533         _Graph& graph;
    1534         Constraints() {}
    1535       };
    1536     };
     2119    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
     2120
     2121    /// \brief Skeleton class for clearable undirected biparite graphs.
     2122    ///
     2123    /// This class describes the interface of clearable undirected
     2124    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
     2125    /// function for clearing the graph.  This concept requires \ref
     2126    /// AlterableBpGraphComponent.
     2127    template <typename BAS = BaseBpGraphComponent>
     2128    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
    15372129
    15382130  }
  • lemon/config.h.in

    r725 r1232  
    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_DEFAULT_LP @LEMON_DEFAULT_LP@
     10#cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
     11#cmakedefine LEMON_USE_PTHREAD 1
     12#cmakedefine LEMON_USE_WIN32_THREADS 1
  • lemon/core.h

    r1259 r1261  
    160160  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    161161
     162  ///Create convenience typedefs for the bipartite graph types and iterators
     163
     164  ///This \c \#define creates the same convenient type definitions as
     165  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
     166  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
     167  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
     168  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
     169  ///
     170  ///\note If the graph type is a dependent type, ie. the graph type depend
     171  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     172  ///macro.
     173#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     174  GRAPH_TYPEDEFS(BpGraph);                                              \
     175  typedef BpGraph::RedNode RedNode;                                     \
     176  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
     177  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
     178  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
     179  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
     180  typedef BpGraph::BlueNode BlueNode;                                   \
     181  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
     182  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
     183  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
     184  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
     185
     186  ///Create convenience typedefs for the bipartite graph types and iterators
     187
     188  ///\see BPGRAPH_TYPEDEFS
     189  ///
     190  ///\note Use this macro, if the graph type is a dependent type,
     191  ///ie. the graph type depend on a template parameter.
     192#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
     193  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
     194  typedef typename BpGraph::RedNode RedNode;                                \
     195  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
     196  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
     197  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
     198  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
     199  typedef typename BpGraph::BlueNode BlueNode;                              \
     200  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
     201  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
     202  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
     203  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
     204
    162205  /// \brief Function to count the items in a graph.
    163206  ///
     
    211254  }
    212255
     256  namespace _graph_utils_bits {
     257   
     258    template <typename Graph, typename Enable = void>
     259    struct CountRedNodesSelector {
     260      static int count(const Graph &g) {
     261        return countItems<Graph, typename Graph::RedNode>(g);
     262      }
     263    };
     264
     265    template <typename Graph>
     266    struct CountRedNodesSelector<
     267      Graph, typename
     268      enable_if<typename Graph::NodeNumTag, void>::type>
     269    {
     270      static int count(const Graph &g) {
     271        return g.redNum();
     272      }
     273    };   
     274  }
     275
     276  /// \brief Function to count the red nodes in the graph.
     277  ///
     278  /// This function counts the red nodes in the graph.
     279  /// The complexity of the function is O(n) but for some
     280  /// graph structures it is specialized to run in O(1).
     281  ///
     282  /// If the graph contains a \e redNum() member function and a
     283  /// \e NodeNumTag tag then this function calls directly the member
     284  /// function to query the cardinality of the node set.
     285  template <typename Graph>
     286  inline int countRedNodes(const Graph& g) {
     287    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
     288  }
     289
     290  namespace _graph_utils_bits {
     291   
     292    template <typename Graph, typename Enable = void>
     293    struct CountBlueNodesSelector {
     294      static int count(const Graph &g) {
     295        return countItems<Graph, typename Graph::BlueNode>(g);
     296      }
     297    };
     298
     299    template <typename Graph>
     300    struct CountBlueNodesSelector<
     301      Graph, typename
     302      enable_if<typename Graph::NodeNumTag, void>::type>
     303    {
     304      static int count(const Graph &g) {
     305        return g.blueNum();
     306      }
     307    };   
     308  }
     309
     310  /// \brief Function to count the blue nodes in the graph.
     311  ///
     312  /// This function counts the blue nodes in the graph.
     313  /// The complexity of the function is O(n) but for some
     314  /// graph structures it is specialized to run in O(1).
     315  ///
     316  /// If the graph contains a \e blueNum() member function and a
     317  /// \e NodeNumTag tag then this function calls directly the member
     318  /// function to query the cardinality of the node set.
     319  template <typename Graph>
     320  inline int countBlueNodes(const Graph& g) {
     321    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
     322  }
     323
    213324  // Arc counting:
    214325
     
    452563      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    453564      static void copy(const From& from, Graph &to,
    454                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     565                       NodeRefMap& nodeRefMap,
     566                       EdgeRefMap& edgeRefMap) {
    455567        to.build(from, nodeRefMap, edgeRefMap);
    456568      }
    457569    };
    458570
     571    template <typename BpGraph, typename Enable = void>
     572    struct BpGraphCopySelector {
     573      template <typename From, typename RedNodeRefMap,
     574                typename BlueNodeRefMap, typename EdgeRefMap>
     575      static void copy(const From& from, BpGraph &to,
     576                       RedNodeRefMap& redNodeRefMap,
     577                       BlueNodeRefMap& blueNodeRefMap,
     578                       EdgeRefMap& edgeRefMap) {
     579        to.clear();
     580        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
     581          redNodeRefMap[it] = to.addRedNode();
     582        }
     583        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
     584          blueNodeRefMap[it] = to.addBlueNode();
     585        }
     586        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
     587          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
     588                                      blueNodeRefMap[from.blueNode(it)]);
     589        }
     590      }
     591    };
     592
     593    template <typename BpGraph>
     594    struct BpGraphCopySelector<
     595      BpGraph,
     596      typename enable_if<typename BpGraph::BuildTag, void>::type>
     597    {
     598      template <typename From, typename RedNodeRefMap,
     599                typename BlueNodeRefMap, typename EdgeRefMap>
     600      static void copy(const From& from, BpGraph &to,
     601                       RedNodeRefMap& redNodeRefMap,
     602                       BlueNodeRefMap& blueNodeRefMap,
     603                       EdgeRefMap& edgeRefMap) {
     604        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     605      }
     606    };
     607
    459608  }
     609
     610  /// \brief Check whether a graph is undirected.
     611  ///
     612  /// This function returns \c true if the given graph is undirected.
     613#ifdef DOXYGEN
     614  template <typename GR>
     615  bool undirected(const GR& g) { return false; }
     616#else
     617  template <typename GR>
     618  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     619  undirected(const GR&) {
     620    return true;
     621  }
     622  template <typename GR>
     623  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     624  undirected(const GR&) {
     625    return false;
     626  }
     627#endif
    460628
    461629  /// \brief Class to copy a digraph.
     
    9821150  graphCopy(const From& from, To& to) {
    9831151    return GraphCopy<From, To>(from, to);
     1152  }
     1153
     1154  /// \brief Class to copy a bipartite graph.
     1155  ///
     1156  /// Class to copy a bipartite graph to another graph (duplicate a
     1157  /// graph). The simplest way of using it is through the
     1158  /// \c bpGraphCopy() function.
     1159  ///
     1160  /// This class not only make a copy of a bipartite graph, but it can
     1161  /// create references and cross references between the nodes, edges
     1162  /// and arcs of the two graphs, and it can copy maps for using with
     1163  /// the newly created graph.
     1164  ///
     1165  /// To make a copy from a graph, first an instance of BpGraphCopy
     1166  /// should be created, then the data belongs to the graph should
     1167  /// assigned to copy. In the end, the \c run() member should be
     1168  /// called.
     1169  ///
     1170  /// The next code copies a graph with several data:
     1171  ///\code
     1172  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
     1173  ///  // Create references for the nodes
     1174  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
     1175  ///  cg.nodeRef(nr);
     1176  ///  // Create cross references (inverse) for the edges
     1177  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
     1178  ///  cg.edgeCrossRef(ecr);
     1179  ///  // Copy a red node map
     1180  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
     1181  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
     1182  ///  cg.redNodeMap(ormap, nrmap);
     1183  ///  // Copy a node
     1184  ///  OrigBpGraph::Node on;
     1185  ///  NewBpGraph::Node nn;
     1186  ///  cg.node(on, nn);
     1187  ///  // Execute copying
     1188  ///  cg.run();
     1189  ///\endcode
     1190  template <typename From, typename To>
     1191  class BpGraphCopy {
     1192  private:
     1193
     1194    typedef typename From::Node Node;
     1195    typedef typename From::RedNode RedNode;
     1196    typedef typename From::BlueNode BlueNode;
     1197    typedef typename From::NodeIt NodeIt;
     1198    typedef typename From::Arc Arc;
     1199    typedef typename From::ArcIt ArcIt;
     1200    typedef typename From::Edge Edge;
     1201    typedef typename From::EdgeIt EdgeIt;
     1202
     1203    typedef typename To::Node TNode;
     1204    typedef typename To::RedNode TRedNode;
     1205    typedef typename To::BlueNode TBlueNode;
     1206    typedef typename To::Arc TArc;
     1207    typedef typename To::Edge TEdge;
     1208
     1209    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
     1210    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
     1211    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
     1212
     1213    struct NodeRefMap {
     1214      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
     1215                 const BlueNodeRefMap& blue_node_ref)
     1216        : _from(from), _red_node_ref(red_node_ref),
     1217          _blue_node_ref(blue_node_ref) {}
     1218
     1219      typedef typename From::Node Key;
     1220      typedef typename To::Node Value;
     1221
     1222      Value operator[](const Key& key) const {
     1223        if (_from.red(key)) {
     1224          return _red_node_ref[_from.asRedNodeUnsafe(key)];
     1225        } else {
     1226          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
     1227        }
     1228      }
     1229
     1230      const From& _from;
     1231      const RedNodeRefMap& _red_node_ref;
     1232      const BlueNodeRefMap& _blue_node_ref;
     1233    };
     1234
     1235    struct ArcRefMap {
     1236      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
     1237        : _from(from), _to(to), _edge_ref(edge_ref) {}
     1238
     1239      typedef typename From::Arc Key;
     1240      typedef typename To::Arc Value;
     1241
     1242      Value operator[](const Key& key) const {
     1243        return _to.direct(_edge_ref[key], _from.direction(key));
     1244      }
     1245
     1246      const From& _from;
     1247      const To& _to;
     1248      const EdgeRefMap& _edge_ref;
     1249    };
     1250
     1251  public:
     1252
     1253    /// \brief Constructor of BpGraphCopy.
     1254    ///
     1255    /// Constructor of BpGraphCopy for copying the content of the
     1256    /// \c from graph into the \c to graph.
     1257    BpGraphCopy(const From& from, To& to)
     1258      : _from(from), _to(to) {}
     1259
     1260    /// \brief Destructor of BpGraphCopy
     1261    ///
     1262    /// Destructor of BpGraphCopy.
     1263    ~BpGraphCopy() {
     1264      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1265        delete _node_maps[i];
     1266      }
     1267      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1268        delete _red_maps[i];
     1269      }
     1270      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1271        delete _blue_maps[i];
     1272      }
     1273      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1274        delete _arc_maps[i];
     1275      }
     1276      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1277        delete _edge_maps[i];
     1278      }
     1279    }
     1280
     1281    /// \brief Copy the node references into the given map.
     1282    ///
     1283    /// This function copies the node references into the given map.
     1284    /// The parameter should be a map, whose key type is the Node type of
     1285    /// the source graph, while the value type is the Node type of the
     1286    /// destination graph.
     1287    template <typename NodeRef>
     1288    BpGraphCopy& nodeRef(NodeRef& map) {
     1289      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
     1290                           NodeRefMap, NodeRef>(map));
     1291      return *this;
     1292    }
     1293
     1294    /// \brief Copy the node cross references into the given map.
     1295    ///
     1296    /// This function copies the node cross references (reverse references)
     1297    /// into the given map. The parameter should be a map, whose key type
     1298    /// is the Node type of the destination graph, while the value type is
     1299    /// the Node type of the source graph.
     1300    template <typename NodeCrossRef>
     1301    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
     1302      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
     1303                           NodeRefMap, NodeCrossRef>(map));
     1304      return *this;
     1305    }
     1306
     1307    /// \brief Make a copy of the given node map.
     1308    ///
     1309    /// This function makes a copy of the given node map for the newly
     1310    /// created graph.
     1311    /// The key type of the new map \c tmap should be the Node type of the
     1312    /// destination graph, and the key type of the original map \c map
     1313    /// should be the Node type of the source graph.
     1314    template <typename FromMap, typename ToMap>
     1315    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
     1316      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
     1317                           NodeRefMap, FromMap, ToMap>(map, tmap));
     1318      return *this;
     1319    }
     1320
     1321    /// \brief Make a copy of the given node.
     1322    ///
     1323    /// This function makes a copy of the given node.
     1324    BpGraphCopy& node(const Node& node, TNode& tnode) {
     1325      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
     1326                           NodeRefMap, TNode>(node, tnode));
     1327      return *this;
     1328    }
     1329
     1330    /// \brief Copy the red node references into the given map.
     1331    ///
     1332    /// This function copies the red node references into the given
     1333    /// map.  The parameter should be a map, whose key type is the
     1334    /// Node type of the source graph with the red item set, while the
     1335    /// value type is the Node type of the destination graph.
     1336    template <typename RedRef>
     1337    BpGraphCopy& redRef(RedRef& map) {
     1338      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
     1339                          RedNodeRefMap, RedRef>(map));
     1340      return *this;
     1341    }
     1342
     1343    /// \brief Copy the red node cross references into the given map.
     1344    ///
     1345    /// This function copies the red node cross references (reverse
     1346    /// references) into the given map. The parameter should be a map,
     1347    /// whose key type is the Node type of the destination graph with
     1348    /// the red item set, while the value type is the Node type of the
     1349    /// source graph.
     1350    template <typename RedCrossRef>
     1351    BpGraphCopy& redCrossRef(RedCrossRef& map) {
     1352      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
     1353                          RedNodeRefMap, RedCrossRef>(map));
     1354      return *this;
     1355    }
     1356
     1357    /// \brief Make a copy of the given red node map.
     1358    ///
     1359    /// This function makes a copy of the given red node map for the newly
     1360    /// created graph.
     1361    /// The key type of the new map \c tmap should be the Node type of
     1362    /// the destination graph with the red items, and the key type of
     1363    /// the original map \c map should be the Node type of the source
     1364    /// graph.
     1365    template <typename FromMap, typename ToMap>
     1366    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
     1367      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
     1368                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
     1369      return *this;
     1370    }
     1371
     1372    /// \brief Make a copy of the given red node.
     1373    ///
     1374    /// This function makes a copy of the given red node.
     1375    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
     1376      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
     1377                          RedNodeRefMap, TRedNode>(node, tnode));
     1378      return *this;
     1379    }
     1380
     1381    /// \brief Copy the blue node references into the given map.
     1382    ///
     1383    /// This function copies the blue node references into the given
     1384    /// map.  The parameter should be a map, whose key type is the
     1385    /// Node type of the source graph with the blue item set, while the
     1386    /// value type is the Node type of the destination graph.
     1387    template <typename BlueRef>
     1388    BpGraphCopy& blueRef(BlueRef& map) {
     1389      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
     1390                           BlueNodeRefMap, BlueRef>(map));
     1391      return *this;
     1392    }
     1393
     1394    /// \brief Copy the blue node cross references into the given map.
     1395    ///
     1396    /// This function copies the blue node cross references (reverse
     1397    /// references) into the given map. The parameter should be a map,
     1398    /// whose key type is the Node type of the destination graph with
     1399    /// the blue item set, while the value type is the Node type of the
     1400    /// source graph.
     1401    template <typename BlueCrossRef>
     1402    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
     1403      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
     1404                           BlueNodeRefMap, BlueCrossRef>(map));
     1405      return *this;
     1406    }
     1407
     1408    /// \brief Make a copy of the given blue node map.
     1409    ///
     1410    /// This function makes a copy of the given blue node map for the newly
     1411    /// created graph.
     1412    /// The key type of the new map \c tmap should be the Node type of
     1413    /// the destination graph with the blue items, and the key type of
     1414    /// the original map \c map should be the Node type of the source
     1415    /// graph.
     1416    template <typename FromMap, typename ToMap>
     1417    BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) {
     1418      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
     1419                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
     1420      return *this;
     1421    }
     1422
     1423    /// \brief Make a copy of the given blue node.
     1424    ///
     1425    /// This function makes a copy of the given blue node.
     1426    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
     1427      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
     1428                           BlueNodeRefMap, TBlueNode>(node, tnode));
     1429      return *this;
     1430    }
     1431
     1432    /// \brief Copy the arc references into the given map.
     1433    ///
     1434    /// This function copies the arc references into the given map.
     1435    /// The parameter should be a map, whose key type is the Arc type of
     1436    /// the source graph, while the value type is the Arc type of the
     1437    /// destination graph.
     1438    template <typename ArcRef>
     1439    BpGraphCopy& arcRef(ArcRef& map) {
     1440      _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
     1441                          ArcRefMap, ArcRef>(map));
     1442      return *this;
     1443    }
     1444
     1445    /// \brief Copy the arc cross references into the given map.
     1446    ///
     1447    /// This function copies the arc cross references (reverse references)
     1448    /// into the given map. The parameter should be a map, whose key type
     1449    /// is the Arc type of the destination graph, while the value type is
     1450    /// the Arc type of the source graph.
     1451    template <typename ArcCrossRef>
     1452    BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
     1453      _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
     1454                          ArcRefMap, ArcCrossRef>(map));
     1455      return *this;
     1456    }
     1457
     1458    /// \brief Make a copy of the given arc map.
     1459    ///
     1460    /// This function makes a copy of the given arc map for the newly
     1461    /// created graph.
     1462    /// The key type of the new map \c tmap should be the Arc type of the
     1463    /// destination graph, and the key type of the original map \c map
     1464    /// should be the Arc type of the source graph.
     1465    template <typename FromMap, typename ToMap>
     1466    BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
     1467      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
     1468                          ArcRefMap, FromMap, ToMap>(map, tmap));
     1469      return *this;
     1470    }
     1471
     1472    /// \brief Make a copy of the given arc.
     1473    ///
     1474    /// This function makes a copy of the given arc.
     1475    BpGraphCopy& arc(const Arc& arc, TArc& tarc) {
     1476      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
     1477                          ArcRefMap, TArc>(arc, tarc));
     1478      return *this;
     1479    }
     1480
     1481    /// \brief Copy the edge references into the given map.
     1482    ///
     1483    /// This function copies the edge references into the given map.
     1484    /// The parameter should be a map, whose key type is the Edge type of
     1485    /// the source graph, while the value type is the Edge type of the
     1486    /// destination graph.
     1487    template <typename EdgeRef>
     1488    BpGraphCopy& edgeRef(EdgeRef& map) {
     1489      _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
     1490                           EdgeRefMap, EdgeRef>(map));
     1491      return *this;
     1492    }
     1493
     1494    /// \brief Copy the edge cross references into the given map.
     1495    ///
     1496    /// This function copies the edge cross references (reverse references)
     1497    /// into the given map. The parameter should be a map, whose key type
     1498    /// is the Edge type of the destination graph, while the value type is
     1499    /// the Edge type of the source graph.
     1500    template <typename EdgeCrossRef>
     1501    BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
     1502      _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
     1503                           Edge, EdgeRefMap, EdgeCrossRef>(map));
     1504      return *this;
     1505    }
     1506
     1507    /// \brief Make a copy of the given edge map.
     1508    ///
     1509    /// This function makes a copy of the given edge map for the newly
     1510    /// created graph.
     1511    /// The key type of the new map \c tmap should be the Edge type of the
     1512    /// destination graph, and the key type of the original map \c map
     1513    /// should be the Edge type of the source graph.
     1514    template <typename FromMap, typename ToMap>
     1515    BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
     1516      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
     1517                           EdgeRefMap, FromMap, ToMap>(map, tmap));
     1518      return *this;
     1519    }
     1520
     1521    /// \brief Make a copy of the given edge.
     1522    ///
     1523    /// This function makes a copy of the given edge.
     1524    BpGraphCopy& edge(const Edge& edge, TEdge& tedge) {
     1525      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
     1526                           EdgeRefMap, TEdge>(edge, tedge));
     1527      return *this;
     1528    }
     1529
     1530    /// \brief Execute copying.
     1531    ///
     1532    /// This function executes the copying of the graph along with the
     1533    /// copying of the assigned data.
     1534    void run() {
     1535      RedNodeRefMap redNodeRefMap(_from);
     1536      BlueNodeRefMap blueNodeRefMap(_from);
     1537      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
     1538      EdgeRefMap edgeRefMap(_from);
     1539      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
     1540      _core_bits::BpGraphCopySelector<To>::
     1541        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     1542      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1543        _node_maps[i]->copy(_from, nodeRefMap);
     1544      }
     1545      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1546        _red_maps[i]->copy(_from, redNodeRefMap);
     1547      }
     1548      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1549        _blue_maps[i]->copy(_from, blueNodeRefMap);
     1550      }
     1551      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1552        _edge_maps[i]->copy(_from, edgeRefMap);
     1553      }
     1554      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1555        _arc_maps[i]->copy(_from, arcRefMap);
     1556      }
     1557    }
     1558
     1559  private:
     1560
     1561    const From& _from;
     1562    To& _to;
     1563
     1564    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
     1565      _node_maps;
     1566
     1567    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
     1568      _red_maps;
     1569
     1570    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
     1571      _blue_maps;
     1572
     1573    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
     1574      _arc_maps;
     1575
     1576    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
     1577      _edge_maps;
     1578
     1579  };
     1580
     1581  /// \brief Copy a graph to another graph.
     1582  ///
     1583  /// This function copies a graph to another graph.
     1584  /// The complete usage of it is detailed in the BpGraphCopy class,
     1585  /// but a short example shows a basic work:
     1586  ///\code
     1587  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
     1588  ///\endcode
     1589  ///
     1590  /// After the copy the \c nr map will contain the mapping from the
     1591  /// nodes of the \c from graph to the nodes of the \c to graph and
     1592  /// \c ecr will contain the mapping from the edges of the \c to graph
     1593  /// to the edges of the \c from graph.
     1594  ///
     1595  /// \see BpGraphCopy
     1596  template <typename From, typename To>
     1597  BpGraphCopy<From, To>
     1598  bpGraphCopy(const From& from, To& to) {
     1599    return BpGraphCopy<From, To>(from, to);
    9841600  }
    9851601
     
    12501866    /// The Digraph type
    12511867    typedef GR Digraph;
    1252 
     1868   
    12531869  protected:
    12541870
  • lemon/cost_scaling.h

    r1041 r1254  
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    94   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient.
     94  /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation,
     95  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
     99  /// It is a polynomial algorithm, its running time complexity is
     100  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
     101  ///
     102  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     103  /// implementations available in LEMON for solving this problem.
     104  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    99105  ///
    100106  /// Most of the parameters of the problem (except for the digraph)
     
    114120  /// consider to use the named template parameters instead.
    115121  ///
    116   /// \warning Both number types must be signed and all input data must
     122  /// \warning Both \c V and \c C must be signed number types.
     123  /// \warning All input data (capacities, supply values, and costs) must
    117124  /// be integer.
    118   /// \warning This algorithm does not support negative costs for such
    119   /// arcs that have infinite upper bound.
     125  /// \warning This algorithm does not support negative costs for
     126  /// arcs having infinite upper bound.
    120127  ///
    121128  /// \note %CostScaling provides three different internal methods,
     
    146153    typedef typename TR::LargeCost LargeCost;
    147154
    148     /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
     155    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
     156    /// of the algorithm
    149157    typedef TR Traits;
    150158
     
    179187    /// relabel operation.
    180188    /// By default, the so called \ref PARTIAL_AUGMENT
    181     /// "Partial Augment-Relabel" method is used, which proved to be
     189    /// "Partial Augment-Relabel" method is used, which turned out to be
    182190    /// the most efficient and the most robust on various test inputs.
    183191    /// However, the other methods can be selected using the \ref run()
     
    234242    };
    235243
    236     typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    237244    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    238245
     
    285292    int _max_rank;
    286293
    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 
    295294  public:
    296295
     
    339338    CostScaling(const GR& graph) :
    340339      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
    341       _cost_map(_cost_vec), _pi_map(_pi),
    342340      INF(std::numeric_limits<Value>::has_infinity ?
    343341          std::numeric_limits<Value>::infinity() :
     
    448446    ///
    449447    /// 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
     448    /// with a map in which \c k is assigned to \c s, \c -k is
    451449    /// assigned to \c t and all other nodes have zero supply value.
    452450    ///
     
    494492    /// \param method The internal method that will be used in the
    495493    /// algorithm. For more information, see \ref Method.
    496     /// \param factor The cost scaling factor. It must be larger than one.
     494    /// \param factor The cost scaling factor. It must be at least two.
    497495    ///
    498496    /// \return \c INFEASIBLE if no feasible flow exists,
     
    508506    /// \see ProblemType, Method
    509507    /// \see resetParams(), reset()
    510     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     508    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
     509      LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
    511510      _alpha = factor;
    512511      ProblemType pt = init();
     
    572571    }
    573572
    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.
     573    /// \brief Reset the internal data structures and all the parameters
     574    /// that have been given before.
     575    ///
     576    /// This function resets the internal data structures and all the
     577    /// paramaters that have been given before using functions \ref lowerMap(),
     578    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     579    ///
     580    /// It is useful for multiple \ref run() calls. By default, all the given
     581    /// parameters are kept for the next \ref run() call, unless
     582    /// \ref resetParams() or \ref reset() is used.
     583    /// If the underlying digraph was also modified after the construction
     584    /// of the class or the last \ref reset() call, then the \ref reset()
     585    /// function must be used, otherwise \ref resetParams() is sufficient.
     586    ///
     587    /// See \ref resetParams() for examples.
     588    ///
    585589    /// \return <tt>(*this)</tt>
     590    ///
     591    /// \see resetParams(), run()
    586592    CostScaling& reset() {
    587593      // Resize vectors
     
    608614      _excess.resize(_res_node_num);
    609615      _next_out.resize(_res_node_num);
    610 
    611       _arc_vec.reserve(_res_arc_num);
    612       _cost_vec.reserve(_res_arc_num);
    613616
    614617      // Copy the graph
     
    668671    ///
    669672    /// This function returns the total cost of the found flow.
    670     /// Its complexity is O(e).
     673    /// Its complexity is O(m).
    671674    ///
    672675    /// \note The return type of the function can be specified as a
     
    706709    }
    707710
    708     /// \brief Return the flow map (the primal solution).
     711    /// \brief Copy the flow values (the primal solution) into the
     712    /// given map.
    709713    ///
    710714    /// This function copies the flow value on each arc into the given
     
    730734    }
    731735
    732     /// \brief Return the potential map (the dual solution).
     736    /// \brief Copy the potential values (the dual solution) into the
     737    /// given map.
    733738    ///
    734739    /// This function copies the potential (dual value) of each node
     
    759764      }
    760765      if (_sum_supply > 0) return INFEASIBLE;
     766
     767      // Check lower and upper bounds
     768      LEMON_DEBUG(checkBoundMaps(),
     769          "Upper bounds must be greater or equal to the lower bounds");
    761770
    762771
     
    887896      }
    888897
    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 
    897898      // Initialize data structures for buckets
    898899      _max_rank = _alpha * _res_node_num;
     
    902903      _rank.resize(_res_node_num + 1);
    903904
    904       // Execute the algorithm
     905      return OPTIMAL;
     906    }
     907   
     908    // Check if the upper bound is greater or equal to the lower bound
     909    // on each arc.
     910    bool checkBoundMaps() {
     911      for (int j = 0; j != _res_arc_num; ++j) {
     912        if (_upper[j] < _lower[j]) return false;
     913      }
     914      return true;
     915    }
     916
     917    // Execute the algorithm and transform the results
     918    void start(Method method) {
     919      const int MAX_PARTIAL_PATH_LENGTH = 4;
     920
    905921      switch (method) {
    906922        case PUSH:
     
    911927          break;
    912928        case PARTIAL_AUGMENT:
    913           startAugment(MAX_PATH_LENGTH);
     929          startAugment(MAX_PARTIAL_PATH_LENGTH);
    914930          break;
    915931      }
    916932
    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();
     933      // Compute node potentials (dual solution)
     934      for (int i = 0; i != _res_node_num; ++i) {
     935        _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
     936      }
     937      bool optimal = true;
     938      for (int i = 0; optimal && i != _res_node_num; ++i) {
     939        LargeCost pi_i = _pi[i];
     940        int last_out = _first_out[i+1];
     941        for (int j = _first_out[i]; j != last_out; ++j) {
     942          if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
     943            optimal = false;
     944            break;
     945          }
     946        }
     947      }
     948
     949      if (!optimal) {
     950        // Compute node potentials for the original costs with BellmanFord
     951        // (if it is necessary)
     952        typedef std::pair<int, int> IntPair;
     953        StaticDigraph sgr;
     954        std::vector<IntPair> arc_vec;
     955        std::vector<LargeCost> cost_vec;
     956        LargeCostArcMap cost_map(cost_vec);
     957
     958        arc_vec.clear();
     959        cost_vec.clear();
     960        for (int j = 0; j != _res_arc_num; ++j) {
     961          if (_res_cap[j] > 0) {
     962            int u = _source[j], v = _target[j];
     963            arc_vec.push_back(IntPair(u, v));
     964            cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
     965          }
     966        }
     967        sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
     968
     969        typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
     970          bf(sgr, cost_map);
     971        bf.init(0);
     972        bf.start();
     973
     974        for (int i = 0; i != _res_node_num; ++i) {
     975          _pi[i] += bf.dist(sgr.node(i));
     976        }
     977      }
     978
     979      // Shift potentials to meet the requirements of the GEQ type
     980      // optimality conditions
     981      LargeCost max_pot = _pi[_root];
     982      for (int i = 0; i != _res_node_num; ++i) {
     983        if (_pi[i] > max_pot) max_pot = _pi[i];
     984      }
     985      if (max_pot != 0) {
     986        for (int i = 0; i != _res_node_num; ++i) {
     987          _pi[i] -= max_pot;
     988        }
     989      }
    933990
    934991      // Handle non-zero lower bounds
     
    9481005        LargeCost pi_u = _pi[u];
    9491006        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;
     1007          Value delta = _res_cap[a];
     1008          if (delta > 0) {
     1009            int v = _target[a];
     1010            if (_cost[a] + pi_u - _pi[v] < 0) {
     1011              _excess[u] -= delta;
     1012              _excess[v] += delta;
     1013              _res_cap[a] = 0;
     1014              _res_cap[_reverse[a]] += delta;
     1015            }
    9571016          }
    9581017        }
     
    9701029    }
    9711030
    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;
     1031    // Price (potential) refinement heuristic
     1032    bool priceRefinement() {
     1033
     1034      // Stack for stroing the topological order
     1035      IntVector stack(_res_node_num);
     1036      int stack_top;
     1037
     1038      // Perform phases
     1039      while (topologicalSort(stack, stack_top)) {
     1040
     1041        // Compute node ranks in the acyclic admissible network and
     1042        // store the nodes in buckets
     1043        for (int i = 0; i != _res_node_num; ++i) {
     1044          _rank[i] = 0;
     1045        }
     1046        const int bucket_end = _root + 1;
     1047        for (int r = 0; r != _max_rank; ++r) {
     1048          _buckets[r] = bucket_end;
     1049        }
     1050        int top_rank = 0;
     1051        for ( ; stack_top >= 0; --stack_top) {
     1052          int u = stack[stack_top], v;
     1053          int rank_u = _rank[u];
     1054
     1055          LargeCost rc, pi_u = _pi[u];
     1056          int last_out = _first_out[u+1];
     1057          for (int a = _first_out[u]; a != last_out; ++a) {
     1058            if (_res_cap[a] > 0) {
     1059              v = _target[a];
     1060              rc = _cost[a] + pi_u - _pi[v];
     1061              if (rc < 0) {
     1062                LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
     1063                if (nrc < LargeCost(_max_rank)) {
     1064                  int new_rank_v = rank_u + static_cast<int>(nrc);
     1065                  if (new_rank_v > _rank[v]) {
     1066                    _rank[v] = new_rank_v;
     1067                  }
     1068                }
     1069              }
     1070            }
     1071          }
     1072
     1073          if (rank_u > 0) {
     1074            top_rank = std::max(top_rank, rank_u);
     1075            int bfirst = _buckets[rank_u];
     1076            _bucket_next[u] = bfirst;
     1077            _bucket_prev[bfirst] = u;
     1078            _buckets[rank_u] = u;
     1079          }
     1080        }
     1081
     1082        // Check if the current flow is epsilon-optimal
     1083        if (top_rank == 0) {
     1084          return true;
     1085        }
     1086
     1087        // Process buckets in top-down order
     1088        for (int rank = top_rank; rank > 0; --rank) {
     1089          while (_buckets[rank] != bucket_end) {
     1090            // Remove the first node from the current bucket
     1091            int u = _buckets[rank];
     1092            _buckets[rank] = _bucket_next[u];
     1093
     1094            // Search the outgoing arcs of u
     1095            LargeCost rc, pi_u = _pi[u];
     1096            int last_out = _first_out[u+1];
     1097            int v, old_rank_v, new_rank_v;
     1098            for (int a = _first_out[u]; a != last_out; ++a) {
     1099              if (_res_cap[a] > 0) {
     1100                v = _target[a];
     1101                old_rank_v = _rank[v];
     1102
     1103                if (old_rank_v < rank) {
     1104
     1105                  // Compute the new rank of node v
     1106                  rc = _cost[a] + pi_u - _pi[v];
     1107                  if (rc < 0) {
     1108                    new_rank_v = rank;
     1109                  } else {
     1110                    LargeCost nrc = rc / _epsilon;
     1111                    new_rank_v = 0;
     1112                    if (nrc < LargeCost(_max_rank)) {
     1113                      new_rank_v = rank - 1 - static_cast<int>(nrc);
     1114                    }
     1115                  }
     1116
     1117                  // Change the rank of node v
     1118                  if (new_rank_v > old_rank_v) {
     1119                    _rank[v] = new_rank_v;
     1120
     1121                    // Remove v from its old bucket
     1122                    if (old_rank_v > 0) {
     1123                      if (_buckets[old_rank_v] == v) {
     1124                        _buckets[old_rank_v] = _bucket_next[v];
     1125                      } else {
     1126                        int pv = _bucket_prev[v], nv = _bucket_next[v];
     1127                        _bucket_next[pv] = nv;
     1128                        _bucket_prev[nv] = pv;
     1129                      }
     1130                    }
     1131
     1132                    // Insert v into its new bucket
     1133                    int nv = _buckets[new_rank_v];
     1134                    _bucket_next[v] = nv;
     1135                    _bucket_prev[nv] = v;
     1136                    _buckets[new_rank_v] = v;
     1137                  }
     1138                }
     1139              }
     1140            }
     1141
     1142            // Refine potential of node u
     1143            _pi[u] -= rank * _epsilon;
     1144          }
     1145        }
     1146
     1147      }
     1148
     1149      return false;
     1150    }
     1151
     1152    // Find and cancel cycles in the admissible network and
     1153    // determine topological order using DFS
     1154    bool topologicalSort(IntVector &stack, int &stack_top) {
     1155      const int MAX_CYCLE_CANCEL = 1;
     1156
     1157      BoolVector reached(_res_node_num, false);
     1158      BoolVector processed(_res_node_num, false);
     1159      IntVector pred(_res_node_num);
     1160      for (int i = 0; i != _res_node_num; ++i) {
     1161        _next_out[i] = _first_out[i];
     1162      }
     1163      stack_top = -1;
     1164
     1165      int cycle_cnt = 0;
     1166      for (int start = 0; start != _res_node_num; ++start) {
     1167        if (reached[start]) continue;
     1168
     1169        // Start DFS search from this start node
     1170        pred[start] = -1;
     1171        int tip = start, v;
     1172        while (true) {
     1173          // Check the outgoing arcs of the current tip node
     1174          reached[tip] = true;
     1175          LargeCost pi_tip = _pi[tip];
     1176          int a, last_out = _first_out[tip+1];
     1177          for (a = _next_out[tip]; a != last_out; ++a) {
     1178            if (_res_cap[a] > 0) {
     1179              v = _target[a];
     1180              if (_cost[a] + pi_tip - _pi[v] < 0) {
     1181                if (!reached[v]) {
     1182                  // A new node is reached
     1183                  reached[v] = true;
     1184                  pred[v] = tip;
     1185                  _next_out[tip] = a;
     1186                  tip = v;
     1187                  a = _next_out[tip];
     1188                  last_out = _first_out[tip+1];
     1189                  break;
     1190                }
     1191                else if (!processed[v]) {
     1192                  // A cycle is found
     1193                  ++cycle_cnt;
     1194                  _next_out[tip] = a;
     1195
     1196                  // Find the minimum residual capacity along the cycle
     1197                  Value d, delta = _res_cap[a];
     1198                  int u, delta_node = tip;
     1199                  for (u = tip; u != v; ) {
     1200                    u = pred[u];
     1201                    d = _res_cap[_next_out[u]];
     1202                    if (d <= delta) {
     1203                      delta = d;
     1204                      delta_node = u;
     1205                    }
     1206                  }
     1207
     1208                  // Augment along the cycle
     1209                  _res_cap[a] -= delta;
     1210                  _res_cap[_reverse[a]] += delta;
     1211                  for (u = tip; u != v; ) {
     1212                    u = pred[u];
     1213                    int ca = _next_out[u];
     1214                    _res_cap[ca] -= delta;
     1215                    _res_cap[_reverse[ca]] += delta;
     1216                  }
     1217
     1218                  // Check the maximum number of cycle canceling
     1219                  if (cycle_cnt >= MAX_CYCLE_CANCEL) {
     1220                    return false;
     1221                  }
     1222
     1223                  // Roll back search to delta_node
     1224                  if (delta_node != tip) {
     1225                    for (u = tip; u != delta_node; u = pred[u]) {
     1226                      reached[u] = false;
     1227                    }
     1228                    tip = delta_node;
     1229                    a = _next_out[tip] + 1;
     1230                    last_out = _first_out[tip+1];
     1231                    break;
     1232                  }
     1233                }
     1234              }
     1235            }
     1236          }
     1237
     1238          // Step back to the previous node
     1239          if (a == last_out) {
     1240            processed[tip] = true;
     1241            stack[++stack_top] = tip;
     1242            tip = pred[tip];
     1243            if (tip < 0) {
     1244              // Finish DFS from the current start node
     1245              break;
     1246            }
     1247            ++_next_out[tip];
     1248          }
     1249        }
     1250
     1251      }
     1252
     1253      return (cycle_cnt == 0);
    9961254    }
    9971255
    9981256    // Global potential update heuristic
    9991257    void globalUpdate() {
    1000       int bucket_end = _root + 1;
     1258      const int bucket_end = _root + 1;
    10011259
    10021260      // Initialize buckets
     
    10051263      }
    10061264      Value total_excess = 0;
     1265      int b0 = bucket_end;
    10071266      for (int i = 0; i != _res_node_num; ++i) {
    10081267        if (_excess[i] < 0) {
    10091268          _rank[i] = 0;
    1010           _bucket_next[i] = _buckets[0];
    1011           _bucket_prev[_buckets[0]] = i;
    1012           _buckets[0] = i;
     1269          _bucket_next[i] = b0;
     1270          _bucket_prev[b0] = i;
     1271          b0 = i;
    10131272        } else {
    10141273          total_excess += _excess[i];
     
    10171276      }
    10181277      if (total_excess == 0) return;
     1278      _buckets[0] = b0;
    10191279
    10201280      // Search the buckets
     
    10261286          _buckets[r] = _bucket_next[u];
    10271287
    1028           // Search the incomming arcs of u
     1288          // Search the incoming arcs of u
    10291289          LargeCost pi_u = _pi[u];
    10301290          int last_out = _first_out[u+1];
     
    10381298                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
    10391299                int new_rank_v = old_rank_v;
    1040                 if (nrc < LargeCost(_max_rank))
    1041                   new_rank_v = r + 1 + int(nrc);
     1300                if (nrc < LargeCost(_max_rank)) {
     1301                  new_rank_v = r + 1 + static_cast<int>(nrc);
     1302                }
    10421303
    10431304                // Change the rank of v
     
    10511312                      _buckets[old_rank_v] = _bucket_next[v];
    10521313                    } else {
    1053                       _bucket_next[_bucket_prev[v]] = _bucket_next[v];
    1054                       _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1314                      int pv = _bucket_prev[v], nv = _bucket_next[v];
     1315                      _bucket_next[pv] = nv;
     1316                      _bucket_prev[nv] = pv;
    10551317                    }
    10561318                  }
    10571319
    1058                   // Insert v to its new bucket
    1059                   _bucket_next[v] = _buckets[new_rank_v];
    1060                   _bucket_prev[_buckets[new_rank_v]] = v;
     1320                  // Insert v into its new bucket
     1321                  int nv = _buckets[new_rank_v];
     1322                  _bucket_next[v] = nv;
     1323                  _bucket_prev[nv] = v;
    10611324                  _buckets[new_rank_v] = v;
    10621325                }
     
    10871350    void startAugment(int max_length) {
    10881351      // 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 *
     1352      const int PRICE_REFINEMENT_LIMIT = 2;
     1353      const double GLOBAL_UPDATE_FACTOR = 1.0;
     1354      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    10931355        (_res_node_num + _sup_node_num * _sup_node_num));
    1094       int next_update_limit = global_update_freq;
    1095 
     1356      int next_global_update_limit = global_update_skip;
     1357
     1358      // Perform cost scaling phases
     1359      IntVector path;
     1360      BoolVector path_arc(_res_arc_num, false);
    10961361      int relabel_cnt = 0;
    1097 
    1098       // Perform cost scaling phases
    1099       std::vector<int> path;
     1362      int eps_phase_cnt = 0;
    11001363      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    11011364                                        1 : _epsilon / _alpha )
    11021365      {
    1103         // Early termination heuristic
    1104         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1105           if (earlyTermination()) break;
     1366        ++eps_phase_cnt;
     1367
     1368        // Price refinement heuristic
     1369        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1370          if (priceRefinement()) continue;
    11061371        }
    11071372
     
    11201385
    11211386          // Find an augmenting path from the start node
    1122           path.clear();
    11231387          int tip = start;
    1124           while (_excess[tip] >= 0 && int(path.size()) < max_length) {
     1388          while (int(path.size()) < max_length && _excess[tip] >= 0) {
    11251389            int u;
    1126             LargeCost min_red_cost, rc, pi_tip = _pi[tip];
     1390            LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max();
     1391            LargeCost pi_tip = _pi[tip];
    11271392            int last_out = _first_out[tip+1];
    11281393            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;
     1394              if (_res_cap[a] > 0) {
     1395                u = _target[a];
     1396                rc = _cost[a] + pi_tip - _pi[u];
     1397                if (rc < 0) {
     1398                  path.push_back(a);
     1399                  _next_out[tip] = a;
     1400                  if (path_arc[a]) {
     1401                    goto augment;   // a cycle is found, stop path search
     1402                  }
     1403                  tip = u;
     1404                  path_arc[a] = true;
     1405                  goto next_step;
     1406                }
     1407                else if (rc < min_red_cost) {
     1408                  min_red_cost = rc;
     1409                }
    11351410              }
    11361411            }
    11371412
    11381413            // Relabel tip node
    1139             min_red_cost = std::numeric_limits<LargeCost>::max();
    11401414            if (tip != start) {
    11411415              int ra = _reverse[path.back()];
    1142               min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
     1416              min_red_cost =
     1417                std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]);
    11431418            }
     1419            last_out = _next_out[tip];
    11441420            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;
     1421              if (_res_cap[a] > 0) {
     1422                rc = _cost[a] + pi_tip - _pi[_target[a]];
     1423                if (rc < min_red_cost) {
     1424                  min_red_cost = rc;
     1425                }
    11481426              }
    11491427            }
     
    11541432            // Step back
    11551433            if (tip != start) {
    1156               tip = _source[path.back()];
     1434              int pa = path.back();
     1435              path_arc[pa] = false;
     1436              tip = _source[pa];
    11571437              path.pop_back();
    11581438            }
     
    11621442
    11631443          // Augment along the found path (as much flow as possible)
     1444        augment:
    11641445          Value delta;
    11651446          int pa, u, v = start;
     
    11681449            u = v;
    11691450            v = _target[pa];
     1451            path_arc[pa] = false;
    11701452            delta = std::min(_res_cap[pa], _excess[u]);
    11711453            _res_cap[pa] -= delta;
     
    11731455            _excess[u] -= delta;
    11741456            _excess[v] += delta;
    1175             if (_excess[v] > 0 && _excess[v] <= delta)
     1457            if (_excess[v] > 0 && _excess[v] <= delta) {
    11761458              _active_nodes.push_back(v);
    1177           }
     1459            }
     1460          }
     1461          path.clear();
    11781462
    11791463          // Global update heuristic
    1180           if (relabel_cnt >= next_update_limit) {
     1464          if (relabel_cnt >= next_global_update_limit) {
    11811465            globalUpdate();
    1182             next_update_limit += global_update_freq;
    1183           }
    1184         }
    1185       }
     1466            next_global_update_limit += global_update_skip;
     1467          }
     1468        }
     1469
     1470      }
     1471
    11861472    }
    11871473
     
    11891475    void startPush() {
    11901476      // Paramters for heuristics
    1191       const int EARLY_TERM_EPSILON_LIMIT = 1000;
     1477      const int PRICE_REFINEMENT_LIMIT = 2;
    11921478      const double GLOBAL_UPDATE_FACTOR = 2.0;
    11931479
    1194       const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
     1480      const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR *
    11951481        (_res_node_num + _sup_node_num * _sup_node_num));
    1196       int next_update_limit = global_update_freq;
    1197 
    1198       int relabel_cnt = 0;
     1482      int next_global_update_limit = global_update_skip;
    11991483
    12001484      // Perform cost scaling phases
    12011485      BoolVector hyper(_res_node_num, false);
    12021486      LargeCostVector hyper_cost(_res_node_num);
     1487      int relabel_cnt = 0;
     1488      int eps_phase_cnt = 0;
    12031489      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
    12041490                                        1 : _epsilon / _alpha )
    12051491      {
    1206         // Early termination heuristic
    1207         if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
    1208           if (earlyTermination()) break;
     1492        ++eps_phase_cnt;
     1493
     1494        // Price refinement heuristic
     1495        if (eps_phase_cnt >= PRICE_REFINEMENT_LIMIT) {
     1496          if (priceRefinement()) continue;
    12091497        }
    12101498
     
    12781566               std::numeric_limits<LargeCost>::max();
    12791567            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;
     1568              if (_res_cap[a] > 0) {
     1569                rc = _cost[a] + pi_n - _pi[_target[a]];
     1570                if (rc < min_red_cost) {
     1571                  min_red_cost = rc;
     1572                }
    12831573              }
    12841574            }
     
    12981588
    12991589          // Global update heuristic
    1300           if (relabel_cnt >= next_update_limit) {
     1590          if (relabel_cnt >= next_global_update_limit) {
    13011591            globalUpdate();
    13021592            for (int u = 0; u != _res_node_num; ++u)
    13031593              hyper[u] = false;
    1304             next_update_limit += global_update_freq;
     1594            next_global_update_limit += global_update_skip;
    13051595          }
    13061596        }
  • lemon/cplex.cc

    r1183 r1231  
    492492                   _message_enabled ? CPX_ON : CPX_OFF);
    493493  }
     494
     495  void CplexBase::_write(std::string file, std::string format) const
     496  {
     497    if(format == "MPS" || format == "LP")
     498      CPXwriteprob(cplexEnv(), cplexLp(), file.c_str(), format.c_str());
     499    else if(format == "SOL")
     500      CPXsolwrite(cplexEnv(), cplexLp(), file.c_str());
     501    else throw UnsupportedFormatError(format);
     502  }
     503
     504
    494505
    495506  // CplexLp members
  • lemon/cplex.h

    r793 r1250  
    151151    bool _message_enabled;
    152152
     153    void _write(std::string file, std::string format) const;
     154
    153155  public:
    154156
     
    171173    const cpxlp* cplexLp() const { return _prob; }
    172174
     175#ifdef DOXYGEN
     176    /// Write the problem or the solution to a file in the given format
     177
     178    /// This function writes the problem or the solution
     179    /// to a file in the given format.
     180    /// Trying to write in an unsupported format will trigger
     181    /// \ref lemon::LpBase::UnsupportedFormatError "UnsupportedFormatError".
     182    /// \param file The file path
     183    /// \param format The output file format.
     184    /// Supportted formats are "MPS", "LP" and "SOL".
     185    void write(std::string file, std::string format = "MPS") const {}
     186#endif
     187
    173188  };
    174189
  • lemon/cycle_canceling.h

    r956 r1255  
    3636#include <lemon/bellman_ford.h>
    3737#include <lemon/howard_mmc.h>
     38#include <lemon/hartmann_orlin_mmc.h>
    3839
    3940namespace lemon {
     
    4748  /// \ref CycleCanceling implements three different cycle-canceling
    4849  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    49   /// \ref amo93networkflows, \ref klein67primal,
    50   /// \ref goldberg89cyclecanceling.
    51   /// The most efficent one (both theoretically and practically)
    52   /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
    53   /// thus it is the default method.
    54   /// It is strongly polynomial, but in practice, it is typically much
    55   /// slower than the scaling algorithms and NetworkSimplex.
     50  /// \cite amo93networkflows, \cite klein67primal,
     51  /// \cite goldberg89cyclecanceling.
     52  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
     53  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
     54  /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$,
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
     57  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5658  ///
    5759  /// Most of the parameters of the problem (except for the digraph)
     
    6668  /// algorithm. By default, it is the same as \c V.
    6769  ///
    68   /// \warning Both number types must be signed and all input data must
     70  /// \warning Both \c V and \c C must be signed number types.
     71  /// \warning All input data (capacities, supply values, and costs) must
    6972  /// be integer.
    70   /// \warning This algorithm does not support negative costs for such
    71   /// arcs that have infinite upper bound.
     73  /// \warning This algorithm does not support negative costs for
     74  /// arcs having infinite upper bound.
    7275  ///
    7376  /// \note For more information about the three available methods,
     
    116119    ///
    117120    /// \ref CycleCanceling provides three different cycle-canceling
    118     /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
    119     /// is used, which proved to be the most efficient and the most robust
    120     /// on various test inputs.
     121    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
     122    /// is used, which is by far the most efficient and the most robust.
    121123    /// However, the other methods can be selected using the \ref run()
    122124    /// function with the proper parameter.
    123125    enum Method {
    124126      /// A simple cycle-canceling method, which uses the
    125       /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
    126       /// number for detecting negative cycles in the residual network.
     127      /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
     128      /// cycles in the residual network.
     129      /// The number of Bellman-Ford iterations is bounded by a successively
     130      /// increased limit.
    127131      SIMPLE_CYCLE_CANCELING,
    128132      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    129133      /// well-known strongly polynomial method
    130       /// \ref goldberg89cyclecanceling. It improves along a
     134      /// \cite goldberg89cyclecanceling. It improves along a
    131135      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    132       /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
     136      /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$.
    133137      MINIMUM_MEAN_CYCLE_CANCELING,
    134       /// The "Cancel And Tighten" algorithm, which can be viewed as an
     138      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    135139      /// improved version of the previous method
    136       /// \ref goldberg89cyclecanceling.
     140      /// \cite goldberg89cyclecanceling.
    137141      /// It is faster both in theory and in practice, its running time
    138       /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
     142      /// complexity is \f$O(n^2 m^2 \log n)\f$.
    139143      CANCEL_AND_TIGHTEN
    140144    };
     
    350354    ///
    351355    /// 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
     356    /// with a map in which \c k is assigned to \c s, \c -k is
    353357    /// assigned to \c t and all other nodes have zero supply value.
    354358    ///
     
    573577    ///
    574578    /// This function returns the total cost of the found flow.
    575     /// Its complexity is O(e).
     579    /// Its complexity is O(m).
    576580    ///
    577581    /// \note The return type of the function can be specified as a
     
    611615    }
    612616
    613     /// \brief Return the flow map (the primal solution).
     617    /// \brief Copy the flow values (the primal solution) into the
     618    /// given map.
    614619    ///
    615620    /// This function copies the flow value on each arc into the given
     
    635640    }
    636641
    637     /// \brief Return the potential map (the dual solution).
     642    /// \brief Copy the potential values (the dual solution) into the
     643    /// given map.
    638644    ///
    639645    /// This function copies the potential (dual value) of each node
     
    664670      }
    665671      if (_sum_supply > 0) return INFEASIBLE;
     672
     673      // Check lower and upper bounds
     674      LEMON_DEBUG(checkBoundMaps(),
     675          "Upper bounds must be greater or equal to the lower bounds");
    666676
    667677
     
    773783
    774784      return OPTIMAL;
     785    }
     786   
     787    // Check if the upper bound is greater or equal to the lower bound
     788    // on each arc.
     789