COIN-OR::LEMON - Graph Library

Ignore:
Files:
25 added
20 deleted
145 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

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

    r1159 r1398  
    1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
     2
     3IF(POLICY CMP0048)
     4  CMAKE_POLICY(SET CMP0048 OLD)
     5ENDIF(POLICY CMP0048)
     6
     7IF(POLICY CMP0026)
     8  #This is for copying the dll's needed by glpk (in lp_test and mip_test)
     9  CMAKE_POLICY(SET CMP0026 OLD)
     10ENDIF(POLICY CMP0026)
    211
    312SET(PROJECT_NAME "LEMON")
     
    1322ELSE()
    1423  EXECUTE_PROCESS(
    15     COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     24    COMMAND
     25    hg log -r. --template "{latesttag}"
    1626    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    17     OUTPUT_VARIABLE HG_REVISION_PATH
     27    OUTPUT_VARIABLE HG_REVISION_TAG
    1828    ERROR_QUIET
    1929    OUTPUT_STRIP_TRAILING_WHITESPACE
    2030  )
    2131  EXECUTE_PROCESS(
    22     COMMAND hg id -i
     32    COMMAND
     33    hg log -r. --template "{latesttagdistance}"
    2334    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    24     OUTPUT_VARIABLE HG_REVISION
     35    OUTPUT_VARIABLE HG_REVISION_DIST
    2536    ERROR_QUIET
    2637    OUTPUT_STRIP_TRAILING_WHITESPACE
    2738  )
    28   IF(HG_REVISION STREQUAL "")
     39  EXECUTE_PROCESS(
     40    COMMAND
     41    hg log -r. --template "{node|short}"
     42    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     43    OUTPUT_VARIABLE HG_REVISION_ID
     44    ERROR_QUIET
     45    OUTPUT_STRIP_TRAILING_WHITESPACE
     46  )
     47
     48  IF(HG_REVISION_TAG STREQUAL "")
    2949    SET(HG_REVISION_ID "hg-tip")
    3050  ELSE()
    31     IF(HG_REVISION_PATH STREQUAL "")
    32       SET(HG_REVISION_ID ${HG_REVISION})
     51    IF(HG_REVISION_TAG STREQUAL "null")
     52      SET(HG_REVISION_TAG "trunk")
     53    ELSEIF(HG_REVISION_TAG MATCHES "^r")
     54      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
     55    ENDIF()
     56    IF(HG_REVISION_DIST STREQUAL "0")
     57      SET(HG_REVISION ${HG_REVISION_TAG})
    3358    ELSE()
    34       SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     59      SET(HG_REVISION
     60        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
    3561    ENDIF()
    3662  ENDIF()
    37   SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
     63
     64  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
    3865ENDIF()
    3966
     
    4471FIND_PACKAGE(Doxygen)
    4572FIND_PACKAGE(Ghostscript)
    46 FIND_PACKAGE(GLPK 4.33)
    47 FIND_PACKAGE(CPLEX)
    48 FIND_PACKAGE(COIN)
     73
     74IF(WIN32)
     75  SET(LEMON_WIN32 TRUE)
     76ENDIF(WIN32)
     77
     78SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     79SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     80SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     81SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
     82
     83IF(LEMON_ENABLE_GLPK)
     84  FIND_PACKAGE(GLPK 4.33)
     85  IF(GLPK_FOUND)
     86    SET(LEMON_HAVE_LP TRUE)
     87    SET(LEMON_HAVE_MIP TRUE)
     88    SET(LEMON_HAVE_GLPK TRUE)
     89  ENDIF(GLPK_FOUND)
     90ENDIF(LEMON_ENABLE_GLPK)
     91IF(LEMON_ENABLE_ILOG)
     92  FIND_PACKAGE(ILOG)
     93  IF(ILOG_FOUND)
     94    SET(LEMON_HAVE_LP TRUE)
     95    SET(LEMON_HAVE_MIP TRUE)
     96    SET(LEMON_HAVE_CPLEX TRUE)
     97  ENDIF(ILOG_FOUND)
     98ENDIF(LEMON_ENABLE_ILOG)
     99IF(LEMON_ENABLE_COIN)
     100  FIND_PACKAGE(COIN)
     101  IF(COIN_FOUND)
     102    SET(LEMON_HAVE_LP TRUE)
     103    SET(LEMON_HAVE_MIP TRUE)
     104    SET(LEMON_HAVE_CLP TRUE)
     105    SET(LEMON_HAVE_CBC TRUE)
     106  ENDIF(COIN_FOUND)
     107ENDIF(LEMON_ENABLE_COIN)
     108IF(LEMON_ENABLE_SOPLEX)
     109  FIND_PACKAGE(SOPLEX)
     110  IF(SOPLEX_FOUND)
     111    SET(LEMON_HAVE_LP TRUE)
     112    SET(LEMON_HAVE_SOPLEX TRUE)
     113  ENDIF(SOPLEX_FOUND)
     114ENDIF(LEMON_ENABLE_SOPLEX)
     115
     116IF(ILOG_FOUND)
     117  SET(DEFAULT_LP "CPLEX")
     118  SET(DEFAULT_MIP "CPLEX")
     119ELSEIF(COIN_FOUND)
     120  SET(DEFAULT_LP "CLP")
     121  SET(DEFAULT_MIP "CBC")
     122ELSEIF(GLPK_FOUND)
     123  SET(DEFAULT_LP "GLPK")
     124  SET(DEFAULT_MIP "GLPK")
     125ELSEIF(SOPLEX_FOUND)
     126  SET(DEFAULT_LP "SOPLEX")
     127ENDIF()
     128
     129IF(NOT LEMON_DEFAULT_LP OR
     130    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     131    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     132    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
     133    (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
     134  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     135    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     136ELSE()
     137  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     138    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
     139ENDIF()
     140IF(NOT LEMON_DEFAULT_MIP OR
     141    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     142    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     143    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     144  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     145    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     146ELSE()
     147  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     148    "Default MIP solver backend (GLPK, CPLEX or CBC)")
     149ENDIF()
     150
    49151
    50152IF(DEFINED ENV{LEMON_CXX_WARNING})
     
    57159  ELSEIF(MSVC)
    58160    # This part is unnecessary 'casue the same is set by the lemon/core.h.
    59     # Still keep it as an example.
    60     SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     161    # Still kept as an example.
     162
     163    # SET(CXX_WARNING "/wd4250 /wd4267 /wd4355 /wd4503 /wd4800 /wd4996")
     164
    61165    # Suppressed warnings:
    62166    # C4250: 'class1' : inherits 'class2::member' via dominance
     167    # C4267: conversion from 'size_t' to 'type', possible loss of data
    63168    # C4355: 'this' : used in base member initializer list
    64169    # C4503: 'function' : decorated name length exceeded, name was truncated
     
    74179SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    75180
    76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     181IF(MSVC)
     182  SET(CMAKE_CXX_FLAGS "/bigobj ${CMAKE_CXX_FLAGS}")
     183  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    77184    "Flags used by the C++ compiler during maintainer builds."
    78     FORCE )
    79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     185    )
     186  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
    80187    "Flags used by the C compiler during maintainer builds."
    81     FORCE )
    82 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    83     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     188    )
     189  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     190    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
    84191    "Flags used for linking binaries during maintainer builds."
    85     FORCE )
    86 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    87     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     192    )
     193  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     194    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
    88195    "Flags used by the shared libraries linker during maintainer builds."
    89     FORCE )
     196    )
     197ELSE()
     198  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     199    "Flags used by the C++ compiler during maintainer builds."
     200    )
     201  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     202    "Flags used by the C compiler during maintainer builds."
     203    )
     204  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     205    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     206    "Flags used for linking binaries during maintainer builds."
     207    )
     208  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     209    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     210    "Flags used by the shared libraries linker during maintainer builds."
     211    )
     212ENDIF()
     213
    90214MARK_AS_ADVANCED(
    91215    CMAKE_CXX_FLAGS_MAINTAINER
     
    115239SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116240
    117 INCLUDE(FindPythonInterp)
     241INCLUDE(FindThreads)
     242
     243IF(NOT LEMON_THREADING)
     244  IF(CMAKE_USE_PTHREADS_INIT)
     245    SET(LEMON_THREADING "Pthread")
     246  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     247    SET(LEMON_THREADING "Win32")
     248  ELSE()
     249    SET(LEMON_THREADING "None")
     250  ENDIF()
     251ENDIF()
     252
     253SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     254  "Choose the threading library, options are: Pthread Win32 None."
     255  FORCE )
     256
     257IF(LEMON_THREADING STREQUAL "Pthread")
     258  SET(LEMON_USE_PTHREAD TRUE)
     259ELSEIF(LEMON_THREADING STREQUAL "Win32")
     260  SET(LEMON_USE_WIN32_THREADS TRUE)
     261ENDIF()
    118262
    119263ENABLE_TESTING()
     
    127271ADD_SUBDIRECTORY(lemon)
    128272IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     273  ADD_SUBDIRECTORY(contrib)
    129274  ADD_SUBDIRECTORY(demo)
    130275  ADD_SUBDIRECTORY(tools)
     
    150295ENDIF()
    151296
     297CONFIGURE_FILE(
     298  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     299  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     300  @ONLY
     301)
     302
     303SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     304STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     305SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     306ADD_CUSTOM_TARGET(dist
     307  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     308  COMMAND hg archive ${ARCHIVE_NAME}
     309  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     310  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     311  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     312  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     313  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     314  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     315  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     316  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     317  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     318  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     319  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     320  DEPENDS html
     321  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     322
     323# CPACK config (Basically for NSIS)
    152324IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    153325  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
  • INSTALL

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

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

    r962 r1281  
     12013-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
    1992010-03-19 Version 1.2 released
    2100
  • cmake/FindCOIN.cmake

    r1120 r1398  
    6666)
    6767
     68FIND_LIBRARY(COIN_PTHREADS_LIBRARY
     69  NAMES pthreads libpthreads
     70  HINTS ${COIN_ROOT_DIR}/lib/coin
     71  HINTS ${COIN_ROOT_DIR}/lib
     72)
     73
    6874INCLUDE(FindPackageHandleStandardArgs)
    6975FIND_PACKAGE_HANDLE_STANDARD_ARGS(COIN DEFAULT_MSG
     
    8389IF(COIN_FOUND)
    8490  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
    85   SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_ZLIB_LIBRARY};${COIN_BZ2_LIBRARY}")
     91  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
    8692  IF(COIN_ZLIB_LIBRARY)
    8793    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_ZLIB_LIBRARY}")
     
    9096    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_BZ2_LIBRARY}")
    9197  ENDIF(COIN_BZ2_LIBRARY)
    92   SET(COIN_CBC_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_ZLIB_LIBRARY};${COIN_BZ2_LIBRARY};${COIN_CLP_LIBRARIES}")
     98   IF(COIN_PTHREADS_LIBRARY)
     99    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_PTHREADS_LIBRARY}")
     100  ENDIF(COIN_PTHREADS_LIBRARY)
     101  SET(COIN_CBC_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_CLP_LIBRARIES}")
    93102  SET(COIN_LIBRARIES ${COIN_CBC_LIBRARIES})
    94103ENDIF(COIN_FOUND)
     
    109118  COIN_BZ2_LIBRARY
    110119)
    111 
    112 IF(COIN_FOUND)
    113   SET(LEMON_HAVE_LP TRUE)
    114   SET(LEMON_HAVE_MIP TRUE)
    115   SET(LEMON_HAVE_CLP TRUE)
    116   SET(LEMON_HAVE_CBC TRUE)
    117 ENDIF(COIN_FOUND)
  • cmake/FindGLPK.cmake

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

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

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

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

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

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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_underscores
     104_start_with_underscore
    105105\endcode
    106106
  • doc/dirs.dox

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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
     39You can place your own C++ code using LEMON into this directory, which
     40will compile to an executable along with LEMON when you build the
     41library. This is probably the easiest way of compiling short to medium
     42codes, for this does require neither a LEMON installed system-wide nor
     43adding several paths to the compiler.
     44
     45Please have a look at <tt>contrib/CMakeLists.txt</tt> for
     46instruction on how to add your own files into the build process.  */
    3447
    3548/**
  • doc/groups.dox

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

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

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

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

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

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

    r1069 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section, it
    67 again starts with a header line describing the names of the maps, but
    68 the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are the source
    70 and the target node of the arc, respectively, then come the map
     66The \e LGF files can also contain bipartite graphs, in this case a
     67\c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
     68graph. If a map is in both of these sections, then it can be used as a
     69regular node map.
     70
     71\code
     72 @red_nodes
     73 label  only_red_map   name
     74 1      "cherry"       "John"
     75 2      "Santa Claus"  "Jack"
     76 3      "blood"        "Jason"
     77 @blue_nodes
     78 label  name
     79 4      "Elisabeth"
     80 5      "Eve"
     81\endcode
     82
     83The \c \@arcs section is very similar to the \c \@nodes section,
     84it again starts with a header line describing the names of the maps,
     85but the \c "label" map is not obligatory here. The following lines
     86describe the arcs. The first two tokens of each line are
     87the source and the target node of the arc, respectively, then come the map
    7188values. The source and target tokens must be node labels.
    7289
  • doc/mainpage.dox.in

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

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    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 \ref amo93networkflows.
     29and arc costs \cite amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
     
    102102\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    103103
    104 However if the sum of the supply values is zero, then these two problems
     104However, if the sum of the supply values is zero, then these two problems
    105105are equivalent.
    106106The \ref min_cost_flow_algs "algorithms" in LEMON support the general
  • doc/references.bib

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

    r1113 r1315  
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.in
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
    99)
    1010
    1111CONFIGURE_FILE(
    12   ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
    1313  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    1414  @ONLY
     
    3737IF(LEMON_HAVE_CPLEX)
    3838  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    39   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     39  INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
    4040ENDIF()
    4141
     
    5050ENDIF()
    5151
     52IF(LEMON_HAVE_SOPLEX)
     53  SET(LEMON_SOURCES ${LEMON_SOURCES} soplex.cc)
     54  INCLUDE_DIRECTORIES(${SOPLEX_INCLUDE_DIRS})
     55ENDIF()
     56
    5257ADD_LIBRARY(lemon ${LEMON_SOURCES})
     58
     59TARGET_LINK_LIBRARIES(lemon
     60  ${GLPK_LIBRARIES} ${COIN_LIBRARIES} ${ILOG_LIBRARIES} ${SOPLEX_LIBRARIES}
     61  )
     62
    5363IF(UNIX)
    54   SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     64  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon VERSION ${LEMON_VERSION} SOVERSION ${LEMON_VERSION})
    5565ENDIF()
    5666
  • lemon/adaptors.h

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

    r956 r1397  
    222222  {
    223223    Opts::iterator o = _opts.find(opt);
    224     Opts::iterator s = _opts.find(syn);
    225224    LEMON_ASSERT(o!=_opts.end(), "Unknown option: '"+opt+"'");
    226     LEMON_ASSERT(s==_opts.end(), "Option already used: '"+syn+"'");
     225    LEMON_ASSERT(_opts.find(syn)==_opts.end(),
     226                 "Option already used: '"+syn+"'");
    227227    ParData p;
    228228    p.help=opt;
  • lemon/arg_parser.h

    r959 r1327  
    2727#include <sstream>
    2828#include <algorithm>
     29#include <lemon/core.h>
    2930#include <lemon/assert.h>
    3031
  • lemon/assert.h

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    200200                             ::lemon::_assert_bits::cstringify(msg),    \
    201201                             #exp), 0)))
    202 #    if LEMON_ENABLE_DEBUG
     202#    if defined LEMON_ENABLE_DEBUG
    203203#      define LEMON_DEBUG(exp, msg)                                     \
    204204         (static_cast<void> (!!(exp) ? 0 : (                            \
  • lemon/base.cc

    r554 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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>
    2425namespace lemon {
    2526
     
    3233#endif
    3334
     35  TimeStamp::Format TimeStamp::_format = TimeStamp::NORMAL;
     36
    3437} //namespace lemon
  • lemon/bellman_ford.h

    r960 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    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(ne)</tt>.
     152  /// <tt>O(nm)</tt>.
    153153  ///
    154154  /// The Bellman-Ford algorithm solves the single-source shortest path
     
    201201    /// The type of the paths.
    202202    typedef PredMapPath<Digraph, PredMap> Path;
    203     ///\brief The \ref BellmanFordDefaultOperationTraits
     203    ///\brief The \ref lemon::BellmanFordDefaultOperationTraits
    204204    /// "operation traits class" of the algorithm.
    205205    typedef typename TR::OperationTraits OperationTraits;
    206206
    207     ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
     207    ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
     208    ///of the algorithm.
    208209    typedef TR Traits;
    209210
  • lemon/bfs.h

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

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

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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>
    2627
    2728//\ingroup graphbits
     
    252253    typedef std::list<ObserverBase*> Observers;
    253254    Observers _observers;
    254 
     255    lemon::bits::Lock _lock;
    255256
    256257  public:
     
    333334
    334335    void attach(ObserverBase& observer) {
     336      _lock.lock();
    335337      observer._index = _observers.insert(_observers.begin(), &observer);
    336338      observer._notifier = this;
     339      _lock.unlock();
    337340    }
    338341
    339342    void detach(ObserverBase& observer) {
     343      _lock.lock();
    340344      _observers.erase(observer._index);
    341345      observer._index = _observers.end();
    342346      observer._notifier = 0;
     347      _lock.unlock();
    343348    }
    344349
  • lemon/bits/array_map.h

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

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

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

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

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

    r1159 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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
    7491330}
    7501331
  • lemon/bits/map_extender.h

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

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

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

    r663 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    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     };
    151233
    152234  };
  • lemon/bits/windows.cc

    r1055 r1341  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222#include<lemon/bits/windows.h>
    2323
    24 #ifdef WIN32
     24#if defined(LEMON_WIN32) && defined(__GNUC__)
     25#pragma GCC diagnostic ignored "-Wold-style-cast"
     26#endif
     27
     28#ifdef LEMON_WIN32
    2529#ifndef WIN32_LEAN_AND_MEAN
    2630#define WIN32_LEAN_AND_MEAN
     
    4145#include <unistd.h>
    4246#include <ctime>
    43 #ifndef WIN32
     47#ifndef LEMON_WIN32
    4448#include <sys/times.h>
    4549#endif
     
    5660                         double &cutime, double &cstime)
    5761    {
    58 #ifdef WIN32
     62#ifdef LEMON_WIN32
    5963      static const double ch = 4294967296.0e-7;
    6064      static const double cl = 1.0e-7;
     
    9599    {
    96100      std::ostringstream os;
    97 #ifdef WIN32
     101#ifdef LEMON_WIN32
    98102      SYSTEMTIME time;
    99103      GetSystemTime(&time);
    100104      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     105      if (GetDateFormat(MY_LOCALE, 0, &time,
    102106                        ("ddd MMM dd"), buf1, 11) &&
    103107          GetTimeFormat(MY_LOCALE, 0, &time,
     
    121125    int getWinRndSeed()
    122126    {
    123 #ifdef WIN32
     127#ifdef LEMON_WIN32
    124128      FILETIME time;
    125129      GetSystemTimeAsFileTime(&time);
     
    131135#endif
    132136    }
     137
     138    WinLock::WinLock() {
     139#ifdef LEMON_WIN32
     140      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
     141      InitializeCriticalSection(lock);
     142      _repr = lock;
     143#else
     144      _repr = 0; //Just to avoid 'unused variable' warning with clang
     145#endif
     146    }
     147
     148    WinLock::~WinLock() {
     149#ifdef LEMON_WIN32
     150      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     151      DeleteCriticalSection(lock);
     152      delete lock;
     153#endif
     154    }
     155
     156    void WinLock::lock() {
     157#ifdef LEMON_WIN32
     158      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     159      EnterCriticalSection(lock);
     160#endif
     161    }
     162
     163    void WinLock::unlock() {
     164#ifdef LEMON_WIN32
     165      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     166      LeaveCriticalSection(lock);
     167#endif
     168    }
    133169  }
    134170}
  • lemon/bits/windows.h

    r576 r1340  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_BITS_WINDOWS_H
    2121
     22#include <lemon/config.h>
    2223#include <string>
    2324
     
    2930    std::string getWinFormattedDate();
    3031    int getWinRndSeed();
     32
     33    class WinLock {
     34    public:
     35      WinLock();
     36      ~WinLock();
     37      void lock();
     38      void unlock();\
     39    private:
     40      void *_repr;
     41    };
    3142  }
    3243}
  • lemon/capacity_scaling.h

    r956 r1363  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2828#include <limits>
    2929#include <lemon/core.h>
     30#include <lemon/maps.h>
    3031#include <lemon/bin_heap.h>
    3132
     
    6768  /// \ref CapacityScaling implements the capacity scaling version
    6869  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     70  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     71  /// \cite edmondskarp72theoretical. It is an efficient dual
     72  /// solution method, which runs in polynomial time
     73  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     74  /// of node supply and arc capacity values.
     75  ///
     76  /// This algorithm is typically slower than \ref CostScaling and
     77  /// \ref NetworkSimplex, but in special cases, it can be more
     78  /// efficient than them.
     79  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7280  ///
    7381  /// Most of the parameters of the problem (except for the digraph)
     
    8795  /// consider to use the named template parameters instead.
    8896  ///
    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.
     97  /// \warning Both \c V and \c C must be signed number types.
     98  /// \warning Capacity bounds and supply values must be integer, but
     99  /// arc costs can be arbitrary real numbers.
     100  /// \warning This algorithm does not support negative costs for
     101  /// arcs having infinite upper bound.
    93102#ifdef DOXYGEN
    94103  template <typename GR, typename V, typename C, typename TR>
     
    111120    typedef typename TR::Heap Heap;
    112121
    113     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     122    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     123    /// of the algorithm
    114124    typedef TR Traits;
    115125
     
    155165
    156166    // Parameters of the problem
    157     bool _have_lower;
     167    bool _has_lower;
    158168    Value _sum_supply;
    159169
     
    348358    template <typename LowerMap>
    349359    CapacityScaling& lowerMap(const LowerMap& map) {
    350       _have_lower = true;
     360      _has_lower = true;
    351361      for (ArcIt a(_graph); a != INVALID; ++a) {
    352362        _lower[_arc_idf[a]] = map[a];
    353         _lower[_arc_idb[a]] = map[a];
    354363      }
    355364      return *this;
     
    423432    ///
    424433    /// Using this function has the same effect as using \ref supplyMap()
    425     /// with such a map in which \c k is assigned to \c s, \c -k is
     434    /// with a map in which \c k is assigned to \c s, \c -k is
    426435    /// assigned to \c t and all other nodes have zero supply value.
    427436    ///
     
    535544        _cost[j] = _forward[j] ? 1 : -1;
    536545      }
    537       _have_lower = false;
     546      _has_lower = false;
    538547      return *this;
    539548    }
     
    638647    ///
    639648    /// This function returns the total cost of the found flow.
    640     /// Its complexity is O(e).
     649    /// Its complexity is O(m).
    641650    ///
    642651    /// \note The return type of the function can be specified as a
     
    676685    }
    677686
    678     /// \brief Return the flow map (the primal solution).
     687    /// \brief Copy the flow values (the primal solution) into the
     688    /// given map.
    679689    ///
    680690    /// This function copies the flow value on each arc into the given
     
    700710    }
    701711
    702     /// \brief Return the potential map (the dual solution).
     712    /// \brief Copy the potential values (the dual solution) into the
     713    /// given map.
    703714    ///
    704715    /// This function copies the potential (dual value) of each node
     
    730741      if (_sum_supply > 0) return INFEASIBLE;
    731742
     743      // Check lower and upper bounds
     744      LEMON_DEBUG(checkBoundMaps(),
     745          "Upper bounds must be greater or equal to the lower bounds");
     746
     747
    732748      // Initialize vectors
    733749      for (int i = 0; i != _root; ++i) {
     
    739755      const Value MAX = std::numeric_limits<Value>::max();
    740756      int last_out;
    741       if (_have_lower) {
     757      if (_has_lower) {
    742758        for (int i = 0; i != _root; ++i) {
    743759          last_out = _first_out[i+1];
     
    824840    }
    825841
     842    // Check if the upper bound is greater than or equal to the lower bound
     843    // on each forward arc.
     844    bool checkBoundMaps() {
     845      for (int j = 0; j != _res_arc_num; ++j) {
     846        if (_forward[j] && _upper[j] < _lower[j]) return false;
     847      }
     848      return true;
     849    }
     850
    826851    ProblemType start() {
    827852      // Execute the algorithm
     
    833858
    834859      // Handle non-zero lower bounds
    835       if (_have_lower) {
     860      if (_has_lower) {
    836861        int limit = _first_out[_root];
    837862        for (int j = 0; j != limit; ++j) {
    838           if (!_forward[j]) _res_cap[j] += _lower[j];
     863          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    839864        }
    840865      }
  • lemon/cbc.cc

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

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

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

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

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

    r1157 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5959#if !defined(NDEBUG)
    6060    void (Concept::*x)() = & Concept::constraints;
    61     ignore_unused_variable_warning(x);
     61    ::lemon::ignore_unused_variable_warning(x);
    6262#endif
    6363  }
     
    6969    typedef typename Concept::template Constraints<Type> ConceptCheck;
    7070    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
    71     ignore_unused_variable_warning(x);
     71    ::lemon::ignore_unused_variable_warning(x);
    7272#endif
    7373  }
  • lemon/concepts/digraph.h

    r956 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    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) { ignore_unused_variable_warning(g); }
     315        explicit ArcIt(const Digraph& g) {
     316          ::lemon::ignore_unused_variable_warning(g);
     317        }
    316318        /// Sets the iterator to the given arc.
    317319
     
    410412      /// \brief The base node of the iterator.
    411413      ///
    412       /// Returns the base node of the given incomming arc iterator
     414      /// Returns the base node of the given incoming arc iterator
    413415      /// (i.e. the target node of the corresponding arc).
    414416      Node baseNode(InArcIt) const { return INVALID; }
     
    416418      /// \brief The running node of the iterator.
    417419      ///
    418       /// Returns the running node of the given incomming arc iterator
     420      /// Returns the running node of the given incoming arc iterator
    419421      /// (i.e. the source node of the corresponding arc).
    420422      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph.h

    r956 r1271  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    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 DigraphCopy instead.
     75      /// Graphs are \e not copy constructible. Use GraphCopy instead.
    7676      Graph(const Graph&) {}
    7777      /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
     78      /// Use GraphCopy instead.
    7979      void operator=(const Graph&) {}
    8080
     
    397397        /// Sets the iterator to the first arc of the given graph.
    398398        ///
    399         explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     399        explicit ArcIt(const Graph &g) {
     400          ::lemon::ignore_unused_variable_warning(g);
     401        }
    400402        /// Sets the iterator to the given arc.
    401403
     
    443445        ///
    444446        OutArcIt(const Graph& n, const Node& g) {
    445           ignore_unused_variable_warning(n);
    446           ignore_unused_variable_warning(g);
     447          ::lemon::ignore_unused_variable_warning(n);
     448          ::lemon::ignore_unused_variable_warning(g);
    447449        }
    448450        /// Sets the iterator to the given arc.
     
    491493        ///
    492494        InArcIt(const Graph& g, const Node& n) {
    493           ignore_unused_variable_warning(n);
    494           ignore_unused_variable_warning(g);
     495          ::lemon::ignore_unused_variable_warning(n);
     496          ::lemon::ignore_unused_variable_warning(g);
    495497        }
    496498        /// Sets the iterator to the given arc.
     
    758760      /// \brief The base node of the iterator.
    759761      ///
    760       /// Returns the base node of the given incomming arc iterator
     762      /// Returns the base node of the given incoming arc iterator
    761763      /// (i.e. the target node of the corresponding arc).
    762764      Node baseNode(InArcIt) const { return INVALID; }
     
    764766      /// \brief The running node of the iterator.
    765767      ///
    766       /// Returns the running node of the given incomming arc iterator
     768      /// Returns the running node of the given incoming arc iterator
    767769      /// (i.e. the source node of the corresponding arc).
    768770      Node runningNode(InArcIt) const { return INVALID; }
  • lemon/concepts/graph_components.h

    r1159 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    109109
    110110          bool b;
     111          ::lemon::ignore_unused_variable_warning(b);
     112
    111113          b = (ia == ib) && (ia != ib);
    112114          b = (ia == INVALID) && (ib != INVALID);
     
    288290            ue = e;
    289291            bool d = graph.direction(e);
    290             ignore_unused_variable_warning(d);
     292            ::lemon::ignore_unused_variable_warning(d);
    291293          }
    292294        }
     
    294296        const _Graph& graph;
    295297      Constraints() {}
     298      };
     299
     300    };
     301
     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;
    296464      };
    297465
     
    367535
    368536          nid = digraph.maxNodeId();
    369           ignore_unused_variable_warning(nid);
     537          ::lemon::ignore_unused_variable_warning(nid);
    370538          eid = digraph.maxArcId();
    371           ignore_unused_variable_warning(eid);
     539          ::lemon::ignore_unused_variable_warning(eid);
    372540        }
    373541
     
    422590          edge = graph.edgeFromId(ueid);
    423591          ueid = graph.maxEdgeId();
    424           ignore_unused_variable_warning(ueid);
     592          ::lemon::ignore_unused_variable_warning(ueid);
    425593        }
    426594
    427595        const _Graph& graph;
    428596        Constraints() {}
     597      };
     598    };
     599
     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;
    429661      };
    430662    };
     
    495727          _GraphItemIt it3 = it1;
    496728          _GraphItemIt it4 = INVALID;
    497           ignore_unused_variable_warning(it3);
    498           ignore_unused_variable_warning(it4);
     729          ::lemon::ignore_unused_variable_warning(it3);
     730          ::lemon::ignore_unused_variable_warning(it4);
    499731
    500732          it2 = ++it1;
     
    586818          _GraphIncIt it3 = it1;
    587819          _GraphIncIt it4 = INVALID;
    588           ignore_unused_variable_warning(it3);
    589           ignore_unused_variable_warning(it4);
     820          ::lemon::ignore_unused_variable_warning(it3);
     821          ::lemon::ignore_unused_variable_warning(it4);
    590822
    591823          it2 = ++it1;
     
    644876      void next(Arc&) const {}
    645877
    646       /// \brief Return the first arc incomming to the given node.
    647       ///
    648       /// This function gives back the first arc incomming to the
     878      /// \brief Return the first arc incoming to the given node.
     879      ///
     880      /// This function gives back the first arc incoming to the
    649881      /// given node.
    650882      void firstIn(Arc&, const Node&) const {}
    651883
    652       /// \brief Return the next arc incomming to the given node.
    653       ///
    654       /// This function gives back the next arc incomming to the
     884      /// \brief Return the next arc incoming to the given node.
     885      ///
     886      /// This function gives back the next arc incoming to the
    655887      /// given node.
    656888      void nextIn(Arc&) const {}
     
    7691001            n = digraph.baseNode(oait);
    7701002            n = digraph.runningNode(oait);
    771             ignore_unused_variable_warning(n);
     1003            ::lemon::ignore_unused_variable_warning(n);
    7721004          }
    7731005        }
     
    9031135    };
    9041136
     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
    9051228    /// \brief Skeleton class for alterable directed graphs.
    9061229    ///
     
    9281251      ArcNotifier;
    9291252
     1253      mutable NodeNotifier node_notifier;
     1254      mutable ArcNotifier arc_notifier;
     1255
    9301256      /// \brief Return the node alteration notifier.
    9311257      ///
    9321258      /// This function gives back the node alteration notifier.
    9331259      NodeNotifier& notifier(Node) const {
    934          return NodeNotifier();
     1260        return node_notifier;
    9351261      }
    9361262
     
    9391265      /// This function gives back the arc alteration notifier.
    9401266      ArcNotifier& notifier(Arc) const {
    941         return ArcNotifier();
     1267        return arc_notifier;
    9421268      }
    9431269
     
    9521278            = digraph.notifier(typename _Digraph::Arc());
    9531279
    954           ignore_unused_variable_warning(nn);
    955           ignore_unused_variable_warning(en);
     1280          ::lemon::ignore_unused_variable_warning(nn);
     1281          ::lemon::ignore_unused_variable_warning(en);
    9561282        }
    9571283
     
    9751301
    9761302      typedef BAS Base;
     1303      typedef AlterableDigraphComponent<Base> Parent;
    9771304      typedef typename Base::Edge Edge;
    9781305
     
    9821309      EdgeNotifier;
    9831310
     1311      mutable EdgeNotifier edge_notifier;
     1312
     1313      using Parent::notifier;
     1314
    9841315      /// \brief Return the edge alteration notifier.
    9851316      ///
    9861317      /// This function gives back the edge alteration notifier.
    9871318      EdgeNotifier& notifier(Edge) const {
    988         return EdgeNotifier();
     1319        return edge_notifier;
    9891320      }
    9901321
     
    9951326          typename _Graph::EdgeNotifier& uen
    9961327            = graph.notifier(typename _Graph::Edge());
    997           ignore_unused_variable_warning(uen);
     1328          ::lemon::ignore_unused_variable_warning(uen);
    9981329        }
    9991330
    10001331        const _Graph& graph;
    10011332        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;
    10021395      };
    10031396    };
     
    10691462          // m3 = cmap;
    10701463
    1071           ignore_unused_variable_warning(m1);
    1072           ignore_unused_variable_warning(m2);
    1073           // ignore_unused_variable_warning(m3);
     1464          ::lemon::ignore_unused_variable_warning(m1);
     1465          ::lemon::ignore_unused_variable_warning(m2);
     1466          // ::lemon::ignore_unused_variable_warning(m3);
    10741467        }
    10751468
     
    13061699    };
    13071700
     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
    13081845    /// \brief Skeleton class for extendable directed graphs.
    13091846    ///
     
    13961933    };
    13971934
     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
    13981994    /// \brief Skeleton class for erasable directed graphs.
    13991995    ///
     
    14762072    };
    14772073
     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
    14782083    /// \brief Skeleton class for clearable directed graphs.
    14792084    ///
     
    15122117    /// This concept requires \ref AlterableGraphComponent.
    15132118    template <typename BAS = BaseGraphComponent>
    1514     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1515     public:
    1516 
    1517       typedef BAS Base;
    1518 
    1519       /// \brief Erase all nodes and edges from the graph.
    1520       ///
    1521       /// This function erases all nodes and edges from the graph.
    1522       void clear() {}
    1523 
    1524       template <typename _Graph>
    1525       struct Constraints {
    1526         void constraints() {
    1527           checkConcept<Base, _Graph>();
    1528           graph.clear();
    1529         }
    1530 
    1531         _Graph& graph;
    1532         Constraints() {}
    1533       };
    1534     };
     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> {};
    15352129
    15362130  }
  • lemon/concepts/heap.h

    r1127 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    261261          item=Item();
    262262          prio=Prio();
    263           ignore_unused_variable_warning(item);
    264           ignore_unused_variable_warning(prio);
     263          ::lemon::ignore_unused_variable_warning(item);
     264          ::lemon::ignore_unused_variable_warning(prio);
    265265
    266266          OwnItem own_item;
     
    269269          own_item=Item();
    270270          own_prio=Prio();
    271           ignore_unused_variable_warning(own_item);
    272           ignore_unused_variable_warning(own_prio);
    273           ignore_unused_variable_warning(own_state);
     271          ::lemon::ignore_unused_variable_warning(own_item);
     272          ::lemon::ignore_unused_variable_warning(own_prio);
     273          ::lemon::ignore_unused_variable_warning(own_state);
    274274
    275275          _Heap heap1(map);
    276276          _Heap heap2 = heap1;
    277           ignore_unused_variable_warning(heap1);
    278           ignore_unused_variable_warning(heap2);
     277          ::lemon::ignore_unused_variable_warning(heap1);
     278          ::lemon::ignore_unused_variable_warning(heap2);
    279279
    280280          int s = heap.size();
    281           ignore_unused_variable_warning(s);
     281          ::lemon::ignore_unused_variable_warning(s);
    282282          bool e = heap.empty();
    283           ignore_unused_variable_warning(e);
     283          ::lemon::ignore_unused_variable_warning(e);
    284284
    285285          prio = heap.prio();
  • lemon/concepts/maps.h

    r1157 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6161          own_val = m[own_key];
    6262
    63           ignore_unused_variable_warning(key);
    64           ignore_unused_variable_warning(val);
    65           ignore_unused_variable_warning(own_key);
    66           ignore_unused_variable_warning(own_val);
     63          ::lemon::ignore_unused_variable_warning(key);
     64          ::lemon::ignore_unused_variable_warning(val);
     65          ::lemon::ignore_unused_variable_warning(own_key);
     66          ::lemon::ignore_unused_variable_warning(own_val);
    6767        }
    6868        const Key& key;
     
    101101          m.set(own_key, own_val);
    102102
    103           ignore_unused_variable_warning(key);
    104           ignore_unused_variable_warning(val);
    105           ignore_unused_variable_warning(own_key);
    106           ignore_unused_variable_warning(own_val);
     103          ::lemon::ignore_unused_variable_warning(key);
     104          ::lemon::ignore_unused_variable_warning(val);
     105          ::lemon::ignore_unused_variable_warning(own_key);
     106          ::lemon::ignore_unused_variable_warning(own_val);
    107107        }
    108108        const Key& key;
  • lemon/concepts/path.h

    r1127 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676      template <typename CPath>
    7777      Path& operator=(const CPath& cpath) {
    78         ignore_unused_variable_warning(cpath);
     78        ::lemon::ignore_unused_variable_warning(cpath);
    7979        return *this;
    8080      }
     
    136136          e = (i < ii);
    137137
    138           ignore_unused_variable_warning(l);
    139           ignore_unused_variable_warning(pp);
    140           ignore_unused_variable_warning(e);
    141           ignore_unused_variable_warning(id);
    142           ignore_unused_variable_warning(ii);
    143           ignore_unused_variable_warning(ed);
     138          ::lemon::ignore_unused_variable_warning(l);
     139          ::lemon::ignore_unused_variable_warning(pp);
     140          ::lemon::ignore_unused_variable_warning(e);
     141          ::lemon::ignore_unused_variable_warning(id);
     142          ::lemon::ignore_unused_variable_warning(ii);
     143          ::lemon::ignore_unused_variable_warning(ed);
    144144        }
    145145      };
     
    163163          e = (i != INVALID);
    164164
    165           ignore_unused_variable_warning(l);
    166           ignore_unused_variable_warning(e);
    167           ignore_unused_variable_warning(id);
    168           ignore_unused_variable_warning(ed);
     165          ::lemon::ignore_unused_variable_warning(l);
     166          ::lemon::ignore_unused_variable_warning(e);
     167          ::lemon::ignore_unused_variable_warning(id);
     168          ::lemon::ignore_unused_variable_warning(ed);
    169169        }
    170170        _Path& p;
     
    189189          e = (i != INVALID);
    190190
    191           ignore_unused_variable_warning(l);
    192           ignore_unused_variable_warning(e);
    193           ignore_unused_variable_warning(id);
    194           ignore_unused_variable_warning(ed);
     191          ::lemon::ignore_unused_variable_warning(l);
     192          ::lemon::ignore_unused_variable_warning(e);
     193          ::lemon::ignore_unused_variable_warning(id);
     194          ::lemon::ignore_unused_variable_warning(ed);
    195195        }
    196196        _Path& p;
  • lemon/config.h.in

    r725 r1340  
    1 /* The version string */
    2 #undef LEMON_VERSION
     1#ifndef LEMON_CONFIG_H
     2#define LEMON_CONFIG_H
    33
    4 /* Define to 1 if you have long long */
    5 #undef LEMON_HAVE_LONG_LONG
     4#define LEMON_VERSION "@PROJECT_VERSION@"
     5#cmakedefine LEMON_HAVE_LONG_LONG 1
    66
    7 /* Define to 1 if you have any LP solver. */
    8 #undef LEMON_HAVE_LP
     7#cmakedefine LEMON_WIN32 1
    98
    10 /* Define to 1 if you have any MIP solver. */
    11 #undef LEMON_HAVE_MIP
     9#cmakedefine LEMON_HAVE_LP 1
     10#cmakedefine LEMON_HAVE_MIP 1
     11#cmakedefine LEMON_HAVE_GLPK 1
     12#cmakedefine LEMON_HAVE_CPLEX 1
     13#cmakedefine LEMON_HAVE_SOPLEX 1
     14#cmakedefine LEMON_HAVE_CLP 1
     15#cmakedefine LEMON_HAVE_CBC 1
    1216
    13 /* Define to 1 if you have CPLEX. */
    14 #undef LEMON_HAVE_CPLEX
     17#define LEMON_CPLEX_ 1
     18#define LEMON_CLP_ 2
     19#define LEMON_GLPK_ 3
     20#define LEMON_SOPLEX_ 4
     21#define LEMON_CBC_ 5
    1522
    16 /* Define to 1 if you have GLPK. */
    17 #undef LEMON_HAVE_GLPK
     23#cmakedefine LEMON_DEFAULT_LP LEMON_@LEMON_DEFAULT_LP@_
     24#cmakedefine LEMON_DEFAULT_MIP LEMON_@LEMON_DEFAULT_MIP@_
    1825
    19 /* Define to 1 if you have SOPLEX */
    20 #undef LEMON_HAVE_SOPLEX
     26#cmakedefine LEMON_USE_PTHREAD 1
     27#cmakedefine LEMON_USE_WIN32_THREADS 1
    2128
    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
     29#endif
  • lemon/connectivity.h

    r956 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    746746  ///
    747747  /// This function checks whether the given undirected graph is
    748   /// bi-node-connected, i.e. any two edges are on same circle.
     748  /// bi-node-connected, i.e. a connected graph without articulation
     749  /// node.
    749750  ///
    750751  /// \return \c true if the graph bi-node-connected.
    751   /// \note By definition, the empty graph is bi-node-connected.
     752  ///
     753  /// \note By definition,
     754  /// \li a graph consisting of zero or one node is bi-node-connected,
     755  /// \li a graph consisting of two isolated nodes
     756  /// is \e not bi-node-connected and
     757  /// \li a graph consisting of two nodes connected by an edge
     758  /// is bi-node-connected.
    752759  ///
    753760  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
    754761  template <typename Graph>
    755762  bool biNodeConnected(const Graph& graph) {
     763    bool hasNonIsolated = false, hasIsolated = false;
     764    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
     765      if (typename Graph::OutArcIt(graph, n) == INVALID) {
     766        if (hasIsolated || hasNonIsolated) {
     767          return false;
     768        } else {
     769          hasIsolated = true;
     770        }
     771      } else {
     772        if (hasIsolated) {
     773          return false;
     774        } else {
     775          hasNonIsolated = true;
     776        }
     777      }
     778    }
    756779    return countBiNodeConnectedComponents(graph) <= 1;
    757780  }
  • lemon/core.h

    r1159 r1341  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_CORE_H
    2121
    22 #include <vector>
    23 #include <algorithm>
    24 
    25 #include <lemon/config.h>
    26 #include <lemon/bits/enable_if.h>
    27 #include <lemon/bits/traits.h>
    28 #include <lemon/assert.h>
    29 
    30 // Disable the following warnings when compiling with MSVC:
    31 // C4250: 'class1' : inherits 'class2::member' via dominance
    32 // C4355: 'this' : used in base member initializer list
    33 // C4503: 'function' : decorated name length exceeded, name was truncated
    34 // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    35 // C4996: 'function': was declared deprecated
    36 #ifdef _MSC_VER
    37 #pragma warning( disable : 4250 4355 4503 4800 4996 )
    38 #endif
    39 
    4022///\file
    4123///\brief LEMON core utilities.
     
    4426///It is automatically included by all graph types, therefore it usually
    4527///do not have to be included directly.
     28
     29// Disable the following warnings when compiling with MSVC:
     30// C4250: 'class1' : inherits 'class2::member' via dominance
     31// C4267: conversion from 'size_t' to 'type', possible loss of data
     32// C4355: 'this' : used in base member initializer list
     33// C4503: 'function' : decorated name length exceeded, name was truncated
     34// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     35// C4996: 'function': was declared deprecated
     36#ifdef _MSC_VER
     37#pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
     38#endif
     39
     40#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
     41// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     42#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
     43#endif
     44
     45#include <vector>
     46#include <algorithm>
     47
     48#include <lemon/config.h>
     49#include <lemon/bits/enable_if.h>
     50#include <lemon/bits/traits.h>
     51#include <lemon/assert.h>
     52
     53
    4654
    4755namespace lemon {
     
    149157  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    150158
     159  ///Create convenience typedefs for the bipartite graph types and iterators
     160
     161  ///This \c \#define creates the same convenient type definitions as
     162  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
     163  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
     164  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
     165  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
     166  ///
     167  ///\note If the graph type is a dependent type, ie. the graph type depend
     168  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     169  ///macro.
     170#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     171  GRAPH_TYPEDEFS(BpGraph);                                              \
     172  typedef BpGraph::RedNode RedNode;                                     \
     173  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
     174  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
     175  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
     176  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
     177  typedef BpGraph::BlueNode BlueNode;                                   \
     178  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
     179  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
     180  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
     181  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
     182
     183  ///Create convenience typedefs for the bipartite graph types and iterators
     184
     185  ///\see BPGRAPH_TYPEDEFS
     186  ///
     187  ///\note Use this macro, if the graph type is a dependent type,
     188  ///ie. the graph type depend on a template parameter.
     189#define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph)                                  \
     190  TEMPLATE_GRAPH_TYPEDEFS(BpGraph);                                         \
     191  typedef typename BpGraph::RedNode RedNode;                                \
     192  typedef typename BpGraph::RedNodeIt RedNodeIt;                            \
     193  typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap;       \
     194  typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap;         \
     195  typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap;   \
     196  typedef typename BpGraph::BlueNode BlueNode;                              \
     197  typedef typename BpGraph::BlueNodeIt BlueNodeIt;                          \
     198  typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap;     \
     199  typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap;       \
     200  typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap
     201
    151202  /// \brief Function to count the items in a graph.
    152203  ///
     
    200251  }
    201252
     253  namespace _graph_utils_bits {
     254
     255    template <typename Graph, typename Enable = void>
     256    struct CountRedNodesSelector {
     257      static int count(const Graph &g) {
     258        return countItems<Graph, typename Graph::RedNode>(g);
     259      }
     260    };
     261
     262    template <typename Graph>
     263    struct CountRedNodesSelector<
     264      Graph, typename
     265      enable_if<typename Graph::NodeNumTag, void>::type>
     266    {
     267      static int count(const Graph &g) {
     268        return g.redNum();
     269      }
     270    };
     271  }
     272
     273  /// \brief Function to count the red nodes in the graph.
     274  ///
     275  /// This function counts the red nodes in the graph.
     276  /// The complexity of the function is O(n) but for some
     277  /// graph structures it is specialized to run in O(1).
     278  ///
     279  /// If the graph contains a \e redNum() member function and a
     280  /// \e NodeNumTag tag then this function calls directly the member
     281  /// function to query the cardinality of the node set.
     282  template <typename Graph>
     283  inline int countRedNodes(const Graph& g) {
     284    return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g);
     285  }
     286
     287  namespace _graph_utils_bits {
     288
     289    template <typename Graph, typename Enable = void>
     290    struct CountBlueNodesSelector {
     291      static int count(const Graph &g) {
     292        return countItems<Graph, typename Graph::BlueNode>(g);
     293      }
     294    };
     295
     296    template <typename Graph>
     297    struct CountBlueNodesSelector<
     298      Graph, typename
     299      enable_if<typename Graph::NodeNumTag, void>::type>
     300    {
     301      static int count(const Graph &g) {
     302        return g.blueNum();
     303      }
     304    };
     305  }
     306
     307  /// \brief Function to count the blue nodes in the graph.
     308  ///
     309  /// This function counts the blue nodes in the graph.
     310  /// The complexity of the function is O(n) but for some
     311  /// graph structures it is specialized to run in O(1).
     312  ///
     313  /// If the graph contains a \e blueNum() member function and a
     314  /// \e NodeNumTag tag then this function calls directly the member
     315  /// function to query the cardinality of the node set.
     316  template <typename Graph>
     317  inline int countBlueNodes(const Graph& g) {
     318    return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g);
     319  }
     320
    202321  // Arc counting:
    203322
     
    441560      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    442561      static void copy(const From& from, Graph &to,
    443                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     562                       NodeRefMap& nodeRefMap,
     563                       EdgeRefMap& edgeRefMap) {
    444564        to.build(from, nodeRefMap, edgeRefMap);
    445565      }
    446566    };
    447567
     568    template <typename BpGraph, typename Enable = void>
     569    struct BpGraphCopySelector {
     570      template <typename From, typename RedNodeRefMap,
     571                typename BlueNodeRefMap, typename EdgeRefMap>
     572      static void copy(const From& from, BpGraph &to,
     573                       RedNodeRefMap& redNodeRefMap,
     574                       BlueNodeRefMap& blueNodeRefMap,
     575                       EdgeRefMap& edgeRefMap) {
     576        to.clear();
     577        for (typename From::RedNodeIt it(from); it != INVALID; ++it) {
     578          redNodeRefMap[it] = to.addRedNode();
     579        }
     580        for (typename From::BlueNodeIt it(from); it != INVALID; ++it) {
     581          blueNodeRefMap[it] = to.addBlueNode();
     582        }
     583        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
     584          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
     585                                      blueNodeRefMap[from.blueNode(it)]);
     586        }
     587      }
     588    };
     589
     590    template <typename BpGraph>
     591    struct BpGraphCopySelector<
     592      BpGraph,
     593      typename enable_if<typename BpGraph::BuildTag, void>::type>
     594    {
     595      template <typename From, typename RedNodeRefMap,
     596                typename BlueNodeRefMap, typename EdgeRefMap>
     597      static void copy(const From& from, BpGraph &to,
     598                       RedNodeRefMap& redNodeRefMap,
     599                       BlueNodeRefMap& blueNodeRefMap,
     600                       EdgeRefMap& edgeRefMap) {
     601        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
     602      }
     603    };
     604
    448605  }
     606
     607  /// \brief Check whether a graph is undirected.
     608  ///
     609  /// This function returns \c true if the given graph is undirected.
     610#ifdef DOXYGEN
     611  template <typename GR>
     612  bool undirected(const GR& g) { return false; }
     613#else
     614  template <typename GR>
     615  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     616  undirected(const GR&) {
     617    return true;
     618  }
     619  template <typename GR>
     620  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     621  undirected(const GR&) {
     622    return false;
     623  }
     624#endif
    449625
    450626  /// \brief Class to copy a digraph.
     
    9711147  graphCopy(const From& from, To& to) {
    9721148    return GraphCopy<From, To>(from, to);
     1149  }
     1150
     1151  /// \brief Class to copy a bipartite graph.
     1152  ///
     1153  /// Class to copy a bipartite graph to another graph (duplicate a
     1154  /// graph). The simplest way of using it is through the
     1155  /// \c bpGraphCopy() function.
     1156  ///
     1157  /// This class not only make a copy of a bipartite graph, but it can
     1158  /// create references and cross references between the nodes, edges
     1159  /// and arcs of the two graphs, and it can copy maps for using with
     1160  /// the newly created graph.
     1161  ///
     1162  /// To make a copy from a graph, first an instance of BpGraphCopy
     1163  /// should be created, then the data belongs to the graph should
     1164  /// assigned to copy. In the end, the \c run() member should be
     1165  /// called.
     1166  ///
     1167  /// The next code copies a graph with several data:
     1168  ///\code
     1169  ///  BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph);
     1170  ///  // Create references for the nodes
     1171  ///  OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph);
     1172  ///  cg.nodeRef(nr);
     1173  ///  // Create cross references (inverse) for the edges
     1174  ///  NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph);
     1175  ///  cg.edgeCrossRef(ecr);
     1176  ///  // Copy a red node map
     1177  ///  OrigBpGraph::RedNodeMap<double> ormap(orig_graph);
     1178  ///  NewBpGraph::RedNodeMap<double> nrmap(new_graph);
     1179  ///  cg.redNodeMap(ormap, nrmap);
     1180  ///  // Copy a node
     1181  ///  OrigBpGraph::Node on;
     1182  ///  NewBpGraph::Node nn;
     1183  ///  cg.node(on, nn);
     1184  ///  // Execute copying
     1185  ///  cg.run();
     1186  ///\endcode
     1187  template <typename From, typename To>
     1188  class BpGraphCopy {
     1189  private:
     1190
     1191    typedef typename From::Node Node;
     1192    typedef typename From::RedNode RedNode;
     1193    typedef typename From::BlueNode BlueNode;
     1194    typedef typename From::NodeIt NodeIt;
     1195    typedef typename From::Arc Arc;
     1196    typedef typename From::ArcIt ArcIt;
     1197    typedef typename From::Edge Edge;
     1198    typedef typename From::EdgeIt EdgeIt;
     1199
     1200    typedef typename To::Node TNode;
     1201    typedef typename To::RedNode TRedNode;
     1202    typedef typename To::BlueNode TBlueNode;
     1203    typedef typename To::Arc TArc;
     1204    typedef typename To::Edge TEdge;
     1205
     1206    typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap;
     1207    typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap;
     1208    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
     1209
     1210    struct NodeRefMap {
     1211      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
     1212                 const BlueNodeRefMap& blue_node_ref)
     1213        : _from(from), _red_node_ref(red_node_ref),
     1214          _blue_node_ref(blue_node_ref) {}
     1215
     1216      typedef typename From::Node Key;
     1217      typedef typename To::Node Value;
     1218
     1219      Value operator[](const Key& key) const {
     1220        if (_from.red(key)) {
     1221          return _red_node_ref[_from.asRedNodeUnsafe(key)];
     1222        } else {
     1223          return _blue_node_ref[_from.asBlueNodeUnsafe(key)];
     1224        }
     1225      }
     1226
     1227      const From& _from;
     1228      const RedNodeRefMap& _red_node_ref;
     1229      const BlueNodeRefMap& _blue_node_ref;
     1230    };
     1231
     1232    struct ArcRefMap {
     1233      ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref)
     1234        : _from(from), _to(to), _edge_ref(edge_ref) {}
     1235
     1236      typedef typename From::Arc Key;
     1237      typedef typename To::Arc Value;
     1238
     1239      Value operator[](const Key& key) const {
     1240        return _to.direct(_edge_ref[key], _from.direction(key));
     1241      }
     1242
     1243      const From& _from;
     1244      const To& _to;
     1245      const EdgeRefMap& _edge_ref;
     1246    };
     1247
     1248  public:
     1249
     1250    /// \brief Constructor of BpGraphCopy.
     1251    ///
     1252    /// Constructor of BpGraphCopy for copying the content of the
     1253    /// \c from graph into the \c to graph.
     1254    BpGraphCopy(const From& from, To& to)
     1255      : _from(from), _to(to) {}
     1256
     1257    /// \brief Destructor of BpGraphCopy
     1258    ///
     1259    /// Destructor of BpGraphCopy.
     1260    ~BpGraphCopy() {
     1261      for (int i = 0; i < int(_node_maps.size()); ++i) {
     1262        delete _node_maps[i];
     1263      }
     1264      for (int i = 0; i < int(_red_maps.size()); ++i) {
     1265        delete _red_maps[i];
     1266      }
     1267      for (int i = 0; i < int(_blue_maps.size()); ++i) {
     1268        delete _blue_maps[i];
     1269      }
     1270      for (int i = 0; i < int(_arc_maps.size()); ++i) {
     1271        delete _arc_maps[i];
     1272      }
     1273      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     1274        delete _edge_maps[i];
     1275      }
     1276    }
     1277
     1278    /// \brief Copy the node references into the given map.
     1279    ///
     1280    /// This function copies the node references into the given map.
     1281    /// The parameter should be a map, whose key type is the Node type of
     1282    /// the source graph, while the value type is the Node type of the
     1283    /// destination graph.
     1284    template <typename NodeRef>
     1285    BpGraphCopy& nodeRef(NodeRef& map) {
     1286      _node_maps.push_back(new _core_bits::RefCopy<From, Node,
     1287                           NodeRefMap, NodeRef>(map));
     1288      return *this;
     1289    }
     1290
     1291    /// \brief Copy the node cross references into the given map.
     1292    ///
     1293    /// This function copies the node cross references (reverse references)
     1294    /// into the given map. The parameter should be a map, whose key type
     1295    /// is the Node type of the destination graph, while the value type is
     1296    /// the Node type of the source graph.
     1297    template <typename NodeCrossRef>
     1298    BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
     1299      _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
     1300                           NodeRefMap, NodeCrossRef>(map));
     1301      return *this;
     1302    }
     1303
     1304    /// \brief Make a copy of the given node map.
     1305    ///
     1306    /// This function makes a copy of the given node map for the newly
     1307    /// created graph.
     1308    /// The key type of the new map \c tmap should be the Node type of the
     1309    /// destination graph, and the key type of the original map \c map
     1310    /// should be the Node type of the source graph.
     1311    template <typename FromMap, typename ToMap>
     1312    BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
     1313      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
     1314                           NodeRefMap, FromMap, ToMap>(map, tmap));
     1315      return *this;
     1316    }
     1317
     1318    /// \brief Make a copy of the given node.
     1319    ///
     1320    /// This function makes a copy of the given node.
     1321    BpGraphCopy& node(const Node& node, TNode& tnode) {
     1322      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
     1323                           NodeRefMap, TNode>(node, tnode));
     1324      return *this;
     1325    }
     1326
     1327    /// \brief Copy the red node references into the given map.
     1328    ///
     1329    /// This function copies the red node references into the given
     1330    /// map.  The parameter should be a map, whose key type is the
     1331    /// Node type of the source graph with the red item set, while the
     1332    /// value type is the Node type of the destination graph.
     1333    template <typename RedRef>
     1334    BpGraphCopy& redRef(RedRef& map) {
     1335      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
     1336                          RedNodeRefMap, RedRef>(map));
     1337      return *this;
     1338    }
     1339
     1340    /// \brief Copy the red node cross references into the given map.
     1341    ///
     1342    /// This function copies the red node cross references (reverse
     1343    /// references) into the given map. The parameter should be a map,
     1344    /// whose key type is the Node type of the destination graph with
     1345    /// the red item set, while the value type is the Node type of the
     1346    /// source graph.
     1347    template <typename RedCrossRef>
     1348    BpGraphCopy& redCrossRef(RedCrossRef& map) {
     1349      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
     1350                          RedNodeRefMap, RedCrossRef>(map));
     1351      return *this;
     1352    }
     1353
     1354    /// \brief Make a copy of the given red node map.
     1355    ///
     1356    /// This function makes a copy of the given red node map for the newly
     1357    /// created graph.
     1358    /// The key type of the new map \c tmap should be the Node type of
     1359    /// the destination graph with the red items, and the key type of
     1360    /// the original map \c map should be the Node type of the source
     1361    /// graph.
     1362    template <typename FromMap, typename ToMap>
     1363    BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) {
     1364      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
     1365                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
     1366      return *this;
     1367    }
     1368
     1369    /// \brief Make a copy of the given red node.
     1370    ///
     1371    /// This function makes a copy of the given red node.
     1372    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
     1373      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
     1374                          RedNodeRefMap, TRedNode>(node, tnode));
     1375      return *this;
     1376    }
     1377
     1378    /// \brief Copy the blue node references into the given map.
     1379    ///
     1380    /// This function copies the blue node references into the given
     1381    /// map.  The parameter should be a map, whose key type is the
     1382    /// Node type of the source graph with the blue item set, while the
     1383    /// value type is the Node type of the destination graph.
     1384    template <typename BlueRef>
     1385    BpGraphCopy& blueRef(BlueRef& map) {
     1386      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
     1387                           BlueNodeRefMap, BlueRef>(map));
     1388      return *this;
     1389    }
     1390
     1391    /// \brief Copy the blue node cross references into the given map.
     1392    ///
     1393    /// This function copies the blue node cross references (reverse
     1394    /// references) into the given map. The parameter should be a map,
     1395    /// whose key type is the Node type of the destination graph with
     1396    /// the blue item set, while the value type is the Node type of the
     1397    /// source graph.
     1398    template <typename BlueCrossRef>
     1399    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
     1400      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
     1401              &