COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 added
107 deleted
110 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r944 r514  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 doc/references.dox
    26 cmake/version.cmake
     25cmake/cmake.version
    2726.dirstamp
    2827.libs/*
    2928.deps/*
    3029demo/*.eps
    31 m4/libtool.m4
    32 m4/ltoptions.m4
    33 m4/ltsugar.m4
    34 m4/ltversion.m4
    35 m4/lt~obsolete.m4
    3630
    3731syntax: regexp
     
    4236^autom4te.cache/.*
    4337^build-aux/.*
    44 ^.*objs.*/.*
     38^objs.*/.*
    4539^test/[a-z_]*$
    46 ^tools/[a-z-_]*$
    4740^demo/.*_demo$
    48 ^.*build.*/.*
     41^build/.*
    4942^doc/gen-images/.*
    5043CMakeFiles
  • CMakeLists.txt

    r1056 r540  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    3 SET(PROJECT_NAME "LEMON")
     3IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     4  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     5ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     6  SET(PROJECT_NAME "LEMON")
     7  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
     8ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     9
    410PROJECT(${PROJECT_NAME})
    511
    6 INCLUDE(FindPythonInterp)
    7 INCLUDE(FindWget)
     12SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
    813
    9 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    10   INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    11 ELSEIF(DEFINED ENV{LEMON_VERSION})
    12   SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
    13 ELSE()
    14   EXECUTE_PROCESS(
    15     COMMAND ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
    16     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    17     OUTPUT_VARIABLE HG_REVISION_PATH
    18     ERROR_QUIET
    19     OUTPUT_STRIP_TRAILING_WHITESPACE
    20   )
    21   EXECUTE_PROCESS(
    22     COMMAND hg id -i
    23     WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
    24     OUTPUT_VARIABLE HG_REVISION
    25     ERROR_QUIET
    26     OUTPUT_STRIP_TRAILING_WHITESPACE
    27   )
    28   IF(HG_REVISION STREQUAL "")
    29     SET(HG_REVISION_ID "hg-tip")
    30   ELSE()
    31     IF(HG_REVISION_PATH STREQUAL "")
    32       SET(HG_REVISION_ID ${HG_REVISION})
    33     ELSE()
    34       SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
    35     ENDIF()
    36   ENDIF()
    37   SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
    38 ENDIF()
     14INCLUDE(FindDoxygen)
     15INCLUDE(FindGhostscript)
    3916
    40 SET(PROJECT_VERSION ${LEMON_VERSION})
    41 
    42 SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    43 
    44 FIND_PACKAGE(Doxygen)
    45 FIND_PACKAGE(Ghostscript)
    46 FIND_PACKAGE(GLPK 4.33)
    47 FIND_PACKAGE(CPLEX)
    48 FIND_PACKAGE(COIN)
    49 
    50 IF(DEFINED ENV{LEMON_CXX_WARNING})
    51   SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
    52 ELSE()
    53   IF(CMAKE_COMPILER_IS_GNUCXX)
    54     SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
    55     SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
    56     SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
    57   ELSEIF(MSVC)
    58     # This part is unnecessary 'casue the same is set by the lemon/core.h.
    59     # Still keep it as an example.
    60     SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
    61     # Suppressed warnings:
    62     # C4250: 'class1' : inherits 'class2::member' via dominance
    63     # C4355: 'this' : used in base member initializer list
    64     # C4503: 'function' : decorated name length exceeded, name was truncated
    65     # C4800: 'type' : forcing value to bool 'true' or 'false'
    66     #        (performance warning)
    67     # C4996: 'function': was declared deprecated
    68   ELSE()
    69     SET(CXX_WARNING "-Wall -W")
    70   ENDIF()
    71 ENDIF()
    72 SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
    73 
    74 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    75 
    76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
    77     "Flags used by the C++ compiler during maintainer builds."
    78     FORCE )
    79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
    80     "Flags used by the C compiler during maintainer builds."
    81     FORCE )
    82 SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    83     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    84     "Flags used for linking binaries during maintainer builds."
    85     FORCE )
    86 SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
    87     "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
    88     "Flags used by the shared libraries linker during maintainer builds."
    89     FORCE )
    90 MARK_AS_ADVANCED(
    91     CMAKE_CXX_FLAGS_MAINTAINER
    92     CMAKE_C_FLAGS_MAINTAINER
    93     CMAKE_EXE_LINKER_FLAGS_MAINTAINER
    94     CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
    95 
    96 IF(CMAKE_CONFIGURATION_TYPES)
    97   LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
    98   LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
    99   SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
    100       "Add the configurations that we need"
    101       FORCE)
    102  endif()
    103 
    104 IF(NOT CMAKE_BUILD_TYPE)
    105   SET(CMAKE_BUILD_TYPE "Release")
    106 ENDIF()
    107 
    108 SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
    109     "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
    110     FORCE )
    111 
     17ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    11218
    11319INCLUDE(CheckTypeSize)
    114 CHECK_TYPE_SIZE("long long" LONG_LONG)
    115 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     20CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
    11621
    11722ENABLE_TESTING()
    11823
    119 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
    120   ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
    121 ELSE()
    122   ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
    123 ENDIF()
     24ADD_SUBDIRECTORY(lemon)
     25ADD_SUBDIRECTORY(demo)
     26ADD_SUBDIRECTORY(doc)
     27ADD_SUBDIRECTORY(test)
    12428
    125 ADD_SUBDIRECTORY(lemon)
    126 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    127   ADD_SUBDIRECTORY(contrib)
    128   ADD_SUBDIRECTORY(demo)
    129   ADD_SUBDIRECTORY(tools)
    130   ADD_SUBDIRECTORY(doc)
    131   ADD_SUBDIRECTORY(test)
    132 ENDIF()
    133 
    134 CONFIGURE_FILE(
    135   ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
    136   ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    137   @ONLY
    138 )
    139 IF(UNIX)
    140   INSTALL(
    141     FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    142     DESTINATION share/lemon/cmake
    143   )
    144 ELSEIF(WIN32)
    145   INSTALL(
    146     FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    147     DESTINATION cmake
    148   )
    149 ENDIF()
    150 
    151 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     29IF(WIN32)
    15230  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    15331  SET(CPACK_PACKAGE_VENDOR "EGRES")
    15432  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    155     "LEMON - Library for Efficient Modeling and Optimization in Networks")
    156   SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
     33    "LEMON - Library of Efficient Models and Optimization in Networks")
     34  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
    15735
    15836  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    16341    "${PROJECT_NAME} ${PROJECT_VERSION}")
    16442
    165   SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     43  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
    16644
    16745  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    16846  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    169   SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    17047  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    17148
     
    17451  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    17552    "DLL and import library")
    176   SET(CPACK_COMPONENT_BIN_DESCRIPTION
    177     "Command line utilities")
    17853  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    17954    "Doxygen generated documentation")
     
    19772
    19873  SET(CPACK_GENERATOR "NSIS")
    199   SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
    200   SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    201   #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     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")
    20277  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    20378  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    21489
    21590  INCLUDE(CPack)
    216 ENDIF()
     91ENDIF(WIN32)
  • INSTALL

    r890 r526  
    2828
    2929      This command compiles the non-template part of LEMON into libemon.a
    30       file. It also compiles the programs in the tools subdirectory by
    31       default.
     30      file. It also compiles the programs in the tools and demo subdirectories
     31      when enabled.
    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).
    7785
    7886--enable-tools
     
    151159
    152160   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 
    178 Makefile Variables
    179 ==================
    180 
    181 Some Makefile variables are reserved by the GNU Coding Standards for
    182 the use of the "user" - the person building the package. For instance,
    183 CXX and CXXFLAGS are such variables, and have the same meaning as
    184 explained in the previous section. These variables can be set on the
    185 command line when invoking `make' like this:
    186 `make [VARIABLE=VALUE]...'
    187 
    188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
    189 to hold several compiler flags related to warnings. Its default value
    190 can be overridden when invoking `make'. For example to disable all
    191 warning flags use `make WARNINGCXXFLAGS='.
    192 
    193 In order to turn off a single flag from the default set of warning
    194 flags, you can use the CXXFLAGS variable, since this is passed after
    195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
    196 used by default when g++ is detected) you can use
    197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.
  • LICENSE

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

    r840 r503  
    11ACLOCAL_AMFLAGS = -I m4
    2 
    3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    53AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     
    1210        m4/lx_check_glpk.m4 \
    1311        m4/lx_check_soplex.m4 \
    14         m4/lx_check_coin.m4 \
    1512        CMakeLists.txt \
    1613        cmake/FindGhostscript.cmake \
    17         cmake/FindCPLEX.cmake \
    18         cmake/FindGLPK.cmake \
    19         cmake/FindCOIN.cmake \
    20         cmake/LEMONConfig.cmake.in \
    2114        cmake/version.cmake.in \
    2215        cmake/version.cmake \
     
    4437include test/Makefile.am
    4538include doc/Makefile.am
     39include demo/Makefile.am
    4640include tools/Makefile.am
    47 include scripts/Makefile.am
    48 
    49 DIST_SUBDIRS = demo
    50 
    51 demo:
    52         $(MAKE) $(AM_MAKEFLAGS) -C demo
    5341
    5442MRPROPERFILES = \
     
    7866        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    7967
    80 .PHONY: demo mrproper dist-bz2 distcheck-bz2
     68.PHONY: mrproper dist-bz2 distcheck-bz2
  • NEWS

    r962 r534  
    1 2010-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 
    81 2009-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 
    16812009-03-27 LEMON joins to the COIN-OR initiative
    1692
     
    17582008-10-13 Version 1.0 released
    1769
    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.
     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.
    18114
    182         * The major name changes compared to the 0.x series (see the
     15        * The major name changes compared to the 0.x series (see the
    18316          Migration Guide in the doc for more details)
    18417          * Graph -> Digraph, UGraph -> Graph
    18518          * Edge -> Arc, UEdge -> Edge
    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)
     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)
    20437          * Concepts
    205             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     38            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
    20639              concepts/graph_components.h)
    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
     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
    21649              (lgf_reader.h, lgf_writer.h)
    21750            * tools to handle the anomalies of calculations with
    218               floating point numbers (tolerance.h)
     51              floating point numbers (tolerance.h)
    21952            * tools to manage RGB colors (color.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)
     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)
  • README

    r921 r318  
    1 =====================================================================
    2 LEMON - a Library for Efficient Modeling and Optimization in Networks
    3 =====================================================================
     1==================================================================
     2LEMON - a Library of Efficient Models 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 
    20 NEWS
    21 
    22    News and version history.
    2319
    2420INSTALL
     
    3834   Some example programs to make you easier to get familiar with LEMON.
    3935
    40 scripts/
    41 
    42    Scripts that make it easier to develop LEMON.
    43 
    4436test/
    4537
  • cmake/version.cmake.in

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

    r1039 r540  
    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 2> /dev/null]))])
     8m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
    99m4_define([lemon_version], [ifelse(lemon_version_number(),
    10                            [],
    11                            [ifelse(lemon_hg_revision(),
    12                            [],
    13                            [hg-tip],
    14                            [lemon_hg_path().lemon_hg_revision()])],
    15                            [lemon_version_number()])])
     10                           [],
     11                           [lemon_hg_path().lemon_hg_revision()],
     12                           [lemon_version_number()])])
    1613
    1714AC_PREREQ([2.59])
     
    2320AC_CONFIG_HEADERS([config.h lemon/config.h])
    2421
    25 AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
     22lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2623
    2724dnl Do compilation tests using the C++ compiler.
     
    4239
    4340AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    44 AC_CHECK_PROG([python_found],[python],[yes],[no])
    4541AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4642
     
    5753
    5854dnl Set custom compiler flags when using g++.
    59 if 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"
     55if 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"
    6157fi
    62 AC_SUBST([WARNINGCXXFLAGS])
    6358
    6459dnl Checks for libraries.
    65 LX_CHECK_GLPK
    66 LX_CHECK_CPLEX
    67 LX_CHECK_SOPLEX
    68 LX_CHECK_COIN
     60#LX_CHECK_GLPK
     61#LX_CHECK_CPLEX
     62#LX_CHECK_SOPLEX
    6963
    70 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    71 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     64dnl Disable/enable building the demo programs.
     65AC_ARG_ENABLE([demo],
     66AS_HELP_STRING([--enable-demo], [build the demo programs])
     67AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
     68              [], [enable_demo=no])
     69AC_MSG_CHECKING([whether to build the demo programs])
     70if test x"$enable_demo" != x"no"; then
     71  AC_MSG_RESULT([yes])
     72else
     73  AC_MSG_RESULT([no])
     74fi
     75AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    7276
    7377dnl Disable/enable building the binary tools.
     
    8387fi
    8488AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
    85 
    86 dnl Support for running test cases using valgrind.
    87 use_valgrind=no
    88 AC_ARG_ENABLE([valgrind],
    89 AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
    90               [use_valgrind=yes])
    91 
    92 if [[ "$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
    98 fi
    99 AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    10089
    10190dnl Checks for header files.
     
    115104dnl Add dependencies on files generated by configure.
    116105AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    117   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     106  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    118107
    119108AC_CONFIG_FILES([
    120109Makefile
    121 demo/Makefile
    122110cmake/version.cmake
    123111doc/Doxyfile
    124 doc/mainpage.dox
    125112lemon/lemon.pc
    126113])
     
    134121echo
    135122echo C++ compiler.................. : $CXX
    136 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     123echo C++ compiles flags............ : $CXXFLAGS
    137124echo
    138125echo Compiler supports long long... : $long_long_found
    139126echo
    140 echo GLPK support.................. : $lx_glpk_found
    141 echo CPLEX support................. : $lx_cplex_found
    142 echo SOPLEX support................ : $lx_soplex_found
    143 echo CLP support................... : $lx_clp_found
    144 echo CBC support................... : $lx_cbc_found
    145 echo
     127#echo GLPK support.................. : $lx_glpk_found
     128#echo CPLEX support................. : $lx_cplex_found
     129#echo SOPLEX support................ : $lx_soplex_found
     130#echo
     131echo Build demo programs........... : $enable_demo
    146132echo Build additional tools........ : $enable_tools
    147 echo Use valgrind for tests........ : $use_valgrind
    148133echo
    149134echo The packace will be installed in
  • demo/CMakeLists.txt

    r726 r539  
    11INCLUDE_DIRECTORIES(
    2   ${PROJECT_SOURCE_DIR}
     2  ${CMAKE_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(
    7   ${PROJECT_BINARY_DIR}/lemon
    8 )
     6LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
    97
    108SET(DEMOS
    119  arg_parser_demo
    1210  graph_to_eps_demo
    13   lgf_demo
    14 )
     11  lgf_demo)
    1512
    1613FOREACH(DEMO_NAME ${DEMOS})
    1714  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
    1815  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
    19 ENDFOREACH()
     16ENDFOREACH(DEMO_NAME)
  • demo/Makefile.am

    r611 r164  
    1 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
     1EXTRA_DIST += \
     2        demo/CMakeLists.txt \
     3        demo/digraph.lgf
    24
    3 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
    4 LDADD = $(top_builddir)/lemon/libemon.la
     5if WANT_DEMO
    56
    6 EXTRA_DIST = \
    7         CMakeLists.txt \
    8         digraph.lgf
     7noinst_PROGRAMS += \
     8        demo/arg_parser_demo \
     9        demo/graph_to_eps_demo \
     10        demo/lgf_demo
    911
    10 noinst_PROGRAMS = \
    11         arg_parser_demo \
    12         graph_to_eps_demo \
    13         lgf_demo
     12endif WANT_DEMO
    1413
    15 arg_parser_demo_SOURCES = arg_parser_demo.cc
    16 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
    17 lgf_demo_SOURCES = lgf_demo.cc
     14demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
     15demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
     16demo_lgf_demo_SOURCES = demo/lgf_demo.cc
  • demo/arg_parser_demo.cc

    r956 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    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 
    7368  // Perform the parsing process
    7469  // (in case of any error it terminates the program)
    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; }
     70  ap.parse();
    8071
    8172  // Check each option if it has been given and print its value
  • demo/graph_to_eps_demo.cc

    r659 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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-2009 LEMON Project").
     88    copyright("(C) 2003-2008 LEMON Project").
    8989    run();
    9090
     
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2009 LEMON Project").
     95    copyright("(C) 2003-2008 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-2009 LEMON Project").
     108    copyright("(C) 2003-2008 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-2009 LEMON Project").
     135    copyright("(C) 2003-2008 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-2009 LEMON Project").
     150    copyright("(C) 2003-2008 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-2009 LEMON Project").
     166    copyright("(C) 2003-2008 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
     
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(std::sqrt(double(palette.size())));
     185  int cols=int(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-2009 LEMON Project").
     196    copyright("(C) 2003-2008 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().
  • demo/lgf_demo.cc

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

    r1040 r520  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
    4 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    5 
    6 SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
     3SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
     4SET(abs_top_builddir ${CMAKE_BINARY_DIR})
    75
    86CONFIGURE_FILE(
    9   ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    10   ${PROJECT_BINARY_DIR}/doc/Doxyfile
    11   @ONLY
    12 )
     7  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
     8  ${CMAKE_BINARY_DIR}/doc/Doxyfile
     9  @ONLY)
    1310
    14 CONFIGURE_FILE(
    15   ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
    16   ${PROJECT_BINARY_DIR}/doc/mainpage.dox
    17   @ONLY
    18 )
    19 
    20 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
     11IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    2112  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    22   SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
    23   ADD_CUSTOM_TARGET(html
    24     COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
    25     COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
    26     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
    27     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
    28     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
    29     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
    30     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    31     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
    32     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
    33     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    34     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
    35     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
    36     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    37     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
    38     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
    39     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    40     COMMAND ${CMAKE_COMMAND} -E remove_directory html
    41     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    42     COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    43     WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    44   )
    45 
    46   SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
    47 
    4813  IF(UNIX)
    49     INSTALL(
    50       DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    51       DESTINATION share/doc/lemon/html
    52       COMPONENT html_documentation
    53     )
     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})
    5425  ELSEIF(WIN32)
    55     INSTALL(
    56       DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    57       DESTINATION doc
    58       COMPONENT html_documentation
    59     )
    60   ENDIF()
    61 
    62 ENDIF()
    63 
    64 IF(WGET_FOUND)
    65 ADD_CUSTOM_TARGET(update-external-tags
    66   COMMAND ${CMAKE_COMMAND} -E make_directory dl
    67   # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
    68   COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
    69   COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
    70   COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
    71   COMMAND ${CMAKE_COMMAND} -E remove_directory dl
    72   WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
    73   )
    74 ENDIF()
     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)
     42ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
  • doc/Doxyfile.in

    r1040 r316  
    1 # Doxyfile 1.7.3
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
     
    55#---------------------------------------------------------------------------
    66DOXYFILE_ENCODING      = UTF-8
    7 PROJECT_NAME           =
    8 PROJECT_NUMBER         =
    9 PROJECT_BRIEF          =
    10 PROJECT_LOGO           =
     7PROJECT_NAME           = @PACKAGE_NAME@
     8PROJECT_NUMBER         = @PACKAGE_VERSION@
    119OUTPUT_DIRECTORY       =
    1210CREATE_SUBDIRS         = NO
     
    2422QT_AUTOBRIEF           = NO
    2523MULTILINE_CPP_IS_BRIEF = NO
     24DETAILS_AT_TOP         = YES
    2625INHERIT_DOCS           = NO
    2726SEPARATE_MEMBER_PAGES  = NO
     
    3231OPTIMIZE_FOR_FORTRAN   = NO
    3332OPTIMIZE_OUTPUT_VHDL   = NO
    34 EXTENSION_MAPPING      =
    3533BUILTIN_STL_SUPPORT    = YES
    3634CPP_CLI_SUPPORT        = NO
     
    5856HIDE_SCOPE_NAMES       = YES
    5957SHOW_INCLUDE_FILES     = YES
    60 FORCE_LOCAL_INCLUDES   = NO
    6158INLINE_INFO            = YES
    6259SORT_MEMBER_DOCS       = NO
    6360SORT_BRIEF_DOCS        = NO
    64 SORT_MEMBERS_CTORS_1ST = NO
    6561SORT_GROUP_NAMES       = NO
    6662SORT_BY_SCOPE_NAME     = NO
    67 STRICT_PROTO_MATCHING  = NO
    6863GENERATE_TODOLIST      = YES
    6964GENERATE_TESTLIST      = YES
     
    7267ENABLED_SECTIONS       =
    7368MAX_INITIALIZER_LINES  = 5
    74 SHOW_USED_FILES        = NO
     69SHOW_USED_FILES        = YES
    7570SHOW_DIRECTORIES       = YES
    7671SHOW_FILES             = YES
    7772SHOW_NAMESPACES        = YES
    7873FILE_VERSION_FILTER    =
    79 LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
     74LAYOUT_FILE            = DoxygenLayout.xml
    8075#---------------------------------------------------------------------------
    8176# configuration options related to warning and progress messages
     
    9691                         "@abs_top_srcdir@/lemon/concepts" \
    9792                         "@abs_top_srcdir@/demo" \
    98                          "@abs_top_srcdir@/contrib" \
    9993                         "@abs_top_srcdir@/tools" \
    100                          "@abs_top_srcdir@/test/test_tools.h" \
    101                          "@abs_top_builddir@/doc/mainpage.dox" \
    102                          "@abs_top_builddir@/doc/references.dox"
     94                         "@abs_top_srcdir@/test/test_tools.h"
    10395INPUT_ENCODING         = UTF-8
    10496FILE_PATTERNS          = *.h \
     
    120112FILTER_PATTERNS        =
    121113FILTER_SOURCE_FILES    = NO
    122 FILTER_SOURCE_PATTERNS =
    123114#---------------------------------------------------------------------------
    124115# configuration options related to source browsing
    125116#---------------------------------------------------------------------------
    126 SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
     117SOURCE_BROWSER         = NO
    127118INLINE_SOURCES         = NO
    128119STRIP_CODE_COMMENTS    = YES
     
    147138HTML_FOOTER            =
    148139HTML_STYLESHEET        =
    149 HTML_COLORSTYLE_HUE    = 220
    150 HTML_COLORSTYLE_SAT    = 100
    151 HTML_COLORSTYLE_GAMMA  = 80
    152 HTML_TIMESTAMP         = YES
    153140HTML_ALIGN_MEMBERS     = YES
    154 HTML_DYNAMIC_SECTIONS  = YES
     141HTML_DYNAMIC_SECTIONS  = NO
    155142GENERATE_DOCSET        = NO
    156143DOCSET_FEEDNAME        = "Doxygen generated docs"
    157144DOCSET_BUNDLE_ID       = org.doxygen.Project
    158 DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
    159 DOCSET_PUBLISHER_NAME  = Publisher
    160145GENERATE_HTMLHELP      = NO
    161146CHM_FILE               =
     
    169154QHP_NAMESPACE          = org.doxygen.Project
    170155QHP_VIRTUAL_FOLDER     = doc
    171 QHP_CUST_FILTER_NAME   =
    172 QHP_CUST_FILTER_ATTRS  =
    173 QHP_SECT_FILTER_ATTRS  =
    174156QHG_LOCATION           =
    175 GENERATE_ECLIPSEHELP   = NO
    176 ECLIPSE_DOC_ID         = org.doxygen.Project
    177157DISABLE_INDEX          = NO
    178158ENUM_VALUES_PER_LINE   = 4
    179159GENERATE_TREEVIEW      = NO
    180 USE_INLINE_TREES       = NO
    181160TREEVIEW_WIDTH         = 250
    182 EXT_LINKS_IN_WINDOW    = NO
    183161FORMULA_FONTSIZE       = 10
    184 FORMULA_TRANSPARENT    = YES
    185 USE_MATHJAX            = NO
    186 MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
    187 SEARCHENGINE           = YES
    188 SERVER_BASED_SEARCH    = NO
    189162#---------------------------------------------------------------------------
    190163# configuration options related to the LaTeX output
     
    203176LATEX_BATCHMODE        = NO
    204177LATEX_HIDE_INDICES     = NO
    205 LATEX_SOURCE_CODE      = NO
    206178#---------------------------------------------------------------------------
    207179# configuration options related to the RTF output
     
    252224SKIP_FUNCTION_MACROS   = YES
    253225#---------------------------------------------------------------------------
    254 # Configuration::additions related to external references
    255 #---------------------------------------------------------------------------
    256 TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     226# Configuration::additions related to external references   
     227#---------------------------------------------------------------------------
     228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    257229GENERATE_TAGFILE       = html/lemon.tag
    258230ALLEXTERNALS           = NO
     
    266238HIDE_UNDOC_RELATIONS   = YES
    267239HAVE_DOT               = YES
    268 DOT_NUM_THREADS        = 0
    269240DOT_FONTNAME           = FreeSans
    270241DOT_FONTSIZE           = 10
     
    284255DOT_PATH               =
    285256DOTFILE_DIRS           =
    286 MSCFILE_DIRS           =
    287257DOT_GRAPH_MAX_NODES    = 50
    288258MAX_DOT_GRAPH_DEPTH    = 0
     
    291261GENERATE_LEGEND        = YES
    292262DOT_CLEANUP            = YES
     263#---------------------------------------------------------------------------
     264# Configuration::additions related to the search engine   
     265#---------------------------------------------------------------------------
     266SEARCHENGINE           = NO
  • doc/DoxygenLayout.xml

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

    r943 r317  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
    11         doc/min_cost_flow.dox \
    1211        doc/named-param.dox \
    1312        doc/namespaces.dox \
     
    1615
    1716DOC_EPS_IMAGES18 = \
    18         grid_graph.eps \
    1917        nodeshape_0.eps \
    2018        nodeshape_1.eps \
     
    2321        nodeshape_4.eps
    2422
    25 DOC_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 
    3523DOC_EPS_IMAGES = \
    36         $(DOC_EPS_IMAGES18) \
    37         $(DOC_EPS_IMAGES27)
     24        $(DOC_EPS_IMAGES18)
    3825
    3926DOC_PNG_IMAGES = \
     
    5845        fi
    5946
    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 
    71 references.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 
    83 html-local: $(DOC_PNG_IMAGES) references.dox
     47html-local: $(DOC_PNG_IMAGES)
    8448        if test ${doxygen_found} = yes; then \
    8549          cd doc; \
     
    10670install-html-local: doc/html
    10771        @$(NORMAL_INSTALL)
    108         $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
     72        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
    10973        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    11074          f="`echo $$p | sed -e 's|^.*/||'`"; \
    111           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
    112           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
     75          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
     76          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
    11377        done
    11478
     
    11781        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    11882          f="`echo $$p | sed -e 's|^.*/||'`"; \
    119           echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
    120           rm -f $(DESTDIR)$(htmldir)/html/$$f; \
     83          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
     84          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
    12185        done
    12286
  • doc/coding_style.dox

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

    r1031 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3232documentation.
    3333*/
    34 
    35 /**
    36 \dir contrib
    37 \brief Directory for user contributed source codes.
    38 
    39 You can place your own C++ code using LEMON into this directory, which
    40 will compile to an executable along with LEMON when you build the
    41 library. This is probably the easiest way of compiling short to medium
    42 codes, for this does require neither a LEMON installed system-wide nor
    43 adding several paths to the compiler.
    44 
    45 Please have a look at <tt>contrib/CMakeLists.txt</tt> for
    46 instruction on how to add your own files into the build process.  */
    4734
    4835/**
     
    8572\brief Auxiliary tools for implementation.
    8673
    87 This directory contains some auxiliary classes for implementing graphs,
     74This directory contains some auxiliary classes for implementing graphs, 
    8875maps and some other classes.
    8976As a user you typically don't have to deal with these files.
  • doc/groups.dox

    r1023 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    23 This group contains the several data structures implemented in LEMON.
     21This group describes the several data structures implemented in LEMON.
    2422*/
    2523
     
    6361
    6462/**
    65 @defgroup graph_adaptors Adaptor Classes for Graphs
     63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    6664@ingroup graphs
    67 \brief Adaptor classes for digraphs and graphs
    68 
    69 This group contains several useful adaptor classes for digraphs and graphs.
    70 
    71 The main parts of LEMON are the different graph structures, generic
    72 graph algorithms, graph concepts, which couple them, and graph
    73 adaptors. While the previous notions are more or less clear, the
    74 latter one needs further explanation. Graph adaptors are graph classes
    75 which serve for considering graph structures in different ways.
    76 
    77 A short example makes this much clearer.  Suppose that we have an
    78 instance \c g of a directed graph type, say ListDigraph and an algorithm
    79 \code
    80 template <typename Digraph>
    81 int algorithm(const Digraph&);
    82 \endcode
    83 is 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
    85 arcs.  In this case, an adaptor class is used, which (according
    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    87 The adaptor uses the original digraph structure and digraph operations when
    88 methods of the reversed oriented graph are called.  This means that the adaptor
    89 have minor memory usage, and do not perform sophisticated algorithmic
    90 actions.  The purpose of it is to give a tool for the cases when a
    91 graph have to be used in a specific alteration.  If this alteration is
    92 obtained by a usual construction like filtering the node or the arc set or
    93 considering a new orientation, then an adaptor is worthwhile to use.
    94 To come back to the reverse oriented graph, in this situation
    95 \code
    96 template<typename Digraph> class ReverseDigraph;
    97 \endcode
    98 template class can be used. The code looks as follows
    99 \code
    100 ListDigraph g;
    101 ReverseDigraph<ListDigraph> rg(g);
    102 int result = algorithm(rg);
    103 \endcode
    104 During running the algorithm, the original digraph \c g is untouched.
    105 This techniques give rise to an elegant code, and based on stable
    106 graph adaptors, complex algorithms can be implemented easily.
    107 
    108 In flow, circulation and matching problems, the residual
    109 graph is of particular importance. Combining an adaptor implementing
    110 this with shortest path algorithms or minimum mean cycle algorithms,
    111 a range of weighted and cardinality optimization algorithms can be
    112 obtained. For other examples, the interested user is referred to the
    113 detailed documentation of particular adaptors.
    114 
    115 The behavior of graph adaptors can be very different. Some of them keep
    116 capabilities of the original graph while in other cases this would be
    117 meaningless. This means that the concepts that they meet depend
    118 on the graph adaptor, and the wrapped graph.
    119 For example, if an arc of a reversed digraph is deleted, this is carried
    120 out by deleting the corresponding arc of the original digraph, thus the
    121 adaptor modifies the original digraph.
    122 However in case of a residual digraph, this operation has no sense.
    123 
    124 Let us stand one more example here to simplify your work.
    125 ReverseDigraph has constructor
    126 \code
    127 ReverseDigraph(Digraph& digraph);
    128 \endcode
    129 This means that in a situation, when a <tt>const %ListDigraph&</tt>
    130 reference to a graph is given, then it have to be instantiated with
    131 <tt>Digraph=const %ListDigraph</tt>.
    132 \code
    133 int algorithm1(const ListDigraph& g) {
    134   ReverseDigraph<const ListDigraph> rg(g);
    135   return algorithm2(rg);
    136 }
    137 \endcode
     65\brief Graph types between real graphs and graph adaptors.
     66
     67This group describes some graph types between real graphs and graph adaptors.
     68These classes wrap graphs to give new functionality as the adaptors do it.
     69On the other hand they are not light-weight structures as the adaptors.
    13870*/
    13971
     
    14375\brief Map structures implemented in LEMON.
    14476
    145 This group contains the map structures implemented in LEMON.
     77This group describes the map structures implemented in LEMON.
    14678
    14779LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    15688\brief Special graph-related maps.
    15789
    158 This group contains maps that are specifically designed to assign
    159 values to the nodes and arcs/edges of graphs.
    160 
    161 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    162 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     90This group describes maps that are specifically designed to assign
     91values to the nodes and arcs of graphs.
    16392*/
    16493
     
    16897\brief Tools to create new maps from existing ones
    16998
    170 This group contains map adaptors that are used to create "implicit"
     99This group describes map adaptors that are used to create "implicit"
    171100maps from other maps.
    172101
    173 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    174103They can make arithmetic and logical operations between one or two maps
    175104(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    227156
    228157/**
     158@defgroup matrices Matrices
     159@ingroup datas
     160\brief Two dimensional data storages implemented in LEMON.
     161
     162This group describes two dimensional data storages implemented in LEMON.
     163*/
     164
     165/**
    229166@defgroup paths Path Structures
    230167@ingroup datas
    231168\brief %Path structures implemented in LEMON.
    232169
    233 This group contains the path structures implemented in LEMON.
     170This group describes the path structures implemented in LEMON.
    234171
    235172LEMON provides flexible data structures to work with paths.
     
    239176any kind of path structure.
    240177
    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 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
     178\sa lemon::concepts::Path
    263179*/
    264180
     
    268184\brief Auxiliary data structures implemented in LEMON.
    269185
    270 This group contains some data structures implemented in LEMON in
     186This group describes some data structures implemented in LEMON in
    271187order to make it easier to implement combinatorial algorithms.
    272188*/
    273189
    274190/**
    275 @defgroup geomdat Geometric Data Structures
    276 @ingroup auxdat
    277 \brief Geometric data structures implemented in LEMON.
    278 
    279 This 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 
    293 This group contains two dimensional data storages implemented in LEMON.
    294 */
    295 
    296 /**
    297191@defgroup algs Algorithms
    298 \brief This group contains the several algorithms
     192\brief This group describes the several algorithms
    299193implemented in LEMON.
    300194
    301 This group contains the several algorithms
     195This group describes the several algorithms
    302196implemented in LEMON.
    303197*/
     
    308202\brief Common graph search algorithms.
    309203
    310 This 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.
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    313206*/
    314207
     
    318211\brief Algorithms for finding shortest paths.
    319212
    320 This 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 
    342 This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     213This group describes the algorithms for finding shortest paths in graphs.
    344214*/
    345215
     
    349219\brief Algorithms for finding maximum flows.
    350220
    351 This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    353 
    354 The \e maximum \e flow \e problem is to find a flow of maximum value between
    355 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    356 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    357 \f$s, t \in V\f$ source and target nodes.
    358 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    359 following 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]
     221This group describes the algorithms for finding maximum flows and
     222feasible circulations.
     223
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum 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]
    365234
    366235LEMON contains several algorithms for solving maximum flow problems:
    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 
    376 In most cases the \ref Preflow algorithm provides the
    377 fastest method for computing a maximum flow. All implementations
    378 also provide functions to query the minimum cut, which is the dual
    379 problem of maximum flow.
    380 
    381 \ref Circulation is a preflow push-relabel algorithm implemented directly
    382 for finding feasible circulations, which is a somewhat different problem,
    383 but it is strongly related to maximum flow.
    384 For more information, see \ref Circulation.
    385 */
    386 
    387 /**
    388 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
     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
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
    389249@ingroup algs
    390250
    391251\brief Algorithms for finding minimum cost flows and circulations.
    392252
    393 This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
    396 "Minimum Cost Flow Problem".
    397 
    398 LEMON 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 
    409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
    410 implementations, but the other two algorithms could be faster in special cases.
    411 For example, if the total supply and/or capacities are rather small,
    412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     253This group describes the algorithms for finding minimum cost flows and
     254circulations.
    413255*/
    414256
     
    419261\brief Algorithms for finding minimum cut in graphs.
    420262
    421 This group contains the algorithms for finding minimum cut in graphs.
    422 
    423 The \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
    425 outgoing 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
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The 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
     267outgoing 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
    427269cut is the \f$X\f$ solution of the next optimization problem:
    428270
    429271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    430     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    431273
    432274LEMON contains several algorithms related to minimum cut problems:
    433275
    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.
     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
    440282
    441283If you want to find minimum cut just between two distinict nodes,
    442 see 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 
    450 This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
    452 
    453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    454 of minimum mean length (cost) in a digraph.
    455 The mean length of a cycle is the average length of its arcs, i.e. the
    456 ratio between the total length of the cycle and the number of arcs on it.
    457 
    458 This 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
    460 conservative if and only if there is no directed cycle of negative total
    461 length. For an arbitrary length function, the negative of the minimum
    462 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    463 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    464 function.
    465 
    466 LEMON 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 
    474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475 most efficient one, though the best known theoretical bound on its running
    476 time is exponential.
    477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    479 typically faster due to the applied early termination scheme.
     284please 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
     292This group describes the algorithms for discovering the graph properties
     293like 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
     304This group describes the algorithms for planarity checking,
     305embedding and drawing.
     306
     307\image html planar.png
     308\image latex planar.eps "Plane graph" width=\textwidth
    480309*/
    481310
     
    485314\brief Algorithms for finding matchings in graphs and bipartite graphs.
    486315
    487 This group contains the algorithms for calculating
     316This group contains algorithm objects and functions to calculate
    488317matchings in graphs and bipartite graphs. The general matching problem is
    489 finding a subset of the edges for which each node has at most one incident
    490 edge.
     318finding a subset of the arcs which does not shares common endpoints.
    491319
    492320There are several different algorithms for calculate matchings in
    493321graphs.  The matching problems in bipartite graphs are generally
    494322easier than in general graphs. The goal of the matching optimization
    495 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    496324matching. The search can be constrained to find perfect or
    497325maximum cardinality matching.
    498326
    499 The 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 
    534 This group contains the algorithms for discovering the graph properties
    535 like 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 Planar Embedding and Drawing
    543 @ingroup algs
    544 \brief Algorithms for planarity checking, embedding and drawing
    545 
    546 This group contains the algorithms for planarity checking,
    547 embedding 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
     327LEMON 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
     357This group describes the algorithms for finding a minimum cost spanning
     358tree in a graph
     359*/
     360
     361/**
     362@defgroup auxalg Auxiliary Algorithms
     363@ingroup algs
     364\brief Auxiliary algorithms implemented in LEMON.
     365
     366This group describes some algorithms implemented in LEMON
     367in order to make it easier to implement complex algorithms.
     368*/
     369
     370/**
     371@defgroup approx Approximation Algorithms
    555372@ingroup algs
    556373\brief Approximation algorithms.
    557374
    558 This group contains the approximation and heuristic algorithms
     375This group describes the approximation and heuristic algorithms
    559376implemented in LEMON.
    560 
    561 <b>Maximum Clique Problem</b>
    562   - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
    563     Grosso, Locatelli, and Pullan.
    564 */
    565 
    566 /**
    567 @defgroup auxalg Auxiliary Algorithms
    568 @ingroup algs
    569 \brief Auxiliary algorithms implemented in LEMON.
    570 
    571 This group contains some algorithms implemented in LEMON
    572 in order to make it easier to implement complex algorithms.
    573377*/
    574378
    575379/**
    576380@defgroup gen_opt_group General Optimization Tools
    577 \brief This group contains some general optimization frameworks
     381\brief This group describes some general optimization frameworks
    578382implemented in LEMON.
    579383
    580 This group contains some general optimization frameworks
     384This group describes some general optimization frameworks
    581385implemented in LEMON.
    582386*/
    583387
    584388/**
    585 @defgroup lp_group LP and MIP Solvers
     389@defgroup lp_group Lp and Mip Solvers
    586390@ingroup gen_opt_group
    587 \brief LP and MIP solver interfaces for LEMON.
    588 
    589 This group contains LP and MIP solver interfaces for LEMON.
    590 Various LP solvers could be used in the same manner with this
    591 high-level interface.
    592 
    593 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    594 \ref cplex, \ref soplex.
     391\brief Lp and Mip solver interfaces for LEMON.
     392
     393This group describes Lp and Mip solver interfaces for LEMON. The
     394various LP solvers could be used in the same manner with this
     395interface.
    595396*/
    596397
     
    609410\brief Metaheuristics for LEMON library.
    610411
    611 This group contains some metaheuristic optimization tools.
     412This group describes some metaheuristic optimization tools.
    612413*/
    613414
     
    624425\brief Simple basic graph utilities.
    625426
    626 This group contains some simple basic graph utilities.
     427This group describes some simple basic graph utilities.
    627428*/
    628429
     
    632433\brief Tools for development, debugging and testing.
    633434
    634 This group contains several useful tools for development,
     435This group describes several useful tools for development,
    635436debugging and testing.
    636437*/
     
    641442\brief Simple tools for measuring the performance of algorithms.
    642443
    643 This group contains simple tools for measuring the performance
     444This group describes simple tools for measuring the performance
    644445of algorithms.
    645446*/
     
    650451\brief Exceptions defined in LEMON.
    651452
    652 This group contains the exceptions defined in LEMON.
     453This group describes the exceptions defined in LEMON.
    653454*/
    654455
     
    657458\brief Graph Input-Output methods
    658459
    659 This group contains the tools for importing and exporting graphs
     460This group describes the tools for importing and exporting graphs
    660461and graph related data. Now it supports the \ref lgf-format
    661462"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    664465
    665466/**
    666 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    667468@ingroup io_group
    668469\brief Reading and writing LEMON Graph Format.
    669470
    670 This group contains methods for reading and writing
     471This group describes methods for reading and writing
    671472\ref lgf-format "LEMON Graph Format".
    672473*/
     
    677478\brief General \c EPS drawer and graph exporter
    678479
    679 This group contains general \c EPS drawing methods and special
     480This group describes general \c EPS drawing methods and special
    680481graph 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 
    688 Tools 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 
    696 Tool to read graphs from \e Nauty format data.
    697482*/
    698483
     
    701486\brief Skeleton classes and concept checking classes
    702487
    703 This group contains the data/algorithm skeletons and concept checking
     488This group describes the data/algorithm skeletons and concept checking
    704489classes implemented in LEMON.
    705490
     
    731516\brief Skeleton and concept checking classes for graph structures
    732517
    733 This group contains the skeletons and concept checking classes of
    734 graph structures.
     518This group describes the skeletons and concept checking classes of LEMON's
     519graph structures and helper classes used to implement these.
    735520*/
    736521
     
    740525\brief Skeleton and concept checking classes for maps
    741526
    742 This group contains the skeletons and concept checking classes of maps.
    743 */
    744 
    745 /**
    746 @defgroup tools Standalone Utility Applications
     527This group describes the skeletons and concept checking classes of maps.
     528*/
     529
     530/**
     531\anchor demoprograms
     532
     533@defgroup demos Demo programs
     534
     535Some demo programs are listed here. Their full source codes can be found in
     536the \c demo subdirectory of the source tree.
     537
     538It order to compile them, use <tt>--enable-demo</tt> configure option when
     539build the library.
     540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
    747544
    748545Some utility applications are listed here.
     
    752549*/
    753550
    754 /**
    755 \anchor demoprograms
    756 
    757 @defgroup demos Demo Programs
    758 
    759 Some demo programs are listed here. Their full source codes can be found in
    760 the \c demo subdirectory of the source tree.
    761 
    762 In order to compile them, use the <tt>make demo</tt> or the
    763 <tt>make check</tt> commands.
    764 */
    765 
    766 }
  • doc/lgf.dox

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

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

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>script/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>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
    58 strings, comments etc. as well as in all LEMON specific identifiers.
    59 So use the script carefully and make a backup copy of your source files
    60 before applying the script to them.</b>
     56<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
     57the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
     58in strings, comments etc. as well as in all identifiers.</b>
    6159
    6260\section migration-lgf LGF tools
  • doc/named-param.dox

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

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

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

    r1012 r539  
    11INCLUDE_DIRECTORIES(
    2   ${PROJECT_SOURCE_DIR}
     2  ${CMAKE_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
     
    99)
    1010
    11 CONFIGURE_FILE(
    12   ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
    13   ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    14   @ONLY
    15 )
    16 
    17 SET(LEMON_SOURCES
     11ADD_LIBRARY(lemon
    1812  arg_parser.cc
    1913  base.cc
    2014  color.cc
    21   lp_base.cc
    22   lp_skeleton.cc
    2315  random.cc
    2416  bits/windows.cc
    2517)
    2618
    27 IF(LEMON_HAVE_GLPK)
    28   SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
    29   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
    30   IF(WIN32)
    31     INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    32     INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    33     INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
    34   ENDIF()
    35 ENDIF()
    36 
    37 IF(LEMON_HAVE_CPLEX)
    38   SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    39   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
    40 ENDIF()
    41 
    42 IF(LEMON_HAVE_CLP)
    43   SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
    44   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    45 ENDIF()
    46 
    47 IF(LEMON_HAVE_CBC)
    48   SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    49   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    50 ENDIF()
    51 
    52 ADD_LIBRARY(lemon ${LEMON_SOURCES})
    53 IF(UNIX)
    54   SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
    55 ENDIF()
    56 
    5719INSTALL(
    5820  TARGETS lemon
    5921  ARCHIVE DESTINATION lib
    60   COMPONENT library
    61 )
     22  COMPONENT library)
    6223
    6324INSTALL(
     
    6526  DESTINATION include/lemon
    6627  COMPONENT headers
    67   FILES_MATCHING PATTERN "*.h"
    68 )
     28  FILES_MATCHING PATTERN "*.h")
    6929
    7030INSTALL(
    7131  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
    7232  DESTINATION include/lemon
    73   COMPONENT headers
    74 )
    75 
    76 INSTALL(
    77   FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
    78   DESTINATION lib/pkgconfig
    79 )
    80 
     33  COMPONENT headers)
  • lemon/Makefile.am

    r1021 r543  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt \
    4         lemon/config.h.cmake
     3        lemon/CMakeLists.txt
    54
    65pkgconfig_DATA += lemon/lemon.pc
     
    98
    109lemon_libemon_la_SOURCES = \
    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 \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc \
    1714        lemon/bits/windows.cc
    1815
    19 nodist_lemon_HEADERS = lemon/config.h   
     16#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     17#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    2018
    21 lemon_libemon_la_CXXFLAGS = \
    22         $(AM_CXXFLAGS) \
    23         $(GLPK_CFLAGS) \
    24         $(CPLEX_CFLAGS) \
    25         $(SOPLEX_CXXFLAGS) \
    26         $(CLP_CXXFLAGS) \
    27         $(CBC_CXXFLAGS)
    28 
    29 lemon_libemon_la_LDFLAGS = \
    30         $(GLPK_LIBS) \
    31         $(CPLEX_LIBS) \
    32         $(SOPLEX_LIBS) \
    33         $(CLP_LIBS) \
    34         $(CBC_LIBS)
    35 
    36 if HAVE_GLPK
    37 lemon_libemon_la_SOURCES += lemon/glpk.cc
    38 endif
    39 
    40 if HAVE_CPLEX
    41 lemon_libemon_la_SOURCES += lemon/cplex.cc
    42 endif
    43 
    44 if HAVE_SOPLEX
    45 lemon_libemon_la_SOURCES += lemon/soplex.cc
    46 endif
    47 
    48 if HAVE_CLP
    49 lemon_libemon_la_SOURCES += lemon/clp.cc
    50 endif
    51 
    52 if HAVE_CBC
    53 lemon_libemon_la_SOURCES += lemon/cbc.cc
    54 endif
     19nodist_lemon_HEADERS = lemon/config.h
    5520
    5621lemon_HEADERS += \
    57         lemon/adaptors.h \
    58         lemon/arg_parser.h \
     22        lemon/arg_parser.h \
    5923        lemon/assert.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 \
     24        lemon/bfs.h \
     25        lemon/bin_heap.h \
     26        lemon/color.h \
    7027        lemon/concept_check.h \
    71         lemon/connectivity.h \
     28        lemon/counter.h \
    7229        lemon/core.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 \
     30        lemon/dfs.h \
     31        lemon/dijkstra.h \
     32        lemon/dim2.h \
    8433        lemon/error.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 \
     34        lemon/graph_to_eps.h \
    9835        lemon/kruskal.h \
    99         lemon/hao_orlin.h \
    10036        lemon/lgf_reader.h \
    10137        lemon/lgf_writer.h \
    10238        lemon/list_graph.h \
    103         lemon/lp.h \
    104         lemon/lp_base.h \
    105         lemon/lp_skeleton.h \
    10639        lemon/maps.h \
    107         lemon/matching.h \
    10840        lemon/math.h \
    109         lemon/min_cost_arborescence.h \
    110         lemon/max_cardinality_search.h \
    111         lemon/nagamochi_ibaraki.h \
    112         lemon/nauty_reader.h \
    113         lemon/network_simplex.h \
    114         lemon/pairing_heap.h \
    11541        lemon/path.h \
    116         lemon/planarity.h \
    117         lemon/preflow.h \
    118         lemon/quad_heap.h \
    119         lemon/radix_heap.h \
    120         lemon/radix_sort.h \
    121         lemon/random.h \
     42        lemon/random.h \
    12243        lemon/smart_graph.h \
    123         lemon/soplex.h \
    124         lemon/static_graph.h \
    125         lemon/suurballe.h \
    126         lemon/time_measure.h \
    127         lemon/tolerance.h \
     44        lemon/time_measure.h \
     45        lemon/tolerance.h \
    12846        lemon/unionfind.h \
    12947        lemon/bits/windows.h
     
    13250        lemon/bits/alteration_notifier.h \
    13351        lemon/bits/array_map.h \
    134         lemon/bits/bezier.h \
     52        lemon/bits/base_extender.h \
     53        lemon/bits/bezier.h \
    13554        lemon/bits/default_map.h \
    136         lemon/bits/edge_set_extender.h \
    137         lemon/bits/enable_if.h \
    138         lemon/bits/graph_adaptor_extender.h \
     55        lemon/bits/enable_if.h \
    13956        lemon/bits/graph_extender.h \
    14057        lemon/bits/map_extender.h \
    14158        lemon/bits/path_dump.h \
    142         lemon/bits/solver_bits.h \
    14359        lemon/bits/traits.h \
    144         lemon/bits/variant.h \
    14560        lemon/bits/vector_map.h
    14661
  • lemon/arg_parser.cc

    r956 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    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 
    3123  void ArgParser::_showHelp(void *p)
    3224  {
    3325    (static_cast<ArgParser*>(p))->showHelp();
    34     (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
     26    exit(1);
    3527  }
    3628
    3729  ArgParser::ArgParser(int argc, const char * const *argv)
    38     :_argc(argc), _argv(argv), _command_name(argv[0]),
    39     _exit_on_problems(true) {
     30    :_argc(argc), _argv(argv), _command_name(argv[0]) {
    4031    funcOption("-help","Print a short help message",_showHelp,this);
    4132    synonym("help","-help");
     
    352343        i!=_others_help.end();++i) showHelp(i);
    353344    for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    354     _terminate(ArgParserException::HELP);
     345    exit(1);
    355346  }
    356347
     
    361352    std::cerr << "\nType '" << _command_name <<
    362353      " --help' to obtain a short summary on the usage.\n\n";
    363     _terminate(ArgParserException::UNKNOWN_OPT);
     354    exit(1);
    364355  }
    365356
     
    424415      std::cerr << "\nType '" << _command_name <<
    425416        " --help' to obtain a short summary on the usage.\n\n";
    426       _terminate(ArgParserException::INVALID_OPT);
     417      exit(1);
    427418    }
    428419  }
  • lemon/arg_parser.h

    r959 r311  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3434
    3535namespace lemon {
    36 
    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 
    8136
    8237  ///Command line arguments parser
     
    162117                    void (*func)(void *),void *data);
    163118
    164     bool _exit_on_problems;
    165 
    166     void _terminate(ArgParserException::Reason reason) const;
    167 
    168119  public:
    169120
     
    430381    const std::vector<std::string> &files() const { return _file_args; }
    431382
    432     ///Throw instead of exit in case of problems
    433     void throwOnProblems()
    434     {
    435       _exit_on_problems=false;
    436     }
    437383  };
    438384}
  • lemon/assert.h

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

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

    r956 r301  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    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 conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
     56    ///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 conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default, it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a \c ProcessedMap.
    69 
    70     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7170    ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7372#ifdef DOXYGEN
    7473    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to
    86     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8785    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    88     ///Instantiates a \c ReachedMap.
    89 
    90     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    9189    ///\param g is the digraph, to which
    92     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the ReachedMap.
    9391    static ReachedMap *createReachedMap(const Digraph &g)
    9492    {
     
    9997
    10098    ///The type of the map that stores the distances of the nodes.
    101     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    102100    typedef typename Digraph::template NodeMap<int> DistMap;
    103     ///Instantiates a \c DistMap.
    104 
    105     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    106104    ///\param g is the digraph, to which we would like to define the
    107     ///\ref DistMap.
     105    ///DistMap.
    108106    static DistMap *createDistMap(const Digraph &g)
    109107    {
     
    122120  ///
    123121  ///\tparam GR The type of the digraph the algorithm runs on.
    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.
     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.
    130129#ifdef DOXYGEN
    131130  template <typename GR,
     
    153152    typedef PredMapPath<Digraph, PredMap> Path;
    154153
    155     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    156155    typedef TR Traits;
    157156
     
    215214    typedef Bfs Create;
    216215
    217     ///\name Named Template Parameters
     216    ///\name Named template parameters
    218217
    219218    ///@{
     
    229228    };
    230229    ///\brief \ref named-templ-param "Named parameter" for setting
    231     ///\c PredMap type.
     230    ///PredMap type.
    232231    ///
    233232    ///\ref named-templ-param "Named parameter" for setting
    234     ///\c PredMap type.
    235     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     233    ///PredMap type.
    236234    template <class T>
    237235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    249247    };
    250248    ///\brief \ref named-templ-param "Named parameter" for setting
    251     ///\c DistMap type.
     249    ///DistMap type.
    252250    ///
    253251    ///\ref named-templ-param "Named parameter" for setting
    254     ///\c DistMap type.
    255     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     252    ///DistMap type.
    256253    template <class T>
    257254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    269266    };
    270267    ///\brief \ref named-templ-param "Named parameter" for setting
    271     ///\c ReachedMap type.
     268    ///ReachedMap type.
    272269    ///
    273270    ///\ref named-templ-param "Named parameter" for setting
    274     ///\c ReachedMap type.
    275     ///It must conform to
    276     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     271    ///ReachedMap type.
    277272    template <class T>
    278273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    290285    };
    291286    ///\brief \ref named-templ-param "Named parameter" for setting
    292     ///\c ProcessedMap type.
     287    ///ProcessedMap type.
    293288    ///
    294289    ///\ref named-templ-param "Named parameter" for setting
    295     ///\c ProcessedMap type.
    296     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     290    ///ProcessedMap type.
    297291    template <class T>
    298292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    309303    };
    310304    ///\brief \ref named-templ-param "Named parameter" for setting
    311     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     305    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    312306    ///
    313307    ///\ref named-templ-param "Named parameter" for setting
    314     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     308    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    315309    ///If you don't set it explicitly, it will be automatically allocated.
    316310    struct SetStandardProcessedMap :
     
    347341
    348342    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    353346    ///\return <tt> (*this) </tt>
    354347    Bfs &predMap(PredMap &m)
     
    365358
    366359    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    371363    ///\return <tt> (*this) </tt>
    372364    Bfs &reachedMap(ReachedMap &m)
     
    383375
    384376    ///Sets the map that indicates which nodes are processed.
    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.
     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.
    389380    ///\return <tt> (*this) </tt>
    390381    Bfs &processedMap(ProcessedMap &m)
     
    402393    ///Sets the map that stores the distances of the nodes calculated by
    403394    ///the algorithm.
    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.
     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.
    408398    ///\return <tt> (*this) </tt>
    409399    Bfs &distMap(DistMap &m)
     
    419409  public:
    420410
    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.
     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.
    428420
    429421    ///@{
    430422
    431     ///\brief Initializes the internal data structures.
    432     ///
    433423    ///Initializes the internal data structures.
     424
     425    ///Initializes the internal data structures.
     426    ///
    434427    void init()
    435428    {
     
    565558    }
    566559
    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.
     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.
    571565    bool emptyQueue() const { return _queue_tail==_queue_head; }
    572566
    573567    ///Returns the number of the nodes to be processed.
    574568
    575     ///Returns the number of the nodes to be processed
    576     ///in the queue.
     569    ///Returns the number of the nodes to be processed in the queue.
    577570    int queueSize() const { return _queue_head-_queue_tail; }
    578571
     
    709702    ///Runs the algorithm to visit all nodes in the digraph.
    710703
    711     ///This method runs the %BFS algorithm in order to visit all nodes
    712     ///in the digraph.
     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).
    713710    ///
    714711    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    735732
    736733    ///\name Query Functions
    737     ///The results of the BFS algorithm can be obtained using these
     734    ///The result of the %BFS algorithm can be obtained using these
    738735    ///functions.\n
    739     ///Either \ref run(Node) "run()" or \ref start() should be called
    740     ///before using them.
     736    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     737    ///"start()" must be called before using them.
    741738
    742739    ///@{
    743740
    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.
     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.
    752749    Path path(Node t) const { return Path(*G, *_pred, t); }
    753750
    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
     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
    759756    ///the return value of this function is undefined.
    760757    ///
    761     ///\pre Either \ref run(Node) "run()" or \ref init()
    762     ///must be called before using this function.
     758    ///\pre Either \ref run() or \ref start() must be called before
     759    ///using this function.
    763760    int dist(Node v) const { return (*_dist)[v]; }
    764761
    765     ///\brief Returns the 'previous arc' of the shortest path tree for
    766     ///the given node.
    767     ///
     762    ///Returns the 'previous arc' of the shortest path tree for a node.
     763
    768764    ///This function returns the 'previous arc' of the shortest path
    769765    ///tree for the node \c v, i.e. it returns the last arc of a
    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.
     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.
    772768    ///
    773769    ///The shortest path tree used here is equal to the shortest path
    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.
     770    ///tree used in \ref predNode().
     771    ///
     772    ///\pre Either \ref run() or \ref start() must be called before
     773    ///using this function.
    778774    Arc predArc(Node v) const { return (*_pred)[v];}
    779775
    780     ///\brief Returns the 'previous node' of the shortest path tree for
    781     ///the given node.
    782     ///
     776    ///Returns the 'previous node' of the shortest path tree for a node.
     777
    783778    ///This function returns the 'previous node' of the shortest path
    784779    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    787782    ///
    788783    ///The shortest path tree used here is equal to the shortest path
    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.
     784    ///tree used in \ref predArc().
     785    ///
     786    ///\pre Either \ref run() or \ref start() must be called before
     787    ///using this function.
    793788    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    794789                                  G->source((*_pred)[v]); }
     
    800795    ///of the nodes calculated by the algorithm.
    801796    ///
    802     ///\pre Either \ref run(Node) "run()" or \ref init()
     797    ///\pre Either \ref run() or \ref init()
    803798    ///must be called before using this function.
    804799    const DistMap &distMap() const { return *_dist;}
     
    808803    ///
    809804    ///Returns a const reference to the node map that stores the predecessor
    810     ///arcs, which form the shortest path tree (forest).
    811     ///
    812     ///\pre Either \ref run(Node) "run()" or \ref init()
     805    ///arcs, which form the shortest path tree.
     806    ///
     807    ///\pre Either \ref run() or \ref init()
    813808    ///must be called before using this function.
    814809    const PredMap &predMap() const { return *_pred;}
    815810
    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()
     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()
    821815    ///must be called before using this function.
    822816    bool reached(Node v) const { return (*_reached)[v]; }
     
    840834    ///The type of the map that stores the predecessor
    841835    ///arcs of the shortest paths.
    842     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     836    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    843837    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    844838    ///Instantiates a PredMap.
     
    855849
    856850    ///The type of the map that indicates which nodes are processed.
    857     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    858     ///By default, it is a NullMap.
     851    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     852    ///By default it is a NullMap.
    859853    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    860854    ///Instantiates a ProcessedMap.
     
    875869
    876870    ///The type of the map that indicates which nodes are reached.
    877     ///It must conform to
    878     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     871    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    879872    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    880873    ///Instantiates a ReachedMap.
     
    891884
    892885    ///The type of the map that stores the distances of the nodes.
    893     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     886    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    894887    typedef typename Digraph::template NodeMap<int> DistMap;
    895888    ///Instantiates a DistMap.
     
    906899
    907900    ///The type of the shortest paths.
    908     ///It must conform to the \ref concepts::Path "Path" concept.
     901    ///It must meet the \ref concepts::Path "Path" concept.
    909902    typedef lemon::Path<Digraph> Path;
    910903  };
     
    912905  /// Default traits class used by BfsWizard
    913906
    914   /// Default traits class used by BfsWizard.
    915   /// \tparam GR The type of the digraph.
     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.
    916913  template<class GR>
    917914  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    941938    /// Constructor.
    942939
    943     /// This constructor does not require parameters, it initiates
     940    /// This constructor does not require parameters, therefore it initiates
    944941    /// all of the attributes to \c 0.
    945942    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    961958  /// This auxiliary class is created to implement the
    962959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    963   /// It does not have own \ref run(Node) "run()" method, it uses the
    964   /// functions and features of the plain \ref Bfs.
     960  /// It does not have own \ref run() method, it uses the functions
     961  /// and features of the plain \ref Bfs.
    965962  ///
    966963  /// This class should only be used through the \ref bfs() function,
    967964  /// which makes it easier to use the algorithm.
    968   ///
    969   /// \tparam TR The traits class that defines various types used by the
    970   /// algorithm.
    971965  template<class TR>
    972966  class BfsWizard : public TR
     
    974968    typedef TR Base;
    975969
     970    ///The type of the digraph the algorithm runs on.
    976971    typedef typename TR::Digraph Digraph;
    977972
     
    981976    typedef typename Digraph::OutArcIt OutArcIt;
    982977
     978    ///\brief The type of the map that stores the predecessor
     979    ///arcs of the shortest paths.
    983980    typedef typename TR::PredMap PredMap;
     981    ///\brief The type of the map that stores the distances of the nodes.
    984982    typedef typename TR::DistMap DistMap;
     983    ///\brief The type of the map that indicates which nodes are reached.
    985984    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
    987988    typedef typename TR::Path Path;
    988989
     
    10541055    ///Runs BFS algorithm to visit all nodes in the digraph.
    10551056
    1056     ///This method runs BFS algorithm in order to visit all nodes
    1057     ///in the digraph.
     1057    ///This method runs BFS algorithm in order to compute
     1058    ///the shortest path to each node.
    10581059    void run()
    10591060    {
     
    10671068      SetPredMapBase(const TR &b) : TR(b) {}
    10681069    };
    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.
     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.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    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.
     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.
    10941093    template<class T>
    10951094    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11051104      SetDistMapBase(const TR &b) : TR(b) {}
    11061105    };
    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.
     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.
    11141111    template<class T>
    11151112    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11251122      SetProcessedMapBase(const TR &b) : TR(b) {}
    11261123    };
    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.
     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.
    11331129    template<class T>
    11341130    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    11831179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11841180  ///\endcode
    1185   ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
    11861182  ///to the end of the parameter list.
    11871183  ///\sa BfsWizard
     
    11991195  /// This class defines the interface of the BfsVisit events, and
    12001196  /// it could be the base of a real visitor class.
    1201   template <typename GR>
     1197  template <typename _Digraph>
    12021198  struct BfsVisitor {
    1203     typedef GR Digraph;
     1199    typedef _Digraph Digraph;
    12041200    typedef typename Digraph::Arc Arc;
    12051201    typedef typename Digraph::Node Node;
     
    12291225  };
    12301226#else
    1231   template <typename GR>
     1227  template <typename _Digraph>
    12321228  struct BfsVisitor {
    1233     typedef GR Digraph;
     1229    typedef _Digraph Digraph;
    12341230    typedef typename Digraph::Arc Arc;
    12351231    typedef typename Digraph::Node Node;
     
    12591255  ///
    12601256  /// Default traits class of BfsVisit class.
    1261   /// \tparam GR The type of the digraph the algorithm runs on.
    1262   template<class GR>
     1257  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1258  template<class _Digraph>
    12631259  struct BfsVisitDefaultTraits {
    12641260
    12651261    /// \brief The type of the digraph the algorithm runs on.
    1266     typedef GR Digraph;
     1262    typedef _Digraph Digraph;
    12671263
    12681264    /// \brief The type of the map that indicates which nodes are reached.
    12691265    ///
    12701266    /// The type of the map that indicates which nodes are reached.
    1271     /// It must conform to
    1272     ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1267    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12731268    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12741269
     
    12861281  /// \ingroup search
    12871282  ///
    1288   /// \brief BFS algorithm class with visitor interface.
     1283  /// \brief %BFS algorithm class with visitor interface.
    12891284  ///
    1290   /// This class provides an efficient implementation of the BFS algorithm
     1285  /// This class provides an efficient implementation of the %BFS algorithm
    12911286  /// with visitor interface.
    12921287  ///
    1293   /// The BfsVisit class provides an alternative interface to the Bfs
     1288  /// The %BfsVisit class provides an alternative interface to the Bfs
    12941289  /// class. It works with callback mechanism, the BfsVisit object calls
    12951290  /// the member functions of the \c Visitor class on every BFS event.
     
    13001295  /// instead.
    13011296  ///
    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
     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
    13081303  /// does not observe the BFS events. If you want to observe the BFS
    13091304  /// events, you should implement your own visitor 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.
     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.
    13151310#ifdef DOXYGEN
    1316   template <typename GR, typename VS, typename TR>
     1311  template <typename _Digraph, typename _Visitor, typename _Traits>
    13171312#else
    1318   template <typename GR = ListDigraph,
    1319             typename VS = BfsVisitor<GR>,
    1320             typename TR = BfsVisitDefaultTraits<GR> >
     1313  template <typename _Digraph = ListDigraph,
     1314            typename _Visitor = BfsVisitor<_Digraph>,
     1315            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    13211316#endif
    13221317  class BfsVisit {
     
    13241319
    13251320    ///The traits class.
    1326     typedef TR Traits;
     1321    typedef _Traits Traits;
    13271322
    13281323    ///The type of the digraph the algorithm runs on.
     
    13301325
    13311326    ///The visitor type used by the algorithm.
    1332     typedef VS Visitor;
     1327    typedef _Visitor Visitor;
    13331328
    13341329    ///The type of the map that indicates which nodes are reached.
     
    13701365    typedef BfsVisit Create;
    13711366
    1372     /// \name Named Template Parameters
     1367    /// \name Named template parameters
    13731368
    13741369    ///@{
     
    14121407    ///
    14131408    /// Sets the map that indicates which nodes are reached.
    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.
     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.
    14181412    /// \return <tt> (*this) </tt>
    14191413    BfsVisit &reachedMap(ReachedMap &m) {
     
    14281422  public:
    14291423
    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.
     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.
    14371434
    14381435    /// @{
     
    17041701    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17051702    ///
    1706     /// This method runs the %BFS algorithm in order to visit all nodes
    1707     /// in the digraph.
     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).
    17081709    ///
    17091710    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    17301731
    17311732    /// \name Query Functions
    1732     /// The results of the BFS algorithm can be obtained using these
     1733    /// The result of the %BFS algorithm can be obtained using these
    17331734    /// functions.\n
    1734     /// Either \ref run(Node) "run()" or \ref start() should be called
    1735     /// before using them.
    1736 
     1735    /// Either \ref lemon::BfsVisit::run() "run()" or
     1736    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1737    /// using them.
    17371738    ///@{
    17381739
    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()
     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()
    17441744    /// must be called before using this function.
    1745     bool reached(Node v) const { return (*_reached)[v]; }
     1745    bool reached(Node v) { return (*_reached)[v]; }
    17461746
    17471747    ///@}
  • lemon/bin_heap.h

    r758 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
     32  ///\ingroup auxdat
    3333  ///
    34   /// \brief Binary heap data structure.
     34  ///\brief A Binary Heap implementation.
    3535  ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
     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.
    3841  ///
    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
     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> >
    4952  class BinHeap {
     53
    5054  public:
    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.
     55    ///\e
     56    typedef _ItemIntMap ItemIntMap;
     57    ///\e
     58    typedef _Prio Prio;
     59    ///\e
    5760    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     61    ///\e
    5962    typedef std::pair<Item,Prio> Pair;
    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
     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
    6770    /// heap's point of view, but may be useful to the user.
    6871    ///
    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.
     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...
    7174    enum State {
    72       IN_HEAP = 0,    ///< = 0.
    73       PRE_HEAP = -1,  ///< = -1.
    74       POST_HEAP = -2  ///< = -2.
     75      IN_HEAP = 0,
     76      PRE_HEAP = -1,
     77      POST_HEAP = -2
    7578    };
    7679
    7780  private:
    78     std::vector<Pair> _data;
    79     Compare _comp;
    80     ItemIntMap &_iim;
     81    std::vector<Pair> data;
     82    Compare comp;
     83    ItemIntMap &iim;
    8184
    8285  public:
    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.
     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.
    120122    void clear() {
    121       _data.clear();
     123      data.clear();
    122124    }
    123125
     
    125127    static int parent(int i) { return (i-1)/2; }
    126128
    127     static int secondChild(int i) { return 2*i+2; }
     129    static int second_child(int i) { return 2*i+2; }
    128130    bool less(const Pair &p1, const Pair &p2) const {
    129       return _comp(p1.second, p2.second);
    130     }
    131 
    132     int bubbleUp(int hole, Pair p) {
     131      return comp(p1.second, p2.second);
     132    }
     133
     134    int bubble_up(int hole, Pair p) {
    133135      int par = parent(hole);
    134       while( hole>0 && less(p,_data[par]) ) {
    135         move(_data[par],hole);
     136      while( hole>0 && less(p,data[par]) ) {
     137        move(data[par],hole);
    136138        hole = par;
    137139        par = parent(hole);
     
    141143    }
    142144
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     145    int bubble_down(int hole, Pair p, int length) {
     146      int child = second_child(hole);
    145147      while(child < length) {
    146         if( less(_data[child-1], _data[child]) ) {
     148        if( less(data[child-1], data[child]) ) {
    147149          --child;
    148150        }
    149         if( !less(_data[child], p) )
     151        if( !less(data[child], p) )
    150152          goto ok;
    151         move(_data[child], hole);
     153        move(data[child], hole);
    152154        hole = child;
    153         child = secondChild(hole);
     155        child = second_child(hole);
    154156      }
    155157      child--;
    156       if( child<length && less(_data[child], p) ) {
    157         move(_data[child], hole);
     158      if( child<length && less(data[child], p) ) {
     159        move(data[child], hole);
    158160        hole=child;
    159161      }
     
    164166
    165167    void move(const Pair &p, int i) {
    166       _data[i] = p;
    167       _iim.set(p.first, i);
     168      data[i] = p;
     169      iim.set(p.first, i);
    168170    }
    169171
    170172  public:
    171 
    172173    /// \brief Insert a pair of item and priority into the heap.
    173174    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     175    /// Adds \c p.first to the heap with priority \c p.second.
    176176    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178177    void push(const Pair &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.
     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.
    188186    /// \param i The item to insert.
    189187    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191188    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192189
    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.
     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.
    197195    Item top() const {
    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.
     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.
    205203    Prio prio() const {
    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.
     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.
    212211    /// \pre The heap must be non-empty.
    213212    void pop() {
    214       int n = _data.size()-1;
    215       _iim.set(_data[0].first, POST_HEAP);
     213      int n = data.size()-1;
     214      iim.set(data[0].first, POST_HEAP);
    216215      if (n > 0) {
    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.
     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.
    228226    void erase(const Item &i) {
    229       int h = _iim[i];
    230       int n = _data.size()-1;
    231       _iim.set(_data[h].first, POST_HEAP);
     227      int h = iim[i];
     228      int n = data.size()-1;
     229      iim.set(data[h].first, POST_HEAP);
    232230      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     231        if ( bubble_up(h, data[n]) == h) {
     232          bubble_down(h, data[n], n);
    235233        }
    236234      }
    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.
     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.
    245244    Prio operator[](const Item &i) const {
    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.
     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.
    256254    /// \param i The item.
    257255    /// \param p The priority.
    258256    void set(const Item &i, const Prio &p) {
    259       int idx = _iim[i];
     257      int idx = iim[i];
    260258      if( idx < 0 ) {
    261259        push(i,p);
    262260      }
    263       else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     261      else if( comp(p, data[idx].second) ) {
     262        bubble_up(idx, Pair(i,p));
    265263      }
    266264      else {
    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.
     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.
    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.
    277276    void decrease(const Item &i, const Prio &p) {
    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.
     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.
    285286    /// \param i The item.
    286287    /// \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       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.
     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.
    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 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.
     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.
    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 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.
     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.
    336335    void replace(const Item& i, const Item& j) {
    337       int idx = _iim[i];
    338       _iim.set(i, _iim[j]);
    339       _iim.set(j, idx);
    340       _data[idx].first = j;
     336      int idx = iim[i];
     337      iim.set(i, iim[j]);
     338      iim.set(j, idx);
     339      data[idx].first = j;
    341340    }
    342341
  • lemon/bits/alteration_notifier.h

    r463 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3636  // a container.
    3737  //
    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
     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
    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 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.
     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.
    5756  //
    5857  // For the proper functonality of this class, we should notify it
    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
     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
    6463  // clear() and build() members. Important rule that if we erase items
    65   // from graphs we should first signal the alteration and after that erase
     64  // from graph we should first signal the alteration and after that erase
    6665  // them from the container, on the other way on item addition we should
    6766  // first extend the container and just after that signal the alteration.
    6867  //
    6968  // The alteration can be observed with a class inherited from the
    70   // ObserverBase nested class. The signals can be handled with
     69  // \e ObserverBase nested class. The signals can be handled with
    7170  // overriding the virtual functions defined in the base class.  The
    7271  // observer base can be attached to the notifier with the
    73   // attach() member and can be detached with detach() function. The
     72  // \e attach() member and can be detached with detach() function. The
    7473  // alteration handlers should not call any function which signals
    7574  // an other alteration in the same notifier and should not
    7675  // detach any observer from the notifier.
    7776  //
    78   // Alteration observers try to be exception safe. If an add() or
    79   // a clear() function throws an exception then the remaining
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
    8079  // observeres will not be notified and the fulfilled additions will
    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
     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
    8786  // reliable. If we want to carry out the node degree in the graph
    88   // as in the \ref InDegMap and we use the reverseArc(), then it cause
     87  // as in the \ref InDegMap and we use the reverseEdge that cause
    8988  // unreliable functionality. Because the alteration observing signals
    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.
     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.
    9493  //
    9594  // \param _Container The container which is observed.
     
    105104    typedef _Item Item;
    106105
    107     // \brief Exception which can be called from clear() and
    108     // erase().
    109     //
    110     // From the clear() and erase() function only this
     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
    111110    // exception is allowed to throw. The exception immediatly
    112111    // detaches the current observer from the notifier. Because the
    113     // clear() and erase() should not throw other exceptions
     112    // \e clear() and \e erase() should not throw other exceptions
    114113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
     
    123122    // The observer interface contains some pure virtual functions
    124123    // to override. The add() and erase() functions are
    125     // to notify the oberver when one item is added or erased.
     124    // to notify the oberver when one item is added or
     125    // erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer
  • lemon/bits/array_map.h

    r956 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    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 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.
     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.
    4243  //
    43   // The template parameters are the Graph, the current Item type and
     44  // The template parameters are the Graph the current Item type and
    4445  // the Value type of the map.
    4546  template <typename _Graph, typename _Item, typename _Value>
     
    4748    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4849  public:
    49     // The graph type.
    50     typedef _Graph GraphType;
    51     // The item type.
     50    // The graph type of the maps.
     51    typedef _Graph Graph;
     52    // The item type of the map.
    5253    typedef _Item Item;
    5354    // The reference map tag.
    5455    typedef True ReferenceMapTag;
    5556
    56     // The key type of the map.
     57    // The key type of the maps.
    5758    typedef _Item Key;
    5859    // The value type of the map.
     
    6465    typedef _Value& Reference;
    6566
    66     // The map type.
    67     typedef ArrayMap Map;
    68 
    6967    // The notifier type.
    7068    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7169
    72   private:
    73 
    7470    // The MapBase of the Map which imlements the core regisitry function.
    7571    typedef typename Notifier::ObserverBase Parent;
    7672
     73  private:
    7774    typedef std::allocator<Value> Allocator;
    7875
     
    8279    //
    8380    // Graph initialized map constructor.
    84     explicit ArrayMap(const GraphType& graph) {
     81    explicit ArrayMap(const Graph& graph) {
    8582      Parent::attach(graph.notifier(Item()));
    8683      allocate_memory();
     
    9693    //
    9794    // It constructs a map and initialize all of the the map.
    98     ArrayMap(const GraphType& graph, const Value& value) {
     95    ArrayMap(const Graph& graph, const Value& value) {
    9996      Parent::attach(graph.notifier(Item()));
    10097      allocate_memory();
     
    140137    // \brief Template assign operator.
    141138    //
    142     // The given parameter should conform to the ReadMap
     139    // The given parameter should be conform to the ReadMap
    143140    // concecpt and could be indiced by the current item set of
    144141    // the NodeMap. In this case the value for each item
     
    204201    // \brief Adds a new key to the map.
    205202    //
    206     // It adds a new key to the map. It is called by the observer notifier
     203    // It adds a new key to the map. It called by the observer notifier
    207204    // and it overrides the add() member function of the observer base.
    208205    virtual void add(const Key& key) {
     
    232229    // \brief Adds more new keys to the map.
    233230    //
    234     // It adds more new keys to the map. It is called by the observer notifier
     231    // It adds more new keys to the map. It called by the observer notifier
    235232    // and it overrides the add() member function of the observer base.
    236233    virtual void add(const std::vector<Key>& keys) {
     
    276273    // \brief Erase a key from the map.
    277274    //
    278     // Erase a key from the map. It is called by the observer notifier
     275    // Erase a key from the map. It called by the observer notifier
    279276    // and it overrides the erase() member function of the observer base.
    280277    virtual void erase(const Key& key) {
     
    285282    // \brief Erase more keys from the map.
    286283    //
    287     // Erase more keys from the map. It is called by the observer notifier
     284    // Erase more keys from the map. It called by the observer notifier
    288285    // and it overrides the erase() member function of the observer base.
    289286    virtual void erase(const std::vector<Key>& keys) {
     
    294291    }
    295292
    296     // \brief Builds the map.
    297     //
    298     // It builds the map. It is called by the observer notifier
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
    299296    // and it overrides the build() member function of the observer base.
    300297    virtual void build() {
     
    310307    // \brief Clear the map.
    311308    //
    312     // It erase all items from the map. It is called by the observer notifier
     309    // It erase all items from the map. It called by the observer notifier
    313310    // and it overrides the clear() member function of the observer base.
    314311    virtual void clear() {
  • lemon/bits/bezier.h

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

    r956 r540  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2008
    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  public:
    156157    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    157 
    158   public:
    159158    typedef DefaultMap<_Graph, _Item, _Value> Map;
    160159
    161     typedef typename Parent::GraphType GraphType;
     160    typedef typename Parent::Graph Graph;
    162161    typedef typename Parent::Value Value;
    163162
    164     explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
    165     DefaultMap(const GraphType& graph, const Value& value)
     163    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
     164    DefaultMap(const Graph& graph, const Value& value)
    166165      : Parent(graph, value) {}
    167166
  • lemon/bits/enable_if.h

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

    r825 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the graph types
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the digraph implementations
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40  public:
     41
    4042    typedef Base Parent;
    41 
    42   public:
    43 
    4443    typedef DigraphExtender Digraph;
    4544
     
    5756    }
    5857
    59     static Node fromId(int id, Node) {
     58    Node fromId(int id, Node) const {
    6059      return Parent::nodeFromId(id);
    6160    }
    6261
    63     static Arc fromId(int id, Arc) {
     62    Arc fromId(int id, Arc) const {
    6463      return Parent::arcFromId(id);
    6564    }
     
    220219    class NodeMap
    221220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
     221    public:
     222      typedef DigraphExtender Digraph;
    222223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    223224
    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;
    246248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    247249
    248     public:
    249250      explicit ArcMap(const Digraph& digraph)
    250251        : Parent(digraph) {}
     
    330331  template <typename Base>
    331332  class GraphExtender : public Base {
     333  public:
     334
    332335    typedef Base Parent;
    333 
    334   public:
    335 
    336336    typedef GraphExtender Graph;
    337337
     
    356356    }
    357357
    358     static Node fromId(int id, Node) {
     358    Node fromId(int id, Node) const {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     static Arc fromId(int id, Arc) {
     362    Arc fromId(int id, Arc) const {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     static Edge fromId(int id, Edge) {
     366    Edge fromId(int id, Edge) const {
    367367      return Parent::edgeFromId(id);
    368368    }
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     604    public:
     605      typedef GraphExtender Graph;
    604606      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    605607
    606     public:
    607       explicit NodeMap(const Graph& graph)
     608      NodeMap(const Graph& graph)
    608609        : Parent(graph) {}
    609610      NodeMap(const Graph& graph, const _Value& value)
     
    626627    class ArcMap
    627628      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     629    public:
     630      typedef GraphExtender Graph;
    628631      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    629632
    630     public:
    631       explicit ArcMap(const Graph& graph)
     633      ArcMap(const Graph& graph)
    632634        : Parent(graph) {}
    633635      ArcMap(const Graph& graph, const _Value& value)
     
    650652    class EdgeMap
    651653      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     654    public:
     655      typedef GraphExtender Graph;
    652656      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    653657
    654     public:
    655       explicit EdgeMap(const Graph& graph)
     658      EdgeMap(const Graph& graph)
    656659        : Parent(graph) {}
    657660
  • lemon/bits/map_extender.h

    r867 r865  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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
    3941    typedef _Map Parent;
    40     typedef typename Parent::GraphType GraphType;
    41 
    42   public:
    43 
    4442    typedef MapExtender Map;
     43
     44
     45    typedef typename Parent::Graph Graph;
    4546    typedef typename Parent::Key Item;
    4647
    4748    typedef typename Parent::Key Key;
    4849    typedef typename Parent::Value Value;
    49     typedef typename Parent::Reference Reference;
    50     typedef typename Parent::ConstReference ConstReference;
    51 
    52     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    5350
    5451    class MapIt;
     
    6057  public:
    6158
    62     MapExtender(const GraphType& graph)
     59    MapExtender(const Graph& graph)
    6360      : Parent(graph) {}
    6461
    65     MapExtender(const GraphType& graph, const Value& value)
     62    MapExtender(const Graph& graph, const Value& value)
    6663      : Parent(graph, value) {}
    6764
     
    7976  public:
    8077    class MapIt : public Item {
    81       typedef Item Parent;
    82 
    83     public:
    84 
     78    public:
     79
     80      typedef Item Parent;
    8581      typedef typename Map::Value Value;
    8682
     
    119115
    120116    class ConstMapIt : public Item {
    121       typedef Item Parent;
    122 
    123     public:
     117    public:
     118
     119      typedef Item Parent;
    124120
    125121      typedef typename Map::Value Value;
     
    150146
    151147    class ItemIt : public Item {
    152       typedef Item Parent;
    153 
    154     public:
     148    public:
     149
     150      typedef Item Parent;
     151
    155152      ItemIt() : map(NULL) {}
    156 
    157153
    158154      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     
    181177  template <typename _Graph, typename _Map>
    182178  class SubMapExtender : public _Map {
     179  public:
     180
    183181    typedef _Map Parent;
    184     typedef _Graph GraphType;
    185 
    186   public:
    187 
    188182    typedef SubMapExtender Map;
     183
     184    typedef _Graph Graph;
     185
    189186    typedef typename Parent::Key Item;
    190187
    191188    typedef typename Parent::Key Key;
    192189    typedef typename Parent::Value Value;
    193     typedef typename Parent::Reference Reference;
    194     typedef typename Parent::ConstReference ConstReference;
    195 
    196     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    197190
    198191    class MapIt;
     
    204197  public:
    205198
    206     SubMapExtender(const GraphType& _graph)
     199    SubMapExtender(const Graph& _graph)
    207200      : Parent(_graph), graph(_graph) {}
    208201
    209     SubMapExtender(const GraphType& _graph, const Value& _value)
     202    SubMapExtender(const Graph& _graph, const Value& _value)
    210203      : Parent(_graph, _value), graph(_graph) {}
    211204
     
    227220  public:
    228221    class MapIt : public Item {
    229       typedef Item Parent;
    230 
    231     public:
     222    public:
     223
     224      typedef Item Parent;
    232225      typedef typename Map::Value Value;
    233226
     
    266259
    267260    class ConstMapIt : public Item {
    268       typedef Item Parent;
    269 
    270     public:
     261    public:
     262
     263      typedef Item Parent;
    271264
    272265      typedef typename Map::Value Value;
     
    297290
    298291    class ItemIt : public Item {
    299       typedef Item Parent;
    300 
    301     public:
     292    public:
     293
     294      typedef Item Parent;
     295
    302296      ItemIt() : map(NULL) {}
    303 
    304297
    305298      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     
    324317  private:
    325318
    326     const GraphType& graph;
     319    const Graph& graph;
    327320
    328321  };
  • lemon/bits/path_dump.h

    r973 r971  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    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>
     19#ifndef LEMON_BITS_PRED_MAP_PATH_H
     20#define LEMON_BITS_PRED_MAP_PATH_H
    2421
    2522namespace lemon {
  • lemon/bits/traits.h

    r663 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  struct InvalidType {};
    3131
    32   template <typename GR, typename _Item>
     32  template <typename _Graph, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename GR, typename Enable = void>
     36  template <typename Graph, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename GR>
     40  template <typename Graph>
    4141  struct NodeNotifierIndicator<
    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> {
     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> {
    5050  public:
    5151
    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 
     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> {
    6461    public:
    65       typedef typename GR::template NodeMap<V> Type;
     62      typedef typename Graph::template NodeMap<_Value> Parent;
     63      typedef typename Graph::template NodeMap<_Value> Type;
    6664      typedef typename Parent::Value Value;
    6765
    68       Map(const GR& _digraph) : Parent(_digraph) {}
    69       Map(const GR& _digraph, const Value& _value)
     66      Map(const Graph& _digraph) : Parent(_digraph) {}
     67      Map(const Graph& _digraph, const Value& _value)
    7068        : Parent(_digraph, _value) {}
    7169
     
    7472  };
    7573
    76   template <typename GR, typename Enable = void>
     74  template <typename Graph, typename Enable = void>
    7775  struct ArcNotifierIndicator {
    7876    typedef InvalidType Type;
    7977  };
    80   template <typename GR>
     78  template <typename Graph>
    8179  struct ArcNotifierIndicator<
    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> {
     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> {
    9088  public:
    9189
    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 
     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> {
    10499    public:
    105       typedef typename GR::template ArcMap<V> Type;
     100      typedef typename Graph::template ArcMap<_Value> Parent;
     101      typedef typename Graph::template ArcMap<_Value> Type;
    106102      typedef typename Parent::Value Value;
    107103
    108       Map(const GR& _digraph) : Parent(_digraph) {}
    109       Map(const GR& _digraph, const Value& _value)
     104      Map(const Graph& _digraph) : Parent(_digraph) {}
     105      Map(const Graph& _digraph, const Value& _value)
    110106        : Parent(_digraph, _value) {}
    111107    };
     
    113109  };
    114110
    115   template <typename GR, typename Enable = void>
     111  template <typename Graph, typename Enable = void>
    116112  struct EdgeNotifierIndicator {
    117113    typedef InvalidType Type;
    118114  };
    119   template <typename GR>
     115  template <typename Graph>
    120116  struct EdgeNotifierIndicator<
    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> {
     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> {
    129125  public:
    130126
    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 
     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> {
    143136    public:
    144       typedef typename GR::template EdgeMap<V> Type;
     137      typedef typename Graph::template EdgeMap<_Value> Parent;
     138      typedef typename Graph::template EdgeMap<_Value> Type;
    145139      typedef typename Parent::Value Value;
    146140
    147       Map(const GR& _digraph) : Parent(_digraph) {}
    148       Map(const GR& _digraph, const Value& _value)
     141      Map(const Graph& _digraph) : Parent(_digraph) {}
     142      Map(const Graph& _digraph, const Value& _value)
    149143        : Parent(_digraph, _value) {}
    150144    };
     
    211205  // Indicators for the tags
    212206
    213   template <typename GR, typename Enable = void>
     207  template <typename Graph, typename Enable = void>
    214208  struct NodeNumTagIndicator {
    215209    static const bool value = false;
    216210  };
    217211
    218   template <typename GR>
     212  template <typename Graph>
    219213  struct NodeNumTagIndicator<
    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>
     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>
    240221  struct EdgeNumTagIndicator {
    241222    static const bool value = false;
    242223  };
    243224
    244   template <typename GR>
     225  template <typename Graph>
    245226  struct EdgeNumTagIndicator<
    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>
     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>
    266234  struct FindEdgeTagIndicator {
    267235    static const bool value = false;
    268236  };
    269237
    270   template <typename GR>
     238  template <typename Graph>
    271239  struct FindEdgeTagIndicator<
    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>
     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>
    279247  struct UndirectedTagIndicator {
    280248    static const bool value = false;
    281249  };
    282250
    283   template <typename GR>
     251  template <typename Graph>
    284252  struct UndirectedTagIndicator<
    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>
     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>
    292260  struct BuildTagIndicator {
    293261    static const bool value = false;
    294262  };
    295263
    296   template <typename GR>
     264  template <typename Graph>
    297265  struct BuildTagIndicator<
    298     GR,
    299     typename enable_if<typename GR::BuildTag, void>::type
     266    Graph,
     267    typename enable_if<typename Graph::BuildTag, void>::type
    300268  > {
    301269    static const bool value = true;
  • lemon/bits/vector_map.h

    r664 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    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 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.
     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.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
     
    5757
    5858    // The graph type of the map.
    59     typedef _Graph GraphType;
     59    typedef _Graph Graph;
    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;
    7577
    7678    // The reference type of the map;
     
    7981    typedef typename Container::const_reference ConstReference;
    8082
    81   private:
    82 
    83     // The base class of the map.
    84     typedef typename Notifier::ObserverBase Parent;
    85 
    86   public:
    8783
    8884    // \brief Constructor to attach the new map into the notifier.
     
    9086    // It constructs a map and attachs it into the notifier.
    9187    // It adds all the items of the graph to the map.
    92     VectorMap(const GraphType& graph) {
     88    VectorMap(const Graph& graph) {
    9389      Parent::attach(graph.notifier(Item()));
    9490      container.resize(Parent::notifier()->maxId() + 1);
     
    9995    // It constructs a map uses a given value to initialize the map.
    10096    // It adds all the items of the graph to the map.
    101     VectorMap(const GraphType& graph, const Value& value) {
     97    VectorMap(const Graph& graph, const Value& value) {
    10298      Parent::attach(graph.notifier(Item()));
    10399      container.resize(Parent::notifier()->maxId() + 1, value);
     
    129125    // \brief Template assign operator.
    130126    //
    131     // The given parameter should conform to the ReadMap
     127    // The given parameter should be conform to the ReadMap
    132128    // concecpt and could be indiced by the current item set of
    133129    // the NodeMap. In this case the value for each item
     
    174170    // \brief Adds a new key to the map.
    175171    //
    176     // It adds a new key to the map. It is called by the observer notifier
     172    // It adds a new key to the map. It called by the observer notifier
    177173    // and it overrides the add() member function of the observer base.
    178174    virtual void add(const Key& key) {
     
    185181    // \brief Adds more new keys to the map.
    186182    //
    187     // It adds more new keys to the map. It is called by the observer notifier
     183    // It adds more new keys to the map. It called by the observer notifier
    188184    // and it overrides the add() member function of the observer base.
    189185    virtual void add(const std::vector<Key>& keys) {
     
    200196    // \brief Erase a key from the map.
    201197    //
    202     // Erase a key from the map. It is called by the observer notifier
     198    // Erase a key from the map. It called by the observer notifier
    203199    // and it overrides the erase() member function of the observer base.
    204200    virtual void erase(const Key& key) {
     
    208204    // \brief Erase more keys from the map.
    209205    //
    210     // It erases more keys from the map. It is called by the observer notifier
     206    // Erase more keys from the map. It called by the observer notifier
    211207    // and it overrides the erase() member function of the observer base.
    212208    virtual void erase(const std::vector<Key>& keys) {
     
    216212    }
    217213
    218     // \brief Build the map.
    219     //
    220     // It builds the map. It is called by the observer notifier
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
    221217    // and it overrides the build() member function of the observer base.
    222218    virtual void build() {
     
    228224    // \brief Clear the map.
    229225    //
    230     // It erases all items from the map. It is called by the observer notifier
     226    // It erase all items from the map. It called by the observer notifier
    231227    // and it overrides the clear() member function of the observer base.
    232228    virtual void clear() {
  • lemon/bits/windows.cc

    r1055 r513  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4141#include <unistd.h>
    4242#include <ctime>
    43 #ifndef WIN32
    4443#include <sys/times.h>
    45 #endif
    4644#include <sys/time.h>
    4745#endif
     
    9997      GetSystemTime(&time);
    10098      char buf1[11], buf2[9], buf3[5];
    101           if (GetDateFormat(MY_LOCALE, 0, &time,
     99          if (GetDateFormat(MY_LOCALE, 0, &time,
    102100                        ("ddd MMM dd"), buf1, 11) &&
    103101          GetTimeFormat(MY_LOCALE, 0, &time,
  • lemon/bits/windows.h

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

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

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

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

    r956 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010