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:
87 added
1 deleted
109 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r514 r610  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/cmake.version
     25cmake/version.cmake
    2626.dirstamp
    2727.libs/*
    2828.deps/*
    2929demo/*.eps
     30m4/libtool.m4
     31m4/ltoptions.m4
     32m4/ltsugar.m4
     33m4/ltversion.m4
     34m4/lt~obsolete.m4
    3035
    3136syntax: regexp
    … …  
    3641^autom4te.cache/.*
    3742^build-aux/.*
    38 ^objs.*/.*
     43^.*objs.*/.*
    3944^test/[a-z_]*$
     45^tools/[a-z-_]*$
    4046^demo/.*_demo$
    41 ^build/.*
     47^.*build.*/.*
    4248^doc/gen-images/.*
    4349CMakeFiles

  • CMakeLists.txt

    r540 r791  
    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)
     6IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     7  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
     8ELSEIF(DEFINED ENV{LEMON_VERSION})
     9  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
     10ELSE()
     11  EXECUTE_PROCESS(
     12    COMMAND hg id -i
     13    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
     14    OUTPUT_VARIABLE HG_REVISION
     15    ERROR_QUIET
     16    OUTPUT_STRIP_TRAILING_WHITESPACE
     17  )
     18  IF(HG_REVISION STREQUAL "")
     19    SET(HG_REVISION "hg-tip")
     20  ENDIF()
     21  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
     22ENDIF()
    1323
    14 INCLUDE(FindDoxygen)
    15 INCLUDE(FindGhostscript)
     24SET(PROJECT_VERSION ${LEMON_VERSION})
    1625
    17 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     26SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
     27
     28FIND_PACKAGE(Doxygen)
     29FIND_PACKAGE(Ghostscript)
     30FIND_PACKAGE(GLPK 4.33)
     31FIND_PACKAGE(CPLEX)
     32FIND_PACKAGE(COIN)
    1833
    1934INCLUDE(CheckTypeSize)
    20 CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
     35CHECK_TYPE_SIZE("long long" LONG_LONG)
     36SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     37
     38INCLUDE(FindPythonInterp)
    2139
    2240ENABLE_TESTING()
    2341
    2442ADD_SUBDIRECTORY(lemon)
    25 ADD_SUBDIRECTORY(demo)
    26 ADD_SUBDIRECTORY(doc)
    27 ADD_SUBDIRECTORY(test)
     43IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     44  ADD_SUBDIRECTORY(demo)
     45  ADD_SUBDIRECTORY(tools)
     46  ADD_SUBDIRECTORY(doc)
     47  ADD_SUBDIRECTORY(test)
     48ENDIF()
    2849
    29 IF(WIN32)
     50CONFIGURE_FILE(
     51  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     52  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     53  @ONLY
     54)
     55IF(UNIX)
     56  INSTALL(
     57    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     58    DESTINATION share/lemon/cmake
     59  )
     60ELSEIF(WIN32)
     61  INSTALL(
     62    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     63    DESTINATION cmake
     64  )
     65ENDIF()
     66
     67IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
    3068  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    3169  SET(CPACK_PACKAGE_VENDOR "EGRES")
    3270  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")
     71    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     72  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3573
    3674  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    … …  
    4179    "${PROJECT_NAME} ${PROJECT_VERSION}")
    4280
    43   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     81  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4482
    4583  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    4684  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     85  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    4786  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4887
    … …  
    5190  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    5291    "DLL and import library")
     92  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     93    "Command line utilities")
    5394  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    5495    "Doxygen generated documentation")
    … …  
    72113
    73114  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")
     115  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     116  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     117  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    77118  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    78119  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
    … …  
    89130
    90131  INCLUDE(CPack)
    91 ENDIF(WIN32)
     132ENDIF()

  • INSTALL

    r526 r615  
    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.

  • LICENSE

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

  • Makefile.am

    r503 r799  
    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
     47
     48DIST_SUBDIRS = demo
     49
     50demo:
     51        $(MAKE) $(AM_MAKEFLAGS) -C demo
    4152
    4253MRPROPERFILES = \
    … …  
    6677        bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
    6778
    68 .PHONY: mrproper dist-bz2 distcheck-bz2
     79.PHONY: demo mrproper dist-bz2 distcheck-bz2

  • NEWS

    r534 r712  
     12009-05-13 Version 1.1 released
     2
     3        This is the second stable release of the 1.x series. It
     4        features a better coverage of the tools available in the 0.x
     5        series, a thoroughly reworked LP/MIP interface plus various
     6        improvements in the existing tools.
     7
     8        * Much improved M$ Windows support
     9          * Various improvements in the CMAKE build system
     10          * Compilation warnings are fixed/suppressed
     11        * Support IBM xlC compiler
     12        * New algorithms
     13          * Connectivity related algorithms (#61)
     14          * Euler walks (#65)
     15          * Preflow push-relabel max. flow algorithm (#176)
     16          * Circulation algorithm (push-relabel based) (#175)
     17          * Suurballe algorithm (#47)
     18          * Gomory-Hu algorithm (#66)
     19          * Hao-Orlin algorithm (#58)
     20          * Edmond's maximum cardinality and weighted matching algorithms
     21            in general graphs (#48,#265)
     22          * Minimum cost arborescence/branching (#60)
     23          * Network Simplex min. cost flow algorithm (#234)
     24        * New data structures
     25          * Full graph structure (#57)
     26          * Grid graph structure (#57)
     27          * Hypercube graph structure (#57)
     28          * Graph adaptors (#67)
     29          * ArcSet and EdgeSet classes (#67)
     30          * Elevator class (#174)
     31        * Other new tools
     32          * LP/MIP interface (#44)
     33            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
     34          * Reader for the Nauty file format (#55)
     35          * DIMACS readers (#167)
     36          * Radix sort algorithms (#72)
     37          * RangeIdMap and CrossRefMap (#160)
     38        * New command line tools
     39          * DIMACS to LGF converter (#182)
     40          * lgf-gen - a graph generator (#45)
     41          * DIMACS solver utility (#226)
     42        * Other code improvements
     43          * Lognormal distribution added to Random (#102)
     44          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
     45          * The standard maps of graphs are guaranteed to be
     46            reference maps (#190)
     47        * Miscellaneous
     48          * Various doc improvements
     49          * Improved 0.x -> 1.x converter script
     50
     51        * Several bugfixes (compared to release 1.0):
     52          #170: Bugfix SmartDigraph::split()
     53          #171: Bugfix in SmartGraph::restoreSnapshot()
     54          #172: Extended test cases for graphs and digraphs
     55          #173: Bugfix in Random
     56                * operator()s always return a double now
     57                * the faulty real<Num>(Num) and real<Num>(Num,Num)
     58                  have been removed
     59          #187: Remove DijkstraWidestPathOperationTraits
     60          #61:  Bugfix in DfsVisit
     61          #193: Bugfix in GraphReader::skipSection()
     62          #195: Bugfix in ConEdgeIt()
     63          #197: Bugfix in heap unionfind
     64                * This bug affects Edmond's general matching algorithms
     65          #207: Fix 'make install' without 'make html' using CMAKE
     66          #208: Suppress or fix VS2008 compilation warnings
     67          ----: Update the LEMON icon
     68          ----: Enable the component-based installer
     69                (in installers made by CPACK)
     70          ----: Set the proper version for CMAKE in the tarballs
     71                (made by autotools)
     72          ----: Minor clarification in the LICENSE file
     73          ----: Add missing unistd.h include to time_measure.h
     74          #204: Compilation bug fixed in graph_to_eps.h with VS2005
     75          #214,#215: windows.h should never be included by lemon headers
     76          #230: Build systems check the availability of 'long long' type
     77          #229: Default implementation of Tolerance<> is used for integer types
     78          #211,#212: Various fixes for compiling on AIX
     79          ----: Improvements in CMAKE config
     80                - docs is installed in share/doc/
     81                - detects newer versions of Ghostscript
     82          #239: Fix missing 'inline' specifier in time_measure.h
     83          #274,#280: Install lemon/config.h
     84          #275: Prefix macro names with LEMON_ in lemon/config.h
     85          ----: Small script for making the release tarballs added
     86          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     87
    1882009-03-27 LEMON joins to the COIN-OR initiative
    289

  • README

    r318 r705  
    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

  • 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 r791  
    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.
    … …  
    108104AC_CONFIG_FILES([
    109105Makefile
     106demo/Makefile
    110107cmake/version.cmake
    111108doc/Doxyfile
    … …  
    121118echo
    122119echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     120echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124121echo
    125122echo Compiler supports long long... : $long_long_found
    126123echo
    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
     124echo GLPK support.................. : $lx_glpk_found
     125echo CPLEX support................. : $lx_cplex_found
     126echo SOPLEX support................ : $lx_soplex_found
     127echo CLP support................... : $lx_clp_found
     128echo CBC support................... : $lx_cbc_found
     129echo
    132130echo Build additional tools........ : $enable_tools
    133131echo

  • 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 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).

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

  • doc/Doxyfile.in

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

  • doc/Makefile.am

    r317 r791  
    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        node_biconnected_components.eps \
     31        strongly_connected_components.eps
     32
    2333DOC_EPS_IMAGES = \
    24         $(DOC_EPS_IMAGES18)
     34        $(DOC_EPS_IMAGES18) \
     35        $(DOC_EPS_IMAGES27)
    2536
    2637DOC_PNG_IMAGES = \
    … …  
    4556        fi
    4657
    47 html-local: $(DOC_PNG_IMAGES)
     58$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
     59        -mkdir doc/gen-images
     60        if test ${gs_found} = yes; then \
     61          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
     62        else \
     63          echo; \
     64          echo "Ghostscript not found."; \
     65          echo; \
     66          exit 1; \
     67        fi
     68
     69references.dox: doc/references.bib
     70        if test ${python_found} = yes; then \
     71          cd doc; \
     72          python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
     73          cd ..; \
     74        else \
     75          echo; \
     76          echo "Python not found."; \
     77          echo; \
     78          exit 1; \
     79        fi
     80
     81html-local: $(DOC_PNG_IMAGES) references.dox
    4882        if test ${doxygen_found} = yes; then \
    4983          cd doc; \
    … …  
    70104install-html-local: doc/html
    71105        @$(NORMAL_INSTALL)
    72         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     106        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    73107        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    74108          f="`echo $$p | sed -e 's|^.*/||'`"; \
    75           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    76           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     109          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     110          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    77111        done
    78112
    … …  
    81115        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    82116          f="`echo $$p | sed -e 's|^.*/||'`"; \
    83           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    84           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     117          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     118          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    85119        done
    86120

  • 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 r818  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
     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"
     263*/
     264
     265/**
     266@defgroup matrices Matrices
     267@ingroup datas
     268\brief Two dimensional data storages implemented in LEMON.
     269
     270This group contains two dimensional data storages implemented in LEMON.
    179271*/
    180272
    … …  
    184276\brief Auxiliary data structures implemented in LEMON.
    185277
    186 This group describes some data structures implemented in LEMON in
     278This group contains some data structures implemented in LEMON in
    187279order to make it easier to implement combinatorial algorithms.
    188280*/
    189281
    190282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This group contains geometric data structures implemented in LEMON.
     288
     289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     290   vector with the usual operations.
     291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     292   rectangular bounding box of a set of \ref lemon::dim2::Point
     293   "dim2::Point"'s.
     294*/
     295
     296/**
     297@defgroup matrices Matrices
     298@ingroup auxdat
     299\brief Two dimensional data storages implemented in LEMON.
     300
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    191305@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     306\brief This group contains the several algorithms
    193307implemented in LEMON.
    194308
    195 This group describes the several algorithms
     309This group contains the several algorithms
    196310implemented in LEMON.
    197311*/
    … …  
    202316\brief Common graph search algorithms.
    203317
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     318This group contains the common graph search algorithms, namely
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    206321*/
    207322
    … …  
    211326\brief Algorithms for finding shortest paths.
    212327
    213 This group describes the algorithms for finding shortest paths in graphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
     330
     331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     332   when all arc lengths are non-negative.
     333 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     334   from a source node when arc lenghts can be either positive or negative,
     335   but the digraph should not contain directed cycles with negative total
     336   length.
     337 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     338   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     339   lenghts can be either positive or negative, but the digraph should
     340   not contain directed cycles with negative total length.
     341 - \ref Suurballe A successive shortest path algorithm for finding
     342   arc-disjoint paths between two nodes having minimum total length.
     343*/
     344
     345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \ref clrs01algorithms.
    214352*/
    215353
    … …  
    219357\brief Algorithms for finding maximum flows.
    220358
    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]
     359This group contains the algorithms for finding maximum flows and
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     361
     362The \e maximum \e flow \e problem is to find a flow of maximum value between
     363a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     364digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     365\f$s, t \in V\f$ source and target nodes.
     366A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     367following optimization problem.
     368
     369\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     370\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     371    \quad \forall u\in V\setminus\{s,t\} \f]
     372\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    234373
    235374LEMON 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
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \ref edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \ref goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \ref dinic70algorithm, \ref sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \ref goldberg88newapproach, \ref sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
     385fastest method for computing a maximum flow. All implementations
     386also provide functions to query the minimum cut, which is the dual
     387problem of maximum flow.
     388
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
     390for finding feasible circulations, which is a somewhat different problem,
     391but it is strongly related to maximum flow.
     392For more information, see \ref Circulation.
     393*/
     394
     395/**
     396@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    249397@ingroup algs
    250398
    251399\brief Algorithms for finding minimum cost flows and circulations.
    252400
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
     401This group contains the algorithms for finding minimum cost flows and
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
     405
     406LEMON contains several algorithms for this problem.
     407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
     412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     413   capacity scaling \ref edmondskarp72theoretical.
     414 - \ref CancelAndTighten The Cancel and Tighten algorithm
     415   \ref goldberg89cyclecanceling.
     416 - \ref CycleCanceling Cycle-Canceling algorithms
     417   \ref klein67primal, \ref goldberg89cyclecanceling.
     418
     419In general NetworkSimplex is the most efficient implementation,
     420but in special cases other algorithms could be faster.
     421For example, if the total supply and/or capacities are rather small,
     422CapacityScaling is usually the fastest algorithm (without effective scaling).
    255423*/
    256424
    … …  
    261429\brief Algorithms for finding minimum cut in graphs.
    262430
    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
     431This group contains the algorithms for finding minimum cut in graphs.
     432
     433The \e minimum \e cut \e problem is to find a non-empty and non-complete
     434\f$X\f$ subset of the nodes with minimum overall capacity on
     435outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     436\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269437cut is the \f$X\f$ solution of the next optimization problem:
    270438
    271439\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]
     440    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    273441
    274442LEMON contains several algorithms related to minimum cut problems:
    275443
    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
     444- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     445  in directed graphs.
     446- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     447  calculating minimum cut in undirected graphs.
     448- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     449  all-pairs minimum cut in undirected graphs.
    282450
    283451If 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
     452see the \ref max_flow "maximum flow problem".
     453*/
     454
     455/**
     456@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     457@ingroup algs
     458\brief Algorithms for finding minimum mean cycles.
     459
     460This group contains the algorithms for finding minimum mean cycles
     461\ref clrs01algorithms, \ref amo93networkflows.
     462
     463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     464of minimum mean length (cost) in a digraph.
     465The mean length of a cycle is the average length of its arcs, i.e. the
     466ratio between the total length of the cycle and the number of arcs on it.
     467
     468This problem has an important connection to \e conservative \e length
     469\e functions, too. A length function on the arcs of a digraph is called
     470conservative if and only if there is no directed cycle of negative total
     471length. For an arbitrary length function, the negative of the minimum
     472cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     473arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     474function.
     475
     476LEMON contains three algorithms for solving the minimum mean cycle problem:
     477- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     478  \ref dasdan98minmeancycle.
     479- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     480  version of Karp's algorithm \ref dasdan98minmeancycle.
     481- \ref Howard "Howard"'s policy iteration algorithm
     482  \ref dasdan98minmeancycle.
     483
     484In practice, the Howard algorithm proved to be by far the most efficient
     485one, though the best known theoretical bound on its running time is
     486exponential.
     487Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     488O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     489applied early termination scheme.
    309490*/
    310491
    … …  
    314495\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315496
    316 This group contains algorithm objects and functions to calculate
     497This group contains the algorithms for calculating
    317498matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
     499finding a subset of the edges for which each node has at most one incident
     500edge.
    319501
    320502There are several different algorithms for calculate matchings in
    321503graphs.  The matching problems in bipartite graphs are generally
    322504easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     505can be finding maximum cardinality, maximum weight or minimum cost
    324506matching. The search can be constrained to find perfect or
    325507maximum cardinality matching.
    326508
    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
     509The matching algorithms implemented in LEMON:
     510- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     511  for calculating maximum cardinality matching in bipartite graphs.
     512- \ref PrBipartiteMatching Push-relabel algorithm
     513  for calculating maximum cardinality matching in bipartite graphs.
     514- \ref MaxWeightedBipartiteMatching
     515  Successive shortest path algorithm for calculating maximum weighted
     516  matching and maximum weighted bipartite matching in bipartite graphs.
     517- \ref MinCostMaxBipartiteMatching
     518  Successive shortest path algorithm for calculating minimum cost maximum
     519  matching in bipartite graphs.
     520- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     521  maximum cardinality matching in general graphs.
     522- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     523  maximum weighted matching in general graphs.
     524- \ref MaxWeightedPerfectMatching
     525  Edmond's blossom shrinking algorithm for calculating maximum weighted
     526  perfect matching in general graphs.
    347527
    348528\image html bipartite_matching.png
    … …  
    351531
    352532/**
    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
     533@defgroup graph_properties Connectivity and Other Graph Properties
     534@ingroup algs
     535\brief Algorithms for discovering the graph properties
     536
     537This group contains the algorithms for discovering the graph properties
     538like connectivity, bipartiteness, euler property, simplicity etc.
     539
     540\image html connected_components.png
     541\image latex connected_components.eps "Connected components" width=\textwidth
     542*/
     543
     544/**
     545@defgroup planar Planarity Embedding and Drawing
     546@ingroup algs
     547\brief Algorithms for planarity checking, embedding and drawing
     548
     549This group contains the algorithms for planarity checking,
     550embedding and drawing.
     551
     552\image html planar.png
     553\image latex planar.eps "Plane graph" width=\textwidth
     554*/
     555
     556/**
     557@defgroup approx Approximation Algorithms
     558@ingroup algs
     559\brief Approximation algorithms.
     560
     561This group contains the approximation and heuristic algorithms
     562implemented in LEMON.
    359563*/
    360564
    … …  
    364568\brief Auxiliary algorithms implemented in LEMON.
    365569
    366 This group describes some algorithms implemented in LEMON
     570This group contains some algorithms implemented in LEMON
    367571in order to make it easier to implement complex algorithms.
    368572*/
    369573
    370574/**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
     575@defgroup gen_opt_group General Optimization Tools
     576\brief This group contains some general optimization frameworks
    376577implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     578
     579This group contains some general optimization frameworks
    382580implemented 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
     581*/
     582
     583/**
     584@defgroup lp_group LP and MIP Solvers
    390585@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.
     586\brief LP and MIP solver interfaces for LEMON.
     587
     588This group contains LP and MIP solver interfaces for LEMON.
     589Various LP solvers could be used in the same manner with this
     590high-level interface.
     591
     592The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     593\ref cplex, \ref soplex.
    396594*/
    397595
    … …  
    410608\brief Metaheuristics for LEMON library.
    411609
    412 This group describes some metaheuristic optimization tools.
     610This group contains some metaheuristic optimization tools.
    413611*/
    414612
    … …  
    425623\brief Simple basic graph utilities.
    426624
    427 This group describes some simple basic graph utilities.
     625This group contains some simple basic graph utilities.
    428626*/
    429627
    … …  
    433631\brief Tools for development, debugging and testing.
    434632
    435 This group describes several useful tools for development,
     633This group contains several useful tools for development,
    436634debugging and testing.
    437635*/
    … …  
    442640\brief Simple tools for measuring the performance of algorithms.
    443641
    444 This group describes simple tools for measuring the performance
     642This group contains simple tools for measuring the performance
    445643of algorithms.
    446644*/
    … …  
    451649\brief Exceptions defined in LEMON.
    452650
    453 This group describes the exceptions defined in LEMON.
     651This group contains the exceptions defined in LEMON.
    454652*/
    455653
    … …  
    458656\brief Graph Input-Output methods
    459657
    460 This group describes the tools for importing and exporting graphs
     658This group contains the tools for importing and exporting graphs
    461659and graph related data. Now it supports the \ref lgf-format
    462660"LEMON Graph Format", the \c DIMACS format and the encapsulated
    … …  
    465663
    466664/**
    467 @defgroup lemon_io LEMON Input-Output
     665@defgroup lemon_io LEMON Graph Format
    468666@ingroup io_group
    469667\brief Reading and writing LEMON Graph Format.
    470668
    471 This group describes methods for reading and writing
     669This group contains methods for reading and writing
    472670\ref lgf-format "LEMON Graph Format".
    473671*/
    … …  
    478676\brief General \c EPS drawer and graph exporter
    479677
    480 This group describes general \c EPS drawing methods and special
     678This group contains general \c EPS drawing methods and special
    481679graph exporting tools.
     680*/
     681
     682/**
     683@defgroup dimacs_group DIMACS Format
     684@ingroup io_group
     685\brief Read and write files in DIMACS format
     686
     687Tools to read a digraph from or write it to a file in DIMACS format data.
     688*/
     689
     690/**
     691@defgroup nauty_group NAUTY Format
     692@ingroup io_group
     693\brief Read \e Nauty format
     694
     695Tool to read graphs from \e Nauty format data.
    482696*/
    483697
    … …  
    486700\brief Skeleton classes and concept checking classes
    487701
    488 This group describes the data/algorithm skeletons and concept checking
     702This group contains the data/algorithm skeletons and concept checking
    489703classes implemented in LEMON.
    490704
    … …  
    516730\brief Skeleton and concept checking classes for graph structures
    517731
    518 This group describes the skeletons and concept checking classes of LEMON's
    519 graph structures and helper classes used to implement these.
     732This group contains the skeletons and concept checking classes of
     733graph structures.
    520734*/
    521735
    … …  
    525739\brief Skeleton and concept checking classes for maps
    526740
    527 This group describes the skeletons and concept checking classes of maps.
     741This group contains the skeletons and concept checking classes of maps.
     742*/
     743
     744/**
     745@defgroup tools Standalone Utility Applications
     746
     747Some utility applications are listed here.
     748
     749The standard compilation procedure (<tt>./configure;make</tt>) will compile
     750them, as well.
    528751*/
    529752
    … …  
    531754\anchor demoprograms
    532755
    533 @defgroup demos Demo programs
     756@defgroup demos Demo Programs
    534757
    535758Some demo programs are listed here. Their full source codes can be found in
    536759the \c demo subdirectory of the source tree.
    537760
    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 
     761In order to compile them, use the <tt>make demo</tt> or the
     762<tt>make check</tt> commands.
     763*/
     764
     765}

  • doc/lgf.dox

    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).

  • 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/mainpage.dox

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

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

  • lemon/Makefile.am

    r543 r827  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt
     3        lemon/CMakeLists.txt \
     4        lemon/config.h.cmake
    45
    56pkgconfig_DATA += lemon/lemon.pc
    … …  
    89
    910lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
    13         lemon/random.cc \
     11        lemon/arg_parser.cc \
     12        lemon/base.cc \
     13        lemon/color.cc \
     14        lemon/lp_base.cc \
     15        lemon/lp_skeleton.cc \
     16        lemon/random.cc \
    1417        lemon/bits/windows.cc
    1518
    16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     19nodist_lemon_HEADERS = lemon/config.h   
    1820
    19 nodist_lemon_HEADERS = lemon/config.h
     21lemon_libemon_la_CXXFLAGS = \
     22        $(AM_CXXFLAGS) \
     23        $(GLPK_CFLAGS) \
     24        $(CPLEX_CFLAGS) \
     25        $(SOPLEX_CXXFLAGS) \
     26        $(CLP_CXXFLAGS) \
     27        $(CBC_CXXFLAGS)
     28
     29lemon_libemon_la_LDFLAGS = \
     30        $(GLPK_LIBS) \
     31        $(CPLEX_LIBS) \
     32        $(SOPLEX_LIBS) \
     33        $(CLP_LIBS) \
     34        $(CBC_LIBS)
     35
     36if HAVE_GLPK
     37lemon_libemon_la_SOURCES += lemon/glpk.cc
     38endif
     39
     40if HAVE_CPLEX
     41lemon_libemon_la_SOURCES += lemon/cplex.cc
     42endif
     43
     44if HAVE_SOPLEX
     45lemon_libemon_la_SOURCES += lemon/soplex.cc
     46endif
     47
     48if HAVE_CLP
     49lemon_libemon_la_SOURCES += lemon/clp.cc
     50endif
     51
     52if HAVE_CBC
     53lemon_libemon_la_SOURCES += lemon/cbc.cc
     54endif
    2055
    2156lemon_HEADERS += \
    22         lemon/arg_parser.h \
     57        lemon/adaptors.h \
     58        lemon/arg_parser.h \
    2359        lemon/assert.h \
    24         lemon/bfs.h \
    25         lemon/bin_heap.h \
    26         lemon/color.h \
     60        lemon/bellman_ford.h \
     61        lemon/bfs.h \
     62        lemon/bin_heap.h \
     63        lemon/binom_heap.h \
     64        lemon/bucket_heap.h \
     65        lemon/cbc.h \
     66        lemon/circulation.h \
     67        lemon/clp.h \
     68        lemon/color.h \
    2769        lemon/concept_check.h \
    28         lemon/counter.h \
     70        lemon/connectivity.h \
     71        lemon/counter.h \
    2972        lemon/core.h \
    30         lemon/dfs.h \
    31         lemon/dijkstra.h \
    32         lemon/dim2.h \
     73        lemon/cplex.h \
     74        lemon/dfs.h \
     75        lemon/dijkstra.h \
     76        lemon/dim2.h \
     77        lemon/dimacs.h \
     78        lemon/edge_set.h \
     79        lemon/elevator.h \
    3380        lemon/error.h \
    34         lemon/graph_to_eps.h \
     81        lemon/euler.h \
     82        lemon/fib_heap.h \
     83        lemon/fourary_heap.h \
     84        lemon/full_graph.h \
     85        lemon/glpk.h \
     86        lemon/gomory_hu.h \
     87        lemon/graph_to_eps.h \
     88        lemon/grid_graph.h \
     89        lemon/hartmann_orlin.h \
     90        lemon/howard.h \
     91        lemon/hypercube_graph.h \
     92        lemon/karp.h \
     93        lemon/kary_heap.h \
    3594        lemon/kruskal.h \
     95        lemon/hao_orlin.h \
    3696        lemon/lgf_reader.h \
    3797        lemon/lgf_writer.h \
    3898        lemon/list_graph.h \
     99        lemon/lp.h \
     100        lemon/lp_base.h \
     101        lemon/lp_skeleton.h \
    39102        lemon/maps.h \
     103        lemon/matching.h \
    40104        lemon/math.h \
     105        lemon/min_cost_arborescence.h \
     106        lemon/nauty_reader.h \
     107        lemon/network_simplex.h \
     108        lemon/pairing_heap.h \
    41109        lemon/path.h \
    42         lemon/random.h \
     110        lemon/preflow.h \
     111        lemon/radix_heap.h \
     112        lemon/radix_sort.h \
     113        lemon/random.h \
    43114        lemon/smart_graph.h \
    44         lemon/time_measure.h \
    45         lemon/tolerance.h \
     115        lemon/soplex.h \
     116        lemon/static_graph.h \
     117        lemon/suurballe.h \
     118        lemon/time_measure.h \
     119        lemon/tolerance.h \
    46120        lemon/unionfind.h \
    47121        lemon/bits/windows.h
    … …  
    50124        lemon/bits/alteration_notifier.h \
    51125        lemon/bits/array_map.h \
    52         lemon/bits/base_extender.h \
    53         lemon/bits/bezier.h \
     126        lemon/bits/bezier.h \
    54127        lemon/bits/default_map.h \
    55         lemon/bits/enable_if.h \
     128        lemon/bits/edge_set_extender.h \
     129        lemon/bits/enable_if.h \
     130        lemon/bits/graph_adaptor_extender.h \
    56131        lemon/bits/graph_extender.h \
    57132        lemon/bits/map_extender.h \
    58133        lemon/bits/path_dump.h \
     134        lemon/bits/solver_bits.h \
    59135        lemon/bits/traits.h \
     136        lemon/bits/variant.h \
    60137        lemon/bits/vector_map.h
    61138

  • lemon/arg_parser.cc

    r311 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/arg_parser.h

    r311 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/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 r764  
    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).
    … …  
    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 the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     87    ///Instantiates a \c ReachedMap.
     88
     89    ///This function instantiates a \ref ReachedMap.
    8990    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     91    ///we would like to define the \ref ReachedMap.
    9192    static ReachedMap *createReachedMap(const Digraph &g)
    9293    {
    … …  
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     102    ///Instantiates a \c DistMap.
     103
     104    ///This function instantiates a \ref DistMap.
    104105    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     106    ///\ref DistMap.
    106107    static DistMap *createDistMap(const Digraph &g)
    107108    {
    … …  
    120121  ///
    121122  ///\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.
     123  ///The default type is \ref ListDigraph.
    129124#ifdef DOXYGEN
    130125  template <typename GR,
    … …  
    152147    typedef PredMapPath<Digraph, PredMap> Path;
    153148
    154     ///The traits class.
     149    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155150    typedef TR Traits;
    156151
    … …  
    214209    typedef Bfs Create;
    215210
    216     ///\name Named template parameters
     211    ///\name Named Template Parameters
    217212
    218213    ///@{
    … …  
    228223    };
    229224    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     225    ///\c PredMap type.
    231226    ///
    232227    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     228    ///\c PredMap type.
     229    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    234230    template <class T>
    235231    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    247243    };
    248244    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     245    ///\c DistMap type.
    250246    ///
    251247    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     248    ///\c DistMap type.
     249    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    253250    template <class T>
    254251    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266263    };
    267264    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     265    ///\c ReachedMap type.
    269266    ///
    270267    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     268    ///\c ReachedMap type.
     269    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272270    template <class T>
    273271    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    285283    };
    286284    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     285    ///\c ProcessedMap type.
    288286    ///
    289287    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     288    ///\c ProcessedMap type.
     289    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    291290    template <class T>
    292291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    303302    };
    304303    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306305    ///
    307306    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     307    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309308    ///If you don't set it explicitly, it will be automatically allocated.
    310309    struct SetStandardProcessedMap :
    … …  
    341340
    342341    ///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.
     342    ///If you don't use this function before calling \ref run(Node) "run()"
     343    ///or \ref init(), an instance will be allocated automatically.
     344    ///The destructor deallocates this automatically allocated map,
     345    ///of course.
    346346    ///\return <tt> (*this) </tt>
    347347    Bfs &predMap(PredMap &m)
    … …  
    358358
    359359    ///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.
     360    ///If you don't use this function before calling \ref run(Node) "run()"
     361    ///or \ref init(), an instance will be allocated automatically.
     362    ///The destructor deallocates this automatically allocated map,
     363    ///of course.
    363364    ///\return <tt> (*this) </tt>
    364365    Bfs &reachedMap(ReachedMap &m)
    … …  
    375376
    376377    ///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.
     378    ///If you don't use this function before calling \ref run(Node) "run()"
     379    ///or \ref init(), an instance will be allocated automatically.
     380    ///The destructor deallocates this automatically allocated map,
     381    ///of course.
    380382    ///\return <tt> (*this) </tt>
    381383    Bfs &processedMap(ProcessedMap &m)
    … …  
    393395    ///Sets the map that stores the distances of the nodes calculated by
    394396    ///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.
     397    ///If you don't use this function before calling \ref run(Node) "run()"
     398    ///or \ref init(), an instance will be allocated automatically.
     399    ///The destructor deallocates this automatically allocated map,
     400    ///of course.
    398401    ///\return <tt> (*this) </tt>
    399402    Bfs &distMap(DistMap &m)
    … …  
    409412  public:
    410413
    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.
     414    ///\name Execution Control
     415    ///The simplest way to execute the BFS algorithm is to use one of the
     416    ///member functions called \ref run(Node) "run()".\n
     417    ///If you need better control on the execution, you have to call
     418    ///\ref init() first, then you can add several source nodes with
     419    ///\ref addSource(). Finally the actual path computation can be
     420    ///performed with one of the \ref start() functions.
    420421
    421422    ///@{
    422423
     424    ///\brief Initializes the internal data structures.
     425    ///
    423426    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427427    void init()
    428428    {
    … …  
    558558    }
    559559
    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.
     560    ///Returns \c false if there are nodes to be processed.
     561
     562    ///Returns \c false if there are nodes to be processed
     563    ///in the queue.
    565564    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566565
    567566    ///Returns the number of the nodes to be processed.
    568567
    569     ///Returns the number of the nodes to be processed in the queue.
     568    ///Returns the number of the nodes to be processed
     569    ///in the queue.
    570570    int queueSize() const { return _queue_head-_queue_tail; }
    571571
    … …  
    732732
    733733    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     734    ///The results of the BFS algorithm can be obtained using these
    735735    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     736    ///Either \ref run(Node) "run()" or \ref start() should be called
     737    ///before using them.
    738738
    739739    ///@{
    740740
    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.
     741    ///The shortest path to the given node.
     742
     743    ///Returns the shortest path to the given node from the root(s).
     744    ///
     745    ///\warning \c t should be reached from the root(s).
     746    ///
     747    ///\pre Either \ref run(Node) "run()" or \ref init()
     748    ///must be called before using this function.
    749749    Path path(Node t) const { return Path(*G, *_pred, t); }
    750750
    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
     751    ///The distance of the given node from the root(s).
     752
     753    ///Returns the distance of the given node from the root(s).
     754    ///
     755    ///\warning If node \c v is not reached from the root(s), then
    756756    ///the return value of this function is undefined.
    757757    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     758    ///\pre Either \ref run(Node) "run()" or \ref init()
     759    ///must be called before using this function.
    760760    int dist(Node v) const { return (*_dist)[v]; }
    761761
    762     ///Returns the 'previous arc' of the shortest path tree for a node.
    763 
     762    ///\brief Returns the 'previous arc' of the shortest path tree for
     763    ///the given node.
     764    ///
    764765    ///This function returns the 'previous arc' of the shortest path
    765766    ///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.
     767    ///shortest path from a root to \c v. It is \c INVALID if \c v
     768    ///is not reached from the root(s) or if \c v is a root.
    768769    ///
    769770    ///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.
     771    ///tree used in \ref predNode() and \ref predMap().
     772    ///
     773    ///\pre Either \ref run(Node) "run()" or \ref init()
     774    ///must be called before using this function.
    774775    Arc predArc(Node v) const { return (*_pred)[v];}
    775776
    776     ///Returns the 'previous node' of the shortest path tree for a node.
    777 
     777    ///\brief Returns the 'previous node' of the shortest path tree for
     778    ///the given node.
     779    ///
    778780    ///This function returns the 'previous node' of the shortest path
    779781    ///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.
     782    ///of a shortest path from a root to \c v. It is \c INVALID
     783    ///if \c v is not reached from the root(s) or if \c v is a root.
    782784    ///
    783785    ///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.
     786    ///tree used in \ref predArc() and \ref predMap().
     787    ///
     788    ///\pre Either \ref run(Node) "run()" or \ref init()
     789    ///must be called before using this function.
    788790    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789791                                  G->source((*_pred)[v]); }
    … …  
    795797    ///of the nodes calculated by the algorithm.
    796798    ///
    797     ///\pre Either \ref run() or \ref init()
     799    ///\pre Either \ref run(Node) "run()" or \ref init()
    798800    ///must be called before using this function.
    799801    const DistMap &distMap() const { return *_dist;}
    … …  
    803805    ///
    804806    ///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()
     807    ///arcs, which form the shortest path tree (forest).
     808    ///
     809    ///\pre Either \ref run(Node) "run()" or \ref init()
    808810    ///must be called before using this function.
    809811    const PredMap &predMap() const { return *_pred;}
    810812
    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()
     813    ///Checks if the given node is reached from the root(s).
     814
     815    ///Returns \c true if \c v is reached from the root(s).
     816    ///
     817    ///\pre Either \ref run(Node) "run()" or \ref init()
    815818    ///must be called before using this function.
    816819    bool reached(Node v) const { return (*_reached)[v]; }
    … …  
    834837    ///The type of the map that stores the predecessor
    835838    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     839    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837840    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838841    ///Instantiates a PredMap.
    … …  
    849852
    850853    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     854    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    852855    ///By default it is a NullMap.
    853856    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    … …  
    869872
    870873    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     874    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872875    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873876    ///Instantiates a ReachedMap.
    … …  
    884887
    885888    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     889    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887890    typedef typename Digraph::template NodeMap<int> DistMap;
    888891    ///Instantiates a DistMap.
    … …  
    899902
    900903    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     904    ///It must conform to the \ref concepts::Path "Path" concept.
    902905    typedef lemon::Path<Digraph> Path;
    903906  };
    … …  
    905908  /// Default traits class used by BfsWizard
    906909
    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.
     910  /// Default traits class used by BfsWizard.
     911  /// \tparam GR The type of the digraph.
    913912  template<class GR>
    914913  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
    … …  
    938937    /// Constructor.
    939938
    940     /// This constructor does not require parameters, therefore it initiates
     939    /// This constructor does not require parameters, it initiates
    941940    /// all of the attributes to \c 0.
    942941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    958957  /// This auxiliary class is created to implement the
    959958  /// \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.
     959  /// It does not have own \ref run(Node) "run()" method, it uses the
     960  /// functions and features of the plain \ref Bfs.
    962961  ///
    963962  /// This class should only be used through the \ref bfs() function,
    … …  
    968967    typedef TR Base;
    969968
    970     ///The type of the digraph the algorithm runs on.
    971969    typedef typename TR::Digraph Digraph;
    972970
    … …  
    976974    typedef typename Digraph::OutArcIt OutArcIt;
    977975
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980976    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982977    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984978    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986979    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988980    typedef typename TR::Path Path;
    989981
    … …  
    10681060      SetPredMapBase(const TR &b) : TR(b) {}
    10691061    };
    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.
     1062
     1063    ///\brief \ref named-templ-param "Named parameter" for setting
     1064    ///the predecessor map.
     1065    ///
     1066    ///\ref named-templ-param "Named parameter" function for setting
     1067    ///the map that stores the predecessor arcs of the nodes.
    10751068    template<class T>
    10761069    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10861079      SetReachedMapBase(const TR &b) : TR(b) {}
    10871080    };
    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.
     1081
     1082    ///\brief \ref named-templ-param "Named parameter" for setting
     1083    ///the reached map.
     1084    ///
     1085    ///\ref named-templ-param "Named parameter" function for setting
     1086    ///the map that indicates which nodes are reached.
    10931087    template<class T>
    10941088    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    11041098      SetDistMapBase(const TR &b) : TR(b) {}
    11051099    };
    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.
     1100
     1101    ///\brief \ref named-templ-param "Named parameter" for setting
     1102    ///the distance map.
     1103    ///
     1104    ///\ref named-templ-param "Named parameter" function for setting
     1105    ///the map that stores the distances of the nodes calculated
     1106    ///by the algorithm.
    11111107    template<class T>
    11121108    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    11221118      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231119    };
    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.
     1120
     1121    ///\brief \ref named-func-param "Named parameter" for setting
     1122    ///the processed map.
     1123    ///
     1124    ///\ref named-templ-param "Named parameter" function for setting
     1125    ///the map that indicates which nodes are processed.
    11291126    template<class T>
    11301127    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    11791176  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801177  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1178  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821179  ///to the end of the parameter list.
    11831180  ///\sa BfsWizard
    … …  
    11951192  /// This class defines the interface of the BfsVisit events, and
    11961193  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1194  template <typename GR>
    11981195  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1196    typedef GR Digraph;
    12001197    typedef typename Digraph::Arc Arc;
    12011198    typedef typename Digraph::Node Node;
    … …  
    12251222  };
    12261223#else
    1227   template <typename _Digraph>
     1224  template <typename GR>
    12281225  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1226    typedef GR Digraph;
    12301227    typedef typename Digraph::Arc Arc;
    12311228    typedef typename Digraph::Node Node;
    … …  
    12551252  ///
    12561253  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1254  /// \tparam GR The type of the digraph the algorithm runs on.
     1255  template<class GR>
    12591256  struct BfsVisitDefaultTraits {
    12601257
    12611258    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1259    typedef GR Digraph;
    12631260
    12641261    /// \brief The type of the map that indicates which nodes are reached.
    12651262    ///
    12661263    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1264    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681265    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691266
    … …  
    12811278  /// \ingroup search
    12821279  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1280  /// \brief BFS algorithm class with visitor interface.
    12841281  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1282  /// This class provides an efficient implementation of the BFS algorithm
    12861283  /// with visitor interface.
    12871284  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1285  /// The BfsVisit class provides an alternative interface to the Bfs
    12891286  /// class. It works with callback mechanism, the BfsVisit object calls
    12901287  /// the member functions of the \c Visitor class on every BFS event.
    … …  
    12951292  /// instead.
    12961293  ///
    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
     1294  /// \tparam GR The type of the digraph the algorithm runs on.
     1295  /// The default type is \ref ListDigraph.
     1296  /// The value of GR is not used directly by \ref BfsVisit,
     1297  /// it is only passed to \ref BfsVisitDefaultTraits.
     1298  /// \tparam VS The Visitor type that is used by the algorithm.
     1299  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031300  /// does not observe the BFS events. If you want to observe the BFS
    13041301  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1302  /// \tparam TR Traits class to set various data types used by the
    13061303  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1304  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081305  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091306  /// a BFS visit traits class.
    13101307#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1308  template <typename GR, typename VS, typename TR>
    13121309#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1310  template <typename GR = ListDigraph,
     1311            typename VS = BfsVisitor<GR>,
     1312            typename TR = BfsVisitDefaultTraits<GR> >
    13161313#endif
    13171314  class BfsVisit {
    … …  
    13191316
    13201317    ///The traits class.
    1321     typedef _Traits Traits;
     1318    typedef TR Traits;
    13221319
    13231320    ///The type of the digraph the algorithm runs on.
    … …  
    13251322
    13261323    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1324    typedef VS Visitor;
    13281325
    13291326    ///The type of the map that indicates which nodes are reached.
    … …  
    13651362    typedef BfsVisit Create;
    13661363
    1367     /// \name Named template parameters
     1364    /// \name Named Template Parameters
    13681365
    13691366    ///@{
    … …  
    14071404    ///
    14081405    /// 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.
     1406    /// If you don't use this function before calling \ref run(Node) "run()"
     1407    /// or \ref init(), an instance will be allocated automatically.
     1408    /// The destructor deallocates this automatically allocated map,
     1409    /// of course.
    14121410    /// \return <tt> (*this) </tt>
    14131411    BfsVisit &reachedMap(ReachedMap &m) {
    … …  
    14221420  public:
    14231421
    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.
     1422    /// \name Execution Control
     1423    /// The simplest way to execute the BFS algorithm is to use one of the
     1424    /// member functions called \ref run(Node) "run()".\n
     1425    /// If you need better control on the execution, you have to call
     1426    /// \ref init() first, then you can add several source nodes with
     1427    /// \ref addSource(). Finally the actual path computation can be
     1428    /// performed with one of the \ref start() functions.
    14341429
    14351430    /// @{
    … …  
    17311726
    17321727    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1728    /// The results of the BFS algorithm can be obtained using these
    17341729    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1730    /// Either \ref run(Node) "run()" or \ref start() should be called
     1731    /// before using them.
     1732
    17381733    ///@{
    17391734
    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()
     1735    /// \brief Checks if the given node is reached from the root(s).
     1736    ///
     1737    /// Returns \c true if \c v is reached from the root(s).
     1738    ///
     1739    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441740    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1741    bool reached(Node v) const { return (*_reached)[v]; }
    17461742
    17471743    ///@}

  • 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 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).
    … …  
    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 r674  
    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).
    … …  
    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;
    159 
    160     typedef typename Parent::Graph Graph;
     160   
     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

    r314 r765  
    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;
     152      typedef Item Parent;
     153
     154    public:
    151155
    152156      ItemIt() {}
    … …  
    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;
     299      typedef Item Parent;
     300
     301    public:
    295302
    296303      ItemIt() {}
    … …  
    317324  private:
    318325
    319     const Graph& graph;
     326    const GraphType& graph;
    320327
    321328  };

  • lemon/bits/path_dump.h

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

  • lemon/bits/traits.h

    r314 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.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 r781  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
    … …  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
    … …  
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    104         /// To allow the use of digraph descriptors as key type in std::map or
    105         /// similar associative container we require this.
    106         ///
    107         /// \note This operator only have to define some strict ordering of
    108         /// the items; this order has nothing to do with the iteration
    109         /// ordering of the items.
     99        /// Artificial ordering operator.
     100        ///
     101        /// \note This operator only has to define some strict ordering of
     102        /// the nodes; this order has nothing to do with the iteration
     103        /// ordering of the nodes.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
    117110      /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
    … …  
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
    … …  
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    142         /// Sets the iterator to the first node of \c g.
    143         ///
    144         NodeIt(const Digraph&) { }
    145         /// Node -> NodeIt conversion.
    146 
    147         /// Sets the iterator to the node of \c the digraph pointed by
    148         /// the trivial iterator.
    149         /// This feature necessitates that each time we
    150         /// iterate the arc-set, the iteration order is the same.
     135        /// Sets the iterator to the first node of the given digraph.
     136        ///
     137        explicit NodeIt(const Digraph&) { }
     138        /// Sets the iterator to the given node.
     139
     140        /// Sets the iterator to the given node of the given digraph.
     141        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
    … …  
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
    … …  
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
    … …  
    175166        ///
    176167        Arc(const Arc&) { }
    177         /// Initialize the iterator to be invalid.
    178 
    179         /// Initialize the iterator to be invalid.
    180         ///
     168        /// %Invalid constructor \& conversion.
     169
     170        /// Initializes the object to be invalid.
     171        /// \sa Invalid for more details.
    181172        Arc(Invalid) { }
    182173        /// Equality operator
    183174
     175        /// Equality operator.
     176        ///
    184177        /// Two iterators are equal if and only if they point to the
    185         /// same object or both are invalid.
     178        /// same object or both are \c INVALID.
    186179        bool operator==(Arc) const { return true; }
    187180        /// Inequality operator
    188181
    189         /// \sa operator==(Arc n)
    190         ///
     182        /// Inequality operator.
    191183        bool operator!=(Arc) const { return true; }
    192184
    193185        /// Artificial ordering operator.
    194186
    195         /// To allow the use of digraph descriptors as key type in std::map or
    196         /// similar associative container we require this.
    197         ///
    198         /// \note This operator only have to define some strict ordering of
    199         /// the items; this order has nothing to do with the iteration
    200         /// ordering of the items.
     187        /// Artificial ordering operator.
     188        ///
     189        /// \note This operator only has to define some strict ordering of
     190        /// the arcs; this order has nothing to do with the iteration
     191        /// ordering of the arcs.
    201192        bool operator<(Arc) const { return false; }
    202193      };
    203194
    204       /// This iterator goes trough the outgoing arcs of a node.
     195      /// Iterator class for the outgoing arcs of a node.
    205196
    206197      /// This iterator goes trough the \e outgoing arcs of a certain node
    … …  
    208199      /// Its usage is quite simple, for example you can count the number
    209200      /// of outgoing arcs of a node \c n
    210       /// in digraph \c g of type \c Digraph as follows.
     201      /// in a digraph \c g of type \c %Digraph as follows.
    211202      ///\code
    212203      /// int count=0;
    213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     204      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    214205      ///\endcode
    215 
    216206      class OutArcIt : public Arc {
    217207      public:
    218208        /// Default constructor
    219209
    220         /// @warning The default constructor sets the iterator
    221         /// to an undefined value.
     210        /// Default constructor.
     211        /// \warning It sets the iterator to an undefined value.
    222212        OutArcIt() { }
    223213        /// Copy constructor.
    … …  
    226216        ///
    227217        OutArcIt(const OutArcIt& e) : Arc(e) { }
    228         /// Initialize the iterator to be invalid.
    229 
    230         /// Initialize the iterator to be invalid.
    231         ///
     218        /// %Invalid constructor \& conversion.
     219
     220        /// Initializes the iterator to be invalid.
     221        /// \sa Invalid for more details.
    232222        OutArcIt(Invalid) { }
    233         /// This constructor sets the iterator to the first outgoing arc.
    234 
    235         /// This constructor sets the iterator to the first outgoing arc of
    236         /// the node.
     223        /// Sets the iterator to the first outgoing arc.
     224
     225        /// Sets the iterator to the first outgoing arc of the given node.
     226        ///
    237227        OutArcIt(const Digraph&, const Node&) { }
    238         /// Arc -> OutArcIt conversion
    239 
    240         /// Sets the iterator to the value of the trivial iterator.
    241         /// This feature necessitates that each time we
    242         /// iterate the arc-set, the iteration order is the same.
     228        /// Sets the iterator to the given arc.
     229
     230        /// Sets the iterator to the given arc of the given digraph.
     231        ///
    243232        OutArcIt(const Digraph&, const Arc&) { }
    244         ///Next outgoing arc
     233        /// Next outgoing arc
    245234
    246235        /// Assign the iterator to the next
    … …  
    249238      };
    250239
    251       /// This iterator goes trough the incoming arcs of a node.
     240      /// Iterator class for the incoming arcs of a node.
    252241
    253242      /// This iterator goes trough the \e incoming arcs of a certain node
    254243      /// of a digraph.
    255244      /// Its usage is quite simple, for example you can count the number
    256       /// of outgoing arcs of a node \c n
    257       /// in digraph \c g of type \c Digraph as follows.
     245      /// of incoming arcs of a node \c n
     246      /// in a digraph \c g of type \c %Digraph as follows.
    258247      ///\code
    259248      /// int count=0;
    260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     249      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    261250      ///\endcode
    262 
    263251      class InArcIt : public Arc {
    264252      public:
    265253        /// Default constructor
    266254
    267         /// @warning The default constructor sets the iterator
    268         /// to an undefined value.
     255        /// Default constructor.
     256        /// \warning It sets the iterator to an undefined value.
    269257        InArcIt() { }
    270258        /// Copy constructor.
    … …  
    273261        ///
    274262        InArcIt(const InArcIt& e) : Arc(e) { }
    275         /// Initialize the iterator to be invalid.
    276 
    277         /// Initialize the iterator to be invalid.
    278         ///
     263        /// %Invalid constructor \& conversion.
     264
     265        /// Initializes the iterator to be invalid.
     266        /// \sa Invalid for more details.
    279267        InArcIt(Invalid) { }
    280         /// This constructor sets the iterator to first incoming arc.
    281 
    282         /// This constructor set the iterator to the first incoming arc of
    283         /// the node.
     268        /// Sets the iterator to the first incoming arc.
     269
     270        /// Sets the iterator to the first incoming arc of the given node.
     271        ///
    284272        InArcIt(const Digraph&, const Node&) { }
    285         /// Arc -> InArcIt conversion
    286 
    287         /// Sets the iterator to the value of the trivial iterator \c e.
    288         /// This feature necessitates that each time we
    289         /// iterate the arc-set, the iteration order is the same.
     273        /// Sets the iterator to the given arc.
     274
     275        /// Sets the iterator to the given arc of the given digraph.
     276        ///
    290277        InArcIt(const Digraph&, const Arc&) { }
    291278        /// Next incoming arc
    292279
    293         /// Assign the iterator to the next inarc of the corresponding node.
    294         ///
     280        /// Assign the iterator to the next
     281        /// incoming arc of the corresponding node.
    295282        InArcIt& operator++() { return *this; }
    296283      };
    297       /// This iterator goes through each arc.
    298 
    299       /// This iterator goes through each arc of a digraph.
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
    300288      /// Its usage is quite simple, for example you can count the number
    301       /// of arcs in a digraph \c g of type \c Digraph as follows:
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    302290      ///\code
    303291      /// int count=0;
    304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
     292      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
    305293      ///\endcode
    306294      class ArcIt : public Arc {
    … …  
    308296        /// Default constructor
    309297
    310         /// @warning The default constructor sets the iterator
    311         /// to an undefined value.
     298        /// Default constructor.
     299        /// \warning It sets the iterator to an undefined value.
    312300        ArcIt() { }
    313301        /// Copy constructor.
    … …  
    316304        ///
    317305        ArcIt(const ArcIt& e) : Arc(e) { }
    318         /// Initialize the iterator to be invalid.
    319 
    320         /// Initialize the iterator to be invalid.
    321         ///
     306        /// %Invalid constructor \& conversion.
     307
     308        /// Initializes the iterator to be invalid.
     309        /// \sa Invalid for more details.
    322310        ArcIt(Invalid) { }
    323         /// This constructor sets the iterator to the first arc.
    324 
    325         /// This constructor sets the iterator to the first arc of \c g.
    326         ///@param g the digraph
    327         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
    328         /// Arc -> ArcIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the arc-set, the iteration order is the same.
     311        /// Sets the iterator to the first arc.
     312
     313        /// Sets the iterator to the first arc of the given digraph.
     314        ///
     315        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     316        /// Sets the iterator to the given arc.
     317
     318        /// Sets the iterator to the given arc of the given digraph.
     319        ///
    333320        ArcIt(const Digraph&, const Arc&) { }
    334         ///Next arc
     321        /// Next arc
    335322
    336323        /// Assign the iterator to the next arc.
     324        ///
    337325        ArcIt& operator++() { return *this; }
    338326      };
    339       ///Gives back the target node of an arc.
    340 
    341       ///Gives back the target node of an arc.
    342       ///
     327
     328      /// \brief The source node of the arc.
     329      ///
     330      /// Returns the source node of the given arc.
     331      Node source(Arc) const { return INVALID; }
     332
     333      /// \brief The target node of the arc.
     334      ///
     335      /// Returns the target node of the given arc.
    343336      Node target(Arc) const { return INVALID; }
    344       ///Gives back the source node of an arc.
    345 
    346       ///Gives back the source node of an arc.
    347       ///
    348       Node source(Arc) const { return INVALID; }
    349 
    350       /// \brief Returns the ID of the node.
     337
     338      /// \brief The ID of the node.
     339      ///
     340      /// Returns the ID of the given node.
    351341      int id(Node) const { return -1; }
    352342
    353       /// \brief Returns the ID of the arc.
     343      /// \brief The ID of the arc.
     344      ///
     345      /// Returns the ID of the given arc.
    354346      int id(Arc) const { return -1; }
    355347
    356       /// \brief Returns the node with the given ID.
    357       ///
    358       /// \pre The argument should be a valid node ID in the graph.
     348      /// \brief The node with the given ID.
     349      ///
     350      /// Returns the node with the given ID.
     351      /// \pre The argument should be a valid node ID in the digraph.
    359352      Node nodeFromId(int) const { return INVALID; }
    360353
    361       /// \brief Returns the arc with the given ID.
    362       ///
    363       /// \pre The argument should be a valid arc ID in the graph.
     354      /// \brief The arc with the given ID.
     355      ///
     356      /// Returns the arc with the given ID.
     357      /// \pre The argument should be a valid arc ID in the digraph.
    364358      Arc arcFromId(int) const { return INVALID; }
    365359
    366       /// \brief Returns an upper bound on the node IDs.
     360      /// \brief An upper bound on the node IDs.
     361      ///
     362      /// Returns an upper bound on the node IDs.
    367363      int maxNodeId() const { return -1; }
    368364
    369       /// \brief Returns an upper bound on the arc IDs.
     365      /// \brief An upper bound on the arc IDs.
     366      ///
     367      /// Returns an upper bound on the arc IDs.
    370368      int maxArcId() const { return -1; }
    371369
    … …  
    393391      int maxId(Arc) const { return -1; }
    394392
     393      /// \brief The opposite node on the arc.
     394      ///
     395      /// Returns the opposite node on the given arc.
     396      Node oppositeNode(Node, Arc) const { return INVALID; }
     397
    395398      /// \brief The base node of the iterator.
    396399      ///
    397       /// Gives back the base node of the iterator.
    398       /// It is always the target of the pointed arc.
    399       Node baseNode(const InArcIt&) const { return INVALID; }
     400      /// Returns the base node of the given outgoing arc iterator
     401      /// (i.e. the source node of the corresponding arc).
     402      Node baseNode(OutArcIt) const { return INVALID; }
    400403
    401404      /// \brief The running node of the iterator.
    402405      ///
    403       /// Gives back the running node of the iterator.
    404       /// It is always the source of the pointed arc.
    405       Node runningNode(const InArcIt&) const { return INVALID; }
     406      /// Returns the running node of the given outgoing arc iterator
     407      /// (i.e. the target node of the corresponding arc).
     408      Node runningNode(OutArcIt) const { return INVALID; }
    406409
    407410      /// \brief The base node of the iterator.
    408411      ///
    409       /// Gives back the base node of the iterator.
    410       /// It is always the source of the pointed arc.
    411       Node baseNode(const OutArcIt&) const { return INVALID; }
     412      /// Returns the base node of the given incomming arc iterator
     413      /// (i.e. the target node of the corresponding arc).
     414      Node baseNode(InArcIt) const { return INVALID; }
    412415
    413416      /// \brief The running node of the iterator.
    414417      ///
    415       /// Gives back the running node of the iterator.
    416       /// It is always the target of the pointed arc.
    417       Node runningNode(const OutArcIt&) const { return INVALID; }
    418 
    419       /// \brief The opposite node on the given arc.
    420       ///
    421       /// Gives back the opposite node on the given arc.
    422       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423 
    424       /// \brief Read write map of the nodes to type \c T.
    425       ///
    426       /// ReadWrite map of the nodes to type \c T.
    427       /// \sa Reference
     418      /// Returns the running node of the given incomming arc iterator
     419      /// (i.e. the source node of the corresponding arc).
     420      Node runningNode(InArcIt) const { return INVALID; }
     421
     422      /// \brief Standard graph map type for the nodes.
     423      ///
     424      /// Standard graph map type for the nodes.
     425      /// It conforms to the ReferenceMap concept.
    428426      template<class T>
    429       class NodeMap : public ReadWriteMap< Node, T > {
    430       public:
    431 
    432         ///\e
    433         NodeMap(const Digraph&) { }
    434         ///\e
     427      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
     428      public:
     429
     430        /// Constructor
     431        explicit NodeMap(const Digraph&) { }
     432        /// Constructor with given initial value
    435433        NodeMap(const Digraph&, T) { }
    436434
    437435      private:
    438436        ///Copy constructor
    439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     437        NodeMap(const NodeMap& nm) :
     438          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440439        ///Assignment operator
    441440        template <typename CMap>
    … …  
    446445      };
    447446
    448       /// \brief Read write map of the arcs to type \c T.
    449       ///
    450       /// Reference map of the arcs to type \c T.
    451       /// \sa Reference
     447      /// \brief Standard graph map type for the arcs.
     448      ///
     449      /// Standard graph map type for the arcs.
     450      /// It conforms to the ReferenceMap concept.
    452451      template<class T>
    453       class ArcMap : public ReadWriteMap<Arc,T> {
    454       public:
    455 
    456         ///\e
    457         ArcMap(const Digraph&) { }
    458         ///\e
     452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
     453      public:
     454
     455        /// Constructor
     456        explicit ArcMap(const Digraph&) { }
     457        /// Constructor with given initial value
    459458        ArcMap(const Digraph&, T) { }
     459
    460460      private:
    461461        ///Copy constructor
    462         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     462        ArcMap(const ArcMap& em) :
     463          ReferenceMap<Arc, T, T&, const T&>(em) { }
    463464        ///Assignment operator
    464465        template <typename CMap>
    … …  
    472473      struct Constraints {
    473474        void constraints() {
     475          checkConcept<BaseDigraphComponent, _Digraph>();
    474476          checkConcept<IterableDigraphComponent<>, _Digraph>();
    475477          checkConcept<IDableDigraphComponent<>, _Digraph>();
    … …  
    485487
    486488
    487 #endif // LEMON_CONCEPT_DIGRAPH_H
     489#endif

  • lemon/concepts/graph.h

    r263 r781  
    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).
    … …  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of Undirected Graphs.
    22 
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
     21///\brief The concept of undirected graphs.
     22
     23#ifndef LEMON_CONCEPTS_GRAPH_H
     24#define LEMON_CONCEPTS_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/graph.h>
     27#include <lemon/concepts/maps.h>
     28#include <lemon/concept_check.h>
    2829#include <lemon/core.h>
    2930
    … …  
    3334    /// \ingroup graph_concepts
    3435    ///
    35     /// \brief Class describing the concept of Undirected Graphs.
     36    /// \brief Class describing the concept of undirected graphs.
    3637    ///
    37     /// This class describes the common interface of all Undirected
    38     /// Graphs.
     38    /// This class describes the common interface of all undirected
     39    /// graphs.
    3940    ///
    40     /// As all concept describing classes it provides only interface
    41     /// without any sensible implementation. So any algorithm for
    42     /// undirected graph should compile with this class, but it will not
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// undirected graphs should compile with this class, but it will not
    4344    /// run properly, of course.
     45    /// An actual graph implementation like \ref ListGraph or
     46    /// \ref SmartGraph may have additional functionality.   
    4447    ///
    45     /// The LEMON undirected graphs also fulfill the concept of
    46     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
    47     /// Concept"). Each edges can be seen as two opposite
    48     /// directed arc and consequently the undirected graph can be
    49     /// seen as the direceted graph of these directed arcs. The
    50     /// Graph has the Edge inner class for the edges and
    51     /// the Arc type for the directed arcs. The Arc type is
    52     /// convertible to Edge or inherited from it so from a directed
    53     /// arc we can get the represented edge.
     48    /// The undirected graphs also fulfill the concept of \ref Digraph
     49    /// "directed graphs", since each edge can also be regarded as two
     50    /// oppositely directed arcs.
     51    /// Undirected graphs provide an Edge type for the undirected edges and
     52    /// an Arc type for the directed arcs. The Arc type is convertible to
     53    /// Edge or inherited from it, i.e. the corresponding edge can be
     54    /// obtained from an arc.
     55    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
     56    /// and ArcMap classes can be used for the arcs (just like in digraphs).
     57    /// Both InArcIt and OutArcIt iterates on the same edges but with
     58    /// opposite direction. IncEdgeIt also iterates on the same edges
     59    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
     60    /// only to Edge.
    5461    ///
    55     /// In the sense of the LEMON each edge has a default
    56     /// direction (it should be in every computer implementation,
    57     /// because the order of edge's nodes defines an
    58     /// orientation). With the default orientation we can define that
    59     /// the directed arc is forward or backward directed. With the \c
    60     /// direction() and \c direct() function we can get the direction
    61     /// of the directed arc and we can direct an edge.
     62    /// In LEMON, each undirected edge has an inherent orientation.
     63    /// Thus it can defined if an arc is forward or backward oriented in
     64    /// an undirected graph with respect to this default oriantation of
     65    /// the represented edge.
     66    /// With the direction() and direct() functions the direction
     67    /// of an arc can be obtained and set, respectively.
    6268    ///
    63     /// The EdgeIt is an iterator for the edges. We can use
    64     /// the EdgeMap to map values for the edges. The InArcIt and
    65     /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncEdgeIt iterates also on the same edges
    67     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    68     /// to Edge.
     69    /// Only nodes and edges can be added to or removed from an undirected
     70    /// graph and the corresponding arcs are added or removed automatically.
     71    ///
     72    /// \sa Digraph
    6973    class Graph {
     74    private:
     75      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
     76      Graph(const Graph&) {}
     77      /// \brief Assignment of a graph to another one is \e not allowed.
     78      /// Use DigraphCopy instead.
     79      void operator=(const Graph&) {}
     80
    7081    public:
    71       /// \brief The undirected graph should be tagged by the
    72       /// UndirectedTag.
    73       ///
    74       /// The undirected graph should be tagged by the UndirectedTag. This
    75       /// tag helps the enable_if technics to make compile time
     82      /// Default constructor.
     83      Graph() {}
     84
     85      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
     86      ///
     87      /// Undirected graphs should be tagged with \c UndirectedTag.
     88      ///
     89      /// This tag helps the \c enable_if technics to make compile time
    7690      /// specializations for undirected graphs.
    7791      typedef True UndirectedTag;
    7892
    79       /// \brief The base type of node iterators,
    80       /// or in other words, the trivial node iterator.
    81       ///
    82       /// This is the base type of each node iterator,
    83       /// thus each kind of node iterator converts to this.
    84       /// More precisely each kind of node iterator should be inherited
    85       /// from the trivial node iterator.
     93      /// The node type of the graph
     94
     95      /// This class identifies a node of the graph. It also serves
     96      /// as a base class of the node iterators,
     97      /// thus they convert to this type.
    8698      class Node {
    8799      public:
    88100        /// Default constructor
    89101
    90         /// @warning The default constructor sets the iterator
    91         /// to an undefined value.</