COIN-OR::LEMON - Graph Library

Changes in / [336:052cecabcb71:337:560e4b6d020d] in lemon-main


Ignore:
Files:
8 added
1 deleted
66 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r249 r298  
    3030syntax: regexp
    3131(.*/)?\#[^/]*\#$
     32(.*/)?\.\#[^/]*$
    3233^doc/html/.*
    3334^doc/.*\.tag
  • CMakeLists.txt

    r236 r274  
    11CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
    22
    3 #EXECUTE_PROCESS(
    4 #  COMMAND hg id -i
    5 #  OUTPUT_VARIABLE HG_REVISION
    6 #  OUTPUT_STRIP_TRAILING_WHITESPACE)
    7 
    83SET(PROJECT_NAME "LEMON")
    9 SET(PROJECT_VERSION_MAJOR "0")
    10 SET(PROJECT_VERSION_MINOR "99")
    11 SET(PROJECT_VERSION_PATCH "0")
    12 SET(PROJECT_VERSION
    13   "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
     4SET(PROJECT_VERSION "hg-tip" CACHE STRING "The version string.")
    145
    156PROJECT(${PROJECT_NAME})
     
    4031  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
    4132
    42   SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})
    43   SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})
    44   SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})
    4533  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
    4634
    4735  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
    48     "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")
     36    "${PROJECT_NAME} ${PROJECT_VERSION}")
    4937  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
    50     "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
     38    "${PROJECT_NAME} ${PROJECT_VERSION}")
    5139
    5240  # Variables to generate a component-based installer.
  • INSTALL

    r245 r318  
    22=========================
    33
    4    Since you are reading this I assume you already obtained one of the release
     4Since you are reading this I assume you already obtained one of the release
    55tarballs and successfully extracted it. The latest version of LEMON is
    66available at our web page (http://lemon.cs.elte.hu/).
    77
    8    In order to install LEMON from the extracted source tarball you have to
     8In order to install LEMON from the extracted source tarball you have to
    99issue the following commands:
    1010
     
    2222
    2323      This command compiles the non-template part of LEMON into libemon.a
    24       file. It also compiles the programs in the tools, benchmark and demo
    25       subdirectories when enabled.
     24      file. It also compiles the programs in the tools and demo subdirectories
     25      when enabled.
    2626
    2727   4. `make check'
     
    5050===============================
    5151
    52    In step 2 you can customize the actions of configure by setting variables
     52In step 2 you can customize the actions of configure by setting variables
    5353and passing options to it. This can be done like this:
    5454`./configure [OPTION]... [VARIABLE=VALUE]...'
    5555
    56    Below you will find some useful variables and options (see
    57 `./configure --help' for more):
     56Below you will find some useful variables and options (see `./configure --help'
     57for more):
    5858
    5959CXX='comp'
     
    7777
    7878   Do not build the examples in the demo subdirectory (default).
    79 
    80 --enable-benchmark
    81 
    82    Build the programs in the benchmark subdirectory.
    83 
    84 --disable-benchmark
    85 
    86    Do not build the programs in the benchmark subdirectory (default).
    8779
    8880--enable-tools
  • Makefile.am

    r227 r321  
    55
    66EXTRA_DIST = \
     7        AUTHORS \
    78        LICENSE \
    89        m4/lx_check_cplex.m4 \
     
    2526bin_PROGRAMS =
    2627check_PROGRAMS =
     28dist_bin_SCRIPTS =
    2729TESTS =
    2830XFAIL_TESTS =
     
    3234include doc/Makefile.am
    3335include demo/Makefile.am
    34 include benchmark/Makefile.am
    3536include tools/Makefile.am
    3637
  • NEWS

    r5 r322  
     12008-10-13 Version 1.0 released
     2
     3        This is the first stable release of LEMON. Compared to the 0.x
     4        release series, it features a considerably smaller but more
     5        matured set of tools. The API has also completely revised and
     6        changed in several places.
     7
     8        * The major name changes compared to the 0.x series (see the
     9          Migration Guide in the doc for more details)
     10          * Graph -> Digraph, UGraph -> Graph
     11          * Edge -> Arc, UEdge -> Edge
     12          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
     13        * Other improvements
     14          * Better documentation
     15          * Reviewed and cleaned up codebase
     16          * CMake based build system (along with the autotools based one)
     17        * Contents of the library (ported from 0.x)
     18          * Algorithms
     19            * breadth-first search (bfs.h)
     20            * depth-first search (dfs.h)
     21            * Dijkstra's algorithm (dijkstra.h)
     22            * Kruskal's algorithm (kruskal.h)
     23          * Data structures
     24            * graph data structures (list_graph.h, smart_graph.h)
     25            * path data structures (path.h)
     26            * binary heap data structure (bin_heap.h)
     27            * union-find data structures (unionfind.h)
     28            * miscellaneous property maps (maps.h)
     29            * two dimensional vector and bounding box (dim2.h)
     30          * Concepts
     31            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
     32              concepts/graph_components.h)
     33            * concepts for other structures (concepts/heap.h, concepts/maps.h,
     34              concepts/path.h)
     35          * Tools
     36            * Mersenne twister random number generator (random.h)
     37            * tools for measuring cpu and wall clock time (time_measure.h)
     38            * tools for counting steps and events (counter.h)
     39            * tool for parsing command line arguments (arg_parser.h)
     40            * tool for visualizing graphs (graph_to_eps.h)
     41            * tools for reading and writing data in LEMON Graph Format
     42              (lgf_reader.h, lgf_writer.h)
     43            * tools to handle the anomalies of calculations with
     44              floating point numbers (tolerance.h)
     45            * tools to manage RGB colors (color.h)
     46          * Infrastructure
     47            * extended assertion handling (assert.h)
     48            * exception classes and error handling (error.h)
     49            * concept checking (concept_check.h)
     50            * commonly used mathematical constants (math.h)
  • README

    r246 r318  
    3636test/
    3737
    38    Contains programs to check the integrity and correctness of LEMON.
    39 
    40 benchmark/
    41  
    42    Contains programs for measuring the performance of algorithms.
     38   Programs to check the integrity and correctness of LEMON.
    4339
    4440tools/
  • configure.ac

    r236 r310  
    22
    33dnl Version information.
    4 m4_define([lemon_version_number], [])
     4m4_define([lemon_version_number],
     5        [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
     6dnl m4_define([lemon_version_number], [])
     7m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
    58m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
    6 m4_define([lemon_version], [ifelse(lemon_version_number(), [], [lemon_hg_revision()], [lemon_version_number()])])
     9m4_define([lemon_version], [ifelse(lemon_version_number(),
     10                           [],
     11                           [lemon_hg_path().lemon_hg_revision()],
     12                           [lemon_version_number()])])
    713
    814AC_PREREQ([2.59])
     
    1622lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    1723
     24dnl Do compilation tests using the C++ compiler.
     25AC_LANG([C++])
     26
    1827dnl Checks for programs.
    1928AC_PROG_CXX
     
    2635AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    2736
     37dnl Detect Intel compiler.
     38AC_MSG_CHECKING([whether we are using the Intel C++ compiler])
     39AC_COMPILE_IFELSE([#ifndef __INTEL_COMPILER
     40choke me
     41#endif], [ICC=[yes]], [ICC=[no]])
     42if test x"$ICC" = x"yes"; then
     43  AC_MSG_RESULT([yes])
     44else
     45  AC_MSG_RESULT([no])
     46fi
     47
    2848dnl Set custom compiler flags when using g++.
    29 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
     49if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
    3050  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"
    3151fi
    3252
    3353dnl Checks for libraries.
    34 LX_CHECK_GLPK
    35 LX_CHECK_CPLEX
    36 LX_CHECK_SOPLEX
     54#LX_CHECK_GLPK
     55#LX_CHECK_CPLEX
     56#LX_CHECK_SOPLEX
    3757
    3858dnl Disable/enable building the demo programs.
     
    6181fi
    6282AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
    63 
    64 dnl Disable/enable building the benchmarks.
    65 AC_ARG_ENABLE([benchmark],
    66 AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
    67 AS_HELP_STRING([--disable-benchmark], [do not build the benchmarks @<:@default@:>@]),
    68               [], [enable_benchmark=no])
    69 AC_MSG_CHECKING([whether to build the benchmarks])
    70 if test x"$enable_benchmark" != x"no"; then
    71   AC_MSG_RESULT([yes])
    72 else
    73   AC_MSG_RESULT([no])
    74 fi
    75 AM_CONDITIONAL([WANT_BENCHMARK], [test x"$enable_benchmark" != x"no"])
    7683
    7784dnl Checks for header files.
     
    109116echo C++ compiles flags............ : $CXXFLAGS
    110117echo
    111 echo GLPK support.................. : $lx_glpk_found
    112 echo CPLEX support................. : $lx_cplex_found
    113 echo SOPLEX support................ : $lx_soplex_found
    114 echo
    115 echo Build benchmarks.............. : $enable_benchmark
     118#echo GLPK support.................. : $lx_glpk_found
     119#echo CPLEX support................. : $lx_cplex_found
     120#echo SOPLEX support................ : $lx_soplex_found
     121#echo
    116122echo Build demo programs........... : $enable_demo
    117123echo Build additional tools........ : $enable_tools
  • demo/arg_parser_demo.cc

    r209 r311  
    2828
    2929using namespace lemon;
    30 int main(int argc, const char **argv)
     30int main(int argc, char **argv)
    3131{
    3232  // Initialize the argument parser
  • demo/graph_to_eps_demo.cc

    r220 r313  
    2727/// how to handle parallel egdes, how to change the properties (like
    2828/// color, shape, size, title etc.) of nodes and arcs individually
    29 /// using appropriate \ref maps-page "graph maps".
     29/// using appropriate graph maps.
    3030///
    3131/// \include graph_to_eps_demo.cc
  • demo/lgf_demo.cc

    r209 r294  
    4545
    4646  try {
    47     digraphReader("digraph.lgf", g). // read the directed graph into g
     47    digraphReader(g, "digraph.lgf"). // read the directed graph into g
    4848      arcMap("capacity", cap).       // read the 'capacity' arc map into cap
    4949      node("source", s).             // read 'source' node to s
    5050      node("target", t).             // read 'target' node to t
    5151      run();
    52   } catch (DataFormatError& error) { // check if there was any error
     52  } catch (Exception& error) { // check if there was any error
    5353    std::cerr << "Error: " << error.what() << std::endl;
    5454    return -1;
     
    6161  std::cout << "We can write it to the standard output:" << std::endl;
    6262
    63   digraphWriter(std::cout, g).     // write g to the standard output
     63  digraphWriter(g).                // write g to the standard output
    6464    arcMap("capacity", cap).       // write cap into 'capacity'
    6565    node("source", s).             // write s to 'source'
  • doc/Doxyfile.in

    r226 r316  
    1 # Doxyfile 1.5.5
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
     
    3434CPP_CLI_SUPPORT        = NO
    3535SIP_SUPPORT            = NO
     36IDL_PROPERTY_SUPPORT   = YES
    3637DISTRIBUTE_GROUP_DOC   = NO
    3738SUBGROUPING            = YES
    3839TYPEDEF_HIDES_STRUCT   = NO
     40SYMBOL_CACHE_SIZE      = 0
    3941#---------------------------------------------------------------------------
    4042# Build related configuration options
     
    6769SHOW_USED_FILES        = YES
    6870SHOW_DIRECTORIES       = YES
     71SHOW_FILES             = YES
     72SHOW_NAMESPACES        = YES
    6973FILE_VERSION_FILTER    =
     74LAYOUT_FILE            = DoxygenLayout.xml
    7075#---------------------------------------------------------------------------
    7176# configuration options related to warning and progress messages
     
    7681WARN_IF_DOC_ERROR      = YES
    7782WARN_NO_PARAMDOC       = NO
    78 WARN_FORMAT            = "$file:$line: $text  "
     83WARN_FORMAT            = "$file:$line: $text"
    7984WARN_LOGFILE           = doxygen.log
    8085#---------------------------------------------------------------------------
     
    134139HTML_STYLESHEET        =
    135140HTML_ALIGN_MEMBERS     = YES
    136 GENERATE_HTMLHELP      = NO
     141HTML_DYNAMIC_SECTIONS  = NO
    137142GENERATE_DOCSET        = NO
    138143DOCSET_FEEDNAME        = "Doxygen generated docs"
    139144DOCSET_BUNDLE_ID       = org.doxygen.Project
    140 HTML_DYNAMIC_SECTIONS  = NO
     145GENERATE_HTMLHELP      = NO
    141146CHM_FILE               =
    142147HHC_LOCATION           =
    143148GENERATE_CHI           = NO
     149CHM_INDEX_ENCODING     =
    144150BINARY_TOC             = NO
    145151TOC_EXPAND             = NO
     152GENERATE_QHP           = NO
     153QCH_FILE               =
     154QHP_NAMESPACE          = org.doxygen.Project
     155QHP_VIRTUAL_FOLDER     = doc
     156QHG_LOCATION           =
    146157DISABLE_INDEX          = NO
    147158ENUM_VALUES_PER_LINE   = 4
    148159GENERATE_TREEVIEW      = NO
    149160TREEVIEW_WIDTH         = 250
     161FORMULA_FONTSIZE       = 10
    150162#---------------------------------------------------------------------------
    151163# configuration options related to the LaTeX output
     
    222234# Configuration options related to the dot tool   
    223235#---------------------------------------------------------------------------
    224 CLASS_DIAGRAMS         = NO
     236CLASS_DIAGRAMS         = YES
    225237MSCGEN_PATH            =
    226238HIDE_UNDOC_RELATIONS   = YES
    227239HAVE_DOT               = YES
     240DOT_FONTNAME           = FreeSans
     241DOT_FONTSIZE           = 10
     242DOT_FONTPATH           =
    228243CLASS_GRAPH            = YES
    229244COLLABORATION_GRAPH    = NO
  • doc/Makefile.am

    r335 r337  
    11EXTRA_DIST += \
    22        doc/Doxyfile.in \
     3        doc/DoxygenLayout.xml \
    34        doc/coding_style.dox \
    45        doc/dirs.dox \
     
    78        doc/license.dox \
    89        doc/mainpage.dox \
     10        doc/migration.dox \
     11        doc/named-param.dox \
    912        doc/namespaces.dox \
    1013        doc/html \
  • doc/dirs.dox

    r209 r318  
    1919/**
    2020\dir demo
    21 \brief A collection of demo application.
     21\brief A collection of demo applications.
    2222
    23 This directory contains several simple demo application, mainly
     23This directory contains several simple demo applications, mainly
    2424for educational purposes.
    2525*/
     
    2929\brief Auxiliary (and the whole generated) documentation.
    3030
    31 Auxiliary (and the whole generated) documentation.
     31This directory contains some auxiliary pages and the whole generated
     32documentation.
    3233*/
    3334
     
    4243/**
    4344\dir tools
    44 \brief Some useful executables
     45\brief Some useful executables.
    4546
    4647This directory contains the sources of some useful complete executables.
    47 
    4848*/
    49 
    50 
    5149
    5250/**
    5351\dir lemon
    54 \brief Base include directory of LEMON
     52\brief Base include directory of LEMON.
    5553
    56 This is the base directory of lemon includes, so each include file must be
     54This is the base directory of LEMON includes, so each include file must be
    5755prefixed with this, e.g.
    5856\code
     
    6462/**
    6563\dir concepts
    66 \brief Concept descriptors and checking classes
     64\brief Concept descriptors and checking classes.
    6765
    68 This directory contains the concept descriptors and concept checkers. As a user
    69 you typically don't have to deal with these files.
     66This directory contains the concept descriptors and concept checking tools.
     67For more information see the \ref concept "Concepts" module.
    7068*/
    7169
    7270/**
    7371\dir bits
    74 \brief Implementation helper files
     72\brief Auxiliary tools for implementation.
    7573
    76 This directory contains some helper classes to implement graphs, maps and
    77 some other classes. As a user you typically don't have to deal with these
    78 files.
     74This directory contains some auxiliary classes for implementing graphs,
     75maps and some other classes.
     76As a user you typically don't have to deal with these files.
    7977*/
  • doc/groups.dox

    r236 r318  
    5555You are free to use the graph structure that fit your requirements
    5656the best, most graph algorithms and auxiliary data structures can be used
    57 with any graph structures.
     57with any graph structure.
     58
     59<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    5860*/
    5961
     
    7577This group describes the map structures implemented in LEMON.
    7678
    77 LEMON provides several special purpose maps that e.g. combine
     79LEMON provides several special purpose maps and map adaptors that e.g. combine
    7880new maps from existing ones.
     81
     82<b>See also:</b> \ref map_concepts "Map Concepts".
    7983*/
    8084
     
    8791values to the nodes and arcs of graphs.
    8892*/
    89 
    9093
    9194/**
     
    105108algorithms.  If a function type algorithm is called then the function
    106109type map adaptors can be used comfortable. For example let's see the
    107 usage of map adaptors with the \c digraphToEps() function.
     110usage of map adaptors with the \c graphToEps() function.
    108111\code
    109112  Color nodeColor(int deg) {
     
    119122  Digraph::NodeMap<int> degree_map(graph);
    120123
    121   digraphToEps(graph, "graph.eps")
     124  graphToEps(graph, "graph.eps")
    122125    .coords(coords).scaleToA4().undirected()
    123126    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
     
    125128\endcode
    126129The \c functorToMap() function makes an \c int to \c Color map from the
    127 \e nodeColor() function. The \c composeMap() compose the \e degree_map
     130\c nodeColor() function. The \c composeMap() compose the \c degree_map
    128131and the previously created map. The composed map is a proper function to
    129132get the color of each node.
     
    163166@defgroup paths Path Structures
    164167@ingroup datas
    165 \brief Path structures implemented in LEMON.
     168\brief %Path structures implemented in LEMON.
    166169
    167170This group describes the path structures implemented in LEMON.
     
    174177
    175178\sa lemon::concepts::Path
    176 
    177179*/
    178180
     
    186188*/
    187189
    188 
    189190/**
    190191@defgroup algs Algorithms
     
    202203
    203204This group describes the common graph search algorithms like
    204 Breadth-first search (Bfs) and Depth-first search (Dfs).
    205 */
    206 
    207 /**
    208 @defgroup shortest_path Shortest Path algorithms
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
     206*/
     207
     208/**
     209@defgroup shortest_path Shortest Path Algorithms
    209210@ingroup algs
    210211\brief Algorithms for finding shortest paths.
     
    214215
    215216/**
    216 @defgroup max_flow Maximum Flow algorithms
     217@defgroup max_flow Maximum Flow Algorithms
    217218@ingroup algs
    218219\brief Algorithms for finding maximum flows.
     
    242243provides functions to query the minimum cut, which is the dual linear
    243244programming problem of the maximum flow.
    244 
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow algorithms
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
    249249@ingroup algs
    250250
     
    256256
    257257/**
    258 @defgroup min_cut Minimum Cut algorithms
     258@defgroup min_cut Minimum Cut Algorithms
    259259@ingroup algs
    260260
     
    283283If you want to find minimum cut just between two distinict nodes,
    284284please see the \ref max_flow "Maximum Flow page".
    285 
    286 */
    287 
    288 /**
    289 @defgroup graph_prop Connectivity and other graph properties
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
    290289@ingroup algs
    291290\brief Algorithms for discovering the graph properties
     
    299298
    300299/**
    301 @defgroup planar Planarity embedding and drawing
     300@defgroup planar Planarity Embedding and Drawing
    302301@ingroup algs
    303302\brief Algorithms for planarity checking, embedding and drawing
     
    311310
    312311/**
    313 @defgroup matching Matching algorithms
     312@defgroup matching Matching Algorithms
    314313@ingroup algs
    315314\brief Algorithms for finding matchings in graphs and bipartite graphs.
     
    349348\image html bipartite_matching.png
    350349\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    351 
    352 */
    353 
    354 /**
    355 @defgroup spantree Minimum Spanning Tree algorithms
     350*/
     351
     352/**
     353@defgroup spantree Minimum Spanning Tree Algorithms
    356354@ingroup algs
    357355\brief Algorithms for finding a minimum cost spanning tree in a graph.
     
    361359*/
    362360
    363 
    364 /**
    365 @defgroup auxalg Auxiliary algorithms
     361/**
     362@defgroup auxalg Auxiliary Algorithms
    366363@ingroup algs
    367364\brief Auxiliary algorithms implemented in LEMON.
     
    372369
    373370/**
    374 @defgroup approx Approximation algorithms
     371@defgroup approx Approximation Algorithms
     372@ingroup algs
    375373\brief Approximation algorithms.
    376374
     
    386384This group describes some general optimization frameworks
    387385implemented in LEMON.
    388 
    389 */
    390 
    391 /**
    392 @defgroup lp_group Lp and Mip solvers
     386*/
     387
     388/**
     389@defgroup lp_group Lp and Mip Solvers
    393390@ingroup gen_opt_group
    394391\brief Lp and Mip solver interfaces for LEMON.
     
    397394various LP solvers could be used in the same manner with this
    398395interface.
    399 
    400 */
    401 
    402 /**
    403 @defgroup lp_utils Tools for Lp and Mip solvers
     396*/
     397
     398/**
     399@defgroup lp_utils Tools for Lp and Mip Solvers
    404400@ingroup lp_group
    405401\brief Helper tools to the Lp and Mip solvers.
     
    442438
    443439/**
    444 @defgroup timecount Time measuring and Counting
     440@defgroup timecount Time Measuring and Counting
    445441@ingroup misc
    446442\brief Simple tools for measuring the performance of algorithms.
     
    448444This group describes simple tools for measuring the performance
    449445of algorithms.
    450 */
    451 
    452 /**
    453 @defgroup graphbits Tools for Graph Implementation
    454 @ingroup utils
    455 \brief Tools to make it easier to create graphs.
    456 
    457 This group describes the tools that makes it easier to create graphs and
    458 the maps that dynamically update with the graph changes.
    459446*/
    460447
     
    472459
    473460This group describes the tools for importing and exporting graphs
    474 and graph related data. Now it supports the LEMON format, the
    475 \c DIMACS format and the encapsulated postscript (EPS) format.
     461and graph related data. Now it supports the \ref lgf-format
     462"LEMON Graph Format", the \c DIMACS format and the encapsulated
     463postscript (EPS) format.
    476464*/
    477465
     
    479467@defgroup lemon_io LEMON Input-Output
    480468@ingroup io_group
    481 \brief Reading and writing \ref lgf-format "LEMON Graph Format".
     469\brief Reading and writing LEMON Graph Format.
    482470
    483471This group describes methods for reading and writing
     
    486474
    487475/**
    488 @defgroup eps_io Postscript exporting
     476@defgroup eps_io Postscript Exporting
    489477@ingroup io_group
    490478\brief General \c EPS drawer and graph exporter
     
    494482*/
    495483
    496 
    497484/**
    498485@defgroup concept Concepts
     
    504491The purpose of the classes in this group is fourfold.
    505492
    506 - These classes contain the documentations of the concepts. In order
     493- These classes contain the documentations of the %concepts. In order
    507494  to avoid document multiplications, an implementation of a concept
    508495  simply refers to the corresponding concept class.
    509496
    510497- These classes declare every functions, <tt>typedef</tt>s etc. an
    511   implementation of the concepts should provide, however completely
     498  implementation of the %concepts should provide, however completely
    512499  without implementations and real data structures behind the
    513500  interface. On the other hand they should provide nothing else. All
     
    522509
    523510- Finally, They can serve as a skeleton of a new implementation of a concept.
    524 
    525 */
    526 
     511*/
    527512
    528513/**
     
    535520*/
    536521
    537 /* --- Unused group
    538 @defgroup experimental Experimental Structures and Algorithms
    539 This group describes some Experimental structures and algorithms.
    540 The stuff here is subject to change.
     522/**
     523@defgroup map_concepts Map Concepts
     524@ingroup concept
     525\brief Skeleton and concept checking classes for maps
     526
     527This group describes the skeletons and concept checking classes of maps.
    541528*/
    542529
  • doc/lgf.dox

    r236 r313  
    7979\endcode
    8080
    81 The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
     81The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
    8282also store the edge set of an undirected graph. In such case there is
    8383a conventional method for store arc maps in the file, if two columns
  • doc/mainpage.dox

    r209 r314  
    5151If you
    5252want to see how LEMON works, see
    53 some \ref demoprograms "demo programs"!
     53some \ref demoprograms "demo programs".
    5454
    5555If you know what you are looking for then try to find it under the
     
    5757section.
    5858
    59 
     59If you are a user of the old (0.x) series of LEMON, please check out the
     60\ref migration "Migration Guide" for the backward incompatibilities.
    6061*/
  • lemon/Makefile.am

    r334 r337  
    1313        lemon/random.cc
    1414
    15 
    16 lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    17 lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     16#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    1817
    1918lemon_HEADERS += \
     
    3837        lemon/maps.h \
    3938        lemon/math.h \
     39        lemon/max_matching.h \
    4040        lemon/path.h \
    4141        lemon/random.h \
  • lemon/arg_parser.cc

    r214 r311  
    2727  }
    2828
    29   ArgParser::ArgParser(int argc, const char **argv) :_argc(argc), _argv(argv),
    30                                                     _command_name(argv[0]) {
     29  ArgParser::ArgParser(int argc, const char * const *argv)
     30    :_argc(argc), _argv(argv), _command_name(argv[0]) {
    3131    funcOption("-help","Print a short help message",_showHelp,this);
    3232    synonym("help","-help");
    3333    synonym("h","-help");
    34 
    3534  }
    3635
  • lemon/arg_parser.h

    r214 r311  
    1717 */
    1818
    19 #ifndef LEMON_ARG_PARSER
    20 #define LEMON_ARG_PARSER
     19#ifndef LEMON_ARG_PARSER_H
     20#define LEMON_ARG_PARSER_H
    2121
    2222#include <vector>
     
    4747
    4848    int _argc;
    49     const char **_argv;
     49    const char * const *_argv;
    5050
    5151    enum OptType { UNKNOWN=0, BOOL=1, STRING=2, DOUBLE=3, INTEGER=4, FUNC=5 };
     
    120120
    121121    ///Constructor
    122     ArgParser(int argc, const char **argv);
     122    ArgParser(int argc, const char * const *argv);
    123123
    124124    ~ArgParser();
     
    311311    ///This is the type of the return value of ArgParser::operator[]().
    312312    ///It automatically converts to \c int, \c double, \c bool or
    313     ///\c std::string if the type of the option matches, otherwise it
    314     ///throws an exception (i.e. it performs runtime type checking).
     313    ///\c std::string if the type of the option matches, which is checked
     314    ///with an \ref LEMON_ASSERT "assertion" (i.e. it performs runtime
     315    ///type checking).
    315316    class RefType
    316317    {
     
    383384}
    384385
    385 #endif // LEMON_ARG_PARSER
     386#endif // LEMON_ARG_PARSER_H
  • lemon/assert.h

    r218 r290  
    2828namespace lemon {
    2929
    30   inline void assert_fail_log(const char *file, int line, const char *function,
    31                               const char *message, const char *assertion)
     30  inline void assert_fail_abort(const char *file, int line,
     31                                const char *function, const char* message,
     32                                const char *assertion)
    3233  {
    3334    std::cerr << file << ":" << line << ": ";
     
    3839      std::cerr << " (assertion '" << assertion << "' failed)";
    3940    std::cerr << std::endl;
    40   }
    41 
    42   inline void assert_fail_abort(const char *file, int line,
    43                                 const char *function, const char* message,
    44                                 const char *assertion)
    45   {
    46     assert_fail_log(file, line, function, message, assertion);
    4741    std::abort();
    4842  }
     
    6458
    6559#undef LEMON_ASSERT
    66 #undef LEMON_FIXME
    6760#undef LEMON_DEBUG
    6861
    69 #if (defined(LEMON_ASSERT_LOG) ? 1 : 0) +               \
    70   (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +               \
     62#if (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +               \
    7163  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
    7264#error "LEMON assertion system is not set properly"
    7365#endif
    7466
    75 #if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) +              \
    76      (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +            \
     67#if ((defined(LEMON_ASSERT_ABORT) ? 1 : 0) +            \
    7768     (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||     \
    7869     defined(LEMON_ENABLE_ASSERTS)) &&                  \
     
    8374
    8475
    85 #if defined LEMON_ASSERT_LOG
    86 #  undef LEMON_ASSERT_HANDLER
    87 #  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log
    88 #elif defined LEMON_ASSERT_ABORT
     76#if defined LEMON_ASSERT_ABORT
    8977#  undef LEMON_ASSERT_HANDLER
    9078#  define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort
     
    10896#  elif defined _MSC_VER
    10997#    define LEMON_FUNCTION_NAME (__FUNCSIG__)
     98#  elif __STDC_VERSION__ >= 199901L
     99#    define LEMON_FUNCTION_NAME (__func__)
    110100#  else
    111 #    define LEMON_FUNCTION_NAME (__func__)
     101#    define LEMON_FUNCTION_NAME ("<unknown>")
    112102#  endif
    113103#endif
     
    119109/// \brief Macro for assertion with customizable message
    120110///
    121 /// Macro for assertion with customizable message.  \param exp An
    122 /// expression that must be convertible to \c bool.  If it is \c
    123 /// false, then an assertion is raised. The concrete behaviour depends
    124 /// on the settings of the assertion system.  \param msg A <tt>const
    125 /// char*</tt> parameter, which can be used to provide information
    126 /// about the circumstances of the failed assertion.
     111/// Macro for assertion with customizable message.
     112/// \param exp An expression that must be convertible to \c bool.  If it is \c
     113/// false, then an assertion is raised. The concrete behaviour depends on the
     114/// settings of the assertion system.
     115/// \param msg A <tt>const char*</tt> parameter, which can be used to provide
     116/// information about the circumstances of the failed assertion.
    127117///
    128118/// The assertions are enabled in the default behaviour.
     
    138128/// The checking is also disabled when the standard macro \c NDEBUG is defined.
    139129///
    140 /// The LEMON assertion system has a wide range of customization
    141 /// properties. As a default behaviour the failed assertion prints a
    142 /// short log message to the standard error and aborts the execution.
    143 ///
    144 /// The following modes can be used in the assertion system:
    145 ///
    146 /// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
    147 ///   message to the standard error and continues the execution.
    148 /// - \c LEMON_ASSERT_ABORT This mode is similar to the \c
    149 ///   LEMON_ASSERT_LOG, but it aborts the program. It is the default
    150 ///   behaviour.
     130/// As a default behaviour the failed assertion prints a short log message to
     131/// the standard error and aborts the execution.
     132///
     133/// However, the following modes can be used in the assertion system:
     134/// - \c LEMON_ASSERT_ABORT The failed assertion prints a short log message to
     135///   the standard error and aborts the program. It is the default behaviour.
    151136/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler
    152137///   function.
     
    176161/// \ingroup exceptions
    177162///
    178 /// \brief Macro for mark not yet implemented features.
    179 ///
    180 /// Macro for mark not yet implemented features and outstanding bugs.
    181 /// It is close to be the shortcut of the following code:
    182 /// \code
    183 ///   LEMON_ASSERT(false, msg);
    184 /// \endcode
    185 ///
    186 /// \see LEMON_ASSERT
    187 #  define LEMON_FIXME(msg)                                              \
    188   (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \
    189                         ::lemon::_assert_bits::cstringify(msg),         \
    190                         static_cast<const char*>(0)))
    191 
    192 /// \ingroup exceptions
    193 ///
    194163/// \brief Macro for internal assertions
    195164///
     
    223192#  ifndef LEMON_ASSERT_HANDLER
    224193#    define LEMON_ASSERT(exp, msg)  (static_cast<void>(0))
    225 #    define LEMON_FIXME(msg) (static_cast<void>(0))
    226194#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))
    227195#  else
     
    232200                             ::lemon::_assert_bits::cstringify(msg),    \
    233201                             #exp), 0)))
    234 #    define LEMON_FIXME(msg)                                            \
    235        (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,   \
    236                              ::lemon::_assert_bits::cstringify(msg),    \
    237                              static_cast<const char*>(0)))
    238 
    239202#    if LEMON_ENABLE_DEBUG
    240203#      define LEMON_DEBUG(exp, msg)                                     \
  • lemon/bfs.h

    r252 r329  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/path.h>
    3132
    3233namespace lemon {
     
    4950    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5051    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    51     ///Instantiates a \ref PredMap.
    52 
    53     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap. 
    5455    ///\param g is the digraph, to which we would like to define the
    55     ///\ref PredMap.
    56     ///\todo The digraph alone may be insufficient to initialize
     56    ///PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
     
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a \ref ProcessedMap.
    69 
    70     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7170    ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7372#ifdef DOXYGEN
    7473    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8281    ///The type of the map that indicates which nodes are reached.
    8382
    84     ///The type of the map that indicates which nodes are reached.
    85     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8684    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a \ref ReachedMap.
    88 
    89     ///This function instantiates a \ref ReachedMap.
     85    ///Instantiates a ReachedMap.
     86
     87    ///This function instantiates a ReachedMap.
    9088    ///\param g is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
     89    ///we would like to define the ReachedMap.
    9290    static ReachedMap *createReachedMap(const Digraph &g)
    9391    {
     
    10098    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10199    typedef typename Digraph::template NodeMap<int> DistMap;
    102     ///Instantiates a \ref DistMap.
    103 
    104     ///This function instantiates a \ref DistMap.
     100    ///Instantiates a DistMap.
     101
     102    ///This function instantiates a DistMap.
    105103    ///\param g is the digraph, to which we would like to define the
    106     ///\ref DistMap.
     104    ///DistMap.
    107105    static DistMap *createDistMap(const Digraph &g)
    108106    {
     
    116114  ///This class provides an efficient implementation of the %BFS algorithm.
    117115  ///
    118   ///There is also a \ref bfs() "function type interface" for the BFS
     116  ///There is also a \ref bfs() "function-type interface" for the BFS
    119117  ///algorithm, which is convenient in the simplier cases and it can be
    120118  ///used easier.
     
    137135  class Bfs {
    138136  public:
    139     ///\ref Exception for uninitialized parameters.
    140 
    141     ///This error represents problems in the initialization of the
    142     ///parameters of the algorithm.
    143     class UninitializedParameter : public lemon::UninitializedParameter {
    144     public:
    145       virtual const char* what() const throw() {
    146         return "lemon::Bfs::UninitializedParameter";
    147       }
    148     };
    149137
    150138    ///The type of the digraph the algorithm runs on.
     
    196184    int _curr_dist;
    197185
    198     ///Creates the maps if necessary.
    199     ///\todo Better memory allocation (instead of new).
     186    //Creates the maps if necessary.
    200187    void create_maps()
    201188    {
     
    231218
    232219    template <class T>
    233     struct DefPredMapTraits : public Traits {
     220    struct SetPredMapTraits : public Traits {
    234221      typedef T PredMap;
    235222      static PredMap *createPredMap(const Digraph &)
    236223      {
    237         throw UninitializedParameter();
     224        LEMON_ASSERT(false, "PredMap is not initialized");
     225        return 0; // ignore warnings
    238226      }
    239227    };
    240228    ///\brief \ref named-templ-param "Named parameter" for setting
    241     ///\ref PredMap type.
     229    ///PredMap type.
    242230    ///
    243231    ///\ref named-templ-param "Named parameter" for setting
    244     ///\ref PredMap type.
     232    ///PredMap type.
    245233    template <class T>
    246     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
    247       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
     234    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     235      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    248236    };
    249237
    250238    template <class T>
    251     struct DefDistMapTraits : public Traits {
     239    struct SetDistMapTraits : public Traits {
    252240      typedef T DistMap;
    253241      static DistMap *createDistMap(const Digraph &)
    254242      {
    255         throw UninitializedParameter();
     243        LEMON_ASSERT(false, "DistMap is not initialized");
     244        return 0; // ignore warnings
    256245      }
    257246    };
    258247    ///\brief \ref named-templ-param "Named parameter" for setting
    259     ///\ref DistMap type.
     248    ///DistMap type.
    260249    ///
    261250    ///\ref named-templ-param "Named parameter" for setting
    262     ///\ref DistMap type.
     251    ///DistMap type.
    263252    template <class T>
    264     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
    265       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
     253    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     254      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    266255    };
    267256
    268257    template <class T>
    269     struct DefReachedMapTraits : public Traits {
     258    struct SetReachedMapTraits : public Traits {
    270259      typedef T ReachedMap;
    271260      static ReachedMap *createReachedMap(const Digraph &)
    272261      {
    273         throw UninitializedParameter();
     262        LEMON_ASSERT(false, "ReachedMap is not initialized");
     263        return 0; // ignore warnings
    274264      }
    275265    };
    276266    ///\brief \ref named-templ-param "Named parameter" for setting
    277     ///\ref ReachedMap type.
     267    ///ReachedMap type.
    278268    ///
    279269    ///\ref named-templ-param "Named parameter" for setting
    280     ///\ref ReachedMap type.
     270    ///ReachedMap type.
    281271    template <class T>
    282     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
    283       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
     272    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     273      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    284274    };
    285275
    286276    template <class T>
    287     struct DefProcessedMapTraits : public Traits {
     277    struct SetProcessedMapTraits : public Traits {
    288278      typedef T ProcessedMap;
    289279      static ProcessedMap *createProcessedMap(const Digraph &)
    290280      {
    291         throw UninitializedParameter();
     281        LEMON_ASSERT(false, "ProcessedMap is not initialized");
     282        return 0; // ignore warnings
    292283      }
    293284    };
    294285    ///\brief \ref named-templ-param "Named parameter" for setting
    295     ///\ref ProcessedMap type.
     286    ///ProcessedMap type.
    296287    ///
    297288    ///\ref named-templ-param "Named parameter" for setting
    298     ///\ref ProcessedMap type.
     289    ///ProcessedMap type.
    299290    template <class T>
    300     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
    301       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
     291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     292      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    302293    };
    303294
    304     struct DefDigraphProcessedMapTraits : public Traits {
     295    struct SetStandardProcessedMapTraits : public Traits {
    305296      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    306297      static ProcessedMap *createProcessedMap(const Digraph &g)
    307298      {
    308299        return new ProcessedMap(g);
     300        return 0; // ignore warnings
    309301      }
    310302    };
    311303    ///\brief \ref named-templ-param "Named parameter" for setting
    312     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    313305    ///
    314306    ///\ref named-templ-param "Named parameter" for setting
    315     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     307    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    316308    ///If you don't set it explicitly, it will be automatically allocated.
    317     template <class T>
    318     struct DefProcessedMapToBeDefaultMap :
    319       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
    320       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
     309    struct SetStandardProcessedMap :
     310      public Bfs< Digraph, SetStandardProcessedMapTraits > {
     311      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
    321312    };
    322313
     
    608599    ///
    609600    ///This method runs the %BFS algorithm from the root node(s)
    610     ///in order to compute the shortest path to \c dest.
     601    ///in order to compute the shortest path to \c t.
    611602    ///
    612603    ///The algorithm computes
    613     ///- the shortest path to \c dest,
    614     ///- the distance of \c dest from the root(s).
     604    ///- the shortest path to \c t,
     605    ///- the distance of \c t from the root(s).
    615606    ///
    616607    ///\pre init() must be called and at least one root node should be
     
    624615    ///  }
    625616    ///\endcode
    626     void start(Node dest)
     617    void start(Node t)
    627618    {
    628619      bool reach = false;
    629       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     620      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    630621    }
    631622
     
    665656    }
    666657
    667     ///Runs the algorithm from the given node.
     658    ///Runs the algorithm from the given source node.
    668659
    669660    ///This method runs the %BFS algorithm from node \c s
     
    689680
    690681    ///This method runs the %BFS algorithm from node \c s
    691     ///in order to compute the shortest path to \c t.
    692     ///
    693     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    694     ///if \c t is reachable form \c s, \c 0 otherwise.
     682    ///in order to compute the shortest path to node \c t
     683    ///(it stops searching when \c t is processed).
     684    ///
     685    ///\return \c true if \c t is reachable form \c s.
    695686    ///
    696687    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     
    701692    ///  b.start(t);
    702693    ///\endcode
    703     int run(Node s,Node t) {
     694    bool run(Node s,Node t) {
    704695      init();
    705696      addSource(s);
    706697      start(t);
    707       return reached(t) ? _curr_dist : 0;
     698      return reached(t);
    708699    }
    709700
     
    843834    ///arcs of the shortest paths.
    844835    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    845     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
    846     ///Instantiates a \ref PredMap.
    847 
    848     ///This function instantiates a \ref PredMap.
     836    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     837    ///Instantiates a PredMap.
     838
     839    ///This function instantiates a PredMap.
    849840    ///\param g is the digraph, to which we would like to define the
    850     ///\ref PredMap.
    851     ///\todo The digraph alone may be insufficient to initialize
    852 #ifdef DOXYGEN
     841    ///PredMap.
    853842    static PredMap *createPredMap(const Digraph &g)
    854 #else
    855     static PredMap *createPredMap(const Digraph &)
    856 #endif
    857     {
    858       return new PredMap();
     843    {
     844      return new PredMap(g);
    859845    }
    860846
     
    863849    ///The type of the map that indicates which nodes are processed.
    864850    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     851    ///By default it is a NullMap.
    865852    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    866     ///Instantiates a \ref ProcessedMap.
    867 
    868     ///This function instantiates a \ref ProcessedMap.
     853    ///Instantiates a ProcessedMap.
     854
     855    ///This function instantiates a ProcessedMap.
    869856    ///\param g is the digraph, to which
    870     ///we would like to define the \ref ProcessedMap.
     857    ///we would like to define the ProcessedMap.
    871858#ifdef DOXYGEN
    872859    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    883870    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    884871    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    885     ///Instantiates a \ref ReachedMap.
    886 
    887     ///This function instantiates a \ref ReachedMap.
     872    ///Instantiates a ReachedMap.
     873
     874    ///This function instantiates a ReachedMap.
    888875    ///\param g is the digraph, to which
    889     ///we would like to define the \ref ReachedMap.
     876    ///we would like to define the ReachedMap.
    890877    static ReachedMap *createReachedMap(const Digraph &g)
    891878    {
     
    897884    ///The type of the map that stores the distances of the nodes.
    898885    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    899     ///
    900     typedef NullMap<typename Digraph::Node,int> DistMap;
    901     ///Instantiates a \ref DistMap.
    902 
    903     ///This function instantiates a \ref DistMap.
     886    typedef typename Digraph::template NodeMap<int> DistMap;
     887    ///Instantiates a DistMap.
     888
     889    ///This function instantiates a DistMap.
    904890    ///\param g is the digraph, to which we would like to define
    905     ///the \ref DistMap
    906 #ifdef DOXYGEN
     891    ///the DistMap
    907892    static DistMap *createDistMap(const Digraph &g)
    908 #else
    909     static DistMap *createDistMap(const Digraph &)
    910 #endif
    911     {
    912       return new DistMap();
    913     }
     893    {
     894      return new DistMap(g);
     895    }
     896
     897    ///The type of the shortest paths.
     898
     899    ///The type of the shortest paths.
     900    ///It must meet the \ref concepts::Path "Path" concept.
     901    typedef lemon::Path<Digraph> Path;
    914902  };
    915903
    916   /// Default traits class used by \ref BfsWizard
     904  /// Default traits class used by BfsWizard
    917905
    918906  /// To make it easier to use Bfs algorithm
     
    941929    //Pointer to the map of distances.
    942930    void *_dist;
    943     //Pointer to the source node.
    944     Node _source;
     931    //Pointer to the shortest path to the target node.
     932    void *_path;
     933    //Pointer to the distance of the target node.
     934    int *_di;
    945935
    946936    public:
     
    948938
    949939    /// This constructor does not require parameters, therefore it initiates
    950     /// all of the attributes to default values (0, INVALID).
     940    /// all of the attributes to \c 0.
    951941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    952                       _dist(0), _source(INVALID) {}
     942                      _dist(0), _path(0), _di(0) {}
    953943
    954944    /// Constructor.
    955945
    956     /// This constructor requires some parameters,
    957     /// listed in the parameters list.
    958     /// Others are initiated to 0.
     946    /// This constructor requires one parameter,
     947    /// others are initiated to \c 0.
    959948    /// \param g The digraph the algorithm runs on.
    960     /// \param s The source node.
    961     BfsWizardBase(const GR &g, Node s=INVALID) :
     949    BfsWizardBase(const GR &g) :
    962950      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    963       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     951      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    964952
    965953  };
    966954
    967   /// Auxiliary class for the function type interface of BFS algorithm.
    968 
    969   /// This auxiliary class is created to implement the function type
    970   /// interface of \ref Bfs algorithm. It uses the functions and features
    971   /// of the plain \ref Bfs, but it is much simpler to use it.
    972   /// It should only be used through the \ref bfs() function, which makes
    973   /// it easier to use the algorithm.
     955  /// Auxiliary class for the function-type interface of BFS algorithm.
     956
     957  /// This auxiliary class is created to implement the
     958  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
     959  /// It does not have own \ref run() method, it uses the functions
     960  /// and features of the plain \ref Bfs.
    974961  ///
    975   /// Simplicity means that the way to change the types defined
    976   /// in the traits class is based on functions that returns the new class
    977   /// and not on templatable built-in classes.
    978   /// When using the plain \ref Bfs
    979   /// the new class with the modified type comes from
    980   /// the original class by using the ::
    981   /// operator. In the case of \ref BfsWizard only
    982   /// a function have to be called, and it will
    983   /// return the needed class.
    984   ///
    985   /// It does not have own \ref run() method. When its \ref run() method
    986   /// is called, it initiates a plain \ref Bfs object, and calls the
    987   /// \ref Bfs::run() method of it.
     962  /// This class should only be used through the \ref bfs() function,
     963  /// which makes it easier to use the algorithm.
    988964  template<class TR>
    989965  class BfsWizard : public TR
     
    1008984    ///\brief The type of the map that indicates which nodes are processed.
    1009985    typedef typename TR::ProcessedMap ProcessedMap;
     986    ///The type of the shortest paths
     987    typedef typename TR::Path Path;
    1010988
    1011989  public:
     
    1018996    /// Constructor that requires parameters.
    1019997    /// These parameters will be the default values for the traits class.
    1020     BfsWizard(const Digraph &g, Node s=INVALID) :
    1021       TR(g,s) {}
     998    /// \param g The digraph the algorithm runs on.
     999    BfsWizard(const Digraph &g) :
     1000      TR(g) {}
    10221001
    10231002    ///Copy constructor
     
    10261005    ~BfsWizard() {}
    10271006
    1028     ///Runs BFS algorithm from a source node.
    1029 
    1030     ///Runs BFS algorithm from a source node.
    1031     ///The node can be given with the \ref source() function.
     1007    ///Runs BFS algorithm from the given source node.
     1008
     1009    ///This method runs BFS algorithm from node \c s
     1010    ///in order to compute the shortest path to each node.
     1011    void run(Node s)
     1012    {
     1013      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1014      if (Base::_pred)
     1015        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1016      if (Base::_dist)
     1017        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1018      if (Base::_reached)
     1019        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1020      if (Base::_processed)
     1021        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1022      if (s!=INVALID)
     1023        alg.run(s);
     1024      else
     1025        alg.run();
     1026    }
     1027
     1028    ///Finds the shortest path between \c s and \c t.
     1029
     1030    ///This method runs BFS algorithm from node \c s
     1031    ///in order to compute the shortest path to node \c t
     1032    ///(it stops searching when \c t is processed).
     1033    ///
     1034    ///\return \c true if \c t is reachable form \c s.
     1035    bool run(Node s, Node t)
     1036    {
     1037      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1038      if (Base::_pred)
     1039        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1040      if (Base::_dist)
     1041        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1042      if (Base::_reached)
     1043        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1044      if (Base::_processed)
     1045        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1046      alg.run(s,t);
     1047      if (Base::_path)
     1048        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     1049      if (Base::_di)
     1050        *Base::_di = alg.dist(t);
     1051      return alg.reached(t);
     1052    }
     1053
     1054    ///Runs BFS algorithm to visit all nodes in the digraph.
     1055
     1056    ///This method runs BFS algorithm in order to compute
     1057    ///the shortest path to each node.
    10321058    void run()
    10331059    {
    1034       if(Base::_source==INVALID) throw UninitializedParameter();
    1035       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    1036       if(Base::_reached)
    1037         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    1038       if(Base::_processed)
    1039         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1040       if(Base::_pred)
    1041         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1042       if(Base::_dist)
    1043         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1044       alg.run(Base::_source);
    1045     }
    1046 
    1047     ///Runs BFS algorithm from the given node.
    1048 
    1049     ///Runs BFS algorithm from the given node.
    1050     ///\param s is the given source.
    1051     void run(Node s)
    1052     {
    1053       Base::_source=s;
    1054       run();
    1055     }
    1056 
    1057     /// Sets the source node, from which the Bfs algorithm runs.
    1058 
    1059     /// Sets the source node, from which the Bfs algorithm runs.
    1060     /// \param s is the source node.
    1061     BfsWizard<TR> &source(Node s)
    1062     {
    1063       Base::_source=s;
    1064       return *this;
     1060      run(INVALID);
    10651061    }
    10661062
    10671063    template<class T>
    1068     struct DefPredMapBase : public Base {
     1064    struct SetPredMapBase : public Base {
    10691065      typedef T PredMap;
    10701066      static PredMap *createPredMap(const Digraph &) { return 0; };
    1071       DefPredMapBase(const TR &b) : TR(b) {}
     1067      SetPredMapBase(const TR &b) : TR(b) {}
    10721068    };
    1073     ///\brief \ref named-templ-param "Named parameter"
    1074     ///for setting \ref PredMap object.
    1075     ///
    1076     /// \ref named-templ-param "Named parameter"
    1077     ///for setting \ref PredMap object.
     1069    ///\brief \ref named-func-param "Named parameter"
     1070    ///for setting PredMap object.
     1071    ///
     1072    ///\ref named-func-param "Named parameter"
     1073    ///for setting PredMap object.
    10781074    template<class T>
    1079     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     1075    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    10801076    {
    10811077      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    1082       return BfsWizard<DefPredMapBase<T> >(*this);
     1078      return BfsWizard<SetPredMapBase<T> >(*this);
    10831079    }
    10841080
    10851081    template<class T>
    1086     struct DefReachedMapBase : public Base {
     1082    struct SetReachedMapBase : public Base {
    10871083      typedef T ReachedMap;
    10881084      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
    1089       DefReachedMapBase(const TR &b) : TR(b) {}
     1085      SetReachedMapBase(const TR &b) : TR(b) {}
    10901086    };
    1091     ///\brief \ref named-templ-param "Named parameter"
    1092     ///for setting \ref ReachedMap object.
    1093     ///
    1094     /// \ref named-templ-param "Named parameter"
    1095     ///for setting \ref ReachedMap object.
     1087    ///\brief \ref named-func-param "Named parameter"
     1088    ///for setting ReachedMap object.
     1089    ///
     1090    /// \ref named-func-param "Named parameter"
     1091    ///for setting ReachedMap object.
    10961092    template<class T>
    1097     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1093    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    10981094    {
    10991095      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    1100       return BfsWizard<DefReachedMapBase<T> >(*this);
     1096      return BfsWizard<SetReachedMapBase<T> >(*this);
    11011097    }
    11021098
    11031099    template<class T>
    1104     struct DefProcessedMapBase : public Base {
     1100    struct SetDistMapBase : public Base {
     1101      typedef T DistMap;
     1102      static DistMap *createDistMap(const Digraph &) { return 0; };
     1103      SetDistMapBase(const TR &b) : TR(b) {}
     1104    };
     1105    ///\brief \ref named-func-param "Named parameter"
     1106    ///for setting DistMap object.
     1107    ///
     1108    /// \ref named-func-param "Named parameter"
     1109    ///for setting DistMap object.
     1110    template<class T>
     1111    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1112    {
     1113      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1114      return BfsWizard<SetDistMapBase<T> >(*this);
     1115    }
     1116
     1117    template<class T>
     1118    struct SetProcessedMapBase : public Base {
    11051119      typedef T ProcessedMap;
    11061120      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
    1107       DefProcessedMapBase(const TR &b) : TR(b) {}
     1121      SetProcessedMapBase(const TR &b) : TR(b) {}
    11081122    };
    1109     ///\brief \ref named-templ-param "Named parameter"
    1110     ///for setting \ref ProcessedMap object.
    1111     ///
    1112     /// \ref named-templ-param "Named parameter"
    1113     ///for setting \ref ProcessedMap object.
     1123    ///\brief \ref named-func-param "Named parameter"
     1124    ///for setting ProcessedMap object.
     1125    ///
     1126    /// \ref named-func-param "Named parameter"
     1127    ///for setting ProcessedMap object.
    11141128    template<class T>
    1115     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1129    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    11161130    {
    11171131      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    1118       return BfsWizard<DefProcessedMapBase<T> >(*this);
     1132      return BfsWizard<SetProcessedMapBase<T> >(*this);
    11191133    }
    11201134
    11211135    template<class T>
    1122     struct DefDistMapBase : public Base {
    1123       typedef T DistMap;
    1124       static DistMap *createDistMap(const Digraph &) { return 0; };
    1125       DefDistMapBase(const TR &b) : TR(b) {}
     1136    struct SetPathBase : public Base {
     1137      typedef T Path;
     1138      SetPathBase(const TR &b) : TR(b) {}
    11261139    };
    1127     ///\brief \ref named-templ-param "Named parameter"
    1128     ///for setting \ref DistMap object.
    1129     ///
    1130     /// \ref named-templ-param "Named parameter"
    1131     ///for setting \ref DistMap object.
     1140    ///\brief \ref named-func-param "Named parameter"
     1141    ///for getting the shortest path to the target node.
     1142    ///
     1143    ///\ref named-func-param "Named parameter"
     1144    ///for getting the shortest path to the target node.
    11321145    template<class T>
    1133     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
    1134     {
    1135       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1136       return BfsWizard<DefDistMapBase<T> >(*this);
     1146    BfsWizard<SetPathBase<T> > path(const T &t)
     1147    {
     1148      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1149      return BfsWizard<SetPathBase<T> >(*this);
     1150    }
     1151
     1152    ///\brief \ref named-func-param "Named parameter"
     1153    ///for getting the distance of the target node.
     1154    ///
     1155    ///\ref named-func-param "Named parameter"
     1156    ///for getting the distance of the target node.
     1157    BfsWizard dist(const int &d)
     1158    {
     1159      Base::_di=const_cast<int*>(&d);
     1160      return *this;
    11371161    }
    11381162
    11391163  };
    11401164
    1141   ///Function type interface for Bfs algorithm.
     1165  ///Function-type interface for BFS algorithm.
    11421166
    11431167  /// \ingroup search
    1144   ///Function type interface for Bfs algorithm.
     1168  ///Function-type interface for BFS algorithm.
    11451169  ///
    1146   ///This function also has several
    1147   ///\ref named-templ-func-param "named parameters",
     1170  ///This function also has several \ref named-func-param "named parameters",
    11481171  ///they are declared as the members of class \ref BfsWizard.
    1149   ///The following
    1150   ///example shows how to use these parameters.
     1172  ///The following examples show how to use these parameters.
    11511173  ///\code
    1152   ///  bfs(g,source).predMap(preds).run();
     1174  ///  // Compute shortest path from node s to each node
     1175  ///  bfs(g).predMap(preds).distMap(dists).run(s);
     1176  ///
     1177  ///  // Compute shortest path from s to t
     1178  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11531179  ///\endcode
    11541180  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     
    11581184  template<class GR>
    11591185  BfsWizard<BfsWizardBase<GR> >
    1160   bfs(const GR &g,typename GR::Node s=INVALID)
     1186  bfs(const GR &digraph)
    11611187  {
    1162     return BfsWizard<BfsWizardBase<GR> >(g,s);
     1188    return BfsWizard<BfsWizardBase<GR> >(digraph);
    11631189  }
    11641190
     
    12411267    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12421268
    1243     /// \brief Instantiates a \ref ReachedMap.
    1244     ///
    1245     /// This function instantiates a \ref ReachedMap.
     1269    /// \brief Instantiates a ReachedMap.
     1270    ///
     1271    /// This function instantiates a ReachedMap.
    12461272    /// \param digraph is the digraph, to which
    1247     /// we would like to define the \ref ReachedMap.
     1273    /// we would like to define the ReachedMap.
    12481274    static ReachedMap *createReachedMap(const Digraph &digraph) {
    12491275      return new ReachedMap(digraph);
     
    12861312  template <typename _Digraph = ListDigraph,
    12871313            typename _Visitor = BfsVisitor<_Digraph>,
    1288             typename _Traits = BfsDefaultTraits<_Digraph> >
     1314            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    12891315#endif
    12901316  class BfsVisit {
    12911317  public:
    1292 
    1293     /// \brief \ref Exception for uninitialized parameters.
    1294     ///
    1295     /// This error represents problems in the initialization
    1296     /// of the parameters of the algorithm.
    1297     class UninitializedParameter : public lemon::UninitializedParameter {
    1298     public:
    1299       virtual const char* what() const throw()
    1300       {
    1301         return "lemon::BfsVisit::UninitializedParameter";
    1302       }
    1303     };
    13041318
    13051319    ///The traits class.
     
    13341348    int _list_front, _list_back;
    13351349
    1336     ///Creates the maps if necessary.
    1337     ///\todo Better memory allocation (instead of new).
     1350    //Creates the maps if necessary.
    13381351    void create_maps() {
    13391352      if(!_reached) {
     
    13551368    ///@{
    13561369    template <class T>
    1357     struct DefReachedMapTraits : public Traits {
     1370    struct SetReachedMapTraits : public Traits {
    13581371      typedef T ReachedMap;
    13591372      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1360         throw UninitializedParameter();
     1373        LEMON_ASSERT(false, "ReachedMap is not initialized");
     1374        return 0; // ignore warnings
    13611375      }
    13621376    };
     
    13661380    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    13671381    template <class T>
    1368     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
    1369                                             DefReachedMapTraits<T> > {
    1370       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
     1382    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
     1383                                            SetReachedMapTraits<T> > {
     1384      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
    13711385    };
    13721386    ///@}
     
    15851599    ///
    15861600    /// This method runs the %BFS algorithm from the root node(s)
    1587     /// in order to compute the shortest path to \c dest.
     1601    /// in order to compute the shortest path to \c t.
    15881602    ///
    15891603    /// The algorithm computes
    1590     /// - the shortest path to \c dest,
    1591     /// - the distance of \c dest from the root(s).
     1604    /// - the shortest path to \c t,
     1605    /// - the distance of \c t from the root(s).
    15921606    ///
    15931607    /// \pre init() must be called and at least one root node should be
     
    16011615    ///   }
    16021616    /// \endcode
    1603     void start(Node dest) {
     1617    void start(Node t) {
    16041618      bool reach = false;
    1605       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     1619      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    16061620    }
    16071621
     
    16411655    }
    16421656
    1643     /// \brief Runs the algorithm from the given node.
     1657    /// \brief Runs the algorithm from the given source node.
    16441658    ///
    16451659    /// This method runs the %BFS algorithm from node \c s
     
    16601674      addSource(s);
    16611675      start();
     1676    }
     1677
     1678    /// \brief Finds the shortest path between \c s and \c t.
     1679    ///
     1680    /// This method runs the %BFS algorithm from node \c s
     1681    /// in order to compute the shortest path to node \c t
     1682    /// (it stops searching when \c t is processed).
     1683    ///
     1684    /// \return \c true if \c t is reachable form \c s.
     1685    ///
     1686    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     1687    /// shortcut of the following code.
     1688    ///\code
     1689    ///   b.init();
     1690    ///   b.addSource(s);
     1691    ///   b.start(t);
     1692    ///\endcode
     1693    bool run(Node s,Node t) {
     1694      init();
     1695      addSource(s);
     1696      start(t);
     1697      return reached(t);
    16621698    }
    16631699
  • lemon/bits/alteration_notifier.h

    r236 r314  
    2525#include <lemon/core.h>
    2626
    27 ///\ingroup graphbits
    28 ///\file
    29 ///\brief Observer notifier for graph alteration observers.
     27//\ingroup graphbits
     28//\file
     29//\brief Observer notifier for graph alteration observers.
    3030
    3131namespace lemon {
    3232
    33   /// \ingroup graphbits
    34   ///
    35   /// \brief Notifier class to notify observes about alterations in
    36   /// a container.
    37   ///
    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
    44   /// nodes and edges in the graph. LEMON would like to handle easily
    45   /// that the node and edge maps should contain values for all nodes or
    46   /// edges. If we want to check on every indicing if the map contains
    47   /// the current indicing key that cause a drawback in the performance
    48   /// in the library. We use another solution we notify all maps about
    49   /// an alteration in the graph, which cause only drawback on the
    50   /// alteration of the graph.
    51   ///
    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.
    56   ///
    57   /// 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
    63   /// 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   /// them from the container, on the other way on item addition we should
    66   /// first extend the container and just after that signal the alteration.
    67   ///
    68   /// The alteration can be observed with a class inherited from the
    69   /// \e ObserverBase nested class. The signals can be handled with
    70   /// overriding the virtual functions defined in the base class.  The
    71   /// observer base can be attached to the notifier with the
    72   /// \e attach() member and can be detached with detach() function. The
    73   /// alteration handlers should not call any function which signals
    74   /// an other alteration in the same notifier and should not
    75   /// detach any observer from the notifier.
    76   ///
    77   /// Alteration observers try to be exception safe. If an \e add() or
    78   /// a \e clear() function throws an exception then the remaining
    79   /// 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
    83   /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
    84   /// exception which detach the observer from the notifier.
    85   ///
    86   /// There are some place when the alteration observing is not completly
    87   /// reliable. If we want to carry out the node degree in the graph
    88   /// as in the \ref InDegMap and we use the reverseEdge that cause
    89   /// unreliable functionality. Because the alteration observing signals
    90   /// only erasing and adding but not the reversing it will stores bad
    91   /// degrees. The sub graph adaptors cannot signal the alterations because
    92   /// just a setting in the filter map can modify the graph and this cannot
    93   /// be watched in any way.
    94   ///
    95   /// \param _Container The container which is observed.
    96   /// \param _Item The item type which is obserbved.
     33  // \ingroup graphbits
     34  //
     35  // \brief Notifier class to notify observes about alterations in
     36  // a container.
     37  //
     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
     44  // nodes and edges in the graph. LEMON would like to handle easily
     45  // that the node and edge maps should contain values for all nodes or
     46  // edges. If we want to check on every indicing if the map contains
     47  // the current indicing key that cause a drawback in the performance
     48  // in the library. We use another solution we notify all maps about
     49  // an alteration in the graph, which cause only drawback on the
     50  // alteration of the graph.
     51  //
     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.
     56  //
     57  // 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
     63  // 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  // them from the container, on the other way on item addition we should
     66  // first extend the container and just after that signal the alteration.
     67  //
     68  // The alteration can be observed with a class inherited from the
     69  // \e ObserverBase nested class. The signals can be handled with
     70  // overriding the virtual functions defined in the base class.  The
     71  // observer base can be attached to the notifier with the
     72  // \e attach() member and can be detached with detach() function. The
     73  // alteration handlers should not call any function which signals
     74  // an other alteration in the same notifier and should not
     75  // detach any observer from the notifier.
     76  //
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
     79  // 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
     86  // 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  // 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.
     93  //
     94  // \param _Container The container which is observed.
     95  // \param _Item The item type which is obserbved.
    9796
    9897  template <typename _Container, typename _Item>
     
    105104    typedef _Item Item;
    106105
    107     /// \brief Exception which can be called from \e clear() and
    108     /// \e erase().
    109     ///
    110     /// From the \e clear() and \e erase() function only this
    111     /// exception is allowed to throw. The exception immediatly
    112     /// detaches the current observer from the notifier. Because the
    113     /// \e clear() and \e erase() should not throw other exceptions
    114     /// it can be used to invalidate the observer.
     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
     110    // exception is allowed to throw. The exception immediatly
     111    // detaches the current observer from the notifier. Because the
     112    // \e clear() and \e erase() should not throw other exceptions
     113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
    116115
    117     /// \brief ObserverBase is the base class for the observers.
    118     ///
    119     /// ObserverBase is the abstract base class for the observers.
    120     /// It will be notified about an item was inserted into or
    121     /// erased from the graph.
    122     ///
    123     /// The observer interface contains some pure virtual functions
    124     /// to override. The add() and erase() functions are
    125     /// to notify the oberver when one item is added or
    126     /// erased.
    127     ///
    128     /// The build() and clear() members are to notify the observer
    129     /// about the container is built from an empty container or
    130     /// is cleared to an empty container.
    131 
     116    // \brief ObserverBase is the base class for the observers.
     117    //
     118    // ObserverBase is the abstract base class for the observers.
     119    // It will be notified about an item was inserted into or
     120    // erased from the graph.
     121    //
     122    // The observer interface contains some pure virtual functions
     123    // to override. The add() and erase() functions are
     124    // to notify the oberver when one item is added or
     125    // erased.
     126    //
     127    // The build() and clear() members are to notify the observer
     128    // about the container is built from an empty container or
     129    // is cleared to an empty container.
    132130    class ObserverBase {
    133131    protected:
     
    136134      friend class AlterationNotifier;
    137135
    138       /// \brief Default constructor.
    139       ///
    140       /// Default constructor for ObserverBase.
    141       ///
     136      // \brief Default constructor.
     137      //
     138      // Default constructor for ObserverBase.
    142139      ObserverBase() : _notifier(0) {}
    143140
    144       /// \brief Constructor which attach the observer into notifier.
    145       ///
    146       /// Constructor which attach the observer into notifier.
     141      // \brief Constructor which attach the observer into notifier.
     142      //
     143      // Constructor which attach the observer into notifier.
    147144      ObserverBase(AlterationNotifier& nf) {
    148145        attach(nf);
    149146      }
    150147
    151       /// \brief Constructor which attach the obserever to the same notifier.
    152       ///
    153       /// Constructor which attach the obserever to the same notifier as
    154       /// the other observer is attached to.
     148      // \brief Constructor which attach the obserever to the same notifier.
     149      //
     150      // Constructor which attach the obserever to the same notifier as
     151      // the other observer is attached to.
    155152      ObserverBase(const ObserverBase& copy) {
    156153        if (copy.attached()) {
     
    159156      }
    160157
    161       /// \brief Destructor
     158      // \brief Destructor
    162159      virtual ~ObserverBase() {
    163160        if (attached()) {
     
    166163      }
    167164
    168       /// \brief Attaches the observer into an AlterationNotifier.
    169       ///
    170       /// This member attaches the observer into an AlterationNotifier.
    171       ///
     165      // \brief Attaches the observer into an AlterationNotifier.
     166      //
     167      // This member attaches the observer into an AlterationNotifier.
    172168      void attach(AlterationNotifier& nf) {
    173169        nf.attach(*this);
    174170      }
    175171
    176       /// \brief Detaches the observer into an AlterationNotifier.
    177       ///
    178       /// This member detaches the observer from an AlterationNotifier.
    179       ///
     172      // \brief Detaches the observer into an AlterationNotifier.
     173      //
     174      // This member detaches the observer from an AlterationNotifier.
    180175      void detach() {
    181176        _notifier->detach(*this);
    182177      }
    183178
    184       /// \brief Gives back a pointer to the notifier which the map
    185       /// attached into.
    186       ///
    187       /// This function gives back a pointer to the notifier which the map
    188       /// attached into.
    189       ///
     179      // \brief Gives back a pointer to the notifier which the map
     180      // attached into.
     181      //
     182      // This function gives back a pointer to the notifier which the map
     183      // attached into.
    190184      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
    191185
    192       /// Gives back true when the observer is attached into a notifier.
     186      // Gives back true when the observer is attached into a notifier.
    193187      bool attached() const { return _notifier != 0; }
    194188
     
    202196      typename std::list<ObserverBase*>::iterator _index;
    203197
    204       /// \brief The member function to notificate the observer about an
    205       /// item is added to the container.
    206       ///
    207       /// The add() member function notificates the observer about an item
    208       /// is added to the container. It have to be overrided in the
    209       /// subclasses.
     198      // \brief The member function to notificate the observer about an
     199      // item is added to the container.
     200      //
     201      // The add() member function notificates the observer about an item
     202      // is added to the container. It have to be overrided in the
     203      // subclasses.
    210204      virtual void add(const Item&) = 0;
    211205
    212       /// \brief The member function to notificate the observer about
    213       /// more item is added to the container.
    214       ///
    215       /// The add() member function notificates the observer about more item
    216       /// is added to the container. It have to be overrided in the
    217       /// subclasses.
     206      // \brief The member function to notificate the observer about
     207      // more item is added to the container.
     208      //
     209      // The add() member function notificates the observer about more item
     210      // is added to the container. It have to be overrided in the
     211      // subclasses.
    218212      virtual void add(const std::vector<Item>& items) = 0;
    219213
    220       /// \brief The member function to notificate the observer about an
    221       /// item is erased from the container.
    222       ///
    223       /// The erase() member function notificates the observer about an
    224       /// item is erased from the container. It have to be overrided in
    225       /// the subclasses.
     214      // \brief The member function to notificate the observer about an
     215      // item is erased from the container.
     216      //
     217      // The erase() member function notificates the observer about an
     218      // item is erased from the container. It have to be overrided in
     219      // the subclasses.
    226220      virtual void erase(const Item&) = 0;
    227221
    228       /// \brief The member function to notificate the observer about
    229       /// more item is erased from the container.
    230       ///
    231       /// The erase() member function notificates the observer about more item
    232       /// is erased from the container. It have to be overrided in the
    233       /// subclasses.
     222      // \brief The member function to notificate the observer about
     223      // more item is erased from the container.
     224      //
     225      // The erase() member function notificates the observer about more item
     226      // is erased from the container. It have to be overrided in the
     227      // subclasses.
    234228      virtual void erase(const std::vector<Item>& items) = 0;
    235229
    236       /// \brief The member function to notificate the observer about the
    237       /// container is built.
    238       ///
    239       /// The build() member function notificates the observer about the
    240       /// container is built from an empty container. It have to be
    241       /// overrided in the subclasses.
    242 
     230      // \brief The member function to notificate the observer about the
     231      // container is built.
     232      //
     233      // The build() member function notificates the observer about the
     234      // container is built from an empty container. It have to be
     235      // overrided in the subclasses.
    243236      virtual void build() = 0;
    244237
    245       /// \brief The member function to notificate the observer about all
    246       /// items are erased from the container.
    247       ///
    248       /// The clear() member function notificates the observer about all
    249       /// items are erased from the container. It have to be overrided in
    250       /// the subclasses.
     238      // \brief The member function to notificate the observer about all
     239      // items are erased from the container.
     240      //
     241      // The clear() member function notificates the observer about all
     242      // items are erased from the container. It have to be overrided in
     243      // the subclasses.
    251244      virtual void clear() = 0;
    252245
     
    263256  public:
    264257
    265     /// \brief Default constructor.
    266     ///
    267     /// The default constructor of the AlterationNotifier.
    268     /// It creates an empty notifier.
     258    // \brief Default constructor.
     259    //
     260    // The default constructor of the AlterationNotifier.
     261    // It creates an empty notifier.
    269262    AlterationNotifier()
    270263      : container(0) {}
    271264
    272     /// \brief Constructor.
    273     ///
    274     /// Constructor with the observed container parameter.
     265    // \brief Constructor.
     266    //
     267    // Constructor with the observed container parameter.
    275268    AlterationNotifier(const Container& _container)
    276269      : container(&_container) {}
    277270
    278     /// \brief Copy Constructor of the AlterationNotifier.
    279     ///
    280     /// Copy constructor of the AlterationNotifier.
    281     /// It creates only an empty notifier because the copiable
    282     /// notifier's observers have to be registered still into that notifier.
     271    // \brief Copy Constructor of the AlterationNotifier.
     272    //
     273    // Copy constructor of the AlterationNotifier.
     274    // It creates only an empty notifier because the copiable
     275    // notifier's observers have to be registered still into that notifier.
    283276    AlterationNotifier(const AlterationNotifier& _notifier)
    284277      : container(_notifier.container) {}
    285278
    286     /// \brief Destructor.
    287     ///
    288     /// Destructor of the AlterationNotifier.
    289     ///
     279    // \brief Destructor.
     280    //
     281    // Destructor of the AlterationNotifier.
    290282    ~AlterationNotifier() {
    291283      typename Observers::iterator it;
     
    295287    }
    296288
    297     /// \brief Sets the container.
    298     ///
    299     /// Sets the container.
     289    // \brief Sets the container.
     290    //
     291    // Sets the container.
    300292    void setContainer(const Container& _container) {
    301293      container = &_container;
     
    308300  public:
    309301
    310 
    311 
    312     /// \brief First item in the container.
    313     ///
    314     /// Returns the first item in the container. It is
    315     /// for start the iteration on the container.
     302    // \brief First item in the container.
     303    //
     304    // Returns the first item in the container. It is
     305    // for start the iteration on the container.
    316306    void first(Item& item) const {
    317307      container->first(item);
    318308    }
    319309
    320     /// \brief Next item in the container.
    321     ///
    322     /// Returns the next item in the container. It is
    323     /// for iterate on the container.
     310    // \brief Next item in the container.
     311    //
     312    // Returns the next item in the container. It is
     313    // for iterate on the container.
    324314    void next(Item& item) const {
    325315      container->next(item);
    326316    }
    327317
    328     /// \brief Returns the id of the item.
    329     ///
    330     /// Returns the id of the item provided by the container.
     318    // \brief Returns the id of the item.
     319    //
     320    // Returns the id of the item provided by the container.
    331321    int id(const Item& item) const {
    332322      return container->id(item);
    333323    }
    334324
    335     /// \brief Returns the maximum id of the container.
    336     ///
    337     /// Returns the maximum id of the container.
     325    // \brief Returns the maximum id of the container.
     326    //
     327    // Returns the maximum id of the container.
    338328    int maxId() const {
    339329      return container->maxId(Item());
     
    355345  public:
    356346
    357     /// \brief Notifies all the registed observers about an item added to
    358     /// the container.
    359     ///
    360     /// It notifies all the registed observers about an item added to
    361     /// the container.
    362     ///
     347    // \brief Notifies all the registed observers about an item added to
     348    // the container.
     349    //
     350    // It notifies all the registed observers about an item added to
     351    // the container.
    363352    void add(const Item& item) {
    364353      typename Observers::reverse_iterator it;
     
    376365    }
    377366
    378     /// \brief Notifies all the registed observers about more item added to
    379     /// the container.
    380     ///
    381     /// It notifies all the registed observers about more item added to
    382     /// the container.
    383     ///
     367    // \brief Notifies all the registed observers about more item added to
     368    // the container.
     369    //
     370    // It notifies all the registed observers about more item added to
     371    // the container.
    384372    void add(const std::vector<Item>& items) {
    385373      typename Observers::reverse_iterator it;
     
    397385    }
    398386
    399     /// \brief Notifies all the registed observers about an item erased from
    400     /// the container.
    401     ///
    402     /// It notifies all the registed observers about an item erased from
    403     /// the container.
    404     ///
     387    // \brief Notifies all the registed observers about an item erased from
     388    // the container.
     389    //
     390    // It notifies all the registed observers about an item erased from
     391    // the container.
    405392    void erase(const Item& item) throw() {
    406393      typename Observers::iterator it = _observers.begin();
     
    417404    }
    418405
    419     /// \brief Notifies all the registed observers about more item erased
    420     /// from the container.
    421     ///
    422     /// It notifies all the registed observers about more item erased from
    423     /// the container.
    424     ///
     406    // \brief Notifies all the registed observers about more item erased
     407    // from the container.
     408    //
     409    // It notifies all the registed observers about more item erased from
     410    // the container.
    425411    void erase(const std::vector<Item>& items) {
    426412      typename Observers::iterator it = _observers.begin();
     
    437423    }
    438424
    439     /// \brief Notifies all the registed observers about the container is
    440     /// built.
    441     ///
    442     /// Notifies all the registed observers about the container is built
    443     /// from an empty container.
     425    // \brief Notifies all the registed observers about the container is
     426    // built.
     427    //
     428    // Notifies all the registed observers about the container is built
     429    // from an empty container.
    444430    void build() {
    445431      typename Observers::reverse_iterator it;
     
    457443    }
    458444
    459     /// \brief Notifies all the registed observers about all items are
    460     /// erased.
    461     ///
    462     /// Notifies all the registed observers about all items are erased
    463     /// from the container.
     445    // \brief Notifies all the registed observers about all items are
     446    // erased.
     447    //
     448    // Notifies all the registed observers about all items are erased
     449    // from the container.
    464450    void clear() {
    465451      typename Observers::iterator it = _observers.begin();
  • lemon/bits/array_map.h

    r209 r314  
    2727#include <lemon/concepts/maps.h>
    2828
    29 /// \ingroup graphbits
    30 /// \file
    31 /// \brief Graph map based on the array storage.
     29// \ingroup graphbits
     30// \file
     31// \brief Graph map based on the array storage.
    3232
    3333namespace lemon {
    3434
    35   /// \ingroup graphbits
    36   ///
    37   /// \brief Graph map based on the array storage.
    38   ///
    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.
    43   ///
    44   /// The template parameters are the Graph the current Item type and
    45   /// the Value type of the map.
     35  // \ingroup graphbits
     36  //
     37  // \brief Graph map based on the array storage.
     38  //
     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.
     43  //
     44  // The template parameters are the Graph the current Item type and
     45  // the Value type of the map.
    4646  template <typename _Graph, typename _Item, typename _Value>
    4747  class ArrayMap
    4848    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4949  public:
    50     /// The graph type of the maps.
     50    // The graph type of the maps.
    5151    typedef _Graph Graph;
    52     /// The item type of the map.
     52    // The item type of the map.
    5353    typedef _Item Item;
    54     /// The reference map tag.
     54    // The reference map tag.
    5555    typedef True ReferenceMapTag;
    5656
    57     /// The key type of the maps.
     57    // The key type of the maps.
    5858    typedef _Item Key;
    59     /// The value type of the map.
     59    // The value type of the map.
    6060    typedef _Value Value;
    6161
    62     /// The const reference type of the map.
     62    // The const reference type of the map.
    6363    typedef const _Value& ConstReference;
    64     /// The reference type of the map.
     64    // The reference type of the map.
    6565    typedef _Value& Reference;
    6666
    67     /// The notifier type.
     67    // The notifier type.
    6868    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    6969
    70     /// The MapBase of the Map which imlements the core regisitry function.
     70    // The MapBase of the Map which imlements the core regisitry function.
    7171    typedef typename Notifier::ObserverBase Parent;
    7272
     
    7676  public:
    7777
    78     /// \brief Graph initialized map constructor.
    79     ///
    80     /// Graph initialized map constructor.
     78    // \brief Graph initialized map constructor.
     79    //
     80    // Graph initialized map constructor.
    8181    explicit ArrayMap(const Graph& graph) {
    8282      Parent::attach(graph.notifier(Item()));
     
    9090    }
    9191
    92     /// \brief Constructor to use default value to initialize the map.
    93     ///
    94     /// It constructs a map and initialize all of the the map.
     92    // \brief Constructor to use default value to initialize the map.
     93    //
     94    // It constructs a map and initialize all of the the map.
    9595    ArrayMap(const Graph& graph, const Value& value) {
    9696      Parent::attach(graph.notifier(Item()));
     
    104104    }
    105105
    106     /// \brief Constructor to copy a map of the same map type.
    107     ///
    108     /// Constructor to copy a map of the same map type.
     106  private:
     107    // \brief Constructor to copy a map of the same map type.
     108    //
     109    // Constructor to copy a map of the same map type.
    109110    ArrayMap(const ArrayMap& copy) : Parent() {
    110111      if (copy.attached()) {
     
    122123    }
    123124
    124     /// \brief Assign operator.
    125     ///
    126     /// This operator assigns for each item in the map the
    127     /// value mapped to the same item in the copied map.
    128     /// The parameter map should be indiced with the same
    129     /// itemset because this assign operator does not change
    130     /// the container of the map.
     125    // \brief Assign operator.
     126    //
     127    // This operator assigns for each item in the map the
     128    // value mapped to the same item in the copied map.
     129    // The parameter map should be indiced with the same
     130    // itemset because this assign operator does not change
     131    // the container of the map.
    131132    ArrayMap& operator=(const ArrayMap& cmap) {
    132133      return operator=<ArrayMap>(cmap);
     
    134135
    135136
    136     /// \brief Template assign operator.
    137     ///
    138     /// The given parameter should be conform to the ReadMap
    139     /// concecpt and could be indiced by the current item set of
    140     /// the NodeMap. In this case the value for each item
    141     /// is assigned by the value of the given ReadMap.
     137    // \brief Template assign operator.
     138    //
     139    // The given parameter should be conform to the ReadMap
     140    // concecpt and could be indiced by the current item set of
     141    // the NodeMap. In this case the value for each item
     142    // is assigned by the value of the given ReadMap.
    142143    template <typename CMap>
    143144    ArrayMap& operator=(const CMap& cmap) {
     
    151152    }
    152153
    153     /// \brief The destructor of the map.
    154     ///
    155     /// The destructor of the map.
     154  public:
     155    // \brief The destructor of the map.
     156    //
     157    // The destructor of the map.
    156158    virtual ~ArrayMap() {
    157159      if (attached()) {
     
    169171  public:
    170172
    171     /// \brief The subscript operator.
    172     ///
    173     /// The subscript operator. The map can be subscripted by the
    174     /// actual keys of the graph.
     173    // \brief The subscript operator.
     174    //
     175    // The subscript operator. The map can be subscripted by the
     176    // actual keys of the graph.
    175177    Value& operator[](const Key& key) {
    176178      int id = Parent::notifier()->id(key);
     
    178180    }
    179181
    180     /// \brief The const subscript operator.
    181     ///
    182     /// The const subscript operator. The map can be subscripted by the
    183     /// actual keys of the graph.
     182    // \brief The const subscript operator.
     183    //
     184    // The const subscript operator. The map can be subscripted by the
     185    // actual keys of the graph.
    184186    const Value& operator[](const Key& key) const {
    185187      int id = Parent::notifier()->id(key);
     
    187189    }
    188190
    189     /// \brief Setter function of the map.
    190     ///
    191     /// Setter function of the map. Equivalent with map[key] = val.
    192     /// This is a compatibility feature with the not dereferable maps.
     191    // \brief Setter function of the map.
     192    //
     193    // Setter function of the map. Equivalent with map[key] = val.
     194    // This is a compatibility feature with the not dereferable maps.
    193195    void set(const Key& key, const Value& val) {
    194196      (*this)[key] = val;
     
    197199  protected:
    198200
    199     /// \brief Adds a new key to the map.
    200     ///
    201     /// It adds a new key to the map. It called by the observer notifier
    202     /// and it overrides the add() member function of the observer base.
     201    // \brief Adds a new key to the map.
     202    //
     203    // It adds a new key to the map. It called by the observer notifier
     204    // and it overrides the add() member function of the observer base.
    203205    virtual void add(const Key& key) {
    204206      Notifier* nf = Parent::notifier();
     
    225227    }
    226228
    227     /// \brief Adds more new keys to the map.
    228     ///
    229     /// It adds more new keys to the map. It called by the observer notifier
    230     /// and it overrides the add() member function of the observer base.
     229    // \brief Adds more new keys to the map.
     230    //
     231    // It adds more new keys to the map. It called by the observer notifier
     232    // and it overrides the add() member function of the observer base.
    231233    virtual void add(const std::vector<Key>& keys) {
    232234      Notifier* nf = Parent::notifier();
     
    269271    }
    270272
    271     /// \brief Erase a key from the map.
    272     ///
    273     /// Erase a key from the map. It called by the observer notifier
    274     /// and it overrides the erase() member function of the observer base.
     273    // \brief Erase a key from the map.
     274    //
     275    // Erase a key from the map. It called by the observer notifier
     276    // and it overrides the erase() member function of the observer base.
    275277    virtual void erase(const Key& key) {
    276278      int id = Parent::notifier()->id(key);
     
    278280    }
    279281
    280     /// \brief Erase more keys from the map.
    281     ///
    282     /// Erase more keys from the map. It called by the observer notifier
    283     /// and it overrides the erase() member function of the observer base.
     282    // \brief Erase more keys from the map.
     283    //
     284    // Erase more keys from the map. It called by the observer notifier
     285    // and it overrides the erase() member function of the observer base.
    284286    virtual void erase(const std::vector<Key>& keys) {
    285287      for (int i = 0; i < int(keys.size()); ++i) {
     
    289291    }
    290292
    291     /// \brief Buildes the map.
    292     ///
    293     /// It buildes the map. It called by the observer notifier
    294     /// and it overrides the build() member function of the observer base.
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
     296    // and it overrides the build() member function of the observer base.
    295297    virtual void build() {
    296298      Notifier* nf = Parent::notifier();
     
    303305    }
    304306
    305     /// \brief Clear the map.
    306     ///
    307     /// It erase all items from the map. It called by the observer notifier
    308     /// and it overrides the clear() member function of the observer base.
     307    // \brief Clear the map.
     308    //
     309    // It erase all items from the map. It called by the observer notifier
     310    // and it overrides the clear() member function of the observer base.
    309311    virtual void clear() {
    310312      Notifier* nf = Parent::notifier();
  • lemon/bits/base_extender.h

    r256 r314  
    2929#include <lemon/concepts/maps.h>
    3030
    31 ///\ingroup digraphbits
    32 ///\file
    33 ///\brief Extenders for the digraph types
     31//\ingroup digraphbits
     32//\file
     33//\brief Extenders for the digraph types
    3434namespace lemon {
    3535
    36   /// \ingroup digraphbits
    37   ///
    38   /// \brief BaseDigraph to BaseGraph extender
     36  // \ingroup digraphbits
     37  //
     38  // \brief BaseDigraph to BaseGraph extender
    3939  template <typename Base>
    4040  class UndirDigraphExtender : public Base {
     
    7575    };
    7676
    77     /// First node of the edge
     77    // First node of the edge
    7878    Node u(const Edge &e) const {
    7979      return Parent::source(e);
    8080    }
    8181
    82     /// Source of the given arc
     82    // Source of the given arc
    8383    Node source(const Arc &e) const {
    8484      return e.forward ? Parent::source(e) : Parent::target(e);
    8585    }
    8686
    87     /// Second node of the edge
     87    // Second node of the edge
    8888    Node v(const Edge &e) const {
    8989      return Parent::target(e);
    9090    }
    9191
    92     /// Target of the given arc
     92    // Target of the given arc
    9393    Node target(const Arc &e) const {
    9494      return e.forward ? Parent::target(e) : Parent::source(e);
    9595    }
    9696
    97     /// \brief Directed arc from an edge.
    98     ///
    99     /// Returns a directed arc corresponding to the specified edge.
    100     /// If the given bool is true, the first node of the given edge and
    101     /// the source node of the returned arc are the same.
     97    // \brief Directed arc from an edge.
     98    //
     99    // Returns a directed arc corresponding to the specified edge.
     100    // If the given bool is true, the first node of the given edge and
     101    // the source node of the returned arc are the same.
    102102    static Arc direct(const Edge &e, bool d) {
    103103      return Arc(e, d);
    104104    }
    105105
    106     /// Returns whether the given directed arc has the same orientation
    107     /// as the corresponding edge.
    108     ///
    109     /// \todo reference to the corresponding point of the undirected digraph
    110     /// concept. "What does the direction of an edge mean?"
     106    // Returns whether the given directed arc has the same orientation
     107    // as the corresponding edge.
    111108    static bool direction(const Arc &a) { return a.forward; }
    112109
     
    302299      Red() {}
    303300      Red(const Node& node) : Node(node) {
    304         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    305                      typename Parent::NodeSetError());
     301        LEMON_DEBUG(Parent::red(node) || node == INVALID,
     302                    typename Parent::NodeSetError());
    306303      }
    307304      Red& operator=(const Node& node) {
    308         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    309                      typename Parent::NodeSetError());
     305        LEMON_DEBUG(Parent::red(node) || node == INVALID,
     306                    typename Parent::NodeSetError());
    310307        Node::operator=(node);
    311308        return *this;
     
    334331      Blue() {}
    335332      Blue(const Node& node) : Node(node) {
    336         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    337                      typename Parent::NodeSetError());
     333        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
     334                    typename Parent::NodeSetError());
    338335      }
    339336      Blue& operator=(const Node& node) {
    340         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    341                      typename Parent::NodeSetError());
     337        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
     338                    typename Parent::NodeSetError());
    342339        Node::operator=(node);
    343340        return *this;
  • lemon/bits/bezier.h

    r209 r314  
    2020#define LEMON_BEZIER_H
    2121
    22 ///\ingroup misc
    23 ///\file
    24 ///\brief Classes to compute with Bezier curves.
    25 ///
    26 ///Up to now this file is used internally by \ref graph_to_eps.h
     22//\ingroup misc
     23//\file
     24//\brief Classes to compute with Bezier curves.
     25//
     26//Up to now this file is used internally by \ref graph_to_eps.h
    2727
    2828#include<lemon/dim2.h>
  • lemon/bits/default_map.h

    r209 r314  
    2020#define LEMON_BITS_DEFAULT_MAP_H
    2121
    22 
    2322#include <lemon/bits/array_map.h>
    2423#include <lemon/bits/vector_map.h>
    2524//#include <lemon/bits/debug_map.h>
    2625
    27 ///\ingroup graphbits
    28 ///\file
    29 ///\brief Graph maps that construct and destruct their elements dynamically.
     26//\ingroup graphbits
     27//\file
     28//\brief Graph maps that construct and destruct their elements dynamically.
    3029
    3130namespace lemon {
     
    150149// #endif
    151150
    152   /// \e
     151  // DefaultMap class
    153152  template <typename _Graph, typename _Item, typename _Value>
    154153  class DefaultMap
  • lemon/bits/enable_if.h

    r220 r314  
    3636#define LEMON_BITS_ENABLE_IF_H
    3737
    38 ///\file
    39 ///\brief Miscellaneous basic utilities
     38//\file
     39//\brief Miscellaneous basic utilities
    4040
    4141namespace lemon
    4242{
    4343
    44   /// Basic type for defining "tags". A "YES" condition for \c enable_if.
     44  // Basic type for defining "tags". A "YES" condition for \c enable_if.
    4545
    46   /// Basic type for defining "tags". A "YES" condition for \c enable_if.
    47   ///
    48   ///\sa False
     46  // Basic type for defining "tags". A "YES" condition for \c enable_if.
     47  //
     48  //\sa False
    4949  struct True {
    50     ///\e
     50    //\e
    5151    static const bool value = true;
    5252  };
    5353
    54   /// Basic type for defining "tags". A "NO" condition for \c enable_if.
     54  // Basic type for defining "tags". A "NO" condition for \c enable_if.
    5555
    56   /// Basic type for defining "tags". A "NO" condition for \c enable_if.
    57   ///
    58   ///\sa True
     56  // Basic type for defining "tags". A "NO" condition for \c enable_if.
     57  //
     58  //\sa True
    5959  struct False {
    60     ///\e
     60    //\e
    6161    static const bool value = false;
    6262  };
  • lemon/bits/graph_extender.h

    r220 r314  
    2828#include <lemon/concepts/maps.h>
    2929
    30 ///\ingroup graphbits
    31 ///\file
    32 ///\brief Extenders for the digraph types
     30//\ingroup graphbits
     31//\file
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    35   /// \ingroup graphbits
    36   ///
    37   /// \brief Extender for the Digraphs
     35  // \ingroup graphbits
     36  //
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {
     
    187187    };
    188188
    189     /// \brief Base node of the iterator
    190     ///
    191     /// Returns the base node (i.e. the source in this case) of the iterator
     189    // \brief Base node of the iterator
     190    //
     191    // Returns the base node (i.e. the source in this case) of the iterator
    192192    Node baseNode(const OutArcIt &arc) const {
    193193      return Parent::source(arc);
    194194    }
    195     /// \brief Running node of the iterator
    196     ///
    197     /// Returns the running node (i.e. the target in this case) of the
    198     /// iterator
     195    // \brief Running node of the iterator
     196    //
     197    // Returns the running node (i.e. the target in this case) of the
     198    // iterator
    199199    Node runningNode(const OutArcIt &arc) const {
    200200      return Parent::target(arc);
    201201    }
    202202
    203     /// \brief Base node of the iterator
    204     ///
    205     /// Returns the base node (i.e. the target in this case) of the iterator
     203    // \brief Base node of the iterator
     204    //
     205    // Returns the base node (i.e. the target in this case) of the iterator
    206206    Node baseNode(const InArcIt &arc) const {
    207207      return Parent::target(arc);
    208208    }
    209     /// \brief Running node of the iterator
    210     ///
    211     /// Returns the running node (i.e. the source in this case) of the
    212     /// iterator
     209    // \brief Running node of the iterator
     210    //
     211    // Returns the running node (i.e. the source in this case) of the
     212    // iterator
    213213    Node runningNode(const InArcIt &arc) const {
    214214      return Parent::source(arc);
     
    228228        : Parent(digraph, value) {}
    229229
     230    private:
    230231      NodeMap& operator=(const NodeMap& cmap) {
    231232        return operator=<NodeMap>(cmap);
     
    252253        : Parent(digraph, value) {}
    253254
     255    private:
    254256      ArcMap& operator=(const ArcMap& cmap) {
    255257        return operator=<ArcMap>(cmap);
     
    324326  };
    325327
    326   /// \ingroup _graphbits
    327   ///
    328   /// \brief Extender for the Graphs
     328  // \ingroup _graphbits
     329  //
     330  // \brief Extender for the Graphs
    329331  template <typename Base>
    330332  class GraphExtender : public Base {
     
    554556    };
    555557
    556     /// \brief Base node of the iterator
    557     ///
    558     /// Returns the base node (ie. the source in this case) of the iterator
     558    // \brief Base node of the iterator
     559    //
     560    // Returns the base node (ie. the source in this case) of the iterator
    559561    Node baseNode(const OutArcIt &arc) const {
    560562      return Parent::source(static_cast<const Arc&>(arc));
    561563    }
    562     /// \brief Running node of the iterator
    563     ///
    564     /// Returns the running node (ie. the target in this case) of the
    565     /// iterator
     564    // \brief Running node of the iterator
     565    //
     566    // Returns the running node (ie. the target in this case) of the
     567    // iterator
    566568    Node runningNode(const OutArcIt &arc) const {
    567569      return Parent::target(static_cast<const Arc&>(arc));
    568570    }
    569571
    570     /// \brief Base node of the iterator
    571     ///
    572     /// Returns the base node (ie. the target in this case) of the iterator
     572    // \brief Base node of the iterator
     573    //
     574    // Returns the base node (ie. the target in this case) of the iterator
    573575    Node baseNode(const InArcIt &arc) const {
    574576      return Parent::target(static_cast<const Arc&>(arc));
    575577    }
    576     /// \brief Running node of the iterator
    577     ///
    578     /// Returns the running node (ie. the source in this case) of the
    579     /// iterator
     578    // \brief Running node of the iterator
     579    //
     580    // Returns the running node (ie. the source in this case) of the
     581    // iterator
    580582    Node runningNode(const InArcIt &arc) const {
    581583      return Parent::source(static_cast<const Arc&>(arc));
    582584    }
    583585
    584     /// Base node of the iterator
    585     ///
    586     /// Returns the base node of the iterator
     586    // Base node of the iterator
     587    //
     588    // Returns the base node of the iterator
    587589    Node baseNode(const IncEdgeIt &edge) const {
    588590      return edge._direction ? u(edge) : v(edge);
    589591    }
    590     /// Running node of the iterator
    591     ///
    592     /// Returns the running node of the iterator
     592    // Running node of the iterator
     593    //
     594    // Returns the running node of the iterator
    593595    Node runningNode(const IncEdgeIt &edge) const {
    594596      return edge._direction ? v(edge) : u(edge);
     
    609611        : Parent(graph, value) {}
    610612
     613    private:
    611614      NodeMap& operator=(const NodeMap& cmap) {
    612615        return operator=<NodeMap>(cmap);
     
    633636        : Parent(graph, value) {}
    634637
     638    private:
    635639      ArcMap& operator=(const ArcMap& cmap) {
    636640        return operator=<ArcMap>(cmap);
     
    658662        : Parent(graph, value) {}
    659663
     664    private:
    660665      EdgeMap& operator=(const EdgeMap& cmap) {
    661666        return operator=<EdgeMap>(cmap);
  • lemon/bits/map_extender.h

    r209 r314  
    2727#include <lemon/concepts/maps.h>
    2828
    29 ///\file
    30 ///\brief Extenders for iterable maps.
     29//\file
     30//\brief Extenders for iterable maps.
    3131
    3232namespace lemon {
    3333
    34   /// \ingroup graphbits
    35   ///
    36   /// \brief Extender for maps
     34  // \ingroup graphbits
     35  //
     36  // \brief Extender for maps
    3737  template <typename _Map>
    3838  class MapExtender : public _Map {
     
    6363      : Parent(graph, value) {}
    6464
     65  private:
    6566    MapExtender& operator=(const MapExtender& cmap) {
    6667      return operator=<MapExtender>(cmap);
     
    7374    }
    7475
     76  public:
    7577    class MapIt : public Item {
    7678    public:
     
    170172  };
    171173
    172   /// \ingroup graphbits
    173   ///
    174   /// \brief Extender for maps which use a subset of the items.
     174  // \ingroup graphbits
     175  //
     176  // \brief Extender for maps which use a subset of the items.
    175177  template <typename _Graph, typename _Map>
    176178  class SubMapExtender : public _Map {
     
    201203      : Parent(_graph, _value), graph(_graph) {}
    202204
     205  private:
    203206    SubMapExtender& operator=(const SubMapExtender& cmap) {
    204207      return operator=<MapExtender>(cmap);
     
    215218    }
    216219
     220  public:
    217221    class MapIt : public Item {
    218222    public:
  • lemon/bits/traits.h

    r220 r314  
    2020#define LEMON_BITS_TRAITS_H
    2121
    22 ///\file
    23 ///\brief Traits for graphs and maps
    24 ///
     22//\file
     23//\brief Traits for graphs and maps
     24//
    2525
    2626#include <lemon/bits/enable_if.h>
  • lemon/bits/vector_map.h

    r220 r314  
    2929#include <lemon/concepts/maps.h>
    3030
    31 ///\ingroup graphbits
    32 ///
    33 ///\file
    34 ///\brief Vector based graph maps.
     31//\ingroup graphbits
     32//
     33//\file
     34//\brief Vector based graph maps.
    3535namespace lemon {
    3636
    37   /// \ingroup graphbits
    38   ///
    39   /// \brief Graph map based on the std::vector storage.
    40   ///
    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.
    44   ///
    45   /// \tparam _Notifier The AlterationNotifier that will notify this map.
    46   /// \tparam _Item The item type of the graph items.
    47   /// \tparam _Value The value type of the map.
    48   /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
     37  // \ingroup graphbits
     38  //
     39  // \brief Graph map based on the std::vector storage.
     40  //
     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.
     44  //
     45  // \tparam _Graph The graph this map is attached to.
     46  // \tparam _Item The item type of the graph items.
     47  // \tparam _Value The value type of the map.
    4948  template <typename _Graph, typename _Item, typename _Value>
    5049  class VectorMap
     
    5251  private:
    5352
    54     /// The container type of the map.
     53    // The container type of the map.
    5554    typedef std::vector<_Value> Container;
    5655
    5756  public:
    5857
    59     /// The graph type of the map.
     58    // The graph type of the map.
    6059    typedef _Graph Graph;
    61     /// The item type of the map.
     60    // The item type of the map.
    6261    typedef _Item Item;
    63     /// The reference map tag.
     62    // The reference map tag.
    6463    typedef True ReferenceMapTag;
    6564
    66     /// The key type of the map.
     65    // The key type of the map.
    6766    typedef _Item Key;
    68     /// The value type of the map.
     67    // The value type of the map.
    6968    typedef _Value Value;
    7069
    71     /// The notifier type.
     70    // The notifier type.
    7271    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
    7372
    74     /// The map type.
     73    // The map type.
    7574    typedef VectorMap Map;
    76     /// The base class of the map.
     75    // The base class of the map.
    7776    typedef typename Notifier::ObserverBase Parent;
    7877
    79     /// The reference type of the map;
     78    // The reference type of the map;
    8079    typedef typename Container::reference Reference;
    81     /// The const reference type of the map;
     80    // The const reference type of the map;
    8281    typedef typename Container::const_reference ConstReference;
    8382
    8483
    85     /// \brief Constructor to attach the new map into the notifier.
    86     ///
    87     /// It constructs a map and attachs it into the notifier.
    88     /// It adds all the items of the graph to the map.
     84    // \brief Constructor to attach the new map into the notifier.
     85    //
     86    // It constructs a map and attachs it into the notifier.
     87    // It adds all the items of the graph to the map.
    8988    VectorMap(const Graph& graph) {
    9089      Parent::attach(graph.notifier(Item()));
     
    9291    }
    9392
    94     /// \brief Constructor uses given value to initialize the map.
    95     ///
    96     /// It constructs a map uses a given value to initialize the map.
    97     /// It adds all the items of the graph to the map.
     93    // \brief Constructor uses given value to initialize the map.
     94    //
     95    // It constructs a map uses a given value to initialize the map.
     96    // It adds all the items of the graph to the map.
    9897    VectorMap(const Graph& graph, const Value& value) {
    9998      Parent::attach(graph.notifier(Item()));
     
    101100    }
    102101
    103     /// \brief Copy constructor
    104     ///
    105     /// Copy constructor.
     102  private:
     103    // \brief Copy constructor
     104    //
     105    // Copy constructor.
    106106    VectorMap(const VectorMap& _copy) : Parent() {
    107107      if (_copy.attached()) {
     
    111111    }
    112112
    113     /// \brief Assign operator.
    114     ///
    115     /// This operator assigns for each item in the map the
    116     /// value mapped to the same item in the copied map.
    117     /// The parameter map should be indiced with the same
    118     /// itemset because this assign operator does not change
    119     /// the container of the map.
     113    // \brief Assign operator.
     114    //
     115    // This operator assigns for each item in the map the
     116    // value mapped to the same item in the copied map.
     117    // The parameter map should be indiced with the same
     118    // itemset because this assign operator does not change
     119    // the container of the map.
    120120    VectorMap& operator=(const VectorMap& cmap) {
    121121      return operator=<VectorMap>(cmap);
     
    123123
    124124
    125     /// \brief Template assign operator.
    126     ///
    127     /// The given parameter should be conform to the ReadMap
    128     /// concecpt and could be indiced by the current item set of
    129     /// the NodeMap. In this case the value for each item
    130     /// is assigned by the value of the given ReadMap.
     125    // \brief Template assign operator.
     126    //
     127    // The given parameter should be conform to the ReadMap
     128    // concecpt and could be indiced by the current item set of
     129    // the NodeMap. In this case the value for each item
     130    // is assigned by the value of the given ReadMap.
    131131    template <typename CMap>
    132132    VectorMap& operator=(const CMap& cmap) {
     
    142142  public:
    143143
    144     /// \brief The subcript operator.
    145     ///
    146     /// The subscript operator. The map can be subscripted by the
    147     /// actual items of the graph.
     144    // \brief The subcript operator.
     145    //
     146    // The subscript operator. The map can be subscripted by the
     147    // actual items of the graph.
    148148    Reference operator[](const Key& key) {
    149149      return container[Parent::notifier()->id(key)];
    150150    }
    151151
    152     /// \brief The const subcript operator.
    153     ///
    154     /// The const subscript operator. The map can be subscripted by the
    155     /// actual items of the graph.
     152    // \brief The const subcript operator.
     153    //
     154    // The const subscript operator. The map can be subscripted by the
     155    // actual items of the graph.
    156156    ConstReference operator[](const Key& key) const {
    157157      return container[Parent::notifier()->id(key)];
     
    159159
    160160
    161     /// \brief The setter function of the map.
    162     ///
    163     /// It the same as operator[](key) = value expression.
     161    // \brief The setter function of the map.
     162    //
     163    // It the same as operator[](key) = value expression.
    164164    void set(const Key& key, const Value& value) {
    165165      (*this)[key] = value;
     
    168168  protected:
    169169
    170     /// \brief Adds a new key to the map.
    171     ///
    172     /// It adds a new key to the map. It called by the observer notifier
    173     /// and it overrides the add() member function of the observer base.
     170    // \brief Adds a new key to the map.
     171    //
     172    // It adds a new key to the map. It called by the observer notifier
     173    // and it overrides the add() member function of the observer base.
    174174    virtual void add(const Key& key) {
    175175      int id = Parent::notifier()->id(key);
     
    179179    }
    180180
    181     /// \brief Adds more new keys to the map.
    182     ///
    183     /// It adds more new keys to the map. It called by the observer notifier
    184     /// and it overrides the add() member function of the observer base.
     181    // \brief Adds more new keys to the map.
     182    //
     183    // It adds more new keys to the map. It called by the observer notifier
     184    // and it overrides the add() member function of the observer base.
    185185    virtual void add(const std::vector<Key>& keys) {
    186186      int max = container.size() - 1;
     
    194194    }
    195195
    196     /// \brief Erase a key from the map.
    197     ///
    198     /// Erase a key from the map. It called by the observer notifier
    199     /// and it overrides the erase() member function of the observer base.
     196    // \brief Erase a key from the map.
     197    //
     198    // Erase a key from the map. It called by the observer notifier
     199    // and it overrides the erase() member function of the observer base.
    200200    virtual void erase(const Key& key) {
    201201      container[Parent::notifier()->id(key)] = Value();
    202202    }
    203203
    204     /// \brief Erase more keys from the map.
    205     ///
    206     /// Erase more keys from the map. It called by the observer notifier
    207     /// and it overrides the erase() member function of the observer base.
     204    // \brief Erase more keys from the map.
     205    //
     206    // Erase more keys from the map. It called by the observer notifier
     207    // and it overrides the erase() member function of the observer base.
    208208    virtual void erase(const std::vector<Key>& keys) {
    209209      for (int i = 0; i < int(keys.size()); ++i) {
     
    212212    }
    213213
    214     /// \brief Buildes the map.
    215     ///
    216     /// It buildes the map. It called by the observer notifier
    217     /// and it overrides the build() member function of the observer base.
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
     217    // and it overrides the build() member function of the observer base.
    218218    virtual void build() {
    219219      int size = Parent::notifier()->maxId() + 1;
     
    222222    }
    223223
    224     /// \brief Clear the map.
    225     ///
    226     /// It erase all items from the map. It called by the observer notifier
    227     /// and it overrides the clear() member function of the observer base.
     224    // \brief Clear the map.
     225    //
     226    // It erase all items from the map. It called by the observer notifier
     227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {
    229229      container.clear();
  • lemon/color.h

    r209 r313  
    9393  extern const Color DARK_CYAN;
    9494
    95   ///Map <tt>int</tt>s to different \ref Color "Color"s
     95  ///Map <tt>int</tt>s to different <tt>Color</tt>s
    9696
    9797  ///This map assigns one of the predefined \ref Color "Color"s to
  • lemon/concept_check.h

    r209 r285  
    1717 */
    1818
    19 // This file contains a modified version of the concept checking
    20 // utility from BOOST.
    21 // See the appropriate copyright notice below.
    22 
    23 // (C) Copyright Jeremy Siek 2000.
    24 // Distributed under the Boost Software License, Version 1.0. (See
    25 // accompanying file LICENSE_1_0.txt or copy at
    26 // http://www.boost.org/LICENSE_1_0.txt)
    27 //
    28 // Revision History:
    29 //   05 May   2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
    30 //   02 April 2001: Removed limits header altogether. (Jeremy Siek)
    31 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
    32 //
    33 
    34 // See http://www.boost.org/libs/concept_check for documentation.
     19// The contents of this file was inspired by the concept checking
     20// utility of the BOOST library (http://www.boost.org).
    3521
    3622///\file
    3723///\brief Basic utilities for concept checking.
    3824///
    39 ///\todo Are we still using BOOST concept checking utility?
    40 ///Is the BOOST copyright notice necessary?
    4125
    4226#ifndef LEMON_CONCEPT_CHECK_H
  • lemon/concepts/digraph.h

    r220 r263  
    435435        NodeMap(const Digraph&, T) { }
    436436
     437      private:
    437438        ///Copy constructor
    438439        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     
    457458        ///\e
    458459        ArcMap(const Digraph&, T) { }
     460      private:
    459461        ///Copy constructor
    460462        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
  • lemon/concepts/graph.h

    r220 r263  
    513513        NodeMap(const Graph&, T) { }
    514514
     515      private:
    515516        ///Copy constructor
    516517        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
     
    536537        ///\e
    537538        ArcMap(const Graph&, T) { }
     539      private:
    538540        ///Copy constructor
    539541        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
     
    559561        ///\e
    560562        EdgeMap(const Graph&, T) { }
     563      private:
    561564        ///Copy constructor
    562565        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
  • lemon/concepts/graph_components.h

    r220 r313  
    983983    ///
    984984    /// This class describes the common interface of the graph maps
    985     /// (NodeMap, ArcMap), that is \ref maps-page "maps" which can be used to
     985    /// (NodeMap, ArcMap), that is maps that can be used to
    986986    /// associate data to graph descriptors (nodes or arcs).
    987987    template <typename _Graph, typename _Item, typename _Value>
     
    10061006      /// Construct a new map for the graph and initalise the values.
    10071007      GraphMap(const Graph&, const Value&) {}
     1008
     1009    private:
    10081010      /// \brief Copy constructor.
    10091011      ///
     
    10221024      }
    10231025
     1026    public:
    10241027      template<typename _Map>
    10251028      struct Constraints {
     
    10311034          _Map a2(g,t);
    10321035          // Copy constructor.
    1033           _Map b(c);
    1034 
    1035           ReadMap<Key, Value> cmap;
    1036           b = cmap;
    1037 
     1036          // _Map b(c);
     1037
     1038          // ReadMap<Key, Value> cmap;
     1039          // b = cmap;
     1040
     1041          ignore_unused_variable_warning(a);
    10381042          ignore_unused_variable_warning(a2);
    1039           ignore_unused_variable_warning(b);
     1043          // ignore_unused_variable_warning(b);
    10401044        }
    10411045
     
    10831087          : Parent(digraph, value) {}
    10841088
     1089      private:
    10851090        /// \brief Copy constructor.
    10861091        ///
     
    11201125          : Parent(digraph, value) {}
    11211126
     1127      private:
    11221128        /// \brief Copy constructor.
    11231129        ///
     
    12161222          : Parent(graph, value) {}
    12171223
     1224      private:
    12181225        /// \brief Copy constructor.
    12191226        ///
  • lemon/concepts/heap.h

    r220 r290  
    130130      /// Otherwise it inserts the given item with the given priority.
    131131      ///
    132       /// It may throw an \ref UnderflowPriorityException.
    133132      /// \param i The item.
    134133      /// \param p The priority.
  • lemon/concepts/maps.h

    r220 r314  
    2323#include <lemon/concept_check.h>
    2424
    25 ///\ingroup concept
     25///\ingroup map_concepts
    2626///\file
    2727///\brief The concept of maps.
     
    3131  namespace concepts {
    3232
    33     /// \addtogroup concept
     33    /// \addtogroup map_concepts
    3434    /// @{
    3535
  • lemon/concepts/path.h

    r236 r281  
    2121///\brief Classes for representing paths in digraphs.
    2222///
    23 ///\todo Iterators have obsolete style
    2423
    2524#ifndef LEMON_CONCEPT_PATH_H
     
    6766      /// \brief Template assigment
    6867      template <typename CPath>
    69       Path& operator=(const CPath& cpath) {}
     68      Path& operator=(const CPath& cpath) {
     69        ignore_unused_variable_warning(cpath);
     70        return *this;
     71      }
    7072
    7173      /// Length of the path ie. the number of arcs in the path.
  • lemon/core.h

    r233 r319  
    2525#include <lemon/bits/enable_if.h>
    2626#include <lemon/bits/traits.h>
     27#include <lemon/assert.h>
    2728
    2829///\file
     
    5960  /// @{
    6061
    61   ///Creates convenience typedefs for the digraph types and iterators
    62 
    63   ///This \c \#define creates convenience typedefs for the following types
    64   ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
     62  ///Create convenience typedefs for the digraph types and iterators
     63
     64  ///This \c \#define creates convenient type definitions for the following
     65  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
    6566  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
    6667  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
     
    8384  typedef Digraph::ArcMap<double> DoubleArcMap
    8485
    85   ///Creates convenience typedefs for the digraph types and iterators
     86  ///Create convenience typedefs for the digraph types and iterators
    8687
    8788  ///\see DIGRAPH_TYPEDEFS
     
    103104  typedef typename Digraph::template ArcMap<double> DoubleArcMap
    104105
    105   ///Creates convenience typedefs for the graph types and iterators
    106 
    107   ///This \c \#define creates the same convenience typedefs as defined
     106  ///Create convenience typedefs for the graph types and iterators
     107
     108  ///This \c \#define creates the same convenient type definitions as defined
    108109  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
    109110  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
     
    111112  ///
    112113  ///\note If the graph type is a dependent type, ie. the graph type depend
    113   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
     114  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
    114115  ///macro.
    115116#define GRAPH_TYPEDEFS(Graph)                                           \
     
    122123  typedef Graph::EdgeMap<double> DoubleEdgeMap
    123124
    124   ///Creates convenience typedefs for the graph types and iterators
     125  ///Create convenience typedefs for the graph types and iterators
    125126
    126127  ///\see GRAPH_TYPEDEFS
     
    137138  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
    138139
    139   /// \brief Function to count the items in the graph.
    140   ///
    141   /// This function counts the items (nodes, arcs etc) in the graph.
    142   /// The complexity of the function is O(n) because
     140  /// \brief Function to count the items in a graph.
     141  ///
     142  /// This function counts the items (nodes, arcs etc.) in a graph.
     143  /// The complexity of the function is linear because
    143144  /// it iterates on all of the items.
    144145  template <typename Graph, typename Item>
     
    177178  ///
    178179  /// This function counts the nodes in the graph.
    179   /// The complexity of the function is O(n) but for some
    180   /// graph structures it is specialized to run in O(1).
    181   ///
    182   /// If the graph contains a \e nodeNum() member function and a
    183   /// \e NodeNumTag tag then this function calls directly the member
     180  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
     181  /// graph structures it is specialized to run in <em>O</em>(1).
     182  ///
     183  /// \note If the graph contains a \c nodeNum() member function and a
     184  /// \c NodeNumTag tag then this function calls directly the member
    184185  /// function to query the cardinality of the node set.
    185186  template <typename Graph>
     
    213214  ///
    214215  /// This function counts the arcs in the graph.
    215   /// The complexity of the function is O(e) but for some
    216   /// graph structures it is specialized to run in O(1).
    217   ///
    218   /// If the graph contains a \e arcNum() member function and a
    219   /// \e EdgeNumTag tag then this function calls directly the member
     216  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
     217  /// graph structures it is specialized to run in <em>O</em>(1).
     218  ///
     219  /// \note If the graph contains a \c arcNum() member function and a
     220  /// \c ArcNumTag tag then this function calls directly the member
    220221  /// function to query the cardinality of the arc set.
    221222  template <typename Graph>
     
    225226
    226227  // Edge counting:
     228
    227229  namespace _core_bits {
    228230
     
    248250  ///
    249251  /// This function counts the edges in the graph.
    250   /// The complexity of the function is O(m) but for some
    251   /// graph structures it is specialized to run in O(1).
    252   ///
    253   /// If the graph contains a \e edgeNum() member function and a
    254   /// \e EdgeNumTag tag then this function calls directly the member
     252  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
     253  /// graph structures it is specialized to run in <em>O</em>(1).
     254  ///
     255  /// \note If the graph contains a \c edgeNum() member function and a
     256  /// \c EdgeNumTag tag then this function calls directly the member
    255257  /// function to query the cardinality of the edge set.
    256258  template <typename Graph>
     
    273275  ///
    274276  /// This function counts the number of the out-arcs from node \c n
    275   /// in the graph.
     277  /// in the graph \c g.
    276278  template <typename Graph>
    277   inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) {
    278     return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
     279  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) {
     280    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
    279281  }
    280282
     
    282284  ///
    283285  /// This function counts the number of the in-arcs to node \c n
    284   /// in the graph.
     286  /// in the graph \c g.
    285287  template <typename Graph>
    286   inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) {
    287     return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
     288  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) {
     289    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
    288290  }
    289291
     
    291293  ///
    292294  /// This function counts the number of the inc-edges to node \c n
    293   /// in the graph.
     295  /// in the undirected graph \c g.
    294296  template <typename Graph>
    295   inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
    296     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
     297  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) {
     298    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
    297299  }
    298300
     
    308310
    309311    template <typename Digraph, typename Item, typename RefMap,
    310               typename ToMap, typename FromMap>
     312              typename FromMap, typename ToMap>
    311313    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
    312314    public:
    313315
    314       MapCopy(ToMap& tmap, const FromMap& map)
    315         : _tmap(tmap), _map(map) {}
     316      MapCopy(const FromMap& map, ToMap& tmap)
     317        : _map(map), _tmap(tmap) {}
    316318
    317319      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
     
    323325
    324326    private:
     327      const FromMap& _map;
    325328      ToMap& _tmap;
    326       const FromMap& _map;
    327329    };
    328330
     
    331333    public:
    332334
    333       ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
     335      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
    334336
    335337      virtual void copy(const Digraph&, const RefMap& refMap) {
     
    338340
    339341    private:
     342      Item _item;
    340343      It& _it;
    341       Item _item;
    342344    };
    343345
     
    380382    struct DigraphCopySelector {
    381383      template <typename From, typename NodeRefMap, typename ArcRefMap>
    382       static void copy(Digraph &to, const From& from,
     384      static void copy(const From& from, Digraph &to,
    383385                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
    384386        for (typename From::NodeIt it(from); it != INVALID; ++it) {
     
    398400    {
    399401      template <typename From, typename NodeRefMap, typename ArcRefMap>
    400       static void copy(Digraph &to, const From& from,
     402      static void copy(const From& from, Digraph &to,
    401403                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
    402404        to.build(from, nodeRefMap, arcRefMap);
     
    407409    struct GraphCopySelector {
    408410      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    409       static void copy(Graph &to, const From& from,
     411      static void copy(const From& from, Graph &to,
    410412                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    411413        for (typename From::NodeIt it(from); it != INVALID; ++it) {
     
    425427    {
    426428      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    427       static void copy(Graph &to, const From& from,
     429      static void copy(const From& from, Graph &to,
    428430                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    429431        to.build(from, nodeRefMap, edgeRefMap);
     
    436438  ///
    437439  /// Class to copy a digraph to another digraph (duplicate a digraph). The
    438   /// simplest way of using it is through the \c copyDigraph() function.
    439   ///
    440   /// This class not just make a copy of a graph, but it can create
     440  /// simplest way of using it is through the \c digraphCopy() function.
     441  ///
     442  /// This class not only make a copy of a digraph, but it can create
    441443  /// references and cross references between the nodes and arcs of
    442   /// the two graphs, it can copy maps for use with the newly created
    443   /// graph and copy nodes and arcs.
    444   ///
    445   /// To make a copy from a graph, first an instance of DigraphCopy
    446   /// should be created, then the data belongs to the graph should
     444  /// the two digraphs, and it can copy maps to use with the newly created
     445  /// digraph.
     446  ///
     447  /// To make a copy from a digraph, first an instance of DigraphCopy
     448  /// should be created, then the data belongs to the digraph should
    447449  /// assigned to copy. In the end, the \c run() member should be
    448450  /// called.
    449451  ///
    450   /// The next code copies a graph with several data:
     452  /// The next code copies a digraph with several data:
    451453  ///\code
    452   ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
    453   ///  // create a reference for the nodes
     454  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
     455  ///  // Create references for the nodes
    454456  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
    455   ///  dc.nodeRef(nr);
    456   ///  // create a cross reference (inverse) for the arcs
     457  ///  cg.nodeRef(nr);
     458  ///  // Create cross references (inverse) for the arcs
    457459  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
    458   ///  dc.arcCrossRef(acr);
    459   ///  // copy an arc map
     460  ///  cg.arcCrossRef(acr);
     461  ///  // Copy an arc map
    460462  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
    461463  ///  NewGraph::ArcMap<double> namap(new_graph);
    462   ///  dc.arcMap(namap, oamap);
    463   ///  // copy a node
     464  ///  cg.arcMap(oamap, namap);
     465  ///  // Copy a node
    464466  ///  OrigGraph::Node on;
    465467  ///  NewGraph::Node nn;
    466   ///  dc.node(nn, on);
    467   ///  // Executions of copy
    468   ///  dc.run();
     468  ///  cg.node(on, nn);
     469  ///  // Execute copying
     470  ///  cg.run();
    469471  ///\endcode
    470   template <typename To, typename From>
     472  template <typename From, typename To>
    471473  class DigraphCopy {
    472474  private:
     
    483485    typedef typename From::template ArcMap<TArc> ArcRefMap;
    484486
    485 
    486487  public:
    487488
    488 
    489     /// \brief Constructor for the DigraphCopy.
    490     ///
    491     /// It copies the content of the \c _from digraph into the
    492     /// \c _to digraph.
    493     DigraphCopy(To& to, const From& from)
     489    /// \brief Constructor of DigraphCopy.
     490    ///
     491    /// Constructor of DigraphCopy for copying the content of the
     492    /// \c from digraph into the \c to digraph.
     493    DigraphCopy(const From& from, To& to)
    494494      : _from(from), _to(to) {}
    495495
    496     /// \brief Destructor of the DigraphCopy
    497     ///
    498     /// Destructor of the DigraphCopy
     496    /// \brief Destructor of DigraphCopy
     497    ///
     498    /// Destructor of DigraphCopy.
    499499    ~DigraphCopy() {
    500500      for (int i = 0; i < int(_node_maps.size()); ++i) {
     
    507507    }
    508508
    509     /// \brief Copies the node references into the given map.
    510     ///
    511     /// Copies the node references into the given map. The parameter
    512     /// should be a map, which key type is the Node type of the source
    513     /// graph, while the value type is the Node type of the
    514     /// destination graph.
     509    /// \brief Copy the node references into the given map.
     510    ///
     511    /// This function copies the node references into the given map.
     512    /// The parameter should be a map, whose key type is the Node type of
     513    /// the source digraph, while the value type is the Node type of the
     514    /// destination digraph.
    515515    template <typename NodeRef>
    516516    DigraphCopy& nodeRef(NodeRef& map) {
     
    520520    }
    521521
    522     /// \brief Copies the node cross references into the given map.
    523     ///
    524     ///  Copies the node cross references (reverse references) into
    525     ///  the given map. The parameter should be a map, which key type
    526     ///  is the Node type of the destination graph, while the value type is
    527     ///  the Node type of the source graph.
     522    /// \brief Copy the node cross references into the given map.
     523    ///
     524    /// This function copies the node cross references (reverse references)
     525    /// into the given map. The parameter should be a map, whose key type
     526    /// is the Node type of the destination digraph, while the value type is
     527    /// the Node type of the source digraph.
    528528    template <typename NodeCrossRef>
    529529    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
     
    533533    }
    534534
    535     /// \brief Make copy of the given map.
    536     ///
    537     /// Makes copy of the given map for the newly created digraph.
    538     /// The new map's key type is the destination graph's node type,
    539     /// and the copied map's key type is the source graph's node type.
    540     template <typename ToMap, typename FromMap>
    541     DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
     535    /// \brief Make a copy of the given node map.
     536    ///
     537    /// This function makes a copy of the given node map for the newly
     538    /// created digraph.
     539    /// The key type of the new map \c tmap should be the Node type of the
     540    /// destination digraph, and the key type of the original map \c map
     541    /// should be the Node type of the source digraph.
     542    template <typename FromMap, typename ToMap>
     543    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
    542544      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
    543                            NodeRefMap, ToMap, FromMap>(tmap, map));
     545                           NodeRefMap, FromMap, ToMap>(map, tmap));
    544546      return *this;
    545547    }
     
    547549    /// \brief Make a copy of the given node.
    548550    ///
    549     /// Make a copy of the given node.
    550     DigraphCopy& node(TNode& tnode, const Node& snode) {
     551    /// This function makes a copy of the given node.
     552    DigraphCopy& node(const Node& node, TNode& tnode) {
    551553      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
    552                            NodeRefMap, TNode>(tnode, snode));
    553       return *this;
    554     }
    555 
    556     /// \brief Copies the arc references into the given map.
    557     ///
    558     /// Copies the arc references into the given map.
     554                           NodeRefMap, TNode>(node, tnode));
     555      return *this;
     556    }
     557
     558    /// \brief Copy the arc references into the given map.
     559    ///
     560    /// This function copies the arc references into the given map.
     561    /// The parameter should be a map, whose key type is the Arc type of
     562    /// the source digraph, while the value type is the Arc type of the
     563    /// destination digraph.
    559564    template <typename ArcRef>
    560565    DigraphCopy& arcRef(ArcRef& map) {
     
    564569    }
    565570
    566     /// \brief Copies the arc cross references into the given map.
    567     ///
    568     ///  Copies the arc cross references (reverse references) into
    569     ///  the given map.
     571    /// \brief Copy the arc cross references into the given map.
     572    ///
     573    /// This function copies the arc cross references (reverse references)
     574    /// into the given map. The parameter should be a map, whose key type
     575    /// is the Arc type of the destination digraph, while the value type is
     576    /// the Arc type of the source digraph.
    570577    template <typename ArcCrossRef>
    571578    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
     
    575582    }
    576583
    577     /// \brief Make copy of the given map.
    578     ///
    579     /// Makes copy of the given map for the newly created digraph.
    580     /// The new map's key type is the to digraph's arc type,
    581     /// and the copied map's key type is the from digraph's arc
    582     /// type.
    583     template <typename ToMap, typename FromMap>
    584     DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
     584    /// \brief Make a copy of the given arc map.
     585    ///
     586    /// This function makes a copy of the given arc map for the newly
     587    /// created digraph.
     588    /// The key type of the new map \c tmap should be the Arc type of the
     589    /// destination digraph, and the key type of the original map \c map
     590    /// should be the Arc type of the source digraph.
     591    template <typename FromMap, typename ToMap>
     592    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
    585593      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
    586                           ArcRefMap, ToMap, FromMap>(tmap, map));
     594                          ArcRefMap, FromMap, ToMap>(map, tmap));
    587595      return *this;
    588596    }
     
    590598    /// \brief Make a copy of the given arc.
    591599    ///
    592     /// Make a copy of the given arc.
    593     DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
     600    /// This function makes a copy of the given arc.
     601    DigraphCopy& arc(const Arc& arc, TArc& tarc) {
    594602      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
    595                           ArcRefMap, TArc>(tarc, sarc));
    596       return *this;
    597     }
    598 
    599     /// \brief Executes the copies.
    600     ///
    601     /// Executes the copies.
     603                          ArcRefMap, TArc>(arc, tarc));
     604      return *this;
     605    }
     606
     607    /// \brief Execute copying.
     608    ///
     609    /// This function executes the copying of the digraph along with the
     610    /// copying of the assigned data.
    602611    void run() {
    603612      NodeRefMap nodeRefMap(_from);
    604613      ArcRefMap arcRefMap(_from);
    605614      _core_bits::DigraphCopySelector<To>::
    606         copy(_to, _from, nodeRefMap, arcRefMap);
     615        copy(_from, _to, nodeRefMap, arcRefMap);
    607616      for (int i = 0; i < int(_node_maps.size()); ++i) {
    608617        _node_maps[i]->copy(_from, nodeRefMap);
     
    615624  protected:
    616625
    617 
    618626    const From& _from;
    619627    To& _to;
    620628
    621629    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
    622     _node_maps;
     630      _node_maps;
    623631
    624632    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    625     _arc_maps;
     633      _arc_maps;
    626634
    627635  };
     
    629637  /// \brief Copy a digraph to another digraph.
    630638  ///
    631   /// Copy a digraph to another digraph. The complete usage of the
    632   /// function is detailed in the DigraphCopy class, but a short
    633   /// example shows a basic work:
     639  /// This function copies a digraph to another digraph.
     640  /// The complete usage of it is detailed in the DigraphCopy class, but
     641  /// a short example shows a basic work:
    634642  ///\code
    635   /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
     643  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
    636644  ///\endcode
    637645  ///
    638646  /// After the copy the \c nr map will contain the mapping from the
    639647  /// nodes of the \c from digraph to the nodes of the \c to digraph and
    640   /// \c ecr will contain the mapping from the arcs of the \c to digraph
     648  /// \c acr will contain the mapping from the arcs of the \c to digraph
    641649  /// to the arcs of the \c from digraph.
    642650  ///
    643651  /// \see DigraphCopy
    644   template <typename To, typename From>
    645   DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
    646     return DigraphCopy<To, From>(to, from);
     652  template <typename From, typename To>
     653  DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
     654    return DigraphCopy<From, To>(from, to);
    647655  }
    648656
     
    650658  ///
    651659  /// Class to copy a graph to another graph (duplicate a graph). The
    652   /// simplest way of using it is through the \c copyGraph() function.
    653   ///
    654   /// This class not just make a copy of a graph, but it can create
     660  /// simplest way of using it is through the \c graphCopy() function.
     661  ///
     662  /// This class not only make a copy of a graph, but it can create
    655663  /// references and cross references between the nodes, edges and arcs of
    656   /// the two graphs, it can copy maps for use with the newly created
    657   /// graph and copy nodes, edges and arcs.
     664  /// the two graphs, and it can copy maps for using with the newly created
     665  /// graph.
    658666  ///
    659667  /// To make a copy from a graph, first an instance of GraphCopy
     
    664672  /// The next code copies a graph with several data:
    665673  ///\code
    666   ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
    667   ///  // create a reference for the nodes
     674  ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
     675  ///  // Create references for the nodes
    668676  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
    669   ///  dc.nodeRef(nr);
    670   ///  // create a cross reference (inverse) for the edges
    671   ///  NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
    672   ///  dc.edgeCrossRef(ecr);
    673   ///  // copy an arc map
    674   ///  OrigGraph::ArcMap<double> oamap(orig_graph);
    675   ///  NewGraph::ArcMap<double> namap(new_graph);
    676   ///  dc.arcMap(namap, oamap);
    677   ///  // copy a node
     677  ///  cg.nodeRef(nr);
     678  ///  // Create cross references (inverse) for the edges
     679  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
     680  ///  cg.edgeCrossRef(ecr);
     681  ///  // Copy an edge map
     682  ///  OrigGraph::EdgeMap<double> oemap(orig_graph);
     683  ///  NewGraph::EdgeMap<double> nemap(new_graph);
     684  ///  cg.edgeMap(oemap, nemap);
     685  ///  // Copy a node
    678686  ///  OrigGraph::Node on;
    679687  ///  NewGraph::Node nn;
    680   ///  dc.node(nn, on);
    681   ///  // Executions of copy
    682   ///  dc.run();
     688  ///  cg.node(on, nn);
     689  ///  // Execute copying
     690  ///  cg.run();
    683691  ///\endcode
    684   template <typename To, typename From>
     692  template <typename From, typename To>
    685693  class GraphCopy {
    686694  private:
     
    701709
    702710    struct ArcRefMap {
    703       ArcRefMap(const To& to, const From& from,
     711      ArcRefMap(const From& from, const To& to,
    704712                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
    705         : _to(to), _from(from),
     713        : _from(from), _to(to),
    706714          _edge_ref(edge_ref), _node_ref(node_ref) {}
    707715
     
    717725      }
    718726
     727      const From& _from;
    719728      const To& _to;
    720       const From& _from;
    721729      const EdgeRefMap& _edge_ref;
    722730      const NodeRefMap& _node_ref;
    723731    };
    724732
    725 
    726733  public:
    727734
    728 
    729     /// \brief Constructor for the GraphCopy.
    730     ///
    731     /// It copies the content of the \c _from graph into the
    732     /// \c _to graph.
    733     GraphCopy(To& to, const From& from)
     735    /// \brief Constructor of GraphCopy.
     736    ///
     737    /// Constructor of GraphCopy for copying the content of the
     738    /// \c from graph into the \c to graph.
     739    GraphCopy(const From& from, To& to)
    734740      : _from(from), _to(to) {}
    735741
    736     /// \brief Destructor of the GraphCopy
    737     ///
    738     /// Destructor of the GraphCopy
     742    /// \brief Destructor of GraphCopy
     743    ///
     744    /// Destructor of GraphCopy.
    739745    ~GraphCopy() {
    740746      for (int i = 0; i < int(_node_maps.size()); ++i) {
     
    747753        delete _edge_maps[i];
    748754      }
    749 
    750     }
    751 
    752     /// \brief Copies the node references into the given map.
    753     ///
    754     /// Copies the node references into the given map.
     755    }
     756
     757    /// \brief Copy the node references into the given map.
     758    ///
     759    /// This function copies the node references into the given map.
     760    /// The parameter should be a map, whose key type is the Node type of
     761    /// the source graph, while the value type is the Node type of the
     762    /// destination graph.
    755763    template <typename NodeRef>
    756764    GraphCopy& nodeRef(NodeRef& map) {
     
    760768    }
    761769
    762     /// \brief Copies the node cross references into the given map.
    763     ///
    764     ///  Copies the node cross references (reverse references) into
    765     ///  the given map.
     770    /// \brief Copy the node cross references into the given map.
     771    ///
     772    /// This function copies the node cross references (reverse references)
     773    /// into the given map. The parameter should be a map, whose key type
     774    /// is the Node type of the destination graph, while the value type is
     775    /// the Node type of the source graph.
    766776    template <typename NodeCrossRef>
    767777    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
     
    771781    }
    772782
    773     /// \brief Make copy of the given map.
    774     ///
    775     /// Makes copy of the given map for the newly created graph.
    776     /// The new map's key type is the to graph's node type,
    777     /// and the copied map's key type is the from graph's node
    778     /// type.
    779     template <typename ToMap, typename FromMap>
    780     GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
     783    /// \brief Make a copy of the given node map.
     784    ///
     785    /// This function makes a copy of the given node map for the newly
     786    /// created graph.
     787    /// The key type of the new map \c tmap should be the Node type of the
     788    /// destination graph, and the key type of the original map \c map
     789    /// should be the Node type of the source graph.
     790    template <typename FromMap, typename ToMap>
     791    GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
    781792      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
    782                            NodeRefMap, ToMap, FromMap>(tmap, map));
     793                           NodeRefMap, FromMap, ToMap>(map, tmap));
    783794      return *this;
    784795    }
     
    786797    /// \brief Make a copy of the given node.
    787798    ///
    788     /// Make a copy of the given node.
    789     GraphCopy& node(TNode& tnode, const Node& snode) {
     799    /// This function makes a copy of the given node.
     800    GraphCopy& node(const Node& node, TNode& tnode) {
    790801      _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
    791                            NodeRefMap, TNode>(tnode, snode));
    792       return *this;
    793     }
    794 
    795     /// \brief Copies the arc references into the given map.
    796     ///
    797     /// Copies the arc references into the given map.
     802                           NodeRefMap, TNode>(node, tnode));
     803      return *this;
     804    }
     805
     806    /// \brief Copy the arc references into the given map.
     807    ///
     808    /// This function copies the arc references into the given map.
     809    /// The parameter should be a map, whose key type is the Arc type of
     810    /// the source graph, while the value type is the Arc type of the
     811    /// destination graph.
    798812    template <typename ArcRef>
    799813    GraphCopy& arcRef(ArcRef& map) {
     
    803817    }
    804818
    805     /// \brief Copies the arc cross references into the given map.
    806     ///
    807     ///  Copies the arc cross references (reverse references) into
    808     ///  the given map.
     819    /// \brief Copy the arc cross references into the given map.
     820    ///
     821    /// This function copies the arc cross references (reverse references)
     822    /// into the given map. The parameter should be a map, whose key type
     823    /// is the Arc type of the destination graph, while the value type is
     824    /// the Arc type of the source graph.
    809825    template <typename ArcCrossRef>
    810826    GraphCopy& arcCrossRef(ArcCrossRef& map) {
     
    814830    }
    815831
    816     /// \brief Make copy of the given map.
    817     ///
    818     /// Makes copy of the given map for the newly created graph.
    819     /// The new map's key type is the to graph's arc type,
    820     /// and the copied map's key type is the from graph's arc
    821     /// type.
    822     template <typename ToMap, typename FromMap>
    823     GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
     832    /// \brief Make a copy of the given arc map.
     833    ///
     834    /// This function makes a copy of the given arc map for the newly
     835    /// created graph.
     836    /// The key type of the new map \c tmap should be the Arc type of the
     837    /// destination graph, and the key type of the original map \c map
     838    /// should be the Arc type of the source graph.
     839    template <typename FromMap, typename ToMap>
     840    GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
    824841      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
    825                           ArcRefMap, ToMap, FromMap>(tmap, map));
     842                          ArcRefMap, FromMap, ToMap>(map, tmap));
    826843      return *this;
    827844    }
     
    829846    /// \brief Make a copy of the given arc.
    830847    ///
    831     /// Make a copy of the given arc.
    832     GraphCopy& arc(TArc& tarc, const Arc& sarc) {
     848    /// This function makes a copy of the given arc.
     849    GraphCopy& arc(const Arc& arc, TArc& tarc) {
    833850      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
    834                           ArcRefMap, TArc>(tarc, sarc));
    835       return *this;
    836     }
    837 
    838     /// \brief Copies the edge references into the given map.
    839     ///
    840     /// Copies the edge references into the given map.
     851                          ArcRefMap, TArc>(arc, tarc));
     852      return *this;
     853    }
     854
     855    /// \brief Copy the edge references into the given map.
     856    ///
     857    /// This function copies the edge references into the given map.
     858    /// The parameter should be a map, whose key type is the Edge type of
     859    /// the source graph, while the value type is the Edge type of the
     860    /// destination graph.
    841861    template <typename EdgeRef>
    842862    GraphCopy& edgeRef(EdgeRef& map) {
     
    846866    }
    847867
    848     /// \brief Copies the edge cross references into the given map.
    849     ///
    850     /// Copies the edge cross references (reverse
    851     /// references) into the given map.
     868    /// \brief Copy the edge cross references into the given map.
     869    ///
     870    /// This function copies the edge cross references (reverse references)
     871    /// into the given map. The parameter should be a map, whose key type
     872    /// is the Edge type of the destination graph, while the value type is
     873    /// the Edge type of the source graph.
    852874    template <typename EdgeCrossRef>
    853875    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
     
    857879    }
    858880
    859     /// \brief Make copy of the given map.
    860     ///
    861     /// Makes copy of the given map for the newly created graph.
    862     /// The new map's key type is the to graph's edge type,
    863     /// and the copied map's key type is the from graph's edge
    864     /// type.
    865     template <typename ToMap, typename FromMap>
    866     GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
     881    /// \brief Make a copy of the given edge map.
     882    ///
     883    /// This function makes a copy of the given edge map for the newly
     884    /// created graph.
     885    /// The key type of the new map \c tmap should be the Edge type of the
     886    /// destination graph, and the key type of the original map \c map
     887    /// should be the Edge type of the source graph.
     888    template <typename FromMap, typename ToMap>
     889    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
    867890      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
    868                            EdgeRefMap, ToMap, FromMap>(tmap, map));
     891                           EdgeRefMap, FromMap, ToMap>(map, tmap));
    869892      return *this;
    870893    }
     
    872895    /// \brief Make a copy of the given edge.
    873896    ///
    874     /// Make a copy of the given edge.
    875     GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
     897    /// This function makes a copy of the given edge.
     898    GraphCopy& edge(const Edge& edge, TEdge& tedge) {
    876899      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
    877                            EdgeRefMap, TEdge>(tedge, sedge));
    878       return *this;
    879     }
    880 
    881     /// \brief Executes the copies.
    882     ///
    883     /// Executes the copies.
     900                           EdgeRefMap, TEdge>(edge, tedge));
     901      return *this;
     902    }
     903
     904    /// \brief Execute copying.
     905    ///
     906    /// This function executes the copying of the graph along with the
     907    /// copying of the assigned data.
    884908    void run() {
    885909      NodeRefMap nodeRefMap(_from);
    886910      EdgeRefMap edgeRefMap(_from);
    887       ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
     911      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
    888912      _core_bits::GraphCopySelector<To>::
    889         copy(_to, _from, nodeRefMap, edgeRefMap);
     913        copy(_from, _to, nodeRefMap, edgeRefMap);
    890914      for (int i = 0; i < int(_node_maps.size()); ++i) {
    891915        _node_maps[i]->copy(_from, nodeRefMap);
     
    905929
    906930    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
    907     _node_maps;
     931      _node_maps;
    908932
    909933    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    910     _arc_maps;
     934      _arc_maps;
    911935
    912936    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
    913     _edge_maps;
     937      _edge_maps;
    914938
    915939  };
     
    917941  /// \brief Copy a graph to another graph.
    918942  ///
    919   /// Copy a graph to another graph. The complete usage of the
    920   /// function is detailed in the GraphCopy class, but a short
    921   /// example shows a basic work:
     943  /// This function copies a graph to another graph.
     944  /// The complete usage of it is detailed in the GraphCopy class,
     945  /// but a short example shows a basic work:
    922946  ///\code
    923   /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
     947  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
    924948  ///\endcode
    925949  ///
    926950  /// After the copy the \c nr map will contain the mapping from the
    927951  /// nodes of the \c from graph to the nodes of the \c to graph and
    928   /// \c ecr will contain the mapping from the arcs of the \c to graph
    929   /// to the arcs of the \c from graph.
     952  /// \c ecr will contain the mapping from the edges of the \c to graph
     953  /// to the edges of the \c from graph.
    930954  ///
    931955  /// \see GraphCopy
    932   template <typename To, typename From>
    933   GraphCopy<To, From>
    934   copyGraph(To& to, const From& from) {
    935     return GraphCopy<To, From>(to, from);
     956  template <typename From, typename To>
     957  GraphCopy<From, To>
     958  graphCopy(const From& from, To& to) {
     959    return GraphCopy<From, To>(from, to);
    936960  }
    937961
     
    958982    struct FindArcSelector<
    959983      Graph,
    960       typename enable_if<typename Graph::FindEdgeTag, void>::type>
     984      typename enable_if<typename Graph::FindArcTag, void>::type>
    961985    {
    962986      typedef typename Graph::Node Node;
     
    968992  }
    969993
    970   /// \brief Finds an arc between two nodes of a graph.
    971   ///
    972   /// Finds an arc from node \c u to node \c v in graph \c g.
     994  /// \brief Find an arc between two nodes of a digraph.
     995  ///
     996  /// This function finds an arc from node \c u to node \c v in the
     997  /// digraph \c g.
    973998  ///
    974999  /// If \c prev is \ref INVALID (this is the default value), then
     
    9791004  /// Thus you can iterate through each arc from \c u to \c v as it follows.
    9801005  ///\code
    981   /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
     1006  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
    9821007  ///   ...
    9831008  /// }
    9841009  ///\endcode
    9851010  ///
    986   ///\sa ArcLookUp
    987   ///\sa AllArcLookUp
    988   ///\sa DynArcLookUp
     1011  /// \note \ref ConArcIt provides iterator interface for the same
     1012  /// functionality.
     1013  ///
    9891014  ///\sa ConArcIt
     1015  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    9901016  template <typename Graph>
    9911017  inline typename Graph::Arc
     
    9951021  }
    9961022
    997   /// \brief Iterator for iterating on arcs connected the same nodes.
    998   ///
    999   /// Iterator for iterating on arcs connected the same nodes. It is
    1000   /// higher level interface for the findArc() function. You can
     1023  /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
     1024  ///
     1025  /// Iterator for iterating on parallel arcs connecting the same nodes. It is
     1026  /// a higher level interface for the \ref findArc() function. You can
    10011027  /// use it the following way:
    10021028  ///\code
     
    10071033  ///
    10081034  ///\sa findArc()
    1009   ///\sa ArcLookUp
    1010   ///\sa AllArcLookUp
    1011   ///\sa DynArcLookUp
     1035  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    10121036  template <typename _Graph>
    10131037  class ConArcIt : public _Graph::Arc {
     
    10221046    /// \brief Constructor.
    10231047    ///
    1024     /// Construct a new ConArcIt iterating on the arcs which
    1025     /// connects the \c u and \c v node.
     1048    /// Construct a new ConArcIt iterating on the arcs that
     1049    /// connects nodes \c u and \c v.
    10261050    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
    10271051      Parent::operator=(findArc(_graph, u, v));
     
    10301054    /// \brief Constructor.
    10311055    ///
    1032     /// Construct a new ConArcIt which continues the iterating from
    1033     /// the \c e arc.
     1056    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    10341057    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    10351058
     
    10921115  }
    10931116
    1094   /// \brief Finds an edge between two nodes of a graph.
    1095   ///
    1096   /// Finds an edge from node \c u to node \c v in graph \c g.
    1097   /// If the node \c u and node \c v is equal then each loop edge
     1117  /// \brief Find an edge between two nodes of a graph.
     1118  ///
     1119  /// This function finds an edge from node \c u to node \c v in graph \c g.
     1120  /// If node \c u and node \c v is equal then each loop edge
    10981121  /// will be enumerated once.
    10991122  ///
    11001123  /// If \c prev is \ref INVALID (this is the default value), then
    1101   /// it finds the first arc from \c u to \c v. Otherwise it looks for
    1102   /// the next arc from \c u to \c v after \c prev.
    1103   /// \return The found arc or \ref INVALID if there is no such an arc.
    1104   ///
    1105   /// Thus you can iterate through each arc from \c u to \c v as it follows.
     1124  /// it finds the first edge from \c u to \c v. Otherwise it looks for
     1125  /// the next edge from \c u to \c v after \c prev.
     1126  /// \return The found edge or \ref INVALID if there is no such an edge.
     1127  ///
     1128  /// Thus you can iterate through each edge between \c u and \c v
     1129  /// as it follows.
    11061130  ///\code
    1107   /// for(Edge e = findEdge(g,u,v); e != INVALID;
    1108   ///     e = findEdge(g,u,v,e)) {
     1131  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
    11091132  ///   ...
    11101133  /// }
    11111134  ///\endcode
    11121135  ///
     1136  /// \note \ref ConEdgeIt provides iterator interface for the same
     1137  /// functionality.
     1138  ///
    11131139  ///\sa ConEdgeIt
    1114 
    11151140  template <typename Graph>
    11161141  inline typename Graph::Edge
     
    11201145  }
    11211146
    1122   /// \brief Iterator for iterating on edges connected the same nodes.
    1123   ///
    1124   /// Iterator for iterating on edges connected the same nodes. It is
    1125   /// higher level interface for the findEdge() function. You can
     1147  /// \brief Iterator for iterating on parallel edges connecting the same nodes.
     1148  ///
     1149  /// Iterator for iterating on parallel edges connecting the same nodes.
     1150  /// It is a higher level interface for the findEdge() function. You can
    11261151  /// use it the following way:
    11271152  ///\code
    1128   /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     1153  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
    11291154  ///   ...
    11301155  /// }
     
    11441169    /// \brief Constructor.
    11451170    ///
    1146     /// Construct a new ConEdgeIt iterating on the edges which
    1147     /// connects the \c u and \c v node.
     1171    /// Construct a new ConEdgeIt iterating on the edges that
     1172    /// connects nodes \c u and \c v.
    11481173    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
    11491174      Parent::operator=(findEdge(_graph, u, v));
     
    11521177    /// \brief Constructor.
    11531178    ///
    1154     /// Construct a new ConEdgeIt which continues the iterating from
    1155     /// the \c e edge.
     1179    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    11561180    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    11571181
     
    11691193
    11701194
    1171   ///Dynamic arc look up between given endpoints.
     1195  ///Dynamic arc look-up between given endpoints.
    11721196
    11731197  ///Using this class, you can find an arc in a digraph from a given
    1174   ///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
     1198  ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
    11751199  ///where <em>d</em> is the out-degree of the source node.
    11761200  ///
     
    11781202  ///the \c operator() member.
    11791203  ///
    1180   ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
    1181   ///digraph is not changed so frequently.
    1182   ///
    1183   ///This class uses a self-adjusting binary search tree, Sleator's
    1184   ///and Tarjan's Splay tree for guarantee the logarithmic amortized
    1185   ///time bound for arc lookups. This class also guarantees the
     1204  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
     1205  ///\ref AllArcLookUp if your digraph is not changed so frequently.
     1206  ///
     1207  ///This class uses a self-adjusting binary search tree, the Splay tree
     1208  ///of Sleator and Tarjan to guarantee the logarithmic amortized
     1209  ///time bound for arc look-ups. This class also guarantees the
    11861210  ///optimal time bound in a constant factor for any distribution of
    11871211  ///queries.
     
    15081532
    15091533    ///Find an arc between two nodes.
    1510     ///\param s The source node
    1511     ///\param t The target node
     1534    ///\param s The source node.
     1535    ///\param t The target node.
    15121536    ///\param p The previous arc between \c s and \c t. It it is INVALID or
    15131537    ///not given, the operator finds the first appropriate arc.
     
    15201544    ///DynArcLookUp<ListDigraph> ae(g);
    15211545    ///...
    1522     ///int n=0;
    1523     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
     1546    ///int n = 0;
     1547    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
    15241548    ///\endcode
    15251549    ///
    1526     ///Finding the arcs take at most <em>O(</em>log<em>d)</em>
     1550    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
    15271551    ///amortized time, specifically, the time complexity of the lookups
    15281552    ///is equal to the optimal search tree implementation for the
     
    15301554    ///
    15311555    ///\note This is a dynamic data structure, therefore the data
    1532     ///structure is updated after each graph alteration. However,
    1533     ///theoretically this data structure is faster than \c ArcLookUp
    1534     ///or AllEdgeLookup, but it often provides worse performance than
     1556    ///structure is updated after each graph alteration. Thus although
     1557    ///this data structure is theoretically faster than \ref ArcLookUp
     1558    ///and \ref AllArcLookUp, it often provides worse performance than
    15351559    ///them.
    1536     ///
    15371560    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
    15381561      if (p == INVALID) {
     
    15861609  };
    15871610
    1588   ///Fast arc look up between given endpoints.
     1611  ///Fast arc look-up between given endpoints.
    15891612
    15901613  ///Using this class, you can find an arc in a digraph from a given
    1591   ///source to a given target in time <em>O(log d)</em>,
     1614  ///source to a given target in time <em>O</em>(log<em>d</em>),
    15921615  ///where <em>d</em> is the out-degree of the source node.
    15931616  ///
     
    15951618  ///Use \ref AllArcLookUp for this purpose.
    15961619  ///
    1597   ///\warning This class is static, so you should refresh() (or at least
    1598   ///refresh(Node)) this data structure
    1599   ///whenever the digraph changes. This is a time consuming (superlinearly
    1600   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
     1620  ///\warning This class is static, so you should call refresh() (or at
     1621  ///least refresh(Node)) to refresh this data structure whenever the
     1622  ///digraph changes. This is a time consuming (superlinearly proportional
     1623  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16011624  ///
    16021625  ///\tparam G The type of the underlying digraph.
     
    16471670    }
    16481671  public:
    1649     ///Refresh the data structure at a node.
     1672    ///Refresh the search data structure at a node.
    16501673
    16511674    ///Build up the search database of node \c n.
    16521675    ///
    1653     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
    1654     ///the number of the outgoing arcs of \c n.
     1676    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
     1677    ///is the number of the outgoing arcs of \c n.
    16551678    void refresh(Node n)
    16561679    {
     
    16681691    ///\ref refresh(Node) "refresh(n)" for each node \c n.
    16691692    ///
    1670     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
    1671     ///the number of the arcs of \c n and <em>D</em> is the maximum
     1693    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
     1694    ///the number of the arcs in the digraph and <em>D</em> is the maximum
    16721695    ///out-degree of the digraph.
    1673 
    16741696    void refresh()
    16751697    {
     
    16791701    ///Find an arc between two nodes.
    16801702
    1681     ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
    1682     /// <em>d</em> is the number of outgoing arcs of \c s.
    1683     ///\param s The source node
    1684     ///\param t The target node
     1703    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
     1704    ///where <em>d</em> is the number of outgoing arcs of \c s.
     1705    ///\param s The source node.
     1706    ///\param t The target node.
    16851707    ///\return An arc from \c s to \c t if there exists,
    16861708    ///\ref INVALID otherwise.
     
    16881710    ///\warning If you change the digraph, refresh() must be called before using
    16891711    ///this operator. If you change the outgoing arcs of
    1690     ///a single node \c n, then
    1691     ///\ref refresh(Node) "refresh(n)" is enough.
    1692     ///
     1712    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
    16931713    Arc operator()(Node s, Node t) const
    16941714    {
     
    17021722  };
    17031723
    1704   ///Fast look up of all arcs between given endpoints.
     1724  ///Fast look-up of all arcs between given endpoints.
    17051725
    17061726  ///This class is the same as \ref ArcLookUp, with the addition
    1707   ///that it makes it possible to find all arcs between given endpoints.
    1708   ///
    1709   ///\warning This class is static, so you should refresh() (or at least
    1710   ///refresh(Node)) this data structure
    1711   ///whenever the digraph changes. This is a time consuming (superlinearly
    1712   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
     1727  ///that it makes it possible to find all parallel arcs between given
     1728  ///endpoints.
     1729  ///
     1730  ///\warning This class is static, so you should call refresh() (or at
     1731  ///least refresh(Node)) to refresh this data structure whenever the
     1732  ///digraph changes. This is a time consuming (superlinearly proportional
     1733  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17131734  ///
    17141735  ///\tparam G The type of the underlying digraph.
     
    17341755      else {
    17351756        next=refreshNext(_right[head],next);
    1736 //         _next[head]=next;
    17371757        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
    17381758          ? next : INVALID;
     
    17591779    ///Build up the search database of node \c n.
    17601780    ///
    1761     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
     1781    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
    17621782    ///the number of the outgoing arcs of \c n.
    1763 
    17641783    void refresh(Node n)
    17651784    {
     
    17731792    ///\ref refresh(Node) "refresh(n)" for each node \c n.
    17741793    ///
    1775     ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
    1776     ///the number of the arcs of \c n and <em>D</em> is the maximum
     1794    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
     1795    ///the number of the arcs in the digraph and <em>D</em> is the maximum
    17771796    ///out-degree of the digraph.
    1778 
    17791797    void refresh()
    17801798    {
     
    17851803
    17861804    ///Find an arc between two nodes.
    1787     ///\param s The source node
    1788     ///\param t The target node
     1805    ///\param s The source node.
     1806    ///\param t The target node.
    17891807    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
    17901808    ///not given, the operator finds the first appropriate arc.
     
    17971815    ///AllArcLookUp<ListDigraph> ae(g);
    17981816    ///...
    1799     ///int n=0;
    1800     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
     1817    ///int n = 0;
     1818    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
    18011819    ///\endcode
    18021820    ///
    1803     ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
    1804     /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
     1821    ///Finding the first arc take <em>O</em>(log<em>d</em>) time,
     1822    ///where <em>d</em> is the number of outgoing arcs of \c s. Then the
    18051823    ///consecutive arcs are found in constant time.
    18061824    ///
    18071825    ///\warning If you change the digraph, refresh() must be called before using
    18081826    ///this operator. If you change the outgoing arcs of
    1809     ///a single node \c n, then
    1810     ///\ref refresh(Node) "refresh(n)" is enough.
     1827    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
    18111828    ///
    18121829#ifdef DOXYGEN
  • lemon/dfs.h

    r252 r319  
    2828#include <lemon/core.h>
    2929#include <lemon/error.h>
    30 #include <lemon/assert.h>
    3130#include <lemon/maps.h>
     31#include <lemon/path.h>
    3232
    3333namespace lemon {
     
    5050    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a \ref PredMap.
    53 
    54     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    56     ///\ref PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
     56    ///PredMap.
    5857    static PredMap *createPredMap(const Digraph &g)
    5958    {
     
    6564    ///The type of the map that indicates which nodes are processed.
    6665    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     ///By default it is a NullMap.
    6866    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    69     ///Instantiates a \ref ProcessedMap.
    70 
    71     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7270    ///\param g is the digraph, to which
    73     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7472#ifdef DOXYGEN
    7573    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    8684    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8785    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    88     ///Instantiates a \ref ReachedMap.
    89 
    90     ///This function instantiates a \ref ReachedMap.
     86    ///Instantiates a ReachedMap.
     87
     88    ///This function instantiates a ReachedMap.
    9189    ///\param g is the digraph, to which
    92     ///we would like to define the \ref ReachedMap.
     90    ///we would like to define the ReachedMap.
    9391    static ReachedMap *createReachedMap(const Digraph &g)
    9492    {
     
    10199    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    102100    typedef typename Digraph::template NodeMap<int> DistMap;
    103     ///Instantiates a \ref DistMap.
    104 
    105     ///This function instantiates a \ref DistMap.
     101    ///Instantiates a DistMap.
     102
     103    ///This function instantiates a DistMap.
    106104    ///\param g is the digraph, to which we would like to define the
    107     ///\ref DistMap.
     105    ///DistMap.
    108106    static DistMap *createDistMap(const Digraph &g)
    109107    {
     
    117115  ///This class provides an efficient implementation of the %DFS algorithm.
    118116  ///
    119   ///There is also a \ref dfs() "function type interface" for the DFS
     117  ///There is also a \ref dfs() "function-type interface" for the DFS
    120118  ///algorithm, which is convenient in the simplier cases and it can be
    121119  ///used easier.
     
    138136  class Dfs {
    139137  public:
    140     ///\ref Exception for uninitialized parameters.
    141 
    142     ///This error represents problems in the initialization of the
    143     ///parameters of the algorithm.
    144     class UninitializedParameter : public lemon::UninitializedParameter {
    145     public:
    146       virtual const char* what() const throw() {
    147         return "lemon::Dfs::UninitializedParameter";
    148       }
    149     };
    150138
    151139    ///The type of the digraph the algorithm runs on.
     
    196184    int _stack_head;
    197185
    198     ///Creates the maps if necessary.
    199     ///\todo Better memory allocation (instead of new).
     186    //Creates the maps if necessary.
    200187    void create_maps()
    201188    {
     
    231218
    232219    template <class T>
    233     struct DefPredMapTraits : public Traits {
     220    struct SetPredMapTraits : public Traits {
    234221      typedef T PredMap;
    235222      static PredMap *createPredMap(const Digraph &)
    236223      {
    237         throw UninitializedParameter();
     224        LEMON_ASSERT(false, "PredMap is not initialized");
     225        return 0; // ignore warnings
    238226      }
    239227    };
    240228    ///\brief \ref named-templ-param "Named parameter" for setting
    241     ///\ref PredMap type.
     229    ///PredMap type.
    242230    ///
    243231    ///\ref named-templ-param "Named parameter" for setting
    244     ///\ref PredMap type.
     232    ///PredMap type.
    245233    template <class T>
    246     struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
    247       typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
     234    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     235      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
    248236    };
    249237
    250238    template <class T>
    251     struct DefDistMapTraits : public Traits {
     239    struct SetDistMapTraits : public Traits {
    252240      typedef T DistMap;
    253241      static DistMap *createDistMap(const Digraph &)
    254242      {
    255         throw UninitializedParameter();
     243        LEMON_ASSERT(false, "DistMap is not initialized");
     244        return 0; // ignore warnings
    256245      }
    257246    };
    258247    ///\brief \ref named-templ-param "Named parameter" for setting
    259     ///\ref DistMap type.
     248    ///DistMap type.
    260249    ///
    261250    ///\ref named-templ-param "Named parameter" for setting
    262     ///\ref DistMap type.
     251    ///DistMap type.
    263252    template <class T>
    264     struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
    265       typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
     253    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     254      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
    266255    };
    267256
    268257    template <class T>
    269     struct DefReachedMapTraits : public Traits {
     258    struct SetReachedMapTraits : public Traits {
    270259      typedef T ReachedMap;
    271260      static ReachedMap *createReachedMap(const Digraph &)
    272261      {
    273         throw UninitializedParameter();
     262        LEMON_ASSERT(false, "ReachedMap is not initialized");
     263        return 0; // ignore warnings
    274264      }
    275265    };
    276266    ///\brief \ref named-templ-param "Named parameter" for setting
    277     ///\ref ReachedMap type.
     267    ///ReachedMap type.
    278268    ///
    279269    ///\ref named-templ-param "Named parameter" for setting
    280     ///\ref ReachedMap type.
     270    ///ReachedMap type.
    281271    template <class T>
    282     struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
    283       typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
     272    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     273      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
    284274    };
    285275
    286276    template <class T>
    287     struct DefProcessedMapTraits : public Traits {
     277    struct SetProcessedMapTraits : public Traits {
    288278      typedef T ProcessedMap;
    289279      static ProcessedMap *createProcessedMap(const Digraph &)
    290280      {
    291         throw UninitializedParameter();
     281        LEMON_ASSERT(false, "ProcessedMap is not initialized");
     282        return 0; // ignore warnings
    292283      }
    293284    };
    294285    ///\brief \ref named-templ-param "Named parameter" for setting
    295     ///\ref ProcessedMap type.
     286    ///ProcessedMap type.
    296287    ///
    297288    ///\ref named-templ-param "Named parameter" for setting
    298     ///\ref ProcessedMap type.
     289    ///ProcessedMap type.
    299290    template <class T>
    300     struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
    301       typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
    302     };
    303 
    304     struct DefDigraphProcessedMapTraits : public Traits {
     291    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     292      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
     293    };
     294
     295    struct SetStandardProcessedMapTraits : public Traits {
    305296      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    306297      static ProcessedMap *createProcessedMap(const Digraph &g)
     
    310301    };
    311302    ///\brief \ref named-templ-param "Named parameter" for setting
    312     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     303    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    313304    ///
    314305    ///\ref named-templ-param "Named parameter" for setting
    315     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     306    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    316307    ///If you don't set it explicitly, it will be automatically allocated.
    317     template <class T>
    318     struct DefProcessedMapToBeDefaultMap :
    319       public Dfs< Digraph, DefDigraphProcessedMapTraits> {
    320       typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
     308    struct SetStandardProcessedMap :
     309      public Dfs< Digraph, SetStandardProcessedMapTraits > {
     310      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
    321311    };
    322312
     
    559549    ///
    560550    ///This method runs the %DFS algorithm from the root node
    561     ///in order to compute the DFS path to \c dest.
     551    ///in order to compute the DFS path to \c t.
    562552    ///
    563553    ///The algorithm computes
    564     ///- the %DFS path to \c dest,
    565     ///- the distance of \c dest from the root in the %DFS tree.
     554    ///- the %DFS path to \c t,
     555    ///- the distance of \c t from the root in the %DFS tree.
    566556    ///
    567557    ///\pre init() must be called and a root node should be
    568558    ///added with addSource() before using this function.
    569     void start(Node dest)
    570     {
    571       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     559    void start(Node t)
     560    {
     561      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
    572562        processNextArc();
    573563    }
     
    599589    }
    600590
    601     ///Runs the algorithm from the given node.
     591    ///Runs the algorithm from the given source node.
    602592
    603593    ///This method runs the %DFS algorithm from node \c s
     
    623613
    624614    ///This method runs the %DFS algorithm from node \c s
    625     ///in order to compute the DFS path to \c t.
    626     ///
    627     ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    628     ///if \c t is reachable form \c s, \c 0 otherwise.
     615    ///in order to compute the DFS path to node \c t
     616    ///(it stops searching when \c t is processed)
     617    ///
     618    ///\return \c true if \c t is reachable form \c s.
    629619    ///
    630620    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    635625    ///  d.start(t);
    636626    ///\endcode
    637     int run(Node s,Node t) {
     627    bool run(Node s,Node t) {
    638628      init();
    639629      addSource(s);
    640630      start(t);
    641       return reached(t)?_stack_head+1:0;
     631      return reached(t);
    642632    }
    643633
     
    777767    ///arcs of the %DFS paths.
    778768    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    779     ///
    780     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
    781     ///Instantiates a \ref PredMap.
    782 
    783     ///This function instantiates a \ref PredMap.
     769    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     770    ///Instantiates a PredMap.
     771
     772    ///This function instantiates a PredMap.
    784773    ///\param g is the digraph, to which we would like to define the
    785     ///\ref PredMap.
    786     ///\todo The digraph alone may be insufficient to initialize
    787 #ifdef DOXYGEN
     774    ///PredMap.
    788775    static PredMap *createPredMap(const Digraph &g)
    789 #else
    790     static PredMap *createPredMap(const Digraph &)
    791 #endif
    792     {
    793       return new PredMap();
     776    {
     777      return new PredMap(g);
    794778    }
    795779
     
    798782    ///The type of the map that indicates which nodes are processed.
    799783    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     784    ///By default it is a NullMap.
    800785    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    801     ///Instantiates a \ref ProcessedMap.
    802 
    803     ///This function instantiates a \ref ProcessedMap.
     786    ///Instantiates a ProcessedMap.
     787
     788    ///This function instantiates a ProcessedMap.
    804789    ///\param g is the digraph, to which
    805     ///we would like to define the \ref ProcessedMap.
     790    ///we would like to define the ProcessedMap.
    806791#ifdef DOXYGEN
    807792    static ProcessedMap *createProcessedMap(const Digraph &g)
     
    818803    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    819804    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    820     ///Instantiates a \ref ReachedMap.
    821 
    822     ///This function instantiates a \ref ReachedMap.
     805    ///Instantiates a ReachedMap.
     806
     807    ///This function instantiates a ReachedMap.
    823808    ///\param g is the digraph, to which
    824     ///we would like to define the \ref ReachedMap.
     809    ///we would like to define the ReachedMap.
    825810    static ReachedMap *createReachedMap(const Digraph &g)
    826811    {
     
    832817    ///The type of the map that stores the distances of the nodes.
    833818    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.