COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 added
71 deleted
109 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r610 r514  
    2323lemon/stamp-h2
    2424doc/Doxyfile
    25 cmake/version.cmake
     25cmake/cmake.version
    2626.dirstamp
    2727.libs/*
    2828.deps/*
    2929demo/*.eps
    30 m4/libtool.m4
    31 m4/ltoptions.m4
    32 m4/ltsugar.m4
    33 m4/ltversion.m4
    34 m4/lt~obsolete.m4
    3530
    3631syntax: regexp
     
    4136^autom4te.cache/.*
    4237^build-aux/.*
    43 ^.*objs.*/.*
     38^objs.*/.*
    4439^test/[a-z_]*$
    45 ^tools/[a-z-_]*$
    4640^demo/.*_demo$
    47 ^.*build.*/.*
     41^build/.*
    4842^doc/gen-images/.*
    4943CMakeFiles
  • CMakeLists.txt

    r727 r540  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    3 SET(PROJECT_NAME "LEMON")
     3IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     4  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     5ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     6  SET(PROJECT_NAME "LEMON")
     7  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
     8ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
     9
    410PROJECT(${PROJECT_NAME})
    511
    6 IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    7   INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
    8 ELSEIF(DEFINED ENV{LEMON_VERSION})
    9   SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
    10 ELSE()
    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.")
    22 ENDIF()
     12SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
    2313
    24 SET(PROJECT_VERSION ${LEMON_VERSION})
     14INCLUDE(FindDoxygen)
     15INCLUDE(FindGhostscript)
    2516
    26 SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    27 
    28 FIND_PACKAGE(Doxygen)
    29 FIND_PACKAGE(Ghostscript)
    30 FIND_PACKAGE(GLPK 4.33)
    31 FIND_PACKAGE(CPLEX)
    32 FIND_PACKAGE(COIN)
     17ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    3318
    3419INCLUDE(CheckTypeSize)
    35 CHECK_TYPE_SIZE("long long" LONG_LONG)
    36 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     20CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
    3721
    3822ENABLE_TESTING()
    3923
    4024ADD_SUBDIRECTORY(lemon)
    41 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    42   ADD_SUBDIRECTORY(demo)
    43   ADD_SUBDIRECTORY(tools)
    44   ADD_SUBDIRECTORY(doc)
    45   ADD_SUBDIRECTORY(test)
    46 ENDIF()
     25ADD_SUBDIRECTORY(demo)
     26ADD_SUBDIRECTORY(doc)
     27ADD_SUBDIRECTORY(test)
    4728
    48 CONFIGURE_FILE(
    49   ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
    50   ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    51   @ONLY
    52 )
    53 IF(UNIX)
    54   INSTALL(
    55     FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    56     DESTINATION share/lemon/cmake
    57   )
    58 ELSEIF(WIN32)
    59   INSTALL(
    60     FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
    61     DESTINATION cmake
    62   )
    63 ENDIF()
    64 
    65 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
     29IF(WIN32)
    6630  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    6731  SET(CPACK_PACKAGE_VENDOR "EGRES")
    6832  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    69     "LEMON - Library for Efficient Modeling and Optimization in Networks")
    70   SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
     33    "LEMON - Library of Efficient Models and Optimization in Networks")
     34  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
    7135
    7236  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     
    7741    "${PROJECT_NAME} ${PROJECT_VERSION}")
    7842
    79   SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
     43  SET(CPACK_COMPONENTS_ALL headers library html_documentation)
    8044
    8145  SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    8246  SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    83   SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
    8447  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    8548
     
    8851  SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    8952    "DLL and import library")
    90   SET(CPACK_COMPONENT_BIN_DESCRIPTION
    91     "Command line utilities")
    9253  SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    9354    "Doxygen generated documentation")
     
    11172
    11273  SET(CPACK_GENERATOR "NSIS")
    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")
     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")
    11677  SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    11778  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     
    12889
    12990  INCLUDE(CPack)
    130 ENDIF()
     91ENDIF(WIN32)
  • INSTALL

    r615 r526  
    2828
    2929      This command compiles the non-template part of LEMON into libemon.a
    30       file. It also compiles the programs in the tools subdirectory by
    31       default.
     30      file. It also compiles the programs in the tools and demo subdirectories
     31      when enabled.
    3232
    3333   4. `make check'
     
    7575
    7676  Set the installation prefix to PREFIX. By default it is /usr/local.
     77
     78--enable-demo
     79
     80   Build the examples in the demo subdirectory.
     81
     82--disable-demo
     83
     84   Do not build the examples in the demo subdirectory (default).
    7785
    7886--enable-tools
     
    151159
    152160   Disable SoPlex support.
    153 
    154 --with-coin[=PREFIX]
    155 
    156    Enable support for COIN-OR solvers (CLP and CBC). You should
    157    specify the prefix too. (by default, COIN-OR tools install
    158    themselves to the source code directory). This command enables the
    159    solvers that are actually found.
    160 
    161 --with-coin-includedir=DIR
    162 
    163    The directory where the COIN-OR header files are located. This is
    164    only useful when the COIN-OR headers and libraries are not under
    165    the same prefix (which is unlikely).
    166 
    167 --with-coin-libdir=DIR
    168 
    169    The directory where the COIN-OR libraries are located. This is only
    170    useful when the COIN-OR headers and libraries are not under the
    171    same prefix (which is unlikely).
    172 
    173 --without-coin
    174 
    175    Disable COIN-OR support.
  • LICENSE

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

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

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

    r705 r318  
    1 =====================================================================
    2 LEMON - a Library for Efficient Modeling and Optimization in Networks
    3 =====================================================================
     1==================================================================
     2LEMON - a Library of Efficient Models and Optimization in Networks
     3==================================================================
    44
    55LEMON is an open source library written in C++. It provides
  • cmake/version.cmake.in

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

    r727 r540  
    33dnl Version information.
    44m4_define([lemon_version_number],
    5           [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     5        [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
    66dnl m4_define([lemon_version_number], [])
    77m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    8 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
     8m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
    99m4_define([lemon_version], [ifelse(lemon_version_number(),
    10                            [],
    11                            [ifelse(lemon_hg_revision(),
    12                            [],
    13                            [hg-tip],
    14                            [lemon_hg_path().lemon_hg_revision()])],
    15                            [lemon_version_number()])])
     10                           [],
     11                           [lemon_hg_path().lemon_hg_revision()],
     12                           [lemon_version_number()])])
    1613
    1714AC_PREREQ([2.59])
     
    2320AC_CONFIG_HEADERS([config.h lemon/config.h])
    2421
    25 AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
     22lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2623
    2724dnl Do compilation tests using the C++ compiler.
     
    5653
    5754dnl Set custom compiler flags when using g++.
    58 if 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"
     55if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
     56  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    6057fi
    61 AC_SUBST([WARNINGCXXFLAGS])
    6258
    6359dnl Checks for libraries.
    64 LX_CHECK_GLPK
    65 LX_CHECK_CPLEX
    66 LX_CHECK_SOPLEX
    67 LX_CHECK_COIN
     60#LX_CHECK_GLPK
     61#LX_CHECK_CPLEX
     62#LX_CHECK_SOPLEX
    6863
    69 AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
    70 AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
     64dnl Disable/enable building the demo programs.
     65AC_ARG_ENABLE([demo],
     66AS_HELP_STRING([--enable-demo], [build the demo programs])
     67AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
     68              [], [enable_demo=no])
     69AC_MSG_CHECKING([whether to build the demo programs])
     70if test x"$enable_demo" != x"no"; then
     71  AC_MSG_RESULT([yes])
     72else
     73  AC_MSG_RESULT([no])
     74fi
     75AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
    7176
    7277dnl Disable/enable building the binary tools.
     
    103108AC_CONFIG_FILES([
    104109Makefile
    105 demo/Makefile
    106110cmake/version.cmake
    107111doc/Doxyfile
     
    117121echo
    118122echo C++ compiler.................. : $CXX
    119 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     123echo C++ compiles flags............ : $CXXFLAGS
    120124echo
    121125echo Compiler supports long long... : $long_long_found
    122126echo
    123 echo GLPK support.................. : $lx_glpk_found
    124 echo CPLEX support................. : $lx_cplex_found
    125 echo SOPLEX support................ : $lx_soplex_found
    126 echo CLP support................... : $lx_clp_found
    127 echo CBC support................... : $lx_cbc_found
    128 echo
     127#echo GLPK support.................. : $lx_glpk_found
     128#echo CPLEX support................. : $lx_cplex_found
     129#echo SOPLEX support................ : $lx_soplex_found
     130#echo
     131echo Build demo programs........... : $enable_demo
    129132echo Build additional tools........ : $enable_tools
    130133echo
  • demo/CMakeLists.txt

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

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

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

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

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

    r726 r520  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
    4 SET(abs_top_builddir ${PROJECT_BINARY_DIR})
     3SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
     4SET(abs_top_builddir ${CMAKE_BINARY_DIR})
    55
    66CONFIGURE_FILE(
    7   ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
    8   ${PROJECT_BINARY_DIR}/doc/Doxyfile
    9   @ONLY
    10 )
     7  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
     8  ${CMAKE_BINARY_DIR}/doc/Doxyfile
     9  @ONLY)
    1110
    1211IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    1312  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 
    3713  IF(UNIX)
    38     INSTALL(
    39       DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    40       DESTINATION share/doc/lemon/html
    41       COMPONENT html_documentation
    42     )
     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})
    4325  ELSEIF(WIN32)
    44     INSTALL(
    45       DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
    46       DESTINATION doc
    47       COMPONENT html_documentation
    48     )
    49   ENDIF()
    50 
    51 ENDIF()
     26    ADD_CUSTOM_TARGET(html
     27      COMMAND if exist gen-images rmdir /s /q gen-images
     28      COMMAND mkdir gen-images
     29      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
     30      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
     31      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
     32      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     33      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
     34      COMMAND if exist html rmdir /s /q html
     35      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     36      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
     37  ENDIF(UNIX)
     38  INSTALL(
     39    DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
     40    DESTINATION share/doc
     41    COMPONENT html_documentation)
     42ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
  • doc/Doxyfile.in

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

    r720 r317  
    99        doc/mainpage.dox \
    1010        doc/migration.dox \
    11         doc/min_cost_flow.dox \
    1211        doc/named-param.dox \
    1312        doc/namespaces.dox \
     
    1615
    1716DOC_EPS_IMAGES18 = \
    18         grid_graph.eps \
    1917        nodeshape_0.eps \
    2018        nodeshape_1.eps \
     
    2321        nodeshape_4.eps
    2422
    25 DOC_EPS_IMAGES27 = \
    26         bipartite_matching.eps \
    27         bipartite_partitions.eps \
    28         connected_components.eps \
    29         edge_biconnected_components.eps \
    30         node_biconnected_components.eps \
    31         strongly_connected_components.eps
    32 
    3323DOC_EPS_IMAGES = \
    34         $(DOC_EPS_IMAGES18) \
    35         $(DOC_EPS_IMAGES27)
     24        $(DOC_EPS_IMAGES18)
    3625
    3726DOC_PNG_IMAGES = \
     
    4938        if test ${gs_found} = yes; then \
    5039          $(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=$@ $<; \
    6240        else \
    6341          echo; \
     
    9270install-html-local: doc/html
    9371        @$(NORMAL_INSTALL)
    94         $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
     72        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
    9573        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    9674          f="`echo $$p | sed -e 's|^.*/||'`"; \
    97           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
    98           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
     75          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
     76          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
    9977        done
    10078
     
    10381        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    10482          f="`echo $$p | sed -e 's|^.*/||'`"; \
    105           echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
    106           rm -f $(DESTDIR)$(htmldir)/html/$$f; \
     83          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
     84          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
    10785        done
    10886
  • doc/coding_style.dox

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

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

    r844 r318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    23 This group contains the several data structures implemented in LEMON.
     21This group describes the several data structures implemented in LEMON.
    2422*/
    2523
     
    6361
    6462/**
    65 @defgroup graph_adaptors Adaptor Classes for Graphs
     63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    6664@ingroup graphs
    67 \brief Adaptor classes for digraphs and graphs
    68 
    69 This group contains several useful adaptor classes for digraphs and graphs.
    70 
    71 The main parts of LEMON are the different graph structures, generic
    72 graph algorithms, graph concepts, which couple them, and graph
    73 adaptors. While the previous notions are more or less clear, the
    74 latter one needs further explanation. Graph adaptors are graph classes
    75 which serve for considering graph structures in different ways.
    76 
    77 A short example makes this much clearer.  Suppose that we have an
    78 instance \c g of a directed graph type, say ListDigraph and an algorithm
    79 \code
    80 template <typename Digraph>
    81 int algorithm(const Digraph&);
    82 \endcode
    83 is needed to run on the reverse oriented graph.  It may be expensive
    84 (in time or in memory usage) to copy \c g with the reversed
    85 arcs.  In this case, an adaptor class is used, which (according
    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
    87 The adaptor uses the original digraph structure and digraph operations when
    88 methods of the reversed oriented graph are called.  This means that the adaptor
    89 have minor memory usage, and do not perform sophisticated algorithmic
    90 actions.  The purpose of it is to give a tool for the cases when a
    91 graph have to be used in a specific alteration.  If this alteration is
    92 obtained by a usual construction like filtering the node or the arc set or
    93 considering a new orientation, then an adaptor is worthwhile to use.
    94 To come back to the reverse oriented graph, in this situation
    95 \code
    96 template<typename Digraph> class ReverseDigraph;
    97 \endcode
    98 template class can be used. The code looks as follows
    99 \code
    100 ListDigraph g;
    101 ReverseDigraph<ListDigraph> rg(g);
    102 int result = algorithm(rg);
    103 \endcode
    104 During running the algorithm, the original digraph \c g is untouched.
    105 This techniques give rise to an elegant code, and based on stable
    106 graph adaptors, complex algorithms can be implemented easily.
    107 
    108 In flow, circulation and matching problems, the residual
    109 graph is of particular importance. Combining an adaptor implementing
    110 this with shortest path algorithms or minimum mean cycle algorithms,
    111 a range of weighted and cardinality optimization algorithms can be
    112 obtained. For other examples, the interested user is referred to the
    113 detailed documentation of particular adaptors.
    114 
    115 The behavior of graph adaptors can be very different. Some of them keep
    116 capabilities of the original graph while in other cases this would be
    117 meaningless. This means that the concepts that they meet depend
    118 on the graph adaptor, and the wrapped graph.
    119 For example, if an arc of a reversed digraph is deleted, this is carried
    120 out by deleting the corresponding arc of the original digraph, thus the
    121 adaptor modifies the original digraph.
    122 However in case of a residual digraph, this operation has no sense.
    123 
    124 Let us stand one more example here to simplify your work.
    125 ReverseDigraph has constructor
    126 \code
    127 ReverseDigraph(Digraph& digraph);
    128 \endcode
    129 This means that in a situation, when a <tt>const %ListDigraph&</tt>
    130 reference to a graph is given, then it have to be instantiated with
    131 <tt>Digraph=const %ListDigraph</tt>.
    132 \code
    133 int algorithm1(const ListDigraph& g) {
    134   ReverseDigraph<const ListDigraph> rg(g);
    135   return algorithm2(rg);
    136 }
    137 \endcode
     65\brief Graph types between real graphs and graph adaptors.
     66
     67This group describes some graph types between real graphs and graph adaptors.
     68These classes wrap graphs to give new functionality as the adaptors do it.
     69On the other hand they are not light-weight structures as the adaptors.
    13870*/
    13971
     
    14375\brief Map structures implemented in LEMON.
    14476
    145 This group contains the map structures implemented in LEMON.
     77This group describes the map structures implemented in LEMON.
    14678
    14779LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    15688\brief Special graph-related maps.
    15789
    158 This group contains maps that are specifically designed to assign
    159 values to the nodes and arcs/edges of graphs.
    160 
    161 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    162 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     90This group describes maps that are specifically designed to assign
     91values to the nodes and arcs of graphs.
    16392*/
    16493
     
    16897\brief Tools to create new maps from existing ones
    16998
    170 This group contains map adaptors that are used to create "implicit"
     99This group describes map adaptors that are used to create "implicit"
    171100maps from other maps.
    172101
    173 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    174103They can make arithmetic and logical operations between one or two maps
    175104(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    227156
    228157/**
     158@defgroup matrices Matrices
     159@ingroup datas
     160\brief Two dimensional data storages implemented in LEMON.
     161
     162This group describes two dimensional data storages implemented in LEMON.
     163*/
     164
     165/**
    229166@defgroup paths Path Structures
    230167@ingroup datas
    231168\brief %Path structures implemented in LEMON.
    232169
    233 This group contains the path structures implemented in LEMON.
     170This group describes the path structures implemented in LEMON.
    234171
    235172LEMON provides flexible data structures to work with paths.
     
    247184\brief Auxiliary data structures implemented in LEMON.
    248185
    249 This group contains some data structures implemented in LEMON in
     186This group describes some data structures implemented in LEMON in
    250187order to make it easier to implement combinatorial algorithms.
    251188*/
     
    253190/**
    254191@defgroup algs Algorithms
    255 \brief This group contains the several algorithms
     192\brief This group describes the several algorithms
    256193implemented in LEMON.
    257194
    258 This group contains the several algorithms
     195This group describes the several algorithms
    259196implemented in LEMON.
    260197*/
     
    265202\brief Common graph search algorithms.
    266203
    267 This group contains the common graph search algorithms, namely
    268 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    269206*/
    270207
     
    274211\brief Algorithms for finding shortest paths.
    275212
    276 This 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.
     213This group describes the algorithms for finding shortest paths in graphs.
    282214*/
    283215
     
    287219\brief Algorithms for finding maximum flows.
    288220
    289 This group contains the algorithms for finding maximum flows and
     221This group describes the algorithms for finding maximum flows and
    290222feasible circulations.
    291223
    292 The \e maximum \e flow \e problem is to find a flow of maximum value between
    293 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    294 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    295 \f$s, t \in V\f$ source and target nodes.
    296 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    297 following 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
    305 Tarjan for solving this problem. It also provides functions to query the
    306 minimum cut, which is the dual problem of maximum flow.
    307 
    308 
    309 \ref Circulation is a preflow push-relabel algorithm implemented directly
    310 for finding feasible circulations, which is a somewhat different problem,
    311 but it is strongly related to maximum flow.
    312 For more information, see \ref Circulation.
    313 */
    314 
    315 /**
    316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     234
     235LEMON 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
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
    317249@ingroup algs
    318250
    319251\brief Algorithms for finding minimum cost flows and circulations.
    320252
    321 This group contains the algorithms for finding minimum cost flows and
    322 circulations. For more information about this problem and its dual
    323 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    324 
    325 \ref NetworkSimplex is an efficient implementation of the primal Network
    326 Simplex algorithm for finding minimum cost flows. It also provides dual
    327 solution (node potentials), if an optimal flow is found.
     253This group describes the algorithms for finding minimum cost flows and
     254circulations.
    328255*/
    329256
     
    334261\brief Algorithms for finding minimum cut in graphs.
    335262
    336 This group contains the algorithms for finding minimum cut in graphs.
    337 
    338 The \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
    340 outgoing 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
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    342269cut is the \f$X\f$ solution of the next optimization problem:
    343270
    344271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    345     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    346273
    347274LEMON contains several algorithms related to minimum cut problems:
    348275
    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.
     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
    353282
    354283If you want to find minimum cut just between two distinict nodes,
    355 see the \ref max_flow "maximum flow problem".
    356 */
    357 
    358 /**
    359 @defgroup graph_properties Connectivity and Other Graph Properties
     284please see the \ref max_flow "Maximum Flow page".
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
    360289@ingroup algs
    361290\brief Algorithms for discovering the graph properties
    362291
    363 This group contains the algorithms for discovering the graph properties
     292This group describes the algorithms for discovering the graph properties
    364293like connectivity, bipartiteness, euler property, simplicity etc.
    365294
     
    369298
    370299/**
     300@defgroup planar Planarity Embedding and Drawing
     301@ingroup algs
     302\brief Algorithms for planarity checking, embedding and drawing
     303
     304This group describes the algorithms for planarity checking,
     305embedding and drawing.
     306
     307\image html planar.png
     308\image latex planar.eps "Plane graph" width=\textwidth
     309*/
     310
     311/**
    371312@defgroup matching Matching Algorithms
    372313@ingroup algs
    373314\brief Algorithms for finding matchings in graphs and bipartite graphs.
    374315
    375 This group contains the algorithms for calculating matchings in graphs.
    376 The general matching problem is finding a subset of the edges for which
    377 each node has at most one incident edge.
     316This group contains algorithm objects and functions to calculate
     317matchings in graphs and bipartite graphs. The general matching problem is
     318finding a subset of the arcs which does not shares common endpoints.
    378319
    379320There are several different algorithms for calculate matchings in
    380 graphs. The goal of the matching optimization
    381 can be finding maximum cardinality, maximum weight or minimum cost
     321graphs.  The matching problems in bipartite graphs are generally
     322easier than in general graphs. The goal of the matching optimization
     323can be the finding maximum cardinality, maximum weight or minimum cost
    382324matching. The search can be constrained to find perfect or
    383325maximum cardinality matching.
    384326
    385 The 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.
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
    393347
    394348\image html bipartite_matching.png
     
    399353@defgroup spantree Minimum Spanning Tree Algorithms
    400354@ingroup algs
    401 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    402 
    403 This group contains the algorithms for finding minimum cost spanning
    404 trees and arborescences.
     355\brief Algorithms for finding a minimum cost spanning tree in a graph.
     356
     357This group describes the algorithms for finding a minimum cost spanning
     358tree in a graph
    405359*/
    406360
     
    410364\brief Auxiliary algorithms implemented in LEMON.
    411365
    412 This group contains some algorithms implemented in LEMON
     366This group describes some algorithms implemented in LEMON
    413367in order to make it easier to implement complex algorithms.
    414368*/
    415369
    416370/**
     371@defgroup approx Approximation Algorithms
     372@ingroup algs
     373\brief Approximation algorithms.
     374
     375This group describes the approximation and heuristic algorithms
     376implemented in LEMON.
     377*/
     378
     379/**
    417380@defgroup gen_opt_group General Optimization Tools
    418 \brief This group contains some general optimization frameworks
     381\brief This group describes some general optimization frameworks
    419382implemented in LEMON.
    420383
    421 This group contains some general optimization frameworks
     384This group describes some general optimization frameworks
    422385implemented in LEMON.
    423386*/
     
    428391\brief Lp and Mip solver interfaces for LEMON.
    429392
    430 This group contains Lp and Mip solver interfaces for LEMON. The
     393This group describes Lp and Mip solver interfaces for LEMON. The
    431394various LP solvers could be used in the same manner with this
    432395interface.
     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
     403This group adds some helper tools to general optimization framework
     404implemented in LEMON.
     405*/
     406
     407/**
     408@defgroup metah Metaheuristics
     409@ingroup gen_opt_group
     410\brief Metaheuristics for LEMON library.
     411
     412This group describes some metaheuristic optimization tools.
    433413*/
    434414
     
    445425\brief Simple basic graph utilities.
    446426
    447 This group contains some simple basic graph utilities.
     427This group describes some simple basic graph utilities.
    448428*/
    449429
     
    453433\brief Tools for development, debugging and testing.
    454434
    455 This group contains several useful tools for development,
     435This group describes several useful tools for development,
    456436debugging and testing.
    457437*/
     
    462442\brief Simple tools for measuring the performance of algorithms.
    463443
    464 This group contains simple tools for measuring the performance
     444This group describes simple tools for measuring the performance
    465445of algorithms.
    466446*/
     
    471451\brief Exceptions defined in LEMON.
    472452
    473 This group contains the exceptions defined in LEMON.
     453This group describes the exceptions defined in LEMON.
    474454*/
    475455
     
    478458\brief Graph Input-Output methods
    479459
    480 This group contains the tools for importing and exporting graphs
     460This group describes the tools for importing and exporting graphs
    481461and graph related data. Now it supports the \ref lgf-format
    482462"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    485465
    486466/**
    487 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    488468@ingroup io_group
    489469\brief Reading and writing LEMON Graph Format.
    490470
    491 This group contains methods for reading and writing
     471This group describes methods for reading and writing
    492472\ref lgf-format "LEMON Graph Format".
    493473*/
     
    498478\brief General \c EPS drawer and graph exporter
    499479
    500 This group contains general \c EPS drawing methods and special
     480This group describes general \c EPS drawing methods and special
    501481graph 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 
    509 Tools 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 
    517 Tool to read graphs from \e Nauty format data.
    518482*/
    519483
     
    522486\brief Skeleton classes and concept checking classes
    523487
    524 This group contains the data/algorithm skeletons and concept checking
     488This group describes the data/algorithm skeletons and concept checking
    525489classes implemented in LEMON.
    526490
     
    552516\brief Skeleton and concept checking classes for graph structures
    553517
    554 This group contains the skeletons and concept checking classes of LEMON's
     518This group describes the skeletons and concept checking classes of LEMON's
    555519graph structures and helper classes used to implement these.
    556520*/
     
    561525\brief Skeleton and concept checking classes for maps
    562526
    563 This group contains the skeletons and concept checking classes of maps.
     527This group describes the skeletons and concept checking classes of maps.
    564528*/
    565529
     
    567531\anchor demoprograms
    568532
    569 @defgroup demos Demo Programs
     533@defgroup demos Demo programs
    570534
    571535Some demo programs are listed here. Their full source codes can be found in
    572536the \c demo subdirectory of the source tree.
    573537
    574 In 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
     538It order to compile them, use <tt>--enable-demo</tt> configure option when
     539build the library.
     540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
    580544
    581545Some utility applications are listed here.
     
    585549*/
    586550
    587 }
  • doc/lgf.dox

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

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

    r705 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2424\subsection whatis What is LEMON
    2525
    26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     26LEMON stands for
     27<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
    2728and <b>O</b>ptimization in <b>N</b>etworks.
    2829It is a C++ template
     
    4142\subsection howtoread How to read the documentation
    4243
    43 If 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>.
     44If you want to get a quick start and see the most important features then
     45take a look at our \ref quicktour
     46"Quick Tour to LEMON" which will guide you along.
    4547
    46 If you know what you are looking for, then try to find it under the
    47 <a class="el" href="modules.html">Modules</a> section.
     48If you already feel like using our library, see the page that tells you
     49\ref getstart "How to start using LEMON".
     50
     51If you
     52want to see how LEMON works, see
     53some \ref demoprograms "demo programs".
     54
     55If you know what you are looking for then try to find it under the
     56<a class="el" href="modules.html">Modules</a>
     57section.
    4858
    4959If you are a user of the old (0.x) series of LEMON, please check out the
  • doc/migration.dox

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

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

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

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

    r726 r539  
    11INCLUDE_DIRECTORIES(
    2   ${PROJECT_SOURCE_DIR}
     2  ${CMAKE_SOURCE_DIR}
    33  ${PROJECT_BINARY_DIR}
    44)
     
    99)
    1010
    11 SET(LEMON_SOURCES
     11ADD_LIBRARY(lemon
    1212  arg_parser.cc
    1313  base.cc
    1414  color.cc
    15   lp_base.cc
    16   lp_skeleton.cc
    1715  random.cc
    1816  bits/windows.cc
    1917)
    2018
    21 IF(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()
    29 ENDIF()
    30 
    31 IF(LEMON_HAVE_CPLEX)
    32   SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    33   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
    34 ENDIF()
    35 
    36 IF(LEMON_HAVE_CLP)
    37   SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
    38   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    39 ENDIF()
    40 
    41 IF(LEMON_HAVE_CBC)
    42   SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    43   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    44 ENDIF()
    45 
    46 ADD_LIBRARY(lemon ${LEMON_SOURCES})
    47 IF(UNIX)
    48   SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
    49 ENDIF()
    50 
    5119INSTALL(
    5220  TARGETS lemon
    5321  ARCHIVE DESTINATION lib
    54   COMPONENT library
    55 )
     22  COMPONENT library)
    5623
    5724INSTALL(
     
    5926  DESTINATION include/lemon
    6027  COMPONENT headers
    61   FILES_MATCHING PATTERN "*.h"
    62 )
     28  FILES_MATCHING PATTERN "*.h")
    6329
    6430INSTALL(
    6531  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
    6632  DESTINATION include/lemon
    67   COMPONENT headers
    68 )
     33  COMPONENT headers)
  • lemon/Makefile.am

    r850 r543  
    11EXTRA_DIST += \
    22        lemon/lemon.pc.in \
    3         lemon/CMakeLists.txt \
    4         lemon/config.h.cmake
     3        lemon/CMakeLists.txt
    54
    65pkgconfig_DATA += lemon/lemon.pc
     
    98
    109lemon_libemon_la_SOURCES = \
    11         lemon/arg_parser.cc \
    12         lemon/base.cc \
    13         lemon/color.cc \
    14         lemon/lp_base.cc \
    15         lemon/lp_skeleton.cc \
    16         lemon/random.cc \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/random.cc \
    1714        lemon/bits/windows.cc
    1815
    19 nodist_lemon_HEADERS = lemon/config.h   
     16#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     17#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    2018
    21 lemon_libemon_la_CXXFLAGS = \
    22         $(AM_CXXFLAGS) \
    23         $(GLPK_CFLAGS) \
    24         $(CPLEX_CFLAGS) \
    25         $(SOPLEX_CXXFLAGS) \
    26         $(CLP_CXXFLAGS) \
    27         $(CBC_CXXFLAGS)
    28 
    29 lemon_libemon_la_LDFLAGS = \
    30         $(GLPK_LIBS) \
    31         $(CPLEX_LIBS) \
    32         $(SOPLEX_LIBS) \
    33         $(CLP_LIBS) \
    34         $(CBC_LIBS)
    35 
    36 if HAVE_GLPK
    37 lemon_libemon_la_SOURCES += lemon/glpk.cc
    38 endif
    39 
    40 if HAVE_CPLEX
    41 lemon_libemon_la_SOURCES += lemon/cplex.cc
    42 endif
    43 
    44 if HAVE_SOPLEX
    45 lemon_libemon_la_SOURCES += lemon/soplex.cc
    46 endif
    47 
    48 if HAVE_CLP
    49 lemon_libemon_la_SOURCES += lemon/clp.cc
    50 endif
    51 
    52 if HAVE_CBC
    53 lemon_libemon_la_SOURCES += lemon/cbc.cc
    54 endif
     19nodist_lemon_HEADERS = lemon/config.h
    5520
    5621lemon_HEADERS += \
    57         lemon/adaptors.h \
    58         lemon/arg_parser.h \
     22        lemon/arg_parser.h \
    5923        lemon/assert.h \
    60         lemon/bfs.h \
    61         lemon/bin_heap.h \
    62         lemon/cbc.h \
    63         lemon/circulation.h \
    64         lemon/clp.h \
    65         lemon/color.h \
     24        lemon/bfs.h \
     25        lemon/bin_heap.h \
     26        lemon/color.h \
    6627        lemon/concept_check.h \
    67         lemon/connectivity.h \
    68         lemon/counter.h \
     28        lemon/counter.h \
    6929        lemon/core.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 \
     30        lemon/dfs.h \
     31        lemon/dijkstra.h \
     32        lemon/dim2.h \
    7733        lemon/error.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 \
     34        lemon/graph_to_eps.h \
    8535        lemon/kruskal.h \
    86         lemon/hao_orlin.h \
    8736        lemon/lgf_reader.h \
    8837        lemon/lgf_writer.h \
    8938        lemon/list_graph.h \
    90         lemon/lp.h \
    91         lemon/lp_base.h \
    92         lemon/lp_skeleton.h \
    9339        lemon/maps.h \
    94         lemon/matching.h \
    9540        lemon/math.h \
    96         lemon/min_cost_arborescence.h \
    97         lemon/nauty_reader.h \
    98         lemon/network_simplex.h \
    9941        lemon/path.h \
    100         lemon/preflow.h \
    101         lemon/radix_sort.h \
    102         lemon/random.h \
     42        lemon/random.h \
    10343        lemon/smart_graph.h \
    104         lemon/soplex.h \
    105         lemon/suurballe.h \
    106         lemon/time_measure.h \
    107         lemon/tolerance.h \
     44        lemon/time_measure.h \
     45        lemon/tolerance.h \
    10846        lemon/unionfind.h \
    10947        lemon/bits/windows.h
     
    11250        lemon/bits/alteration_notifier.h \
    11351        lemon/bits/array_map.h \
    114         lemon/bits/bezier.h \
     52        lemon/bits/base_extender.h \
     53        lemon/bits/bezier.h \
    11554        lemon/bits/default_map.h \
    116         lemon/bits/edge_set_extender.h \
    117         lemon/bits/enable_if.h \
    118         lemon/bits/graph_adaptor_extender.h \
     55        lemon/bits/enable_if.h \
    11956        lemon/bits/graph_extender.h \
    12057        lemon/bits/map_extender.h \
    12158        lemon/bits/path_dump.h \
    122         lemon/bits/solver_bits.h \
    12359        lemon/bits/traits.h \
    124         lemon/bits/variant.h \
    12560        lemon/bits/vector_map.h
    12661
  • lemon/arg_parser.cc

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

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

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

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

    r525 r301  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \c PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
     56    ///PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a \c ProcessedMap.
    68 
    69     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the 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 \c ReachedMap.
    87 
    88     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the 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 \c DistMap.
    102 
    103     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///\ref DistMap.
     105    ///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 type is \ref ListDigraph.
     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.
    123129#ifdef DOXYGEN
    124130  template <typename GR,
     
    146152    typedef PredMapPath<Digraph, PredMap> Path;
    147153
    148     ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     154    ///The traits class.
    149155    typedef TR Traits;
    150156
     
    208214    typedef Bfs Create;
    209215
    210     ///\name Named Template Parameters
     216    ///\name Named template parameters
    211217
    212218    ///@{
     
    222228    };
    223229    ///\brief \ref named-templ-param "Named parameter" for setting
    224     ///\c PredMap type.
     230    ///PredMap type.
    225231    ///
    226232    ///\ref named-templ-param "Named parameter" for setting
    227     ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     233    ///PredMap type.
    229234    template <class T>
    230235    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    242247    };
    243248    ///\brief \ref named-templ-param "Named parameter" for setting
    244     ///\c DistMap type.
     249    ///DistMap type.
    245250    ///
    246251    ///\ref named-templ-param "Named parameter" for setting
    247     ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     252    ///DistMap type.
    249253    template <class T>
    250254    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    262266    };
    263267    ///\brief \ref named-templ-param "Named parameter" for setting
    264     ///\c ReachedMap type.
     268    ///ReachedMap type.
    265269    ///
    266270    ///\ref named-templ-param "Named parameter" for setting
    267     ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     271    ///ReachedMap type.
    269272    template <class T>
    270273    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    282285    };
    283286    ///\brief \ref named-templ-param "Named parameter" for setting
    284     ///\c ProcessedMap type.
     287    ///ProcessedMap type.
    285288    ///
    286289    ///\ref named-templ-param "Named parameter" for setting
    287     ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     290    ///ProcessedMap type.
    289291    template <class T>
    290292    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    301303    };
    302304    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     305    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304306    ///
    305307    ///\ref named-templ-param "Named parameter" for setting
    306     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     308    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307309    ///If you don't set it explicitly, it will be automatically allocated.
    308310    struct SetStandardProcessedMap :
     
    339341
    340342    ///Sets the map that stores the predecessor arcs.
    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.
     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.
    345346    ///\return <tt> (*this) </tt>
    346347    Bfs &predMap(PredMap &m)
     
    357358
    358359    ///Sets the map that indicates which nodes are reached.
    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.
     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.
    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(Node) "run()"
    378     ///or \ref init(), an instance will be allocated automatically.
    379     ///The destructor deallocates this automatically allocated map,
    380     ///of course.
     377    ///If you don't use this function before calling \ref run(),
     378    ///it will allocate one. The destructor deallocates this
     379    ///automatically allocated map, of course.
    381380    ///\return <tt> (*this) </tt>
    382381    Bfs &processedMap(ProcessedMap &m)
     
    394393    ///Sets the map that stores the distances of the nodes calculated by
    395394    ///the algorithm.
    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.
     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.
    400398    ///\return <tt> (*this) </tt>
    401399    Bfs &distMap(DistMap &m)
     
    411409  public:
    412410
    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.
     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.
    420420
    421421    ///@{
    422422
    423     ///\brief Initializes the internal data structures.
    424     ///
    425423    ///Initializes the internal data structures.
     424
     425    ///Initializes the internal data structures.
     426    ///
    426427    void init()
    427428    {
     
    557558    }
    558559
    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.
     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.
    563565    bool emptyQueue() const { return _queue_tail==_queue_head; }
    564566
    565567    ///Returns the number of the nodes to be processed.
    566568
    567     ///Returns the number of the nodes to be processed
    568     ///in the queue.
     569    ///Returns the number of the nodes to be processed in the queue.
    569570    int queueSize() const { return _queue_head-_queue_tail; }
    570571
     
    731732
    732733    ///\name Query Functions
    733     ///The results of the BFS algorithm can be obtained using these
     734    ///The result of the %BFS algorithm can be obtained using these
    734735    ///functions.\n
    735     ///Either \ref run(Node) "run()" or \ref start() should be called
    736     ///before using them.
     736    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     737    ///"start()" must be called before using them.
    737738
    738739    ///@{
     
    742743    ///Returns the shortest path to a node.
    743744    ///
    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.
     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.
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
     
    752753    ///Returns the distance of a node from the root(s).
    753754    ///
    754     ///\warning If node \c v is not reached from the root(s), then
     755    ///\warning If node \c v is not reachable from the root(s), then
    755756    ///the return value of this function is undefined.
    756757    ///
    757     ///\pre Either \ref run(Node) "run()" or \ref init()
    758     ///must be called before using this function.
     758    ///\pre Either \ref run() or \ref start() must be called before
     759    ///using this function.
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
     
    763764    ///This function returns the 'previous arc' of the shortest path
    764765    ///tree for the node \c v, i.e. it returns the last arc of a
    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.
     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.
    767768    ///
    768769    ///The shortest path tree used here is equal to the shortest path
    769770    ///tree used in \ref predNode().
    770771    ///
    771     ///\pre Either \ref run(Node) "run()" or \ref init()
    772     ///must be called before using this function.
     772    ///\pre Either \ref run() or \ref start() must be called before
     773    ///using this function.
    773774    Arc predArc(Node v) const { return (*_pred)[v];}
    774775
     
    777778    ///This function returns the 'previous node' of the shortest path
    778779    ///tree for the node \c v, i.e. it returns the last but one node
    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.
     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.
    781782    ///
    782783    ///The shortest path tree used here is equal to the shortest path
    783784    ///tree used in \ref predArc().
    784785    ///
    785     ///\pre Either \ref run(Node) "run()" or \ref init()
    786     ///must be called before using this function.
     786    ///\pre Either \ref run() or \ref start() must be called before
     787    ///using this function.
    787788    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    788789                                  G->source((*_pred)[v]); }
     
    794795    ///of the nodes calculated by the algorithm.
    795796    ///
    796     ///\pre Either \ref run(Node) "run()" or \ref init()
     797    ///\pre Either \ref run() or \ref init()
    797798    ///must be called before using this function.
    798799    const DistMap &distMap() const { return *_dist;}
     
    804805    ///arcs, which form the shortest path tree.
    805806    ///
    806     ///\pre Either \ref run(Node) "run()" or \ref init()
     807    ///\pre Either \ref run() or \ref init()
    807808    ///must be called before using this function.
    808809    const PredMap &predMap() const { return *_pred;}
    809810
    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()
     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()
    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(Node) "run()" method, it uses the
    961   /// functions and features of the plain \ref Bfs.
     960  /// It does not have own \ref run() method, it uses the functions
     961  /// and features of the plain \ref Bfs.
    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(Node) "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run() "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 GR>
     1197  template <typename _Digraph>
    11981198  struct BfsVisitor {
    1199     typedef GR Digraph;
     1199    typedef _Digraph Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
     
    12251225  };
    12261226#else
    1227   template <typename GR>
     1227  template <typename _Digraph>
    12281228  struct BfsVisitor {
    1229     typedef GR Digraph;
     1229    typedef _Digraph Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
     
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam GR The type of the digraph the algorithm runs on.
    1258   template<class GR>
     1257  /// \tparam _Digraph The type of the digraph the algorithm runs on.
     1258  template<class _Digraph>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef GR Digraph;
     1262    typedef _Digraph 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 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
     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
    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 TR Traits class to set various data types used by the
     1305  /// \tparam _Traits Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename GR, typename VS, typename TR>
     1311  template <typename _Digraph, typename _Visitor, typename _Traits>
    13121312#else
    1313   template <typename GR = ListDigraph,
    1314             typename VS = BfsVisitor<GR>,
    1315             typename TR = BfsVisitDefaultTraits<GR> >
     1313  template <typename _Digraph = ListDigraph,
     1314            typename _Visitor = BfsVisitor<_Digraph>,
     1315            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    13161316#endif
    13171317  class BfsVisit {
     
    13191319
    13201320    ///The traits class.
    1321     typedef TR Traits;
     1321    typedef _Traits Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
     
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef VS Visitor;
     1327    typedef _Visitor 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(Node) "run()"
    1410     /// or \ref init(), an instance will be allocated automatically.
    1411     /// The destructor deallocates this automatically allocated map,
    1412     /// of course.
     1409    /// If you don't use this function before calling \ref run(),
     1410    /// it will allocate one. The destructor deallocates this
     1411    /// automatically allocated map, of course.
    14131412    /// \return <tt> (*this) </tt>
    14141413    BfsVisit &reachedMap(ReachedMap &m) {
     
    14231422  public:
    14241423
    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.
     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.
    14321434
    14331435    /// @{
     
    17291731
    17301732    /// \name Query Functions
    1731     /// The results of the BFS algorithm can be obtained using these
     1733    /// The result of the %BFS algorithm can be obtained using these
    17321734    /// functions.\n
    1733     /// Either \ref run(Node) "run()" or \ref start() should be called
    1734     /// before using them.
    1735 
     1735    /// Either \ref lemon::BfsVisit::run() "run()" or
     1736    /// \ref lemon::BfsVisit::start() "start()" must be called before
     1737    /// using them.
    17361738    ///@{
    17371739
    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()
     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()
    17431744    /// must be called before using this function.
    1744     bool reached(Node v) const { return (*_reached)[v]; }
     1745    bool reached(Node v) { return (*_reached)[v]; }
    17451746
    17461747    ///@}
  • lemon/bin_heap.h

    r631 r209  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    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.
     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.
    4341  ///
    44   ///\tparam PR Type of the priority of the items.
    45   ///\tparam IM A read and writable item map with int values, used internally
     42  ///\tparam _Prio Type of the priority of the items.
     43  ///\tparam _ItemIntMap A read and writable Item int map, used internally
    4644  ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
    48   ///The default is \c std::less<PR>.
     45  ///\tparam _Compare A class for the ordering of the priorities. The
     46  ///default is \c std::less<_Prio>.
    4947  ///
    5048  ///\sa FibHeap
    5149  ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     50  template <typename _Prio, typename _ItemIntMap,
     51            typename _Compare = std::less<_Prio> >
    5352  class BinHeap {
    5453
    5554  public:
    5655    ///\e
    57     typedef IM ItemIntMap;
    58     ///\e
    59     typedef PR Prio;
     56    typedef _ItemIntMap ItemIntMap;
     57    ///\e
     58    typedef _Prio Prio;
    6059    ///\e
    6160    typedef typename ItemIntMap::Key Item;
     
    6362    typedef std::pair<Item,Prio> Pair;
    6463    ///\e
    65     typedef Comp Compare;
     64    typedef _Compare Compare;
    6665
    6766    /// \brief Type to represent the items states.
     
    7170    /// heap's point of view, but may be useful to the user.
    7271    ///
    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.
     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...
    7574    enum State {
    76       IN_HEAP = 0,    ///< = 0.
    77       PRE_HEAP = -1,  ///< = -1.
    78       POST_HEAP = -2  ///< = -2.
     75      IN_HEAP = 0,
     76      PRE_HEAP = -1,
     77      POST_HEAP = -2
    7978    };
    8079
    8180  private:
    82     std::vector<Pair> _data;
    83     Compare _comp;
    84     ItemIntMap &_iim;
     81    std::vector<Pair> data;
     82    Compare comp;
     83    ItemIntMap &iim;
    8584
    8685  public:
     
    8887    ///
    8988    /// The constructor.
    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
     89    /// \param _iim should be given to the constructor, since it is used
    9990    /// internally to handle the cross references. The value of the map
    10091    /// should be PRE_HEAP (-1) for each element.
    101     ///
    102     /// \param comp The comparator function object.
    103     BinHeap(ItemIntMap &map, const Compare &comp)
    104       : _iim(map), _comp(comp) {}
     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) {}
    105104
    106105
     
    108107    ///
    109108    /// \brief Returns the number of items stored in the heap.
    110     int size() const { return _data.size(); }
     109    int size() const { return data.size(); }
    111110
    112111    /// \brief Checks if the heap stores no items.
    113112    ///
    114113    /// Returns \c true if and only if the heap stores no items.
    115     bool empty() const { return _data.empty(); }
     114    bool empty() const { return data.empty(); }
    116115
    117116    /// \brief Make empty this heap.
     
    122121    /// each item to \c PRE_HEAP.
    123122    void clear() {
    124       _data.clear();
     123      data.clear();
    125124    }
    126125
     
    130129    static int second_child(int i) { return 2*i+2; }
    131130    bool less(const Pair &p1, const Pair &p2) const {
    132       return _comp(p1.second, p2.second);
     131      return comp(p1.second, p2.second);
    133132    }
    134133
    135134    int bubble_up(int hole, Pair p) {
    136135      int par = parent(hole);
    137       while( hole>0 && less(p,_data[par]) ) {
    138         move(_data[par],hole);
     136      while( hole>0 && less(p,data[par]) ) {
     137        move(data[par],hole);
    139138        hole = par;
    140139        par = parent(hole);
     
    147146      int child = second_child(hole);
    148147      while(child < length) {
    149         if( less(_data[child-1], _data[child]) ) {
     148        if( less(data[child-1], data[child]) ) {
    150149          --child;
    151150        }
    152         if( !less(_data[child], p) )
     151        if( !less(data[child], p) )
    153152          goto ok;
    154         move(_data[child], hole);
     153        move(data[child], hole);
    155154        hole = child;
    156155        child = second_child(hole);
    157156      }
    158157      child--;
    159       if( child<length && less(_data[child], p) ) {
    160         move(_data[child], hole);
     158      if( child<length && less(data[child], p) ) {
     159        move(data[child], hole);
    161160        hole=child;
    162161      }
     
    167166
    168167    void move(const Pair &p, int i) {
    169       _data[i] = p;
    170       _iim.set(p.first, i);
     168      data[i] = p;
     169      iim.set(p.first, i);
    171170    }
    172171
     
    177176    /// \param p The pair to insert.
    178177    void push(const Pair &p) {
    179       int n = _data.size();
    180       _data.resize(n+1);
     178      int n = data.size();
     179      data.resize(n+1);
    181180      bubble_up(n, p);
    182181    }
     
    195194    /// \pre The heap must be nonempty.
    196195    Item top() const {
    197       return _data[0].first;
     196      return data[0].first;
    198197    }
    199198
     
    203202    /// \pre The heap must be nonempty.
    204203    Prio prio() const {
    205       return _data[0].second;
     204      return data[0].second;
    206205    }
    207206
     
    212211    /// \pre The heap must be non-empty.
    213212    void pop() {
    214       int n = _data.size()-1;
    215       _iim.set(_data[0].first, POST_HEAP);
     213      int n = data.size()-1;
     214      iim.set(data[0].first, POST_HEAP);
    216215      if (n > 0) {
    217         bubble_down(0, _data[n], n);
    218       }
    219       _data.pop_back();
     216        bubble_down(0, data[n], n);
     217      }
     218      data.pop_back();
    220219    }
    221220
     
    226225    /// \pre The item should be in the heap.
    227226    void erase(const Item &i) {
    228       int h = _iim[i];
    229       int n = _data.size()-1;
    230       _iim.set(_data[h].first, POST_HEAP);
     227      int h = iim[i];
     228      int n = data.size()-1;
     229      iim.set(data[h].first, POST_HEAP);
    231230      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     231        if ( bubble_up(h, data[n]) == h) {
     232          bubble_down(h, data[n], n);
    234233        }
    235234      }
    236       _data.pop_back();
     235      data.pop_back();
    237236    }
    238237
     
    241240    ///
    242241    /// This function returns the priority of item \c i.
    243     /// \param i The item.
    244242    /// \pre \c i must be in the heap.
     243    /// \param i The item.
    245244    Prio operator[](const Item &i) const {
    246       int idx = _iim[i];
    247       return _data[idx].second;
     245      int idx = iim[i];
     246      return data[idx].second;
    248247    }
    249248
     
    256255    /// \param p The priority.
    257256    void set(const Item &i, const Prio &p) {
    258       int idx = _iim[i];
     257      int idx = iim[i];
    259258      if( idx < 0 ) {
    260259        push(i,p);
    261260      }
    262       else if( _comp(p, _data[idx].second) ) {
     261      else if( comp(p, data[idx].second) ) {
    263262        bubble_up(idx, Pair(i,p));
    264263      }
    265264      else {
    266         bubble_down(idx, Pair(i,p), _data.size());
     265        bubble_down(idx, Pair(i,p), data.size());
    267266      }
    268267    }
     
    271270    ///
    272271    /// This method decreases the priority of item \c i to \c p.
    273     /// \param i The item.
    274     /// \param p The priority.
    275272    /// \pre \c i must be stored in the heap with priority at least \c
    276273    /// p relative to \c Compare.
     274    /// \param i The item.
     275    /// \param p The priority.
    277276    void decrease(const Item &i, const Prio &p) {
    278       int idx = _iim[i];
     277      int idx = iim[i];
    279278      bubble_up(idx, Pair(i,p));
    280279    }
     
    283282    ///
    284283    /// This method sets the priority of item \c i to \c p.
    285     /// \param i The item.
    286     /// \param p The priority.
    287284    /// \pre \c i must be stored in the heap with priority at most \c
    288285    /// p relative to \c Compare.
     286    /// \param i The item.
     287    /// \param p The priority.
    289288    void increase(const Item &i, const Prio &p) {
    290       int idx = _iim[i];
    291       bubble_down(idx, Pair(i,p), _data.size());
     289      int idx = iim[i];
     290      bubble_down(idx, Pair(i,p), data.size());
    292291    }
    293292
     
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
    303       int s = _iim[i];
     302      int s = iim[i];
    304303      if( s>=0 )
    305304        s=0;
     
    321320          erase(i);
    322321        }
    323         _iim[i] = st;
     322        iim[i] = st;
    324323        break;
    325324      case IN_HEAP:
     
    335334    /// with the same prioriority as prevoiusly the \c i item.
    336335    void replace(const Item& i, const Item& j) {
    337       int idx = _iim[i];
    338       _iim.set(i, _iim[j]);
    339       _iim.set(j, idx);
    340       _data[idx].first = j;
     336      int idx = iim[i];
     337      iim.set(i, iim[j]);
     338      iim.set(j, idx);
     339      data[idx].first = j;
    341340    }
    342341
  • lemon/bits/alteration_notifier.h

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

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

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

    r674 r540  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    154154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
     156  public:
    156157    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     158    typedef DefaultMap<_Graph, _Item, _Value> Map;
    157159
    158   public:
    159     typedef DefaultMap<_Graph, _Item, _Value> Map;
    160    
    161     typedef typename Parent::GraphType GraphType;
     160    typedef typename Parent::Graph Graph;
    162161    typedef typename Parent::Value Value;
    163162
    164     explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
    165     DefaultMap(const GraphType& graph, const Value& value)
     163    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
     164    DefaultMap(const Graph& graph, const Value& value)
    166165      : Parent(graph, value) {}
    167166
  • lemon/bits/enable_if.h

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

    r732 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the graph types
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the digraph implementations
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     40  public:
     41
    4042    typedef Base Parent;
    41 
    42   public:
    43 
    4443    typedef DigraphExtender Digraph;
    4544
     
    220219    class NodeMap
    221220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
     221    public:
     222      typedef DigraphExtender Digraph;
    222223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    223224
    224     public:
    225225      explicit NodeMap(const Digraph& digraph)
    226226        : Parent(digraph) {}
     
    244244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
     246    public:
     247      typedef DigraphExtender Digraph;
    246248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    247249
    248     public:
    249250      explicit ArcMap(const Digraph& digraph)
    250251        : Parent(digraph) {}
     
    330331  template <typename Base>
    331332  class GraphExtender : public Base {
     333  public:
     334
    332335    typedef Base Parent;
    333 
    334   public:
    335 
    336336    typedef GraphExtender Graph;
    337337
     
    602602    class NodeMap
    603603      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     604    public:
     605      typedef GraphExtender Graph;
    604606      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    605607
    606     public:
    607       explicit NodeMap(const Graph& graph)
     608      NodeMap(const Graph& graph)
    608609        : Parent(graph) {}
    609610      NodeMap(const Graph& graph, const _Value& value)
     
    626627    class ArcMap
    627628      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     629    public:
     630      typedef GraphExtender Graph;
    628631      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    629632
    630     public:
    631       explicit ArcMap(const Graph& graph)
     633      ArcMap(const Graph& graph)
    632634        : Parent(graph) {}
    633635      ArcMap(const Graph& graph, const _Value& value)
     
    650652    class EdgeMap
    651653      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     654    public:
     655      typedef GraphExtender Graph;
    652656      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    653657
    654     public:
    655       explicit EdgeMap(const Graph& graph)
     658      EdgeMap(const Graph& graph)
    656659        : Parent(graph) {}
    657660
  • lemon/bits/map_extender.h

    r664 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
     39  public:
     40
    3941    typedef _Map Parent;
    40     typedef typename Parent::GraphType GraphType;
    41 
    42   public:
    43 
    4442    typedef MapExtender Map;
     43
     44
     45    typedef typename Parent::Graph Graph;
    4546    typedef typename Parent::Key Item;
    4647
    4748    typedef typename Parent::Key Key;
    4849    typedef typename Parent::Value Value;
    49     typedef typename Parent::Reference Reference;
    50     typedef typename Parent::ConstReference ConstReference;
    5150
    5251    class MapIt;
     
    5857  public:
    5958
    60     MapExtender(const GraphType& graph)
     59    MapExtender(const Graph& graph)
    6160      : Parent(graph) {}
    6261
    63     MapExtender(const GraphType& graph, const Value& value)
     62    MapExtender(const Graph& graph, const Value& value)
    6463      : Parent(graph, value) {}
    6564
     
    7776  public:
    7877    class MapIt : public Item {
    79       typedef Item Parent;
    80 
    81     public:
    82 
     78    public:
     79
     80      typedef Item Parent;
    8381      typedef typename Map::Value Value;
    8482
     
    117115
    118116    class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
     117    public:
     118
     119      typedef Item Parent;
    122120
    123121      typedef typename Map::Value Value;
     
    148146
    149147    class ItemIt : public Item {
    150       typedef Item Parent;
    151 
    152     public:
     148    public:
     149
     150      typedef Item Parent;
    153151
    154152      ItemIt() {}
     
    179177  template <typename _Graph, typename _Map>
    180178  class SubMapExtender : public _Map {
     179  public:
     180
    181181    typedef _Map Parent;
    182     typedef _Graph GraphType;
    183 
    184   public:
    185 
    186182    typedef SubMapExtender Map;
     183
     184    typedef _Graph Graph;
     185
    187186    typedef typename Parent::Key Item;
    188187
    189188    typedef typename Parent::Key Key;
    190189    typedef typename Parent::Value Value;
    191     typedef typename Parent::Reference Reference;
    192     typedef typename Parent::ConstReference ConstReference;
    193190
    194191    class MapIt;
     
    200197  public:
    201198
    202     SubMapExtender(const GraphType& _graph)
     199    SubMapExtender(const Graph& _graph)
    203200      : Parent(_graph), graph(_graph) {}
    204201
    205     SubMapExtender(const GraphType& _graph, const Value& _value)
     202    SubMapExtender(const Graph& _graph, const Value& _value)
    206203      : Parent(_graph, _value), graph(_graph) {}
    207204
     
    223220  public:
    224221    class MapIt : public Item {
    225       typedef Item Parent;
    226 
    227     public:
     222    public:
     223
     224      typedef Item Parent;
    228225      typedef typename Map::Value Value;
    229226
     
    262259
    263260    class ConstMapIt : public Item {
    264       typedef Item Parent;
    265 
    266     public:
     261    public:
     262
     263      typedef Item Parent;
    267264
    268265      typedef typename Map::Value Value;
     
    293290
    294291    class ItemIt : public Item {
    295       typedef Item Parent;
    296 
    297     public:
     292    public:
     293
     294      typedef Item Parent;
    298295
    299296      ItemIt() {}
     
    320317  private:
    321318
    322     const GraphType& graph;
     319    const Graph& graph;
    323320
    324321  };
  • lemon/bits/path_dump.h

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

    r663 r314  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030  struct InvalidType {};
    3131
    32   template <typename GR, typename _Item>
     32  template <typename _Graph, typename _Item>
    3333  class ItemSetTraits {};
    3434
    3535
    36   template <typename GR, typename Enable = void>
     36  template <typename Graph, typename Enable = void>
    3737  struct NodeNotifierIndicator {
    3838    typedef InvalidType Type;
    3939  };
    40   template <typename GR>
     40  template <typename Graph>
    4141  struct NodeNotifierIndicator<
    42     GR,
    43     typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
    44   > {
    45     typedef typename GR::NodeNotifier Type;
    46   };
    47 
    48   template <typename GR>
    49   class ItemSetTraits<GR, typename GR::Node> {
     42    Graph,
     43    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
     44  > {
     45    typedef typename Graph::NodeNotifier Type;
     46  };
     47
     48  template <typename _Graph>
     49  class ItemSetTraits<_Graph, typename _Graph::Node> {
    5050  public:
    5151
    52     typedef GR Graph;
    53     typedef GR Digraph;
    54 
    55     typedef typename GR::Node Item;
    56     typedef typename GR::NodeIt ItemIt;
    57 
    58     typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
    59 
    60     template <typename V>
    61     class Map : public GR::template NodeMap<V> {
    62       typedef typename GR::template NodeMap<V> Parent;
    63 
     52    typedef _Graph Graph;
     53
     54    typedef typename Graph::Node Item;
     55    typedef typename Graph::NodeIt ItemIt;
     56
     57    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
     58
     59    template <typename _Value>
     60    class Map : public Graph::template NodeMap<_Value> {
    6461    public:
    65       typedef typename GR::template NodeMap<V> Type;
     62      typedef typename Graph::template NodeMap<_Value> Parent;
     63      typedef typename Graph::template NodeMap<_Value> Type;
    6664      typedef typename Parent::Value Value;
    6765
    68       Map(const GR& _digraph) : Parent(_digraph) {}
    69       Map(const GR& _digraph, const Value& _value)
     66      Map(const Graph& _digraph) : Parent(_digraph) {}
     67      Map(const Graph& _digraph, const Value& _value)
    7068        : Parent(_digraph, _value) {}
    7169
     
    7472  };
    7573
    76   template <typename GR, typename Enable = void>
     74  template <typename Graph, typename Enable = void>
    7775  struct ArcNotifierIndicator {
    7876    typedef InvalidType Type;
    7977  };
    80   template <typename GR>
     78  template <typename Graph>
    8179  struct ArcNotifierIndicator<
    82     GR,
    83     typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
    84   > {
    85     typedef typename GR::ArcNotifier Type;
    86   };
    87 
    88   template <typename GR>
    89   class ItemSetTraits<GR, typename GR::Arc> {
     80    Graph,
     81    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
     82  > {
     83    typedef typename Graph::ArcNotifier Type;
     84  };
     85
     86  template <typename _Graph>
     87  class ItemSetTraits<_Graph, typename _Graph::Arc> {
    9088  public:
    9189
    92     typedef GR Graph;
    93     typedef GR Digraph;
    94 
    95     typedef typename GR::Arc Item;
    96     typedef typename GR::ArcIt ItemIt;
    97 
    98     typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
    99 
    100     template <typename V>
    101     class Map : public GR::template ArcMap<V> {
    102       typedef typename GR::template ArcMap<V> Parent;
    103 
     90    typedef _Graph Graph;
     91
     92    typedef typename Graph::Arc Item;
     93    typedef typename Graph::ArcIt ItemIt;
     94
     95    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
     96
     97    template <typename _Value>
     98    class Map : public Graph::template ArcMap<_Value> {
    10499    public:
    105       typedef typename GR::template ArcMap<V> Type;
     100      typedef typename Graph::template ArcMap<_Value> Parent;
     101      typedef typename Graph::template ArcMap<_Value> Type;
    106102      typedef typename Parent::Value Value;
    107103
    108       Map(const GR& _digraph) : Parent(_digraph) {}
    109       Map(const GR& _digraph, const Value& _value)
     104      Map(const Graph& _digraph) : Parent(_digraph) {}
     105      Map(const Graph& _digraph, const Value& _value)
    110106        : Parent(_digraph, _value) {}
    111107    };
     
    113109  };
    114110
    115   template <typename GR, typename Enable = void>
     111  template <typename Graph, typename Enable = void>
    116112  struct EdgeNotifierIndicator {
    117113    typedef InvalidType Type;
    118114  };
    119   template <typename GR>
     115  template <typename Graph>
    120116  struct EdgeNotifierIndicator<
    121     GR,
    122     typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
    123   > {
    124     typedef typename GR::EdgeNotifier Type;
    125   };
    126 
    127   template <typename GR>
    128   class ItemSetTraits<GR, typename GR::Edge> {
     117    Graph,
     118    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
     119  > {
     120    typedef typename Graph::EdgeNotifier Type;
     121  };
     122
     123  template <typename _Graph>
     124  class ItemSetTraits<_Graph, typename _Graph::Edge> {
    129125  public:
    130126
    131     typedef GR Graph;
    132     typedef GR Digraph;
    133 
    134     typedef typename GR::Edge Item;
    135     typedef typename GR::EdgeIt ItemIt;
    136 
    137     typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
    138 
    139     template <typename V>
    140     class Map : public GR::template EdgeMap<V> {
    141       typedef typename GR::template EdgeMap<V> Parent;
    142 
     127    typedef _Graph Graph;
     128
     129    typedef typename Graph::Edge Item;
     130    typedef typename Graph::EdgeIt ItemIt;
     131
     132    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
     133
     134    template <typename _Value>
     135    class Map : public Graph::template EdgeMap<_Value> {
    143136    public:
    144       typedef typename GR::template EdgeMap<V> Type;
     137      typedef typename Graph::template EdgeMap<_Value> Parent;
     138      typedef typename Graph::template EdgeMap<_Value> Type;
    145139      typedef typename Parent::Value Value;
    146140
    147       Map(const GR& _digraph) : Parent(_digraph) {}
    148       Map(const GR& _digraph, const Value& _value)
     141      Map(const Graph& _digraph) : Parent(_digraph) {}
     142      Map(const Graph& _digraph, const Value& _value)
    149143        : Parent(_digraph, _value) {}
    150144    };
     
    211205  // Indicators for the tags
    212206
    213   template <typename GR, typename Enable = void>
     207  template <typename Graph, typename Enable = void>
    214208  struct NodeNumTagIndicator {
    215209    static const bool value = false;
    216210  };
    217211
    218   template <typename GR>
     212  template <typename Graph>
    219213  struct NodeNumTagIndicator<
    220     GR,
    221     typename enable_if<typename GR::NodeNumTag, void>::type
    222   > {
    223     static const bool value = true;
    224   };
    225 
    226   template <typename GR, typename Enable = void>
    227   struct ArcNumTagIndicator {
    228     static const bool value = false;
    229   };
    230 
    231   template <typename GR>
    232   struct ArcNumTagIndicator<
    233     GR,
    234     typename enable_if<typename GR::ArcNumTag, void>::type
    235   > {
    236     static const bool value = true;
    237   };
    238 
    239   template <typename GR, typename Enable = void>
     214    Graph,
     215    typename enable_if<typename Graph::NodeNumTag, void>::type
     216  > {
     217    static const bool value = true;
     218  };
     219
     220  template <typename Graph, typename Enable = void>
    240221  struct EdgeNumTagIndicator {
    241222    static const bool value = false;
    242223  };
    243224
    244   template <typename GR>
     225  template <typename Graph>
    245226  struct EdgeNumTagIndicator<
    246     GR,
    247     typename enable_if<typename GR::EdgeNumTag, void>::type
    248   > {
    249     static const bool value = true;
    250   };
    251 
    252   template <typename GR, typename Enable = void>
    253   struct FindArcTagIndicator {
    254     static const bool value = false;
    255   };
    256 
    257   template <typename GR>
    258   struct FindArcTagIndicator<
    259     GR,
    260     typename enable_if<typename GR::FindArcTag, void>::type
    261   > {
    262     static const bool value = true;
    263   };
    264 
    265   template <typename GR, typename Enable = void>
     227    Graph,
     228    typename enable_if<typename Graph::EdgeNumTag, void>::type
     229  > {
     230    static const bool value = true;
     231  };
     232
     233  template <typename Graph, typename Enable = void>
    266234  struct FindEdgeTagIndicator {
    267235    static const bool value = false;
    268236  };
    269237
    270   template <typename GR>
     238  template <typename Graph>
    271239  struct FindEdgeTagIndicator<
    272     GR,
    273     typename enable_if<typename GR::FindEdgeTag, void>::type
    274   > {
    275     static const bool value = true;
    276   };
    277 
    278   template <typename GR, typename Enable = void>
     240    Graph,
     241    typename enable_if<typename Graph::FindEdgeTag, void>::type
     242  > {
     243    static const bool value = true;
     244  };
     245
     246  template <typename Graph, typename Enable = void>
    279247  struct UndirectedTagIndicator {
    280248    static const bool value = false;
    281249  };
    282250
    283   template <typename GR>
     251  template <typename Graph>
    284252  struct UndirectedTagIndicator<
    285     GR,
    286     typename enable_if<typename GR::UndirectedTag, void>::type
    287   > {
    288     static const bool value = true;
    289   };
    290 
    291   template <typename GR, typename Enable = void>
     253    Graph,
     254    typename enable_if<typename Graph::UndirectedTag, void>::type
     255  > {
     256    static const bool value = true;
     257  };
     258
     259  template <typename Graph, typename Enable = void>
    292260  struct BuildTagIndicator {
    293261    static const bool value = false;
    294262  };
    295263
    296   template <typename GR>
     264  template <typename Graph>
    297265  struct BuildTagIndicator<
    298     GR,
    299     typename enable_if<typename GR::BuildTag, void>::type
     266    Graph,
     267    typename enable_if<typename Graph::BuildTag, void>::type
    300268  > {
    301269    static const bool value = true;
  • lemon/bits/vector_map.h

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

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

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

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

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

    r627 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_DIGRAPH_H
    20 #define LEMON_CONCEPTS_DIGRAPH_H
     19#ifndef LEMON_CONCEPT_DIGRAPH_H
     20#define LEMON_CONCEPT_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
     
    422422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423423
    424       /// \brief Reference map of the nodes to type \c T.
    425       ///
    426       /// Reference map of the nodes to type \c T.
     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
    427428      template<class T>
    428       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
     429      class NodeMap : public ReadWriteMap< Node, T > {
    429430      public:
    430431
     
    436437      private:
    437438        ///Copy constructor
    438         NodeMap(const NodeMap& nm) :
    439           ReferenceMap<Node, T, T&, const T&>(nm) { }
     439        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    440440        ///Assignment operator
    441441        template <typename CMap>
     
    446446      };
    447447
    448       /// \brief Reference map of the arcs to type \c T.
     448      /// \brief Read write map of the arcs to type \c T.
    449449      ///
    450450      /// Reference map of the arcs to type \c T.
     451      /// \sa Reference
    451452      template<class T>
    452       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
     453      class ArcMap : public ReadWriteMap<Arc,T> {
    453454      public:
    454455
     
    459460      private:
    460461        ///Copy constructor
    461         ArcMap(const ArcMap& em) :
    462           ReferenceMap<Arc, T, T&, const T&>(em) { }
     462        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
    463463        ///Assignment operator
    464464        template <typename CMap>
     
    472472      struct Constraints {
    473473        void constraints() {
    474           checkConcept<BaseDigraphComponent, _Digraph>();
    475474          checkConcept<IterableDigraphComponent<>, _Digraph>();
    476475          checkConcept<IDableDigraphComponent<>, _Digraph>();
     
    486485
    487486
    488 #endif
     487#endif // LEMON_CONCEPT_DIGRAPH_H
  • lemon/concepts/graph.h

    r704 r263  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPTS_GRAPH_H
    24 #define LEMON_CONCEPTS_GRAPH_H
     23#ifndef LEMON_CONCEPT_GRAPH_H
     24#define LEMON_CONCEPT_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
     27#include <lemon/concepts/graph.h>
    2728#include <lemon/core.h>
    2829
     
    311312      /// The directed arc type. It can be converted to the
    312313      /// edge or it should be inherited from the undirected
    313       /// edge.
    314       class Arc {
     314      /// arc.
     315      class Arc : public Edge {
    315316      public:
    316317        /// Default constructor
     
    323324        /// Copy constructor.
    324325        ///
    325         Arc(const Arc&) { }
     326        Arc(const Arc& e) : Edge(e) { }
    326327        /// Initialize the iterator to be invalid.
    327328
     
    350351        bool operator<(Arc) const { return false; }
    351352
    352         /// Converison to Edge
    353         operator Edge() const { return Edge(); }
    354353      };
    355354      /// This iterator goes through each directed arc.
     
    500499      };
    501500
    502       /// \brief Reference map of the nodes to type \c T.
    503       ///
    504       /// Reference map of the nodes to type \c T.
     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
    505505      template<class T>
    506       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     506      class NodeMap : public ReadWriteMap< Node, T >
    507507      {
    508508      public:
     
    515515      private:
    516516        ///Copy constructor
    517         NodeMap(const NodeMap& nm) :
    518           ReferenceMap<Node, T, T&, const T&>(nm) { }
     517        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
    519518        ///Assignment operator
    520519        template <typename CMap>
     
    525524      };
    526525
    527       /// \brief Reference map of the arcs to type \c T.
    528       ///
    529       /// Reference map of the arcs to type \c T.
     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
    530530      template<class T>
    531       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     531      class ArcMap : public ReadWriteMap<Arc,T>
    532532      {
    533533      public:
     
    539539      private:
    540540        ///Copy constructor
    541         ArcMap(const ArcMap& em) :
    542           ReferenceMap<Arc, T, T&, const T&>(em) { }
     541        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
    543542        ///Assignment operator
    544543        template <typename CMap>
     
    549548      };
    550549
    551       /// Reference map of the edges to type \c T.
    552 
    553       /// Reference map of the edges to type \c T.
     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
    554554      template<class T>
    555       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     555      class EdgeMap : public ReadWriteMap<Edge,T>
    556556      {
    557557      public:
     
    563563      private:
    564564        ///Copy constructor
    565         EdgeMap(const EdgeMap& em) :
    566           ReferenceMap<Edge, T, T&, const T&>(em) {}
     565        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
    567566        ///Assignment operator
    568567        template <typename CMap>
     
    604603      /// \brief Opposite node on an arc
    605604      ///
    606       /// \return The opposite of the given node on the given edge.
     605      /// \return the opposite of the given Node on the given Edge
    607606      Node oppositeNode(Node, Edge) const { return INVALID; }
    608607
    609608      /// \brief First node of the edge.
    610609      ///
    611       /// \return The first node of the given edge.
     610      /// \return the first node of the given Edge.
    612611      ///
    613612      /// Naturally edges don't have direction and thus
    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
     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
    617616      /// edge, and is used to define the "default" direction
    618617      /// of the directed versions of the arcs.
    619       /// \sa v()
    620       /// \sa direction()
     618      /// \sa direction
    621619      Node u(Edge) const { return INVALID; }
    622620
    623621      /// \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()
    635622      Node v(Edge) const { return INVALID; }
    636623
     
    751738      struct Constraints {
    752739        void constraints() {
    753           checkConcept<BaseGraphComponent, _Graph>();
    754740          checkConcept<IterableGraphComponent<>, _Graph>();
    755741          checkConcept<IDableGraphComponent<>, _Graph>();
  • lemon/concepts/graph_components.h

    r713 r313  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of graph components.
    2222
    23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    24 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     23
     24#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
     25#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
    2526
    2627#include <lemon/core.h>
     
    3233  namespace concepts {
    3334
    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.
     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.
    3839    ///
    3940    /// \note This class is a template class so that we can use it to
    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'.
     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
    4446#ifndef DOXYGEN
    45     template <char sel = '0'>
     47    template <char _selector = '0'>
    4648#endif
    4749    class GraphItem {
     
    4951      /// \brief Default constructor.
    5052      ///
    51       /// Default constructor.
    5253      /// \warning The default constructor is not required to set
    5354      /// the item to some well-defined value. So you should consider it
    5455      /// as uninitialized.
    5556      GraphItem() {}
    56 
    5757      /// \brief Copy constructor.
    5858      ///
    5959      /// Copy constructor.
     60      ///
    6061      GraphItem(const GraphItem &) {}
    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.
     62      /// \brief Invalid constructor \& conversion.
     63      ///
     64      /// This constructor initializes the item to be invalid.
    6665      /// \sa Invalid for more details.
    6766      GraphItem(Invalid) {}
    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 
     67      /// \brief Assign operator for nodes.
     68      ///
     69      /// The nodes are assignable.
     70      ///
     71      GraphItem& operator=(GraphItem const&) { return *this; }
    7972      /// \brief Equality operator.
    8073      ///
    81       /// Equality operator.
    82       bool operator==(const GraphItem&) const { return false; }
    83 
     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; }
    8477      /// \brief Inequality operator.
    8578      ///
    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).
     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.
    9487      ///
    9588      /// \note This operator only have to define some strict ordering of
    9689      /// the items; this order has nothing to do with the iteration
    9790      /// ordering of the items.
    98       bool operator<(const GraphItem&) const { return false; }
     91      bool operator<(GraphItem) const { return false; }
    9992
    10093      template<typename _GraphItem>
     
    10295        void constraints() {
    10396          _GraphItem i1;
    104           i1=INVALID;
    10597          _GraphItem i2 = i1;
    10698          _GraphItem i3 = INVALID;
     
    109101
    110102          bool b;
     103          //          b = (ia == ib) && (ia != ib) && (ia < ib);
    111104          b = (ia == ib) && (ia != ib);
    112105          b = (ia == INVALID) && (ib != INVALID);
     
    119112    };
    120113
    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.
     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.
    127121    class BaseDigraphComponent {
    128122    public:
     
    132126      /// \brief Node class of the digraph.
    133127      ///
    134       /// This class represents the nodes of the digraph.
     128      /// This class represents the Nodes of the digraph.
     129      ///
    135130      typedef GraphItem<'n'> Node;
    136131
    137132      /// \brief Arc class of the digraph.
    138133      ///
    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.
     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.
    155153      Node oppositeNode(const Node&, const Arc&) const {
    156154        return INVALID;
     
    178176    };
    179177
    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.
     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.
    187187    class BaseGraphComponent : public BaseDigraphComponent {
    188188    public:
    189 
    190       typedef BaseGraphComponent Graph;
    191 
    192189      typedef BaseDigraphComponent::Node Node;
    193190      typedef BaseDigraphComponent::Arc Arc;
    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 
     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'> {
    203199      public:
     200        typedef GraphItem<'u'> Parent;
    204201        /// \brief Default constructor.
    205202        ///
    206         /// Default constructor.
    207203        /// \warning The default constructor is not required to set
    208204        /// the item to some well-defined value. So you should consider it
    209205        /// as uninitialized.
    210206        Edge() {}
    211 
    212207        /// \brief Copy constructor.
    213208        ///
    214209        /// Copy constructor.
     210        ///
    215211        Edge(const Edge &) : Parent() {}
    216 
    217         /// \brief Constructor for conversion from \c INVALID.
    218         ///
    219         /// Constructor for conversion from \c INVALID.
    220         /// It initializes the item to be invalid.
     212        /// \brief Invalid constructor \& conversion.
     213        ///
     214        /// This constructor initializes the item to be invalid.
    221215        /// \sa Invalid for more details.
    222216        Edge(Invalid) {}
    223 
    224         /// \brief Constructor for conversion from an arc.
    225         ///
    226         /// Constructor for conversion from an arc.
     217        /// \brief Converter from arc to edge.
     218        ///
    227219        /// Besides the core graph item functionality each arc should
    228220        /// be convertible to the represented edge.
    229221        Edge(const 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.
     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.
    255230      ///
    256231      /// Returns the direction of the arc. Each arc represents an
     
    259234      bool direction(const Arc&) const { return true; }
    260235
    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; }
     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;}
    266263
    267264      template <typename _Graph>
     
    273270        void constraints() {
    274271          checkConcept<BaseDigraphComponent, _Graph>();
    275           checkConcept<GraphItem<'e'>, Edge>();
     272          checkConcept<GraphItem<'u'>, Edge>();
    276273          {
    277274            Node n;
     
    281278            n = graph.v(ue);
    282279            e = graph.direct(ue, true);
    283             e = graph.direct(ue, false);
    284280            e = graph.direct(ue, n);
    285281            e = graph.oppositeArc(e);
     
    295291    };
    296292
    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;
     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;
    308304      typedef typename Base::Node Node;
    309305      typedef typename Base::Arc Arc;
    310306
    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; }
     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;}
    348346
    349347      template <typename _Digraph>
     
    353351          checkConcept<Base, _Digraph >();
    354352          typename _Digraph::Node node;
    355           node=INVALID;
    356353          int nid = digraph.id(node);
    357354          nid = digraph.id(node);
    358355          node = digraph.nodeFromId(nid);
    359356          typename _Digraph::Arc arc;
    360           arc=INVALID;
    361357          int eid = digraph.id(arc);
    362358          eid = digraph.id(arc);
     
    373369    };
    374370
    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;
     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;
    387382      typedef typename Base::Edge Edge;
    388383
    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; }
     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;}
    409405
    410406      template <typename _Graph>
     
    412408
    413409        void constraints() {
     410          checkConcept<Base, _Graph >();
    414411          checkConcept<IDableDigraphComponent<Base>, _Graph >();
    415412          typename _Graph::Edge edge;
     
    425422    };
    426423
    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 {
     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 {
    433430    public:
    434431      /// \brief Default constructor.
    435432      ///
    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.
     433      /// @warning The default constructor sets the iterator
     434      /// to an undefined value.
    440435      GraphItemIt() {}
    441 
    442436      /// \brief Copy constructor.
    443437      ///
    444438      /// Copy constructor.
    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.
     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.
    456449      /// \sa Invalid for more details.
    457450      GraphItemIt(Invalid) {}
    458 
    459       /// \brief Assignment operator.
    460       ///
    461       /// Assignment operator for the iterator.
     451      /// \brief Assign operator for items.
     452      ///
     453      /// The items are assignable.
     454      ///
    462455      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
    463 
    464       /// \brief Increment the iterator.
    465       ///
    466       /// This operator increments the iterator, i.e. assigns it to the
    467       /// next item.
     456      /// \brief Next item.
     457      ///
     458      /// Assign the iterator to the next item.
     459      ///
    468460      GraphItemIt& operator++() { return *this; }
    469  
    470461      /// \brief Equality operator
    471462      ///
    472       /// Equality operator.
    473463      /// Two iterators are equal if and only if they point to the
    474464      /// same object or both are invalid.
    475465      bool operator==(const GraphItemIt&) const { return true;}
    476 
    477466      /// \brief Inequality operator
    478467      ///
    479       /// Inequality operator.
    480       /// Two iterators are equal if and only if they point to the
    481       /// same object or both are invalid.
     468      /// \sa operator==(Node n)
     469      ///
    482470      bool operator!=(const GraphItemIt&) const { return true;}
    483471
     
    485473      struct Constraints {
    486474        void constraints() {
    487           checkConcept<GraphItem<>, _GraphItemIt>();
    488475          _GraphItemIt it1(g);
    489476          _GraphItemIt it2;
    490           _GraphItemIt it3 = it1;
    491           _GraphItemIt it4 = INVALID;
    492477
    493478          it2 = ++it1;
     
    495480          ++(++it1);
    496481
    497           Item bi = it1;
     482          _Item bi = it1;
    498483          bi = it2;
    499484        }
    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 {
     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 {
    519500    public:
    520501      /// \brief Default constructor.
    521502      ///
    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.
     503      /// @warning The default constructor sets the iterator
     504      /// to an undefined value.
    526505      GraphIncIt() {}
    527 
    528506      /// \brief Copy constructor.
    529507      ///
    530508      /// Copy constructor.
    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.
     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.
    544521      /// \sa Invalid for more details.
    545522      GraphIncIt(Invalid) {}
    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.
     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      ///
    556532      GraphIncIt& operator++() { return *this; }
    557533
    558534      /// \brief Equality operator
    559535      ///
    560       /// Equality operator.
    561536      /// Two iterators are equal if and only if they point to the
    562537      /// same object or both are invalid.
     
    565540      /// \brief Inequality operator
    566541      ///
    567       /// Inequality operator.
    568       /// Two iterators are equal if and only if they point to the
    569       /// same object or both are invalid.
     542      /// \sa operator==(Node n)
     543      ///
    570544      bool operator!=(const GraphIncIt&) const { return true;}
    571545
     
    573547      struct Constraints {
    574548        void constraints() {
    575           checkConcept<GraphItem<sel>, _GraphIncIt>();
     549          checkConcept<GraphItem<_selector>, _GraphIncIt>();
    576550          _GraphIncIt it1(graph, node);
    577551          _GraphIncIt it2;
    578           _GraphIncIt it3 = it1;
    579           _GraphIncIt it4 = INVALID;
    580552
    581553          it2 = ++it1;
    582554          ++it2 = it1;
    583555          ++(++it1);
    584           Item e = it1;
     556          _Item e = it1;
    585557          e = it2;
    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.
     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.
    597573    /// This concept is part of the Digraph concept.
    598     template <typename BAS = BaseDigraphComponent>
    599     class IterableDigraphComponent : public BAS {
    600 
    601     public:
    602 
    603       typedef BAS Base;
     574    template <typename _Base = BaseDigraphComponent>
     575    class IterableDigraphComponent : public _Base {
     576
     577    public:
     578
     579      typedef _Base Base;
    604580      typedef typename Base::Node Node;
    605581      typedef typename Base::Arc Arc;
     
    607583      typedef IterableDigraphComponent Digraph;
    608584
    609       /// \name Base Iteration
    610       ///
    611       /// This interface provides functions for iteration on digraph items.
     585      /// \name Base iteration
     586      ///
     587      /// This interface provides functions for iteration on digraph items
    612588      ///
    613589      /// @{
    614590
    615       /// \brief Return the first node.
    616       ///
    617       /// This function gives back the first node in the iteration order.
     591      /// \brief Gives back the first node in the iterating order.
     592      ///
     593      /// Gives back the first node in the iterating order.
     594      ///
    618595      void first(Node&) const {}
    619596
    620       /// \brief Return the next node.
    621       ///
    622       /// This function gives back the next node in the iteration order.
     597      /// \brief Gives back the next node in the iterating order.
     598      ///
     599      /// Gives back the next node in the iterating order.
     600      ///
    623601      void next(Node&) const {}
    624602
    625       /// \brief Return the first arc.
    626       ///
    627       /// This function gives back the first arc in the iteration order.
     603      /// \brief Gives back the first arc in the iterating order.
     604      ///
     605      /// Gives back the first arc in the iterating order.
     606      ///
    628607      void first(Arc&) const {}
    629608
    630       /// \brief Return the next arc.
    631       ///
    632       /// This function gives back the next arc in the iteration order.
     609      /// \brief Gives back the next arc in the iterating order.
     610      ///
     611      /// Gives back the next arc in the iterating order.
     612      ///
    633613      void next(Arc&) const {}
    634614
    635       /// \brief Return the first arc incomming to the given node.
    636       ///
    637       /// This function gives back the first arc incomming to the
     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      ///
     621      void firstIn(Arc&, const Node&) const {}
     622
     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      ///
     628      void nextIn(Arc&) const {}
     629
     630      /// \brief Gives back the first of the arcs start from the
    638631      /// given node.
    639       void firstIn(Arc&, const Node&) const {}
    640 
    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.
    645       void nextIn(Arc&) const {}
    646 
    647       /// \brief Return the first arc outgoing form the given node.
    648       ///
    649       /// This function gives back the first arc outgoing form the
    650       /// given node.
     632      ///
     633      /// Gives back the first of the arcs start from the given node.
     634      ///
    651635      void firstOut(Arc&, const Node&) const {}
    652636
    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.
     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      ///
    657642      void nextOut(Arc&) const {}
    658643
    659644      /// @}
    660645
    661       /// \name Class Based Iteration
    662       ///
    663       /// This interface provides iterator classes for digraph items.
     646      /// \name Class based iteration
     647      ///
     648      /// This interface provides functions for iteration on digraph items
    664649      ///
    665650      /// @{
     
    671656      typedef GraphItemIt<Digraph, Node> NodeIt;
    672657
    673       /// \brief This iterator goes through each arc.
    674       ///
    675       /// This iterator goes through each arc.
     658      /// \brief This iterator goes through each node.
     659      ///
     660      /// This iterator goes through each node.
    676661      ///
    677662      typedef GraphItemIt<Digraph, Arc> ArcIt;
     
    679664      /// \brief This iterator goes trough the incoming arcs of a node.
    680665      ///
    681       /// This iterator goes trough the \e incoming arcs of a certain node
     666      /// This iterator goes trough the \e inccoming arcs of a certain node
    682667      /// of a digraph.
    683668      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
     
    691676      /// \brief The base node of the iterator.
    692677      ///
    693       /// This function gives back the base node of the iterator.
    694       /// It is always the target node of the pointed arc.
     678      /// Gives back the base node of the iterator.
     679      /// It is always the target of the pointed arc.
    695680      Node baseNode(const InArcIt&) const { return INVALID; }
    696681
    697682      /// \brief The running node of the iterator.
    698683      ///
    699       /// This function gives back the running node of the iterator.
    700       /// It is always the source node of the pointed arc.
     684      /// Gives back the running node of the iterator.
     685      /// It is always the source of the pointed arc.
    701686      Node runningNode(const InArcIt&) const { return INVALID; }
    702687
    703688      /// \brief The base node of the iterator.
    704689      ///
    705       /// This function gives back the base node of the iterator.
    706       /// It is always the source node of the pointed arc.
     690      /// Gives back the base node of the iterator.
     691      /// It is always the source of the pointed arc.
    707692      Node baseNode(const OutArcIt&) const { return INVALID; }
    708693
    709694      /// \brief The running node of the iterator.
    710695      ///
    711       /// This function gives back the running node of the iterator.
    712       /// It is always the target node of the pointed arc.
     696      /// Gives back the running node of the iterator.
     697      /// It is always the target of the pointed arc.
    713698      Node runningNode(const OutArcIt&) const { return INVALID; }
    714699
     
    752737
    753738            typename _Digraph::Node n;
    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);
     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);
    760745            ignore_unused_variable_warning(n);
    761746          }
     
    763748
    764749        const _Digraph& digraph;
    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.
     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.
    773758    /// This concept is part of the Graph concept.
    774     template <typename BAS = BaseGraphComponent>
    775     class IterableGraphComponent : public IterableDigraphComponent<BAS> {
    776     public:
    777 
    778       typedef BAS Base;
     759    template <typename _Base = BaseGraphComponent>
     760    class IterableGraphComponent : public IterableDigraphComponent<_Base> {
     761    public:
     762
     763      typedef _Base Base;
    779764      typedef typename Base::Node Node;
    780765      typedef typename Base::Arc Arc;
     
    784769      typedef IterableGraphComponent Graph;
    785770
    786       /// \name Base Iteration
    787       ///
    788       /// This interface provides functions for iteration on edges.
    789       ///
     771      /// \name Base iteration
     772      ///
     773      /// This interface provides functions for iteration on graph items
    790774      /// @{
    791775
    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.
     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      ///
    798784      void first(Edge&) const {}
    799785
    800       /// \brief Return the next edge.
    801       ///
    802       /// This function gives back the next edge in the iteration order.
     786      /// \brief Gives back the next edge in the iterating
     787      /// order.
     788      ///
     789      /// Gives back the next edge in the iterating order.
     790      ///
    803791      void next(Edge&) const {}
    804792
    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
     793
     794      /// \brief Gives back the first of the edges from the
    810795      /// 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.
    811801      void firstInc(Edge&, bool&, const Node&) const {}
    812802
     
    814804      /// given node.
    815805      ///
    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.
     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.
    818809      void nextInc(Edge&, bool&) const {}
    819810
    820       using IterableDigraphComponent<Base>::baseNode;
    821       using IterableDigraphComponent<Base>::runningNode;
     811      using IterableDigraphComponent<_Base>::baseNode;
     812      using IterableDigraphComponent<_Base>::runningNode;
    822813
    823814      /// @}
    824815
    825       /// \name Class Based Iteration
    826       ///
    827       /// This interface provides iterator classes for edges.
     816      /// \name Class based iteration
     817      ///
     818      /// This interface provides functions for iteration on graph items
    828819      ///
    829820      /// @{
    830821
    831       /// \brief This iterator goes through each edge.
    832       ///
    833       /// This iterator goes through each edge.
     822      /// \brief This iterator goes through each node.
     823      ///
     824      /// This iterator goes through each node.
    834825      typedef GraphItemIt<Graph, Edge> EdgeIt;
    835 
    836       /// \brief This iterator goes trough the incident edges of a
     826      /// \brief This iterator goes trough the incident arcs of a
    837827      /// node.
    838828      ///
    839       /// This iterator goes trough the incident edges of a certain
     829      /// This iterator goes trough the incident arcs of a certain
    840830      /// node of a graph.
    841       typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
    842 
     831      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
    843832      /// \brief The base node of the iterator.
    844833      ///
    845       /// This function gives back the base node of the iterator.
     834      /// Gives back the base node of the iterator.
    846835      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    847836
    848837      /// \brief The running node of the iterator.
    849838      ///
    850       /// This function gives back the running node of the iterator.
     839      /// Gives back the running node of the iterator.
    851840      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    852841
     
    877866              typename _Graph::EdgeIt >();
    878867            checkConcept<GraphIncIt<_Graph, typena