COIN-OR::LEMON - Graph Library

Ignore:
Files:
55 added
103 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r514 r564  
    2828.deps/*
    2929demo/*.eps
     30m4/libtool.m4
     31m4/ltoptions.m4
     32m4/ltsugar.m4
     33m4/ltversion.m4
     34m4/lt~obsolete.m4
    3035
    3136syntax: regexp
     
    3641^autom4te.cache/.*
    3742^build-aux/.*
    38 ^objs.*/.*
     43^.*objs.*/.*
    3944^test/[a-z_]*$
     45^tools/[a-z-_]*$
    4046^demo/.*_demo$
    41 ^build/.*
     47^.*build.*/.*
    4248^doc/gen-images/.*
    4349CMakeFiles
  • CMakeLists.txt

    r520 r599  
    1010PROJECT(${PROJECT_NAME})
    1111
    12 SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     12SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
    1313
    1414INCLUDE(FindDoxygen)
    1515INCLUDE(FindGhostscript)
     16FIND_PACKAGE(GLPK 4.33)
     17
     18ADD_DEFINITIONS(-DHAVE_CONFIG_H)
     19
     20IF(MSVC)
     21  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
     22# Suppressed warnings:
     23# C4250: 'class1' : inherits 'class2::member' via dominance
     24# C4355: 'this' : used in base member initializer list
     25# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     26# C4996: 'function': was declared deprecated
     27ENDIF(MSVC)
     28
     29IF(GLPK_FOUND)
     30  SET(HAVE_LP TRUE)
     31  SET(HAVE_MIP TRUE)
     32  SET(HAVE_GLPK TRUE)
     33ENDIF(GLPK_FOUND)
    1634
    1735INCLUDE(CheckTypeSize)
     
    2139
    2240ADD_SUBDIRECTORY(lemon)
    23 ADD_SUBDIRECTORY(demo)
    24 ADD_SUBDIRECTORY(doc)
    25 ADD_SUBDIRECTORY(test)
     41IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     42  ADD_SUBDIRECTORY(demo)
     43  ADD_SUBDIRECTORY(tools)
     44  ADD_SUBDIRECTORY(doc)
     45  ADD_SUBDIRECTORY(test)
     46ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
    2647
    27 IF(WIN32)
    28   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
    29   SET(CPACK_PACKAGE_VENDOR "EGRES")
    30   SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
    31     "LEMON - Library of Efficient Models and Optimization in Networks")
    32   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
     48IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     49  IF(WIN32)
     50    SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     51    SET(CPACK_PACKAGE_VENDOR "EGRES")
     52    SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     53      "LEMON - Library of Efficient Models and Optimization in Networks")
     54    SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
    3355
    34   SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
     56    SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    3557
    36   SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    37     "${PROJECT_NAME} ${PROJECT_VERSION}")
    38   SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    39     "${PROJECT_NAME} ${PROJECT_VERSION}")
     58    SET(CPACK_PACKAGE_INSTALL_DIRECTORY
     59      "${PROJECT_NAME} ${PROJECT_VERSION}")
     60    SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
     61      "${PROJECT_NAME} ${PROJECT_VERSION}")
    4062
    41   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
     63    SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
    4264
    43   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
    44   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
    45   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
     65    SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
     66    SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
     67    SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
     68    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
    4669
    47   SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
    48     "C++ header files")
    49   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
    50     "DLL and import library")
    51   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
    52     "Doxygen generated documentation")
     70    SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
     71      "C++ header files")
     72    SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     73      "DLL and import library")
     74    SET(CPACK_COMPONENT_BIN_DESCRIPTION
     75      "Command line utilities")
     76    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     77      "Doxygen generated documentation")
    5378
    54   SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
     79    SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
    5580
    56   SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
    57   SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
    58   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
     81    SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
     82    SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
     83    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
    5984
    60   SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
    61     "Components needed to develop software using LEMON")
    62   SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
    63     "Documentation of LEMON")
     85    SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
     86      "Components needed to develop software using LEMON")
     87    SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
     88      "Documentation of LEMON")
    6489
    65   SET(CPACK_ALL_INSTALL_TYPES Full Developer)
     90    SET(CPACK_ALL_INSTALL_TYPES Full Developer)
    6691
    67   SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
    68   SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
    69   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
     92    SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
     93    SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
     94    SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
    7095
    71   SET(CPACK_GENERATOR "NSIS")
    72   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
    73   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
    74   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
    75   SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
    76   SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
    77   SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
    78   SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
    79   SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
    80   SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
    81     CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
    82     ")
    83   SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
    84     !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
    85     Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
    86     ")
     96    SET(CPACK_GENERATOR "NSIS")
     97    SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
     98    SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
     99    #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
     100    SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
     101    SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
     102    SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
     103    SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
     104    SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
     105    SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
     106      CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\"
     107      ")
     108    SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
     109      !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
     110      Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
     111      ")
    87112
    88   INCLUDE(CPack)
    89 ENDIF(WIN32)
     113    INCLUDE(CPack)
     114  ENDIF(WIN32)
     115ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
  • LICENSE

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

    r503 r555  
    11ACLOCAL_AMFLAGS = -I m4
     2
     3AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    24
    35AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
     
    1214        CMakeLists.txt \
    1315        cmake/FindGhostscript.cmake \
     16        cmake/FindGLPK.cmake \
    1417        cmake/version.cmake.in \
    1518        cmake/version.cmake \
  • configure.ac

    r515 r564  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
    21 
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2321
    2422dnl Do compilation tests using the C++ compiler.
     
    5351
    5452dnl Set custom compiler flags when using g++.
    55 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    56   CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
     53if test "$GXX" = yes -a "$ICC" = no; then
     54  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"
    5755fi
     56AC_SUBST([WARNINGCXXFLAGS])
    5857
    5958dnl Checks for libraries.
    60 #LX_CHECK_GLPK
    61 #LX_CHECK_CPLEX
    62 #LX_CHECK_SOPLEX
     59LX_CHECK_GLPK
     60LX_CHECK_CPLEX
     61LX_CHECK_SOPLEX
     62LX_CHECK_CLP
     63
     64AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
     65AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
    6366
    6467dnl Disable/enable building the demo programs.
     
    121124echo
    122125echo C++ compiler.................. : $CXX
    123 echo C++ compiles flags............ : $CXXFLAGS
     126echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    124127echo
    125128echo Compiler supports long long... : $long_long_found
    126129echo
    127 #echo GLPK support.................. : $lx_glpk_found
    128 #echo CPLEX support................. : $lx_cplex_found
    129 #echo SOPLEX support................ : $lx_soplex_found
    130 #echo
     130echo GLPK support.................. : $lx_glpk_found
     131echo CPLEX support................. : $lx_cplex_found
     132echo SOPLEX support................ : $lx_soplex_found
     133echo CLP support................... : $lx_clp_found
     134echo
    131135echo Build demo programs........... : $enable_demo
    132136echo Build additional tools........ : $enable_tools
  • demo/CMakeLists.txt

    r225 r596  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     6LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    47
    58SET(DEMOS
  • demo/arg_parser_demo.cc

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

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

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

    r520 r596  
    11SET(PACKAGE_NAME ${PROJECT_NAME})
    22SET(PACKAGE_VERSION ${PROJECT_VERSION})
    3 SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
    4 SET(abs_top_builddir ${CMAKE_BINARY_DIR})
     3SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
     4SET(abs_top_builddir ${PROJECT_BINARY_DIR})
    55
    66CONFIGURE_FILE(
    7   ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
    8   ${CMAKE_BINARY_DIR}/doc/Doxyfile
     7  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
     8  ${PROJECT_BINARY_DIR}/doc/Doxyfile
    99  @ONLY)
    1010
     
    1515      COMMAND rm -rf gen-images
    1616      COMMAND mkdir gen-images
     17      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1718      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
    1819      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
  • doc/Doxyfile.in

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

    r317 r349  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \
  • doc/coding_style.dox

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

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

    r318 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2224*/
    2325
     
    6163
    6264/**
     65@defgroup graph_adaptors Adaptor Classes for Graphs
     66@ingroup graphs
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
     138*/
     139
     140/**
    63141@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64142@ingroup graphs
    65143\brief Graph types between real graphs and graph adaptors.
    66144
    67 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    68146These classes wrap graphs to give new functionality as the adaptors do it.
    69147On the other hand they are not light-weight structures as the adaptors.
     
    75153\brief Map structures implemented in LEMON.
    76154
    77 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    78156
    79157LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    88166\brief Special graph-related maps.
    89167
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     168This group contains maps that are specifically designed to assign
     169values to the nodes and arcs/edges of graphs.
     170
     171If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     172\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92173*/
    93174
     
    97178\brief Tools to create new maps from existing ones
    98179
    99 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    100181maps from other maps.
    101182
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     183Most of them are \ref concepts::ReadMap "read-only maps".
    103184They can make arithmetic and logical operations between one or two maps
    104185(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    160241\brief Two dimensional data storages implemented in LEMON.
    161242
    162 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    163244*/
    164245
     
    168249\brief %Path structures implemented in LEMON.
    169250
    170 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    171252
    172253LEMON provides flexible data structures to work with paths.
     
    184265\brief Auxiliary data structures implemented in LEMON.
    185266
    186 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    187268order to make it easier to implement combinatorial algorithms.
    188269*/
     
    190271/**
    191272@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    193274implemented in LEMON.
    194275
    195 This group describes the several algorithms
     276This group contains the several algorithms
    196277implemented in LEMON.
    197278*/
     
    202283\brief Common graph search algorithms.
    203284
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     285This group contains the common graph search algorithms, namely
     286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206287*/
    207288
     
    211292\brief Algorithms for finding shortest paths.
    212293
    213 This group describes the algorithms for finding shortest paths in graphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
     295
     296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     297   when all arc lengths are non-negative.
     298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     299   from a source node when arc lenghts can be either positive or negative,
     300   but the digraph should not contain directed cycles with negative total
     301   length.
     302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     303   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     304   lenghts can be either positive or negative, but the digraph should
     305   not contain directed cycles with negative total length.
     306 - \ref Suurballe A successive shortest path algorithm for finding
     307   arc-disjoint paths between two nodes having minimum total length.
    214308*/
    215309
     
    219313\brief Algorithms for finding maximum flows.
    220314
    221 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    222316feasible circulations.
    223317
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     318The \e maximum \e flow \e problem is to find a flow of maximum value between
     319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     320digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     321\f$s, t \in V\f$ source and target nodes.
     322A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     323following optimization problem.
     324
     325\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
     326\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
     327    \qquad \forall v\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
    234329
    235330LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
     331- \ref EdmondsKarp Edmonds-Karp algorithm.
     332- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     333- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     334- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     335
     336In most cases the \ref Preflow "Preflow" algorithm provides the
     337fastest method for computing a maximum flow. All implementations
     338provides functions to also query the minimum cut, which is the dual
     339problem of the maximum flow.
    245340*/
    246341
     
    251346\brief Algorithms for finding minimum cost flows and circulations.
    252347
    253 This group describes the algorithms for finding minimum cost flows and
     348This group contains the algorithms for finding minimum cost flows and
    254349circulations.
     350
     351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     352minimum total cost from a set of supply nodes to a set of demand nodes
     353in a network with capacity constraints and arc costs.
     354Formally, let \f$G=(V,A)\f$ be a digraph,
     355\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     356upper bounds for the flow values on the arcs,
     357\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     358on the arcs, and
     359\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     360of the nodes.
     361A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     362the following optimization problem.
     363
     364\f[ \min\sum_{a\in A} f(a) cost(a) \f]
     365\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
     366    supply(v) \qquad \forall v\in V \f]
     367\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
     368
     369LEMON contains several algorithms for solving minimum cost flow problems:
     370 - \ref CycleCanceling Cycle-canceling algorithms.
     371 - \ref CapacityScaling Successive shortest path algorithm with optional
     372   capacity scaling.
     373 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
     374   cost scaling.
     375 - \ref NetworkSimplex Primal network simplex algorithm with various
     376   pivot strategies.
    255377*/
    256378
     
    261383\brief Algorithms for finding minimum cut in graphs.
    262384
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     385This group contains the algorithms for finding minimum cut in graphs.
     386
     387The \e minimum \e cut \e problem is to find a non-empty and non-complete
     388\f$X\f$ subset of the nodes with minimum overall capacity on
     389outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     390\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269391cut is the \f$X\f$ solution of the next optimization problem:
    270392
    271393\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     394    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273395
    274396LEMON contains several algorithms related to minimum cut problems:
    275397
    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
     398- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     399  in directed graphs.
     400- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     401  calculating minimum cut in undirected graphs.
     402- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     403  all-pairs minimum cut in undirected graphs.
    282404
    283405If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
     406see the \ref max_flow "maximum flow problem".
    285407*/
    286408
     
    290412\brief Algorithms for discovering the graph properties
    291413
    292 This group describes the algorithms for discovering the graph properties
     414This group contains the algorithms for discovering the graph properties
    293415like connectivity, bipartiteness, euler property, simplicity etc.
    294416
     
    302424\brief Algorithms for planarity checking, embedding and drawing
    303425
    304 This group describes the algorithms for planarity checking,
     426This group contains the algorithms for planarity checking,
    305427embedding and drawing.
    306428
     
    321443graphs.  The matching problems in bipartite graphs are generally
    322444easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     445can be finding maximum cardinality, maximum weight or minimum cost
    324446matching. The search can be constrained to find perfect or
    325447maximum cardinality matching.
    326448
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
     449The matching algorithms implemented in LEMON:
     450- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     451  for calculating maximum cardinality matching in bipartite graphs.
     452- \ref PrBipartiteMatching Push-relabel algorithm
     453  for calculating maximum cardinality matching in bipartite graphs.
     454- \ref MaxWeightedBipartiteMatching
     455  Successive shortest path algorithm for calculating maximum weighted
     456  matching and maximum weighted bipartite matching in bipartite graphs.
     457- \ref MinCostMaxBipartiteMatching
     458  Successive shortest path algorithm for calculating minimum cost maximum
     459  matching in bipartite graphs.
     460- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     461  maximum cardinality matching in general graphs.
     462- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     463  maximum weighted matching in general graphs.
     464- \ref MaxWeightedPerfectMatching
     465  Edmond's blossom shrinking algorithm for calculating maximum weighted
     466  perfect matching in general graphs.
    347467
    348468\image html bipartite_matching.png
     
    355475\brief Algorithms for finding a minimum cost spanning tree in a graph.
    356476
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     477This group contains the algorithms for finding a minimum cost spanning
     478tree in a graph.
    359479*/
    360480
     
    364484\brief Auxiliary algorithms implemented in LEMON.
    365485
    366 This group describes some algorithms implemented in LEMON
     486This group contains some algorithms implemented in LEMON
    367487in order to make it easier to implement complex algorithms.
    368488*/
     
    373493\brief Approximation algorithms.
    374494
    375 This group describes the approximation and heuristic algorithms
     495This group contains the approximation and heuristic algorithms
    376496implemented in LEMON.
    377497*/
     
    379499/**
    380500@defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     501\brief This group contains some general optimization frameworks
    382502implemented in LEMON.
    383503
    384 This group describes some general optimization frameworks
     504This group contains some general optimization frameworks
    385505implemented in LEMON.
    386506*/
     
    391511\brief Lp and Mip solver interfaces for LEMON.
    392512
    393 This group describes Lp and Mip solver interfaces for LEMON. The
     513This group contains Lp and Mip solver interfaces for LEMON. The
    394514various LP solvers could be used in the same manner with this
    395515interface.
     
    410530\brief Metaheuristics for LEMON library.
    411531
    412 This group describes some metaheuristic optimization tools.
     532This group contains some metaheuristic optimization tools.
    413533*/
    414534
     
    425545\brief Simple basic graph utilities.
    426546
    427 This group describes some simple basic graph utilities.
     547This group contains some simple basic graph utilities.
    428548*/
    429549
     
    433553\brief Tools for development, debugging and testing.
    434554
    435 This group describes several useful tools for development,
     555This group contains several useful tools for development,
    436556debugging and testing.
    437557*/
     
    442562\brief Simple tools for measuring the performance of algorithms.
    443563
    444 This group describes simple tools for measuring the performance
     564This group contains simple tools for measuring the performance
    445565of algorithms.
    446566*/
     
    451571\brief Exceptions defined in LEMON.
    452572
    453 This group describes the exceptions defined in LEMON.
     573This group contains the exceptions defined in LEMON.
    454574*/
    455575
     
    458578\brief Graph Input-Output methods
    459579
    460 This group describes the tools for importing and exporting graphs
     580This group contains the tools for importing and exporting graphs
    461581and graph related data. Now it supports the \ref lgf-format
    462582"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    465585
    466586/**
    467 @defgroup lemon_io LEMON Input-Output
     587@defgroup lemon_io LEMON Graph Format
    468588@ingroup io_group
    469589\brief Reading and writing LEMON Graph Format.
    470590
    471 This group describes methods for reading and writing
     591This group contains methods for reading and writing
    472592\ref lgf-format "LEMON Graph Format".
    473593*/
     
    478598\brief General \c EPS drawer and graph exporter
    479599
    480 This group describes general \c EPS drawing methods and special
     600This group contains general \c EPS drawing methods and special
    481601graph exporting tools.
     602*/
     603
     604/**
     605@defgroup dimacs_group DIMACS format
     606@ingroup io_group
     607\brief Read and write files in DIMACS format
     608
     609Tools to read a digraph from or write it to a file in DIMACS format data.
     610*/
     611
     612/**
     613@defgroup nauty_group NAUTY Format
     614@ingroup io_group
     615\brief Read \e Nauty format
     616
     617Tool to read graphs from \e Nauty format data.
    482618*/
    483619
     
    486622\brief Skeleton classes and concept checking classes
    487623
    488 This group describes the data/algorithm skeletons and concept checking
     624This group contains the data/algorithm skeletons and concept checking
    489625classes implemented in LEMON.
    490626
     
    516652\brief Skeleton and concept checking classes for graph structures
    517653
    518 This group describes the skeletons and concept checking classes of LEMON's
     654This group contains the skeletons and concept checking classes of LEMON's
    519655graph structures and helper classes used to implement these.
    520656*/
     
    525661\brief Skeleton and concept checking classes for maps
    526662
    527 This group describes the skeletons and concept checking classes of maps.
     663This group contains the skeletons and concept checking classes of maps.
    528664*/
    529665
     
    531667\anchor demoprograms
    532668
    533 @defgroup demos Demo programs
     669@defgroup demos Demo Programs
    534670
    535671Some demo programs are listed here. Their full source codes can be found in
     
    541677
    542678/**
    543 @defgroup tools Standalone utility applications
     679@defgroup tools Standalone Utility Applications
    544680
    545681Some utility applications are listed here.
     
    549685*/
    550686
     687}
  • doc/lgf.dox

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

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

    r314 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4646"Quick Tour to LEMON" which will guide you along.
    4747
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
     48If you already feel like using our library, see the
     49<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    5450
    5551If you know what you are looking for then try to find it under the
    56 <a class="el" href="modules.html">Modules</a>
    57 section.
     52<a class="el" href="modules.html">Modules</a> section.
    5853
    5954If you are a user of the old (0.x) series of LEMON, please check out the
  • doc/migration.dox

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

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

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

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

    r511 r596  
    1 INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
     1INCLUDE_DIRECTORIES(
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
     4)
    25
    3 ADD_LIBRARY(lemon
     6CONFIGURE_FILE(
     7  ${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
     8  ${CMAKE_CURRENT_BINARY_DIR}/config.h
     9)
     10
     11SET(LEMON_SOURCES
    412  arg_parser.cc
    513  base.cc
    614  color.cc
     15  lp_base.cc
     16  lp_skeleton.cc
    717  random.cc
    818  bits/windows.cc
    919)
     20
     21IF(HAVE_GLPK)
     22  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     23  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     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(WIN32)
     29ENDIF(HAVE_GLPK)
     30
     31ADD_LIBRARY(lemon ${LEMON_SOURCES})
    1032
    1133INSTALL(
  • lemon/Makefile.am

    r511 r597  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    11         lemon/base.cc \
    12         lemon/color.cc \
     10        lemon/arg_parser.cc \
     11        lemon/base.cc \
     12        lemon/color.cc \
     13        lemon/lp_base.cc \
     14        lemon/lp_skeleton.cc \
    1315        lemon/random.cc \
    1416        lemon/bits/windows.cc
    1517
    16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     18
     19lemon_libemon_la_CXXFLAGS = \
     20        $(AM_CXXFLAGS) \
     21        $(GLPK_CFLAGS) \
     22        $(CPLEX_CFLAGS) \
     23        $(SOPLEX_CXXFLAGS) \
     24        $(CLP_CXXFLAGS)
     25
     26lemon_libemon_la_LDFLAGS = \
     27        $(GLPK_LIBS) \
     28        $(CPLEX_LIBS) \
     29        $(SOPLEX_LIBS) \
     30        $(CLP_LIBS)
     31
     32if HAVE_GLPK
     33lemon_libemon_la_SOURCES += lemon/glpk.cc
     34endif
     35
     36if HAVE_CPLEX
     37lemon_libemon_la_SOURCES += lemon/cplex.cc
     38endif
     39
     40if HAVE_SOPLEX
     41lemon_libemon_la_SOURCES += lemon/soplex.cc
     42endif
     43
     44if HAVE_CLP
     45lemon_libemon_la_SOURCES += lemon/clp.cc
     46endif
    1847
    1948lemon_HEADERS += \
    20         lemon/arg_parser.h \
     49        lemon/adaptors.h \
     50        lemon/arg_parser.h \
    2151        lemon/assert.h \
    22         lemon/bfs.h \
    23         lemon/bin_heap.h \
    24         lemon/color.h \
     52        lemon/bfs.h \
     53        lemon/bin_heap.h \
     54        lemon/circulation.h \
     55        lemon/clp.h \
     56        lemon/color.h \
    2557        lemon/concept_check.h \
    26         lemon/counter.h \
     58        lemon/connectivity.h \
     59        lemon/counter.h \
    2760        lemon/core.h \
    28         lemon/dfs.h \
    29         lemon/dijkstra.h \
    30         lemon/dim2.h \
     61        lemon/cplex.h \
     62        lemon/dfs.h \
     63        lemon/dijkstra.h \
     64        lemon/dim2.h \
     65        lemon/dimacs.h \
     66        lemon/edge_set.h \
     67        lemon/elevator.h \
    3168        lemon/error.h \
    32         lemon/graph_to_eps.h \
     69        lemon/euler.h \
     70        lemon/full_graph.h \
     71        lemon/glpk.h \
     72        lemon/gomory_hu.h \
     73        lemon/graph_to_eps.h \
     74        lemon/grid_graph.h \
     75        lemon/hypercube_graph.h \
    3376        lemon/kruskal.h \
     77        lemon/hao_orlin.h \
    3478        lemon/lgf_reader.h \
    3579        lemon/lgf_writer.h \
    3680        lemon/list_graph.h \
     81        lemon/lp.h \
     82        lemon/lp_base.h \
     83        lemon/lp_skeleton.h \
     84        lemon/list_graph.h \
    3785        lemon/maps.h \
    3886        lemon/math.h \
     87        lemon/max_matching.h \
     88        lemon/min_cost_arborescence.h \
     89        lemon/nauty_reader.h \
    3990        lemon/path.h \
    40         lemon/random.h \
     91        lemon/preflow.h \
     92        lemon/radix_sort.h \
     93        lemon/random.h \
    4194        lemon/smart_graph.h \
    42         lemon/time_measure.h \
    43         lemon/tolerance.h \
     95        lemon/soplex.h \
     96        lemon/suurballe.h \
     97        lemon/time_measure.h \
     98        lemon/tolerance.h \
    4499        lemon/unionfind.h \
    45100        lemon/bits/windows.h
     
    49104        lemon/bits/array_map.h \
    50105        lemon/bits/base_extender.h \
    51         lemon/bits/bezier.h \
     106        lemon/bits/bezier.h \
    52107        lemon/bits/default_map.h \
    53         lemon/bits/enable_if.h \
     108        lemon/bits/edge_set_extender.h \
     109        lemon/bits/enable_if.h \
     110        lemon/bits/graph_adaptor_extender.h \
    54111        lemon/bits/graph_extender.h \
    55112        lemon/bits/map_extender.h \
    56113        lemon/bits/path_dump.h \
     114        lemon/bits/solver_bits.h \
    57115        lemon/bits/traits.h \
     116        lemon/bits/variant.h \
    58117        lemon/bits/vector_map.h
    59118
  • lemon/arg_parser.cc

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

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

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

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

    r301 r525  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    127   ///See \ref BfsDefaultTraits for the documentation of
    128   ///a Bfs traits class.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    214208    typedef Bfs Create;
    215209
    216     ///\name Named template parameters
     210    ///\name Named Template Parameters
    217211
    218212    ///@{
     
    228222    };
    229223    ///\brief \ref named-templ-param "Named parameter" for setting
    230     ///PredMap type.
     224    ///\c PredMap type.
    231225    ///
    232226    ///\ref named-templ-param "Named parameter" for setting
    233     ///PredMap type.
     227    ///\c PredMap type.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    234229    template <class T>
    235230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    247242    };
    248243    ///\brief \ref named-templ-param "Named parameter" for setting
    249     ///DistMap type.
     244    ///\c DistMap type.
    250245    ///
    251246    ///\ref named-templ-param "Named parameter" for setting
    252     ///DistMap type.
     247    ///\c DistMap type.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    253249    template <class T>
    254250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266262    };
    267263    ///\brief \ref named-templ-param "Named parameter" for setting
    268     ///ReachedMap type.
     264    ///\c ReachedMap type.
    269265    ///
    270266    ///\ref named-templ-param "Named parameter" for setting
    271     ///ReachedMap type.
     267    ///\c ReachedMap type.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    272269    template <class T>
    273270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    285282    };
    286283    ///\brief \ref named-templ-param "Named parameter" for setting
    287     ///ProcessedMap type.
     284    ///\c ProcessedMap type.
    288285    ///
    289286    ///\ref named-templ-param "Named parameter" for setting
    290     ///ProcessedMap type.
     287    ///\c ProcessedMap type.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    291289    template <class T>
    292290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    303301    };
    304302    ///\brief \ref named-templ-param "Named parameter" for setting
    305     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    306304    ///
    307305    ///\ref named-templ-param "Named parameter" for setting
    308     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    309307    ///If you don't set it explicitly, it will be automatically allocated.
    310308    struct SetStandardProcessedMap :
     
    341339
    342340    ///Sets the map that stores the predecessor arcs.
    343     ///If you don't use this function before calling \ref run(),
    344     ///it will allocate one. The destructor deallocates this
    345     ///automatically allocated map, of course.
     341    ///If you don't use this function before calling \ref run(Node) "run()"
     342    ///or \ref init(), an instance will be allocated automatically.
     343    ///The destructor deallocates this automatically allocated map,
     344    ///of course.
    346345    ///\return <tt> (*this) </tt>
    347346    Bfs &predMap(PredMap &m)
     
    358357
    359358    ///Sets the map that indicates which nodes are reached.
    360     ///If you don't use this function before calling \ref run(),
    361     ///it will allocate one. The destructor deallocates this
    362     ///automatically allocated map, of course.
     359    ///If you don't use this function before calling \ref run(Node) "run()"
     360    ///or \ref init(), an instance will be allocated automatically.
     361    ///The destructor deallocates this automatically allocated map,
     362    ///of course.
    363363    ///\return <tt> (*this) </tt>
    364364    Bfs &reachedMap(ReachedMap &m)
     
    375375
    376376    ///Sets the map that indicates which nodes are processed.
    377     ///If you don't use this function before calling \ref run(),
    378     ///it will allocate one. The destructor deallocates this
    379     ///automatically allocated map, of course.
     377    ///If you don't use this function before calling \ref run(Node) "run()"
     378    ///or \ref init(), an instance will be allocated automatically.
     379    ///The destructor deallocates this automatically allocated map,
     380    ///of course.
    380381    ///\return <tt> (*this) </tt>
    381382    Bfs &processedMap(ProcessedMap &m)
     
    393394    ///Sets the map that stores the distances of the nodes calculated by
    394395    ///the algorithm.
    395     ///If you don't use this function before calling \ref run(),
    396     ///it will allocate one. The destructor deallocates this
    397     ///automatically allocated map, of course.
     396    ///If you don't use this function before calling \ref run(Node) "run()"
     397    ///or \ref init(), an instance will be allocated automatically.
     398    ///The destructor deallocates this automatically allocated map,
     399    ///of course.
    398400    ///\return <tt> (*this) </tt>
    399401    Bfs &distMap(DistMap &m)
     
    409411  public:
    410412
    411     ///\name Execution control
    412     ///The simplest way to execute the algorithm is to use
    413     ///one of the member functions called \ref lemon::Bfs::run() "run()".
    414     ///\n
    415     ///If you need more control on the execution, first you must call
    416     ///\ref lemon::Bfs::init() "init()", then you can add several source
    417     ///nodes with \ref lemon::Bfs::addSource() "addSource()".
    418     ///Finally \ref lemon::Bfs::start() "start()" will perform the
    419     ///actual path computation.
     413    ///\name Execution Control
     414    ///The simplest way to execute the BFS algorithm is to use one of the
     415    ///member functions called \ref run(Node) "run()".\n
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
     418    ///\ref addSource(). Finally the actual path computation can be
     419    ///performed with one of the \ref start() functions.
    420420
    421421    ///@{
    422422
     423    ///\brief Initializes the internal data structures.
     424    ///
    423425    ///Initializes the internal data structures.
    424 
    425     ///Initializes the internal data structures.
    426     ///
    427426    void init()
    428427    {
     
    558557    }
    559558
    560     ///\brief Returns \c false if there are nodes
    561     ///to be processed.
    562     ///
    563     ///Returns \c false if there are nodes
    564     ///to be processed in the queue.
     559    ///Returns \c false if there are nodes to be processed.
     560
     561    ///Returns \c false if there are nodes to be processed
     562    ///in the queue.
    565563    bool emptyQueue() const { return _queue_tail==_queue_head; }
    566564
    567565    ///Returns the number of the nodes to be processed.
    568566
    569     ///Returns the number of the nodes to be processed in the queue.
     567    ///Returns the number of the nodes to be processed
     568    ///in the queue.
    570569    int queueSize() const { return _queue_head-_queue_tail; }
    571570
     
    732731
    733732    ///\name Query Functions
    734     ///The result of the %BFS algorithm can be obtained using these
     733    ///The results of the BFS algorithm can be obtained using these
    735734    ///functions.\n
    736     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
    737     ///"start()" must be called before using them.
     735    ///Either \ref run(Node) "run()" or \ref start() should be called
     736    ///before using them.
    738737
    739738    ///@{
     
    743742    ///Returns the shortest path to a node.
    744743    ///
    745     ///\warning \c t should be reachable from the root(s).
    746     ///
    747     ///\pre Either \ref run() or \ref start() must be called before
    748     ///using this function.
     744    ///\warning \c t should be reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
     747    ///must be called before using this function.
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
     
    753752    ///Returns the distance of a node from the root(s).
    754753    ///
    755     ///\warning If node \c v is not reachable from the root(s), then
     754    ///\warning If node \c v is not reached from the root(s), then
    756755    ///the return value of this function is undefined.
    757756    ///
    758     ///\pre Either \ref run() or \ref start() must be called before
    759     ///using this function.
     757    ///\pre Either \ref run(Node) "run()" or \ref init()
     758    ///must be called before using this function.
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
     
    764763    ///This function returns the 'previous arc' of the shortest path
    765764    ///tree for the node \c v, i.e. it returns the last arc of a
    766     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    767     ///is not reachable from the root(s) or if \c v is a root.
     765    ///shortest path from a root to \c v. It is \c INVALID if \c v
     766    ///is not reached from the root(s) or if \c v is a root.
    768767    ///
    769768    ///The shortest path tree used here is equal to the shortest path
    770769    ///tree used in \ref predNode().
    771770    ///
    772     ///\pre Either \ref run() or \ref start() must be called before
    773     ///using this function.
     771    ///\pre Either \ref run(Node) "run()" or \ref init()
     772    ///must be called before using this function.
    774773    Arc predArc(Node v) const { return (*_pred)[v];}
    775774
     
    778777    ///This function returns the 'previous node' of the shortest path
    779778    ///tree for the node \c v, i.e. it returns the last but one node
    780     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    781     ///if \c v is not reachable from the root(s) or if \c v is a root.
     779    ///from a shortest path from a root to \c v. It is \c INVALID
     780    ///if \c v is not reached from the root(s) or if \c v is a root.
    782781    ///
    783782    ///The shortest path tree used here is equal to the shortest path
    784783    ///tree used in \ref predArc().
    785784    ///
    786     ///\pre Either \ref run() or \ref start() must be called before
    787     ///using this function.
     785    ///\pre Either \ref run(Node) "run()" or \ref init()
     786    ///must be called before using this function.
    788787    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    789788                                  G->source((*_pred)[v]); }
     
    795794    ///of the nodes calculated by the algorithm.
    796795    ///
    797     ///\pre Either \ref run() or \ref init()
     796    ///\pre Either \ref run(Node) "run()" or \ref init()
    798797    ///must be called before using this function.
    799798    const DistMap &distMap() const { return *_dist;}
     
    805804    ///arcs, which form the shortest path tree.
    806805    ///
    807     ///\pre Either \ref run() or \ref init()
     806    ///\pre Either \ref run(Node) "run()" or \ref init()
    808807    ///must be called before using this function.
    809808    const PredMap &predMap() const { return *_pred;}
    810809
    811     ///Checks if a node is reachable from the root(s).
    812 
    813     ///Returns \c true if \c v is reachable from the root(s).
    814     ///\pre Either \ref run() or \ref start()
     810    ///Checks if a node is reached from the root(s).
     811
     812    ///Returns \c true if \c v is reached from the root(s).
     813    ///
     814    ///\pre Either \ref run(Node) "run()" or \ref init()
    815815    ///must be called before using this function.
    816816    bool reached(Node v) const { return (*_reached)[v]; }
     
    958958  /// This auxiliary class is created to implement the
    959959  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
    960   /// It does not have own \ref run() method, it uses the functions
    961   /// and features of the plain \ref Bfs.
     960  /// It does not have own \ref run(Node) "run()" method, it uses the
     961  /// functions and features of the plain \ref Bfs.
    962962  ///
    963963  /// This class should only be used through the \ref bfs() function,
     
    11791179  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11801180  ///\endcode
    1181   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     1181  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
    11821182  ///to the end of the parameter list.
    11831183  ///\sa BfsWizard
     
    11951195  /// This class defines the interface of the BfsVisit events, and
    11961196  /// it could be the base of a real visitor class.
    1197   template <typename _Digraph>
     1197  template <typename GR>
    11981198  struct BfsVisitor {
    1199     typedef _Digraph Digraph;
     1199    typedef GR Digraph;
    12001200    typedef typename Digraph::Arc Arc;
    12011201    typedef typename Digraph::Node Node;
     
    12251225  };
    12261226#else
    1227   template <typename _Digraph>
     1227  template <typename GR>
    12281228  struct BfsVisitor {
    1229     typedef _Digraph Digraph;
     1229    typedef GR Digraph;
    12301230    typedef typename Digraph::Arc Arc;
    12311231    typedef typename Digraph::Node Node;
     
    12551255  ///
    12561256  /// Default traits class of BfsVisit class.
    1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1258   template<class _Digraph>
     1257  /// \tparam GR The type of the digraph the algorithm runs on.
     1258  template<class GR>
    12591259  struct BfsVisitDefaultTraits {
    12601260
    12611261    /// \brief The type of the digraph the algorithm runs on.
    1262     typedef _Digraph Digraph;
     1262    typedef GR Digraph;
    12631263
    12641264    /// \brief The type of the map that indicates which nodes are reached.
     
    12811281  /// \ingroup search
    12821282  ///
    1283   /// \brief %BFS algorithm class with visitor interface.
     1283  /// \brief BFS algorithm class with visitor interface.
    12841284  ///
    1285   /// This class provides an efficient implementation of the %BFS algorithm
     1285  /// This class provides an efficient implementation of the BFS algorithm
    12861286  /// with visitor interface.
    12871287  ///
    1288   /// The %BfsVisit class provides an alternative interface to the Bfs
     1288  /// The BfsVisit class provides an alternative interface to the Bfs
    12891289  /// class. It works with callback mechanism, the BfsVisit object calls
    12901290  /// the member functions of the \c Visitor class on every BFS event.
     
    12951295  /// instead.
    12961296  ///
    1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1298   /// The default value is
    1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
    1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
     1297  /// \tparam GR The type of the digraph the algorithm runs on.
     1298  /// The default type is \ref ListDigraph.
     1299  /// The value of GR is not used directly by \ref BfsVisit,
     1300  /// it is only passed to \ref BfsVisitDefaultTraits.
     1301  /// \tparam VS The Visitor type that is used by the algorithm.
     1302  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
    13031303  /// does not observe the BFS events. If you want to observe the BFS
    13041304  /// events, you should implement your own visitor class.
    1305   /// \tparam _Traits Traits class to set various data types used by the
     1305  /// \tparam TR Traits class to set various data types used by the
    13061306  /// algorithm. The default traits class is
    1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
     1307  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    13081308  /// See \ref BfsVisitDefaultTraits for the documentation of
    13091309  /// a BFS visit traits class.
    13101310#ifdef DOXYGEN
    1311   template <typename _Digraph, typename _Visitor, typename _Traits>
     1311  template <typename GR, typename VS, typename TR>
    13121312#else
    1313   template <typename _Digraph = ListDigraph,
    1314             typename _Visitor = BfsVisitor<_Digraph>,
    1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
     1313  template <typename GR = ListDigraph,
     1314            typename VS = BfsVisitor<GR>,
     1315            typename TR = BfsVisitDefaultTraits<GR> >
    13161316#endif
    13171317  class BfsVisit {
     
    13191319
    13201320    ///The traits class.
    1321     typedef _Traits Traits;
     1321    typedef TR Traits;
    13221322
    13231323    ///The type of the digraph the algorithm runs on.
     
    13251325
    13261326    ///The visitor type used by the algorithm.
    1327     typedef _Visitor Visitor;
     1327    typedef VS Visitor;
    13281328
    13291329    ///The type of the map that indicates which nodes are reached.
     
    13651365    typedef BfsVisit Create;
    13661366
    1367     /// \name Named template parameters
     1367    /// \name Named Template Parameters
    13681368
    13691369    ///@{
     
    14071407    ///
    14081408    /// Sets the map that indicates which nodes are reached.
    1409     /// If you don't use this function before calling \ref run(),
    1410     /// it will allocate one. The destructor deallocates this
    1411     /// automatically allocated map, of course.
     1409    /// If you don't use this function before calling \ref run(Node) "run()"
     1410    /// or \ref init(), an instance will be allocated automatically.
     1411    /// The destructor deallocates this automatically allocated map,
     1412    /// of course.
    14121413    /// \return <tt> (*this) </tt>
    14131414    BfsVisit &reachedMap(ReachedMap &m) {
     
    14221423  public:
    14231424
    1424     /// \name Execution control
    1425     /// The simplest way to execute the algorithm is to use
    1426     /// one of the member functions called \ref lemon::BfsVisit::run()
    1427     /// "run()".
    1428     /// \n
    1429     /// If you need more control on the execution, first you must call
    1430     /// \ref lemon::BfsVisit::init() "init()", then you can add several
    1431     /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
    1432     /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
    1433     /// actual path computation.
     1425    /// \name Execution Control
     1426    /// The simplest way to execute the BFS algorithm is to use one of the
     1427    /// member functions called \ref run(Node) "run()".\n
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
     1430    /// \ref addSource(). Finally the actual path computation can be
     1431    /// performed with one of the \ref start() functions.
    14341432
    14351433    /// @{
     
    17311729
    17321730    /// \name Query Functions
    1733     /// The result of the %BFS algorithm can be obtained using these
     1731    /// The results of the BFS algorithm can be obtained using these
    17341732    /// functions.\n
    1735     /// Either \ref lemon::BfsVisit::run() "run()" or
    1736     /// \ref lemon::BfsVisit::start() "start()" must be called before
    1737     /// using them.
     1733    /// Either \ref run(Node) "run()" or \ref start() should be called
     1734    /// before using them.
     1735
    17381736    ///@{
    17391737
    1740     /// \brief Checks if a node is reachable from the root(s).
    1741     ///
    1742     /// Returns \c true if \c v is reachable from the root(s).
    1743     /// \pre Either \ref run() or \ref start()
     1738    /// \brief Checks if a node is reached from the root(s).
     1739    ///
     1740    /// Returns \c true if \c v is reached from the root(s).
     1741    ///
     1742    /// \pre Either \ref run(Node) "run()" or \ref init()
    17441743    /// must be called before using this function.
    1745     bool reached(Node v) { return (*_reached)[v]; }
     1744    bool reached(Node v) const { return (*_reached)[v]; }
    17461745
    17471746    ///@}
  • lemon/bin_heap.h

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

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

    r314 r525  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure what
    40   // automatically updates the map when a key is added to or erased from
    41   // the map. This map uses the allocators to implement
    42   // the container functionality.
     39  // The ArrayMap template class is graph map structure that automatically
     40  // updates the map when a key is added to or erased from the graph.
     41  // This map uses the allocators to implement the container functionality.
    4342  //
    44   // The template parameters are the Graph the current Item type and
     43  // The template parameters are the Graph, the current Item type and
    4544  // the Value type of the map.
    4645  template <typename _Graph, typename _Item, typename _Value>
     
    4847    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4948  public:
    50     // The graph type of the maps.
     49    // The graph type.
    5150    typedef _Graph Graph;
    52     // The item type of the map.
     51    // The item type.
    5352    typedef _Item Item;
    5453    // The reference map tag.
    5554    typedef True ReferenceMapTag;
    5655
    57     // The key type of the maps.
     56    // The key type of the map.
    5857    typedef _Item Key;
    5958    // The value type of the map.
     
    137136    // \brief Template assign operator.
    138137    //
    139     // The given parameter should be conform to the ReadMap
     138    // The given parameter should conform to the ReadMap
    140139    // concecpt and could be indiced by the current item set of
    141140    // the NodeMap. In this case the value for each item
     
    201200    // \brief Adds a new key to the map.
    202201    //
    203     // It adds a new key to the map. It called by the observer notifier
     202    // It adds a new key to the map. It is called by the observer notifier
    204203    // and it overrides the add() member function of the observer base.
    205204    virtual void add(const Key& key) {
     
    229228    // \brief Adds more new keys to the map.
    230229    //
    231     // It adds more new keys to the map. It called by the observer notifier
     230    // It adds more new keys to the map. It is called by the observer notifier
    232231    // and it overrides the add() member function of the observer base.
    233232    virtual void add(const std::vector<Key>& keys) {
     
    273272    // \brief Erase a key from the map.
    274273    //
    275     // Erase a key from the map. It called by the observer notifier
     274    // Erase a key from the map. It is called by the observer notifier
    276275    // and it overrides the erase() member function of the observer base.
    277276    virtual void erase(const Key& key) {
     
    282281    // \brief Erase more keys from the map.
    283282    //
    284     // Erase more keys from the map. It called by the observer notifier
     283    // Erase more keys from the map. It is called by the observer notifier
    285284    // and it overrides the erase() member function of the observer base.
    286285    virtual void erase(const std::vector<Key>& keys) {
     
    291290    }
    292291
    293     // \brief Buildes the map.
    294     //
    295     // It buildes the map. It called by the observer notifier
     292    // \brief Builds the map.
     293    //
     294    // It builds the map. It is called by the observer notifier
    296295    // and it overrides the build() member function of the observer base.
    297296    virtual void build() {
     
    307306    // \brief Clear the map.
    308307    //
    309     // It erase all items from the map. It called by the observer notifier
     308    // It erase all items from the map. It is called by the observer notifier
    310309    // and it overrides the clear() member function of the observer base.
    311310    virtual void clear() {
  • lemon/bits/base_extender.h

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the digraph types
     33//\brief Extenders for the graph types
    3434namespace lemon {
    3535
  • lemon/bits/bezier.h

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

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

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

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the digraph types
     32//\brief Extenders for the graph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the Digraphs
     37  // \brief Extender for the digraph implementations
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
  • lemon/bits/map_extender.h

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

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

    r314 r463  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    219219
    220220  template <typename Graph, typename Enable = void>
     221  struct ArcNumTagIndicator {
     222    static const bool value = false;
     223  };
     224
     225  template <typename Graph>
     226  struct ArcNumTagIndicator<
     227    Graph,
     228    typename enable_if<typename Graph::ArcNumTag, void>::type
     229  > {
     230    static const bool value = true;
     231  };
     232
     233  template <typename Graph, typename Enable = void>
    221234  struct EdgeNumTagIndicator {
    222235    static const bool value = false;
     
    232245
    233246  template <typename Graph, typename Enable = void>
     247  struct FindArcTagIndicator {
     248    static const bool value = false;
     249  };
     250
     251  template <typename Graph>
     252  struct FindArcTagIndicator<
     253    Graph,
     254    typename enable_if<typename Graph::FindArcTag, void>::type
     255  > {
     256    static const bool value = true;
     257  };
     258
     259  template <typename Graph, typename Enable = void>
    234260  struct FindEdgeTagIndicator {
    235261    static const bool value = false;
  • lemon/bits/vector_map.h

    r314 r525  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure what
    42   // automatically updates the map when a key is added to or erased from
    43   // the map. This map type uses the std::vector to store the values.
     41  // The VectorMap template class is graph map structure that automatically
     42  // updates the map when a key is added to or erased from the graph.
     43  // This map type uses std::vector to store the values.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
     
    125125    // \brief Template assign operator.
    126126    //
    127     // The given parameter should be conform to the ReadMap
     127    // The given parameter should conform to the ReadMap
    128128    // concecpt and could be indiced by the current item set of
    129129    // the NodeMap. In this case the value for each item
     
    170170    // \brief Adds a new key to the map.
    171171    //
    172     // It adds a new key to the map. It called by the observer notifier
     172    // It adds a new key to the map. It is called by the observer notifier
    173173    // and it overrides the add() member function of the observer base.
    174174    virtual void add(const Key& key) {
     
    181181    // \brief Adds more new keys to the map.
    182182    //
    183     // It adds more new keys to the map. It called by the observer notifier
     183    // It adds more new keys to the map. It is called by the observer notifier
    184184    // and it overrides the add() member function of the observer base.
    185185    virtual void add(const std::vector<Key>& keys) {
     
    196196    // \brief Erase a key from the map.
    197197    //
    198     // Erase a key from the map. It called by the observer notifier
     198    // Erase a key from the map. It is called by the observer notifier
    199199    // and it overrides the erase() member function of the observer base.
    200200    virtual void erase(const Key& key) {
     
    204204    // \brief Erase more keys from the map.
    205205    //
    206     // Erase more keys from the map. It called by the observer notifier
     206    // It erases more keys from the map. It is called by the observer notifier
    207207    // and it overrides the erase() member function of the observer base.
    208208    virtual void erase(const std::vector<Key>& keys) {
     
    212212    }
    213213
    214     // \brief Buildes the map.
    215     //
    216     // It buildes the map. It called by the observer notifier
     214    // \brief Build the map.
     215    //
     216    // It builds the map. It is called by the observer notifier
    217217    // and it overrides the build() member function of the observer base.
    218218    virtual void build() {
     
    224224    // \brief Clear the map.
    225225    //
    226     // It erase all items from the map. It called by the observer notifier
     226    // It erases all items from the map. It is called by the observer notifier
    227227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {
  • lemon/bits/windows.h

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

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

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

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

    r263 r576  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
    20 #define LEMON_CONCEPT_DIGRAPH_H
     19#ifndef LEMON_CONCEPTS_DIGRAPH_H
     20#define LEMON_CONCEPTS_DIGRAPH_H
    2121
    2222///\ingroup graph_concepts
     
    485485
    486486
    487 #endif // LEMON_CONCEPT_DIGRAPH_H
     487#endif
  • lemon/concepts/graph.h

    r263 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of Undirected Graphs.
    2222
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
     23#ifndef LEMON_CONCEPTS_GRAPH_H
     24#define LEMON_CONCEPTS_GRAPH_H
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/graph.h>
    2827#include <lemon/core.h>
    2928
     
    603602      /// \brief Opposite node on an arc
    604603      ///
    605       /// \return the opposite of the given Node on the given Edge
     604      /// \return The opposite of the given node on the given edge.
    606605      Node oppositeNode(Node, Edge) const { return INVALID; }
    607606
    608607      /// \brief First node of the edge.
    609608      ///
    610       /// \return the first node of the given Edge.
     609      /// \return The first node of the given edge.
    611610      ///
    612611      /// Naturally edges don't have direction and thus
    613       /// don't have source and target node. But we use these two methods
    614       /// to query the two nodes of the arc. The direction of the arc
    615       /// which arises this way is called the inherent direction of the
     612      /// don't have source and target node. However we use \c u() and \c v()
     613      /// methods to query the two nodes of the arc. The direction of the
     614      /// arc which arises this way is called the inherent direction of the
    616615      /// edge, and is used to define the "default" direction
    617616      /// of the directed versions of the arcs.
    618       /// \sa direction
     617      /// \sa v()
     618      /// \sa direction()
    619619      Node u(Edge) const { return INVALID; }
    620620
    621621      /// \brief Second node of the edge.
     622      ///
     623      /// \return The second node of the given edge.
     624      ///
     625      /// Naturally edges don't have direction and thus
     626      /// don't have source and target node. However we use \c u() and \c v()
     627      /// methods to query the two nodes of the arc. The direction of the
     628      /// arc which arises this way is called the inherent direction of the
     629      /// edge, and is used to define the "default" direction
     630      /// of the directed versions of the arcs.
     631      /// \sa u()
     632      /// \sa direction()
    622633      Node v(Edge) const { return INVALID; }
    623634
  • lemon/concepts/graph_components.h

    r313 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of graph components.
    2222
    23 
    24 #ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
    25 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
     23#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     24#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    2625
    2726#include <lemon/core.h>
     
    4544
    4645#ifndef DOXYGEN
    47     template <char _selector = '0'>
     46    template <char sel = '0'>
    4847#endif
    4948    class GraphItem {
     
    115114    ///
    116115    /// This class provides the minimal set of features needed for a
    117     /// directed graph structure. All digraph concepts have to be
     116    /// directed graph structure. All digraph concepts have to
    118117    /// conform to this base directed graph. It just provides types
    119118    /// for nodes and arcs and functions to get the source and the
     
    180179    /// This class provides the minimal set of features needed for an
    181180    /// undirected graph structure. All undirected graph concepts have
    182     /// to be conform to this base graph. It just provides types for
     181    /// to conform to this base graph. It just provides types for
    183182    /// nodes, arcs and edges and functions to get the
    184183    /// source and the target of the arcs and edges,
     
    295294    /// This class provides beside the core digraph features
    296295    /// core id functions for the digraph structure.
    297     /// The most of the base digraphs should be conform to this concept.
     296    /// The most of the base digraphs should conform to this concept.
    298297    /// The id's are unique and immutable.
    299     template <typename _Base = BaseDigraphComponent>
    300     class IDableDigraphComponent : public _Base {
    301     public:
    302 
    303       typedef _Base Base;
     298    template <typename BAS = BaseDigraphComponent>
     299    class IDableDigraphComponent : public BAS {
     300    public:
     301
     302      typedef BAS Base;
    304303      typedef typename Base::Node Node;
    305304      typedef typename Base::Arc Arc;
     
    373372    /// This class provides beside the core undirected graph features
    374373    /// core id functions for the undirected graph structure.  The
    375     /// most of the base undirected graphs should be conform to this
     374    /// most of the base undirected graphs should conform to this
    376375    /// 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;
     376    template <typename BAS = BaseGraphComponent>
     377    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
     378    public:
     379
     380      typedef BAS Base;
    382381      typedef typename Base::Edge Edge;
    383382
    384       using IDableDigraphComponent<_Base>::id;
     383      using IDableDigraphComponent<Base>::id;
    385384
    386385      /// \brief Gives back an unique integer id for the Edge.
     
    426425    /// Skeleton class for graph NodeIt and ArcIt.
    427426    ///
    428     template <typename _Graph, typename _Item>
    429     class GraphItemIt : public _Item {
     427    template <typename GR, typename Item>
     428    class GraphItemIt : public Item {
    430429    public:
    431430      /// \brief Default constructor.
     
    443442      /// Sets the iterator to the first item of \c the graph.
    444443      ///
    445       explicit GraphItemIt(const _Graph&) {}
     444      explicit GraphItemIt(const GR&) {}
    446445      /// \brief Invalid constructor \& conversion.
    447446      ///
     
    480479          ++(++it1);
    481480
    482           _Item bi = it1;
     481          Item bi = it1;
    483482          bi = it2;
    484483        }
    485         _Graph& g;
     484        GR& g;
    486485      };
    487486    };
     
    490489    ///
    491490    /// \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
     491    /// base class, the \c sel is a additional template parameter (selector).
     492    /// For InArcIt you should instantiate it with character 'i' and for
    494493    /// 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 {
     494    template <typename GR,
     495              typename Item = typename GR::Arc,
     496              typename Base = typename GR::Node,
     497              char sel = '0'>
     498    class GraphIncIt : public Item {
    500499    public:
    501500      /// \brief Default constructor.
     
    508507      /// Copy constructor.
    509508      ///
    510       GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
     509      GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
    511510      /// \brief Sets the iterator to the first arc incoming into or outgoing
    512511      /// from the node.
     
    515514      /// from the node.
    516515      ///
    517       explicit GraphIncIt(const _Graph&, const _Base&) {}
     516      explicit GraphIncIt(const GR&, const Base&) {}
    518517      /// \brief Invalid constructor \& conversion.
    519518      ///
     
    547546      struct Constraints {
    548547        void constraints() {
    549           checkConcept<GraphItem<_selector>, _GraphIncIt>();
     548          checkConcept<GraphItem<sel>, _GraphIncIt>();
    550549          _GraphIncIt it1(graph, node);
    551550          _GraphIncIt it2;
     
    554553          ++it2 = it1;
    555554          ++(++it1);
    556           _Item e = it1;
     555          Item e = it1;
    557556          e = it2;
    558557
    559558        }
    560559
    561         _Item arc;
    562         _Base node;
    563         _Graph graph;
     560        Item arc;
     561        Base node;
     562        GR graph;
    564563        _GraphIncIt it;
    565564      };
     
    572571    /// iterator based iterable interface for the digraph structure.
    573572    /// This concept is part of the Digraph concept.
    574     template <typename _Base = BaseDigraphComponent>
    575     class IterableDigraphComponent : public _Base {
    576 
    577     public:
    578 
    579       typedef _Base Base;
     573    template <typename BAS = BaseDigraphComponent>
     574    class IterableDigraphComponent : public BAS {
     575
     576    public:
     577
     578      typedef BAS Base;
    580579      typedef typename Base::Node Node;
    581580      typedef typename Base::Arc Arc;
     
    757756    /// based iterable interface for the undirected graph structure.
    758757    /// This concept is part of the Graph concept.
    759     template <typename _Base = BaseGraphComponent>
    760     class IterableGraphComponent : public IterableDigraphComponent<_Base> {
    761     public:
    762 
    763       typedef _Base Base;
     758    template <typename BAS = BaseGraphComponent>
     759    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
     760    public:
     761
     762      typedef BAS Base;
    764763      typedef typename Base::Node Node;
    765764      typedef typename Base::Arc Arc;
     
    774773      /// @{
    775774
    776       using IterableDigraphComponent<_Base>::first;
    777       using IterableDigraphComponent<_Base>::next;
     775      using IterableDigraphComponent<Base>::first;
     776      using IterableDigraphComponent<Base>::next;
    778777
    779778      /// \brief Gives back the first edge in the iterating
     
    809808      void nextInc(Edge&, bool&) const {}
    810809
    811       using IterableDigraphComponent<_Base>::baseNode;
    812       using IterableDigraphComponent<_Base>::runningNode;
     810      using IterableDigraphComponent<Base>::baseNode;
     811      using IterableDigraphComponent<Base>::runningNode;
    813812
    814813      /// @}
     
    876875
    877876        const _Graph& graph;
    878 
    879877      };
    880878    };
     
    888886    /// alteration occured in the digraph all the observers will
    889887    /// notified about it.
    890     template <typename _Base = BaseDigraphComponent>
    891     class AlterableDigraphComponent : public _Base {
    892     public:
    893 
    894       typedef _Base Base;
     888    template <typename BAS = BaseDigraphComponent>
     889    class AlterableDigraphComponent : public BAS {
     890    public:
     891
     892      typedef BAS Base;
    895893      typedef typename Base::Node Node;
    896894      typedef typename Base::Arc Arc;
     
    946944    /// alteration occured in the graph all the observers will
    947945    /// notified about it.
    948     template <typename _Base = BaseGraphComponent>
    949     class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
    950     public:
    951 
    952       typedef _Base Base;
     946    template <typename BAS = BaseGraphComponent>
     947    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
     948    public:
     949
     950      typedef BAS Base;
    953951      typedef typename Base::Edge Edge;
    954952
     
    975973
    976974        const _Graph& graph;
    977 
    978       };
    979 
     975      };
    980976    };
    981977
     
    985981    /// (NodeMap, ArcMap), that is maps that can be used to
    986982    /// associate data to graph descriptors (nodes or arcs).
    987     template <typename _Graph, typename _Item, typename _Value>
    988     class GraphMap : public ReadWriteMap<_Item, _Value> {
    989     public:
    990 
    991       typedef ReadWriteMap<_Item, _Value> Parent;
     983    template <typename GR, typename K, typename V>
     984    class GraphMap : public ReadWriteMap<K, V> {
     985    public:
     986
     987      typedef ReadWriteMap<K, V> Parent;
    992988
    993989      /// The graph type of the map.
    994       typedef _Graph Graph;
     990      typedef GR Graph;
    995991      /// The key type of the map.
    996       typedef _Item Key;
     992      typedef K Key;
    997993      /// The value type of the map.
    998       typedef _Value Value;
     994      typedef V Value;
    999995
    1000996      /// \brief Construct a new map.
     
    10561052    /// map interface for the digraph structure.
    10571053    /// This concept is part of the Digraph concept.
    1058     template <typename _Base = BaseDigraphComponent>
    1059     class MappableDigraphComponent : public _Base  {
    1060     public:
    1061 
    1062       typedef _Base Base;
     1054    template <typename BAS = BaseDigraphComponent>
     1055    class MappableDigraphComponent : public BAS  {
     1056    public:
     1057
     1058      typedef BAS Base;
    10631059      typedef typename Base::Node Node;
    10641060      typedef typename Base::Arc Arc;
     
    10701066      /// ReadWrite map of the nodes.
    10711067      ///
    1072       template <typename _Value>
    1073       class NodeMap : public GraphMap<Digraph, Node, _Value> {
     1068      template <typename V>
     1069      class NodeMap : public GraphMap<Digraph, Node, V> {
    10741070      public:
    1075         typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
     1071        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
    10761072
    10771073        /// \brief Construct a new map.
     
    10841080        ///
    10851081        /// Construct a new map for the digraph and initalise the values.
    1086         NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
     1082        NodeMap(const MappableDigraphComponent& digraph, const V& value)
    10871083          : Parent(digraph, value) {}
    10881084
     
    10981094        template <typename CMap>
    10991095        NodeMap& operator=(const CMap&) {
    1100           checkConcept<ReadMap<Node, _Value>, CMap>();
     1096          checkConcept<ReadMap<Node, V>, CMap>();
    11011097          return *this;
    11021098        }
     
    11081104      /// ReadWrite map of the arcs.
    11091105      ///
    1110       template <typename _Value>
    1111       class ArcMap : public GraphMap<Digraph, Arc, _Value> {
     1106      template <typename V>
     1107      class ArcMap : public GraphMap<Digraph, Arc, V> {
    11121108      public:
    1113         typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
     1109        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
    11141110
    11151111        /// \brief Construct a new map.
     
    11221118        ///
    11231119        /// Construct a new map for the digraph and initalise the values.
    1124         ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
     1120        ArcMap(const MappableDigraphComponent& digraph, const V& value)
    11251121          : Parent(digraph, value) {}
    11261122
     
    11361132        template <typename CMap>
    11371133        ArcMap& operator=(const CMap&) {
    1138           checkConcept<ReadMap<Arc, _Value>, CMap>();
     1134          checkConcept<ReadMap<Arc, V>, CMap>();
    11391135          return *this;
    11401136        }
     
    11921188    /// map interface for the graph structure.
    11931189    /// This concept is part of the Graph concept.
    1194     template <typename _Base = BaseGraphComponent>
    1195     class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
    1196     public:
    1197 
    1198       typedef _Base Base;
     1190    template <typename BAS = BaseGraphComponent>
     1191    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
     1192    public:
     1193
     1194      typedef BAS Base;
    11991195      typedef typename Base::Edge Edge;
    12001196
     
    12051201      /// ReadWrite map of the edges.
    12061202      ///
    1207       template <typename _Value>
    1208       class EdgeMap : public GraphMap<Graph, Edge, _Value> {
     1203      template <typename V>
     1204      class EdgeMap : public GraphMap<Graph, Edge, V> {
    12091205      public:
    1210         typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
     1206        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
    12111207
    12121208        /// \brief Construct a new map.
     
    12191215        ///
    12201216        /// Construct a new map for the graph and initalise the values.
    1221         EdgeMap(const MappableGraphComponent& graph, const _Value& value)
     1217        EdgeMap(const MappableGraphComponent& graph, const V& value)
    12221218          : Parent(graph, value) {}
    12231219
     
    12331229        template <typename CMap>
    12341230        EdgeMap& operator=(const CMap&) {
    1235           checkConcept<ReadMap<Edge, _Value>, CMap>();
     1231          checkConcept<ReadMap<Edge, V>, CMap>();
    12361232          return *this;
    12371233        }
     
    12771273    /// difference between the base and this interface is that the
    12781274    /// digraph alterations should handled already on this level.
    1279     template <typename _Base = BaseDigraphComponent>
    1280     class ExtendableDigraphComponent : public _Base {
    1281     public:
    1282       typedef _Base Base;
    1283 
    1284       typedef typename _Base::Node Node;
    1285       typedef typename _Base::Arc Arc;
     1275    template <typename BAS = BaseDigraphComponent>
     1276    class ExtendableDigraphComponent : public BAS {
     1277    public:
     1278      typedef BAS Base;
     1279
     1280      typedef typename Base::Node Node;
     1281      typedef typename Base::Arc Arc;
    12861282
    12871283      /// \brief Adds a new node to the digraph.
     
    13221318    /// that the graph alterations should handled already on this
    13231319    /// level.
    1324     template <typename _Base = BaseGraphComponent>
    1325     class ExtendableGraphComponent : public _Base {
    1326     public:
    1327 
    1328       typedef _Base Base;
    1329       typedef typename _Base::Node Node;
    1330       typedef typename _Base::Edge Edge;
     1320    template <typename BAS = BaseGraphComponent>
     1321    class ExtendableGraphComponent : public BAS {
     1322    public:
     1323
     1324      typedef BAS Base;
     1325      typedef typename Base::Node Node;
     1326      typedef typename Base::Edge Edge;
    13311327
    13321328      /// \brief Adds a new node to the graph.
     
    13661362    /// the base and this interface is that the digraph alterations
    13671363    /// should handled already on this level.
    1368     template <typename _Base = BaseDigraphComponent>
    1369     class ErasableDigraphComponent : public _Base {
    1370     public:
    1371 
    1372       typedef _Base Base;
     1364    template <typename BAS = BaseDigraphComponent>
     1365    class ErasableDigraphComponent : public BAS {
     1366    public:
     1367
     1368      typedef BAS Base;
    13731369      typedef typename Base::Node Node;
    13741370      typedef typename Base::Arc Arc;
     
    14061402    /// main difference between the base and this interface is that
    14071403    /// the graph alterations should handled already on this level.
    1408     template <typename _Base = BaseGraphComponent>
    1409     class ErasableGraphComponent : public _Base {
    1410     public:
    1411 
    1412       typedef _Base Base;
     1404    template <typename BAS = BaseGraphComponent>
     1405    class ErasableGraphComponent : public BAS {
     1406    public:
     1407
     1408      typedef BAS Base;
    14131409      typedef typename Base::Node Node;
    14141410      typedef typename Base::Edge Edge;
     
    14461442    /// the base and this interface is that the digraph alterations
    14471443    /// should handled already on this level.
    1448     template <typename _Base = BaseDigraphComponent>
    1449     class ClearableDigraphComponent : public _Base {
    1450     public:
    1451 
    1452       typedef _Base Base;
     1444    template <typename BAS = BaseDigraphComponent>
     1445    class ClearableDigraphComponent : public BAS {
     1446    public:
     1447
     1448      typedef BAS Base;
    14531449
    14541450      /// \brief Erase all nodes and arcs from the digraph.
     
    14751471    /// main difference between the base and this interface is that
    14761472    /// the graph alterations should handled already on this level.
    1477     template <typename _Base = BaseGraphComponent>
    1478     class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
    1479     public:
    1480 
    1481       typedef _Base Base;
     1473    template <typename BAS = BaseGraphComponent>
     1474    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
     1475    public:
     1476
     1477      typedef BAS Base;
    14821478
    14831479      template <typename _Graph>
  • lemon/concepts/heap.h

    r290 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2121///\brief The concept of heaps.
    2222
    23 #ifndef LEMON_CONCEPT_HEAP_H
    24 #define LEMON_CONCEPT_HEAP_H
     23#ifndef LEMON_CONCEPTS_HEAP_H
     24#define LEMON_CONCEPTS_HEAP_H
    2525
    2626#include <lemon/core.h>
     27#include <lemon/concept_check.h>
    2728
    2829namespace lemon {
     
    3536    /// \brief The heap concept.
    3637    ///
    37     /// Concept class describing the main interface of heaps.
    38     template <typename Priority, typename ItemIntMap>
     38    /// Concept class describing the main interface of heaps. A \e heap
     39    /// is a data structure for storing items with specified values called
     40    /// \e priorities in such a way that finding the item with minimum
     41    /// priority is efficient. In a heap one can change the priority of an
     42    /// item, add or erase an item, etc.
     43    ///
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
     46    /// internally 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>.
     49#ifdef DOXYGEN
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
     51#else
     52    template <typename PR, typename IM>
     53#endif
    3954    class Heap {
    4055    public:
    4156
     57      /// Type of the item-int map.
     58      typedef IM ItemIntMap;
     59      /// Type of the priorities.
     60      typedef PR Prio;
    4261      /// Type of the items stored in the heap.
    4362      typedef typename ItemIntMap::Key Item;
    44 
    45       /// Type of the priorities.
    46       typedef Priority Prio;
    4763
    4864      /// \brief Type to represent the states of the items.
     
    5369      /// the user.
    5470      ///
    55       /// The \c ItemIntMap must be initialized in such a way, that it
    56       /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
     71      /// The item-int map must be initialized in such way that it assigns
     72      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    5773      enum State {
    58         IN_HEAP = 0,
    59         PRE_HEAP = -1,
    60         POST_HEAP = -2
     74        IN_HEAP = 0,    ///< The "in heap" state constant.
     75        PRE_HEAP = -1,  ///< The "pre heap" state constant.
     76        POST_HEAP = -2  ///< The "post heap" state constant.
    6177      };
    6278
     
    119135      ///
    120136      /// Returns the priority of the given item.
     137      /// \param i The item.
    121138      /// \pre \c i must be in the heap.
    122       /// \param i The item.
    123139      Prio operator[](const Item &i) const {}
    124140
     
    137153      ///
    138154      /// Decreases the priority of an item to the given value.
     155      /// \param i The item.
     156      /// \param p The priority.
    139157      /// \pre \c i must be stored in the heap with priority at least \c p.
     158      void decrease(const Item &i, const Prio &p) {}
     159
     160      /// \brief Increases the priority of an item to the given value.
     161      ///
     162      /// Increases the priority of an item to the given value.
    140163      /// \param i The item.
    141164      /// \param p The priority.
    142       void decrease(const Item &i, const Prio &p) {}
    143 
    144       /// \brief Increases the priority of an item to the given value.
    145       ///
    146       /// Increases the priority of an item to the given value.
    147165      /// \pre \c i must be stored in the heap with priority at most \c p.
    148       /// \param i The item.
    149       /// \param p The priority.
    150166      void increase(const Item &i, const Prio &p) {}
    151167
     
    243259  } // namespace lemon
    244260}
    245 #endif // LEMON_CONCEPT_PATH_H
     261#endif
  • lemon/concepts/maps.h

    r314 r576  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
    19 #ifndef LEMON_CONCEPT_MAPS_H
    20 #define LEMON_CONCEPT_MAPS_H
     19#ifndef LEMON_CONCEPTS_MAPS_H
     20#define LEMON_CONCEPTS_MAPS_H
    2121
    2222#include <lemon/core.h>
     
    214214} //namespace lemon
    215215
    216 #endif // LEMON_CONCEPT_MAPS_H
     216#endif
  • lemon/concepts/path.h

    r281 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222///
    2323
    24 #ifndef LEMON_CONCEPT_PATH_H
    25 #define LEMON_CONCEPT_PATH_H
     24#ifndef LEMON_CONCEPTS_PATH_H
     25#define LEMON_CONCEPTS_PATH_H
    2626
    2727#include <lemon/core.h>
     
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
    41     /// \tparam _Digraph The digraph type in which the path is.
     41    /// \tparam GR The digraph type in which the path is.
    4242    ///
    4343    /// In a sense, the path can be treated as a list of arcs. The
     
    4646    /// paths cannot store the source.
    4747    ///
    48     template <typename _Digraph>
     48    template <typename GR>
    4949    class Path {
    5050    public:
    5151
    5252      /// Type of the underlying digraph.
    53       typedef _Digraph Digraph;
     53      typedef GR Digraph;
    5454      /// Arc type of the underlying digraph.
    5555      typedef typename Digraph::Arc Arc;
     
    206206    /// assigned to a real path and the dumpers can be implemented as
    207207    /// an adaptor class to the predecessor map.
    208 
    209     /// \tparam _Digraph The digraph type in which the path is.
     208    ///
     209    /// \tparam GR The digraph type in which the path is.
    210210    ///
    211211    /// The paths can be constructed from any path type by a
    212212    /// template constructor or a template assignment operator.
    213     ///
    214     template <typename _Digraph>
     213    template <typename GR>
    215214    class PathDumper {
    216215    public:
    217216
    218217      /// Type of the underlying digraph.
    219       typedef _Digraph Digraph;
     218      typedef GR Digraph;
    220219      /// Arc type of the underlying digraph.
    221220      typedef typename Digraph::Arc Arc;
     
    306305} // namespace lemon
    307306
    308 #endif // LEMON_CONCEPT_PATH_H
     307#endif
  • lemon/config.h.cmake

    r515 r564  
    11#cmakedefine HAVE_LONG_LONG 1
     2#cmakedefine HAVE_LP 1
     3#cmakedefine HAVE_MIP 1
     4#cmakedefine HAVE_GLPK 1
  • lemon/config.h.in

    r515 r564  
     1/* Define to 1 if you have long long */
     2#undef HAVE_LONG_LONG
     3
     4/* Define to 1 if you have any LP solver. */
     5#undef HAVE_LP
     6
     7/* Define to 1 if you have any MIP solver. */
     8#undef HAVE_MIP
     9
    110/* Define to 1 if you have CPLEX. */
    211#undef HAVE_CPLEX
     
    514#undef HAVE_GLPK
    615
    7 /* Define to 1 if you have long long */
    8 #undef HAVE_LONG_LONG
     16/* Define to 1 if you have SOPLEX */
     17#undef HAVE_SOPLEX
     18
     19/* Define to 1 if you have CLP */
     20#undef HAVE_CLP
  • lemon/core.h

    r523 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    10351035  ///\sa findArc()
    10361036  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1037   template <typename _Graph>
    1038   class ConArcIt : public _Graph::Arc {
     1037  template <typename GR>
     1038  class ConArcIt : public GR::Arc {
    10391039  public:
    10401040
    1041     typedef _Graph Graph;
     1041    typedef GR Graph;
    10421042    typedef typename Graph::Arc Parent;
    10431043
     
    11581158  ///
    11591159  ///\sa findEdge()
    1160   template <typename _Graph>
    1161   class ConEdgeIt : public _Graph::Edge {
     1160  template <typename GR>
     1161  class ConEdgeIt : public GR::Edge {
    11621162  public:
    11631163
    1164     typedef _Graph Graph;
     1164    typedef GR Graph;
    11651165    typedef typename Graph::Edge Parent;
    11661166
     
    12121212  ///queries.
    12131213  ///
    1214   ///\tparam G The type of the underlying digraph.
     1214  ///\tparam GR The type of the underlying digraph.
    12151215  ///
    12161216  ///\sa ArcLookUp
    12171217  ///\sa AllArcLookUp
    1218   template<class G>
     1218  template <typename GR>
    12191219  class DynArcLookUp
    1220     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1220    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12211221  {
    12221222  public:
    1223     typedef typename ItemSetTraits<G, typename G::Arc>
     1223    typedef typename ItemSetTraits<GR, typename GR::Arc>
    12241224    ::ItemNotifier::ObserverBase Parent;
    12251225
    1226     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1227     typedef G Digraph;
     1226    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1227    typedef GR Digraph;
    12281228
    12291229  protected:
    12301230
    1231     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1231    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
    12321232    public:
    12331233
    1234       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1235 
    1236       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1234      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1235
     1236      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12371237
    12381238      virtual void add(const Node& node) {
     
    16241624  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16251625  ///
    1626   ///\tparam G The type of the underlying digraph.
     1626  ///\tparam GR The type of the underlying digraph.
    16271627  ///
    16281628  ///\sa DynArcLookUp
    16291629  ///\sa AllArcLookUp
    1630   template<class G>
     1630  template<class GR>
    16311631  class ArcLookUp
    16321632  {
    16331633  public:
    1634     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1635     typedef G Digraph;
     1634    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1635    typedef GR Digraph;
    16361636
    16371637  protected:
     
    17341734  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17351735  ///
    1736   ///\tparam G The type of the underlying digraph.
     1736  ///\tparam GR The type of the underlying digraph.
    17371737  ///
    17381738  ///\sa DynArcLookUp
    17391739  ///\sa ArcLookUp
    1740   template<class G>
    1741   class AllArcLookUp : public ArcLookUp<G>
     1740  template<class GR>
     1741  class AllArcLookUp : public ArcLookUp<GR>
    17421742  {
    1743     using ArcLookUp<G>::_g;
    1744     using ArcLookUp<G>::_right;
    1745     using ArcLookUp<G>::_left;
    1746     using ArcLookUp<G>::_head;
    1747 
    1748     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1749     typedef G Digraph;
     1743    using ArcLookUp<GR>::_g;
     1744    using ArcLookUp<GR>::_right;
     1745    using ArcLookUp<GR>::_left;
     1746    using ArcLookUp<GR>::_head;
     1747
     1748    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1749    typedef GR Digraph;
    17501750
    17511751    typename Digraph::template ArcMap<Arc> _next;
     
    17741774    ///It builds up the search database, which remains valid until the digraph
    17751775    ///changes.
    1776     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1776    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17771777
    17781778    ///Refresh the data structure at a node.
     
    17841784    void refresh(Node n)
    17851785    {
    1786       ArcLookUp<G>::refresh(n);
     1786      ArcLookUp<GR>::refresh(n);
    17871787      refreshNext(_head[n]);
    17881788    }
     
    18311831    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18321832#else
    1833     using ArcLookUp<G>::operator() ;
     1833    using ArcLookUp<GR>::operator() ;
    18341834    Arc operator()(Node s, Node t, Arc prev) const
    18351835    {
  • lemon/counter.h

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

    r319 r525  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    53 
    54     ///This function instantiates a PredMap.
     52    ///Instantiates a \c PredMap.
     53
     54    ///This function instantiates a \ref PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
     56    ///\ref PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6666    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    68 
    69     ///This function instantiates a ProcessedMap.
     67    ///Instantiates a \c ProcessedMap.
     68
     69    ///This function instantiates a \ref ProcessedMap.
    7070    ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
     71    ///we would like to define the \ref ProcessedMap.
    7272#ifdef DOXYGEN
    7373    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8484    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8585    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    87 
    88     ///This function instantiates a ReachedMap.
     86    ///Instantiates a \c ReachedMap.
     87
     88    ///This function instantiates a \ref ReachedMap.
    8989    ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
     90    ///we would like to define the \ref ReachedMap.
    9191    static ReachedMap *createReachedMap(const Digraph &g)
    9292    {
     
    9999    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    100100    typedef typename Digraph::template NodeMap<int> DistMap;
    101     ///Instantiates a DistMap.
    102 
    103     ///This function instantiates a DistMap.
     101    ///Instantiates a \c DistMap.
     102
     103    ///This function instantiates a \ref DistMap.
    104104    ///\param g is the digraph, to which we would like to define the
    105     ///DistMap.
     105    ///\ref DistMap.
    106106    static DistMap *createDistMap(const Digraph &g)
    107107    {
     
    120120  ///
    121121  ///\tparam GR The type of the digraph the algorithm runs on.
    122   ///The default value is \ref ListDigraph. The value of GR is not used
    123   ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
    124   ///\tparam TR Traits class to set various data types used by the algorithm.
    125   ///The default traits class is
    126   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    127   ///See \ref DfsDefaultTraits for the documentation of
    128   ///a Dfs traits class.
     122  ///The default type is \ref ListDigraph.
    129123#ifdef DOXYGEN
    130124  template <typename GR,
     
    152146    typedef PredMapPath<Digraph, PredMap> Path;
    153147
    154     ///The traits class.
     148    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    155149    typedef TR Traits;
    156150
     
    227221    };
    228222    ///\brief \ref named-templ-param "Named parameter" for setting
    229     ///PredMap type.
     223    ///\c PredMap type.
    230224    ///
    231225    ///\ref named-templ-param "Named parameter" for setting
    232     ///PredMap type.
     226    ///\c PredMap type.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    233228    template <class T>
    234229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    246241    };
    247242    ///\brief \ref named-templ-param "Named parameter" for setting
    248     ///DistMap type.
     243    ///\c DistMap type.
    249244    ///
    250245    ///\ref named-templ-param "Named parameter" for setting
    251     ///DistMap type.
     246    ///\c DistMap type.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    252248    template <class T>
    253249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265261    };
    266262    ///\brief \ref named-templ-param "Named parameter" for setting
    267     ///ReachedMap type.
     263    ///\c ReachedMap type.
    268264    ///
    269265    ///\ref named-templ-param "Named parameter" for setting
    270     ///ReachedMap type.
     266    ///\c ReachedMap type.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    271268    template <class T>
    272269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    284281    };
    285282    ///\brief \ref named-templ-param "Named parameter" for setting
    286     ///ProcessedMap type.
     283    ///\c ProcessedMap type.
    287284    ///
    288285    ///\ref named-templ-param "Named parameter" for setting
    289     ///ProcessedMap type.
     286    ///\c ProcessedMap type.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290288    template <class T>
    291289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    301299    };
    302300    ///\brief \ref named-templ-param "Named parameter" for setting
    303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     301    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    304302    ///
    305303    ///\ref named-templ-param "Named parameter" for setting
    306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    307305    ///If you don't set it explicitly, it will be automatically allocated.
    308306    struct SetStandardProcessedMap :
     
    339337
    340338    ///Sets the map that stores the predecessor arcs.
    341     ///If you don't use this function before calling \ref run(),
    342     ///it will allocate one. The destructor deallocates this
    343     ///automatically allocated map, of course.
     339    ///If you don't use this function before calling \ref run(Node) "run()"
     340    ///or \ref init(), an instance will be allocated automatically.
     341    ///The destructor deallocates this automatically allocated map,
     342    ///of course.
    344343    ///\return <tt> (*this) </tt>
    345344    Dfs &predMap(PredMap &m)
     
    356355
    357356    ///Sets the map that indicates which nodes are reached.
    358     ///If you don't use this function before calling \ref run(),
    359     ///it will allocate one. The destructor deallocates this
    360     ///automatically allocated map, of course.
     357    ///If you don't use this function before calling \ref run(Node) "run()"
     358    ///or \ref init(), an instance will be allocated automatically.
     359    ///The destructor deallocates this automatically allocated map,
     360    ///of course.
    361361    ///\return <tt> (*this) </tt>
    362362    Dfs &reachedMap(ReachedMap &m)
     
    373373
    374374    ///Sets the map that indicates which nodes are processed.
    375     ///If you don't use this function before calling \ref run(),
    376     ///it will allocate one. The destructor deallocates this
    377     ///automatically allocated map, of course.
     375    ///If you don't use this function before calling \ref run(Node) "run()"
     376    ///or \ref init(), an instance will be allocated automatically.
     377    ///The destructor deallocates this automatically allocated map,
     378    ///of course.
    378379    ///\return <tt> (*this) </tt>
    379380    Dfs &processedMap(ProcessedMap &m)
     
    391392    ///Sets the map that stores the distances of the nodes calculated by
    392393    ///the algorithm.
    393     ///If you don't use this function before calling \ref run(),
    394     ///it will allocate one. The destructor deallocates this
    395     ///automatically allocated map, of course.
     394    ///If you don't use this function before calling \ref run(Node) "run()"
     395    ///or \ref init(), an instance will be allocated automatically.
     396    ///The destructor deallocates this automatically allocated map,
     397    ///of course.
    396398    ///\return <tt> (*this) </tt>
    397399    Dfs &distMap(DistMap &m)
     
    407409  public:
    408410
    409     ///\name Execution control
    410     ///The simplest way to execute the algorithm is to use
    411     ///one of the member functions called \ref lemon::Dfs::run() "run()".
    412     ///\n
    413     ///If you need more control on the execution, first you must call
    414     ///\ref lemon::Dfs::init() "init()", then you can add a source node
    415     ///with \ref lemon::Dfs::addSource() "addSource()".
    416     ///Finally \ref lemon::Dfs::start() "start()" will perform the
    417     ///actual path computation.
     411    ///\name Execution Control
     412    ///The simplest way to execute the DFS algorithm is to use one of the
     413    ///member functions called \ref run(Node) "run()".\n
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
     416    ///and perform the actual computation with \ref start().
     417    ///This procedure can be repeated if there are nodes that have not
     418    ///been reached.
    418419
    419420    ///@{
    420421
     422    ///\brief Initializes the internal data structures.
     423    ///
    421424    ///Initializes the internal data structures.
    422 
    423     ///Initializes the internal data structures.
    424     ///
    425425    void init()
    426426    {
     
    439439    ///Adds a new source node to the set of nodes to be processed.
    440440    ///
    441     ///\pre The stack must be empty. (Otherwise the algorithm gives
    442     ///false results.)
    443     ///
    444     ///\warning Distances will be wrong (or at least strange) in case of
    445     ///multiple sources.
     441    ///\pre The stack must be empty. Otherwise the algorithm gives
     442    ///wrong results. (One of the outgoing arcs of all the source nodes
     443    ///except for the last one will not be visited and distances will
     444    ///also be wrong.)
    446445    void addSource(Node s)
    447446    {
     
    507506    }
    508507
    509     ///\brief Returns \c false if there are nodes
    510     ///to be processed.
    511     ///
    512     ///Returns \c false if there are nodes
    513     ///to be processed in the queue (stack).
     508    ///Returns \c false if there are nodes to be processed.
     509
     510    ///Returns \c false if there are nodes to be processed
     511    ///in the queue (stack).
    514512    bool emptyQueue() const { return _stack_head<0; }
    515513
    516514    ///Returns the number of the nodes to be processed.
    517515
    518     ///Returns the number of the nodes to be processed in the queue (stack).
     516    ///Returns the number of the nodes to be processed
     517    ///in the queue (stack).
    519518    int queueSize() const { return _stack_head+1; }
    520519
     
    638637    ///
    639638    ///The algorithm computes
    640     ///- the %DFS tree,
    641     ///- the distance of each node from the root in the %DFS tree.
     639    ///- the %DFS tree (forest),
     640    ///- the distance of each node from the root(s) in the %DFS tree.
    642641    ///
    643642    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    664663
    665664    ///\name Query Functions
    666     ///The result of the %DFS algorithm can be obtained using these
     665    ///The results of the DFS algorithm can be obtained using these
    667666    ///functions.\n
    668     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
    669     ///"start()" must be called before using them.
     667    ///Either \ref run(Node) "run()" or \ref start() should be called
     668    ///before using them.
    670669
    671670    ///@{
     
    675674    ///Returns the DFS path to a node.
    676675    ///
    677     ///\warning \c t should be reachable from the root.
    678     ///
    679     ///\pre Either \ref run() or \ref start() must be called before
    680     ///using this function.
     676    ///\warning \c t should be reached from the root(s).
     677    ///
     678    ///\pre Either \ref run(Node) "run()" or \ref init()
     679    ///must be called before using this function.
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    683     ///The distance of a node from the root.
    684 
    685     ///Returns the distance of a node from the root.
    686     ///
    687     ///\warning If node \c v is not reachable from the root, then
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
     685    ///
     686    ///\warning If node \c v is not reached from the root(s), then
    688687    ///the return value of this function is undefined.
    689688    ///
    690     ///\pre Either \ref run() or \ref start() must be called before
    691     ///using this function.
     689    ///\pre Either \ref run(Node) "run()" or \ref init()
     690    ///must be called before using this function.
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
     
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
    697     ///node \c v, i.e. it returns the last arc of a %DFS path from the
    698     ///root to \c v. It is \c INVALID
    699     ///if \c v is not reachable from the root(s) or if \c v is a root.
     696    ///node \c v, i.e. it returns the last arc of a %DFS path from a
     697    ///root to \c v. It is \c INVALID if \c v is not reached from the
     698    ///root(s) or if \c v is a root.
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702701    ///\ref predNode().
    703702    ///
    704     ///\pre Either \ref run() or \ref start() must be called before using
    705     ///this function.
     703    ///\pre Either \ref run(Node) "run()" or \ref init()
     704    ///must be called before using this function.
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
     
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///from a %DFS path from the root to \c v. It is \c INVALID
    713     ///if \c v is not reachable from the root(s) or if \c v is a root.
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716715    ///\ref predArc().
    717716    ///
    718     ///\pre Either \ref run() or \ref start() must be called before
    719     ///using this function.
     717    ///\pre Either \ref run(Node) "run()" or \ref init()
     718    ///must be called before using this function.
    720719    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    721720                                  G->source((*_pred)[v]); }
     
    727726    ///distances of the nodes calculated by the algorithm.
    728727    ///
    729     ///\pre Either \ref run() or \ref init()
     728    ///\pre Either \ref run(Node) "run()" or \ref init()
    730729    ///must be called before using this function.
    731730    const DistMap &distMap() const { return *_dist;}
     
    737736    ///arcs, which form the DFS tree.
    738737    ///
    739     ///\pre Either \ref run() or \ref init()
     738    ///\pre Either \ref run(Node) "run()" or \ref init()
    740739    ///must be called before using this function.
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    743     ///Checks if a node is reachable from the root(s).
    744 
    745     ///Returns \c true if \c v is reachable from the root(s).
    746     ///\pre Either \ref run() or \ref start()
     742    ///Checks if a node is reached from the root(s).
     743
     744    ///Returns \c true if \c v is reached from the root(s).
     745    ///
     746    ///\pre Either \ref run(Node) "run()" or \ref init()
    747747    ///must be called before using this function.
    748748    bool reached(Node v) const { return (*_reached)[v]; }
     
    890890  /// This auxiliary class is created to implement the
    891891  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
    892   /// It does not have own \ref run() method, it uses the functions
    893   /// and features of the plain \ref Dfs.
     892  /// It does not have own \ref run(Node) "run()" method, it uses the
     893  /// functions and features of the plain \ref Dfs.
    894894  ///
    895895  /// This class should only be used through the \ref dfs() function,
     
    11111111  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    11121112  ///\endcode
    1113 
    1114   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
     1113  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
    11151114  ///to the end of the parameter list.
    11161115  ///\sa DfsWizard
     
    11281127  /// This class defines the interface of the DfsVisit events, and
    11291128  /// it could be the base of a real visitor class.
    1130   template <typename _Digraph>
     1129  template <typename GR>
    11311130  struct DfsVisitor {
    1132     typedef _Digraph Digraph;
     1131    typedef GR Digraph;
    11331132    typedef typename Digraph::Arc Arc;
    11341133    typedef typename Digraph::Node Node;
     
    11661165  };
    11671166#else
    1168   template <typename _Digraph>
     1167  template <typename GR>
    11691168  struct DfsVisitor {
    1170     typedef _Digraph Digraph;
     1169    typedef GR Digraph;
    11711170    typedef typename Digraph::Arc Arc;
    11721171    typedef typename Digraph::Node Node;
     
    12011200  /// Default traits class of DfsVisit class.
    12021201  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1203   template<class _Digraph>
     1202  template<class GR>
    12041203  struct DfsVisitDefaultTraits {
    12051204
    12061205    /// \brief The type of the digraph the algorithm runs on.
    1207     typedef _Digraph Digraph;
     1206    typedef GR Digraph;
    12081207
    12091208    /// \brief The type of the map that indicates which nodes are reached.
     
    12261225  /// \ingroup search
    12271226  ///
    1228   /// \brief %DFS algorithm class with visitor interface.
     1227  /// \brief DFS algorithm class with visitor interface.
    12291228  ///
    1230   /// This class provides an efficient implementation of the %DFS algorithm
     1229  /// This class provides an efficient implementation of the DFS algorithm
    12311230  /// with visitor interface.
    12321231  ///
    1233   /// The %DfsVisit class provides an alternative interface to the Dfs
     1232  /// The DfsVisit class provides an alternative interface to the Dfs
    12341233  /// class. It works with callback mechanism, the DfsVisit object calls
    12351234  /// the member functions of the \c Visitor class on every DFS event.
     
    12401239  /// instead.
    12411240  ///
    1242   /// \tparam _Digraph The type of the digraph the algorithm runs on.
    1243   /// The default value is
    1244   /// \ref ListDigraph. The value of _Digraph is not used directly by
    1245   /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
    1246   /// \tparam _Visitor The Visitor type that is used by the algorithm.
    1247   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
     1241  /// \tparam GR The type of the digraph the algorithm runs on.
     1242  /// The default type is \ref ListDigraph.
     1243  /// The value of GR is not used directly by \ref DfsVisit,
     1244  /// it is only passed to \ref DfsVisitDefaultTraits.
     1245  /// \tparam VS The Visitor type that is used by the algorithm.
     1246  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
    12481247  /// does not observe the DFS events. If you want to observe the DFS
    12491248  /// events, you should implement your own visitor class.
    1250   /// \tparam _Traits Traits class to set various data types used by the
     1249  /// \tparam TR Traits class to set various data types used by the
    12511250  /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
     1251  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    12531252  /// See \ref DfsVisitDefaultTraits for the documentation of
    12541253  /// a DFS visit traits class.
    12551254#ifdef DOXYGEN
    1256   template <typename _Digraph, typename _Visitor, typename _Traits>
     1255  template <typename GR, typename VS, typename TR>
    12571256#else
    1258   template <typename _Digraph = ListDigraph,
    1259             typename _Visitor = DfsVisitor<_Digraph>,
    1260             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
     1257  template <typename GR = ListDigraph,
     1258            typename VS = DfsVisitor<GR>,
     1259            typename TR = DfsVisitDefaultTraits<GR> >
    12611260#endif
    12621261  class DfsVisit {
     
    12641263
    12651264    ///The traits class.
    1266     typedef _Traits Traits;
     1265    typedef TR Traits;
    12671266
    12681267    ///The type of the digraph the algorithm runs on.
     
    12701269
    12711270    ///The visitor type used by the algorithm.
    1272     typedef _Visitor Visitor;
     1271    typedef VS Visitor;
    12731272
    12741273    ///The type of the map that indicates which nodes are reached.
     
    13101309    typedef DfsVisit Create;
    13111310
    1312     /// \name Named template parameters
     1311    /// \name Named Template Parameters
    13131312
    13141313    ///@{
     
    13521351    ///
    13531352    /// Sets the map that indicates which nodes are reached.
    1354     /// If you don't use this function before calling \ref run(),
    1355     /// it will allocate one. The destructor deallocates this
    1356     /// automatically allocated map, of course.
     1353    /// If you don't use this function before calling \ref run(Node) "run()"
     1354    /// or \ref init(), an instance will be allocated automatically.
     1355    /// The destructor deallocates this automatically allocated map,
     1356    /// of course.
    13571357    /// \return <tt> (*this) </tt>
    13581358    DfsVisit &reachedMap(ReachedMap &m) {
     
    13671367  public:
    13681368
    1369     /// \name Execution control
    1370     /// The simplest way to execute the algorithm is to use
    1371     /// one of the member functions called \ref lemon::DfsVisit::run()
    1372     /// "run()".
    1373     /// \n
    1374     /// If you need more control on the execution, first you must call
    1375     /// \ref lemon::DfsVisit::init() "init()", then you can add several
    1376     /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
    1377     /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
    1378     /// actual path computation.
     1369    /// \name Execution Control
     1370    /// The simplest way to execute the DFS algorithm is to use one of the
     1371    /// member functions called \ref run(Node) "run()".\n
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
     1374    /// and perform the actual computation with \ref start().
     1375    /// This procedure can be repeated if there are nodes that have not
     1376    /// been reached.
    13791377
    13801378    /// @{
     
    13921390    }
    13931391
    1394     ///Adds a new source node.
    1395 
    1396     ///Adds a new source node to the set of nodes to be processed.
    1397     ///
    1398     ///\pre The stack must be empty. (Otherwise the algorithm gives
    1399     ///false results.)
    1400     ///
    1401     ///\warning Distances will be wrong (or at least strange) in case of
    1402     ///multiple sources.
     1392    /// \brief Adds a new source node.
     1393    ///
     1394    /// Adds a new source node to the set of nodes to be processed.
     1395    ///
     1396    /// \pre The stack must be empty. Otherwise the algorithm gives
     1397    /// wrong results. (One of the outgoing arcs of all the source nodes
     1398    /// except for the last one will not be visited and distances will
     1399    /// also be wrong.)
    14031400    void addSource(Node s)
    14041401    {
     
    14141411          } else {
    14151412            _visitor->leave(s);
     1413            _visitor->stop(s);
    14161414          }
    14171415        }
     
    15901588    ///
    15911589    /// The algorithm computes
    1592     /// - the %DFS tree,
    1593     /// - the distance of each node from the root in the %DFS tree.
     1590    /// - the %DFS tree (forest),
     1591    /// - the distance of each node from the root(s) in the %DFS tree.
    15941592    ///
    15951593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16161614
    16171615    /// \name Query Functions
    1618     /// The result of the %DFS algorithm can be obtained using these
     1616    /// The results of the DFS algorithm can be obtained using these
    16191617    /// functions.\n
    1620     /// Either \ref lemon::DfsVisit::run() "run()" or
    1621     /// \ref lemon::DfsVisit::start() "start()" must be called before
    1622     /// using them.
     1618    /// Either \ref run(Node) "run()" or \ref start() should be called
     1619    /// before using them.
     1620
    16231621    ///@{
    16241622
    1625     /// \brief Checks if a node is reachable from the root(s).
    1626     ///
    1627     /// Returns \c true if \c v is reachable from the root(s).
    1628     /// \pre Either \ref run() or \ref start()
     1623    /// \brief Checks if a node is reached from the root(s).
     1624    ///
     1625    /// Returns \c true if \c v is reached from the root(s).
     1626    ///
     1627    /// \pre Either \ref run(Node) "run()" or \ref init()
    16291628    /// must be called before using this function.
    1630     bool reached(Node v) { return (*_reached)[v]; }
     1629    bool reached(Node v) const { return (*_reached)[v]; }
    16311630
    16321631    ///@}
  • lemon/dijkstra.h

    r412 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3939  /// This operation traits class defines all computational operations and
    4040  /// constants which are used in the Dijkstra algorithm.
    41   template <typename Value>
     41  template <typename V>
    4242  struct DijkstraDefaultOperationTraits {
     43    /// \e
     44    typedef V Value;
    4345    /// \brief Gives back the zero value of the type.
    4446    static Value zero() {
     
    5961  ///Default traits class of Dijkstra class.
    6062  ///\tparam GR The type of the digraph.
    61   ///\tparam LM The type of the length map.
    62   template<class GR, class LM>
     63  ///\tparam LEN The type of the length map.
     64  template<typename GR, typename LEN>
    6365  struct DijkstraDefaultTraits
    6466  {
     
    7072    ///The type of the map that stores the arc lengths.
    7173    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    72     typedef LM LengthMap;
     74    typedef LEN LengthMap;
    7375    ///The type of the length of the arcs.
    74     typedef typename LM::Value Value;
    75 
    76     /// Operation traits for Dijkstra algorithm.
     76    typedef typename LEN::Value Value;
     77
     78    /// Operation traits for %Dijkstra algorithm.
    7779
    7880    /// This class defines the operations that are used in the algorithm.
     
    8587    /// Usually it is \c Digraph::NodeMap<int>.
    8688    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    87     ///Instantiates a \ref HeapCrossRef.
     89    ///Instantiates a \c HeapCrossRef.
    8890
    8991    ///This function instantiates a \ref HeapCrossRef.
     
    9597    }
    9698
    97     ///The heap type used by the Dijkstra algorithm.
     99    ///The heap type used by the %Dijkstra algorithm.
    98100
    99101    ///The heap type used by the Dijkstra algorithm.
     
    101103    ///\sa BinHeap
    102104    ///\sa Dijkstra
    103     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    104     ///Instantiates a \ref Heap.
     105    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
     106    ///Instantiates a \c Heap.
    105107
    106108    ///This function instantiates a \ref Heap.
     
    117119    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    118120    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    119     ///Instantiates a PredMap.
    120 
    121     ///This function instantiates a PredMap.
     121    ///Instantiates a \c PredMap.
     122
     123    ///This function instantiates a \ref PredMap.
    122124    ///\param g is the digraph, to which we would like to define the
    123     ///PredMap.
     125    ///\ref PredMap.
    124126    static PredMap *createPredMap(const Digraph &g)
    125127    {
     
    133135    ///By default it is a NullMap.
    134136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    135     ///Instantiates a ProcessedMap.
    136 
    137     ///This function instantiates a ProcessedMap.
     137    ///Instantiates a \c ProcessedMap.
     138
     139    ///This function instantiates a \ref ProcessedMap.
    138140    ///\param g is the digraph, to which
    139     ///we would like to define the ProcessedMap
     141    ///we would like to define the \ref ProcessedMap.
    140142#ifdef DOXYGEN
    141143    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    151153    ///The type of the map that stores the distances of the nodes.
    152154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    153     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    154     ///Instantiates a DistMap.
    155 
    156     ///This function instantiates a DistMap.
     155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
     156    ///Instantiates a \c DistMap.
     157
     158    ///This function instantiates a \ref DistMap.
    157159    ///\param g is the digraph, to which we would like to define
    158     ///the DistMap
     160    ///the \ref DistMap.
    159161    static DistMap *createDistMap(const Digraph &g)
    160162    {
     
    180182  ///
    181183  ///\tparam GR The type of the digraph the algorithm runs on.
    182   ///The default value is \ref ListDigraph.
    183   ///The value of GR is not used directly by \ref Dijkstra, it is only
    184   ///passed to \ref DijkstraDefaultTraits.
    185   ///\tparam LM A readable arc map that determines the lengths of the
    186   ///arcs. It is read once for each arc, so the map may involve in
     184  ///The default type is \ref ListDigraph.
     185  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
     186  ///the lengths of the arcs.
     187  ///It is read once for each arc, so the map may involve in
    187188  ///relatively time consuming process to compute the arc lengths if
    188189  ///it is necessary. The default map type is \ref
    189   ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    190   ///The value of LM is not used directly by \ref Dijkstra, it is only
    191   ///passed to \ref DijkstraDefaultTraits.
    192   ///\tparam TR Traits class to set various data types used by the algorithm.
    193   ///The default traits class is \ref DijkstraDefaultTraits
    194   ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    195   ///for the documentation of a Dijkstra traits class.
     190  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    196191#ifdef DOXYGEN
    197   template <typename GR, typename LM, typename TR>
     192  template <typename GR, typename LEN, typename TR>
    198193#else
    199194  template <typename GR=ListDigraph,
    200             typename LM=typename GR::template ArcMap<int>,
    201             typename TR=DijkstraDefaultTraits<GR,LM> >
     195            typename LEN=typename GR::template ArcMap<int>,
     196            typename TR=DijkstraDefaultTraits<GR,LEN> >
    202197#endif
    203198  class Dijkstra {
     
    224219    ///The heap type used by the algorithm.
    225220    typedef typename TR::Heap Heap;
    226     ///The operation traits class.
     221    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
     222    ///of the algorithm.
    227223    typedef typename TR::OperationTraits OperationTraits;
    228224
    229     ///The traits class.
     225    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    230226    typedef TR Traits;
    231227
     
    240236    const Digraph *G;
    241237    //Pointer to the length map.
    242     const LengthMap *length;
     238    const LengthMap *_length;
    243239    //Pointer to the map of predecessors arcs.
    244240    PredMap *_pred;
     
    305301    };
    306302    ///\brief \ref named-templ-param "Named parameter" for setting
    307     ///PredMap type.
     303    ///\c PredMap type.
    308304    ///
    309305    ///\ref named-templ-param "Named parameter" for setting
    310     ///PredMap type.
     306    ///\c PredMap type.
     307    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    311308    template <class T>
    312309    struct SetPredMap
     
    325322    };
    326323    ///\brief \ref named-templ-param "Named parameter" for setting
    327     ///DistMap type.
     324    ///\c DistMap type.
    328325    ///
    329326    ///\ref named-templ-param "Named parameter" for setting
    330     ///DistMap type.
     327    ///\c DistMap type.
     328    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    331329    template <class T>
    332330    struct SetDistMap
     
    345343    };
    346344    ///\brief \ref named-templ-param "Named parameter" for setting
    347     ///ProcessedMap type.
     345    ///\c ProcessedMap type.
    348346    ///
    349347    ///\ref named-templ-param "Named parameter" for setting
    350     ///ProcessedMap type.
     348    ///\c ProcessedMap type.
     349    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    351350    template <class T>
    352351    struct SetProcessedMap
     
    363362    };
    364363    ///\brief \ref named-templ-param "Named parameter" for setting
    365     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     364    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    366365    ///
    367366    ///\ref named-templ-param "Named parameter" for setting
    368     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     367    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    369368    ///If you don't set it explicitly, it will be automatically allocated.
    370369    struct SetStandardProcessedMap
     
    389388    };
    390389    ///\brief \ref named-templ-param "Named parameter" for setting
    391     ///heap and cross reference type
     390    ///heap and cross reference types
    392391    ///
    393392    ///\ref named-templ-param "Named parameter" for setting heap and cross
    394     ///reference type.
     393    ///reference types. If this named parameter is used, then external
     394    ///heap and cross reference objects must be passed to the algorithm
     395    ///using the \ref heap() function before calling \ref run(Node) "run()"
     396    ///or \ref init().
     397    ///\sa SetStandardHeap
    395398    template <class H, class CR = typename Digraph::template NodeMap<int> >
    396399    struct SetHeap
     
    412415    };
    413416    ///\brief \ref named-templ-param "Named parameter" for setting
    414     ///heap and cross reference type with automatic allocation
     417    ///heap and cross reference types with automatic allocation
    415418    ///
    416419    ///\ref named-templ-param "Named parameter" for setting heap and cross
    417     ///reference type. It can allocate the heap and the cross reference
    418     ///object if the cross reference's constructor waits for the digraph as
    419     ///parameter and the heap's constructor waits for the cross reference.
     420    ///reference types with automatic allocation.
     421    ///They should have standard constructor interfaces to be able to
     422    ///automatically created by the algorithm (i.e. the digraph should be
     423    ///passed to the constructor of the cross reference and the cross
     424    ///reference should be passed to the constructor of the heap).
     425    ///However external heap and cross reference objects could also be
     426    ///passed to the algorithm using the \ref heap() function before
     427    ///calling \ref run(Node) "run()" or \ref init().
     428    ///\sa SetHeap
    420429    template <class H, class CR = typename Digraph::template NodeMap<int> >
    421430    struct SetStandardHeap
     
    434443    ///
    435444    ///\ref named-templ-param "Named parameter" for setting
    436     ///\ref OperationTraits type.
     445    ///\c OperationTraits type.
    437446    template <class T>
    438447    struct SetOperationTraits
     
    453462
    454463    ///Constructor.
    455     ///\param _g The digraph the algorithm runs on.
    456     ///\param _length The length map used by the algorithm.
    457     Dijkstra(const Digraph& _g, const LengthMap& _length) :
    458       G(&_g), length(&_length),
     464    ///\param g The digraph the algorithm runs on.
     465    ///\param length The length map used by the algorithm.
     466    Dijkstra(const Digraph& g, const LengthMap& length) :
     467      G(&g), _length(&length),
    459468      _pred(NULL), local_pred(false),
    460469      _dist(NULL), local_dist(false),
     
    480489    Dijkstra &lengthMap(const LengthMap &m)
    481490    {
    482       length = &m;
     491      _length = &m;
    483492      return *this;
    484493    }
     
    487496
    488497    ///Sets the map that stores the predecessor arcs.
    489     ///If you don't use this function before calling \ref run(),
    490     ///it will allocate one. The destructor deallocates this
    491     ///automatically allocated map, of course.
     498    ///If you don't use this function before calling \ref run(Node) "run()"
     499    ///or \ref init(), an instance will be allocated automatically.
     500    ///The destructor deallocates this automatically allocated map,
     501    ///of course.
    492502    ///\return <tt> (*this) </tt>
    493503    Dijkstra &predMap(PredMap &m)
     
    504514
    505515    ///Sets the map that indicates which nodes are processed.
    506     ///If you don't use this function before calling \ref run(),
    507     ///it will allocate one. The destructor deallocates this
    508     ///automatically allocated map, of course.
     516    ///If you don't use this function before calling \ref run(Node) "run()"
     517    ///or \ref init(), an instance will be allocated automatically.
     518    ///The destructor deallocates this automatically allocated map,
     519    ///of course.
    509520    ///\return <tt> (*this) </tt>
    510521    Dijkstra &processedMap(ProcessedMap &m)
     
    522533    ///Sets the map that stores the distances of the nodes calculated by the
    523534    ///algorithm.
    524     ///If you don't use this function before calling \ref run(),
    525     ///it will allocate one. The destructor deallocates this
    526     ///automatically allocated map, of course.
     535    ///If you don't use this function before calling \ref run(Node) "run()"
     536    ///or \ref init(), an instance will be allocated automatically.
     537    ///The destructor deallocates this automatically allocated map,
     538    ///of course.
    527539    ///\return <tt> (*this) </tt>
    528540    Dijkstra &distMap(DistMap &m)
     
    539551
    540552    ///Sets the heap and the cross reference used by algorithm.
    541     ///If you don't use this function before calling \ref run(),
    542     ///it will allocate one. The destructor deallocates this
    543     ///automatically allocated heap and cross reference, of course.
     553    ///If you don't use this function before calling \ref run(Node) "run()"
     554    ///or \ref init(), heap and cross reference instances will be
     555    ///allocated automatically.
     556    ///The destructor deallocates these automatically allocated objects,
     557    ///of course.
    544558    ///\return <tt> (*this) </tt>
    545559    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
     
    568582  public:
    569583
    570     ///\name Execution control
    571     ///The simplest way to execute the algorithm is to use one of the
    572     ///member functions called \ref lemon::Dijkstra::run() "run()".
    573     ///\n
    574     ///If you need more control on the execution, first you must call
    575     ///\ref lemon::Dijkstra::init() "init()", then you can add several
    576     ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
    577     ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
    578     ///actual path computation.
     584    ///\name Execution Control
     585    ///The simplest way to execute the %Dijkstra algorithm is to use
     586    ///one of the member functions called \ref run(Node) "run()".\n
     587    ///If you need more control on the execution, first you have to call
     588    ///\ref init(), then you can add several source nodes with
     589    ///\ref addSource(). Finally the actual path computation can be
     590    ///performed with one of the \ref start() functions.
    579591
    580592    ///@{
    581593
     594    ///\brief Initializes the internal data structures.
     595    ///
    582596    ///Initializes the internal data structures.
    583 
    584     ///Initializes the internal data structures.
    585     ///
    586597    void init()
    587598    {
     
    631642        switch(_heap->state(w)) {
    632643        case Heap::PRE_HEAP:
    633           _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
     644          _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
    634645          _pred->set(w,e);
    635646          break;
    636647        case Heap::IN_HEAP:
    637648          {
    638             Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
     649            Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
    639650            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
    640651              _heap->decrease(w, newvalue);
     
    659670    }
    660671
    661     ///\brief Returns \c false if there are nodes
    662     ///to be processed.
    663     ///
    664     ///Returns \c false if there are nodes
    665     ///to be processed in the priority heap.
     672    ///Returns \c false if there are nodes to be processed.
     673
     674    ///Returns \c false if there are nodes to be processed
     675    ///in the priority heap.
    666676    bool emptyQueue() const { return _heap->empty(); }
    667677
    668     ///Returns the number of the nodes to be processed in the priority heap
    669 
    670     ///Returns the number of the nodes to be processed in the priority heap.
    671     ///
     678    ///Returns the number of the nodes to be processed.
     679
     680    ///Returns the number of the nodes to be processed
     681    ///in the priority heap.
    672682    int queueSize() const { return _heap->size(); }
    673683
     
    790800
    791801    ///\name Query Functions
    792     ///The result of the %Dijkstra algorithm can be obtained using these
     802    ///The results of the %Dijkstra algorithm can be obtained using these
    793803    ///functions.\n
    794     ///Either \ref lemon::Dijkstra::run() "run()" or
    795     ///\ref lemon::Dijkstra::start() "start()" must be called before
    796     ///using them.
     804    ///Either \ref run(Node) "run()" or \ref start() should be called
     805    ///before using them.
    797806
    798807    ///@{
     
    802811    ///Returns the shortest path to a node.
    803812    ///
    804     ///\warning \c t should be reachable from the root(s).
    805     ///
    806     ///\pre Either \ref run() or \ref start() must be called before
    807     ///using this function.
     813    ///\warning \c t should be reached from the root(s).
     814    ///
     815    ///\pre Either \ref run(Node) "run()" or \ref init()
     816    ///must be called before using this function.
    808817    Path path(Node t) const { return Path(*G, *_pred, t); }
    809818
     
    812821    ///Returns the distance of a node from the root(s).
    813822    ///
    814     ///\warning If node \c v is not reachable from the root(s), then
     823    ///\warning If node \c v is not reached from the root(s), then
    815824    ///the return value of this function is undefined.
    816825    ///
    817     ///\pre Either \ref run() or \ref start() must be called before
    818     ///using this function.
     826    ///\pre Either \ref run(Node) "run()" or \ref init()
     827    ///must be called before using this function.
    819828    Value dist(Node v) const { return (*_dist)[v]; }
    820829
     
    823832    ///This function returns the 'previous arc' of the shortest path
    824833    ///tree for the node \c v, i.e. it returns the last arc of a
    825     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
    826     ///is not reachable from the root(s) or if \c v is a root.
     834    ///shortest path from a root to \c v. It is \c INVALID if \c v
     835    ///is not reached from the root(s) or if \c v is a root.
    827836    ///
    828837    ///The shortest path tree used here is equal to the shortest path
    829838    ///tree used in \ref predNode().
    830839    ///
    831     ///\pre Either \ref run() or \ref start() must be called before
    832     ///using this function.
     840    ///\pre Either \ref run(Node) "run()" or \ref init()
     841    ///must be called before using this function.
    833842    Arc predArc(Node v) const { return (*_pred)[v]; }
    834843
     
    837846    ///This function returns the 'previous node' of the shortest path
    838847    ///tree for the node \c v, i.e. it returns the last but one node
    839     ///from a shortest path from the root(s) to \c v. It is \c INVALID
    840     ///if \c v is not reachable from the root(s) or if \c v is a root.
     848    ///from a shortest path from a root to \c v. It is \c INVALID
     849    ///if \c v is not reached from the root(s) or if \c v is a root.
    841850    ///
    842851    ///The shortest path tree used here is equal to the shortest path
    843852    ///tree used in \ref predArc().
    844853    ///
    845     ///\pre Either \ref run() or \ref start() must be called before
    846     ///using this function.
     854    ///\pre Either \ref run(Node) "run()" or \ref init()
     855    ///must be called before using this function.
    847856    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    848857                                  G->source((*_pred)[v]); }
     
    854863    ///of the nodes calculated by the algorithm.
    855864    ///
    856     ///\pre Either \ref run() or \ref init()
     865    ///\pre Either \ref run(Node) "run()" or \ref init()
    857866    ///must be called before using this function.
    858867    const DistMap &distMap() const { return *_dist;}
     
    864873    ///arcs, which form the shortest path tree.
    865874    ///
    866     ///\pre Either \ref run() or \ref init()
     875    ///\pre Either \ref run(Node) "run()" or \ref init()
    867876    ///must be called before using this function.
    868877    const PredMap &predMap() const { return *_pred;}
    869878
    870     ///Checks if a node is reachable from the root(s).
    871 
    872     ///Returns \c true if \c v is reachable from the root(s).
    873     ///\pre Either \ref run() or \ref start()
     879    ///Checks if a node is reached from the root(s).
     880
     881    ///Returns \c true if \c v is reached from the root(s).
     882    ///
     883    ///\pre Either \ref run(Node) "run()" or \ref init()
    874884    ///must be called before using this function.
    875885    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
     
    880890    ///Returns \c true if \c v is processed, i.e. the shortest
    881891    ///path to \c v has already found.
    882     ///\pre Either \ref run() or \ref init()
     892    ///
     893    ///\pre Either \ref run(Node) "run()" or \ref init()
    883894    ///must be called before using this function.
    884895    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
     
    889900    ///Returns the current distance of a node from the root(s).
    890901    ///It may be decreased in the following processes.
    891     ///\pre Either \ref run() or \ref init()
     902    ///
     903    ///\pre Either \ref run(Node) "run()" or \ref init()
    892904    ///must be called before using this function and
    893905    ///node \c v must be reached but not necessarily processed.
     
    904916  ///Default traits class of dijkstra() function.
    905917  ///\tparam GR The type of the digraph.
    906   ///\tparam LM The type of the length map.
    907   template<class GR, class LM>
     918  ///\tparam LEN The type of the length map.
     919  template<class GR, class LEN>
    908920  struct DijkstraWizardDefaultTraits
    909921  {
     
    914926    ///The type of the map that stores the arc lengths.
    915927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    916     typedef LM LengthMap;
     928    typedef LEN LengthMap;
    917929    ///The type of the length of the arcs.
    918     typedef typename LM::Value Value;
     930    typedef typename LEN::Value Value;
    919931
    920932    /// Operation traits for Dijkstra algorithm.
     
    9981010    ///The type of the map that stores the distances of the nodes.
    9991011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1000     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     1012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10011013    ///Instantiates a DistMap.
    10021014
     
    10241036  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10251037  /// \ref DijkstraWizard class.
    1026   template<class GR,class LM>
    1027   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
     1038  template<typename GR, typename LEN>
     1039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
    10281040  {
    1029     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
     1041    typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
    10301042  protected:
    10311043    //The type of the nodes in the digraph.
     
    10611073    /// \param g The digraph the algorithm runs on.
    10621074    /// \param l The length map.
    1063     DijkstraWizardBase(const GR &g,const LM &l) :
     1075    DijkstraWizardBase(const GR &g,const LEN &l) :
    10641076      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    1065       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
     1077      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
    10661078      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
    10671079
     
    10721084  /// This auxiliary class is created to implement the
    10731085  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
    1074   /// It does not have own \ref run() method, it uses the functions
    1075   /// and features of the plain \ref Dijkstra.
     1086  /// It does not have own \ref run(Node) "run()" method, it uses the
     1087  /// functions and features of the plain \ref Dijkstra.
    10761088  ///
    10771089  /// This class should only be used through the \ref dijkstra() function,
     
    12681280  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12691281  ///\endcode
    1270   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     1282  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
    12711283  ///to the end of the parameter list.
    12721284  ///\sa DijkstraWizard
    12731285  ///\sa Dijkstra
    1274   template<class GR, class LM>
    1275   DijkstraWizard<DijkstraWizardBase<GR,LM> >
    1276   dijkstra(const GR &digraph, const LM &length)
     1286  template<typename GR, typename LEN>
     1287  DijkstraWizard<DijkstraWizardBase<GR,LEN> >
     1288  dijkstra(const GR &digraph, const LEN &length)
    12771289  {
    1278     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
     1290    return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
    12791291  }
    12801292
  • lemon/dim2.h

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

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

    r511 r606  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6565///Default traits class of \ref GraphToEps.
    6666///
    67 ///\c G is the type of the underlying graph.
    68 template<class G>
     67///\param GR is the type of the underlying graph.
     68template<class GR>
    6969struct DefaultGraphToEpsTraits
    7070{
    71   typedef G Graph;
     71  typedef GR Graph;
    7272  typedef typename Graph::Node Node;
    7373  typedef typename Graph::NodeIt NodeIt;
     
    140140
    141141  ///Constructor
    142   ///\param _g  Reference to the graph to be printed.
    143   ///\param _os Reference to the output stream.
    144   ///\param _os Reference to the output stream.
     142  ///\param gr  Reference to the graph to be printed.
     143  ///\param ost Reference to the output stream.
    145144  ///By default it is <tt>std::cout</tt>.
    146   ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
     145  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147146  ///will be explicitly deallocated by the destructor.
    148   DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
    149                           bool _pros=false) :
    150     g(_g), os(_os),
     147  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,
     148                          bool pros = false) :
     149    g(gr), os(ost),
    151150    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
    152151    _nodeColors(WHITE), _arcColors(BLACK),
     
    159158    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
    160159    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
    161     _undirected(lemon::UndirectedTagIndicator<G>::value),
    162     _pleaseRemoveOsStream(_pros), _scaleToA4(false),
     160    _undirected(lemon::UndirectedTagIndicator<GR>::value),
     161    _pleaseRemoveOsStream(pros), _scaleToA4(false),
    163162    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
    164163    _autoNodeScale(false),
     
    11351134///to the end of the parameter list.
    11361135///\sa GraphToEps
    1137 ///\sa graphToEps(G &g, const char *file_name)
    1138 template<class G>
    1139 GraphToEps<DefaultGraphToEpsTraits<G> >
    1140 graphToEps(G &g, std::ostream& os=std::cout)
     1136///\sa graphToEps(GR &g, const char *file_name)
     1137template<class GR>
     1138GraphToEps<DefaultGraphToEpsTraits<GR> >
     1139graphToEps(GR &g, std::ostream& os=std::cout)
    11411140{
    11421141  return
    1143     GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
     1142    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));
    11441143}
    11451144
     
    11481147///\ingroup eps_io
    11491148///This function does the same as
    1150 ///\ref graphToEps(G &g,std::ostream& os)
     1149///\ref graphToEps(GR &g,std::ostream& os)
    1151