COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
41 added
26 deleted
141 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r610 r944  
    2323lemon/stamp-h2
    2424doc/Doxyfile
     25doc/references.dox
    2526cmake/version.cmake
    2627.dirstamp

  • 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 r1346  
    1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
     2
     3IF(POLICY CMP0048)
     4  CMAKE_POLICY(SET CMP0048 OLD)
     5ENDIF(POLICY CMP0048)
     6
     7IF(POLICY CMP0043)
     8  CMAKE_POLICY(SET CMP0043 OLD)
     9ENDIF(POLICY CMP0043)
     10
     11IF(POLICY CMP0026)
     12  #This is for copying the dll's needed by glpk (in lp_test and mip_test)
     13  CMAKE_POLICY(SET CMP0026 OLD)
     14ENDIF(POLICY CMP0026)
    215
    316SET(PROJECT_NAME "LEMON")
    417PROJECT(${PROJECT_NAME})
     18
     19INCLUDE(FindPythonInterp)
     20INCLUDE(FindWget)
    521
    622IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    … …  
    1026ELSE()
    1127  EXECUTE_PROCESS(
    12     COMMAND hg id -i
     28    COMMAND
     29    hg log -r. --template "{latesttag}"
    1330    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    14     OUTPUT_VARIABLE HG_REVISION
     31    OUTPUT_VARIABLE HG_REVISION_TAG
    1532    ERROR_QUIET
    1633    OUTPUT_STRIP_TRAILING_WHITESPACE
    1734  )
    18   IF(HG_REVISION STREQUAL "")
    19     SET(HG_REVISION "hg-tip")
     35  EXECUTE_PROCESS(
     36    COMMAND
     37    hg log -r. --template "{latesttagdistance}"
     38    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     39    OUTPUT_VARIABLE HG_REVISION_DIST
     40    ERROR_QUIET
     41    OUTPUT_STRIP_TRAILING_WHITESPACE
     42  )
     43  EXECUTE_PROCESS(
     44    COMMAND
     45    hg log -r. --template "{node|short}"
     46    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     47    OUTPUT_VARIABLE HG_REVISION_ID
     48    ERROR_QUIET
     49    OUTPUT_STRIP_TRAILING_WHITESPACE
     50  )
     51
     52  IF(HG_REVISION_TAG STREQUAL "")
     53    SET(HG_REVISION_ID "hg-tip")
     54  ELSE()
     55    IF(HG_REVISION_TAG STREQUAL "null")
     56      SET(HG_REVISION_TAG "trunk")
     57    ELSEIF(HG_REVISION_TAG MATCHES "^r")
     58      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
     59    ENDIF()
     60    IF(HG_REVISION_DIST STREQUAL "0")
     61      SET(HG_REVISION ${HG_REVISION_TAG})
     62    ELSE()
     63      SET(HG_REVISION
     64        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
     65    ENDIF()
    2066  ENDIF()
     67
    2168  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
    2269ENDIF()
    … …  
    2875FIND_PACKAGE(Doxygen)
    2976FIND_PACKAGE(Ghostscript)
    30 FIND_PACKAGE(GLPK 4.33)
    31 FIND_PACKAGE(CPLEX)
    32 FIND_PACKAGE(COIN)
     77
     78IF(WIN32)
     79  SET(LEMON_WIN32 TRUE)
     80ENDIF(WIN32)
     81
     82SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     83SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     84SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     85SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
     86
     87IF(LEMON_ENABLE_GLPK)
     88  FIND_PACKAGE(GLPK 4.33)
     89ENDIF(LEMON_ENABLE_GLPK)
     90IF(LEMON_ENABLE_ILOG)
     91  FIND_PACKAGE(ILOG)
     92ENDIF(LEMON_ENABLE_ILOG)
     93IF(LEMON_ENABLE_COIN)
     94  FIND_PACKAGE(COIN)
     95ENDIF(LEMON_ENABLE_COIN)
     96IF(LEMON_ENABLE_SOPLEX)
     97  FIND_PACKAGE(SOPLEX)
     98ENDIF(LEMON_ENABLE_SOPLEX)
     99
     100IF(GLPK_FOUND)
     101  SET(LEMON_HAVE_LP TRUE)
     102  SET(LEMON_HAVE_MIP TRUE)
     103  SET(LEMON_HAVE_GLPK TRUE)
     104ENDIF(GLPK_FOUND)
     105IF(ILOG_FOUND)
     106  SET(LEMON_HAVE_LP TRUE)
     107  SET(LEMON_HAVE_MIP TRUE)
     108  SET(LEMON_HAVE_CPLEX TRUE)
     109ENDIF(ILOG_FOUND)
     110IF(COIN_FOUND)
     111  SET(LEMON_HAVE_LP TRUE)
     112  SET(LEMON_HAVE_MIP TRUE)
     113  SET(LEMON_HAVE_CLP TRUE)
     114  SET(LEMON_HAVE_CBC TRUE)
     115ENDIF(COIN_FOUND)
     116IF(SOPLEX_FOUND)
     117  SET(LEMON_HAVE_LP TRUE)
     118  SET(LEMON_HAVE_SOPLEX TRUE)
     119ENDIF(SOPLEX_FOUND)
     120
     121IF(ILOG_FOUND)
     122  SET(DEFAULT_LP "CPLEX")
     123  SET(DEFAULT_MIP "CPLEX")
     124ELSEIF(COIN_FOUND)
     125  SET(DEFAULT_LP "CLP")
     126  SET(DEFAULT_MIP "CBC")
     127ELSEIF(GLPK_FOUND)
     128  SET(DEFAULT_LP "GLPK")
     129  SET(DEFAULT_MIP "GLPK")
     130ELSEIF(SOPLEX_FOUND)
     131  SET(DEFAULT_LP "SOPLEX")
     132ENDIF()
     133
     134IF(NOT LEMON_DEFAULT_LP OR
     135    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     136    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     137    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
     138    (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
     139  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     140    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     141ELSE()
     142  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     143    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
     144ENDIF()
     145IF(NOT LEMON_DEFAULT_MIP OR
     146    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     147    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     148    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     149  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     150    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     151ELSE()
     152  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     153    "Default MIP solver backend (GLPK, CPLEX or CBC)")
     154ENDIF()
     155
     156
     157IF(DEFINED ENV{LEMON_CXX_WARNING})
     158  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     159ELSE()
     160  IF(CMAKE_COMPILER_IS_GNUCXX)
     161    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")
     162    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     163    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     164  ELSEIF(MSVC)
     165    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     166    # Still kept as an example.
     167
     168    # SET(CXX_WARNING "/wd4250 /wd4267 /wd4355 /wd4503 /wd4800 /wd4996")
     169
     170    # Suppressed warnings:
     171    # C4250: 'class1' : inherits 'class2::member' via dominance
     172    # C4267: conversion from 'size_t' to 'type', possible loss of data
     173    # C4355: 'this' : used in base member initializer list
     174    # C4503: 'function' : decorated name length exceeded, name was truncated
     175    # C4800: 'type' : forcing value to bool 'true' or 'false'
     176    #        (performance warning)
     177    # C4996: 'function': was declared deprecated
     178  ELSE()
     179    SET(CXX_WARNING "-Wall")
     180  ENDIF()
     181ENDIF()
     182SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     183
     184SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     185
     186IF(MSVC)
     187  SET(CMAKE_CXX_FLAGS "/bigobj ${CMAKE_CXX_FLAGS}")
     188  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     189    "Flags used by the C++ compiler during maintainer builds."
     190    )
     191  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     192    "Flags used by the C compiler during maintainer builds."
     193    )
     194  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     195    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     196    "Flags used for linking binaries during maintainer builds."
     197    )
     198  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     199    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     200    "Flags used by the shared libraries linker during maintainer builds."
     201    )
     202ELSE()
     203  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     204    "Flags used by the C++ compiler during maintainer builds."
     205    )
     206  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     207    "Flags used by the C compiler during maintainer builds."
     208    )
     209  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     210    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     211    "Flags used for linking binaries during maintainer builds."
     212    )
     213  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     214    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     215    "Flags used by the shared libraries linker during maintainer builds."
     216    )
     217ENDIF()
     218
     219MARK_AS_ADVANCED(
     220    CMAKE_CXX_FLAGS_MAINTAINER
     221    CMAKE_C_FLAGS_MAINTAINER
     222    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     223    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     224
     225IF(CMAKE_CONFIGURATION_TYPES)
     226  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     227  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     228  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     229      "Add the configurations that we need"
     230      FORCE)
     231 endif()
     232
     233IF(NOT CMAKE_BUILD_TYPE)
     234  SET(CMAKE_BUILD_TYPE "Release")
     235ENDIF()
     236
     237SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     238    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     239    FORCE )
     240
     241SET_DIRECTORY_PROPERTIES(PROPERTIES
     242  COMPILE_DEFINITIONS_DEBUG "LEMON_ENABLE_DEBUG"
     243  COMPILE_DEFINITIONS_MAINTAINER "LEMON_ENABLE_DEBUG"
     244)
    33245
    34246INCLUDE(CheckTypeSize)
    … …  
    36248SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    37249
    38 INCLUDE(FindPythonInterp)
     250INCLUDE(FindThreads)
     251
     252IF(NOT LEMON_THREADING)
     253  IF(CMAKE_USE_PTHREADS_INIT)
     254    SET(LEMON_THREADING "Pthread")
     255  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     256    SET(LEMON_THREADING "Win32")
     257  ELSE()
     258    SET(LEMON_THREADING "None")
     259  ENDIF()
     260ENDIF()
     261
     262SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     263  "Choose the threading library, options are: Pthread Win32 None."
     264  FORCE )
     265
     266IF(LEMON_THREADING STREQUAL "Pthread")
     267  SET(LEMON_USE_PTHREAD TRUE)
     268ELSEIF(LEMON_THREADING STREQUAL "Win32")
     269  SET(LEMON_USE_WIN32_THREADS TRUE)
     270ENDIF()
    39271
    40272ENABLE_TESTING()
     273
     274
     275INCLUDE(CheckCXXCompilerFlag)
     276CHECK_CXX_COMPILER_FLAG("-std=c++11" LEMON_CXX11)
     277IF(LEMON_CXX11)
     278  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
     279ENDIF()
     280
     281
     282IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     283  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     284ELSE()
     285  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     286ENDIF()
    41287
    42288ADD_SUBDIRECTORY(lemon)
    43289IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     290  ADD_SUBDIRECTORY(contrib)
    44291  ADD_SUBDIRECTORY(demo)
    45292  ADD_SUBDIRECTORY(tools)
    … …  
    65312ENDIF()
    66313
    67 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     314CONFIGURE_FILE(
     315  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     316  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     317  @ONLY
     318)
     319
     320SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     321STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     322SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     323ADD_CUSTOM_TARGET(dist
     324  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     325  COMMAND hg archive ${ARCHIVE_NAME}
     326  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     327  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     328  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     329  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     330  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     331  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     332  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     333  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     334  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     335  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     336  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     337  DEPENDS html
     338  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     339
     340# CPACK config (Basically for NSIS)
     341IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    68342  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    69343  SET(CPACK_PACKAGE_VENDOR "EGRES")

  • INSTALL

    r615 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.
     159  Root directory prefixes of optional third party libraries.
    153160
    154 --with-coin[=PREFIX]
     161Makefile Variables
     162==================
    155163
    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.
     164make VERBOSE=1
    160165
    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.
     166   This results in a more verbose output by showing the full
     167   compiler and linker commands.

  • LICENSE

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

  • NEWS

    r712 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
     992010-03-19 Version 1.2 released
     100
     101        This is major feature release
     102
     103        * New algorithms
     104          * Bellman-Ford algorithm (#51)
     105          * Minimum mean cycle algorithms (#179)
     106            * Karp, Hartman-Orlin and Howard algorithms
     107          * New minimum cost flow algorithms (#180)
     108            * Cost Scaling algorithms
     109            * Capacity Scaling algorithm
     110            * Cycle-Canceling algorithms
     111          * Planarity related algorithms (#62)
     112            * Planarity checking algorithm
     113            * Planar embedding algorithm
     114            * Schnyder's planar drawing algorithm
     115            * Coloring planar graphs with five or six colors
     116          * Fractional matching algorithms (#314)
     117        * New data structures
     118          * StaticDigraph structure (#68)
     119          * Several new priority queue structures (#50, #301)
     120            * Fibonacci, Radix, Bucket, Pairing, Binomial
     121              D-ary and fourary heaps (#301)
     122          * Iterable map structures (#73)
     123        * Other new tools and functionality
     124          * Map utility functions (#320)
     125          * Reserve functions are added to ListGraph and SmartGraph (#311)
     126          * A resize() function is added to HypercubeGraph (#311)
     127          * A count() function is added to CrossRefMap (#302)
     128          * Support for multiple targets in Suurballe using fullInit() (#181)
     129          * Traits class and named parameters for Suurballe (#323)
     130          * Separate reset() and resetParams() functions in NetworkSimplex
     131            to handle graph changes (#327)
     132          * tolerance() functions are added to HaoOrlin (#306)
     133        * Implementation improvements
     134          * Improvements in weighted matching algorithms (#314)
     135            * Jumpstart initialization
     136          * ArcIt iteration is based on out-arc lists instead of in-arc lists
     137            in ListDigraph (#311)
     138          * Faster add row operation in CbcMip (#203)
     139          * Better implementation for split() in ListDigraph (#311)
     140          * ArgParser can also throw exception instead of exit(1) (#332)
     141        * Miscellaneous
     142          * A simple interactive bootstrap script
     143          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
     144                #316,#319)
     145            * BibTeX references in the doc (#184)
     146          * Optionally use valgrind when running tests
     147          * Also check ReferenceMapTag in concept checks (#312)
     148          * dimacs-solver uses long long type by default.
     149        * Several bugfixes (compared to release 1.1):
     150          #295: Suppress MSVC warnings using pragmas
     151          ----: Various CMAKE related improvements
     152                * Remove duplications from doc/CMakeLists.txt
     153                * Rename documentation install folder from 'docs' to 'html'
     154                * Add tools/CMakeLists.txt to the tarball
     155                * Generate and install LEMONConfig.cmake
     156                * Change the label of the html project in Visual Studio
     157                * Fix the check for the 'long long' type
     158                * Put the version string into config.h
     159                * Minor CMake improvements
     160                * Set the version to 'hg-tip' if everything fails
     161          #311: Add missing 'explicit' keywords
     162          #302: Fix the implementation and doc of CrossRefMap
     163          #308: Remove duplicate list_graph.h entry from source list
     164          #307: Bugfix in Preflow and Circulation
     165          #305: Bugfix and extension in the rename script
     166          #312: Also check ReferenceMapTag in concept checks
     167          #250: Bugfix in pathSource() and pathTarget()
     168          #321: Use pathCopy(from,to) instead of copyPath(to,from)
     169          #322: Distribure LEMONConfig.cmake.in
     170          #330: Bug fix in map_extender.h
     171          #336: Fix the date field comment of graphToEps() output
     172          #323: Bug fix in Suurballe
     173          #335: Fix clear() function in ExtendFindEnum
     174          #337: Use void* as the LPX object pointer
     175          #317: Fix (and improve) error message in mip_test.cc
     176                Remove unnecessary OsiCbc dependency
     177          #356: Allow multiple executions of weighted matching algorithms (#356)
     178
    11792009-05-13 Version 1.1 released
    2180
    … …  
    73251          ----: Add missing unistd.h include to time_measure.h
    74252          #204: Compilation bug fixed in graph_to_eps.h with VS2005
    75           #214,#215: windows.h should never be included by lemon headers
     253          #214,#215: windows.h should never be included by LEMON headers
    76254          #230: Build systems check the availability of 'long long' type
    77255          #229: Default implementation of Tolerance<> is used for integer types
    … …  
    952732008-10-13 Version 1.0 released
    96274
    97         This is the first stable release of LEMON. Compared to the 0.x
    98         release series, it features a considerably smaller but more
    99         matured set of tools. The API has also completely revised and
    100         changed in several places.
    101 
    102         * The major name changes compared to the 0.x series (see the
     275        This is the first stable release of LEMON. Compared to the 0.x
     276        release series, it features a considerably smaller but more
     277        matured set of tools. The API has also completely revised and
     278        changed in several places.
     279
     280        * The major name changes compared to the 0.x series (see the
    103281          Migration Guide in the doc for more details)
    104282          * Graph -> Digraph, UGraph -> Graph
    105283          * Edge -> Arc, UEdge -> Edge
    106           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
    107         * Other improvements
    108           * Better documentation
    109           * Reviewed and cleaned up codebase
    110           * CMake based build system (along with the autotools based one)
    111         * Contents of the library (ported from 0.x)
    112           * Algorithms
    113             * breadth-first search (bfs.h)
    114             * depth-first search (dfs.h)
    115             * Dijkstra's algorithm (dijkstra.h)
    116             * Kruskal's algorithm (kruskal.h)
    117           * Data structures
    118             * graph data structures (list_graph.h, smart_graph.h)
    119             * path data structures (path.h)
    120             * binary heap data structure (bin_heap.h)
    121             * union-find data structures (unionfind.h)
    122             * miscellaneous property maps (maps.h)
    123             * two dimensional vector and bounding box (dim2.h)
     284          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     285        * Other improvements
     286          * Better documentation
     287          * Reviewed and cleaned up codebase
     288          * CMake based build system (along with the autotools based one)
     289        * Contents of the library (ported from 0.x)
     290          * Algorithms
     291            * breadth-first search (bfs.h)
     292            * depth-first search (dfs.h)
     293            * Dijkstra's algorithm (dijkstra.h)
     294            * Kruskal's algorithm (kruskal.h)
     295          * Data structures
     296            * graph data structures (list_graph.h, smart_graph.h)
     297            * path data structures (path.h)
     298            * binary heap data structure (bin_heap.h)
     299            * union-find data structures (unionfind.h)
     300            * miscellaneous property maps (maps.h)
     301            * two dimensional vector and bounding box (dim2.h)
    124302          * Concepts
    125             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     303            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    126304              concepts/graph_components.h)
    127             * concepts for other structures (concepts/heap.h, concepts/maps.h,
    128               concepts/path.h)
    129           * Tools
    130             * Mersenne twister random number generator (random.h)
    131             * tools for measuring cpu and wall clock time (time_measure.h)
    132             * tools for counting steps and events (counter.h)
    133             * tool for parsing command line arguments (arg_parser.h)
    134             * tool for visualizing graphs (graph_to_eps.h)
    135             * tools for reading and writing data in LEMON Graph Format
     305            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     306              concepts/path.h)
     307          * Tools
     308            * Mersenne twister random number generator (random.h)
     309            * tools for measuring cpu and wall clock time (time_measure.h)
     310            * tools for counting steps and events (counter.h)
     311            * tool for parsing command line arguments (arg_parser.h)
     312            * tool for visualizing graphs (graph_to_eps.h)
     313            * tools for reading and writing data in LEMON Graph Format
    136314              (lgf_reader.h, lgf_writer.h)
    137315            * tools to handle the anomalies of calculations with
    138               floating point numbers (tolerance.h)
     316              floating point numbers (tolerance.h)
    139317            * tools to manage RGB colors (color.h)
    140           * Infrastructure
    141             * extended assertion handling (assert.h)
    142             * exception classes and error handling (error.h)
    143             * concept checking (concept_check.h)
    144             * commonly used mathematical constants (math.h)
     318          * Infrastructure
     319            * extended assertion handling (assert.h)
     320            * exception classes and error handling (error.h)
     321            * concept checking (concept_check.h)
     322            * commonly used mathematical constants (math.h)

  • README

    r705 r921  
    1818   Copying, distribution and modification conditions and terms.
    1919
     20NEWS
     21
     22   News and version history.
     23
    2024INSTALL
    2125
    … …  
    3438   Some example programs to make you easier to get familiar with LEMON.
    3539
     40scripts/
     41
     42   Scripts that make it easier to develop LEMON.
     43
    3644test/
    3745

  • 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.")

  • demo/arg_parser_demo.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6666    .other("...");
    6767
     68  // Throw an exception when problems occurs. The default behavior is to
     69  // exit(1) on these cases, but this makes Valgrind falsely warn
     70  // about memory leaks.
     71  ap.throwOnProblems();
     72
    6873  // Perform the parsing process
    6974  // (in case of any error it terminates the program)
    70   ap.parse();
     75  // The try {} construct is necessary only if the ap.trowOnProblems()
     76  // setting is in use.
     77  try {
     78    ap.parse();
     79  } catch (ArgParserException &) { return 1; }
    7180
    7281  // Check each option if it has been given and print its value

  • doc/CMakeLists.txt

    r791 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/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    24     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    25     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    26     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    27     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    28     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    29     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
    3058    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    31     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    3259    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3360    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    … …  
    5178
    5279ENDIF()
     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 r1354  
    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
    … …  
    1820STRIP_FROM_PATH        = "@abs_top_srcdir@"
    1921STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
    20 SHORT_NAMES            = YES
     22SHORT_NAMES            = NO
    2123JAVADOC_AUTOBRIEF      = NO
    2224QT_AUTOBRIEF           = NO
    … …  
    3032OPTIMIZE_FOR_FORTRAN   = NO
    3133OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3235BUILTIN_STL_SUPPORT    = YES
    3336CPP_CLI_SUPPORT        = NO
    … …  
    3740SUBGROUPING            = YES
    3841TYPEDEF_HIDES_STRUCT   = NO
    39 SYMBOL_CACHE_SIZE      = 0
    4042#---------------------------------------------------------------------------
    4143# Build related configuration options
    … …  
    5557HIDE_SCOPE_NAMES       = YES
    5658SHOW_INCLUDE_FILES     = YES
     59FORCE_LOCAL_INCLUDES   = NO
    5760INLINE_INFO            = YES
    5861SORT_MEMBER_DOCS       = NO
    5962SORT_BRIEF_DOCS        = NO
     63SORT_MEMBERS_CTORS_1ST = NO
    6064SORT_GROUP_NAMES       = NO
    6165SORT_BY_SCOPE_NAME     = NO
     66STRICT_PROTO_MATCHING  = NO
    6267GENERATE_TODOLIST      = YES
    6368GENERATE_TESTLIST      = YES
    … …  
    6772MAX_INITIALIZER_LINES  = 5
    6873SHOW_USED_FILES        = NO
    69 SHOW_DIRECTORIES       = YES
    7074SHOW_FILES             = YES
    7175SHOW_NAMESPACES        = YES
    7276FILE_VERSION_FILTER    =
    73 LAYOUT_FILE            = DoxygenLayout.xml
     77LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     78CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    7479#---------------------------------------------------------------------------
    7580# configuration options related to warning and progress messages
    … …  
    9095                         "@abs_top_srcdir@/lemon/concepts" \
    9196                         "@abs_top_srcdir@/demo" \
     97                         "@abs_top_srcdir@/contrib" \
    9298                         "@abs_top_srcdir@/tools" \
    9399                         "@abs_top_srcdir@/test/test_tools.h" \
    94                          "@abs_top_builddir@/doc/references.dox"
     100                         "@abs_top_builddir@/doc/mainpage.dox"
    95101INPUT_ENCODING         = UTF-8
    96102FILE_PATTERNS          = *.h \
    … …  
    112118FILTER_PATTERNS        =
    113119FILTER_SOURCE_FILES    = NO
     120FILTER_SOURCE_PATTERNS =
    114121#---------------------------------------------------------------------------
    115122# configuration options related to source browsing
    116123#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     124SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118125INLINE_SOURCES         = NO
    119126STRIP_CODE_COMMENTS    = YES
    … …  
    138145HTML_FOOTER            =
    139146HTML_STYLESHEET        =
    140 HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     147HTML_COLORSTYLE_HUE    = 220
     148HTML_COLORSTYLE_SAT    = 100
     149HTML_COLORSTYLE_GAMMA  = 80
     150HTML_TIMESTAMP         = YES
     151HTML_DYNAMIC_SECTIONS  = YES
    142152GENERATE_DOCSET        = NO
    143153DOCSET_FEEDNAME        = "Doxygen generated docs"
    144154DOCSET_BUNDLE_ID       = org.doxygen.Project
     155DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     156DOCSET_PUBLISHER_NAME  = Publisher
    145157GENERATE_HTMLHELP      = NO
    146158CHM_FILE               =
    … …  
    154166QHP_NAMESPACE          = org.doxygen.Project
    155167QHP_VIRTUAL_FOLDER     = doc
     168QHP_CUST_FILTER_NAME   =
     169QHP_CUST_FILTER_ATTRS  =
     170QHP_SECT_FILTER_ATTRS  =
    156171QHG_LOCATION           =
     172GENERATE_ECLIPSEHELP   = NO
     173ECLIPSE_DOC_ID         = org.doxygen.Project
    157174DISABLE_INDEX          = NO
    158175ENUM_VALUES_PER_LINE   = 4
    159176GENERATE_TREEVIEW      = NO
    160177TREEVIEW_WIDTH         = 250
     178EXT_LINKS_IN_WINDOW    = NO
    161179FORMULA_FONTSIZE       = 10
     180FORMULA_TRANSPARENT    = YES
     181USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
     182MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
     183SEARCHENGINE           = YES
     184SERVER_BASED_SEARCH    = NO
    162185#---------------------------------------------------------------------------
    163186# configuration options related to the LaTeX output
    … …  
    176199LATEX_BATCHMODE        = NO
    177200LATEX_HIDE_INDICES     = NO
     201LATEX_SOURCE_CODE      = NO
    178202#---------------------------------------------------------------------------
    179203# configuration options related to the RTF output
    … …  
    197221GENERATE_XML           = NO
    198222XML_OUTPUT             = xml
    199 XML_SCHEMA             =
    200 XML_DTD                =
    201223XML_PROGRAMLISTING     = YES
    202224#---------------------------------------------------------------------------
    … …  
    224246SKIP_FUNCTION_MACROS   = YES
    225247#---------------------------------------------------------------------------
    226 # Options related to the search engine   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     248# Configuration::additions related to external references
     249#---------------------------------------------------------------------------
     250TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
    229251GENERATE_TAGFILE       = html/lemon.tag
    230252ALLEXTERNALS           = NO
    … …  
    238260HIDE_UNDOC_RELATIONS   = YES
    239261HAVE_DOT               = YES
    240 DOT_FONTNAME           = FreeSans
     262DOT_NUM_THREADS        = 0
     263DOT_FONTNAME           =
    241264DOT_FONTSIZE           = 10
    242265DOT_FONTPATH           =
    … …  
    255278DOT_PATH               =
    256279DOTFILE_DIRS           =
     280MSCFILE_DIRS           =
    257281DOT_GRAPH_MAX_NODES    = 50
    258282MAX_DOT_GRAPH_DEPTH    = 0
    … …  
    261285GENERATE_LEGEND        = YES
    262286DOT_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

    r879 r1366  
    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).
    … …  
    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
    … …  
    264272
    265273/**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
    271 */
    272 
    273 /**
    274274@defgroup auxdat Auxiliary Data Structures
    275275@ingroup datas
    … …  
    318318This group contains the common graph search algorithms, namely
    319319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    320 \ref clrs01algorithms.
     320\cite clrs01algorithms.
    321321*/
    322322
    … …  
    327327
    328328This group contains the algorithms for finding shortest paths in digraphs
    329 \ref clrs01algorithms.
     329\cite clrs01algorithms.
    330330
    331331 - \ref Dijkstra algorithm for finding shortest paths from a source node
    … …  
    349349
    350350This group contains the algorithms for finding minimum cost spanning
    351 trees and arborescences \ref clrs01algorithms.
     351trees and arborescences \cite clrs01algorithms.
    352352*/
    353353
    … …  
    358358
    359359This group contains the algorithms for finding maximum flows and
    360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    361361
    362362The \e maximum \e flow \e problem is to find a flow of maximum value between
    … …  
    374374LEMON contains several algorithms for solving maximum flow problems:
    375375- \ref EdmondsKarp Edmonds-Karp algorithm
    376   \ref edmondskarp72theoretical.
     376  \cite edmondskarp72theoretical.
    377377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    378   \ref goldberg88newapproach.
     378  \cite goldberg88newapproach.
    379379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    380   \ref dinic70algorithm, \ref sleator83dynamic.
     380  \cite dinic70algorithm, \cite sleator83dynamic.
    381381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    382   \ref goldberg88newapproach, \ref sleator83dynamic.
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
    383383
    384384In most cases the \ref Preflow algorithm provides the
    … …  
    387387problem of maximum flow.
    388388
    389 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
    390390for finding feasible circulations, which is a somewhat different problem,
    391391but it is strongly related to maximum flow.
    … …  
    400400
    401401This group contains the algorithms for finding minimum cost flows and
    402 circulations \ref amo93networkflows. For more information about this
    403 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
    404404"Minimum Cost Flow Problem".
    405405
    406406LEMON contains several algorithms for this problem.
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    409409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    410    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    411    \ref bunnagel98efficient.
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
    412412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    413    shortest path method \ref edmondskarp72theoretical.
     413   shortest path method \cite edmondskarp72theoretical.
    414414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    415    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    416 
    417 In general NetworkSimplex is the most efficient implementation,
    418 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.
    419424For example, if the total supply and/or capacities are rather small,
    420 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.
    421437*/
    422438
    … …  
    457473
    458474This group contains the algorithms for finding minimum mean cycles
    459 \ref clrs01algorithms, \ref amo93networkflows.
     475\cite amo93networkflows, \cite karp78characterization.
    460476
    461477The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    … …  
    473489
    474490LEMON contains three algorithms for solving the minimum mean cycle problem:
    475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
    476   \ref dasdan98minmeancycle.
    477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
    478   version of Karp's algorithm \ref dasdan98minmeancycle.
    479 - \ref Howard "Howard"'s policy iteration algorithm
    480   \ref dasdan98minmeancycle.
    481 
    482 In practice, the Howard algorithm proved to be by far the most efficient
    483 one, though the best known theoretical bound on its running time is
    484 exponential.
    485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    487 applied early termination scheme.
     491- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
     492- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     493  version of Karp's algorithm \cite hartmann93finding.
     494- \ref HowardMmc Howard's policy iteration algorithm
     495  \cite dasdan98minmeancycle, \cite dasdan04experimental.
     496
     497In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     498most efficient one, though the best known theoretical bound on its running
     499time is exponential.
     500Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     501run in time O(nm) and use space O(n<sup>2</sup>+m).
    488502*/
    489503
    … …  
    523537  Edmond's blossom shrinking algorithm for calculating maximum weighted
    524538  perfect matching in general graphs.
    525 
    526 \image html bipartite_matching.png
    527 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
     539- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     540  maximum cardinality fractional matching in general graphs.
     541- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     542  maximum weighted fractional matching in general graphs.
     543- \ref MaxWeightedPerfectFractionalMatching
     544  Augmenting path algorithm for calculating maximum weighted
     545  perfect fractional matching in general graphs.
     546
     547\image html matching.png
     548\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
    528549*/
    529550
    … …  
    541562
    542563/**
    543 @defgroup planar Planarity Embedding and Drawing
     564@defgroup graph_isomorphism Graph Isomorphism
     565@ingroup algs
     566\brief Algorithms for testing (sub)graph isomorphism
     567
     568This group contains algorithms for finding isomorph copies of a
     569given graph in another one, or simply check whether two graphs are isomorphic.
     570
     571The formal definition of subgraph isomorphism is as follows.
     572
     573We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
     574function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
     575embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
     576
     577The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
     578mapping with the property that whenever \f$(u,v)\in E_1\f$, then
     579\f$(f(u),f(v))\in E_2\f$.
     580
     581In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
     582also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
     583E_2\f$
     584
     585In addition, the graph nodes may be \e labeled, i.e. we are given two
     586node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
     587L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
     588G_1\f$.
     589
     590*/
     591
     592/**
     593@defgroup planar Planar Embedding and Drawing
    544594@ingroup algs
    545595\brief Algorithms for planarity checking, embedding and drawing
    … …  
    553603
    554604/**
    555 @defgroup approx Approximation Algorithms
     605@defgroup tsp Traveling Salesman Problem
     606@ingroup algs
     607\brief Algorithms for the symmetric traveling salesman problem
     608
     609This group contains basic heuristic algorithms for the the symmetric
     610\e traveling \e salesman \e problem (TSP).
     611Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     612the problem is to find a shortest possible tour that visits each node exactly
     613once (i.e. the minimum cost Hamiltonian cycle).
     614
     615These TSP algorithms are intended to be used with a \e metric \e cost
     616\e function, i.e. the edge costs should satisfy the triangle inequality.
     617Otherwise the algorithms could yield worse results.
     618
     619LEMON provides five well-known heuristics for solving symmetric TSP:
     620 - \ref NearestNeighborTsp Neareast neighbor algorithm
     621 - \ref GreedyTsp Greedy algorithm
     622 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     623 - \ref ChristofidesTsp Christofides algorithm
     624 - \ref Opt2Tsp 2-opt algorithm
     625
     626\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     627solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     628
     629\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     630approximation factor: 3/2.
     631
     632\ref Opt2Tsp usually provides the best results in practice, but
     633it is the slowest method. It can also be used to improve given tours,
     634for example, the results of other algorithms.
     635
     636\image html tsp.png
     637\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     638*/
     639
     640/**
     641@defgroup approx_algs Approximation Algorithms
    556642@ingroup algs
    557643\brief Approximation algorithms.
    … …  
    559645This group contains the approximation and heuristic algorithms
    560646implemented in LEMON.
     647
     648<b>Maximum Clique Problem</b>
     649  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     650    Grosso, Locatelli, and Pullan.
    561651*/
    562652
    … …  
    588678high-level interface.
    589679
    590 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    591 \ref cplex, \ref soplex.
     680The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     681\cite cplex, \cite soplex.
    592682*/
    593683
    … …  
    676766This group contains general \c EPS drawing methods and special
    677767graph exporting tools.
     768
     769\image html graph_to_eps.png
    678770*/
    679771

  • 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

    r835 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).
    … …  
    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$,
    … …  
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
    84  
     84
    8585Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    8686\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    … …  
    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
    … …  
    120120\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    121121
    122 It means that the total demand must be less or equal to the 
     122It means that the total demand must be less or equal to the
    123123total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
    124124positive) and all the demands have to be satisfied, but there

  • doc/named-param.dox

    r463 r1351  
    2626function parameters by name also when you call the function. It is
    2727especially comfortable in case of a function having tons of parameters
    28 with natural default values. Sadly, C++ lack this amenity.
     28with natural default values. Sadly, C++ lacks this amenity.
    2929
    3030However, with a crafty trick and with some little

  • doc/references.bib

    r802 r1367  
    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}
     357
     358@article{cordella2004sub,
     359  author =       {Cordella, Luigi P. and Foggia, Pasquale and Sansone,
     360                  Carlo and Vento, Mario},
     361  title =        {A (sub)graph isomorphism algorithm for matching
     362                  large graphs},
     363  journal =      {IEEE Transactions on Pattern Analysis and Machine
     364                  Intelligence},
     365  volume =       26,
     366  number =       10,
     367  pages =        {1367--1372},
     368  year =         2004
     369}

  • 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

    r834 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).
    … …  
    422422      Parent::initialize(digraph);
    423423      _node_filter = &node_filter;
    424       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    425425    }
    426426
    … …  
    509509
    510510    template <typename V>
    511     class NodeMap 
    512       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    513               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511    class NodeMap
     512      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     513              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    514514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516516
    517517    public:
    … …  
    536536
    537537    template <typename V>
    538     class ArcMap 
     538    class ArcMap
    539539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    540               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    541541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    542542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    … …  
    583583      Parent::initialize(digraph);
    584584      _node_filter = &node_filter;
    585       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    586586    }
    587587
    … …  
    652652
    653653    template <typename V>
    654     class NodeMap 
     654    class NodeMap
    655655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    657       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    658658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    659659
    … …  
    679679
    680680    template <typename V>
    681     class ArcMap 
     681    class ArcMap
    682682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    683683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    … …  
    10221022
    10231023    template <typename V>
    1024     class NodeMap 
     1024    class NodeMap
    10251025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10261026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1027       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10281028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10291029
    … …  
    10491049
    10501050    template <typename V>
    1051     class ArcMap 
     1051    class ArcMap
    10521052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10531053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1054       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10551055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10561056
    … …  
    10761076
    10771077    template <typename V>
    1078     class EdgeMap 
     1078    class EdgeMap
    10791079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10801080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1081       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10821082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10831083
    … …  
    11181118    NF* _node_filter;
    11191119    EF* _edge_filter;
    1120     SubGraphBase() 
    1121           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11221122
    11231123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
    … …  
    12201220
    12211221    template <typename V>
    1222     class NodeMap 
     1222    class NodeMap
    12231223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12241224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1225       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12261226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12271227
    … …  
    12471247
    12481248    template <typename V>
    1249     class ArcMap 
     1249    class ArcMap
    12501250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12511251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1252       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12531253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12541254
    … …  
    12741274
    12751275    template <typename V>
    1276     class EdgeMap 
     1276    class EdgeMap
    12771277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12781278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1279       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1280         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12811281
    12821282    public:
    … …  
    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
    … …  
    15051505#endif
    15061506    typedef DigraphAdaptorExtender<
    1507       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    15081508                     true> > Parent;
    15091509
    … …  
    15261526    /// Creates a subgraph for the given digraph or graph with the
    15271527    /// given node filter map.
    1528     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15291529      : Parent(), const_true_map()
    15301530    {
    … …  
    15641564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15651565    public GraphAdaptorExtender<
    1566       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15671567                   true> > {
    15681568
    15691569    typedef GraphAdaptorExtender<
    1570       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15711571                   true> > Parent;
    15721572
    … …  
    16541654#endif
    16551655    typedef DigraphAdaptorExtender<
    1656       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16571657                     AF, false> > Parent;
    16581658
    … …  
    17621762  class FilterEdges :
    17631763    public GraphAdaptorExtender<
    1764       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17651765                   EF, false> > {
    17661766#endif
    17671767    typedef GraphAdaptorExtender<
    1768       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17691769                   EF, false> > Parent;
    17701770
    … …  
    17911791    /// Creates a subgraph for the given graph with the given edge
    17921792    /// filter map.
    1793     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17941794      : Parent(), const_true_map() {
    17951795      Parent::initialize(graph, const_true_map, edge_filter);
    … …  
    18591859      bool _forward;
    18601860
    1861       Arc(const Edge& edge, bool forward) 
     1861      Arc(const Edge& edge, bool forward)
    18621862        : _edge(edge), _forward(forward) {}
    18631863
    … …  
    20992099
    21002100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2101         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    21022102          _backward(*adaptor._digraph, value) {}
    21032103
    … …  
    22172217    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22182218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2219    
     2219
    22202220    typedef EdgeNotifier ArcNotifier;
    22212221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
    … …  
    22782278    /// Creates an undirected graph from the given digraph.
    22792279    Undirector(DGR& digraph) {
    2280       initialize(digraph);
     2280      this->initialize(digraph);
    22812281    }
    22822282
    … …  
    27292729           typename FM = CM,
    27302730           typename TL = Tolerance<typename CM::Value> >
    2731   class ResidualDigraph 
     2731  class ResidualDigraph
    27322732    : public SubDigraph<
    27332733        Undirector<const DGR>,
    … …  
    27862786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27872787                    FM& flow, const TL& tolerance = Tolerance())
    2788       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27892789        _graph(digraph), _node_filter(),
    27902790        _forward_filter(capacity, flow, tolerance),
    … …  
    28682868
    28692869      /// Constructor
    2870       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28712871        : _adaptor(&adaptor) {}
    28722872
    … …  
    34483448    /// to get a node map of the split digraph.
    34493449    /// Its value type is inherited from the first node map type (\c IN).
    3450     /// \tparam IN The type of the node map for the in-nodes. 
     3450    /// \tparam IN The type of the node map for the in-nodes.
    34513451    /// \tparam OUT The type of the node map for the out-nodes.
    34523452    template <typename IN, typename OUT>

  • lemon/arg_parser.cc

    r463 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2121namespace lemon {
    2222
     23  void ArgParser::_terminate(ArgParserException::Reason reason) const
     24  {
     25    if(_exit_on_problems)
     26      exit(1);
     27    else throw(ArgParserException(reason));
     28  }
     29
     30
    2331  void ArgParser::_showHelp(void *p)
    2432  {
    2533    (static_cast<ArgParser*>(p))->showHelp();
    26     exit(1);
     34    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
    2735  }
    2836
    2937  ArgParser::ArgParser(int argc, const char * const *argv)
    30     :_argc(argc), _argv(argv), _command_name(argv[0]) {
     38    :_argc(argc), _argv(argv), _command_name(argv[0]),
     39    _exit_on_problems(true) {
    3140    funcOption("-help","Print a short help message",_showHelp,this);
    3241    synonym("help","-help");
    … …  
    343352        i!=_others_help.end();++i) showHelp(i);
    344353    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    345     exit(1);
     354    _terminate(ArgParserException::HELP);
    346355  }
    347356
    … …  
    352361    std::cerr << "\nType '" << _command_name <<
    353362      " --help' to obtain a short summary on the usage.\n\n";
    354     exit(1);
     363    _terminate(ArgParserException::UNKNOWN_OPT);
    355364  }
    356365
    … …  
    415424      std::cerr << "\nType '" << _command_name <<
    416425        " --help' to obtain a short summary on the usage.\n\n";
    417       exit(1);
     426      _terminate(ArgParserException::INVALID_OPT);
    418427    }
    419428  }

  • lemon/arg_parser.h

    r463 r1327  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2727#include <sstream>
    2828#include <algorithm>
     29#include <lemon/core.h>
    2930#include <lemon/assert.h>
    3031
    … …  
    3435
    3536namespace lemon {
     37
     38  ///Exception used by ArgParser
     39
     40  ///Exception used by ArgParser.
     41  ///
     42  class ArgParserException : public Exception {
     43  public:
     44    /// Reasons for failure
     45
     46    /// Reasons for failure.
     47    ///
     48    enum Reason {
     49      HELP,         ///< <tt>--help</tt> option was given.
     50      UNKNOWN_OPT,  ///< Unknown option was given.
     51      INVALID_OPT   ///< Invalid combination of options.
     52    };
     53
     54  private:
     55    Reason _reason;
     56
     57  public:
     58    ///Constructor
     59    ArgParserException(Reason r) throw() : _reason(r) {}
     60    ///Virtual destructor
     61    virtual ~ArgParserException() throw() {}
     62    ///A short description of the exception
     63    virtual const char* what() const throw() {
     64      switch(_reason)
     65        {
     66        case HELP:
     67          return "lemon::ArgParseException: ask for help";
     68          break;
     69        case UNKNOWN_OPT:
     70          return "lemon::ArgParseException: unknown option";
     71          break;
     72        case INVALID_OPT:
     73          return "lemon::ArgParseException: invalid combination of options";
     74          break;
     75        }
     76      return "";
     77    }
     78    ///Return the reason for the failure
     79    Reason reason() const {return _reason; }
     80  };
     81
    3682
    3783  ///Command line arguments parser
    … …  
    116162                    const std::string &help,
    117163                    void (*func)(void *),void *data);
     164
     165    bool _exit_on_problems;
     166
     167    void _terminate(ArgParserException::Reason reason) const;
    118168
    119169  public:
    … …  
    381431    const std::vector<std::string> &files() const { return _file_args; }
    382432
     433    ///Throw instead of exit in case of problems
     434    void throwOnProblems()
     435    {
     436      _exit_on_problems=false;
     437    }
    383438  };
    384439}

  • 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

    r870 r1337  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3030#include <lemon/maps.h>
    3131#include <lemon/path.h>
     32#include <lemon/bits/stl_iterators.h>
    3233
    3334#include <limits>
    … …  
    3637
    3738  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    38   /// 
     39  ///
    3940  /// This operation traits class defines all computational operations
    4041  /// and constants that are used in the Bellman-Ford algorithm.
    … …  
    4344  /// value is used as extremal infinity value.
    4445  template <
    45     typename V, 
     46    typename V,
    4647    bool has_inf = std::numeric_limits<V>::has_infinity>
    4748  struct BellmanFordDefaultOperationTraits {
    … …  
    8485    }
    8586  };
    86  
     87
    8788  /// \brief Default traits class of BellmanFord class.
    8889  ///
    … …  
    9293  template<typename GR, typename LEN>
    9394  struct BellmanFordDefaultTraits {
    94     /// The type of the digraph the algorithm runs on. 
     95    /// The type of the digraph the algorithm runs on.
    9596    typedef GR Digraph;
    9697
    … …  
    110111    /// \see BellmanFordDefaultOperationTraits
    111112    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    112  
    113     /// \brief The type of the map that stores the last arcs of the 
     113
     114    /// \brief The type of the map that stores the last arcs of the
    114115    /// shortest paths.
    115     /// 
     116    ///
    116117    /// The type of the map that stores the last
    117118    /// arcs of the shortest paths.
    … …  
    120121
    121122    /// \brief Instantiates a \c PredMap.
    122     /// 
    123     /// This function instantiates a \ref PredMap. 
     123    ///
     124    /// This function instantiates a \ref PredMap.
    124125    /// \param g is the digraph to which we would like to define the
    125126    /// \ref PredMap.
    … …  
    136137    /// \brief Instantiates a \c DistMap.
    137138    ///
    138     /// This function instantiates a \ref DistMap. 
    139     /// \param g is the digraph to which we would like to define the 
     139    /// This function instantiates a \ref DistMap.
     140    /// \param g is the digraph to which we would like to define the
    140141    /// \ref DistMap.
    141142    static DistMap *createDistMap(const GR& g) {
    … …  
    144145
    145146  };
    146  
     147
    147148  /// \brief %BellmanFord algorithm class.
    148149  ///
    149150  /// \ingroup shortest_path
    150   /// This class provides an efficient implementation of the Bellman-Ford 
     151  /// This class provides an efficient implementation of the Bellman-Ford
    151152  /// algorithm. The maximum time complexity of the algorithm is
    152   /// <tt>O(ne)</tt>.
     153  /// <tt>O(nm)</tt>.
    153154  ///
    154155  /// The Bellman-Ford algorithm solves the single-source shortest path
    … …  
    159160  ///
    160161  /// The arc lengths are passed to the algorithm using a
    161   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     162  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    162163  /// kind of length. The type of the length values is determined by the
    163164  /// \ref concepts::ReadMap::Value "Value" type of the length map.
    … …  
    172173  /// the lengths of the arcs. The default map type is
    173174  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     175  /// \tparam TR The traits class that defines various types used by the
     176  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
     177  /// "BellmanFordDefaultTraits<GR, LEN>".
     178  /// In most cases, this parameter should not be set directly,
     179  /// consider to use the named template parameters instead.
    174180#ifdef DOXYGEN
    175181  template <typename GR, typename LEN, typename TR>
    … …  
    184190    ///The type of the underlying digraph.
    185191    typedef typename TR::Digraph Digraph;
    186    
     192
    187193    /// \brief The type of the arc lengths.
    188194    typedef typename TR::LengthMap::Value Value;
    … …  
    196202    /// The type of the paths.
    197203    typedef PredMapPath<Digraph, PredMap> Path;
    198     ///\brief The \ref BellmanFordDefaultOperationTraits
     204    ///\brief The \ref lemon::BellmanFordDefaultOperationTraits
    199205    /// "operation traits class" of the algorithm.
    200206    typedef typename TR::OperationTraits OperationTraits;
    201207
    202     ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
     208    ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class"
     209    ///of the algorithm.
    203210    typedef TR Traits;
    204211
    … …  
    231238    void create_maps() {
    232239      if(!_pred) {
    233         _local_pred = true;
    234         _pred = Traits::createPredMap(*_gr);
     240        _local_pred = true;
     241        _pred = Traits::createPredMap(*_gr);
    235242      }
    236243      if(!_dist) {
    237         _local_dist = true;
    238         _dist = Traits::createDistMap(*_gr);
     244        _local_dist = true;
     245        _dist = Traits::createDistMap(*_gr);
    239246      }
    240247      if(!_mask) {
    … …  
    242249      }
    243250    }
    244    
     251
    245252  public :
    246  
     253
    247254    typedef BellmanFord Create;
    248255
    … …  
    267274    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    268275    template <class T>
    269     struct SetPredMap 
     276    struct SetPredMap
    270277      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
    271278      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    272279    };
    273    
     280
    274281    template <class T>
    275282    struct SetDistMapTraits : public Traits {
    … …  
    288295    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289296    template <class T>
    290     struct SetDistMap 
     297    struct SetDistMap
    291298      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
    292299      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
    … …  
    297304      typedef T OperationTraits;
    298305    };
    299    
    300     /// \brief \ref named-templ-param "Named parameter" for setting 
     306
     307    /// \brief \ref named-templ-param "Named parameter" for setting
    301308    /// \c OperationTraits type.
    302309    ///
    … …  
    310317      Create;
    311318    };
    312    
     319
    313320    ///@}
    314321
    315322  protected:
    316    
     323
    317324    BellmanFord() {}
    318325
    319   public:     
    320    
     326  public:
     327
    321328    /// \brief Constructor.
    322329    ///
    … …  
    328335      _pred(0), _local_pred(false),
    329336      _dist(0), _local_dist(false), _mask(0) {}
    330    
     337
    331338    ///Destructor.
    332339    ~BellmanFord() {
    … …  
    355362    BellmanFord &predMap(PredMap &map) {
    356363      if(_local_pred) {
    357         delete _pred;
    358         _local_pred=false;
     364        delete _pred;
     365        _local_pred=false;
    359366      }
    360367      _pred = &map;
    … …  
    373380    BellmanFord &distMap(DistMap &map) {
    374381      if(_local_dist) {
    375         delete _dist;
    376         _local_dist=false;
     382        delete _dist;
     383        _local_dist=false;
    377384      }
    378385      _dist = &map;
    … …  
    392399
    393400    /// \brief Initializes the internal data structures.
    394     /// 
     401    ///
    395402    /// Initializes the internal data structures. The optional parameter
    396403    /// is the initial distance of each node.
    … …  
    398405      create_maps();
    399406      for (NodeIt it(*_gr); it != INVALID; ++it) {
    400         _pred->set(it, INVALID);
    401         _dist->set(it, value);
     407        _pred->set(it, INVALID);
     408        _dist->set(it, value);
    402409      }
    403410      _process.clear();
    404411      if (OperationTraits::less(value, OperationTraits::infinity())) {
    405         for (NodeIt it(*_gr); it != INVALID; ++it) {
    406           _process.push_back(it);
    407           _mask->set(it, true);
    408         }
     412        for (NodeIt it(*_gr); it != INVALID; ++it) {
     413          _process.push_back(it);
     414          _mask->set(it, true);
     415        }
    409416      } else {
    410         for (NodeIt it(*_gr); it != INVALID; ++it) {
    411           _mask->set(it, false);
    412         }
    413       }
    414     }
    415    
     417        for (NodeIt it(*_gr); it != INVALID; ++it) {
     418          _mask->set(it, false);
     419        }
     420      }
     421    }
     422
    416423    /// \brief Adds a new source node.
    417424    ///
    … …  
    421428      _dist->set(source, dst);
    422429      if (!(*_mask)[source]) {
    423         _process.push_back(source);
    424         _mask->set(source, true);
     430        _process.push_back(source);
     431        _mask->set(source, true);
    425432      }
    426433    }
    … …  
    447454    bool processNextRound() {
    448455      for (int i = 0; i < int(_process.size()); ++i) {
    449         _mask->set(_process[i], false);
     456        _mask->set(_process[i], false);
    450457      }
    451458      std::vector<Node> nextProcess;
    452459      std::vector<Value> values(_process.size());
    453460      for (int i = 0; i < int(_process.size()); ++i) {
    454         values[i] = (*_dist)[_process[i]];
     461        values[i] = (*_dist)[_process[i]];
    455462      }
    456463      for (int i = 0; i < int(_process.size()); ++i) {
    457         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    458           Node target = _gr->target(it);
    459           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
    460           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    461             _pred->set(target, it);
    462             _dist->set(target, relaxed);
    463             if (!(*_mask)[target]) {
    464               _mask->set(target, true);
    465               nextProcess.push_back(target);
    466             }
    467           }       
    468         }
     464        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     465          Node target = _gr->target(it);
     466          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
     467          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     468            _pred->set(target, it);
     469            _dist->set(target, relaxed);
     470            if (!(*_mask)[target]) {
     471              _mask->set(target, true);
     472              nextProcess.push_back(target);
     473            }
     474          }
     475        }
    469476      }
    470477      _process.swap(nextProcess);
    … …  
    488495    bool processNextWeakRound() {
    489496      for (int i = 0; i < int(_process.size()); ++i) {
    490         _mask->set(_process[i], false);
     497        _mask->set(_process[i], false);
    491498      }
    492499      std::vector<Node> nextProcess;
    493500      for (int i = 0; i < int(_process.size()); ++i) {
    494         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    495           Node target = _gr->target(it);
    496           Value relaxed =
    497             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    498           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    499             _pred->set(target, it);
    500             _dist->set(target, relaxed);
    501             if (!(*_mask)[target]) {
    502               _mask->set(target, true);
    503               nextProcess.push_back(target);
    504             }
    505           }       
    506         }
     501        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     502          Node target = _gr->target(it);
     503          Value relaxed =
     504            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
     505          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     506            _pred->set(target, it);
     507            _dist->set(target, relaxed);
     508            if (!(*_mask)[target]) {
     509              _mask->set(target, true);
     510              nextProcess.push_back(target);
     511            }
     512          }
     513        }
    507514      }
    508515      _process.swap(nextProcess);
    … …  
    526533      int num = countNodes(*_gr) - 1;
    527534      for (int i = 0; i < num; ++i) {
    528         if (processNextWeakRound()) break;
     535        if (processNextWeakRound()) break;
    529536      }
    530537    }
    … …  
    538545    /// if the digraph contains cycles with negative total length.
    539546    ///
    540     /// The algorithm computes 
     547    /// The algorithm computes
    541548    /// - the shortest path tree (forest),
    542549    /// - the distance of each node from the root(s).
    543     /// 
     550    ///
    544551    /// \return \c false if there is a negative cycle in the digraph.
    545552    ///
    546553    /// \pre init() must be called and at least one root node should be
    547     /// added with addSource() before using this function. 
     554    /// added with addSource() before using this function.
    548555    bool checkedStart() {
    549556      int num = countNodes(*_gr);
    550557      for (int i = 0; i < num; ++i) {
    551         if (processNextWeakRound()) return true;
     558        if (processNextWeakRound()) return true;
    552559      }
    553560      return _process.empty();
    … …  
    573580    ///
    574581    /// \pre init() must be called and at least one root node should be
    575     /// added with addSource() before using this function. 
     582    /// added with addSource() before using this function.
    576583    void limitedStart(int num) {
    577584      for (int i = 0; i < num; ++i) {
    578         if (processNextRound()) break;
    579       }
    580     }
    581    
     585        if (processNextRound()) break;
     586      }
     587    }
     588
    582589    /// \brief Runs the algorithm from the given root node.
    583     ///   
     590    ///
    584591    /// This method runs the Bellman-Ford algorithm from the given root
    585592    /// node \c s in order to compute the shortest path to each node.
    … …  
    600607      start();
    601608    }
    602    
     609
    603610    /// \brief Runs the algorithm from the given root node with arc
    604611    /// number limit.
    605     ///   
     612    ///
    606613    /// This method runs the Bellman-Ford algorithm from the given root
    607614    /// node \c s in order to compute the shortest path distance for each
    … …  
    629636      limitedStart(num);
    630637    }
    631    
     638
    632639    ///@}
    633640
    … …  
    644651      ///
    645652      /// Constructor for getting the active nodes of the given BellmanFord
    646       /// instance. 
     653      /// instance.
    647654      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    648655      {
    … …  
    658665      ///
    659666      /// Conversion to \c Node.
    660       operator Node() const { 
     667      operator Node() const {
    661668        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    662669      }
    … …  
    667674      ActiveIt& operator++() {
    668675        --_index;
    669         return *this; 
    670       }
    671 
    672       bool operator==(const ActiveIt& it) const { 
    673         return static_cast<Node>(*this) == static_cast<Node>(it); 
    674       }
    675       bool operator!=(const ActiveIt& it) const { 
    676         return static_cast<Node>(*this) != static_cast<Node>(it); 
    677       }
    678       bool operator<(const ActiveIt& it) const { 
    679         return static_cast<Node>(*this) < static_cast<Node>(it); 
    680       }
    681      
     676        return *this;
     677      }
     678
     679      bool operator==(const ActiveIt& it) const {
     680        return static_cast<Node>(*this) == static_cast<Node>(it);
     681      }
     682      bool operator!=(const ActiveIt& it) const {
     683        return static_cast<Node>(*this) != static_cast<Node>(it);
     684      }
     685      bool operator<(const ActiveIt& it) const {
     686        return static_cast<Node>(*this) < static_cast<Node>(it);
     687      }
     688
    682689    private:
    683690      const BellmanFord* _algorithm;
    684691      int _index;
    685692    };
    686    
     693
     694    /// \brief Gets the collection of the active nodes.
     695    ///
     696    /// This function can be used for iterating on the active nodes of the
     697    /// Bellman-Ford algorithm after the last phase.
     698    /// These nodes should be checked in the next phase to
     699    /// find augmenting arcs outgoing from them.
     700    /// It returns a wrapped ActiveIt, which looks
     701    /// like an STL container (by having begin() and end())
     702    /// which you can use in range-based for loops, STL algorithms, etc.
     703    LemonRangeWrapper1<ActiveIt, BellmanFord>
     704    activeNodes() const {
     705      return LemonRangeWrapper1<ActiveIt, BellmanFord>(*this);
     706    }
     707
     708
    687709    /// \name Query Functions
    688710    /// The result of the Bellman-Ford algorithm can be obtained using these
    689711    /// functions.\n
    690712    /// Either \ref run() or \ref init() should be called before using them.
    691    
     713
    692714    ///@{
    693715
    694716    /// \brief The shortest path to the given node.
    695     ///   
     717    ///
    696718    /// Gives back the shortest path to the given node from the root(s).
    697719    ///
    … …  
    704726      return Path(*_gr, *_pred, t);
    705727    }
    706          
     728
    707729    /// \brief The distance of the given node from the root(s).
    708730    ///
    … …  
    744766    /// \pre Either \ref run() or \ref init() must be called before
    745767    /// using this function.
    746     Node predNode(Node v) const { 
    747       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
    748     }
    749    
     768    Node predNode(Node v) const {
     769      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
     770    }
     771
    750772    /// \brief Returns a const reference to the node map that stores the
    751773    /// distances of the nodes.
    … …  
    757779    /// using this function.
    758780    const DistMap &distMap() const { return *_dist;}
    759  
     781
    760782    /// \brief Returns a const reference to the node map that stores the
    761783    /// predecessor arcs.
    … …  
    767789    /// using this function.
    768790    const PredMap &predMap() const { return *_pred; }
    769  
     791
    770792    /// \brief Checks if a node is reached from the root(s).
    771793    ///
    … …  
    779801
    780802    /// \brief Gives back a negative cycle.
    781     ///   
     803    ///
    782804    /// This function gives back a directed cycle with negative total
    783805    /// length if the algorithm has already found one.
    … …  
    806828      return cycle;
    807829    }
    808    
     830
    809831    ///@}
    810832  };
    811  
     833
    812834  /// \brief Default traits class of bellmanFord() function.
    813835  ///
    … …  
    817839  template <typename GR, typename LEN>
    818840  struct BellmanFordWizardDefaultTraits {
    819     /// The type of the digraph the algorithm runs on. 
     841    /// The type of the digraph the algorithm runs on.
    820842    typedef GR Digraph;
    821843
    … …  
    838860    /// \brief The type of the map that stores the last
    839861    /// arcs of the shortest paths.
    840     /// 
     862    ///
    841863    /// The type of the map that stores the last arcs of the shortest paths.
    842864    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    844866
    845867    /// \brief Instantiates a \c PredMap.
    846     /// 
     868    ///
    847869    /// This function instantiates a \ref PredMap.
    848870    /// \param g is the digraph to which we would like to define the
    … …  
    860882    /// \brief Instantiates a \c DistMap.
    861883    ///
    862     /// This function instantiates a \ref DistMap. 
     884    /// This function instantiates a \ref DistMap.
    863885    /// \param g is the digraph to which we would like to define the
    864886    /// \ref DistMap.
    … …  
    873895    typedef lemon::Path<Digraph> Path;
    874896  };
    875  
     897
    876898  /// \brief Default traits class used by BellmanFordWizard.
    877899  ///
    … …  
    880902  /// \tparam LEN The type of the length map.
    881903  template <typename GR, typename LEN>
    882   class BellmanFordWizardBase 
     904  class BellmanFordWizardBase
    883905    : public BellmanFordWizardDefaultTraits<GR, LEN> {
    884906
    … …  
    903925    public:
    904926    /// Constructor.
    905    
     927
    906928    /// This constructor does not require parameters, it initiates
    907929    /// all of the attributes to default values \c 0.
    … …  
    910932
    911933    /// Constructor.
    912    
     934
    913935    /// This constructor requires two parameters,
    914936    /// others are initiated to \c 0.
    915937    /// \param gr The digraph the algorithm runs on.
    916938    /// \param len The length map.
    917     BellmanFordWizardBase(const GR& gr, 
    918                           const LEN& len) :
    919       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
    920       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
     939    BellmanFordWizardBase(const GR& gr,
     940                          const LEN& len) :
     941      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     942      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
    921943      _pred(0), _dist(0), _path(0), _di(0) {}
    922944
    923945  };
    924  
     946
    925947  /// \brief Auxiliary class for the function-type interface of the
    926948  /// \ref BellmanFord "Bellman-Ford" algorithm.
    … …  
    934956  /// This class should only be used through the \ref bellmanFord()
    935957  /// function, which makes it easier to use the algorithm.
     958  ///
     959  /// \tparam TR The traits class that defines various types used by the
     960  /// algorithm.
    936961  template<class TR>
    937962  class BellmanFordWizard : public TR {
    … …  
    944969    typedef typename Digraph::Arc Arc;
    945970    typedef typename Digraph::OutArcIt ArcIt;
    946    
     971
    947972    typedef typename TR::LengthMap LengthMap;
    948973    typedef typename LengthMap::Value Value;
    … …  
    961986    /// \param gr The digraph the algorithm runs on.
    962987    /// \param len The length map.
    963     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
     988    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
    964989      : TR(gr, len) {}
    965990
    … …  
    970995
    971996    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    972     ///   
     997    ///
    973998    /// This method runs the Bellman-Ford algorithm from the given source
    974999    /// node in order to compute the shortest path to each node.
    9751000    void run(Node s) {
    976       BellmanFord<Digraph,LengthMap,TR> 
    977         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     1001      BellmanFord<Digraph,LengthMap,TR>
     1002        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    9781003           *reinterpret_cast<const LengthMap*>(Base::_length));
    9791004      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    … …  
    10101035      SetPredMapBase(const TR &b) : TR(b) {}
    10111036    };
    1012    
     1037
    10131038    /// \brief \ref named-templ-param "Named parameter" for setting
    10141039    /// the predecessor map.
    … …  
    10211046      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    10221047    }
    1023    
     1048
    10241049    template<class T>
    10251050    struct SetDistMapBase : public Base {
    … …  
    10281053      SetDistMapBase(const TR &b) : TR(b) {}
    10291054    };
    1030    
     1055
    10311056    /// \brief \ref named-templ-param "Named parameter" for setting
    10321057    /// the distance map.
    … …  
    10691094      return *this;
    10701095    }
    1071    
     1096
    10721097  };
    1073  
     1098
    10741099  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
    10751100  /// algorithm.
    … …  
    10791104  /// algorithm.
    10801105  ///
    1081   /// This function also has several \ref named-templ-func-param 
    1082   /// "named parameters", they are declared as the members of class 
     1106  /// This function also has several \ref named-templ-func-param
     1107  /// "named parameters", they are declared as the members of class
    10831108  /// \ref BellmanFordWizard.
    10841109  /// The following examples show how to use these parameters.
    … …  
    10971122  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
    10981123  bellmanFord(const GR& digraph,
    1099               const LEN& length)
     1124              const LEN& length)
    11001125  {
    11011126    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);

  • lemon/bfs.h

    r835 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).
    … …  
    8383
    8484    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8687    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8788    ///Instantiates a \c ReachedMap.
    … …  
    122123  ///\tparam GR The type of the digraph the algorithm runs on.
    123124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref BfsDefaultTraits
     127  ///"BfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    124130#ifdef DOXYGEN
    125131  template <typename GR,
    … …  
    147153    typedef PredMapPath<Digraph, PredMap> Path;
    148154
    149     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
    150156    typedef TR Traits;
    151157
    … …  
    267273    ///\ref named-templ-param "Named parameter" for setting
    268274    ///\c ReachedMap type.
    269     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    270277    template <class T>
    271278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    868875
    869876    ///The type of the map that indicates which nodes are reached.
    870     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    871879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    872880    ///Instantiates a ReachedMap.
    … …  
    958966  /// This class should only be used through the \ref bfs() function,
    959967  /// which makes it easier to use the algorithm.
     968  ///
     969  /// \tparam TR The traits class that defines various types used by the
     970  /// algorithm.
    960971  template<class TR>
    961972  class BfsWizard : public TR
    … …  
    12411252      }
    12421253      _Visitor& visitor;
     1254      Constraints() {}
    12431255    };
    12441256  };
    … …  
    12581270    ///
    12591271    /// The type of the map that indicates which nodes are reached.
    1260     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1272    /// It must conform to
     1273    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12611274    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12621275
    … …  
    12961309  /// does not observe the BFS events. If you want to observe the BFS
    12971310  /// events, you should implement your own visitor class.
    1298   /// \tparam TR Traits class to set various data types used by the
    1299   /// algorithm. The default traits class is
    1300   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    1301   /// See \ref BfsVisitDefaultTraits for the documentation of
    1302   /// a BFS visit traits class.
     1311  /// \tparam TR The traits class that defines various types used by the
     1312  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
     1313  /// "BfsVisitDefaultTraits<GR>".
     1314  /// In most cases, this parameter should not be set directly,
     1315  /// consider to use the named template parameters instead.
    13031316#ifdef DOXYGEN
    13041317  template <typename GR, typename VS, typename TR>

  • 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

    r664 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).
    … …  
    7171
    7272  private:
    73  
     73
    7474    // The MapBase of the Map which imlements the core regisitry function.
    7575    typedef typename Notifier::ObserverBase Parent;

  • 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

    r674 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).
    … …  
    158158  public:
    159159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
     160
    161161    typedef typename Parent::GraphType GraphType;
    162162    typedef typename Parent::Value Value;

  • lemon/bits/edge_set_extender.h

    r732 r1337  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
    … …  
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9595      const Digraph* digraph;
    9696    public:
    … …  
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node)
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() {
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc {
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node)
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() {
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
     117      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
     118    }
     119
     120    class ArcIt : public Arc {
    118121      const Digraph* digraph;
    119122    public:
    … …  
    124127
    125128      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) :
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() {
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc {
     129        _graph.first(static_cast<Arc&>(*this));
     130      }
     131
     132      ArcIt(const Digraph& _graph, const Arc& e) :
     133        Arc(e), digraph(&_graph) { }
     134
     135      ArcIt& operator++() {
     136        digraph->next(*this);
     137        return *this;
     138      }
     139
     140    };
     141
     142    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
     143      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
     144    }
     145
     146    class OutArcIt : public Arc {
    141147      const Digraph* digraph;
    142148    public:
    … …  
    146152      OutArcIt(Invalid i) : Arc(i) { }
    147153
    148       OutArcIt(const Digraph& _graph, const Node& node)
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc)
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() {
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc {
     154      OutArcIt(const Digraph& _graph, const Node& node)
     155        : digraph(&_graph) {
     156        _graph.firstOut(*this, node);
     157      }
     158
     159      OutArcIt(const Digraph& _graph, const Arc& arc)
     160        : Arc(arc), digraph(&_graph) {}
     161
     162      OutArcIt& operator++() {
     163        digraph->nextOut(*this);
     164        return *this;
     165      }
     166
     167    };
     168
     169    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
     170      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
     171    }
     172
     173    class InArcIt : public Arc {
    165174      const Digraph* digraph;
    166175    public:
    … …  
    170179      InArcIt(Invalid i) : Arc(i) { }
    171180
    172       InArcIt(const Digraph& _graph, const Node& node)
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) :
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() {
    181         digraph->nextIn(*this);
    182         return *this;
    183       }
    184 
    185     };
     181      InArcIt(const Digraph& _graph, const Node& node)
     182        : digraph(&_graph) {
     183        _graph.firstIn(*this, node);
     184      }
     185
     186      InArcIt(const Digraph& _graph, const Arc& arc) :
     187        Arc(arc), digraph(&_graph) {}
     188
     189      InArcIt& operator++() {
     190        digraph->nextIn(*this);
     191        return *this;
     192      }
     193
     194    };
     195
     196    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
     197      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
     198    }
    186199
    187200    // \brief Base node of the iterator
    … …  
    216229
    217230    // Mappable extension
    218    
     231
    219232    template <typename _Value>
    220     class ArcMap 
     233    class ArcMap
    221234      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222235      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223236
    224237    public:
    225       explicit ArcMap(const Digraph& _g) 
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v) 
    228         : Parent(_g, _v) {}
     238      explicit ArcMap(const Digraph& _g)
     239        : Parent(_g) {}
     240      ArcMap(const Digraph& _g, const _Value& _v)
     241        : Parent(_g, _v) {}
    229242
    230243      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     244        return operator=<ArcMap>(cmap);
    232245      }
    233246
    … …  
    235248      ArcMap& operator=(const CMap& cmap) {
    236249        Parent::operator=(cmap);
    237         return *this;
     250        return *this;
    238251      }
    239252
    … …  
    248261      return arc;
    249262    }
    250    
     263
    251264    void clear() {
    252265      notifier(Arc()).clear();
    … …  
    281294    typedef EdgeSetExtender Graph;
    282295
     296    typedef True UndirectedTag;
     297
    283298    typedef typename Parent::Node Node;
    284299    typedef typename Parent::Arc Arc;
    … …  
    311326    Node oppositeNode(const Node &n, const Edge &e) const {
    312327      if( n == Parent::u(e))
    313         return Parent::v(e);
     328        return Parent::v(e);
    314329      else if( n == Parent::v(e))
    315         return Parent::u(e);
     330        return Parent::u(e);
    316331      else
    317         return INVALID;
     332        return INVALID;
    318333    }
    319334
    … …  
    339354
    340355    using Parent::notifier;
    341    
     356
    342357    ArcNotifier& notifier(Arc) const {
    343358      return arc_notifier;
    … …  
    349364
    350365
    351     class NodeIt : public Node { 
     366    class NodeIt : public Node {
    352367      const Graph* graph;
    353368    public:
    … …  
    358373
    359374      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    360         _graph.first(static_cast<Node&>(*this));
    361       }
    362 
    363       NodeIt(const Graph& _graph, const Node& node)
    364         : Node(node), graph(&_graph) {}
    365 
    366       NodeIt& operator++() {
    367         graph->next(*this);
    368         return *this;
    369       }
    370 
    371     };
    372 
    373 
    374     class ArcIt : public Arc {
     375        _graph.first(static_cast<Node&>(*this));
     376      }
     377
     378      NodeIt(const Graph& _graph, const Node& node)
     379        : Node(node), graph(&_graph) {}
     380
     381      NodeIt& operator++() {
     382        graph->next(*this);
     383        return *this;
     384      }
     385
     386    };
     387
     388    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
     389      return LemonRangeWrapper1<NodeIt, Graph>(*this);
     390    }
     391
     392    class ArcIt : public Arc {
    375393      const Graph* graph;
    376394    public:
    … …  
    381399
    382400      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    383         _graph.first(static_cast<Arc&>(*this));
    384       }
    385 
    386       ArcIt(const Graph& _graph, const Arc& e) :
    387         Arc(e), graph(&_graph) { }
    388 
    389       ArcIt& operator++() {
    390         graph->next(*this);
    391         return *this;
    392       }
    393 
    394     };
    395 
    396 
    397     class OutArcIt : public Arc {
     401        _graph.first(static_cast<Arc&>(*this));
     402      }
     403
     404      ArcIt(const Graph& _graph, const Arc& e) :
     405        Arc(e), graph(&_graph) { }
     406
     407      ArcIt& operator++() {
     408        graph->next(*this);
     409        return *this;
     410      }
     411
     412    };
     413
     414    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
     415      return LemonRangeWrapper1<ArcIt, Graph>(*this);
     416    }
     417
     418    class OutArcIt : public Arc {
    398419      const Graph* graph;
    399420    public:
    … …  
    403424      OutArcIt(Invalid i) : Arc(i) { }
    404425
    405       OutArcIt(const Graph& _graph, const Node& node)
    406         : graph(&_graph) {
    407         _graph.firstOut(*this, node);
    408       }
    409 
    410       OutArcIt(const Graph& _graph, const Arc& arc)
    411         : Arc(arc), graph(&_graph) {}
    412 
    413       OutArcIt& operator++() {
    414         graph->nextOut(*this);
    415         return *this;
    416       }
    417 
    418     };
    419 
    420 
    421     class InArcIt : public Arc {
     426      OutArcIt(const Graph& _graph, const Node& node)
     427        : graph(&_graph) {
     428        _graph.firstOut(*this, node);
     429      }
     430
     431      OutArcIt(const Graph& _graph, const Arc& arc)
     432        : Arc(arc), graph(&_graph) {}
     433
     434      OutArcIt& operator++() {
     435        graph->nextOut(*this);
     436        return *this;
     437      }
     438
     439    };
     440
     441    LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
     442      return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
     443    }
     444
     445    class InArcIt : public Arc {
    422446      const Graph* graph;
    423447    public:
    … …  
    427451      InArcIt(Invalid i) : Arc(i) { }
    428452
    429       InArcIt(const Graph& _graph, const Node& node)
    430         : graph(&_graph) {
    431         _graph.firstIn(*this, node);
    432       }
    433 
    434       InArcIt(const Graph& _graph, const Arc& arc) :
    435         Arc(arc), graph(&_graph) {}
    436 
    437       InArcIt& operator++() {
    438         graph->nextIn(*this);
    439         return *this;
    440       }
    441 
    442     };
    443 
    444 
    445     class EdgeIt : public Parent::Edge {
     453      InArcIt(const Graph& _graph, const Node& node)
     454        : graph(&_graph) {
     455        _graph.firstIn(*this, node);
     456      }
     457
     458      InArcIt(const Graph& _graph, const Arc& arc) :
     459        Arc(arc), graph(&_graph) {}
     460
     461      InArcIt& operator++() {
     462        graph->nextIn(*this);
     463        return *this;
     464      }
     465
     466    };
     467
     468    LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
     469      return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
     470    }
     471
     472    class EdgeIt : public Parent::Edge {
    446473      const Graph* graph;
    447474    public:
    … …  
    452479
    453480      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    454         _graph.first(static_cast<Edge&>(*this));
    455       }
    456 
    457       EdgeIt(const Graph& _graph, const Edge& e) :
    458         Edge(e), graph(&_graph) { }
    459 
    460       EdgeIt& operator++() {
    461         graph->next(*this);
    462         return *this;
    463       }
    464 
    465     };
     481        _graph.first(static_cast<Edge&>(*this));
     482      }
     483
     484      EdgeIt(const Graph& _graph, const Edge& e) :
     485        Edge(e), graph(&_graph) { }
     486
     487      EdgeIt& operator++() {
     488        graph->next(*this);
     489        return *this;
     490      }
     491
     492    };
     493
     494    LemonRangeWrapper1<EdgeIt, Graph> edges() const {
     495      return LemonRangeWrapper1<EdgeIt, Graph>(*this);
     496    }
    466497
    467498    class IncEdgeIt : public Parent::Edge {
    … …  
    476507
    477508      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    478         _graph.firstInc(*this, direction, n);
     509        _graph.firstInc(*this, direction, n);
    479510      }
    480511
    481512      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    482         : graph(&_graph), Edge(ue) {
    483         direction = (_graph.source(ue) == n);
     513        : graph(&_graph), Edge(ue) {
     514        direction = (_graph.source(ue) == n);
    484515      }
    485516
    486517      IncEdgeIt& operator++() {
    487         graph->nextInc(*this, direction);
    488         return *this;
    489       }
    490     };
     518        graph->nextInc(*this, direction);
     519        return *this;
     520      }
     521    };
     522
     523    LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
     524      return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
     525    }
    491526
    492527    // \brief Base node of the iterator
    … …  
    522557    // Returns the base node of the iterator
    523558    Node baseNode(const IncEdgeIt &e) const {
    524       return e.direction ? u(e) : v(e);
     559      return e.direction ? this->u(e) : this->v(e);
    525560    }
    526561    // Running node of the iterator
    … …  
    528563    // Returns the running node of the iterator
    529564    Node runningNode(const IncEdgeIt &e) const {
    530       return e.direction ? v(e) : u(e);
     565      return e.direction ? this->v(e) : this->u(e);
    531566    }
    532567
    533568
    534569    template <typename _Value>
    535     class ArcMap 
     570    class ArcMap
    536571      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    537572      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    538573
    539574    public:
    540       explicit ArcMap(const Graph& _g) 
    541         : Parent(_g) {}
    542       ArcMap(const Graph& _g, const _Value& _v) 
    543         : Parent(_g, _v) {}
     575      explicit ArcMap(const Graph& _g)
     576        : Parent(_g) {}
     577      ArcMap(const Graph& _g, const _Value& _v)
     578        : Parent(_g, _v) {}
    544579
    545580      ArcMap& operator=(const ArcMap& cmap) {
    546         return operator=<ArcMap>(cmap);
     581        return operator=<ArcMap>(cmap);
    547582      }
    548583
    … …  
    550585      ArcMap& operator=(const CMap& cmap) {
    551586        Parent::operator=(cmap);
    552         return *this;
     587        return *this;
    553588      }
    554589
    … …  
    557592
    558593    template <typename _Value>
    559     class EdgeMap 
     594    class EdgeMap
    560595      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    561596      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    562597
    563598    public:
    564       explicit EdgeMap(const Graph& _g) 
    565         : Parent(_g) {}
    566 
    567       EdgeMap(const Graph& _g, const _Value& _v) 
    568         : Parent(_g, _v) {}
     599      explicit EdgeMap(const Graph& _g)
     600        : Parent(_g) {}
     601
     602      EdgeMap(const Graph& _g, const _Value& _v)
     603        : Parent(_g, _v) {}
    569604
    570605      EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
     606        return operator=<EdgeMap>(cmap);
    572607      }
    573608
    … …  
    575610      EdgeMap& operator=(const CMap& cmap) {
    576611        Parent::operator=(cmap);
    577         return *this;
     612        return *this;
    578613      }
    579614
    … …  
    592627      return edge;
    593628    }
    594    
     629
    595630    void clear() {
    596631      notifier(Arc()).clear();
    … …  
    618653      arc_notifier.clear();
    619654    }
    620    
     655
    621656  };
    622657

  • lemon/bits/graph_adaptor_extender.h

    r664 r1337  
    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).
    … …  
    8686    };
    8787
     88    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
     89      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
     90    }
    8891
    8992    class ArcIt : public Arc {
    … …  
    108111
    109112    };
     113
     114    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
     115      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
     116    }
    110117
    111118
    … …  
    133140    };
    134141
     142    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
     143      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
     144    }
     145
    135146
    136147    class InArcIt : public Arc {
    … …  
    157168    };
    158169
     170    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
     171      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
     172    }
     173
    159174    Node baseNode(const OutArcIt &e) const {
    160175      return Parent::source(e);
    … …  
    181196    typedef _Graph Graph;
    182197    typedef GraphAdaptorExtender Adaptor;
     198
     199    typedef True UndirectedTag;
    183200
    184201    typedef typename Parent::Node Node;
    … …  
    253270    };
    254271
     272    LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
     273      return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
     274    }
     275
    255276
    256277    class ArcIt : public Arc {
    … …  
    275296
    276297    };
     298
     299    LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
     300      return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
     301    }
    277302
    278303
    … …  
    300325    };
    301326
     327    LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
     328      return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
     329    }
     330
    302331
    303332    class InArcIt : public Arc {
    … …  
    324353    };
    325354
     355    LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
     356      return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
     357    }
     358
    326359    class EdgeIt : public Parent::Edge {
    327360      const Adaptor* _adaptor;
    … …  
    345378
    346379    };
     380
     381    LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
     382      return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
     383    }
     384
    347385
    348386    class IncEdgeIt : public Edge {
    … …  
    371409    };
    372410
     411    LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
     412      return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
     413    }
     414
     415
    373416    Node baseNode(const OutArcIt &a) const {
    374417      return Parent::source(a);

  • lemon/bits/graph_extender.h

    r825 r1336  
    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).
    … …  
    2828#include <lemon/concepts/maps.h>
    2929
     30#include <lemon/bits/stl_iterators.h>
     31
    3032//\ingroup graphbits
    3133//\file
    … …  
    117119    };
    118120
     121    LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
     122      return LemonRangeWrapper1<NodeIt, Digraph>(*this);
     123    }
     124
    119125
    120126    class ArcIt : public Arc {
    … …  
    139145
    140146    };
     147
     148    LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
     149      return LemonRangeWrapper1<ArcIt, Digraph>(*this);
     150    }
    141151
    142152
    … …  
    164174    };
    165175
     176    LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
     177      return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
     178    }
     179
    166180
    167181    class InArcIt : public Arc {
    … …  
    187201
    188202    };
     203
     204    LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
     205      return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
     206    }
    189207
    190208    // \brief Base node of the iterator
    … …  
    437455    };
    438456
     457    LemonRangeWrapper1<NodeIt, Graph> nodes() const {
     458      return LemonRangeWrapper1<NodeIt, Graph>(*this);
     459    }
     460
    439461
    440462    class ArcIt : public Arc {
    … …  
    459481
    460482    };
     483
     484    LemonRangeWrapper1<ArcIt, Graph> arcs() const {
     485      return LemonRangeWrapper1<ArcIt, Graph>(*this);
     486    }
    461487
    462488
    … …