COIN-OR::LEMON - Graph Library

Ignore:
Files:
71 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 r727  
    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})
    2137
    2238ENABLE_TESTING()
    2339
    2440ADD_SUBDIRECTORY(lemon)
    25 ADD_SUBDIRECTORY(demo)
    26 ADD_SUBDIRECTORY(doc)
    27 ADD_SUBDIRECTORY(test)
     41IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     42  ADD_SUBDIRECTORY(demo)
     43  ADD_SUBDIRECTORY(tools)
     44  ADD_SUBDIRECTORY(doc)
     45  ADD_SUBDIRECTORY(test)
     46ENDIF()
    2847
    29 IF(WIN32)
     48CONFIGURE_FILE(
     49  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
     50  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     51  @ONLY
     52)
     53IF(UNIX)
     54  INSTALL(
     55    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     56    DESTINATION share/lemon/cmake
     57  )
     58ELSEIF(WIN32)
     59  INSTALL(
     60    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
     61    DESTINATION cmake
     62  )
     63ENDIF()
     64
     65IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
    3066  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    3167  SET(CPACK_PACKAGE_VENDOR "EGRES")
    3268  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")
     69    "LEMON - Library for Efficient Modeling and Optimization in Networks")
     70  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3571
    3672  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    4177    "${PROJECT_NAME} ${PROJECT_VERSION}")
    4278
    43   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     79  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4480
    4581  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    4682  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     83  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    4784  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4885
     
    5188  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    5289    "DLL and import library")
     90  SET(CPACK_COMPONENT_BIN_DESCRIPTION
     91    "Command line utilities")
    5392  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    5493    "Doxygen generated documentation")
     
    72111
    73112  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")
     113  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     114  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     115  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    77116  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    78117  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    89128
    90129  INCLUDE(CPack)
    91 ENDIF(WIN32)
     130ENDIF()
  • 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 r939  
     12010-03-08 Version 1.1.2 released
     2
     3        Bugfix release.
     4
     5        #317: Fix (and improve) error message in mip_test.cc
     6              Remove unnecessary OsiCbc dependency
     7        #250: Fix in pathSource() and pathTarget()
     8        #322: Distribute LEMONConfig.cmake.in
     9        #321: Use pathCopy(from,to) instead of copyPath(to,from)
     10        #330: Bug fix in map_extender.h
     11        #335: Fix clear() function in ExtendFindEnum
     12        #337: Use void* as LPX object pointer
     13        #336: Fix the date field comment of graphToEps() output
     14        #323: Bug fix in Suurballe
     15
     162009-10-03 Version 1.1.1 released
     17
     18        Bugfix release.
     19
     20        #295: Suppress MSVC warnings using pragmas
     21        ----: Various CMAKE related improvements
     22              * Remove duplications from doc/CMakeLists.txt
     23              * Rename documentation install folder from 'docs' to 'html'
     24              * Add tools/CMakeLists.txt to the tarball
     25              * Generate and install LEMONConfig.cmake
     26              * Change the label of the html project in Visual Studio
     27              * Fix the check for the 'long long' type
     28              * Put the version string into config.h
     29              * Minor CMake improvements
     30              * Set the version to 'hg-tip' if everything fails
     31        #311: Add missing 'explicit' keywords
     32        #302: Fix the implementation and doc of CrossRefMap
     33        #308: Remove duplicate list_graph.h entry from source list
     34        #307: Bug fix in Preflow and Circulation
     35
     362009-05-13 Version 1.1 released
     37
     38        This is the second stable release of the 1.x series. It
     39        features a better coverage of the tools available in the 0.x
     40        series, a thoroughly reworked LP/MIP interface plus various
     41        improvements in the existing tools.
     42
     43        * Much improved M$ Windows support
     44          * Various improvements in the CMAKE build system
     45          * Compilation warnings are fixed/suppressed
     46        * Support IBM xlC compiler
     47        * New algorithms
     48          * Connectivity related algorithms (#61)
     49          * Euler walks (#65)
     50          * Preflow push-relabel max. flow algorithm (#176)
     51          * Circulation algorithm (push-relabel based) (#175)
     52          * Suurballe algorithm (#47)
     53          * Gomory-Hu algorithm (#66)
     54          * Hao-Orlin algorithm (#58)
     55          * Edmond's maximum cardinality and weighted matching algorithms
     56            in general graphs (#48,#265)
     57          * Minimum cost arborescence/branching (#60)
     58          * Network Simplex min. cost flow algorithm (#234)
     59        * New data structures
     60          * Full graph structure (#57)
     61          * Grid graph structure (#57)
     62          * Hypercube graph structure (#57)
     63          * Graph adaptors (#67)
     64          * ArcSet and EdgeSet classes (#67)
     65          * Elevator class (#174)
     66        * Other new tools
     67          * LP/MIP interface (#44)
     68            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
     69          * Reader for the Nauty file format (#55)
     70          * DIMACS readers (#167)
     71          * Radix sort algorithms (#72)
     72          * RangeIdMap and CrossRefMap (#160)
     73        * New command line tools
     74          * DIMACS to LGF converter (#182)
     75          * lgf-gen - a graph generator (#45)
     76          * DIMACS solver utility (#226)
     77        * Other code improvements
     78          * Lognormal distribution added to Random (#102)
     79          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
     80          * The standard maps of graphs are guaranteed to be
     81            reference maps (#190)
     82        * Miscellaneous
     83          * Various doc improvements
     84          * Improved 0.x -> 1.x converter script
     85
     86        * Several bugfixes (compared to release 1.0):
     87          #170: Bugfix SmartDigraph::split()
     88          #171: Bugfix in SmartGraph::restoreSnapshot()
     89          #172: Extended test cases for graphs and digraphs
     90          #173: Bugfix in Random
     91                * operator()s always return a double now
     92                * the faulty real<Num>(Num) and real<Num>(Num,Num)
     93                  have been removed
     94          #187: Remove DijkstraWidestPathOperationTraits
     95          #61:  Bugfix in DfsVisit
     96          #193: Bugfix in GraphReader::skipSection()
     97          #195: Bugfix in ConEdgeIt()
     98          #197: Bugfix in heap unionfind
     99                * This bug affects Edmond's general matching algorithms
     100          #207: Fix 'make install' without 'make html' using CMAKE
     101          #208: Suppress or fix VS2008 compilation warnings
     102          ----: Update the LEMON icon
     103          ----: Enable the component-based installer
     104                (in installers made by CPACK)
     105          ----: Set the proper version for CMAKE in the tarballs
     106                (made by autotools)
     107          ----: Minor clarification in the LICENSE file
     108          ----: Add missing unistd.h include to time_measure.h
     109          #204: Compilation bug fixed in graph_to_eps.h with VS2005
     110          #214,#215: windows.h should never be included by lemon headers
     111          #230: Build systems check the availability of 'long long' type
     112          #229: Default implementation of Tolerance<> is used for integer types
     113          #211,#212: Various fixes for compiling on AIX
     114          ----: Improvements in CMAKE config
     115                - docs is installed in share/doc/
     116                - detects newer versions of Ghostscript
     117          #239: Fix missing 'inline' specifier in time_measure.h
     118          #274,#280: Install lemon/config.h
     119          #275: Prefix macro names with LEMON_ in lemon/config.h
     120          ----: Small script for making the release tarballs added
     121          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     122
    11232009-03-27 LEMON joins to the COIN-OR initiative
    2124
  • 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 r727  
    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.
     
    5356
    5457dnl 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"
     58if test "$GXX" = yes -a "$ICC" = no; then
     59  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"
    5760fi
     61AC_SUBST([WARNINGCXXFLAGS])
    5862
    5963dnl Checks for libraries.
    60 #LX_CHECK_GLPK
    61 #LX_CHECK_CPLEX
    62 #LX_CHECK_SOPLEX
     64LX_CHECK_GLPK
     65LX_CHECK_CPLEX
     66LX_CHECK_SOPLEX
     67LX_CHECK_COIN
    6368
    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"])
     69AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     70AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    7671
    7772dnl Disable/enable building the binary tools.
     
    108103AC_CONFIG_FILES([
    109104Makefile
     105demo/Makefile
    110106cmake/version.cmake
    111107doc/Doxyfile
     
    121117echo
    122118echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     119echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124120echo
    125121echo Compiler supports long long... : $long_long_found
    126122echo
    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
     123echo GLPK support.................. : $lx_glpk_found
     124echo CPLEX support................. : $lx_cplex_found
     125echo SOPLEX support................ : $lx_soplex_found
     126echo CLP support................... : $lx_clp_found
     127echo CBC support................... : $lx_cbc_found
     128echo
    132129echo Build additional tools........ : $enable_tools
    133130echo
  • 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 r726  
    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
    1112IF(DOXYGEN_EXECUTABLE 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 ${DOXYGEN_EXECUTABLE} Doxyfile
     32    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     33  )
     34
     35  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
     36
    1337  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})
     38    INSTALL(
     39      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     40      DESTINATION share/doc/lemon/html
     41      COMPONENT html_documentation
     42    )
    2543  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)
     44    INSTALL(
     45      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     46      DESTINATION doc
     47      COMPONENT html_documentation
     48    )
     49  ENDIF()
     50
     51ENDIF()
  • doc/Doxyfile.in

    r316 r379  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     69SHOW_USED_FILES        = NO
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES
  • doc/Makefile.am

    r317 r720  
    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 = \
     
    3849        if test ${gs_found} = yes; then \
    3950          $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
     51        else \
     52          echo; \
     53          echo "Ghostscript not found."; \
     54          echo; \
     55          exit 1; \
     56        fi
     57
     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=$@ $<; \
    4062        else \
    4163          echo; \
     
    7092install-html-local: doc/html
    7193        @$(NORMAL_INSTALL)
    72         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     94        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
    7395        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    7496          f="`echo $$p | sed -e 's|^.*/||'`"; \
    75           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    76           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     97          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
     98          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
    7799        done
    78100
     
    81103        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    82104          f="`echo $$p | sed -e 's|^.*/||'`"; \
    83           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    84           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     105          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
     106          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
    85107        done
    86108
  • 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 r844  
    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.
     
    184247\brief Auxiliary data structures implemented in LEMON.
    185248
    186 This group describes some data structures implemented in LEMON in
     249This group contains some data structures implemented in LEMON in
    187250order to make it easier to implement combinatorial algorithms.
    188251*/
     
    190253/**
    191254@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     255\brief This group contains the several algorithms
    193256implemented in LEMON.
    194257
    195 This group describes the several algorithms
     258This group contains the several algorithms
    196259implemented in LEMON.
    197260*/
     
    202265\brief Common graph search algorithms.
    203266
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     267This group contains the common graph search algorithms, namely
     268\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206269*/
    207270
     
    211274\brief Algorithms for finding shortest paths.
    212275
    213 This group describes the algorithms for finding shortest paths in graphs.
     276This group contains the algorithms for finding shortest paths in digraphs.
     277
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
     280 - \ref Suurballe A successive shortest path algorithm for finding
     281   arc-disjoint paths between two nodes having minimum total length.
    214282*/
    215283
     
    219287\brief Algorithms for finding maximum flows.
    220288
    221 This group describes the algorithms for finding maximum flows and
     289This group contains the algorithms for finding maximum flows and
    222290feasible circulations.
    223291
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    234 
    235 LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     292The \e maximum \e flow \e problem is to find a flow of maximum value between
     293a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     294digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     295\f$s, t \in V\f$ source and target nodes.
     296A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     297following optimization problem.
     298
     299\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     300\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     301    \quad \forall u\in V\setminus\{s,t\} \f]
     302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
     303
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
     308
     309\ref Circulation is a preflow push-relabel algorithm implemented directly
     310for finding feasible circulations, which is a somewhat different problem,
     311but it is strongly related to maximum flow.
     312For more information, see \ref Circulation.
     313*/
     314
     315/**
     316@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    249317@ingroup algs
    250318
    251319\brief Algorithms for finding minimum cost flows and circulations.
    252320
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
     321This group contains the algorithms for finding minimum cost flows and
     322circulations. For more information about this problem and its dual
     323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     324
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    255328*/
    256329
     
    261334\brief Algorithms for finding minimum cut in graphs.
    262335
    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
     336This group contains the algorithms for finding minimum cut in graphs.
     337
     338The \e minimum \e cut \e problem is to find a non-empty and non-complete
     339\f$X\f$ subset of the nodes with minimum overall capacity on
     340outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     341\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269342cut is the \f$X\f$ solution of the next optimization problem:
    270343
    271344\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]
     345    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273346
    274347LEMON contains several algorithms related to minimum cut problems:
    275348
    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
     349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     350  in directed graphs.
     351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     352  all-pairs minimum cut in undirected graphs.
    282353
    283354If 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
     355see the \ref max_flow "maximum flow problem".
     356*/
     357
     358/**
     359@defgroup graph_properties Connectivity and Other Graph Properties
    289360@ingroup algs
    290361\brief Algorithms for discovering the graph properties
    291362
    292 This group describes the algorithms for discovering the graph properties
     363This group contains the algorithms for discovering the graph properties
    293364like connectivity, bipartiteness, euler property, simplicity etc.
    294365
     
    298369
    299370/**
    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
    309 */
    310 
    311 /**
    312371@defgroup matching Matching Algorithms
    313372@ingroup algs
    314373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315374
    316 This group contains algorithm objects and functions to calculate
    317 matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    319378
    320379There are several different algorithms for calculate matchings in
    321 graphs.  The matching problems in bipartite graphs are generally
    322 easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     380graphs. The goal of the matching optimization
     381can be finding maximum cardinality, maximum weight or minimum cost
    324382matching. The search can be constrained to find perfect or
    325383maximum cardinality matching.
    326384
    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
     385The matching algorithms implemented in LEMON:
     386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     387  maximum cardinality matching in general graphs.
     388- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     389  maximum weighted matching in general graphs.
     390- \ref MaxWeightedPerfectMatching
     391  Edmond's blossom shrinking algorithm for calculating maximum weighted
     392  perfect matching in general graphs.
    347393
    348394\image html bipartite_matching.png
     
    353399@defgroup spantree Minimum Spanning Tree Algorithms
    354400@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
     401\brief Algorithms for finding minimum cost spanning trees and arborescences.
     402
     403This group contains the algorithms for finding minimum cost spanning
     404trees and arborescences.
    359405*/
    360406
     
    364410\brief Auxiliary algorithms implemented in LEMON.
    365411
    366 This group describes some algorithms implemented in LEMON
     412This group contains some algorithms implemented in LEMON
    367413in order to make it easier to implement complex algorithms.
    368414*/
    369415
    370416/**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
     417@defgroup gen_opt_group General Optimization Tools
     418\brief This group contains some general optimization frameworks
    376419implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
    382 implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
     420
     421This group contains some general optimization frameworks
    385422implemented in LEMON.
    386423*/
     
    391428\brief Lp and Mip solver interfaces for LEMON.
    392429
    393 This group describes Lp and Mip solver interfaces for LEMON. The
     430This group contains Lp and Mip solver interfaces for LEMON. The
    394431various LP solvers could be used in the same manner with this
    395432interface.
    396 */
    397 
    398 /**
    399 @defgroup lp_utils Tools for Lp and Mip Solvers
    400 @ingroup lp_group
    401 \brief Helper tools to the Lp and Mip solvers.
    402 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
    413433*/
    414434
     
    425445\brief Simple basic graph utilities.
    426446
    427 This group describes some simple basic graph utilities.
     447This group contains some simple basic graph utilities.
    428448*/
    429449
     
    433453\brief Tools for development, debugging and testing.
    434454
    435 This group describes several useful tools for development,
     455This group contains several useful tools for development,
    436456debugging and testing.
    437457*/
     
    442462\brief Simple tools for measuring the performance of algorithms.
    443463
    444 This group describes simple tools for measuring the performance
     464This group contains simple tools for measuring the performance
    445465of algorithms.
    446466*/
     
    451471\brief Exceptions defined in LEMON.
    452472
    453 This group describes the exceptions defined in LEMON.
     473This group contains the exceptions defined in LEMON.
    454474*/
    455475
     
    458478\brief Graph Input-Output methods
    459479
    460 This group describes the tools for importing and exporting graphs
     480This group contains the tools for importing and exporting graphs
    461481and graph related data. Now it supports the \ref lgf-format
    462482"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    465485
    466486/**
    467 @defgroup lemon_io LEMON Input-Output
     487@defgroup lemon_io LEMON Graph Format
    468488@ingroup io_group
    469489\brief Reading and writing LEMON Graph Format.
    470490
    471 This group describes methods for reading and writing
     491This group contains methods for reading and writing
    472492\ref lgf-format "LEMON Graph Format".
    473493*/
     
    478498\brief General \c EPS drawer and graph exporter
    479499
    480 This group describes general \c EPS drawing methods and special
     500This group contains general \c EPS drawing methods and special
    481501graph exporting tools.
     502*/
     503
     504/**
     505@defgroup dimacs_group DIMACS format
     506@ingroup io_group
     507\brief Read and write files in DIMACS format
     508
     509Tools to read a digraph from or write it to a file in DIMACS format data.
     510*/
     511
     512/**
     513@defgroup nauty_group NAUTY Format
     514@ingroup io_group
     515\brief Read \e Nauty format
     516
     517Tool to read graphs from \e Nauty format data.
    482518*/
    483519
     
    486522\brief Skeleton classes and concept checking classes
    487523
    488 This group describes the data/algorithm skeletons and concept checking
     524This group contains the data/algorithm skeletons and concept checking
    489525classes implemented in LEMON.
    490526
     
    516552\brief Skeleton and concept checking classes for graph structures
    517553
    518 This group describes the skeletons and concept checking classes of LEMON's
     554This group contains the skeletons and concept checking classes of LEMON's
    519555graph structures and helper classes used to implement these.
    520556*/
     
    525561\brief Skeleton and concept checking classes for maps
    526562
    527 This group describes the skeletons and concept checking classes of maps.
     563This group contains the skeletons and concept checking classes of maps.
    528564*/
    529565
     
    531567\anchor demoprograms
    532568
    533 @defgroup demos Demo programs
     569@defgroup demos Demo Programs
    534570
    535571Some demo programs are listed here. Their full source codes can be found in
    536572the \c demo subdirectory of the source tree.
    537573
    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
     574In order to compile them, use the <tt>make demo</tt> or the
     575<tt>make check</tt> commands.
     576*/
     577
     578/**
     579@defgroup tools Standalone Utility Applications
    544580
    545581Some utility applications are listed here.
     
    549585*/
    550586
     587}
  • 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 r705  
    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).
     
    2424\subsection whatis What is LEMON
    2525
    26 LEMON stands for
    27 <b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
     26LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    2827and <b>O</b>ptimization in <b>N</b>etworks.
    2928It is a C++ template
     
    4241\subsection howtoread How to read the documentation
    4342
    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.
     43If you would like to get to know the library, see
     44<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    4745
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    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.
     46If you know what you are looking for, then try to find it under the
     47<a class="el" href="modules.html">Modules</a> section.
    5848
    5949If 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 r913  
    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/bfs.h \
     61        lemon/bin_heap.h \
     62        lemon/cbc.h \
     63        lemon/circulation.h \
     64        lemon/clp.h \
     65        lemon/color.h \
    2766        lemon/concept_check.h \
    28         lemon/counter.h \
     67        lemon/connectivity.h \
     68        lemon/counter.h \
    2969        lemon/core.h \
    30         lemon/dfs.h \
    31         lemon/dijkstra.h \
    32         lemon/dim2.h \
     70        lemon/cplex.h \
     71        lemon/dfs.h \
     72        lemon/dijkstra.h \
     73        lemon/dim2.h \
     74        lemon/dimacs.h \
     75        lemon/edge_set.h \
     76        lemon/elevator.h \
    3377        lemon/error.h \
    34         lemon/graph_to_eps.h \
     78        lemon/euler.h \
     79        lemon/full_graph.h \
     80        lemon/glpk.h \
     81        lemon/gomory_hu.h \
     82        lemon/graph_to_eps.h \
     83        lemon/grid_graph.h \
     84        lemon/hypercube_graph.h \
    3585        lemon/kruskal.h \
     86        lemon/hao_orlin.h \
    3687        lemon/lgf_reader.h \
    3788        lemon/lgf_writer.h \
    3889        lemon/list_graph.h \
     90        lemon/lp.h \
     91        lemon/lp_base.h \
     92        lemon/lp_skeleton.h \
    3993        lemon/maps.h \
     94        lemon/matching.h \
    4095        lemon/math.h \
     96        lemon/min_cost_arborescence.h \
     97        lemon/nauty_reader.h \
     98        lemon/network_simplex.h \
    4199        lemon/path.h \
    42         lemon/random.h \
     100        lemon/preflow.h \
     101        lemon/radix_sort.h \
     102        lemon/random.h \
    43103        lemon/smart_graph.h \
    44         lemon/time_measure.h \
    45         lemon/tolerance.h \
     104        lemon/soplex.h \
     105        lemon/suurballe.h \
     106        lemon/time_measure.h \
     107        lemon/tolerance.h \
    46108        lemon/unionfind.h \
    47109        lemon/bits/windows.h
     
    50112        lemon/bits/alteration_notifier.h \
    51113        lemon/bits/array_map.h \
    52         lemon/bits/base_extender.h \
    53         lemon/bits/bezier.h \
     114        lemon/bits/bezier.h \
    54115        lemon/bits/default_map.h \
    55         lemon/bits/enable_if.h \
     116        lemon/bits/edge_set_extender.h \
     117        lemon/bits/enable_if.h \
     118        lemon/bits/graph_adaptor_extender.h \
    56119        lemon/bits/graph_extender.h \
    57120        lemon/bits/map_extender.h \
    58121        lemon/bits/path_dump.h \
     122        lemon/bits/solver_bits.h \
    59123        lemon/bits/traits.h \
     124        lemon/bits/variant.h \
    60125        lemon/bits/vector_map.h
    61126
  • 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 r525  
    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).
     
    5050    ///It must meet 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    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    120120  ///
    121121  ///\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.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    214208    typedef Bfs Create;
    215209
    216     ///\name Named template parameters
     210    ///\name Named Template Parameters
    217211
    218212    ///@{
     
    228222    };
    229223    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     224    ///\c PredMap type.
    231225    ///
    232226    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     227    ///\c PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    234229    template <class T>
    235230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    247242    };
    248243    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     244    ///\c DistMap type.
    250245    ///
    251246    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     247    ///\c DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    253249    template <class T>
    254250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266262    };
    267263    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     264    ///\c ReachedMap type.
    269265    ///
    270266    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     267    ///\c ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272269    template <class T>
    273270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    285282    };
    286283    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     284    ///\c ProcessedMap type.
    288285    ///
    289286    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     287    ///\c ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    291289    template <class T>
    292290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    303301    };
    304302    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306304    ///
    307305    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309307    ///If you don't set it explicitly, it will be automatically allocated.
    310308    struct SetStandardProcessedMap :
     
    341339
    342340    ///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.
     341    ///If you don't use this function before calling \ref run(Node) "run()"
     342    ///or \ref init(), an instance will be allocated automatically.
     343    ///The destructor deallocates this automatically allocated map,
     344    ///of course.
    346345    ///\return <tt> (*this) </tt>
    347346    Bfs &predMap(PredMap &m)
     
    358357
    359358    ///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.
     359    ///If you don't use this function before calling \ref run(Node) "run()"
     360    ///or \ref init(), an instance will be allocated automatically.
     361    ///The destructor deallocates this automatically allocated map,
     362    ///of course.
    363363    ///\return <tt> (*this) </tt>
    364364    Bfs &reachedMap(ReachedMap &m)
     
    375375
    376376    ///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.
     377    ///If you don't use this function before calling \ref run(Node) "run()"
     378    ///or \ref init(), an instance will be allocated automatically.
     379    ///The destructor deallocates this automatically allocated map,
     380    ///of course.
    380381    ///\return <tt> (*this) </tt>
    381382    Bfs &processedMap(ProcessedMap &m)
     
    393394    ///Sets the map that stores the distances of the nodes calculated by
    394395    ///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.
     396    ///If you don't use this function before calling \ref run(Node) "run()"
     397    ///or \ref init(), an instance will be allocated automatically.
     398    ///The destructor deallocates this automatically allocated map,
     399    ///of course.
    398400    ///\return <tt> (*this) </tt>
    399401    Bfs &distMap(DistMap &m)
     
    409411  public:
    410412
    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.
     413    ///\name Execution Control
     414    ///The simplest way to execute the BFS algorithm is to use one of the
     415    ///member functions called \ref run(Node) "run()".\n
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
     418    ///\ref addSource(). Finally the actual path computation can be
     419    ///performed with one of the \ref start() functions.
    420420
    421421    ///@{
    422422
     423    ///\brief Initializes the internal data structures.
     424    ///
    423425    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427426    void init()
    428427    {
     
    558557    }
    559558
    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.
     559    ///Returns \c false if there are nodes to be processed.
     560
     561    ///Returns \c false if there are nodes to be processed
     562    ///in the queue.
    565563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566564
    567565    ///Returns the number of the nodes to be processed.
    568566
    569     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    570569    int queueSize() const { return _queue_head-_queue_tail; }
    571570
     
    732731
    733732    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    735734    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    738737
    739738    ///@{
     
    743742    ///Returns the shortest path to a node.
    744743    ///
    745     ///\warning \c t should be reachable from the root(s).
    746     ///
    747     ///\pre Either \ref run() or \ref start() must be called before
    748     ///using this function.
     744    ///\warning \c t should be reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
     747    ///must be called before using this function.
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
     
    753752    ///Returns the distance of a node from the root(s).
    754753    ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    756755    ///the return value of this function is undefined.
    757756    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
     
    764763    ///This function returns the 'previous arc' of the shortest path
    765764    ///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.
     765    ///shortest path from a root to \c v. It is \c INVALID if \c v
     766    ///is not reached from the root(s) or if \c v is a root.
    768767    ///
    769768    ///The shortest path tree used here is equal to the shortest path
    770769    ///tree used in \ref predNode().
    771770    ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    774773    Arc predArc(Node v) const { return (*_pred)[v];}
    775774
     
    778777    ///This function returns the 'previous node' of the shortest path
    779778    ///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.
     779    ///from a shortest path from a root to \c v. It is \c INVALID
     780    ///if \c v is not reached from the root(s) or if \c v is a root.
    782781    ///
    783782    ///The shortest path tree used here is equal to the shortest path
    784783    ///tree used in \ref predArc().
    785784    ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    788787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789788                                  G->source((*_pred)[v]); }
     
    795794    ///of the nodes calculated by the algorithm.
    796795    ///
    797     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    798797    ///must be called before using this function.
    799798    const DistMap &distMap() const { return *_dist;}
     
    805804    ///arcs, which form the shortest path tree.
    806805    ///
    807     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    808807    ///must be called before using this function.
    809808    const PredMap &predMap() const { return *_pred;}
    810809
    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()
     810    ///Checks if a node is reached from the root(s).
     811
     812    ///Returns \c true if \c v is reached from the root(s).
     813    ///
     814    ///\pre Either \ref run(Node) "run()" or \ref init()
    815815    ///must be called before using this function.
    816816    bool reached(Node v) const { return (*_reached)[v]; }
     
    958958  /// This auxiliary class is created to implement the
    959959  /// \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.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions and features of the plain \ref Bfs.
    962962  ///
    963963  /// This class should only be used through the \ref bfs() function,
     
    11791179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801180  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821182  ///to the end of the parameter list.
    11831183  ///\sa BfsWizard
     
    11951195  /// This class defines the interface of the BfsVisit events, and
    11961196  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1197  template <typename GR>
    11981198  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1199    typedef GR Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
     
    12251225  };
    12261226#else
    1227   template <typename _Digraph>
     1227  template <typename GR>
    12281228  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1229    typedef GR Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
     
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1257  /// \tparam GR The type of the digraph the algorithm runs on.
     1258  template<class GR>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1262    typedef GR Digraph;
    12631263
    12641264    /// \brief The type of the map that indicates which nodes are reached.
     
    12811281  /// \ingroup search
    12821282  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1283  /// \brief BFS algorithm class with visitor interface.
    12841284  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1285  /// This class provides an efficient implementation of the BFS algorithm
    12861286  /// with visitor interface.
    12871287  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1288  /// The BfsVisit class provides an alternative interface to the Bfs
    12891289  /// class. It works with callback mechanism, the BfsVisit object calls
    12901290  /// the member functions of the \c Visitor class on every BFS event.
     
    12951295  /// instead.
    12961296  ///
    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
     1297  /// \tparam GR The type of the digraph the algorithm runs on.
     1298  /// The default type is \ref ListDigraph.
     1299  /// The value of GR is not used directly by \ref BfsVisit,
     1300  /// it is only passed to \ref BfsVisitDefaultTraits.
     1301  /// \tparam VS The Visitor type that is used by the algorithm.
     1302  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031303  /// does not observe the BFS events. If you want to observe the BFS
    13041304  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1305  /// \tparam TR Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1311  template <typename GR, typename VS, typename TR>
    13121312#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1313  template <typename GR = ListDigraph,
     1314            typename VS = BfsVisitor<GR>,
     1315            typename TR = BfsVisitDefaultTraits<GR> >
    13161316#endif
    13171317  class BfsVisit {
     
    13191319
    13201320    ///The traits class.
    1321     typedef _Traits Traits;
     1321    typedef TR Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
     
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1327    typedef VS Visitor;
    13281328
    13291329    ///The type of the map that indicates which nodes are reached.
     
    13651365    typedef BfsVisit Create;
    13661366
    1367     /// \name Named template parameters
     1367    /// \name Named Template Parameters
    13681368
    13691369    ///@{
     
    14071407    ///
    14081408    /// 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.
     1409    /// If you don't use this function before calling \ref run(Node) "run()"
     1410    /// or \ref init(), an instance will be allocated automatically.
     1411    /// The destructor deallocates this automatically allocated map,
     1412    /// of course.
    14121413    /// \return <tt> (*this) </tt>
    14131414    BfsVisit &reachedMap(ReachedMap &m) {
     
    14221423  public:
    14231424
    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.
     1425    /// \name Execution Control
     1426    /// The simplest way to execute the BFS algorithm is to use one of the
     1427    /// member functions called \ref run(Node) "run()".\n
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
     1430    /// \ref addSource(). Finally the actual path computation can be
     1431    /// performed with one of the \ref start() functions.
    14341432
    14351433    /// @{
     
    17311729
    17321730    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17341732    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17381736    ///@{
    17391737
    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()
     1738    /// \brief Checks if a node is reached from the root(s).
     1739    ///
     1740    /// Returns \c true if \c v is reached from the root(s).
     1741    ///
     1742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441743    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1744    bool reached(Node v) const { return (*_reached)[v]; }
    17461745
    17471746    ///@}
  • lemon/bin_heap.h

    r209 r912  
    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).
     
    3434  ///\brief A Binary Heap implementation.
    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  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
    4143  ///
    42   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
    4446  ///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  ///\tparam Comp A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
    4749  ///
    4850  ///\sa FibHeap
    4951  ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     52  template <typename PR, typename IM, typename Comp = std::less<PR> >
    5253  class BinHeap {
    5354
    5455  public:
    5556    ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
     57    typedef IM ItemIntMap;
     58    ///\e
     59    typedef PR Prio;
    5960    ///\e
    6061    typedef typename ItemIntMap::Key Item;
     
    6263    typedef std::pair<Item,Prio> Pair;
    6364    ///\e
    64     typedef _Compare Compare;
     65    typedef Comp Compare;
    6566
    6667    /// \brief Type to represent the items states.
     
    7071    /// heap's point of view, but may be useful to the user.
    7172    ///
    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...
     73    /// The item-int map must be initialized in such way that it assigns
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    7475    enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
     76      IN_HEAP = 0,    ///< = 0.
     77      PRE_HEAP = -1,  ///< = -1.
     78      POST_HEAP = -2  ///< = -2.
    7879    };
    7980
    8081  private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
     82    std::vector<Pair> _data;
     83    Compare _comp;
     84    ItemIntMap &_iim;
    8485
    8586  public:
     
    8788    ///
    8889    /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     93    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
     94
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
    9099    /// internally to handle the cross references. The value of the map
    91100    /// 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) {}
     101    ///
     102    /// \param comp The comparator function object.
     103    BinHeap(ItemIntMap &map, const Compare &comp)
     104      : _iim(map), _comp(comp) {}
    104105
    105106
     
    107108    ///
    108109    /// \brief Returns the number of items stored in the heap.
    109     int size() const { return data.size(); }
     110    int size() const { return _data.size(); }
    110111
    111112    /// \brief Checks if the heap stores no items.
    112113    ///
    113114    /// Returns \c true if and only if the heap stores no items.
    114     bool empty() const { return data.empty(); }
     115    bool empty() const { return _data.empty(); }
    115116
    116117    /// \brief Make empty this heap.
     
    121122    /// each item to \c PRE_HEAP.
    122123    void clear() {
    123       data.clear();
     124      _data.clear();
    124125    }
    125126
     
    129130    static int second_child(int i) { return 2*i+2; }
    130131    bool less(const Pair &p1, const Pair &p2) const {
    131       return comp(p1.second, p2.second);
     132      return _comp(p1.second, p2.second);
    132133    }
    133134
    134135    int bubble_up(int hole, Pair p) {
    135136      int par = parent(hole);
    136       while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
     137      while( hole>0 && less(p,_data[par]) ) {
     138        move(_data[par],hole);
    138139        hole = par;
    139140        par = parent(hole);
     
    146147      int child = second_child(hole);
    147148      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
     149        if( less(_data[child-1], _data[child]) ) {
    149150          --child;
    150151        }
    151         if( !less(data[child], p) )
     152        if( !less(_data[child], p) )
    152153          goto ok;
    153         move(data[child], hole);
     154        move(_data[child], hole);
    154155        hole = child;
    155156        child = second_child(hole);
    156157      }
    157158      child--;
    158       if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
     159      if( child<length && less(_data[child], p) ) {
     160        move(_data[child], hole);
    160161        hole=child;
    161162      }
     
    166167
    167168    void move(const Pair &p, int i) {
    168       data[i] = p;
    169       iim.set(p.first, i);
     169      _data[i] = p;
     170      _iim.set(p.first, i);
    170171    }
    171172
     
    176177    /// \param p The pair to insert.
    177178    void push(const Pair &p) {
    178       int n = data.size();
    179       data.resize(n+1);
     179      int n = _data.size();
     180      _data.resize(n+1);
    180181      bubble_up(n, p);
    181182    }
     
    194195    /// \pre The heap must be nonempty.
    195196    Item top() const {
    196       return data[0].first;
     197      return _data[0].first;
    197198    }
    198199
     
    202203    /// \pre The heap must be nonempty.
    203204    Prio prio() const {
    204       return data[0].second;
     205      return _data[0].second;
    205206    }
    206207
     
    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();
     217        bubble_down(0, _data[n], n);
     218      }
     219      _data.pop_back();
    219220    }
    220221
     
    225226    /// \pre The item should be in the heap.
    226227    void erase(const Item &i) {
    227       int h = iim[i];
    228       int n = data.size()-1;
    229       iim.set(data[h].first, POST_HEAP);
     228      int h = _iim[i];
     229      int n = _data.size()-1;
     230      _iim.set(_data[h].first, POST_HEAP);
    230231      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    233234        }
    234235      }
    235       data.pop_back();
     236      _data.pop_back();
    236237    }
    237238
     
    240241    ///
    241242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
    242244    /// \pre \c i must be in the heap.
    243     /// \param i The item.
    244245    Prio operator[](const Item &i) const {
    245       int idx = iim[i];
    246       return data[idx].second;
     246      int idx = _iim[i];
     247      return _data[idx].second;
    247248    }
    248249
     
    255256    /// \param p The priority.
    256257    void set(const Item &i, const Prio &p) {
    257       int idx = iim[i];
     258      int idx = _iim[i];
    258259      if( idx < 0 ) {
    259260        push(i,p);
    260261      }
    261       else if( comp(p, data[idx].second) ) {
     262      else if( _comp(p, _data[idx].second) ) {
    262263        bubble_up(idx, Pair(i,p));
    263264      }
    264265      else {
    265         bubble_down(idx, Pair(i,p), data.size());
     266        bubble_down(idx, Pair(i,p), _data.size());
    266267      }
    267268    }
     
    270271    ///
    271272    /// This method decreases the priority of item \c i to \c p.
     273    /// \param i The item.
     274    /// \param p The priority.
    272275    /// \pre \c i must be stored in the heap with priority at least \c
    273276    /// p relative to \c Compare.
     277    void decrease(const Item &i, const Prio &p) {
     278      int idx = _iim[i];
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    274285    /// \param i The item.
    275286    /// \param p The priority.
    276     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.
    284287    /// \pre \c i must be stored in the heap with priority at most \c
    285288    /// p relative to \c Compare.
    286     /// \param i The item.
    287     /// \param p The priority.
    288289    void increase(const Item &i, const Prio &p) {
    289       int idx = iim[i];
    290       bubble_down(idx, Pair(i,p), data.size());
     290      int idx = _iim[i];
     291      bubble_down(idx, Pair(i,p), _data.size());
    291292    }
    292293
     
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    302       int s = iim[i];
     303      int s = _iim[i];
    303304      if( s>=0 )
    304305        s=0;
     
    320321          erase(i);
    321322        }
    322         iim[i] = st;
     323        _iim[i] = st;
    323324        break;
    324325      case IN_HEAP:
     
    334335    /// with the same prioriority as prevoiusly the \c i item.
    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 r732  
    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
     
    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
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    604     public:
    605       typedef GraphExtender Graph;
    606604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    607605
    608       NodeMap(const Graph& graph)
     606    public:
     607      explicit NodeMap(const Graph& graph)
    609608        : Parent(graph) {}
    610609      NodeMap(const Graph& graph, const _Value& value)
     
    627626    class ArcMap
    628627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    629     public:
    630       typedef GraphExtender Graph;
    631628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    632629
    633       ArcMap(const Graph& graph)
     630    public:
     631      explicit ArcMap(const Graph& graph)
    634632        : Parent(graph) {}
    635633      ArcMap(const Graph& graph, const _Value& value)
     
    652650    class EdgeMap
    653651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    654     public:
    655       typedef GraphExtender Graph;
    656652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    657653
    658       EdgeMap(const Graph& graph)
     654    public:
     655      explicit EdgeMap(const Graph& graph)
    659656        : Parent(graph) {}
    660657
  • lemon/bits/map_extender.h

    r865 r913  
    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;
    5051
    5152    class MapIt;
     
    5758  public:
    5859
    59     MapExtender(const Graph& graph)
     60    MapExtender(const GraphType& graph)
    6061      : Parent(graph) {}
    6162
    62     MapExtender(const Graph& graph, const Value& value)
     63    MapExtender(const GraphType& graph, const Value& value)
    6364      : Parent(graph, value) {}
    6465
     
    7677  public:
    7778    class MapIt : public Item {
    78     public:
    79 
    80       typedef Item Parent;
     79      typedef Item Parent;
     80
     81    public:
     82
    8183      typedef typename Map::Value Value;
    8284
     
    115117
    116118    class ConstMapIt : public Item {
    117     public:
    118 
    119       typedef Item Parent;
     119      typedef Item Parent;
     120
     121    public:
    120122
    121123      typedef typename Map::Value Value;
     
    146148
    147149    class ItemIt : public Item {
    148     public:
    149 
    150       typedef Item Parent;
    151 
     150      typedef Item Parent;
     151
     152    public:
    152153      ItemIt() : map(NULL) {}
     154
    153155
    154156      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     
    177179  template <typename _Graph, typename _Map>
    178180  class SubMapExtender : public _Map {
    179   public:
    180 
    181181    typedef _Map Parent;
     182    typedef _Graph GraphType;
     183
     184  public:
     185
    182186    typedef SubMapExtender Map;
    183 
    184     typedef _Graph Graph;
    185 
    186187    typedef typename Parent::Key Item;
    187188
    188189    typedef typename Parent::Key Key;
    189190    typedef typename Parent::Value Value;
     191    typedef typename Parent::Reference Reference;
     192    typedef typename Parent::ConstReference ConstReference;
    190193
    191194    class MapIt;
     
    197200  public:
    198201
    199     SubMapExtender(const Graph& _graph)
     202    SubMapExtender(const GraphType& _graph)
    200203      : Parent(_graph), graph(_graph) {}
    201204
    202     SubMapExtender(const Graph& _graph, const Value& _value)
     205    SubMapExtender(const GraphType& _graph, const Value& _value)
    203206      : Parent(_graph, _value), graph(_graph) {}
    204207
     
    220223  public:
    221224    class MapIt : public Item {
    222     public:
    223 
    224       typedef Item Parent;
     225      typedef Item Parent;
     226
     227    public:
    225228      typedef typename Map::Value Value;
    226229
     
    259262
    260263    class ConstMapIt : public Item {
    261     public:
    262 
    263       typedef Item Parent;
     264      typedef Item Parent;
     265
     266    public:
    264267
    265268      typedef typename Map::Value Value;
     
    290293
    291294    class ItemIt : public Item {
    292     public:
    293 
    294       typedef Item Parent;
    295 
     295      typedef Item Parent;
     296
     297    public:
    296298      ItemIt() : map(NULL) {}
     299
    297300
    298301      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     
    317320  private:
    318321
    319     const Graph& graph;
     322    const GraphType& graph;
    320323
    321324  };
  • lemon/bits/path_dump.h

    r971 r973  
    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 r627  
    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
     
    422422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423423
    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
     424      /// \brief Reference map of the nodes to type \c T.
     425      ///
     426      /// Reference map of the nodes to type \c T.
    428427      template<class T>
    429       class NodeMap : public ReadWriteMap< Node, T > {
     428      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    430429      public:
    431430
     
    437436      private:
    438437        ///Copy constructor
    439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     438        NodeMap(const NodeMap& nm) :
     439          ReferenceMap<Node, T, T&, const T&>(nm) { }
    440440        ///Assignment operator
    441441        template <typename CMap>
     
    446446      };
    447447
    448       /// \brief Read write map of the arcs to type \c T.
     448      /// \brief Reference map of the arcs to type \c T.
    449449      ///
    450450      /// Reference map of the arcs to type \c T.
    451       /// \sa Reference
    452451      template<class T>
    453       class ArcMap : public ReadWriteMap<Arc,T> {
     452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    454453      public:
    455454
     
    460459      private:
    461460        ///Copy constructor
    462         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     461        ArcMap(const ArcMap& em) :
     462          ReferenceMap<Arc, T, T&, const T&>(em) { }
    463463        ///Assignment operator
    464464        template <typename CMap>
     
    472472      struct Constraints {
    473473        void constraints() {
     474          checkConcept<BaseDigraphComponent, _Digraph>();
    474475          checkConcept<IterableDigraphComponent<>, _Digraph>();
    475476          checkConcept<IDableDigraphComponent<>, _Digraph>();
     
    485486
    486487
    487 #endif // LEMON_CONCEPT_DIGRAPH_H
     488#endif
  • lemon/concepts/graph.h

    r263 r704  
    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).
     
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
     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>
    2827#include <lemon/core.h>
    2928
     
    312311      /// The directed arc type. It can be converted to the
    313312      /// edge or it should be inherited from the undirected
    314       /// arc.
    315       class Arc : public Edge {
     313      /// edge.
     314      class Arc {
    316315      public:
    317316        /// Default constructor
     
    324323        /// Copy constructor.
    325324        ///
    326         Arc(const Arc& e) : Edge(e) { }
     325        Arc(const Arc&) { }
    327326        /// Initialize the iterator to be invalid.
    328327
     
    351350        bool operator<(Arc) const { return false; }
    352351
     352        /// Converison to Edge
     353        operator Edge() const { return Edge(); }
    353354      };
    354355      /// This iterator goes through each directed arc.
     
    499500      };
    500501
    501       /// \brief Read write map of the nodes to type \c T.
    502       ///
    503       /// ReadWrite map of the nodes to type \c T.
    504       /// \sa Reference
     502      /// \brief Reference map of the nodes to type \c T.
     503      ///
     504      /// Reference map of the nodes to type \c T.
    505505      template<class T>
    506       class NodeMap : public ReadWriteMap< Node, T >
     506      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    507507      {
    508508      public:
     
    515515      private:
    516516        ///Copy constructor
    517         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     517        NodeMap(const NodeMap& nm) :
     518          ReferenceMap<Node, T, T&, const T&>(nm) { }
    518519        ///Assignment operator
    519520        template <typename CMap>
     
    524525      };
    525526
    526       /// \brief Read write map of the directed arcs to type \c T.
    527       ///
    528       /// Reference map of the directed arcs to type \c T.
    529       /// \sa Reference
     527      /// \brief Reference map of the arcs to type \c T.
     528      ///
     529      /// Reference map of the arcs to type \c T.
    530530      template<class T>
    531       class ArcMap : public ReadWriteMap<Arc,T>
     531      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    532532      {
    533533      public:
     
    539539      private:
    540540        ///Copy constructor
    541         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     541        ArcMap(const ArcMap& em) :
     542          ReferenceMap<Arc, T, T&, const T&>(em) { }
    542543        ///Assignment operator
    543544        template <typename CMap>
     
    548549      };
    549550
    550       /// Read write map of the edges to type \c T.
    551 
    552       /// Reference map of the arcs to type \c T.
    553       /// \sa Reference
     551      /// Reference map of the edges to type \c T.
     552
     553      /// Reference map of the edges to type \c T.
    554554      template<class T>
    555       class EdgeMap : public ReadWriteMap<Edge,T>
     555      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    556556      {
    557557      public:
     
    563563      private:
    564564        ///Copy constructor
    565         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
     565        EdgeMap(const EdgeMap& em) :
     566          ReferenceMap<Edge, T, T&, const T&>(em) {}
    566567        ///Assignment operator
    567568        template <typename CMap>
     
    603604      /// \brief Opposite node on an arc
    604605      ///
    605       /// \return the opposite of the given Node on the given Edge
     606      /// \return The opposite of the given node on the given edge.
    606607      Node oppositeNode(Node, Edge) const { return INVALID; }
    607608
    608609      /// \brief First node of the edge.
    609610      ///
    610       /// \return the first node of the given Edge.
     611      /// \return The first node of the given edge.
    611612      ///
    612613      /// Naturally edges don't have direction and thus
    613       /// don't have source and target node. But we use these two methods
    614       /// to query the two nodes of the arc. The direction of the arc
    615       /// which arises this way is called the inherent direction of the
     614      /// don't have source and target node. However we use \c u() and \c v()
     615      /// methods to query the two nodes of the arc. The direction of the
     616      /// arc which arises this way is called the inherent direction of the
    616617      /// edge, and is used to define the "default" direction
    617618      /// of the directed versions of the arcs.
    618       /// \sa direction
     619      /// \sa v()
     620      /// \sa direction()
    619621      Node u(Edge) const { return INVALID; }
    620622
    621623      /// \brief Second node of the edge.
     624      ///
     625      /// \return The second node of the given edge.
     626      ///
     627      /// Naturally edges don't have direction and thus
     628      /// don't have source and target node. However we use \c u() and \c v()
     629      /// methods to query the two nodes of the arc. The direction of the
     630      /// arc which arises this way is called the inherent direction of the
     631      /// edge, and is used to define the "default" direction
     632      /// of the directed versions of the arcs.
     633      /// \sa u()
     634      /// \sa direction()
    622635      Node v(Edge) const { return INVALID; }
    623636
     
    738751      struct Constraints {
    739752        void constraints() {
     753          checkConcept<BaseGraphComponent, _Graph>();
    740754          checkConcept<IterableGraphComponent<>, _Graph>();
    741755          checkConcept<IDableGraphComponent<>, _Graph>();
  • lemon/concepts/graph_components.h

    r313 r713  
    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).
     
    2121///\brief The concept of graph components.
    2222
    23 
    24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
    25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
     23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2625
    2726#include <lemon/core.h>
     
    3332  namespace concepts {
    3433
    35     /// \brief Skeleton class for graph Node and Arc types
    36     ///
    37     /// This class describes the interface of Node and Arc (and Edge
    38     /// in undirected graphs) subtypes of graph types.
     34    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
     35    ///
     36    /// This class describes the concept of \c Node, \c Arc and \c Edge
     37    /// subtypes of digraph and graph types.
    3938    ///
    4039    /// \note This class is a template class so that we can use it to
    41     /// create graph skeleton classes. The reason for this is than Node
    42     /// and Arc types should \em not derive from the same base class.
    43     /// For Node you should instantiate it with character 'n' and for Arc
    44     /// with 'a'.
    45 
     40    /// create graph skeleton classes. The reason for this is that \c Node
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
     42    /// base class. For \c Node you should instantiate it with character
     43    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    4644#ifndef DOXYGEN
    47     template <char _selector = '0'>
     45    template <char sel = '0'>
    4846#endif
    4947    class GraphItem {
     
    5149      /// \brief Default constructor.
    5250      ///
     51      /// Default constructor.
    5352      /// \warning The default constructor is not required to set
    5453      /// the item to some well-defined value. So you should consider it
    5554      /// as uninitialized.
    5655      GraphItem() {}
     56
    5757      /// \brief Copy constructor.
    5858      ///
    5959      /// Copy constructor.
    60       ///
    6160      GraphItem(const GraphItem &) {}
    62       /// \brief Invalid constructor \& conversion.
    63       ///
    64       /// This constructor initializes the item to be invalid.
     61
     62      /// \brief Constructor for conversion from \c INVALID.
     63      ///
     64      /// Constructor for conversion from \c INVALID.
     65      /// It initializes the item to be invalid.
    6566      /// \sa Invalid for more details.
    6667      GraphItem(Invalid) {}
    67       /// \brief Assign operator for nodes.
    68       ///
    69       /// The nodes are assignable.
    70       ///
    71       GraphItem& operator=(GraphItem const&) { return *this; }
     68
     69      /// \brief Assignment operator.
     70      ///
     71      /// Assignment operator for the item.
     72      GraphItem& operator=(const GraphItem&) { return *this; }
     73
     74      /// \brief Assignment operator for INVALID.
     75      ///
     76      /// This operator makes the item invalid.
     77      GraphItem& operator=(Invalid) { return *this; }
     78
    7279      /// \brief Equality operator.
    7380      ///
    74       /// Two iterators are equal if and only if they represents the
    75       /// same node in the graph or both are invalid.
    76       bool operator==(GraphItem) const { return false; }
     81      /// Equality operator.
     82      bool operator==(const GraphItem&) const { return false; }
     83
    7784      /// \brief Inequality operator.
    7885      ///
    79       /// \sa operator==(const Node& n)
    80       ///
    81       bool operator!=(GraphItem) const { return false; }
    82 
    83       /// \brief Artificial ordering operator.
    84       ///
    85       /// To allow the use of graph descriptors as key type in std::map or
    86       /// similar associative container we require this.
     86      /// Inequality operator.
     87      bool operator!=(const GraphItem&) const { return false; }
     88
     89      /// \brief Ordering operator.
     90      ///
     91      /// This operator defines an ordering of the items.
     92      /// It makes possible to use graph item types as key types in
     93      /// associative containers (e.g. \c std::map).
    8794      ///
    8895      /// \note This operator only have to define some strict ordering of
    8996      /// the items; this order has nothing to do with the iteration
    9097      /// ordering of the items.
    91       bool operator<(GraphItem) const { return false; }
     98      bool operator<(const GraphItem&) const { return false; }
    9299
    93100      template<typename _GraphItem>
     
    95102        void constraints() {
    96103          _GraphItem i1;
     104          i1=INVALID;
    97105          _GraphItem i2 = i1;
    98106          _GraphItem i3 = INVALID;
     
    101109
    102110          bool b;
    103           //          b = (ia == ib) && (ia != ib) && (ia < ib);
    104111          b = (ia == ib) && (ia != ib);
    105112          b = (ia == INVALID) && (ib != INVALID);
     
    112119    };
    113120
    114     /// \brief An empty base directed graph class.
    115     ///
    116     /// This class provides the minimal set of features needed for a
    117     /// directed graph structure. All digraph concepts have to be
    118     /// conform to this base directed graph. It just provides types
    119     /// for nodes and arcs and functions to get the source and the
    120     /// target of the arcs.
     121    /// \brief Base skeleton class for directed graphs.
     122    ///
     123    /// This class describes the base interface of directed graph types.
     124    /// All digraph %concepts have to conform to this class.
     125    /// It just provides types for nodes and arcs and functions
     126    /// to get the source and the target nodes of arcs.
    121127    class BaseDigraphComponent {
    122128    public:
     
    126132      /// \brief Node class of the digraph.
    127133      ///
    128       /// This class represents the Nodes of the digraph.
    129       ///
     134      /// This class represents the nodes of the digraph.
    130135      typedef GraphItem<'n'> Node;
    131136
    132137      /// \brief Arc class of the digraph.
    133138      ///
    134       /// This class represents the Arcs of the digraph.
    135       ///
    136       typedef GraphItem<'e'> Arc;
    137 
    138       /// \brief Gives back the target node of an arc.
    139       ///
    140       /// Gives back the target node of an arc.
    141       ///
    142       Node target(const Arc&) const { return INVALID;}
    143 
    144       /// \brief Gives back the source node of an arc.
    145       ///
    146       /// Gives back the source node of an arc.
    147       ///
    148       Node source(const Arc&) const { return INVALID;}
    149 
    150       /// \brief Gives back the opposite node on the given arc.
    151       ///
    152       /// Gives back the opposite node on the given arc.
     139      /// This class represents the arcs of the digraph.
     140      typedef GraphItem<'a'> Arc;
     141
     142      /// \brief Return the source node of an arc.
     143      ///
     144      /// This function returns the source node of an arc.
     145      Node source(const Arc&) const { return INVALID; }
     146
     147      /// \brief Return the target node of an arc.
     148      ///
     149      /// This function returns the target node of an arc.
     150      Node target(const Arc&) const { return INVALID; }
     151
     152      /// \brief Return the opposite node on the given arc.
     153      ///
     154      /// This function returns the opposite node on the given arc.
    153155      Node oppositeNode(const Node&, const Arc&) const {
    154156        return INVALID;
     
    176178    };
    177179
    178     /// \brief An empty base undirected graph class.
    179     ///
    180     /// This class provides the minimal set of features needed for an
    181     /// undirected graph structure. All undirected graph concepts have
    182     /// to be conform to this base graph. It just provides types for
    183     /// nodes, arcs and edges and functions to get the
    184     /// source and the target of the arcs and edges,
    185     /// conversion from arcs to edges and function to get
    186     /// both direction of the edges.
     180    /// \brief Base skeleton class for undirected graphs.
     181    ///
     182    /// This class describes the base interface of undirected graph types.
     183    /// All graph %concepts have to conform to this class.
     184    /// It extends the interface of \ref BaseDigraphComponent with an
     185    /// \c Edge type and functions to get the end nodes of edges,
     186    /// to convert from arcs to edges and to get both direction of edges.
    187187    class BaseGraphComponent : public BaseDigraphComponent {
    188188    public:
     189
     190      typedef BaseGraphComponent Graph;
     191
    189192      typedef BaseDigraphComponent::Node Node;
    190193      typedef BaseDigraphComponent::Arc Arc;
    191       /// \brief Undirected arc class of the graph.
    192       ///
    193       /// This class represents the edges of the graph.
    194       /// The undirected graphs can be used as a directed graph which
    195       /// for each arc contains the opposite arc too so the graph is
    196       /// bidirected. The edge represents two opposite
    197       /// directed arcs.
    198       class Edge : public GraphItem<'u'> {
     194
     195      /// \brief Undirected edge class of the graph.
     196      ///
     197      /// This class represents the undirected edges of the graph.
     198      /// Undirected graphs can be used as directed graphs, each edge is
     199      /// represented by two opposite directed arcs.
     200      class Edge : public GraphItem<'e'> {
     201        typedef GraphItem<'e'> Parent;
     202
    199203      public:
    200         typedef GraphItem<'u'> Parent;
    201204        /// \brief Default constructor.
    202205        ///
     206        /// Default constructor.
    203207        /// \warning The default constructor is not required to set
    204208        /// the item to some well-defined value. So you should consider it
    205209        /// as uninitialized.
    206210        Edge() {}
     211
    207212        /// \brief Copy constructor.
    208213        ///
    209214        /// Copy constructor.
     215        Edge(const Edge &) : Parent() {}
     216
     217        /// \brief Constructor for conversion from \c INVALID.
    210218        ///
    211         Edge(const Edge &) : Parent() {}
    212         /// \brief Invalid constructor \& conversion.
    213         ///
    214         /// This constructor initializes the item to be invalid.
     219        /// Constructor for conversion from \c INVALID.
     220        /// It initializes the item to be invalid.
    215221        /// \sa Invalid for more details.
    216222        Edge(Invalid) {}
    217         /// \brief Converter from arc to edge.
     223
     224        /// \brief Constructor for conversion from an arc.
    218225        ///
     226        /// Constructor for conversion from an arc.
    219227        /// Besides the core graph item functionality each arc should
    220228        /// be convertible to the represented edge.
    221229        Edge(const Arc&) {}
    222         /// \brief Assign arc to edge.
    223         ///
    224         /// Besides the core graph item functionality each arc should
    225         /// be convertible to the represented edge.
    226         Edge& operator=(const Arc&) { return *this; }
    227       };
    228 
    229       /// \brief Returns the direction of the arc.
     230     };
     231
     232      /// \brief Return one end node of an edge.
     233      ///
     234      /// This function returns one end node of an edge.
     235      Node u(const Edge&) const { return INVALID; }
     236
     237      /// \brief Return the other end node of an edge.
     238      ///
     239      /// This function returns the other end node of an edge.
     240      Node v(const Edge&) const { return INVALID; }
     241
     242      /// \brief Return a directed arc related to an edge.
     243      ///
     244      /// This function returns a directed arc from its direction and the
     245      /// represented edge.
     246      Arc direct(const Edge&, bool) const { return INVALID; }
     247
     248      /// \brief Return a directed arc related to an edge.
     249      ///
     250      /// This function returns a directed arc from its source node and the
     251      /// represented edge.
     252      Arc direct(const Edge&, const Node&) const { return INVALID; }
     253
     254      /// \brief Return the direction of the arc.
    230255      ///
    231256      /// Returns the direction of the arc. Each arc represents an
     
    234259      bool direction(const Arc&) const { return true; }
    235260
    236       /// \brief Returns the directed arc.
    237       ///
    238       /// Returns the directed arc from its direction and the
    239       /// represented edge.
    240       Arc direct(const Edge&, bool) const { return INVALID;}
    241 
    242       /// \brief Returns the directed arc.
    243       ///
    244       /// Returns the directed arc from its source and the
    245       /// represented edge.
    246       Arc direct(const Edge&, const Node&) const { return INVALID;}
    247 
    248       /// \brief Returns the opposite arc.
    249       ///
    250       /// Returns the opposite arc. It is the arc representing the
    251       /// same edge and has opposite direction.
    252       Arc oppositeArc(const Arc&) const { return INVALID;}
    253 
    254       /// \brief Gives back one ending of an edge.
    255       ///
    256       /// Gives back one ending of an edge.
    257       Node u(const Edge&) const { return INVALID;}
    258 
    259       /// \brief Gives back the other ending of an edge.
    260       ///
    261       /// Gives back the other ending of an edge.
    262       Node v(const Edge&) const { return INVALID;}
     261      /// \brief Return the opposite arc.
     262      ///
     263      /// This function returns the opposite arc, i.e. the arc representing
     264      /// the same edge and has opposite direction.
     265      Arc oppositeArc(const Arc&) const { return INVALID; }
    263266
    264267      template <typename _Graph>
     
    270273        void constraints() {
    271274          checkConcept<BaseDigraphComponent, _Graph>();
    272           checkConcept<GraphItem<'u'>, Edge>();
     275          checkConcept<GraphItem<'e'>, Edge>();
    273276          {
    274277            Node n;
     
    278281            n = graph.v(ue);
    279282            e = graph.direct(ue, true);
     283            e = graph.direct(ue, false);
    280284            e = graph.direct(ue, n);
    281285            e = graph.oppositeArc(e);
     
    291295    };
    292296
    293     /// \brief An empty idable base digraph class.
    294     ///
    295     /// This class provides beside the core digraph features
    296     /// core id functions for the digraph structure.
    297     /// The most of the base digraphs should be conform to this concept.
    298     /// The id's are unique and immutable.
    299     template <typename _Base = BaseDigraphComponent>
    300     class IDableDigraphComponent : public _Base {
    301     public:
    302 
    303       typedef _Base Base;
     297    /// \brief Skeleton class for \e idable directed graphs.
     298    ///
     299    /// This class describes the interface of \e idable directed graphs.
     300    /// It extends \ref BaseDigraphComponent with the core ID functions.
     301    /// The ids of the items must be unique and immutable.
     302    /// This concept is part of the Digraph concept.
     303    template <typename BAS = BaseDigraphComponent>
     304    class IDableDigraphComponent : public BAS {
     305    public:
     306
     307      typedef BAS Base;
    304308      typedef typename Base::Node Node;
    305309      typedef typename Base::Arc Arc;
    306310
    307       /// \brief Gives back an unique integer id for the Node.
    308       ///
    309       /// Gives back an unique integer id for the Node.
    310       ///
    311       int id(const Node&) const { return -1;}
    312 
    313       /// \brief Gives back the node by the unique id.
    314       ///
    315       /// Gives back the node by the unique id.
    316       /// If the digraph does not contain node with the given id
    317       /// then the result of the function is undetermined.
    318       Node nodeFromId(int) const { return INVALID;}
    319 
    320       /// \brief Gives back an unique integer id for the Arc.
    321       ///
    322       /// Gives back an unique integer id for the Arc.
    323       ///
    324       int id(const Arc&) const { return -1;}
    325 
    326       /// \brief Gives back the arc by the unique id.
    327       ///
    328       /// Gives back the arc by the unique id.
    329       /// If the digraph does not contain arc with the given id
    330       /// then the result of the function is undetermined.
    331       Arc arcFromId(int) const { return INVALID;}
    332 
    333       /// \brief Gives back an integer greater or equal to the maximum
    334       /// Node id.
    335       ///
    336       /// Gives back an integer greater or equal to the maximum Node
    337       /// id.
    338       int maxNodeId() const { return -1;}
    339 
    340       /// \brief Gives back an integer greater or equal to the maximum
    341       /// Arc id.
    342       ///
    343       /// Gives back an integer greater or equal to the maximum Arc
    344       /// id.
    345       int maxArcId() const { return -1;}
     311      /// \brief Return a unique integer id for the given node.
     312      ///
     313      /// This function returns a unique integer id for the given node.
     314      int id(const Node&) const { return -1; }
     315
     316      /// \brief Return the node by its unique id.
     317      ///
     318      /// This function returns the node by its unique id.
     319      /// If the digraph does not contain a node with the given id,
     320      /// then the result of the function is undefined.
     321      Node nodeFromId(int) const { return INVALID; }
     322
     323      /// \brief Return a unique integer id for the given arc.
     324      ///
     325      /// This function returns a unique integer id for the given arc.
     326      int id(const Arc&) const { return -1; }
     327
     328      /// \brief Return the arc by its unique id.
     329      ///
     330      /// This function returns the arc by its unique id.
     331      /// If the digraph does not contain an arc with the given id,
     332      /// then the result of the function is undefined.
     333      Arc arcFromId(int) const { return INVALID; }
     334
     335      /// \brief Return an integer greater or equal to the maximum
     336      /// node id.
     337      ///
     338      /// This function returns an integer greater or equal to the
     339      /// maximum node id.
     340      int maxNodeId() const { return -1; }
     341
     342      /// \brief Return an integer greater or equal to the maximum
     343      /// arc id.
     344      ///
     345      /// This function returns an integer greater or equal to the
     346      /// maximum arc id.
     347      int maxArcId() const { return -1; }
    346348
    347349      template <typename _Digraph>
     
    351353          checkConcept<Base, _Digraph >();
    352354          typename _Digraph::Node node;
     355          node=INVALID;
    353356          int nid = digraph.id(node);
    354357          nid = digraph.id(node);
    355358          node = digraph.nodeFromId(nid);
    356359          typename _Digraph::Arc arc;
     360          arc=INVALID;
    357361          int eid = digraph.id(arc);
    358362          eid = digraph.id(arc);
     
    369373    };
    370374
    371     /// \brief An empty idable base undirected graph class.
    372     ///
    373     /// This class provides beside the core undirected graph features
    374     /// core id functions for the undirected graph structure.  The
    375     /// most of the base undirected graphs should be conform to this
    376     /// concept.  The id's are unique and immutable.
    377     template <typename _Base = BaseGraphComponent>
    378     class IDableGraphComponent : public IDableDigraphComponent<_Base> {
    379     public:
    380 
    381       typedef _Base Base;
     375    /// \brief Skeleton class for \e idable undirected graphs.
     376    ///
     377    /// This class describes the interface of \e idable undirected
     378    /// graphs. It extends \ref IDableDigraphComponent with the core ID
     379    /// functions of undirected graphs.
     380    /// The ids of the items must be unique and immutable.
     381    /// This concept is part of the Graph concept.
     382    template <typename BAS = BaseGraphComponent>
     383    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
     384    public:
     385
     386      typedef BAS Base;
    382387      typedef typename Base::Edge Edge;
    383388
    384       using IDableDigraphComponent<_Base>::id;
    385 
    386       /// \brief Gives back an unique integer id for the Edge.
    387       ///
    388       /// Gives back an unique integer id for the Edge.
    389       ///
    390       int id(const Edge&) const { return -1;}
    391 
    392       /// \brief Gives back the edge by the unique id.
    393       ///
    394       /// Gives back the edge by the unique id.  If the
    395       /// graph does not contain arc with the given id then the
    396       /// result of the function is undetermined.
    397       Edge edgeFromId(int) const { return INVALID;}
    398 
    399       /// \brief Gives back an integer greater or equal to the maximum
    400       /// Edge id.
    401       ///
    402       /// Gives back an integer greater or equal to the maximum Edge
    403       /// id.
    404       int maxEdgeId() const { return -1;}
     389      using IDableDigraphComponent<Base>::id;
     390
     391      /// \brief Return a unique integer id for the given edge.
     392      ///
     393      /// This function returns a unique integer id for the given edge.
     394      int id(const Edge&) const { return -1; }
     395
     396      /// \brief Return the edge by its unique id.
     397      ///
     398      /// This function returns the edge by its unique id.
     399      /// If the graph does not contain an edge with the given id,
     400      /// then the result of the function is undefined.
     401      Edge edgeFromId(int) const { return INVALID; }
     402
     403      /// \brief Return an integer greater or equal to the maximum
     404      /// edge id.
     405      ///
     406      /// This function returns an integer greater or equal to the
     407      /// maximum edge id.
     408      int maxEdgeId() const { return -1; }
    405409
    406410      template <typename _Graph>
     
    408412
    409413        void constraints() {
    410           checkConcept<Base, _Graph >();
    411414          checkConcept<IDableDigraphComponent<Base>, _Graph >();
    412415          typename _Graph::Edge edge;
     
    422425    };
    423426
    424     /// \brief Skeleton class for graph NodeIt and ArcIt
    425     ///
    426     /// Skeleton class for graph NodeIt and ArcIt.
    427     ///
    428     template <typename _Graph, typename _Item>
    429     class GraphItemIt : public _Item {
     427    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
     428    ///
     429    /// This class describes the concept of \c NodeIt, \c ArcIt and
     430    /// \c EdgeIt subtypes of digraph and graph types.
     431    template <typename GR, typename Item>
     432    class GraphItemIt : public Item {
    430433    public:
    431434      /// \brief Default constructor.
    432435      ///
    433       /// @warning The default constructor sets the iterator
    434       /// to an undefined value.
     436      /// Default constructor.
     437      /// \warning The default constructor is not required to set
     438      /// the iterator to some well-defined value. So you should consider it
     439      /// as uninitialized.
    435440      GraphItemIt() {}
     441
    436442      /// \brief Copy constructor.
    437443      ///
    438444      /// Copy constructor.
    439       ///
    440       GraphItemIt(const GraphItemIt& ) {}
    441       /// \brief Sets the iterator to the first item.
    442       ///
    443       /// Sets the iterator to the first item of \c the graph.
    444       ///
    445       explicit GraphItemIt(const _Graph&) {}
    446       /// \brief Invalid constructor \& conversion.
    447       ///
    448       /// This constructor initializes the item to be invalid.
     445      GraphItemIt(const GraphItemIt& it) : Item(it) {}
     446
     447      /// \brief Constructor that sets the iterator to the first item.
     448      ///
     449      /// Constructor that sets the iterator to the first item.
     450      explicit GraphItemIt(const GR&) {}
     451
     452      /// \brief Constructor for conversion from \c INVALID.
     453      ///
     454      /// Constructor for conversion from \c INVALID.
     455      /// It initializes the iterator to be invalid.
    449456      /// \sa Invalid for more details.
    450457      GraphItemIt(Invalid) {}
    451       /// \brief Assign operator for items.
    452       ///
    453       /// The items are assignable.
    454       ///
     458
     459      /// \brief Assignment operator.
     460      ///
     461      /// Assignment operator for the iterator.
    455462      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    456       /// \brief Next item.
    457       ///
    458       /// Assign the iterator to the next item.
    459       ///
     463
     464      /// \brief Increment the iterator.
     465      ///
     466      /// This operator increments the iterator, i.e. assigns it to the
     467      /// next item.
    460468      GraphItemIt& operator++() { return *this; }
     469 
    461470      /// \brief Equality operator
    462471      ///
     472      /// Equality operator.
    463473      /// Two iterators are equal if and only if they point to the
    464474      /// same object or both are invalid.
    465475      bool operator==(const GraphItemIt&) const { return true;}
     476
    466477      /// \brief Inequality operator
    467478      ///
    468       /// \sa operator==(Node n)
    469       ///
     479      /// Inequality operator.
     480      /// Two iterators are equal if and only if they point to the
     481      /// same object or both are invalid.
    470482      bool operator!=(const GraphItemIt&) const { return true;}
    471483
     
    473485      struct Constraints {
    474486        void constraints() {
     487          checkConcept<GraphItem<>, _GraphItemIt>();
    475488          _GraphItemIt it1(g);
    476489          _GraphItemIt it2;
     490          _GraphItemIt it3 = it1;
     491          _GraphItemIt it4 = INVALID;
    477492
    478493          it2 = ++it1;
     
    480495          ++(++it1);
    481496
    482           _Item bi = it1;
     497          Item bi = it1;
    483498          bi = it2;
    484499        }
    485         _Graph& g;
    486       };
    487     };
    488 
    489     /// \brief Skeleton class for graph InArcIt and OutArcIt
    490     ///
    491     /// \note Because InArcIt and OutArcIt may not inherit from the same
    492     /// base class, the _selector is a additional template parameter. For
    493     /// InArcIt you should instantiate it with character 'i' and for
    494     /// OutArcIt with 'o'.
    495     template <typename _Graph,
    496               typename _Item = typename _Graph::Arc,
    497               typename _Base = typename _Graph::Node,
    498               char _selector = '0'>
    499     class GraphIncIt : public _Item {
     500        const GR& g;
     501      };
     502    };
     503
     504    /// \brief Concept class for \c InArcIt, \c OutArcIt and
     505    /// \c IncEdgeIt types.
     506    ///
     507    /// This class describes the concept of \c InArcIt, \c OutArcIt
     508    /// and \c IncEdgeIt subtypes of digraph and graph types.
     509    ///
     510    /// \note Since these iterator classes do not inherit from the same
     511    /// base class, there is an additional template parameter (selector)
     512    /// \c sel. For \c InArcIt you should instantiate it with character
     513    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
     514    template <typename GR,
     515              typename Item = typename GR::Arc,
     516              typename Base = typename GR::Node,
     517              char sel = '0'>
     518    class GraphIncIt : public Item {
    500519    public:
    501520      /// \brief Default constructor.
    502521      ///
    503       /// @warning The default constructor sets the iterator
    504       /// to an undefined value.
     522      /// Default constructor.
     523      /// \warning The default constructor is not required to set
     524      /// the iterator to some well-defined value. So you should consider it
     525      /// as uninitialized.
    505526      GraphIncIt() {}
     527
    506528      /// \brief Copy constructor.
    507529      ///
    508530      /// Copy constructor.
    509       ///
    510       GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
    511       /// \brief Sets the iterator to the first arc incoming into or outgoing
    512       /// from the node.
    513       ///
    514       /// Sets the iterator to the first arc incoming into or outgoing
    515       /// from the node.
    516       ///
    517       explicit GraphIncIt(const _Graph&, const _Base&) {}
    518       /// \brief Invalid constructor \& conversion.
    519       ///
    520       /// This constructor initializes the item to be invalid.
     531      GraphIncIt(const GraphIncIt& it) : Item(it) {}
     532
     533      /// \brief Constructor that sets the iterator to the first
     534      /// incoming or outgoing arc.
     535      ///
     536      /// Constructor that sets the iterator to the first arc
     537      /// incoming to or outgoing from the given node.
     538      explicit GraphIncIt(const GR&, const Base&) {}
     539
     540      /// \brief Constructor for conversion from \c INVALID.
     541      ///
     542      /// Constructor for conversion from \c INVALID.
     543      /// It initializes the iterator to be invalid.
    521544      /// \sa Invalid for more details.
    522545      GraphIncIt(Invalid) {}
    523       /// \brief Assign operator for iterators.
    524       ///
    525       /// The iterators are assignable.
    526       ///
    527       GraphIncIt& operator=(GraphIncIt const&) { return *this; }
    528       /// \brief Next item.
    529       ///
    530       /// Assign the iterator to the next item.
    531       ///
     546
     547      /// \brief Assignment operator.
     548      ///
     549      /// Assignment operator for the iterator.
     550      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
     551
     552      /// \brief Increment the iterator.
     553      ///
     554      /// This operator increments the iterator, i.e. assigns it to the
     555      /// next arc incoming to or outgoing from the given node.
    532556      GraphIncIt& operator++() { return *this; }
    533557
    534558      /// \brief Equality operator
    535559      ///
     560      /// Equality operator.
    536561      /// Two iterators are equal if and only if they point to the
    537562      /// same object or both are invalid.
     
    540565      /// \brief Inequality operator
    541566      ///
    542       /// \sa operator==(Node n)
    543       ///
     567      /// Inequality operator.
     568      /// Two iterators are equal if and only if they point to the
     569      /// same object or both are invalid.
    544570      bool operator!=(const GraphIncIt&) const { return true;}
    545571
     
    547573      struct Constraints {
    548574        void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
     575          checkConcept<GraphItem<sel>, _GraphIncIt>();
    550576          _GraphIncIt it1(graph, node);
    551577          _GraphIncIt it2;
     578          _GraphIncIt it3 = it1;
     579          _GraphIncIt it4 = INVALID;
    552580
    553581          it2 = ++it1;
    554582          ++it2 = it1;
    555583          ++(++it1);
    556           _Item e = it1;
     584          Item e = it1;
    557585          e = it2;
    558 
    559         }
    560 
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
    564         _GraphIncIt it;
    565       };
    566     };
    567 
    568 
    569     /// \brief An empty iterable digraph class.
    570     ///
    571     /// This class provides beside the core digraph features
    572     /// iterator based iterable interface for the digraph structure.
     586        }
     587        const Base& node;
     588        const GR& graph;
     589      };
     590    };
     591
     592    /// \brief Skeleton class for iterable directed graphs.
     593    ///
     594    /// This class describes the interface of iterable directed
     595    /// graphs. It extends \ref BaseDigraphComponent with the core
     596    /// iterable interface.
    573597    /// This concept is part of the Digraph concept.
    574     template <typename _Base = BaseDigraphComponent>
    575     class IterableDigraphComponent : public _Base {
    576 
    577     public:
    578 
    579       typedef _Base Base;
     598    template <typename BAS = BaseDigraphComponent>
     599    class IterableDigraphComponent : public BAS {
     600
     601    public:
     602
     603      typedef BAS Base;
    580604      typedef typename Base::Node Node;
    581605      typedef typename Base::Arc Arc;
     
    583607      typedef IterableDigraphComponent Digraph;
    584608
    585       /// \name Base iteration
    586       ///
    587       /// This interface provides functions for iteration on digraph items
     609      /// \name Base Iteration
     610      ///
     611      /// This interface provides functions for iteration on digraph items.
    588612      ///
    589613      /// @{
    590614
    591       /// \brief Gives back the first node in the iterating order.
    592       ///
    593       /// Gives back the first node in the iterating order.
    594       ///
     615      /// \brief Return the first node.
     616      ///
     617      /// This function gives back the first node in the iteration order.
    595618      void first(Node&) const {}
    596619
    597       /// \brief Gives back the next node in the iterating order.
    598       ///
    599       /// Gives back the next node in the iterating order.
    600       ///
     620      /// \brief Return the next node.
     621      ///
     622      /// This function gives back the next node in the iteration order.
    601623      void next(Node&) const {}
    602624
    603       /// \brief Gives back the first arc in the iterating order.
    604       ///
    605       /// Gives back the first arc in the iterating order.
    606       ///
     625      /// \brief Return the first arc.
     626      ///
     627      /// This function gives back the first arc in the iteration order.
    607628      void first(Arc&) const {}
    608629
    609       /// \brief Gives back the next arc in the iterating order.
    610       ///
    611       /// Gives back the next arc in the iterating order.
    612       ///
     630      /// \brief Return the next arc.
     631      ///
     632      /// This function gives back the next arc in the iteration order.
    613633      void next(Arc&) const {}
    614634
    615 
    616       /// \brief Gives back the first of the arcs point to the given
    617       /// node.
    618       ///
    619       /// Gives back the first of the arcs point to the given node.
    620       ///
     635      /// \brief Return the first arc incomming to the given node.
     636      ///
     637      /// This function gives back the first arc incomming to the
     638      /// given node.
    621639      void firstIn(Arc&, const Node&) const {}
    622640
    623       /// \brief Gives back the next of the arcs points to the given
    624       /// node.
    625       ///
    626       /// Gives back the next of the arcs points to the given node.
    627       ///
     641      /// \brief Return the next arc incomming to the given node.
     642      ///
     643      /// This function gives back the next arc incomming to the
     644      /// given node.
    628645      void nextIn(Arc&) const {}
    629646
    630       /// \brief Gives back the first of the arcs start from the
     647      /// \brief Return the first arc outgoing form the given node.
     648      ///
     649      /// This function gives back the first arc outgoing form the
    631650      /// given node.
    632       ///
    633       /// Gives back the first of the arcs start from the given node.
    634       ///
    635651      void firstOut(Arc&, const Node&) const {}
    636652
    637       /// \brief Gives back the next of the arcs start from the given
    638       /// node.
    639       ///
    640       /// Gives back the next of the arcs start from the given node.
    641       ///
     653      /// \brief Return the next arc outgoing form the given node.
     654      ///
     655      /// This function gives back the next arc outgoing form the
     656      /// given node.
    642657      void nextOut(Arc&) const {}
    643658
    644659      /// @}
    645660
    646       /// \name Class based iteration
    647       ///
    648       /// This interface provides functions for iteration on digraph items
     661      /// \name Class Based Iteration
     662      ///
     663      /// This interface provides iterator classes for digraph items.
    649664      ///
    650665      /// @{
     
    656671      typedef GraphItemIt<Digraph, Node> NodeIt;
    657672
    658       /// \brief This iterator goes through each node.
    659       ///
    660       /// This iterator goes through each node.
     673      /// \brief This iterator goes through each arc.
     674      ///
     675      /// This iterator goes through each arc.
    661676      ///
    662677      typedef GraphItemIt<Digraph, Arc> ArcIt;
     
    664679      /// \brief This iterator goes trough the incoming arcs of a node.
    665680      ///
    666       /// This iterator goes trough the \e inccoming arcs of a certain node
     681      /// This iterator goes trough the \e incoming arcs of a certain node
    667682      /// of a digraph.
    668683      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
     
    676691      /// \brief The base node of the iterator.
    677692      ///
    678       /// Gives back the base node of the iterator.
    679       /// It is always the target of the pointed arc.
     693      /// This function gives back the base node of the iterator.
     694      /// It is always the target node of the pointed arc.
    680695      Node baseNode(const InArcIt&) const { return INVALID; }
    681696
    682697      /// \brief The running node of the iterator.
    683698      ///
    684       /// Gives back the running node of the iterator.
    685       /// It is always the source of the pointed arc.
     699      /// This function gives back the running node of the iterator.
     700      /// It is always the source node of the pointed arc.
    686701      Node runningNode(const InArcIt&) const { return INVALID; }
    687702
    688703      /// \brief The base node of the iterator.
    689704      ///
    690       /// Gives back the base node of the iterator.
    691       /// It is always the source of the pointed arc.
     705      /// This function gives back the base node of the iterator.
     706      /// It is always the source node of the pointed arc.
    692707      Node baseNode(const OutArcIt&) const { return INVALID; }
    693708
    694709      /// \brief The running node of the iterator.
    695710      ///
    696       /// Gives back the running node of the iterator.
    697       /// It is always the target of the pointed arc.
     711      /// This function gives back the running node of the iterator.
     712      /// It is always the target node of the pointed arc.
    698713      Node runningNode(const OutArcIt&) const { return INVALID; }
    699714
     
    737752
    738753            typename _Digraph::Node n;
    739             typename _Digraph::InArcIt ieit(INVALID);
    740             typename _Digraph::OutArcIt oeit(INVALID);
    741             n = digraph.baseNode(ieit);
    742             n = digraph.runningNode(ieit);
    743             n = digraph.baseNode(oeit);
    744             n = digraph.runningNode(oeit);
     754            const typename _Digraph::InArcIt iait(INVALID);
     755            const typename _Digraph::OutArcIt oait(INVALID);
     756            n = digraph.baseNode(iait);
     757            n = digraph.runningNode(iait);
     758            n = digraph.baseNode(oait);
     759            n = digraph.runningNode(oait);
    745760            ignore_unused_variable_warning(n);
    746761          }
     
    748763
    749764        const _Digraph& digraph;
    750 
    751       };
    752     };
    753 
    754     /// \brief An empty iterable undirected graph class.
    755     ///
    756     /// This class provides beside the core graph features iterator
    757     /// based iterable interface for the undirected graph structure.
     765      };
     766    };
     767
     768    /// \brief Skeleton class for iterable undirected graphs.
     769    ///
     770    /// This class describes the interface of iterable undirected
     771    /// graphs. It extends \ref IterableDigraphComponent with the core
     772    /// iterable interface of undirected graphs.
    758773    /// This concept is part of the Graph concept.
    759     template <typename _Base = BaseGraphComponent>
    760     class IterableGraphComponent : public IterableDigraphComponent<_Base> {
    761     public:
    762 
    763       typedef _Base Base;
     774    template <typename BAS = BaseGraphComponent>
     775    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
     776    public:
     777
     778      typedef BAS Base;
    764779      typedef typename Base::Node Node;
    765780      typedef typename Base::Arc Arc;
     
    769784      typedef IterableGraphComponent Graph;
    770785
    771       /// \name Base iteration
    772       ///
    773       /// This interface provides functions for iteration on graph items
     786      /// \name Base Iteration
     787      ///
     788      /// This interface provides functions for iteration on edges.
     789      ///
    774790      /// @{
    775791
    776       using IterableDigraphComponent<_Base>::first;
    777       using IterableDigraphComponent<_Base>::next;
    778 
    779       /// \brief Gives back the first edge in the iterating
    780       /// order.
    781       ///
    782       /// Gives back the first edge in the iterating order.
    783       ///
     792      using IterableDigraphComponent<Base>::first;
     793      using IterableDigraphComponent<Base>::next;
     794
     795      /// \brief Return the first edge.
     796      ///
     797      /// This function gives back the first edge in the iteration order.
    784798      void first(Edge&) const {}
    785799
    786       /// \brief Gives back the next edge in the iterating
    787       /// order.
    788       ///
    789       /// Gives back the next edge in the iterating order.
    790       ///
     800      /// \brief Return the next edge.
     801      ///
     802      /// This function gives back the next edge in the iteration order.
    791803      void next(Edge&) const {}
    792804
    793 
    794       /// \brief Gives back the first of the edges from the
     805      /// \brief Return the first edge incident to the given node.
     806      ///
     807      /// This function gives back the first edge incident to the given
     808      /// node. The bool parameter gives back the direction for which the
     809      /// source node of the directed arc representing the edge is the
    795810      /// given node.
    796       ///
    797       /// Gives back the first of the edges from the given
    798       /// node. The bool parameter gives back that direction which
    799       /// gives a good direction of the edge so the source of the
    800       /// directed arc is the given node.
    801811      void firstInc(Edge&, bool&, const Node&) const {}
    802812
     
    804814      /// given node.
    805815      ///
    806       /// Gives back the next of the edges from the given
    807       /// node. The bool parameter should be used as the \c firstInc()
    808       /// use it.
     816      /// This function gives back the next edge incident to the given
     817      /// node. The bool parameter should be used as \c firstInc() use it.
    809818      void nextInc(Edge&, bool&) const {}
    810819
    811       using IterableDigraphComponent<_Base>::baseNode;
    812       using IterableDigraphComponent<_Base>::runningNode;
     820      using IterableDigraphComponent<Base>::baseNode;
     821      using IterableDigraphComponent<Base>::runningNode;
    813822
    814823      /// @}
    815824
    816       /// \name Class based iteration
    817       ///
    818       /// This interface provides functions for iteration on graph items
     825      /// \name Class Based Iteration
     826      ///
     827      /// This interface provides iterator classes for edges.
    819828      ///
    820829      /// @{
    821830
    822       /// \brief This iterator goes through each node.
    823       ///
    824       /// This iterator goes through each node.
     831      /// \brief This iterator goes through each edge.
     832      ///
     833      /// This iterator goes through each edge.
    825834      typedef GraphItemIt<Graph, Edge> EdgeIt;
    826       /// \brief This iterator goes trough the incident arcs of a
     835
     836      /// \brief This iterator goes trough the incident edges of a
    827837      /// node.
    828838      ///
    829       /// This iterator goes trough the incident arcs of a certain
     839      /// This iterator goes trough the incident edges of a certain
    830840      /// node of a graph.
    831       typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
     841      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
     842
    832843      /// \brief The base node of the iterator.
    833844      ///
    834       /// Gives back the base node of the iterator.
     845      /// This function gives back the base node of the iterator.
    835846      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    836847
    837848      /// \brief The running node of the iterator.
    838849      ///
    839       /// Gives back the running node of the iterator.
     850      /// This function gives back the running node of the iterator.
    840851      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    841852