COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
101 added
2 deleted
111 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

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

  • CMakeLists.txt

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

  • INSTALL

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

  • LICENSE

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

  • Makefile.am

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

  • NEWS

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

  • README

    r318 r921  
    1 ==================================================================
    2 LEMON - a Library of Efficient Models and Optimization in Networks
    3 ==================================================================
     1=====================================================================
     2LEMON - a Library for Efficient Modeling and Optimization in Networks
     3=====================================================================
    44
    55LEMON is an open source library written in C++. It provides
    … …  
    1717
    1818   Copying, distribution and modification conditions and terms.
     19
     20NEWS
     21
     22   News and version history.
    1923
    2024INSTALL
    … …  
    3438   Some example programs to make you easier to get familiar with LEMON.
    3539
     40scripts/
     41
     42   Scripts that make it easier to develop LEMON.
     43
    3644test/
    3745

  • cmake/version.cmake.in

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

  • configure.ac

    r540 r1039  
    33dnl Version information.
    44m4_define([lemon_version_number],
    5         [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     5          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
    66dnl m4_define([lemon_version_number], [])
    77m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
     8m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
    99m4_define([lemon_version], [ifelse(lemon_version_number(),
    10                            [],
    11                            [lemon_hg_path().lemon_hg_revision()],
    12                            [lemon_version_number()])])
     10                           [],
     11                           [ifelse(lemon_hg_revision(),
     12                           [],
     13                           [hg-tip],
     14                           [lemon_hg_path().lemon_hg_revision()])],
     15                           [lemon_version_number()])])
    1316
    1417AC_PREREQ([2.59])
    … …  
    2023AC_CONFIG_HEADERS([config.h lemon/config.h])
    2124
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
     25AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
    2326
    2427dnl Do compilation tests using the C++ compiler.
    … …  
    3942
    4043AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    4145AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4246
    … …  
    5357
    5458dnl Set custom compiler flags when using g++.
    55 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    56   CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
     59if test "$GXX" = yes -a "$ICC" = no; then
     60  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    5761fi
     62AC_SUBST([WARNINGCXXFLAGS])
    5863
    5964dnl Checks for libraries.
    60 #LX_CHECK_GLPK
    61 #LX_CHECK_CPLEX
    62 #LX_CHECK_SOPLEX
     65LX_CHECK_GLPK
     66LX_CHECK_CPLEX
     67LX_CHECK_SOPLEX
     68LX_CHECK_COIN
    6369
    64 dnl Disable/enable building the demo programs.
    65 AC_ARG_ENABLE([demo],
    66 AS_HELP_STRING([--enable-demo], [build the demo programs])
    67 AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
    68               [], [enable_demo=no])
    69 AC_MSG_CHECKING([whether to build the demo programs])
    70 if test x"$enable_demo" != x"no"; then
    71   AC_MSG_RESULT([yes])
    72 else
    73   AC_MSG_RESULT([no])
    74 fi
    75 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
     70AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     71AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    7672
    7773dnl Disable/enable building the binary tools.
    … …  
    8783fi
    8884AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
     85
     86dnl Support for running test cases using valgrind.
     87use_valgrind=no
     88AC_ARG_ENABLE([valgrind],
     89AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
     90              [use_valgrind=yes])
     91
     92if [[ "$use_valgrind" = "yes" ]]; then
     93  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
     94
     95  if [[ "$HAVE_VALGRIND" = "no" ]]; then
     96    AC_MSG_ERROR([Valgrind not found in PATH.])
     97  fi
     98fi
     99AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    89100
    90101dnl Checks for header files.
    … …  
    104115dnl Add dependencies on files generated by configure.
    105116AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
    106   ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
     117  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
    107118
    108119AC_CONFIG_FILES([
    109120Makefile
     121demo/Makefile
    110122cmake/version.cmake
    111123doc/Doxyfile
     124doc/mainpage.dox
    112125lemon/lemon.pc
    113126])
    … …  
    121134echo
    122135echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     136echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124137echo
    125138echo Compiler supports long long... : $long_long_found
    126139echo
    127 #echo GLPK support.................. : $lx_glpk_found
    128 #echo CPLEX support................. : $lx_cplex_found
    129 #echo SOPLEX support................ : $lx_soplex_found
    130 #echo
    131 echo Build demo programs........... : $enable_demo
     140echo GLPK support.................. : $lx_glpk_found
     141echo CPLEX support................. : $lx_cplex_found
     142echo SOPLEX support................ : $lx_soplex_found
     143echo CLP support................... : $lx_clp_found
     144echo CBC support................... : $lx_cbc_found
     145echo
    132146echo Build additional tools........ : $enable_tools
     147echo Use valgrind for tests........ : $use_valgrind
    133148echo
    134149echo The packace will be installed in

  • demo/CMakeLists.txt

    r539 r726  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
     2  ${PROJECT_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    55
    6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(
     7  ${PROJECT_BINARY_DIR}/lemon
     8)
    79
    810SET(DEMOS
    911  arg_parser_demo
    1012  graph_to_eps_demo
    11   lgf_demo)
     13  lgf_demo
     14)
    1215
    1316FOREACH(DEMO_NAME ${DEMOS})
    1417  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
    1518  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
    16 ENDFOREACH(DEMO_NAME)
     19ENDFOREACH()

  • demo/Makefile.am

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

  • demo/arg_parser_demo.cc

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

  • demo/graph_to_eps_demo.cc

    r313 r659  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    8686    coords(coords).
    8787    title("Sample .eps figure").
    88     copyright("(C) 2003-2008 LEMON Project").
     88    copyright("(C) 2003-2009 LEMON Project").
    8989    run();
    9090
    … …  
    9393    coords(coords).
    9494    title("Sample .eps figure").
    95     copyright("(C) 2003-2008 LEMON Project").
     95    copyright("(C) 2003-2009 LEMON Project").
    9696    absoluteNodeSizes().absoluteArcWidths().
    9797    nodeScale(2).nodeSizes(sizes).
    … …  
    106106  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
    107107    title("Sample .eps figure (with arrowheads)").
    108     copyright("(C) 2003-2008 LEMON Project").
     108    copyright("(C) 2003-2009 LEMON Project").
    109109    absoluteNodeSizes().absoluteArcWidths().
    110110    nodeColors(composeMap(palette,colors)).
    … …  
    133133  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
    134134    title("Sample .eps figure (parallel arcs)").
    135     copyright("(C) 2003-2008 LEMON Project").
     135    copyright("(C) 2003-2009 LEMON Project").
    136136    absoluteNodeSizes().absoluteArcWidths().
    137137    nodeShapes(shapes).
    … …  
    148148  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
    149149    title("Sample .eps figure (parallel arcs and arrowheads)").
    150     copyright("(C) 2003-2008 LEMON Project").
     150    copyright("(C) 2003-2009 LEMON Project").
    151151    absoluteNodeSizes().absoluteArcWidths().
    152152    nodeScale(2).nodeSizes(sizes).
    … …  
    164164  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
    165165    title("Sample .eps figure (fits to A4)").
    166     copyright("(C) 2003-2008 LEMON Project").
     166    copyright("(C) 2003-2009 LEMON Project").
    167167    scaleToA4().
    168168    absoluteNodeSizes().absoluteArcWidths().
    … …  
    183183  ListDigraph::NodeMap<Point> hcoords(h);
    184184
    185   int cols=int(sqrt(double(palette.size())));
     185  int cols=int(std::sqrt(double(palette.size())));
    186186  for(int i=0;i<int(paletteW.size());i++) {
    187187    Node n=h.addNode();
    … …  
    194194    scale(60).
    195195    title("Sample .eps figure (Palette demo)").
    196     copyright("(C) 2003-2008 LEMON Project").
     196    copyright("(C) 2003-2009 LEMON Project").
    197197    coords(hcoords).
    198198    absoluteNodeSizes().absoluteArcWidths().

  • demo/lgf_demo.cc

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

  • doc/CMakeLists.txt

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

  • doc/Doxyfile.in

    r316 r1039  
    1 # Doxyfile 1.5.7.1
     1# Doxyfile 1.7.3
    22
    33#---------------------------------------------------------------------------
    … …  
    55#---------------------------------------------------------------------------
    66DOXYFILE_ENCODING      = UTF-8
    7 PROJECT_NAME           = @PACKAGE_NAME@
    8 PROJECT_NUMBER         = @PACKAGE_VERSION@
     7PROJECT_NAME           =
     8PROJECT_NUMBER         =
     9PROJECT_BRIEF          =
     10PROJECT_LOGO           =
    911OUTPUT_DIRECTORY       =
    1012CREATE_SUBDIRS         = NO
    … …  
    2224QT_AUTOBRIEF           = NO
    2325MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2526INHERIT_DOCS           = NO
    2627SEPARATE_MEMBER_PAGES  = NO
    … …  
    3132OPTIMIZE_FOR_FORTRAN   = NO
    3233OPTIMIZE_OUTPUT_VHDL   = NO
     34EXTENSION_MAPPING      =
    3335BUILTIN_STL_SUPPORT    = YES
    3436CPP_CLI_SUPPORT        = NO
    … …  
    5658HIDE_SCOPE_NAMES       = YES
    5759SHOW_INCLUDE_FILES     = YES
     60FORCE_LOCAL_INCLUDES   = NO
    5861INLINE_INFO            = YES
    5962SORT_MEMBER_DOCS       = NO
    6063SORT_BRIEF_DOCS        = NO
     64SORT_MEMBERS_CTORS_1ST = NO
    6165SORT_GROUP_NAMES       = NO
    6266SORT_BY_SCOPE_NAME     = NO
     67STRICT_PROTO_MATCHING  = NO
    6368GENERATE_TODOLIST      = YES
    6469GENERATE_TESTLIST      = YES
    … …  
    6772ENABLED_SECTIONS       =
    6873MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     74SHOW_USED_FILES        = NO
    7075SHOW_DIRECTORIES       = YES
    7176SHOW_FILES             = YES
    7277SHOW_NAMESPACES        = YES
    7378FILE_VERSION_FILTER    =
    74 LAYOUT_FILE            = DoxygenLayout.xml
     79LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
    7580#---------------------------------------------------------------------------
    7681# configuration options related to warning and progress messages
    … …  
    9297                         "@abs_top_srcdir@/demo" \
    9398                         "@abs_top_srcdir@/tools" \
    94                          "@abs_top_srcdir@/test/test_tools.h"
     99                         "@abs_top_srcdir@/test/test_tools.h" \
     100                         "@abs_top_builddir@/doc/mainpage.dox" \
     101                         "@abs_top_builddir@/doc/references.dox"
    95102INPUT_ENCODING         = UTF-8
    96103FILE_PATTERNS          = *.h \
    … …  
    112119FILTER_PATTERNS        =
    113120FILTER_SOURCE_FILES    = NO
     121FILTER_SOURCE_PATTERNS =
    114122#---------------------------------------------------------------------------
    115123# configuration options related to source browsing
    116124#---------------------------------------------------------------------------
    117 SOURCE_BROWSER         = NO
     125SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
    118126INLINE_SOURCES         = NO
    119127STRIP_CODE_COMMENTS    = YES
    … …  
    138146HTML_FOOTER            =
    139147HTML_STYLESHEET        =
     148HTML_COLORSTYLE_HUE    = 220
     149HTML_COLORSTYLE_SAT    = 100
     150HTML_COLORSTYLE_GAMMA  = 80
     151HTML_TIMESTAMP         = YES
    140152HTML_ALIGN_MEMBERS     = YES
    141 HTML_DYNAMIC_SECTIONS  = NO
     153HTML_DYNAMIC_SECTIONS  = YES
    142154GENERATE_DOCSET        = NO
    143155DOCSET_FEEDNAME        = "Doxygen generated docs"
    144156DOCSET_BUNDLE_ID       = org.doxygen.Project
     157DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
     158DOCSET_PUBLISHER_NAME  = Publisher
    145159GENERATE_HTMLHELP      = NO
    146160CHM_FILE               =
    … …  
    154168QHP_NAMESPACE          = org.doxygen.Project
    155169QHP_VIRTUAL_FOLDER     = doc
     170QHP_CUST_FILTER_NAME   =
     171QHP_CUST_FILTER_ATTRS  =
     172QHP_SECT_FILTER_ATTRS  =
    156173QHG_LOCATION           =
     174GENERATE_ECLIPSEHELP   = NO
     175ECLIPSE_DOC_ID         = org.doxygen.Project
    157176DISABLE_INDEX          = NO
    158177ENUM_VALUES_PER_LINE   = 4
    159178GENERATE_TREEVIEW      = NO
     179USE_INLINE_TREES       = NO
    160180TREEVIEW_WIDTH         = 250
     181EXT_LINKS_IN_WINDOW    = NO
    161182FORMULA_FONTSIZE       = 10
     183FORMULA_TRANSPARENT    = YES
     184USE_MATHJAX            = NO
     185MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
     186SEARCHENGINE           = YES
     187SERVER_BASED_SEARCH    = NO
    162188#---------------------------------------------------------------------------
    163189# configuration options related to the LaTeX output
    … …  
    176202LATEX_BATCHMODE        = NO
    177203LATEX_HIDE_INDICES     = NO
     204LATEX_SOURCE_CODE      = NO
    178205#---------------------------------------------------------------------------
    179206# configuration options related to the RTF output
    … …  
    224251SKIP_FUNCTION_MACROS   = YES
    225252#---------------------------------------------------------------------------
    226 # Configuration::additions related to external references   
    227 #---------------------------------------------------------------------------
    228 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
     253# Configuration::additions related to external references
     254#---------------------------------------------------------------------------
     255TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
    229256GENERATE_TAGFILE       = html/lemon.tag
    230257ALLEXTERNALS           = NO
    … …  
    238265HIDE_UNDOC_RELATIONS   = YES
    239266HAVE_DOT               = YES
     267DOT_NUM_THREADS        = 0
    240268DOT_FONTNAME           = FreeSans
    241269DOT_FONTSIZE           = 10
    … …  
    255283DOT_PATH               =
    256284DOTFILE_DIRS           =
     285MSCFILE_DIRS           =
    257286DOT_GRAPH_MAX_NODES    = 50
    258287MAX_DOT_GRAPH_DEPTH    = 0
    … …  
    261290GENERATE_LEGEND        = YES
    262291DOT_CLEANUP            = YES
    263 #---------------------------------------------------------------------------
    264 # Configuration::additions related to the search engine   
    265 #---------------------------------------------------------------------------
    266 SEARCHENGINE           = NO

  • doc/DoxygenLayout.xml

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

  • doc/Makefile.am

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

  • doc/coding_style.dox

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

  • doc/dirs.dox

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

  • doc/groups.dox

    r318 r963  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2224*/
    2325
    … …  
    6163
    6264/**
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6466@ingroup graphs
    65 \brief Graph types between real graphs and graph adaptors.
    66 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
    70138*/
    71139
    … …  
    75143\brief Map structures implemented in LEMON.
    76144
    77 This group describes the map structures implemented in LEMON.
     145This group contains the map structures implemented in LEMON.
    78146
    79147LEMON provides several special purpose maps and map adaptors that e.g. combine
    … …  
    88156\brief Special graph-related maps.
    89157
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     158This group contains maps that are specifically designed to assign
     159values to the nodes and arcs/edges of graphs.
     160
     161If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     162\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92163*/
    93164
    … …  
    97168\brief Tools to create new maps from existing ones
    98169
    99 This group describes map adaptors that are used to create "implicit"
     170This group contains map adaptors that are used to create "implicit"
    100171maps from other maps.
    101172
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     173Most of them are \ref concepts::ReadMap "read-only maps".
    103174They can make arithmetic and logical operations between one or two maps
    104175(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    156227
    157228/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166229@defgroup paths Path Structures
    167230@ingroup datas
    168231\brief %Path structures implemented in LEMON.
    169232
    170 This group describes the path structures implemented in LEMON.
     233This group contains the path structures implemented in LEMON.
    171234
    172235LEMON provides flexible data structures to work with paths.
    … …  
    176239any kind of path structure.
    177240
    178 \sa lemon::concepts::Path
     241\sa \ref concepts::Path "Path concept"
     242*/
     243
     244/**
     245@defgroup heaps Heap Structures
     246@ingroup datas
     247\brief %Heap structures implemented in LEMON.
     248
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
    179263*/
    180264
    … …  
    184268\brief Auxiliary data structures implemented in LEMON.
    185269
    186 This group describes some data structures implemented in LEMON in
     270This group contains some data structures implemented in LEMON in
    187271order to make it easier to implement combinatorial algorithms.
    188272*/
    189273
    190274/**
     275@defgroup geomdat Geometric Data Structures
     276@ingroup auxdat
     277\brief Geometric data structures implemented in LEMON.
     278
     279This group contains geometric data structures implemented in LEMON.
     280
     281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     282   vector with the usual operations.
     283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     284   rectangular bounding box of a set of \ref lemon::dim2::Point
     285   "dim2::Point"'s.
     286*/
     287
     288/**
    191289@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     290\brief This group contains the several algorithms
    193291implemented in LEMON.
    194292
    195 This group describes the several algorithms
     293This group contains the several algorithms
    196294implemented in LEMON.
    197295*/
    … …  
    202300\brief Common graph search algorithms.
    203301
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     302This group contains the common graph search algorithms, namely
     303\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     304\ref clrs01algorithms.
    206305*/
    207306
    … …  
    211310\brief Algorithms for finding shortest paths.
    212311
    213 This group describes the algorithms for finding shortest paths in graphs.
     312This group contains the algorithms for finding shortest paths in digraphs
     313\ref clrs01algorithms.
     314
     315 - \ref Dijkstra algorithm for finding shortest paths from a source node
     316   when all arc lengths are non-negative.
     317 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     318   from a source node when arc lenghts can be either positive or negative,
     319   but the digraph should not contain directed cycles with negative total
     320   length.
     321 - \ref Suurballe A successive shortest path algorithm for finding
     322   arc-disjoint paths between two nodes having minimum total length.
     323*/
     324
     325/**
     326@defgroup spantree Minimum Spanning Tree Algorithms
     327@ingroup algs
     328\brief Algorithms for finding minimum cost spanning trees and arborescences.
     329
     330This group contains the algorithms for finding minimum cost spanning
     331trees and arborescences \ref clrs01algorithms.
    214332*/
    215333
    … …  
    219337\brief Algorithms for finding maximum flows.
    220338
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    234 
    235 LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     339This group contains the algorithms for finding maximum flows and
     340feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     341
     342The \e maximum \e flow \e problem is to find a flow of maximum value between
     343a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     344digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     345\f$s, t \in V\f$ source and target nodes.
     346A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     347following optimization problem.
     348
     349\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     350\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     351    \quad \forall u\in V\setminus\{s,t\} \f]
     352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
     353
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
     358
     359\ref Circulation is a preflow push-relabel algorithm implemented directly
     360for finding feasible circulations, which is a somewhat different problem,
     361but it is strongly related to maximum flow.
     362For more information, see \ref Circulation.
     363*/
     364
     365/**
     366@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    249367@ingroup algs
    250368
    251369\brief Algorithms for finding minimum cost flows and circulations.
    252370
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
     371This group contains the algorithms for finding minimum cost flows and
     372circulations \ref amo93networkflows. For more information about this
     373problem and its dual solution, see \ref min_cost_flow
     374"Minimum Cost Flow Problem".
     375
     376LEMON contains several algorithms for this problem.
     377 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     378   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     379 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     380   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     381   \ref bunnagel98efficient.
     382 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     383   shortest path method \ref edmondskarp72theoretical.
     384 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     385   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     386
     387In general NetworkSimplex is the most efficient implementation,
     388but in special cases other algorithms could be faster.
     389For example, if the total supply and/or capacities are rather small,
     390CapacityScaling is usually the fastest algorithm (without effective scaling).
    255391*/
    256392
    … …  
    261397\brief Algorithms for finding minimum cut in graphs.
    262398
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     399This group contains the algorithms for finding minimum cut in graphs.
     400
     401The \e minimum \e cut \e problem is to find a non-empty and non-complete
     402\f$X\f$ subset of the nodes with minimum overall capacity on
     403outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     404\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269405cut is the \f$X\f$ solution of the next optimization problem:
    270406
    271407\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     408    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    273409
    274410LEMON contains several algorithms related to minimum cut problems:
    275411
    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
     412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     413  in directed graphs.
     414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     415  all-pairs minimum cut in undirected graphs.
    282416
    283417If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
    285 */
    286 
    287 /**
    288 @defgroup graph_prop Connectivity and Other Graph Properties
    289 @ingroup algs
    290 \brief Algorithms for discovering the graph properties
    291 
    292 This group describes the algorithms for discovering the graph properties
    293 like connectivity, bipartiteness, euler property, simplicity etc.
    294 
    295 \image html edge_biconnected_components.png
    296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    297 */
    298 
    299 /**
    300 @defgroup planar Planarity Embedding and Drawing
    301 @ingroup algs
    302 \brief Algorithms for planarity checking, embedding and drawing
    303 
    304 This group describes the algorithms for planarity checking,
    305 embedding and drawing.
    306 
    307 \image html planar.png
    308 \image latex planar.eps "Plane graph" width=\textwidth
     418see the \ref max_flow "maximum flow problem".
     419*/
     420
     421/**
     422@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     423@ingroup algs
     424\brief Algorithms for finding minimum mean cycles.
     425
     426This group contains the algorithms for finding minimum mean cycles
     427\ref clrs01algorithms, \ref amo93networkflows.
     428
     429The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     430of minimum mean length (cost) in a digraph.
     431The mean length of a cycle is the average length of its arcs, i.e. the
     432ratio between the total length of the cycle and the number of arcs on it.
     433
     434This problem has an important connection to \e conservative \e length
     435\e functions, too. A length function on the arcs of a digraph is called
     436conservative if and only if there is no directed cycle of negative total
     437length. For an arbitrary length function, the negative of the minimum
     438cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     439arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     440function.
     441
     442LEMON contains three algorithms for solving the minimum mean cycle problem:
     443- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     444  \ref dasdan98minmeancycle.
     445- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     446  version of Karp's algorithm \ref dasdan98minmeancycle.
     447- \ref HowardMmc Howard's policy iteration algorithm
     448  \ref dasdan98minmeancycle.
     449
     450In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     451most efficient one, though the best known theoretical bound on its running
     452time is exponential.
     453Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     454run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     455typically faster due to the applied early termination scheme.
    309456*/
    310457
    … …  
    314461\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315462
    316 This group contains algorithm objects and functions to calculate
     463This group contains the algorithms for calculating
    317464matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
     465finding a subset of the edges for which each node has at most one incident
     466edge.
    319467
    320468There are several different algorithms for calculate matchings in
    321469graphs.  The matching problems in bipartite graphs are generally
    322470easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     471can be finding maximum cardinality, maximum weight or minimum cost
    324472matching. The search can be constrained to find perfect or
    325473maximum cardinality matching.
    326474
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
    347 
    348 \image html bipartite_matching.png
    349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    350 */
    351 
    352 /**
    353 @defgroup spantree Minimum Spanning Tree Algorithms
    354 @ingroup algs
    355 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    356 
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     475The matching algorithms implemented in LEMON:
     476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     477  maximum cardinality matching in general graphs.
     478- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     479  maximum weighted matching in general graphs.
     480- \ref MaxWeightedPerfectMatching
     481  Edmond's blossom shrinking algorithm for calculating maximum weighted
     482  perfect matching in general graphs.
     483- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     484  maximum cardinality fractional matching in general graphs.
     485- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     486  maximum weighted fractional matching in general graphs.
     487- \ref MaxWeightedPerfectFractionalMatching
     488  Augmenting path algorithm for calculating maximum weighted
     489  perfect fractional matching in general graphs.
     490
     491\image html matching.png
     492\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     493*/
     494
     495/**
     496@defgroup graph_properties Connectivity and Other Graph Properties
     497@ingroup algs
     498\brief Algorithms for discovering the graph properties
     499
     500This group contains the algorithms for discovering the graph properties
     501like connectivity, bipartiteness, euler property, simplicity etc.
     502
     503\image html connected_components.png
     504\image latex connected_components.eps "Connected components" width=\textwidth
     505*/
     506
     507/**
     508@defgroup planar Planarity Embedding and Drawing
     509@ingroup algs
     510\brief Algorithms for planarity checking, embedding and drawing
     511
     512This group contains the algorithms for planarity checking,
     513embedding and drawing.
     514
     515\image html planar.png
     516\image latex planar.eps "Plane graph" width=\textwidth
    359517*/
    360518
    … …  
    364522\brief Auxiliary algorithms implemented in LEMON.
    365523
    366 This group describes some algorithms implemented in LEMON
     524This group contains some algorithms implemented in LEMON
    367525in order to make it easier to implement complex algorithms.
    368526*/
    369527
    370528/**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
     529@defgroup gen_opt_group General Optimization Tools
     530\brief This group contains some general optimization frameworks
    376531implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     532
     533This group contains some general optimization frameworks
    382534implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented in LEMON.
    386 */
    387 
    388 /**
    389 @defgroup lp_group Lp and Mip Solvers
     535*/
     536
     537/**
     538@defgroup lp_group LP and MIP Solvers
    390539@ingroup gen_opt_group
    391 \brief Lp and Mip solver interfaces for LEMON.
    392 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
    396 */
    397 
    398 /**
    399 @defgroup lp_utils Tools for Lp and Mip Solvers
    400 @ingroup lp_group
    401 \brief Helper tools to the Lp and Mip solvers.
    402 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
     540\brief LP and MIP solver interfaces for LEMON.
     541
     542This group contains LP and MIP solver interfaces for LEMON.
     543Various LP solvers could be used in the same manner with this
     544high-level interface.
     545
     546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     547\ref cplex, \ref soplex.
    413548*/
    414549
    … …  
    425560\brief Simple basic graph utilities.
    426561
    427 This group describes some simple basic graph utilities.
     562This group contains some simple basic graph utilities.
    428563*/
    429564
    … …  
    433568\brief Tools for development, debugging and testing.
    434569
    435 This group describes several useful tools for development,
     570This group contains several useful tools for development,
    436571debugging and testing.
    437572*/
    … …  
    442577\brief Simple tools for measuring the performance of algorithms.
    443578
    444 This group describes simple tools for measuring the performance
     579This group contains simple tools for measuring the performance
    445580of algorithms.
    446581*/
    … …  
    451586\brief Exceptions defined in LEMON.
    452587
    453 This group describes the exceptions defined in LEMON.
     588This group contains the exceptions defined in LEMON.
    454589*/
    455590
    … …  
    458593\brief Graph Input-Output methods
    459594
    460 This group describes the tools for importing and exporting graphs
     595This group contains the tools for importing and exporting graphs
    461596and graph related data. Now it supports the \ref lgf-format
    462597"LEMON Graph Format", the \c DIMACS format and the encapsulated
    … …  
    465600
    466601/**
    467 @defgroup lemon_io LEMON Input-Output
     602@defgroup lemon_io LEMON Graph Format
    468603@ingroup io_group
    469604\brief Reading and writing LEMON Graph Format.
    470605
    471 This group describes methods for reading and writing
     606This group contains methods for reading and writing
    472607\ref lgf-format "LEMON Graph Format".
    473608*/
    … …  
    478613\brief General \c EPS drawer and graph exporter
    479614
    480 This group describes general \c EPS drawing methods and special
     615This group contains general \c EPS drawing methods and special
    481616graph exporting tools.
     617*/
     618
     619/**
     620@defgroup dimacs_group DIMACS Format
     621@ingroup io_group
     622\brief Read and write files in DIMACS format
     623
     624Tools to read a digraph from or write it to a file in DIMACS format data.
     625*/
     626
     627/**
     628@defgroup nauty_group NAUTY Format
     629@ingroup io_group
     630\brief Read \e Nauty format
     631
     632Tool to read graphs from \e Nauty format data.
    482633*/
    483634
    … …  
    486637\brief Skeleton classes and concept checking classes
    487638
    488 This group describes the data/algorithm skeletons and concept checking
     639This group contains the data/algorithm skeletons and concept checking
    489640classes implemented in LEMON.
    490641
    … …  
    516667\brief Skeleton and concept checking classes for graph structures
    517668
    518 This group describes the skeletons and concept checking classes of LEMON's
    519 graph structures and helper classes used to implement these.
     669This group contains the skeletons and concept checking classes of
     670graph structures.
    520671*/
    521672
    … …  
    525676\brief Skeleton and concept checking classes for maps
    526677
    527 This group describes the skeletons and concept checking classes of maps.
     678This group contains the skeletons and concept checking classes of maps.
     679*/
     680
     681/**
     682@defgroup tools Standalone Utility Applications
     683
     684Some utility applications are listed here.
     685
     686The standard compilation procedure (<tt>./configure;make</tt>) will compile
     687them, as well.
    528688*/
    529689
    … …  
    531691\anchor demoprograms
    532692
    533 @defgroup demos Demo programs
     693@defgroup demos Demo Programs
    534694
    535695Some demo programs are listed here. Their full source codes can be found in
    536696the \c demo subdirectory of the source tree.
    537697
    538 It order to compile them, use <tt>--enable-demo</tt> configure option when
    539 build the library.
    540 */
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 
     698In order to compile them, use the <tt>make demo</tt> or the
     699<tt>make check</tt> commands.
     700*/
     701
     702}

  • doc/lgf.dox

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

  • doc/license.dox

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

  • doc/migration.dox

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

  • doc/named-param.dox

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

  • doc/namespaces.dox

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

  • doc/template.h

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

  • lemon/CMakeLists.txt

    r539 r1012  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
     2  ${PROJECT_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
    … …  
    99)
    1010
    11 ADD_LIBRARY(lemon
     11CONFIGURE_FILE(
     12  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
     13  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     14  @ONLY
     15)
     16
     17SET(LEMON_SOURCES
    1218  arg_parser.cc
    1319  base.cc
    1420  color.cc
     21  lp_base.cc
     22  lp_skeleton.cc
    1523  random.cc
    1624  bits/windows.cc
    1725)
    1826
     27IF(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()
     35ENDIF()
     36
     37IF(LEMON_HAVE_CPLEX)
     38  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
     39  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
     40ENDIF()
     41
     42IF(LEMON_HAVE_CLP)
     43  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
     44  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     45ENDIF()
     46
     47IF(LEMON_HAVE_CBC)
     48  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
     49  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
     50ENDIF()
     51
     52ADD_LIBRARY(lemon ${LEMON_SOURCES})
     53IF(UNIX)
     54  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
     55ENDIF()
     56
    1957INSTALL(
    2058  TARGETS lemon
    2159  ARCHIVE DESTINATION lib
    22   COMPONENT library)
     60  COMPONENT library
     61)
    2362
    2463INSTALL(
    … …  
    2665  DESTINATION include/lemon
    2766  COMPONENT headers
    28   FILES_MATCHING PATTERN "*.h")
     67  FILES_MATCHING PATTERN "*.h"
     68)
    2969
    3070INSTALL(
    3171  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
    3272  DESTINATION include/lemon
    33   COMPONENT headers)
     73  COMPONENT headers
     74)
     75
     76INSTALL(
     77  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
     78  DESTINATION lib/pkgconfig
     79)
     80

  • lemon/Makefile.am

    r1086 r1090  
    22        lemon/lemon.pc.in \
    33        lemon/lemon.pc.cmake \
    4         lemon/CMakeLists.txt
     4        lemon/CMakeLists.txt \
     5        lemon/config.h.cmake
    56
    67pkgconfig_DATA += lemon/lemon.pc
    … …  
    910
    1011lemon_libemon_la_SOURCES = \
    11         lemon/arg_parser.cc \
    12         lemon/base.cc \
    13         lemon/color.cc \
    14         lemon/random.cc \
     12        lemon/arg_parser.cc \
     13        lemon/base.cc \
     14        lemon/color.cc \
     15        lemon/lp_base.cc \
     16        lemon/lp_skeleton.cc \
     17        lemon/random.cc \
    1518        lemon/bits/windows.cc
    1619
    17 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    18 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     20nodist_lemon_HEADERS = lemon/config.h   
    1921
    20 nodist_lemon_HEADERS = lemon/config.h
     22lemon_libemon_la_CXXFLAGS = \
     23        $(AM_CXXFLAGS) \
     24        $(GLPK_CFLAGS) \
     25        $(CPLEX_CFLAGS) \
     26        $(SOPLEX_CXXFLAGS) \
     27        $(CLP_CXXFLAGS) \
     28        $(CBC_CXXFLAGS)
     29
     30lemon_libemon_la_LDFLAGS = \
     31        $(GLPK_LIBS) \
     32        $(CPLEX_LIBS) \
     33        $(SOPLEX_LIBS) \
     34        $(CLP_LIBS) \
     35        $(CBC_LIBS)
     36
     37if HAVE_GLPK
     38lemon_libemon_la_SOURCES += lemon/glpk.cc
     39endif
     40
     41if HAVE_CPLEX
     42lemon_libemon_la_SOURCES += lemon/cplex.cc
     43endif
     44
     45if HAVE_SOPLEX
     46lemon_libemon_la_SOURCES += lemon/soplex.cc
     47endif
     48
     49if HAVE_CLP
     50lemon_libemon_la_SOURCES += lemon/clp.cc
     51endif
     52
     53if HAVE_CBC
     54lemon_libemon_la_SOURCES += lemon/cbc.cc
     55endif
    2156
    2257lemon_HEADERS += \
    23         lemon/arg_parser.h \
     58        lemon/adaptors.h \
     59        lemon/arg_parser.h \
    2460        lemon/assert.h \
    25         lemon/bfs.h \
    26         lemon/bin_heap.h \
    27         lemon/color.h \
     61        lemon/bellman_ford.h \
     62        lemon/bfs.h \
     63        lemon/bin_heap.h \
     64        lemon/binomial_heap.h \
     65        lemon/bucket_heap.h \
     66        lemon/capacity_scaling.h \
     67        lemon/cbc.h \
     68        lemon/circulation.h \
     69        lemon/clp.h \
     70        lemon/color.h \
    2871        lemon/concept_check.h \
    29         lemon/counter.h \
     72        lemon/connectivity.h \
    3073        lemon/core.h \
    31         lemon/dfs.h \
    32         lemon/dijkstra.h \
    33         lemon/dim2.h \
     74        lemon/cost_scaling.h \
     75        lemon/counter.h \
     76        lemon/cplex.h \
     77        lemon/cycle_canceling.h \
     78        lemon/dfs.h \
     79        lemon/dheap.h \
     80        lemon/dijkstra.h \
     81        lemon/dim2.h \
     82        lemon/dimacs.h \
     83        lemon/edge_set.h \
     84        lemon/elevator.h \
    3485        lemon/error.h \
    35         lemon/graph_to_eps.h \
     86        lemon/euler.h \
     87        lemon/fib_heap.h \
     88        lemon/fractional_matching.h \
     89        lemon/full_graph.h \
     90        lemon/glpk.h \
     91        lemon/gomory_hu.h \
     92        lemon/graph_to_eps.h \
     93        lemon/grid_graph.h \
     94        lemon/hartmann_orlin_mmc.h \
     95        lemon/howard_mmc.h \
     96        lemon/hypercube_graph.h \
     97        lemon/karp_mmc.h \
    3698        lemon/kruskal.h \
     99        lemon/hao_orlin.h \
    37100        lemon/lgf_reader.h \
    38101        lemon/lgf_writer.h \
    39102        lemon/list_graph.h \
     103        lemon/lp.h \
     104        lemon/lp_base.h \
     105        lemon/lp_skeleton.h \
    40106        lemon/maps.h \
     107        lemon/matching.h \
    41108        lemon/math.h \
     109        lemon/min_cost_arborescence.h \
     110        lemon/nauty_reader.h \
     111        lemon/network_simplex.h \
     112        lemon/pairing_heap.h \
    42113        lemon/path.h \
    43         lemon/random.h \
     114        lemon/planarity.h \
     115        lemon/preflow.h \
     116        lemon/quad_heap.h \
     117        lemon/radix_heap.h \
     118        lemon/radix_sort.h \
     119        lemon/random.h \
    44120        lemon/smart_graph.h \
    45         lemon/time_measure.h \
    46         lemon/tolerance.h \
     121        lemon/soplex.h \
     122        lemon/static_graph.h \
     123        lemon/suurballe.h \
     124        lemon/time_measure.h \
     125        lemon/tolerance.h \
    47126        lemon/unionfind.h \
    48127        lemon/bits/windows.h
    … …  
    51130        lemon/bits/alteration_notifier.h \
    52131        lemon/bits/array_map.h \
    53         lemon/bits/base_extender.h \
    54         lemon/bits/bezier.h \
     132        lemon/bits/bezier.h \
    55133        lemon/bits/default_map.h \
    56         lemon/bits/enable_if.h \
     134        lemon/bits/edge_set_extender.h \
     135        lemon/bits/enable_if.h \
     136        lemon/bits/graph_adaptor_extender.h \
    57137        lemon/bits/graph_extender.h \
    58138        lemon/bits/map_extender.h \
    59139        lemon/bits/path_dump.h \
     140        lemon/bits/solver_bits.h \
    60141        lemon/bits/traits.h \
     142        lemon/bits/variant.h \
    61143        lemon/bits/vector_map.h
    62144

  • lemon/arg_parser.cc

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

  • lemon/arg_parser.h

    r311 r959  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3535namespace lemon {
    3636
     37  ///Exception used by ArgParser
     38
     39  ///Exception used by ArgParser.
     40  ///
     41  class ArgParserException : public Exception {
     42  public:
     43    /// Reasons for failure
     44
     45    /// Reasons for failure.
     46    ///
     47    enum Reason {
     48      HELP,         ///< <tt>--help</tt> option was given.
     49      UNKNOWN_OPT,  ///< Unknown option was given.
     50      INVALID_OPT   ///< Invalid combination of options.
     51    };
     52
     53  private:
     54    Reason _reason;
     55
     56  public:
     57    ///Constructor
     58    ArgParserException(Reason r) throw() : _reason(r) {}
     59    ///Virtual destructor
     60    virtual ~ArgParserException() throw() {}
     61    ///A short description of the exception
     62    virtual const char* what() const throw() {
     63      switch(_reason)
     64        {
     65        case HELP:
     66          return "lemon::ArgParseException: ask for help";
     67          break;
     68        case UNKNOWN_OPT:
     69          return "lemon::ArgParseException: unknown option";
     70          break;
     71        case INVALID_OPT:
     72          return "lemon::ArgParseException: invalid combination of options";
     73          break;
     74        }
     75      return "";
     76    }
     77    ///Return the reason for the failure
     78    Reason reason() const {return _reason; }
     79  };
     80
     81
    3782  ///Command line arguments parser
    3883
    … …  
    116161                    const std::string &help,
    117162                    void (*func)(void *),void *data);
     163
     164    bool _exit_on_problems;
     165
     166    void _terminate(ArgParserException::Reason reason) const;
    118167
    119168  public:
    … …  
    381430    const std::vector<std::string> &files() const { return _file_args; }
    382431
     432    ///Throw instead of exit in case of problems
     433    void throwOnProblems()
     434    {
     435      _exit_on_problems=false;
     436    }
    383437  };
    384438}

  • lemon/assert.h

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

  • lemon/base.cc

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

  • lemon/bfs.h

    r301 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
    … …  
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     68    ///Instantiates a \c ProcessedMap.
     69
     70    ///This function instantiates a \ref ProcessedMap.
    7071    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     72    ///we would like to define the \ref ProcessedMap
    7273#ifdef DOXYGEN
    7374    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     88    ///Instantiates a \c ReachedMap.
     89
     90    ///This function instantiates a \ref ReachedMap.
    8991    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     92    ///we would like to define the \ref ReachedMap.
    9193    static ReachedMap *createReachedMap(const Digraph &g)
    9294    {
    … …  
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     103    ///Instantiates a \c DistMap.
     104
     105    ///This function instantiates a \ref DistMap.
    104106    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     107    ///\ref DistMap.
    106108    static DistMap *createDistMap(const Digraph &g)
    107109    {
    … …  
    120122  ///
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    127   ///See \ref BfsDefaultTraits for the documentation of
    128   ///a Bfs traits class.
     124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref BfsDefaultTraits
     127  ///"BfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    129130#ifdef DOXYGEN
    130131  template <typename GR,
    … …  
    152153    typedef PredMapPath<Digraph, PredMap> Path;
    153154
    154     ///The traits class.
     155    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155156    typedef TR Traits;
    156157
    … …  
    214215    typedef Bfs Create;
    215216
    216     ///\name Named template parameters
     217    ///\name Named Template Parameters
    217218
    218219    ///@{
    … …  
    228229    };
    229230    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     231    ///\c PredMap type.
    231232    ///
    232233    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     234    ///\c PredMap type.
     235    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    234236    template <class T>
    235237    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    247249    };
    248250    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     251    ///\c DistMap type.
    250252    ///
    251253    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     254    ///\c DistMap type.
     255    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    253256    template <class T>
    254257    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266269    };
    267270    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     271    ///\c ReachedMap type.
    269272    ///
    270273    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     274    ///\c ReachedMap type.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272277    template <class T>
    273278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    285290    };
    286291    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     292    ///\c ProcessedMap type.
    288293    ///
    289294    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     295    ///\c ProcessedMap type.
     296    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    291297    template <class T>
    292298    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    303309    };
    304310    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     311    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306312    ///
    307313    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     314    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309315    ///If you don't set it explicitly, it will be automatically allocated.
    310316    struct SetStandardProcessedMap :
    … …  
    341347
    342348    ///Sets the map that stores the predecessor arcs.
    343     ///If you don't use this function before calling \ref run(),
    344     ///it will allocate one. The destructor deallocates this
    345     ///automatically allocated map, of course.
     349    ///If you don't use this function before calling \ref run(Node) "run()"
     350    ///or \ref init(), an instance will be allocated automatically.
     351    ///The destructor deallocates this automatically allocated map,
     352    ///of course.
    346353    ///\return <tt> (*this) </tt>
    347354    Bfs &predMap(PredMap &m)
    … …  
    358365
    359366    ///Sets the map that indicates which nodes are reached.
    360     ///If you don't use this function before calling \ref run(),
    361     ///it will allocate one. The destructor deallocates this
    362     ///automatically allocated map, of course.
     367    ///If you don't use this function before calling \ref run(Node) "run()"
     368    ///or \ref init(), an instance will be allocated automatically.
     369    ///The destructor deallocates this automatically allocated map,
     370    ///of course.
    363371    ///\return <tt> (*this) </tt>
    364372    Bfs &reachedMap(ReachedMap &m)
    … …  
    375383
    376384    ///Sets the map that indicates which nodes are processed.
    377     ///If you don't use this function before calling \ref run(),
    378     ///it will allocate one. The destructor deallocates this
    379     ///automatically allocated map, of course.
     385    ///If you don't use this function before calling \ref run(Node) "run()"
     386    ///or \ref init(), an instance will be allocated automatically.
     387    ///The destructor deallocates this automatically allocated map,
     388    ///of course.
    380389    ///\return <tt> (*this) </tt>
    381390    Bfs &processedMap(ProcessedMap &m)
    … …  
    393402    ///Sets the map that stores the distances of the nodes calculated by
    394403    ///the algorithm.
    395     ///If you don't use this function before calling \ref run(),
    396     ///it will allocate one. The destructor deallocates this
    397     ///automatically allocated map, of course.
     404    ///If you don't use this function before calling \ref run(Node) "run()"
     405    ///or \ref init(), an instance will be allocated automatically.
     406    ///The destructor deallocates this automatically allocated map,
     407    ///of course.
    398408    ///\return <tt> (*this) </tt>
    399409    Bfs &distMap(DistMap &m)
    … …  
    409419  public:
    410420
    411     ///\name Execution control
    412     ///The simplest way to execute the algorithm is to use
    413     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    414     ///\n
    415     ///If you need more control on the execution, first you must call
    416     ///\ref lemon::Bfs::init() "init()", then you can add several source
    417     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    418     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    419     ///actual path computation.
     421    ///\name Execution Control
     422    ///The simplest way to execute the BFS algorithm is to use one of the
     423    ///member functions called \ref run(Node) "run()".\n
     424    ///If you need better control on the execution, you have to call
     425    ///\ref init() first, then you can add several source nodes with
     426    ///\ref addSource(). Finally the actual path computation can be
     427    ///performed with one of the \ref start() functions.
    420428
    421429    ///@{
    422430
     431    ///\brief Initializes the internal data structures.
     432    ///
    423433    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427434    void init()
    428435    {
    … …  
    558565    }
    559566
    560     ///\brief Returns \c false if there are nodes
    561     ///to be processed.
    562     ///
    563     ///Returns \c false if there are nodes
    564     ///to be processed in the queue.
     567    ///Returns \c false if there are nodes to be processed.
     568
     569    ///Returns \c false if there are nodes to be processed
     570    ///in the queue.
    565571    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566572
    567573    ///Returns the number of the nodes to be processed.
    568574
    569     ///Returns the number of the nodes to be processed in the queue.
     575    ///Returns the number of the nodes to be processed
     576    ///in the queue.
    570577    int queueSize() const { return _queue_head-_queue_tail; }
    571578
    … …  
    702709    ///Runs the algorithm to visit all nodes in the digraph.
    703710
    704     ///This method runs the %BFS algorithm in order to
    705     ///compute the shortest path to each node.
    706     ///
    707     ///The algorithm computes
    708     ///- the shortest path tree (forest),
    709     ///- the distance of each node from the root(s).
     711    ///This method runs the %BFS algorithm in order to visit all nodes
     712    ///in the digraph.
    710713    ///
    711714    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    732735
    733736    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     737    ///The results of the BFS algorithm can be obtained using these
    735738    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     739    ///Either \ref run(Node) "run()" or \ref start() should be called
     740    ///before using them.
    738741
    739742    ///@{
    740743
    741     ///The shortest path to a node.
    742 
    743     ///Returns the shortest path to a node.
    744     ///
    745     ///\warning \c t should be reachable from the root(s).
    746     ///
    747     ///\pre Either \ref run() or \ref start() must be called before
    748     ///using this function.
     744    ///The shortest path to the given node.
     745
     746    ///Returns the shortest path to the given node from the root(s).
     747    ///
     748    ///\warning \c t should be reached from the root(s).
     749    ///
     750    ///\pre Either \ref run(Node) "run()" or \ref init()
     751    ///must be called before using this function.
    749752    Path path(Node t) const { return Path(*G, *_pred, t); }
    750753
    751     ///The distance of a node from the root(s).
    752 
    753     ///Returns the distance of a node from the root(s).
    754     ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///The distance of the given node from the root(s).
     755
     756    ///Returns the distance of the given node from the root(s).
     757    ///
     758    ///\warning If node \c v is not reached from the root(s), then
    756759    ///the return value of this function is undefined.
    757760    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     761    ///\pre Either \ref run(Node) "run()" or \ref init()
     762    ///must be called before using this function.
    760763    int dist(Node v) const { return (*_dist)[v]; }
    761764
    762     ///Returns the 'previous arc' of the shortest path tree for a node.
    763 
     765    ///\brief Returns the 'previous arc' of the shortest path tree for
     766    ///the given node.
     767    ///
    764768    ///This function returns the 'previous arc' of the shortest path
    765769    ///tree for the node \c v, i.e. it returns the last arc of a
    766     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    767     ///is not reachable from the root(s) or if \c v is a root.
     770    ///shortest path from a root to \c v. It is \c INVALID if \c v
     771    ///is not reached from the root(s) or if \c v is a root.
    768772    ///
    769773    ///The shortest path tree used here is equal to the shortest path
    770     ///tree used in \ref predNode().
    771     ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     774    ///tree used in \ref predNode() and \ref predMap().
     775    ///
     776    ///\pre Either \ref run(Node) "run()" or \ref init()
     777    ///must be called before using this function.
    774778    Arc predArc(Node v) const { return (*_pred)[v];}
    775779
    776     ///Returns the 'previous node' of the shortest path tree for a node.
    777 
     780    ///\brief Returns the 'previous node' of the shortest path tree for
     781    ///the given node.
     782    ///
    778783    ///This function returns the 'previous node' of the shortest path
    779784    ///tree for the node \c v, i.e. it returns the last but one node
    780     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    781     ///if \c v is not reachable from the root(s) or if \c v is a root.
     785    ///of a shortest path from a root to \c v. It is \c INVALID
     786    ///if \c v is not reached from the root(s) or if \c v is a root.
    782787    ///
    783788    ///The shortest path tree used here is equal to the shortest path
    784     ///tree used in \ref predArc().
    785     ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     789    ///tree used in \ref predArc() and \ref predMap().
     790    ///
     791    ///\pre Either \ref run(Node) "run()" or \ref init()
     792    ///must be called before using this function.
    788793    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789794                                  G->source((*_pred)[v]); }
    … …  
    795800    ///of the nodes calculated by the algorithm.
    796801    ///
    797     ///\pre Either \ref run() or \ref init()
     802    ///\pre Either \ref run(Node) "run()" or \ref init()
    798803    ///must be called before using this function.
    799804    const DistMap &distMap() const { return *_dist;}
    … …  
    803808    ///
    804809    ///Returns a const reference to the node map that stores the predecessor
    805     ///arcs, which form the shortest path tree.
    806     ///
    807     ///\pre Either \ref run() or \ref init()
     810    ///arcs, which form the shortest path tree (forest).
     811    ///
     812    ///\pre Either \ref run(Node) "run()" or \ref init()
    808813    ///must be called before using this function.
    809814    const PredMap &predMap() const { return *_pred;}
    810815
    811     ///Checks if a node is reachable from the root(s).
    812 
    813     ///Returns \c true if \c v is reachable from the root(s).
    814     ///\pre Either \ref run() or \ref start()
     816    ///Checks if the given node is reached from the root(s).
     817
     818    ///Returns \c true if \c v is reached from the root(s).
     819    ///
     820    ///\pre Either \ref run(Node) "run()" or \ref init()
    815821    ///must be called before using this function.
    816822    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    834840    ///The type of the map that stores the predecessor
    835841    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     842    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837843    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838844    ///Instantiates a PredMap.
    … …  
    849855
    850856    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    852     ///By default it is a NullMap.
     857    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     858    ///By default, it is a NullMap.
    853859    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    854860    ///Instantiates a ProcessedMap.
    … …  
    869875
    870876    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873880    ///Instantiates a ReachedMap.
    … …  
    884891
    885892    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     893    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887894    typedef typename Digraph::template NodeMap<int> DistMap;
    888895    ///Instantiates a DistMap.
    … …  
    899906
    900907    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     908    ///It must conform to the \ref concepts::Path "Path" concept.
    902909    typedef lemon::Path<Digraph> Path;
    903910  };
    … …  
    905912  /// Default traits class used by BfsWizard
    906913
    907   /// To make it easier to use Bfs algorithm
    908   /// we have created a wizard class.
    909   /// This \ref BfsWizard class needs default traits,
    910   /// as well as the \ref Bfs class.
    911   /// The \ref BfsWizardBase is a class to be the default traits of the
    912   /// \ref BfsWizard class.
     914  /// Default traits class used by BfsWizard.
     915  /// \tparam GR The type of the digraph.
    913916  template<class GR>
    914917  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
    … …  
    938941    /// Constructor.
    939942
    940     /// This constructor does not require parameters, therefore it initiates
     943    /// This constructor does not require parameters, it initiates
    941944    /// all of the attributes to \c 0.
    942945    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    958961  /// This auxiliary class is created to implement the
    959962  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run() method, it uses the functions
    961   /// and features of the plain \ref Bfs.
     963  /// It does not have own \ref run(Node) "run()" method, it uses the
     964  /// functions and features of the plain \ref Bfs.
    962965  ///
    963966  /// This class should only be used through the \ref bfs() function,
    964967  /// which makes it easier to use the algorithm.
     968  ///
     969  /// \tparam TR The traits class that defines various types used by the
     970  /// algorithm.
    965971  template<class TR>
    966972  class BfsWizard : public TR
    … …  
    968974    typedef TR Base;
    969975
    970     ///The type of the digraph the algorithm runs on.
    971976    typedef typename TR::Digraph Digraph;
    972977
    … …  
    976981    typedef typename Digraph::OutArcIt OutArcIt;
    977982
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980983    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982984    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984985    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986986    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988987    typedef typename TR::Path Path;
    989988
    … …  
    10551054    ///Runs BFS algorithm to visit all nodes in the digraph.
    10561055
    1057     ///This method runs BFS algorithm in order to compute
    1058     ///the shortest path to each node.
     1056    ///This method runs BFS algorithm in order to visit all nodes
     1057    ///in the digraph.
    10591058    void run()
    10601059    {
    … …  
    10681067      SetPredMapBase(const TR &b) : TR(b) {}
    10691068    };
    1070     ///\brief \ref named-func-param "Named parameter"
    1071     ///for setting PredMap object.
    1072     ///
    1073     ///\ref named-func-param "Named parameter"
    1074     ///for setting PredMap object.
     1069
     1070    ///\brief \ref named-templ-param "Named parameter" for setting
     1071    ///the predecessor map.
     1072    ///
     1073    ///\ref named-templ-param "Named parameter" function for setting
     1074    ///the map that stores the predecessor arcs of the nodes.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088     ///\brief \ref named-func-param "Named parameter"
    1089     ///for setting ReachedMap object.
    1090     ///
    1091     /// \ref named-func-param "Named parameter"
    1092     ///for setting ReachedMap object.
     1088
     1089    ///\brief \ref named-templ-param "Named parameter" for setting
     1090    ///the reached map.
     1091    ///
     1092    ///\ref named-templ-param "Named parameter" function for setting
     1093    ///the map that indicates which nodes are reached.
    10931094    template<class T>
    10941095    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    11041105      SetDistMapBase(const TR &b) : TR(b) {}
    11051106    };
    1106     ///\brief \ref named-func-param "Named parameter"
    1107     ///for setting DistMap object.
    1108     ///
    1109     /// \ref named-func-param "Named parameter"
    1110     ///for setting DistMap object.
     1107
     1108    ///\brief \ref named-templ-param "Named parameter" for setting
     1109    ///the distance map.
     1110    ///
     1111    ///\ref named-templ-param "Named parameter" function for setting
     1112    ///the map that stores the distances of the nodes calculated
     1113    ///by the algorithm.
    11111114    template<class T>
    11121115    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    11221125      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231126    };
    1124     ///\brief \ref named-func-param "Named parameter"
    1125     ///for setting ProcessedMap object.
    1126     ///
    1127     /// \ref named-func-param "Named parameter"
    1128     ///for setting ProcessedMap object.
     1127
     1128    ///\brief \ref named-func-param "Named parameter" for setting
     1129    ///the processed map.
     1130    ///
     1131    ///\ref named-templ-param "Named parameter" function for setting
     1132    ///the map that indicates which nodes are processed.
    11291133    template<class T>
    11301134    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    11791183  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801184  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1185  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821186  ///to the end of the parameter list.
    11831187  ///\sa BfsWizard
    … …  
    11951199  /// This class defines the interface of the BfsVisit events, and
    11961200  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1201  template <typename GR>
    11981202  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1203    typedef GR Digraph;
    12001204    typedef typename Digraph::Arc Arc;
    12011205    typedef typename Digraph::Node Node;
    … …  
    12251229  };
    12261230#else
    1227   template <typename _Digraph>
     1231  template <typename GR>
    12281232  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1233    typedef GR Digraph;
    12301234    typedef typename Digraph::Arc Arc;
    12311235    typedef typename Digraph::Node Node;
    … …  
    12551259  ///
    12561260  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1261  /// \tparam GR The type of the digraph the algorithm runs on.
     1262  template<class GR>
    12591263  struct BfsVisitDefaultTraits {
    12601264
    12611265    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1266    typedef GR Digraph;
    12631267
    12641268    /// \brief The type of the map that indicates which nodes are reached.
    12651269    ///
    12661270    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1271    /// It must conform to
     1272    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681273    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691274
    … …  
    12811286  /// \ingroup search
    12821287  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1288  /// \brief BFS algorithm class with visitor interface.
    12841289  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1290  /// This class provides an efficient implementation of the BFS algorithm
    12861291  /// with visitor interface.
    12871292  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1293  /// The BfsVisit class provides an alternative interface to the Bfs
    12891294  /// class. It works with callback mechanism, the BfsVisit object calls
    12901295  /// the member functions of the \c Visitor class on every BFS event.
    … …  
    12951300  /// instead.
    12961301  ///
    1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1298   /// The default value is
    1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1302  /// \tparam GR The type of the digraph the algorithm runs on.
     1303  /// The default type is \ref ListDigraph.
     1304  /// The value of GR is not used directly by \ref BfsVisit,
     1305  /// it is only passed to \ref BfsVisitDefaultTraits.
     1306  /// \tparam VS The Visitor type that is used by the algorithm.
     1307  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031308  /// does not observe the BFS events. If you want to observe the BFS
    13041309  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
    1306   /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    1308   /// See \ref BfsVisitDefaultTraits for the documentation of
    1309   /// a BFS visit traits class.
     1310  /// \tparam TR The traits class that defines various types used by the
     1311  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
     1312  /// "BfsVisitDefaultTraits<GR>".
     1313  /// In most cases, this parameter should not be set directly,
     1314  /// consider to use the named template parameters instead.
    13101315#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1316  template <typename GR, typename VS, typename TR>
    13121317#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1318  template <typename GR = ListDigraph,
     1319            typename VS = BfsVisitor<GR>,
     1320            typename TR = BfsVisitDefaultTraits<GR> >
    13161321#endif
    13171322  class BfsVisit {
    … …  
    13191324
    13201325    ///The traits class.
    1321     typedef _Traits Traits;
     1326    typedef TR Traits;
    13221327
    13231328    ///The type of the digraph the algorithm runs on.
    … …  
    13251330
    13261331    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1332    typedef VS Visitor;
    13281333
    13291334    ///The type of the map that indicates which nodes are reached.
    … …  
    13651370    typedef BfsVisit Create;
    13661371
    1367     /// \name Named template parameters
     1372    /// \name Named Template Parameters
    13681373
    13691374    ///@{
    … …  
    14071412    ///
    14081413    /// Sets the map that indicates which nodes are reached.
    1409     /// If you don't use this function before calling \ref run(),
    1410     /// it will allocate one. The destructor deallocates this
    1411     /// automatically allocated map, of course.
     1414    /// If you don't use this function before calling \ref run(Node) "run()"
     1415    /// or \ref init(), an instance will be allocated automatically.
     1416    /// The destructor deallocates this automatically allocated map,
     1417    /// of course.
    14121418    /// \return <tt> (*this) </tt>
    14131419    BfsVisit &reachedMap(ReachedMap &m) {
    … …  
    14221428  public:
    14231429
    1424     /// \name Execution control
    1425     /// The simplest way to execute the algorithm is to use
    1426     /// one of the member functions called \ref lemon::BfsVisit::run()
    1427     /// "run()".
    1428     /// \n
    1429     /// If you need more control on the execution, first you must call
    1430     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1431     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1432     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1433     /// actual path computation.
     1430    /// \name Execution Control
     1431    /// The simplest way to execute the BFS algorithm is to use one of the
     1432    /// member functions called \ref run(Node) "run()".\n
     1433    /// If you need better control on the execution, you have to call
     1434    /// \ref init() first, then you can add several source nodes with
     1435    /// \ref addSource(). Finally the actual path computation can be
     1436    /// performed with one of the \ref start() functions.
    14341437
    14351438    /// @{
    … …  
    17011704    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17021705    ///
    1703     /// This method runs the %BFS algorithm in order to
    1704     /// compute the shortest path to each node.
    1705     ///
    1706     /// The algorithm computes
    1707     /// - the shortest path tree (forest),
    1708     /// - the distance of each node from the root(s).
     1706    /// This method runs the %BFS algorithm in order to visit all nodes
     1707    /// in the digraph.
    17091708    ///
    17101709    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    17311730
    17321731    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1732    /// The results of the BFS algorithm can be obtained using these
    17341733    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1734    /// Either \ref run(Node) "run()" or \ref start() should be called
     1735    /// before using them.
     1736
    17381737    ///@{
    17391738
    1740     /// \brief Checks if a node is reachable from the root(s).
    1741     ///
    1742     /// Returns \c true if \c v is reachable from the root(s).
    1743     /// \pre Either \ref run() or \ref start()
     1739    /// \brief Checks if the given node is reached from the root(s).
     1740    ///
     1741    /// Returns \c true if \c v is reached from the root(s).
     1742    ///
     1743    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441744    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1745    bool reached(Node v) const { return (*_reached)[v]; }
    17461746
    17471747    ///@}

  • lemon/bin_heap.h

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

  • lemon/bits/alteration_notifier.h

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

  • lemon/bits/array_map.h

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

  • lemon/bits/bezier.h

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

  • lemon/bits/default_map.h

    r540 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     157
    156158  public:
    157     typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    158159    typedef DefaultMap<_Graph, _Item, _Value> Map;
    159160
    160     typedef typename Parent::Graph Graph;
     161    typedef typename Parent::GraphType GraphType;
    161162    typedef typename Parent::Value Value;
    162163
    163     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    164     DefaultMap(const Graph& graph, const Value& value)
     164    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
     165    DefaultMap(const GraphType& graph, const Value& value)
    165166      : Parent(graph, value) {}
    166167

  • lemon/bits/enable_if.h

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

  • lemon/bits/graph_extender.h

    r314 r825  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the digraph types
     32//\brief Extenders for the graph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the Digraphs
     37  // \brief Extender for the digraph implementations
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40    typedef Base Parent;
     41
    4042  public:
    4143
    42     typedef Base Parent;
    4344    typedef DigraphExtender Digraph;
    4445
    … …  
    5657    }
    5758
    58     Node fromId(int id, Node) const {
     59    static Node fromId(int id, Node) {
    5960      return Parent::nodeFromId(id);
    6061    }
    6162
    62     Arc fromId(int id, Arc) const {
     63    static Arc fromId(int id, Arc) {
    6364      return Parent::arcFromId(id);
    6465    }
    … …  
    219220    class NodeMap
    220221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    221     public:
    222       typedef DigraphExtender Digraph;
    223222      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    224223
     224    public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
    … …  
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246     public:
    247       typedef DigraphExtender Digraph;
    248246      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249247
     248    public:
    250249      explicit ArcMap(const Digraph& digraph)
    251250        : Parent(digraph) {}
    … …  
    331330  template <typename Base>
    332331  class GraphExtender : public Base {
     332    typedef Base Parent;
     333
    333334  public:
    334335
    335     typedef Base Parent;
    336336    typedef GraphExtender Graph;
    337337
    … …  
    356356    }
    357357
    358     Node fromId(int id, Node) const {
     358    static Node fromId(int id, Node) {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     Arc fromId(int id, Arc) const {
     362    static Arc fromId(int id, Arc) {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     Edge fromId(int id, Edge) const {
     366    static Edge fromId(int id, Edge) {
    367367      return Parent::edgeFromId(id);
    368368    }
    … …  
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
    608       NodeMap(const Graph& graph)
     606    public:
     607      explicit NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
    610609      NodeMap(const Graph& graph, const _Value& value)
    … …  
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
    633       ArcMap(const Graph& graph)
     630    public:
     631      explicit ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
    635633      ArcMap(const Graph& graph, const _Value& value)
    … …  
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
    658       EdgeMap(const Graph& graph)
     654    public:
     655      explicit EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}
    660657

  • lemon/bits/map_extender.h

    r865 r867  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
    39   public:
    40 
    4139    typedef _Map Parent;
     40    typedef typename Parent::GraphType GraphType;
     41
     42  public:
     43
    4244    typedef MapExtender Map;
    43 
    44 
    45     typedef typename Parent::Graph Graph;
    4645    typedef typename Parent::Key Item;
    4746
    4847    typedef typename Parent::Key Key;
    4948    typedef typename Parent::Value Value;
     49    typedef typename Parent::Reference Reference;
     50    typedef typename Parent::ConstReference ConstReference;
     51
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    5053
    5154    class MapIt;
    … …  
    5760  public:
    5861
    59     MapExtender(const Graph& graph)
     62    MapExtender(const GraphType& graph)
    6063      : Parent(graph) {}
    6164
    62     MapExtender(const Graph& graph, const Value& value)
     65    MapExtender(const GraphType& graph, const Value& value)
    6366      : Parent(graph, value) {}
    6467
    … …  
    7679  public:
    7780    class MapIt : public Item {
    78     public:
    79 
    80       typedef Item Parent;
     81      typedef Item Parent;
     82
     83    public:
     84
    8185      typedef typename Map::Value Value;
    8286
    … …  
    115119
    116120    class ConstMapIt : public Item {
    117     public:
    118 
    119       typedef Item Parent;
     121      typedef Item Parent;
     122
     123    public:
    120124
    121125      typedef typename Map::Value Value;
    … …  
    146150
    147151    class ItemIt : public Item {
    148     public:
    149 
    150       typedef Item Parent;
    151 
     152      typedef Item Parent;
     153
     154    public:
    152155      ItemIt() : map(NULL) {}
     156
    153157
    154158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
    … …  
    177181  template <typename _Graph, typename _Map>
    178182  class SubMapExtender : public _Map {
    179   public:
    180 
    181183    typedef _Map Parent;
     184    typedef _Graph GraphType;
     185
     186  public:
     187
    182188    typedef SubMapExtender Map;
    183 
    184     typedef _Graph Graph;
    185 
    186189    typedef typename Parent::Key Item;
    187190
    188191    typedef typename Parent::Key Key;
    189192    typedef typename Parent::Value Value;
     193    typedef typename Parent::Reference Reference;
     194    typedef typename Parent::ConstReference ConstReference;
     195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    190197
    191198    class MapIt;
    … …  
    197204  public:
    198205
    199     SubMapExtender(const Graph& _graph)
     206    SubMapExtender(const GraphType& _graph)
    200207      : Parent(_graph), graph(_graph) {}
    201208
    202     SubMapExtender(const Graph& _graph, const Value& _value)
     209    SubMapExtender(const GraphType& _graph, const Value& _value)
    203210      : Parent(_graph, _value), graph(_graph) {}
    204211
    … …  
    220227  public:
    221228    class MapIt : public Item {
    222     public:
    223 
    224       typedef Item Parent;
     229      typedef Item Parent;
     230
     231    public:
    225232      typedef typename Map::Value Value;
    226233
    … …  
    259266
    260267    class ConstMapIt : public Item {
    261     public:
    262 
    263       typedef Item Parent;
     268      typedef Item Parent;
     269
     270    public:
    264271
    265272      typedef typename Map::Value Value;
    … …  
    290297
    291298    class ItemIt : public Item {
    292     public:
    293 
    294       typedef Item Parent;
    295 
     299      typedef Item Parent;
     300
     301    public:
    296302      ItemIt() : map(NULL) {}
     303
    297304
    298305      ItemIt(Invalid i) : Parent(i), map(NULL) { }
    … …  
    317324  private:
    318325
    319     const Graph& graph;
     326    const GraphType& graph;
    320327
    321328  };

  • lemon/bits/path_dump.h

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

  • lemon/bits/traits.h

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

  • lemon/bits/vector_map.h

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

  • lemon/bits/windows.cc

    r513 r1084  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4141#include <unistd.h>
    4242#include <ctime>
     43#ifndef WIN32
    4344#include <sys/times.h>
     45#endif
    4446#include <sys/time.h>
    4547#endif
    … …  
    9799      GetSystemTime(&time);
    98100      char buf1[11], buf2[9], buf3[5];
    99           if (GetDateFormat(MY_LOCALE, 0, &time,
     101          if (GetDateFormat(MY_LOCALE, 0, &time,
    100102                        ("ddd MMM dd"), buf1, 11) &&
    101103          GetTimeFormat(MY_LOCALE, 0, &time,

  • lemon/bits/windows.h

    r511 r576  
    1717 */
    1818
    19 #ifndef LEMON_WINDOWS_H
    20 #define LEMON_WINDOWS_H
     19#ifndef LEMON_BITS_WINDOWS_H
     20#define LEMON_BITS_WINDOWS_H
    2121
    2222#include <string>

  • lemon/color.cc

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

  • lemon/color.h

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

  • lemon/concept_check.h

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

  • lemon/concepts/digraph.h

    r263 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
    … …  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76