COIN-OR::LEMON - Graph Library

Changes in / [769:e746fb14e680:770:432c54cec63c] in lemon-1.2


Ignore:
Files:
9 added
65 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r680 r744  
    3535CHECK_TYPE_SIZE("long long" LONG_LONG)
    3636SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
     37
     38INCLUDE(FindPythonInterp)
    3739
    3840ENABLE_TESTING()
  • Makefile.am

    r629 r752  
    1818        cmake/FindGLPK.cmake \
    1919        cmake/FindCOIN.cmake \
     20        cmake/LEMONConfig.cmake.in \
    2021        cmake/version.cmake.in \
    2122        cmake/version.cmake \
  • configure.ac

    r680 r744  
    4242
    4343AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     44AC_CHECK_PROG([python_found],[python],[yes],[no])
    4445AC_CHECK_PROG([gs_found],[gs],[yes],[no])
    4546
  • doc/CMakeLists.txt

    r679 r744  
    1010)
    1111
    12 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
     12IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND 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
    3132    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
    3233    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
  • doc/Doxyfile.in

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

    r673 r744  
    6767        fi
    6868
    69 html-local: $(DOC_PNG_IMAGES)
     69references.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
     81html-local: $(DOC_PNG_IMAGES) references.dox
    7082        if test ${doxygen_found} = yes; then \
    7183          cd doc; \
  • doc/groups.dox

    r768 r770  
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    247239any kind of path structure.
    248240
    249 \sa lemon::concepts::Path
     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
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used 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
     270This group contains two dimensional data storages implemented in LEMON.
    250271*/
    251272
     
    260281
    261282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This 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
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    262305@defgroup algs Algorithms
    263306\brief This group contains the several algorithms
     
    274317
    275318This group contains the common graph search algorithms, namely
    276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    277321*/
    278322
     
    282326\brief Algorithms for finding shortest paths.
    283327
    284 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    285330
    286331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    299344
    300345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \ref clrs01algorithms.
     352*/
     353
     354/**
    301355@defgroup max_flow Maximum Flow Algorithms
    302356@ingroup algs
     
    304358
    305359This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307361
    308362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    319373
    320374LEMON contains several algorithms for solving maximum flow problems:
    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 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
     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
     384In most cases the \ref Preflow algorithm provides the
    327385fastest method for computing a maximum flow. All implementations
    328386also provide functions to query the minimum cut, which is the dual
     
    342400
    343401This group contains the algorithms for finding minimum cost flows and
    344 circulations. For more information about this problem and its dual
    345 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
    346405
    347406LEMON contains several algorithms for this problem.
    348407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    350409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    352412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
     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.
    356418
    357419In general NetworkSimplex is the most efficient implementation,
     
    376438
    377439\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     440    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379441
    380442LEMON contains several algorithms related to minimum cut problems:
     
    423485O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    424486applied early termination scheme.
    425 */
    426 
    427 /**
    428 @defgroup graph_properties Connectivity and Other Graph Properties
    429 @ingroup algs
    430 \brief Algorithms for discovering the graph properties
    431 
    432 This group contains the algorithms for discovering the graph properties
    433 like connectivity, bipartiteness, euler property, simplicity etc.
    434 
    435 \image html edge_biconnected_components.png
    436 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    437 */
    438 
    439 /**
    440 @defgroup planar Planarity Embedding and Drawing
    441 @ingroup algs
    442 \brief Algorithms for planarity checking, embedding and drawing
    443 
    444 This group contains the algorithms for planarity checking,
    445 embedding and drawing.
    446 
    447 \image html planar.png
    448 \image latex planar.eps "Plane graph" width=\textwidth
    449487*/
    450488
     
    490528
    491529/**
    492 @defgroup spantree Minimum Spanning Tree Algorithms
    493 @ingroup algs
    494 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    495 
    496 This group contains the algorithms for finding minimum cost spanning
    497 trees and arborescences.
     530@defgroup graph_properties Connectivity and Other Graph Properties
     531@ingroup algs
     532\brief Algorithms for discovering the graph properties
     533
     534This group contains the algorithms for discovering the graph properties
     535like connectivity, bipartiteness, euler property, simplicity etc.
     536
     537\image html connected_components.png
     538\image latex connected_components.eps "Connected components" width=\textwidth
     539*/
     540
     541/**
     542@defgroup planar Planarity Embedding and Drawing
     543@ingroup algs
     544\brief Algorithms for planarity checking, embedding and drawing
     545
     546This group contains the algorithms for planarity checking,
     547embedding and drawing.
     548
     549\image html planar.png
     550\image latex planar.eps "Plane graph" width=\textwidth
     551*/
     552
     553/**
     554@defgroup approx Approximation Algorithms
     555@ingroup algs
     556\brief Approximation algorithms.
     557
     558This group contains the approximation and heuristic algorithms
     559implemented in LEMON.
    498560*/
    499561
     
    505567This group contains some algorithms implemented in LEMON
    506568in order to make it easier to implement complex algorithms.
    507 */
    508 
    509 /**
    510 @defgroup approx Approximation Algorithms
    511 @ingroup algs
    512 \brief Approximation algorithms.
    513 
    514 This group contains the approximation and heuristic algorithms
    515 implemented in LEMON.
    516569*/
    517570
     
    526579
    527580/**
    528 @defgroup lp_group Lp and Mip Solvers
     581@defgroup lp_group LP and MIP Solvers
    529582@ingroup gen_opt_group
    530 \brief Lp and Mip solver interfaces for LEMON.
    531 
    532 This group contains Lp and Mip solver interfaces for LEMON. The
    533 various LP solvers could be used in the same manner with this
    534 interface.
     583\brief LP and MIP solver interfaces for LEMON.
     584
     585This group contains LP and MIP solver interfaces for LEMON.
     586Various LP solvers could be used in the same manner with this
     587high-level interface.
     588
     589The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     590\ref cplex, \ref soplex.
    535591*/
    536592
     
    622678
    623679/**
    624 @defgroup dimacs_group DIMACS format
     680@defgroup dimacs_group DIMACS Format
    625681@ingroup io_group
    626682\brief Read and write files in DIMACS format
     
    671727\brief Skeleton and concept checking classes for graph structures
    672728
    673 This group contains the skeletons and concept checking classes of LEMON's
    674 graph structures and helper classes used to implement these.
     729This group contains the skeletons and concept checking classes of
     730graph structures.
    675731*/
    676732
     
    684740
    685741/**
     742@defgroup tools Standalone Utility Applications
     743
     744Some utility applications are listed here.
     745
     746The standard compilation procedure (<tt>./configure;make</tt>) will compile
     747them, as well.
     748*/
     749
     750/**
    686751\anchor demoprograms
    687752
     
    695760*/
    696761
    697 /**
    698 @defgroup tools Standalone Utility Applications
    699 
    700 Some utility applications are listed here.
    701 
    702 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    703 them, as well.
    704 */
    705 
    706762}
  • doc/mainpage.dox

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

    r663 r755  
    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.
     29and arc costs \ref amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • lemon/Makefile.am

    r766 r770  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
     63        lemon/binom_heap.h \
    6264        lemon/bucket_heap.h \
    6365        lemon/cbc.h \
     
    7981        lemon/euler.h \
    8082        lemon/fib_heap.h \
     83        lemon/fourary_heap.h \
    8184        lemon/full_graph.h \
    8285        lemon/glpk.h \
     
    8891        lemon/hypercube_graph.h \
    8992        lemon/karp.h \
     93        lemon/kary_heap.h \
    9094        lemon/kruskal.h \
    9195        lemon/hao_orlin.h \
     
    96100        lemon/lp_base.h \
    97101        lemon/lp_skeleton.h \
    98         lemon/list_graph.h \
    99102        lemon/maps.h \
    100103        lemon/matching.h \
     
    103106        lemon/nauty_reader.h \
    104107        lemon/network_simplex.h \
     108        lemon/pairing_heap.h \
    105109        lemon/path.h \
    106110        lemon/preflow.h \
  • lemon/bfs.h

    r492 r717  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8687    ///Instantiates a \c ReachedMap.
     
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101102    ///Instantiates a \c DistMap.
     
    226227    ///\ref named-templ-param "Named parameter" for setting
    227228    ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     229    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229230    template <class T>
    230231    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    246247    ///\ref named-templ-param "Named parameter" for setting
    247248    ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     249    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249250    template <class T>
    250251    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266267    ///\ref named-templ-param "Named parameter" for setting
    267268    ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     269    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269270    template <class T>
    270271    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    286287    ///\ref named-templ-param "Named parameter" for setting
    287288    ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     289    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289290    template <class T>
    290291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    414415    ///The simplest way to execute the BFS algorithm is to use one of the
    415416    ///member functions called \ref run(Node) "run()".\n
    416     ///If you need more control on the execution, first you have to call
    417     ///\ref init(), then you can add several source nodes with
     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
    418419    ///\ref addSource(). Finally the actual path computation can be
    419420    ///performed with one of the \ref start() functions.
     
    738739    ///@{
    739740
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     741    ///The shortest path to the given node.
     742
     743    ///Returns the shortest path to the given node from the root(s).
    743744    ///
    744745    ///\warning \c t should be reached from the root(s).
     
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     751    ///The distance of the given node from the root(s).
     752
     753    ///Returns the distance of the given node from the root(s).
    753754    ///
    754755    ///\warning If node \c v is not reached from the root(s), then
     
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     762    ///\brief Returns the 'previous arc' of the shortest path tree for
     763    ///the given node.
     764    ///
    763765    ///This function returns the 'previous arc' of the shortest path
    764766    ///tree for the node \c v, i.e. it returns the last arc of a
     
    767769    ///
    768770    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     771    ///tree used in \ref predNode() and \ref predMap().
    770772    ///
    771773    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    773775    Arc predArc(Node v) const { return (*_pred)[v];}
    774776
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     777    ///\brief Returns the 'previous node' of the shortest path tree for
     778    ///the given node.
     779    ///
    777780    ///This function returns the 'previous node' of the shortest path
    778781    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     782    ///of a shortest path from a root to \c v. It is \c INVALID
    780783    ///if \c v is not reached from the root(s) or if \c v is a root.
    781784    ///
    782785    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     786    ///tree used in \ref predArc() and \ref predMap().
    784787    ///
    785788    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    802805    ///
    803806    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     807    ///arcs, which form the shortest path tree (forest).
    805808    ///
    806809    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808811    const PredMap &predMap() const { return *_pred;}
    809812
    810     ///Checks if a node is reached from the root(s).
     813    ///Checks if the given node is reached from the root(s).
    811814
    812815    ///Returns \c true if \c v is reached from the root(s).
     
    834837    ///The type of the map that stores the predecessor
    835838    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     839    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837840    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838841    ///Instantiates a PredMap.
     
    849852
    850853    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     854    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    852855    ///By default it is a NullMap.
    853856    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    869872
    870873    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     874    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872875    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873876    ///Instantiates a ReachedMap.
     
    884887
    885888    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     889    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887890    typedef typename Digraph::template NodeMap<int> DistMap;
    888891    ///Instantiates a DistMap.
     
    899902
    900903    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     904    ///It must conform to the \ref concepts::Path "Path" concept.
    902905    typedef lemon::Path<Digraph> Path;
    903906  };
     
    905908  /// Default traits class used by BfsWizard
    906909
    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.
     910  /// Default traits class used by BfsWizard.
     911  /// \tparam GR The type of the digraph.
    913912  template<class GR>
    914913  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    938937    /// Constructor.
    939938
    940     /// This constructor does not require parameters, therefore it initiates
     939    /// This constructor does not require parameters, it initiates
    941940    /// all of the attributes to \c 0.
    942941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    968967    typedef TR Base;
    969968
    970     ///The type of the digraph the algorithm runs on.
    971969    typedef typename TR::Digraph Digraph;
    972970
     
    976974    typedef typename Digraph::OutArcIt OutArcIt;
    977975
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980976    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982977    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984978    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986979    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988980    typedef typename TR::Path Path;
    989981
     
    10681060      SetPredMapBase(const TR &b) : TR(b) {}
    10691061    };
    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.
     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.
    10751068    template<class T>
    10761069    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861079      SetReachedMapBase(const TR &b) : TR(b) {}
    10871080    };
    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.
     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.
    10931087    template<class T>
    10941088    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11041098      SetDistMapBase(const TR &b) : TR(b) {}
    11051099    };
    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.
     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.
    11111107    template<class T>
    11121108    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11221118      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231119    };
    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.
     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.
    11291126    template<class T>
    11301127    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12651262    ///
    12661263    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1264    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681265    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691266
     
    14261423    /// The simplest way to execute the BFS algorithm is to use one of the
    14271424    /// member functions called \ref run(Node) "run()".\n
    1428     /// If you need more control on the execution, first you have to call
    1429     /// \ref init(), then you can add several source nodes with
     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
    14301427    /// \ref addSource(). Finally the actual path computation can be
    14311428    /// performed with one of the \ref start() functions.
     
    17361733    ///@{
    17371734
    1738     /// \brief Checks if a node is reached from the root(s).
     1735    /// \brief Checks if the given node is reached from the root(s).
    17391736    ///
    17401737    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r683 r711  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure.
     36  /// This class implements the \e binary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3738  ///
    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
     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
    5247  template <typename PR, typename IM, typename CMP = std::less<PR> >
     48#endif
    5349  class BinHeap {
    54 
    5550  public:
    56     ///\e
     51
     52    /// Type of the item-int map.
    5753    typedef IM ItemIntMap;
    58     ///\e
     54    /// Type of the priorities.
    5955    typedef PR Prio;
    60     ///\e
     56    /// Type of the items stored in the heap.
    6157    typedef typename ItemIntMap::Key Item;
    62     ///\e
     58    /// Type of the item-priority pairs.
    6359    typedef std::pair<Item,Prio> Pair;
    64     ///\e
     60    /// Functor type for comparing the priorities.
    6561    typedef CMP Compare;
    6662
    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
     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
    7167    /// heap's point of view, but may be useful to the user.
    7268    ///
     
    8581
    8682  public:
    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.
     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.
    9390    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9491
    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.
     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.
    10399    BinHeap(ItemIntMap &map, const Compare &comp)
    104100      : _iim(map), _comp(comp) {}
    105101
    106102
    107     /// The number of items stored in the heap.
    108     ///
    109     /// \brief Returns the number of items stored in the heap.
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
    110106    int size() const { return _data.size(); }
    111107
    112     /// \brief Checks if the heap stores no items.
    113     ///
    114     /// Returns \c true if and only if the heap stores no items.
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
    115111    bool empty() const { return _data.empty(); }
    116112
    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.
     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.
    123120    void clear() {
    124121      _data.clear();
     
    128125    static int parent(int i) { return (i-1)/2; }
    129126
    130     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    131128    bool less(const Pair &p1, const Pair &p2) const {
    132129      return _comp(p1.second, p2.second);
    133130    }
    134131
    135     int bubble_up(int hole, Pair p) {
     132    int bubbleUp(int hole, Pair p) {
    136133      int par = parent(hole);
    137134      while( hole>0 && less(p,_data[par]) ) {
     
    144141    }
    145142
    146     int bubble_down(int hole, Pair p, int length) {
    147       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    148145      while(child < length) {
    149146        if( less(_data[child-1], _data[child]) ) {
     
    154151        move(_data[child], hole);
    155152        hole = child;
    156         child = second_child(hole);
     153        child = secondChild(hole);
    157154      }
    158155      child--;
     
    172169
    173170  public:
     171
    174172    /// \brief Insert a pair of item and priority into the heap.
    175173    ///
    176     /// Adds \c p.first to the heap with priority \c p.second.
     174    /// This function inserts \c p.first to the heap with priority
     175    /// \c p.second.
    177176    /// \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       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.
     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.
    187188    /// \param i The item to insert.
    188189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    189191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    190192
    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.
     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.
    196197    Item top() const {
    197198      return _data[0].first;
    198199    }
    199200
    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.
     201    /// \brief The minimum priority.
     202    ///
     203    /// This function returns the minimum priority.
     204    /// \pre The heap must be non-empty.
    204205    Prio prio() const {
    205206      return _data[0].second;
    206207    }
    207208
    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.
     209    /// \brief Remove the item having minimum priority.
     210    ///
     211    /// This function removes the item having minimum priority.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubble_down(0, _data[n], n);
     217        bubbleDown(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    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.
     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.
    227228    void erase(const Item &i) {
    228229      int h = _iim[i];
     
    230231      _iim.set(_data[h].first, POST_HEAP);
    231232      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    234235        }
    235236      }
     
    237238    }
    238239
    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.
     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.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
     
    248248    }
    249249
    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.
     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.
    255256    /// \param i The item.
    256257    /// \param p The priority.
     
    261262      }
    262263      else if( _comp(p, _data[idx].second) ) {
    263         bubble_up(idx, Pair(i,p));
     264        bubbleUp(idx, Pair(i,p));
    264265      }
    265266      else {
    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.
     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.
    273274    /// \param i The item.
    274275    /// \param p The priority.
    275     /// \pre \c i must be stored in the heap with priority at least \c
    276     /// p relative to \c Compare.
     276    /// \pre \e i must be stored in the heap with priority at least \e p.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubble_up(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increases the priority of \c i to \c p.
    283     ///
    284     /// This method sets the priority of item \c i to \c p.
     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.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \c i must be stored in the heap with priority at most \c
    288     /// p relative to \c Compare.
     287    /// \pre \e i must be stored in the heap with priority at most \e p.
    289288    void increase(const Item &i, const Prio &p) {
    290289      int idx = _iim[i];
    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.
     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.
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
     
    307306    }
    308307
    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.
     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.
    314313    /// \param i The item.
    315314    /// \param st The state. It should not be \c IN_HEAP.
     
    328327    }
    329328
    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.
     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.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
  • lemon/bits/edge_set_extender.h

    r617 r685  
    538538
    539539    public:
    540       ArcMap(const Graph& _g)
     540      explicit ArcMap(const Graph& _g)
    541541        : Parent(_g) {}
    542542      ArcMap(const Graph& _g, const _Value& _v)
     
    562562
    563563    public:
    564       EdgeMap(const Graph& _g)
     564      explicit EdgeMap(const Graph& _g)
    565565        : Parent(_g) {}
    566566
  • lemon/bits/graph_extender.h

    r617 r685  
    605605
    606606    public:
    607       NodeMap(const Graph& graph)
     607      explicit NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
     
    629629
    630630    public:
    631       ArcMap(const Graph& graph)
     631      explicit ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
     
    653653
    654654    public:
    655       EdgeMap(const Graph& graph)
     655      explicit EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657
  • lemon/bits/map_extender.h

    r617 r718  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
     
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
  • lemon/bucket_heap.h

    r683 r711  
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Bucket Heap implementation.
     24///\brief Bucket heap implementation.
    2525
    2626#include <vector>
     
    5454  }
    5555
    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.
     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
    7378  template <typename IM, bool MIN = true>
    7479  class BucketHeap {
    7580
    7681  public:
    77     /// \e
    78     typedef typename IM::Key Item;
    79     /// \e
     82
     83    /// Type of the item-int map.
     84    typedef IM ItemIntMap;
     85    /// Type of the priorities.
    8086    typedef int Prio;
    81     /// \e
    82     typedef std::pair<Item, Prio> Pair;
    83     /// \e
    84     typedef IM ItemIntMap;
     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;
    8591
    8692  private:
     
    9096  public:
    9197
    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
     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
    96102    /// heap's point of view, but may be useful to the user.
    97103    ///
     
    105111
    106112  public:
    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.
     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.
    113120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    114121
    115     /// The number of items stored in the heap.
    116     ///
    117     /// \brief Returns the number of items stored in the heap.
     122    /// \brief The number of items stored in the heap.
     123    ///
     124    /// This function returns the number of items stored in the heap.
    118125    int size() const { return _data.size(); }
    119126
    120     /// \brief Checks if the heap stores no items.
    121     ///
    122     /// Returns \c true if and only if the heap stores no items.
     127    /// \brief Check if the heap is empty.
     128    ///
     129    /// This function returns \c true if the heap is empty.
    123130    bool empty() const { return _data.empty(); }
    124131
    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.
     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.
    131139    void clear() {
    132140      _data.clear(); _first.clear(); _minimum = 0;
     
    135143  private:
    136144
    137     void relocate_last(int idx) {
     145    void relocateLast(int idx) {
    138146      if (idx + 1 < int(_data.size())) {
    139147        _data[idx] = _data.back();
     
    175183
    176184  public:
     185
    177186    /// \brief Insert a pair of item and priority into the heap.
    178187    ///
    179     /// Adds \c p.first to the heap with priority \c p.second.
     188    /// This function inserts \c p.first to the heap with priority
     189    /// \c p.second.
    180190    /// \param p The pair to insert.
     191    /// \pre \c p.first must not be stored in the heap.
    181192    void push(const Pair& p) {
    182193      push(p.first, p.second);
     
    185196    /// \brief Insert an item into the heap with the given priority.
    186197    ///
    187     /// Adds \c i to the heap with priority \c p.
     198    /// This function inserts the given item into the heap with the
     199    /// given priority.
    188200    /// \param i The item to insert.
    189201    /// \param p The priority of the item.
     202    /// \pre \e i must not be stored in the heap.
    190203    void push(const Item &i, const Prio &p) {
    191204      int idx = _data.size();
     
    198211    }
    199212
    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.
     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.
    204217    Item top() const {
    205218      while (_first[_minimum] == -1) {
     
    209222    }
    210223
    211     /// \brief Returns the minimum priority.
    212     ///
    213     /// It returns the minimum priority.
    214     /// \pre The heap must be nonempty.
     224    /// \brief The minimum priority.
     225    ///
     226    /// This function returns the minimum priority.
     227    /// \pre The heap must be non-empty.
    215228    Prio prio() const {
    216229      while (_first[_minimum] == -1) {
     
    220233    }
    221234
    222     /// \brief Deletes the item with minimum priority.
    223     ///
    224     /// This method deletes the item with minimum priority from the heap.
     235    /// \brief Remove the item having minimum priority.
     236    ///
     237    /// This function removes the item having minimum priority.
    225238    /// \pre The heap must be non-empty.
    226239    void pop() {
     
    231244      _iim[_data[idx].item] = -2;
    232245      unlace(idx);
    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.
     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.
    241255    void erase(const Item &i) {
    242256      int idx = _iim[i];
    243257      _iim[_data[idx].item] = -2;
    244258      unlace(idx);
    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.
     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.
    254267    Prio operator[](const Item &i) const {
    255268      int idx = _iim[i];
     
    257270    }
    258271
    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.
     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.
    264278    /// \param i The item.
    265279    /// \param p The priority.
     
    275289    }
    276290
    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.
     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.
    282294    /// \param i The item.
    283295    /// \param p The priority.
     296    /// \pre \e i must be stored in the heap with priority at least \e p.
    284297    void decrease(const Item &i, const Prio &p) {
    285298      int idx = _iim[i];
     
    292305    }
    293306
    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.
     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.
    299310    /// \param i The item.
    300311    /// \param p The priority.
     312    /// \pre \e i must be stored in the heap with priority at most \e p.
    301313    void increase(const Item &i, const Prio &p) {
    302314      int idx = _iim[i];
     
    306318    }
    307319
    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.
     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.
    315327    /// \param i The item.
    316328    State state(const Item &i) const {
     
    320332    }
    321333
    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.
     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.
    327339    /// \param i The item.
    328340    /// \param st The state. It should not be \c IN_HEAP.
     
    360372  }; // class BucketHeap
    361373
    362   /// \ingroup auxdat
    363   ///
    364   /// \brief A Simplified Bucket Heap implementation.
     374  /// \ingroup heaps
     375  ///
     376  /// \brief Simplified bucket heap data structure.
    365377  ///
    366378  /// This class implements a simplified \e bucket \e heap data
    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.
     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.
    379397  ///
    380398  /// \sa BucketHeap
     
    383401
    384402  public:
    385     typedef typename IM::Key Item;
     403
     404    /// Type of the item-int map.
     405    typedef IM ItemIntMap;
     406    /// Type of the priorities.
    386407    typedef int Prio;
    387     typedef std::pair<Item, Prio> Pair;
    388     typedef IM ItemIntMap;
     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;
    389412
    390413  private:
     
    394417  public:
    395418
    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
     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
    400423    /// heap's point of view, but may be useful to the user.
    401424    ///
     
    410433  public:
    411434
    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.
     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.
    418441    explicit SimpleBucketHeap(ItemIntMap &map)
    419442      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    420443
    421     /// \brief Returns the number of items stored in the heap.
    422     ///
    423     /// The number of items stored in the heap.
     444    /// \brief The number of items stored in the heap.
     445    ///
     446    /// This function returns the number of items stored in the heap.
    424447    int size() const { return _num; }
    425448
    426     /// \brief Checks if the heap stores no items.
    427     ///
    428     /// Returns \c true if and only if the heap stores no items.
     449    /// \brief Check if the heap is empty.
     450    ///
     451    /// This function returns \c true if the heap is empty.
    429452    bool empty() const { return _num == 0; }
    430453
    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.
     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.
    437461    void clear() {
    438462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
     
    441465    /// \brief Insert a pair of item and priority into the heap.
    442466    ///
    443     /// Adds \c p.first to the heap with priority \c p.second.
     467    /// This function inserts \c p.first to the heap with priority
     468    /// \c p.second.
    444469    /// \param p The pair to insert.
     470    /// \pre \c p.first must not be stored in the heap.
    445471    void push(const Pair& p) {
    446472      push(p.first, p.second);
     
    449475    /// \brief Insert an item into the heap with the given priority.
    450476    ///
    451     /// Adds \c i to the heap with priority \c p.
     477    /// This function inserts the given item into the heap with the
     478    /// given priority.
    452479    /// \param i The item to insert.
    453480    /// \param p The priority of the item.
     481    /// \pre \e i must not be stored in the heap.
    454482    void push(const Item &i, const Prio &p) {
    455483      int idx;
     
    472500    }
    473501
    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.
     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.
    478506    Item top() const {
    479507      while (_first[_minimum] == -1) {
     
    483511    }
    484512
    485     /// \brief Returns the minimum priority.
    486     ///
    487     /// It returns the minimum priority.
    488     /// \pre The heap must be nonempty.
     513    /// \brief The minimum priority.
     514    ///
     515    /// This function returns the minimum priority.
     516    /// \pre The heap must be non-empty.
    489517    Prio prio() const {
    490518      while (_first[_minimum] == -1) {
     
    494522    }
    495523
    496     /// \brief Deletes the item with minimum priority.
    497     ///
    498     /// This method deletes the item with minimum priority from the heap.
     524    /// \brief Remove the item having minimum priority.
     525    ///
     526    /// This function removes the item having minimum priority.
    499527    /// \pre The heap must be non-empty.
    500528    void pop() {
     
    510538    }
    511539
    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.
     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.
    520547    Prio operator[](const Item &i) const {
    521       for (int k = 0; k < _first.size(); ++k) {
     548      for (int k = 0; k < int(_first.size()); ++k) {
    522549        int idx = _first[k];
    523550        while (idx != -1) {
     
    531558    }
    532559
    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.
     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.
    540567    /// \param i The item.
    541568    State state(const Item &i) const {
  • lemon/cbc.cc

    r576 r746  
    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  }
    97109
    98110  void CbcMip::_eraseCol(int i) {
  • lemon/cbc.h

    r576 r746  
    6363    virtual int _addCol();
    6464    virtual int _addRow();
     65    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    6566
    6667    virtual void _eraseCol(int i);
  • lemon/circulation.h

    r641 r715  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
     75#ifdef DOXYGEN
     76    typedef GR::ArcMap<Value> FlowMap;
     77#else
    7578    typedef typename Digraph::template ArcMap<Value> FlowMap;
     79#endif
    7680
    7781    /// \brief Instantiates a FlowMap.
     
    8892    /// The elevator type used by the algorithm.
    8993    ///
    90     /// \sa Elevator
    91     /// \sa LinkedElevator
     94    /// \sa Elevator, LinkedElevator
     95#ifdef DOXYGEN
     96    typedef lemon::Elevator<GR, GR::Node> Elevator;
     97#else
    9298    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     99#endif
    93100
    94101    /// \brief Instantiates an Elevator.
     
    451458    }
    452459
    453     /// \brief Sets the tolerance used by algorithm.
    454     ///
    455     /// Sets the tolerance used by algorithm.
    456     Circulation& tolerance(const Tolerance& tolerance) const {
     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) {
    457465      _tol = tolerance;
    458466      return *this;
     
    461469    /// \brief Returns a const reference to the tolerance.
    462470    ///
    463     /// Returns a const reference to the tolerance.
     471    /// Returns a const reference to the tolerance object used by
     472    /// the algorithm.
    464473    const Tolerance& tolerance() const {
    465       return tolerance;
     474      return _tol;
    466475    }
    467476
    468477    /// \name Execution Control
    469478    /// The simplest way to execute the algorithm is to call \ref run().\n
    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
     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
    472481    /// the \ref start() function.
    473482
  • lemon/clp.cc

    r576 r746  
    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
    8194
    8295  void ClpLp::_eraseCol(int c) {
  • lemon/clp.h

    r576 r746  
    7676    virtual int _addCol();
    7777    virtual int _addRow();
     78    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    7879
    7980    virtual void _eraseCol(int i);
  • lemon/concepts/digraph.h

    r580 r734  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     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.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    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 
     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.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
     
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    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.
     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.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
    117110      /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
     
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
     
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    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.
     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        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
     
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
     
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
     
    175166        ///
    176167        Arc(const Arc&) { }
    177         /// Initialize the iterator to be invalid.
    178 
    179         /// Initialize the iterator to be invalid.
    180         ///
     168        /// %Invalid constructor \& conversion.
     169
     170        /// Initializes the object to be invalid.
     171        /// \sa Invalid for more details.
    181172        Arc(Invalid) { }
    182173        /// Equality operator
    183174
     175        /// Equality operator.
     176        ///
    184177        /// Two iterators are equal if and only if they point to the
    185         /// same object or both are invalid.
     178        /// same object or both are \c INVALID.
    186179        bool operator==(Arc) const { return true; }
    187180        /// Inequality operator
    188181
    189         /// \sa operator==(Arc n)
    190         ///
     182        /// Inequality operator.
    191183        bool operator!=(Arc) const { return true; }
    192184
    193185        /// Artificial ordering operator.
    194186
    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.
     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.
    201192        bool operator<(Arc) const { return false; }
    202193      };
    203194
    204       /// This iterator goes trough the outgoing arcs of a node.
     195      /// Iterator class for the outgoing arcs of a node.
    205196
    206197      /// This iterator goes trough the \e outgoing arcs of a certain node
     
    208199      /// Its usage is quite simple, for example you can count the number
    209200      /// of outgoing arcs of a node \c n
    210       /// in digraph \c g of type \c Digraph as follows.
     201      /// in a digraph \c g of type \c %Digraph as follows.
    211202      ///\code
    212203      /// int count=0;
    213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     204      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    214205      ///\endcode
    215 
    216206      class OutArcIt : public Arc {
    217207      public:
    218208        /// Default constructor
    219209
    220         /// @warning The default constructor sets the iterator
    221         /// to an undefined value.
     210        /// Default constructor.
     211        /// \warning It sets the iterator to an undefined value.
    222212        OutArcIt() { }
    223213        /// Copy constructor.
     
    226216        ///
    227217        OutArcIt(const OutArcIt& e) : Arc(e) { }
    228         /// Initialize the iterator to be invalid.
    229 
    230         /// Initialize the iterator to be invalid.
    231         ///
     218        /// %Invalid constructor \& conversion.
     219
     220        /// Initializes the iterator to be invalid.
     221        /// \sa Invalid for more details.
    232222        OutArcIt(Invalid) { }
    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.
     223        /// Sets the iterator to the first outgoing arc.
     224
     225        /// Sets the iterator to the first outgoing arc of the given node.
     226        ///
    237227        OutArcIt(const Digraph&, const Node&) { }
    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.
     228        /// Sets the iterator to the given arc.
     229
     230        /// Sets the iterator to the given arc of the given digraph.
     231        ///
    243232        OutArcIt(const Digraph&, const Arc&) { }
    244         ///Next outgoing arc
     233        /// Next outgoing arc
    245234
    246235        /// Assign the iterator to the next
     
    249238      };
    250239
    251       /// This iterator goes trough the incoming arcs of a node.
     240      /// Iterator class for the incoming arcs of a node.
    252241
    253242      /// This iterator goes trough the \e incoming arcs of a certain node
    254243      /// of a digraph.
    255244      /// Its usage is quite simple, for example you can count the number
    256       /// of outgoing arcs of a node \c n
    257       /// in digraph \c g of type \c Digraph as follows.
     245      /// of incoming arcs of a node \c n
     246      /// in a digraph \c g of type \c %Digraph as follows.
    258247      ///\code
    259248      /// int count=0;
    260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     249      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    261250      ///\endcode
    262 
    263251      class InArcIt : public Arc {
    264252      public:
    265253        /// Default constructor
    266254
    267         /// @warning The default constructor sets the iterator
    268         /// to an undefined value.
     255        /// Default constructor.
     256        /// \warning It sets the iterator to an undefined value.
    269257        InArcIt() { }
    270258        /// Copy constructor.
     
    273261        ///
    274262        InArcIt(const InArcIt& e) : Arc(e) { }
    275         /// Initialize the iterator to be invalid.
    276 
    277         /// Initialize the iterator to be invalid.
    278         ///
     263        /// %Invalid constructor \& conversion.
     264
     265        /// Initializes the iterator to be invalid.
     266        /// \sa Invalid for more details.
    279267        InArcIt(Invalid) { }
    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.
     268        /// Sets the iterator to the first incoming arc.
     269
     270        /// Sets the iterator to the first incoming arc of the given node.
     271        ///
    284272        InArcIt(const Digraph&, const Node&) { }
    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.
     273        /// Sets the iterator to the given arc.
     274
     275        /// Sets the iterator to the given arc of the given digraph.
     276        ///
    290277        InArcIt(const Digraph&, const Arc&) { }
    291278        /// Next incoming arc
    292279
    293         /// Assign the iterator to the next inarc of the corresponding node.
    294         ///
     280        /// Assign the iterator to the next
     281        /// incoming arc of the corresponding node.
    295282        InArcIt& operator++() { return *this; }
    296283      };
    297       /// This iterator goes through each arc.
    298 
    299       /// This iterator goes through each arc of a digraph.
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
    300288      /// Its usage is quite simple, for example you can count the number
    301       /// of arcs in a digraph \c g of type \c Digraph as follows:
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    302290      ///\code
    303291      /// int count=0;
    304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
     292      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
    305293      ///\endcode
    306294      class ArcIt : public Arc {
     
    308296        /// Default constructor
    309297
    310         /// @warning The default constructor sets the iterator
    311         /// to an undefined value.
     298        /// Default constructor.
     299        /// \warning It sets the iterator to an undefined value.
    312300        ArcIt() { }
    313301        /// Copy constructor.
     
    316304        ///
    317305        ArcIt(const ArcIt& e) : Arc(e) { }
    318         /// Initialize the iterator to be invalid.
    319 
    320         /// Initialize the iterator to be invalid.
    321         ///
     306        /// %Invalid constructor \& conversion.
     307
     308        /// Initializes the iterator to be invalid.
     309        /// \sa Invalid for more details.
    322310        ArcIt(Invalid) { }
    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.
     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        ///
    333320        ArcIt(const Digraph&, const Arc&) { }
    334         ///Next arc
     321        /// Next arc
    335322
    336323        /// Assign the iterator to the next arc.
     324        ///
    337325        ArcIt& operator++() { return *this; }
    338326      };
    339       ///Gives back the target node of an arc.
    340 
    341       ///Gives back the target node of an arc.
    342       ///
     327
     328      /// \brief The source node of the arc.
     329      ///
     330      /// Returns the source node of the given arc.
     331      Node source(Arc) const { return INVALID; }
     332
     333      /// \brief The target node of the arc.
     334      ///
     335      /// Returns the target node of the given arc.
    343336      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       ///
    348       Node source(Arc) const { return INVALID; }
    349 
    350       /// \brief Returns the ID of the node.
     337
     338      /// \brief The ID of the node.
     339      ///
     340      /// Returns the ID of the given node.
    351341      int id(Node) const { return -1; }
    352342
    353       /// \brief Returns the ID of the arc.
     343      /// \brief The ID of the arc.
     344      ///
     345      /// Returns the ID of the given arc.
    354346      int id(Arc) const { return -1; }
    355347
    356       /// \brief Returns the node with the given ID.
    357       ///
    358       /// \pre The argument should be a valid node ID in the graph.
     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.
    359352      Node nodeFromId(int) const { return INVALID; }
    360353
    361       /// \brief Returns the arc with the given ID.
    362       ///
    363       /// \pre The argument should be a valid arc ID in the graph.
     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.
    364358      Arc arcFromId(int) const { return INVALID; }
    365359
    366       /// \brief Returns an upper bound on the node IDs.
     360      /// \brief An upper bound on the node IDs.
     361      ///
     362      /// Returns an upper bound on the node IDs.
    367363      int maxNodeId() const { return -1; }
    368364
    369       /// \brief Returns an upper bound on the arc IDs.
     365      /// \brief An upper bound on the arc IDs.
     366      ///
     367      /// Returns an upper bound on the arc IDs.
    370368      int maxArcId() const { return -1; }
    371369
     
    393391      int maxId(Arc) const { return -1; }
    394392
     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
    395398      /// \brief The base node of the iterator.
    396399      ///
    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; }
     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; }
    400403
    401404      /// \brief The running node of the iterator.
    402405      ///
    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; }
     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; }
    406409
    407410      /// \brief The base node of the iterator.
    408411      ///
    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; }
     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; }
    412415
    413416      /// \brief The running node of the iterator.
    414417      ///
    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.
     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.
    427426      template<class T>
    428427      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    429428      public:
    430429
    431         ///\e
    432         NodeMap(const Digraph&) { }
    433         ///\e
     430        /// Constructor
     431        explicit NodeMap(const Digraph&) { }
     432        /// Constructor with given initial value
    434433        NodeMap(const Digraph&, T) { }
    435434
     
    446445      };
    447446
    448       /// \brief Reference map of the arcs to type \c T.
    449       ///
    450       /// Reference map of the arcs to type \c T.
     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.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         ///\e
    456         ArcMap(const Digraph&) { }
    457         ///\e
     455        /// Constructor
     456        explicit ArcMap(const Digraph&) { }
     457        /// Constructor with given initial value
    458458        ArcMap(const Digraph&, T) { }
     459
    459460      private:
    460461        ///Copy constructor
  • lemon/concepts/graph.h

    r657 r734  
    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>
    2729#include <lemon/core.h>
    2830
     
    3234    /// \ingroup graph_concepts
    3335    ///
    34     /// \brief Class describing the concept of Undirected Graphs.
     36    /// \brief Class describing the concept of undirected graphs.
    3537    ///
    36     /// This class describes the common interface of all Undirected
    37     /// Graphs.
     38    /// This class describes the common interface of all undirected
     39    /// graphs.
    3840    ///
    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
     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
    4244    /// run properly, of course.
     45    /// An actual graph implementation like \ref ListGraph or
     46    /// \ref SmartGraph may have additional functionality.   
    4347    ///
    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.
     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.
    5361    ///
    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.
     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.
    6168    ///
    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.
     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
    6873    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
    6981    public:
    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
     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
    7590      /// specializations for undirected graphs.
    7691      typedef True UndirectedTag;
    7792
    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.
     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.
    8598      class Node {
    8699      public:
    87100        /// Default constructor
    88101
    89         /// @warning The default constructor sets the iterator
    90         /// to an undefined value.
     102        /// Default constructor.
     103        /// \warning It sets the object to an undefined value.
    91104        Node() { }
    92105        /// Copy constructor.
     
    96109        Node(const Node&) { }
    97110
    98         /// Invalid constructor \& conversion.
    99 
    100         /// This constructor initializes the iterator to be invalid.
     111        /// %Invalid constructor \& conversion.
     112
     113        /// Initializes the object to be invalid.
    101114        /// \sa Invalid for more details.
    102115        Node(Invalid) { }
    103116        /// Equality operator
    104117
     118        /// Equality operator.
     119        ///
    105120        /// Two iterators are equal if and only if they point to the
    106         /// same object or both are invalid.
     121        /// same object or both are \c INVALID.
    107122        bool operator==(Node) const { return true; }
    108123
    109124        /// Inequality operator
    110125
    111         /// \sa operator==(Node n)
    112         ///
     126        /// Inequality operator.
    113127        bool operator!=(Node) const { return true; }
    114128
    115129        /// Artificial ordering operator.
    116130
    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
     131        /// Artificial ordering operator.
     132        ///
     133        /// \note This operator only has to define some strict ordering of
    121134        /// the items; this order has nothing to do with the iteration
    122135        /// ordering of the items.
     
    125138      };
    126139
    127       /// This iterator goes through each node.
    128 
    129       /// This iterator goes through each node.
     140      /// Iterator class for the nodes.
     141
     142      /// This iterator goes through each node of the graph.
    130143      /// Its usage is quite simple, for example you can count the number
    131       /// of nodes in graph \c g of type \c Graph like this:
     144      /// of nodes in a graph \c g of type \c %Graph like this:
    132145      ///\code
    133146      /// int count=0;
     
    138151        /// Default constructor
    139152
    140         /// @warning The default constructor sets the iterator
    141         /// to an undefined value.
     153        /// Default constructor.
     154        /// \warning It sets the iterator to an undefined value.
    142155        NodeIt() { }
    143156        /// Copy constructor.
     
    146159        ///
    147160        NodeIt(const NodeIt& n) : Node(n) { }
    148         /// Invalid constructor \& conversion.
    149 
    150         /// Initialize the iterator to be invalid.
     161        /// %Invalid constructor \& conversion.
     162
     163        /// Initializes the iterator to be invalid.
    151164        /// \sa Invalid for more details.
    152165        NodeIt(Invalid) { }
    153166        /// Sets the iterator to the first node.
    154167
    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.
     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        ///
    164175        NodeIt(const Graph&, const Node&) { }
    165176        /// Next node.
     
    171182
    172183
    173       /// The base type of the edge iterators.
    174 
    175       /// The base type of the edge iterators.
    176       ///
     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.
    177189      class Edge {
    178190      public:
    179191        /// Default constructor
    180192
    181         /// @warning The default constructor sets the iterator
    182         /// to an undefined value.
     193        /// Default constructor.
     194        /// \warning It sets the object to an undefined value.
    183195        Edge() { }
    184196        /// Copy constructor.
     
    187199        ///
    188200        Edge(const Edge&) { }
    189         /// Initialize the iterator to be invalid.
    190 
    191         /// Initialize the iterator to be invalid.
    192         ///
     201        /// %Invalid constructor \& conversion.
     202
     203        /// Initializes the object to be invalid.
     204        /// \sa Invalid for more details.
    193205        Edge(Invalid) { }
    194206        /// Equality operator
    195207
     208        /// Equality operator.
     209        ///
    196210        /// Two iterators are equal if and only if they point to the
    197         /// same object or both are invalid.
     211        /// same object or both are \c INVALID.
    198212        bool operator==(Edge) const { return true; }
    199213        /// Inequality operator
    200214
    201         /// \sa operator==(Edge n)
    202         ///
     215        /// Inequality operator.
    203216        bool operator!=(Edge) const { return true; }
    204217
    205218        /// Artificial ordering operator.
    206219
    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.
     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.
    213225        bool operator<(Edge) const { return false; }
    214226      };
    215227
    216       /// This iterator goes through each edge.
    217 
    218       /// This iterator goes through each edge of a graph.
     228      /// Iterator class for the edges.
     229
     230      /// This iterator goes through each edge of the graph.
    219231      /// Its usage is quite simple, for example you can count the number
    220       /// of edges in a graph \c g of type \c Graph as follows:
     232      /// of edges in a graph \c g of type \c %Graph as follows:
    221233      ///\code
    222234      /// int count=0;
     
    227239        /// Default constructor
    228240
    229         /// @warning The default constructor sets the iterator
    230         /// to an undefined value.
     241        /// Default constructor.
     242        /// \warning It sets the iterator to an undefined value.
    231243        EdgeIt() { }
    232244        /// Copy constructor.
     
    235247        ///
    236248        EdgeIt(const EdgeIt& e) : Edge(e) { }
    237         /// Initialize the iterator to be invalid.
    238 
    239         /// Initialize the iterator to be invalid.
    240         ///
     249        /// %Invalid constructor \& conversion.
     250
     251        /// Initializes the iterator to be invalid.
     252        /// \sa Invalid for more details.
    241253        EdgeIt(Invalid) { }
    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.
     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        ///
    252263        EdgeIt(const Graph&, const Edge&) { }
    253264        /// Next edge
    254265
    255266        /// Assign the iterator to the next edge.
     267        ///
    256268        EdgeIt& operator++() { return *this; }
    257269      };
    258270
    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       ///
     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.
    266275      /// Its usage is quite simple, for example you can compute the
    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.
     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.
    269278      ///
    270279      ///\code
     
    272281      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    273282      ///\endcode
     283      ///
     284      /// \warning Loop edges will be iterated twice.
    274285      class IncEdgeIt : public Edge {
    275286      public:
    276287        /// Default constructor
    277288
    278         /// @warning The default constructor sets the iterator
    279         /// to an undefined value.
     289        /// Default constructor.
     290        /// \warning It sets the iterator to an undefined value.
    280291        IncEdgeIt() { }
    281292        /// Copy constructor.
     
    284295        ///
    285296        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    286         /// Initialize the iterator to be invalid.
    287 
    288         /// Initialize the iterator to be invalid.
    289         ///
     297        /// %Invalid constructor \& conversion.
     298
     299        /// Initializes the iterator to be invalid.
     300        /// \sa Invalid for more details.
    290301        IncEdgeIt(Invalid) { }
    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.
     302        /// Sets the iterator to the first incident edge.
     303
     304        /// Sets the iterator to the first incident edge of the given node.
     305        ///
    295306        IncEdgeIt(const Graph&, const Node&) { }
    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.
     307        /// Sets the iterator to the given edge.
     308
     309        /// Sets the iterator to the given edge of the given graph.
     310        ///
    301311        IncEdgeIt(const Graph&, const Edge&) { }
    302         /// Next incident arc
    303 
    304         /// Assign the iterator to the next incident arc
     312        /// Next incident edge
     313
     314        /// Assign the iterator to the next incident edge
    305315        /// of the corresponding node.
    306316        IncEdgeIt& operator++() { return *this; }
    307317      };
    308318
    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.
     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.
    314324      class Arc {
    315325      public:
    316326        /// Default constructor
    317327
    318         /// @warning The default constructor sets the iterator
    319         /// to an undefined value.
     328        /// Default constructor.
     329        /// \warning It sets the object to an undefined value.
    320330        Arc() { }
    321331        /// Copy constructor.
     
    324334        ///
    325335        Arc(const Arc&) { }
    326         /// Initialize the iterator to be invalid.
    327 
    328         /// Initialize the iterator to be invalid.
    329         ///
     336        /// %Invalid constructor \& conversion.
     337
     338        /// Initializes the object to be invalid.
     339        /// \sa Invalid for more details.
    330340        Arc(Invalid) { }
    331341        /// Equality operator
    332342
     343        /// Equality operator.
     344        ///
    333345        /// Two iterators are equal if and only if they point to the
    334         /// same object or both are invalid.
     346        /// same object or both are \c INVALID.
    335347        bool operator==(Arc) const { return true; }
    336348        /// Inequality operator
    337349
    338         /// \sa operator==(Arc n)
    339         ///
     350        /// Inequality operator.
    340351        bool operator!=(Arc) const { return true; }
    341352
    342353        /// Artificial ordering operator.
    343354
    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.
     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.
    350360        bool operator<(Arc) const { return false; }
    351361
    352         /// Converison to Edge
     362        /// Converison to \c Edge
     363       
     364        /// Converison to \c Edge.
     365        ///
    353366        operator Edge() const { return Edge(); }
    354367      };
    355       /// This iterator goes through each directed arc.
    356 
    357       /// This iterator goes through each arc of a graph.
     368
     369      /// Iterator class for the arcs.
     370
     371      /// This iterator goes through each directed arc of the graph.
    358372      /// Its usage is quite simple, for example you can count the number
    359       /// of arcs in a graph \c g of type \c Graph as follows:
     373      /// of arcs in a graph \c g of type \c %Graph as follows:
    360374      ///\code
    361375      /// int count=0;
    362       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
     376      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
    363377      ///\endcode
    364378      class ArcIt : public Arc {
     
    366380        /// Default constructor
    367381
    368         /// @warning The default constructor sets the iterator
    369         /// to an undefined value.
     382        /// Default constructor.
     383        /// \warning It sets the iterator to an undefined value.
    370384        ArcIt() { }
    371385        /// Copy constructor.
     
    374388        ///
    375389        ArcIt(const ArcIt& e) : Arc(e) { }
    376         /// Initialize the iterator to be invalid.
    377 
    378         /// Initialize the iterator to be invalid.
    379         ///
     390        /// %Invalid constructor \& conversion.
     391
     392        /// Initializes the iterator to be invalid.
     393        /// \sa Invalid for more details.
    380394        ArcIt(Invalid) { }
    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.
     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        ///
    391404        ArcIt(const Graph&, const Arc&) { }
    392         ///Next arc
     405        /// Next arc
    393406
    394407        /// Assign the iterator to the next arc.
     408        ///
    395409        ArcIt& operator++() { return *this; }
    396410      };
    397411
    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.
     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.
    402416      /// Its usage is quite simple, for example you can count the number
    403417      /// of outgoing arcs of a node \c n
    404       /// in graph \c g of type \c Graph as follows.
     418      /// in a graph \c g of type \c %Graph as follows.
    405419      ///\code
    406420      /// int count=0;
    407       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     421      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    408422      ///\endcode
    409 
    410423      class OutArcIt : public Arc {
    411424      public:
    412425        /// Default constructor
    413426
    414         /// @warning The default constructor sets the iterator
    415         /// to an undefined value.
     427        /// Default constructor.
     428        /// \warning It sets the iterator to an undefined value.
    416429        OutArcIt() { }
    417430        /// Copy constructor.
     
    420433        ///
    421434        OutArcIt(const OutArcIt& e) : Arc(e) { }
    422         /// Initialize the iterator to be invalid.
    423 
    424         /// Initialize the iterator to be invalid.
    425         ///
     435        /// %Invalid constructor \& conversion.
     436
     437        /// Initializes the iterator to be invalid.
     438        /// \sa Invalid for more details.
    426439        OutArcIt(Invalid) { }
    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
     440        /// Sets the iterator to the first outgoing arc.
     441
     442        /// Sets the iterator to the first outgoing arc of the given node.
     443        ///
    433444        OutArcIt(const Graph& n, const Node& g) {
    434445          ignore_unused_variable_warning(n);
    435446          ignore_unused_variable_warning(g);
    436447        }
    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.
     448        /// Sets the iterator to the given arc.
     449
     450        /// Sets the iterator to the given arc of the given graph.
     451        ///
    442452        OutArcIt(const Graph&, const Arc&) { }
    443         ///Next outgoing arc
     453        /// Next outgoing arc
    444454
    445455        /// Assign the iterator to the next
     
    448458      };
    449459
    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.
     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.
    454464      /// Its usage is quite simple, for example you can count the number
    455       /// of outgoing arcs of a node \c n
    456       /// in graph \c g of type \c Graph as follows.
     465      /// of incoming arcs of a node \c n
     466      /// in a graph \c g of type \c %Graph as follows.
    457467      ///\code
    458468      /// int count=0;
    459       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     469      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    460470      ///\endcode
    461 
    462471      class InArcIt : public Arc {
    463472      public:
    464473        /// Default constructor
    465474
    466         /// @warning The default constructor sets the iterator
    467         /// to an undefined value.
     475        /// Default constructor.
     476        /// \warning It sets the iterator to an undefined value.
    468477        InArcIt() { }
    469478        /// Copy constructor.
     
    472481        ///
    473482        InArcIt(const InArcIt& e) : Arc(e) { }
    474         /// Initialize the iterator to be invalid.
    475 
    476         /// Initialize the iterator to be invalid.
    477         ///
     483        /// %Invalid constructor \& conversion.
     484
     485        /// Initializes the iterator to be invalid.
     486        /// \sa Invalid for more details.
    478487        InArcIt(Invalid) { }
    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
     488        /// Sets the iterator to the first incoming arc.
     489
     490        /// Sets the iterator to the first incoming arc of the given node.
     491        ///
    485492        InArcIt(const Graph& g, const Node& n) {
    486493          ignore_unused_variable_warning(n);
    487494          ignore_unused_variable_warning(g);
    488495        }
    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.
     496        /// Sets the iterator to the given arc.
     497
     498        /// Sets the iterator to the given arc of the given graph.
     499        ///
    494500        InArcIt(const Graph&, const Arc&) { }
    495501        /// Next incoming arc
    496502
    497         /// Assign the iterator to the next inarc of the corresponding node.
    498         ///
     503        /// Assign the iterator to the next
     504        /// incoming arc of the corresponding node.
    499505        InArcIt& operator++() { return *this; }
    500506      };
    501507
    502       /// \brief Reference map of the nodes to type \c T.
    503       ///
    504       /// Reference map of the nodes to type \c T.
     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.
    505512      template<class T>
    506513      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
     
    508515      public:
    509516
    510         ///\e
    511         NodeMap(const Graph&) { }
    512         ///\e
     517        /// Constructor
     518        explicit NodeMap(const Graph&) { }
     519        /// Constructor with given initial value
    513520        NodeMap(const Graph&, T) { }
    514521
     
    525532      };
    526533
    527       /// \brief Reference map of the arcs to type \c T.
    528       ///
    529       /// Reference map of the arcs to type \c T.
     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.
    530538      template<class T>
    531539      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
     
    533541      public:
    534542
    535         ///\e
    536         ArcMap(const Graph&) { }
    537         ///\e
     543        /// Constructor
     544        explicit ArcMap(const Graph&) { }
     545        /// Constructor with given initial value
    538546        ArcMap(const Graph&, T) { }
     547
    539548      private:
    540549        ///Copy constructor
     
    549558      };
    550559
    551       /// Reference map of the edges to type \c T.
    552 
    553       /// Reference map of the edges to type \c T.
     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.
    554564      template<class T>
    555565      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
     
    557567      public:
    558568
    559         ///\e
    560         EdgeMap(const Graph&) { }
    561         ///\e
     569        /// Constructor
     570        explicit EdgeMap(const Graph&) { }
     571        /// Constructor with given initial value
    562572        EdgeMap(const Graph&, T) { }
     573
    563574      private:
    564575        ///Copy constructor
     
    573584      };
    574585
    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.
     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.
    619595      /// \sa v()
    620596      /// \sa direction()
    621597      Node u(Edge) const { return INVALID; }
    622598
    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.
     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.
    633608      /// \sa u()
    634609      /// \sa direction()
    635610      Node v(Edge) const { return INVALID; }
    636611
    637       /// \brief Source node of the directed arc.
     612      /// \brief The source node of the arc.
     613      ///
     614      /// Returns the source node of the given arc.
    638615      Node source(Arc) const { return INVALID; }
    639616
    640       /// \brief Target node of the directed arc.
     617      /// \brief The target node of the arc.
     618      ///
     619      /// Returns the target node of the given arc.
    641620      Node target(Arc) const { return INVALID; }
    642621
    643       /// \brief Returns the id of the node.
     622      /// \brief The ID of the node.
     623      ///
     624      /// Returns the ID of the given node.
    644625      int id(Node) const { return -1; }
    645626
    646       /// \brief Returns the id of the edge.
     627      /// \brief The ID of the edge.
     628      ///
     629      /// Returns the ID of the given edge.
    647630      int id(Edge) const { return -1; }
    648631
    649       /// \brief Returns the id of the arc.
     632      /// \brief The ID of the arc.
     633      ///
     634      /// Returns the ID of the given arc.
    650635      int id(Arc) const { return -1; }
    651636
    652       /// \brief Returns the node with the given id.
    653       ///
    654       /// \pre The argument should be a valid node id in the graph.
     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.
    655641      Node nodeFromId(int) const { return INVALID; }
    656642
    657       /// \brief Returns the edge with the given id.
    658       ///
    659       /// \pre The argument should be a valid edge id in the graph.
     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.
    660647      Edge edgeFromId(int) const { return INVALID; }
    661648
    662       /// \brief Returns the arc with the given id.
    663       ///
    664       /// \pre The argument should be a valid arc id in the graph.
     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.
    665653      Arc arcFromId(int) const { return INVALID; }
    666654
    667       /// \brief Returns an upper bound on the node IDs.
     655      /// \brief An upper bound on the node IDs.
     656      ///
     657      /// Returns an upper bound on the node IDs.
    668658      int maxNodeId() const { return -1; }
    669659
    670       /// \brief Returns an upper bound on the edge IDs.
     660      /// \brief An upper bound on the edge IDs.
     661      ///
     662      /// Returns an upper bound on the edge IDs.
    671663      int maxEdgeId() const { return -1; }
    672664
    673       /// \brief Returns an upper bound on the arc IDs.
     665      /// \brief An upper bound on the arc IDs.
     666      ///
     667      /// Returns an upper bound on the arc IDs.
    674668      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; }
    675703
    676704      void first(Node&) const {}
     
    706734      int maxId(Arc) const { return -1; }
    707735
    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       }
     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; }
    749769
    750770      template <typename _Graph>
  • lemon/concepts/graph_components.h

    r666 r734  
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only have to define some strict ordering of
     95      /// \note This operator only has 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

    r584 r710  
    1717 */
    1818
     19#ifndef LEMON_CONCEPTS_HEAP_H
     20#define LEMON_CONCEPTS_HEAP_H
     21
    1922///\ingroup concept
    2023///\file
    2124///\brief The concept of heaps.
    2225
    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     /// 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.
     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.
    4345    ///
    44     /// \tparam PR Type of the priority of the items.
    45     /// \tparam IM A read and writable item map with int values, used
     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
    4652    /// internally to handle the cross references.
    47     /// \tparam Comp A functor class for the ordering of the priorities.
     53    /// \tparam CMP A functor class for comparing the priorities.
    4854    /// The default is \c std::less<PR>.
    4955#ifdef DOXYGEN
    50     template <typename PR, typename IM, typename Comp = std::less<PR> >
     56    template <typename PR, typename IM, typename CMP>
    5157#else
    52     template <typename PR, typename IM>
     58    template <typename PR, typename IM, typename CMP = std::less<PR> >
    5359#endif
    5460    class Heap {
     
    6571      ///
    6672      /// Each item has a state associated to it. It can be "in heap",
    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.
     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.
    7075      ///
    7176      /// The item-int map must be initialized in such way that it assigns
     
    7378      enum State {
    7479        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    75         PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
    76         POST_HEAP = -2  ///< = -2. The "post heap" state constant.
     80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
     81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
    7782      };
    7883
    79       /// \brief The constructor.
    80       ///
    81       /// The constructor.
     84      /// \brief Constructor.
     85      ///
     86      /// Constructor.
    8287      /// \param map A map that assigns \c int values to keys of type
    8388      /// \c Item. It is used internally by the heap implementations to
    8489      /// handle the cross references. The assigned value must be
    85       /// \c PRE_HEAP (<tt>-1</tt>) for every item.
     90      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    8691      explicit Heap(ItemIntMap &map) {}
    8792
     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
    88103      /// \brief The number of items stored in the heap.
    89104      ///
    90       /// Returns the number of items stored in the heap.
     105      /// This function returns the number of items stored in the heap.
    91106      int size() const { return 0; }
    92107
    93       /// \brief Checks if the heap is empty.
    94       ///
    95       /// Returns \c true if the heap is empty.
     108      /// \brief Check if the heap is empty.
     109      ///
     110      /// This function returns \c true if the heap is empty.
    96111      bool empty() const { return false; }
    97112
    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.
     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.
    106126      /// \param i The item to insert.
    107127      /// \param p The priority of the item.
     128      /// \pre \e i must not be stored in the heap.
    108129      void push(const Item &i, const Prio &p) {}
    109130
    110       /// \brief Returns the item having minimum priority.
    111       ///
    112       /// Returns the item having minimum priority.
     131      /// \brief Return the item having minimum priority.
     132      ///
     133      /// This function returns the item having minimum priority.
    113134      /// \pre The heap must be non-empty.
    114135      Item top() const {}
     
    116137      /// \brief The minimum priority.
    117138      ///
    118       /// Returns the minimum priority.
     139      /// This function returns the minimum priority.
    119140      /// \pre The heap must be non-empty.
    120141      Prio prio() const {}
    121142
    122       /// \brief Removes the item having minimum priority.
    123       ///
    124       /// Removes the item having minimum priority.
     143      /// \brief Remove the item having minimum priority.
     144      ///
     145      /// This function removes the item having minimum priority.
    125146      /// \pre The heap must be non-empty.
    126147      void pop() {}
    127148
    128       /// \brief Removes an item from the heap.
    129       ///
    130       /// Removes the given item from the heap if it is already stored.
     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.
    131153      /// \param i The item to delete.
     154      /// \pre \e i must be in the heap.
    132155      void erase(const Item &i) {}
    133156
    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.
     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.
    139162      Prio operator[](const Item &i) const {}
    140163
    141       /// \brief Sets the priority of an item or inserts it, if it is
     164      /// \brief Set the priority of an item or insert it, if it is
    142165      /// not stored in the heap.
    143166      ///
    144167      /// This method sets the priority of the given item if it is
    145       /// already stored in the heap.
    146       /// Otherwise it inserts the given item with the given priority.
     168      /// already stored in the heap. Otherwise it inserts the given
     169      /// item into the heap with the given priority.
    147170      ///
    148171      /// \param i The item.
     
    150173      void set(const Item &i, const Prio &p) {}
    151174
    152       /// \brief Decreases the priority of an item to the given value.
    153       ///
    154       /// Decreases the priority of an item to the given value.
     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.
    155178      /// \param i The item.
    156179      /// \param p The priority.
    157       /// \pre \c i must be stored in the heap with priority at least \c p.
     180      /// \pre \e i must be stored in the heap with priority at least \e p.
    158181      void decrease(const Item &i, const Prio &p) {}
    159182
    160       /// \brief Increases the priority of an item to the given value.
    161       ///
    162       /// Increases the priority of an item to the given value.
     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.
    163186      /// \param i The item.
    164187      /// \param p The priority.
    165       /// \pre \c i must be stored in the heap with priority at most \c p.
     188      /// \pre \e i must be stored in the heap with priority at most \e p.
    166189      void increase(const Item &i, const Prio &p) {}
    167190
    168       /// \brief Returns if an item is in, has already been in, or has
    169       /// never been in the heap.
     191      /// \brief Return the state of an item.
    170192      ///
    171193      /// This method returns \c PRE_HEAP if the given item has never
     
    177199      State state(const Item &i) const {}
    178200
    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.
     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.
    184206      /// \param i The item.
    185207      /// \param st The state. It should not be \c IN_HEAP.
  • lemon/concepts/maps.h

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

    r576 r746  
    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  }
    114147
    115148  void CplexBase::_eraseCol(int i) {
  • lemon/cplex.h

    r576 r746  
    9494    virtual int _addCol();
    9595    virtual int _addRow();
     96    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    9697
    9798    virtual void _eraseCol(int i);
  • lemon/dfs.h

    r584 r717  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8687    ///Instantiates a \c ReachedMap.
     
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101102    ///Instantiates a \c DistMap.
     
    225226    ///\ref named-templ-param "Named parameter" for setting
    226227    ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     228    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    228229    template <class T>
    229230    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    245246    ///\ref named-templ-param "Named parameter" for setting
    246247    ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     248    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    248249    template <class T>
    249250    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265266    ///\ref named-templ-param "Named parameter" for setting
    266267    ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268269    template <class T>
    269270    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    285286    ///\ref named-templ-param "Named parameter" for setting
    286287    ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     288    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    288289    template <class T>
    289290    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    412413    ///The simplest way to execute the DFS algorithm is to use one of the
    413414    ///member functions called \ref run(Node) "run()".\n
    414     ///If you need more control on the execution, first you have to call
    415     ///\ref init(), then you can add a source node with \ref addSource()
     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()
    416417    ///and perform the actual computation with \ref start().
    417418    ///This procedure can be repeated if there are nodes that have not
     
    670671    ///@{
    671672
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     673    ///The DFS path to the given node.
     674
     675    ///Returns the DFS path to the given node from the root(s).
    675676    ///
    676677    ///\warning \c t should be reached from the root(s).
     
    680681    Path path(Node t) const { return Path(*G, *_pred, t); }
    681682
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     683    ///The distance of the given node from the root(s).
     684
     685    ///Returns the distance of the given node from the root(s).
    685686    ///
    686687    ///\warning If node \c v is not reached from the root(s), then
     
    691692    int dist(Node v) const { return (*_dist)[v]; }
    692693
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     694    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694695
    695696    ///This function returns the 'previous arc' of the %DFS tree for the
     
    699700    ///
    700701    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     702    ///\ref predNode() and \ref predMap().
    702703    ///
    703704    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    705706    Arc predArc(Node v) const { return (*_pred)[v];}
    706707
    707     ///Returns the 'previous node' of the %DFS tree.
     708    ///Returns the 'previous node' of the %DFS tree for the given node.
    708709
    709710    ///This function returns the 'previous node' of the %DFS
    710711    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///of a %DFS path from a root to \c v. It is \c INVALID
    712713    ///if \c v is not reached from the root(s) or if \c v is a root.
    713714    ///
    714715    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     716    ///\ref predArc() and \ref predMap().
    716717    ///
    717718    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    734735    ///
    735736    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     737    ///arcs, which form the DFS tree (forest).
    737738    ///
    738739    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    740741    const PredMap &predMap() const { return *_pred;}
    741742
    742     ///Checks if a node is reached from the root(s).
     743    ///Checks if the given node. node is reached from the root(s).
    743744
    744745    ///Returns \c true if \c v is reached from the root(s).
     
    766767    ///The type of the map that stores the predecessor
    767768    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     769    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769770    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770771    ///Instantiates a PredMap.
     
    781782
    782783    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     784    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    784785    ///By default it is a NullMap.
    785786    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    801802
    802803    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     804    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804805    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805806    ///Instantiates a ReachedMap.
     
    816817
    817818    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     819    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819820    typedef typename Digraph::template NodeMap<int> DistMap;
    820821    ///Instantiates a DistMap.
     
    831832
    832833    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     834    ///It must conform to the \ref concepts::Path "Path" concept.
    834835    typedef lemon::Path<Digraph> Path;
    835836  };
     
    837838  /// Default traits class used by DfsWizard
    838839
    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.
     840  /// Default traits class used by DfsWizard.
     841  /// \tparam GR The type of the digraph.
    845842  template<class GR>
    846843  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870867    /// Constructor.
    871868
    872     /// This constructor does not require parameters, therefore it initiates
     869    /// This constructor does not require parameters, it initiates
    873870    /// all of the attributes to \c 0.
    874871    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    900897    typedef TR Base;
    901898
    902     ///The type of the digraph the algorithm runs on.
    903899    typedef typename TR::Digraph Digraph;
    904900
     
    908904    typedef typename Digraph::OutArcIt OutArcIt;
    909905
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912906    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914907    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916908    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918909    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920910    typedef typename TR::Path Path;
    921911
     
    1000990      SetPredMapBase(const TR &b) : TR(b) {}
    1001991    };
    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.
     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.
    1007998    template<class T>
    1008999    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181009      SetReachedMapBase(const TR &b) : TR(b) {}
    10191010    };
    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.
     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.
    10251017    template<class T>
    10261018    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361028      SetDistMapBase(const TR &b) : TR(b) {}
    10371029    };
    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.
     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.
    10431037    template<class T>
    10441038    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541048      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551049    };
    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.
     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.
    10611056    template<class T>
    10621057    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12091204    ///
    12101205    /// The type of the map that indicates which nodes are reached.
    1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1206    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12121207    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12131208
     
    13701365    /// The simplest way to execute the DFS algorithm is to use one of the
    13711366    /// member functions called \ref run(Node) "run()".\n
    1372     /// If you need more control on the execution, first you have to call
    1373     /// \ref init(), then you can add a source node with \ref addSource()
     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()
    13741369    /// and perform the actual computation with \ref start().
    13751370    /// This procedure can be repeated if there are nodes that have not
     
    16211616    ///@{
    16221617
    1623     /// \brief Checks if a node is reached from the root(s).
     1618    /// \brief Checks if the given node is reached from the root(s).
    16241619    ///
    16251620    /// Returns \c true if \c v is reached from the root(s).
  • lemon/dijkstra.h

    r584 r717  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the length of the arcs.
     75    ///The type of the arc lengths.
    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 meet the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must conform to 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.
    171175  ///
    172176  ///The arc lengths are passed to the algorithm using a
     
    202206    typedef typename TR::Digraph Digraph;
    203207
    204     ///The type of the length of the arcs.
     208    ///The type of the arc lengths.
    205209    typedef typename TR::LengthMap::Value Value;
    206210    ///The type of the map that stores the arc lengths.
     
    305309    ///\ref named-templ-param "Named parameter" for setting
    306310    ///\c PredMap type.
    307     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     311    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    308312    template <class T>
    309313    struct SetPredMap
     
    326330    ///\ref named-templ-param "Named parameter" for setting
    327331    ///\c DistMap type.
    328     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     332    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    329333    template <class T>
    330334    struct SetDistMap
     
    347351    ///\ref named-templ-param "Named parameter" for setting
    348352    ///\c ProcessedMap type.
    349     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     353    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    350354    template <class T>
    351355    struct SetProcessedMap
     
    444448    ///\ref named-templ-param "Named parameter" for setting
    445449    ///\c OperationTraits type.
     450    /// For more information see \ref DijkstraDefaultOperationTraits.
    446451    template <class T>
    447452    struct SetOperationTraits
     
    585590    ///The simplest way to execute the %Dijkstra algorithm is to use
    586591    ///one of the member functions called \ref run(Node) "run()".\n
    587     ///If you need more control on the execution, first you have to call
    588     ///\ref init(), then you can add several source nodes with
     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
    589594    ///\ref addSource(). Finally the actual path computation can be
    590595    ///performed with one of the \ref start() functions.
     
    802807    ///The results of the %Dijkstra algorithm can be obtained using these
    803808    ///functions.\n
    804     ///Either \ref run(Node) "run()" or \ref start() should be called
     809    ///Either \ref run(Node) "run()" or \ref init() should be called
    805810    ///before using them.
    806811
    807812    ///@{
    808813
    809     ///The shortest path to a node.
    810 
    811     ///Returns the shortest path to a node.
     814    ///The shortest path to the given node.
     815
     816    ///Returns the shortest path to the given node from the root(s).
    812817    ///
    813818    ///\warning \c t should be reached from the root(s).
     
    817822    Path path(Node t) const { return Path(*G, *_pred, t); }
    818823
    819     ///The distance of a node from the root(s).
    820 
    821     ///Returns the distance of a node from the root(s).
     824    ///The distance of the given node from the root(s).
     825
     826    ///Returns the distance of the given node from the root(s).
    822827    ///
    823828    ///\warning If node \c v is not reached from the root(s), then
     
    828833    Value dist(Node v) const { return (*_dist)[v]; }
    829834
    830     ///Returns the 'previous arc' of the shortest path tree for a node.
    831 
     835    ///\brief Returns the 'previous arc' of the shortest path tree for
     836    ///the given node.
     837    ///
    832838    ///This function returns the 'previous arc' of the shortest path
    833839    ///tree for the node \c v, i.e. it returns the last arc of a
     
    836842    ///
    837843    ///The shortest path tree used here is equal to the shortest path
    838     ///tree used in \ref predNode().
     844    ///tree used in \ref predNode() and \ref predMap().
    839845    ///
    840846    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    842848    Arc predArc(Node v) const { return (*_pred)[v]; }
    843849
    844     ///Returns the 'previous node' of the shortest path tree for a node.
    845 
     850    ///\brief Returns the 'previous node' of the shortest path tree for
     851    ///the given node.
     852    ///
    846853    ///This function returns the 'previous node' of the shortest path
    847854    ///tree for the node \c v, i.e. it returns the last but one node
    848     ///from a shortest path from a root to \c v. It is \c INVALID
     855    ///of a shortest path from a root to \c v. It is \c INVALID
    849856    ///if \c v is not reached from the root(s) or if \c v is a root.
    850857    ///
    851858    ///The shortest path tree used here is equal to the shortest path
    852     ///tree used in \ref predArc().
     859    ///tree used in \ref predArc() and \ref predMap().
    853860    ///
    854861    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    871878    ///
    872879    ///Returns a const reference to the node map that stores the predecessor
    873     ///arcs, which form the shortest path tree.
     880    ///arcs, which form the shortest path tree (forest).
    874881    ///
    875882    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    877884    const PredMap &predMap() const { return *_pred;}
    878885
    879     ///Checks if a node is reached from the root(s).
     886    ///Checks if the given node is reached from the root(s).
    880887
    881888    ///Returns \c true if \c v is reached from the root(s).
     
    896903                                          Heap::POST_HEAP; }
    897904
    898     ///The current distance of a node from the root(s).
    899 
    900     ///Returns the current distance of a node from the root(s).
     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).
    901908    ///It may be decreased in the following processes.
    902909    ///
     
    925932
    926933    ///The type of the map that stores the arc lengths.
    927     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     934    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    928935    typedef LEN LengthMap;
    929     ///The type of the length of the arcs.
     936    ///The type of the arc lengths.
    930937    typedef typename LEN::Value Value;
    931938
     
    974981    ///The type of the map that stores the predecessor
    975982    ///arcs of the shortest paths.
    976     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     983    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    977984    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    978985    ///Instantiates a PredMap.
     
    989996
    990997    ///The type of the map that indicates which nodes are processed.
    991     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     998    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    992999    ///By default it is a NullMap.
    9931000    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    10091016
    10101017    ///The type of the map that stores the distances of the nodes.
    1011     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1018    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    10121019    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10131020    ///Instantiates a DistMap.
     
    10241031
    10251032    ///The type of the shortest paths.
    1026     ///It must meet the \ref concepts::Path "Path" concept.
     1033    ///It must conform to the \ref concepts::Path "Path" concept.
    10271034    typedef lemon::Path<Digraph> Path;
    10281035  };
     
    10301037  /// Default traits class used by DijkstraWizard
    10311038
    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.
     1039  /// Default traits class used by DijkstraWizard.
     1040  /// \tparam GR The type of the digraph.
     1041  /// \tparam LEN The type of the length map.
    10381042  template<typename GR, typename LEN>
    10391043  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
     
    10941098    typedef TR Base;
    10951099
    1096     ///The type of the digraph the algorithm runs on.
    10971100    typedef typename TR::Digraph Digraph;
    10981101
     
    11021105    typedef typename Digraph::OutArcIt OutArcIt;
    11031106
    1104     ///The type of the map that stores the arc lengths.
    11051107    typedef typename TR::LengthMap LengthMap;
    1106     ///The type of the length of the arcs.
    11071108    typedef typename LengthMap::Value Value;
    1108     ///\brief The type of the map that stores the predecessor
    1109     ///arcs of the shortest paths.
    11101109    typedef typename TR::PredMap PredMap;
    1111     ///The type of the map that stores the distances of the nodes.
    11121110    typedef typename TR::DistMap DistMap;
    1113     ///The type of the map that indicates which nodes are processed.
    11141111    typedef typename TR::ProcessedMap ProcessedMap;
    1115     ///The type of the shortest paths
    11161112    typedef typename TR::Path Path;
    1117     ///The heap type used by the dijkstra algorithm.
    11181113    typedef typename TR::Heap Heap;
    11191114
     
    11871182      SetPredMapBase(const TR &b) : TR(b) {}
    11881183    };
    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.
     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.
    11941190    template<class T>
    11951191    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
     
    12051201      SetDistMapBase(const TR &b) : TR(b) {}
    12061202    };
    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.
     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.
    12121210    template<class T>
    12131211    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     
    12231221      SetProcessedMapBase(const TR &b) : TR(b) {}
    12241222    };
    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.
     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.
    12301229    template<class T>
    12311230    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12401239      SetPathBase(const TR &b) : TR(b) {}
    12411240    };
     1241
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.
  • lemon/dim2.h

    r440 r714  
    2222#include <iostream>
    2323
    24 ///\ingroup misc
     24///\ingroup geomdat
    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.
    3427
    3528namespace lemon {
     
    4134  namespace dim2 {
    4235
    43   /// \addtogroup misc
     36  /// \addtogroup geomdat
    4437  /// @{
    4538
  • lemon/fib_heap.h

    r683 r711  
    2121
    2222///\file
    23 ///\ingroup auxdat
    24 ///\brief Fibonacci Heap implementation.
     23///\ingroup heaps
     24///\brief Fibonacci heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
     
    3031namespace lemon {
    3132
    32   /// \ingroup auxdat
     33  /// \ingroup heaps
    3334  ///
    34   ///\brief Fibonacci Heap.
     35  /// \brief Fibonacci heap data structure.
    3536  ///
    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.
     37  /// This class implements the \e Fibonacci \e heap data structure.
     38  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4139  ///
    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".
     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".
    4543  ///
    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
     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>.
    5449#ifdef DOXYGEN
    55   template <typename PRIO, typename IM, typename CMP>
     50  template <typename PR, typename IM, typename CMP>
    5651#else
    57   template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
     52  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5853#endif
    5954  class FibHeap {
    6055  public:
    61     ///\e
     56
     57    /// Type of the item-int map.
    6258    typedef IM ItemIntMap;
    63     ///\e
    64     typedef PRIO Prio;
    65     ///\e
     59    /// Type of the priorities.
     60    typedef PR Prio;
     61    /// Type of the items stored in the heap.
    6662    typedef typename ItemIntMap::Key Item;
    67     ///\e
     63    /// Type of the item-priority pairs.
    6864    typedef std::pair<Item,Prio> Pair;
    69     ///\e
     65    /// Functor type for comparing the priorities.
    7066    typedef CMP Compare;
    7167
     
    8177  public:
    8278
    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
     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
    8783    /// heap's point of view, but may be useful to the user.
    8884    ///
     
    9591    };
    9692
    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.
     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.
    10199    explicit FibHeap(ItemIntMap &map)
    102100      : _minimum(0), _iim(map), _num() {}
    103101
    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.
     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.
    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     /// Returns the number of items stored in the heap.
     114    /// This function returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Checks if the heap stores no items.
    118     ///
    119     ///   Returns \c true if and only if the heap stores no items.
     117    /// \brief Check if the heap is empty.
     118    ///
     119    /// This function returns \c true if the heap is empty.
    120120    bool empty() const { return _num==0; }
    121121
    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.
     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.
    128129    void clear() {
    129130      _data.clear(); _minimum = 0; _num = 0;
    130131    }
    131132
    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) {
     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) {
    151141      int i=_iim[item];
    152142      if ( i < 0 ) {
     
    169159        _data[_minimum].right_neighbor=i;
    170160        _data[i].left_neighbor=_minimum;
    171         if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
     161        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
    172162      } else {
    173163        _data[i].right_neighbor=_data[i].left_neighbor=i;
    174164        _minimum=i;
    175165      }
    176       _data[i].prio=value;
     166      _data[i].prio=prio;
    177167      ++_num;
    178168    }
    179169
    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.
     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.
    185174    Item top() const { return _data[_minimum].name; }
    186175
    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.
     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.
    205185    /// \pre The heap must be non-empty.
    206186    void pop() {
     
    209189        _data[_minimum].in=false;
    210190        if ( _data[_minimum].degree!=0 ) {
    211           makeroot(_data[_minimum].child);
     191          makeRoot(_data[_minimum].child);
    212192          _minimum=_data[_minimum].child;
    213193          balance();
     
    222202          int last_child=_data[child].left_neighbor;
    223203
    224           makeroot(child);
     204          makeRoot(child);
    225205
    226206          _data[left].right_neighbor=child;
     
    235215    }
    236216
    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.
     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.
    241223    void erase (const Item& item) {
    242224      int i=_iim[item];
     
    253235    }
    254236
    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) {
     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) {
    261255      int i=_iim[item];
    262       _data[i].prio=value;
     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;
    263271      int p=_data[i].parent;
    264272
    265       if ( p!=-1 && _comp(value, _data[p].prio) ) {
     273      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
    266274        cut(i,p);
    267275        cascade(p);
    268276      }
    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) {
     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) {
    280287      erase(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.
     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.
    292299    State state(const Item &item) const {
    293300      int i=_iim[item];
     
    299306    }
    300307
    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.
     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.
    306313    /// \param i The item.
    307314    /// \param st The state. It should not be \c IN_HEAP.
     
    366373    }
    367374
    368     void makeroot(int c) {
     375    void makeRoot(int c) {
    369376      int s=c;
    370377      do {
  • lemon/full_graph.h

    r617 r735  
    2525///\ingroup graphs
    2626///\file
    27 ///\brief FullGraph and FullDigraph classes.
     27///\brief FullDigraph and FullGraph classes.
    2828
    2929namespace lemon {
     
    149149  /// \ingroup graphs
    150150  ///
    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,
     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,
    164166  /// but there are two differences. While this class conforms only
    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.
     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.
    169171  ///
    170172  /// \sa FullGraph
     
    174176  public:
    175177
    176     /// \brief Constructor
     178    /// \brief Default constructor.
     179    ///
     180    /// Default constructor. The number of nodes and arcs will be zero.
    177181    FullDigraph() { construct(0); }
    178182
     
    185189    /// \brief Resizes the digraph
    186190    ///
    187     /// Resizes the digraph. The function will fully destroy and
    188     /// rebuild the digraph. This cause that the maps of the digraph will
     191    /// This function resizes the digraph. It fully destroys and
     192    /// rebuilds the structure, therefore the maps of the digraph will be
    189193    /// reallocated automatically and the previous values will be lost.
    190194    void resize(int n) {
     
    198202    /// \brief Returns the node with the given index.
    199203    ///
    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>.
     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>.
    203207    /// \sa index()
    204208    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    206210    /// \brief Returns the index of the given node.
    207211    ///
    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()
    212     int index(const Node& node) const { return Parent::index(node); }
     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()()
     216    int index(Node node) const { return Parent::index(node); }
    213217
    214218    /// \brief Returns the arc connecting the given nodes.
    215219    ///
    216220    /// Returns the arc connecting the given nodes.
    217     Arc arc(const Node& u, const Node& v) const {
     221    Arc arc(Node u, Node v) const {
    218222      return Parent::arc(u, v);
    219223    }
     
    521525  /// \brief An undirected full graph class.
    522526  ///
    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
     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
    534540  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    535541  /// this class conforms to the \ref concepts::Graph "Graph" concept,
    536   /// moreover \c FullGraph does not contain a loop arc for each
    537   /// node as \c FullDigraph does.
     542  /// moreover this class does not contain a loop for each
     543  /// node as FullDigraph does.
    538544  ///
    539545  /// \sa FullDigraph
     
    543549  public:
    544550
    545     /// \brief Constructor
     551    /// \brief Default constructor.
     552    ///
     553    /// Default constructor. The number of nodes and edges will be zero.
    546554    FullGraph() { construct(0); }
    547555
     
    554562    /// \brief Resizes the graph
    555563    ///
    556     /// Resizes the graph. The function will fully destroy and
    557     /// rebuild the graph. This cause that the maps of the graph will
     564    /// This function resizes the graph. It fully destroys and
     565    /// rebuilds the structure, therefore the maps of the graph will be
    558566    /// reallocated automatically and the previous values will be lost.
    559567    void resize(int n) {
     
    569577    /// \brief Returns the node with the given index.
    570578    ///
    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>.
     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>.
    574582    /// \sa index()
    575583    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    577585    /// \brief Returns the index of the given node.
    578586    ///
    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()
    583     int index(const Node& node) const { return Parent::index(node); }
     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()()
     591    int index(Node node) const { return Parent::index(node); }
    584592
    585593    /// \brief Returns the arc connecting the given nodes.
    586594    ///
    587595    /// Returns the arc connecting the given nodes.
    588     Arc arc(const Node& s, const Node& t) const {
     596    Arc arc(Node s, Node t) const {
    589597      return Parent::arc(s, t);
    590598    }
    591599
    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 {
     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 {
    596604      return Parent::edge(u, v);
    597605    }
  • lemon/glpk.cc

    r576 r746  
    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());
    5995    return i;
    6096  }
  • lemon/glpk.h

    r650 r746  
    5555    virtual int _addCol();
    5656    virtual int _addRow();
     57    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    5758
    5859    virtual void _eraseCol(int i);
  • lemon/gomory_hu.h

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

    r617 r735  
    471471  /// \brief Grid graph class
    472472  ///
    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
     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
    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().
    484488  ///
    485489  /// \image html grid_graph.png
     
    497501  ///\endcode
    498502  ///
    499   /// This graph type fully conforms to the \ref concepts::Graph
    500   /// "Graph concept".
     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.
    501506  class GridGraph : public ExtendedGridGraphBase {
    502507    typedef ExtendedGridGraphBase Parent;
     
    504509  public:
    505510
    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>.
     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>".
    509516    class IndexMap {
    510517    public:
     
    515522
    516523      /// \brief Constructor
    517       ///
    518       /// Constructor
    519524      IndexMap(const GridGraph& graph) : _graph(graph) {}
    520525
    521526      /// \brief The subscript operator
    522       ///
    523       /// The subscript operator.
    524