COIN-OR::LEMON - Graph Library

Ignore:
Files:
69 added
18 deleted
127 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r564 r944  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
     25doc/references.dox
     26cmake/version.cmake
    2627.dirstamp
    2728.libs/*
  • 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

    r599 r1344  
    1 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    2 
    3 IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    4   INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    5 ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    6   SET(PROJECT_NAME "LEMON")
    7   SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
    8 ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
    9 
     1CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
     2
     3IF(POLICY CMP0048)
     4  CMAKE_POLICY(SET CMP0048 OLD)
     5ENDIF(POLICY CMP0048)
     6
     7IF(POLICY CMP0026)
     8  #This is for copying the dll's needed by glpk (in lp_test and mip_test)
     9  CMAKE_POLICY(SET CMP0026 OLD)
     10ENDIF(POLICY CMP0026)
     11
     12SET(PROJECT_NAME "LEMON")
    1013PROJECT(${PROJECT_NAME})
    1114
     15INCLUDE(FindPythonInterp)
     16INCLUDE(FindWget)
     17
     18IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     19  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     20ELSEIF(DEFINED ENV{LEMON_VERSION})
     21  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
     22ELSE()
     23  EXECUTE_PROCESS(
     24    COMMAND
     25    hg log -r. --template "{latesttag}"
     26    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     27    OUTPUT_VARIABLE HG_REVISION_TAG
     28    ERROR_QUIET
     29    OUTPUT_STRIP_TRAILING_WHITESPACE
     30  )
     31  EXECUTE_PROCESS(
     32    COMMAND
     33    hg log -r. --template "{latesttagdistance}"
     34    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     35    OUTPUT_VARIABLE HG_REVISION_DIST
     36    ERROR_QUIET
     37    OUTPUT_STRIP_TRAILING_WHITESPACE
     38  )
     39  EXECUTE_PROCESS(
     40    COMMAND
     41    hg log -r. --template "{node|short}"
     42    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     43    OUTPUT_VARIABLE HG_REVISION_ID
     44    ERROR_QUIET
     45    OUTPUT_STRIP_TRAILING_WHITESPACE
     46  )
     47
     48  IF(HG_REVISION_TAG STREQUAL "")
     49    SET(HG_REVISION_ID "hg-tip")
     50  ELSE()
     51    IF(HG_REVISION_TAG STREQUAL "null")
     52      SET(HG_REVISION_TAG "trunk")
     53    ELSEIF(HG_REVISION_TAG MATCHES "^r")
     54      STRING(SUBSTRING ${HG_REVISION_TAG} 1 -1 HG_REVISION_TAG)
     55    ENDIF()
     56    IF(HG_REVISION_DIST STREQUAL "0")
     57      SET(HG_REVISION ${HG_REVISION_TAG})
     58    ELSE()
     59      SET(HG_REVISION
     60        "${HG_REVISION_TAG}+${HG_REVISION_DIST}-${HG_REVISION_ID}")
     61    ENDIF()
     62  ENDIF()
     63
     64  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     65ENDIF()
     66
     67SET(PROJECT_VERSION ${LEMON_VERSION})
     68
    1269SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    1370
    14 INCLUDE(FindDoxygen)
    15 INCLUDE(FindGhostscript)
    16 FIND_PACKAGE(GLPK 4.33)
    17 
    18 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     71FIND_PACKAGE(Doxygen)
     72FIND_PACKAGE(Ghostscript)
     73
     74IF(WIN32)
     75  SET(LEMON_WIN32 TRUE)
     76ENDIF(WIN32)
     77
     78SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
     79SET(LEMON_ENABLE_ILOG YES CACHE STRING "Enable ILOG (CPLEX) solver backend.")
     80SET(LEMON_ENABLE_COIN YES CACHE STRING "Enable COIN solver backend.")
     81SET(LEMON_ENABLE_SOPLEX YES CACHE STRING "Enable SoPlex solver backend.")
     82
     83IF(LEMON_ENABLE_GLPK)
     84  FIND_PACKAGE(GLPK 4.33)
     85ENDIF(LEMON_ENABLE_GLPK)
     86IF(LEMON_ENABLE_ILOG)
     87  FIND_PACKAGE(ILOG)
     88ENDIF(LEMON_ENABLE_ILOG)
     89IF(LEMON_ENABLE_COIN)
     90  FIND_PACKAGE(COIN)
     91ENDIF(LEMON_ENABLE_COIN)
     92IF(LEMON_ENABLE_SOPLEX)
     93  FIND_PACKAGE(SOPLEX)
     94ENDIF(LEMON_ENABLE_SOPLEX)
     95
     96IF(GLPK_FOUND)
     97  SET(LEMON_HAVE_LP TRUE)
     98  SET(LEMON_HAVE_MIP TRUE)
     99  SET(LEMON_HAVE_GLPK TRUE)
     100ENDIF(GLPK_FOUND)
     101IF(ILOG_FOUND)
     102  SET(LEMON_HAVE_LP TRUE)
     103  SET(LEMON_HAVE_MIP TRUE)
     104  SET(LEMON_HAVE_CPLEX TRUE)
     105ENDIF(ILOG_FOUND)
     106IF(COIN_FOUND)
     107  SET(LEMON_HAVE_LP TRUE)
     108  SET(LEMON_HAVE_MIP TRUE)
     109  SET(LEMON_HAVE_CLP TRUE)
     110  SET(LEMON_HAVE_CBC TRUE)
     111ENDIF(COIN_FOUND)
     112IF(SOPLEX_FOUND)
     113  SET(LEMON_HAVE_LP TRUE)
     114  SET(LEMON_HAVE_SOPLEX TRUE)
     115ENDIF(SOPLEX_FOUND)
     116
     117IF(ILOG_FOUND)
     118  SET(DEFAULT_LP "CPLEX")
     119  SET(DEFAULT_MIP "CPLEX")
     120ELSEIF(COIN_FOUND)
     121  SET(DEFAULT_LP "CLP")
     122  SET(DEFAULT_MIP "CBC")
     123ELSEIF(GLPK_FOUND)
     124  SET(DEFAULT_LP "GLPK")
     125  SET(DEFAULT_MIP "GLPK")
     126ELSEIF(SOPLEX_FOUND)
     127  SET(DEFAULT_LP "SOPLEX")
     128ENDIF()
     129
     130IF(NOT LEMON_DEFAULT_LP OR
     131    (NOT ILOG_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CPLEX")) OR
     132    (NOT COIN_FOUND AND (LEMON_DEFAULT_LP STREQUAL "CLP")) OR
     133    (NOT GLPK_FOUND AND (LEMON_DEFAULT_LP STREQUAL "GLPK")) OR
     134    (NOT SOPLEX_FOUND AND (LEMON_DEFAULT_LP STREQUAL "SOPLEX")))
     135  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     136    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
     137ELSE()
     138  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     139    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
     140ENDIF()
     141IF(NOT LEMON_DEFAULT_MIP OR
     142    (NOT ILOG_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CPLEX")) OR
     143    (NOT COIN_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "CBC")) OR
     144    (NOT GLPK_FOUND AND (LEMON_DEFAULT_MIP STREQUAL "GLPK")))
     145  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     146    "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
     147ELSE()
     148  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     149    "Default MIP solver backend (GLPK, CPLEX or CBC)")
     150ENDIF()
     151
     152
     153IF(DEFINED ENV{LEMON_CXX_WARNING})
     154  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     155ELSE()
     156  IF(CMAKE_COMPILER_IS_GNUCXX)
     157    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")
     158    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     159    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     160  ELSEIF(MSVC)
     161    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     162    # Still kept as an example.
     163
     164    # SET(CXX_WARNING "/wd4250 /wd4267 /wd4355 /wd4503 /wd4800 /wd4996")
     165
     166    # Suppressed warnings:
     167    # C4250: 'class1' : inherits 'class2::member' via dominance
     168    # C4267: conversion from 'size_t' to 'type', possible loss of data
     169    # C4355: 'this' : used in base member initializer list
     170    # C4503: 'function' : decorated name length exceeded, name was truncated
     171    # C4800: 'type' : forcing value to bool 'true' or 'false'
     172    #        (performance warning)
     173    # C4996: 'function': was declared deprecated
     174  ELSE()
     175    SET(CXX_WARNING "-Wall")
     176  ENDIF()
     177ENDIF()
     178SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     179
     180SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    19181
    20182IF(MSVC)
    21   SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
    22 # Suppressed warnings:
    23 # C4250: 'class1' : inherits 'class2::member' via dominance
    24 # C4355: 'this' : used in base member initializer list
    25 # C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
    26 # C4996: 'function': was declared deprecated
    27 ENDIF(MSVC)
    28 
    29 IF(GLPK_FOUND)
    30   SET(HAVE_LP TRUE)
    31   SET(HAVE_MIP TRUE)
    32   SET(HAVE_GLPK TRUE)
    33 ENDIF(GLPK_FOUND)
     183  SET(CMAKE_CXX_FLAGS "/bigobj ${CMAKE_CXX_FLAGS}")
     184  SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     185    "Flags used by the C++ compiler during maintainer builds."
     186    )
     187  SET( CMAKE_C_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     188    "Flags used by the C compiler during maintainer builds."
     189    )
     190  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     191    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     192    "Flags used for linking binaries during maintainer builds."
     193    )
     194  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     195    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     196    "Flags used by the shared libraries linker during maintainer builds."
     197    )
     198ELSE()
     199  SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     200    "Flags used by the C++ compiler during maintainer builds."
     201    )
     202  SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     203    "Flags used by the C compiler during maintainer builds."
     204    )
     205  SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     206    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     207    "Flags used for linking binaries during maintainer builds."
     208    )
     209  SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     210    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     211    "Flags used by the shared libraries linker during maintainer builds."
     212    )
     213ENDIF()
     214
     215MARK_AS_ADVANCED(
     216    CMAKE_CXX_FLAGS_MAINTAINER
     217    CMAKE_C_FLAGS_MAINTAINER
     218    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     219    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     220
     221IF(CMAKE_CONFIGURATION_TYPES)
     222  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     223  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     224  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     225      "Add the configurations that we need"
     226      FORCE)
     227 endif()
     228
     229IF(NOT CMAKE_BUILD_TYPE)
     230  SET(CMAKE_BUILD_TYPE "Release")
     231ENDIF()
     232
     233SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     234    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     235    FORCE )
     236
    34237
    35238INCLUDE(CheckTypeSize)
    36239CHECK_TYPE_SIZE("long long" LONG_LONG)
     240SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     241
     242INCLUDE(FindThreads)
     243
     244IF(NOT LEMON_THREADING)
     245  IF(CMAKE_USE_PTHREADS_INIT)
     246    SET(LEMON_THREADING "Pthread")
     247  ELSEIF(CMAKE_USE_WIN32_THREADS_INIT)
     248    SET(LEMON_THREADING "Win32")
     249  ELSE()
     250    SET(LEMON_THREADING "None")
     251  ENDIF()
     252ENDIF()
     253
     254SET( LEMON_THREADING "${LEMON_THREADING}" CACHE STRING
     255  "Choose the threading library, options are: Pthread Win32 None."
     256  FORCE )
     257
     258IF(LEMON_THREADING STREQUAL "Pthread")
     259  SET(LEMON_USE_PTHREAD TRUE)
     260ELSEIF(LEMON_THREADING STREQUAL "Win32")
     261  SET(LEMON_USE_WIN32_THREADS TRUE)
     262ENDIF()
    37263
    38264ENABLE_TESTING()
     265
     266IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     267  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     268ELSE()
     269  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     270ENDIF()
    39271
    40272ADD_SUBDIRECTORY(lemon)
    41273IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     274  ADD_SUBDIRECTORY(contrib)
    42275  ADD_SUBDIRECTORY(demo)
    43276  ADD_SUBDIRECTORY(tools)
    44277  ADD_SUBDIRECTORY(doc)
    45278  ADD_SUBDIRECTORY(test)
    46 ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    47 
     279ENDIF()
     280
     281CONFIGURE_FILE(
     282  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     283  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     284  @ONLY
     285)
     286IF(UNIX)
     287  INSTALL(
     288    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     289    DESTINATION share/lemon/cmake
     290  )
     291ELSEIF(WIN32)
     292  INSTALL(
     293    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     294    DESTINATION cmake
     295  )
     296ENDIF()
     297
     298CONFIGURE_FILE(
     299  ${PROJECT_SOURCE_DIR}/cmake/version.cmake.in
     300  ${PROJECT_BINARY_DIR}/cmake/version.cmake
     301  @ONLY
     302)
     303
     304SET(ARCHIVE_BASE_NAME ${CMAKE_PROJECT_NAME})
     305STRING(TOLOWER ${ARCHIVE_BASE_NAME} ARCHIVE_BASE_NAME)
     306SET(ARCHIVE_NAME ${ARCHIVE_BASE_NAME}-${PROJECT_VERSION})
     307ADD_CUSTOM_TARGET(dist
     308  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     309  COMMAND hg archive ${ARCHIVE_NAME}
     310  COMMAND cmake -E copy cmake/version.cmake ${ARCHIVE_NAME}/cmake/version.cmake
     311  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_NAME}
     312  COMMAND zip -r ${ARCHIVE_BASE_NAME}-nodoc-${PROJECT_VERSION}.zip ${ARCHIVE_NAME}
     313  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_NAME}/doc/html
     314  COMMAND tar -czf ${ARCHIVE_NAME}.tar.gz ${ARCHIVE_NAME}
     315  COMMAND zip -r ${ARCHIVE_NAME}.zip ${ARCHIVE_NAME}
     316  COMMAND cmake -E copy_directory doc/html ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     317  COMMAND tar -czf ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.tar.gz ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     318  COMMAND zip -r ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}.zip ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     319  COMMAND cmake -E remove_directory ${ARCHIVE_NAME}
     320  COMMAND cmake -E remove_directory ${ARCHIVE_BASE_NAME}-doc-${PROJECT_VERSION}
     321  DEPENDS html
     322  WORKING_DIRECTORY ${PROJECT_BINARY_DIR})
     323
     324# CPACK config (Basically for NSIS)
    48325IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    49   IF(WIN32)
    50     SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    51     SET(CPACK_PACKAGE_VENDOR "EGRES")
    52     SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    53       "LEMON - Library of Efficient Models and Optimization in Networks")
    54     SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    55 
    56     SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    57 
    58     SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    59       "${PROJECT_NAME} ${PROJECT_VERSION}")
    60     SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    61       "${PROJECT_NAME} ${PROJECT_VERSION}")
    62 
    63     SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    64 
    65     SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    66     SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    67     SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    68     SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    69 
    70     SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    71       "C++ header files")
    72     SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    73       "DLL and import library")
    74     SET(CPACK_COMPONENT_BIN_DESCRIPTION
    75       "Command line utilities")
    76     SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    77       "Doxygen generated documentation")
    78 
    79     SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    80 
    81     SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    82     SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    83     SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    84 
    85     SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    86       "Components needed to develop software using LEMON")
    87     SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    88       "Documentation of LEMON")
    89 
    90     SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    91 
    92     SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    93     SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    94     SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    95 
    96     SET(CPACK_GENERATOR "NSIS")
    97     SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
    98     SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    99     #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    100     SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    101     SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
    102     SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
    103     SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
    104     SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    105     SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    106       CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    107       ")
    108     SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
    109       !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
    110       Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
    111       ")
    112 
    113     INCLUDE(CPack)
    114   ENDIF(WIN32)
    115 ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     326  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     327  SET(CPACK_PACKAGE_VENDOR "EGRES")
     328  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     329    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     330  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
     331
     332  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     333
     334  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     335    "${PROJECT_NAME} ${PROJECT_VERSION}")
     336  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     337    "${PROJECT_NAME} ${PROJECT_VERSION}")
     338
     339  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     340
     341  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     342  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     343  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     344  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     345
     346  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     347    "C++ header files")
     348  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     349    "DLL and import library")
     350  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     351    "Command line utilities")
     352  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     353    "Doxygen generated documentation")
     354
     355  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     356
     357  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     358  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     359  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     360
     361  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     362    "Components needed to develop software using LEMON")
     363  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     364    "Documentation of LEMON")
     365
     366  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     367
     368  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     369  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     370  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     371
     372  SET(CPACK_GENERATOR "NSIS")
     373  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     374  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     375  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     376  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     377  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     378  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     379  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     380  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     381  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     382    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     383    ")
     384  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     385    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     386    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     387    ")
     388
     389  INCLUDE(CPack)
     390ENDIF()
  • INSTALL

    r526 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 and demo subdirectories
    31       when enabled.
     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-demo
     75-DCMAKE_BUILD_TYPE=[Release|Debug|Maintainer|...]
    7976
    80    Build the examples in the demo subdirectory.
     77  This sets the compiler options. The choices are the following
    8178
    82 --disable-demo
     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 examples in the demo subdirectory (default).
     83  'Debug': Optimization is turned off and debug info is added (-O0
     84    -ggdb with gcc). If is recommended during the development.
    8585
    86 --enable-tools
     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    Build the programs in the tools subdirectory (default).
     91  'RelWithDebInfo': Optimized build with debug info.
    8992
    90 --disable-tools
     93  'MinSizeRel': Size optimized build (-Os with gcc)
    9194
    92    Do not build the programs in the tools subdirectory.
     95-DTEST_WITH_VALGRIND=YES
    9396
    94 --with-glpk[=PREFIX]
     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.
    9599
    96    Enable GLPK support (default). You should specify the prefix too if
    97    you installed GLPK to some non-standard location (e.g. your home
    98    directory). If it is not found, GLPK support will be disabled.
     100-DCMAKE_CXX_COMPILER=path-to-compiler
    99101
    100 --with-glpk-includedir=DIR
     102  Change the compiler to be used.
    101103
    102    The directory where the GLPK header files are located. This is only
    103    useful when the GLPK headers and libraries are not under the same
    104    prefix (which is unlikely).
     104-DBUILD_SHARED_LIBS=TRUE
    105105
    106 --with-glpk-libdir=DIR
     106  Build shared library instead of static one. Think twice if you
     107  really want to use this option.
    107108
    108    The directory where the GLPK libraries are located. This is only
    109    useful when the GLPK headers and libraries are not under the same
    110    prefix (which is unlikely).
     109-DLEMON_DOC_SOURCE_BROWSER=YES
    111110
    112 --without-glpk
     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.
    113114
    114    Disable GLPK support.
     115-DLEMON_DOC_USE_MATHJAX=YES
    115116
    116 --with-cplex[=PREFIX]
     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.
    117121
    118    Enable CPLEX support (default). You should specify the prefix too
    119    if you installed CPLEX to some non-standard location
    120    (e.g. /opt/ilog/cplex75). If it is not found, CPLEX support will be
    121    disabled.
     122  On the other hand, it needs either Internet access or a locally
     123  installed version of MathJax to properly render the doc.
    122124
    123 --with-cplex-includedir=DIR
     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.
    124133
    125    The directory where the CPLEX header files are located. This is
    126    only useful when the CPLEX headers and libraries are not under the
    127    same prefix (e.g.  /usr/local/cplex/cplex75/include).
     134  See http://docs.mathjax.org/en/latest/installation.html for more details.
    128135
    129 --with-cplex-libdir=DIR
     136 
     137-DLEMON_ENABLE_GLPK=NO
     138-DLEMON_ENABLE_COIN=NO
     139-DLEMON_ENABLE_ILOG=NO
    130140
    131    The directory where the CPLEX libraries are located. This is only
    132    useful when the CPLEX headers and libraries are not under the same
    133    prefix (e.g.
    134    /usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_pic_mt).
     141  Enable optional third party libraries. They are all enabled by default.
    135142
    136 --without-cplex
     143-DLEMON_DEFAULT_LP=GLPK
    137144
    138    Disable CPLEX support.
     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.
    139148
    140 --with-soplex[=PREFIX]
     149-DLEMON_DEFAULT_MIP=GLPK
    141150
    142    Enable SoPlex support (default). You should specify the prefix too if
    143    you installed SoPlex to some non-standard location (e.g. your home
    144    directory). If it is not found, SoPlex support will be disabled.
     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.
    145154
    146 --with-soplex-includedir=DIR
     155-DGLPK_ROOT_DIR=DIRECTORY
     156-DCOIN_ROOT_DIR=DIRECTORY
     157-DILOG_ROOT_DIR=DIRECTORY
    147158
    148    The directory where the SoPlex header files are located. This is only
    149    useful when the SoPlex headers and libraries are not under the same
    150    prefix (which is unlikely).
     159  Root directory prefixes of optional third party libraries.
    151160
    152 --with-soplex-libdir=DIR
     161Makefile Variables
     162==================
    153163
    154    The directory where the SoPlex libraries are located. This is only
    155    useful when the SoPlex headers and libraries are not under the same
    156    prefix (which is unlikely).
     164make VERBOSE=1
    157165
    158 --without-soplex
    159 
    160    Disable SoPlex 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

    r534 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
     1792009-05-13 Version 1.1 released
     180
     181        This is the second stable release of the 1.x series. It
     182        features a better coverage of the tools available in the 0.x
     183        series, a thoroughly reworked LP/MIP interface plus various
     184        improvements in the existing tools.
     185
     186        * Much improved M$ Windows support
     187          * Various improvements in the CMAKE build system
     188          * Compilation warnings are fixed/suppressed
     189        * Support IBM xlC compiler
     190        * New algorithms
     191          * Connectivity related algorithms (#61)
     192          * Euler walks (#65)
     193          * Preflow push-relabel max. flow algorithm (#176)
     194          * Circulation algorithm (push-relabel based) (#175)
     195          * Suurballe algorithm (#47)
     196          * Gomory-Hu algorithm (#66)
     197          * Hao-Orlin algorithm (#58)
     198          * Edmond's maximum cardinality and weighted matching algorithms
     199            in general graphs (#48,#265)
     200          * Minimum cost arborescence/branching (#60)
     201          * Network Simplex min. cost flow algorithm (#234)
     202        * New data structures
     203          * Full graph structure (#57)
     204          * Grid graph structure (#57)
     205          * Hypercube graph structure (#57)
     206          * Graph adaptors (#67)
     207          * ArcSet and EdgeSet classes (#67)
     208          * Elevator class (#174)
     209        * Other new tools
     210          * LP/MIP interface (#44)
     211            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
     212          * Reader for the Nauty file format (#55)
     213          * DIMACS readers (#167)
     214          * Radix sort algorithms (#72)
     215          * RangeIdMap and CrossRefMap (#160)
     216        * New command line tools
     217          * DIMACS to LGF converter (#182)
     218          * lgf-gen - a graph generator (#45)
     219          * DIMACS solver utility (#226)
     220        * Other code improvements
     221          * Lognormal distribution added to Random (#102)
     222          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
     223          * The standard maps of graphs are guaranteed to be
     224            reference maps (#190)
     225        * Miscellaneous
     226          * Various doc improvements
     227          * Improved 0.x -> 1.x converter script
     228
     229        * Several bugfixes (compared to release 1.0):
     230          #170: Bugfix SmartDigraph::split()
     231          #171: Bugfix in SmartGraph::restoreSnapshot()
     232          #172: Extended test cases for graphs and digraphs
     233          #173: Bugfix in Random
     234                * operator()s always return a double now
     235                * the faulty real<Num>(Num) and real<Num>(Num,Num)
     236                  have been removed
     237          #187: Remove DijkstraWidestPathOperationTraits
     238          #61:  Bugfix in DfsVisit
     239          #193: Bugfix in GraphReader::skipSection()
     240          #195: Bugfix in ConEdgeIt()
     241          #197: Bugfix in heap unionfind
     242                * This bug affects Edmond's general matching algorithms
     243          #207: Fix 'make install' without 'make html' using CMAKE
     244          #208: Suppress or fix VS2008 compilation warnings
     245          ----: Update the LEMON icon
     246          ----: Enable the component-based installer
     247                (in installers made by CPACK)
     248          ----: Set the proper version for CMAKE in the tarballs
     249                (made by autotools)
     250          ----: Minor clarification in the LICENSE file
     251          ----: Add missing unistd.h include to time_measure.h
     252          #204: Compilation bug fixed in graph_to_eps.h with VS2005
     253          #214,#215: windows.h should never be included by LEMON headers
     254          #230: Build systems check the availability of 'long long' type
     255          #229: Default implementation of Tolerance<> is used for integer types
     256          #211,#212: Various fixes for compiling on AIX
     257          ----: Improvements in CMAKE config
     258                - docs is installed in share/doc/
     259                - detects newer versions of Ghostscript
     260          #239: Fix missing 'inline' specifier in time_measure.h
     261          #274,#280: Install lemon/config.h
     262          #275: Prefix macro names with LEMON_ in lemon/config.h
     263          ----: Small script for making the release tarballs added
     264          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     265
    12662009-03-27 LEMON joins to the COIN-OR initiative
    2267
     
    82732008-10-13 Version 1.0 released
    9274
    10         This is the first stable release of LEMON. Compared to the 0.x
    11         release series, it features a considerably smaller but more
    12         matured set of tools. The API has also completely revised and
    13         changed in several places.
    14 
    15         * 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
    16281          Migration Guide in the doc for more details)
    17282          * Graph -> Digraph, UGraph -> Graph
    18283          * Edge -> Arc, UEdge -> Edge
    19           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
    20         * Other improvements
    21           * Better documentation
    22           * Reviewed and cleaned up codebase
    23           * CMake based build system (along with the autotools based one)
    24         * Contents of the library (ported from 0.x)
    25           * Algorithms
    26             * breadth-first search (bfs.h)
    27             * depth-first search (dfs.h)
    28             * Dijkstra's algorithm (dijkstra.h)
    29             * Kruskal's algorithm (kruskal.h)
    30           * Data structures
    31             * graph data structures (list_graph.h, smart_graph.h)
    32             * path data structures (path.h)
    33             * binary heap data structure (bin_heap.h)
    34             * union-find data structures (unionfind.h)
    35             * miscellaneous property maps (maps.h)
    36             * 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)
    37302          * Concepts
    38             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     303            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    39304              concepts/graph_components.h)
    40             * concepts for other structures (concepts/heap.h, concepts/maps.h,
    41               concepts/path.h)
    42           * Tools
    43             * Mersenne twister random number generator (random.h)
    44             * tools for measuring cpu and wall clock time (time_measure.h)
    45             * tools for counting steps and events (counter.h)
    46             * tool for parsing command line arguments (arg_parser.h)
    47             * tool for visualizing graphs (graph_to_eps.h)
    48             * 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
    49314              (lgf_reader.h, lgf_writer.h)
    50315            * tools to handle the anomalies of calculations with
    51               floating point numbers (tolerance.h)
     316              floating point numbers (tolerance.h)
    52317            * tools to manage RGB colors (color.h)
    53           * Infrastructure
    54             * extended assertion handling (assert.h)
    55             * exception classes and error handling (error.h)
    56             * concept checking (concept_check.h)
    57             * 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

    r318 r921  
    1 ==================================================================
    2 LEMON - a Library of Efficient Models and Optimization in Networks
    3 ==================================================================
     1=====================================================================
     2LEMON - a Library for Efficient Modeling and Optimization in Networks
     3=====================================================================
    44
    55LEMON is an open source library written in C++. It provides
     
    1717
    1818   Copying, distribution and modification conditions and terms.
     19
     20NEWS
     21
     22   News and version history.
    1923
    2024INSTALL
     
    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/FindGLPK.cmake

    r496 r1232  
     1SET(GLPK_ROOT_DIR "" CACHE PATH "GLPK root directory")
     2
    13SET(GLPK_REGKEY "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GnuWin32\\Glpk;InstallPath]")
    24GET_FILENAME_COMPONENT(GLPK_ROOT_PATH ${GLPK_REGKEY} ABSOLUTE)
     
    46FIND_PATH(GLPK_INCLUDE_DIR
    57  glpk.h
    6   PATHS ${GLPK_REGKEY}/include)
     8  PATHS ${GLPK_REGKEY}/include
     9  HINTS ${GLPK_ROOT_DIR}/include
     10)
     11FIND_LIBRARY(GLPK_LIBRARY
     12  glpk
     13  PATHS ${GLPK_REGKEY}/lib
     14  HINTS ${GLPK_ROOT_DIR}/lib
     15)
    716
    8 FIND_LIBRARY(GLPK_LIBRARY
    9   NAMES glpk
    10   PATHS ${GLPK_REGKEY}/lib)
     17IF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
     18  FILE(READ ${GLPK_INCLUDE_DIR}/glpk.h GLPK_GLPK_H)
     19
     20  STRING(REGEX MATCH "define[ ]+GLP_MAJOR_VERSION[ ]+[0-9]+" GLPK_MAJOR_VERSION_LINE "${GLPK_GLPK_H}")
     21  STRING(REGEX REPLACE "define[ ]+GLP_MAJOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MAJOR "${GLPK_MAJOR_VERSION_LINE}")
     22
     23  STRING(REGEX MATCH "define[ ]+GLP_MINOR_VERSION[ ]+[0-9]+" GLPK_MINOR_VERSION_LINE "${GLPK_GLPK_H}")
     24  STRING(REGEX REPLACE "define[ ]+GLP_MINOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MINOR "${GLPK_MINOR_VERSION_LINE}")
     25
     26  SET(GLPK_VERSION_STRING "${GLPK_VERSION_MAJOR}.${GLPK_VERSION_MINOR}")
     27
     28  IF(GLPK_FIND_VERSION)
     29    IF(GLPK_FIND_VERSION_COUNT GREATER 2)
     30      MESSAGE(SEND_ERROR "unexpected version string")
     31    ENDIF(GLPK_FIND_VERSION_COUNT GREATER 2)
     32
     33    MATH(EXPR GLPK_REQUESTED_VERSION "${GLPK_FIND_VERSION_MAJOR}*100 + ${GLPK_FIND_VERSION_MINOR}")
     34    MATH(EXPR GLPK_FOUND_VERSION "${GLPK_VERSION_MAJOR}*100 + ${GLPK_VERSION_MINOR}")
     35
     36    IF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     37      SET(GLPK_PROPER_VERSION_FOUND FALSE)
     38    ELSE(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     39      SET(GLPK_PROPER_VERSION_FOUND TRUE)
     40    ENDIF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     41  ELSE(GLPK_FIND_VERSION)
     42    SET(GLPK_PROPER_VERSION_FOUND TRUE)
     43  ENDIF(GLPK_FIND_VERSION)
     44ENDIF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
    1145
    1246INCLUDE(FindPackageHandleStandardArgs)
    13 FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR)
     47FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_PROPER_VERSION_FOUND)
    1448
    1549IF(GLPK_FOUND)
     50  SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR})
    1651  SET(GLPK_LIBRARIES ${GLPK_LIBRARY})
    1752  SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin)
  • cmake/version.cmake.in

    r503 r1135  
    1 SET(PROJECT_NAME "@PACKAGE_NAME@")
    2 SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
     1SET(LEMON_VERSION "@LEMON_VERSION@" CACHE STRING "LEMON version string.")
  • demo/CMakeLists.txt

    r596 r726  
    44)
    55
    6 LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(
     7  ${PROJECT_BINARY_DIR}/lemon
     8)
    79
    810SET(DEMOS
    911  arg_parser_demo
    1012  graph_to_eps_demo
    11   lgf_demo)
     13  lgf_demo
     14)
    1215
    1316FOREACH(DEMO_NAME ${DEMOS})
    1417  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
    1518  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
    16 ENDFOREACH(DEMO_NAME)
     19ENDFOREACH()
  • 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
  • demo/graph_to_eps_demo.cc

    r463 r659  
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(sqrt(double(palette.size())));
     185  int cols=int(std::sqrt(double(palette.size())));
    186186  for(int i=0;i<int(paletteW.size());i++) {
    187187    Node n=h.addNode();
  • doc/CMakeLists.txt

    r596 r1251  
    44SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
     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
     14
    615CONFIGURE_FILE(
    716  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    817  ${PROJECT_BINARY_DIR}/doc/Doxyfile
    9   @ONLY)
     18  @ONLY
     19)
    1020
    11 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     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
     36IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    1237  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     38  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     39  ADD_CUSTOM_TARGET(html
     40    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
     41    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
     42    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r20 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     43    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/adaptors2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/adaptors2.eps
     44    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     45    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     46    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     47    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     48    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r32 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     49    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     50    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     51    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r40 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     52    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r24 -sOutputFile=gen-images/tsp.png ${CMAKE_CURRENT_SOURCE_DIR}/images/tsp.eps
     53    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     54    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     55    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     56    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     57    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     58    COMMAND ${CMAKE_COMMAND} -E remove_directory html
     59    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     60    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     61  )
     62
     63  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     64
    1365  IF(UNIX)
    14     ADD_CUSTOM_TARGET(html
    15       COMMAND rm -rf gen-images
    16       COMMAND mkdir gen-images
    17       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    18       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    19       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    20       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    21       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    22       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    23       COMMAND rm -rf html
    24       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    25       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
     66    INSTALL(
     67      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     68      DESTINATION share/doc/lemon/html
     69      COMPONENT html_documentation
     70    )
    2671  ELSEIF(WIN32)
    27     ADD_CUSTOM_TARGET(html
    28       COMMAND if exist gen-images rmdir /s /q gen-images
    29       COMMAND mkdir gen-images
    30       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    31       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    32       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    33       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    34       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    35       COMMAND if exist html rmdir /s /q html
    36       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    37       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
    38   ENDIF(UNIX)
    39   INSTALL(
    40     DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    41     DESTINATION share/doc
    42     COMPONENT html_documentation)
    43 ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     72    INSTALL(
     73      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     74      DESTINATION doc
     75      COMPONENT html_documentation
     76    )
     77  ENDIF()
     78
     79ENDIF()
     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

    r379 r1251  
    1 # Doxyfile 1.5.7.1
     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
     
    2224QT_AUTOBRIEF           = NO
    2325MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2526INHERIT_DOCS           = NO
    2627SEPARATE_MEMBER_PAGES  = NO
     
    3132OPTIMIZE_FOR_FORTRAN   = NO
    3233OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3335BUILTIN_STL_SUPPORT    = YES
    3436CPP_CLI_SUPPORT        = NO
     
    5658HIDE_SCOPE_NAMES       = YES
    5759SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5861INLINE_INFO            = YES
    5962SORT_MEMBER_DOCS       = NO
    6063SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6165SORT_GROUP_NAMES       = NO
    6266SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6368GENERATE_TODOLIST      = YES
    6469GENERATE_TESTLIST      = YES
     
    7277SHOW_NAMESPACES        = YES
    7378FILE_VERSION_FILTER    =
    74 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     80CITE_BIB_FILES         = "@abs_top_srcdir@/doc/references.bib"
    7581#---------------------------------------------------------------------------
    7682# configuration options related to warning and progress messages
     
    9197                         "@abs_top_srcdir@/lemon/concepts" \
    9298                         "@abs_top_srcdir@/demo" \
     99                         "@abs_top_srcdir@/contrib" \
    93100                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     101                         "@abs_top_srcdir@/test/test_tools.h" \
     102                         "@abs_top_builddir@/doc/mainpage.dox"
    95103INPUT_ENCODING         = UTF-8
    96104FILE_PATTERNS          = *.h \
     
    112120FILTER_PATTERNS        =
    113121FILTER_SOURCE_FILES    = NO
     122FILTER_SOURCE_PATTERNS =
    114123#---------------------------------------------------------------------------
    115124# configuration options related to source browsing
    116125#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     126SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118127INLINE_SOURCES         = NO
    119128STRIP_CODE_COMMENTS    = YES
     
    138147HTML_FOOTER            =
    139148HTML_STYLESHEET        =
     149HTML_COLORSTYLE_HUE    = 220
     150HTML_COLORSTYLE_SAT    = 100
     151HTML_COLORSTYLE_GAMMA  = 80
     152HTML_TIMESTAMP         = YES
    140153HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     154HTML_DYNAMIC_SECTIONS  = YES
    142155GENERATE_DOCSET        = NO
    143156DOCSET_FEEDNAME        = "Doxygen generated docs"
    144157DOCSET_BUNDLE_ID       = org.doxygen.Project
     158DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     159DOCSET_PUBLISHER_NAME  = Publisher
    145160GENERATE_HTMLHELP      = NO
    146161CHM_FILE               =
     
    154169QHP_NAMESPACE          = org.doxygen.Project
    155170QHP_VIRTUAL_FOLDER     = doc
     171QHP_CUST_FILTER_NAME   =
     172QHP_CUST_FILTER_ATTRS  =
     173QHP_SECT_FILTER_ATTRS  =
    156174QHG_LOCATION           =
     175GENERATE_ECLIPSEHELP   = NO
     176ECLIPSE_DOC_ID         = org.doxygen.Project
    157177DISABLE_INDEX          = NO
    158178ENUM_VALUES_PER_LINE   = 4
    159179GENERATE_TREEVIEW      = NO
     180USE_INLINE_TREES       = NO
    160181TREEVIEW_WIDTH         = 250
     182EXT_LINKS_IN_WINDOW    = NO
    161183FORMULA_FONTSIZE       = 10
     184FORMULA_TRANSPARENT    = YES
     185USE_MATHJAX            = @LEMON_DOC_USE_MATHJAX@
     186MATHJAX_RELPATH        = @LEMON_DOC_MATHJAX_RELPATH@
     187SEARCHENGINE           = YES
     188SERVER_BASED_SEARCH    = NO
    162189#---------------------------------------------------------------------------
    163190# configuration options related to the LaTeX output
     
    176203LATEX_BATCHMODE        = NO
    177204LATEX_HIDE_INDICES     = NO
     205LATEX_SOURCE_CODE      = NO
    178206#---------------------------------------------------------------------------
    179207# configuration options related to the RTF output
     
    224252SKIP_FUNCTION_MACROS   = YES
    225253#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     254# Configuration::additions related to external references
     255#---------------------------------------------------------------------------
     256TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = @LEMON_DOC_LIBSTDC++_URL@"
    229257GENERATE_TAGFILE       = html/lemon.tag
    230258ALLEXTERNALS           = NO
     
    238266HIDE_UNDOC_RELATIONS   = YES
    239267HAVE_DOT               = YES
     268DOT_NUM_THREADS        = 0
    240269DOT_FONTNAME           = FreeSans
    241270DOT_FONTSIZE           = 10
     
    255284DOT_PATH               =
    256285DOTFILE_DIRS           =
     286MSCFILE_DIRS           =
    257287DOT_GRAPH_MAX_NODES    = 50
    258288MAX_DOT_GRAPH_DEPTH    = 0
     
    261291GENERATE_LEGEND        = YES
    262292DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

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

    r463 r1270  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9999\subsection pri-loc-var Private member variables
    100100
    101 Private member variables should start with underscore
     101Private member variables should start with underscore.
    102102
    103103\code
    104 _start_with_underscores
     104_start_with_underscore
    105105\endcode
    106106
  • doc/dirs.dox

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

    r606 r1271  
    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
     
    139147
    140148/**
    141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    142 @ingroup graphs
    143 \brief Graph types between real graphs and graph adaptors.
    144 
    145 This group contains some graph types between real graphs and graph adaptors.
    146 These classes wrap graphs to give new functionality as the adaptors do it.
    147 On the other hand they are not light-weight structures as the adaptors.
    148 */
    149 
    150 /**
    151149@defgroup maps Maps
    152150@ingroup datas
     
    237235
    238236/**
    239 @defgroup matrices Matrices
    240 @ingroup datas
    241 \brief Two dimensional data storages implemented in LEMON.
    242 
    243 This group contains two dimensional data storages implemented in LEMON.
    244 */
    245 
    246 /**
    247237@defgroup paths Path Structures
    248238@ingroup datas
     
    257247any kind of path structure.
    258248
    259 \sa lemon::concepts::Path
     249\sa \ref concepts::Path "Path concept"
     250*/
     251
     252/**
     253@defgroup heaps Heap Structures
     254@ingroup datas
     255\brief %Heap structures implemented in LEMON.
     256
     257This group contains the heap structures implemented in LEMON.
     258
     259LEMON provides several heap classes. They are efficient implementations
     260of the abstract data type \e priority \e queue. They store items with
     261specified values called \e priorities in such a way that finding and
     262removing the item with minimum priority are efficient.
     263The basic operations are adding and erasing items, changing the priority
     264of an item, etc.
     265
     266Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     267The heap implementations have the same interface, thus any of them can be
     268used easily in such algorithms.
     269
     270\sa \ref concepts::Heap "Heap concept"
    260271*/
    261272
     
    270281
    271282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This group contains geometric data structures implemented in LEMON.
     288
     289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     290   vector with the usual operations.
     291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     292   rectangular bounding box of a set of \ref lemon::dim2::Point
     293   "dim2::Point"'s.
     294*/
     295
     296/**
     297@defgroup matrices Matrices
     298@ingroup auxdat
     299\brief Two dimensional data storages implemented in LEMON.
     300
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    272305@defgroup algs Algorithms
    273306\brief This group contains the several algorithms
     
    284317
    285318This group contains the common graph search algorithms, namely
    286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\cite clrs01algorithms.
    287321*/
    288322
     
    292326\brief Algorithms for finding shortest paths.
    293327
    294 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\cite clrs01algorithms.
    295330
    296331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    309344
    310345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \cite clrs01algorithms.
     352*/
     353
     354/**
    311355@defgroup max_flow Maximum Flow Algorithms
    312356@ingroup algs
     
    314358
    315359This group contains the algorithms for finding maximum flows and
    316 feasible circulations.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    317361
    318362The \e maximum \e flow \e problem is to find a flow of maximum value between
    319363a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     364digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321365\f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     366A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323367following optimization problem.
    324368
    325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    327     \qquad \forall v\in V\setminus\{s,t\} \f]
    328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     369\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     370\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     371    \quad \forall u\in V\setminus\{s,t\} \f]
     372\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    329373
    330374LEMON contains several algorithms for solving maximum flow problems:
    331 - \ref EdmondsKarp Edmonds-Karp algorithm.
    332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    335 
    336 In most cases the \ref Preflow "Preflow" algorithm provides the
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \cite edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \cite goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \cite dinic70algorithm, \cite sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
    337385fastest method for computing a maximum flow. All implementations
    338 provides functions to also query the minimum cut, which is the dual
    339 problem of the maximum flow.
    340 */
    341 
    342 /**
    343 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     386also provide functions to query the minimum cut, which is the dual
     387problem of maximum flow.
     388
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
     390for finding feasible circulations, which is a somewhat different problem,
     391but it is strongly related to maximum flow.
     392For more information, see \ref Circulation.
     393*/
     394
     395/**
     396@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    344397@ingroup algs
    345398
     
    347400
    348401This group contains the algorithms for finding minimum cost flows and
    349 circulations.
    350 
    351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352 minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints and arc costs.
    354 Formally, let \f$G=(V,A)\f$ be a digraph,
    355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    356 upper bounds for the flow values on the arcs,
    357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    358 on the arcs, and
    359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    360 of the nodes.
    361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    362 the following optimization problem.
    363 
    364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    366     supply(v) \qquad \forall v\in V \f]
    367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    368 
    369 LEMON contains several algorithms for solving minimum cost flow problems:
    370  - \ref CycleCanceling Cycle-canceling algorithms.
    371  - \ref CapacityScaling Successive shortest path algorithm with optional
    372    capacity scaling.
    373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    374    cost scaling.
    375  - \ref NetworkSimplex Primal network simplex algorithm with various
    376    pivot strategies.
     402circulations \cite amo93networkflows. For more information about this
     403problem and its dual solution, see: \ref min_cost_flow
     404"Minimum Cost Flow Problem".
     405
     406LEMON contains several algorithms for this problem.
     407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
     412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     413   shortest path method \cite edmondskarp72theoretical.
     414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     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.
     424For example, if the total supply and/or capacities are rather small,
     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.
    377437*/
    378438
     
    392452
    393453\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    394     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     454    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    395455
    396456LEMON contains several algorithms related to minimum cut problems:
     
    408468
    409469/**
    410 @defgroup graph_prop Connectivity and Other Graph Properties
    411 @ingroup algs
    412 \brief Algorithms for discovering the graph properties
    413 
    414 This group contains the algorithms for discovering the graph properties
    415 like connectivity, bipartiteness, euler property, simplicity etc.
    416 
    417 \image html edge_biconnected_components.png
    418 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    419 */
    420 
    421 /**
    422 @defgroup planar Planarity Embedding and Drawing
    423 @ingroup algs
    424 \brief Algorithms for planarity checking, embedding and drawing
    425 
    426 This group contains the algorithms for planarity checking,
    427 embedding and drawing.
    428 
    429 \image html planar.png
    430 \image latex planar.eps "Plane graph" width=\textwidth
     470@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     471@ingroup algs
     472\brief Algorithms for finding minimum mean cycles.
     473
     474This group contains the algorithms for finding minimum mean cycles
     475\cite amo93networkflows, \cite karp78characterization.
     476
     477The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     478of minimum mean length (cost) in a digraph.
     479The mean length of a cycle is the average length of its arcs, i.e. the
     480ratio between the total length of the cycle and the number of arcs on it.
     481
     482This problem has an important connection to \e conservative \e length
     483\e functions, too. A length function on the arcs of a digraph is called
     484conservative if and only if there is no directed cycle of negative total
     485length. For an arbitrary length function, the negative of the minimum
     486cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     487arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     488function.
     489
     490LEMON contains three algorithms for solving the minimum mean cycle problem:
     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).
    431502*/
    432503
     
    436507\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437508
    438 This group contains algorithm objects and functions to calculate
     509This group contains the algorithms for calculating
    439510matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the arcs which does not shares common endpoints.
     511finding a subset of the edges for which each node has at most one incident
     512edge.
    441513
    442514There are several different algorithms for calculate matchings in
     
    465537  Edmond's blossom shrinking algorithm for calculating maximum weighted
    466538  perfect matching in general graphs.
    467 
    468 \image html bipartite_matching.png
    469 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    470 */
    471 
    472 /**
    473 @defgroup spantree Minimum Spanning Tree Algorithms
    474 @ingroup algs
    475 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    476 
    477 This group contains the algorithms for finding a minimum cost spanning
    478 tree in a graph.
     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
     549*/
     550
     551/**
     552@defgroup graph_properties Connectivity and Other Graph Properties
     553@ingroup algs
     554\brief Algorithms for discovering the graph properties
     555
     556This group contains the algorithms for discovering the graph properties
     557like connectivity, bipartiteness, euler property, simplicity etc.
     558
     559\image html connected_components.png
     560\image latex connected_components.eps "Connected components" width=\textwidth
     561*/
     562
     563/**
     564@defgroup planar Planar Embedding and Drawing
     565@ingroup algs
     566\brief Algorithms for planarity checking, embedding and drawing
     567
     568This group contains the algorithms for planarity checking,
     569embedding and drawing.
     570
     571\image html planar.png
     572\image latex planar.eps "Plane graph" width=\textwidth
     573*/
     574
     575/**
     576@defgroup tsp Traveling Salesman Problem
     577@ingroup algs
     578\brief Algorithms for the symmetric traveling salesman problem
     579
     580This group contains basic heuristic algorithms for the the symmetric
     581\e traveling \e salesman \e problem (TSP).
     582Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     583the problem is to find a shortest possible tour that visits each node exactly
     584once (i.e. the minimum cost Hamiltonian cycle).
     585
     586These TSP algorithms are intended to be used with a \e metric \e cost
     587\e function, i.e. the edge costs should satisfy the triangle inequality.
     588Otherwise the algorithms could yield worse results.
     589
     590LEMON provides five well-known heuristics for solving symmetric TSP:
     591 - \ref NearestNeighborTsp Neareast neighbor algorithm
     592 - \ref GreedyTsp Greedy algorithm
     593 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     594 - \ref ChristofidesTsp Christofides algorithm
     595 - \ref Opt2Tsp 2-opt algorithm
     596
     597\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     598solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     599
     600\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     601approximation factor: 3/2.
     602
     603\ref Opt2Tsp usually provides the best results in practice, but
     604it is the slowest method. It can also be used to improve given tours,
     605for example, the results of other algorithms.
     606
     607\image html tsp.png
     608\image latex tsp.eps "Traveling salesman problem" width=\textwidth
     609*/
     610
     611/**
     612@defgroup approx_algs Approximation Algorithms
     613@ingroup algs
     614\brief Approximation algorithms.
     615
     616This group contains the approximation and heuristic algorithms
     617implemented in LEMON.
     618
     619<b>Maximum Clique Problem</b>
     620  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     621    Grosso, Locatelli, and Pullan.
    479622*/
    480623
     
    486629This group contains some algorithms implemented in LEMON
    487630in order to make it easier to implement complex algorithms.
    488 */
    489 
    490 /**
    491 @defgroup approx Approximation Algorithms
    492 @ingroup algs
    493 \brief Approximation algorithms.
    494 
    495 This group contains the approximation and heuristic algorithms
    496 implemented in LEMON.
    497631*/
    498632
     
    507641
    508642/**
    509 @defgroup lp_group Lp and Mip Solvers
     643@defgroup lp_group LP and MIP Solvers
    510644@ingroup gen_opt_group
    511 \brief Lp and Mip solver interfaces for LEMON.
    512 
    513 This group contains Lp and Mip solver interfaces for LEMON. The
    514 various LP solvers could be used in the same manner with this
    515 interface.
     645\brief LP and MIP solver interfaces for LEMON.
     646
     647This group contains LP and MIP solver interfaces for LEMON.
     648Various LP solvers could be used in the same manner with this
     649high-level interface.
     650
     651The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     652\cite cplex, \cite soplex.
    516653*/
    517654
     
    600737This group contains general \c EPS drawing methods and special
    601738graph exporting tools.
    602 */
    603 
    604 /**
    605 @defgroup dimacs_group DIMACS format
     739
     740\image html graph_to_eps.png
     741*/
     742
     743/**
     744@defgroup dimacs_group DIMACS Format
    606745@ingroup io_group
    607746\brief Read and write files in DIMACS format
     
    652791\brief Skeleton and concept checking classes for graph structures
    653792
    654 This group contains the skeletons and concept checking classes of LEMON's
    655 graph structures and helper classes used to implement these.
     793This group contains the skeletons and concept checking classes of
     794graph structures.
    656795*/
    657796
     
    665804
    666805/**
     806@defgroup tools Standalone Utility Applications
     807
     808Some utility applications are listed here.
     809
     810The standard compilation procedure (<tt>./configure;make</tt>) will compile
     811them, as well.
     812*/
     813
     814/**
    667815\anchor demoprograms
    668816
     
    672820the \c demo subdirectory of the source tree.
    673821
    674 It order to compile them, use <tt>--enable-demo</tt> configure option when
    675 build the library.
    676 */
    677 
    678 /**
    679 @defgroup tools Standalone Utility Applications
    680 
    681 Some utility applications are listed here.
    682 
    683 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    684 them, as well.
     822In order to compile them, use the <tt>make demo</tt> or the
     823<tt>make check</tt> commands.
    685824*/
    686825
  • 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
  • lemon/CMakeLists.txt

    r596 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
     
    1925)
    2026
    21 IF(HAVE_GLPK)
     27IF(LEMON_HAVE_GLPK)
    2228  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    23   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     29  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
    2430  IF(WIN32)
    2531    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    2632    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    2733    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
    28   ENDIF(WIN32)
    29 ENDIF(HAVE_GLPK)
     34  ENDIF()
     35ENDIF()
     36
     37IF(LEMON_HAVE_CPLEX)
     38  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     39  INCLUDE_DIRECTORIES(${ILOG_INCLUDE_DIRS})
     40ENDIF()
     41
     42IF(LEMON_HAVE_CLP)
     43  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     44  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     45ENDIF()
     46
     47IF(LEMON_HAVE_CBC)
     48  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     49  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     50ENDIF()
     51
     52IF(LEMON_HAVE_SOPLEX)
     53  SET(LEMON_SOURCES ${LEMON_SOURCES} soplex.cc)
     54  INCLUDE_DIRECTORIES(${SOPLEX_INCLUDE_DIRS})
     55ENDIF()
    3056
    3157ADD_LIBRARY(lemon ${LEMON_SOURCES})
     58
     59TARGET_LINK_LIBRARIES(lemon
     60  ${GLPK_LIBRARIES} ${COIN_LIBRARIES} ${ILOG_LIBRARIES} ${SOPLEX_LIBRARIES}
     61  )
     62
     63IF(UNIX)
     64  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon VERSION ${LEMON_VERSION} SOVERSION ${LEMON_VERSION})
     65ENDIF()
    3266
    3367INSTALL(
    3468  TARGETS lemon
    3569  ARCHIVE DESTINATION lib
    36   COMPONENT library)
     70  LIBRARY DESTINATION lib
     71  COMPONENT library
     72)
    3773
    3874INSTALL(
     
    4076  DESTINATION include/lemon
    4177  COMPONENT headers
    42   FILES_MATCHING PATTERN "*.h")
     78  FILES_MATCHING PATTERN "*.h"
     79)
     80
     81INSTALL(
     82  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
     83  DESTINATION include/lemon
     84  COMPONENT headers
     85)
     86
     87INSTALL(
     88  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     89  DESTINATION lib/pkgconfig
     90)
     91
  • lemon/adaptors.h

    r606 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).
     
    110110    template <typename V>
    111111    class NodeMap : public DGR::template NodeMap<V> {
     112      typedef typename DGR::template NodeMap<V> Parent;
     113
    112114    public:
    113 
    114       typedef typename DGR::template NodeMap<V> Parent;
    115 
    116115      explicit NodeMap(const Adaptor& adaptor)
    117116        : Parent(*adaptor._digraph) {}
    118 
    119117      NodeMap(const Adaptor& adaptor, const V& value)
    120118        : Parent(*adaptor._digraph, value) { }
     
    135133    template <typename V>
    136134    class ArcMap : public DGR::template ArcMap<V> {
     135      typedef typename DGR::template ArcMap<V> Parent;
     136
    137137    public:
    138 
    139       typedef typename DGR::template ArcMap<V> Parent;
    140 
    141138      explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
    142139        : Parent(*adaptor._digraph) {}
    143 
    144140      ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
    145141        : Parent(*adaptor._digraph, value) {}
     
    256252    template <typename V>
    257253    class NodeMap : public GR::template NodeMap<V> {
     254      typedef typename GR::template NodeMap<V> Parent;
     255
    258256    public:
    259       typedef typename GR::template NodeMap<V> Parent;
    260257      explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
    261258        : Parent(*adapter._graph) {}
     
    278275    template <typename V>
    279276    class ArcMap : public GR::template ArcMap<V> {
     277      typedef typename GR::template ArcMap<V> Parent;
     278
    280279    public:
    281       typedef typename GR::template ArcMap<V> Parent;
    282280      explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
    283281        : Parent(*adapter._graph) {}
     
    299297    template <typename V>
    300298    class EdgeMap : public GR::template EdgeMap<V> {
     299      typedef typename GR::template EdgeMap<V> Parent;
     300
    301301    public:
    302       typedef typename GR::template EdgeMap<V> Parent;
    303302      explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
    304303        : Parent(*adapter._graph) {}
     
    322321  template <typename DGR>
    323322  class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
     323    typedef DigraphAdaptorBase<DGR> Parent;
    324324  public:
    325325    typedef DGR Digraph;
    326     typedef DigraphAdaptorBase<DGR> Parent;
    327326  protected:
    328327    ReverseDigraphBase() : Parent() { }
     
    361360  /// by adding or removing nodes or arcs, unless the \c GR template
    362361  /// parameter is set to be \c const.
     362  ///
     363  /// This class provides item counting in the same time as the adapted
     364  /// digraph structure.
    363365  ///
    364366  /// \tparam DGR The type of the adapted digraph.
     
    375377    public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
    376378#endif
     379    typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    377380  public:
    378381    /// The type of the adapted digraph.
    379382    typedef DGR Digraph;
    380     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
    381383  protected:
    382384    ReverseDigraph() { }
     
    404406  template <typename DGR, typename NF, typename AF, bool ch = true>
    405407  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
     408    typedef DigraphAdaptorBase<DGR> Parent;
    406409  public:
    407410    typedef DGR Digraph;
     
    410413
    411414    typedef SubDigraphBase Adaptor;
    412     typedef DigraphAdaptorBase<DGR> Parent;
    413415  protected:
    414416    NF* _node_filter;
     
    420422      Parent::initialize(digraph);
    421423      _node_filter = &node_filter;
    422       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    423425    }
    424426
     
    507509
    508510    template <typename V>
    509     class NodeMap
    510       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    511               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>)> {
     514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     516
    512517    public:
    513518      typedef V Value;
    514       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515             LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516519
    517520      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     
    533536
    534537    template <typename V>
    535     class ArcMap 
     538    class ArcMap
    536539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     543
    538544    public:
    539545      typedef V Value;
    540       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    541         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    542546
    543547      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
     
    563567  class SubDigraphBase<DGR, NF, AF, false>
    564568    : public DigraphAdaptorBase<DGR> {
     569    typedef DigraphAdaptorBase<DGR> Parent;
    565570  public:
    566571    typedef DGR Digraph;
     
    569574
    570575    typedef SubDigraphBase Adaptor;
    571     typedef DigraphAdaptorBase<Digraph> Parent;
    572576  protected:
    573577    NF* _node_filter;
     
    579583      Parent::initialize(digraph);
    580584      _node_filter = &node_filter;
    581       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    582586    }
    583587
     
    648652
    649653    template <typename V>
    650     class NodeMap 
     654    class NodeMap
    651655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    652656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     659
    653660    public:
    654661      typedef V Value;
    655       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    657662
    658663      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     
    674679
    675680    template <typename V>
    676     class ArcMap 
     681    class ArcMap
    677682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    678683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     684      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     685        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     686
    679687    public:
    680688      typedef V Value;
    681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    682           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
    683689
    684690      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
     
    716722  /// by adding or removing nodes or arcs, unless the \c GR template
    717723  /// parameter is set to be \c const.
     724  ///
     725  /// This class provides only linear time counting for nodes and arcs.
    718726  ///
    719727  /// \tparam DGR The type of the adapted digraph.
     
    864872  template <typename GR, typename NF, typename EF, bool ch = true>
    865873  class SubGraphBase : public GraphAdaptorBase<GR> {
     874    typedef GraphAdaptorBase<GR> Parent;
    866875  public:
    867876    typedef GR Graph;
     
    870879
    871880    typedef SubGraphBase Adaptor;
    872     typedef GraphAdaptorBase<GR> Parent;
    873881  protected:
    874882
     
    10141022
    10151023    template <typename V>
    1016     class NodeMap 
     1024    class NodeMap
    10171025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10181026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1029
    10191030    public:
    10201031      typedef V Value;
    1021       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1022         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10231032
    10241033      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     
    10401049
    10411050    template <typename V>
    1042     class ArcMap 
     1051    class ArcMap
    10431052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10441053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1056
    10451057    public:
    10461058      typedef V Value;
    1047       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1048         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10491059
    10501060      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     
    10661076
    10671077    template <typename V>
    1068     class EdgeMap 
     1078    class EdgeMap
    10691079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10701080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1083
    10711084    public:
    10721085      typedef V Value;
    1073       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    1074         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10751086
    10761087      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
     
    10971108  class SubGraphBase<GR, NF, EF, false>
    10981109    : public GraphAdaptorBase<GR> {
     1110    typedef GraphAdaptorBase<GR> Parent;
    10991111  public:
    11001112    typedef GR Graph;
     
    11031115
    11041116    typedef SubGraphBase Adaptor;
    1105     typedef GraphAdaptorBase<GR> Parent;
    11061117  protected:
    11071118    NF* _node_filter;
    11081119    EF* _edge_filter;
    1109     SubGraphBase() 
    1110           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11111122
    11121123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12091220
    12101221    template <typename V>
    1211     class NodeMap 
     1222    class NodeMap
    12121223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12131224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
     1227
    12141228    public:
    12151229      typedef V Value;
    1216       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1217         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12181230
    12191231      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     
    12351247
    12361248    template <typename V>
    1237     class ArcMap 
     1249    class ArcMap
    12381250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12391251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
     1254
    12401255    public:
    12411256      typedef V Value;
    1242       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1243         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12441257
    12451258      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     
    12611274
    12621275    template <typename V>
    1263     class EdgeMap 
     1276    class EdgeMap
    12641277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12651278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1281
    12661282    public:
    12671283      typedef V Value;
    1268       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1269                   LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12701284
    12711285      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
     
    13051319  /// by adding or removing nodes or edges, unless the \c GR template
    13061320  /// parameter is set to be \c const.
     1321  ///
     1322  /// This class provides only linear time counting for nodes, edges and arcs.
    13071323  ///
    13081324  /// \tparam GR The type of the adapted graph.
     
    13561372    /// and edge filter maps.
    13571373    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
    1358       initialize(graph, node_filter, edge_filter);
     1374      this->initialize(graph, node_filter, edge_filter);
    13591375    }
    13601376
     
    14621478  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14631479  /// parameter is set to be \c const.
     1480  ///
     1481  /// This class provides only linear time item counting.
    14641482  ///
    14651483  /// \tparam GR The type of the adapted digraph or graph.
     
    14861504                     true> > {
    14871505#endif
     1506    typedef DigraphAdaptorExtender<
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1508                     true> > Parent;
     1509
    14881510  public:
    14891511
     
    14911513    typedef NF NodeFilterMap;
    14921514
    1493     typedef DigraphAdaptorExtender<
    1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    1495                      true> > Parent;
    1496 
    14971515    typedef typename Parent::Node Node;
    14981516
     
    15081526    /// Creates a subgraph for the given digraph or graph with the
    15091527    /// given node filter map.
    1510     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15111529      : Parent(), const_true_map()
    15121530    {
     
    15461564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15471565    public GraphAdaptorExtender<
    1548       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15491567                   true> > {
    15501568
    1551   public:
     1569    typedef GraphAdaptorExtender<
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1571                   true> > Parent;
     1572
     1573  public:
     1574
    15521575    typedef GR Graph;
    15531576    typedef NF NodeFilterMap;
    1554     typedef GraphAdaptorExtender<
    1555       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    1556                    true> > Parent;
    15571577
    15581578    typedef typename Parent::Node Node;
     1579
    15591580  protected:
    15601581    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
     
    16071628  /// by adding or removing nodes or arcs, unless the \c GR template
    16081629  /// parameter is set to be \c const.
     1630  ///
     1631  /// This class provides only linear time counting for nodes and arcs.
    16091632  ///
    16101633  /// \tparam DGR The type of the adapted digraph.
     
    16301653                     AF, false> > {
    16311654#endif
    1632   public:
     1655    typedef DigraphAdaptorExtender<
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1657                     AF, false> > Parent;
     1658
     1659  public:
     1660
    16331661    /// The type of the adapted digraph.
    16341662    typedef DGR Digraph;
    16351663    /// The type of the arc filter map.
    16361664    typedef AF ArcFilterMap;
    1637 
    1638     typedef DigraphAdaptorExtender<
    1639       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    1640                      AF, false> > Parent;
    16411665
    16421666    typedef typename Parent::Arc Arc;
     
    17161740  /// by adding or removing nodes or edges, unless the \c GR template
    17171741  /// parameter is set to be \c const.
     1742  ///
     1743  /// This class provides only linear time counting for nodes, edges and arcs.
    17181744  ///
    17191745  /// \tparam GR The type of the adapted graph.
     
    17361762  class FilterEdges :
    17371763    public GraphAdaptorExtender<
    1738       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17391765                   EF, false> > {
    17401766#endif
    1741   public:
     1767    typedef GraphAdaptorExtender<
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1769                   EF, false> > Parent;
     1770
     1771  public:
     1772
    17421773    /// The type of the adapted graph.
    17431774    typedef GR Graph;
     
    17451776    typedef EF EdgeFilterMap;
    17461777
    1747     typedef GraphAdaptorExtender<
    1748       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    1749                    EF, false> > Parent;
    1750 
    17511778    typedef typename Parent::Edge Edge;
    17521779
     
    17641791    /// Creates a subgraph for the given graph with the given edge
    17651792    /// filter map.
    1766     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17671794      : Parent(), const_true_map() {
    17681795      Parent::initialize(graph, const_true_map, edge_filter);
     
    18261853    typedef typename Digraph::Node Node;
    18271854
    1828     class Arc : public Edge {
     1855    class Arc {
    18291856      friend class UndirectorBase;
    18301857    protected:
     1858      Edge _edge;
    18311859      bool _forward;
    18321860
    1833       Arc(const Edge& edge, bool forward) :
    1834         Edge(edge), _forward(forward) {}
     1861      Arc(const Edge& edge, bool forward)
     1862        : _edge(edge), _forward(forward) {}
    18351863
    18361864    public:
    18371865      Arc() {}
    18381866
    1839       Arc(Invalid) : Edge(INVALID), _forward(true) {}
     1867      Arc(Invalid) : _edge(INVALID), _forward(true) {}
     1868
     1869      operator const Edge&() const { return _edge; }
    18401870
    18411871      bool operator==(const Arc &other) const {
    1842         return _forward == other._forward &&
    1843           static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
     1872        return _forward == other._forward && _edge == other._edge;
    18441873      }
    18451874      bool operator!=(const Arc &other) const {
    1846         return _forward != other._forward ||
    1847           static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
     1875        return _forward != other._forward || _edge != other._edge;
    18481876      }
    18491877      bool operator<(const Arc &other) const {
    18501878        return _forward < other._forward ||
    1851           (_forward == other._forward &&
    1852            static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
     1879          (_forward == other._forward && _edge < other._edge);
    18531880      }
    18541881    };
     
    18631890
    18641891    void first(Arc& a) const {
    1865       _digraph->first(a);
     1892      _digraph->first(a._edge);
    18661893      a._forward = true;
    18671894    }
     
    18711898        a._forward = false;
    18721899      } else {
    1873         _digraph->next(a);
     1900        _digraph->next(a._edge);
    18741901        a._forward = true;
    18751902      }
     
    18851912
    18861913    void firstOut(Arc& a, const Node& n) const {
    1887       _digraph->firstIn(a, n);
    1888       if( static_cast<const Edge&>(a) != INVALID ) {
     1914      _digraph->firstIn(a._edge, n);
     1915      if (a._edge != INVALID ) {
    18891916        a._forward = false;
    18901917      } else {
    1891         _digraph->firstOut(a, n);
     1918        _digraph->firstOut(a._edge, n);
    18921919        a._forward = true;
    18931920      }
     
    18951922    void nextOut(Arc &a) const {
    18961923      if (!a._forward) {
    1897         Node n = _digraph->target(a);
    1898         _digraph->nextIn(a);
    1899         if (static_cast<const Edge&>(a) == INVALID ) {
    1900           _digraph->firstOut(a, n);
     1924        Node n = _digraph->target(a._edge);
     1925        _digraph->nextIn(a._edge);
     1926        if (a._edge == INVALID) {
     1927          _digraph->firstOut(a._edge, n);
    19011928          a._forward = true;
    19021929        }
    19031930      }
    19041931      else {
    1905         _digraph->nextOut(a);
     1932        _digraph->nextOut(a._edge);
    19061933      }
    19071934    }
    19081935
    19091936    void firstIn(Arc &a, const Node &n) const {
    1910       _digraph->firstOut(a, n);
    1911       if (static_cast<const Edge&>(a) != INVALID ) {
     1937      _digraph->firstOut(a._edge, n);
     1938      if (a._edge != INVALID ) {
    19121939        a._forward = false;
    19131940      } else {
    1914         _digraph->firstIn(a, n);
     1941        _digraph->firstIn(a._edge, n);
    19151942        a._forward = true;
    19161943      }
     
    19181945    void nextIn(Arc &a) const {
    19191946      if (!a._forward) {
    1920         Node n = _digraph->source(a);
    1921         _digraph->nextOut(a);
    1922         if( static_cast<const Edge&>(a) == INVALID ) {
    1923           _digraph->firstIn(a, n);
     1947        Node n = _digraph->source(a._edge);
     1948        _digraph->nextOut(a._edge);
     1949        if (a._edge == INVALID ) {
     1950          _digraph->firstIn(a._edge, n);
    19241951          a._forward = true;
    19251952        }
    19261953      }
    19271954      else {
    1928         _digraph->nextIn(a);
     1955        _digraph->nextIn(a._edge);
    19291956      }
    19301957    }
     
    19591986
    19601987    Node source(const Arc &a) const {
    1961       return a._forward ? _digraph->source(a) : _digraph->target(a);
     1988      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
    19621989    }
    19631990
    19641991    Node target(const Arc &a) const {
    1965       return a._forward ? _digraph->target(a) : _digraph->source(a);
     1992      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
    19661993    }
    19671994
    19681995    static Arc direct(const Edge &e, bool d) {
    19691996      return Arc(e, d);
    1970     }
    1971     Arc direct(const Edge &e, const Node& n) const {
    1972       return Arc(e, _digraph->source(e) == n);
    19731997    }
    19741998
     
    20752099
    20762100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2077         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    20782102          _backward(*adaptor._digraph, value) {}
    20792103
     
    21122136    template <typename V>
    21132137    class NodeMap : public DGR::template NodeMap<V> {
     2138      typedef typename DGR::template NodeMap<V> Parent;
     2139
    21142140    public:
    2115 
    21162141      typedef V Value;
    2117       typedef typename DGR::template NodeMap<Value> Parent;
    21182142
    21192143      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
     
    21382162    template <typename V>
    21392163    class ArcMap
    2140       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
    2141     {
     2164      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
     2165      typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
     2166
    21422167    public:
    21432168      typedef V Value;
    2144       typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
    21452169
    21462170      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
     
    21642188    template <typename V>
    21652189    class EdgeMap : public Digraph::template ArcMap<V> {
     2190      typedef typename Digraph::template ArcMap<V> Parent;
     2191
    21662192    public:
    2167 
    21682193      typedef V Value;
    2169       typedef typename Digraph::template ArcMap<V> Parent;
    21702194
    21712195      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
     
    21942218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    21952219
     2220    typedef EdgeNotifier ArcNotifier;
     2221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     2222
    21962223  protected:
    21972224
     
    22182245  /// by adding or removing nodes or edges, unless the \c GR template
    22192246  /// parameter is set to be \c const.
     2247  ///
     2248  /// This class provides item counting in the same time as the adapted
     2249  /// digraph structure.
    22202250  ///
    22212251  /// \tparam DGR The type of the adapted digraph.
     
    22362266    public GraphAdaptorExtender<UndirectorBase<DGR> > {
    22372267#endif
     2268    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22382269  public:
    22392270    /// The type of the adapted digraph.
    22402271    typedef DGR Digraph;
    2241     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
    22422272  protected:
    22432273    Undirector() { }
     
    22482278    /// Creates an undirected graph from the given digraph.
    22492279    Undirector(DGR& digraph) {
    2250       initialize(digraph);
     2280      this->initialize(digraph);
    22512281    }
    22522282
     
    24472477    template <typename V>
    24482478    class NodeMap : public GR::template NodeMap<V> {
     2479      typedef typename GR::template NodeMap<V> Parent;
     2480
    24492481    public:
    2450 
    2451       typedef typename GR::template NodeMap<V> Parent;
    24522482
    24532483      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
     
    24722502    template <typename V>
    24732503    class ArcMap : public GR::template EdgeMap<V> {
     2504      typedef typename Graph::template EdgeMap<V> Parent;
     2505
    24742506    public:
    2475 
    2476       typedef typename Graph::template EdgeMap<V> Parent;
    24772507
    24782508      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
     
    25212551  /// by adding or removing nodes or arcs, unless the \c GR template
    25222552  /// parameter is set to be \c const.
     2553  ///
     2554  /// This class provides item counting in the same time as the adapted
     2555  /// graph structure.
    25232556  ///
    25242557  /// \tparam GR The type of the adapted graph.
     
    25442577    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
    25452578#endif
     2579    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25462580  public:
    25472581
     
    25512585    typedef DM DirectionMap;
    25522586
    2553     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
    25542587    typedef typename Parent::Arc Arc;
     2588
    25552589  protected:
    25562590    Orienter() { }
     2591
    25572592  public:
    25582593
     
    26632698  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26642699  ///
     2700  /// This class provides only linear time counting for nodes and arcs.
     2701  ///
    26652702  /// \tparam DGR The type of the adapted digraph.
    26662703  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    26922729           typename FM = CM,
    26932730           typename TL = Tolerance<typename CM::Value> >
    2694   class ResidualDigraph 
     2731  class ResidualDigraph
    26952732    : public SubDigraph<
    26962733        Undirector<const DGR>,
     
    27492786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27502787                    FM& flow, const TL& tolerance = Tolerance())
    2751       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27522789        _graph(digraph), _node_filter(),
    27532790        _forward_filter(capacity, flow, tolerance),
     
    28312868
    28322869      /// Constructor
    2833       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28342871        : _adaptor(&adaptor) {}
    28352872
     
    28642901  template <typename DGR>
    28652902  class SplitNodesBase {
     2903    typedef DigraphAdaptorBase<const DGR> Parent;
     2904
    28662905  public:
    28672906
    28682907    typedef DGR Digraph;
    2869     typedef DigraphAdaptorBase<const DGR> Parent;
    28702908    typedef SplitNodesBase Adaptor;
    28712909
     
    32263264    template <typename V>
    32273265    class NodeMap
    3228       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
    3229     {
     3266      : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
     3267      typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
     3268
    32303269    public:
    32313270      typedef V Value;
    3232       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
    32333271
    32343272      NodeMap(const SplitNodesBase<DGR>& adaptor)
     
    32523290    template <typename V>
    32533291    class ArcMap
    3254       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
    3255     {
     3292      : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
     3293      typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
     3294
    32563295    public:
    32573296      typedef V Value;
    3258       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
    32593297
    32603298      ArcMap(const SplitNodesBase<DGR>& adaptor)
     
    33093347  /// in the adaptor.
    33103348  ///
     3349  /// This class provides item counting in the same time as the adapted
     3350  /// digraph structure.
     3351  ///
    33113352  /// \tparam DGR The type of the adapted digraph.
    33123353  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    33223363    : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
    33233364#endif
     3365    typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
     3366
    33243367  public:
    33253368    typedef DGR Digraph;
    3326     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
    33273369
    33283370    typedef typename DGR::Node DigraphNode;
     
    34063448    /// to get a node map of the split digraph.
    34073449    /// Its value type is inherited from the first node map type (\c IN).
    3408     /// \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.
    34093451    /// \tparam OUT The type of the node map for the out-nodes.
    34103452    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/bfs.h

    r525 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).
     
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
     
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
     
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///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.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
     
    146153    typedef PredMapPath<Digraph, PredMap> Path;
    147154
    148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     155    ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
    149156    typedef TR Traits;
    150157
     
    226233    ///\ref named-templ-param "Named parameter" for setting
    227234    ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     235    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229236    template <class T>
    230237    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    246253    ///\ref named-templ-param "Named parameter" for setting
    247254    ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     255    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249256    template <class T>
    250257    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266273    ///\ref named-templ-param "Named parameter" for setting
    267274    ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269277    template <class T>
    270278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    286294    ///\ref named-templ-param "Named parameter" for setting
    287295    ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     296    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289297    template <class T>
    290298    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    414422    ///The simplest way to execute the BFS algorithm is to use one of the
    415423    ///member functions called \ref run(Node) "run()".\n
    416     ///If you need more control on the execution, first you have to call
    417     ///\ref init(), then you can add several source nodes with
     424    ///If you need better control on the execution, you have to call
     425    ///\ref init() first, then you can add several source nodes with
    418426    ///\ref addSource(). Finally the actual path computation can be
    419427    ///performed with one of the \ref start() functions.
     
    701709    ///Runs the algorithm to visit all nodes in the digraph.
    702710
    703     ///This method runs the %BFS algorithm in order to
    704     ///compute the shortest path to each node.
    705     ///
    706     ///The algorithm computes
    707     ///- the shortest path tree (forest),
    708     ///- the distance of each node from the root(s).
     711    ///This method runs the %BFS algorithm in order to visit all nodes
     712    ///in the digraph.
    709713    ///
    710714    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    738742    ///@{
    739743
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     744    ///The shortest path to the given node.
     745
     746    ///Returns the shortest path to the given node from the root(s).
    743747    ///
    744748    ///\warning \c t should be reached from the root(s).
     
    748752    Path path(Node t) const { return Path(*G, *_pred, t); }
    749753
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     754    ///The distance of the given node from the root(s).
     755
     756    ///Returns the distance of the given node from the root(s).
    753757    ///
    754758    ///\warning If node \c v is not reached from the root(s), then
     
    759763    int dist(Node v) const { return (*_dist)[v]; }
    760764
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     765    ///\brief Returns the 'previous arc' of the shortest path tree for
     766    ///the given node.
     767    ///
    763768    ///This function returns the 'previous arc' of the shortest path
    764769    ///tree for the node \c v, i.e. it returns the last arc of a
     
    767772    ///
    768773    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     774    ///tree used in \ref predNode() and \ref predMap().
    770775    ///
    771776    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    773778    Arc predArc(Node v) const { return (*_pred)[v];}
    774779
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     780    ///\brief Returns the 'previous node' of the shortest path tree for
     781    ///the given node.
     782    ///
    777783    ///This function returns the 'previous node' of the shortest path
    778784    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     785    ///of a shortest path from a root to \c v. It is \c INVALID
    780786    ///if \c v is not reached from the root(s) or if \c v is a root.
    781787    ///
    782788    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     789    ///tree used in \ref predArc() and \ref predMap().
    784790    ///
    785791    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    802808    ///
    803809    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     810    ///arcs, which form the shortest path tree (forest).
    805811    ///
    806812    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808814    const PredMap &predMap() const { return *_pred;}
    809815
    810     ///Checks if a node is reached from the root(s).
     816    ///Checks if the given node is reached from the root(s).
    811817
    812818    ///Returns \c true if \c v is reached from the root(s).
     
    834840    ///The type of the map that stores the predecessor
    835841    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     842    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837843    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838844    ///Instantiates a PredMap.
     
    849855
    850856    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    852     ///By default it is a NullMap.
     857    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     858    ///By default, it is a NullMap.
    853859    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    854860    ///Instantiates a ProcessedMap.
     
    869875
    870876    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873880    ///Instantiates a ReachedMap.
     
    884891
    885892    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     893    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887894    typedef typename Digraph::template NodeMap<int> DistMap;
    888895    ///Instantiates a DistMap.
     
    899906
    900907    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     908    ///It must conform to the \ref concepts::Path "Path" concept.
    902909    typedef lemon::Path<Digraph> Path;
    903910  };
     
    905912  /// Default traits class used by BfsWizard
    906913
    907   /// To make it easier to use Bfs algorithm
    908   /// we have created a wizard class.
    909   /// This \ref BfsWizard class needs default traits,
    910   /// as well as the \ref Bfs class.
    911   /// The \ref BfsWizardBase is a class to be the default traits of the
    912   /// \ref BfsWizard class.
     914  /// Default traits class used by BfsWizard.
     915  /// \tparam GR The type of the digraph.
    913916  template<class GR>
    914917  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    938941    /// Constructor.
    939942
    940     /// This constructor does not require parameters, therefore it initiates
     943    /// This constructor does not require parameters, it initiates
    941944    /// all of the attributes to \c 0.
    942945    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    963966  /// This class should only be used through the \ref bfs() function,
    964967  /// which makes it easier to use the algorithm.
     968  ///
     969  /// \tparam TR The traits class that defines various types used by the
     970  /// algorithm.
    965971  template<class TR>
    966972  class BfsWizard : public TR
     
    968974    typedef TR Base;
    969975
    970     ///The type of the digraph the algorithm runs on.
    971976    typedef typename TR::Digraph Digraph;
    972977
     
    976981    typedef typename Digraph::OutArcIt OutArcIt;
    977982
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980983    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982984    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984985    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986986    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988987    typedef typename TR::Path Path;
    989988
     
    10551054    ///Runs BFS algorithm to visit all nodes in the digraph.
    10561055
    1057     ///This method runs BFS algorithm in order to compute
    1058     ///the shortest path to each node.
     1056    ///This method runs BFS algorithm in order to visit all nodes
     1057    ///in the digraph.
    10591058    void run()
    10601059    {
     
    10681067      SetPredMapBase(const TR &b) : TR(b) {}
    10691068    };
    1070     ///\brief \ref named-func-param "Named parameter"
    1071     ///for setting PredMap object.
    1072     ///
    1073     ///\ref named-func-param "Named parameter"
    1074     ///for setting PredMap object.
     1069
     1070    ///\brief \ref named-templ-param "Named parameter" for setting
     1071    ///the predecessor map.
     1072    ///
     1073    ///\ref named-templ-param "Named parameter" function for setting
     1074    ///the map that stores the predecessor arcs of the nodes.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088     ///\brief \ref named-func-param "Named parameter"
    1089     ///for setting ReachedMap object.
    1090     ///
    1091     /// \ref named-func-param "Named parameter"
    1092     ///for setting ReachedMap object.
     1088
     1089    ///\brief \ref named-templ-param "Named parameter" for setting
     1090    ///the reached map.
     1091    ///
     1092    ///\ref named-templ-param "Named parameter" function for setting
     1093    ///the map that indicates which nodes are reached.
    10931094    template<class T>
    10941095    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11041105      SetDistMapBase(const TR &b) : TR(b) {}
    11051106    };
    1106     ///\brief \ref named-func-param "Named parameter"
    1107     ///for setting DistMap object.
    1108     ///
    1109     /// \ref named-func-param "Named parameter"
    1110     ///for setting DistMap object.
     1107
     1108    ///\brief \ref named-templ-param "Named parameter" for setting
     1109    ///the distance map.
     1110    ///
     1111    ///\ref named-templ-param "Named parameter" function for setting
     1112    ///the map that stores the distances of the nodes calculated
     1113    ///by the algorithm.
    11111114    template<class T>
    11121115    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11221125      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231126    };
    1124     ///\brief \ref named-func-param "Named parameter"
    1125     ///for setting ProcessedMap object.
    1126     ///
    1127     /// \ref named-func-param "Named parameter"
    1128     ///for setting ProcessedMap object.
     1127
     1128    ///\brief \ref named-func-param "Named parameter" for setting
     1129    ///the processed map.
     1130    ///
     1131    ///\ref named-templ-param "Named parameter" function for setting
     1132    ///the map that indicates which nodes are processed.
    11291133    template<class T>
    11301134    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12481252      }
    12491253      _Visitor& visitor;
     1254      Constraints() {}
    12501255    };
    12511256  };
     
    12651270    ///
    12661271    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1272    /// It must conform to
     1273    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681274    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691275
     
    13031309  /// does not observe the BFS events. If you want to observe the BFS
    13041310  /// events, you should implement your own visitor class.
    1305   /// \tparam TR Traits class to set various data types used by the
    1306   /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    1308   /// See \ref BfsVisitDefaultTraits for the documentation of
    1309   /// 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.
    13101316#ifdef DOXYGEN
    13111317  template <typename GR, typename VS, typename TR>
     
    14261432    /// The simplest way to execute the BFS algorithm is to use one of the
    14271433    /// member functions called \ref run(Node) "run()".\n
    1428     /// If you need more control on the execution, first you have to call
    1429     /// \ref init(), then you can add several source nodes with
     1434    /// If you need better control on the execution, you have to call
     1435    /// \ref init() first, then you can add several source nodes with
    14301436    /// \ref addSource(). Finally the actual path computation can be
    14311437    /// performed with one of the \ref start() functions.
     
    16991705    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17001706    ///
    1701     /// This method runs the %BFS algorithm in order to
    1702     /// compute the shortest path to each node.
    1703     ///
    1704     /// The algorithm computes
    1705     /// - the shortest path tree (forest),
    1706     /// - the distance of each node from the root(s).
     1707    /// This method runs the %BFS algorithm in order to visit all nodes
     1708    /// in the digraph.
    17071709    ///
    17081710    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    17361738    ///@{
    17371739
    1738     /// \brief Checks if a node is reached from the root(s).
     1740    /// \brief Checks if the given node is reached from the root(s).
    17391741    ///
    17401742    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r606 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).
     
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure.
    37   ///
    38   ///A \e heap is a data structure for storing items with specified values
    39   ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c Comp specifies the ordering of the priorities.
    41   ///In a heap one can change the priority of an item, add or erase an
    42   ///item, etc.
     36  /// This class implements the \e binary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4338  ///
    44   ///\tparam PR Type of the priority of the items.
    45   ///\tparam IM A read and writable item map with int values, used internally
    46   ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
    48   ///The default is \c std::less<PR>.
    49   ///
    50   ///\sa FibHeap
    51   ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     39  /// \tparam PR Type of the priorities of the items.
     40  /// \tparam IM A read-writable item map with \c int values, used
     41  /// internally to handle the cross references.
     42  /// \tparam CMP A functor class for comparing the priorities.
     43  /// The default is \c std::less<PR>.
     44#ifdef DOXYGEN
     45  template <typename PR, typename IM, typename CMP>
     46#else
     47  template <typename PR, typename IM, typename CMP = std::less<PR> >
     48#endif
    5349  class BinHeap {
    54 
    5550  public:
    56     ///\e
     51
     52    /// Type of the item-int map.
    5753    typedef IM ItemIntMap;
    58     ///\e
     54    /// Type of the priorities.
    5955    typedef PR Prio;
    60     ///\e
     56    /// Type of the items stored in the heap.
    6157    typedef typename ItemIntMap::Key Item;
    62     ///\e
     58    /// Type of the item-priority pairs.
    6359    typedef std::pair<Item,Prio> Pair;
    64     ///\e
    65     typedef Comp Compare;
    66 
    67     /// \brief Type to represent the items states.
    68     ///
    69     /// Each Item element have a state associated to it. It may be "in heap",
    70     /// "pre heap" or "post heap". The latter two are indifferent from the
     60    /// Functor type for comparing the priorities.
     61    typedef CMP Compare;
     62
     63    /// \brief Type to represent the states of the items.
     64    ///
     65    /// Each item has a state associated to it. It can be "in heap",
     66    /// "pre-heap" or "post-heap". The latter two are indifferent from the
    7167    /// heap's point of view, but may be useful to the user.
    7268    ///
     
    7470    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7571    enum State {
    76       IN_HEAP = 0,    ///< \e
    77       PRE_HEAP = -1,  ///< \e
    78       POST_HEAP = -2  ///< \e
     72      IN_HEAP = 0,    ///< = 0.
     73      PRE_HEAP = -1,  ///< = -1.
     74      POST_HEAP = -2  ///< = -2.
    7975    };
    8076
     
    8581
    8682  public:
    87     /// \brief The constructor.
    88     ///
    89     /// The constructor.
    90     /// \param map should be given to the constructor, since it is used
    91     /// internally to handle the cross references. The value of the map
    92     /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     83
     84    /// \brief Constructor.
     85    ///
     86    /// Constructor.
     87    /// \param map A map that assigns \c int values to the items.
     88    /// It is used internally to handle the cross references.
     89    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    9390    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9491
    95     /// \brief The constructor.
    96     ///
    97     /// The constructor.
    98     /// \param map should be given to the constructor, since it is used
    99     /// internally to handle the cross references. The value of the map
    100     /// should be PRE_HEAP (-1) for each element.
    101     ///
    102     /// \param comp The comparator function object.
     92    /// \brief Constructor.
     93    ///
     94    /// Constructor.
     95    /// \param map A map that assigns \c int values to the items.
     96    /// It is used internally to handle the cross references.
     97    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     98    /// \param comp The function object used for comparing the priorities.
    10399    BinHeap(ItemIntMap &map, const Compare &comp)
    104100      : _iim(map), _comp(comp) {}
    105101
    106102
    107     /// The number of items stored in the heap.
    108     ///
    109     /// \brief Returns the number of items stored in the heap.
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
    110106    int size() const { return _data.size(); }
    111107
    112     /// \brief Checks if the heap stores no items.
    113     ///
    114     /// Returns \c true if and only if the heap stores no items.
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
    115111    bool empty() const { return _data.empty(); }
    116112
    117     /// \brief Make empty this heap.
    118     ///
    119     /// Make empty this heap. It does not change the cross reference map.
    120     /// If you want to reuse what is not surely empty you should first clear
    121     /// the heap and after that you should set the cross reference map for
    122     /// each item to \c PRE_HEAP.
     113    /// \brief Make the heap empty.
     114    ///
     115    /// This functon makes the heap empty.
     116    /// It does not change the cross reference map. If you want to reuse
     117    /// a heap that is not surely empty, you should first clear it and
     118    /// then you should set the cross reference map to \c PRE_HEAP
     119    /// for each item.
    123120    void clear() {
    124121      _data.clear();
     
    128125    static int parent(int i) { return (i-1)/2; }
    129126
    130     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    131128    bool less(const Pair &p1, const Pair &p2) const {
    132129      return _comp(p1.second, p2.second);
    133130    }
    134131
    135     int bubble_up(int hole, Pair p) {
     132    int bubbleUp(int hole, Pair p) {
    136133      int par = parent(hole);
    137134      while( hole>0 && less(p,_data[par]) ) {
     
    144141    }
    145142
    146     int bubble_down(int hole, Pair p, int length) {
    147       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    148145      while(child < length) {
    149146        if( less(_data[child-1], _data[child]) ) {
     
    154151        move(_data[child], hole);
    155152        hole = child;
    156         child = second_child(hole);
     153        child = secondChild(hole);
    157154      }
    158155      child--;
     
    172169
    173170  public:
     171
    174172    /// \brief Insert a pair of item and priority into the heap.
    175173    ///
    176     /// Adds \c p.first to the heap with priority \c p.second.
     174    /// This function inserts \c p.first to the heap with priority
     175    /// \c p.second.
    177176    /// \param p The pair to insert.
     177    /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubble_up(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given heap.
    185     ///
    186     /// Adds \c i to the heap with priority \c p.
     181      bubbleUp(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given priority.
     185    ///
     186    /// This function inserts the given item into the heap with the
     187    /// given priority.
    187188    /// \param i The item to insert.
    188189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    189191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    190192
    191     /// \brief Returns the item with minimum priority relative to \c Compare.
    192     ///
    193     /// This method returns the item with minimum priority relative to \c
    194     /// Compare.
    195     /// \pre The heap must be nonempty.
     193    /// \brief Return the item having minimum priority.
     194    ///
     195    /// This function returns the item having minimum priority.
     196    /// \pre The heap must be non-empty.
    196197    Item top() const {
    197198      return _data[0].first;
    198199    }
    199200
    200     /// \brief Returns the minimum priority relative to \c Compare.
    201     ///
    202     /// It returns the minimum priority relative to \c Compare.
    203     /// \pre The heap must be nonempty.
     201    /// \brief The minimum priority.
     202    ///
     203    /// This function returns the minimum priority.
     204    /// \pre The heap must be non-empty.
    204205    Prio prio() const {
    205206      return _data[0].second;
    206207    }
    207208
    208     /// \brief Deletes the item with minimum priority relative to \c Compare.
    209     ///
    210     /// This method deletes the item with minimum priority relative to \c
    211     /// Compare from the heap.
     209    /// \brief Remove the item having minimum priority.
     210    ///
     211    /// This function removes the item having minimum priority.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubble_down(0, _data[n], n);
     217        bubbleDown(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Deletes \c i from the heap.
    223     ///
    224     /// This method deletes item \c i from the heap.
    225     /// \param i The item to erase.
    226     /// \pre The item should be in the heap.
     222    /// \brief Remove the given item from the heap.
     223    ///
     224    /// This function removes the given item from the heap if it is
     225    /// already stored.
     226    /// \param i The item to delete.
     227    /// \pre \e i must be in the heap.
    227228    void erase(const Item &i) {
    228229      int h = _iim[i];
     
    230231      _iim.set(_data[h].first, POST_HEAP);
    231232      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    234235        }
    235236      }
     
    237238    }
    238239
    239 
    240     /// \brief Returns the priority of \c i.
    241     ///
    242     /// This function returns the priority of item \c i.
    243     /// \param i The item.
    244     /// \pre \c i must be in the heap.
     240    /// \brief The priority of the given item.
     241    ///
     242    /// This function returns the priority of the given item.
     243    /// \param i The item.
     244    /// \pre \e i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
     
    248248    }
    249249
    250     /// \brief \c i gets to the heap with priority \c p independently
    251     /// if \c i was already there.
    252     ///
    253     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    254     /// in the heap and sets the priority of \c i to \c p otherwise.
     250    /// \brief Set the priority of an item or insert it, if it is
     251    /// not stored in the heap.
     252    ///
     253    /// This method sets the priority of the given item if it is
     254    /// already stored in the heap. Otherwise it inserts the given
     255    /// item into the heap with the given priority.
    255256    /// \param i The item.
    256257    /// \param p The priority.
     
    261262      }
    262263      else if( _comp(p, _data[idx].second) ) {
    263         bubble_up(idx, Pair(i,p));
     264        bubbleUp(idx, Pair(i,p));
    264265      }
    265266      else {
    266         bubble_down(idx, Pair(i,p), _data.size());
    267       }
    268     }
    269 
    270     /// \brief Decreases the priority of \c i to \c p.
    271     ///
    272     /// This method decreases the priority of item \c i to \c p.
     267        bubbleDown(idx, Pair(i,p), _data.size());
     268      }
     269    }
     270
     271    /// \brief Decrease the priority of an item to the given value.
     272    ///
     273    /// This function decreases the priority of an item to the given value.
    273274    /// \param i The item.
    274275    /// \param p The priority.
    275     /// \pre \c i must be stored in the heap with priority at least \c
    276     /// p relative to \c Compare.
     276    /// \pre \e i must be stored in the heap with priority at least \e p.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubble_up(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increases the priority of \c i to \c p.
    283     ///
    284     /// This method sets the priority of item \c i to \c p.
     279      bubbleUp(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increase the priority of an item to the given value.
     283    ///
     284    /// This function increases the priority of an item to the given value.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \c i must be stored in the heap with priority at most \c
    288     /// p relative to \c Compare.
     287    /// \pre \e i must be stored in the heap with priority at most \e p.
    289288    void increase(const Item &i, const Prio &p) {
    290289      int idx = _iim[i];
    291       bubble_down(idx, Pair(i,p), _data.size());
    292     }
    293 
    294     /// \brief Returns if \c item is in, has already been in, or has
    295     /// never been in the heap.
    296     ///
    297     /// This method returns PRE_HEAP if \c item has never been in the
    298     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    299     /// otherwise. In the latter case it is possible that \c item will
    300     /// get back to the heap again.
     290      bubbleDown(idx, Pair(i,p), _data.size());
     291    }
     292
     293    /// \brief Return the state of an item.
     294    ///
     295    /// This method returns \c PRE_HEAP if the given item has never
     296    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     297    /// and \c POST_HEAP otherwise.
     298    /// In the latter case it is possible that the item will get back
     299    /// to the heap again.
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
     
    307306    }
    308307
    309     /// \brief Sets the state of the \c item in the heap.
    310     ///
    311     /// Sets the state of the \c item in the heap. It can be used to
    312     /// manually clear the heap when it is important to achive the
    313     /// better time complexity.
     308    /// \brief Set the state of an item in the heap.
     309    ///
     310    /// This function sets the state of the given item in the heap.
     311    /// It can be used to manually clear the heap when it is important
     312    /// to achive better time complexity.
    314313    /// \param i The item.
    315314    /// \param st The state. It should not be \c IN_HEAP.
     
    328327    }
    329328
    330     /// \brief Replaces an item in the heap.
    331     ///
    332     /// The \c i item is replaced with \c j item. The \c i item should
    333     /// be in the heap, while the \c j should be out of the heap. The
    334     /// \c i item will out of the heap and \c j will be in the heap
    335     /// with the same prioriority as prevoiusly the \c i item.
     329    /// \brief Replace an item in the heap.
     330    ///
     331    /// This function replaces item \c i with item \c j.
     332    /// Item \c i must be in the heap, while \c j must be out of the heap.
     333    /// After calling this method, item \c i will be out of the
     334    /// heap and \c j will be in the heap with the same prioriority
     335    /// as item \c i had before.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
  • 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

    r525 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).
     
    4848  public:
    4949    // The graph type.
    50     typedef _Graph Graph;
     50    typedef _Graph GraphType;
    5151    // The item type.
    5252    typedef _Item Item;
     
    6464    typedef _Value& Reference;
    6565
     66    // The map type.
     67    typedef ArrayMap Map;
     68
    6669    // The notifier type.
    6770    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6871
     72  private:
     73
    6974    // The MapBase of the Map which imlements the core regisitry function.
    7075    typedef typename Notifier::ObserverBase Parent;
    7176
    72   private:
    7377    typedef std::allocator<Value> Allocator;
    7478
     
    7882    //
    7983    // Graph initialized map constructor.
    80     explicit ArrayMap(const Graph& graph) {
     84    explicit ArrayMap(const GraphType& graph) {
    8185      Parent::attach(graph.notifier(Item()));
    8286      allocate_memory();
     
    9296    //
    9397    // It constructs a map and initialize all of the the map.
    94     ArrayMap(const Graph& graph, const Value& value) {
     98    ArrayMap(const GraphType& graph, const Value& value) {
    9599      Parent::attach(graph.notifier(Item()));
    96100      allocate_memory();
  • 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

    r582 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).
     
    9898
    9999
    100 #if defined HAVE_LONG_LONG
     100#if defined LEMON_HAVE_LONG_LONG
    101101
    102102  // long long
     
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     157
    156158  public:
    157     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    158159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    159160
    160     typedef typename Parent::Graph Graph;
     161    typedef typename Parent::GraphType GraphType;
    161162    typedef typename Parent::Value Value;
    162163
    163     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    164     DefaultMap(const Graph& graph, const Value& value)
     164    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
     165    DefaultMap(const GraphType& graph, const Value& value)
    165166      : Parent(graph, value) {}
    166167
  • lemon/bits/edge_set_extender.h

    r606 r1270  
    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).
     
    3535  template <typename Base>
    3636  class ArcSetExtender : public Base {
     37    typedef Base Parent;
     38
    3739  public:
    3840
    39     typedef Base Parent;
    4041    typedef ArcSetExtender Digraph;
    4142
     
    6364    Node oppositeNode(const Node &n, const Arc &e) const {
    6465      if (n == Parent::source(e))
    65         return Parent::target(e);
     66        return Parent::target(e);
    6667      else if(n==Parent::target(e))
    67         return Parent::source(e);
     68        return Parent::source(e);
    6869      else
    69         return INVALID;
     70        return INVALID;
    7071    }
    7172
     
    9192    // Iterable extensions
    9293
    93     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9495      const Digraph* digraph;
    9596    public:
     
    100101
    101102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    102         _graph.first(static_cast<Node&>(*this));
    103       }
    104 
    105       NodeIt(const Digraph& _graph, const Node& node) 
    106         : Node(node), digraph(&_graph) {}
    107 
    108       NodeIt& operator++() { 
    109         digraph->next(*this);
    110         return *this;
    111       }
    112 
    113     };
    114 
    115 
    116     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
     117    class ArcIt : public Arc {
    117118      const Digraph* digraph;
    118119    public:
     
    123124
    124125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    125         _graph.first(static_cast<Arc&>(*this));
    126       }
    127 
    128       ArcIt(const Digraph& _graph, const Arc& e) : 
    129         Arc(e), digraph(&_graph) { }
    130 
    131       ArcIt& operator++() { 
    132         digraph->next(*this);
    133         return *this;
    134       }
    135 
    136     };
    137 
    138 
    139     class OutArcIt : public Arc { 
     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 {
    140141      const Digraph* digraph;
    141142    public:
     
    145146      OutArcIt(Invalid i) : Arc(i) { }
    146147
    147       OutArcIt(const Digraph& _graph, const Node& node) 
    148         : digraph(&_graph) {
    149         _graph.firstOut(*this, node);
    150       }
    151 
    152       OutArcIt(const Digraph& _graph, const Arc& arc) 
    153         : Arc(arc), digraph(&_graph) {}
    154 
    155       OutArcIt& operator++() { 
    156         digraph->nextOut(*this);
    157         return *this;
    158       }
    159 
    160     };
    161 
    162 
    163     class InArcIt : public Arc { 
     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 {
    164165      const Digraph* digraph;
    165166    public:
     
    169170      InArcIt(Invalid i) : Arc(i) { }
    170171
    171       InArcIt(const Digraph& _graph, const Node& node) 
    172         : digraph(&_graph) {
    173         _graph.firstIn(*this, node);
    174       }
    175 
    176       InArcIt(const Digraph& _graph, const Arc& arc) : 
    177         Arc(arc), digraph(&_graph) {}
    178 
    179       InArcIt& operator++() { 
    180         digraph->nextIn(*this);
    181         return *this;
     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;
    182183      }
    183184
     
    215216
    216217    // Mappable extension
    217    
     218
    218219    template <typename _Value>
    219     class ArcMap 
     220    class ArcMap
    220221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    221     public:
    222       typedef ArcSetExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    224223
    225       explicit ArcMap(const Digraph& _g)
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v)
    228         : Parent(_g, _v) {}
     224    public:
     225      explicit ArcMap(const Digraph& _g)
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v)
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250    
     250
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    275275  template <typename Base>
    276276  class EdgeSetExtender : public Base {
     277    typedef Base Parent;
    277278
    278279  public:
    279280
    280     typedef Base Parent;
    281     typedef EdgeSetExtender Digraph;
     281    typedef EdgeSetExtender Graph;
     282
     283    typedef True UndirectedTag;
    282284
    283285    typedef typename Parent::Node Node;
     
    285287    typedef typename Parent::Edge Edge;
    286288
    287 
    288289    int maxId(Node) const {
    289290      return Parent::maxNodeId();
     
    312313    Node oppositeNode(const Node &n, const Edge &e) const {
    313314      if( n == Parent::u(e))
    314         return Parent::v(e);
     315        return Parent::v(e);
    315316      else if( n == Parent::v(e))
    316         return Parent::u(e);
     317        return Parent::u(e);
    317318      else
    318         return INVALID;
     319        return INVALID;
    319320    }
    320321
     
    340341
    341342    using Parent::notifier;
    342    
     343
    343344    ArcNotifier& notifier(Arc) const {
    344345      return arc_notifier;
     
    350351
    351352
    352     class NodeIt : public Node { 
    353       const Digraph* digraph;
     353    class NodeIt : public Node {
     354      const Graph* graph;
    354355    public:
    355356
     
    358359      NodeIt(Invalid i) : Node(i) { }
    359360
    360       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    361         _graph.first(static_cast<Node&>(*this));
    362       }
    363 
    364       NodeIt(const Digraph& _graph, const Node& node)
    365         : Node(node), digraph(&_graph) {}
    366 
    367       NodeIt& operator++() { 
    368         digraph->next(*this);
    369         return *this;
    370       }
    371 
    372     };
    373 
    374 
    375     class ArcIt : public Arc { 
    376       const Digraph* digraph;
     361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     362        _graph.first(static_cast<Node&>(*this));
     363      }
     364
     365      NodeIt(const Graph& _graph, const Node& node)
     366        : Node(node), graph(&_graph) {}
     367
     368      NodeIt& operator++() {
     369        graph->next(*this);
     370        return *this;
     371      }
     372
     373    };
     374
     375
     376    class ArcIt : public Arc {
     377      const Graph* graph;
    377378    public:
    378379
     
    381382      ArcIt(Invalid i) : Arc(i) { }
    382383
    383       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    384         _graph.first(static_cast<Arc&>(*this));
    385       }
    386 
    387       ArcIt(const Digraph& _graph, const Arc& e) :
    388         Arc(e), digraph(&_graph) { }
    389 
    390       ArcIt& operator++() { 
    391         digraph->next(*this);
    392         return *this;
    393       }
    394 
    395     };
    396 
    397 
    398     class OutArcIt : public Arc { 
    399       const Digraph* digraph;
     384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
     385        _graph.first(static_cast<Arc&>(*this));
     386      }
     387
     388      ArcIt(const Graph& _graph, const Arc& e) :
     389        Arc(e), graph(&_graph) { }
     390
     391      ArcIt& operator++() {
     392        graph->next(*this);
     393        return *this;
     394      }
     395
     396    };
     397
     398
     399    class OutArcIt : public Arc {
     400      const Graph* graph;
    400401    public:
    401402
     
    404405      OutArcIt(Invalid i) : Arc(i) { }
    405406
    406       OutArcIt(const Digraph& _graph, const Node& node)
    407         : digraph(&_graph) {
    408         _graph.firstOut(*this, node);
    409       }
    410 
    411       OutArcIt(const Digraph& _graph, const Arc& arc)
    412         : Arc(arc), digraph(&_graph) {}
    413 
    414       OutArcIt& operator++() { 
    415         digraph->nextOut(*this);
    416         return *this;
    417       }
    418 
    419     };
    420 
    421 
    422     class InArcIt : public Arc { 
    423       const Digraph* digraph;
     407      OutArcIt(const Graph& _graph, const Node& node)
     408        : graph(&_graph) {
     409        _graph.firstOut(*this, node);
     410      }
     411
     412      OutArcIt(const Graph& _graph, const Arc& arc)
     413        : Arc(arc), graph(&_graph) {}
     414
     415      OutArcIt& operator++() {
     416        graph->nextOut(*this);
     417        return *this;
     418      }
     419
     420    };
     421
     422
     423    class InArcIt : public Arc {
     424      const Graph* graph;
    424425    public:
    425426
     
    428429      InArcIt(Invalid i) : Arc(i) { }
    429430
    430       InArcIt(const Digraph& _graph, const Node& node)
    431         : digraph(&_graph) {
    432         _graph.firstIn(*this, node);
    433       }
    434 
    435       InArcIt(const Digraph& _graph, const Arc& arc) :
    436         Arc(arc), digraph(&_graph) {}
    437 
    438       InArcIt& operator++() { 
    439         digraph->nextIn(*this);
    440         return *this;
    441       }
    442 
    443     };
    444 
    445 
    446     class EdgeIt : public Parent::Edge { 
    447       const Digraph* digraph;
     431      InArcIt(const Graph& _graph, const Node& node)
     432        : graph(&_graph) {
     433        _graph.firstIn(*this, node);
     434      }
     435
     436      InArcIt(const Graph& _graph, const Arc& arc) :
     437        Arc(arc), graph(&_graph) {}
     438
     439      InArcIt& operator++() {
     440        graph->nextIn(*this);
     441        return *this;
     442      }
     443
     444    };
     445
     446
     447    class EdgeIt : public Parent::Edge {
     448      const Graph* graph;
    448449    public:
    449450
     
    452453      EdgeIt(Invalid i) : Edge(i) { }
    453454
    454       explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
    455         _graph.first(static_cast<Edge&>(*this));
    456       }
    457 
    458       EdgeIt(const Digraph& _graph, const Edge& e) :
    459         Edge(e), digraph(&_graph) { }
    460 
    461       EdgeIt& operator++() { 
    462         digraph->next(*this);
    463         return *this;
     455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     456        _graph.first(static_cast<Edge&>(*this));
     457      }
     458
     459      EdgeIt(const Graph& _graph, const Edge& e) :
     460        Edge(e), graph(&_graph) { }
     461
     462      EdgeIt& operator++() {
     463        graph->next(*this);
     464        return *this;
    464465      }
    465466
     
    468469    class IncEdgeIt : public Parent::Edge {
    469470      friend class EdgeSetExtender;
    470       const Digraph* digraph;
     471      const Graph* graph;
    471472      bool direction;
    472473    public:
     
    476477      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
    477478
    478       IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
    479         _graph.firstInc(*this, direction, n);
    480       }
    481 
    482       IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
    483         : digraph(&_graph), Edge(ue) {
    484         direction = (_graph.source(ue) == n);
     479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     480        _graph.firstInc(*this, direction, n);
     481      }
     482
     483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    485486      }
    486487
    487488      IncEdgeIt& operator++() {
    488         digraph->nextInc(*this, direction);
    489         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    490491      }
    491492    };
     
    523524    // Returns the base node of the iterator
    524525    Node baseNode(const IncEdgeIt &e) const {
    525       return e.direction ? u(e) : v(e);
     526      return e.direction ? this->u(e) : this->v(e);
    526527    }
    527528    // Running node of the iterator
     
    529530    // Returns the running node of the iterator
    530531    Node runningNode(const IncEdgeIt &e) const {
    531       return e.direction ? v(e) : u(e);
     532      return e.direction ? this->v(e) : this->u(e);
    532533    }
    533534
    534535
    535536    template <typename _Value>
    536     class ArcMap
    537       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    538     public:
    539       typedef EdgeSetExtender Digraph;
    540       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    541 
    542       ArcMap(const Digraph& _g)
    543         : Parent(_g) {}
    544       ArcMap(const Digraph& _g, const _Value& _v)
    545         : Parent(_g, _v) {}
     537    class ArcMap
     538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
     540
     541    public:
     542      explicit ArcMap(const Graph& _g)
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v)
     545        : Parent(_g, _v) {}
    546546
    547547      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    549549      }
    550550
     
    552552      ArcMap& operator=(const CMap& cmap) {
    553553        Parent::operator=(cmap);
    554         return *this;
     554        return *this;
    555555      }
    556556
     
    559559
    560560    template <typename _Value>
    561     class EdgeMap
    562       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
    563     public:
    564       typedef EdgeSetExtender Digraph;
    565       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
    566 
    567       EdgeMap(const Digraph& _g)
    568         : Parent(_g) {}
    569 
    570       EdgeMap(const Digraph& _g, const _Value& _v)
    571         : Parent(_g, _v) {}
     561    class EdgeMap
     562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     564
     565    public:
     566      explicit EdgeMap(const Graph& _g)
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v)
     570        : Parent(_g, _v) {}
    572571
    573572      EdgeMap& operator=(const EdgeMap& cmap) {
    574         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    575574      }
    576575
     
    578577      EdgeMap& operator=(const CMap& cmap) {
    579578        Parent::operator=(cmap);
    580         return *this;
     579        return *this;
    581580      }
    582581
     
    595594      return edge;
    596595    }
    597    
     596
    598597    void clear() {
    599598      notifier(Arc()).clear();
     
    621620      arc_notifier.clear();
    622621    }
    623    
     622
    624623  };
    625624
  • lemon/bits/graph_adaptor_extender.h

    r478 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).
     
    2323#include <lemon/error.h>
    2424
    25 #include <lemon/bits/default_map.h>
    26 
    2725namespace lemon {
    2826
    2927  template <typename _Digraph>
    3028  class DigraphAdaptorExtender : public _Digraph {
     29    typedef _Digraph Parent;
     30
    3131  public:
    3232
    33     typedef _Digraph Parent;
    3433    typedef _Digraph Digraph;
    3534    typedef DigraphAdaptorExtender Adaptor;
     
    176175  template <typename _Graph>
    177176  class GraphAdaptorExtender : public _Graph {
     177    typedef _Graph Parent;
     178
    178179  public:
    179180
    180     typedef _Graph Parent;
    181181    typedef _Graph Graph;
    182182    typedef GraphAdaptorExtender Adaptor;
     183
     184    typedef True UndirectedTag;
    183185
    184186    typedef typename Parent::Node Node;
  • lemon/bits/graph_extender.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).
     
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40    typedef Base Parent;
     41
    4042  public:
    4143
    42     typedef Base Parent;
    4344    typedef DigraphExtender Digraph;
    4445
     
    5657    }
    5758
    58     Node fromId(int id, Node) const {
     59    static Node fromId(int id, Node) {
    5960      return Parent::nodeFromId(id);
    6061    }
    6162
    62     Arc fromId(int id, Arc) const {
     63    static Arc fromId(int id, Arc) {
    6364      return Parent::arcFromId(id);
    6465    }
     
    219220    class NodeMap
    220221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    221     public:
    222       typedef DigraphExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    224223
     224    public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
     
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246     public:
    247       typedef DigraphExtender Digraph;
    248246      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249247
     248    public:
    250249      explicit ArcMap(const Digraph& digraph)
    251250        : Parent(digraph) {}
     
    331330  template <typename Base>
    332331  class GraphExtender : public Base {
     332    typedef Base Parent;
     333
    333334  public:
    334335
    335     typedef Base Parent;
    336336    typedef GraphExtender Graph;
    337337
     
    356356    }
    357357
    358     Node fromId(int id, Node) const {
     358    static Node fromId(int id, Node) {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     Arc fromId(int id, Arc) const {
     362    static Arc fromId(int id, Arc) {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     Edge fromId(int id, Edge) const {
     366    static Edge fromId(int id, Edge) {
    367367      return Parent::edgeFromId(id);
    368368    }
     
    588588    // Returns the base node of the iterator
    589589    Node baseNode(const IncEdgeIt &edge) const {
    590       return edge._direction ? u(edge) : v(edge);
     590      return edge._direction ? this->u(edge) : this->v(edge);
    591591    }
    592592    // Running node of the iterator
     
    594594    // Returns the running node of the iterator
    595595    Node runningNode(const IncEdgeIt &edge) const {
    596       return edge._direction ? v(edge) : u(edge);
     596      return edge._direction ? this->v(edge) : this->u(edge);
    597597    }
    598598
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
    608       NodeMap(const Graph& graph)
     606    public:
     607      explicit NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
    610609      NodeMap(const Graph& graph, const _Value& value)
     
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
    633       ArcMap(const Graph& graph)
     630    public:
     631      explicit ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
    635633      ArcMap(const Graph& graph, const _Value& value)
     
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
    658       EdgeMap(const Graph& graph)
     654    public:
     655      explicit EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}
    660657
     
    750747  };
    751748
     749  // \ingroup _graphbits
     750  //
     751  // \brief Extender for the BpGraphs
     752  template <typename Base>
     753  class BpGraphExtender : public Base {
     754    typedef Base Parent;
     755
     756  public:
     757
     758    typedef BpGraphExtender BpGraph;
     759
     760    typedef True UndirectedTag;
     761
     762    typedef typename Parent::Node Node;
     763    typedef typename Parent::RedNode RedNode;
     764    typedef typename Parent::BlueNode BlueNode;
     765    typedef typename Parent::Arc Arc;
     766    typedef typename Parent::Edge Edge;
     767
     768    // BpGraph extension
     769
     770    using Parent::first;
     771    using Parent::next;
     772    using Parent::id;
     773
     774    int maxId(Node) const {
     775      return Parent::maxNodeId();
     776    }
     777
     778    int maxId(RedNode) const {
     779      return Parent::maxRedId();
     780    }
     781
     782    int maxId(BlueNode) const {
     783      return Parent::maxBlueId();
     784    }
     785
     786    int maxId(Arc) const {
     787      return Parent::maxArcId();
     788    }
     789
     790    int maxId(Edge) const {
     791      return Parent::maxEdgeId();
     792    }
     793
     794    static Node fromId(int id, Node) {
     795      return Parent::nodeFromId(id);
     796    }
     797
     798    static Arc fromId(int id, Arc) {
     799      return Parent::arcFromId(id);
     800    }
     801
     802    static Edge fromId(int id, Edge) {
     803      return Parent::edgeFromId(id);
     804    }
     805
     806    Node u(Edge e) const { return this->redNode(e); }
     807    Node v(Edge e) const { return this->blueNode(e); }
     808
     809    Node oppositeNode(const Node &n, const Edge &e) const {
     810      if( n == u(e))
     811        return v(e);
     812      else if( n == v(e))
     813        return u(e);
     814      else
     815        return INVALID;
     816    }
     817
     818    Arc oppositeArc(const Arc &arc) const {
     819      return Parent::direct(arc, !Parent::direction(arc));
     820    }
     821
     822    using Parent::direct;
     823    Arc direct(const Edge &edge, const Node &node) const {
     824    &nb