COIN-OR::LEMON - Graph Library

Ignore:
Files:
52 added
5 deleted
132 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 r1072  
    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 r1161  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    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 
     3SET(PROJECT_NAME "LEMON")
    104PROJECT(${PROJECT_NAME})
    115
     6INCLUDE(FindPythonInterp)
     7INCLUDE(FindWget)
     8
     9IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     10  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     11ELSEIF(DEFINED ENV{LEMON_VERSION})
     12  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
     13ELSE()
     14  EXECUTE_PROCESS(
     15    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     16    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     17    OUTPUT_VARIABLE HG_REVISION_PATH
     18    ERROR_QUIET
     19    OUTPUT_STRIP_TRAILING_WHITESPACE
     20  )
     21  EXECUTE_PROCESS(
     22    COMMAND hg id -i
     23    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     24    OUTPUT_VARIABLE HG_REVISION
     25    ERROR_QUIET
     26    OUTPUT_STRIP_TRAILING_WHITESPACE
     27  )
     28  IF(HG_REVISION STREQUAL "")
     29    SET(HG_REVISION_ID "hg-tip")
     30  ELSE()
     31    IF(HG_REVISION_PATH STREQUAL "")
     32      SET(HG_REVISION_ID ${HG_REVISION})
     33    ELSE()
     34      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     35    ENDIF()
     36  ENDIF()
     37  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
     38ENDIF()
     39
     40SET(PROJECT_VERSION ${LEMON_VERSION})
     41
    1242SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    1343
    14 INCLUDE(FindDoxygen)
    15 INCLUDE(FindGhostscript)
     44FIND_PACKAGE(Doxygen)
     45FIND_PACKAGE(Ghostscript)
    1646FIND_PACKAGE(GLPK 4.33)
    17 
    18 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    19 
    20 IF(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)
     47FIND_PACKAGE(CPLEX)
     48FIND_PACKAGE(COIN)
     49
     50IF(DEFINED ENV{LEMON_CXX_WARNING})
     51  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     52ELSE()
     53  IF(CMAKE_COMPILER_IS_GNUCXX)
     54    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")
     55    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     56    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     57  ELSEIF(MSVC)
     58    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     59    # Still keep it as an example.
     60    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     61    # Suppressed warnings:
     62    # C4250: 'class1' : inherits 'class2::member' via dominance
     63    # C4355: 'this' : used in base member initializer list
     64    # C4503: 'function' : decorated name length exceeded, name was truncated
     65    # C4800: 'type' : forcing value to bool 'true' or 'false'
     66    #        (performance warning)
     67    # C4996: 'function': was declared deprecated
     68  ELSE()
     69    SET(CXX_WARNING "-Wall")
     70  ENDIF()
     71ENDIF()
     72SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     73
     74SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     75
     76SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
     77    "Flags used by the C++ compiler during maintainer builds."
     78    FORCE )
     79SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
     80    "Flags used by the C compiler during maintainer builds."
     81    FORCE )
     82SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     83    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     84    "Flags used for linking binaries during maintainer builds."
     85    FORCE )
     86SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     87    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     88    "Flags used by the shared libraries linker during maintainer builds."
     89    FORCE )
     90MARK_AS_ADVANCED(
     91    CMAKE_CXX_FLAGS_MAINTAINER
     92    CMAKE_C_FLAGS_MAINTAINER
     93    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     94    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     95
     96IF(CMAKE_CONFIGURATION_TYPES)
     97  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     98  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     99  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     100      "Add the configurations that we need"
     101      FORCE)
     102 endif()
     103
     104IF(NOT CMAKE_BUILD_TYPE)
     105  SET(CMAKE_BUILD_TYPE "Release")
     106ENDIF()
     107
     108SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     109    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     110    FORCE )
     111
    34112
    35113INCLUDE(CheckTypeSize)
    36114CHECK_TYPE_SIZE("long long" LONG_LONG)
     115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     116
     117INCLUDE(FindPythonInterp)
    37118
    38119ENABLE_TESTING()
     120
     121IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     122  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     123ELSE()
     124  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     125ENDIF()
    39126
    40127ADD_SUBDIRECTORY(lemon)
     
    44131  ADD_SUBDIRECTORY(doc)
    45132  ADD_SUBDIRECTORY(test)
    46 ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     133ENDIF()
     134
     135CONFIGURE_FILE(
     136  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     137  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     138  @ONLY
     139)
     140IF(UNIX)
     141  INSTALL(
     142    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     143    DESTINATION share/lemon/cmake
     144  )
     145ELSEIF(WIN32)
     146  INSTALL(
     147    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     148    DESTINATION cmake
     149  )
     150ENDIF()
    47151
    48152IF(${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})
     153  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     154  SET(CPACK_PACKAGE_VENDOR "EGRES")
     155  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     156    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     157  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
     158
     159  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     160
     161  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     162    "${PROJECT_NAME} ${PROJECT_VERSION}")
     163  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     164    "${PROJECT_NAME} ${PROJECT_VERSION}")
     165
     166  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     167
     168  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     169  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     170  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     171  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     172
     173  SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     174    "C++ header files")
     175  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     176    "DLL and import library")
     177  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     178    "Command line utilities")
     179  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     180    "Doxygen generated documentation")
     181
     182  SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     183
     184  SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     185  SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     186  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     187
     188  SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     189    "Components needed to develop software using LEMON")
     190  SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     191    "Documentation of LEMON")
     192
     193  SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     194
     195  SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     196  SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     197  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     198
     199  SET(CPACK_GENERATOR "NSIS")
     200  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     201  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     202  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     203  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     204  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     205  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     206  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     207  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     208  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     209    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     210    ")
     211  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     212    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     213    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     214    ")
     215
     216  INCLUDE(CPack)
     217ENDIF()
  • INSTALL

    r526 r890  
    2828
    2929      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.
     30      file. It also compiles the programs in the tools subdirectory by
     31      default.
    3232
    3333   4. `make check'
     
    7575
    7676  Set the installation prefix to PREFIX. By default it is /usr/local.
    77 
    78 --enable-demo
    79 
    80    Build the examples in the demo subdirectory.
    81 
    82 --disable-demo
    83 
    84    Do not build the examples in the demo subdirectory (default).
    8577
    8678--enable-tools
     
    159151
    160152   Disable SoPlex support.
     153
     154--with-coin[=PREFIX]
     155
     156   Enable support for COIN-OR solvers (CLP and CBC). You should
     157   specify the prefix too. (by default, COIN-OR tools install
     158   themselves to the source code directory). This command enables the
     159   solvers that are actually found.
     160
     161--with-coin-includedir=DIR
     162
     163   The directory where the COIN-OR header files are located. This is
     164   only useful when the COIN-OR headers and libraries are not under
     165   the same prefix (which is unlikely).
     166
     167--with-coin-libdir=DIR
     168
     169   The directory where the COIN-OR libraries are located. This is only
     170   useful when the COIN-OR headers and libraries are not under the
     171   same prefix (which is unlikely).
     172
     173--without-coin
     174
     175   Disable COIN-OR support.
     176
     177
     178Makefile Variables
     179==================
     180
     181Some Makefile variables are reserved by the GNU Coding Standards for
     182the use of the "user" - the person building the package. For instance,
     183CXX and CXXFLAGS are such variables, and have the same meaning as
     184explained in the previous section. These variables can be set on the
     185command line when invoking `make' like this:
     186`make [VARIABLE=VALUE]...'
     187
     188WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
     189to hold several compiler flags related to warnings. Its default value
     190can be overridden when invoking `make'. For example to disable all
     191warning flags use `make WARNINGCXXFLAGS='.
     192
     193In order to turn off a single flag from the default set of warning
     194flags, you can use the CXXFLAGS variable, since this is passed after
     195WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
     196used by default when g++ is detected) you can use
     197`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
  • LICENSE

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

    r555 r840  
    1212        m4/lx_check_glpk.m4 \
    1313        m4/lx_check_soplex.m4 \
     14        m4/lx_check_coin.m4 \
    1415        CMakeLists.txt \
    1516        cmake/FindGhostscript.cmake \
     17        cmake/FindCPLEX.cmake \
    1618        cmake/FindGLPK.cmake \
     19        cmake/FindCOIN.cmake \
     20        cmake/LEMONConfig.cmake.in \
    1721        cmake/version.cmake.in \
    1822        cmake/version.cmake \
     
    4044include test/Makefile.am
    4145include doc/Makefile.am
    42 include demo/Makefile.am
    4346include tools/Makefile.am
     47include scripts/Makefile.am
     48
     49DIST_SUBDIRS = demo
     50
     51demo:
     52        $(MAKE) $(AM_MAKEFLAGS) -C demo
    4453
    4554MRPROPERFILES = \
     
    6978        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    7079
    71 .PHONY: mrproper dist-bz2 distcheck-bz2
     80.PHONY: demo mrproper dist-bz2 distcheck-bz2
  • NEWS

    r534 r1277  
     12013-08-10 Version 1.2.4 released
     2
     3        Bugfix release.
     4
     5        #432: Add missing doc/template.h and doc/references.bib to release
     6              tarball
     7        #433: Support shared library build
     8        ----: Update CPLEX lookup
     9        ----: Make CBC interface compatible with latest CBC releases
     10        ----: Intel C++ compatibility fixes
     11        #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
     12        #444: Bugfix in path copy constructors and assignment operators
     13        #447: Bugfix in AllArcLookUp<>
     14        #448: Bugfix in adaptor_test.cc
     15        #449: Fix clang compilation warnings and errors
     16        #440: Fix a bug + remove redundant typedefs in dimacs-solver
     17        #453: Avoid GCC 4.7 compiler warnings
     18        #445: Fix missing initialization in CplexEnv::CplexEnv()
     19        #461: Bugfix in assert.h
     20        #470: Fix compilation issues related to various gcc versions
     21        #439: Bugfix in biNodeConnected()
     22        #469: Bugfix in test/maps_test.cc
     23
     242011-11-09 Version 1.2.3 released
     25
     26        Bugfix release.
     27
     28        #428: Add missing lemon/lemon.pc.cmake to the release tarball
     29        #429: Fix VS warnings
     30        #430: Fix LpBase::Constr two-side limit bug
     31
     322011-08-08 Version 1.2.2 released
     33
     34        Bugfix release.
     35
     36        #392: Bug fix in Dfs::start(s,t)
     37        #414: Fix wrong initialization in Preflow
     38        #404: Update Doxygen configuration
     39        #416: Support tests with valgrind
     40        #418: Better Win CodeBlock/MinGW support
     41        #419: Backport build environment improvements from the main branch
     42              - Build of mip_test and lp_test precede the running of the tests
     43              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
     44              - Do not look for COIN_VOL libraries
     45        #382: Allow lgf file without Arc maps
     46        #417: Bug fix in CostScaling
     47
     482010-10-21 Version 1.2.1 released
     49
     50        Bugfix release.
     51
     52        #366: Fix Pred[Matrix]MapPath::empty()
     53        #371: Bug fix in (di)graphCopy()
     54              The target graph is cleared before adding nodes and arcs/edges.
     55
     56        #364: Add missing UndirectedTags
     57        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
     58        #372: Fix a critical bug in preflow
     59
     602010-03-19 Version 1.2 released
     61
     62        This is major feature release
     63
     64        * New algorithms
     65          * Bellman-Ford algorithm (#51)
     66          * Minimum mean cycle algorithms (#179)
     67            * Karp, Hartman-Orlin and Howard algorithms
     68          * New minimum cost flow algorithms (#180)
     69            * Cost Scaling algorithms
     70            * Capacity Scaling algorithm
     71            * Cycle-Canceling algorithms
     72          * Planarity related algorithms (#62)
     73            * Planarity checking algorithm
     74            * Planar embedding algorithm
     75            * Schnyder's planar drawing algorithm
     76            * Coloring planar graphs with five or six colors
     77          * Fractional matching algorithms (#314)
     78        * New data structures
     79          * StaticDigraph structure (#68)
     80          * Several new priority queue structures (#50, #301)
     81            * Fibonacci, Radix, Bucket, Pairing, Binomial
     82              D-ary and fourary heaps (#301)
     83          * Iterable map structures (#73)
     84        * Other new tools and functionality
     85          * Map utility functions (#320)
     86          * Reserve functions are added to ListGraph and SmartGraph (#311)
     87          * A resize() function is added to HypercubeGraph (#311)
     88          * A count() function is added to CrossRefMap (#302)
     89          * Support for multiple targets in Suurballe using fullInit() (#181)
     90          * Traits class and named parameters for Suurballe (#323)
     91          * Separate reset() and resetParams() functions in NetworkSimplex
     92            to handle graph changes (#327)
     93          * tolerance() functions are added to HaoOrlin (#306)
     94        * Implementation improvements
     95          * Improvements in weighted matching algorithms (#314)
     96            * Jumpstart initialization
     97          * ArcIt iteration is based on out-arc lists instead of in-arc lists
     98            in ListDigraph (#311)
     99          * Faster add row operation in CbcMip (#203)
     100          * Better implementation for split() in ListDigraph (#311)
     101          * ArgParser can also throw exception instead of exit(1) (#332)
     102        * Miscellaneous
     103          * A simple interactive bootstrap script
     104          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
     105                #316,#319)
     106            * BibTeX references in the doc (#184)
     107          * Optionally use valgrind when running tests
     108          * Also check ReferenceMapTag in concept checks (#312)
     109          * dimacs-solver uses long long type by default.
     110        * Several bugfixes (compared to release 1.1):
     111          #295: Suppress MSVC warnings using pragmas
     112          ----: Various CMAKE related improvements
     113                * Remove duplications from doc/CMakeLists.txt
     114                * Rename documentation install folder from 'docs' to 'html'
     115                * Add tools/CMakeLists.txt to the tarball
     116                * Generate and install LEMONConfig.cmake
     117                * Change the label of the html project in Visual Studio
     118                * Fix the check for the 'long long' type
     119                * Put the version string into config.h
     120                * Minor CMake improvements
     121                * Set the version to 'hg-tip' if everything fails
     122          #311: Add missing 'explicit' keywords
     123          #302: Fix the implementation and doc of CrossRefMap
     124          #308: Remove duplicate list_graph.h entry from source list
     125          #307: Bugfix in Preflow and Circulation
     126          #305: Bugfix and extension in the rename script
     127          #312: Also check ReferenceMapTag in concept checks
     128          #250: Bugfix in pathSource() and pathTarget()
     129          #321: Use pathCopy(from,to) instead of copyPath(to,from)
     130          #322: Distribure LEMONConfig.cmake.in
     131          #330: Bug fix in map_extender.h
     132          #336: Fix the date field comment of graphToEps() output
     133          #323: Bug fix in Suurballe
     134          #335: Fix clear() function in ExtendFindEnum
     135          #337: Use void* as the LPX object pointer
     136          #317: Fix (and improve) error message in mip_test.cc
     137                Remove unnecessary OsiCbc dependency
     138          #356: Allow multiple executions of weighted matching algorithms (#356)
     139
     1402009-05-13 Version 1.1 released
     141
     142        This is the second stable release of the 1.x series. It
     143        features a better coverage of the tools available in the 0.x
     144        series, a thoroughly reworked LP/MIP interface plus various
     145        improvements in the existing tools.
     146
     147        * Much improved M$ Windows support
     148          * Various improvements in the CMAKE build system
     149          * Compilation warnings are fixed/suppressed
     150        * Support IBM xlC compiler
     151        * New algorithms
     152          * Connectivity related algorithms (#61)
     153          * Euler walks (#65)
     154          * Preflow push-relabel max. flow algorithm (#176)
     155          * Circulation algorithm (push-relabel based) (#175)
     156          * Suurballe algorithm (#47)
     157          * Gomory-Hu algorithm (#66)
     158          * Hao-Orlin algorithm (#58)
     159          * Edmond's maximum cardinality and weighted matching algorithms
     160            in general graphs (#48,#265)
     161          * Minimum cost arborescence/branching (#60)
     162          * Network Simplex min. cost flow algorithm (#234)
     163        * New data structures
     164          * Full graph structure (#57)
     165          * Grid graph structure (#57)
     166          * Hypercube graph structure (#57)
     167          * Graph adaptors (#67)
     168          * ArcSet and EdgeSet classes (#67)
     169          * Elevator class (#174)
     170        * Other new tools
     171          * LP/MIP interface (#44)
     172            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
     173          * Reader for the Nauty file format (#55)
     174          * DIMACS readers (#167)
     175          * Radix sort algorithms (#72)
     176          * RangeIdMap and CrossRefMap (#160)
     177        * New command line tools
     178          * DIMACS to LGF converter (#182)
     179          * lgf-gen - a graph generator (#45)
     180          * DIMACS solver utility (#226)
     181        * Other code improvements
     182          * Lognormal distribution added to Random (#102)
     183          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
     184          * The standard maps of graphs are guaranteed to be
     185            reference maps (#190)
     186        * Miscellaneous
     187          * Various doc improvements
     188          * Improved 0.x -> 1.x converter script
     189
     190        * Several bugfixes (compared to release 1.0):
     191          #170: Bugfix SmartDigraph::split()
     192          #171: Bugfix in SmartGraph::restoreSnapshot()
     193          #172: Extended test cases for graphs and digraphs
     194          #173: Bugfix in Random
     195                * operator()s always return a double now
     196                * the faulty real<Num>(Num) and real<Num>(Num,Num)
     197                  have been removed
     198          #187: Remove DijkstraWidestPathOperationTraits
     199          #61:  Bugfix in DfsVisit
     200          #193: Bugfix in GraphReader::skipSection()
     201          #195: Bugfix in ConEdgeIt()
     202          #197: Bugfix in heap unionfind
     203                * This bug affects Edmond's general matching algorithms
     204          #207: Fix 'make install' without 'make html' using CMAKE
     205          #208: Suppress or fix VS2008 compilation warnings
     206          ----: Update the LEMON icon
     207          ----: Enable the component-based installer
     208                (in installers made by CPACK)
     209          ----: Set the proper version for CMAKE in the tarballs
     210                (made by autotools)
     211          ----: Minor clarification in the LICENSE file
     212          ----: Add missing unistd.h include to time_measure.h
     213          #204: Compilation bug fixed in graph_to_eps.h with VS2005
     214          #214,#215: windows.h should never be included by LEMON headers
     215          #230: Build systems check the availability of 'long long' type
     216          #229: Default implementation of Tolerance<> is used for integer types
     217          #211,#212: Various fixes for compiling on AIX
     218          ----: Improvements in CMAKE config
     219                - docs is installed in share/doc/
     220                - detects newer versions of Ghostscript
     221          #239: Fix missing 'inline' specifier in time_measure.h
     222          #274,#280: Install lemon/config.h
     223          #275: Prefix macro names with LEMON_ in lemon/config.h
     224          ----: Small script for making the release tarballs added
     225          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     226
    12272009-03-27 LEMON joins to the COIN-OR initiative
    2228
     
    82342008-10-13 Version 1.0 released
    9235
    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
     236        This is the first stable release of LEMON. Compared to the 0.x
     237        release series, it features a considerably smaller but more
     238        matured set of tools. The API has also completely revised and
     239        changed in several places.
     240
     241        * The major name changes compared to the 0.x series (see the
    16242          Migration Guide in the doc for more details)
    17243          * Graph -> Digraph, UGraph -> Graph
    18244          * 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)
     245          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     246        * Other improvements
     247          * Better documentation
     248          * Reviewed and cleaned up codebase
     249          * CMake based build system (along with the autotools based one)
     250        * Contents of the library (ported from 0.x)
     251          * Algorithms
     252            * breadth-first search (bfs.h)
     253            * depth-first search (dfs.h)
     254            * Dijkstra's algorithm (dijkstra.h)
     255            * Kruskal's algorithm (kruskal.h)
     256          * Data structures
     257            * graph data structures (list_graph.h, smart_graph.h)
     258            * path data structures (path.h)
     259            * binary heap data structure (bin_heap.h)
     260            * union-find data structures (unionfind.h)
     261            * miscellaneous property maps (maps.h)
     262            * two dimensional vector and bounding box (dim2.h)
    37263          * Concepts
    38             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     264            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    39265              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
     266            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     267              concepts/path.h)
     268          * Tools
     269            * Mersenne twister random number generator (random.h)
     270            * tools for measuring cpu and wall clock time (time_measure.h)
     271            * tools for counting steps and events (counter.h)
     272            * tool for parsing command line arguments (arg_parser.h)
     273            * tool for visualizing graphs (graph_to_eps.h)
     274            * tools for reading and writing data in LEMON Graph Format
    49275              (lgf_reader.h, lgf_writer.h)
    50276            * tools to handle the anomalies of calculations with
    51               floating point numbers (tolerance.h)
     277              floating point numbers (tolerance.h)
    52278            * 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)
     279          * Infrastructure
     280            * extended assertion handling (assert.h)
     281            * exception classes and error handling (error.h)
     282            * concept checking (concept_check.h)
     283            * 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 r685  
     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)
     
    1954
    2055MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
     56
     57IF(GLPK_FOUND)
     58  SET(LEMON_HAVE_LP TRUE)
     59  SET(LEMON_HAVE_MIP TRUE)
     60  SET(LEMON_HAVE_GLPK TRUE)
     61ENDIF(GLPK_FOUND)
  • cmake/version.cmake.in

    r503 r725  
    1 SET(PROJECT_NAME "@PACKAGE_NAME@")
    2 SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
     1SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
  • configure.ac

    r564 r1276  
    33dnl Version information.
    44m4_define([lemon_version_number],
    5         [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     5          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
    66dnl m4_define([lemon_version_number], [])
    77m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
     8m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
    99m4_define([lemon_version], [ifelse(lemon_version_number(),
    10                            [],
    11                            [lemon_hg_path().lemon_hg_revision()],
    12                            [lemon_version_number()])])
     10                           [],
     11                           [ifelse(lemon_hg_revision(),
     12                           [],
     13                           [hg-tip],
     14                           [lemon_hg_path().lemon_hg_revision()])],
     15                           [lemon_version_number()])])
    1316
    1417AC_PREREQ([2.59])
     
    1619AC_CONFIG_AUX_DIR([build-aux])
    1720AC_CONFIG_MACRO_DIR([m4])
    18 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
     21AM_INIT_AUTOMAKE([-Wall foreign subdir-objects nostdinc])
    1922AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2023AC_CONFIG_HEADERS([config.h lemon/config.h])
     24
     25AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
    2126
    2227dnl Do compilation tests using the C++ compiler.
     
    2631AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
    2732if test x"$long_long_found" = x"yes"; then
    28   AC_DEFINE([HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
     33  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
    2934fi
    3035
     
    3742
    3843AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    3945AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4046
     
    6066LX_CHECK_CPLEX
    6167LX_CHECK_SOPLEX
    62 LX_CHECK_CLP
     68LX_CHECK_COIN
    6369
    6470AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    6571AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    66 
    67 dnl Disable/enable building the demo programs.
    68 AC_ARG_ENABLE([demo],
    69 AS_HELP_STRING([--enable-demo], [build the demo programs])
    70 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    71               [], [enable_demo=no])
    72 AC_MSG_CHECKING([whether to build the demo programs])
    73 if test x"$enable_demo" != x"no"; then
    74   AC_MSG_RESULT([yes])
    75 else
    76   AC_MSG_RESULT([no])
    77 fi
    78 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    7972
    8073dnl Disable/enable building the binary tools.
     
    9083fi
    9184AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
     85
     86dnl Support for running test cases using valgrind.
     87use_valgrind=no
     88AC_ARG_ENABLE([valgrind],
     89AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
     90              [use_valgrind=yes])
     91
     92if [[ "$use_valgrind" = "yes" ]]; then
     93  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
     94
     95  if [[ "$HAVE_VALGRIND" = "no" ]]; then
     96    AC_MSG_ERROR([Valgrind not found in PATH.])
     97  fi
     98fi
     99AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    92100
    93101dnl Checks for header files.
     
    107115dnl Add dependencies on files generated by configure.
    108116AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    109   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     117  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    110118
    111119AC_CONFIG_FILES([
    112120Makefile
     121demo/Makefile
    113122cmake/version.cmake
    114123doc/Doxyfile
     124doc/mainpage.dox
    115125lemon/lemon.pc
    116126])
     
    132142echo SOPLEX support................ : $lx_soplex_found
    133143echo CLP support................... : $lx_clp_found
     144echo CBC support................... : $lx_cbc_found
    134145echo
    135 echo Build demo programs........... : $enable_demo
    136146echo Build additional tools........ : $enable_tools
     147echo Use valgrind for tests........ : $use_valgrind
    137148echo
    138149echo The packace will be installed in
  • 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/Makefile.am

    r415 r611  
    1 EXTRA_DIST += \
    2         demo/CMakeLists.txt \
    3         demo/digraph.lgf
     1AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    5 if WANT_DEMO
     3AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     4LDADD = $(top_builddir)/lemon/libemon.la
    65
    7 noinst_PROGRAMS += \
    8         demo/arg_parser_demo \
    9         demo/graph_to_eps_demo \
    10         demo/lgf_demo
     6EXTRA_DIST = \
     7        CMakeLists.txt \
     8        digraph.lgf
    119
    12 endif WANT_DEMO
     10noinst_PROGRAMS = \
     11        arg_parser_demo \
     12        graph_to_eps_demo \
     13        lgf_demo
    1314
    14 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
    15 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
    16 demo_lgf_demo_SOURCES = demo/lgf_demo.cc
     15arg_parser_demo_SOURCES = arg_parser_demo.cc
     16graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
     17lgf_demo_SOURCES = lgf_demo.cc
  • 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 r1110  
    44SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
     6SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     7
    68CONFIGURE_FILE(
    79  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    810  ${PROJECT_BINARY_DIR}/doc/Doxyfile
    9   @ONLY)
     11  @ONLY
     12)
    1013
    11 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     14CONFIGURE_FILE(
     15  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
     16  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
     17  @ONLY
     18)
     19
     20IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    1221  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     22  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     23  ADD_CUSTOM_TARGET(html
     24    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
     25    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
     26    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     27    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     28    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     29    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     30    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     31    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     32    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     33    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     34    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     35    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     36    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     37    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     38    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     39    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     40    COMMAND ${CMAKE_COMMAND} -E remove_directory html
     41    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
     42    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     43    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     44  )
     45
     46  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     47
    1348  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})
     49    INSTALL(
     50      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     51      DESTINATION share/doc/lemon/html
     52      COMPONENT html_documentation
     53    )
    2654  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)
     55    INSTALL(
     56      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     57      DESTINATION doc
     58      COMPONENT html_documentation
     59    )
     60  ENDIF()
     61
     62ENDIF()
     63
     64IF(WGET_FOUND)
     65ADD_CUSTOM_TARGET(update-external-tags
     66  COMMAND ${CMAKE_COMMAND} -E make_directory dl
     67  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
     68  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
     69  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
     70  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
     71  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
     72  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     73  )
     74ENDIF()
  • doc/Doxyfile.in

    r379 r1110  
    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"
    7580#---------------------------------------------------------------------------
    7681# configuration options related to warning and progress messages
     
    9297                         "@abs_top_srcdir@/demo" \
    9398                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     99                         "@abs_top_srcdir@/test/test_tools.h" \
     100                         "@abs_top_builddir@/doc/mainpage.dox" \
     101                         "@abs_top_builddir@/doc/references.dox"
    95102INPUT_ENCODING         = UTF-8
    96103FILE_PATTERNS          = *.h \
     
    112119FILTER_PATTERNS        =
    113120FILTER_SOURCE_FILES    = NO
     121FILTER_SOURCE_PATTERNS =
    114122#---------------------------------------------------------------------------
    115123# configuration options related to source browsing
    116124#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     125SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118126INLINE_SOURCES         = NO
    119127STRIP_CODE_COMMENTS    = YES
     
    138146HTML_FOOTER            =
    139147HTML_STYLESHEET        =
     148HTML_COLORSTYLE_HUE    = 220
     149HTML_COLORSTYLE_SAT    = 100
     150HTML_COLORSTYLE_GAMMA  = 80
     151HTML_TIMESTAMP         = YES
    140152HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     153HTML_DYNAMIC_SECTIONS  = YES
    142154GENERATE_DOCSET        = NO
    143155DOCSET_FEEDNAME        = "Doxygen generated docs"
    144156DOCSET_BUNDLE_ID       = org.doxygen.Project
     157DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     158DOCSET_PUBLISHER_NAME  = Publisher
    145159GENERATE_HTMLHELP      = NO
    146160CHM_FILE               =
     
    154168QHP_NAMESPACE          = org.doxygen.Project
    155169QHP_VIRTUAL_FOLDER     = doc
     170QHP_CUST_FILTER_NAME   =
     171QHP_CUST_FILTER_ATTRS  =
     172QHP_SECT_FILTER_ATTRS  =
    156173QHG_LOCATION           =
     174GENERATE_ECLIPSEHELP   = NO
     175ECLIPSE_DOC_ID         = org.doxygen.Project
    157176DISABLE_INDEX          = NO
    158177ENUM_VALUES_PER_LINE   = 4
    159178GENERATE_TREEVIEW      = NO
     179USE_INLINE_TREES       = NO
    160180TREEVIEW_WIDTH         = 250
     181EXT_LINKS_IN_WINDOW    = NO
    161182FORMULA_FONTSIZE       = 10
     183FORMULA_TRANSPARENT    = YES
     184USE_MATHJAX            = NO
     185MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     186SEARCHENGINE           = YES
     187SERVER_BASED_SEARCH    = NO
    162188#---------------------------------------------------------------------------
    163189# configuration options related to the LaTeX output
     
    176202LATEX_BATCHMODE        = NO
    177203LATEX_HIDE_INDICES     = NO
     204LATEX_SOURCE_CODE      = NO
    178205#---------------------------------------------------------------------------
    179206# configuration options related to the RTF output
     
    224251SKIP_FUNCTION_MACROS   = YES
    225252#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     253# Configuration::additions related to external references
     254#---------------------------------------------------------------------------
     255TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    229256GENERATE_TAGFILE       = html/lemon.tag
    230257ALLEXTERNALS           = NO
     
    238265HIDE_UNDOC_RELATIONS   = YES
    239266HAVE_DOT               = YES
     267DOT_NUM_THREADS        = 0
    240268DOT_FONTNAME           = FreeSans
    241269DOT_FONTSIZE           = 10
     
    255283DOT_PATH               =
    256284DOTFILE_DIRS           =
     285MSCFILE_DIRS           =
    257286DOT_GRAPH_MAX_NODES    = 50
    258287MAX_DOT_GRAPH_DEPTH    = 0
     
    261290GENERATE_LEGEND        = YES
    262291DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

    r316 r1036  
    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="dirs" visible="yes" title="" intro=""/>
     21    <tab type="examples" visible="yes" title="" intro=""/>
     22    <tab type="pages" visible="yes" title="" intro=""/>
    2323  </navindex>
    2424
  • doc/Makefile.am

    r349 r1115  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
     11        doc/min_cost_flow.dox \
    1112        doc/named-param.dox \
    1213        doc/namespaces.dox \
     14        doc/references.bib \
     15        doc/template.h \
    1316        doc/html \
    1417        doc/CMakeLists.txt
     
    2225        nodeshape_4.eps
    2326
     27DOC_EPS_IMAGES27 = \
     28        bipartite_matching.eps \
     29        bipartite_partitions.eps \
     30        connected_components.eps \
     31        edge_biconnected_components.eps \
     32        matching.eps \
     33        node_biconnected_components.eps \
     34        planar.eps \
     35        strongly_connected_components.eps
     36
    2437DOC_EPS_IMAGES = \
    25         $(DOC_EPS_IMAGES18)
     38        $(DOC_EPS_IMAGES18) \
     39        $(DOC_EPS_IMAGES27)
    2640
    2741DOC_PNG_IMAGES = \
     
    4660        fi
    4761
    48 html-local: $(DOC_PNG_IMAGES)
     62$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
     63        -mkdir doc/gen-images
     64        if test ${gs_found} = yes; then \
     65          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
     66        else \
     67          echo; \
     68          echo "Ghostscript not found."; \
     69          echo; \
     70          exit 1; \
     71        fi
     72
     73references.dox: doc/references.bib
     74        if test ${python_found} = yes; then \
     75          cd doc; \
     76          python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
     77          cd ..; \
     78        else \
     79          echo; \
     80          echo "Python not found."; \
     81          echo; \
     82          exit 1; \
     83        fi
     84
     85html-local: $(DOC_PNG_IMAGES) references.dox
    4986        if test ${doxygen_found} = yes; then \
    5087          cd doc; \
     
    71108install-html-local: doc/html
    72109        @$(NORMAL_INSTALL)
    73         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     110        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    74111        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    75112          f="`echo $$p | sed -e 's|^.*/||'`"; \
    76           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    77           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     113          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     114          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    78115        done
    79116
     
    82119        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    83120          f="`echo $$p | sed -e 's|^.*/||'`"; \
    84           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    85           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     121          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     122          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    86123        done
    87124
  • doc/groups.dox

    r606 r963  
    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).
     
    139139
    140140/**
    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 /**
    151141@defgroup maps Maps
    152142@ingroup datas
     
    237227
    238228/**
    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 /**
    247229@defgroup paths Path Structures
    248230@ingroup datas
     
    257239any kind of path structure.
    258240
    259 \sa lemon::concepts::Path
     241\sa \ref concepts::Path "Path concept"
     242*/
     243
     244/**
     245@defgroup heaps Heap Structures
     246@ingroup datas
     247\brief %Heap structures implemented in LEMON.
     248
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
    260263*/
    261264
     
    270273
    271274/**
     275@defgroup geomdat Geometric Data Structures
     276@ingroup auxdat
     277\brief Geometric data structures implemented in LEMON.
     278
     279This group contains geometric data structures implemented in LEMON.
     280
     281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     282   vector with the usual operations.
     283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     284   rectangular bounding box of a set of \ref lemon::dim2::Point
     285   "dim2::Point"'s.
     286*/
     287
     288/**
    272289@defgroup algs Algorithms
    273290\brief This group contains the several algorithms
     
    284301
    285302This group contains the common graph search algorithms, namely
    286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     303\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     304\ref clrs01algorithms.
    287305*/
    288306
     
    292310\brief Algorithms for finding shortest paths.
    293311
    294 This group contains the algorithms for finding shortest paths in digraphs.
     312This group contains the algorithms for finding shortest paths in digraphs
     313\ref clrs01algorithms.
    295314
    296315 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    300319   but the digraph should not contain directed cycles with negative total
    301320   length.
    302  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    303    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    304    lenghts can be either positive or negative, but the digraph should
    305    not contain directed cycles with negative total length.
    306321 - \ref Suurballe A successive shortest path algorithm for finding
    307322   arc-disjoint paths between two nodes having minimum total length.
     
    309324
    310325/**
     326@defgroup spantree Minimum Spanning Tree Algorithms
     327@ingroup algs
     328\brief Algorithms for finding minimum cost spanning trees and arborescences.
     329
     330This group contains the algorithms for finding minimum cost spanning
     331trees and arborescences \ref clrs01algorithms.
     332*/
     333
     334/**
    311335@defgroup max_flow Maximum Flow Algorithms
    312336@ingroup algs
     
    314338
    315339This group contains the algorithms for finding maximum flows and
    316 feasible circulations.
     340feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    317341
    318342The \e maximum \e flow \e problem is to find a flow of maximum value between
    319343a 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
     344digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321345\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
     346A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323347following optimization problem.
    324348
    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]
    329 
    330 LEMON 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
    337 fastest 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
     349\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     350\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     351    \quad \forall u\in V\setminus\{s,t\} \f]
     352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
     353
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
     358
     359\ref Circulation is a preflow push-relabel algorithm implemented directly
     360for finding feasible circulations, which is a somewhat different problem,
     361but it is strongly related to maximum flow.
     362For more information, see \ref Circulation.
     363*/
     364
     365/**
     366@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    344367@ingroup algs
    345368
     
    347370
    348371This 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.
     372circulations \ref amo93networkflows. For more information about this
     373problem and its dual solution, see \ref min_cost_flow
     374"Minimum Cost Flow Problem".
     375
     376LEMON contains several algorithms for this problem.
     377 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     378   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     379 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     380   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     381   \ref bunnagel98efficient.
     382 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     383   shortest path method \ref edmondskarp72theoretical.
     384 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     385   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     386
     387In general NetworkSimplex is the most efficient implementation,
     388but in special cases other algorithms could be faster.
     389For example, if the total supply and/or capacities are rather small,
     390CapacityScaling is usually the fastest algorithm (without effective scaling).
    377391*/
    378392
     
    392406
    393407\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]
     408    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    395409
    396410LEMON contains several algorithms related to minimum cut problems:
     
    398412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    399413  in directed graphs.
    400 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    401   calculating minimum cut in undirected graphs.
    402414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    403415  all-pairs minimum cut in undirected graphs.
     
    408420
    409421/**
    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
     422@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     423@ingroup algs
     424\brief Algorithms for finding minimum mean cycles.
     425
     426This group contains the algorithms for finding minimum mean cycles
     427\ref clrs01algorithms, \ref amo93networkflows.
     428
     429The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     430of minimum mean length (cost) in a digraph.
     431The mean length of a cycle is the average length of its arcs, i.e. the
     432ratio between the total length of the cycle and the number of arcs on it.
     433
     434This problem has an important connection to \e conservative \e length
     435\e functions, too. A length function on the arcs of a digraph is called
     436conservative if and only if there is no directed cycle of negative total
     437length. For an arbitrary length function, the negative of the minimum
     438cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     439arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     440function.
     441
     442LEMON contains three algorithms for solving the minimum mean cycle problem:
     443- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     444  \ref dasdan98minmeancycle.
     445- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     446  version of Karp's algorithm \ref dasdan98minmeancycle.
     447- \ref HowardMmc Howard's policy iteration algorithm
     448  \ref dasdan98minmeancycle.
     449
     450In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     451most efficient one, though the best known theoretical bound on its running
     452time is exponential.
     453Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     454run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     455typically faster due to the applied early termination scheme.
    431456*/
    432457
     
    436461\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437462
    438 This group contains algorithm objects and functions to calculate
     463This group contains the algorithms for calculating
    439464matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the arcs which does not shares common endpoints.
     465finding a subset of the edges for which each node has at most one incident
     466edge.
    441467
    442468There are several different algorithms for calculate matchings in
     
    448474
    449475The matching algorithms implemented in LEMON:
    450 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    451   for calculating maximum cardinality matching in bipartite graphs.
    452 - \ref PrBipartiteMatching Push-relabel algorithm
    453   for calculating maximum cardinality matching in bipartite graphs.
    454 - \ref MaxWeightedBipartiteMatching
    455   Successive shortest path algorithm for calculating maximum weighted
    456   matching and maximum weighted bipartite matching in bipartite graphs.
    457 - \ref MinCostMaxBipartiteMatching
    458   Successive shortest path algorithm for calculating minimum cost maximum
    459   matching in bipartite graphs.
    460476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    461477  maximum cardinality matching in general graphs.
     
    465481  Edmond's blossom shrinking algorithm for calculating maximum weighted
    466482  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.
     483- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     484  maximum cardinality fractional matching in general graphs.
     485- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     486  maximum weighted fractional matching in general graphs.
     487- \ref MaxWeightedPerfectFractionalMatching
     488  Augmenting path algorithm for calculating maximum weighted
     489  perfect fractional matching in general graphs.
     490
     491\image html matching.png
     492\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     493*/
     494
     495/**
     496@defgroup graph_properties Connectivity and Other Graph Properties
     497@ingroup algs
     498\brief Algorithms for discovering the graph properties
     499
     500This group contains the algorithms for discovering the graph properties
     501like connectivity, bipartiteness, euler property, simplicity etc.
     502
     503\image html connected_components.png
     504\image latex connected_components.eps "Connected components" width=\textwidth
     505*/
     506
     507/**
     508@defgroup planar Planarity Embedding and Drawing
     509@ingroup algs
     510\brief Algorithms for planarity checking, embedding and drawing
     511
     512This group contains the algorithms for planarity checking,
     513embedding and drawing.
     514
     515\image html planar.png
     516\image latex planar.eps "Plane graph" width=\textwidth
    479517*/
    480518
     
    486524This group contains some algorithms implemented in LEMON
    487525in 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.
    497526*/
    498527
     
    507536
    508537/**
    509 @defgroup lp_group Lp and Mip Solvers
     538@defgroup lp_group LP and MIP Solvers
    510539@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.
    516 */
    517 
    518 /**
    519 @defgroup lp_utils Tools for Lp and Mip Solvers
    520 @ingroup lp_group
    521 \brief Helper tools to the Lp and Mip solvers.
    522 
    523 This group adds some helper tools to general optimization framework
    524 implemented in LEMON.
    525 */
    526 
    527 /**
    528 @defgroup metah Metaheuristics
    529 @ingroup gen_opt_group
    530 \brief Metaheuristics for LEMON library.
    531 
    532 This group contains some metaheuristic optimization tools.
     540\brief LP and MIP solver interfaces for LEMON.
     541
     542This group contains LP and MIP solver interfaces for LEMON.
     543Various LP solvers could be used in the same manner with this
     544high-level interface.
     545
     546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     547\ref cplex, \ref soplex.
    533548*/
    534549
     
    603618
    604619/**
    605 @defgroup dimacs_group DIMACS format
     620@defgroup dimacs_group DIMACS Format
    606621@ingroup io_group
    607622\brief Read and write files in DIMACS format
     
    652667\brief Skeleton and concept checking classes for graph structures
    653668
    654 This group contains the skeletons and concept checking classes of LEMON's
    655 graph structures and helper classes used to implement these.
     669This group contains the skeletons and concept checking classes of
     670graph structures.
    656671*/
    657672
     
    665680
    666681/**
     682@defgroup tools Standalone Utility Applications
     683
     684Some utility applications are listed here.
     685
     686The standard compilation procedure (<tt>./configure;make</tt>) will compile
     687them, as well.
     688*/
     689
     690/**
    667691\anchor demoprograms
    668692
     
    672696the \c demo subdirectory of the source tree.
    673697
    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.
     698In order to compile them, use the <tt>make demo</tt> or the
     699<tt>make check</tt> commands.
    685700*/
    686701
  • doc/lgf.dox

    r463 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464\endcode
    6565
    66 The \c \@arcs section is very similar to the \c \@nodes section,
    67 it again starts with a header line describing the names of the maps,
    68 but the \c "label" map is not obligatory here. The following lines
    69 describe the arcs. The first two tokens of each line are
    70 the source and the target node of the arc, respectively, then come the map
     66The \c \@arcs section is very similar to the \c \@nodes section, it
     67again starts with a header line describing the names of the maps, but
     68the \c "label" map is not obligatory here. The following lines
     69describe the arcs. The first two tokens of each line are the source
     70and the target node of the arc, respectively, then come the map
    7171values. The source and target tokens must be node labels.
    7272
     
    7979\endcode
    8080
     81If there is no map in the \c \@arcs section at all, then it must be
     82indicated by a sole '-' sign in the first line.
     83
     84\code
     85 @arcs
     86         -
     87 1   2
     88 1   3
     89 2   3
     90\endcode
     91
    8192The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    8293also store the edge set of an undirected graph. In such case there is
    8394a 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
     95have the same caption with \c '+' and \c '-' prefix, then these columns
    8596can be regarded as the values of an arc map.
    8697
  • lemon/CMakeLists.txt

    r596 r1113  
    77  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
    88  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11CONFIGURE_FILE(
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     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(${CPLEX_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()
    3051
    3152ADD_LIBRARY(lemon ${LEMON_SOURCES})
     53IF(UNIX)
     54  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     55ENDIF()
    3256
    3357INSTALL(
    3458  TARGETS lemon
    3559  ARCHIVE DESTINATION lib
    36   COMPONENT library)
     60  LIBRARY DESTINATION lib
     61  COMPONENT library
     62)
    3763
    3864INSTALL(
     
    4066  DESTINATION include/lemon
    4167  COMPONENT headers
    42   FILES_MATCHING PATTERN "*.h")
     68  FILES_MATCHING PATTERN "*.h"
     69)
     70
     71INSTALL(
     72  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
     73  DESTINATION include/lemon
     74  COMPONENT headers
     75)
     76
     77INSTALL(
     78  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     79  DESTINATION lib/pkgconfig
     80)
     81
  • lemon/Makefile.am

    r597 r1110  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt
     3        lemon/lemon.pc.cmake \
     4        lemon/CMakeLists.txt \
     5        lemon/config.h.cmake
    46
    57pkgconfig_DATA += lemon/lemon.pc
     
    1315        lemon/lp_base.cc \
    1416        lemon/lp_skeleton.cc \
    15         lemon/random.cc \
     17        lemon/random.cc \
    1618        lemon/bits/windows.cc
    1719
     20nodist_lemon_HEADERS = lemon/config.h   
    1821
    1922lemon_libemon_la_CXXFLAGS = \
     
    2225        $(CPLEX_CFLAGS) \
    2326        $(SOPLEX_CXXFLAGS) \
    24         $(CLP_CXXFLAGS)
     27        $(CLP_CXXFLAGS) \
     28        $(CBC_CXXFLAGS)
    2529
    2630lemon_libemon_la_LDFLAGS = \
     
    2832        $(CPLEX_LIBS) \
    2933        $(SOPLEX_LIBS) \
    30         $(CLP_LIBS)
     34        $(CLP_LIBS) \
     35        $(CBC_LIBS)
    3136
    3237if HAVE_GLPK
     
    4651endif
    4752
     53if HAVE_CBC
     54lemon_libemon_la_SOURCES += lemon/cbc.cc
     55endif
     56
    4857lemon_HEADERS += \
    4958        lemon/adaptors.h \
    5059        lemon/arg_parser.h \
    5160        lemon/assert.h \
     61        lemon/bellman_ford.h \
    5262        lemon/bfs.h \
    5363        lemon/bin_heap.h \
     64        lemon/binomial_heap.h \
     65        lemon/bucket_heap.h \
     66        lemon/capacity_scaling.h \
     67        lemon/cbc.h \
    5468        lemon/circulation.h \
    5569        lemon/clp.h \
     
    5771        lemon/concept_check.h \
    5872        lemon/connectivity.h \
     73        lemon/core.h \
     74        lemon/cost_scaling.h \
    5975        lemon/counter.h \
    60         lemon/core.h \
    6176        lemon/cplex.h \
     77        lemon/cycle_canceling.h \
    6278        lemon/dfs.h \
     79        lemon/dheap.h \
    6380        lemon/dijkstra.h \
    6481        lemon/dim2.h \
     
    6885        lemon/error.h \
    6986        lemon/euler.h \
     87        lemon/fib_heap.h \
     88        lemon/fractional_matching.h \
    7089        lemon/full_graph.h \
    7190        lemon/glpk.h \
     
    7392        lemon/graph_to_eps.h \
    7493        lemon/grid_graph.h \
     94        lemon/hartmann_orlin_mmc.h \
     95        lemon/howard_mmc.h \
    7596        lemon/hypercube_graph.h \
     97        lemon/karp_mmc.h \
    7698        lemon/kruskal.h \
    7799        lemon/hao_orlin.h \
     
    82104        lemon/lp_base.h \
    83105        lemon/lp_skeleton.h \
    84         lemon/list_graph.h \
    85106        lemon/maps.h \
     107        lemon/matching.h \
    86108        lemon/math.h \
    87         lemon/max_matching.h \
    88109        lemon/min_cost_arborescence.h \
    89110        lemon/nauty_reader.h \
     111        lemon/network_simplex.h \
     112        lemon/pairing_heap.h \
    90113        lemon/path.h \
     114        lemon/planarity.h \
    91115        lemon/preflow.h \
     116        lemon/quad_heap.h \
     117        lemon/radix_heap.h \
    92118        lemon/radix_sort.h \
    93119        lemon/random.h \
    94120        lemon/smart_graph.h \
    95121        lemon/soplex.h \
     122        lemon/static_graph.h \
    96123        lemon/suurballe.h \
    97124        lemon/time_measure.h \
     
    103130        lemon/bits/alteration_notifier.h \
    104131        lemon/bits/array_map.h \
    105         lemon/bits/base_extender.h \
    106132        lemon/bits/bezier.h \
    107133        lemon/bits/default_map.h \
  • lemon/adaptors.h

    r606 r1159  
    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).
     
    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 r959  
    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).
     
    3535namespace lemon {
    3636
     37  ///Exception used by ArgParser
     38
     39  ///Exception used by ArgParser.
     40  ///
     41  class ArgParserException : public Exception {
     42  public:
     43    /// Reasons for failure
     44
     45    /// Reasons for failure.
     46    ///
     47    enum Reason {
     48      HELP,         ///< <tt>--help</tt> option was given.
     49      UNKNOWN_OPT,  ///< Unknown option was given.
     50      INVALID_OPT   ///< Invalid combination of options.
     51    };
     52
     53  private:
     54    Reason _reason;
     55
     56  public:
     57    ///Constructor
     58    ArgParserException(Reason r) throw() : _reason(r) {}
     59    ///Virtual destructor
     60    virtual ~ArgParserException() throw() {}
     61    ///A short description of the exception
     62    virtual const char* what() const throw() {
     63      switch(_reason)
     64        {
     65        case HELP:
     66          return "lemon::ArgParseException: ask for help";
     67          break;
     68        case UNKNOWN_OPT:
     69          return "lemon::ArgParseException: unknown option";
     70          break;
     71        case INVALID_OPT:
     72          return "lemon::ArgParseException: invalid combination of options";
     73          break;
     74        }
     75      return "";
     76    }
     77    ///Return the reason for the failure
     78    Reason reason() const {return _reason; }
     79  };
     80
     81
    3782  ///Command line arguments parser
    3883
     
    116161                    const std::string &help,
    117162                    void (*func)(void *),void *data);
     163
     164    bool _exit_on_problems;
     165
     166    void _terminate(ArgParserException::Reason reason) const;
    118167
    119168  public:
     
    381430    const std::vector<std::string> &files() const { return _file_args; }
    382431
     432    ///Throw instead of exit in case of problems
     433    void throwOnProblems()
     434    {
     435      _exit_on_problems=false;
     436    }
    383437  };
    384438}
  • lemon/assert.h

    r463 r1242  
    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/bfs.h

    r525 r1127  
    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).
     
    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,
     
    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 r758  
    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/array_map.h

    r525 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).
     
    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 r1157  
    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 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).
     
    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 r1161  
    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-2010
    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 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    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 r1159  
    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
  • lemon/bits/map_extender.h

    r463 r867  
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
    39   public:
    40 
    4139    typedef _Map Parent;
     40    typedef typename Parent::GraphType GraphType;
     41
     42  public:
     43
    4244    typedef MapExtender Map;
    43 
    44 
    45     typedef typename Parent::Graph Graph;
    4645    typedef typename Parent::Key Item;
    4746
    4847    typedef typename Parent::Key Key;
    4948    typedef typename Parent::Value Value;
     49    typedef typename Parent::Reference Reference;
     50    typedef typename Parent::ConstReference ConstReference;
     51
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    5053
    5154    class MapIt;
     
    5760  public:
    5861
    59     MapExtender(const Graph& graph)
     62    MapExtender(const GraphType& graph)
    6063      : Parent(graph) {}
    6164
    62     MapExtender(const Graph& graph, const Value& value)
     65    MapExtender(const GraphType& graph, const Value& value)
    6366      : Parent(graph, value) {}
    6467
     
    7679  public:
    7780    class MapIt : public Item {
    78     public:
    79 
    80       typedef Item Parent;
     81      typedef Item Parent;
     82
     83    public:
     84
    8185      typedef typename Map::Value Value;
    8286
    83       MapIt() {}
    84 
    85       MapIt(Invalid i) : Parent(i) { }
    86 
    87       explicit MapIt(Map& _map) : map(_map) {
    88         map.notifier()->first(*this);
     87      MapIt() : map(NULL) {}
     88
     89      MapIt(Invalid i) : Parent(i), map(NULL) {}
     90
     91      explicit MapIt(Map& _map) : map(&_map) {
     92        map->notifier()->first(*this);
    8993      }
    9094
    9195      MapIt(const Map& _map, const Item& item)
     96        : Parent(item), map(&_map) {}
     97
     98      MapIt& operator++() {
     99        map->notifier()->next(*this);
     100        return *this;
     101      }
     102
     103      typename MapTraits<Map>::ConstReturnValue operator*() const {
     104        return (*map)[*this];
     105      }
     106
     107      typename MapTraits<Map>::ReturnValue operator*() {
     108        return (*map)[*this];
     109      }
     110
     111      void set(const Value& value) {
     112        map->set(*this, value);
     113      }
     114
     115    protected:
     116      Map* map;
     117
     118    };
     119
     120    class ConstMapIt : public Item {
     121      typedef Item Parent;
     122
     123    public:
     124
     125      typedef typename Map::Value Value;
     126
     127      ConstMapIt() : map(NULL) {}
     128
     129      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
     130
     131      explicit ConstMapIt(Map& _map) : map(&_map) {
     132        map->notifier()->first(*this);
     133      }
     134
     135      ConstMapIt(const Map& _map, const Item& item)
    92136        : Parent(item), map(_map) {}
    93137
    94       MapIt& operator++() {
    95         map.notifier()->next(*this);
     138      ConstMapIt& operator++() {
     139        map->notifier()->next(*this);
    96140        return *this;
    97141      }
     
    101145      }
    102146
    103       typename MapTraits<Map>::ReturnValue operator*() {
    104         return map[*this];
    105       }
    106 
    107       void set(const Value& value) {
    108         map.set(*this, value);
    109       }
    110 
    111     protected:
    112       Map& map;
    113 
    114     };
    115 
    116     class ConstMapIt : public Item {
    117     public:
    118 
    119       typedef Item Parent;
    120 
    121       typedef typename Map::Value Value;
    122 
    123       ConstMapIt() {}
    124 
    125       ConstMapIt(Invalid i) : Parent(i) { }
    126 
    127       explicit ConstMapIt(Map& _map) : map(_map) {
    128         map.notifier()->first(*this);
    129       }
    130 
    131       ConstMapIt(const Map& _map, const Item& item)
    132         : Parent(item), map(_map) {}
    133 
    134       ConstMapIt& operator++() {
    135         map.notifier()->next(*this);
    136         return *this;
    137       }
    138 
    139       typename MapTraits<Map>::ConstReturnValue operator*() const {
    140         return map[*this];
    141       }
    142 
    143     protected:
    144       const Map& map;
     147    protected:
     148      const Map* map;
    145149    };
    146150
    147151    class ItemIt : public Item {
    148     public:
    149 
    150       typedef Item Parent;
    151 
    152       ItemIt() {}
    153 
    154       ItemIt(Invalid i) : Parent(i) { }
    155 
    156       explicit ItemIt(Map& _map) : map(_map) {
    157         map.notifier()->first(*this);
     152      typedef Item Parent;
     153
     154    public:
     155      ItemIt() : map(NULL) {}
     156
     157
     158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     159
     160      explicit ItemIt(Map& _map) : map(&_map) {
     161        map->notifier()->first(*this);
    158162      }
    159163
    160164      ItemIt(const Map& _map, const Item& item)
    161         : Parent(item), map(_map) {}
     165        : Parent(item), map(&_map) {}
    162166
    163167      ItemIt& operator++() {
    164         map.notifier()->next(*this);
    165         return *this;
    166       }
    167 
    168     protected:
    169       const Map& map;
     168        map->notifier()->next(*this);
     169        return *this;
     170      }
     171
     172    protected:
     173      const Map* map;
    170174
    171175    };
     
    177181  template <typename _Graph, typename _Map>
    178182  class SubMapExtender : public _Map {
    179   public:
    180 
    181183    typedef _Map Parent;
     184    typedef _Graph GraphType;
     185
     186  public:
     187
    182188    typedef SubMapExtender Map;
    183 
    184     typedef _Graph Graph;
    185 
    186189    typedef typename Parent::Key Item;
    187190
    188191    typedef typename Parent::Key Key;
    189192    typedef typename Parent::Value Value;
     193    typedef typename Parent::Reference Reference;
     194    typedef typename Parent::ConstReference ConstReference;
     195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    190197
    191198    class MapIt;
     
    197204  public:
    198205
    199     SubMapExtender(const Graph& _graph)
     206    SubMapExtender(const GraphType& _graph)
    200207      : Parent(_graph), graph(_graph) {}
    201208
    202     SubMapExtender(const Graph& _graph, const Value& _value)
     209    SubMapExtender(const GraphType& _graph, const Value& _value)
    203210      : Parent(_graph, _value), graph(_graph) {}
    204211
     
    220227  public:
    221228    class MapIt : public Item {
    222     public:
    223 
    224       typedef Item Parent;
     229      typedef Item Parent;
     230
     231    public:
    225232      typedef typename Map::Value Value;
    226233
    227       MapIt() {}
    228 
    229       MapIt(Invalid i) : Parent(i) { }
    230 
    231       explicit MapIt(Map& _map) : map(_map) {
    232         map.graph.first(*this);
     234      MapIt() : map(NULL) {}
     235
     236      MapIt(Invalid i) : Parent(i), map(NULL) { }
     237
     238      explicit MapIt(Map& _map) : map(&_map) {
     239        map->graph.first(*this);
    233240      }
    234241
    235242      MapIt(const Map& _map, const Item& item)
    236         : Parent(item), map(_map) {}
     243        : Parent(item), map(&_map) {}
    237244
    238245      MapIt& operator++() {
    239         map.graph.next(*this);
     246        map->graph.next(*this);
    240247        return *this;
    241248      }
    242249
    243250      typename MapTraits<Map>::ConstReturnValue operator*() const {
    244         return map[*this];
     251        return (*map)[*this];
    245252      }
    246253
    247254      typename MapTraits<Map>::ReturnValue operator*() {
    248         return map[*this];
     255        return (*map)[*this];
    249256      }
    250257
    251258      void set(const Value& value) {
    252         map.set(*this, value);
    253       }
    254 
    255     protected:
    256       Map& map;
     259        map->set(*this, value);
     260      }
     261
     262    protected:
     263      Map* map;
    257264
    258265    };
    259266
    260267    class ConstMapIt : public Item {
    261     public:
    262 
    263       typedef Item Parent;
     268      typedef Item Parent;
     269
     270    public:
    264271
    265272      typedef typename Map::Value Value;
    266273
    267       ConstMapIt() {}
    268 
    269       ConstMapIt(Invalid i) : Parent(i) { }
    270 
    271       explicit ConstMapIt(Map& _map) : map(_map) {
    272         map.graph.first(*this);
     274      ConstMapIt() : map(NULL) {}
     275
     276      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
     277
     278      explicit ConstMapIt(Map& _map) : map(&_map) {
     279        map->graph.first(*this);
    273280      }
    274281
    275282      ConstMapIt(const Map& _map, const Item& item)
    276         : Parent(item), map(_map) {}
     283        : Parent(item), map(&_map) {}
    277284
    278285      ConstMapIt& operator++() {
    279         map.graph.next(*this);
     286        map->graph.next(*this);
    280287        return *this;
    281288      }
    282289
    283290      typename MapTraits<Map>::ConstReturnValue operator*() const {
    284         return map[*this];
    285       }
    286 
    287     protected:
    288       const Map& map;
     291        return (*map)[*this];
     292      }
     293
     294    protected:
     295      const Map* map;
    289296    };
    290297
    291298    class ItemIt : public Item {
    292     public:
    293 
    294       typedef Item Parent;
    295 
    296       ItemIt() {}
    297 
    298       ItemIt(Invalid i) : Parent(i) { }
    299 
    300       explicit ItemIt(Map& _map) : map(_map) {
    301         map.graph.first(*this);
     299      typedef Item Parent;
     300
     301    public:
     302      ItemIt() : map(NULL) {}</