COIN-OR::LEMON - Graph Library

Changes in / [906:e24922c56bc2:907:1937b6455b7d] in lemon-main


Ignore:
Files:
100 added
1 deleted
110 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r494 r866  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
     25doc/references.dox
     26cmake/version.cmake
    2627.dirstamp
    2728.libs/*
    2829.deps/*
    2930demo/*.eps
     31m4/libtool.m4
     32m4/ltoptions.m4
     33m4/ltsugar.m4
     34m4/ltversion.m4
     35m4/lt~obsolete.m4
    3036
    3137syntax: regexp
     
    3642^autom4te.cache/.*
    3743^build-aux/.*
    38 ^objs.*/.*
     44^.*objs.*/.*
    3945^test/[a-z_]*$
     46^tools/[a-z-_]*$
    4047^demo/.*_demo$
    41 ^build/.*
     48^.*build.*/.*
    4249^doc/gen-images/.*
    4350CMakeFiles
  • CMakeLists.txt

    r511 r902  
    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
    12 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
    13 
    14 INCLUDE(FindDoxygen)
    15 INCLUDE(FindGhostscript)
    16 
    17 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     6INCLUDE(FindPythonInterp)
     7
     8IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     9  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     10ELSEIF(DEFINED ENV{LEMON_VERSION})
     11  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
     12ELSE()
     13  EXECUTE_PROCESS(
     14    COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
     15    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     16    OUTPUT_VARIABLE HG_REVISION_PATH
     17    ERROR_QUIET
     18    OUTPUT_STRIP_TRAILING_WHITESPACE
     19  )
     20  EXECUTE_PROCESS(
     21    COMMAND hg id -i
     22    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     23    OUTPUT_VARIABLE HG_REVISION
     24    ERROR_QUIET
     25    OUTPUT_STRIP_TRAILING_WHITESPACE
     26  )
     27  IF(HG_REVISION STREQUAL "")
     28    SET(HG_REVISION_ID "hg-tip")
     29  ELSE()
     30    IF(HG_REVISION_PATH STREQUAL "")
     31      SET(HG_REVISION_ID ${HG_REVISION})
     32    ELSE()
     33      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
     34    ENDIF()
     35  ENDIF()
     36  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
     37ENDIF()
     38
     39SET(PROJECT_VERSION ${LEMON_VERSION})
     40
     41SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
     42
     43FIND_PACKAGE(Doxygen)
     44FIND_PACKAGE(Ghostscript)
     45FIND_PACKAGE(GLPK 4.33)
     46FIND_PACKAGE(CPLEX)
     47FIND_PACKAGE(COIN)
     48
     49IF(DEFINED ENV{LEMON_CXX_WARNING})
     50  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
     51ELSE()
     52  IF(CMAKE_COMPILER_IS_GNUCXX)
     53    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 -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     54    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     55    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
     56  ELSEIF(MSVC)
     57    # This part is unnecessary 'casue the same is set by the lemon/core.h.
     58    # Still keep it as an example.
     59    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
     60    # Suppressed warnings:
     61    # C4250: 'class1' : inherits 'class2::member' via dominance
     62    # C4355: 'this' : used in base member initializer list
     63    # C4503: 'function' : decorated name length exceeded, name was truncated
     64    # C4800: 'type' : forcing value to bool 'true' or 'false'
     65    #        (performance warning)
     66    # C4996: 'function': was declared deprecated
     67  ELSE()
     68    SET(CXX_WARNING "-Wall -W")
     69  ENDIF()
     70ENDIF()
     71SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
     72
     73SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
     74
     75SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
     76    "Flags used by the C++ compiler during maintainer builds."
     77    FORCE )
     78SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
     79    "Flags used by the C compiler during maintainer builds."
     80    FORCE )
     81SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     82    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     83    "Flags used for linking binaries during maintainer builds."
     84    FORCE )
     85SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
     86    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
     87    "Flags used by the shared libraries linker during maintainer builds."
     88    FORCE )
     89MARK_AS_ADVANCED(
     90    CMAKE_CXX_FLAGS_MAINTAINER
     91    CMAKE_C_FLAGS_MAINTAINER
     92    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
     93    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
     94
     95IF(CMAKE_CONFIGURATION_TYPES)
     96  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
     97  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
     98  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
     99      "Add the configurations that we need"
     100      FORCE)
     101 endif()
     102
     103IF(NOT CMAKE_BUILD_TYPE)
     104  SET(CMAKE_BUILD_TYPE "Release")
     105ENDIF()
     106
     107SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
     108    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
     109    FORCE )
     110
    18111
    19112INCLUDE(CheckTypeSize)
    20 CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
     113CHECK_TYPE_SIZE("long long" LONG_LONG)
     114SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    21115
    22116ENABLE_TESTING()
    23117
     118IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
     119  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
     120ELSE()
     121  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
     122ENDIF()
     123
    24124ADD_SUBDIRECTORY(lemon)
    25 ADD_SUBDIRECTORY(demo)
    26 ADD_SUBDIRECTORY(doc)
    27 ADD_SUBDIRECTORY(test)
    28 
    29 IF(WIN32)
     125IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     126  ADD_SUBDIRECTORY(demo)
     127  ADD_SUBDIRECTORY(tools)
     128  ADD_SUBDIRECTORY(doc)
     129  ADD_SUBDIRECTORY(test)
     130ENDIF()
     131
     132CONFIGURE_FILE(
     133  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     134  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     135  @ONLY
     136)
     137IF(UNIX)
     138  INSTALL(
     139    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     140    DESTINATION share/lemon/cmake
     141  )
     142ELSEIF(WIN32)
     143  INSTALL(
     144    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     145    DESTINATION cmake
     146  )
     147ENDIF()
     148
     149IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    30150  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    31151  SET(CPACK_PACKAGE_VENDOR "EGRES")
    32152  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    33     "LEMON - Library of Efficient Models and Optimization in Networks")
    34   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     153    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     154  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    35155
    36156  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    41161    "${PROJECT_NAME} ${PROJECT_VERSION}")
    42162
    43   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     163  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    44164
    45165  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    46166  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     167  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    47168  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    48169
     
    51172  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    52173    "DLL and import library")
     174  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     175    "Command line utilities")
    53176  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    54177    "Doxygen generated documentation")
     
    72195
    73196  SET(CPACK_GENERATOR "NSIS")
    74   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
    75   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    76   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     197  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     198  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     199  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    77200  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    78201  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    89212
    90213  INCLUDE(CPack)
    91 ENDIF(WIN32)
     214ENDIF()
  • INSTALL

    r504 r824  
    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

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

    r480 r793  
    11ACLOCAL_AMFLAGS = -I m4
     2
     3AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    24
    35AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     
    1012        m4/lx_check_glpk.m4 \
    1113        m4/lx_check_soplex.m4 \
     14        m4/lx_check_coin.m4 \
    1215        CMakeLists.txt \
    1316        cmake/FindGhostscript.cmake \
     17        cmake/FindCPLEX.cmake \
     18        cmake/FindGLPK.cmake \
     19        cmake/FindCOIN.cmake \
     20        cmake/LEMONConfig.cmake.in \
    1421        cmake/version.cmake.in \
    1522        cmake/version.cmake \
     
    3744include test/Makefile.am
    3845include doc/Makefile.am
    39 include demo/Makefile.am
    4046include tools/Makefile.am
     47include scripts/Makefile.am
     48
     49DIST_SUBDIRS = demo
     50
     51demo:
     52        $(MAKE) $(AM_MAKEFLAGS) -C demo
    4153
    4254MRPROPERFILES = \
     
    6678        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    6779
    68 .PHONY: mrproper dist-bz2 distcheck-bz2
     80.PHONY: demo mrproper dist-bz2 distcheck-bz2
  • NEWS

    r507 r881  
     12010-03-19 Version 1.2 released
     2
     3        This is major feature release
     4
     5        * New algorithms
     6          * Bellman-Ford algorithm (#51)
     7          * Minimum mean cycle algorithms (#179)
     8            * Karp, Hartman-Orlin and Howard algorithms
     9          * New minimum cost flow algorithms (#180)
     10            * Cost Scaling algorithms
     11            * Capacity Scaling algorithm
     12            * Cycle-Canceling algorithms
     13          * Planarity related algorithms (#62)
     14            * Planarity checking algorithm
     15            * Planar embedding algorithm
     16            * Schnyder's planar drawing algorithm
     17            * Coloring planar graphs with five or six colors
     18          * Fractional matching algorithms (#314)
     19        * New data structures
     20          * StaticDigraph structure (#68)
     21          * Several new priority queue structures (#50, #301)
     22            * Fibonacci, Radix, Bucket, Pairing, Binomial
     23              D-ary and fourary heaps (#301)
     24          * Iterable map structures (#73)
     25        * Other new tools and functionality
     26          * Map utility functions (#320)
     27          * Reserve functions are added to ListGraph and SmartGraph (#311)
     28          * A resize() function is added to HypercubeGraph (#311)
     29          * A count() function is added to CrossRefMap (#302)
     30          * Support for multiple targets in Suurballe using fullInit() (#181)
     31          * Traits class and named parameters for Suurballe (#323)
     32          * Separate reset() and resetParams() functions in NetworkSimplex
     33            to handle graph changes (#327)
     34          * tolerance() functions are added to HaoOrlin (#306)
     35        * Implementation improvements
     36          * Improvements in weighted matching algorithms (#314)
     37            * Jumpstart initialization
     38          * ArcIt iteration is based on out-arc lists instead of in-arc lists
     39            in ListDigraph (#311)
     40          * Faster add row operation in CbcMip (#203)
     41          * Better implementation for split() in ListDigraph (#311)
     42          * ArgParser can also throw exception instead of exit(1) (#332)
     43        * Miscellaneous
     44          * A simple interactive bootstrap script
     45          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
     46                #316,#319)
     47            * BibTeX references in the doc (#184)
     48          * Optionally use valgrind when running tests
     49          * Also check ReferenceMapTag in concept checks (#312)
     50          * dimacs-solver uses long long type by default.
     51        * Several bugfixes (compared to release 1.1):
     52          #295: Suppress MSVC warnings using pragmas
     53          ----: Various CMAKE related improvements
     54                * Remove duplications from doc/CMakeLists.txt
     55                * Rename documentation install folder from 'docs' to 'html'
     56                * Add tools/CMakeLists.txt to the tarball
     57                * Generate and install LEMONConfig.cmake
     58                * Change the label of the html project in Visual Studio
     59                * Fix the check for the 'long long' type
     60                * Put the version string into config.h
     61                * Minor CMake improvements
     62                * Set the version to 'hg-tip' if everything fails
     63          #311: Add missing 'explicit' keywords
     64          #302: Fix the implementation and doc of CrossRefMap
     65          #308: Remove duplicate list_graph.h entry from source list
     66          #307: Bugfix in Preflow and Circulation
     67          #305: Bugfix and extension in the rename script
     68          #312: Also check ReferenceMapTag in concept checks
     69          #250: Bugfix in pathSource() and pathTarget()
     70          #321: Use pathCopy(from,to) instead of copyPath(to,from)
     71          #322: Distribure LEMONConfig.cmake.in
     72          #330: Bug fix in map_extender.h
     73          #336: Fix the date field comment of graphToEps() output
     74          #323: Bug fix in Suurballe
     75          #335: Fix clear() function in ExtendFindEnum
     76          #337: Use void* as the LPX object pointer
     77          #317: Fix (and improve) error message in mip_test.cc
     78                Remove unnecessary OsiCbc dependency
     79          #356: Allow multiple executions of weighted matching algorithms (#356)
     80
     812009-05-13 Version 1.1 released
     82
     83        This is the second stable release of the 1.x series. It
     84        features a better coverage of the tools available in the 0.x
     85        series, a thoroughly reworked LP/MIP interface plus various
     86        improvements in the existing tools.
     87
     88        * Much improved M$ Windows support
     89          * Various improvements in the CMAKE build system
     90          * Compilation warnings are fixed/suppressed
     91        * Support IBM xlC compiler
     92        * New algorithms
     93          * Connectivity related algorithms (#61)
     94          * Euler walks (#65)
     95          * Preflow push-relabel max. flow algorithm (#176)
     96          * Circulation algorithm (push-relabel based) (#175)
     97          * Suurballe algorithm (#47)
     98          * Gomory-Hu algorithm (#66)
     99          * Hao-Orlin algorithm (#58)
     100          * Edmond's maximum cardinality and weighted matching algorithms
     101            in general graphs (#48,#265)
     102          * Minimum cost arborescence/branching (#60)
     103          * Network Simplex min. cost flow algorithm (#234)
     104        * New data structures
     105          * Full graph structure (#57)
     106          * Grid graph structure (#57)
     107          * Hypercube graph structure (#57)
     108          * Graph adaptors (#67)
     109          * ArcSet and EdgeSet classes (#67)
     110          * Elevator class (#174)
     111        * Other new tools
     112          * LP/MIP interface (#44)
     113            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
     114          * Reader for the Nauty file format (#55)
     115          * DIMACS readers (#167)
     116          * Radix sort algorithms (#72)
     117          * RangeIdMap and CrossRefMap (#160)
     118        * New command line tools
     119          * DIMACS to LGF converter (#182)
     120          * lgf-gen - a graph generator (#45)
     121          * DIMACS solver utility (#226)
     122        * Other code improvements
     123          * Lognormal distribution added to Random (#102)
     124          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
     125          * The standard maps of graphs are guaranteed to be
     126            reference maps (#190)
     127        * Miscellaneous
     128          * Various doc improvements
     129          * Improved 0.x -> 1.x converter script
     130
     131        * Several bugfixes (compared to release 1.0):
     132          #170: Bugfix SmartDigraph::split()
     133          #171: Bugfix in SmartGraph::restoreSnapshot()
     134          #172: Extended test cases for graphs and digraphs
     135          #173: Bugfix in Random
     136                * operator()s always return a double now
     137                * the faulty real<Num>(Num) and real<Num>(Num,Num)
     138                  have been removed
     139          #187: Remove DijkstraWidestPathOperationTraits
     140          #61:  Bugfix in DfsVisit
     141          #193: Bugfix in GraphReader::skipSection()
     142          #195: Bugfix in ConEdgeIt()
     143          #197: Bugfix in heap unionfind
     144                * This bug affects Edmond's general matching algorithms
     145          #207: Fix 'make install' without 'make html' using CMAKE
     146          #208: Suppress or fix VS2008 compilation warnings
     147          ----: Update the LEMON icon
     148          ----: Enable the component-based installer
     149                (in installers made by CPACK)
     150          ----: Set the proper version for CMAKE in the tarballs
     151                (made by autotools)
     152          ----: Minor clarification in the LICENSE file
     153          ----: Add missing unistd.h include to time_measure.h
     154          #204: Compilation bug fixed in graph_to_eps.h with VS2005
     155          #214,#215: windows.h should never be included by LEMON headers
     156          #230: Build systems check the availability of 'long long' type
     157          #229: Default implementation of Tolerance<> is used for integer types
     158          #211,#212: Various fixes for compiling on AIX
     159          ----: Improvements in CMAKE config
     160                - docs is installed in share/doc/
     161                - detects newer versions of Ghostscript
     162          #239: Fix missing 'inline' specifier in time_measure.h
     163          #274,#280: Install lemon/config.h
     164          #275: Prefix macro names with LEMON_ in lemon/config.h
     165          ----: Small script for making the release tarballs added
     166          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     167
    11682009-03-27 LEMON joins to the COIN-OR initiative
    2169
     
    81752008-10-13 Version 1.0 released
    9176
    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
     177        This is the first stable release of LEMON. Compared to the 0.x
     178        release series, it features a considerably smaller but more
     179        matured set of tools. The API has also completely revised and
     180        changed in several places.
     181
     182        * The major name changes compared to the 0.x series (see the
    16183          Migration Guide in the doc for more details)
    17184          * Graph -> Digraph, UGraph -> Graph
    18185          * 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)
     186          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     187        * Other improvements
     188          * Better documentation
     189          * Reviewed and cleaned up codebase
     190          * CMake based build system (along with the autotools based one)
     191        * Contents of the library (ported from 0.x)
     192          * Algorithms
     193            * breadth-first search (bfs.h)
     194            * depth-first search (dfs.h)
     195            * Dijkstra's algorithm (dijkstra.h)
     196            * Kruskal's algorithm (kruskal.h)
     197          * Data structures
     198            * graph data structures (list_graph.h, smart_graph.h)
     199            * path data structures (path.h)
     200            * binary heap data structure (bin_heap.h)
     201            * union-find data structures (unionfind.h)
     202            * miscellaneous property maps (maps.h)
     203            * two dimensional vector and bounding box (dim2.h)
    37204          * Concepts
    38             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     205            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    39206              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
     207            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     208              concepts/path.h)
     209          * Tools
     210            * Mersenne twister random number generator (random.h)
     211            * tools for measuring cpu and wall clock time (time_measure.h)
     212            * tools for counting steps and events (counter.h)
     213            * tool for parsing command line arguments (arg_parser.h)
     214            * tool for visualizing graphs (graph_to_eps.h)
     215            * tools for reading and writing data in LEMON Graph Format
    49216              (lgf_reader.h, lgf_writer.h)
    50217            * tools to handle the anomalies of calculations with
    51               floating point numbers (tolerance.h)
     218              floating point numbers (tolerance.h)
    52219            * 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)
     220          * Infrastructure
     221            * extended assertion handling (assert.h)
     222            * exception classes and error handling (error.h)
     223            * concept checking (concept_check.h)
     224            * commonly used mathematical constants (math.h)
  • README

    r318 r848  
    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/version.cmake.in

    r480 r678  
    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

    r511 r793  
    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])
     
    2023AC_CONFIG_HEADERS([config.h lemon/config.h])
    2124
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
     25AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
    2326
    2427dnl Do compilation tests using the C++ compiler.
     
    3942
    4043AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    4145AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4246
     
    5357
    5458dnl Set custom compiler flags when using g++.
    55 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    56   CXXFLAGS="$CXXFLAGS -Wall -W -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 -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
     59if test "$GXX" = yes -a "$ICC" = no; then
     60  WARNINGCXXFLAGS="-Wall -W -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 -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    5761fi
     62AC_SUBST([WARNINGCXXFLAGS])
    5863
    5964dnl Checks for libraries.
    60 #LX_CHECK_GLPK
    61 #LX_CHECK_CPLEX
    62 #LX_CHECK_SOPLEX
     65LX_CHECK_GLPK
     66LX_CHECK_CPLEX
     67LX_CHECK_SOPLEX
     68LX_CHECK_COIN
    6369
    64 dnl Disable/enable building the demo programs.
    65 AC_ARG_ENABLE([demo],
    66 AS_HELP_STRING([--enable-demo], [build the demo programs])
    67 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    68               [], [enable_demo=no])
    69 AC_MSG_CHECKING([whether to build the demo programs])
    70 if test x"$enable_demo" != x"no"; then
    71   AC_MSG_RESULT([yes])
    72 else
    73   AC_MSG_RESULT([no])
    74 fi
    75 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
     70AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     71AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    7672
    7773dnl Disable/enable building the binary tools.
     
    8783fi
    8884AM_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"])
    89100
    90101dnl Checks for header files.
     
    108119AC_CONFIG_FILES([
    109120Makefile
     121demo/Makefile
    110122cmake/version.cmake
    111123doc/Doxyfile
     
    121133echo
    122134echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     135echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124136echo
    125137echo Compiler supports long long... : $long_long_found
    126138echo
    127 #echo GLPK support.................. : $lx_glpk_found
    128 #echo CPLEX support................. : $lx_cplex_found
    129 #echo SOPLEX support................ : $lx_soplex_found
    130 #echo
    131 echo Build demo programs........... : $enable_demo
     139echo GLPK support.................. : $lx_glpk_found
     140echo CPLEX support................. : $lx_cplex_found
     141echo SOPLEX support................ : $lx_soplex_found
     142echo CLP support................... : $lx_clp_found
     143echo CBC support................... : $lx_cbc_found
     144echo
    132145echo Build additional tools........ : $enable_tools
     146echo Use valgrind for tests........ : $use_valgrind
    133147echo
    134148echo The packace will be installed in
  • demo/CMakeLists.txt

    r510 r679  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
     2  ${PROJECT_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(${CMAKE_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

    r164 r564  
    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

    r311 r877  
    33 * 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).
     
    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

    r313 r612  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8686    coords(coords).
    8787    title("Sample .eps figure").
    88     copyright("(C) 2003-2008 LEMON Project").
     88    copyright("(C) 2003-2009 LEMON Project").
    8989    run();
    9090
     
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2008 LEMON Project").
     95    copyright("(C) 2003-2009 LEMON Project").
    9696    absoluteNodeSizes().absoluteArcWidths().
    9797    nodeScale(2).nodeSizes(sizes).
     
    106106  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
    107107    title("Sample .eps figure (with arrowheads)").
    108     copyright("(C) 2003-2008 LEMON Project").
     108    copyright("(C) 2003-2009 LEMON Project").
    109109    absoluteNodeSizes().absoluteArcWidths().
    110110    nodeColors(composeMap(palette,colors)).
     
    133133  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
    134134    title("Sample .eps figure (parallel arcs)").
    135     copyright("(C) 2003-2008 LEMON Project").
     135    copyright("(C) 2003-2009 LEMON Project").
    136136    absoluteNodeSizes().absoluteArcWidths().
    137137    nodeShapes(shapes).
     
    148148  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
    149149    title("Sample .eps figure (parallel arcs and arrowheads)").
    150     copyright("(C) 2003-2008 LEMON Project").
     150    copyright("(C) 2003-2009 LEMON Project").
    151151    absoluteNodeSizes().absoluteArcWidths().
    152152    nodeScale(2).nodeSizes(sizes).
     
    164164  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
    165165    title("Sample .eps figure (fits to A4)").
    166     copyright("(C) 2003-2008 LEMON Project").
     166    copyright("(C) 2003-2009 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
     
    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();
     
    194194    scale(60).
    195195    title("Sample .eps figure (Palette demo)").
    196     copyright("(C) 2003-2008 LEMON Project").
     196    copyright("(C) 2003-2009 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().
  • demo/lgf_demo.cc

    r294 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/CMakeLists.txt

    r500 r865  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
    4 SET(abs_top_builddir ${CMAKE_BINARY_DIR})
     3SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
     4SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
    8   ${CMAKE_BINARY_DIR}/doc/Doxyfile
    9   @ONLY)
     7  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
     8  ${PROJECT_BINARY_DIR}/doc/Doxyfile
     9  @ONLY
     10)
    1011
    11 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
    1213  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
     14  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     15  ADD_CUSTOM_TARGET(html
     16    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
     17    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
     18    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
     19    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
     20    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
     21    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     22    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
     23    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     24    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     25    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     26    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     27    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     28    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     29    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     30    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     31    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     32    COMMAND ${CMAKE_COMMAND} -E remove_directory html
     33    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
     34    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     35    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     36  )
     37
     38  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     39
    1340  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/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    18       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
    19       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
    20       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
    21       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
    22       COMMAND rm -rf html
    23       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    24       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
     41    INSTALL(
     42      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     43      DESTINATION share/doc/lemon/html
     44      COMPONENT html_documentation
     45    )
    2546  ELSEIF(WIN32)
    26     ADD_CUSTOM_TARGET(html
    27       COMMAND if exist gen-images rmdir /s /q gen-images
    28       COMMAND mkdir gen-images
    29       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
    30       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
    31       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
    32       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
    33       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
    34       COMMAND if exist html rmdir /s /q html
    35       COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    36       WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
    37   ENDIF(UNIX)
    38   INSTALL(
    39     DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    40     DESTINATION share/doc
    41     COMPONENT html_documentation)
    42 ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     47    INSTALL(
     48      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     49      DESTINATION doc
     50      COMPONENT html_documentation
     51    )
     52  ENDIF()
     53
     54ENDIF()
  • doc/Doxyfile.in

    r316 r756  
    1 # Doxyfile 1.5.7.1
     1# Doxyfile 1.5.9
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2524INHERIT_DOCS           = NO
    2625SEPARATE_MEMBER_PAGES  = NO
     
    6766ENABLED_SECTIONS       =
    6867MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     68SHOW_USED_FILES        = NO
    7069SHOW_DIRECTORIES       = YES
    7170SHOW_FILES             = YES
     
    9291                         "@abs_top_srcdir@/demo" \
    9392                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     93                         "@abs_top_srcdir@/test/test_tools.h" \
     94                         "@abs_top_builddir@/doc/references.dox"
    9595INPUT_ENCODING         = UTF-8
    9696FILE_PATTERNS          = *.h \
     
    224224SKIP_FUNCTION_MACROS   = YES
    225225#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
     226# Options related to the search engine   
    227227#---------------------------------------------------------------------------
    228228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/Makefile.am

    r317 r865  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
     11        doc/min_cost_flow.dox \
    1112        doc/named-param.dox \
    1213        doc/namespaces.dox \
     
    1516
    1617DOC_EPS_IMAGES18 = \
     18        grid_graph.eps \
    1719        nodeshape_0.eps \
    1820        nodeshape_1.eps \
     
    2123        nodeshape_4.eps
    2224
     25DOC_EPS_IMAGES27 = \
     26        bipartite_matching.eps \
     27        bipartite_partitions.eps \
     28        connected_components.eps \
     29        edge_biconnected_components.eps \
     30        matching.eps \
     31        node_biconnected_components.eps \
     32        planar.eps \
     33        strongly_connected_components.eps
     34
    2335DOC_EPS_IMAGES = \
    24         $(DOC_EPS_IMAGES18)
     36        $(DOC_EPS_IMAGES18) \
     37        $(DOC_EPS_IMAGES27)
    2538
    2639DOC_PNG_IMAGES = \
     
    4558        fi
    4659
    47 html-local: $(DOC_PNG_IMAGES)
     60$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
     61        -mkdir doc/gen-images
     62        if test ${gs_found} = yes; then \
     63          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
     64        else \
     65          echo; \
     66          echo "Ghostscript not found."; \
     67          echo; \
     68          exit 1; \
     69        fi
     70
     71references.dox: doc/references.bib
     72        if test ${python_found} = yes; then \
     73          cd doc; \
     74          python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
     75          cd ..; \
     76        else \
     77          echo; \
     78          echo "Python not found."; \
     79          echo; \
     80          exit 1; \
     81        fi
     82
     83html-local: $(DOC_PNG_IMAGES) references.dox
    4884        if test ${doxygen_found} = yes; then \
    4985          cd doc; \
     
    70106install-html-local: doc/html
    71107        @$(NORMAL_INSTALL)
    72         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     108        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    73109        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    74110          f="`echo $$p | sed -e 's|^.*/||'`"; \
    75           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    76           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     111          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     112          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    77113        done
    78114
     
    81117        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    82118          f="`echo $$p | sed -e 's|^.*/||'`"; \
    83           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    84           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     119          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     120          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    85121        done
    86122
  • doc/coding_style.dox

    r210 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/dirs.dox

    r318 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7272\brief Auxiliary tools for implementation.
    7373
    74 This directory contains some auxiliary classes for implementing graphs, 
     74This directory contains some auxiliary classes for implementing graphs,
    7575maps and some other classes.
    7676As a user you typically don't have to deal with these files.
  • doc/groups.dox

    r318 r904  
    33 * 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).
     
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2224*/
    2325
     
    6163
    6264/**
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6466@ingroup graphs
    65 \brief Graph types between real graphs and graph adaptors.
    66 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
    70138*/
    71139
     
    75143\brief Map structures implemented in LEMON.
    76144
    77 This group describes the map structures implemented in LEMON.
     145This group contains the map structures implemented in LEMON.
    78146
    79147LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    88156\brief Special graph-related maps.
    89157
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     158This group contains maps that are specifically designed to assign
     159values to the nodes and arcs/edges of graphs.
     160
     161If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     162\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92163*/
    93164
     
    97168\brief Tools to create new maps from existing ones
    98169
    99 This group describes map adaptors that are used to create "implicit"
     170This group contains map adaptors that are used to create "implicit"
    100171maps from other maps.
    101172
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     173Most of them are \ref concepts::ReadMap "read-only maps".
    103174They can make arithmetic and logical operations between one or two maps
    104175(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    156227
    157228/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166229@defgroup paths Path Structures
    167230@ingroup datas
    168231\brief %Path structures implemented in LEMON.
    169232
    170 This group describes the path structures implemented in LEMON.
     233This group contains the path structures implemented in LEMON.
    171234
    172235LEMON provides flexible data structures to work with paths.
     
    176239any kind of path structure.
    177240
    178 \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"
    179263*/
    180264
     
    184268\brief Auxiliary data structures implemented in LEMON.
    185269
    186 This group describes some data structures implemented in LEMON in
     270This group contains some data structures implemented in LEMON in
    187271order to make it easier to implement combinatorial algorithms.
    188272*/
    189273
    190274/**
     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/**
     289@defgroup matrices Matrices
     290@ingroup auxdat
     291\brief Two dimensional data storages implemented in LEMON.
     292
     293This group contains two dimensional data storages implemented in LEMON.
     294*/
     295
     296/**
    191297@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     298\brief This group contains the several algorithms
    193299implemented in LEMON.
    194300
    195 This group describes the several algorithms
     301This group contains the several algorithms
    196302implemented in LEMON.
    197303*/
     
    202308\brief Common graph search algorithms.
    203309
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     310This group contains the common graph search algorithms, namely
     311\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     312\ref clrs01algorithms.
    206313*/
    207314
     
    211318\brief Algorithms for finding shortest paths.
    212319
    213 This group describes the algorithms for finding shortest paths in graphs.
     320This group contains the algorithms for finding shortest paths in digraphs
     321\ref clrs01algorithms.
     322
     323 - \ref Dijkstra algorithm for finding shortest paths from a source node
     324   when all arc lengths are non-negative.
     325 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     326   from a source node when arc lenghts can be either positive or negative,
     327   but the digraph should not contain directed cycles with negative total
     328   length.
     329 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     330   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     331   lenghts can be either positive or negative, but the digraph should
     332   not contain directed cycles with negative total length.
     333 - \ref Suurballe A successive shortest path algorithm for finding
     334   arc-disjoint paths between two nodes having minimum total length.
     335*/
     336
     337/**
     338@defgroup spantree Minimum Spanning Tree Algorithms
     339@ingroup algs
     340\brief Algorithms for finding minimum cost spanning trees and arborescences.
     341
     342This group contains the algorithms for finding minimum cost spanning
     343trees and arborescences \ref clrs01algorithms.
    214344*/
    215345
     
    219349\brief Algorithms for finding maximum flows.
    220350
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     351This group contains the algorithms for finding maximum flows and
     352feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     353
     354The \e maximum \e flow \e problem is to find a flow of maximum value between
     355a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     356digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     357\f$s, t \in V\f$ source and target nodes.
     358A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     359following optimization problem.
     360
     361\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     362\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     363    \quad \forall u\in V\setminus\{s,t\} \f]
     364\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    234365
    235366LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     367- \ref EdmondsKarp Edmonds-Karp algorithm
     368  \ref edmondskarp72theoretical.
     369- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     370  \ref goldberg88newapproach.
     371- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     372  \ref dinic70algorithm, \ref sleator83dynamic.
     373- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     374  \ref goldberg88newapproach, \ref sleator83dynamic.
     375
     376In most cases the \ref Preflow algorithm provides the
     377fastest method for computing a maximum flow. All implementations
     378also provide functions to query the minimum cut, which is the dual
     379problem of maximum flow.
     380
     381\ref Circulation is a preflow push-relabel algorithm implemented directly
     382for finding feasible circulations, which is a somewhat different problem,
     383but it is strongly related to maximum flow.
     384For more information, see \ref Circulation.
     385*/
     386
     387/**
     388@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    249389@ingroup algs
    250390
    251391\brief Algorithms for finding minimum cost flows and circulations.
    252392
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
     393This group contains the algorithms for finding minimum cost flows and
     394circulations \ref amo93networkflows. For more information about this
     395problem and its dual solution, see \ref min_cost_flow
     396"Minimum Cost Flow Problem".
     397
     398LEMON contains several algorithms for this problem.
     399 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     400   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     401 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     402   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     403   \ref bunnagel98efficient.
     404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     405   shortest path method \ref edmondskarp72theoretical.
     406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     408
     409In general NetworkSimplex is the most efficient implementation,
     410but in special cases other algorithms could be faster.
     411For example, if the total supply and/or capacities are rather small,
     412CapacityScaling is usually the fastest algorithm (without effective scaling).
    255413*/
    256414
     
    261419\brief Algorithms for finding minimum cut in graphs.
    262420
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     421This group contains the algorithms for finding minimum cut in graphs.
     422
     423The \e minimum \e cut \e problem is to find a non-empty and non-complete
     424\f$X\f$ subset of the nodes with minimum overall capacity on
     425outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     426\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269427cut is the \f$X\f$ solution of the next optimization problem:
    270428
    271429\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     430    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    273431
    274432LEMON contains several algorithms related to minimum cut problems:
    275433
    276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    277   in directed graphs
    278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    279   calculate minimum cut in undirected graphs
    280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    281   pairs minimum cut in undirected graphs
     434- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     435  in directed graphs.
     436- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     437  calculating minimum cut in undirected graphs.
     438- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     439  all-pairs minimum cut in undirected graphs.
    282440
    283441If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
    285 */
    286 
    287 /**
    288 @defgroup graph_prop Connectivity and Other Graph Properties
    289 @ingroup algs
    290 \brief Algorithms for discovering the graph properties
    291 
    292 This group describes the algorithms for discovering the graph properties
    293 like connectivity, bipartiteness, euler property, simplicity etc.
    294 
    295 \image html edge_biconnected_components.png
    296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    297 */
    298 
    299 /**
    300 @defgroup planar Planarity Embedding and Drawing
    301 @ingroup algs
    302 \brief Algorithms for planarity checking, embedding and drawing
    303 
    304 This group describes the algorithms for planarity checking,
    305 embedding and drawing.
    306 
    307 \image html planar.png
    308 \image latex planar.eps "Plane graph" width=\textwidth
     442see the \ref max_flow "maximum flow problem".
     443*/
     444
     445/**
     446@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     447@ingroup algs
     448\brief Algorithms for finding minimum mean cycles.
     449
     450This group contains the algorithms for finding minimum mean cycles
     451\ref clrs01algorithms, \ref amo93networkflows.
     452
     453The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     454of minimum mean length (cost) in a digraph.
     455The mean length of a cycle is the average length of its arcs, i.e. the
     456ratio between the total length of the cycle and the number of arcs on it.
     457
     458This problem has an important connection to \e conservative \e length
     459\e functions, too. A length function on the arcs of a digraph is called
     460conservative if and only if there is no directed cycle of negative total
     461length. For an arbitrary length function, the negative of the minimum
     462cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     463arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     464function.
     465
     466LEMON contains three algorithms for solving the minimum mean cycle problem:
     467- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     468  \ref dasdan98minmeancycle.
     469- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     470  version of Karp's algorithm \ref dasdan98minmeancycle.
     471- \ref HowardMmc Howard's policy iteration algorithm
     472  \ref dasdan98minmeancycle.
     473
     474In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     475most efficient one, though the best known theoretical bound on its running
     476time is exponential.
     477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    309480*/
    310481
     
    314485\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315486
    316 This group contains algorithm objects and functions to calculate
     487This group contains the algorithms for calculating
    317488matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
     489finding a subset of the edges for which each node has at most one incident
     490edge.
    319491
    320492There are several different algorithms for calculate matchings in
    321493graphs.  The matching problems in bipartite graphs are generally
    322494easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     495can be finding maximum cardinality, maximum weight or minimum cost
    324496matching. The search can be constrained to find perfect or
    325497maximum cardinality matching.
    326498
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
    347 
    348 \image html bipartite_matching.png
    349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    350 */
    351 
    352 /**
    353 @defgroup spantree Minimum Spanning Tree Algorithms
    354 @ingroup algs
    355 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    356 
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     499The matching algorithms implemented in LEMON:
     500- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     501  for calculating maximum cardinality matching in bipartite graphs.
     502- \ref PrBipartiteMatching Push-relabel algorithm
     503  for calculating maximum cardinality matching in bipartite graphs.
     504- \ref MaxWeightedBipartiteMatching
     505  Successive shortest path algorithm for calculating maximum weighted
     506  matching and maximum weighted bipartite matching in bipartite graphs.
     507- \ref MinCostMaxBipartiteMatching
     508  Successive shortest path algorithm for calculating minimum cost maximum
     509  matching in bipartite graphs.
     510- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     511  maximum cardinality matching in general graphs.
     512- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     513  maximum weighted matching in general graphs.
     514- \ref MaxWeightedPerfectMatching
     515  Edmond's blossom shrinking algorithm for calculating maximum weighted
     516  perfect matching in general graphs.
     517- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     518  maximum cardinality fractional matching in general graphs.
     519- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     520  maximum weighted fractional matching in general graphs.
     521- \ref MaxWeightedPerfectFractionalMatching
     522  Augmenting path algorithm for calculating maximum weighted
     523  perfect fractional matching in general graphs.
     524
     525\image html matching.png
     526\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     527*/
     528
     529/**
     530@defgroup graph_properties Connectivity and Other Graph Properties
     531@ingroup algs
     532\brief Algorithms for discovering the graph properties
     533
     534This group contains the algorithms for discovering the graph properties
     535like connectivity, bipartiteness, euler property, simplicity etc.
     536
     537\image html connected_components.png
     538\image latex connected_components.eps "Connected components" width=\textwidth
     539*/
     540
     541/**
     542@defgroup planar Planarity Embedding and Drawing
     543@ingroup algs
     544\brief Algorithms for planarity checking, embedding and drawing
     545
     546This group contains the algorithms for planarity checking,
     547embedding and drawing.
     548
     549\image html planar.png
     550\image latex planar.eps "Plane graph" width=\textwidth
     551*/
     552
     553/**
     554@defgroup approx_algs Approximation Algorithms
     555@ingroup algs
     556\brief Approximation algorithms.
     557
     558This group contains the approximation and heuristic algorithms
     559implemented in LEMON.
     560
     561<b>Maximum Clique Problem</b>
     562  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     563    Grosso, Locatelli, and Pullan.
    359564*/
    360565
     
    364569\brief Auxiliary algorithms implemented in LEMON.
    365570
    366 This group describes some algorithms implemented in LEMON
     571This group contains some algorithms implemented in LEMON
    367572in order to make it easier to implement complex algorithms.
    368573*/
    369574
    370575/**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
     576@defgroup gen_opt_group General Optimization Tools
     577\brief This group contains some general optimization frameworks
    376578implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     579
     580This group contains some general optimization frameworks
    382581implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented in LEMON.
    386 */
    387 
    388 /**
    389 @defgroup lp_group Lp and Mip Solvers
     582*/
     583
     584/**
     585@defgroup lp_group LP and MIP Solvers
    390586@ingroup gen_opt_group
    391 \brief Lp and Mip solver interfaces for LEMON.
    392 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
     587\brief LP and MIP solver interfaces for LEMON.
     588
     589This group contains LP and MIP solver interfaces for LEMON.
     590Various LP solvers could be used in the same manner with this
     591high-level interface.
     592
     593The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     594\ref cplex, \ref soplex.
    396595*/
    397596
     
    410609\brief Metaheuristics for LEMON library.
    411610
    412 This group describes some metaheuristic optimization tools.
     611This group contains some metaheuristic optimization tools.
    413612*/
    414613
     
    425624\brief Simple basic graph utilities.
    426625
    427 This group describes some simple basic graph utilities.
     626This group contains some simple basic graph utilities.
    428627*/
    429628
     
    433632\brief Tools for development, debugging and testing.
    434633
    435 This group describes several useful tools for development,
     634This group contains several useful tools for development,
    436635debugging and testing.
    437636*/
     
    442641\brief Simple tools for measuring the performance of algorithms.
    443642
    444 This group describes simple tools for measuring the performance
     643This group contains simple tools for measuring the performance
    445644of algorithms.
    446645*/
     
    451650\brief Exceptions defined in LEMON.
    452651
    453 This group describes the exceptions defined in LEMON.
     652This group contains the exceptions defined in LEMON.
    454653*/
    455654
     
    458657\brief Graph Input-Output methods
    459658
    460 This group describes the tools for importing and exporting graphs
     659This group contains the tools for importing and exporting graphs
    461660and graph related data. Now it supports the \ref lgf-format
    462661"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    465664
    466665/**
    467 @defgroup lemon_io LEMON Input-Output
     666@defgroup lemon_io LEMON Graph Format
    468667@ingroup io_group
    469668\brief Reading and writing LEMON Graph Format.
    470669
    471 This group describes methods for reading and writing
     670This group contains methods for reading and writing
    472671\ref lgf-format "LEMON Graph Format".
    473672*/
     
    478677\brief General \c EPS drawer and graph exporter
    479678
    480 This group describes general \c EPS drawing methods and special
     679This group contains general \c EPS drawing methods and special
    481680graph exporting tools.
     681*/
     682
     683/**
     684@defgroup dimacs_group DIMACS Format
     685@ingroup io_group
     686\brief Read and write files in DIMACS format
     687
     688Tools to read a digraph from or write it to a file in DIMACS format data.
     689*/
     690
     691/**
     692@defgroup nauty_group NAUTY Format
     693@ingroup io_group
     694\brief Read \e Nauty format
     695
     696Tool to read graphs from \e Nauty format data.
    482697*/
    483698
     
    486701\brief Skeleton classes and concept checking classes
    487702
    488 This group describes the data/algorithm skeletons and concept checking
     703This group contains the data/algorithm skeletons and concept checking
    489704classes implemented in LEMON.
    490705
     
    516731\brief Skeleton and concept checking classes for graph structures
    517732
    518 This group describes the skeletons and concept checking classes of LEMON's
    519 graph structures and helper classes used to implement these.
     733This group contains the skeletons and concept checking classes of
     734graph structures.
    520735*/
    521736
     
    525740\brief Skeleton and concept checking classes for maps
    526741
    527 This group describes the skeletons and concept checking classes of maps.
     742This group contains the skeletons and concept checking classes of maps.
     743*/
     744
     745/**
     746@defgroup tools Standalone Utility Applications
     747
     748Some utility applications are listed here.
     749
     750The standard compilation procedure (<tt>./configure;make</tt>) will compile
     751them, as well.
    528752*/
    529753
     
    531755\anchor demoprograms
    532756
    533 @defgroup demos Demo programs
     757@defgroup demos Demo Programs
    534758
    535759Some demo programs are listed here. Their full source codes can be found in
    536760the \c demo subdirectory of the source tree.
    537761
    538 It order to compile them, use <tt>--enable-demo</tt> configure option when
    539 build the library.
    540 */
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 
     762In order to compile them, use the <tt>make demo</tt> or the
     763<tt>make check</tt> commands.
     764*/
     765
     766}
  • doc/lgf.dox

    r313 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/license.dox

    r209 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/mainpage.dox

    r314 r877  
    33 * 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).
     
    2222\section intro Introduction
    2323
    24 \subsection whatis What is LEMON
    25 
    26 LEMON stands for
    27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
    28 and <b>O</b>ptimization in <b>N</b>etworks.
    29 It is a C++ template
    30 library aimed at combinatorial optimization tasks which
    31 often involve in working
    32 with graphs.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementations of common
     27data structures and algorithms with focus on combinatorial optimization
     28tasks connected mainly with graphs and networks.
    3329
    3430<b>
     
    4036</b>
    4137
    42 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
     43Budapest, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
    4346
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
     47\section howtoread How to Read the Documentation
    4748
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
     49If you would like to get to know the library, see
     50<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5051
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
     52If you are interested in starting to use the library, see the <a class="el"
     53href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
     54Guide</a>.
    5455
    55 If you know what you are looking for then try to find it under the
    56 <a class="el" href="modules.html">Modules</a>
    57 section.
     56If you know what you are looking for, then try to find it under the
     57<a class="el" href="modules.html">Modules</a> section.
    5858
    5959If you are a user of the old (0.x) series of LEMON, please check out the
  • doc/migration.dox

    r314 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
    2929update are typeset <b>boldface</b>.
    3030
     
    5454
    5555\warning
    56 <b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
    57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
    58 in strings, comments etc. as well as in all identifiers.</b>
     56<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
     57\c ugraph, \c edge and \c uedge in your own identifiers and in
     58strings, comments etc. as well as in all LEMON specific identifiers.
     59So use the script carefully and make a backup copy of your source files
     60before applying the script to them.</b>
    5961
    6062\section migration-lgf LGF tools
  • doc/named-param.dox

    r269 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • doc/namespaces.dox

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

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

    r510 r679  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
     2  ${PROJECT_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
     
    99)
    1010
    11 ADD_LIBRARY(lemon
     11SET(LEMON_SOURCES
    1212  arg_parser.cc
    1313  base.cc
    1414  color.cc
     15  lp_base.cc
     16  lp_skeleton.cc
    1517  random.cc
    1618  bits/windows.cc
    1719)
    1820
     21IF(LEMON_HAVE_GLPK)
     22  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     23  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
     24  IF(WIN32)
     25    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
     26    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
     27    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
     28  ENDIF()
     29ENDIF()
     30
     31IF(LEMON_HAVE_CPLEX)
     32  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     33  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     34ENDIF()
     35
     36IF(LEMON_HAVE_CLP)
     37  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     38  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     39ENDIF()
     40
     41IF(LEMON_HAVE_CBC)
     42  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     43  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     44ENDIF()
     45
     46ADD_LIBRARY(lemon ${LEMON_SOURCES})
     47IF(UNIX)
     48  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     49ENDIF()
     50
    1951INSTALL(
    2052  TARGETS lemon
    2153  ARCHIVE DESTINATION lib
    22   COMPONENT library)
     54  COMPONENT library
     55)
    2356
    2457INSTALL(
     
    2659  DESTINATION include/lemon
    2760  COMPONENT headers
    28   FILES_MATCHING PATTERN "*.h")
     61  FILES_MATCHING PATTERN "*.h"
     62)
    2963
    3064INSTALL(
    3165  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
    3266  DESTINATION include/lemon
    33   COMPONENT headers)
     67  COMPONENT headers
     68)
  • lemon/Makefile.am

    r512 r904  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt
     3        lemon/CMakeLists.txt \
     4        lemon/config.h.cmake
    45
    56pkgconfig_DATA += lemon/lemon.pc
     
    89
    910lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc \
     11        lemon/arg_parser.cc \
     12        lemon/base.cc \
     13        lemon/color.cc \
     14        lemon/lp_base.cc \
     15        lemon/lp_skeleton.cc \
     16        lemon/random.cc \
    1417        lemon/bits/windows.cc
    1518
    16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     19nodist_lemon_HEADERS = lemon/config.h   
    1820
    19 nodist_lemon_HEADERS = lemon/config.h
     21lemon_libemon_la_CXXFLAGS = \
     22        $(AM_CXXFLAGS) \
     23        $(GLPK_CFLAGS) \
     24        $(CPLEX_CFLAGS) \
     25        $(SOPLEX_CXXFLAGS) \
     26        $(CLP_CXXFLAGS) \
     27        $(CBC_CXXFLAGS)
     28
     29lemon_libemon_la_LDFLAGS = \
     30        $(GLPK_LIBS) \
     31        $(CPLEX_LIBS) \
     32        $(SOPLEX_LIBS) \
     33        $(CLP_LIBS) \
     34        $(CBC_LIBS)
     35
     36if HAVE_GLPK
     37lemon_libemon_la_SOURCES += lemon/glpk.cc
     38endif
     39
     40if HAVE_CPLEX
     41lemon_libemon_la_SOURCES += lemon/cplex.cc
     42endif
     43
     44if HAVE_SOPLEX
     45lemon_libemon_la_SOURCES += lemon/soplex.cc
     46endif
     47
     48if HAVE_CLP
     49lemon_libemon_la_SOURCES += lemon/clp.cc
     50endif
     51
     52if HAVE_CBC
     53lemon_libemon_la_SOURCES += lemon/cbc.cc
     54endif
    2055
    2156lemon_HEADERS += \
    22         lemon/arg_parser.h \
     57        lemon/adaptors.h \
     58        lemon/arg_parser.h \
    2359        lemon/assert.h \
    24         lemon/bfs.h \
    25         lemon/bin_heap.h \
    26         lemon/color.h \
     60        lemon/bellman_ford.h \
     61        lemon/bfs.h \
     62        lemon/bin_heap.h \
     63        lemon/binomial_heap.h \
     64        lemon/bucket_heap.h \
     65        lemon/capacity_scaling.h \
     66        lemon/cbc.h \
     67        lemon/circulation.h \
     68        lemon/clp.h \
     69        lemon/color.h \
    2770        lemon/concept_check.h \
    28         lemon/counter.h \
     71        lemon/connectivity.h \
    2972        lemon/core.h \
    30         lemon/dfs.h \
    31         lemon/dijkstra.h \
    32         lemon/dim2.h \
     73        lemon/cost_scaling.h \
     74        lemon/counter.h \
     75        lemon/cplex.h \
     76        lemon/cycle_canceling.h \
     77        lemon/dfs.h \
     78        lemon/dheap.h \
     79        lemon/dijkstra.h \
     80        lemon/dim2.h \
     81        lemon/dimacs.h \
     82        lemon/edge_set.h \
     83        lemon/elevator.h \
    3384        lemon/error.h \
    34         lemon/graph_to_eps.h \
     85        lemon/euler.h \
     86        lemon/fib_heap.h \
     87        lemon/fractional_matching.h \
     88        lemon/full_graph.h \
     89        lemon/glpk.h \
     90        lemon/gomory_hu.h \
     91        lemon/graph_to_eps.h \
     92        lemon/grid_graph.h \
     93        lemon/grosso_locatelli_pullan_mc.h \
     94        lemon/hartmann_orlin_mmc.h \
     95        lemon/howard_mmc.h \
     96        lemon/hypercube_graph.h \
     97        lemon/karp_mmc.h \
    3598        lemon/kruskal.h \
     99        lemon/hao_orlin.h \
    36100        lemon/lgf_reader.h \
    37101        lemon/lgf_writer.h \
    38102        lemon/list_graph.h \
     103        lemon/lp.h \
     104        lemon/lp_base.h \
     105        lemon/lp_skeleton.h \
    39106        lemon/maps.h \
     107        lemon/matching.h \
    40108        lemon/math.h \
     109        lemon/min_cost_arborescence.h \
     110        lemon/nauty_reader.h \
     111        lemon/network_simplex.h \
     112        lemon/pairing_heap.h \
    41113        lemon/path.h \
    42         lemon/random.h \
     114        lemon/planarity.h \
     115        lemon/preflow.h \
     116        lemon/quad_heap.h \
     117        lemon/radix_heap.h \
     118        lemon/radix_sort.h \
     119        lemon/random.h \
    43120        lemon/smart_graph.h \
    44         lemon/time_measure.h \
    45         lemon/tolerance.h \
     121        lemon/soplex.h \
     122        lemon/static_graph.h \
     123        lemon/suurballe.h \
     124        lemon/time_measure.h \
     125        lemon/tolerance.h \
    46126        lemon/unionfind.h \
    47127        lemon/bits/windows.h
     
    50130        lemon/bits/alteration_notifier.h \
    51131        lemon/bits/array_map.h \
    52         lemon/bits/base_extender.h \
    53         lemon/bits/bezier.h \
     132        lemon/bits/bezier.h \
    54133        lemon/bits/default_map.h \
    55         lemon/bits/enable_if.h \
     134        lemon/bits/edge_set_extender.h \
     135        lemon/bits/enable_if.h \
     136        lemon/bits/graph_adaptor_extender.h \
    56137        lemon/bits/graph_extender.h \
    57138        lemon/bits/map_extender.h \
    58139        lemon/bits/path_dump.h \
     140        lemon/bits/solver_bits.h \
    59141        lemon/bits/traits.h \
     142        lemon/bits/variant.h \
    60143        lemon/bits/vector_map.h
    61144
  • lemon/arg_parser.cc

    r311 r877  
    33 * 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).
     
    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

    r311 r879  
    33 * 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).
     
    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

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

    r220 r477  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = 1e-4;
     26  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;
  • lemon/bfs.h

    r301 r877  
    33 * 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).
     
    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;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    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;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     68    ///Instantiates a \c ProcessedMap.
     69
     70    ///This function instantiates a \ref ProcessedMap.
    7071    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     72    ///we would like to define the \ref ProcessedMap
    7273#ifdef DOXYGEN
    7374    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    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;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     88    ///Instantiates a \c ReachedMap.
     89
     90    ///This function instantiates a \ref ReachedMap.
    8991    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     92    ///we would like to define the \ref ReachedMap.
    9193    static ReachedMap *createReachedMap(const Digraph &g)
    9294    {
     
    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;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     103    ///Instantiates a \c DistMap.
     104
     105    ///This function instantiates a \ref DistMap.
    104106    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     107    ///\ref DistMap.
    106108    static DistMap *createDistMap(const Digraph &g)
    107109    {
     
    120122  ///
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    127   ///See \ref BfsDefaultTraits for the documentation of
    128   ///a Bfs traits class.
     124  ///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.
    129130#ifdef DOXYGEN
    130131  template <typename GR,
     
    152153    typedef PredMapPath<Digraph, PredMap> Path;
    153154
    154     ///The traits class.
     155    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155156    typedef TR Traits;
    156157
     
    214215    typedef Bfs Create;
    215216
    216     ///\name Named template parameters
     217    ///\name Named Template Parameters
    217218
    218219    ///@{
     
    228229    };
    229230    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     231    ///\c PredMap type.
    231232    ///
    232233    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     234    ///\c PredMap type.
     235    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    234236    template <class T>
    235237    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    247249    };
    248250    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     251    ///\c DistMap type.
    250252    ///
    251253    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     254    ///\c DistMap type.
     255    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    253256    template <class T>
    254257    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266269    };
    267270    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     271    ///\c ReachedMap type.
    269272    ///
    270273    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     274    ///\c ReachedMap type.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272277    template <class T>
    273278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    285290    };
    286291    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     292    ///\c ProcessedMap type.
    288293    ///
    289294    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     295    ///\c ProcessedMap type.
     296    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    291297    template <class T>
    292298    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    303309    };
    304310    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     311    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306312    ///
    307313    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     314    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309315    ///If you don't set it explicitly, it will be automatically allocated.
    310316    struct SetStandardProcessedMap :
     
    341347
    342348    ///Sets the map that stores the predecessor arcs.
    343     ///If you don't use this function before calling \ref run(),
    344     ///it will allocate one. The destructor deallocates this
    345     ///automatically allocated map, of course.
     349    ///If you don't use this function before calling \ref run(Node) "run()"
     350    ///or \ref init(), an instance will be allocated automatically.
     351    ///The destructor deallocates this automatically allocated map,
     352    ///of course.
    346353    ///\return <tt> (*this) </tt>
    347354    Bfs &predMap(PredMap &m)
     
    358365
    359366    ///Sets the map that indicates which nodes are reached.
    360     ///If you don't use this function before calling \ref run(),
    361     ///it will allocate one. The destructor deallocates this
    362     ///automatically allocated map, of course.
     367    ///If you don't use this function before calling \ref run(Node) "run()"
     368    ///or \ref init(), an instance will be allocated automatically.
     369    ///The destructor deallocates this automatically allocated map,
     370    ///of course.
    363371    ///\return <tt> (*this) </tt>
    364372    Bfs &reachedMap(ReachedMap &m)
     
    375383
    376384    ///Sets the map that indicates which nodes are processed.
    377     ///If you don't use this function before calling \ref run(),
    378     ///it will allocate one. The destructor deallocates this
    379     ///automatically allocated map, of course.
     385    ///If you don't use this function before calling \ref run(Node) "run()"
     386    ///or \ref init(), an instance will be allocated automatically.
     387    ///The destructor deallocates this automatically allocated map,
     388    ///of course.
    380389    ///\return <tt> (*this) </tt>
    381390    Bfs &processedMap(ProcessedMap &m)
     
    393402    ///Sets the map that stores the distances of the nodes calculated by
    394403    ///the algorithm.
    395     ///If you don't use this function before calling \ref run(),
    396     ///it will allocate one. The destructor deallocates this
    397     ///automatically allocated map, of course.
     404    ///If you don't use this function before calling \ref run(Node) "run()"
     405    ///or \ref init(), an instance will be allocated automatically.
     406    ///The destructor deallocates this automatically allocated map,
     407    ///of course.
    398408    ///\return <tt> (*this) </tt>
    399409    Bfs &distMap(DistMap &m)
     
    409419  public:
    410420
    411     ///\name Execution control
    412     ///The simplest way to execute the algorithm is to use
    413     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    414     ///\n
    415     ///If you need more control on the execution, first you must call
    416     ///\ref lemon::Bfs::init() "init()", then you can add several source
    417     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    418     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    419     ///actual path computation.
     421    ///\name Execution Control
     422    ///The simplest way to execute the BFS algorithm is to use one of the
     423    ///member functions called \ref run(Node) "run()".\n
     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
     426    ///\ref addSource(). Finally the actual path computation can be
     427    ///performed with one of the \ref start() functions.
    420428
    421429    ///@{
    422430
     431    ///\brief Initializes the internal data structures.
     432    ///
    423433    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427434    void init()
    428435    {
     
    558565    }
    559566
    560     ///\brief Returns \c false if there are nodes
    561     ///to be processed.
    562     ///
    563     ///Returns \c false if there are nodes
    564     ///to be processed in the queue.
     567    ///Returns \c false if there are nodes to be processed.
     568
     569    ///Returns \c false if there are nodes to be processed
     570    ///in the queue.
    565571    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566572
    567573    ///Returns the number of the nodes to be processed.
    568574
    569     ///Returns the number of the nodes to be processed in the queue.
     575    ///Returns the number of the nodes to be processed
     576    ///in the queue.
    570577    int queueSize() const { return _queue_head-_queue_tail; }
    571578
     
    702709    ///Runs the algorithm to visit all nodes in the digraph.
    703710
    704     ///This method runs the %BFS algorithm in order to
    705     ///compute the shortest path to each node.
    706     ///
    707     ///The algorithm computes
    708     ///- the shortest path tree (forest),
    709     ///- 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.
    710713    ///
    711714    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    732735
    733736    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     737    ///The results of the BFS algorithm can be obtained using these
    735738    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     739    ///Either \ref run(Node) "run()" or \ref start() should be called
     740    ///before using them.
    738741
    739742    ///@{
    740743
    741     ///The shortest path to a node.
    742 
    743     ///Returns the shortest path to a node.
    744     ///
    745     ///\warning \c t should be reachable from the root(s).
    746     ///
    747     ///\pre Either \ref run() or \ref start() must be called before
    748     ///using this function.
     744    ///The shortest path to the given node.
     745
     746    ///Returns the shortest path to the given node from the root(s).
     747    ///
     748    ///\warning \c t should be reached from the root(s).
     749    ///
     750    ///\pre Either \ref run(Node) "run()" or \ref init()
     751    ///must be called before using this function.
    749752    Path path(Node t) const { return Path(*G, *_pred, t); }
    750753
    751     ///The distance of a node from the root(s).
    752 
    753     ///Returns the distance of a node from the root(s).
    754     ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///The distance of the given node from the root(s).
     755
     756    ///Returns the distance of the given node from the root(s).
     757    ///
     758    ///\warning If node \c v is not reached from the root(s), then
    756759    ///the return value of this function is undefined.
    757760    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     761    ///\pre Either \ref run(Node) "run()" or \ref init()
     762    ///must be called before using this function.
    760763    int dist(Node v) const { return (*_dist)[v]; }
    761764
    762     ///Returns the 'previous arc' of the shortest path tree for a node.
    763 
     765    ///\brief Returns the 'previous arc' of the shortest path tree for
     766    ///the given node.
     767    ///
    764768    ///This function returns the 'previous arc' of the shortest path
    765769    ///tree for the node \c v, i.e. it returns the last arc of a
    766     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    767     ///is not reachable from the root(s) or if \c v is a root.
     770    ///shortest path from a root to \c v. It is \c INVALID if \c v
     771    ///is not reached from the root(s) or if \c v is a root.
    768772    ///
    769773    ///The shortest path tree used here is equal to the shortest path
    770     ///tree used in \ref predNode().
    771     ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     774    ///tree used in \ref predNode() and \ref predMap().
     775    ///
     776    ///\pre Either \ref run(Node) "run()" or \ref init()
     777    ///must be called before using this function.
    774778    Arc predArc(Node v) const { return (*_pred)[v];}
    775779
    776     ///Returns the 'previous node' of the shortest path tree for a node.
    777 
     780    ///\brief Returns the 'previous node' of the shortest path tree for
     781    ///the given node.
     782    ///
    778783    ///This function returns the 'previous node' of the shortest path
    779784    ///tree for the node \c v, i.e. it returns the last but one node
    780     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    781     ///if \c v is not reachable from the root(s) or if \c v is a root.
     785    ///of a shortest path from a root to \c v. It is \c INVALID
     786    ///if \c v is not reached from the root(s) or if \c v is a root.
    782787    ///
    783788    ///The shortest path tree used here is equal to the shortest path
    784     ///tree used in \ref predArc().
    785     ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     789    ///tree used in \ref predArc() and \ref predMap().
     790    ///
     791    ///\pre Either \ref run(Node) "run()" or \ref init()
     792    ///must be called before using this function.
    788793    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789794                                  G->source((*_pred)[v]); }
     
    795800    ///of the nodes calculated by the algorithm.
    796801    ///
    797     ///\pre Either \ref run() or \ref init()
     802    ///\pre Either \ref run(Node) "run()" or \ref init()
    798803    ///must be called before using this function.
    799804    const DistMap &distMap() const { return *_dist;}
     
    803808    ///
    804809    ///Returns a const reference to the node map that stores the predecessor
    805     ///arcs, which form the shortest path tree.
    806     ///
    807     ///\pre Either \ref run() or \ref init()
     810    ///arcs, which form the shortest path tree (forest).
     811    ///
     812    ///\pre Either \ref run(Node) "run()" or \ref init()
    808813    ///must be called before using this function.
    809814    const PredMap &predMap() const { return *_pred;}
    810815
    811     ///Checks if a node is reachable from the root(s).
    812 
    813     ///Returns \c true if \c v is reachable from the root(s).
    814     ///\pre Either \ref run() or \ref start()
     816    ///Checks if the given node is reached from the root(s).
     817
     818    ///Returns \c true if \c v is reached from the root(s).
     819    ///
     820    ///\pre Either \ref run(Node) "run()" or \ref init()
    815821    ///must be called before using this function.
    816822    bool reached(Node v) const { return (*_reached)[v]; }
     
    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),
     
    958961  /// This auxiliary class is created to implement the
    959962  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run() method, it uses the functions
    961   /// and features of the plain \ref Bfs.
     963  /// It does not have own \ref run(Node) "run()" method, it uses the
     964  /// functions and features of the plain \ref Bfs.
    962965  ///
    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)
     
    11791183  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801184  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1185  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821186  ///to the end of the parameter list.
    11831187  ///\sa BfsWizard
     
    11951199  /// This class defines the interface of the BfsVisit events, and
    11961200  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1201  template <typename GR>
    11981202  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1203    typedef GR Digraph;
    12001204    typedef typename Digraph::Arc Arc;
    12011205    typedef typename Digraph::Node Node;
     
    12251229  };
    12261230#else
    1227   template <typename _Digraph>
     1231  template <typename GR>
    12281232  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1233    typedef GR Digraph;
    12301234    typedef typename Digraph::Arc Arc;
    12311235    typedef typename Digraph::Node Node;
     
    12551259  ///
    12561260  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1261  /// \tparam GR The type of the digraph the algorithm runs on.
     1262  template<class GR>
    12591263  struct BfsVisitDefaultTraits {
    12601264
    12611265    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1266    typedef GR Digraph;
    12631267
    12641268    /// \brief The type of the map that indicates which nodes are reached.
    12651269    ///
    12661270    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1271    /// It must conform to
     1272    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681273    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691274
     
    12811286  /// \ingroup search
    12821287  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1288  /// \brief BFS algorithm class with visitor interface.
    12841289  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1290  /// This class provides an efficient implementation of the BFS algorithm
    12861291  /// with visitor interface.
    12871292  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1293  /// The BfsVisit class provides an alternative interface to the Bfs
    12891294  /// class. It works with callback mechanism, the BfsVisit object calls
    12901295  /// the member functions of the \c Visitor class on every BFS event.
     
    12951300  /// instead.
    12961301  ///
    1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1298   /// The default value is
    1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1302  /// \tparam GR The type of the digraph the algorithm runs on.
     1303  /// The default type is \ref ListDigraph.
     1304  /// The value of GR is not used directly by \ref BfsVisit,
     1305  /// it is only passed to \ref BfsVisitDefaultTraits.
     1306  /// \tparam VS The Visitor type that is used by the algorithm.
     1307  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031308  /// does not observe the BFS events. If you want to observe the BFS
    13041309  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
    1306   /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    1308   /// See \ref BfsVisitDefaultTraits for the documentation of
    1309   /// a BFS visit traits class.
     1310  /// \tparam TR The traits class that defines various types used by the
     1311  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
     1312  /// "BfsVisitDefaultTraits<GR>".
     1313  /// In most cases, this parameter should not be set directly,
     1314  /// consider to use the named template parameters instead.
    13101315#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1316  template <typename GR, typename VS, typename TR>
    13121317#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1318  template <typename GR = ListDigraph,
     1319            typename VS = BfsVisitor<GR>,
     1320            typename TR = BfsVisitDefaultTraits<GR> >
    13161321#endif
    13171322  class BfsVisit {
     
    13191324
    13201325    ///The traits class.
    1321     typedef _Traits Traits;
     1326    typedef TR Traits;
    13221327
    13231328    ///The type of the digraph the algorithm runs on.
     
    13251330
    13261331    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1332    typedef VS Visitor;
    13281333
    13291334    ///The type of the map that indicates which nodes are reached.
     
    13651370    typedef BfsVisit Create;
    13661371
    1367     /// \name Named template parameters
     1372    /// \name Named Template Parameters
    13681373
    13691374    ///@{
     
    14071412    ///
    14081413    /// Sets the map that indicates which nodes are reached.
    1409     /// If you don't use this function before calling \ref run(),
    1410     /// it will allocate one. The destructor deallocates this
    1411     /// automatically allocated map, of course.
     1414    /// If you don't use this function before calling \ref run(Node) "run()"
     1415    /// or \ref init(), an instance will be allocated automatically.
     1416    /// The destructor deallocates this automatically allocated map,
     1417    /// of course.
    14121418    /// \return <tt> (*this) </tt>
    14131419    BfsVisit &reachedMap(ReachedMap &m) {
     
    14221428  public:
    14231429
    1424     /// \name Execution control
    1425     /// The simplest way to execute the algorithm is to use
    1426     /// one of the member functions called \ref lemon::BfsVisit::run()
    1427     /// "run()".
    1428     /// \n
    1429     /// If you need more control on the execution, first you must call
    1430     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1431     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1432     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1433     /// actual path computation.
     1430    /// \name Execution Control
     1431    /// The simplest way to execute the BFS algorithm is to use one of the
     1432    /// member functions called \ref run(Node) "run()".\n
     1433    /// If you need better control on the execution, you have to call
     1434    /// \ref init() first, then you can add several source nodes with
     1435    /// \ref addSource(). Finally the actual path computation can be
     1436    /// performed with one of the \ref start() functions.
    14341437
    14351438    /// @{
     
    17011704    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17021705    ///
    1703     /// This method runs the %BFS algorithm in order to
    1704     /// compute the shortest path to each node.
    1705     ///
    1706     /// The algorithm computes
    1707     /// - the shortest path tree (forest),
    1708     /// - the distance of each node from the root(s).
     1706    /// This method runs the %BFS algorithm in order to visit all nodes
     1707    /// in the digraph.
    17091708    ///
    17101709    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    17311730
    17321731    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1732    /// The results of the BFS algorithm can be obtained using these
    17341733    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1734    /// Either \ref run(Node) "run()" or \ref start() should be called
     1735    /// before using them.
     1736
    17381737    ///@{
    17391738
    1740     /// \brief Checks if a node is reachable from the root(s).
    1741     ///
    1742     /// Returns \c true if \c v is reachable from the root(s).
    1743     /// \pre Either \ref run() or \ref start()
     1739    /// \brief Checks if the given node is reached from the root(s).
     1740    ///
     1741    /// Returns \c true if \c v is reached from the root(s).
     1742    ///
     1743    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441744    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1745    bool reached(Node v) const { return (*_reached)[v]; }
    17461746
    17471747    ///@}
  • lemon/bin_heap.h

    r209 r711  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure. A \e heap
    37   ///is a data structure for storing items with specified values called \e
    38   ///priorities in such a way that finding the item with minimum priority is
    39   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    40   ///one can change the priority of an item, add or erase an item, etc.
     36  /// This class implements the \e binary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4138  ///
    42   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
    44   ///to handle the cross references.
    45   ///\tparam _Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<_Prio>.
    47   ///
    48   ///\sa FibHeap
    49   ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     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
    5249  class BinHeap {
    53 
    5450  public:
    55     ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
    59     ///\e
     51
     52    /// Type of the item-int map.
     53    typedef IM ItemIntMap;
     54    /// Type of the priorities.
     55    typedef PR Prio;
     56    /// Type of the items stored in the heap.
    6057    typedef typename ItemIntMap::Key Item;
    61     ///\e
     58    /// Type of the item-priority pairs.
    6259    typedef std::pair<Item,Prio> Pair;
    63     ///\e
    64     typedef _Compare Compare;
    65 
    66     /// \brief Type to represent the items states.
    67     ///
    68     /// Each Item element have a state associated to it. It may be "in heap",
    69     /// "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
    7067    /// heap's point of view, but may be useful to the user.
    7168    ///
    72     /// The ItemIntMap \e should be initialized in such way that it maps
    73     /// PRE_HEAP (-1) to any element to be put in the heap...
     69    /// The item-int map must be initialized in such way that it assigns
     70    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7471    enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
     72      IN_HEAP = 0,    ///< = 0.
     73      PRE_HEAP = -1,  ///< = -1.
     74      POST_HEAP = -2  ///< = -2.
    7875    };
    7976
    8077  private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
     78    std::vector<Pair> _data;
     79    Compare _comp;
     80    ItemIntMap &_iim;
    8481
    8582  public:
    86     /// \brief The constructor.
    87     ///
    88     /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
    90     /// internally to handle the cross references. The value of the map
    91     /// should be PRE_HEAP (-1) for each element.
    92     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93 
    94     /// \brief The constructor.
    95     ///
    96     /// The constructor.
    97     /// \param _iim should be given to the constructor, since it is used
    98     /// internally to handle the cross references. The value of the map
    99     /// should be PRE_HEAP (-1) for each element.
    100     ///
    101     /// \param _comp The comparator function object.
    102     BinHeap(ItemIntMap &_iim, const Compare &_comp)
    103       : iim(_iim), comp(_comp) {}
    104 
    105 
    106     /// The number of items stored in the heap.
    107     ///
    108     /// \brief Returns the number of items stored in the heap.
    109     int size() const { return data.size(); }
    110 
    111     /// \brief Checks if the heap stores no items.
    112     ///
    113     /// Returns \c true if and only if the heap stores no items.
    114     bool empty() const { return data.empty(); }
    115 
    116     /// \brief Make empty this heap.
    117     ///
    118     /// Make empty this heap. It does not change the cross reference map.
    119     /// If you want to reuse what is not surely empty you should first clear
    120     /// the heap and after that you should set the cross reference map for
    121     /// each item to \c PRE_HEAP.
     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.
     90    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
     91
     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.
     99    BinHeap(ItemIntMap &map, const Compare &comp)
     100      : _iim(map), _comp(comp) {}
     101
     102
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
     106    int size() const { return _data.size(); }
     107
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
     111    bool empty() const { return _data.empty(); }
     112
     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.
    122120    void clear() {
    123       data.clear();
     121      _data.clear();
    124122    }
    125123
     
    127125    static int parent(int i) { return (i-1)/2; }
    128126
    129     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    130128    bool less(const Pair &p1, const Pair &p2) const {
    131       return comp(p1.second, p2.second);
    132     }
    133 
    134     int bubble_up(int hole, Pair p) {
     129      return _comp(p1.second, p2.second);
     130    }
     131
     132    int bubbleUp(int hole, Pair p) {
    135133      int par = parent(hole);
    136       while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
     134      while( hole>0 && less(p,_data[par]) ) {
     135        move(_data[par],hole);
    138136        hole = par;
    139137        par = parent(hole);
     
    143141    }
    144142
    145     int bubble_down(int hole, Pair p, int length) {
    146       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    147145      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
     146        if( less(_data[child-1], _data[child]) ) {
    149147          --child;
    150148        }
    151         if( !less(data[child], p) )
     149        if( !less(_data[child], p) )
    152150          goto ok;
    153         move(data[child], hole);
     151        move(_data[child], hole);
    154152        hole = child;
    155         child = second_child(hole);
     153        child = secondChild(hole);
    156154      }
    157155      child--;
    158       if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
     156      if( child<length && less(_data[child], p) ) {
     157        move(_data[child], hole);
    160158        hole=child;
    161159      }
     
    166164
    167165    void move(const Pair &p, int i) {
    168       data[i] = p;
    169       iim.set(p.first, i);
     166      _data[i] = p;
     167      _iim.set(p.first, i);
    170168    }
    171169
    172170  public:
     171
    173172    /// \brief Insert a pair of item and priority into the heap.
    174173    ///
    175     /// 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.
    176176    /// \param p The pair to insert.
     177    /// \pre \c p.first must not be stored in the heap.
    177178    void push(const Pair &p) {
    178       int n = data.size();
    179       data.resize(n+1);
    180       bubble_up(n, p);
    181     }
    182 
    183     /// \brief Insert an item into the heap with the given heap.
    184     ///
    185     /// Adds \c i to the heap with priority \c p.
     179      int n = _data.size();
     180      _data.resize(n+1);
     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.
    186188    /// \param i The item to insert.
    187189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    188191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    189192
    190     /// \brief Returns the item with minimum priority relative to \c Compare.
    191     ///
    192     /// This method returns the item with minimum priority relative to \c
    193     /// Compare.
    194     /// \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.
    195197    Item top() const {
    196       return data[0].first;
    197     }
    198 
    199     /// \brief Returns the minimum priority relative to \c Compare.
    200     ///
    201     /// It returns the minimum priority relative to \c Compare.
    202     /// \pre The heap must be nonempty.
     198      return _data[0].first;
     199    }
     200
     201    /// \brief The minimum priority.
     202    ///
     203    /// This function returns the minimum priority.
     204    /// \pre The heap must be non-empty.
    203205    Prio prio() const {
    204       return data[0].second;
    205     }
    206 
    207     /// \brief Deletes the item with minimum priority relative to \c Compare.
    208     ///
    209     /// This method deletes the item with minimum priority relative to \c
    210     /// Compare from the heap.
     206      return _data[0].second;
     207    }
     208
     209    /// \brief Remove the item having minimum priority.
     210    ///
     211    /// This function removes the item having minimum priority.
    211212    /// \pre The heap must be non-empty.
    212213    void pop() {
    213       int n = data.size()-1;
    214       iim.set(data[0].first, POST_HEAP);
     214      int n = _data.size()-1;
     215      _iim.set(_data[0].first, POST_HEAP);
    215216      if (n > 0) {
    216         bubble_down(0, data[n], n);
    217       }
    218       data.pop_back();
    219     }
    220 
    221     /// \brief Deletes \c i from the heap.
    222     ///
    223     /// This method deletes item \c i from the heap.
    224     /// \param i The item to erase.
    225     /// \pre The item should be in the heap.
     217        bubbleDown(0, _data[n], n);
     218      }
     219      _data.pop_back();
     220    }
     221
     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.
    226228    void erase(const Item &i) {
    227       int h = iim[i];
    228       int n = data.size()-1;
    229       iim.set(data[h].first, POST_HEAP);
     229      int h = _iim[i];
     230      int n = _data.size()-1;
     231      _iim.set(_data[h].first, POST_HEAP);
    230232      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    233235        }
    234236      }
    235       data.pop_back();
    236     }
    237 
    238 
    239     /// \brief Returns the priority of \c i.
    240     ///
    241     /// This function returns the priority of item \c i.
    242     /// \pre \c i must be in the heap.
    243     /// \param i The item.
     237      _data.pop_back();
     238    }
     239
     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.
    244245    Prio operator[](const Item &i) const {
    245       int idx = iim[i];
    246       return data[idx].second;
    247     }
    248 
    249     /// \brief \c i gets to the heap with priority \c p independently
    250     /// if \c i was already there.
    251     ///
    252     /// This method calls \ref push(\c i, \c p) if \c i is not stored
    253     /// in the heap and sets the priority of \c i to \c p otherwise.
     246      int idx = _iim[i];
     247      return _data[idx].second;
     248    }
     249
     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.
    254256    /// \param i The item.
    255257    /// \param p The priority.
    256258    void set(const Item &i, const Prio &p) {
    257       int idx = iim[i];
     259      int idx = _iim[i];
    258260      if( idx < 0 ) {
    259261        push(i,p);
    260262      }
    261       else if( comp(p, data[idx].second) ) {
    262         bubble_up(idx, Pair(i,p));
     263      else if( _comp(p, _data[idx].second) ) {
     264        bubbleUp(idx, Pair(i,p));
    263265      }
    264266      else {
    265         bubble_down(idx, Pair(i,p), data.size());
    266       }
    267     }
    268 
    269     /// \brief Decreases the priority of \c i to \c p.
    270     ///
    271     /// This method decreases the priority of item \c i to \c p.
    272     /// \pre \c i must be stored in the heap with priority at least \c
    273     /// p relative to \c Compare.
     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.
    274274    /// \param i The item.
    275275    /// \param p The priority.
     276    /// \pre \e i must be stored in the heap with priority at least \e p.
    276277    void decrease(const Item &i, const Prio &p) {
    277       int idx = iim[i];
    278       bubble_up(idx, Pair(i,p));
    279     }
    280 
    281     /// \brief Increases the priority of \c i to \c p.
    282     ///
    283     /// This method sets the priority of item \c i to \c p.
    284     /// \pre \c i must be stored in the heap with priority at most \c
    285     /// p relative to \c Compare.
     278      int idx = _iim[i];
     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.
    286285    /// \param i The item.
    287286    /// \param p The priority.
     287    /// \pre \e i must be stored in the heap with priority at most \e p.
    288288    void increase(const Item &i, const Prio &p) {
    289       int idx = iim[i];
    290       bubble_down(idx, Pair(i,p), data.size());
    291     }
    292 
    293     /// \brief Returns if \c item is in, has already been in, or has
    294     /// never been in the heap.
    295     ///
    296     /// This method returns PRE_HEAP if \c item has never been in the
    297     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
    298     /// otherwise. In the latter case it is possible that \c item will
    299     /// get back to the heap again.
     289      int idx = _iim[i];
     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.
    300300    /// \param i The item.
    301301    State state(const Item &i) const {
    302       int s = iim[i];
     302      int s = _iim[i];
    303303      if( s>=0 )
    304304        s=0;
     
    306306    }
    307307
    308     /// \brief Sets the state of the \c item in the heap.
    309     ///
    310     /// Sets the state of the \c item in the heap. It can be used to
    311     /// manually clear the heap when it is important to achive the
    312     /// 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.
    313313    /// \param i The item.
    314314    /// \param st The state. It should not be \c IN_HEAP.
     
    320320          erase(i);
    321321        }
    322         iim[i] = st;
     322        _iim[i] = st;
    323323        break;
    324324      case IN_HEAP:
     
    327327    }
    328328
    329     /// \brief Replaces an item in the heap.
    330     ///
    331     /// The \c i item is replaced with \c j item. The \c i item should
    332     /// be in the heap, while the \c j should be out of the heap. The
    333     /// \c i item will out of the heap and \c j will be in the heap
    334     /// 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.
    335336    void replace(const Item& i, const Item& j) {
    336       int idx = iim[i];
    337       iim.set(i, iim[j]);
    338       iim.set(j, idx);
    339       data[idx].first = j;
     337      int idx = _iim[i];
     338      _iim.set(i, _iim[j]);
     339      _iim.set(j, idx);
     340      _data[idx].first = j;
    340341    }
    341342
  • lemon/bits/alteration_notifier.h

    r314 r440  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636  // a container.
    3737  //
    38   // The simple graph's can be refered as two containers, one node container
    39   // and one edge container. But they are not standard containers they
    40   // does not store values directly they are just key continars for more
    41   // value containers which are the node and edge maps.
    42   //
    43   // The graph's node and edge sets can be changed as we add or erase
     38  // The simple graphs can be refered as two containers: a node container
     39  // and an edge container. But they do not store values directly, they
     40  // are just key continars for more value containers, which are the
     41  // node and edge maps.
     42  //
     43  // The node and edge sets of the graphs can be changed as we add or erase
    4444  // nodes and edges in the graph. LEMON would like to handle easily
    4545  // that the node and edge maps should contain values for all nodes or
    4646  // edges. If we want to check on every indicing if the map contains
    4747  // the current indicing key that cause a drawback in the performance
    48   // in the library. We use another solution we notify all maps about
     48  // in the library. We use another solution: we notify all maps about
    4949  // an alteration in the graph, which cause only drawback on the
    5050  // alteration of the graph.
    5151  //
    52   // This class provides an interface to the container. The \e first() and \e
    53   // next() member functions make possible to iterate on the keys of the
    54   // container. The \e id() function returns an integer id for each key.
    55   // The \e maxId() function gives back an upper bound of the ids.
     52  // This class provides an interface to a node or edge container.
     53  // The first() and next() member functions make possible
     54  // to iterate on the keys of the container.
     55  // The id() function returns an integer id for each key.
     56  // The maxId() function gives back an upper bound of the ids.
    5657  //
    5758  // For the proper functonality of this class, we should notify it
    58   // about each alteration in the container. The alterations have four type
    59   // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
    60   // \e erase() signals that only one or few items added or erased to or
    61   // from the graph. If all items are erased from the graph or from an empty
    62   // graph a new graph is builded then it can be signaled with the
     59  // about each alteration in the container. The alterations have four type:
     60  // add(), erase(), build() and clear(). The add() and
     61  // erase() signal that only one or few items added or erased to or
     62  // from the graph. If all items are erased from the graph or if a new graph
     63  // is built from an empty graph, then it can be signaled with the
    6364  // clear() and build() members. Important rule that if we erase items
    64   // from graph we should first signal the alteration and after that erase
     65  // from graphs we should first signal the alteration and after that erase
    6566  // them from the container, on the other way on item addition we should
    6667  // first extend the container and just after that signal the alteration.
    6768  //
    6869  // The alteration can be observed with a class inherited from the
    69   // \e ObserverBase nested class. The signals can be handled with
     70  // ObserverBase nested class. The signals can be handled with
    7071  // overriding the virtual functions defined in the base class.  The
    7172  // observer base can be attached to the notifier with the
    72   // \e attach() member and can be detached with detach() function. The
     73  // attach() member and can be detached with detach() function. The
    7374  // alteration handlers should not call any function which signals
    7475  // an other alteration in the same notifier and should not
    7576  // detach any observer from the notifier.
    7677  //
    77   // Alteration observers try to be exception safe. If an \e add() or
    78   // a \e clear() function throws an exception then the remaining
     78  // Alteration observers try to be exception safe. If an add() or
     79  // a clear() function throws an exception then the remaining
    7980  // observeres will not be notified and the fulfilled additions will
    80   // be rolled back by calling the \e erase() or \e clear()
    81   // functions. Thence the \e erase() and \e clear() should not throw
    82   // exception. Actullay, it can be throw only \ref ImmediateDetach
    83   // exception which detach the observer from the notifier.
    84   //
    85   // There are some place when the alteration observing is not completly
     81  // be rolled back by calling the erase() or clear() functions.
     82  // Hence erase() and clear() should not throw exception.
     83  // Actullay, they can throw only \ref ImmediateDetach exception,
     84  // which detach the observer from the notifier.
     85  //
     86  // There are some cases, when the alteration observing is not completly
    8687  // reliable. If we want to carry out the node degree in the graph
    87   // as in the \ref InDegMap and we use the reverseEdge that cause
     88  // as in the \ref InDegMap and we use the reverseArc(), then it cause
    8889  // unreliable functionality. Because the alteration observing signals
    89   // only erasing and adding but not the reversing it will stores bad
    90   // degrees. The sub graph adaptors cannot signal the alterations because
    91   // just a setting in the filter map can modify the graph and this cannot
    92   // be watched in any way.
     90  // only erasing and adding but not the reversing, it will stores bad
     91  // degrees. Apart form that the subgraph adaptors cannot even signal
     92  // the alterations because just a setting in the filter map can modify
     93  // the graph and this cannot be watched in any way.
    9394  //
    9495  // \param _Container The container which is observed.
     
    104105    typedef _Item Item;
    105106
    106     // \brief Exception which can be called from \e clear() and
    107     // \e erase().
    108     //
    109     // From the \e clear() and \e erase() function only this
     107    // \brief Exception which can be called from clear() and
     108    // erase().
     109    //
     110    // From the clear() and erase() function only this
    110111    // exception is allowed to throw. The exception immediatly
    111112    // detaches the current observer from the notifier. Because the
    112     // \e clear() and \e erase() should not throw other exceptions
     113    // clear() and erase() should not throw other exceptions
    113114    // it can be used to invalidate the observer.
    114115    struct ImmediateDetach {};
     
    122123    // The observer interface contains some pure virtual functions
    123124    // to override. The add() and erase() functions are
    124     // to notify the oberver when one item is added or
    125     // erased.
     125    // to notify the oberver when one item is added or erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer
  • lemon/bits/array_map.h

    r314 r877  
    33 * 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).
     
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure what
    40   // automatically updates the map when a key is added to or erased from
    41   // the map. This map uses the allocators to implement
    42   // the container functionality.
     39  // The ArrayMap template class is graph map structure that automatically
     40  // updates the map when a key is added to or erased from the graph.
     41  // This map uses the allocators to implement the container functionality.
    4342  //
    44   // The template parameters are the Graph the current Item type and
     43  // The template parameters are the Graph, the current Item type and
    4544  // the Value type of the map.
    4645  template <typename _Graph, typename _Item, typename _Value>
     
    4847    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4948  public:
    50     // The graph type of the maps.
    51     typedef _Graph Graph;
    52     // The item type of the map.
     49    // The graph type.
     50    typedef _Graph GraphType;
     51    // The item type.
    5352    typedef _Item Item;
    5453    // The reference map tag.
    5554    typedef True ReferenceMapTag;
    5655
    57     // The key type of the maps.
     56    // The key type of the map.
    5857    typedef _Item Key;
    5958    // The value type of the map.
     
    6564    typedef _Value& Reference;
    6665
     66    // The map type.
     67    typedef ArrayMap Map;
     68
    6769    // The notifier type.
    6870    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6971
     72  private:
     73
    7074    // The MapBase of the Map which imlements the core regisitry function.
    7175    typedef typename Notifier::ObserverBase Parent;
    7276
    73   private:
    7477    typedef std::allocator<Value> Allocator;
    7578
     
    7982    //
    8083    // Graph initialized map constructor.
    81     explicit ArrayMap(const Graph& graph) {
     84    explicit ArrayMap(const GraphType& graph) {
    8285      Parent::attach(graph.notifier(Item()));
    8386      allocate_memory();
     
    9396    //
    9497    // It constructs a map and initialize all of the the map.
    95     ArrayMap(const Graph& graph, const Value& value) {
     98    ArrayMap(const GraphType& graph, const Value& value) {
    9699      Parent::attach(graph.notifier(Item()));
    97100      allocate_memory();
     
    137140    // \brief Template assign operator.
    138141    //
    139     // The given parameter should be conform to the ReadMap
     142    // The given parameter should conform to the ReadMap
    140143    // concecpt and could be indiced by the current item set of
    141144    // the NodeMap. In this case the value for each item
     
    201204    // \brief Adds a new key to the map.
    202205    //
    203     // It adds a new key to the map. It called by the observer notifier
     206    // It adds a new key to the map. It is called by the observer notifier
    204207    // and it overrides the add() member function of the observer base.
    205208    virtual void add(const Key& key) {
     
    229232    // \brief Adds more new keys to the map.
    230233    //
    231     // It adds more new keys to the map. It called by the observer notifier
     234    // It adds more new keys to the map. It is called by the observer notifier
    232235    // and it overrides the add() member function of the observer base.
    233236    virtual void add(const std::vector<Key>& keys) {
     
    273276    // \brief Erase a key from the map.
    274277    //
    275     // Erase a key from the map. It called by the observer notifier
     278    // Erase a key from the map. It is called by the observer notifier
    276279    // and it overrides the erase() member function of the observer base.
    277280    virtual void erase(const Key& key) {
     
    282285    // \brief Erase more keys from the map.
    283286    //
    284     // Erase more keys from the map. It called by the observer notifier
     287    // Erase more keys from the map. It is called by the observer notifier
    285288    // and it overrides the erase() member function of the observer base.
    286289    virtual void erase(const std::vector<Key>& keys) {
     
    291294    }
    292295
    293     // \brief Buildes the map.
    294     //
    295     // It buildes the map. It called by the observer notifier
     296    // \brief Builds the map.
     297    //
     298    // It builds the map. It is called by the observer notifier
    296299    // and it overrides the build() member function of the observer base.
    297300    virtual void build() {
     
    307310    // \brief Clear the map.
    308311    //
    309     // It erase all items from the map. It called by the observer notifier
     312    // It erase all items from the map. It is called by the observer notifier
    310313    // and it overrides the clear() member function of the observer base.
    311314    virtual void clear() {
  • lemon/bits/bezier.h

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

    r511 r877  
    33 * 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).
     
    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/enable_if.h

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

    r314 r778  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the digraph types
     32//\brief Extenders for the graph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the Digraphs
     37  // \brief Extender for the digraph implementations
    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    }
     
    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

    r801 r802  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    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
     
    115119
    116120    class ConstMapIt : public Item {
    117     public:
    118 
    119       typedef Item Parent;
     121      typedef Item Parent;
     122
     123    public:
    120124
    121125      typedef typename Map::Value Value;
     
    146150
    147151    class ItemIt : public Item {
    148     public:
    149 
    150       typedef Item Parent;
    151 
     152      typedef Item Parent;
     153
     154    public:
    152155      ItemIt() : map(NULL) {}
     156
    153157
    154158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     
    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
     
    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;
     
    290297
    291298    class ItemIt : public Item {
    292     public:
    293 
    294       typedef Item Parent;
    295 
     299      typedef Item Parent;
     300
     301    public:
    296302      ItemIt() : map(NULL) {}
     303
    297304
    298305      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     
    317324  private:
    318325
    319     const Graph& graph;
     326    const GraphType& graph;
    320327
    321328  };
  • lemon/bits/path_dump.h

    r886 r887  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_BITS_PRED_MAP_PATH_H
    20 #define LEMON_BITS_PRED_MAP_PATH_H
     19#ifndef LEMON_BITS_PATH_DUMP_H
     20#define LEMON_BITS_PATH_DUMP_H
     21
     22#include <lemon/core.h>
     23#include <lemon/concept_check.h>
    2124
    2225namespace lemon {
  • lemon/bits/traits.h

    r314 r616  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  struct InvalidType {};
    3131
    32   template <typename _Graph, typename _Item>
     32  template <typename GR, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename Graph, typename Enable = void>
     36  template <typename GR, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename Graph>
     40  template <typename GR>
    4141  struct NodeNotifierIndicator<
    42     Graph,
    43     typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
    44   > {
    45     typedef typename Graph::NodeNotifier Type;
    46   };
    47 
    48   template <typename _Graph>
    49   class ItemSetTraits<_Graph, typename _Graph::Node> {
     42    GR,
     43    typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
     44  > {
     45    typedef typename GR::NodeNotifier Type;
     46  };
     47
     48  template <typename GR>
     49  class ItemSetTraits<GR, typename GR::Node> {
    5050  public:
    5151
    52     typedef _Graph Graph;
    53 
    54     typedef typename Graph::Node Item;
    55     typedef typename Graph::NodeIt ItemIt;
    56 
    57     typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
    58 
    59     template <typename _Value>
    60     class Map : public Graph::template NodeMap<_Value> {
     52    typedef GR Graph;
     53    typedef GR Digraph;
     54
     55    typedef typename GR::Node Item;
     56    typedef typename GR::NodeIt ItemIt;
     57
     58    typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
     59
     60    template <typename V>
     61    class Map : public GR::template NodeMap<V> {
     62      typedef typename GR::template NodeMap<V> Parent;
     63
    6164    public:
    62       typedef typename Graph::template NodeMap<_Value> Parent;
    63       typedef typename Graph::template NodeMap<_Value> Type;
     65      typedef typename GR::template NodeMap<V> Type;
    6466      typedef typename Parent::Value Value;
    6567
    66       Map(const Graph& _digraph) : Parent(_digraph) {}
    67       Map(const Graph& _digraph, const Value& _value)
     68      Map(const GR& _digraph) : Parent(_digraph) {}
     69      Map(const GR& _digraph, const Value& _value)
    6870        : Parent(_digraph, _value) {}
    6971
     
    7274  };
    7375
    74   template <typename Graph, typename Enable = void>
     76  template <typename GR, typename Enable = void>
    7577  struct ArcNotifierIndicator {
    7678    typedef InvalidType Type;
    7779  };
    78   template <typename Graph>
     80  template <typename GR>
    7981  struct ArcNotifierIndicator<
    80     Graph,
    81     typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
    82   > {
    83     typedef typename Graph::ArcNotifier Type;
    84   };
    85 
    86   template <typename _Graph>
    87   class ItemSetTraits<_Graph, typename _Graph::Arc> {
     82    GR,
     83    typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
     84  > {
     85    typedef typename GR::ArcNotifier Type;
     86  };
     87
     88  template <typename GR>
     89  class ItemSetTraits<GR, typename GR::Arc> {
    8890  public:
    8991
    90     typedef _Graph Graph;
    91 
    92     typedef typename Graph::Arc Item;
    93     typedef typename Graph::ArcIt ItemIt;
    94 
    95     typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
    96 
    97     template <typename _Value>
    98     class Map : public Graph::template ArcMap<_Value> {
     92    typedef GR Graph;
     93    typedef GR Digraph;
     94
     95    typedef typename GR::Arc Item;
     96    typedef typename GR::ArcIt ItemIt;
     97
     98    typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
     99
     100    template <typename V>
     101    class Map : public GR::template ArcMap<V> {
     102      typedef typename GR::template ArcMap<V> Parent;
     103
    99104    public:
    100       typedef typename Graph::template ArcMap<_Value> Parent;
    101       typedef typename Graph::template ArcMap<_Value> Type;
     105      typedef typename GR::template ArcMap<V> Type;
    102106      typedef typename Parent::Value Value;
    103107
    104       Map(const Graph& _digraph) : Parent(_digraph) {}
    105       Map(const Graph& _digraph, const Value& _value)
     108      Map(const GR& _digraph) : Parent(_digraph) {}
     109      Map(const GR& _digraph, const Value& _value)
    106110        : Parent(_digraph, _value) {}
    107111    };
     
    109113  };
    110114
    111   template <typename Graph, typename Enable = void>
     115  template <typename GR, typename Enable = void>
    112116  struct EdgeNotifierIndicator {
    113117    typedef InvalidType Type;
    114118  };
    115   template <typename Graph>
     119  template <typename GR>
    116120  struct EdgeNotifierIndicator<
    117     Graph,
    118     typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
    119   > {
    120     typedef typename Graph::EdgeNotifier Type;
    121   };
    122 
    123   template <typename _Graph>
    124   class ItemSetTraits<_Graph, typename _Graph::Edge> {
     121    GR,
     122    typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
     123  > {
     124    typedef typename GR::EdgeNotifier Type;
     125  };
     126
     127  template <typename GR>
     128  class ItemSetTraits<GR, typename GR::Edge> {
    125129  public:
    126130
    127     typedef _Graph Graph;
    128 
    129     typedef typename Graph::Edge Item;
    130     typedef typename Graph::EdgeIt ItemIt;
    131 
    132     typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
    133 
    134     template <typename _Value>
    135     class Map : public Graph::template EdgeMap<_Value> {
     131    typedef GR Graph;
     132    typedef GR Digraph;
     133
     134    typedef typename GR::Edge Item;
     135    typedef typename GR::EdgeIt ItemIt;
     136
     137    typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
     138
     139    template <typename V>
     140    class Map : public GR::template EdgeMap<V> {
     141      typedef typename GR::template EdgeMap<V> Parent;
     142
    136143    public:
    137       typedef typename Graph::template EdgeMap<_Value> Parent;
    138       typedef typename Graph::template EdgeMap<_Value> Type;
     144      typedef typename GR::template EdgeMap<V> Type;
    139145      typedef typename Parent::Value Value;
    140146
    141       Map(const Graph& _digraph) : Parent(_digraph) {}
    142       Map(const Graph& _digraph, const Value& _value)
     147      Map(const GR& _digraph) : Parent(_digraph) {}
     148      Map(const GR& _digraph, const Value& _value)
    143149        : Parent(_digraph, _value) {}
    144150    };
     
    205211  // Indicators for the tags
    206212
    207   template <typename Graph, typename Enable = void>
     213  template <typename GR, typename Enable = void>
    208214  struct NodeNumTagIndicator {
    209215    static const bool value = false;
    210216  };
    211217
    212   template <typename Graph>
     218  template <typename GR>
    213219  struct NodeNumTagIndicator<
    214     Graph,
    215     typename enable_if<typename Graph::NodeNumTag, void>::type
    216   > {
    217     static const bool value = true;
    218   };
    219 
    220   template <typename Graph, typename Enable = void>
     220    GR,
     221    typename enable_if<typename GR::NodeNumTag, void>::type
     222  > {
     223    static const bool value = true;
     224  };
     225
     226  template <typename GR, typename Enable = void>
     227  struct ArcNumTagIndicator {
     228    static const bool value = false;
     229  };
     230
     231  template <typename GR>
     232  struct ArcNumTagIndicator<
     233    GR,
     234    typename enable_if<typename GR::ArcNumTag, void>::type
     235  > {
     236    static const bool value = true;
     237  };
     238
     239  template <typename GR, typename Enable = void>
    221240  struct EdgeNumTagIndicator {
    222241    static const bool value = false;
    223242  };
    224243
    225   template <typename Graph>
     244  template <typename GR>
    226245  struct EdgeNumTagIndicator<
    227     Graph,
    228     typename enable_if<typename Graph::EdgeNumTag, void>::type
    229   > {
    230     static const bool value = true;
    231   };
    232 
    233   template <typename Graph, typename Enable = void>
     246    GR,
     247    typename enable_if<typename GR::EdgeNumTag, void>::type
     248  > {
     249    static const bool value = true;
     250  };
     251
     252  template <typename GR, typename Enable = void>
     253  struct FindArcTagIndicator {
     254    static const bool value = false;
     255  };
     256
     257  template <typename GR>
     258  struct FindArcTagIndicator<
     259    GR,
     260    typename enable_if<typename GR::FindArcTag, void>::type
     261  > {
     262    static const bool value = true;
     263  };
     264
     265  template <typename GR, typename Enable = void>
    234266  struct FindEdgeTagIndicator {
    235267    static const bool value = false;
    236268  };
    237269
    238   template <typename Graph>
     270  template <typename GR>
    239271  struct FindEdgeTagIndicator<
    240     Graph,
    241     typename enable_if<typename Graph::FindEdgeTag, void>::type
    242   > {
    243     static const bool value = true;
    244   };
    245 
    246   template <typename Graph, typename Enable = void>
     272    GR,
     273    typename enable_if<typename GR::FindEdgeTag, void>::type
     274  > {
     275    static const bool value = true;
     276  };
     277
     278  template <typename GR, typename Enable = void>
    247279  struct UndirectedTagIndicator {
    248280    static const bool value = false;
    249281  };
    250282
    251   template <typename Graph>
     283  template <typename GR>
    252284  struct UndirectedTagIndicator<
    253     Graph,
    254     typename enable_if<typename Graph::UndirectedTag, void>::type
    255   > {
    256     static const bool value = true;
    257   };
    258 
    259   template <typename Graph, typename Enable = void>
     285    GR,
     286    typename enable_if<typename GR::UndirectedTag, void>::type
     287  > {
     288    static const bool value = true;
     289  };
     290
     291  template <typename GR, typename Enable = void>
    260292  struct BuildTagIndicator {
    261293    static const bool value = false;
    262294  };
    263295
    264   template <typename Graph>
     296  template <typename GR>
    265297  struct BuildTagIndicator<
    266     Graph,
    267     typename enable_if<typename Graph::BuildTag, void>::type
     298    GR,
     299    typename enable_if<typename GR::BuildTag, void>::type
    268300  > {
    269301    static const bool value = true;
  • lemon/bits/vector_map.h

    r314 r617  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure what
    42   // automatically updates the map when a key is added to or erased from
    43   // the map. This map type uses the std::vector to store the values.
     41  // The VectorMap template class is graph map structure that automatically
     42  // updates the map when a key is added to or erased from the graph.
     43  // This map type uses std::vector to store the values.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
     
    5757
    5858    // The graph type of the map.
    59     typedef _Graph Graph;
     59    typedef _Graph GraphType;
    6060    // The item type of the map.
    6161    typedef _Item Item;
     
    7373    // The map type.
    7474    typedef VectorMap Map;
    75     // The base class of the map.
    76     typedef typename Notifier::ObserverBase Parent;
    7775
    7876    // The reference type of the map;
     
    8179    typedef typename Container::const_reference ConstReference;
    8280
     81  private:
     82
     83    // The base class of the map.
     84    typedef typename Notifier::ObserverBase Parent;
     85
     86  public:
    8387
    8488    // \brief Constructor to attach the new map into the notifier.
     
    8690    // It constructs a map and attachs it into the notifier.
    8791    // It adds all the items of the graph to the map.
    88     VectorMap(const Graph& graph) {
     92    VectorMap(const GraphType& graph) {
    8993      Parent::attach(graph.notifier(Item()));
    9094      container.resize(Parent::notifier()->maxId() + 1);
     
    9599    // It constructs a map uses a given value to initialize the map.
    96100    // It adds all the items of the graph to the map.
    97     VectorMap(const Graph& graph, const Value& value) {
     101    VectorMap(const GraphType& graph, const Value& value) {
    98102      Parent::attach(graph.notifier(Item()));
    99103      container.resize(Parent::notifier()->maxId() + 1, value);
     
    125129    // \brief Template assign operator.
    126130    //
    127     // The given parameter should be conform to the ReadMap
     131    // The given parameter should conform to the ReadMap
    128132    // concecpt and could be indiced by the current item set of
    129133    // the NodeMap. In this case the value for each item
     
    170174    // \brief Adds a new key to the map.
    171175    //
    172     // It adds a new key to the map. It called by the observer notifier
     176    // It adds a new key to the map. It is called by the observer notifier
    173177    // and it overrides the add() member function of the observer base.
    174178    virtual void add(const Key& key) {
     
    181185    // \brief Adds more new keys to the map.
    182186    //
    183     // It adds more new keys to the map. It called by the observer notifier
     187    // It adds more new keys to the map. It is called by the observer notifier
    184188    // and it overrides the add() member function of the observer base.
    185189    virtual void add(const std::vector<Key>& keys) {
     
    196200    // \brief Erase a key from the map.
    197201    //
    198     // Erase a key from the map. It called by the observer notifier
     202    // Erase a key from the map. It is called by the observer notifier
    199203    // and it overrides the erase() member function of the observer base.
    200204    virtual void erase(const Key& key) {
     
    204208    // \brief Erase more keys from the map.
    205209    //
    206     // Erase more keys from the map. It called by the observer notifier
     210    // It erases more keys from the map. It is called by the observer notifier
    207211    // and it overrides the erase() member function of the observer base.
    208212    virtual void erase(const std::vector<Key>& keys) {
     
    212216    }
    213217
    214     // \brief Buildes the map.
    215     //
    216     // It buildes the map. It called by the observer notifier
     218    // \brief Build the map.
     219    //
     220    // It builds the map. It is called by the observer notifier
    217221    // and it overrides the build() member function of the observer base.
    218222    virtual void build() {
     
    224228    // \brief Clear the map.
    225229    //
    226     // It erase all items from the map. It called by the observer notifier
     230    // It erases all items from the map. It is called by the observer notifier
    227231    // and it overrides the clear() member function of the observer base.
    228232    virtual void clear() {
  • lemon/bits/windows.cc

    r493 r877  
    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).
     
    9797      GetSystemTime(&time);
    9898      char buf1[11], buf2[9], buf3[5];
    99           if (GetDateFormat(MY_LOCALE, 0, &time,
     99          if (GetDateFormat(MY_LOCALE, 0, &time,
    100100                        ("ddd MMM dd"), buf1, 11) &&
    101101          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/bits/windows.h

    r491 r529  
    1717 */
    1818
    19 #ifndef LEMON_WINDOWS_H
    20 #define LEMON_WINDOWS_H
     19#ifndef LEMON_BITS_WINDOWS_H
     20#define LEMON_BITS_WINDOWS_H
    2121
    2222#include <string>
  • lemon/color.cc

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

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

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

    r263 r877  
    33 * 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).
     
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
     
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
     
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    104         /// To allow the use of digraph descriptors as key type in std::map or
    105         /// similar associative container we require this.
    106         ///
    107         /// \note This operator only have to define some strict ordering of
    108         /// the items; this order has nothing to do with the iteration
    109         /// ordering of the items.
     99        /// Artificial ordering operator.
     100        ///
     101        /// \note This operator only has to define some strict ordering of
     102        /// the nodes; this order has nothing to do with the iteration
     103        /// ordering of the nodes.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
    117       /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
     110      /// Its usage is quite simple, for example, you can count the number
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
     
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
     
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    142         /// Sets the iterator to the first node of \c g.
    143         ///
    144         NodeIt(const Digraph&) { }
    145         /// Node -> NodeIt conversion.
    146 
    147         /// Sets the iterator to the node of \c the digraph pointed by
    148         /// the trivial iterator.
    149         /// This feature necessitates that each time we
    150         /// iterate the arc-set, the iteration order is the same.
     135        /// Sets the iterator to the first node of the given digraph.
     136        ///
     137        explicit NodeIt(const Digraph&) { }
     138        /// Sets the iterator to the given node.
     139
     140        /// Sets the iterator to the given node of the given digraph.
     141        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
     
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
     
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
     
    175166        ///
    176167