COIN-OR::LEMON - Graph Library

Ignore:
Files:
28 added
20 deleted
134 edited

Legend:

Unmodified
Added
Removed
  • AUTHORS

    r320 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>
     
    2424
    2525Again, please visit the history of the old LEMON repository for more
    26 details: http://lemon.cs.elte.hu/svn/lemon/trunk
     26details: http://lemon.cs.elte.hu/hg/lemon-0.x
  • CMakeLists.txt

    r791 r1313  
    1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
     2
     3CMAKE_POLICY(SET CMP0048 OLD)
    24
    35SET(PROJECT_NAME "LEMON")
    46PROJECT(${PROJECT_NAME})
     7
     8INCLUDE(FindPythonInterp)
     9INCLUDE(FindWget)
    510
    611IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     
    1015ELSE()
    1116  EXECUTE_PROCESS(
    12     COMMAND hg id -i
     17    COMMAND
     18    hg log -r. --template "{latesttag}"
    1319    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    14     OUTPUT_VARIABLE HG_REVISION
     20    OUTPUT_VARIABLE HG_REVISION_TAG
    1521    ERROR_QUIET
    1622    OUTPUT_STRIP_TRAILING_WHITESPACE
    1723  )
    18   IF(HG_REVISION STREQUAL "")
    19     SET(HG_REVISION "hg-tip")
     24  EXECUTE_PROCESS(
     25    COMMAND
     26    hg log -r. --template "{latesttagdistance}"
     27    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     28    OUTPUT_VARIABLE HG_REVISION_DIST
     29    ERROR_QUIET
     30    OUTPUT_STRIP_TRAILING_WHITESPACE
     31  )
     32  EXECUTE_PROCESS(
     33    COMMAND
     34    hg log -r. --template "{node|short}"
     35    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     36    OUTPUT_VARIABLE HG_REVISION_ID
     37    ERROR_QUIET
     38    OUTPUT_STRIP_TRAILING_WHITESPACE
     39  )
     40
     41  IF(HG_REVISION_TAG STREQUAL "")
     42    SET(HG_REVISION_ID "hg-tip")
     43  ELSE()
     44    IF(HG_REVISION_TAG STREQUAL "null")
     45      SET(HG_REVISION_TAG "trunk")
     46    ELSEIF(HG_REVISION_TAG MATCHES "^r")
     47      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
     48    ENDIF()
     49    IF(HG_REVISION_DIST STREQUAL "0")
     50      SET(HG_REVISION ${HG_REVISION_TAG})
     51    ELSE()
     52      SET(HG_REVISION
     53        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
     54    ENDIF()
    2055  ENDIF()
     56
    2157  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
    2258ENDIF()
     
    2864FIND_PACKAGE(Doxygen)
    2965FIND_PACKAGE(Ghostscript)
    30 FIND_PACKAGE(GLPK 4.33)
    31 FIND_PACKAGE(CPLEX)
    32 FIND_PACKAGE(COIN)
     66
     67SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     68SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     69SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     70SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
     71
     72IF(LEMON_ENABLE_GLPK)
     73  FIND_PACKAGE(GLPK 4.33)
     74ENDIF(LEMON_ENABLE_GLPK)
     75IF(LEMON_ENABLE_ILOG)
     76  FIND_PACKAGE(ILOG)
     77ENDIF(LEMON_ENABLE_ILOG)
     78IF(LEMON_ENABLE_COIN)
     79  FIND_PACKAGE(COIN)
     80ENDIF(LEMON_ENABLE_COIN)
     81IF(LEMON_ENABLE_SOPLEX)
     82  FIND_PACKAGE(SOPLEX)
     83ENDIF(LEMON_ENABLE_SOPLEX)
     84
     85IF(GLPK_FOUND)
     86  SET(LEMON_HAVE_LP TRUE)
     87  SET(LEMON_HAVE_MIP TRUE)
     88  SET(LEMON_HAVE_GLPK TRUE)
     89ENDIF(GLPK_FOUND)
     90IF(ILOG_FOUND)
     91  SET(LEMON_HAVE_LP TRUE)
     92  SET(LEMON_HAVE_MIP TRUE)
     93  SET(LEMON_HAVE_CPLEX TRUE)
     94ENDIF(ILOG_FOUND)
     95IF(COIN_FOUND)
     96  SET(LEMON_HAVE_LP TRUE)
     97  SET(LEMON_HAVE_MIP TRUE)
     98  SET(LEMON_HAVE_CLP TRUE)
     99  SET(LEMON_HAVE_CBC TRUE)
     100ENDIF(COIN_FOUND)
     101IF(SOPLEX_FOUND)
     102  SET(LEMON_HAVE_LP TRUE)
     103  SET(LEMON_HAVE_SOPLEX TRUE)
     104ENDIF(SOPLEX_FOUND)
     105
     106IF(ILOG_FOUND)
     107  SET(DEFAULT_LP "CPLEX")
     108  SET(DEFAULT_MIP "CPLEX")
     109ELSEIF(COIN_FOUND)
     110  SET(DEFAULT_LP "CLP")
     111  SET(DEFAULT_MIP "CBC")
     112ELSEIF(GLPK_FOUND)
     113  SET(DEFAULT_LP "GLPK")
     114  SET(DEFAULT_MIP "GLPK")
     115ELSEIF(SOPLEX_FOUND)
     116  SET(DEFAULT_LP "SOPLEX")
     117ENDIF()
     118
     119IF(NOT LEMON_DEFAULT_LP OR
     120    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     121    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     122    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
     123    (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
     124  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     125    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     126ELSE()
     127  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     128    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
     129ENDIF()
     130IF(NOT LEMON_DEFAULT_MIP OR
     131    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     132    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     133    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     134  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     135    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     136ELSE()
     137  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     138    "Default MIP solver backend (GLPK, CPLEX or CBC)")
     139ENDIF()
     140
     141
     142IF(DEFINED ENV{LEMON_CXX_WARNING})
     143  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     144ELSE()
     145  IF(CMAKE_COMPILER_IS_GNUCXX)
     146    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     147    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     148    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     149  ELSEIF(MSVC)
     150    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     151    # Still keep it as an example.
     152    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     153    # Suppressed warnings:
     154    # C4250: 'class1' : inherits 'class2::member' via dominance
     155    # C4355: 'this' : used in base member initializer list
     156    # C4503: 'function' : decorated name length exceeded, name was truncated
     157    # C4800: 'type' : forcing value to bool 'true' or 'false'
     158    #        (performance warning)
     159    # C4996: 'function': was declared deprecated
     160  ELSE()
     161    SET(CXX_WARNING "-Wall")
     162  ENDIF()
     163ENDIF()
     164SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     165
     166SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     167
     168IF(MSVC)
     169  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     170    "Flags used by the C++ compiler during maintainer builds."
     171    )
     172  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     173    "Flags used by the C compiler during maintainer builds."
     174    )
     175  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     176    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     177    "Flags used for linking binaries during maintainer builds."
     178    )
     179  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     180    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     181    "Flags used by the shared libraries linker during maintainer builds."
     182    )
     183ELSE()
     184  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     185    "Flags used by the C++ compiler during maintainer builds."
     186    )
     187  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     188    "Flags used by the C compiler during maintainer builds."
     189    )
     190  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     191    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     192    "Flags used for linking binaries during maintainer builds."
     193    )
     194  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     195    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     196    "Flags used by the shared libraries linker during maintainer builds."
     197    )
     198ENDIF()
     199
     200MARK_AS_ADVANCED(
     201    CMAKE_CXX_FLAGS_MAINTAINER
     202    CMAKE_C_FLAGS_MAINTAINER
     203    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     204    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     205
     206IF(CMAKE_CONFIGURATION_TYPES)
     207  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     208  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     209  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     210      "Add the configurations that we need"
     211      FORCE)
     212 endif()
     213
     214IF(NOT CMAKE_BUILD_TYPE)
     215  SET(CMAKE_BUILD_TYPE "Release")
     216ENDIF()
     217
     218SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     219    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     220    FORCE )
     221
    33222
    34223INCLUDE(CheckTypeSize)
     
    36225SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    37226
    38 INCLUDE(FindPythonInterp)
     227INCLUDE(FindThreads)
     228
     229IF(NOT LEMON_THREADING)
     230  IF(CMAKE_USE_PTHREADS_INIT)
     231    SET(LEMON_THREADING "Pthread")
     232  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     233    SET(LEMON_THREADING "Win32")
     234  ELSE()
     235    SET(LEMON_THREADING "None")
     236  ENDIF()
     237ENDIF()
     238
     239SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     240  "Choose the threading library, options are: Pthread Win32 None."
     241  FORCE )
     242
     243IF(LEMON_THREADING STREQUAL "Pthread")
     244  SET(LEMON_USE_PTHREAD TRUE)
     245ELSEIF(LEMON_THREADING STREQUAL "Win32")
     246  SET(LEMON_USE_WIN32_THREADS TRUE)
     247ENDIF()
    39248
    40249ENABLE_TESTING()
     250
     251IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     252  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     253ELSE()
     254  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     255ENDIF()
    41256
    42257ADD_SUBDIRECTORY(lemon)
    43258IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     259  ADD_SUBDIRECTORY(contrib)
    44260  ADD_SUBDIRECTORY(demo)
    45261  ADD_SUBDIRECTORY(tools)
     
    65281ENDIF()
    66282
    67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     283CONFIGURE_FILE(
     284  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     285  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     286  @ONLY
     287)
     288
     289SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     290STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     291SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     292ADD_CUSTOM_TARGET(dist
     293  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     294  COMMAND hg archive ${ARCHIVE_NAME}
     295  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     296  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     297  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     298  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     299  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     300  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     301  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     302  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     303  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     304  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     305  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     306  DEPENDS html
     307  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     308
     309# CPACK config (Basically for NSIS)
     310IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    68311  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    69312  SET(CPACK_PACKAGE_VENDOR "EGRES")
  • 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

    r681 r1232  
    66FIND_LIBRARY(COIN_CBC_LIBRARY
    77  NAMES Cbc libCbc
     8  HINTS ${COIN_ROOT_DIR}/lib/coin
    89  HINTS ${COIN_ROOT_DIR}/lib
    910)
    1011FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
    1112  NAMES CbcSolver libCbcSolver
     13  HINTS ${COIN_ROOT_DIR}/lib/coin
    1214  HINTS ${COIN_ROOT_DIR}/lib
    1315)
    1416FIND_LIBRARY(COIN_CGL_LIBRARY
    1517  NAMES Cgl libCgl
     18  HINTS ${COIN_ROOT_DIR}/lib/coin
    1619  HINTS ${COIN_ROOT_DIR}/lib
    1720)
    1821FIND_LIBRARY(COIN_CLP_LIBRARY
    1922  NAMES Clp libClp
     23  HINTS ${COIN_ROOT_DIR}/lib/coin
    2024  HINTS ${COIN_ROOT_DIR}/lib
    2125)
    2226FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
    2327  NAMES CoinUtils libCoinUtils
     28  HINTS ${COIN_ROOT_DIR}/lib/coin
    2429  HINTS ${COIN_ROOT_DIR}/lib
    2530)
    2631FIND_LIBRARY(COIN_OSI_LIBRARY
    2732  NAMES Osi libOsi
     33  HINTS ${COIN_ROOT_DIR}/lib/coin
    2834  HINTS ${COIN_ROOT_DIR}/lib
    2935)
    3036FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
    3137  NAMES OsiCbc libOsiCbc
     38  HINTS ${COIN_ROOT_DIR}/lib/coin
    3239  HINTS ${COIN_ROOT_DIR}/lib
    3340)
    3441FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
    3542  NAMES OsiClp libOsiClp
     43  HINTS ${COIN_ROOT_DIR}/lib/coin
    3644  HINTS ${COIN_ROOT_DIR}/lib
    3745)
    3846FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
    3947  NAMES OsiVol libOsiVol
     48  HINTS ${COIN_ROOT_DIR}/lib/coin
    4049  HINTS ${COIN_ROOT_DIR}/lib
    4150)
    4251FIND_LIBRARY(COIN_VOL_LIBRARY
    4352  NAMES Vol libVol
     53  HINTS ${COIN_ROOT_DIR}/lib/coin
     54  HINTS ${COIN_ROOT_DIR}/lib
     55)
     56
     57FIND_LIBRARY(COIN_ZLIB_LIBRARY
     58  NAMES z libz
     59  HINTS ${COIN_ROOT_DIR}/lib/coin
     60  HINTS ${COIN_ROOT_DIR}/lib
     61)
     62FIND_LIBRARY(COIN_BZ2_LIBRARY
     63  NAMES bz2 libbz2
     64  HINTS ${COIN_ROOT_DIR}/lib/coin
    4465  HINTS ${COIN_ROOT_DIR}/lib
    4566)
     
    5677  COIN_OSI_CBC_LIBRARY
    5778  COIN_OSI_CLP_LIBRARY
    58   COIN_OSI_VOL_LIBRARY
    59   COIN_VOL_LIBRARY
     79  # COIN_OSI_VOL_LIBRARY
     80  # COIN_VOL_LIBRARY
    6081)
    6182
    6283IF(COIN_FOUND)
    6384  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
    64   SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")
    65   SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
    66   SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
     85  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_ZLIB_LIBRARY};${COIN_BZ2_LIBRARY}")
     86  IF(COIN_ZLIB_LIBRARY)
     87    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_ZLIB_LIBRARY}")
     88  ENDIF(COIN_ZLIB_LIBRARY)
     89   IF(COIN_BZ2_LIBRARY)
     90    SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARIES};${COIN_BZ2_LIBRARY}")
     91  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}")
     93  SET(COIN_LIBRARIES ${COIN_CBC_LIBRARIES})
    6794ENDIF(COIN_FOUND)
    6895
     
    79106  COIN_OSI_VOL_LIBRARY
    80107  COIN_VOL_LIBRARY
     108  COIN_ZLIB_LIBRARY
     109  COIN_BZ2_LIBRARY
    81110)
    82 
    83 IF(COIN_FOUND)
    84   SET(LEMON_HAVE_LP TRUE)
    85   SET(LEMON_HAVE_MIP TRUE)
    86   SET(LEMON_HAVE_CLP TRUE)
    87   SET(LEMON_HAVE_CBC TRUE)
    88 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

    r943 r1251  
    33SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
    44SET(abs_top_builddir ${PROJECT_BINARY_DIR})
     5
     6SET(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
    514
    615CONFIGURE_FILE(
     
    1019)
    1120
     21CONFIGURE_FILE(
     22  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
     23  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
     24  @ONLY
     25)
     26
     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
    1236IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    1337  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     
    1640    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    1741    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    18     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
    19     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
    20     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
    21     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    22     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    23     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    24     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    25     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    26     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    27     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    28     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    29     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    30     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    31     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
    3258    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    33     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    3459    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3560    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     
    5378
    5479ENDIF()
     80
     81IF(WGET_FOUND)
     82ADD_CUSTOM_TARGET(update-external-tags
     83  COMMAND ${WGET_EXECUTABLE} -N ${LEMON_DOC_LIBSTDC++_URL}/libstdc++.tag
     84  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     85  )
     86ENDIF()
  • doc/Doxyfile.in

    r803 r1251  
    1 # Doxyfile 1.5.9
     1# Doxyfile 1.7.3
    22
    33#---------------------------------------------------------------------------
     
    55#---------------------------------------------------------------------------
    66DOXYFILE_ENCODING      = UTF-8
    7 PROJECT_NAME           = @PACKAGE_NAME@
    8 PROJECT_NUMBER         = @PACKAGE_VERSION@
     7PROJECT_NAME           =
     8PROJECT_NUMBER         =
     9PROJECT_BRIEF          =
     10PROJECT_LOGO           =
    911OUTPUT_DIRECTORY       =
    1012CREATE_SUBDIRS         = NO
     
    3032OPTIMIZE_FOR_FORTRAN   = NO
    3133OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3235BUILTIN_STL_SUPPORT    = YES
    3336CPP_CLI_SUPPORT        = NO
     
    5558HIDE_SCOPE_NAMES       = YES
    5659SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5761INLINE_INFO            = YES
    5862SORT_MEMBER_DOCS       = NO
    5963SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6065SORT_GROUP_NAMES       = NO
    6166SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6268GENERATE_TODOLIST      = YES
    6369GENERATE_TESTLIST      = YES
     
    7177SHOW_NAMESPACES        = YES
    7278FILE_VERSION_FILTER    =
    73 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     80CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    7481#---------------------------------------------------------------------------
    7582# configuration options related to warning and progress messages
     
    9097                         "@abs_top_srcdir@/lemon/concepts" \
    9198                         "@abs_top_srcdir@/demo" \
     99                         "@abs_top_srcdir@/contrib" \
    92100                         "@abs_top_srcdir@/tools" \
    93101                         "@abs_top_srcdir@/test/test_tools.h" \
    94                          "@abs_top_builddir@/doc/references.dox"
     102                         "@abs_top_builddir@/doc/mainpage.dox"
    95103INPUT_ENCODING         = UTF-8
    96104FILE_PATTERNS          = *.h \
     
    112120FILTER_PATTERNS        =
    113121FILTER_SOURCE_FILES    = NO
     122FILTER_SOURCE_PATTERNS =
    114123#---------------------------------------------------------------------------
    115124# configuration options related to source browsing
    116125#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     126SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118127INLINE_SOURCES         = NO
    119128STRIP_CODE_COMMENTS    = YES
     
    138147HTML_FOOTER            =
    139148HTML_STYLESHEET        =
     149HTML_COLORSTYLE_HUE    = 220
     150HTML_COLORSTYLE_SAT    = 100
     151HTML_COLORSTYLE_GAMMA  = 80
     152HTML_TIMESTAMP         = YES
    140153HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     154HTML_DYNAMIC_SECTIONS  = YES
    142155GENERATE_DOCSET        = NO
    143156DOCSET_FEEDNAME        = "Doxygen generated docs"
    144157DOCSET_BUNDLE_ID       = org.doxygen.Project
     158DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     159DOCSET_PUBLISHER_NAME  = Publisher
    145160GENERATE_HTMLHELP      = NO
    146161CHM_FILE               =
     
    154169QHP_NAMESPACE          = org.doxygen.Project
    155170QHP_VIRTUAL_FOLDER     = doc
     171QHP_CUST_FILTER_NAME   =
     172QHP_CUST_FILTER_ATTRS  =
     173QHP_SECT_FILTER_ATTRS  =
    156174QHG_LOCATION           =
     175GENERATE_ECLIPSEHELP   = NO
     176ECLIPSE_DOC_ID         = org.doxygen.Project
    157177DISABLE_INDEX          = NO
    158178ENUM_VALUES_PER_LINE   = 4
    159179GENERATE_TREEVIEW      = NO
     180USE_INLINE_TREES       = NO
    160181TREEVIEW_WIDTH         = 250
     182EXT_LINKS_IN_WINDOW    = NO
    161183FORMULA_FONTSIZE       = 10
     184FORMULA_TRANSPARENT    = YES
     185USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
     186MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
     187SEARCHENGINE           = YES
     188SERVER_BASED_SEARCH    = NO
    162189#---------------------------------------------------------------------------
    163190# configuration options related to the LaTeX output
     
    176203LATEX_BATCHMODE        = NO
    177204LATEX_HIDE_INDICES     = NO
     205LATEX_SOURCE_CODE      = NO
    178206#---------------------------------------------------------------------------
    179207# configuration options related to the RTF output
     
    224252SKIP_FUNCTION_MACROS   = YES
    225253#---------------------------------------------------------------------------
    226 # Options related to the search engine   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     254# Configuration::additions related to external references
     255#---------------------------------------------------------------------------
     256TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
    229257GENERATE_TAGFILE       = html/lemon.tag
    230258ALLEXTERNALS           = NO
     
    238266HIDE_UNDOC_RELATIONS   = YES
    239267HAVE_DOT               = YES
     268DOT_NUM_THREADS        = 0
    240269DOT_FONTNAME           = FreeSans
    241270DOT_FONTSIZE           = 10
     
    255284DOT_PATH               =
    256285DOTFILE_DIRS           =
     286MSCFILE_DIRS           =
    257287DOT_GRAPH_MAX_NODES    = 50
    258288MAX_DOT_GRAPH_DEPTH    = 0
     
    261291GENERATE_LEGEND        = YES
    262292DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

    r316 r1251  
    33  <navindex>
    44    <tab type="mainpage" visible="yes" title=""/>
    5     <tab type="modules" visible="yes" title=""/>
     5    <tab type="modules" visible="yes" title="" intro=""/>
    66    <tab type="classes" visible="yes" title="">
    7       <tab type="classes" visible="yes" title=""/>
    8       <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
    9       <tab type="hierarchy" visible="yes" title=""/>
    10       <tab type="classmembers" visible="yes" title=""/>
     7      <tab type="classes" visible="yes" title="" intro=""/>
     8      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
     9      <tab type="hierarchy" visible="yes" title="" intro=""/>
     10      <tab type="classmembers" visible="yes" title="" intro=""/>
    1111    </tab>
    1212    <tab type="namespaces" visible="yes" title="">
    13       <tab type="namespaces" visible="yes" title=""/>
    14       <tab type="namespacemembers" visible="yes" title=""/>
     13      <tab type="namespaces" visible="yes" title="" intro=""/>
     14      <tab type="namespacemembers" visible="yes" title="" intro=""/>
    1515    </tab>
    1616    <tab type="files" visible="yes" title="">
    17       <tab type="files" visible="yes" title=""/>
    18       <tab type="globals" visible="yes" title=""/>
     17      <tab type="files" visible="yes" title="" intro=""/>
     18      <tab type="globals" visible="yes" title="" intro=""/>
    1919    </tab>
    20     <tab type="dirs" visible="yes" title=""/>
    21     <tab type="examples" visible="yes" title=""/> 
    22     <tab type="pages" visible="yes" title=""/>
     20    <tab type="examples" visible="yes" title="" intro=""/>
     21    <tab type="pages" visible="yes" title="" intro=""/>
    2322  </navindex>
    2423
  • 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

    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).
     
    6464\endcode
    6565
     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
    6683The \c \@arcs section is very similar to the \c \@nodes section,
    6784it again starts with a header line describing the names of the maps,
     
    7996\endcode
    8097
     98If there is no map in the \c \@arcs section at all, then it must be
     99indicated by a sole '-' sign in the first line.
     100
     101\code
     102 @arcs
     103         -
     104 1   2
     105 1   3
     106 2   3
     107\endcode
     108
    81109The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    82110also store the edge set of an undirected graph. In such case there is
    83111a conventional method for store arc maps in the file, if two columns
    84 has the same caption with \c '+' and \c '-' prefix, then these columns
     112have the same caption with \c '+' and \c '-' prefix, then these columns
    85113can be regarded as the values of an arc map.
    86114
  • 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

    r726 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
     9)
     10
     11CONFIGURE_FILE(
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.in
     13  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     14  @ONLY
    915)
    1016
     
    3137IF(LEMON_HAVE_CPLEX)
    3238  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    33   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     39  INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
    3440ENDIF()
    3541
     
    4450ENDIF()
    4551
     52IF(LEMON_HAVE_SOPLEX)
     53  SET(LEMON_SOURCES ${LEMON_SOURCES} soplex.cc)
     54  INCLUDE_DIRECTORIES(${SOPLEX_INCLUDE_DIRS})
     55ENDIF()
     56
    4657ADD_LIBRARY(lemon ${LEMON_SOURCES})
     58
     59TARGET_LINK_LIBRARIES(lemon
     60  ${GLPK_LIBRARIES} ${COIN_LIBRARIES} ${ILOG_LIBRARIES} ${SOPLEX_LIBRARIES}
     61  )
     62
    4763IF(UNIX)
    48   SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     64  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon VERSION ${LEMON_VERSION} SOVERSION ${LEMON_VERSION})
    4965ENDIF()
    5066
     
    5268  TARGETS lemon
    5369  ARCHIVE DESTINATION lib
     70  LIBRARY DESTINATION lib
    5471  COMPONENT library
    5572)
     
    6784  COMPONENT headers
    6885)
     86
     87INSTALL(
     88  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     89  DESTINATION lib/pkgconfig
     90)
     91
  • lemon/adaptors.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).
     
    13721372    /// and edge filter maps.
    13731373    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
    1374       initialize(graph, node_filter, edge_filter);
     1374      this->initialize(graph, node_filter, edge_filter);
    13751375    }
    13761376
     
    22782278    /// Creates an undirected graph from the given digraph.
    22792279    Undirector(DGR& digraph) {
    2280       initialize(digraph);
     2280      this->initialize(digraph);
    22812281    }
    22822282
  • 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

    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).
     
    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
     
    12521252      }
    12531253      _Visitor& visitor;
     1254      Constraints() {}
    12541255    };
    12551256  };
  • 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

    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).
     
    160160    const Point d=(a+b)/2;
    161161    const Point e=(b+c)/2;
    162     const Point f=(d+e)/2;
     162    // const Point f=(d+e)/2;
    163163    R f1=_f(Bezier3(p1,a,d,e),_d);
    164164    R f2=_f(Bezier3(e,d,c,p4),_d);
  • 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

    r968 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).
     
    524524    // Returns the base node of the iterator
    525525    Node baseNode(const IncEdgeIt &e) const {
    526       return e.direction ? u(e) : v(e);
     526      return e.direction ? this->u(e) : this->v(e);
    527527    }
    528528    // Running node of the iterator
     
    530530    // Returns the running node of the iterator
    531531    Node runningNode(const IncEdgeIt &e) const {
    532       return e.direction ? v(e) : u(e);
     532      return e.direction ? this->v(e) : this->u(e);
    533533    }
    534534
  • 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

    r825 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).
     
    588588    // Returns the base node of the iterator
    589589    Node baseNode(const IncEdgeIt &edge) const {
    590       return edge._direction ? u(edge) : v(edge);
     590      return edge._direction ? this->u(edge) : this->v(edge);
    591591    }
    592592    // Running node of the iterator
     
    594594    // Returns the running node of the iterator
    595595    Node runningNode(const IncEdgeIt &edge) const {
    596       return edge._direction ? v(edge) : u(edge);
     596      return edge._direction ? this->v(edge) : this->u(edge);
    597597    }
    598598
     
    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

    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).
     
    4545      void clear() {
    4646        first_item = -1;
     47        last_item = -1;
    4748        first_free_item = -1;
    4849        items.clear();
  • 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

    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).
     
    4141#include <unistd.h>
    4242#include <ctime>
     43#ifndef WIN32
    4344#include <sys/times.h>
     45#endif
    4446#include <sys/time.h>
    4547#endif
     
    129131#endif
    130132    }
     133
     134    WinLock::WinLock() {
     135#ifdef WIN32
     136      CRITICAL_SECTION *lock = new CRITICAL_SECTION;
     137      InitializeCriticalSection(lock);
     138      _repr = lock;
     139#else
     140      _repr = 0; //Just to avoid 'unused variable' warning with clang
     141#endif
     142    }
     143
     144    WinLock::~WinLock() {
     145#ifdef WIN32
     146      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     147      DeleteCriticalSection(lock);
     148      delete lock;
     149#endif
     150    }
     151
     152    void WinLock::lock() {
     153#ifdef WIN32
     154      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     155      EnterCriticalSection(lock);
     156#endif
     157    }
     158
     159    void WinLock::unlock() {
     160#ifdef WIN32
     161      CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
     162      LeaveCriticalSection(lock);
     163#endif
     164    }
    131165  }
    132166}
  • lemon/bits/windows.h

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

    r956 r1298  
    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).
     
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
     74  ///
     75  /// This algorithm is typically slower than \ref CostScaling and
     76  /// \ref NetworkSimplex, but in special cases, it can be more
     77  /// efficient than them.
     78  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    7279  ///
    7380  /// Most of the parameters of the problem (except for the digraph)
     
    8794  /// consider to use the named template parameters instead.
    8895  ///
    89   /// \warning Both number types must be signed and all input data must
    90   /// be integer.
    91   /// \warning This algorithm does not support negative costs for such
    92   /// arcs that have infinite upper bound.
     96  /// \warning Both \c V and \c C must be signed number types.
     97  /// \warning Capacity bounds and supply values must be integer, but
     98  /// arc costs can be arbitrary real numbers.
     99  /// \warning This algorithm does not support negative costs for
     100  /// arcs having infinite upper bound.
    93101#ifdef DOXYGEN
    94102  template <typename GR, typename V, typename C, typename TR>
     
    111119    typedef typename TR::Heap Heap;
    112120
    113     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     121    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     122    /// of the algorithm
    114123    typedef TR Traits;
    115124
     
    155164
    156165    // Parameters of the problem
    157     bool _have_lower;
     166    bool _has_lower;
    158167    Value _sum_supply;
    159168
     
    348357    template <typename LowerMap>
    349358    CapacityScaling& lowerMap(const LowerMap& map) {
    350       _have_lower = true;
     359      _has_lower = true;
    351360      for (ArcIt a(_graph); a != INVALID; ++a) {
    352361        _lower[_arc_idf[a]] = map[a];
    353         _lower[_arc_idb[a]] = map[a];
    354362      }
    355363      return *this;
     
    423431    ///
    424432    /// 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
     433    /// with a map in which \c k is assigned to \c s, \c -k is
    426434    /// assigned to \c t and all other nodes have zero supply value.
    427435    ///
     
    535543        _cost[j] = _forward[j] ? 1 : -1;
    536544      }
    537       _have_lower = false;
     545      _has_lower = false;
    538546      return *this;
    539547    }
     
    638646    ///
    639647    /// This function returns the total cost of the found flow.
    640     /// Its complexity is O(e).
     648    /// Its complexity is O(m).
    641649    ///
    642650    /// \note The return type of the function can be specified as a
     
    676684    }
    677685
    678     /// \brief Return the flow map (the primal solution).
     686    /// \brief Copy the flow values (the primal solution) into the
     687    /// given map.
    679688    ///
    680689    /// This function copies the flow value on each arc into the given
     
    700709    }
    701710
    702     /// \brief Return the potential map (the dual solution).
     711    /// \brief Copy the potential values (the dual solution) into the
     712    /// given map.
    703713    ///
    704714    /// This function copies the potential (dual value) of each node
     
    730740      if (_sum_supply > 0) return INFEASIBLE;
    731741
     742      // Check lower and upper bounds
     743      LEMON_DEBUG(checkBoundMaps(),
     744          "Upper bounds must be greater or equal to the lower bounds");
     745
     746
    732747      // Initialize vectors
    733748      for (int i = 0; i != _root; ++i) {
     
    739754      const Value MAX = std::numeric_limits<Value>::max();
    740755      int last_out;
    741       if (_have_lower) {
     756      if (_has_lower) {
    742757        for (int i = 0; i != _root; ++i) {
    743758          last_out = _first_out[i+1];
     
    824839    }
    825840
     841    // Check if the upper bound is greater than or equal to the lower bound
     842    // on each forward arc.
     843    bool checkBoundMaps() {
     844      for (int j = 0; j != _res_arc_num; ++j) {
     845        if (_forward[j] && _upper[j] < _lower[j]) return false;
     846      }
     847      return true;
     848    }
     849
    826850    ProblemType start() {
    827851      // Execute the algorithm
     
    833857
    834858      // Handle non-zero lower bounds
    835       if (_have_lower) {
     859      if (_has_lower) {
    836860        int limit = _first_out[_root];
    837861        for (int j = 0; j != limit; ++j) {
    838           if (!_forward[j]) _res_cap[j] += _lower[j];
     862          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    839863        }
    840864      }
  • lemon/cbc.cc

    r793 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).
     
    2626#include <coin/OsiSolverInterface.hpp>
    2727
    28 #ifdef COIN_HAS_CLP
    2928#include "coin/OsiClpSolverInterface.hpp"
    30 #endif
    31 #ifdef COIN_HAS_OSL
    32 #include "coin/OsiOslSolverInterface.hpp"
    33 #endif
    3429
    3530#include "coin/CbcCutGenerator.hpp"
     
    271266      delete _osi_solver;
    272267    }
    273 #ifdef COIN_HAS_CLP
    274268    _osi_solver = new OsiClpSolverInterface();
    275 #elif COIN_HAS_OSL
    276     _osi_solver = new OsiOslSolverInterface();
    277 #else
    278 #error Cannot instantiate Osi solver
    279 #endif
    280269
    281270    _osi_solver->loadFromCoinModel(*_prob);
     
    329318      _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
    330319
    331 #ifdef COIN_HAS_CLP
    332320      OsiClpSolverInterface* osiclp =
    333321        dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver());
     
    335323        osiclp->setupForRepeatedUse(2, 0);
    336324      }
    337 #endif
    338325
    339326      CbcRounding heuristic1(*_cbc_model);
     
    449436
    450437    _prob = new CoinModel();
    451     rows.clear();
    452     cols.clear();
    453438  }
    454439
  • 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

    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).
     
    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.
     
    573574
    574575      Node act;
    575       Node bact=INVALID;
    576       Node last_activated=INVALID;
    577576      while((act=_level->highestActive())!=INVALID) {
    578577        int actlevel=(*_level)[act];
  • lemon/clp.cc

    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).
     
    438438    delete _prob;
    439439    _prob = new ClpSimplex();
    440     rows.clear();
    441     cols.clear();
    442440    _col_names_ref.clear();
    443441    _clear_temporals();
  • 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

    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).
     
    3636
    3737  template <class T> inline void ignore_unused_variable_warning(const T&) { }
     38  template <class T1, class T2>
     39  inline void ignore_unused_variable_warning(const T1&, const T2&) { }
     40  template <class T1, class T2, class T3>
     41  inline void ignore_unused_variable_warning(const T1&, const T2&,
     42                                             const T3&) { }
     43  template <class T1, class T2, class T3, class T4>
     44  inline void ignore_unused_variable_warning(const T1&, const T2&,
     45                                             const T3&, const T4&) { }
     46  template <class T1, class T2, class T3, class T4, class T5>
     47  inline void ignore_unused_variable_warning(const T1&, const T2&,
     48                                             const T3&, const T4&,
     49                                             const T5&) { }
     50  template <class T1, class T2, class T3, class T4, class T5, class T6>
     51  inline void ignore_unused_variable_warning(const T1&, const T2&,
     52                                             const T3&, const T4&,
     53                                             const T5&, const T6&) { }
    3854
    3955  ///\e
     
    4359#if !defined(NDEBUG)
    4460    void (Concept::*x)() = & Concept::constraints;
    45     ignore_unused_variable_warning(x);
     61    ::lemon::ignore_unused_variable_warning(x);
    4662#endif
    4763  }
     
    5369    typedef typename Concept::template Constraints<Type> ConceptCheck;
    5470    void (ConceptCheck::*x)() = & ConceptCheck::constraints;
    55     ignore_unused_variable_warning(x);
     71    ::lemon::ignore_unused_variable_warning(x);
    5672#endif
    5773  }
  • 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

    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).
     
    109109
    110110          bool b;
     111          ::lemon::ignore_unused_variable_warning(b);
     112
    111113          b = (ia == ib) && (ia != ib);
    112114          b = (ia == INVALID) && (ib != INVALID);
     
    116118        const _GraphItem &ia;
    117119        const _GraphItem &ib;
     120        Constraints() {}
    118121      };
    119122    };
     
    175178
    176179        const _Digraph& digraph;
     180        Constraints() {}
    177181      };
    178182    };
     
    286290            ue = e;
    287291            bool d = graph.direction(e);
    288             ignore_unused_variable_warning(d);
     292            ::lemon::ignore_unused_variable_warning(d);
    289293          }
    290294        }
    291295
    292296        const _Graph& graph;
     297      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;
    293464      };
    294465
     
    364535
    365536          nid = digraph.maxNodeId();
    366           ignore_unused_variable_warning(nid);
     537          ::lemon::ignore_unused_variable_warning(nid);
    367538          eid = digraph.maxArcId();
    368           ignore_unused_variable_warning(eid);
     539          ::lemon::ignore_unused_variable_warning(eid);
    369540        }
    370541
    371542        const _Digraph& digraph;
     543        Constraints() {}
    372544      };
    373545    };
     
    418590          edge = graph.edgeFromId(ueid);
    419591          ueid = graph.maxEdgeId();
    420           ignore_unused_variable_warning(ueid);
     592          ::lemon::ignore_unused_variable_warning(ueid);
    421593        }
    422594
    423595        const _Graph& graph;
     596        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;
    424661      };
    425662    };
     
    490727          _GraphItemIt it3 = it1;
    491728          _GraphItemIt it4 = INVALID;
     729          ::lemon::ignore_unused_variable_warning(it3);
     730          ::lemon::ignore_unused_variable_warning(it4);
    492731
    493732          it2 = ++it1;
     
    499738        }
    500739        const GR& g;
     740        Constraints() {}
    501741      };
    502742    };
     
    578818          _GraphIncIt it3 = it1;
    579819          _GraphIncIt it4 = INVALID;
     820          ::lemon::ignore_unused_variable_warning(it3);
     821          ::lemon::ignore_unused_variable_warning(it4);
    580822
    581823          it2 = ++it1;
     
    587829        const Base& node;
    588830        const GR& graph;
     831        Constraints() {}
    589832      };
    590833    };
     
    633876      void next(Arc&) const {}
    634877
    635       /// \brief Return the first arc incomming to the given node.
    636       ///
    637       /// 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
    638881      /// given node.
    639882      void firstIn(Arc&, const Node&) const {}
    640883
    641       /// \brief Return the next arc incomming to the given node.
    642       ///
    643       /// 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
    644887      /// given node.
    645888      void nextIn(Arc&) const {}
     
    7581001            n = digraph.baseNode(oait);
    7591002            n = digraph.runningNode(oait);
    760             ignore_unused_variable_warning(n);
     1003            ::lemon::ignore_unused_variable_warning(n);
    7611004          }
    7621005        }
    7631006
    7641007        const _Digraph& digraph;
     1008        Constraints() {}
    7651009      };
    7661010    };
     
    8871131
    8881132        const _Graph& graph;
     1133        Constraints() {}
     1134      };
     1135    };
     1136
     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;
    8891225      };
    8901226    };
     
    9151251      ArcNotifier;
    9161252
     1253      mutable NodeNotifier node_notifier;
     1254      mutable ArcNotifier arc_notifier;
     1255
    9171256      /// \brief Return the node alteration notifier.
    9181257      ///
    9191258      /// This function gives back the node alteration notifier.
    9201259      NodeNotifier& notifier(Node) const {
    921          return NodeNotifier();
     1260        return node_notifier;
    9221261      }
    9231262
     
    9261265      /// This function gives back the arc alteration notifier.
    9271266      ArcNotifier& notifier(Arc) const {
    928         return ArcNotifier();
     1267        return arc_notifier;
    9291268      }
    9301269
     
    9391278            = digraph.notifier(typename _Digraph::Arc());
    9401279
    941           ignore_unused_variable_warning(nn);
    942           ignore_unused_variable_warning(en);
     1280          ::lemon::ignore_unused_variable_warning(nn);
     1281          ::lemon::ignore_unused_variable_warning(en);
    9431282        }
    9441283
    9451284        const _Digraph& digraph;
     1285        Constraints() {}
    9461286      };
    9471287    };
     
    9611301
    9621302      typedef BAS Base;
     1303      typedef AlterableDigraphComponent<Base> Parent;
    9631304      typedef typename Base::Edge Edge;
    9641305
     
    9681309      EdgeNotifier;
    9691310
     1311      mutable EdgeNotifier edge_notifier;
     1312
     1313      using Parent::notifier;
     1314
    9701315      /// \brief Return the edge alteration notifier.
    9711316      ///
    9721317      /// This function gives back the edge alteration notifier.
    9731318      EdgeNotifier& notifier(Edge) const {
    974         return EdgeNotifier();
     1319        return edge_notifier;
    9751320      }
    9761321
     
    9811326          typename _Graph::EdgeNotifier& uen
    9821327            = graph.notifier(typename _Graph::Edge());
    983           ignore_unused_variable_warning(uen);
     1328          ::lemon::ignore_unused_variable_warning(uen);
    9841329        }
    9851330
    9861331        const _Graph& graph;
     1332        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;
    9871395      };
    9881396    };
     
    10541462          // m3 = cmap;
    10551463
    1056           ignore_unused_variable_warning(m1);
    1057           ignore_unused_variable_warning(m2);
    1058           // 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);
    10591467        }
    10601468
     
    10621470        const GR &g;
    10631471        const typename GraphMap::Value &t;
     1472        Constraints() {}
    10641473      };
    10651474
     
    12001609
    12011610        const _Digraph& digraph;
     1611        Constraints() {}
    12021612      };
    12031613    };
     
    12851695
    12861696        const _Graph& graph;
     1697        Constraints() {}
     1698      };
     1699    };
     1700
     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;
    12871842      };
    12881843    };
     
    13291884
    13301885        _Digraph& digraph;
     1886        Constraints() {}
    13311887      };
    13321888    };
     
    13731929
    13741930        _Graph& graph;
     1931        Constraints() {}
     1932      };
     1933    };
     1934
     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;
    13751991      };
    13761992    };
     
    14122028
    14132029        _Digraph& digraph;
     2030        Constraints() {}
    14142031      };
    14152032    };
     
    14512068
    14522069        _Graph& graph;
    1453       };
    1454     };
     2070        Constraints() {}
     2071      };
     2072    };
     2073
     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> {};
    14552082
    14562083    /// \brief Skeleton class for clearable directed graphs.
     
    14792106
    14802107        _Digraph& digraph;
     2108        Constraints() {}
    14812109      };
    14822110    };
     
    14892117    /// This concept requires \ref AlterableGraphComponent.
    14902118    template <typename BAS = BaseGraphComponent>
    1491     class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
    1492     public:
    1493 
    1494       typedef BAS Base;
    1495 
    1496       /// \brief Erase all nodes and edges from the graph.
    1497       ///
    1498       /// This function erases all nodes and edges from the graph.
    1499       void clear() {}
    1500 
    1501       template <typename _Graph>
    1502       struct Constraints {
    1503         void constraints() {
    1504           checkConcept<Base, _Graph>();
    1505           graph.clear();
    1506         }
    1507 
    1508         _Graph& graph;
    1509       };
    1510     };
     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> {};
    15112129
    15122130  }
  • lemon/concepts/heap.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).
     
    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();
     
    315315        _Heap& heap;
    316316        ItemIntMap& map;
     317        Constraints() {}
    317318      };
    318319    };
  • lemon/concepts/maps.h

    r765 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).
     
    5050      /// Returns the value associated with the given key.
    5151      Value operator[](const Key &) const {
    52         return *static_cast<Value *>(0);
     52        return *(static_cast<Value *>(0)+1);
    5353      }
    5454
     
    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;
    6969        const typename _ReadMap::Key& own_key;
    7070        const _ReadMap& m;
     71        Constraints() {}
    7172      };
    7273
     
    100101          m.set(own_key, own_val);
    101102
    102           ignore_unused_variable_warning(key);
    103           ignore_unused_variable_warning(val);
    104           ignore_unused_variable_warning(own_key);
    105           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);
    106107        }
    107108        const Key& key;
     
    110111        const typename _WriteMap::Value& own_val;
    111112        _WriteMap& m;
     113        Constraints() {}
    112114      };
    113115    };
     
    130132      /// Returns the value associated with the given key.
    131133      Value operator[](const Key &) const {
    132         return *static_cast<Value *>(0);
     134        Value *r = 0;
     135        return *r;
    133136      }
    134137
     
    170173      /// Returns a reference to the value associated with the given key.
    171174      Reference operator[](const Key &) {
    172         return *static_cast<Value *>(0);
     175        Value *r = 0;
     176        return *r;
    173177      }
    174178
    175179      /// Returns a const reference to the value associated with the given key.
    176180      ConstReference operator[](const Key &) const {
    177         return *static_cast<Value *>(0);
     181        Value *r = 0;
     182        return *r;
    178183      }
    179184
     
    206211        typename _ReferenceMap::ConstReference own_cref;
    207212        _ReferenceMap& m;
     213        Constraints() {}
    208214      };
    209215    };
  • lemon/concepts/path.h

    r832 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;
     171        PathDumperConstraints() {}
    171172      };
    172173
     
    188189          e = (i != INVALID);
    189190
    190           ignore_unused_variable_warning(l);
    191           ignore_unused_variable_warning(e);
    192           ignore_unused_variable_warning(id);
    193           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);
    194195        }
    195196        _Path& p;
     197        PathDumperConstraints() {}
    196198      };
    197199
  • lemon/config.h.in

    r725 r1306  
    1 /* The version string */
    2 #undef LEMON_VERSION
     1#define LEMON_VERSION "@PROJECT_VERSION@"
     2#cmakedefine LEMON_HAVE_LONG_LONG 1
    33
    4 /* Define to 1 if you have long long */
    5 #undef LEMON_HAVE_LONG_LONG
     4#cmakedefine LEMON_HAVE_LP 1
     5#cmakedefine LEMON_HAVE_MIP 1
     6#cmakedefine LEMON_HAVE_GLPK 1
     7#cmakedefine LEMON_HAVE_CPLEX 1
     8#cmakedefine LEMON_HAVE_SOPLEX 1
     9#cmakedefine LEMON_HAVE_CLP 1
     10#cmakedefine LEMON_HAVE_CBC 1
    611
    7 /* Define to 1 if you have any LP solver. */
    8 #undef LEMON_HAVE_LP
     12#define _LEMON_CPLEX 1
     13#define _LEMON_CLP 2
     14#define _LEMON_GLPK 3
     15#define _LEMON_SOPLEX 4
     16#define _LEMON_CBC 5
    917
    10 /* Define to 1 if you have any MIP solver. */
    11 #undef LEMON_HAVE_MIP
     18#cmakedefine LEMON_DEFAULT_LP _LEMON_@LEMON_DEFAULT_LP@
     19#cmakedefine LEMON_DEFAULT_MIP _LEMON_@LEMON_DEFAULT_MIP@
    1220
    13 /* Define to 1 if you have CPLEX. */
    14 #undef LEMON_HAVE_CPLEX
    15 
    16 /* Define to 1 if you have GLPK. */
    17 #undef LEMON_HAVE_GLPK
    18 
    19 /* Define to 1 if you have SOPLEX */
    20 #undef LEMON_HAVE_SOPLEX
    21 
    22 /* Define to 1 if you have CLP */
    23 #undef LEMON_HAVE_CLP
    24 
    25 /* Define to 1 if you have CBC */
    26 #undef LEMON_HAVE_CBC
     21#cmakedefine LEMON_USE_PTHREAD 1
     22#cmakedefine LEMON_USE_WIN32_THREADS 1
  • 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

    r988 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).
     
    3636#ifdef _MSC_VER
    3737#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
     39
     40#ifdef __GNUC__
     41#define GCC_VERSION (__GNUC__ * 10000                   \
     42                     + __GNUC_MINOR__ * 100             \
     43                     + __GNUC_PATCHLEVEL__)
     44#endif
     45
     46#if GCC_VERSION >= 40800
     47// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
     48#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
    3849#endif
    3950
     
    149160  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    150161
     162  ///Create convenience typedefs for the bipartite graph types and iterators
     163
     164  ///This \c \#define creates the same convenient type definitions as
     165  ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it
     166  ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap,
     167  ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt,
     168  ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap.
     169  ///
     170  ///\note If the graph type is a dependent type, ie. the graph type depend
     171  ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS()
     172  ///macro.
     173#define BPGRAPH_TYPEDEFS(BpGraph)                                       \
     174  GRAPH_TYPEDEFS(BpGraph);                                              \
     175  typedef BpGraph::RedNode RedNode;                                     \
     176  typedef BpGraph::RedNodeIt RedNodeIt;                                 \
     177  typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap;                     \
     178  typedef BpGraph::RedNodeMap<int> IntRedNodeMap;                       \
     179  typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap;                 \
     180  typedef BpGraph::BlueNode BlueNode;                                   \
     181  typedef BpGraph::BlueNodeIt BlueNodeIt;                               \
     182  typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap;                   \
     183  typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap;                     \
     184  typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap
     185