COIN-OR::LEMON - Graph Library

Ignore:
Files:
13 deleted
64 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r791 r727  
    3535CHECK_TYPE_SIZE("long long" LONG_LONG)
    3636SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    37 
    38 INCLUDE(FindPythonInterp)
    3937
    4038ENABLE_TESTING()
  • Makefile.am

    r799 r676  
    1818        cmake/FindGLPK.cmake \
    1919        cmake/FindCOIN.cmake \
    20         cmake/LEMONConfig.cmake.in \
    2120        cmake/version.cmake.in \
    2221        cmake/version.cmake \
  • configure.ac

    r791 r727  
    4242
    4343AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    44 AC_CHECK_PROG([python_found],[python],[yes],[no])
    4544AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4645
  • doc/CMakeLists.txt

    r791 r726  
    1010)
    1111
    12 IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
    1313  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
    1414  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
     
    2929    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3030    COMMAND ${CMAKE_COMMAND} -E remove_directory html
    31     COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
    3231    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3332    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
  • doc/Doxyfile.in

    r803 r379  
    1 # Doxyfile 1.5.9
     1# Doxyfile 1.5.7.1
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
     24DETAILS_AT_TOP         = YES
    2425INHERIT_DOCS           = NO
    2526SEPARATE_MEMBER_PAGES  = NO
     
    9192                         "@abs_top_srcdir@/demo" \
    9293                         "@abs_top_srcdir@/tools" \
    93                          "@abs_top_srcdir@/test/test_tools.h" \
    94                          "@abs_top_builddir@/doc/references.dox"
     94                         "@abs_top_srcdir@/test/test_tools.h"
    9595INPUT_ENCODING         = UTF-8
    9696FILE_PATTERNS          = *.h \
     
    224224SKIP_FUNCTION_MACROS   = YES
    225225#---------------------------------------------------------------------------
    226 # Options related to the search engine   
     226# Configuration::additions related to external references   
    227227#---------------------------------------------------------------------------
    228228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/Makefile.am

    r791 r720  
    6767        fi
    6868
    69 references.dox: doc/references.bib
    70         if test ${python_found} = yes; then \
    71           cd doc; \
    72           python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
    73           cd ..; \
    74         else \
    75           echo; \
    76           echo "Python not found."; \
    77           echo; \
    78           exit 1; \
    79         fi
    80 
    81 html-local: $(DOC_PNG_IMAGES) references.dox
     69html-local: $(DOC_PNG_IMAGES)
    8270        if test ${doxygen_found} = yes; then \
    8371          cd doc; \
  • doc/groups.dox

    r818 r710  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    239247any kind of path structure.
    240248
    241 \sa \ref concepts::Path "Path concept"
    242 */
    243 
    244 /**
    245 @defgroup heaps Heap Structures
    246 @ingroup datas
    247 \brief %Heap structures implemented in LEMON.
    248 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
    263 */
    264 
    265 /**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
     249\sa lemon::concepts::Path
    271250*/
    272251
     
    281260
    282261/**
    283 @defgroup geomdat Geometric Data Structures
    284 @ingroup auxdat
    285 \brief Geometric data structures implemented in LEMON.
    286 
    287 This group contains geometric data structures implemented in LEMON.
    288 
    289  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    290    vector with the usual operations.
    291  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    292    rectangular bounding box of a set of \ref lemon::dim2::Point
    293    "dim2::Point"'s.
    294 */
    295 
    296 /**
    297 @defgroup matrices Matrices
    298 @ingroup auxdat
    299 \brief Two dimensional data storages implemented in LEMON.
    300 
    301 This group contains two dimensional data storages implemented in LEMON.
    302 */
    303 
    304 /**
    305262@defgroup algs Algorithms
    306263\brief This group contains the several algorithms
     
    317274
    318275This group contains the common graph search algorithms, namely
    319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    320 \ref clrs01algorithms.
     276\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    321277*/
    322278
     
    326282\brief Algorithms for finding shortest paths.
    327283
    328 This group contains the algorithms for finding shortest paths in digraphs
    329 \ref clrs01algorithms.
     284This group contains the algorithms for finding shortest paths in digraphs.
    330285
    331286 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    344299
    345300/**
    346 @defgroup spantree Minimum Spanning Tree Algorithms
    347 @ingroup algs
    348 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    349 
    350 This group contains the algorithms for finding minimum cost spanning
    351 trees and arborescences \ref clrs01algorithms.
    352 */
    353 
    354 /**
    355301@defgroup max_flow Maximum Flow Algorithms
    356302@ingroup algs
     
    358304
    359305This group contains the algorithms for finding maximum flows and
    360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     306feasible circulations.
    361307
    362308The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    373319
    374320LEMON contains several algorithms for solving maximum flow problems:
    375 - \ref EdmondsKarp Edmonds-Karp algorithm
    376   \ref edmondskarp72theoretical.
    377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    378   \ref goldberg88newapproach.
    379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    380   \ref dinic70algorithm, \ref sleator83dynamic.
    381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    382   \ref goldberg88newapproach, \ref sleator83dynamic.
    383 
    384 In most cases the \ref Preflow algorithm provides the
     321- \ref EdmondsKarp Edmonds-Karp algorithm.
     322- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     323- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     324- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     325
     326In most cases the \ref Preflow "Preflow" algorithm provides the
    385327fastest method for computing a maximum flow. All implementations
    386328also provide functions to query the minimum cut, which is the dual
     
    400342
    401343This group contains the algorithms for finding minimum cost flows and
    402 circulations \ref amo93networkflows. For more information about this
    403 problem and its dual solution, see \ref min_cost_flow
    404 "Minimum Cost Flow Problem".
     344circulations. For more information about this problem and its dual
     345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    405346
    406347LEMON contains several algorithms for this problem.
    407348 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     349   pivot strategies.
    409350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
    411    \ref bunnagel98efficient.
     351   cost scaling.
    412352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    413    capacity scaling \ref edmondskarp72theoretical.
    414  - \ref CancelAndTighten The Cancel and Tighten algorithm
    415    \ref goldberg89cyclecanceling.
    416  - \ref CycleCanceling Cycle-Canceling algorithms
    417    \ref klein67primal, \ref goldberg89cyclecanceling.
     353   capacity scaling.
     354 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     355 - \ref CycleCanceling Cycle-Canceling algorithms.
    418356
    419357In general NetworkSimplex is the most efficient implementation,
     
    438376
    439377\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    440     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     378    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    441379
    442380LEMON contains several algorithms related to minimum cut problems:
     
    454392
    455393/**
    456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
    457 @ingroup algs
    458 \brief Algorithms for finding minimum mean cycles.
    459 
    460 This group contains the algorithms for finding minimum mean cycles
    461 \ref clrs01algorithms, \ref amo93networkflows.
    462 
    463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    464 of minimum mean length (cost) in a digraph.
    465 The mean length of a cycle is the average length of its arcs, i.e. the
    466 ratio between the total length of the cycle and the number of arcs on it.
    467 
    468 This problem has an important connection to \e conservative \e length
    469 \e functions, too. A length function on the arcs of a digraph is called
    470 conservative if and only if there is no directed cycle of negative total
    471 length. For an arbitrary length function, the negative of the minimum
    472 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    473 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    474 function.
    475 
    476 LEMON contains three algorithms for solving the minimum mean cycle problem:
    477 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
    478   \ref dasdan98minmeancycle.
    479 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
    480   version of Karp's algorithm \ref dasdan98minmeancycle.
    481 - \ref Howard "Howard"'s policy iteration algorithm
    482   \ref dasdan98minmeancycle.
    483 
    484 In practice, the Howard algorithm proved to be by far the most efficient
    485 one, though the best known theoretical bound on its running time is
    486 exponential.
    487 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    488 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    489 applied early termination scheme.
     394@defgroup graph_properties Connectivity and Other Graph Properties
     395@ingroup algs
     396\brief Algorithms for discovering the graph properties
     397
     398This group contains the algorithms for discovering the graph properties
     399like connectivity, bipartiteness, euler property, simplicity etc.
     400
     401\image html edge_biconnected_components.png
     402\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     403*/
     404
     405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
    490415*/
    491416
     
    531456
    532457/**
    533 @defgroup graph_properties Connectivity and Other Graph Properties
    534 @ingroup algs
    535 \brief Algorithms for discovering the graph properties
    536 
    537 This group contains the algorithms for discovering the graph properties
    538 like connectivity, bipartiteness, euler property, simplicity etc.
    539 
    540 \image html connected_components.png
    541 \image latex connected_components.eps "Connected components" width=\textwidth
    542 */
    543 
    544 /**
    545 @defgroup planar Planarity Embedding and Drawing
    546 @ingroup algs
    547 \brief Algorithms for planarity checking, embedding and drawing
    548 
    549 This group contains the algorithms for planarity checking,
    550 embedding and drawing.
    551 
    552 \image html planar.png
    553 \image latex planar.eps "Plane graph" width=\textwidth
     458@defgroup spantree Minimum Spanning Tree Algorithms
     459@ingroup algs
     460\brief Algorithms for finding minimum cost spanning trees and arborescences.
     461
     462This group contains the algorithms for finding minimum cost spanning
     463trees and arborescences.
     464*/
     465
     466/**
     467@defgroup auxalg Auxiliary Algorithms
     468@ingroup algs
     469\brief Auxiliary algorithms implemented in LEMON.
     470
     471This group contains some algorithms implemented in LEMON
     472in order to make it easier to implement complex algorithms.
    554473*/
    555474
     
    561480This group contains the approximation and heuristic algorithms
    562481implemented in LEMON.
    563 */
    564 
    565 /**
    566 @defgroup auxalg Auxiliary Algorithms
    567 @ingroup algs
    568 \brief Auxiliary algorithms implemented in LEMON.
    569 
    570 This group contains some algorithms implemented in LEMON
    571 in order to make it easier to implement complex algorithms.
    572482*/
    573483
     
    582492
    583493/**
    584 @defgroup lp_group LP and MIP Solvers
     494@defgroup lp_group Lp and Mip Solvers
    585495@ingroup gen_opt_group
    586 \brief LP and MIP solver interfaces for LEMON.
    587 
    588 This group contains LP and MIP solver interfaces for LEMON.
    589 Various LP solvers could be used in the same manner with this
    590 high-level interface.
    591 
    592 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    593 \ref cplex, \ref soplex.
     496\brief Lp and Mip solver interfaces for LEMON.
     497
     498This group contains Lp and Mip solver interfaces for LEMON. The
     499various LP solvers could be used in the same manner with this
     500interface.
    594501*/
    595502
     
    681588
    682589/**
    683 @defgroup dimacs_group DIMACS Format
     590@defgroup dimacs_group DIMACS format
    684591@ingroup io_group
    685592\brief Read and write files in DIMACS format
     
    730637\brief Skeleton and concept checking classes for graph structures
    731638
    732 This group contains the skeletons and concept checking classes of
    733 graph structures.
     639This group contains the skeletons and concept checking classes of LEMON's
     640graph structures and helper classes used to implement these.
    734641*/
    735642
     
    743650
    744651/**
     652\anchor demoprograms
     653
     654@defgroup demos Demo Programs
     655
     656Some demo programs are listed here. Their full source codes can be found in
     657the \c demo subdirectory of the source tree.
     658
     659In order to compile them, use the <tt>make demo</tt> or the
     660<tt>make check</tt> commands.
     661*/
     662
     663/**
    745664@defgroup tools Standalone Utility Applications
    746665
     
    751670*/
    752671
    753 /**
    754 \anchor demoprograms
    755 
    756 @defgroup demos Demo Programs
    757 
    758 Some demo programs are listed here. Their full source codes can be found in
    759 the \c demo subdirectory of the source tree.
    760 
    761 In order to compile them, use the <tt>make demo</tt> or the
    762 <tt>make check</tt> commands.
    763 */
    764 
    765672}
  • doc/mainpage.dox

    r802 r705  
    2222\section intro Introduction
    2323
    24 <b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
    25 and <b>O</b>ptimization in <b>N</b>etworks</i>.
    26 It is a C++ template library providing efficient implementation of common
    27 data structures and algorithms with focus on combinatorial optimization
    28 problems in graphs and networks.
     24\subsection whatis What is LEMON
     25
     26LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     27and <b>O</b>ptimization in <b>N</b>etworks.
     28It is a C++ template
     29library aimed at combinatorial optimization tasks which
     30often involve in working
     31with graphs.
    2932
    3033<b>
     
    3639</b>
    3740
    38 The project is maintained by the
    39 <a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
    40 Combinatorial Optimization</a> \ref egres
    41 at the Operations Research Department of the
    42 <a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
    43 Budapest</a>, Hungary.
    44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
    45 initiative \ref coinor.
    46 
    47 \section howtoread How to Read the Documentation
     41\subsection howtoread How to read the documentation
    4842
    4943If you would like to get to know the library, see
  • doc/min_cost_flow.dox

    r802 r710  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs \ref amo93networkflows.
     29and arc costs.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • lemon/Makefile.am

    r827 r820  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
    60         lemon/bellman_ford.h \
    6160        lemon/bfs.h \
    6261        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
    6462        lemon/bucket_heap.h \
    6563        lemon/cbc.h \
     
    8179        lemon/euler.h \
    8280        lemon/fib_heap.h \
    83         lemon/fourary_heap.h \
    8481        lemon/full_graph.h \
    8582        lemon/glpk.h \
     
    8784        lemon/graph_to_eps.h \
    8885        lemon/grid_graph.h \
    89         lemon/hartmann_orlin.h \
    90         lemon/howard.h \
    9186        lemon/hypercube_graph.h \
    92         lemon/karp.h \
    93         lemon/kary_heap.h \
    9487        lemon/kruskal.h \
    9588        lemon/hao_orlin.h \
     
    10699        lemon/nauty_reader.h \
    107100        lemon/network_simplex.h \
    108         lemon/pairing_heap.h \
    109101        lemon/path.h \
    110102        lemon/preflow.h \
  • lemon/bfs.h

    r764 r525  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a \c ProcessedMap.
     
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8685    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8786    ///Instantiates a \c ReachedMap.
     
    9897
    9998    ///The type of the map that stores the distances of the nodes.
    100     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    101100    typedef typename Digraph::template NodeMap<int> DistMap;
    102101    ///Instantiates a \c DistMap.
     
    227226    ///\ref named-templ-param "Named parameter" for setting
    228227    ///\c PredMap type.
    229     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    230229    template <class T>
    231230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    247246    ///\ref named-templ-param "Named parameter" for setting
    248247    ///\c DistMap type.
    249     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    250249    template <class T>
    251250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    267266    ///\ref named-templ-param "Named parameter" for setting
    268267    ///\c ReachedMap type.
    269     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    270269    template <class T>
    271270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    287286    ///\ref named-templ-param "Named parameter" for setting
    288287    ///\c ProcessedMap type.
    289     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290289    template <class T>
    291290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    415414    ///The simplest way to execute the BFS algorithm is to use one of the
    416415    ///member functions called \ref run(Node) "run()".\n
    417     ///If you need better control on the execution, you have to call
    418     ///\ref init() first, then you can add several source nodes with
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
    419418    ///\ref addSource(). Finally the actual path computation can be
    420419    ///performed with one of the \ref start() functions.
     
    739738    ///@{
    740739
    741     ///The shortest path to the given node.
    742 
    743     ///Returns the shortest path to the given node from the root(s).
     740    ///The shortest path to a node.
     741
     742    ///Returns the shortest path to a node.
    744743    ///
    745744    ///\warning \c t should be reached from the root(s).
     
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
    751     ///The distance of the given node from the root(s).
    752 
    753     ///Returns the distance of the given node from the root(s).
     750    ///The distance of a node from the root(s).
     751
     752    ///Returns the distance of a node from the root(s).
    754753    ///
    755754    ///\warning If node \c v is not reached from the root(s), then
     
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
    762     ///\brief Returns the 'previous arc' of the shortest path tree for
    763     ///the given node.
    764     ///
     761    ///Returns the 'previous arc' of the shortest path tree for a node.
     762
    765763    ///This function returns the 'previous arc' of the shortest path
    766764    ///tree for the node \c v, i.e. it returns the last arc of a
     
    769767    ///
    770768    ///The shortest path tree used here is equal to the shortest path
    771     ///tree used in \ref predNode() and \ref predMap().
     769    ///tree used in \ref predNode().
    772770    ///
    773771    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    775773    Arc predArc(Node v) const { return (*_pred)[v];}
    776774
    777     ///\brief Returns the 'previous node' of the shortest path tree for
    778     ///the given node.
    779     ///
     775    ///Returns the 'previous node' of the shortest path tree for a node.
     776
    780777    ///This function returns the 'previous node' of the shortest path
    781778    ///tree for the node \c v, i.e. it returns the last but one node
    782     ///of a shortest path from a root to \c v. It is \c INVALID
     779    ///from a shortest path from a root to \c v. It is \c INVALID
    783780    ///if \c v is not reached from the root(s) or if \c v is a root.
    784781    ///
    785782    ///The shortest path tree used here is equal to the shortest path
    786     ///tree used in \ref predArc() and \ref predMap().
     783    ///tree used in \ref predArc().
    787784    ///
    788785    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    805802    ///
    806803    ///Returns a const reference to the node map that stores the predecessor
    807     ///arcs, which form the shortest path tree (forest).
     804    ///arcs, which form the shortest path tree.
    808805    ///
    809806    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    811808    const PredMap &predMap() const { return *_pred;}
    812809
    813     ///Checks if the given node is reached from the root(s).
     810    ///Checks if a node is reached from the root(s).
    814811
    815812    ///Returns \c true if \c v is reached from the root(s).
     
    837834    ///The type of the map that stores the predecessor
    838835    ///arcs of the shortest paths.
    839     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     836    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    840837    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    841838    ///Instantiates a PredMap.
     
    852849
    853850    ///The type of the map that indicates which nodes are processed.
    854     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     851    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    855852    ///By default it is a NullMap.
    856853    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    872869
    873870    ///The type of the map that indicates which nodes are reached.
    874     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     871    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    875872    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    876873    ///Instantiates a ReachedMap.
     
    887884
    888885    ///The type of the map that stores the distances of the nodes.
    889     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     886    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    890887    typedef typename Digraph::template NodeMap<int> DistMap;
    891888    ///Instantiates a DistMap.
     
    902899
    903900    ///The type of the shortest paths.
    904     ///It must conform to the \ref concepts::Path "Path" concept.
     901    ///It must meet the \ref concepts::Path "Path" concept.
    905902    typedef lemon::Path<Digraph> Path;
    906903  };
     
    908905  /// Default traits class used by BfsWizard
    909906
    910   /// Default traits class used by BfsWizard.
    911   /// \tparam GR The type of the digraph.
     907  /// To make it easier to use Bfs algorithm
     908  /// we have created a wizard class.
     909  /// This \ref BfsWizard class needs default traits,
     910  /// as well as the \ref Bfs class.
     911  /// The \ref BfsWizardBase is a class to be the default traits of the
     912  /// \ref BfsWizard class.
    912913  template<class GR>
    913914  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    937938    /// Constructor.
    938939
    939     /// This constructor does not require parameters, it initiates
     940    /// This constructor does not require parameters, therefore it initiates
    940941    /// all of the attributes to \c 0.
    941942    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    967968    typedef TR Base;
    968969
     970    ///The type of the digraph the algorithm runs on.
    969971    typedef typename TR::Digraph Digraph;
    970972
     
    974976    typedef typename Digraph::OutArcIt OutArcIt;
    975977
     978    ///\brief The type of the map that stores the predecessor
     979    ///arcs of the shortest paths.
    976980    typedef typename TR::PredMap PredMap;
     981    ///\brief The type of the map that stores the distances of the nodes.
    977982    typedef typename TR::DistMap DistMap;
     983    ///\brief The type of the map that indicates which nodes are reached.
    978984    typedef typename TR::ReachedMap ReachedMap;
     985    ///\brief The type of the map that indicates which nodes are processed.
    979986    typedef typename TR::ProcessedMap ProcessedMap;
     987    ///The type of the shortest paths
    980988    typedef typename TR::Path Path;
    981989
     
    10601068      SetPredMapBase(const TR &b) : TR(b) {}
    10611069    };
    1062 
    1063     ///\brief \ref named-templ-param "Named parameter" for setting
    1064     ///the predecessor map.
    1065     ///
    1066     ///\ref named-templ-param "Named parameter" function for setting
    1067     ///the map that stores the predecessor arcs of the nodes.
     1070    ///\brief \ref named-func-param "Named parameter"
     1071    ///for setting PredMap object.
     1072    ///
     1073    ///\ref named-func-param "Named parameter"
     1074    ///for setting PredMap object.
    10681075    template<class T>
    10691076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10791086      SetReachedMapBase(const TR &b) : TR(b) {}
    10801087    };
    1081 
    1082     ///\brief \ref named-templ-param "Named parameter" for setting
    1083     ///the reached map.
    1084     ///
    1085     ///\ref named-templ-param "Named parameter" function for setting
    1086     ///the map that indicates which nodes are reached.
     1088    ///\brief \ref named-func-param "Named parameter"
     1089    ///for setting ReachedMap object.
     1090    ///
     1091    /// \ref named-func-param "Named parameter"
     1092    ///for setting ReachedMap object.
    10871093    template<class T>
    10881094    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10981104      SetDistMapBase(const TR &b) : TR(b) {}
    10991105    };
    1100 
    1101     ///\brief \ref named-templ-param "Named parameter" for setting
    1102     ///the distance map.
    1103     ///
    1104     ///\ref named-templ-param "Named parameter" function for setting
    1105     ///the map that stores the distances of the nodes calculated
    1106     ///by the algorithm.
     1106    ///\brief \ref named-func-param "Named parameter"
     1107    ///for setting DistMap object.
     1108    ///
     1109    /// \ref named-func-param "Named parameter"
     1110    ///for setting DistMap object.
    11071111    template<class T>
    11081112    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11181122      SetProcessedMapBase(const TR &b) : TR(b) {}
    11191123    };
    1120 
    1121     ///\brief \ref named-func-param "Named parameter" for setting
    1122     ///the processed map.
    1123     ///
    1124     ///\ref named-templ-param "Named parameter" function for setting
    1125     ///the map that indicates which nodes are processed.
     1124    ///\brief \ref named-func-param "Named parameter"
     1125    ///for setting ProcessedMap object.
     1126    ///
     1127    /// \ref named-func-param "Named parameter"
     1128    ///for setting ProcessedMap object.
    11261129    template<class T>
    11271130    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12621265    ///
    12631266    /// The type of the map that indicates which nodes are reached.
    1264     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1267    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12651268    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12661269
     
    14231426    /// The simplest way to execute the BFS algorithm is to use one of the
    14241427    /// member functions called \ref run(Node) "run()".\n
    1425     /// If you need better control on the execution, you have to call
    1426     /// \ref init() first, then you can add several source nodes with
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
    14271430    /// \ref addSource(). Finally the actual path computation can be
    14281431    /// performed with one of the \ref start() functions.
     
    17331736    ///@{
    17341737
    1735     /// \brief Checks if the given node is reached from the root(s).
     1738    /// \brief Checks if a node is reached from the root(s).
    17361739    ///
    17371740    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r758 r730  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
    33   ///
    34   /// \brief Binary heap data structure.
    35   ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
    38   ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
     32  ///\ingroup auxdat
     33  ///
     34  ///\brief A Binary Heap implementation.
     35  ///
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
     43  ///
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
    4752  template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
    4953  class BinHeap {
     54
    5055  public:
    51 
    52     /// Type of the item-int map.
     56    ///\e
    5357    typedef IM ItemIntMap;
    54     /// Type of the priorities.
     58    ///\e
    5559    typedef PR Prio;
    56     /// Type of the items stored in the heap.
     60    ///\e
    5761    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     62    ///\e
    5963    typedef std::pair<Item,Prio> Pair;
    60     /// Functor type for comparing the priorities.
     64    ///\e
    6165    typedef CMP Compare;
    6266
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     67    /// \brief Type to represent the items states.
     68    ///
     69    /// Each Item element have a state associated to it. It may be "in heap",
     70    /// "pre heap" or "post heap". The latter two are indifferent from the
    6771    /// heap's point of view, but may be useful to the user.
    6872    ///
     
    8185
    8286  public:
    83 
    84     /// \brief Constructor.
    85     ///
    86     /// Constructor.
    87     /// \param map A map that assigns \c int values to the items.
    88     /// It is used internally to handle the cross references.
    89     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     87    /// \brief The constructor.
     88    ///
     89    /// The constructor.
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    9093    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9194
    92     /// \brief Constructor.
    93     ///
    94     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     /// \param comp The function object used for comparing the priorities.
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
     99    /// internally to handle the cross references. The value of the map
     100    /// should be PRE_HEAP (-1) for each element.
     101    ///
     102    /// \param comp The comparator function object.
    99103    BinHeap(ItemIntMap &map, const Compare &comp)
    100104      : _iim(map), _comp(comp) {}
    101105
    102106
    103     /// \brief The number of items stored in the heap.
    104     ///
    105     /// This function returns the number of items stored in the heap.
     107    /// The number of items stored in the heap.
     108    ///
     109    /// \brief Returns the number of items stored in the heap.
    106110    int size() const { return _data.size(); }
    107111
    108     /// \brief Check if the heap is empty.
    109     ///
    110     /// This function returns \c true if the heap is empty.
     112    /// \brief Checks if the heap stores no items.
     113    ///
     114    /// Returns \c true if and only if the heap stores no items.
    111115    bool empty() const { return _data.empty(); }
    112116
    113     /// \brief Make the heap empty.
    114     ///
    115     /// This functon makes the heap empty.
    116     /// It does not change the cross reference map. If you want to reuse
    117     /// a heap that is not surely empty, you should first clear it and
    118     /// then you should set the cross reference map to \c PRE_HEAP
    119     /// for each item.
     117    /// \brief Make empty this heap.
     118    ///
     119    /// Make empty this heap. It does not change the cross reference map.
     120    /// If you want to reuse what is not surely empty you should first clear
     121    /// the heap and after that you should set the cross reference map for
     122    /// each item to \c PRE_HEAP.
    120123    void clear() {
    121124      _data.clear();
     
    125128    static int parent(int i) { return (i-1)/2; }
    126129
    127     static int secondChild(int i) { return 2*i+2; }
     130    static int second_child(int i) { return 2*i+2; }
    128131    bool less(const Pair &p1, const Pair &p2) const {
    129132      return _comp(p1.second, p2.second);
    130133    }
    131134
    132     int bubbleUp(int hole, Pair p) {
     135    int bubble_up(int hole, Pair p) {
    133136      int par = parent(hole);
    134137      while( hole>0 && less(p,_data[par]) ) {
     
    141144    }
    142145
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     146    int bubble_down(int hole, Pair p, int length) {
     147      int child = second_child(hole);
    145148      while(child < length) {
    146149        if( less(_data[child-1], _data[child]) ) {
     
    151154        move(_data[child], hole);
    152155        hole = child;
    153         child = secondChild(hole);
     156        child = second_child(hole);
    154157      }
    155158      child--;
     
    169172
    170173  public:
    171 
    172174    /// \brief Insert a pair of item and priority into the heap.
    173175    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     176    /// Adds \c p.first to the heap with priority \c p.second.
    176177    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubbleUp(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given priority.
    185     ///
    186     /// This function inserts the given item into the heap with the
    187     /// given priority.
     181      bubble_up(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given heap.
     185    ///
     186    /// Adds \c i to the heap with priority \c p.
    188187    /// \param i The item to insert.
    189188    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192190
    193     /// \brief Return the item having minimum priority.
    194     ///
    195     /// This function returns the item having minimum priority.
    196     /// \pre The heap must be non-empty.
     191    /// \brief Returns the item with minimum priority relative to \c Compare.
     192    ///
     193    /// This method returns the item with minimum priority relative to \c
     194    /// Compare.
     195    /// \pre The heap must be nonempty.
    197196    Item top() const {
    198197      return _data[0].first;
    199198    }
    200199
    201     /// \brief The minimum priority.
    202     ///
    203     /// This function returns the minimum priority.
    204     /// \pre The heap must be non-empty.
     200    /// \brief Returns the minimum priority relative to \c Compare.
     201    ///
     202    /// It returns the minimum priority relative to \c Compare.
     203    /// \pre The heap must be nonempty.
    205204    Prio prio() const {
    206205      return _data[0].second;
    207206    }
    208207
    209     /// \brief Remove the item having minimum priority.
    210     ///
    211     /// This function removes the item having minimum priority.
     208    /// \brief Deletes the item with minimum priority relative to \c Compare.
     209    ///
     210    /// This method deletes the item with minimum priority relative to \c
     211    /// Compare from the heap.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubbleDown(0, _data[n], n);
     217        bubble_down(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Remove the given item from the heap.
    223     ///
    224     /// This function removes the given item from the heap if it is
    225     /// already stored.
    226     /// \param i The item to delete.
    227     /// \pre \e i must be in the heap.
     222    /// \brief Deletes \c i from the heap.
     223    ///
     224    /// This method deletes item \c i from the heap.
     225    /// \param i The item to erase.
     226    /// \pre The item should be in the heap.
    228227    void erase(const Item &i) {
    229228      int h = _iim[i];
     
    231230      _iim.set(_data[h].first, POST_HEAP);
    232231      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    235234        }
    236235      }
     
    238237    }
    239238
    240     /// \brief The priority of the given item.
    241     ///
    242     /// This function returns the priority of the given item.
    243     /// \param i The item.
    244     /// \pre \e i must be in the heap.
     239
     240    /// \brief Returns the priority of \c i.
     241    ///
     242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
     244    /// \pre \c i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
     
    248248    }
    249249
    250     /// \brief Set the priority of an item or insert it, if it is
    251     /// not stored in the heap.
    252     ///
    253     /// This method sets the priority of the given item if it is
    254     /// already stored in the heap. Otherwise it inserts the given
    255     /// item into the heap with the given priority.
     250    /// \brief \c i gets to the heap with priority \c p independently
     251    /// if \c i was already there.
     252    ///
     253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     254    /// in the heap and sets the priority of \c i to \c p otherwise.
    256255    /// \param i The item.
    257256    /// \param p The priority.
     
    262261      }
    263262      else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     263        bubble_up(idx, Pair(i,p));
    265264      }
    266265      else {
    267         bubbleDown(idx, Pair(i,p), _data.size());
    268       }
    269     }
    270 
    271     /// \brief Decrease the priority of an item to the given value.
    272     ///
    273     /// This function decreases the priority of an item to the given value.
     266        bubble_down(idx, Pair(i,p), _data.size());
     267      }
     268    }
     269
     270    /// \brief Decreases the priority of \c i to \c p.
     271    ///
     272    /// This method decreases the priority of item \c i to \c p.
    274273    /// \param i The item.
    275274    /// \param p The priority.
    276     /// \pre \e i must be stored in the heap with priority at least \e p.
     275    /// \pre \c i must be stored in the heap with priority at least \c
     276    /// p relative to \c Compare.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubbleUp(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increase the priority of an item to the given value.
    283     ///
    284     /// This function increases the priority of an item to the given value.
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \e i must be stored in the heap with priority at most \e p.
     287    /// \pre \c i must be stored in the heap with priority at most \c
     288    /// p relative to \c Compare.
    288289    void increase(const Item &i, const Prio &p) {
    289290      int idx = _iim[i];
    290       bubbleDown(idx, Pair(i,p), _data.size());
    291     }
    292 
    293     /// \brief Return the state of an item.
    294     ///
    295     /// This method returns \c PRE_HEAP if the given item has never
    296     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    297     /// and \c POST_HEAP otherwise.
    298     /// In the latter case it is possible that the item will get back
    299     /// to the heap again.
     291      bubble_down(idx, Pair(i,p), _data.size());
     292    }
     293
     294    /// \brief Returns if \c item is in, has already been in, or has
     295    /// never been in the heap.
     296    ///
     297    /// This method returns PRE_HEAP if \c item has never been in the
     298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     299    /// otherwise. In the latter case it is possible that \c item will
     300    /// get back to the heap again.
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
     
    306307    }
    307308
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     309    /// \brief Sets the state of the \c item in the heap.
     310    ///
     311    /// Sets the state of the \c item in the heap. It can be used to
     312    /// manually clear the heap when it is important to achive the
     313    /// better time complexity.
    313314    /// \param i The item.
    314315    /// \param st The state. It should not be \c IN_HEAP.
     
    327328    }
    328329
    329     /// \brief Replace an item in the heap.
    330     ///
    331     /// This function replaces item \c i with item \c j.
    332     /// Item \c i must be in the heap, while \c j must be out of the heap.
    333     /// After calling this method, item \c i will be out of the
    334     /// heap and \c j will be in the heap with the same prioriority
    335     /// as item \c i had before.
     330    /// \brief Replaces an item in the heap.
     331    ///
     332    /// The \c i item is replaced with \c j item. The \c i item should
     333    /// be in the heap, while the \c j should be out of the heap. The
     334    /// \c i item will out of the heap and \c j will be in the heap
     335    /// with the same prioriority as prevoiusly the \c i item.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
  • lemon/bits/map_extender.h

    r765 r664  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
    52     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    53 
    5452    class MapIt;
    5553    class ConstMapIt;
     
    194192    typedef typename Parent::ConstReference ConstReference;
    195193
    196     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    197 
    198194    class MapIt;
    199195    class ConstMapIt;
  • lemon/bucket_heap.h

    r758 r730  
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Bucket heap implementation.
     24///\brief Bucket Heap implementation.
    2525
    2626#include <vector>
     
    5454  }
    5555
    56   /// \ingroup heaps
    57   ///
    58   /// \brief Bucket heap data structure.
    59   ///
    60   /// This class implements the \e bucket \e heap data structure.
    61   /// It practically conforms to the \ref concepts::Heap "heap concept",
    62   /// but it has some limitations.
    63   ///
    64   /// The bucket heap is a very simple structure. It can store only
    65   /// \c int priorities and it maintains a list of items for each priority
    66   /// in the range <tt>[0..C)</tt>. So it should only be used when the
    67   /// priorities are small. It is not intended to use as a Dijkstra heap.
    68   ///
    69   /// \tparam IM A read-writable item map with \c int values, used
    70   /// internally to handle the cross references.
    71   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    72   /// The default is \e min-heap. If this parameter is set to \c false,
    73   /// then the comparison is reversed, so the top(), prio() and pop()
    74   /// functions deal with the item having maximum priority instead of the
    75   /// minimum.
    76   ///
    77   /// \sa SimpleBucketHeap
     56  /// \ingroup auxdat
     57  ///
     58  /// \brief A Bucket Heap implementation.
     59  ///
     60  /// This class implements the \e bucket \e heap data structure. A \e heap
     61  /// is a data structure for storing items with specified values called \e
     62  /// priorities in such a way that finding the item with minimum priority is
     63  /// efficient. The bucket heap is very simple implementation, it can store
     64  /// only integer priorities and it stores for each priority in the
     65  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
     66  /// the priorities are small. It is not intended to use as dijkstra heap.
     67  ///
     68  /// \param IM A read and write Item int map, used internally
     69  /// to handle the cross references.
     70  /// \param MIN If the given parameter is false then instead of the
     71  /// minimum value the maximum can be retrivied with the top() and
     72  /// prio() member functions.
    7873  template <typename IM, bool MIN = true>
    7974  class BucketHeap {
    8075
    8176  public:
    82 
    83     /// Type of the item-int map.
     77    /// \e
     78    typedef typename IM::Key Item;
     79    /// \e
     80    typedef int Prio;
     81    /// \e
     82    typedef std::pair<Item, Prio> Pair;
     83    /// \e
    8484    typedef IM ItemIntMap;
    85     /// Type of the priorities.
    86     typedef int Prio;
    87     /// Type of the items stored in the heap.
    88     typedef typename ItemIntMap::Key Item;
    89     /// Type of the item-priority pairs.
    90     typedef std::pair<Item,Prio> Pair;
    9185
    9286  private:
     
    9690  public:
    9791
    98     /// \brief Type to represent the states of the items.
    99     ///
    100     /// Each item has a state associated to it. It can be "in heap",
    101     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     92    /// \brief Type to represent the items states.
     93    ///
     94    /// Each Item element have a state associated to it. It may be "in heap",
     95    /// "pre heap" or "post heap". The latter two are indifferent from the
    10296    /// heap's point of view, but may be useful to the user.
    10397    ///
     
    111105
    112106  public:
    113 
    114     /// \brief Constructor.
    115     ///
    116     /// Constructor.
    117     /// \param map A map that assigns \c int values to the items.
    118     /// It is used internally to handle the cross references.
    119     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     107    /// \brief The constructor.
     108    ///
     109    /// The constructor.
     110    /// \param map should be given to the constructor, since it is used
     111    /// internally to handle the cross references. The value of the map
     112    /// should be PRE_HEAP (-1) for each element.
    120113    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    121114
    122     /// \brief The number of items stored in the heap.
    123     ///
    124     /// This function returns the number of items stored in the heap.
     115    /// The number of items stored in the heap.
     116    ///
     117    /// \brief Returns the number of items stored in the heap.
    125118    int size() const { return _data.size(); }
    126119
    127     /// \brief Check if the heap is empty.
    128     ///
    129     /// This function returns \c true if the heap is empty.
     120    /// \brief Checks if the heap stores no items.
     121    ///
     122    /// Returns \c true if and only if the heap stores no items.
    130123    bool empty() const { return _data.empty(); }
    131124
    132     /// \brief Make the heap empty.
    133     ///
    134     /// This functon makes the heap empty.
    135     /// It does not change the cross reference map. If you want to reuse
    136     /// a heap that is not surely empty, you should first clear it and
    137     /// then you should set the cross reference map to \c PRE_HEAP
    138     /// for each item.
     125    /// \brief Make empty this heap.
     126    ///
     127    /// Make empty this heap. It does not change the cross reference
     128    /// map.  If you want to reuse a heap what is not surely empty you
     129    /// should first clear the heap and after that you should set the
     130    /// cross reference map for each item to \c PRE_HEAP.
    139131    void clear() {
    140132      _data.clear(); _first.clear(); _minimum = 0;
     
    143135  private:
    144136
    145     void relocateLast(int idx) {
     137    void relocate_last(int idx) {
    146138      if (idx + 1 < int(_data.size())) {
    147139        _data[idx] = _data.back();
     
    183175
    184176  public:
    185 
    186177    /// \brief Insert a pair of item and priority into the heap.
    187178    ///
    188     /// This function inserts \c p.first to the heap with priority
    189     /// \c p.second.
     179    /// Adds \c p.first to the heap with priority \c p.second.
    190180    /// \param p The pair to insert.
    191     /// \pre \c p.first must not be stored in the heap.
    192181    void push(const Pair& p) {
    193182      push(p.first, p.second);
     
    196185    /// \brief Insert an item into the heap with the given priority.
    197186    ///
    198     /// This function inserts the given item into the heap with the
    199     /// given priority.
     187    /// Adds \c i to the heap with priority \c p.
    200188    /// \param i The item to insert.
    201189    /// \param p The priority of the item.
    202     /// \pre \e i must not be stored in the heap.
    203190    void push(const Item &i, const Prio &p) {
    204191      int idx = _data.size();
     
    211198    }
    212199
    213     /// \brief Return the item having minimum priority.
    214     ///
    215     /// This function returns the item having minimum priority.
    216     /// \pre The heap must be non-empty.
     200    /// \brief Returns the item with minimum priority.
     201    ///
     202    /// This method returns the item with minimum priority.
     203    /// \pre The heap must be nonempty.
    217204    Item top() const {
    218205      while (_first[_minimum] == -1) {
     
    222209    }
    223210
    224     /// \brief The minimum priority.
    225     ///
    226     /// This function returns the minimum priority.
    227     /// \pre The heap must be non-empty.
     211    /// \brief Returns the minimum priority.
     212    ///
     213    /// It returns the minimum priority.
     214    /// \pre The heap must be nonempty.
    228215    Prio prio() const {
    229216      while (_first[_minimum] == -1) {
     
    233220    }
    234221
    235     /// \brief Remove the item having minimum priority.
    236     ///
    237     /// This function removes the item having minimum priority.
     222    /// \brief Deletes the item with minimum priority.
     223    ///
     224    /// This method deletes the item with minimum priority from the heap.
    238225    /// \pre The heap must be non-empty.
    239226    void pop() {
     
    244231      _iim[_data[idx].item] = -2;
    245232      unlace(idx);
    246       relocateLast(idx);
    247     }
    248 
    249     /// \brief Remove the given item from the heap.
    250     ///
    251     /// This function removes the given item from the heap if it is
    252     /// already stored.
    253     /// \param i The item to delete.
    254     /// \pre \e i must be in the heap.
     233      relocate_last(idx);
     234    }
     235
     236    /// \brief Deletes \c i from the heap.
     237    ///
     238    /// This method deletes item \c i from the heap, if \c i was
     239    /// already stored in the heap.
     240    /// \param i The item to erase.
    255241    void erase(const Item &i) {
    256242      int idx = _iim[i];
    257243      _iim[_data[idx].item] = -2;
    258244      unlace(idx);
    259       relocateLast(idx);
    260     }
    261 
    262     /// \brief The priority of the given item.
    263     ///
    264     /// This function returns the priority of the given item.
    265     /// \param i The item.
    266     /// \pre \e i must be in the heap.
     245      relocate_last(idx);
     246    }
     247
     248
     249    /// \brief Returns the priority of \c i.
     250    ///
     251    /// This function returns the priority of item \c i.
     252    /// \pre \c i must be in the heap.
     253    /// \param i The item.
    267254    Prio operator[](const Item &i) const {
    268255      int idx = _iim[i];
     
    270257    }
    271258
    272     /// \brief Set the priority of an item or insert it, if it is
    273     /// not stored in the heap.
    274     ///
    275     /// This method sets the priority of the given item if it is
    276     /// already stored in the heap. Otherwise it inserts the given
    277     /// item into the heap with the given priority.
     259    /// \brief \c i gets to the heap with priority \c p independently
     260    /// if \c i was already there.
     261    ///
     262    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     263    /// in the heap and sets the priority of \c i to \c p otherwise.
    278264    /// \param i The item.
    279265    /// \param p The priority.
     
    289275    }
    290276
    291     /// \brief Decrease the priority of an item to the given value.
    292     ///
    293     /// This function decreases the priority of an item to the given value.
     277    /// \brief Decreases the priority of \c i to \c p.
     278    ///
     279    /// This method decreases the priority of item \c i to \c p.
     280    /// \pre \c i must be stored in the heap with priority at least \c
     281    /// p relative to \c Compare.
    294282    /// \param i The item.
    295283    /// \param p The priority.
    296     /// \pre \e i must be stored in the heap with priority at least \e p.
    297284    void decrease(const Item &i, const Prio &p) {
    298285      int idx = _iim[i];
     
    305292    }
    306293
    307     /// \brief Increase the priority of an item to the given value.
    308     ///
    309     /// This function increases the priority of an item to the given value.
     294    /// \brief Increases the priority of \c i to \c p.
     295    ///
     296    /// This method sets the priority of item \c i to \c p.
     297    /// \pre \c i must be stored in the heap with priority at most \c
     298    /// p relative to \c Compare.
    310299    /// \param i The item.
    311300    /// \param p The priority.
    312     /// \pre \e i must be stored in the heap with priority at most \e p.
    313301    void increase(const Item &i, const Prio &p) {
    314302      int idx = _iim[i];
     
    318306    }
    319307
    320     /// \brief Return the state of an item.
    321     ///
    322     /// This method returns \c PRE_HEAP if the given item has never
    323     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    324     /// and \c POST_HEAP otherwise.
    325     /// In the latter case it is possible that the item will get back
    326     /// to the heap again.
     308    /// \brief Returns if \c item is in, has already been in, or has
     309    /// never been in the heap.
     310    ///
     311    /// This method returns PRE_HEAP if \c item has never been in the
     312    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     313    /// otherwise. In the latter case it is possible that \c item will
     314    /// get back to the heap again.
    327315    /// \param i The item.
    328316    State state(const Item &i) const {
     
    332320    }
    333321
    334     /// \brief Set the state of an item in the heap.
    335     ///
    336     /// This function sets the state of the given item in the heap.
    337     /// It can be used to manually clear the heap when it is important
    338     /// to achive better time complexity.
     322    /// \brief Sets the state of the \c item in the heap.
     323    ///
     324    /// Sets the state of the \c item in the heap. It can be used to
     325    /// manually clear the heap when it is important to achive the
     326    /// better time complexity.
    339327    /// \param i The item.
    340328    /// \param st The state. It should not be \c IN_HEAP.
     
    372360  }; // class BucketHeap
    373361
    374   /// \ingroup heaps
    375   ///
    376   /// \brief Simplified bucket heap data structure.
     362  /// \ingroup auxdat
     363  ///
     364  /// \brief A Simplified Bucket Heap implementation.
    377365  ///
    378366  /// This class implements a simplified \e bucket \e heap data
    379   /// structure. It does not provide some functionality, but it is
    380   /// faster and simpler than BucketHeap. The main difference is
    381   /// that BucketHeap stores a doubly-linked list for each key while
    382   /// this class stores only simply-linked lists. It supports erasing
    383   /// only for the item having minimum priority and it does not support
    384   /// key increasing and decreasing.
    385   ///
    386   /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some
    388   /// functionality.
    389   ///
    390   /// \tparam IM A read-writable item map with \c int values, used
    391   /// internally to handle the cross references.
    392   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    393   /// The default is \e min-heap. If this parameter is set to \c false,
    394   /// then the comparison is reversed, so the top(), prio() and pop()
    395   /// functions deal with the item having maximum priority instead of the
    396   /// minimum.
     367  /// structure.  It does not provide some functionality but it faster
     368  /// and simplier data structure than the BucketHeap. The main
     369  /// difference is that the BucketHeap stores for every key a double
     370  /// linked list while this class stores just simple lists. In the
     371  /// other way it does not support erasing each elements just the
     372  /// minimal and it does not supports key increasing, decreasing.
     373  ///
     374  /// \param IM A read and write Item int map, used internally
     375  /// to handle the cross references.
     376  /// \param MIN If the given parameter is false then instead of the
     377  /// minimum value the maximum can be retrivied with the top() and
     378  /// prio() member functions.
    397379  ///
    398380  /// \sa BucketHeap
     
    401383
    402384  public:
    403 
    404     /// Type of the item-int map.
     385    typedef typename IM::Key Item;
     386    typedef int Prio;
     387    typedef std::pair<Item, Prio> Pair;
    405388    typedef IM ItemIntMap;
    406     /// Type of the priorities.
    407     typedef int Prio;
    408     /// Type of the items stored in the heap.
    409     typedef typename ItemIntMap::Key Item;
    410     /// Type of the item-priority pairs.
    411     typedef std::pair<Item,Prio> Pair;
    412389
    413390  private:
     
    417394  public:
    418395
    419     /// \brief Type to represent the states of the items.
    420     ///
    421     /// Each item has a state associated to it. It can be "in heap",
    422     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     396    /// \brief Type to represent the items states.
     397    ///
     398    /// Each Item element have a state associated to it. It may be "in heap",
     399    /// "pre heap" or "post heap". The latter two are indifferent from the
    423400    /// heap's point of view, but may be useful to the user.
    424401    ///
     
    433410  public:
    434411
    435     /// \brief Constructor.
    436     ///
    437     /// Constructor.
    438     /// \param map A map that assigns \c int values to the items.
    439     /// It is used internally to handle the cross references.
    440     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     412    /// \brief The constructor.
     413    ///
     414    /// The constructor.
     415    /// \param map should be given to the constructor, since it is used
     416    /// internally to handle the cross references. The value of the map
     417    /// should be PRE_HEAP (-1) for each element.
    441418    explicit SimpleBucketHeap(ItemIntMap &map)
    442419      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    443420
    444     /// \brief The number of items stored in the heap.
    445     ///
    446     /// This function returns the number of items stored in the heap.
     421    /// \brief Returns the number of items stored in the heap.
     422    ///
     423    /// The number of items stored in the heap.
    447424    int size() const { return _num; }
    448425
    449     /// \brief Check if the heap is empty.
    450     ///
    451     /// This function returns \c true if the heap is empty.
     426    /// \brief Checks if the heap stores no items.
     427    ///
     428    /// Returns \c true if and only if the heap stores no items.
    452429    bool empty() const { return _num == 0; }
    453430
    454     /// \brief Make the heap empty.
    455     ///
    456     /// This functon makes the heap empty.
    457     /// It does not change the cross reference map. If you want to reuse
    458     /// a heap that is not surely empty, you should first clear it and
    459     /// then you should set the cross reference map to \c PRE_HEAP
    460     /// for each item.
     431    /// \brief Make empty this heap.
     432    ///
     433    /// Make empty this heap. It does not change the cross reference
     434    /// map.  If you want to reuse a heap what is not surely empty you
     435    /// should first clear the heap and after that you should set the
     436    /// cross reference map for each item to \c PRE_HEAP.
    461437    void clear() {
    462438      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
     
    465441    /// \brief Insert a pair of item and priority into the heap.
    466442    ///
    467     /// This function inserts \c p.first to the heap with priority
    468     /// \c p.second.
     443    /// Adds \c p.first to the heap with priority \c p.second.
    469444    /// \param p The pair to insert.
    470     /// \pre \c p.first must not be stored in the heap.
    471445    void push(const Pair& p) {
    472446      push(p.first, p.second);
     
    475449    /// \brief Insert an item into the heap with the given priority.
    476450    ///
    477     /// This function inserts the given item into the heap with the
    478     /// given priority.
     451    /// Adds \c i to the heap with priority \c p.
    479452    /// \param i The item to insert.
    480453    /// \param p The priority of the item.
    481     /// \pre \e i must not be stored in the heap.
    482454    void push(const Item &i, const Prio &p) {
    483455      int idx;
     
    500472    }
    501473
    502     /// \brief Return the item having minimum priority.
    503     ///
    504     /// This function returns the item having minimum priority.
    505     /// \pre The heap must be non-empty.
     474    /// \brief Returns the item with minimum priority.
     475    ///
     476    /// This method returns the item with minimum priority.
     477    /// \pre The heap must be nonempty.
    506478    Item top() const {
    507479      while (_first[_minimum] == -1) {
     
    511483    }
    512484
    513     /// \brief The minimum priority.
    514     ///
    515     /// This function returns the minimum priority.
    516     /// \pre The heap must be non-empty.
     485    /// \brief Returns the minimum priority.
     486    ///
     487    /// It returns the minimum priority.
     488    /// \pre The heap must be nonempty.
    517489    Prio prio() const {
    518490      while (_first[_minimum] == -1) {
     
    522494    }
    523495
    524     /// \brief Remove the item having minimum priority.
    525     ///
    526     /// This function removes the item having minimum priority.
     496    /// \brief Deletes the item with minimum priority.
     497    ///
     498    /// This method deletes the item with minimum priority from the heap.
    527499    /// \pre The heap must be non-empty.
    528500    void pop() {
     
    538510    }
    539511
    540     /// \brief The priority of the given item.
    541     ///
    542     /// This function returns the priority of the given item.
    543     /// \param i The item.
    544     /// \pre \e i must be in the heap.
    545     /// \warning This operator is not a constant time function because
    546     /// it scans the whole data structure to find the proper value.
     512    /// \brief Returns the priority of \c i.
     513    ///
     514    /// This function returns the priority of item \c i.
     515    /// \warning This operator is not a constant time function
     516    /// because it scans the whole data structure to find the proper
     517    /// value.
     518    /// \pre \c i must be in the heap.
     519    /// \param i The item.
    547520    Prio operator[](const Item &i) const {
    548       for (int k = 0; k < int(_first.size()); ++k) {
     521      for (int k = 0; k < _first.size(); ++k) {
    549522        int idx = _first[k];
    550523        while (idx != -1) {
     
    558531    }
    559532
    560     /// \brief Return the state of an item.
    561     ///
    562     /// This method returns \c PRE_HEAP if the given item has never
    563     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    564     /// and \c POST_HEAP otherwise.
    565     /// In the latter case it is possible that the item will get back
    566     /// to the heap again.
     533    /// \brief Returns if \c item is in, has already been in, or has
     534    /// never been in the heap.
     535    ///
     536    /// This method returns PRE_HEAP if \c item has never been in the
     537    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     538    /// otherwise. In the latter case it is possible that \c item will
     539    /// get back to the heap again.
    567540    /// \param i The item.
    568541    State state(const Item &i) const {
  • lemon/cbc.cc

    r793 r623  
    9595  }
    9696
    97   int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    98     std::vector<int> indexes;
    99     std::vector<Value> values;
    100 
    101     for(ExprIterator it = b; it != e; ++it) {
    102       indexes.push_back(it->first);
    103       values.push_back(it->second);
    104     }
    105 
    106     _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    107     return _prob->numberRows() - 1;
    108   }
    10997
    11098  void CbcMip::_eraseCol(int i) {
  • lemon/cbc.h

    r793 r623  
    6363    virtual int _addCol();
    6464    virtual int _addRow();
    65     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    6665
    6766    virtual void _eraseCol(int i);
  • lemon/circulation.h

    r762 r688  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75 #ifdef DOXYGEN
    76     typedef GR::ArcMap<Value> FlowMap;
    77 #else
    7875    typedef typename Digraph::template ArcMap<Value> FlowMap;
    79 #endif
    8076
    8177    /// \brief Instantiates a FlowMap.
     
    9288    /// The elevator type used by the algorithm.
    9389    ///
    94     /// \sa Elevator, LinkedElevator
    95 #ifdef DOXYGEN
    96     typedef lemon::Elevator<GR, GR::Node> Elevator;
    97 #else
     90    /// \sa Elevator
     91    /// \sa LinkedElevator
    9892    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    99 #endif
    10093
    10194    /// \brief Instantiates an Elevator.
     
    458451    }
    459452
    460     /// \brief Sets the tolerance used by the algorithm.
    461     ///
    462     /// Sets the tolerance object used by the algorithm.
    463     /// \return <tt>(*this)</tt>
    464     Circulation& tolerance(const Tolerance& tolerance) {
     453    /// \brief Sets the tolerance used by algorithm.
     454    ///
     455    /// Sets the tolerance used by algorithm.
     456    Circulation& tolerance(const Tolerance& tolerance) const {
    465457      _tol = tolerance;
    466458      return *this;
     
    469461    /// \brief Returns a const reference to the tolerance.
    470462    ///
    471     /// Returns a const reference to the tolerance object used by
    472     /// the algorithm.
     463    /// Returns a const reference to the tolerance.
    473464    const Tolerance& tolerance() const {
    474       return _tol;
     465      return tolerance;
    475466    }
    476467
    477468    /// \name Execution Control
    478469    /// The simplest way to execute the algorithm is to call \ref run().\n
    479     /// If you need better control on the initial solution or the execution,
    480     /// you have to call one of the \ref init() functions first, then
     470    /// If you need more control on the initial solution or the execution,
     471    /// first you have to call one of the \ref init() functions, then
    481472    /// the \ref start() function.
    482473
  • lemon/clp.cc

    r793 r623  
    7979  }
    8080
    81   int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
    82     std::vector<int> indexes;
    83     std::vector<Value> values;
    84 
    85     for(ExprIterator it = b; it != e; ++it) {
    86       indexes.push_back(it->first);
    87       values.push_back(it->second);
    88     }
    89 
    90     _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    91     return _prob->numberRows() - 1;
    92   }
    93 
    9481
    9582  void ClpLp::_eraseCol(int c) {
  • lemon/clp.h

    r793 r623  
    7676    virtual int _addCol();
    7777    virtual int _addRow();
    78     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    7978
    8079    virtual void _eraseCol(int i);
  • lemon/concepts/digraph.h

    r781 r627  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the common interface of all directed
    39     /// graphs (digraphs).
     38    /// This class describes the \ref concept "concept" of the
     39    /// immutable directed digraphs.
    4040    ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// directed graphs should compile with this class, but it will not
    44     /// run properly, of course.
    45     /// An actual digraph implementation like \ref ListDigraph or
    46     /// \ref SmartDigraph may have additional functionality.
     41    /// Note that actual digraph implementation like @ref ListDigraph or
     42    /// @ref SmartDigraph may have several additional functionality.
    4743    ///
    48     /// \sa Graph
     44    /// \sa concept
    4945    class Digraph {
    5046    private:
    51       /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
    52       Digraph(const Digraph &) {}
    53       /// \brief Assignment of a digraph to another one is \e not allowed.
    54       /// Use DigraphCopy instead.
     47      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
     48
     49      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
     50      ///
     51      Digraph(const Digraph &) {};
     52      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
     53      ///\e not allowed. Use DigraphCopy() instead.
     54
     55      ///Assignment of \ref Digraph "Digraph"s to another ones are
     56      ///\e not allowed.  Use DigraphCopy() instead.
     57
    5558      void operator=(const Digraph &) {}
    56 
    5759    public:
    58       /// Default constructor.
     60      ///\e
     61
     62      /// Defalult constructor.
     63
     64      /// Defalult constructor.
     65      ///
    5966      Digraph() { }
    60 
    61       /// The node type of the digraph
     67      /// Class for identifying a node of the digraph
    6268
    6369      /// This class identifies a node of the digraph. It also serves
    6470      /// as a base class of the node iterators,
    65       /// thus they convert to this type.
     71      /// thus they will convert to this type.
    6672      class Node {
    6773      public:
    6874        /// Default constructor
    6975
    70         /// Default constructor.
    71         /// \warning It sets the object to an undefined value.
     76        /// @warning The default constructor sets the iterator
     77        /// to an undefined value.
    7278        Node() { }
    7379        /// Copy constructor.
     
    7783        Node(const Node&) { }
    7884
    79         /// %Invalid constructor \& conversion.
    80 
    81         /// Initializes the object to be invalid.
     85        /// Invalid constructor \& conversion.
     86
     87        /// This constructor initializes the iterator to be invalid.
    8288        /// \sa Invalid for more details.
    8389        Node(Invalid) { }
    8490        /// Equality operator
    8591
    86         /// Equality operator.
    87         ///
    8892        /// Two iterators are equal if and only if they point to the
    89         /// same object or both are \c INVALID.
     93        /// same object or both are invalid.
    9094        bool operator==(Node) const { return true; }
    9195
    9296        /// Inequality operator
    9397
    94         /// Inequality operator.
     98        /// \sa operator==(Node n)
     99        ///
    95100        bool operator!=(Node) const { return true; }
    96101
    97102        /// Artificial ordering operator.
    98103
    99         /// Artificial ordering operator.
    100         ///
    101         /// \note This operator only has to define some strict ordering of
    102         /// the nodes; this order has nothing to do with the iteration
    103         /// ordering of the nodes.
     104        /// To allow the use of digraph descriptors as key type in std::map or
     105        /// similar associative container we require this.
     106        ///
     107        /// \note This operator only have to define some strict ordering of
     108        /// the items; this order has nothing to do with the iteration
     109        /// ordering of the items.
    104110        bool operator<(Node) const { return false; }
    105       };
    106 
    107       /// Iterator class for the nodes.
    108 
    109       /// This iterator goes through each node of the digraph.
     111
     112      };
     113
     114      /// This iterator goes through each node.
     115
     116      /// This iterator goes through each node.
    110117      /// Its usage is quite simple, for example you can count the number
    111       /// of nodes in a digraph \c g of type \c %Digraph like this:
     118      /// of nodes in digraph \c g of type \c Digraph like this:
    112119      ///\code
    113120      /// int count=0;
     
    118125        /// Default constructor
    119126
    120         /// Default constructor.
    121         /// \warning It sets the iterator to an undefined value.
     127        /// @warning The default constructor sets the iterator
     128        /// to an undefined value.
    122129        NodeIt() { }
    123130        /// Copy constructor.
     
    126133        ///
    127134        NodeIt(const NodeIt& n) : Node(n) { }
    128         /// %Invalid constructor \& conversion.
    129 
    130         /// Initializes the iterator to be invalid.
     135        /// Invalid constructor \& conversion.
     136
     137        /// Initialize the iterator to be invalid.
    131138        /// \sa Invalid for more details.
    132139        NodeIt(Invalid) { }
    133140        /// Sets the iterator to the first node.
    134141
    135         /// Sets the iterator to the first node of the given digraph.
    136         ///
    137         explicit NodeIt(const Digraph&) { }
    138         /// Sets the iterator to the given node.
    139 
    140         /// Sets the iterator to the given node of the given digraph.
    141         ///
     142        /// Sets the iterator to the first node of \c g.
     143        ///
     144        NodeIt(const Digraph&) { }
     145        /// Node -> NodeIt conversion.
     146
     147        /// Sets the iterator to the node of \c the digraph pointed by
     148        /// the trivial iterator.
     149        /// This feature necessitates that each time we
     150        /// iterate the arc-set, the iteration order is the same.
    142151        NodeIt(const Digraph&, const Node&) { }
    143152        /// Next node.
     
    149158
    150159
    151       /// The arc type of the digraph
     160      /// Class for identifying an arc of the digraph
    152161
    153162      /// This class identifies an arc of the digraph. It also serves
     
    158167        /// Default constructor
    159168
    160         /// Default constructor.
    161         /// \warning It sets the object to an undefined value.
     169        /// @warning The default constructor sets the iterator
     170        /// to an undefined value.
    162171        Arc() { }
    163172        /// Copy constructor.
     
    166175        ///
    167176        Arc(const Arc&) { }
    168         /// %Invalid constructor \& conversion.
    169 
    170         /// Initializes the object to be invalid.
    171         /// \sa Invalid for more details.
     177        /// Initialize the iterator to be invalid.
     178
     179        /// Initialize the iterator to be invalid.
     180        ///
    172181        Arc(Invalid) { }
    173182        /// Equality operator
    174183
    175         /// Equality operator.
    176         ///
    177184        /// Two iterators are equal if and only if they point to the
    178         /// same object or both are \c INVALID.
     185        /// same object or both are invalid.
    179186        bool operator==(Arc) const { return true; }
    180187        /// Inequality operator
    181188
    182         /// Inequality operator.
     189        /// \sa operator==(Arc n)
     190        ///
    183191        bool operator!=(Arc) const { return true; }
    184192
    185193        /// Artificial ordering operator.
    186194
    187         /// Artificial ordering operator.
    188         ///
    189         /// \note This operator only has to define some strict ordering of
    190         /// the arcs; this order has nothing to do with the iteration
    191         /// ordering of the arcs.
     195        /// To allow the use of digraph descriptors as key type in std::map or
     196        /// similar associative container we require this.
     197        ///
     198        /// \note This operator only have to define some strict ordering of
     199        /// the items; this order has nothing to do with the iteration
     200        /// ordering of the items.
    192201        bool operator<(Arc) const { return false; }
    193202      };
    194203
    195       /// Iterator class for the outgoing arcs of a node.
     204      /// This iterator goes trough the outgoing arcs of a node.
    196205
    197206      /// This iterator goes trough the \e outgoing arcs of a certain node
     
    199208      /// Its usage is quite simple, for example you can count the number
    200209      /// of outgoing arcs of a node \c n
    201       /// in a digraph \c g of type \c %Digraph as follows.
     210      /// in digraph \c g of type \c Digraph as follows.
    202211      ///\code
    203212      /// int count=0;
    204       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     213      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    205214      ///\endcode
     215
    206216      class OutArcIt : public Arc {
    207217      public:
    208218        /// Default constructor
    209219
    210         /// Default constructor.
    211         /// \warning It sets the iterator to an undefined value.
     220        /// @warning The default constructor sets the iterator
     221        /// to an undefined value.
    212222        OutArcIt() { }
    213223        /// Copy constructor.
     
    216226        ///
    217227        OutArcIt(const OutArcIt& e) : Arc(e) { }
    218         /// %Invalid constructor \& conversion.
    219 
    220         /// Initializes the iterator to be invalid.
    221         /// \sa Invalid for more details.
     228        /// Initialize the iterator to be invalid.
     229
     230        /// Initialize the iterator to be invalid.
     231        ///
    222232        OutArcIt(Invalid) { }
    223         /// Sets the iterator to the first outgoing arc.
    224 
    225         /// Sets the iterator to the first outgoing arc of the given node.
    226         ///
     233        /// This constructor sets the iterator to the first outgoing arc.
     234
     235        /// This constructor sets the iterator to the first outgoing arc of
     236        /// the node.
    227237        OutArcIt(const Digraph&, const Node&) { }
    228         /// Sets the iterator to the given arc.
    229 
    230         /// Sets the iterator to the given arc of the given digraph.
    231         ///
     238        /// Arc -> OutArcIt conversion
     239
     240        /// Sets the iterator to the value of the trivial iterator.
     241        /// This feature necessitates that each time we
     242        /// iterate the arc-set, the iteration order is the same.
    232243        OutArcIt(const Digraph&, const Arc&) { }
    233         /// Next outgoing arc
     244        ///Next outgoing arc
    234245
    235246        /// Assign the iterator to the next
     
    238249      };
    239250
    240       /// Iterator class for the incoming arcs of a node.
     251      /// This iterator goes trough the incoming arcs of a node.
    241252
    242253      /// This iterator goes trough the \e incoming arcs of a certain node
    243254      /// of a digraph.
    244255      /// Its usage is quite simple, for example you can count the number
    245       /// of incoming arcs of a node \c n
    246       /// in a digraph \c g of type \c %Digraph as follows.
     256      /// of outgoing arcs of a node \c n
     257      /// in digraph \c g of type \c Digraph as follows.
    247258      ///\code
    248259      /// int count=0;
    249       /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     260      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    250261      ///\endcode
     262
    251263      class InArcIt : public Arc {
    252264      public:
    253265        /// Default constructor
    254266
    255         /// Default constructor.
    256         /// \warning It sets the iterator to an undefined value.
     267        /// @warning The default constructor sets the iterator
     268        /// to an undefined value.
    257269        InArcIt() { }
    258270        /// Copy constructor.
     
    261273        ///
    262274        InArcIt(const InArcIt& e) : Arc(e) { }
    263         /// %Invalid constructor \& conversion.
    264 
    265         /// Initializes the iterator to be invalid.
    266         /// \sa Invalid for more details.
     275        /// Initialize the iterator to be invalid.
     276
     277        /// Initialize the iterator to be invalid.
     278        ///
    267279        InArcIt(Invalid) { }
    268         /// Sets the iterator to the first incoming arc.
    269 
    270         /// Sets the iterator to the first incoming arc of the given node.
    271         ///
     280        /// This constructor sets the iterator to first incoming arc.
     281
     282        /// This constructor set the iterator to the first incoming arc of
     283        /// the node.
    272284        InArcIt(const Digraph&, const Node&) { }
    273         /// Sets the iterator to the given arc.
    274 
    275         /// Sets the iterator to the given arc of the given digraph.
    276         ///
     285        /// Arc -> InArcIt conversion
     286
     287        /// Sets the iterator to the value of the trivial iterator \c e.
     288        /// This feature necessitates that each time we
     289        /// iterate the arc-set, the iteration order is the same.
    277290        InArcIt(const Digraph&, const Arc&) { }
    278291        /// Next incoming arc
    279292
    280         /// Assign the iterator to the next
    281         /// incoming arc of the corresponding node.
     293        /// Assign the iterator to the next inarc of the corresponding node.
     294        ///
    282295        InArcIt& operator++() { return *this; }
    283296      };
    284 
    285       /// Iterator class for the arcs.
    286 
    287       /// This iterator goes through each arc of the digraph.
     297      /// This iterator goes through each arc.
     298
     299      /// This iterator goes through each arc of a digraph.
    288300      /// Its usage is quite simple, for example you can count the number
    289       /// of arcs in a digraph \c g of type \c %Digraph as follows:
     301      /// of arcs in a digraph \c g of type \c Digraph as follows:
    290302      ///\code
    291303      /// int count=0;
    292       /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
     304      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
    293305      ///\endcode
    294306      class ArcIt : public Arc {
     
    296308        /// Default constructor
    297309
    298         /// Default constructor.
    299         /// \warning It sets the iterator to an undefined value.
     310        /// @warning The default constructor sets the iterator
     311        /// to an undefined value.
    300312        ArcIt() { }
    301313        /// Copy constructor.
     
    304316        ///
    305317        ArcIt(const ArcIt& e) : Arc(e) { }
    306         /// %Invalid constructor \& conversion.
    307 
    308         /// Initializes the iterator to be invalid.
    309         /// \sa Invalid for more details.
     318        /// Initialize the iterator to be invalid.
     319
     320        /// Initialize the iterator to be invalid.
     321        ///
    310322        ArcIt(Invalid) { }
    311         /// Sets the iterator to the first arc.
    312 
    313         /// Sets the iterator to the first arc of the given digraph.
    314         ///
    315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
    316         /// Sets the iterator to the given arc.
    317 
    318         /// Sets the iterator to the given arc of the given digraph.
    319         ///
     323        /// This constructor sets the iterator to the first arc.
     324
     325        /// This constructor sets the iterator to the first arc of \c g.
     326        ///@param g the digraph
     327        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     328        /// Arc -> ArcIt conversion
     329
     330        /// Sets the iterator to the value of the trivial iterator \c e.
     331        /// This feature necessitates that each time we
     332        /// iterate the arc-set, the iteration order is the same.
    320333        ArcIt(const Digraph&, const Arc&) { }
    321         /// Next arc
     334        ///Next arc
    322335
    323336        /// Assign the iterator to the next arc.
    324         ///
    325337        ArcIt& operator++() { return *this; }
    326338      };
    327 
    328       /// \brief The source node of the arc.
    329       ///
    330       /// Returns the source node of the given arc.
     339      ///Gives back the target node of an arc.
     340
     341      ///Gives back the target node of an arc.
     342      ///
     343      Node target(Arc) const { return INVALID; }
     344      ///Gives back the source node of an arc.
     345
     346      ///Gives back the source node of an arc.
     347      ///
    331348      Node source(Arc) const { return INVALID; }
    332349
    333       /// \brief The target node of the arc.
    334       ///
    335       /// Returns the target node of the given arc.
    336       Node target(Arc) const { return INVALID; }
    337 
    338       /// \brief The ID of the node.
    339       ///
    340       /// Returns the ID of the given node.
     350      /// \brief Returns the ID of the node.
    341351      int id(Node) const { return -1; }
    342352
    343       /// \brief The ID of the arc.
    344       ///
    345       /// Returns the ID of the given arc.
     353      /// \brief Returns the ID of the arc.
    346354      int id(Arc) const { return -1; }
    347355
    348       /// \brief The node with the given ID.
    349       ///
    350       /// Returns the node with the given ID.
    351       /// \pre The argument should be a valid node ID in the digraph.
     356      /// \brief Returns the node with the given ID.
     357      ///
     358      /// \pre The argument should be a valid node ID in the graph.
    352359      Node nodeFromId(int) const { return INVALID; }
    353360
    354       /// \brief The arc with the given ID.
    355       ///
    356       /// Returns the arc with the given ID.
    357       /// \pre The argument should be a valid arc ID in the digraph.
     361      /// \brief Returns the arc with the given ID.
     362      ///
     363      /// \pre The argument should be a valid arc ID in the graph.
    358364      Arc arcFromId(int) const { return INVALID; }
    359365
    360       /// \brief An upper bound on the node IDs.
    361       ///
    362       /// Returns an upper bound on the node IDs.
     366      /// \brief Returns an upper bound on the node IDs.
    363367      int maxNodeId() const { return -1; }
    364368
    365       /// \brief An upper bound on the arc IDs.
    366       ///
    367       /// Returns an upper bound on the arc IDs.
     369      /// \brief Returns an upper bound on the arc IDs.
    368370      int maxArcId() const { return -1; }
    369371
     
    391393      int maxId(Arc) const { return -1; }
    392394
    393       /// \brief The opposite node on the arc.
    394       ///
    395       /// Returns the opposite node on the given arc.
    396       Node oppositeNode(Node, Arc) const { return INVALID; }
    397 
    398395      /// \brief The base node of the iterator.
    399396      ///
    400       /// Returns the base node of the given outgoing arc iterator
    401       /// (i.e. the source node of the corresponding arc).
    402       Node baseNode(OutArcIt) const { return INVALID; }
     397      /// Gives back the base node of the iterator.
     398      /// It is always the target of the pointed arc.
     399      Node baseNode(const InArcIt&) const { return INVALID; }
    403400
    404401      /// \brief The running node of the iterator.
    405402      ///
    406       /// Returns the running node of the given outgoing arc iterator
    407       /// (i.e. the target node of the corresponding arc).
    408       Node runningNode(OutArcIt) const { return INVALID; }
     403      /// Gives back the running node of the iterator.
     404      /// It is always the source of the pointed arc.
     405      Node runningNode(const InArcIt&) const { return INVALID; }
    409406
    410407      /// \brief The base node of the iterator.
    411408      ///
    412       /// Returns the base node of the given incomming arc iterator
    413       /// (i.e. the target node of the corresponding arc).
    414       Node baseNode(InArcIt) const { return INVALID; }
     409      /// Gives back the base node of the iterator.
     410      /// It is always the source of the pointed arc.
     411      Node baseNode(const OutArcIt&) const { return INVALID; }
    415412
    416413      /// \brief The running node of the iterator.
    417414      ///
    418       /// Returns the running node of the given incomming arc iterator
    419       /// (i.e. the source node of the corresponding arc).
    420       Node runningNode(InArcIt) const { return INVALID; }
    421 
    422       /// \brief Standard graph map type for the nodes.
    423       ///
    424       /// Standard graph map type for the nodes.
    425       /// It conforms to the ReferenceMap concept.
     415      /// Gives back the running node of the iterator.
     416      /// It is always the target of the pointed arc.
     417      Node runningNode(const OutArcIt&) const { return INVALID; }
     418
     419      /// \brief The opposite node on the given arc.
     420      ///
     421      /// Gives back the opposite node on the given arc.
     422      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
     423
     424      /// \brief Reference map of the nodes to type \c T.
     425      ///
     426      /// Reference map of the nodes to type \c T.
    426427      template<class T>
    427428      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    428429      public:
    429430
    430         /// Constructor
    431         explicit NodeMap(const Digraph&) { }
    432         /// Constructor with given initial value
     431        ///\e
     432        NodeMap(const Digraph&) { }
     433        ///\e
    433434        NodeMap(const Digraph&, T) { }
    434435
     
    445446      };
    446447
    447       /// \brief Standard graph map type for the arcs.
    448       ///
    449       /// Standard graph map type for the arcs.
    450       /// It conforms to the ReferenceMap concept.
     448      /// \brief Reference map of the arcs to type \c T.
     449      ///
     450      /// Reference map of the arcs to type \c T.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         /// Constructor
    456         explicit ArcMap(const Digraph&) { }
    457         /// Constructor with given initial value
     455        ///\e
     456        ArcMap(const Digraph&) { }
     457        ///\e
    458458        ArcMap(const Digraph&, T) { }
    459 
    460459      private:
    461460        ///Copy constructor
  • lemon/concepts/graph.h

    r781 r704  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of undirected graphs.
     21///\brief The concept of Undirected Graphs.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_H
     
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/maps.h>
    28 #include <lemon/concept_check.h>
    2927#include <lemon/core.h>
    3028
     
    3432    /// \ingroup graph_concepts
    3533    ///
    36     /// \brief Class describing the concept of undirected graphs.
     34    /// \brief Class describing the concept of Undirected Graphs.
    3735    ///
    38     /// This class describes the common interface of all undirected
    39     /// graphs.
     36    /// This class describes the common interface of all Undirected
     37    /// Graphs.
    4038    ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// undirected graphs should compile with this class, but it will not
     39    /// As all concept describing classes it provides only interface
     40    /// without any sensible implementation. So any algorithm for
     41    /// undirected graph should compile with this class, but it will not
    4442    /// run properly, of course.
    45     /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.   
    4743    ///
    48     /// The undirected graphs also fulfill the concept of \ref Digraph
    49     /// "directed graphs", since each edge can also be regarded as two
    50     /// oppositely directed arcs.
    51     /// Undirected graphs provide an Edge type for the undirected edges and
    52     /// an Arc type for the directed arcs. The Arc type is convertible to
    53     /// Edge or inherited from it, i.e. the corresponding edge can be
    54     /// obtained from an arc.
    55     /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
    56     /// and ArcMap classes can be used for the arcs (just like in digraphs).
    57     /// Both InArcIt and OutArcIt iterates on the same edges but with
    58     /// opposite direction. IncEdgeIt also iterates on the same edges
    59     /// as OutArcIt and InArcIt, but it is not convertible to Arc,
    60     /// only to Edge.
     44    /// The LEMON undirected graphs also fulfill the concept of
     45    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
     46    /// Concept"). Each edges can be seen as two opposite
     47    /// directed arc and consequently the undirected graph can be
     48    /// seen as the direceted graph of these directed arcs. The
     49    /// Graph has the Edge inner class for the edges and
     50    /// the Arc type for the directed arcs. The Arc type is
     51    /// convertible to Edge or inherited from it so from a directed
     52    /// arc we can get the represented edge.
    6153    ///
    62     /// In LEMON, each undirected edge has an inherent orientation.
    63     /// Thus it can defined if an arc is forward or backward oriented in
    64     /// an undirected graph with respect to this default oriantation of
    65     /// the represented edge.
    66     /// With the direction() and direct() functions the direction
    67     /// of an arc can be obtained and set, respectively.
     54    /// In the sense of the LEMON each edge has a default
     55    /// direction (it should be in every computer implementation,
     56    /// because the order of edge's nodes defines an
     57    /// orientation). With the default orientation we can define that
     58    /// the directed arc is forward or backward directed. With the \c
     59    /// direction() and \c direct() function we can get the direction
     60    /// of the directed arc and we can direct an edge.
    6861    ///
    69     /// Only nodes and edges can be added to or removed from an undirected
    70     /// graph and the corresponding arcs are added or removed automatically.
    71     ///
    72     /// \sa Digraph
     62    /// The EdgeIt is an iterator for the edges. We can use
     63    /// the EdgeMap to map values for the edges. The InArcIt and
     64    /// OutArcIt iterates on the same edges but with opposite
     65    /// direction. The IncEdgeIt iterates also on the same edges
     66    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
     67    /// to Edge.
    7368    class Graph {
    74     private:
    75       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
    76       Graph(const Graph&) {}
    77       /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
    79       void operator=(const Graph&) {}
    80 
    8169    public:
    82       /// Default constructor.
    83       Graph() {}
    84 
    85       /// \brief Undirected graphs should be tagged with \c UndirectedTag.
    86       ///
    87       /// Undirected graphs should be tagged with \c UndirectedTag.
    88       ///
    89       /// This tag helps the \c enable_if technics to make compile time
     70      /// \brief The undirected graph should be tagged by the
     71      /// UndirectedTag.
     72      ///
     73      /// The undirected graph should be tagged by the UndirectedTag. This
     74      /// tag helps the enable_if technics to make compile time
    9075      /// specializations for undirected graphs.
    9176      typedef True UndirectedTag;
    9277
    93       /// The node type of the graph
    94 
    95       /// This class identifies a node of the graph. It also serves
    96       /// as a base class of the node iterators,
    97       /// thus they convert to this type.
     78      /// \brief The base type of node iterators,
     79      /// or in other words, the trivial node iterator.
     80      ///
     81      /// This is the base type of each node iterator,
     82      /// thus each kind of node iterator converts to this.
     83      /// More precisely each kind of node iterator should be inherited
     84      /// from the trivial node iterator.
    9885      class Node {
    9986      public:
    10087        /// Default constructor
    10188
    102         /// Default constructor.
    103         /// \warning It sets the object to an undefined value.
     89        /// @warning The default constructor sets the iterator
     90        /// to an undefined value.
    10491        Node() { }
    10592        /// Copy constructor.
     
    10996        Node(const Node&) { }
    11097
    111         /// %Invalid constructor \& conversion.
    112 
    113         /// Initializes the object to be invalid.
     98        /// Invalid constructor \& conversion.
     99
     100        /// This constructor initializes the iterator to be invalid.
    114101        /// \sa Invalid for more details.
    115102        Node(Invalid) { }
    116103        /// Equality operator
    117104
    118         /// Equality operator.
    119         ///
    120105        /// Two iterators are equal if and only if they point to the
    121         /// same object or both are \c INVALID.
     106        /// same object or both are invalid.
    122107        bool operator==(Node) const { return true; }
    123108
    124109        /// Inequality operator
    125110
    126         /// Inequality operator.
     111        /// \sa operator==(Node n)
     112        ///
    127113        bool operator!=(Node) const { return true; }
    128114
    129115        /// Artificial ordering operator.
    130116
    131         /// Artificial ordering operator.
    132         ///
    133         /// \note This operator only has to define some strict ordering of
     117        /// To allow the use of graph descriptors as key type in std::map or
     118        /// similar associative container we require this.
     119        ///
     120        /// \note This operator only have to define some strict ordering of
    134121        /// the items; this order has nothing to do with the iteration
    135122        /// ordering of the items.
     
    138125      };
    139126
    140       /// Iterator class for the nodes.
    141 
    142       /// This iterator goes through each node of the graph.
     127      /// This iterator goes through each node.
     128
     129      /// This iterator goes through each node.
    143130      /// Its usage is quite simple, for example you can count the number
    144       /// of nodes in a graph \c g of type \c %Graph like this:
     131      /// of nodes in graph \c g of type \c Graph like this:
    145132      ///\code
    146133      /// int count=0;
     
    151138        /// Default constructor
    152139
    153         /// Default constructor.
    154         /// \warning It sets the iterator to an undefined value.
     140        /// @warning The default constructor sets the iterator
     141        /// to an undefined value.
    155142        NodeIt() { }
    156143        /// Copy constructor.
     
    159146        ///
    160147        NodeIt(const NodeIt& n) : Node(n) { }
    161         /// %Invalid constructor \& conversion.
    162 
    163         /// Initializes the iterator to be invalid.
     148        /// Invalid constructor \& conversion.
     149
     150        /// Initialize the iterator to be invalid.
    164151        /// \sa Invalid for more details.
    165152        NodeIt(Invalid) { }
    166153        /// Sets the iterator to the first node.
    167154
    168         /// Sets the iterator to the first node of the given digraph.
    169         ///
    170         explicit NodeIt(const Graph&) { }
    171         /// Sets the iterator to the given node.
    172 
    173         /// Sets the iterator to the given node of the given digraph.
    174         ///
     155        /// Sets the iterator to the first node of \c g.
     156        ///
     157        NodeIt(const Graph&) { }
     158        /// Node -> NodeIt conversion.
     159
     160        /// Sets the iterator to the node of \c the graph pointed by
     161        /// the trivial iterator.
     162        /// This feature necessitates that each time we
     163        /// iterate the arc-set, the iteration order is the same.
    175164        NodeIt(const Graph&, const Node&) { }
    176165        /// Next node.
     
    182171
    183172
    184       /// The edge type of the graph
    185 
    186       /// This class identifies an edge of the graph. It also serves
    187       /// as a base class of the edge iterators,
    188       /// thus they will convert to this type.
     173      /// The base type of the edge iterators.
     174
     175      /// The base type of the edge iterators.
     176      ///
    189177      class Edge {
    190178      public:
    191179        /// Default constructor
    192180
    193         /// Default constructor.
    194         /// \warning It sets the object to an undefined value.
     181        /// @warning The default constructor sets the iterator
     182        /// to an undefined value.
    195183        Edge() { }
    196184        /// Copy constructor.
     
    199187        ///
    200188        Edge(const Edge&) { }
    201         /// %Invalid constructor \& conversion.
    202 
    203         /// Initializes the object to be invalid.
    204         /// \sa Invalid for more details.
     189        /// Initialize the iterator to be invalid.
     190
     191        /// Initialize the iterator to be invalid.
     192        ///
    205193        Edge(Invalid) { }
    206194        /// Equality operator
    207195
    208         /// Equality operator.
    209         ///
    210196        /// Two iterators are equal if and only if they point to the
    211         /// same object or both are \c INVALID.
     197        /// same object or both are invalid.
    212198        bool operator==(Edge) const { return true; }
    213199        /// Inequality operator
    214200
    215         /// Inequality operator.
     201        /// \sa operator==(Edge n)
     202        ///
    216203        bool operator!=(Edge) const { return true; }
    217204
    218205        /// Artificial ordering operator.
    219206
    220         /// Artificial ordering operator.
    221         ///
    222         /// \note This operator only has to define some strict ordering of
    223         /// the edges; this order has nothing to do with the iteration
    224         /// ordering of the edges.
     207        /// To allow the use of graph descriptors as key type in std::map or
     208        /// similar associative container we require this.
     209        ///
     210        /// \note This operator only have to define some strict ordering of
     211        /// the items; this order has nothing to do with the iteration
     212        /// ordering of the items.
    225213        bool operator<(Edge) const { return false; }
    226214      };
    227215
    228       /// Iterator class for the edges.
    229 
    230       /// This iterator goes through each edge of the graph.
     216      /// This iterator goes through each edge.
     217
     218      /// This iterator goes through each edge of a graph.
    231219      /// Its usage is quite simple, for example you can count the number
    232       /// of edges in a graph \c g of type \c %Graph as follows:
     220      /// of edges in a graph \c g of type \c Graph as follows:
    233221      ///\code
    234222      /// int count=0;
     
    239227        /// Default constructor
    240228
    241         /// Default constructor.
    242         /// \warning It sets the iterator to an undefined value.
     229        /// @warning The default constructor sets the iterator
     230        /// to an undefined value.
    243231        EdgeIt() { }
    244232        /// Copy constructor.
     
    247235        ///
    248236        EdgeIt(const EdgeIt& e) : Edge(e) { }
    249         /// %Invalid constructor \& conversion.
    250 
    251         /// Initializes the iterator to be invalid.
    252         /// \sa Invalid for more details.
     237        /// Initialize the iterator to be invalid.
     238
     239        /// Initialize the iterator to be invalid.
     240        ///
    253241        EdgeIt(Invalid) { }
    254         /// Sets the iterator to the first edge.
    255 
    256         /// Sets the iterator to the first edge of the given graph.
    257         ///
    258         explicit EdgeIt(const Graph&) { }
    259         /// Sets the iterator to the given edge.
    260 
    261         /// Sets the iterator to the given edge of the given graph.
    262         ///
     242        /// This constructor sets the iterator to the first edge.
     243
     244        /// This constructor sets the iterator to the first edge.
     245        EdgeIt(const Graph&) { }
     246        /// Edge -> EdgeIt conversion
     247
     248        /// Sets the iterator to the value of the trivial iterator.
     249        /// This feature necessitates that each time we
     250        /// iterate the edge-set, the iteration order is the
     251        /// same.
    263252        EdgeIt(const Graph&, const Edge&) { }
    264253        /// Next edge
    265254
    266255        /// Assign the iterator to the next edge.
    267         ///
    268256        EdgeIt& operator++() { return *this; }
    269257      };
    270258
    271       /// Iterator class for the incident edges of a node.
    272 
    273       /// This iterator goes trough the incident undirected edges
    274       /// of a certain node of a graph.
     259      /// \brief This iterator goes trough the incident undirected
     260      /// arcs of a node.
     261      ///
     262      /// This iterator goes trough the incident edges
     263      /// of a certain node of a graph. You should assume that the
     264      /// loop arcs will be iterated twice.
     265      ///
    275266      /// Its usage is quite simple, for example you can compute the
    276       /// degree (i.e. the number of incident edges) of a node \c n
    277       /// in a graph \c g of type \c %Graph as follows.
     267      /// degree (i.e. count the number of incident arcs of a node \c n
     268      /// in graph \c g of type \c Graph as follows.
    278269      ///
    279270      ///\code
     
    281272      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    282273      ///\endcode
    283       ///
    284       /// \warning Loop edges will be iterated twice.
    285274      class IncEdgeIt : public Edge {
    286275      public:
    287276        /// Default constructor
    288277
    289         /// Default constructor.
    290         /// \warning It sets the iterator to an undefined value.
     278        /// @warning The default constructor sets the iterator
     279        /// to an undefined value.
    291280        IncEdgeIt() { }
    292281        /// Copy constructor.
     
    295284        ///
    296285        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    297         /// %Invalid constructor \& conversion.
    298 
    299         /// Initializes the iterator to be invalid.
    300         /// \sa Invalid for more details.
     286        /// Initialize the iterator to be invalid.
     287
     288        /// Initialize the iterator to be invalid.
     289        ///
    301290        IncEdgeIt(Invalid) { }
    302         /// Sets the iterator to the first incident edge.
    303 
    304         /// Sets the iterator to the first incident edge of the given node.
    305         ///
     291        /// This constructor sets the iterator to first incident arc.
     292
     293        /// This constructor set the iterator to the first incident arc of
     294        /// the node.
    306295        IncEdgeIt(const Graph&, const Node&) { }
    307         /// Sets the iterator to the given edge.
    308 
    309         /// Sets the iterator to the given edge of the given graph.
    310         ///
     296        /// Edge -> IncEdgeIt conversion
     297
     298        /// Sets the iterator to the value of the trivial iterator \c e.
     299        /// This feature necessitates that each time we
     300        /// iterate the arc-set, the iteration order is the same.
    311301        IncEdgeIt(const Graph&, const Edge&) { }
    312         /// Next incident edge
    313 
    314         /// Assign the iterator to the next incident edge
     302        /// Next incident arc
     303
     304        /// Assign the iterator to the next incident arc
    315305        /// of the corresponding node.
    316306        IncEdgeIt& operator++() { return *this; }
    317307      };
    318308
    319       /// The arc type of the graph
    320 
    321       /// This class identifies a directed arc of the graph. It also serves
    322       /// as a base class of the arc iterators,
    323       /// thus they will convert to this type.
     309      /// The directed arc type.
     310
     311      /// The directed arc type. It can be converted to the
     312      /// edge or it should be inherited from the undirected
     313      /// edge.
    324314      class Arc {
    325315      public:
    326316        /// Default constructor
    327317
    328         /// Default constructor.
    329         /// \warning It sets the object to an undefined value.
     318        /// @warning The default constructor sets the iterator
     319        /// to an undefined value.
    330320        Arc() { }
    331321        /// Copy constructor.
     
    334324        ///
    335325        Arc(const Arc&) { }
    336         /// %Invalid constructor \& conversion.
    337 
    338         /// Initializes the object to be invalid.
    339         /// \sa Invalid for more details.
     326        /// Initialize the iterator to be invalid.
     327
     328        /// Initialize the iterator to be invalid.
     329        ///
    340330        Arc(Invalid) { }
    341331        /// Equality operator
    342332
    343         /// Equality operator.
    344         ///
    345333        /// Two iterators are equal if and only if they point to the
    346         /// same object or both are \c INVALID.
     334        /// same object or both are invalid.
    347335        bool operator==(Arc) const { return true; }
    348336        /// Inequality operator
    349337
    350         /// Inequality operator.
     338        /// \sa operator==(Arc n)
     339        ///
    351340        bool operator!=(Arc) const { return true; }
    352341
    353342        /// Artificial ordering operator.
    354343
    355         /// Artificial ordering operator.
    356         ///
    357         /// \note This operator only has to define some strict ordering of
    358         /// the arcs; this order has nothing to do with the iteration
    359         /// ordering of the arcs.
     344        /// To allow the use of graph descriptors as key type in std::map or
     345        /// similar associative container we require this.
     346        ///
     347        /// \note This operator only have to define some strict ordering of
     348        /// the items; this order has nothing to do with the iteration
     349        /// ordering of the items.
    360350        bool operator<(Arc) const { return false; }
    361351
    362         /// Converison to \c Edge
    363        
    364         /// Converison to \c Edge.
    365         ///
     352        /// Converison to Edge
    366353        operator Edge() const { return Edge(); }
    367354      };
    368 
    369       /// Iterator class for the arcs.
    370 
    371       /// This iterator goes through each directed arc of the graph.
     355      /// This iterator goes through each directed arc.
     356
     357      /// This iterator goes through each arc of a graph.
    372358      /// Its usage is quite simple, for example you can count the number
    373       /// of arcs in a graph \c g of type \c %Graph as follows:
     359      /// of arcs in a graph \c g of type \c Graph as follows:
    374360      ///\code
    375361      /// int count=0;
    376       /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
     362      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
    377363      ///\endcode
    378364      class ArcIt : public Arc {
     
    380366        /// Default constructor
    381367
    382         /// Default constructor.
    383         /// \warning It sets the iterator to an undefined value.
     368        /// @warning The default constructor sets the iterator
     369        /// to an undefined value.
    384370        ArcIt() { }
    385371        /// Copy constructor.
     
    388374        ///
    389375        ArcIt(const ArcIt& e) : Arc(e) { }
    390         /// %Invalid constructor \& conversion.
    391 
    392         /// Initializes the iterator to be invalid.
    393         /// \sa Invalid for more details.
     376        /// Initialize the iterator to be invalid.
     377
     378        /// Initialize the iterator to be invalid.
     379        ///
    394380        ArcIt(Invalid) { }
    395         /// Sets the iterator to the first arc.
    396 
    397         /// Sets the iterator to the first arc of the given graph.
    398         ///
    399         explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
    400         /// Sets the iterator to the given arc.
    401 
    402         /// Sets the iterator to the given arc of the given graph.
    403         ///
     381        /// This constructor sets the iterator to the first arc.
     382
     383        /// This constructor sets the iterator to the first arc of \c g.
     384        ///@param g the graph
     385        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     386        /// Arc -> ArcIt conversion
     387
     388        /// Sets the iterator to the value of the trivial iterator \c e.
     389        /// This feature necessitates that each time we
     390        /// iterate the arc-set, the iteration order is the same.
    404391        ArcIt(const Graph&, const Arc&) { }
    405         /// Next arc
     392        ///Next arc
    406393
    407394        /// Assign the iterator to the next arc.
    408         ///
    409395        ArcIt& operator++() { return *this; }
    410396      };
    411397
    412       /// Iterator class for the outgoing arcs of a node.
    413 
    414       /// This iterator goes trough the \e outgoing directed arcs of a
    415       /// certain node of a graph.
     398      /// This iterator goes trough the outgoing directed arcs of a node.
     399
     400      /// This iterator goes trough the \e outgoing arcs of a certain node
     401      /// of a graph.
    416402      /// Its usage is quite simple, for example you can count the number
    417403      /// of outgoing arcs of a node \c n
    418       /// in a graph \c g of type \c %Graph as follows.
     404      /// in graph \c g of type \c Graph as follows.
    419405      ///\code
    420406      /// int count=0;
    421       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     407      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    422408      ///\endcode
     409
    423410      class OutArcIt : public Arc {
    424411      public:
    425412        /// Default constructor
    426413
    427         /// Default constructor.
    428         /// \warning It sets the iterator to an undefined value.
     414        /// @warning The default constructor sets the iterator
     415        /// to an undefined value.
    429416        OutArcIt() { }
    430417        /// Copy constructor.
     
    433420        ///
    434421        OutArcIt(const OutArcIt& e) : Arc(e) { }
    435         /// %Invalid constructor \& conversion.
    436 
    437         /// Initializes the iterator to be invalid.
    438         /// \sa Invalid for more details.
     422        /// Initialize the iterator to be invalid.
     423
     424        /// Initialize the iterator to be invalid.
     425        ///
    439426        OutArcIt(Invalid) { }
    440         /// Sets the iterator to the first outgoing arc.
    441 
    442         /// Sets the iterator to the first outgoing arc of the given node.
    443         ///
     427        /// This constructor sets the iterator to the first outgoing arc.
     428
     429        /// This constructor sets the iterator to the first outgoing arc of
     430        /// the node.
     431        ///@param n the node
     432        ///@param g the graph
    444433        OutArcIt(const Graph& n, const Node& g) {
    445434          ignore_unused_variable_warning(n);
    446435          ignore_unused_variable_warning(g);
    447436        }
    448         /// Sets the iterator to the given arc.
    449 
    450         /// Sets the iterator to the given arc of the given graph.
    451         ///
     437        /// Arc -> OutArcIt conversion
     438
     439        /// Sets the iterator to the value of the trivial iterator.
     440        /// This feature necessitates that each time we
     441        /// iterate the arc-set, the iteration order is the same.
    452442        OutArcIt(const Graph&, const Arc&) { }
    453         /// Next outgoing arc
     443        ///Next outgoing arc
    454444
    455445        /// Assign the iterator to the next
     
    458448      };
    459449
    460       /// Iterator class for the incoming arcs of a node.
    461 
    462       /// This iterator goes trough the \e incoming directed arcs of a
    463       /// certain node of a graph.
     450      /// This iterator goes trough the incoming directed arcs of a node.
     451
     452      /// This iterator goes trough the \e incoming arcs of a certain node
     453      /// of a graph.
    464454      /// Its usage is quite simple, for example you can count the number
    465       /// of incoming arcs of a node \c n
    466       /// in a graph \c g of type \c %Graph as follows.
     455      /// of outgoing arcs of a node \c n
     456      /// in graph \c g of type \c Graph as follows.
    467457      ///\code
    468458      /// int count=0;
    469       /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     459      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    470460      ///\endcode
     461
    471462      class InArcIt : public Arc {
    472463      public:
    473464        /// Default constructor
    474465
    475         /// Default constructor.
    476         /// \warning It sets the iterator to an undefined value.
     466        /// @warning The default constructor sets the iterator
     467        /// to an undefined value.
    477468        InArcIt() { }
    478469        /// Copy constructor.
     
    481472        ///
    482473        InArcIt(const InArcIt& e) : Arc(e) { }
    483         /// %Invalid constructor \& conversion.
    484 
    485         /// Initializes the iterator to be invalid.
    486         /// \sa Invalid for more details.
     474        /// Initialize the iterator to be invalid.
     475
     476        /// Initialize the iterator to be invalid.
     477        ///
    487478        InArcIt(Invalid) { }
    488         /// Sets the iterator to the first incoming arc.
    489 
    490         /// Sets the iterator to the first incoming arc of the given node.
    491         ///
     479        /// This constructor sets the iterator to first incoming arc.
     480
     481        /// This constructor set the iterator to the first incoming arc of
     482        /// the node.
     483        ///@param n the node
     484        ///@param g the graph
    492485        InArcIt(const Graph& g, const Node& n) {
    493486          ignore_unused_variable_warning(n);
    494487          ignore_unused_variable_warning(g);
    495488        }
    496         /// Sets the iterator to the given arc.
    497 
    498         /// Sets the iterator to the given arc of the given graph.
    499         ///
     489        /// Arc -> InArcIt conversion
     490
     491        /// Sets the iterator to the value of the trivial iterator \c e.
     492        /// This feature necessitates that each time we
     493        /// iterate the arc-set, the iteration order is the same.
    500494        InArcIt(const Graph&, const Arc&) { }
    501495        /// Next incoming arc
    502496
    503         /// Assign the iterator to the next
    504         /// incoming arc of the corresponding node.
     497        /// Assign the iterator to the next inarc of the corresponding node.
     498        ///
    505499        InArcIt& operator++() { return *this; }
    506500      };
    507501
    508       /// \brief Standard graph map type for the nodes.
    509       ///
    510       /// Standard graph map type for the nodes.
    511       /// It conforms to the ReferenceMap concept.
     502      /// \brief Reference map of the nodes to type \c T.
     503      ///
     504      /// Reference map of the nodes to type \c T.
    512505      template<class T>
    513506      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     
    515508      public:
    516509
    517         /// Constructor
    518         explicit NodeMap(const Graph&) { }
    519         /// Constructor with given initial value
     510        ///\e
     511        NodeMap(const Graph&) { }
     512        ///\e
    520513        NodeMap(const Graph&, T) { }
    521514
     
    532525      };
    533526
    534       /// \brief Standard graph map type for the arcs.
    535       ///
    536       /// Standard graph map type for the arcs.
    537       /// It conforms to the ReferenceMap concept.
     527      /// \brief Reference map of the arcs to type \c T.
     528      ///
     529      /// Reference map of the arcs to type \c T.
    538530      template<class T>
    539531      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     
    541533      public:
    542534
    543         /// Constructor
    544         explicit ArcMap(const Graph&) { }
    545         /// Constructor with given initial value
     535        ///\e
     536        ArcMap(const Graph&) { }
     537        ///\e
    546538        ArcMap(const Graph&, T) { }
    547 
    548539      private:
    549540        ///Copy constructor
     
    558549      };
    559550
    560       /// \brief Standard graph map type for the edges.
    561       ///
    562       /// Standard graph map type for the edges.
    563       /// It conforms to the ReferenceMap concept.
     551      /// Reference map of the edges to type \c T.
     552
     553      /// Reference map of the edges to type \c T.
    564554      template<class T>
    565555      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     
    567557      public:
    568558
    569         /// Constructor
    570         explicit EdgeMap(const Graph&) { }
    571         /// Constructor with given initial value
     559        ///\e
     560        EdgeMap(const Graph&) { }
     561        ///\e
    572562        EdgeMap(const Graph&, T) { }
    573 
    574563      private:
    575564        ///Copy constructor
     
    584573      };
    585574
    586       /// \brief The first node of the edge.
    587       ///
    588       /// Returns the first node of the given edge.
    589       ///
    590       /// Edges don't have source and target nodes, however methods
    591       /// u() and v() are used to query the two end-nodes of an edge.
    592       /// The orientation of an edge that arises this way is called
    593       /// the inherent direction, it is used to define the default
    594       /// direction for the corresponding arcs.
     575      /// \brief Direct the given edge.
     576      ///
     577      /// Direct the given edge. The returned arc source
     578      /// will be the given node.
     579      Arc direct(const Edge&, const Node&) const {
     580        return INVALID;
     581      }
     582
     583      /// \brief Direct the given edge.
     584      ///
     585      /// Direct the given edge. The returned arc
     586      /// represents the given edge and the direction comes
     587      /// from the bool parameter. The source of the edge and
     588      /// the directed arc is the same when the given bool is true.
     589      Arc direct(const Edge&, bool) const {
     590        return INVALID;
     591      }
     592
     593      /// \brief Returns true if the arc has default orientation.
     594      ///
     595      /// Returns whether the given directed arc is same orientation as
     596      /// the corresponding edge's default orientation.
     597      bool direction(Arc) const { return true; }
     598
     599      /// \brief Returns the opposite directed arc.
     600      ///
     601      /// Returns the opposite directed arc.
     602      Arc oppositeArc(Arc) const { return INVALID; }
     603
     604      /// \brief Opposite node on an arc
     605      ///
     606      /// \return The opposite of the given node on the given edge.
     607      Node oppositeNode(Node, Edge) const { return INVALID; }
     608
     609      /// \brief First node of the edge.
     610      ///
     611      /// \return The first node of the given edge.
     612      ///
     613      /// Naturally edges don't have direction and thus
     614      /// don't have source and target node. However we use \c u() and \c v()
     615      /// methods to query the two nodes of the arc. The direction of the
     616      /// arc which arises this way is called the inherent direction of the
     617      /// edge, and is used to define the "default" direction
     618      /// of the directed versions of the arcs.
    595619      /// \sa v()
    596620      /// \sa direction()
    597621      Node u(Edge) const { return INVALID; }
    598622
    599       /// \brief The second node of the edge.
    600       ///
    601       /// Returns the second node of the given edge.
    602       ///
    603       /// Edges don't have source and target nodes, however methods
    604       /// u() and v() are used to query the two end-nodes of an edge.
    605       /// The orientation of an edge that arises this way is called
    606       /// the inherent direction, it is used to define the default
    607       /// direction for the corresponding arcs.
     623      /// \brief Second node of the edge.
     624      ///
     625      /// \return The second node of the given edge.
     626      ///
     627      /// Naturally edges don't have direction and thus
     628      /// don't have source and target node. However we use \c u() and \c v()
     629      /// methods to query the two nodes of the arc. The direction of the
     630      /// arc which arises this way is called the inherent direction of the
     631      /// edge, and is used to define the "default" direction
     632      /// of the directed versions of the arcs.
    608633      /// \sa u()
    609634      /// \sa direction()
    610635      Node v(Edge) const { return INVALID; }
    611636
    612       /// \brief The source node of the arc.
    613       ///
    614       /// Returns the source node of the given arc.
     637      /// \brief Source node of the directed arc.
    615638      Node source(Arc) const { return INVALID; }
    616639
    617       /// \brief The target node of the arc.
    618       ///
    619       /// Returns the target node of the given arc.
     640      /// \brief Target node of the directed arc.
    620641      Node target(Arc) const { return INVALID; }
    621642
    622       /// \brief The ID of the node.
    623       ///
    624       /// Returns the ID of the given node.
     643      /// \brief Returns the id of the node.
    625644      int id(Node) const { return -1; }
    626645
    627       /// \brief The ID of the edge.
    628       ///
    629       /// Returns the ID of the given edge.
     646      /// \brief Returns the id of the edge.
    630647      int id(Edge) const { return -1; }
    631648
    632       /// \brief The ID of the arc.
    633       ///
    634       /// Returns the ID of the given arc.
     649      /// \brief Returns the id of the arc.
    635650      int id(Arc) const { return -1; }
    636651
    637       /// \brief The node with the given ID.
    638       ///
    639       /// Returns the node with the given ID.
    640       /// \pre The argument should be a valid node ID in the graph.
     652      /// \brief Returns the node with the given id.
     653      ///
     654      /// \pre The argument should be a valid node id in the graph.
    641655      Node nodeFromId(int) const { return INVALID; }
    642656
    643       /// \brief The edge with the given ID.
    644       ///
    645       /// Returns the edge with the given ID.
    646       /// \pre The argument should be a valid edge ID in the graph.
     657      /// \brief Returns the edge with the given id.
     658      ///
     659      /// \pre The argument should be a valid edge id in the graph.
    647660      Edge edgeFromId(int) const { return INVALID; }
    648661
    649       /// \brief The arc with the given ID.
    650       ///
    651       /// Returns the arc with the given ID.
    652       /// \pre The argument should be a valid arc ID in the graph.
     662      /// \brief Returns the arc with the given id.
     663      ///
     664      /// \pre The argument should be a valid arc id in the graph.
    653665      Arc arcFromId(int) const { return INVALID; }
    654666
    655       /// \brief An upper bound on the node IDs.
    656       ///
    657       /// Returns an upper bound on the node IDs.
     667      /// \brief Returns an upper bound on the node IDs.
    658668      int maxNodeId() const { return -1; }
    659669
    660       /// \brief An upper bound on the edge IDs.
    661       ///
    662       /// Returns an upper bound on the edge IDs.
     670      /// \brief Returns an upper bound on the edge IDs.
    663671      int maxEdgeId() const { return -1; }
    664672
    665       /// \brief An upper bound on the arc IDs.
    666       ///
    667       /// Returns an upper bound on the arc IDs.
     673      /// \brief Returns an upper bound on the arc IDs.
    668674      int maxArcId() const { return -1; }
    669 
    670       /// \brief The direction of the arc.
    671       ///
    672       /// Returns \c true if the direction of the given arc is the same as
    673       /// the inherent orientation of the represented edge.
    674       bool direction(Arc) const { return true; }
    675 
    676       /// \brief Direct the edge.
    677       ///
    678       /// Direct the given edge. The returned arc
    679       /// represents the given edge and its direction comes
    680       /// from the bool parameter. If it is \c true, then the direction
    681       /// of the arc is the same as the inherent orientation of the edge.
    682       Arc direct(Edge, bool) const {
    683         return INVALID;
    684       }
    685 
    686       /// \brief Direct the edge.
    687       ///
    688       /// Direct the given edge. The returned arc represents the given
    689       /// edge and its source node is the given node.
    690       Arc direct(Edge, Node) const {
    691         return INVALID;
    692       }
    693 
    694       /// \brief The oppositely directed arc.
    695       ///
    696       /// Returns the oppositely directed arc representing the same edge.
    697       Arc oppositeArc(Arc) const { return INVALID; }
    698 
    699       /// \brief The opposite node on the edge.
    700       ///
    701       /// Returns the opposite node on the given edge.
    702       Node oppositeNode(Node, Edge) const { return INVALID; }
    703675
    704676      void first(Node&) const {}
     
    734706      int maxId(Arc) const { return -1; }
    735707
    736       /// \brief The base node of the iterator.
    737       ///
    738       /// Returns the base node of the given incident edge iterator.
    739       Node baseNode(IncEdgeIt) const { return INVALID; }
    740 
    741       /// \brief The running node of the iterator.
    742       ///
    743       /// Returns the running node of the given incident edge iterator.
    744       Node runningNode(IncEdgeIt) const { return INVALID; }
    745 
    746       /// \brief The base node of the iterator.
    747       ///
    748       /// Returns the base node of the given outgoing arc iterator
    749       /// (i.e. the source node of the corresponding arc).
    750       Node baseNode(OutArcIt) const { return INVALID; }
    751 
    752       /// \brief The running node of the iterator.
    753       ///
    754       /// Returns the running node of the given outgoing arc iterator
    755       /// (i.e. the target node of the corresponding arc).
    756       Node runningNode(OutArcIt) const { return INVALID; }
    757 
    758       /// \brief The base node of the iterator.
    759       ///
    760       /// Returns the base node of the given incomming arc iterator
    761       /// (i.e. the target node of the corresponding arc).
    762       Node baseNode(InArcIt) const { return INVALID; }
    763 
    764       /// \brief The running node of the iterator.
    765       ///
    766       /// Returns the running node of the given incomming arc iterator
    767       /// (i.e. the source node of the corresponding arc).
    768       Node runningNode(InArcIt) const { return INVALID; }
     708      /// \brief Base node of the iterator
     709      ///
     710      /// Returns the base node (the source in this case) of the iterator
     711      Node baseNode(OutArcIt e) const {
     712        return source(e);
     713      }
     714      /// \brief Running node of the iterator
     715      ///
     716      /// Returns the running node (the target in this case) of the
     717      /// iterator
     718      Node runningNode(OutArcIt e) const {
     719        return target(e);
     720      }
     721
     722      /// \brief Base node of the iterator
     723      ///
     724      /// Returns the base node (the target in this case) of the iterator
     725      Node baseNode(InArcIt e) const {
     726        return target(e);
     727      }
     728      /// \brief Running node of the iterator
     729      ///
     730      /// Returns the running node (the source in this case) of the
     731      /// iterator
     732      Node runningNode(InArcIt e) const {
     733        return source(e);
     734      }
     735
     736      /// \brief Base node of the iterator
     737      ///
     738      /// Returns the base node of the iterator
     739      Node baseNode(IncEdgeIt) const {
     740        return INVALID;
     741      }
     742
     743      /// \brief Running node of the iterator
     744      ///
     745      /// Returns the running node of the iterator
     746      Node runningNode(IncEdgeIt) const {
     747        return INVALID;
     748      }
    769749
    770750      template <typename _Graph>
  • lemon/concepts/graph_components.h

    r781 r713  
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only has to define some strict ordering of
     95      /// \note This operator only have to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.
  • lemon/concepts/heap.h

    r757 r631  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_HEAP_H
    20 #define LEMON_CONCEPTS_HEAP_H
    21 
    2219///\ingroup concept
    2320///\file
    2421///\brief The concept of heaps.
    2522
     23#ifndef LEMON_CONCEPTS_HEAP_H
     24#define LEMON_CONCEPTS_HEAP_H
     25
    2626#include <lemon/core.h>
    2727#include <lemon/concept_check.h>
     
    3636    /// \brief The heap concept.
    3737    ///
    38     /// This concept class describes the main interface of heaps.
    39     /// The various \ref heaps "heap structures" are efficient
    40     /// implementations of the abstract data type \e priority \e queue.
    41     /// They store items with specified values called \e priorities
    42     /// in such a way that finding and removing the item with minimum
    43     /// priority are efficient. The basic operations are adding and
    44     /// erasing items, changing the priority of an item, etc.
     38    /// Concept class describing the main interface of heaps. A \e heap
     39    /// is a data structure for storing items with specified values called
     40    /// \e priorities in such a way that finding the item with minimum
     41    /// priority is efficient. In a heap one can change the priority of an
     42    /// item, add or erase an item, etc.
    4543    ///
    46     /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    47     /// Any class that conforms to this concept can be used easily in such
    48     /// algorithms.
    49     ///
    50     /// \tparam PR Type of the priorities of the items.
    51     /// \tparam IM A read-writable item map with \c int values, used
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
    5246    /// internally to handle the cross references.
    53     /// \tparam CMP A functor class for comparing the priorities.
     47    /// \tparam Comp A functor class for the ordering of the priorities.
    5448    /// The default is \c std::less<PR>.
    5549#ifdef DOXYGEN
    56     template <typename PR, typename IM, typename CMP>
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
    5751#else
    58     template <typename PR, typename IM, typename CMP = std::less<PR> >
     52    template <typename PR, typename IM>
    5953#endif
    6054    class Heap {
     
    7165      ///
    7266      /// Each item has a state associated to it. It can be "in heap",
    73       /// "pre-heap" or "post-heap". The latter two are indifferent from the
    74       /// heap's point of view, but may be useful to the user.
     67      /// "pre heap" or "post heap". The later two are indifferent
     68      /// from the point of view of the heap, but may be useful for
     69      /// the user.
    7570      ///
    7671      /// The item-int map must be initialized in such way that it assigns
     
    7873      enum State {
    7974        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    80         PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
    81         POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
     75        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
     76        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
    8277      };
    8378
    84       /// \brief Constructor.
    85       ///
    86       /// Constructor.
     79      /// \brief The constructor.
     80      ///
     81      /// The constructor.
    8782      /// \param map A map that assigns \c int values to keys of type
    8883      /// \c Item. It is used internally by the heap implementations to
    8984      /// handle the cross references. The assigned value must be
    90       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     85      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
    9186      explicit Heap(ItemIntMap &map) {}
    9287
    93       /// \brief Constructor.
    94       ///
    95       /// Constructor.
    96       /// \param map A map that assigns \c int values to keys of type
    97       /// \c Item. It is used internally by the heap implementations to
    98       /// handle the cross references. The assigned value must be
    99       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    100       /// \param comp The function object used for comparing the priorities.
    101       explicit Heap(ItemIntMap &map, const CMP &comp) {}
    102 
    10388      /// \brief The number of items stored in the heap.
    10489      ///
    105       /// This function returns the number of items stored in the heap.
     90      /// Returns the number of items stored in the heap.
    10691      int size() const { return 0; }
    10792
    108       /// \brief Check if the heap is empty.
    109       ///
    110       /// This function returns \c true if the heap is empty.
     93      /// \brief Checks if the heap is empty.
     94      ///
     95      /// Returns \c true if the heap is empty.
    11196      bool empty() const { return false; }
    11297
    113       /// \brief Make the heap empty.
    114       ///
    115       /// This functon makes the heap empty.
    116       /// It does not change the cross reference map. If you want to reuse
    117       /// a heap that is not surely empty, you should first clear it and
    118       /// then you should set the cross reference map to \c PRE_HEAP
    119       /// for each item.
    120       void clear() {}
    121 
    122       /// \brief Insert an item into the heap with the given priority.
    123       ///
    124       /// This function inserts the given item into the heap with the
    125       /// given priority.
     98      /// \brief Makes the heap empty.
     99      ///
     100      /// Makes the heap empty.
     101      void clear();
     102
     103      /// \brief Inserts an item into the heap with the given priority.
     104      ///
     105      /// Inserts the given item into the heap with the given priority.
    126106      /// \param i The item to insert.
    127107      /// \param p The priority of the item.
    128       /// \pre \e i must not be stored in the heap.
    129108      void push(const Item &i, const Prio &p) {}
    130109
    131       /// \brief Return the item having minimum priority.
    132       ///
    133       /// This function returns the item having minimum priority.
     110      /// \brief Returns the item having minimum priority.
     111      ///
     112      /// Returns the item having minimum priority.
    134113      /// \pre The heap must be non-empty.
    135114      Item top() const {}
     
    137116      /// \brief The minimum priority.
    138117      ///
    139       /// This function returns the minimum priority.
     118      /// Returns the minimum priority.
    140119      /// \pre The heap must be non-empty.
    141120      Prio prio() const {}
    142121
    143       /// \brief Remove the item having minimum priority.
    144       ///
    145       /// This function removes the item having minimum priority.
     122      /// \brief Removes the item having minimum priority.
     123      ///
     124      /// Removes the item having minimum priority.
    146125      /// \pre The heap must be non-empty.
    147126      void pop() {}
    148127
    149       /// \brief Remove the given item from the heap.
    150       ///
    151       /// This function removes the given item from the heap if it is
    152       /// already stored.
     128      /// \brief Removes an item from the heap.
     129      ///
     130      /// Removes the given item from the heap if it is already stored.
    153131      /// \param i The item to delete.
    154       /// \pre \e i must be in the heap.
    155132      void erase(const Item &i) {}
    156133
    157       /// \brief The priority of the given item.
    158       ///
    159       /// This function returns the priority of the given item.
    160       /// \param i The item.
    161       /// \pre \e i must be in the heap.
     134      /// \brief The priority of an item.
     135      ///
     136      /// Returns the priority of the given item.
     137      /// \param i The item.
     138      /// \pre \c i must be in the heap.
    162139      Prio operator[](const Item &i) const {}
    163140
    164       /// \brief Set the priority of an item or insert it, if it is
     141      /// \brief Sets the priority of an item or inserts it, if it is
    165142      /// not stored in the heap.
    166143      ///
    167144      /// This method sets the priority of the given item if it is
    168       /// already stored in the heap. Otherwise it inserts the given
    169       /// item into the heap with the given priority.
     145      /// already stored in the heap.
     146      /// Otherwise it inserts the given item with the given priority.
    170147      ///
    171148      /// \param i The item.
     
    173150      void set(const Item &i, const Prio &p) {}
    174151
    175       /// \brief Decrease the priority of an item to the given value.
    176       ///
    177       /// This function decreases the priority of an item to the given value.
     152      /// \brief Decreases the priority of an item to the given value.
     153      ///
     154      /// Decreases the priority of an item to the given value.
    178155      /// \param i The item.
    179156      /// \param p The priority.
    180       /// \pre \e i must be stored in the heap with priority at least \e p.
     157      /// \pre \c i must be stored in the heap with priority at least \c p.
    181158      void decrease(const Item &i, const Prio &p) {}
    182159
    183       /// \brief Increase the priority of an item to the given value.
    184       ///
    185       /// This function increases the priority of an item to the given value.
     160      /// \brief Increases the priority of an item to the given value.
     161      ///
     162      /// Increases the priority of an item to the given value.
    186163      /// \param i The item.
    187164      /// \param p The priority.
    188       /// \pre \e i must be stored in the heap with priority at most \e p.
     165      /// \pre \c i must be stored in the heap with priority at most \c p.
    189166      void increase(const Item &i, const Prio &p) {}
    190167
    191       /// \brief Return the state of an item.
     168      /// \brief Returns if an item is in, has already been in, or has
     169      /// never been in the heap.
    192170      ///
    193171      /// This method returns \c PRE_HEAP if the given item has never
     
    199177      State state(const Item &i) const {}
    200178
    201       /// \brief Set the state of an item in the heap.
    202       ///
    203       /// This function sets the state of the given item in the heap.
    204       /// It can be used to manually clear the heap when it is important
    205       /// to achive better time complexity.
     179      /// \brief Sets the state of an item in the heap.
     180      ///
     181      /// Sets the state of the given item in the heap. It can be used
     182      /// to manually clear the heap when it is important to achive the
     183      /// better time complexity.
    206184      /// \param i The item.
    207185      /// \param st The state. It should not be \c IN_HEAP.
  • lemon/concepts/maps.h

    r765 r576  
    183183      template<typename _ReferenceMap>
    184184      struct Constraints {
    185         typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
    186         constraints() {
     185        void constraints() {
    187186          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    188187          ref = m[key];
  • lemon/cplex.cc

    r793 r623  
    112112  }
    113113
    114   int CplexBase::_addRow(Value lb, ExprIterator b,
    115                          ExprIterator e, Value ub) {
    116     int i = CPXgetnumrows(cplexEnv(), _prob);
    117     if (lb == -INF) {
    118       const char s = 'L';
    119       CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
    120     } else if (ub == INF) {
    121       const char s = 'G';
    122       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
    123     } else if (lb == ub){
    124       const char s = 'E';
    125       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
    126     } else {
    127       const char s = 'R';
    128       double len = ub - lb;
    129       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
    130     }
    131 
    132     std::vector<int> indices;
    133     std::vector<int> rowlist;
    134     std::vector<Value> values;
    135 
    136     for(ExprIterator it=b; it!=e; ++it) {
    137       indices.push_back(it->first);
    138       values.push_back(it->second);
    139       rowlist.push_back(i);
    140     }
    141 
    142     CPXchgcoeflist(cplexEnv(), _prob, values.size(),
    143                    &rowlist.front(), &indices.front(), &values.front());
    144 
    145     return i;
    146   }
    147114
    148115  void CplexBase::_eraseCol(int i) {
  • lemon/cplex.h

    r793 r623  
    9494    virtual int _addCol();
    9595    virtual int _addRow();
    96     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    9796
    9897    virtual void _eraseCol(int i);
  • lemon/dfs.h

    r764 r631  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
     
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a \c ProcessedMap.
     
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8685    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8786    ///Instantiates a \c ReachedMap.
     
    9897
    9998    ///The type of the map that stores the distances of the nodes.
    100     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    101100    typedef typename Digraph::template NodeMap<int> DistMap;
    102101    ///Instantiates a \c DistMap.
     
    226225    ///\ref named-templ-param "Named parameter" for setting
    227226    ///\c PredMap type.
    228     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    229228    template <class T>
    230229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    246245    ///\ref named-templ-param "Named parameter" for setting
    247246    ///\c DistMap type.
    248     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    249248    template <class T>
    250249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    266265    ///\ref named-templ-param "Named parameter" for setting
    267266    ///\c ReachedMap type.
    268     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269268    template <class T>
    270269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    286285    ///\ref named-templ-param "Named parameter" for setting
    287286    ///\c ProcessedMap type.
    288     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    289288    template <class T>
    290289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    413412    ///The simplest way to execute the DFS algorithm is to use one of the
    414413    ///member functions called \ref run(Node) "run()".\n
    415     ///If you need better control on the execution, you have to call
    416     ///\ref init() first, then you can add a source node with \ref addSource()
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
    417416    ///and perform the actual computation with \ref start().
    418417    ///This procedure can be repeated if there are nodes that have not
     
    671670    ///@{
    672671
    673     ///The DFS path to the given node.
    674 
    675     ///Returns the DFS path to the given node from the root(s).
     672    ///The DFS path to a node.
     673
     674    ///Returns the DFS path to a node.
    676675    ///
    677676    ///\warning \c t should be reached from the root(s).
     
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    683     ///The distance of the given node from the root(s).
    684 
    685     ///Returns the distance of the given node from the root(s).
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
    686685    ///
    687686    ///\warning If node \c v is not reached from the root(s), then
     
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
    694     ///Returns the 'previous arc' of the %DFS tree for the given node.
     693    ///Returns the 'previous arc' of the %DFS tree for a node.
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
     
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702     ///\ref predNode() and \ref predMap().
     701    ///\ref predNode().
    703702    ///
    704703    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
    708     ///Returns the 'previous node' of the %DFS tree for the given node.
     707    ///Returns the 'previous node' of the %DFS tree.
    709708
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///of a %DFS path from a root to \c v. It is \c INVALID
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
    713712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716     ///\ref predArc() and \ref predMap().
     715    ///\ref predArc().
    717716    ///
    718717    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    735734    ///
    736735    ///Returns a const reference to the node map that stores the predecessor
    737     ///arcs, which form the DFS tree (forest).
     736    ///arcs, which form the DFS tree.
    738737    ///
    739738    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    743     ///Checks if the given node. node is reached from the root(s).
     742    ///Checks if a node is reached from the root(s).
    744743
    745744    ///Returns \c true if \c v is reached from the root(s).
     
    767766    ///The type of the map that stores the predecessor
    768767    ///arcs of the %DFS paths.
    769     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     768    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    770769    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    771770    ///Instantiates a PredMap.
     
    782781
    783782    ///The type of the map that indicates which nodes are processed.
    784     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     783    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    785784    ///By default it is a NullMap.
    786785    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    802801
    803802    ///The type of the map that indicates which nodes are reached.
    804     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     803    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    805804    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    806805    ///Instantiates a ReachedMap.
     
    817816
    818817    ///The type of the map that stores the distances of the nodes.
    819     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     818    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    820819    typedef typename Digraph::template NodeMap<int> DistMap;
    821820    ///Instantiates a DistMap.
     
    832831
    833832    ///The type of the DFS paths.
    834     ///It must conform to the \ref concepts::Path "Path" concept.
     833    ///It must meet the \ref concepts::Path "Path" concept.
    835834    typedef lemon::Path<Digraph> Path;
    836835  };
     
    838837  /// Default traits class used by DfsWizard
    839838
    840   /// Default traits class used by DfsWizard.
    841   /// \tparam GR The type of the digraph.
     839  /// To make it easier to use Dfs algorithm
     840  /// we have created a wizard class.
     841  /// This \ref DfsWizard class needs default traits,
     842  /// as well as the \ref Dfs class.
     843  /// The \ref DfsWizardBase is a class to be the default traits of the
     844  /// \ref DfsWizard class.
    842845  template<class GR>
    843846  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    867870    /// Constructor.
    868871
    869     /// This constructor does not require parameters, it initiates
     872    /// This constructor does not require parameters, therefore it initiates
    870873    /// all of the attributes to \c 0.
    871874    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    897900    typedef TR Base;
    898901
     902    ///The type of the digraph the algorithm runs on.
    899903    typedef typename TR::Digraph Digraph;
    900904
     
    904908    typedef typename Digraph::OutArcIt OutArcIt;
    905909
     910    ///\brief The type of the map that stores the predecessor
     911    ///arcs of the DFS paths.
    906912    typedef typename TR::PredMap PredMap;
     913    ///\brief The type of the map that stores the distances of the nodes.
    907914    typedef typename TR::DistMap DistMap;
     915    ///\brief The type of the map that indicates which nodes are reached.
    908916    typedef typename TR::ReachedMap ReachedMap;
     917    ///\brief The type of the map that indicates which nodes are processed.
    909918    typedef typename TR::ProcessedMap ProcessedMap;
     919    ///The type of the DFS paths
    910920    typedef typename TR::Path Path;
    911921
     
    9901000      SetPredMapBase(const TR &b) : TR(b) {}
    9911001    };
    992 
    993     ///\brief \ref named-templ-param "Named parameter" for setting
    994     ///the predecessor map.
    995     ///
    996     ///\ref named-templ-param "Named parameter" function for setting
    997     ///the map that stores the predecessor arcs of the nodes.
     1002    ///\brief \ref named-func-param "Named parameter"
     1003    ///for setting PredMap object.
     1004    ///
     1005    ///\ref named-func-param "Named parameter"
     1006    ///for setting PredMap object.
    9981007    template<class T>
    9991008    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10091018      SetReachedMapBase(const TR &b) : TR(b) {}
    10101019    };
    1011 
    1012     ///\brief \ref named-templ-param "Named parameter" for setting
    1013     ///the reached map.
    1014     ///
    1015     ///\ref named-templ-param "Named parameter" function for setting
    1016     ///the map that indicates which nodes are reached.
     1020    ///\brief \ref named-func-param "Named parameter"
     1021    ///for setting ReachedMap object.
     1022    ///
     1023    /// \ref named-func-param "Named parameter"
     1024    ///for setting ReachedMap object.
    10171025    template<class T>
    10181026    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10281036      SetDistMapBase(const TR &b) : TR(b) {}
    10291037    };
    1030 
    1031     ///\brief \ref named-templ-param "Named parameter" for setting
    1032     ///the distance map.
    1033     ///
    1034     ///\ref named-templ-param "Named parameter" function for setting
    1035     ///the map that stores the distances of the nodes calculated
    1036     ///by the algorithm.
     1038    ///\brief \ref named-func-param "Named parameter"
     1039    ///for setting DistMap object.
     1040    ///
     1041    /// \ref named-func-param "Named parameter"
     1042    ///for setting DistMap object.
    10371043    template<class T>
    10381044    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10481054      SetProcessedMapBase(const TR &b) : TR(b) {}
    10491055    };
    1050 
    1051     ///\brief \ref named-func-param "Named parameter" for setting
    1052     ///the processed map.
    1053     ///
    1054     ///\ref named-templ-param "Named parameter" function for setting
    1055     ///the map that indicates which nodes are processed.
     1056    ///\brief \ref named-func-param "Named parameter"
     1057    ///for setting ProcessedMap object.
     1058    ///
     1059    /// \ref named-func-param "Named parameter"
     1060    ///for setting ProcessedMap object.
    10561061    template<class T>
    10571062    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12041209    ///
    12051210    /// The type of the map that indicates which nodes are reached.
    1206     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1211    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12071212    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12081213
     
    13651370    /// The simplest way to execute the DFS algorithm is to use one of the
    13661371    /// member functions called \ref run(Node) "run()".\n
    1367     /// If you need better control on the execution, you have to call
    1368     /// \ref init() first, then you can add a source node with \ref addSource()
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
    13691374    /// and perform the actual computation with \ref start().
    13701375    /// This procedure can be repeated if there are nodes that have not
     
    16161621    ///@{
    16171622
    1618     /// \brief Checks if the given node is reached from the root(s).
     1623    /// \brief Checks if a node is reached from the root(s).
    16191624    ///
    16201625    /// Returns \c true if \c v is reached from the root(s).
  • lemon/dijkstra.h

    r764 r631  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the arc lengths.
     75    ///The type of the length of the arcs.
    7676    typedef typename LEN::Value Value;
    7777
     
    117117    ///The type of the map that stores the predecessor
    118118    ///arcs of the shortest paths.
    119     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    120120    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    121121    ///Instantiates a \c PredMap.
     
    132132
    133133    ///The type of the map that indicates which nodes are processed.
    134     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    135135    ///By default it is a NullMap.
    136136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    152152
    153153    ///The type of the map that stores the distances of the nodes.
    154     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    155155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    156156    ///Instantiates a \c DistMap.
     
    169169  /// \ingroup shortest_path
    170170  ///This class provides an efficient implementation of the %Dijkstra algorithm.
    171   ///
    172   ///The %Dijkstra algorithm solves the single-source shortest path problem
    173   ///when all arc lengths are non-negative. If there are negative lengths,
    174   ///the BellmanFord algorithm should be used instead.
    175171  ///
    176172  ///The arc lengths are passed to the algorithm using a
     
    206202    typedef typename TR::Digraph Digraph;
    207203
    208     ///The type of the arc lengths.
     204    ///The type of the length of the arcs.
    209205    typedef typename TR::LengthMap::Value Value;
    210206    ///The type of the map that stores the arc lengths.
     
    309305    ///\ref named-templ-param "Named parameter" for setting
    310306    ///\c PredMap type.
    311     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     307    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    312308    template <class T>
    313309    struct SetPredMap
     
    330326    ///\ref named-templ-param "Named parameter" for setting
    331327    ///\c DistMap type.
    332     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     328    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    333329    template <class T>
    334330    struct SetDistMap
     
    351347    ///\ref named-templ-param "Named parameter" for setting
    352348    ///\c ProcessedMap type.
    353     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     349    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    354350    template <class T>
    355351    struct SetProcessedMap
     
    448444    ///\ref named-templ-param "Named parameter" for setting
    449445    ///\c OperationTraits type.
    450     /// For more information see \ref DijkstraDefaultOperationTraits.
    451446    template <class T>
    452447    struct SetOperationTraits
     
    590585    ///The simplest way to execute the %Dijkstra algorithm is to use
    591586    ///one of the member functions called \ref run(Node) "run()".\n
    592     ///If you need better control on the execution, you have to call
    593     ///\ref init() first, then you can add several source nodes with
     587    ///If you need more control on the execution, first you have to call
     588    ///\ref init(), then you can add several source nodes with
    594589    ///\ref addSource(). Finally the actual path computation can be
    595590    ///performed with one of the \ref start() functions.
     
    807802    ///The results of the %Dijkstra algorithm can be obtained using these
    808803    ///functions.\n
    809     ///Either \ref run(Node) "run()" or \ref init() should be called
     804    ///Either \ref run(Node) "run()" or \ref start() should be called
    810805    ///before using them.
    811806
    812807    ///@{
    813808
    814     ///The shortest path to the given node.
    815 
    816     ///Returns the shortest path to the given node from the root(s).
     809    ///The shortest path to a node.
     810
     811    ///Returns the shortest path to a node.
    817812    ///
    818813    ///\warning \c t should be reached from the root(s).
     
    822817    Path path(Node t) const { return Path(*G, *_pred, t); }
    823818
    824     ///The distance of the given node from the root(s).
    825 
    826     ///Returns the distance of the given node from the root(s).
     819    ///The distance of a node from the root(s).
     820
     821    ///Returns the distance of a node from the root(s).
    827822    ///
    828823    ///\warning If node \c v is not reached from the root(s), then
     
    833828    Value dist(Node v) const { return (*_dist)[v]; }
    834829
    835     ///\brief Returns the 'previous arc' of the shortest path tree for
    836     ///the given node.
    837     ///
     830    ///Returns the 'previous arc' of the shortest path tree for a node.
     831
    838832    ///This function returns the 'previous arc' of the shortest path
    839833    ///tree for the node \c v, i.e. it returns the last arc of a
     
    842836    ///
    843837    ///The shortest path tree used here is equal to the shortest path
    844     ///tree used in \ref predNode() and \ref predMap().
     838    ///tree used in \ref predNode().
    845839    ///
    846840    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    848842    Arc predArc(Node v) const { return (*_pred)[v]; }
    849843
    850     ///\brief Returns the 'previous node' of the shortest path tree for
    851     ///the given node.
    852     ///
     844    ///Returns the 'previous node' of the shortest path tree for a node.
     845
    853846    ///This function returns the 'previous node' of the shortest path
    854847    ///tree for the node \c v, i.e. it returns the last but one node
    855     ///of a shortest path from a root to \c v. It is \c INVALID
     848    ///from a shortest path from a root to \c v. It is \c INVALID
    856849    ///if \c v is not reached from the root(s) or if \c v is a root.
    857850    ///
    858851    ///The shortest path tree used here is equal to the shortest path
    859     ///tree used in \ref predArc() and \ref predMap().
     852    ///tree used in \ref predArc().
    860853    ///
    861854    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    878871    ///
    879872    ///Returns a const reference to the node map that stores the predecessor
    880     ///arcs, which form the shortest path tree (forest).
     873    ///arcs, which form the shortest path tree.
    881874    ///
    882875    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    884877    const PredMap &predMap() const { return *_pred;}
    885878
    886     ///Checks if the given node is reached from the root(s).
     879    ///Checks if a node is reached from the root(s).
    887880
    888881    ///Returns \c true if \c v is reached from the root(s).
     
    903896                                          Heap::POST_HEAP; }
    904897
    905     ///The current distance of the given node from the root(s).
    906 
    907     ///Returns the current distance of the given node from the root(s).
     898    ///The current distance of a node from the root(s).
     899
     900    ///Returns the current distance of a node from the root(s).
    908901    ///It may be decreased in the following processes.
    909902    ///
     
    932925
    933926    ///The type of the map that stores the arc lengths.
    934     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    935928    typedef LEN LengthMap;
    936     ///The type of the arc lengths.
     929    ///The type of the length of the arcs.
    937930    typedef typename LEN::Value Value;
    938931
     
    981974    ///The type of the map that stores the predecessor
    982975    ///arcs of the shortest paths.
    983     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     976    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    984977    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    985978    ///Instantiates a PredMap.
     
    996989
    997990    ///The type of the map that indicates which nodes are processed.
    998     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     991    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    999992    ///By default it is a NullMap.
    1000993    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    10161009
    10171010    ///The type of the map that stores the distances of the nodes.
    1018     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     1011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10191012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10201013    ///Instantiates a DistMap.
     
    10311024
    10321025    ///The type of the shortest paths.
    1033     ///It must conform to the \ref concepts::Path "Path" concept.
     1026    ///It must meet the \ref concepts::Path "Path" concept.
    10341027    typedef lemon::Path<Digraph> Path;
    10351028  };
     
    10371030  /// Default traits class used by DijkstraWizard
    10381031
    1039   /// Default traits class used by DijkstraWizard.
    1040   /// \tparam GR The type of the digraph.
    1041   /// \tparam LEN The type of the length map.
     1032  /// To make it easier to use Dijkstra algorithm
     1033  /// we have created a wizard class.
     1034  /// This \ref DijkstraWizard class needs default traits,
     1035  /// as well as the \ref Dijkstra class.
     1036  /// The \ref DijkstraWizardBase is a class to be the default traits of the
     1037  /// \ref DijkstraWizard class.
    10421038  template<typename GR, typename LEN>
    10431039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
     
    10981094    typedef TR Base;
    10991095
     1096    ///The type of the digraph the algorithm runs on.
    11001097    typedef typename TR::Digraph Digraph;
    11011098
     
    11051102    typedef typename Digraph::OutArcIt OutArcIt;
    11061103
     1104    ///The type of the map that stores the arc lengths.
    11071105    typedef typename TR::LengthMap LengthMap;
     1106    ///The type of the length of the arcs.
    11081107    typedef typename LengthMap::Value Value;
     1108    ///\brief The type of the map that stores the predecessor
     1109    ///arcs of the shortest paths.
    11091110    typedef typename TR::PredMap PredMap;
     1111    ///The type of the map that stores the distances of the nodes.
    11101112    typedef typename TR::DistMap DistMap;
     1113    ///The type of the map that indicates which nodes are processed.
    11111114    typedef typename TR::ProcessedMap ProcessedMap;
     1115    ///The type of the shortest paths
    11121116    typedef typename TR::Path Path;
     1117    ///The heap type used by the dijkstra algorithm.
    11131118    typedef typename TR::Heap Heap;
    11141119
     
    11821187      SetPredMapBase(const TR &b) : TR(b) {}
    11831188    };
    1184 
    1185     ///\brief \ref named-templ-param "Named parameter" for setting
    1186     ///the predecessor map.
    1187     ///
    1188     ///\ref named-templ-param "Named parameter" function for setting
    1189     ///the map that stores the predecessor arcs of the nodes.
     1189    ///\brief \ref named-func-param "Named parameter"
     1190    ///for setting PredMap object.
     1191    ///
     1192    ///\ref named-func-param "Named parameter"
     1193    ///for setting PredMap object.
    11901194    template<class T>
    11911195    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
     
    12011205      SetDistMapBase(const TR &b) : TR(b) {}
    12021206    };
    1203 
    1204     ///\brief \ref named-templ-param "Named parameter" for setting
    1205     ///the distance map.
    1206     ///
    1207     ///\ref named-templ-param "Named parameter" function for setting
    1208     ///the map that stores the distances of the nodes calculated
    1209     ///by the algorithm.
     1207    ///\brief \ref named-func-param "Named parameter"
     1208    ///for setting DistMap object.
     1209    ///
     1210    ///\ref named-func-param "Named parameter"
     1211    ///for setting DistMap object.
    12101212    template<class T>
    12111213    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     
    12211223      SetProcessedMapBase(const TR &b) : TR(b) {}
    12221224    };
    1223 
    1224     ///\brief \ref named-func-param "Named parameter" for setting
    1225     ///the processed map.
    1226     ///
    1227     ///\ref named-templ-param "Named parameter" function for setting
    1228     ///the map that indicates which nodes are processed.
     1225    ///\brief \ref named-func-param "Named parameter"
     1226    ///for setting ProcessedMap object.
     1227    ///
     1228    /// \ref named-func-param "Named parameter"
     1229    ///for setting ProcessedMap object.
    12291230    template<class T>
    12301231    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12391240      SetPathBase(const TR &b) : TR(b) {}
    12401241    };
    1241 
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.
  • lemon/dim2.h

    r761 r463  
    2222#include <iostream>
    2323
    24 ///\ingroup geomdat
     24///\ingroup misc
    2525///\file
    2626///\brief A simple two dimensional vector and a bounding box implementation
     27///
     28/// The class \ref lemon::dim2::Point "dim2::Point" implements
     29/// a two dimensional vector with the usual operations.
     30///
     31/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
     32/// the rectangular bounding box of a set of
     33/// \ref lemon::dim2::Point "dim2::Point"'s.
    2734
    2835namespace lemon {
     
    3441  namespace dim2 {
    3542
    36   /// \addtogroup geomdat
     43  /// \addtogroup misc
    3744  /// @{
    3845
  • lemon/fib_heap.h

    r758 r730  
    2121
    2222///\file
    23 ///\ingroup heaps
    24 ///\brief Fibonacci heap implementation.
     23///\ingroup auxdat
     24///\brief Fibonacci Heap implementation.
    2525
    2626#include <vector>
    27 #include <utility>
    2827#include <functional>
    2928#include <lemon/math.h>
     
    3130namespace lemon {
    3231
    33   /// \ingroup heaps
     32  /// \ingroup auxdat
    3433  ///
    35   /// \brief Fibonacci heap data structure.
     34  ///\brief Fibonacci Heap.
    3635  ///
    37   /// This class implements the \e Fibonacci \e heap data structure.
    38   /// It fully conforms to the \ref concepts::Heap "heap concept".
     36  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
     37  ///is a data structure for storing items with specified values called \e
     38  ///priorities in such a way that finding the item with minimum priority is
     39  ///efficient. \c CMP specifies the ordering of the priorities. In a heap
     40  ///one can change the priority of an item, add or erase an item, etc.
    3941  ///
    40   /// The methods \ref increase() and \ref erase() are not efficient in a
    41   /// Fibonacci heap. In case of many calls of these operations, it is
    42   /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
     42  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
     43  ///heap. In case of many calls to these operations, it is better to use a
     44  ///\ref BinHeap "binary heap".
    4345  ///
    44   /// \tparam PR Type of the priorities of the items.
    45   /// \tparam IM A read-writable item map with \c int values, used
    46   /// internally to handle the cross references.
    47   /// \tparam CMP A functor class for comparing the priorities.
    48   /// The default is \c std::less<PR>.
     46  ///\param PRIO Type of the priority of the items.
     47  ///\param IM A read and writable Item int map, used internally
     48  ///to handle the cross references.
     49  ///\param CMP A class for the ordering of the priorities. The
     50  ///default is \c std::less<PRIO>.
     51  ///
     52  ///\sa BinHeap
     53  ///\sa Dijkstra
    4954#ifdef DOXYGEN
    50   template <typename PR, typename IM, typename CMP>
     55  template <typename PRIO, typename IM, typename CMP>
    5156#else
    52   template <typename PR, typename IM, typename CMP = std::less<PR> >
     57  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
    5358#endif
    5459  class FibHeap {
    5560  public:
    56 
    57     /// Type of the item-int map.
     61    ///\e
    5862    typedef IM ItemIntMap;
    59     /// Type of the priorities.
    60     typedef PR Prio;
    61     /// Type of the items stored in the heap.
     63    ///\e
     64    typedef PRIO Prio;
     65    ///\e
    6266    typedef typename ItemIntMap::Key Item;
    63     /// Type of the item-priority pairs.
     67    ///\e
    6468    typedef std::pair<Item,Prio> Pair;
    65     /// Functor type for comparing the priorities.
     69    ///\e
    6670    typedef CMP Compare;
    6771
     
    7781  public:
    7882
    79     /// \brief Type to represent the states of the items.
    80     ///
    81     /// Each item has a state associated to it. It can be "in heap",
    82     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     83    /// \brief Type to represent the items states.
     84    ///
     85    /// Each Item element have a state associated to it. It may be "in heap",
     86    /// "pre heap" or "post heap". The latter two are indifferent from the
    8387    /// heap's point of view, but may be useful to the user.
    8488    ///
     
    9195    };
    9296
    93     /// \brief Constructor.
    94     ///
    95     /// Constructor.
    96     /// \param map A map that assigns \c int values to the items.
    97     /// It is used internally to handle the cross references.
    98     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     97    /// \brief The constructor
     98    ///
     99    /// \c map should be given to the constructor, since it is
     100    ///   used internally to handle the cross references.
    99101    explicit FibHeap(ItemIntMap &map)
    100102      : _minimum(0), _iim(map), _num() {}
    101103
    102     /// \brief Constructor.
    103     ///
    104     /// Constructor.
    105     /// \param map A map that assigns \c int values to the items.
    106     /// It is used internally to handle the cross references.
    107     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    108     /// \param comp The function object used for comparing the priorities.
     104    /// \brief The constructor
     105    ///
     106    /// \c map should be given to the constructor, since it is used
     107    /// internally to handle the cross references. \c comp is an
     108    /// object for ordering of the priorities.
    109109    FibHeap(ItemIntMap &map, const Compare &comp)
    110110      : _minimum(0), _iim(map), _comp(comp), _num() {}
     
    112112    /// \brief The number of items stored in the heap.
    113113    ///
    114     /// This function returns the number of items stored in the heap.
     114    /// Returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Check if the heap is empty.
    118     ///
    119     /// This function returns \c true if the heap is empty.
     117    /// \brief Checks if the heap stores no items.
     118    ///
     119    ///   Returns \c true if and only if the heap stores no items.
    120120    bool empty() const { return _num==0; }
    121121
    122     /// \brief Make the heap empty.
    123     ///
    124     /// This functon makes the heap empty.
    125     /// It does not change the cross reference map. If you want to reuse
    126     /// a heap that is not surely empty, you should first clear it and
    127     /// then you should set the cross reference map to \c PRE_HEAP
    128     /// for each item.
     122    /// \brief Make empty this heap.
     123    ///
     124    /// Make empty this heap. It does not change the cross reference
     125    /// map.  If you want to reuse a heap what is not surely empty you
     126    /// should first clear the heap and after that you should set the
     127    /// cross reference map for each item to \c PRE_HEAP.
    129128    void clear() {
    130129      _data.clear(); _minimum = 0; _num = 0;
    131130    }
    132131
    133     /// \brief Insert an item into the heap with the given priority.
    134     ///
    135     /// This function inserts the given item into the heap with the
    136     /// given priority.
    137     /// \param item The item to insert.
    138     /// \param prio The priority of the item.
    139     /// \pre \e item must not be stored in the heap.
    140     void push (const Item& item, const Prio& prio) {
     132    /// \brief \c item gets to the heap with priority \c value independently
     133    /// if \c item was already there.
     134    ///
     135    /// This method calls \ref push(\c item, \c value) if \c item is not
     136    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
     137    /// \ref increase(\c item, \c value) otherwise.
     138    void set (const Item& item, const Prio& value) {
     139      int i=_iim[item];
     140      if ( i >= 0 && _data[i].in ) {
     141        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     142        if ( _comp(_data[i].prio, value) ) increase(item, value);
     143      } else push(item, value);
     144    }
     145
     146    /// \brief Adds \c item to the heap with priority \c value.
     147    ///
     148    /// Adds \c item to the heap with priority \c value.
     149    /// \pre \c item must not be stored in the heap.
     150    void push (const Item& item, const Prio& value) {
    141151      int i=_iim[item];
    142152      if ( i < 0 ) {
     
    159169        _data[_minimum].right_neighbor=i;
    160170        _data[i].left_neighbor=_minimum;
    161         if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
     171        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
    162172      } else {
    163173        _data[i].right_neighbor=_data[i].left_neighbor=i;
    164174        _minimum=i;
    165175      }
    166       _data[i].prio=prio;
     176      _data[i].prio=value;
    167177      ++_num;
    168178    }
    169179
    170     /// \brief Return the item having minimum priority.
    171     ///
    172     /// This function returns the item having minimum priority.
    173     /// \pre The heap must be non-empty.
     180    /// \brief Returns the item with minimum priority relative to \c Compare.
     181    ///
     182    /// This method returns the item with minimum priority relative to \c
     183    /// Compare.
     184    /// \pre The heap must be nonempty.
    174185    Item top() const { return _data[_minimum].name; }
    175186
    176     /// \brief The minimum priority.
    177     ///
    178     /// This function returns the minimum priority.
    179     /// \pre The heap must be non-empty.
    180     Prio prio() const { return _data[_minimum].prio; }
    181 
    182     /// \brief Remove the item having minimum priority.
    183     ///
    184     /// This function removes the item having minimum priority.
     187    /// \brief Returns the minimum priority relative to \c Compare.
     188    ///
     189    /// It returns the minimum priority relative to \c Compare.
     190    /// \pre The heap must be nonempty.
     191    const Prio& prio() const { return _data[_minimum].prio; }
     192
     193    /// \brief Returns the priority of \c item.
     194    ///
     195    /// It returns the priority of \c item.
     196    /// \pre \c item must be in the heap.
     197    const Prio& operator[](const Item& item) const {
     198      return _data[_iim[item]].prio;
     199    }
     200
     201    /// \brief Deletes the item with minimum priority relative to \c Compare.
     202    ///
     203    /// This method deletes the item with minimum priority relative to \c
     204    /// Compare from the heap.
    185205    /// \pre The heap must be non-empty.
    186206    void pop() {
     
    189209        _data[_minimum].in=false;
    190210        if ( _data[_minimum].degree!=0 ) {
    191           makeRoot(_data[_minimum].child);
     211          makeroot(_data[_minimum].child);
    192212          _minimum=_data[_minimum].child;
    193213          balance();
     
    202222          int last_child=_data[child].left_neighbor;
    203223
    204           makeRoot(child);
     224          makeroot(child);
    205225
    206226          _data[left].right_neighbor=child;
     
    215235    }
    216236
    217     /// \brief Remove the given item from the heap.
    218     ///
    219     /// This function removes the given item from the heap if it is
    220     /// already stored.
    221     /// \param item The item to delete.
    222     /// \pre \e item must be in the heap.
     237    /// \brief Deletes \c item from the heap.
     238    ///
     239    /// This method deletes \c item from the heap, if \c item was already
     240    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    223241    void erase (const Item& item) {
    224242      int i=_iim[item];
     
    235253    }
    236254
    237     /// \brief The priority of the given item.
    238     ///
    239     /// This function returns the priority of the given item.
    240     /// \param item The item.
    241     /// \pre \e item must be in the heap.
    242     Prio operator[](const Item& item) const {
    243       return _data[_iim[item]].prio;
    244     }
    245 
    246     /// \brief Set the priority of an item or insert it, if it is
    247     /// not stored in the heap.
    248     ///
    249     /// This method sets the priority of the given item if it is
    250     /// already stored in the heap. Otherwise it inserts the given
    251     /// item into the heap with the given priority.
    252     /// \param item The item.
    253     /// \param prio The priority.
    254     void set (const Item& item, const Prio& prio) {
     255    /// \brief Decreases the priority of \c item to \c value.
     256    ///
     257    /// This method decreases the priority of \c item to \c value.
     258    /// \pre \c item must be stored in the heap with priority at least \c
     259    ///   value relative to \c Compare.
     260    void decrease (Item item, const Prio& value) {
    255261      int i=_iim[item];
    256       if ( i >= 0 && _data[i].in ) {
    257         if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
    258         if ( _comp(_data[i].prio, prio) ) increase(item, prio);
    259       } else push(item, prio);
    260     }
    261 
    262     /// \brief Decrease the priority of an item to the given value.
    263     ///
    264     /// This function decreases the priority of an item to the given value.
    265     /// \param item The item.
    266     /// \param prio The priority.
    267     /// \pre \e item must be stored in the heap with priority at least \e prio.
    268     void decrease (const Item& item, const Prio& prio) {
    269       int i=_iim[item];
    270       _data[i].prio=prio;
     262      _data[i].prio=value;
    271263      int p=_data[i].parent;
    272264
    273       if ( p!=-1 && _comp(prio, _data[p].prio) ) {
     265      if ( p!=-1 && _comp(value, _data[p].prio) ) {
    274266        cut(i,p);
    275267        cascade(p);
    276268      }
    277       if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
    278     }
    279 
    280     /// \brief Increase the priority of an item to the given value.
    281     ///
    282     /// This function increases the priority of an item to the given value.
    283     /// \param item The item.
    284     /// \param prio The priority.
    285     /// \pre \e item must be stored in the heap with priority at most \e prio.
    286     void increase (const Item& item, const Prio& prio) {
     269      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
     270    }
     271
     272    /// \brief Increases the priority of \c item to \c value.
     273    ///
     274    /// This method sets the priority of \c item to \c value. Though
     275    /// there is no precondition on the priority of \c item, this
     276    /// method should be used only if it is indeed necessary to increase
     277    /// (relative to \c Compare) the priority of \c item, because this
     278    /// method is inefficient.
     279    void increase (Item item, const Prio& value) {
    287280      erase(item);
    288       push(item, prio);
    289     }
    290 
    291     /// \brief Return the state of an item.
    292     ///
    293     /// This method returns \c PRE_HEAP if the given item has never
    294     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    295     /// and \c POST_HEAP otherwise.
    296     /// In the latter case it is possible that the item will get back
    297     /// to the heap again.
    298     /// \param item The item.
     281      push(item, value);
     282    }
     283
     284
     285    /// \brief Returns if \c item is in, has already been in, or has never
     286    /// been in the heap.
     287    ///
     288    /// This method returns PRE_HEAP if \c item has never been in the
     289    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     290    /// otherwise. In the latter case it is possible that \c item will
     291    /// get back to the heap again.
    299292    State state(const Item &item) const {
    300293      int i=_iim[item];
     
    306299    }
    307300
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     301    /// \brief Sets the state of the \c item in the heap.
     302    ///
     303    /// Sets the state of the \c item in the heap. It can be used to
     304    /// manually clear the heap when it is important to achive the
     305    /// better time _complexity.
    313306    /// \param i The item.
    314307    /// \param st The state. It should not be \c IN_HEAP.
     
    373366    }
    374367
    375     void makeRoot(int c) {
     368    void makeroot(int c) {
    376369      int s=c;
    377370      do {
  • lemon/full_graph.h

    r827 r825  
    2525///\ingroup graphs
    2626///\file
    27 ///\brief FullDigraph and FullGraph classes.
     27///\brief FullGraph and FullDigraph classes.
    2828
    2929namespace lemon {
     
    149149  /// \ingroup graphs
    150150  ///
    151   /// \brief A directed full graph class.
    152   ///
    153   /// FullDigraph is a simple and fast implmenetation of directed full
    154   /// (complete) graphs. It contains an arc from each node to each node
    155   /// (including a loop for each node), therefore the number of arcs
    156   /// is the square of the number of nodes.
    157   /// This class is completely static and it needs constant memory space.
    158   /// Thus you can neither add nor delete nodes or arcs, however
    159   /// the structure can be resized using resize().
    160   ///
    161   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
    162   /// Most of its member functions and nested classes are documented
    163   /// only in the concept class.
    164   ///
    165   /// \note FullDigraph and FullGraph classes are very similar,
     151  /// \brief A full digraph class.
     152  ///
     153  /// This is a simple and fast directed full graph implementation.
     154  /// From each node go arcs to each node (including the source node),
     155  /// therefore the number of the arcs in the digraph is the square of
     156  /// the node number. This digraph type is completely static, so you
     157  /// can neither add nor delete either arcs or nodes, and it needs
     158  /// constant space in memory.
     159  ///
     160  /// This class fully conforms to the \ref concepts::Digraph
     161  /// "Digraph concept".
     162  ///
     163  /// The \c FullDigraph and \c FullGraph classes are very similar,
    166164  /// but there are two differences. While this class conforms only
    167   /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
    168   /// conforms to the \ref concepts::Graph "Graph" concept,
    169   /// moreover FullGraph does not contain a loop for each
    170   /// node as this class does.
     165  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
     166  /// class conforms to the \ref concepts::Graph "Graph" concept,
     167  /// moreover \c FullGraph does not contain a loop arc for each
     168  /// node as \c FullDigraph does.
    171169  ///
    172170  /// \sa FullGraph
     
    176174  public:
    177175
    178     /// \brief Default constructor.
    179     ///
    180     /// Default constructor. The number of nodes and arcs will be zero.
     176    /// \brief Constructor
    181177    FullDigraph() { construct(0); }
    182178
     
    189185    /// \brief Resizes the digraph
    190186    ///
    191     /// This function resizes the digraph. It fully destroys and
    192     /// rebuilds the structure, therefore the maps of the digraph will be
     187    /// Resizes the digraph. The function will fully destroy and
     188    /// rebuild the digraph. This cause that the maps of the digraph will
    193189    /// reallocated automatically and the previous values will be lost.
    194190    void resize(int n) {
     
    202198    /// \brief Returns the node with the given index.
    203199    ///
    204     /// Returns the node with the given index. Since this structure is
    205     /// completely static, the nodes can be indexed with integers from
    206     /// the range <tt>[0..nodeNum()-1]</tt>.
     200    /// Returns the node with the given index. Since it is a static
     201    /// digraph its nodes can be indexed with integers from the range
     202    /// <tt>[0..nodeNum()-1]</tt>.
    207203    /// \sa index()
    208204    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    210206    /// \brief Returns the index of the given node.
    211207    ///
    212     /// Returns the index of the given node. Since this structure is
    213     /// completely static, the nodes can be indexed with integers from
    214     /// the range <tt>[0..nodeNum()-1]</tt>.
    215     /// \sa operator()()
     208    /// Returns the index of the given node. Since it is a static
     209    /// digraph its nodes can be indexed with integers from the range
     210    /// <tt>[0..nodeNum()-1]</tt>.
     211    /// \sa operator()
    216212    static int index(const Node& node) { return Parent::index(node); }
    217213
     
    219215    ///
    220216    /// Returns the arc connecting the given nodes.
    221     Arc arc(Node u, Node v) const {
     217    Arc arc(const Node& u, const Node& v) const {
    222218      return Parent::arc(u, v);
    223219    }
     
    525521  /// \brief An undirected full graph class.
    526522  ///
    527   /// FullGraph is a simple and fast implmenetation of undirected full
    528   /// (complete) graphs. It contains an edge between every distinct pair
    529   /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
    530   /// This class is completely static and it needs constant memory space.
    531   /// Thus you can neither add nor delete nodes or edges, however
    532   /// the structure can be resized using resize().
    533   ///
    534   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
    535   /// Most of its member functions and nested classes are documented
    536   /// only in the concept class.
    537   ///
    538   /// \note FullDigraph and FullGraph classes are very similar,
    539   /// but there are two differences. While FullDigraph
     523  /// This is a simple and fast undirected full graph
     524  /// implementation. From each node go edge to each other node,
     525  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
     526  /// This graph type is completely static, so you can neither
     527  /// add nor delete either edges or nodes, and it needs constant
     528  /// space in memory.
     529  ///
     530  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
     531  ///
     532  /// The \c FullGraph and \c FullDigraph classes are very similar,
     533  /// but there are two differences. While the \c FullDigraph class
    540534  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    541535  /// this class conforms to the \ref concepts::Graph "Graph" concept,
    542   /// moreover this class does not contain a loop for each
    543   /// node as FullDigraph does.
     536  /// moreover \c FullGraph does not contain a loop arc for each
     537  /// node as \c FullDigraph does.
    544538  ///
    545539  /// \sa FullDigraph
     
    549543  public:
    550544
    551     /// \brief Default constructor.
    552     ///
    553     /// Default constructor. The number of nodes and edges will be zero.
     545    /// \brief Constructor
    554546    FullGraph() { construct(0); }
    555547
     
    562554    /// \brief Resizes the graph
    563555    ///
    564     /// This function resizes the graph. It fully destroys and
    565     /// rebuilds the structure, therefore the maps of the graph will be
     556    /// Resizes the graph. The function will fully destroy and
     557    /// rebuild the graph. This cause that the maps of the graph will
    566558    /// reallocated automatically and the previous values will be lost.
    567559    void resize(int n) {
     
    577569    /// \brief Returns the node with the given index.
    578570    ///
    579     /// Returns the node with the given index. Since this structure is
    580     /// completely static, the nodes can be indexed with integers from
    581     /// the range <tt>[0..nodeNum()-1]</tt>.
     571    /// Returns the node with the given index. Since it is a static
     572    /// graph its nodes can be indexed with integers from the range
     573    /// <tt>[0..nodeNum()-1]</tt>.
    582574    /// \sa index()
    583575    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    585577    /// \brief Returns the index of the given node.
    586578    ///
    587     /// Returns the index of the given node. Since this structure is
    588     /// completely static, the nodes can be indexed with integers from
    589     /// the range <tt>[0..nodeNum()-1]</tt>.
    590     /// \sa operator()()
     579    /// Returns the index of the given node. Since it is a static
     580    /// graph its nodes can be indexed with integers from the range
     581    /// <tt>[0..nodeNum()-1]</tt>.
     582    /// \sa operator()
    591583    static int index(const Node& node) { return Parent::index(node); }
    592584
     
    594586    ///
    595587    /// Returns the arc connecting the given nodes.
    596     Arc arc(Node s, Node t) const {
     588    Arc arc(const Node& s, const Node& t) const {
    597589      return Parent::arc(s, t);
    598590    }
    599591
    600     /// \brief Returns the edge connecting the given nodes.
    601     ///
    602     /// Returns the edge connecting the given nodes.
    603     Edge edge(Node u, Node v) const {
     592    /// \brief Returns the edge connects the given nodes.
     593    ///
     594    /// Returns the edge connects the given nodes.
     595    Edge edge(const Node& u, const Node& v) const {
    604596      return Parent::edge(u, v);
    605597    }
  • lemon/glpk.cc

    r793 r623  
    5757    int i = glp_add_rows(lp, 1);
    5858    glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
    59     return i;
    60   }
    61 
    62   int GlpkBase::_addRow(Value lo, ExprIterator b,
    63                         ExprIterator e, Value up) {
    64     int i = glp_add_rows(lp, 1);
    65 
    66     if (lo == -INF) {
    67       if (up == INF) {
    68         glp_set_row_bnds(lp, i, GLP_FR, lo, up);
    69       } else {
    70         glp_set_row_bnds(lp, i, GLP_UP, lo, up);
    71       }   
    72     } else {
    73       if (up == INF) {
    74         glp_set_row_bnds(lp, i, GLP_LO, lo, up);
    75       } else if (lo != up) {       
    76         glp_set_row_bnds(lp, i, GLP_DB, lo, up);
    77       } else {
    78         glp_set_row_bnds(lp, i, GLP_FX, lo, up);
    79       }
    80     }
    81 
    82     std::vector<int> indexes;
    83     std::vector<Value> values;
    84 
    85     indexes.push_back(0);
    86     values.push_back(0);
    87 
    88     for(ExprIterator it = b; it != e; ++it) {
    89       indexes.push_back(it->first);
    90       values.push_back(it->second);
    91     }
    92 
    93     glp_set_mat_row(lp, i, values.size() - 1,
    94                     &indexes.front(), &values.front());
    9559    return i;
    9660  }
  • lemon/glpk.h

    r793 r697  
    5555    virtual int _addCol();
    5656    virtual int _addRow();
    57     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    5857
    5958    virtual void _eraseCol(int i);
  • lemon/gomory_hu.h

    r760 r643  
    360360    /// \c t.
    361361    /// \code
    362     /// GomoryHu<Graph> gom(g, capacities);
     362    /// GomoruHu<Graph> gom(g, capacities);
    363363    /// gom.run();
    364364    /// int cnt=0;
    365     /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
     365    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    366366    /// \endcode
    367367    class MinCutNodeIt
     
    457457    /// \c t.
    458458    /// \code
    459     /// GomoryHu<Graph> gom(g, capacities);
     459    /// GomoruHu<Graph> gom(g, capacities);
    460460    /// gom.run();
    461461    /// int value=0;
    462     /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
     462    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    463463    ///   value+=capacities[e];
    464464    /// \endcode
  • lemon/grid_graph.h

    r782 r664  
    471471  /// \brief Grid graph class
    472472  ///
    473   /// GridGraph implements a special graph type. The nodes of the
    474   /// graph can be indexed by two integer values \c (i,j) where \c i is
    475   /// in the range <tt>[0..width()-1]</tt> and j is in the range
    476   /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
    477   /// the indices differ exactly on one position and the difference is
    478   /// also exactly one. The nodes of the graph can be obtained by position
    479   /// using the \c operator()() function and the indices of the nodes can
    480   /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
     473  /// This class implements a special graph type. The nodes of the
     474  /// graph can be indexed by two integer \c (i,j) value where \c i is
     475  /// in the \c [0..width()-1] range and j is in the \c
     476  /// [0..height()-1] range. Two nodes are connected in the graph if
     477  /// the indexes differ exactly on one position and exactly one is
     478  /// the difference. The nodes of the graph can be indexed by position
     479  /// with the \c operator()() function. The positions of the nodes can be
     480  /// get with \c pos(), \c col() and \c row() members. The outgoing
    481481  /// arcs can be retrieved with the \c right(), \c up(), \c left()
    482482  /// and \c down() functions, where the bottom-left corner is the
    483483  /// origin.
    484   ///
    485   /// This class is completely static and it needs constant memory space.
    486   /// Thus you can neither add nor delete nodes or edges, however
    487   /// the structure can be resized using resize().
    488484  ///
    489485  /// \image html grid_graph.png
     
    501497  ///\endcode
    502498  ///
    503   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
    504   /// Most of its member functions and nested classes are documented
    505   /// only in the concept class.
     499  /// This graph type fully conforms to the \ref concepts::Graph
     500  /// "Graph concept".
    506501  class GridGraph : public ExtendedGridGraphBase {
    507502    typedef ExtendedGridGraphBase Parent;
     
    509504  public:
    510505
    511     /// \brief Map to get the indices of the nodes as \ref dim2::Point
    512     /// "dim2::Point<int>".
    513     ///
    514     /// Map to get the indices of the nodes as \ref dim2::Point
    515     /// "dim2::Point<int>".
     506    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
     507    ///
     508    /// Map to get the indices of the nodes as dim2::Point<int>.
    516509    class IndexMap {
    517510    public:
     
    522515
    523516      /// \brief Constructor
     517      ///
     518      /// Constructor
    524519      IndexMap(const GridGraph& graph) : _graph(graph) {}
    525520
    526521      /// \brief The subscript operator
     522      ///
     523      /// The subscript operator.
    527524      Value operator[](Key key) const {
    528525        return _graph.pos(key);
     
    544541
    545542      /// \brief Constructor
     543      ///
     544      /// Constructor
    546545      ColMap(const GridGraph& graph) : _graph(graph) {}
    547546
    548547      /// \brief The subscript operator
     548      ///
     549      /// The subscript operator.
    549550      Value operator[](Key key) const {
    550551        return _graph.col(key);
     
    566567
    567568      /// \brief Constructor
     569      ///
     570      /// Constructor
    568571      RowMap(const GridGraph& graph) : _graph(graph) {}
    569572
    570573      /// \brief The subscript operator
     574      ///
     575      /// The subscript operator.
    571576      Value operator[](Key key) const {
    572577        return _graph.row(key);
     
    579584    /// \brief Constructor
    580585    ///
    581     /// Construct a grid graph with the given size.