COIN-OR::LEMON - Graph Library

Ignore:
Files:
20 added
26 deleted
134 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

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

    r1264 r1159  
    1313ELSE()
    1414  EXECUTE_PROCESS(
    15     COMMAND
    16     hg log -r. --template "{latesttag}"
     15    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
    1716    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    18     OUTPUT_VARIABLE HG_REVISION_TAG
     17    OUTPUT_VARIABLE HG_REVISION_PATH
    1918    ERROR_QUIET
    2019    OUTPUT_STRIP_TRAILING_WHITESPACE
    2120  )
    2221  EXECUTE_PROCESS(
    23     COMMAND
    24     hg log -r. --template "{latesttagdistance}"
     22    COMMAND hg id -i
    2523    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    26     OUTPUT_VARIABLE HG_REVISION_DIST
     24    OUTPUT_VARIABLE HG_REVISION
    2725    ERROR_QUIET
    2826    OUTPUT_STRIP_TRAILING_WHITESPACE
    2927  )
    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 "")
     28  IF(HG_REVISION STREQUAL "")
    4029    SET(HG_REVISION_ID "hg-tip")
    4130  ELSE()
    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})
     31    IF(HG_REVISION_PATH STREQUAL "")
     32      SET(HG_REVISION_ID ${HG_REVISION})
    4933    ELSE()
    50       SET(HG_REVISION
    51         "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
     34      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
    5235    ENDIF()
    5336  ENDIF()
    54 
    55   SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     37  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
    5638ENDIF()
    5739
     
    6244FIND_PACKAGE(Doxygen)
    6345FIND_PACKAGE(Ghostscript)
    64 
    65 SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
    66 SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
    67 SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
    68 SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
    69 
    70 IF(LEMON_ENABLE_GLPK)
    71   FIND_PACKAGE(GLPK 4.33)
    72 ENDIF(LEMON_ENABLE_GLPK)
    73 IF(LEMON_ENABLE_ILOG)
    74   FIND_PACKAGE(ILOG)
    75 ENDIF(LEMON_ENABLE_ILOG)
    76 IF(LEMON_ENABLE_COIN)
    77   FIND_PACKAGE(COIN)
    78 ENDIF(LEMON_ENABLE_COIN)
    79 IF(LEMON_ENABLE_SOPLEX)
    80   FIND_PACKAGE(SOPLEX)
    81 ENDIF(LEMON_ENABLE_SOPLEX)
    82 
    83 IF(GLPK_FOUND)
    84   SET(LEMON_HAVE_LP TRUE)
    85   SET(LEMON_HAVE_MIP TRUE)
    86   SET(LEMON_HAVE_GLPK TRUE)
    87 ENDIF(GLPK_FOUND)
    88 IF(ILOG_FOUND)
    89   SET(LEMON_HAVE_LP TRUE)
    90   SET(LEMON_HAVE_MIP TRUE)
    91   SET(LEMON_HAVE_CPLEX TRUE)
    92 ENDIF(ILOG_FOUND)
    93 IF(COIN_FOUND)
    94   SET(LEMON_HAVE_LP TRUE)
    95   SET(LEMON_HAVE_MIP TRUE)
    96   SET(LEMON_HAVE_CLP TRUE)
    97   SET(LEMON_HAVE_CBC TRUE)
    98 ENDIF(COIN_FOUND)
    99 IF(SOPLEX_FOUND)
    100   SET(LEMON_HAVE_LP TRUE)
    101   SET(LEMON_HAVE_SOPLEX TRUE)
    102 ENDIF(SOPLEX_FOUND)
    103 
    104 IF(ILOG_FOUND)
    105   SET(DEFAULT_LP "CPLEX")
    106   SET(DEFAULT_MIP "CPLEX")
    107 ELSEIF(COIN_FOUND)
    108   SET(DEFAULT_LP "CLP")
    109   SET(DEFAULT_MIP "CBC")
    110 ELSEIF(GLPK_FOUND)
    111   SET(DEFAULT_LP "GLPK")
    112   SET(DEFAULT_MIP "GLPK")
    113 ELSEIF(SOPLEX_FOUND)
    114   SET(DEFAULT_LP "SOPLEX")
    115 ENDIF()
    116 
    117 IF(NOT LEMON_DEFAULT_LP OR
    118     (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
    119     (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
    120     (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
    121     (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
    122   SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
    123     "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
    124 ENDIF()
    125 IF(NOT LEMON_DEFAULT_MIP OR
    126     (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
    127     (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
    128     (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
    129   SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
    130     "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
    131 ENDIF()
    132 
     46FIND_PACKAGE(GLPK 4.33)
     47FIND_PACKAGE(CPLEX)
     48FIND_PACKAGE(COIN)
    13349
    13450IF(DEFINED ENV{LEMON_CXX_WARNING})
     
    15874SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    15975
    160 IF(MSVC)
    161   SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     76SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
    16277    "Flags used by the C++ compiler during maintainer builds."
    163     )
    164   SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     78    FORCE )
     79SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
    16580    "Flags used by the C compiler during maintainer builds."
    166     )
    167   SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    168     "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
    169     "Flags used for linking binaries during maintainer builds."
    170     )
    171   SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    172     "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
    173     "Flags used by the shared libraries linker during maintainer builds."
    174     )
    175 ELSE()
    176   SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
    177     "Flags used by the C++ compiler during maintainer builds."
    178     )
    179   SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
    180     "Flags used by the C compiler during maintainer builds."
    181     )
    182   SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     81    FORCE )
     82SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    18383    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    18484    "Flags used for linking binaries during maintainer builds."
    185     )
    186   SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     85    FORCE )
     86SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    18787    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    18888    "Flags used by the shared libraries linker during maintainer builds."
    189     )
    190 ENDIF()
    191 
     89    FORCE )
    19290MARK_AS_ADVANCED(
    19391    CMAKE_CXX_FLAGS_MAINTAINER
     
    217115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    218116
    219 INCLUDE(FindThreads)
    220 
    221 IF(NOT LEMON_THREADING)
    222   IF(CMAKE_USE_PTHREADS_INIT)
    223     SET(LEMON_THREADING "Pthread")
    224   ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
    225     SET(LEMON_THREADING "Win32")
    226   ELSE()
    227     SET(LEMON_THREADING "None")
    228   ENDIF()
    229 ENDIF()
    230 
    231 SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
    232   "Choose the threading library, options are: Pthread Win32 None."
    233   FORCE )
    234 
    235 IF(LEMON_THREADING STREQUAL "Pthread")
    236   SET(LEMON_USE_PTHREAD TRUE)
    237 ELSEIF(LEMON_THREADING STREQUAL "Win32")
    238   SET(LEMON_USE_WIN32_THREADS TRUE)
    239 ENDIF()
     117INCLUDE(FindPythonInterp)
    240118
    241119ENABLE_TESTING()
     
    249127ADD_SUBDIRECTORY(lemon)
    250128IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    251   ADD_SUBDIRECTORY(contrib)
    252129  ADD_SUBDIRECTORY(demo)
    253130  ADD_SUBDIRECTORY(tools)
     
    273150ENDIF()
    274151
    275 CONFIGURE_FILE(
    276   ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
    277   ${PROJECT_BINARY_DIR}/cmake/version.cmake
    278   @ONLY
    279 )
    280 
    281 SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
    282 STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
    283 SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
    284 ADD_CUSTOM_TARGET(dist
    285   COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
    286   COMMAND hg archive ${ARCHIVE_NAME}
    287   COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
    288   COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
    289   COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
    290   COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
    291   COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
    292   COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
    293   COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
    294   COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
    295   COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
    296   COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
    297   COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
    298   DEPENDS html
    299   WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
    300 
    301 # CPACK config (Basically for NSIS)
    302152IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    303153  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
  • INSTALL

    r1233 r890  
    22=========================
    33
    4 This file contains instructions for building and installing LEMON from
    5 source on Linux. The process on Windows is similar.
     4Since you are reading this I assume you already obtained one of the release
     5tarballs and successfully extracted it. The latest version of LEMON is
     6available at our web page (http://lemon.cs.elte.hu/).
    67
    7 Note that it is not necessary to install LEMON in order to use
    8 it. Instead, you can easily integrate it with your own code
    9 directly. For instructions, see
    10 https://lemon.cs.elte.hu/trac/lemon/wiki/HowToCompile
    11 
     8LEMON provides two different build environments, one is based on "autotool",
     9while the other is based on "cmake". This file contains instructions only for
     10the former one, which is the recommended build environment on Linux, Mac OSX
     11and other unices or if you use Cygwin on Windows. For cmake installation
     12instructions visit http://lemon.cs.elte.hu.
    1213
    1314In order to install LEMON from the extracted source tarball you have to
    1415issue the following commands:
    1516
    16    1. Step into the root of the source directory.
     17   1. `cd lemon-x.y.z'
    1718
    18       $ cd lemon-x.y.z
     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.
    1921
    20    2. Create a build subdirectory and step into it.
     22   2. `./configure'
    2123
    22       $ mkdir build
    23       $ cd build
     24      This command runs the configure shell script, which does some checks and
     25      creates the makefiles.
    2426
    25    3. Perform system checks and create the makefiles.
     27   3. `make'
    2628
    27       $ cmake ..
     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.
    2832
    29    4. Build LEMON.
     33   4. `make check'
    3034
    31       $ make
     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.
    3238
    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
     39   5. `make install'
    5340
    5441      This command installs LEMON under /usr/local (you will need root
    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'
     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
    6154
    6255Configure Options and Variables
    6356===============================
    6457
    65 In Step 3, you can customize the build process by passing options to CMAKE.
     58In step 2 you can customize the actions of configure by setting variables
     59and passing options to it. This can be done like this:
     60`./configure [OPTION]... [VARIABLE=VALUE]...'
    6661
    67 $ cmake [OPTIONS] ..
     62Below you will find some useful variables and options (see `./configure --help'
     63for more):
    6864
    69 You find a list of the most useful options below.
     65CXX='comp'
    7066
    71 -DCMAKE_INSTALL_PREFIX=PREFIX
     67  Change the C++ compiler to 'comp'.
     68
     69CXXFLAGS='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
    7275
    7376  Set the installation prefix to PREFIX. By default it is /usr/local.
    7477
    75 -DCMAKE_BUILD_TYPE=[Release|Debug|Maintainer|...]
     78--enable-tools
    7679
    77   This sets the compiler options. The choices are the following
     80   Build the programs in the tools subdirectory (default).
    7881
    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.
     82--disable-tools
    8283
    83   'Debug': Optimization is turned off and debug info is added (-O0
    84     -ggdb with gcc). If is recommended during the development.
     84   Do not build the programs in the tools subdirectory.
    8585
    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.
     86--with-glpk[=PREFIX]
    9087
    91   'RelWithDebInfo': Optimized build with debug info.
     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.
    9291
    93   'MinSizeRel': Size optimized build (-Os with gcc)
     92--with-glpk-includedir=DIR
    9493
    95 -DTEST_WITH_VALGRIND=YES
     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).
    9697
    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.
     98--with-glpk-libdir=DIR
    9999
    100 -DCMAKE_CXX_COMPILER=path-to-compiler
     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).
    101103
    102   Change the compiler to be used.
     104--without-glpk
    103105
    104 -DBUILD_SHARED_LIBS=TRUE
     106   Disable GLPK support.
    105107
    106   Build shared library instead of static one. Think twice if you
    107   really want to use this option.
     108--with-cplex[=PREFIX]
    108109
    109 -DLEMON_DOC_SOURCE_BROWSER=YES
     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.
    110114
    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.
     115--with-cplex-includedir=DIR
    114116
    115 -DLEMON_DOC_USE_MATHJAX=YES
     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).
    116120
    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.
     121--with-cplex-libdir=DIR
    121122
    122   On the other hand, it needs either Internet access or a locally
    123   installed version of MathJax to properly render the doc.
     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).
    124127
    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.
     128--without-cplex
    133129
    134   See http://docs.mathjax.org/en/latest/installation.html for more details.
     130   Disable CPLEX support.
    135131
    136  
    137 -DLEMON_ENABLE_GLPK=NO
    138 -DLEMON_ENABLE_COIN=NO
    139 -DLEMON_ENABLE_ILOG=NO
     132--with-soplex[=PREFIX]
    140133
    141   Enable optional third party libraries. They are all enabled by default.
     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.
    142137
    143 -DLEMON_DEFAULT_LP=GLPK
     138--with-soplex-includedir=DIR
    144139
    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.
     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).
    148143
    149 -DLEMON_DEFAULT_MIP=GLPK
     144--with-soplex-libdir=DIR
    150145
    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.
     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).
    154149
    155 -DGLPK_ROOT_DIR=DIRECTORY
    156 -DCOIN_ROOT_DIR=DIRECTORY
    157 -DILOG_ROOT_DIR=DIRECTORY
     150--without-soplex
    158151
    159   Root directory prefixes of optional third party libraries.
     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
    160177
    161178Makefile Variables
    162179==================
    163180
    164 make VERBOSE=1
     181Some Makefile variables are reserved by the GNU Coding Standards for
     182the use of the "user" - the person building the package. For instance,
     183CXX and CXXFLAGS are such variables, and have the same meaning as
     184explained in the previous section. These variables can be set on the
     185command line when invoking `make' like this:
     186`make [VARIABLE=VALUE]...'
    165187
    166    This results in a more verbose output by showing the full
    167    compiler and linker commands.
     188WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
     189to hold several compiler flags related to warnings. Its default value
     190can be overridden when invoking `make'. For example to disable all
     191warning flags use `make WARNINGCXXFLAGS='.
     192
     193In order to turn off a single flag from the default set of warning
     194flags, you can use the CXXFLAGS variable, since this is passed after
     195WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
     196used by default when g++ is detected) you can use
     197`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
  • LICENSE

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

    r1281 r962  
    1 2013-08-10 Version 1.3 released
    2 
    3         This is major feature release
    4 
    5         * New data structures
    6 
    7           #69 : Bipartite graph concepts and implementations
    8 
    9         * New algorithms
    10 
    11           #177: Port Edmonds-Karp algorithm
    12           #380, #405: Heuristic algorithm for the max clique problem
    13           #386: Heuristic algorithms for symmetric TSP
    14           ----: Nagamochi-Ibaraki algorithm [5087694945e4]
    15           #397, #56: Max. cardinality search
    16 
    17         * Other new features
    18 
    19           #223: Thread safe graph and graph map implementations
    20           #442: Different TimeStamp print formats
    21           #457: File export functionality to LpBase
    22           #362: Bidirectional iterator support for radixSort()
    23 
    24         * Implementation improvements
    25 
    26           ----: Network Simplex
    27                 #391: Better update process, pivot rule and arc mixing
    28                 #435: Improved Altering List pivot rule
    29           #417: Various fine tunings in CostScaling
    30           #438: Optional iteration limit in HowardMmc
    31           #436: Ensure strongly polynomial running time for CycleCanceling
    32                 while keeping the same performance
    33           ----: Make the CBC interface be compatible with latest CBC releases
    34                 [ee581a0ecfbf]
    35 
    36         * CMAKE has become the default build environment (#434)
    37 
    38           ----: Autotool support has been dropped
    39           ----: Improved LP/MIP configuration
    40                 #465: Enable/disable options for LP/MIP backends
    41                 #446: Better CPLEX discovery
    42                 #460: Add cmake config to find SoPlex
    43           ----: Allow CPACK configuration on all platforms
    44           #390: Add 'Maintainer' CMAKE build type
    45           #388: Add 'check' target.
    46           #401: Add contrib dir
    47           #389: Better version string setting in CMAKE
    48           #433: Support shared library build   
    49           #416: Support testing with valgrind
    50  
    51         * Doc improvements
    52 
    53           #395: SOURCE_BROWSER Doxygen switch is configurable from CMAKE
    54                 update-external-tags CMAKE target
    55           #455: Optionally use MathJax for rendering the math formulae
    56           #402, #437, #459, #456, #463: Various doc improvements
    57 
    58         * Bugfixes (compared to release 1.2):
    59 
    60           #432: Add missing doc/template.h and doc/references.bib to release
    61                 tarball
    62           ----: Intel C++ compatibility fixes
    63           #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
    64           #444: Bugfix in path copy constructors and assignment operators
    65           #447: Bugfix in AllArcLookUp<>
    66           #448: Bugfix in adaptor_test.cc
    67           #449: Fix clang compilation warnings and errors
    68           #440: Fix a bug + remove redundant typedefs in dimacs-solver
    69           #453: Avoid GCC 4.7 compiler warnings
    70           #445: Fix missing initialization in CplexEnv::CplexEnv()
    71           #428: Add missing lemon/lemon.pc.cmake to the release tarball
    72           #393: Create and install lemon.pc
    73           #429: Fix VS warnings
    74           #430: Fix LpBase::Constr two-side limit bug
    75           #392: Bug fix in Dfs::start(s,t)
    76           #414: Fix wrong initialization in Preflow
    77           #418: Better Win CodeBlock/MinGW support
    78           #419: Build environment improvements
    79                 - Build of mip_test and lp_test precede the running of the tests
    80                 - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
    81                 - Do not look for COIN_VOL libraries
    82           #382: Allow lgf file without Arc maps
    83           #417: Bug fix in CostScaling
    84           #366: Fix Pred[Matrix]MapPath::empty()
    85           #371: Bug fix in (di)graphCopy()
    86                 The target graph is cleared before adding nodes and arcs/edges.
    87           #364: Add missing UndirectedTags
    88           #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
    89           #372: Fix a critical bug in preflow
    90           #461: Bugfix in assert.h
    91           #470: Fix compilation issues related to various gcc versions
    92           #446: Fix #define indicating CPLEX availability
    93           #294: Add explicit namespace to
    94                 ignore_unused_variable_warning() usages
    95           #420: Bugfix in IterableValueMap
    96           #439: Bugfix in biNodeConnected()
    97 
    98 
    9912010-03-19 Version 1.2 released
    1002
  • cmake/FindCOIN.cmake

    r1232 r1120  
    109109  COIN_BZ2_LIBRARY
    110110)
     111
     112IF(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)
     117ENDIF(COIN_FOUND)
  • cmake/FindGLPK.cmake

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

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

    r1251 r1107  
    55
    66SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
    7 SET(LEMON_DOC_USE_MATHJAX "NO" CACHE STRING "Use MathJax to display math formulae (YES/NO).")
    8 SET(LEMON_DOC_MATHJAX_RELPATH "http://www.mathjax.org/mathjax" CACHE STRING "MathJax library location.")
    9 
    10 SET(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 
    147
    158CONFIGURE_FILE(
     
    2518)
    2619
    27 # Copy doc from source (if exists)
    28 IF(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     )
    34 ENDIF()
    35 
    3620IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    3721  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     
    4024    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    4125    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    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
     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
    5840    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
    5942    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    6043    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     
    8164IF(WGET_FOUND)
    8265ADD_CUSTOM_TARGET(update-external-tags
    83   COMMAND ${WGET_EXECUTABLE} -N ${LEMON_DOC_LIBSTDC++_URL}/libstdc++.tag
     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
    8472  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    8573  )
  • doc/Doxyfile.in

    r1251 r1107  
    7878FILE_VERSION_FILTER    =
    7979LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
    80 CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    8180#---------------------------------------------------------------------------
    8281# configuration options related to warning and progress messages
     
    9796                         "@abs_top_srcdir@/lemon/concepts" \
    9897                         "@abs_top_srcdir@/demo" \
    99                          "@abs_top_srcdir@/contrib" \
    10098                         "@abs_top_srcdir@/tools" \
    10199                         "@abs_top_srcdir@/test/test_tools.h" \
    102                          "@abs_top_builddir@/doc/mainpage.dox"
     100                         "@abs_top_builddir@/doc/mainpage.dox" \
     101                         "@abs_top_builddir@/doc/references.dox"
    103102INPUT_ENCODING         = UTF-8
    104103FILE_PATTERNS          = *.h \
     
    183182FORMULA_FONTSIZE       = 10
    184183FORMULA_TRANSPARENT    = YES
    185 USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
    186 MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
     184USE_MATHJAX            = NO
     185MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
    187186SEARCHENGINE           = YES
    188187SERVER_BASED_SEARCH    = NO
     
    254253# Configuration::additions related to external references
    255254#---------------------------------------------------------------------------
    256 TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
     255TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    257256GENERATE_TAGFILE       = html/lemon.tag
    258257ALLEXTERNALS           = NO
  • doc/DoxygenLayout.xml

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

    r1270 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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_underscore
     104_start_with_underscores
    105105\endcode
    106106
  • doc/dirs.dox

    r1270 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3232documentation.
    3333*/
    34 
    35 /**
    36 \dir contrib
    37 \brief Directory for user contributed source codes.
    38 
    39 You can place your own C++ code using LEMON into this directory, which
    40 will compile to an executable along with LEMON when you build the
    41 library. This is probably the easiest way of compiling short to medium
    42 codes, for this does require neither a LEMON installed system-wide nor
    43 adding several paths to the compiler.
    44 
    45 Please have a look at <tt>contrib/CMakeLists.txt</tt> for
    46 instruction on how to add your own files into the build process.  */
    4734
    4835/**
  • doc/groups.dox

    r1280 r959  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    113113detailed documentation of particular adaptors.
    114114
    115 Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
    116 an adaptor can even be applied to another one.
    117 The following image illustrates a situation when a \ref SubDigraph adaptor
    118 is 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 
    123115The behavior of graph adaptors can be very different. Some of them keep
    124116capabilities of the original graph while in other cases this would be
     
    295287
    296288/**
     289@defgroup matrices Matrices
     290@ingroup auxdat
     291\brief Two dimensional data storages implemented in LEMON.
     292
     293This group contains two dimensional data storages implemented in LEMON.
     294*/
     295
     296/**
    297297@defgroup algs Algorithms
    298298\brief This group contains the several algorithms
     
    310310This group contains the common graph search algorithms, namely
    311311\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \cite clrs01algorithms.
     312\ref clrs01algorithms.
    313313*/
    314314
     
    319319
    320320This group contains the algorithms for finding shortest paths in digraphs
    321 \cite clrs01algorithms.
     321\ref clrs01algorithms.
    322322
    323323 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    327327   but the digraph should not contain directed cycles with negative total
    328328   length.
     329 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     330   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     331   lenghts can be either positive or negative, but the digraph should
     332   not contain directed cycles with negative total length.
    329333 - \ref Suurballe A successive shortest path algorithm for finding
    330334   arc-disjoint paths between two nodes having minimum total length.
     
    337341
    338342This group contains the algorithms for finding minimum cost spanning
    339 trees and arborescences \cite clrs01algorithms.
     343trees and arborescences \ref clrs01algorithms.
    340344*/
    341345
     
    346350
    347351This group contains the algorithms for finding maximum flows and
    348 feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
     352feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    349353
    350354The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    360364\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    361365
    362 \ref Preflow is an efficient implementation of Goldberg-Tarjan's
    363 preflow push-relabel algorithm \cite goldberg88newapproach for finding
    364 maximum flows. It also provides functions to query the minimum cut,
    365 which is the dual problem of maximum flow.
     366LEMON contains several algorithms for solving maximum flow problems:
     367- \ref EdmondsKarp Edmonds-Karp algorithm
     368  \ref edmondskarp72theoretical.
     369- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     370  \ref goldberg88newapproach.
     371- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     372  \ref dinic70algorithm, \ref sleator83dynamic.
     373- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     374  \ref goldberg88newapproach, \ref sleator83dynamic.
     375
     376In most cases the \ref Preflow algorithm provides the
     377fastest method for computing a maximum flow. All implementations
     378also provide functions to query the minimum cut, which is the dual
     379problem of maximum flow.
    366380
    367381\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    378392
    379393This group contains the algorithms for finding minimum cost flows and
    380 circulations \cite amo93networkflows. For more information about this
    381 problem and its dual solution, see: \ref min_cost_flow
     394circulations \ref amo93networkflows. For more information about this
     395problem and its dual solution, see \ref min_cost_flow
    382396"Minimum Cost Flow Problem".
    383397
    384398LEMON contains several algorithms for this problem.
    385399 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    386    pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
     400   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    387401 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    388    relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
    389    \cite bunnagel98efficient.
     402   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     403   \ref bunnagel98efficient.
    390404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    391    shortest path method \cite edmondskarp72theoretical.
     405   shortest path method \ref edmondskarp72theoretical.
    392406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    393    strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
    394 
    395 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
    396 implementations.
    397 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to
    398 several thousands of nodes) and on dense graphs, while \ref CostScaling is
    399 typically more efficient on large graphs (e.g. hundreds of thousands of
    400 nodes or above), especially if they are sparse.
    401 However, other algorithms could be faster in special cases.
     407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     408
     409In general NetworkSimplex is the most efficient implementation,
     410but in special cases other algorithms could be faster.
    402411For example, if the total supply and/or capacities are rather small,
    403 \ref CapacityScaling is usually the fastest algorithm
    404 (without effective scaling).
    405 
    406 These classes are intended to be used with integer-valued input data
    407 (capacities, supply values, and costs), except for \ref CapacityScaling,
    408 which is capable of handling real-valued arc costs (other numerical
    409 data are required to be integer).
    410 
    411 For more details about these implementations and for a comprehensive
    412 experimental study, see the paper \cite KiralyKovacs12MCF.
    413 It also compares these codes to other publicly available
    414 minimum cost flow solvers.
     412CapacityScaling is usually the fastest algorithm (without effective scaling).
    415413*/
    416414
     
    451449
    452450This group contains the algorithms for finding minimum mean cycles
    453 \cite amo93networkflows, \cite karp78characterization.
     451\ref clrs01algorithms, \ref amo93networkflows.
    454452
    455453The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    467465
    468466LEMON contains three algorithms for solving the minimum mean cycle problem:
    469 - \ref KarpMmc Karp's original algorithm \cite karp78characterization.
     467- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     468  \ref dasdan98minmeancycle.
    470469- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    471   version of Karp's algorithm \cite hartmann93finding.
     470  version of Karp's algorithm \ref dasdan98minmeancycle.
    472471- \ref HowardMmc Howard's policy iteration algorithm
    473   \cite dasdan98minmeancycle, \cite dasdan04experimental.
    474 
    475 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     472  \ref dasdan98minmeancycle.
     473
     474In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
    476475most efficient one, though the best known theoretical bound on its running
    477476time is exponential.
    478477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    479 run in time O(nm) and use space O(n<sup>2</sup>+m).
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    480480*/
    481481
     
    498498
    499499The matching algorithms implemented in LEMON:
     500- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     501  for calculating maximum cardinality matching in bipartite graphs.
     502- \ref PrBipartiteMatching Push-relabel algorithm
     503  for calculating maximum cardinality matching in bipartite graphs.
     504- \ref MaxWeightedBipartiteMatching
     505  Successive shortest path algorithm for calculating maximum weighted
     506  matching and maximum weighted bipartite matching in bipartite graphs.
     507- \ref MinCostMaxBipartiteMatching
     508  Successive shortest path algorithm for calculating minimum cost maximum
     509  matching in bipartite graphs.
    500510- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    501511  maximum cardinality matching in general graphs.
     
    530540
    531541/**
    532 @defgroup planar Planar Embedding and Drawing
     542@defgroup planar Planarity Embedding and Drawing
    533543@ingroup algs
    534544\brief Algorithms for planarity checking, embedding and drawing
     
    542552
    543553/**
    544 @defgroup tsp Traveling Salesman Problem
    545 @ingroup algs
    546 \brief Algorithms for the symmetric traveling salesman problem
    547 
    548 This group contains basic heuristic algorithms for the the symmetric
    549 \e traveling \e salesman \e problem (TSP).
    550 Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
    551 the problem is to find a shortest possible tour that visits each node exactly
    552 once (i.e. the minimum cost Hamiltonian cycle).
    553 
    554 These TSP algorithms are intended to be used with a \e metric \e cost
    555 \e function, i.e. the edge costs should satisfy the triangle inequality.
    556 Otherwise the algorithms could yield worse results.
    557 
    558 LEMON provides five well-known heuristics for solving symmetric TSP:
    559  - \ref NearestNeighborTsp Neareast neighbor algorithm
    560  - \ref GreedyTsp Greedy algorithm
    561  - \ref InsertionTsp Insertion heuristic (with four selection methods)
    562  - \ref ChristofidesTsp Christofides algorithm
    563  - \ref Opt2Tsp 2-opt algorithm
    564 
    565 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
    566 solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
    567 
    568 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
    569 approximation factor: 3/2.
    570 
    571 \ref Opt2Tsp usually provides the best results in practice, but
    572 it is the slowest method. It can also be used to improve given tours,
    573 for example, the results of other algorithms.
    574 
    575 \image html tsp.png
    576 \image latex tsp.eps "Traveling salesman problem" width=\textwidth
    577 */
    578 
    579 /**
    580 @defgroup approx_algs Approximation Algorithms
     554@defgroup approx Approximation Algorithms
    581555@ingroup algs
    582556\brief Approximation algorithms.
     
    584558This group contains the approximation and heuristic algorithms
    585559implemented in LEMON.
    586 
    587 <b>Maximum Clique Problem</b>
    588   - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
    589     Grosso, Locatelli, and Pullan.
    590560*/
    591561
     
    617587high-level interface.
    618588
    619 The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
    620 \cite cplex, \cite soplex.
     589The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     590\ref cplex, \ref soplex.
     591*/
     592
     593/**
     594@defgroup lp_utils Tools for Lp and Mip Solvers
     595@ingroup lp_group
     596\brief Helper tools to the Lp and Mip solvers.
     597
     598This group adds some helper tools to general optimization framework
     599implemented in LEMON.
     600*/
     601
     602/**
     603@defgroup metah Metaheuristics
     604@ingroup gen_opt_group
     605\brief Metaheuristics for LEMON library.
     606
     607This group contains some metaheuristic optimization tools.
    621608*/
    622609
     
    688675This group contains general \c EPS drawing methods and special
    689676graph exporting tools.
    690 
    691 \image html graph_to_eps.png
    692677*/
    693678
  • doc/images/bipartite_partitions.eps

    r1213 r634  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Mar  8 00:18:43 2013
     3%%CreationDate: Tue Nov 15 16:51:43 2005
    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 7.00153 lb
    57 513.857 -446.322 575.52 -315.656 637.183 -184.989 0 0 0 7.00153 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 7.00153 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 7.00153 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 7.00153 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 7.00153 lb
    62 869.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
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 7.00153 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 7.00153 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 7.00153 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 7.00153 lb
    78 399.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
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 7.00153 lb
     56513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
     57513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
     58393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
     59393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
     60393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
     61869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
     62869.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
     7479.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
     75637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
     76205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
     77399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
     78399.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
     85120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
    8686grestore
    8787%Nodes:
    8888gsave
    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
    92 108.644 334.741 23.3384 0 0 1 nc
    93 120.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
    98 399.34 88.0898 23.3384 1 0 0 nc
    99 205.543 -322.996 23.3384 1 0 0 nc
    100 637.183 -184.989 23.3384 0 0 1 nc
    101 79.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
    108 596.074 302.442 23.3384 0 0 1 nc
    109 869.153 52.8539 23.3384 1 0 0 nc
    110 393.468 566.711 23.3384 1 0 0 nc
    111 513.857 -446.322 23.3384 1 0 0 nc
     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
     92108.644 334.741 20 0 0 1 nc
     93120.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
     98399.34 88.0898 20 1 0 0 nc
     99205.543 -322.996 20 1 0 0 nc
     100637.183 -184.989 20 0 0 1 nc
     10179.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
     108596.074 302.442 20 0 0 1 nc
     109869.153 52.8539 20 1 0 0 nc
     110393.468 566.711 20 1 0 0 nc
     111513.857 -446.322 20 1 0 0 nc
    112112grestore
    113113grestore
  • doc/images/connected_components.eps

    r1213 r634  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Mar  8 00:18:43 2013
     3%%CreationDate: Fri Nov  4 13:47:12 2005
    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 6.25356 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 6.25356 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 6.25356 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 6.25356 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 6.25356 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 6.25356 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 6.25356 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 6.25356 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 6.25356 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 6.25356 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 6.25356 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 6.25356 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 6.25356 lb
    69 277.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
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 6.25356 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 6.25356 lb
    76 986.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
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 6.25356 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 6.25356 lb
    80 422.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
    82 329.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
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 6.25356 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 6.25356 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 6.25356 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 6.25356 lb
    88 415.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
    97 116.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
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 6.25356 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 6.25356 lb
    108 588.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
     56574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
     69277.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
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
     76986.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
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
     80422.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
     82329.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
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
     88415.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
     97116.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
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
     108588.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
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20.8452 0 0 0 nc
    115 -689.204 -237.261 20.8452 0 0 0 nc
    116 924.667 409.347 20.8452 1 0 0 nc
    117 588.113 544.499 20.8452 1 0 0 nc
    118 670.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
    125 201.208 38.3422 20.8452 0 1 0 nc
    126 116.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
    132 415.393 -289.516 20.8452 0 0 1 nc
    133 730.084 -307.139 20.8452 0 0 1 nc
    134 526.164 32.7279 20.8452 0 0 1 nc
    135 762.812 -17.6227 20.8452 0 0 1 nc
    136 -67.9734 319.727 20.8452 0 0 1 nc
    137 329.797 314.692 20.8452 0 0 1 nc
    138 -5.03507 561.41 20.8452 0 0 1 nc
    139 422.945 521.129 20.8452 0 0 1 nc
    140 -470.779 158.605 20.8452 0 0 1 nc
    141 986.873 -115.807 20.8452 0 0 1 nc
    142 906.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
    146 206.221 -205.967 20.8452 1 1 0 nc
    147 277.311 -252.33 20.8452 1 1 0 nc
    148 271.13 -175.058 20.8452 1 1 0 nc
    149 366.947 -110.15 20.8452 1 1 0 nc
    150 397.855 -196.694 20.8452 1 1 0 nc
    151 438.037 -88.514 20.8452 1 1 0 nc
    152 286.584 -48.3327 20.8452 1 1 0 nc
    153 212.403 -23.6057 20.8452 1 1 0 nc
    154 280.402 10.3938 20.8452 1 1 0 nc
    155 694.579 115.483 20.8452 1 0 0 nc
    156 574.035 177.301 20.8452 1 0 0 nc
     114-567.302 43.6423 20 0 0 0 nc
     115-689.204 -237.261 20 0 0 0 nc
     116924.667 409.347 20 1 0 0 nc
     117588.113 544.499 20 1 0 0 nc
     118670.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
     125201.208 38.3422 20 0 1 0 nc
     126116.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
     132415.393 -289.516 20 0 0 1 nc
     133730.084 -307.139 20 0 0 1 nc
     134526.164 32.7279 20 0 0 1 nc
     135762.812 -17.6227 20 0 0 1 nc
     136-67.9734 319.727 20 0 0 1 nc
     137329.797 314.692 20 0 0 1 nc
     138-5.03507 561.41 20 0 0 1 nc
     139422.945 521.129 20 0 0 1 nc
     140-470.779 158.605 20 0 0 1 nc
     141986.873 -115.807 20 0 0 1 nc
     142906.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
     146206.221 -205.967 20 1 1 0 nc
     147277.311 -252.33 20 1 1 0 nc
     148271.13 -175.058 20 1 1 0 nc
     149366.947 -110.15 20 1 1 0 nc
     150397.855 -196.694 20 1 1 0 nc
     151438.037 -88.514 20 1 1 0 nc
     152286.584 -48.3327 20 1 1 0 nc
     153212.403 -23.6057 20 1 1 0 nc
     154280.402 10.3938 20 1 1 0 nc
     155694.579 115.483 20 1 0 0 nc
     156574.035 177.301 20 1 0 0 nc
    157157grestore
    158158grestore
  • doc/images/edge_biconnected_components.eps

    r1213 r634  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Mar  8 00:18:43 2013
     3%%CreationDate: Fri Nov  4 13:47:12 2005
    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 6.25356 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 6.25356 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 6.25356 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 6.25356 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 6.25356 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 6.25356 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 6.25356 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 6.25356 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 6.25356 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 6.25356 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 6.25356 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 6.25356 lb
    69 277.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
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 6.25356 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 6.25356 lb
    76 986.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
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 6.25356 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 6.25356 lb
    80 422.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
    82 329.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
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 6.25356 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 6.25356 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 6.25356 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 6.25356 lb
    88 415.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
    97 116.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
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
    108 588.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
     56574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
     69277.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
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
     76986.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
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
     80422.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
     82329.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
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
     88415.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
     97116.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
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
     108588.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
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20.8452 0 0 0 nc
    115 -689.204 -237.261 20.8452 0 0 0 nc
    116 924.667 409.347 20.8452 0 0 1 nc
    117 588.113 544.499 20.8452 0 0 1 nc
    118 670.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
    125 201.208 38.3422 20.8452 1 1 0 nc
    126 116.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
    132 415.393 -289.516 20.8452 0.5 0 0 nc
    133 730.084 -307.139 20.8452 0.5 0 0 nc
    134 526.164 32.7279 20.8452 0.5 0 0 nc
    135 762.812 -17.6227 20.8452 0.5 0 0 nc
    136 -67.9734 319.727 20.8452 0.5 0 0 nc
    137 329.797 314.692 20.8452 0.5 0 0 nc
    138 -5.03507 561.41 20.8452 0.5 0 0 nc
    139 422.945 521.129 20.8452 0.5 0 0 nc
    140 -470.779 158.605 20.8452 0 1 1 nc
    141 986.873 -115.807 20.8452 0.5 0 0 nc
    142 906.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
    146 206.221 -205.967 20.8452 0 0 0.5 nc
    147 277.311 -252.33 20.8452 0 0 0.5 nc
    148 271.13 -175.058 20.8452 0 0 0.5 nc
    149 366.947 -110.15 20.8452 0 0 0.5 nc
    150 397.855 -196.694 20.8452 0 0 0.5 nc
    151 438.037 -88.514 20.8452 0 0 0.5 nc
    152 286.584 -48.3327 20.8452 0 0 0.5 nc
    153 212.403 -23.6057 20.8452 0 0 0.5 nc
    154 280.402 10.3938 20.8452 0 0 0.5 nc
    155 694.579 115.483 20.8452 1 0 0 nc
    156 574.035 177.301 20.8452 0 1 0 nc
     114-567.302 43.6423 20 0 0 0 nc
     115-689.204 -237.261 20 0 0 0 nc
     116924.667 409.347 20 0 0 1 nc
     117588.113 544.499 20 0 0 1 nc
     118670.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
     125201.208 38.3422 20 1 1 0 nc
     126116.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
     132415.393 -289.516 20 0.5 0 0 nc
     133730.084 -307.139 20 0.5 0 0 nc
     134526.164 32.7279 20 0.5 0 0 nc
     135762.812 -17.6227 20 0.5 0 0 nc
     136-67.9734 319.727 20 0.5 0 0 nc
     137329.797 314.692 20 0.5 0 0 nc
     138-5.03507 561.41 20 0.5 0 0 nc
     139422.945 521.129 20 0.5 0 0 nc
     140-470.779 158.605 20 0 1 1 nc
     141986.873 -115.807 20 0.5 0 0 nc
     142906.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
     146206.221 -205.967 20 0 0 0.5 nc
     147277.311 -252.33 20 0 0 0.5 nc
     148271.13 -175.058 20 0 0 0.5 nc
     149366.947 -110.15 20 0 0 0.5 nc
     150397.855 -196.694 20 0 0 0.5 nc
     151438.037 -88.514 20 0 0 0.5 nc
     152286.584 -48.3327 20 0 0 0.5 nc
     153212.403 -23.6057 20 0 0 0.5 nc
     154280.402 10.3938 20 0 0 0.5 nc
     155694.579 115.483 20 1 0 0 nc
     156574.035 177.301 20 0 1 0 nc
    157157grestore
    158158grestore
  • doc/images/node_biconnected_components.eps

    r1213 r634  
    11%!PS-Adobe-2.0 EPSF-2.0
    22%%Creator: LEMON, graphToEps()
    3 %%CreationDate: Fri Mar  8 00:18:43 2013
     3%%CreationDate: Fri Nov  4 13:47:12 2005
    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 6.25356 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 6.25356 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 6.25356 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 6.25356 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 6.25356 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 6.25356 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 6.25356 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 6.25356 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 6.25356 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 6.25356 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 6.25356 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 6.25356 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 6.25356 lb
    69 277.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
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 6.25356 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 6.25356 lb
    76 986.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
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 6.25356 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 6.25356 lb
    80 422.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
    82 329.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
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 6.25356 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 6.25356 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 6.25356 lb
    88 415.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
    97 116.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
    106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 6.25356 lb
    107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 6.25356 lb
    108 588.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
     56574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
     57694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
     58280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
     59280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
     60212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
     61286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
     62286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
     63438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
     64438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
     65397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
     66366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
     67271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
     68271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
     69277.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
     74906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
     75906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
     76986.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
     78422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
     79422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
     80422.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
     82329.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
     84762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
     85762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
     86526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
     87730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
     88415.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
     97116.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
     106670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
     107670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
     108588.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
    111111grestore
    112112%Nodes:
    113113gsave
    114 -567.302 43.6423 20.8452 0 0 1 nc
    115 -689.204 -237.261 20.8452 0 0 1 nc
    116 924.667 409.347 20.8452 0 0 1 nc
    117 588.113 544.499 20.8452 0 0 1 nc
    118 670.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
    125 201.208 38.3422 20.8452 0 0 1 nc
    126 116.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
    132 415.393 -289.516 20.8452 1 0 0 nc
    133 730.084 -307.139 20.8452 0 0 1 nc
    134 526.164 32.7279 20.8452 1 0 0 nc
    135 762.812 -17.6227 20.8452 1 0 0 nc
    136 -67.9734 319.727 20.8452 0 0 1 nc
    137 329.797 314.692 20.8452 0 0 1 nc
    138 -5.03507 561.41 20.8452 0 0 1 nc
    139 422.945 521.129 20.8452 0 0 1 nc
    140 -470.779 158.605 20.8452 1 0 0 nc
    141 986.873 -115.807 20.8452 0 0 1 nc
    142 906.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
    146 206.221 -205.967 20.8452 0 0 1 nc
    147 277.311 -252.33 20.8452 0 0 1 nc
    148 271.13 -175.058 20.8452 1 0 0 nc
    149 366.947 -110.15 20.8452 1 0 0 nc
    150 397.855 -196.694 20.8452 0 0 1 nc
    151 438.037 -88.514 20.8452 0 0 1 nc
    152 286.584 -48.3327 20.8452 1 0 0 nc
    153 212.403 -23.6057 20.8452 0 0 1 nc
    154 280.402 10.3938 20.8452 0 0 1 nc
    155 694.579 115.483 20.8452 0 0 1 nc
    156 574.035 177.301 20.8452 0 0 1 nc
     114-567.302 43.6423 20 0 0 1 nc
     115-689.204 -237.261 20 0 0 1 nc
     116924.667 409.347 20 0 0 1 nc
     117588.113 544.499 20 0 0 1 nc
     118670.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
     125201.208 38.3422 20 0 0 1 nc
     126116.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
     132415.393 -289.516 20 1 0 0 nc
     133730.084 -307.139 20 0 0 1 nc
     134526.164 32.7279 20 1 0 0 nc
     135762.812 -17.6227 20 1 0 0 nc
     136-67.9734 319.727 20 0 0 1 nc
     137329.797 314.692 20 0 0 1 nc
     138-5.03507 561.41 20 0 0 1 nc
     139422.945 521.129 20 0 0 1 nc
     140-470.779 158.605 20 1 0 0 nc
     141986.873 -115.807 20 0 0 1 nc
     142906.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
     146206.221 -205.967 20 0 0 1 nc
     147277.311 -252.33 20 0 0 1 nc
     148271.13 -175.058 20 1 0 0 nc
     149366.947 -110.15 20 1 0 0 nc
     150397.855 -196.694 20 0 0 1 nc
     151438.037 -88.514 20 0 0 1 nc
     152286.584 -48.3327 20 1 0 0 nc
     153212.403 -23.6057 20 0 0 1 nc
     154280.402 10.3938 20 0 0 1 nc
     155694.579 115.483 20 0 0 1 nc
     156574.035 177.301 20 0 0 1 nc
    157157grestore
    158158grestore
  • doc/images/strongly_connected_components.eps

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

    r1270 r1069  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464\endcode
    6565
    66 The \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
    68 graph. If a map is in both of these sections, then it can be used as a
    69 regular 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 
    83 The \c \@arcs section is very similar to the \c \@nodes section,
    84 it again starts with a header line describing the names of the maps,
    85 but the \c "label" map is not obligatory here. The following lines
    86 describe the arcs. The first two tokens of each line are
    87 the source and the target node of the arc, respectively, then come the map
     66The \c \@arcs section is very similar to the \c \@nodes section, it
     67again starts with a header line describing the names of the maps, but
     68the \c "label" map is not obligatory here. The following lines
     69describe the arcs. The first two tokens of each line are the source
     70and the target node of the arc, respectively, then come the map
    8871values. The source and target tokens must be node labels.
    8972
  • doc/mainpage.dox.in

    r1221 r1039  
    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 \cite DezsoJuttnerKovacs11Lemon.
     28tasks connected mainly with graphs and networks.
    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> \cite egres
     40Combinatorial Optimization</a> \ref 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 \cite coinor.
     45initiative \ref coinor.
    4646
    4747\section howtoread How to Read the Documentation
  • doc/min_cost_flow.dox

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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 \cite amo93networkflows.
     29and arc costs \ref 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

    r1219 r802  
    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/}}
     7  howpublished = {\url{http://lemon.cs.elte.hu/}},
     8  year =         2009
    89}
    910
     
    2021                  {O}perations {R}esearch},
    2122  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}
    4423}
    4524
     
    233212  volume =       23,
    234213  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}
    245214}
    246215
     
    257226}
    258227
    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 
    270228
    271229%%%%% Minimum cost flow algorithms %%%%%
     
    340298  address =      {Dublin, Ireland},
    341299  year =         1991,
    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 }
     300  month =        sep,
     301}
  • lemon/CMakeLists.txt

    r1264 r1113  
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.in
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
    99)
    1010
    1111CONFIGURE_FILE(
    12   ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
    1313  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    1414  @ONLY
     
    3737IF(LEMON_HAVE_CPLEX)
    3838  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    39   INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
     39  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
    4040ENDIF()
    4141
     
    4848  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    4949  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    50 ENDIF()
    51 
    52 IF(LEMON_HAVE_SOPLEX)
    53   SET(LEMON_SOURCES ${LEMON_SOURCES} soplex.cc)
    54   INCLUDE_DIRECTORIES(${SOPLEX_INCLUDE_DIRS})
    5550ENDIF()
    5651
  • lemon/adaptors.h

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/assert.h

    r1270 r1242  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/base.cc

    r1270 r554  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222#include<lemon/tolerance.h>
    2323#include<lemon/core.h>
    24 #include<lemon/time_measure.h>
    2524namespace lemon {
    2625
     
    3332#endif
    3433
    35   TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
    36 
    3734} //namespace lemon
  • lemon/bellman_ford.h

    r1270 r960  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    150150  /// This class provides an efficient implementation of the Bellman-Ford
    151151  /// algorithm. The maximum time complexity of the algorithm is
    152   /// <tt>O(nm)</tt>.
     152  /// <tt>O(ne)</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 lemon::BellmanFordDefaultOperationTraits
     203    ///\brief The \ref BellmanFordDefaultOperationTraits
    204204    /// "operation traits class" of the algorithm.
    205205    typedef typename TR::OperationTraits OperationTraits;
    206206
    207     ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
    208     ///of the algorithm.
     207    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
    209208    typedef TR Traits;
    210209
  • lemon/bfs.h

    r1270 r1127  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    153153    typedef PredMapPath<Digraph, PredMap> Path;
    154154
    155     ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    156156    typedef TR Traits;
    157157
  • lemon/bin_heap.h

    r1270 r758  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/alteration_notifier.h

    r1270 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424
    2525#include <lemon/core.h>
    26 #include <lemon/bits/lock.h>
    2726
    2827//\ingroup graphbits
     
    253252    typedef std::list<ObserverBase*> Observers;
    254253    Observers _observers;
    255     lemon::bits::Lock _lock;
     254
    256255
    257256  public:
     
    334333
    335334    void attach(ObserverBase& observer) {
    336       _lock.lock();
    337335      observer._index = _observers.insert(_observers.begin(), &observer);
    338336      observer._notifier = this;
    339       _lock.unlock();
    340337    }
    341338
    342339    void detach(ObserverBase& observer) {
    343       _lock.lock();
    344340      _observers.erase(observer._index);
    345341      observer._index = _observers.end();
    346342      observer._notifier = 0;
    347       _lock.unlock();
    348343    }
    349344
  • lemon/bits/array_map.h

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/bezier.h

    r1270 r1157  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/default_map.h

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/edge_set_extender.h

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_adaptor_extender.h

    r1270 r965  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/graph_extender.h

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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 
    1330749}
    1331750
  • lemon/bits/map_extender.h

    r1270 r867  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/path_dump.h

    r1270 r973  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/solver_bits.h

    r1270 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/bits/traits.h

    r1270 r663  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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      };
    233151
    234152  };
  • lemon/bits/windows.cc

    r1270 r1055  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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     }
    165133  }
    166134}
  • lemon/bits/windows.h

    r1270 r576  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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     };
    4131  }
    4232}
  • lemon/capacity_scaling.h

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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" \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".)
     69  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
     70  /// \ref edmondskarp72theoretical. It is an efficient dual
     71  /// solution method.
    7972  ///
    8073  /// Most of the parameters of the problem (except for the digraph)
     
    9487  /// consider to use the named template parameters instead.
    9588  ///
    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.
     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.
    10193#ifdef DOXYGEN
    10294  template <typename GR, typename V, typename C, typename TR>
     
    119111    typedef typename TR::Heap Heap;
    120112
    121     /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
    122     /// of the algorithm
     113    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
    123114    typedef TR Traits;
    124115
     
    432423    ///
    433424    /// Using this function has the same effect as using \ref supplyMap()
    434     /// with a map in which \c k is assigned to \c s, \c -k is
     425    /// with such a map in which \c k is assigned to \c s, \c -k is
    435426    /// assigned to \c t and all other nodes have zero supply value.
    436427    ///
     
    647638    ///
    648639    /// This function returns the total cost of the found flow.
    649     /// Its complexity is O(m).
     640    /// Its complexity is O(e).
    650641    ///
    651642    /// \note The return type of the function can be specified as a
     
    685676    }
    686677
    687     /// \brief Copy the flow values (the primal solution) into the
    688     /// given map.
     678    /// \brief Return the flow map (the primal solution).
    689679    ///
    690680    /// This function copies the flow value on each arc into the given
     
    710700    }
    711701
    712     /// \brief Copy the potential values (the dual solution) into the
    713     /// given map.
     702    /// \brief Return the potential map (the dual solution).
    714703    ///
    715704    /// This function copies the potential (dual value) of each node
     
    740729      }
    741730      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 
    747731
    748732      // Initialize vectors
     
    838822
    839823      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;
    849824    }
    850825
  • lemon/cbc.cc

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/cbc.h

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
     19// -*- C++ -*-
    1920#ifndef LEMON_CBC_H
    2021#define LEMON_CBC_H
  • lemon/circulation.h

    r1270 r1159  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    196196  public:
    197197
    198     /// \brief The \ref lemon::CirculationDefaultTraits "traits class"
    199     /// of the algorithm.
     198    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
    200199    typedef TR Traits;
    201200    ///The type of the digraph the algorithm runs on.
  • lemon/clp.cc

    r1270 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/clp.h

    r1270 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concept_check.h

    r1270 r1257  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concepts/digraph.h

    r1271 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    313313        /// Sets the iterator to the first arc of the given digraph.
    314314        ///
    315         explicit ArcIt(const Digraph& g) {
    316           ::lemon::ignore_unused_variable_warning(g);
    317         }
     315        explicit ArcIt(const Digraph& g) { ::lemon::ignore_unused_variable_warning(g); }
    318316        /// Sets the iterator to the given arc.
    319317
     
    412410      /// \brief The base node of the iterator.
    413411      ///
    414       /// Returns the base node of the given incoming arc iterator
     412      /// Returns the base node of the given incomming arc iterator
    415413      /// (i.e. the target node of the corresponding arc).
    416414      Node baseNode(InArcIt) const { return INVALID; }
     
    418416      /// \brief The running node of the iterator.
    419417      ///
    420       /// Returns the running node of the given incoming arc iterator
     418      /// Returns the running node of the given incomming arc iterator
    421419      /// (i.e. the source node of the corresponding arc).
    422420      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r1271 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7373    class Graph {
    7474    private:
    75       /// Graphs are \e not copy constructible. Use GraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use GraphCopy instead.
     78      /// Use DigraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080
     
    397397        /// Sets the iterator to the first arc of the given graph.
    398398        ///
    399         explicit ArcIt(const Graph &g) {
    400           ::lemon::ignore_unused_variable_warning(g);
    401         }
     399        explicit ArcIt(const Graph &g) { ::lemon::ignore_unused_variable_warning(g); }
    402400        /// Sets the iterator to the given arc.
    403401
     
    760758      /// \brief The base node of the iterator.
    761759      ///
    762       /// Returns the base node of the given incoming arc iterator
     760      /// Returns the base node of the given incomming arc iterator
    763761      /// (i.e. the target node of the corresponding arc).
    764762      Node baseNode(InArcIt) const { return INVALID; }
     
    766764      /// \brief The running node of the iterator.
    767765      ///
    768       /// Returns the running node of the given incoming arc iterator
     766      /// Returns the running node of the given incomming arc iterator
    769767      /// (i.e. the source node of the corresponding arc).
    770768      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1270 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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             ::lemon::ignore_unused_variable_warning(b);
    460           }
    461         }
    462 
    463         const _BpGraph& bpgraph;
    464       };
    465 
    466     };
    467 
    468302    /// \brief Skeleton class for \e idable directed graphs.
    469303    ///
     
    598432    };
    599433
    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           ::lemon::ignore_unused_variable_warning(rid);
    657           ::lemon::ignore_unused_variable_warning(bid);
    658         }
    659 
    660         const _BpGraph& bpgraph;
    661       };
    662     };
    663 
    664434    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    665435    ///
     
    876646      void next(Arc&) const {}
    877647
    878       /// \brief Return the first arc incoming to the given node.
    879       ///
    880       /// This function gives back the first arc incoming to the
     648      /// \brief Return the first arc incomming to the given node.
     649      ///
     650      /// This function gives back the first arc incomming to the
    881651      /// given node.
    882652      void firstIn(Arc&, const Node&) const {}
    883653
    884       /// \brief Return the next arc incoming to the given node.
    885       ///
    886       /// This function gives back the next arc incoming to the
     654      /// \brief Return the next arc incomming to the given node.
     655      ///
     656      /// This function gives back the next arc incomming to the
    887657      /// given node.
    888658      void nextIn(Arc&) const {}
     
    1135905    };
    1136906
    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 
    1228907    /// \brief Skeleton class for alterable directed graphs.
    1229908    ///
     
    1251930      ArcNotifier;
    1252931
    1253       mutable NodeNotifier node_notifier;
    1254       mutable ArcNotifier arc_notifier;
    1255 
    1256932      /// \brief Return the node alteration notifier.
    1257933      ///
    1258934      /// This function gives back the node alteration notifier.
    1259935      NodeNotifier& notifier(Node) const {
    1260         return node_notifier;
     936         return NodeNotifier();
    1261937      }
    1262938
     
    1265941      /// This function gives back the arc alteration notifier.
    1266942      ArcNotifier& notifier(Arc) const {
    1267         return arc_notifier;
     943        return ArcNotifier();
    1268944      }
    1269945
     
    1301977
    1302978      typedef BAS Base;
    1303       typedef AlterableDigraphComponent<Base> Parent;
    1304979      typedef typename Base::Edge Edge;
    1305980
     
    1309984      EdgeNotifier;
    1310985
    1311       mutable EdgeNotifier edge_notifier;
    1312 
    1313       using Parent::notifier;
    1314 
    1315986      /// \brief Return the edge alteration notifier.
    1316987      ///
    1317988      /// This function gives back the edge alteration notifier.
    1318989      EdgeNotifier& notifier(Edge) const {
    1319         return edge_notifier;
     990        return EdgeNotifier();
    1320991      }
    1321992
     
    13311002        const _Graph& graph;
    13321003        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           ::lemon::ignore_unused_variable_warning(rnn);
    1391           ::lemon::ignore_unused_variable_warning(bnn);
    1392         }
    1393 
    1394         const _BpGraph& bpgraph;
    13951004      };
    13961005    };
     
    16991308    };
    17001309
    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 
    18451310    /// \brief Skeleton class for extendable directed graphs.
    18461311    ///
     
    19331398    };
    19341399
    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 
    19941400    /// \brief Skeleton class for erasable directed graphs.
    19951401    ///
     
    20721478    };
    20731479
    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 
    20831480    /// \brief Skeleton class for clearable directed graphs.
    20841481    ///
     
    21171514    /// This concept requires \ref AlterableGraphComponent.
    21181515    template <typename BAS = BaseGraphComponent>
    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> {};
     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    };
    21291537
    21301538  }
  • lemon/concepts/heap.h

    r1270 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concepts/maps.h

    r1270 r1257  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/concepts/path.h

    r1270 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/config.h.in

    r1264 r725  
    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_SOPLEX 1
    8 #cmakedefine LEMON_HAVE_CLP 1
    9 #cmakedefine LEMON_HAVE_CBC 1
    10 #cmakedefine LEMON_DEFAULT_LP @LEMON_DEFAULT_LP@
    11 #cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
    12 #cmakedefine LEMON_USE_PTHREAD 1
    13 #cmakedefine LEMON_USE_WIN32_THREADS 1
     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
  • lemon/connectivity.h

    r1270 r1268  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/core.h

    r1270 r1259  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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 
    205162  /// \brief Function to count the items in a graph.
    206163  ///
     
    254211  }
    255212
    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 
    324213  // Arc counting:
    325214
     
    563452      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    564453      static void copy(const From& from, Graph &to,
    565                        NodeRefMap& nodeRefMap,
    566                        EdgeRefMap& edgeRefMap) {
     454                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    567455        to.build(from, nodeRefMap, edgeRefMap);
    568456      }
    569457    };
    570458
    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 
    608459  }
    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
    628460
    629461  /// \brief Class to copy a digraph.
     
    1150982  graphCopy(const From& from, To& to) {
    1151983    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);
    1600984  }
    1601985
  • lemon/cost_scaling.h

    <
    r1271 r1041  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2013
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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" \cite amo93networkflows,
    95   /// \cite goldberg90approximation,
    96   /// \cite goldberg97efficient, \cite bunnagel98efficient.
     94  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
     95  /// \ref goldberg97efficient, \ref bunnagel98efficient.
    9796  /// It is a highly efficient primal-dual solution method, which
    9897  /// can be viewed as the generalization of the \ref Preflow
    9998  /// "preflow push-relabel" algorithm for the maximum flow problem.
    100   /// It is a polynomial algorithm, its running time complexity is
    101   /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    102   ///
    103   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    104   /// implementations available in LEMON for solving this problem.
    105   /// (For more information, see \ref min_cost_flow_algs "the module page".)
    10699  ///
    107100  /// Most of the parameters of the problem (except for the digraph)
     
    121114  /// consider to use the named template parameters instead.
    122115  ///
    123   /// \warning Both \c V and \c C must be signed number types.
    124   /// \warning All input data (capacities, supply values, and costs) must
     116  /// \warning Both number types must be signed and all input data must
    125117  /// be integer.
    126   /// \warning This algorithm does not support negative costs for
    127   /// arcs having infinite upper bound.
     118  /// \warning This algorithm does not support negative costs for such
     119  /// arcs that have infinite upper bound.
    128120  ///
    129121  /// \note %CostScaling provides three different internal methods,
     
    154146    typedef typename TR::LargeCost LargeCost;
    155147
    156     /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
    157     /// of the algorithm
     148    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
    158149    typedef TR Traits;
    159150
     
    188179    /// relabel operation.
    189180    /// By default, the so called \ref PARTIAL_AUGMENT
    190     /// "Partial Augment-Relabel" method is used, which turned out to be
     181    /// "Partial Augment-Relabel" method is used, which proved to be
    191182    /// the most efficient and the most robust on various test inputs.
    192183    /// However, the other methods can be selected using the \ref run()
     
    215206    typedef std::vector<LargeCost> LargeCostVector;
    216207    typedef std::vector<char> BoolVector;
    217     // Note: vector<char> is used instead of vector<bool>
    218     // for efficiency reasons
     208    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    219209
    220210  private:
     
    244234    };
    245235
     236    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
    246237    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
    247238
     
    294285    int _max_rank;
    295286
     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
    296295  public:
    297296
     
    340339    CostScaling(const GR& graph) :
    341340      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
     341      _cost_map(_cost_vec), _pi_map(_pi),
    342342      INF(std::numeric_limits<Value>::has_infinity ?
    343343          std::numeric_limits<Value>::infinity() :
     
    448448    ///
    449449    /// Using this function has the same effect as using \ref supplyMap()
    450     /// with a map in which \c k is assigned to \c s, \c -k is
     450    /// with such a map in which \c k is assigned to \c s, \c -k is
    451451    /// assigned to \c t and all other nodes have zero supply value.
    452452    ///
     
    494494    /// \param method The internal method that will be used in the
    495495    /// algorithm. For more information, see \ref Method.
    496     /// \param factor The cost scaling factor. It must be at least two.
     496    /// \param factor The cost scaling factor. It must be larger than one.
    497497    ///
    498498    /// \return \c INFEASIBLE if no feasible flow exists,
     
    508508    /// \see ProblemType, Method
    509509    /// \see resetParams(), reset()
    510     ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 16) {
    511       LEMON_ASSERT(factor >= 2, "The scaling factor must be at least 2");
     510    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
    512511      _alpha = factor;
    513512      ProblemType pt = init();
     
    573572    }
    574573
    575     /// \brief Reset the internal data structures and all the parameters
    576     /// that have been given before.
    577     ///
    578     /// This function resets the internal data structures and all the
    579     /// paramaters that have been given before using functions \ref lowerMap(),
    580     /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
    581     ///
    582     /// It is useful for multiple \ref run() calls. By default, all the given
    583     /// parameters are kept for the next \ref run() call, unless
    584     /// \ref resetParams() or \ref reset() is used.
    585     /// If the underlying digraph was also modified after the construction
    586     /// of the class or the last \ref reset() call, then the \ref reset()
    587     /// function must be used, otherwise \ref resetParams() is sufficient.
    588     ///
    589     /// See \ref resetParams() for examples.
    590     ///
     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.
    591585    /// \return <tt>(*this)</tt>
    592     ///
    593     /// \see resetParams(), run()
    594586    CostScaling& reset() {
    595587      // Resize vectors
     
    616608      _excess.resize(_res_node_num);
    617609      _next_out.resize(_res_node_num);
     610
     611      _arc_vec.reserve(_res_arc_num);
     612      _cost_vec.reserve(_res_arc_num);
    618613
    619614      // Copy the graph
     
    673668    ///
    674669    /// This function returns the total cost of the found flow.
    675     /// Its complexity is O(m).
     670    /// Its complexity is O(e).
    676671    ///
    677672    /// \note The return type of the function can be specified as a
     
    711706    }
    712707
    713     /// \brief Copy the flow values (the primal solution) into the
    714     /// given map.
     708    /// \brief Return the flow map (the primal solution).
    715709    ///
    716710    /// This function copies the flow value on each arc into the given
     
    736730    }
    737731
    738     /// \brief Copy the potential values (the dual solution) into the
    739     /// given map.
     732    /// \brief Return the potential map (the dual solution).
    740733    ///
    741734    /// This function copies the potential (dual value) of each node
     
    766759      }
    767760      if (_sum_supply > 0) return INFEASIBLE;
    768 
    769       // Check lower and upper bounds
    770       LEMON_DEBUG(checkBoundMaps(),
    771           "Upper bounds must be greater or equal to the lower bounds");
    772761
    773762
     
    898887      }
    899888
     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
    900897      // Initialize data structures for buckets
    901898      _max_rank = _alpha * _res_node_num;
     
    905902      _rank.resize(_res_node_num + 1);
    906903
    907       return OPTIMAL;
    908     }
    909 
    910     // Check if the upper bound is greater or equal to the lower bound
    911     // on each arc.
    912     bool checkBoundMaps() {
    913       for (int j = 0; j != _res_arc_num; ++j) {
    914         if (_upper[j] < _lower[j]) return false;
    915       }
    916       return true;
    917     }
    918 
    919     // Execute the algorithm and transform the results
    920     void start(Method method) {
    921       const int MAX_PARTIAL_PATH_LENGTH = 4;
    922 
     904      // Execute the algorithm
    923905      switch (method) {
    924906        case PUSH:
     
    929911          break;
    930912        case PARTIAL_AUGMENT:
    931           startAugment(MAX_PARTIAL_PATH_LENGTH);
     913          startAugment(MAX_PATH_LENGTH);
    932914          break;
    933915      }
    934916
    935       // Compute node potentials (dual solution)
    936       for (int i = 0; i != _res_node_num; ++i) {
    937         _pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha));
    938       }
    939       bool optimal = true;
    940       for (int i = 0; optimal && i != _res_node_num; ++i) {
    941         LargeCost pi_i = _pi[i];
    942         int last_out = _first_out[i+1];
    943         for (int j = _first_out[i]; j != last_out; ++j) {
    944           if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
    945             optimal = false;
    946             break;
    947           }
    948         }
    949       }
    950 
    951       if (!optimal) {
    952         // Compute node potentials for the original costs with BellmanFord
    953         // (if it is necessary)
    954         typedef std::pair<int, int> IntPair;
    955         StaticDigraph sgr;
    956         std::vector<IntPair> arc_vec;
    957         std::vector<LargeCost> cost_vec;
    958         LargeCostArcMap cost_map(cost_vec);
    959 
    960         arc_vec.clear();
    961         cost_vec.clear();
    962         for (int j = 0; j != _res_arc_num; ++j) {
    963           if (_res_cap[j] > 0) {
    964             int u = _source[j], v = _target[j];
    965             arc_vec.push_back(IntPair(u, v));
    966             cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]);
    967           }
    968         }
    969         sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end());
    970 
    971         typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create
    972           bf(sgr, cost_map);
    973         bf.init(0);
    974         bf.start();
    975 
    976         for (int i = 0; i != _res_node_num; ++i) {
    977           _pi[i] += bf.dist(sgr.node(i));
    978         }
    979       }
    980 
    981       // Shift potentials to meet the requirements of the GEQ type
    982       // optimality conditions
    983       LargeCost max_pot = _pi[_root];
    984       for (int i = 0; i != _res_node_num; ++i) {
    985         if (_pi[i] > max_pot) max_pot = _pi[i];
    986       }
    987       if (max_pot != 0) {
    988         for (int i = 0; i != _res_node_num; ++i) {
    989           _pi[i] -= max_pot;
    990         }
    991       }
     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();
    992933
    993934      // Handle non-zero lower bounds
     
    1007948        LargeCost pi_u = _pi[u];
    1008949        for (int a = _first_out[u]; a != last_out; ++a) {
    1009           Value delta = _res_cap[a];
    1010           if (delta > 0) {
    1011             int v = _target[a];
    1012             if (_cost[a] + pi_u - _pi[v] < 0) {
    1013               _excess[u] -= delta;
    1014               _excess[v] += delta;
    1015               _res_cap[a] = 0;
    1016               _res_cap[_reverse[a]] += delta;
    1017             }
     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;
    1018957          }
    1019958        }
     
    1031970    }
    1032971
    1033     // Price (potential) refinement heuristic
    1034     bool priceRefinement() {
    1035 
    1036       // Stack for stroing the topological order
    1037       IntVector stack(_res_node_num);
    1038       int stack_top;
    1039 
    1040       // Perform phases
    1041       while (topologicalSort(stack, stack_top)) {
    1042 
    1043         // Compute node ranks in the acyclic admissible network and
    1044         // store the nodes in buckets
    1045         for (int i = 0; i != _res_node_num; ++i) {
    1046           _rank[i] = 0;
    1047         }
    1048         const int bucket_end = _root + 1;
    1049         for (int r = 0; r != _max_rank; ++r) {
    1050           _buckets[r] = bucket_end;
    1051         }
    1052         int top_rank = 0;
    1053         for ( ; stack_top >= 0; --stack_top) {
    1054           int u = stack[stack_top], v;
    1055           int rank_u = _rank[u];
    1056 
    1057           LargeCost rc, pi_u = _pi[u];
    1058           int last_out = _first_out[u+1];
    1059           for (int a = _first_out[u]; a != last_out; ++a) {
    1060             if (_res_cap[a] > 0) {
    1061               v = _target[a];
    1062               rc = _cost[a] + pi_u - _pi[v];
    1063               if (rc < 0) {
    1064                 LargeCost nrc = static_cast<LargeCost>((-rc - 0.5) / _epsilon);
    1065                 if (nrc < LargeCost(_max_rank)) {
    1066                   int new_rank_v = rank_u + static_cast<int>(nrc);
    1067                   if (new_rank_v > _rank[v]) {
    1068                     _rank[v] = new_rank_v;
    1069                   }