COIN-OR::LEMON - Graph Library

Ignore:
Files:
10 added
67 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

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

    r676 r840  
    1818        cmake/FindGLPK.cmake \
    1919        cmake/FindCOIN.cmake \
     20        cmake/LEMONConfig.cmake.in \
    2021        cmake/version.cmake.in \
    2122        cmake/version.cmake \
     
    4445include doc/Makefile.am
    4546include tools/Makefile.am
     47include scripts/Makefile.am
    4648
    4749DIST_SUBDIRS = demo
  • configure.ac

    r727 r840  
    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
     
    8283fi
    8384AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
     85
     86dnl Support for running test cases using valgrind.
     87use_valgrind=no
     88AC_ARG_ENABLE([valgrind],
     89AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
     90              [use_valgrind=yes])
     91
     92if [[ "$use_valgrind" = "yes" ]]; then
     93  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
     94
     95  if [[ "$HAVE_VALGRIND" = "no" ]]; then
     96    AC_MSG_ERROR([Valgrind not found in PATH.])
     97  fi
     98fi
     99AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
    84100
    85101dnl Checks for header files.
     
    128144echo
    129145echo Build additional tools........ : $enable_tools
     146echo Use valgrind for tests........ : $use_valgrind
    130147echo
    131148echo The packace will be installed in
  • doc/CMakeLists.txt

    r726 r791  
    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

    r379 r803  
    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

    r720 r791  
    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

    r757 r818  
    281281
    282282/**
     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/**
    283305@defgroup algs Algorithms
    284306\brief This group contains the several algorithms
     
    295317
    296318This group contains the common graph search algorithms, namely
    297 \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.
    298321*/
    299322
     
    303326\brief Algorithms for finding shortest paths.
    304327
    305 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.
    306330
    307331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    320344
    321345/**
     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/**
    322355@defgroup max_flow Maximum Flow Algorithms
    323356@ingroup algs
     
    325358
    326359This group contains the algorithms for finding maximum flows and
    327 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    328361
    329362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    340373
    341374LEMON contains several algorithms for solving maximum flow problems:
    342 - \ref EdmondsKarp Edmonds-Karp algorithm.
    343 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    344 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    345 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    346 
    347 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
    348385fastest method for computing a maximum flow. All implementations
    349386also provide functions to query the minimum cut, which is the dual
     
    363400
    364401This group contains the algorithms for finding minimum cost flows and
    365 circulations. For more information about this problem and its dual
    366 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".
    367405
    368406LEMON contains several algorithms for this problem.
    369407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    370    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    371409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    372    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    373412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    374    capacity scaling.
    375  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    376  - \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.
    377418
    378419In general NetworkSimplex is the most efficient implementation,
     
    397438
    398439\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    399     \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]
    400441
    401442LEMON contains several algorithms related to minimum cut problems:
     
    413454
    414455/**
    415 @defgroup graph_properties Connectivity and Other Graph Properties
    416 @ingroup algs
    417 \brief Algorithms for discovering the graph properties
    418 
    419 This group contains the algorithms for discovering the graph properties
    420 like connectivity, bipartiteness, euler property, simplicity etc.
    421 
    422 \image html edge_biconnected_components.png
    423 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    424 */
    425 
    426 /**
    427 @defgroup planar Planarity Embedding and Drawing
    428 @ingroup algs
    429 \brief Algorithms for planarity checking, embedding and drawing
    430 
    431 This group contains the algorithms for planarity checking,
    432 embedding and drawing.
    433 
    434 \image html planar.png
    435 \image latex planar.eps "Plane graph" width=\textwidth
     456@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     457@ingroup algs
     458\brief Algorithms for finding minimum mean cycles.
     459
     460This group contains the algorithms for finding minimum mean cycles
     461\ref clrs01algorithms, \ref amo93networkflows.
     462
     463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     464of minimum mean length (cost) in a digraph.
     465The mean length of a cycle is the average length of its arcs, i.e. the
     466ratio between the total length of the cycle and the number of arcs on it.
     467
     468This problem has an important connection to \e conservative \e length
     469\e functions, too. A length function on the arcs of a digraph is called
     470conservative if and only if there is no directed cycle of negative total
     471length. For an arbitrary length function, the negative of the minimum
     472cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     473arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     474function.
     475
     476LEMON contains three algorithms for solving the minimum mean cycle problem:
     477- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     478  \ref dasdan98minmeancycle.
     479- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     480  version of Karp's algorithm \ref dasdan98minmeancycle.
     481- \ref Howard "Howard"'s policy iteration algorithm
     482  \ref dasdan98minmeancycle.
     483
     484In practice, the Howard algorithm proved to be by far the most efficient
     485one, though the best known theoretical bound on its running time is
     486exponential.
     487Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     488O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     489applied early termination scheme.
    436490*/
    437491
     
    477531
    478532/**
    479 @defgroup spantree Minimum Spanning Tree Algorithms
    480 @ingroup algs
    481 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    482 
    483 This group contains the algorithms for finding minimum cost spanning
    484 trees and arborescences.
     533@defgroup graph_properties Connectivity and Other Graph Properties
     534@ingroup algs
     535\brief Algorithms for discovering the graph properties
     536
     537This group contains the algorithms for discovering the graph properties
     538like connectivity, bipartiteness, euler property, simplicity etc.
     539
     540\image html connected_components.png
     541\image latex connected_components.eps "Connected components" width=\textwidth
     542*/
     543
     544/**
     545@defgroup planar Planarity Embedding and Drawing
     546@ingroup algs
     547\brief Algorithms for planarity checking, embedding and drawing
     548
     549This group contains the algorithms for planarity checking,
     550embedding and drawing.
     551
     552\image html planar.png
     553\image latex planar.eps "Plane graph" width=\textwidth
     554*/
     555
     556/**
     557@defgroup approx Approximation Algorithms
     558@ingroup algs
     559\brief Approximation algorithms.
     560
     561This group contains the approximation and heuristic algorithms
     562implemented in LEMON.
    485563*/
    486564
     
    492570This group contains some algorithms implemented in LEMON
    493571in order to make it easier to implement complex algorithms.
    494 */
    495 
    496 /**
    497 @defgroup approx Approximation Algorithms
    498 @ingroup algs
    499 \brief Approximation algorithms.
    500 
    501 This group contains the approximation and heuristic algorithms
    502 implemented in LEMON.
    503572*/
    504573
     
    513582
    514583/**
    515 @defgroup lp_group Lp and Mip Solvers
     584@defgroup lp_group LP and MIP Solvers
    516585@ingroup gen_opt_group
    517 \brief Lp and Mip solver interfaces for LEMON.
    518 
    519 This group contains Lp and Mip solver interfaces for LEMON. The
    520 various LP solvers could be used in the same manner with this
    521 interface.
     586\brief LP and MIP solver interfaces for LEMON.
     587
     588This group contains LP and MIP solver interfaces for LEMON.
     589Various LP solvers could be used in the same manner with this
     590high-level interface.
     591
     592The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     593\ref cplex, \ref soplex.
    522594*/
    523595
     
    609681
    610682/**
    611 @defgroup dimacs_group DIMACS format
     683@defgroup dimacs_group DIMACS Format
    612684@ingroup io_group
    613685\brief Read and write files in DIMACS format
     
    658730\brief Skeleton and concept checking classes for graph structures
    659731
    660 This group contains the skeletons and concept checking classes of LEMON's
    661 graph structures and helper classes used to implement these.
     732This group contains the skeletons and concept checking classes of
     733graph structures.
    662734*/
    663735
     
    671743
    672744/**
     745@defgroup tools Standalone Utility Applications
     746
     747Some utility applications are listed here.
     748
     749The standard compilation procedure (<tt>./configure;make</tt>) will compile
     750them, as well.
     751*/
     752
     753/**
    673754\anchor demoprograms
    674755
     
    682763*/
    683764
    684 /**
    685 @defgroup tools Standalone Utility Applications
    686 
    687 Some utility applications are listed here.
    688 
    689 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    690 them, as well.
    691 */
    692 
    693765}
  • doc/mainpage.dox

    r705 r802  
    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

    r710 r835  
    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$,
     
    7979   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    8080 - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)<=0\f$;
     81   - \f$\pi(u)\leq 0\f$;
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
     
    146146   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    147147 - For all \f$u\in V\f$ nodes:
    148    - \f$\pi(u)>=0\f$;
     148   - \f$\pi(u)\geq 0\f$;
    149149   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    150150     then \f$\pi(u)=0\f$.
  • lemon/Makefile.am

    r861 r863  
    8787        lemon/graph_to_eps.h \
    8888        lemon/grid_graph.h \
     89        lemon/hartmann_orlin.h \
     90        lemon/howard.h \
    8991        lemon/hypercube_graph.h \
     92        lemon/karp.h \
    9093        lemon/kary_heap.h \
    9194        lemon/kruskal.h \
     
    112115        lemon/smart_graph.h \
    113116        lemon/soplex.h \
     117        lemon/static_graph.h \
    114118        lemon/suurballe.h \
    115119        lemon/time_measure.h \
  • lemon/adaptors.h

    r703 r834  
    361361  /// parameter is set to be \c const.
    362362  ///
     363  /// This class provides item counting in the same time as the adapted
     364  /// digraph structure.
     365  ///
    363366  /// \tparam DGR The type of the adapted digraph.
    364367  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    719722  /// by adding or removing nodes or arcs, unless the \c GR template
    720723  /// parameter is set to be \c const.
     724  ///
     725  /// This class provides only linear time counting for nodes and arcs.
    721726  ///
    722727  /// \tparam DGR The type of the adapted digraph.
     
    13151320  /// parameter is set to be \c const.
    13161321  ///
     1322  /// This class provides only linear time counting for nodes, edges and arcs.
     1323  ///
    13171324  /// \tparam GR The type of the adapted graph.
    13181325  /// It must conform to the \ref concepts::Graph "Graph" concept.
     
    14711478  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14721479  /// parameter is set to be \c const.
     1480  ///
     1481  /// This class provides only linear time item counting.
    14731482  ///
    14741483  /// \tparam GR The type of the adapted digraph or graph.
     
    16201629  /// parameter is set to be \c const.
    16211630  ///
     1631  /// This class provides only linear time counting for nodes and arcs.
     1632  ///
    16221633  /// \tparam DGR The type of the adapted digraph.
    16231634  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    17291740  /// by adding or removing nodes or edges, unless the \c GR template
    17301741  /// parameter is set to be \c const.
     1742  ///
     1743  /// This class provides only linear time counting for nodes, edges and arcs.
    17311744  ///
    17321745  /// \tparam GR The type of the adapted graph.
     
    22332246  /// parameter is set to be \c const.
    22342247  ///
     2248  /// This class provides item counting in the same time as the adapted
     2249  /// digraph structure.
     2250  ///
    22352251  /// \tparam DGR The type of the adapted digraph.
    22362252  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    25352551  /// by adding or removing nodes or arcs, unless the \c GR template
    25362552  /// parameter is set to be \c const.
     2553  ///
     2554  /// This class provides item counting in the same time as the adapted
     2555  /// graph structure.
    25372556  ///
    25382557  /// \tparam GR The type of the adapted graph.
     
    26782697  /// arcs).
    26792698  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
     2699  ///
     2700  /// This class provides only linear time counting for nodes and arcs.
    26802701  ///
    26812702  /// \tparam DGR The type of the adapted digraph.
     
    33263347  /// in the adaptor.
    33273348  ///
     3349  /// This class provides item counting in the same time as the adapted
     3350  /// digraph structure.
     3351  ///
    33283352  /// \tparam DGR The type of the adapted digraph.
    33293353  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
  • lemon/bellman_ford.h

    r746 r835  
    2424/// \brief Bellman-Ford algorithm.
    2525
     26#include <lemon/list_graph.h>
    2627#include <lemon/bits/path_dump.h>
    2728#include <lemon/core.h>
     
    300301    /// \ref named-templ-param "Named parameter" for setting
    301302    /// \c OperationTraits type.
    302     /// For more information see \ref BellmanFordDefaultOperationTraits.
     303    /// For more information, see \ref BellmanFordDefaultOperationTraits.
    303304    template <class T>
    304305    struct SetOperationTraits
     
    718719    ///
    719720    /// The shortest path tree used here is equal to the shortest path
    720     /// tree used in \ref predNode() and \predMap().
     721    /// tree used in \ref predNode() and \ref predMap().
    721722    ///
    722723    /// \pre Either \ref run() or \ref init() must be called before
     
    733734    ///
    734735    /// The shortest path tree used here is equal to the shortest path
    735     /// tree used in \ref predArc() and \predMap().
     736    /// tree used in \ref predArc() and \ref predMap().
    736737    ///
    737738    /// \pre Either \ref run() or \ref init() must be called before
     
    776777    /// length if the algorithm has already found one.
    777778    /// Otherwise it gives back an empty path.
    778     lemon::Path<Digraph> negativeCycle() {
     779    lemon::Path<Digraph> negativeCycle() const {
    779780      typename Digraph::template NodeMap<int> state(*_gr, -1);
    780781      lemon::Path<Digraph> cycle;
  • lemon/bfs.h

    r525 r835  
    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.
     
    701702    ///Runs the algorithm to visit all nodes in the digraph.
    702703
    703     ///This method runs the %BFS algorithm in order to
    704     ///compute the shortest path to each node.
    705     ///
    706     ///The algorithm computes
    707     ///- the shortest path tree (forest),
    708     ///- the distance of each node from the root(s).
     704    ///This method runs the %BFS algorithm in order to visit all nodes
     705    ///in the digraph.
    709706    ///
    710707    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    738735    ///@{
    739736
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     737    ///The shortest path to the given node.
     738
     739    ///Returns the shortest path to the given node from the root(s).
    743740    ///
    744741    ///\warning \c t should be reached from the root(s).
     
    748745    Path path(Node t) const { return Path(*G, *_pred, t); }
    749746
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     747    ///The distance of the given node from the root(s).
     748
     749    ///Returns the distance of the given node from the root(s).
    753750    ///
    754751    ///\warning If node \c v is not reached from the root(s), then
     
    759756    int dist(Node v) const { return (*_dist)[v]; }
    760757
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     758    ///\brief Returns the 'previous arc' of the shortest path tree for
     759    ///the given node.
     760    ///
    763761    ///This function returns the 'previous arc' of the shortest path
    764762    ///tree for the node \c v, i.e. it returns the last arc of a
     
    767765    ///
    768766    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     767    ///tree used in \ref predNode() and \ref predMap().
    770768    ///
    771769    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    773771    Arc predArc(Node v) const { return (*_pred)[v];}
    774772
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     773    ///\brief Returns the 'previous node' of the shortest path tree for
     774    ///the given node.
     775    ///
    777776    ///This function returns the 'previous node' of the shortest path
    778777    ///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
     778    ///of a shortest path from a root to \c v. It is \c INVALID
    780779    ///if \c v is not reached from the root(s) or if \c v is a root.
    781780    ///
    782781    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     782    ///tree used in \ref predArc() and \ref predMap().
    784783    ///
    785784    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    802801    ///
    803802    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     803    ///arcs, which form the shortest path tree (forest).
    805804    ///
    806805    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808807    const PredMap &predMap() const { return *_pred;}
    809808
    810     ///Checks if a node is reached from the root(s).
     809    ///Checks if the given node is reached from the root(s).
    811810
    812811    ///Returns \c true if \c v is reached from the root(s).
     
    834833    ///The type of the map that stores the predecessor
    835834    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     835    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837836    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838837    ///Instantiates a PredMap.
     
    849848
    850849    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    852     ///By default it is a NullMap.
     850    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     851    ///By default, it is a NullMap.
    853852    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    854853    ///Instantiates a ProcessedMap.
     
    869868
    870869    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     870    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872871    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873872    ///Instantiates a ReachedMap.
     
    884883
    885884    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     885    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887886    typedef typename Digraph::template NodeMap<int> DistMap;
    888887    ///Instantiates a DistMap.
     
    899898
    900899    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     900    ///It must conform to the \ref concepts::Path "Path" concept.
    902901    typedef lemon::Path<Digraph> Path;
    903902  };
     
    905904  /// Default traits class used by BfsWizard
    906905
    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.
     906  /// Default traits class used by BfsWizard.
     907  /// \tparam GR The type of the digraph.
    913908  template<class GR>
    914909  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    938933    /// Constructor.
    939934
    940     /// This constructor does not require parameters, therefore it initiates
     935    /// This constructor does not require parameters, it initiates
    941936    /// all of the attributes to \c 0.
    942937    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    968963    typedef TR Base;
    969964
    970     ///The type of the digraph the algorithm runs on.
    971965    typedef typename TR::Digraph Digraph;
    972966
     
    976970    typedef typename Digraph::OutArcIt OutArcIt;
    977971
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980972    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982973    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984974    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986975    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988976    typedef typename TR::Path Path;
    989977
     
    10551043    ///Runs BFS algorithm to visit all nodes in the digraph.
    10561044
    1057     ///This method runs BFS algorithm in order to compute
    1058     ///the shortest path to each node.
     1045    ///This method runs BFS algorithm in order to visit all nodes
     1046    ///in the digraph.
    10591047    void run()
    10601048    {
     
    10681056      SetPredMapBase(const TR &b) : TR(b) {}
    10691057    };
    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.
     1058
     1059    ///\brief \ref named-templ-param "Named parameter" for setting
     1060    ///the predecessor map.
     1061    ///
     1062    ///\ref named-templ-param "Named parameter" function for setting
     1063    ///the map that stores the predecessor arcs of the nodes.
    10751064    template<class T>
    10761065    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861075      SetReachedMapBase(const TR &b) : TR(b) {}
    10871076    };
    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.
     1077
     1078    ///\brief \ref named-templ-param "Named parameter" for setting
     1079    ///the reached map.
     1080    ///
     1081    ///\ref named-templ-param "Named parameter" function for setting
     1082    ///the map that indicates which nodes are reached.
    10931083    template<class T>
    10941084    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11041094      SetDistMapBase(const TR &b) : TR(b) {}
    11051095    };
    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.
     1096
     1097    ///\brief \ref named-templ-param "Named parameter" for setting
     1098    ///the distance map.
     1099    ///
     1100    ///\ref named-templ-param "Named parameter" function for setting
     1101    ///the map that stores the distances of the nodes calculated
     1102    ///by the algorithm.
    11111103    template<class T>
    11121104    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11221114      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231115    };
    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.
     1116
     1117    ///\brief \ref named-func-param "Named parameter" for setting
     1118    ///the processed map.
     1119    ///
     1120    ///\ref named-templ-param "Named parameter" function for setting
     1121    ///the map that indicates which nodes are processed.
    11291122    template<class T>
    11301123    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12651258    ///
    12661259    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1260    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681261    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691262
     
    14261419    /// The simplest way to execute the BFS algorithm is to use one of the
    14271420    /// 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
     1421    /// If you need better control on the execution, you have to call
     1422    /// \ref init() first, then you can add several source nodes with
    14301423    /// \ref addSource(). Finally the actual path computation can be
    14311424    /// performed with one of the \ref start() functions.
     
    16991692    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17001693    ///
    1701     /// This method runs the %BFS algorithm in order to
    1702     /// compute the shortest path to each node.
    1703     ///
    1704     /// The algorithm computes
    1705     /// - the shortest path tree (forest),
    1706     /// - the distance of each node from the root(s).
     1694    /// This method runs the %BFS algorithm in order to visit all nodes
     1695    /// in the digraph.
    17071696    ///
    17081697    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     
    17361725    ///@{
    17371726
    1738     /// \brief Checks if a node is reached from the root(s).
     1727    /// \brief Checks if the given node is reached from the root(s).
    17391728    ///
    17401729    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bits/graph_extender.h

    r732 r825  
    5757    }
    5858
    59     Node fromId(int id, Node) const {
     59    static Node fromId(int id, Node) {
    6060      return Parent::nodeFromId(id);
    6161    }
    6262
    63     Arc fromId(int id, Arc) const {
     63    static Arc fromId(int id, Arc) {
    6464      return Parent::arcFromId(id);
    6565    }
     
    356356    }
    357357
    358     Node fromId(int id, Node) const {
     358    static Node fromId(int id, Node) {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     Arc fromId(int id, Arc) const {
     362    static Arc fromId(int id, Arc) {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     Edge fromId(int id, Edge) const {
     366    static Edge fromId(int id, Edge) {
    367367      return Parent::edgeFromId(id);
    368368    }
  • lemon/bits/map_extender.h

    r664 r765  
    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/cbc.cc

    r623 r793  
    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

    r623 r793  
    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

    r736 r833  
    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.
     
    300307    /// able to automatically created by the algorithm (i.e. the
    301308    /// digraph and the maximum level should be passed to it).
    302     /// However an external elevator object could also be passed to the
     309    /// However, an external elevator object could also be passed to the
    303310    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    304311    /// before calling \ref run() or \ref init().
     
    470477    /// \name Execution Control
    471478    /// The simplest way to execute the algorithm is to call \ref run().\n
    472     /// If you need more control on the initial solution or the execution,
    473     /// 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
    474481    /// the \ref start() function.
    475482
  • lemon/clp.cc

    r623 r793  
    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

    r623 r793  
    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

    r627 r833  
    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.
    117       /// 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:
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
     110      /// Its usage is quite simple, for example, you can count the number
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    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
    207198      /// of a digraph.
    208       /// Its usage is quite simple, for example you can count the number
     199      /// 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.
    255       /// 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.
     244      /// Its usage is quite simple, for example, you can count the number
     245      /// of incoming arcs of a node \c n
     246      /// in a digraph \c g of type \c %Digraph as follows.
    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.
    300       /// 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:
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
     288      /// Its usage is quite simple, for example, you can count the number
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    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

    r704 r833  
    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.
    130       /// 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:
     140      /// Iterator class for the nodes.
     141
     142      /// This iterator goes through each node of the graph.
     143      /// Its usage is quite simple, for example, you can count the number
     144      /// of nodes in a graph \c g of type \c %Graph like this:
    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.
    219       /// 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:
     228      /// Iterator class for the edges.
     229
     230      /// This iterator goes through each edge of the graph.
     231      /// Its usage is quite simple, for example, you can count the number
     232      /// of edges in a graph \c g of type \c %Graph as follows:
    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       ///
    266       /// 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.
     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.
     275      /// Its usage is quite simple, for example, you can compute the
     276      /// degree (i.e. the number of incident edges) of a node \c n
     277      /// in a graph \c g of type \c %Graph as follows.
    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.
    358       /// 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:
     368
     369      /// Iterator class for the arcs.
     370
     371      /// This iterator goes through each directed arc of the graph.
     372      /// Its usage is quite simple, for example, you can count the number
     373      /// of arcs in a graph \c g of type \c %Graph as follows:
    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.
    402       /// Its usage is quite simple, for example you can count the number
     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.
     416      /// 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.
    454       /// 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.
     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.
     464      /// Its usage is quite simple, for example, you can count the number
     465      /// of incoming arcs of a node \c n
     466      /// in a graph \c g of type \c %Graph as follows.
    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

    r713 r833  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of graph components.
     21///\brief The concepts of graph components.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     
    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/maps.h

    r576 r765  
    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/concepts/path.h

    r606 r832  
    1919///\ingroup concept
    2020///\file
    21 ///\brief Classes for representing paths in digraphs.
     21///\brief The concept of paths
    2222///
    2323
     
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
     41    /// In a sense, a path can be treated as a list of arcs.
     42    /// LEMON path types just store this list. As a consequence, they cannot
     43    /// enumerate the nodes on the path directly and a zero length path
     44    /// cannot store its source node.
     45    ///
     46    /// The arcs of a path should be stored in the order of their directions,
     47    /// i.e. the target node of each arc should be the same as the source
     48    /// node of the next arc. This consistency could be checked using
     49    /// \ref checkPath().
     50    /// The source and target nodes of a (consistent) path can be obtained
     51    /// using \ref pathSource() and \ref pathTarget().
     52    ///
     53    /// A path can be constructed from another path of any type using the
     54    /// copy constructor or the assignment operator.
     55    ///
    4156    /// \tparam GR The digraph type in which the path is.
    42     ///
    43     /// In a sense, the path can be treated as a list of arcs. The
    44     /// lemon path type stores just this list. As a consequence it
    45     /// cannot enumerate the nodes in the path and the zero length
    46     /// paths cannot store the source.
    47     ///
    4857    template <typename GR>
    4958    class Path {
     
    6069      Path() {}
    6170
    62       /// \brief Template constructor
     71      /// \brief Template copy constructor
    6372      template <typename CPath>
    6473      Path(const CPath& cpath) {}
    6574
    66       /// \brief Template assigment
     75      /// \brief Template assigment operator
    6776      template <typename CPath>
    6877      Path& operator=(const CPath& cpath) {
     
    7180      }
    7281
    73       /// Length of the path ie. the number of arcs in the path.
     82      /// Length of the path, i.e. the number of arcs on the path.
    7483      int length() const { return 0;}
    7584
     
    8089      void clear() {}
    8190
    82       /// \brief LEMON style iterator for path arcs
     91      /// \brief LEMON style iterator for enumerating the arcs of a path.
    8392      ///
    84       /// This class is used to iterate on the arcs of the paths.
     93      /// LEMON style iterator class for enumerating the arcs of a path.
    8594      class ArcIt {
    8695      public:
     
    8998        /// Invalid constructor
    9099        ArcIt(Invalid) {}
    91         /// Constructor for first arc
     100        /// Sets the iterator to the first arc of the given path
    92101        ArcIt(const Path &) {}
    93102
    94         /// Conversion to Arc
     103        /// Conversion to \c Arc
    95104        operator Arc() const { return INVALID; }
    96105
     
    193202    ///
    194203    /// A skeleton structure for path dumpers. The path dumpers are
    195     /// the generalization of the paths. The path dumpers can
    196     /// enumerate the arcs of the path wheter in forward or in
    197     /// backward order.  In most time these classes are not used
    198     /// directly rather it used to assign a dumped class to a real
    199     /// path type.
     204    /// the generalization of the paths, they can enumerate the arcs
     205    /// of the path either in forward or in backward order.
     206    /// These classes are typically not used directly, they are rather
     207    /// used to be assigned to a real path type.
    200208    ///
    201209    /// The main purpose of this concept is that the shortest path
    202     /// algorithms can enumerate easily the arcs in reverse order.
    203     /// If we would like to give back a real path from these
    204     /// algorithms then we should create a temporarly path object. In
    205     /// LEMON such algorithms gives back a path dumper what can
    206     /// assigned to a real path and the dumpers can be implemented as
     210    /// algorithms can enumerate the arcs easily in reverse order.
     211    /// In LEMON, such algorithms give back a (reverse) path dumper that
     212    /// can be assigned to a real path. The dumpers can be implemented as
    207213    /// an adaptor class to the predecessor map.
    208214    ///
    209215    /// \tparam GR The digraph type in which the path is.
    210     ///
    211     /// The paths can be constructed from any path type by a
    212     /// template constructor or a template assignment operator.
    213216    template <typename GR>
    214217    class PathDumper {
     
    220223      typedef typename Digraph::Arc Arc;
    221224
    222       /// Length of the path ie. the number of arcs in the path.
     225      /// Length of the path, i.e. the number of arcs on the path.
    223226      int length() const { return 0;}
    224227
     
    228231      /// \brief Forward or reverse dumping
    229232      ///
    230       /// If the RevPathTag is defined and true then reverse dumping
    231       /// is provided in the path dumper. In this case instead of the
    232       /// ArcIt the RevArcIt iterator should be implemented in the
    233       /// dumper.
     233      /// If this tag is defined to be \c True, then reverse dumping
     234      /// is provided in the path dumper. In this case, \c RevArcIt
     235      /// iterator should be implemented instead of \c ArcIt iterator.
    234236      typedef False RevPathTag;
    235237
    236       /// \brief LEMON style iterator for path arcs
     238      /// \brief LEMON style iterator for enumerating the arcs of a path.
    237239      ///
    238       /// This class is used to iterate on the arcs of the paths.
     240      /// LEMON style iterator class for enumerating the arcs of a path.
    239241      class ArcIt {
    240242      public:
     
    243245        /// Invalid constructor
    244246        ArcIt(Invalid) {}
    245         /// Constructor for first arc
     247        /// Sets the iterator to the first arc of the given path
    246248        ArcIt(const PathDumper&) {}
    247249
    248         /// Conversion to Arc
     250        /// Conversion to \c Arc
    249251        operator Arc() const { return INVALID; }
    250252
     
    261263      };
    262264
    263       /// \brief LEMON style iterator for path arcs
     265      /// \brief LEMON style iterator for enumerating the arcs of a path
     266      /// in reverse direction.
    264267      ///
    265       /// This class is used to iterate on the arcs of the paths in
    266       /// reverse direction.
     268      /// LEMON style iterator class for enumerating the arcs of a path
     269      /// in reverse direction.
    267270      class RevArcIt {
    268271      public:
     
    271274        /// Invalid constructor
    272275        RevArcIt(Invalid) {}
    273         /// Constructor for first arc
     276        /// Sets the iterator to the last arc of the given path
    274277        RevArcIt(const PathDumper &) {}
    275278
    276         /// Conversion to Arc
     279        /// Conversion to \c Arc
    277280        operator Arc() const { return INVALID; }
    278281
  • lemon/counter.h

    r463 r833  
    213213  /// 'Do nothing' version of Counter.
    214214
    215   /// This class can be used in the same way as \ref Counter however it
     215  /// This class can be used in the same way as \ref Counter, but it
    216216  /// does not count at all and does not print report on destruction.
    217217  ///
  • lemon/cplex.cc

    r623 r793  
    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

    r623 r793  
    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

    r631 r835  
    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
     
    633634    ///Runs the algorithm to visit all nodes in the digraph.
    634635
    635     ///This method runs the %DFS algorithm in order to compute the
    636     ///%DFS path to each node.
    637     ///
    638     ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     636    ///This method runs the %DFS algorithm in order to visit all nodes
     637    ///in the digraph.
    641638    ///
    642639    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
     
    670667    ///@{
    671668
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     669    ///The DFS path to the given node.
     670
     671    ///Returns the DFS path to the given node from the root(s).
    675672    ///
    676673    ///\warning \c t should be reached from the root(s).
     
    680677    Path path(Node t) const { return Path(*G, *_pred, t); }
    681678
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     679    ///The distance of the given node from the root(s).
     680
     681    ///Returns the distance of the given node from the root(s).
    685682    ///
    686683    ///\warning If node \c v is not reached from the root(s), then
     
    691688    int dist(Node v) const { return (*_dist)[v]; }
    692689
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     690    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694691
    695692    ///This function returns the 'previous arc' of the %DFS tree for the
     
    699696    ///
    700697    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     698    ///\ref predNode() and \ref predMap().
    702699    ///
    703700    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    705702    Arc predArc(Node v) const { return (*_pred)[v];}
    706703
    707     ///Returns the 'previous node' of the %DFS tree.
     704    ///Returns the 'previous node' of the %DFS tree for the given node.
    708705
    709706    ///This function returns the 'previous node' of the %DFS
    710707    ///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
     708    ///of a %DFS path from a root to \c v. It is \c INVALID
    712709    ///if \c v is not reached from the root(s) or if \c v is a root.
    713710    ///
    714711    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     712    ///\ref predArc() and \ref predMap().
    716713    ///
    717714    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    734731    ///
    735732    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     733    ///arcs, which form the DFS tree (forest).
    737734    ///
    738735    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    740737    const PredMap &predMap() const { return *_pred;}
    741738
    742     ///Checks if a node is reached from the root(s).
     739    ///Checks if the given node. node is reached from the root(s).
    743740
    744741    ///Returns \c true if \c v is reached from the root(s).
     
    766763    ///The type of the map that stores the predecessor
    767764    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     765    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769766    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770767    ///Instantiates a PredMap.
     
    781778
    782779    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    784     ///By default it is a NullMap.
     780    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     781    ///By default, it is a NullMap.
    785782    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    786783    ///Instantiates a ProcessedMap.
     
    801798
    802799    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     800    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804801    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805802    ///Instantiates a ReachedMap.
     
    816813
    817814    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     815    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819816    typedef typename Digraph::template NodeMap<int> DistMap;
    820817    ///Instantiates a DistMap.
     
    831828
    832829    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     830    ///It must conform to the \ref concepts::Path "Path" concept.
    834831    typedef lemon::Path<Digraph> Path;
    835832  };
     
    837834  /// Default traits class used by DfsWizard
    838835
    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.
     836  /// Default traits class used by DfsWizard.
     837  /// \tparam GR The type of the digraph.
    845838  template<class GR>
    846839  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870863    /// Constructor.
    871864
    872     /// This constructor does not require parameters, therefore it initiates
     865    /// This constructor does not require parameters, it initiates
    873866    /// all of the attributes to \c 0.
    874867    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    900893    typedef TR Base;
    901894
    902     ///The type of the digraph the algorithm runs on.
    903895    typedef typename TR::Digraph Digraph;
    904896
     
    908900    typedef typename Digraph::OutArcIt OutArcIt;
    909901
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912902    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914903    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916904    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918905    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920906    typedef typename TR::Path Path;
    921907
     
    987973    ///Runs DFS algorithm to visit all nodes in the digraph.
    988974
    989     ///This method runs DFS algorithm in order to compute
    990     ///the DFS path to each node.
     975    ///This method runs DFS algorithm in order to visit all nodes
     976    ///in the digraph.
    991977    void run()
    992978    {
     
    1000986      SetPredMapBase(const TR &b) : TR(b) {}
    1001987    };
    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.
     988
     989    ///\brief \ref named-templ-param "Named parameter" for setting
     990    ///the predecessor map.
     991    ///
     992    ///\ref named-templ-param "Named parameter" function for setting
     993    ///the map that stores the predecessor arcs of the nodes.
    1007994    template<class T>
    1008995    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181005      SetReachedMapBase(const TR &b) : TR(b) {}
    10191006    };
    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.
     1007
     1008    ///\brief \ref named-templ-param "Named parameter" for setting
     1009    ///the reached map.
     1010    ///
     1011    ///\ref named-templ-param "Named parameter" function for setting
     1012    ///the map that indicates which nodes are reached.
    10251013    template<class T>
    10261014    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361024      SetDistMapBase(const TR &b) : TR(b) {}
    10371025    };
    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.
     1026
     1027    ///\brief \ref named-templ-param "Named parameter" for setting
     1028    ///the distance map.
     1029    ///
     1030    ///\ref named-templ-param "Named parameter" function for setting
     1031    ///the map that stores the distances of the nodes calculated
     1032    ///by the algorithm.
    10431033    template<class T>
    10441034    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541044      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551045    };
    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.
     1046
     1047    ///\brief \ref named-func-param "Named parameter" for setting
     1048    ///the processed map.
     1049    ///
     1050    ///\ref named-templ-param "Named parameter" function for setting
     1051    ///the map that indicates which nodes are processed.
    10611052    template<class T>
    10621053    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12091200    ///
    12101201    /// The type of the map that indicates which nodes are reached.
    1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1202    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12121203    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12131204
     
    13701361    /// The simplest way to execute the DFS algorithm is to use one of the
    13711362    /// 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()
     1363    /// If you need better control on the execution, you have to call
     1364    /// \ref init() first, then you can add a source node with \ref addSource()
    13741365    /// and perform the actual computation with \ref start().
    13751366    /// This procedure can be repeated if there are nodes that have not
     
    15841575    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15851576
    1586     /// This method runs the %DFS algorithm in order to
    1587     /// compute the %DFS path to each node.
    1588     ///
    1589     /// The algorithm computes
    1590     /// - the %DFS tree (forest),
    1591     /// - the distance of each node from the root(s) in the %DFS tree.
     1577    /// This method runs the %DFS algorithm in order to visit all nodes
     1578    /// in the digraph.
    15921579    ///
    15931580    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     
    16211608    ///@{
    16221609
    1623     /// \brief Checks if a node is reached from the root(s).
     1610    /// \brief Checks if the given node is reached from the root(s).
    16241611    ///
    16251612    /// Returns \c true if \c v is reached from the root(s).
  • lemon/dijkstra.h

    r631 r835  
    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.
    135     ///By default it is a NullMap.
     134    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     135    ///By default, it is a NullMap.
    136136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    137137    ///Instantiates a \c 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.
    205     typedef typename TR::LengthMap::Value Value;
     208    ///The type of the arc lengths.
     209    typedef typename TR::Value Value;
    206210    ///The type of the map that stores the arc lengths.
    207211    typedef typename TR::LengthMap LengthMap;
     
    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
     
    423427    ///passed to the constructor of the cross reference and the cross
    424428    ///reference should be passed to the constructor of the heap).
    425     ///However external heap and cross reference objects could also be
     429    ///However, external heap and cross reference objects could also be
    426430    ///passed to the algorithm using the \ref heap() function before
    427431    ///calling \ref run(Node) "run()" or \ref init().
     
    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.
    992     ///By default it is a NullMap.
     998    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     999    ///By default, it is a NullMap.
    9931000    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    9941001    ///Instantiates a 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

    r463 r761  
    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/edge_set.h

    r717 r834  
    256256  /// all arcs incident to the given node is erased from the arc set.
    257257  ///
     258  /// This class fully conforms to the \ref concepts::Digraph
     259  /// "Digraph" concept.
     260  /// It provides only linear time counting for nodes and arcs.
     261  ///
    258262  /// \param GR The type of the graph which shares its node set with
    259263  /// this class. Its interface must conform to the
    260264  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    261265  /// concept.
    262   ///
    263   /// This class fully conforms to the \ref concepts::Digraph
    264   /// "Digraph" concept.
    265266  template <typename GR>
    266267  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
     
    686687  /// incident to the given node is erased from the arc set.
    687688  ///
     689  /// This class fully conforms to the \ref concepts::Graph "Graph"
     690  /// concept.
     691  /// It provides only linear time counting for nodes, edges and arcs.
     692  ///
    688693  /// \param GR The type of the graph which shares its node set
    689694  /// with this class. Its interface must conform to the
    690695  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    691   /// concept.
    692   ///
    693   /// This class fully conforms to the \ref concepts::Graph "Graph"
    694696  /// concept.
    695697  template <typename GR>
     
    868870    }
    869871
    870     void next(Arc& arc) const {
     872    static void next(Arc& arc) {
    871873      --arc.id;
    872874    }
     
    955957  /// arcs. Therefore the arcs cannot be erased from the arc sets.
    956958  ///
     959  /// This class fully conforms to the \ref concepts::Digraph "Digraph"
     960  /// concept.
     961  /// It provides only linear time counting for nodes and arcs.
     962  ///
    957963  /// \warning If a node is erased from the underlying graph and this
    958964  /// node is the source or target of one arc in the arc set, then
    959965  /// the arc set is invalidated, and it cannot be used anymore. The
    960966  /// validity can be checked with the \c valid() member function.
    961   ///
    962   /// This class fully conforms to the \ref concepts::Digraph
    963   /// "Digraph" concept.
    964967  template <typename GR>
    965968  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
     
    11741177    }
    11751178
    1176     void next(Arc& arc) const {
     1179    static void next(Arc& arc) {
    11771180      --arc.id;
    11781181    }
     
    11821185    }
    11831186
    1184     void next(Edge& arc) const {
     1187    static void next(Edge& arc) {
    11851188      --arc.id;
    11861189    }
     
    13051308  /// edges cannot be erased from the edge sets.
    13061309  ///
     1310  /// This class fully conforms to the \ref concepts::Graph "Graph"
     1311  /// concept.
     1312  /// It provides only linear time counting for nodes, edges and arcs.
     1313  ///
    13071314  /// \warning If a node is erased from the underlying graph and this
    13081315  /// node is incident to one edge in the edge set, then the edge set
    13091316  /// is invalidated, and it cannot be used anymore. The validity can
    13101317  /// be checked with the \c valid() member function.
    1311   ///
    1312   /// This class fully conforms to the \ref concepts::Graph
    1313   /// "Graph" concept.
    13141318  template <typename GR>
    13151319  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  • lemon/full_graph.h

    r664 r834  
    2525///\ingroup graphs
    2626///\file
    27 ///\brief FullGraph and FullDigraph classes.
     27///\brief FullDigraph and FullGraph classes.
    2828
    2929namespace lemon {
     
    5252
    5353    Node operator()(int ix) const { return Node(ix); }
    54     int index(const Node& node) const { return node._id; }
     54    static int index(const Node& node) { return node._id; }
    5555
    5656    Arc arc(const Node& s, const Node& t) const {
     
    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  /// This class provides constant time counting for nodes and arcs.
     166  ///
     167  /// \note FullDigraph and FullGraph classes are very similar,
    164168  /// 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.
     169  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
     170  /// conforms to the \ref concepts::Graph "Graph" concept,
     171  /// moreover FullGraph does not contain a loop for each
     172  /// node as this class does.
    169173  ///
    170174  /// \sa FullGraph
     
    174178  public:
    175179
    176     /// \brief Constructor
     180    /// \brief Default constructor.
     181    ///
     182    /// Default constructor. The number of nodes and arcs will be zero.
    177183    FullDigraph() { construct(0); }
    178184
     
    185191    /// \brief Resizes the digraph
    186192    ///
    187     /// Resizes the digraph. The function will fully destroy and
    188     /// rebuild the digraph. This cause that the maps of the digraph will
     193    /// This function resizes the digraph. It fully destroys and
     194    /// rebuilds the structure, therefore the maps of the digraph will be
    189195    /// reallocated automatically and the previous values will be lost.
    190196    void resize(int n) {
     
    198204    /// \brief Returns the node with the given index.
    199205    ///
    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>.
     206    /// Returns the node with the given index. Since this structure is
     207    /// completely static, the nodes can be indexed with integers from
     208    /// the range <tt>[0..nodeNum()-1]</tt>.
     209    /// The index of a node is the same as its ID.
    203210    /// \sa index()
    204211    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    206213    /// \brief Returns the index of the given node.
    207214    ///
    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); }
     215    /// Returns the index of the given node. Since this structure is
     216    /// completely static, the nodes can be indexed with integers from
     217    /// the range <tt>[0..nodeNum()-1]</tt>.
     218    /// The index of a node is the same as its ID.
     219    /// \sa operator()()
     220    static int index(const Node& node) { return Parent::index(node); }
    213221
    214222    /// \brief Returns the arc connecting the given nodes.
    215223    ///
    216224    /// Returns the arc connecting the given nodes.
    217     Arc arc(const Node& u, const Node& v) const {
     225    Arc arc(Node u, Node v) const {
    218226      return Parent::arc(u, v);
    219227    }
     
    284292
    285293    Node operator()(int ix) const { return Node(ix); }
    286     int index(const Node& node) const { return node._id; }
     294    static int index(const Node& node) { return node._id; }
    287295
    288296    Edge edge(const Node& u, const Node& v) const {
     
    521529  /// \brief An undirected full graph class.
    522530  ///
    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
     531  /// FullGraph is a simple and fast implmenetation of undirected full
     532  /// (complete) graphs. It contains an edge between every distinct pair
     533  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
     534  /// This class is completely static and it needs constant memory space.
     535  /// Thus you can neither add nor delete nodes or edges, however
     536  /// the structure can be resized using resize().
     537  ///
     538  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
     539  /// Most of its member functions and nested classes are documented
     540  /// only in the concept class.
     541  ///
     542  /// This class provides constant time counting for nodes, edges and arcs.
     543  ///
     544  /// \note FullDigraph and FullGraph classes are very similar,
     545  /// but there are two differences. While FullDigraph
    534546  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
    535547  /// 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.
     548  /// moreover this class does not contain a loop for each
     549  /// node as FullDigraph does.
    538550  ///
    539551  /// \sa FullDigraph
     
    543555  public:
    544556
    545     /// \brief Constructor
     557    /// \brief Default constructor.
     558    ///
     559    /// Default constructor. The number of nodes and edges will be zero.
    546560    FullGraph() { construct(0); }
    547561
     
    554568    /// \brief Resizes the graph
    555569    ///
    556     /// Resizes the graph. The function will fully destroy and
    557     /// rebuild the graph. This cause that the maps of the graph will
     570    /// This function resizes the graph. It fully destroys and
     571    /// rebuilds the structure, therefore the maps of the graph will be
    558572    /// reallocated automatically and the previous values will be lost.
    559573    void resize(int n) {
     
    569583    /// \brief Returns the node with the given index.
    570584    ///
    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>.
     585    /// Returns the node with the given index. Since this structure is
     586    /// completely static, the nodes can be indexed with integers from
     587    /// the range <tt>[0..nodeNum()-1]</tt>.
     588    /// The index of a node is the same as its ID.
    574589    /// \sa index()
    575590    Node operator()(int ix) const { return Parent::operator()(ix); }
     
    577592    /// \brief Returns the index of the given node.
    578593    ///
    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); }
     594    /// Returns the index of the given node. Since this structure is
     595    /// completely static, the nodes can be indexed with integers from
     596    /// the range <tt>[0..nodeNum()-1]</tt>.
     597    /// The index of a node is the same as its ID.
     598    /// \sa operator()()
     599    static int index(const Node& node) { return Parent::index(node); }
    584600
    585601    /// \brief Returns the arc connecting the given nodes.
    586602    ///
    587603    /// Returns the arc connecting the given nodes.
    588     Arc arc(const Node& s, const Node& t) const {
     604    Arc arc(Node s, Node t) const {
    589605      return Parent::arc(s, t);
    590606    }
    591607
    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 {
     608    /// \brief Returns the edge connecting the given nodes.
     609    ///
     610    /// Returns the edge connecting the given nodes.
     611    Edge edge(Node u, Node v) const {
    596612      return Parent::edge(u, v);
    597613    }
  • lemon/glpk.cc

    r623 r793  
    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

    r697 r793  
    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

    r643 r833  
    295295    /// \pre \ref run() must be called before using this function.
    296296    template <typename CutMap>
    297     Value minCutMap(const Node& s, ///<
     297    Value minCutMap(const Node& s,
    298298                    const Node& t,
    299                     ///<
    300299                    CutMap& cutMap
    301                     ///<
    302300                    ) const {
    303301      Node sn = s, tn = t;
     
    360358    /// \c t.
    361359    /// \code
    362     /// GomoruHu<Graph> gom(g, capacities);
     360    /// GomoryHu<Graph> gom(g, capacities);
    363361    /// gom.run();
    364362    /// int cnt=0;
    365     /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
     363    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    366364    /// \endcode
    367365    class MinCutNodeIt
     
    395393                   /// \endcode
    396394                   /// does not necessarily give the same set of nodes.
    397                    /// However it is ensured that
     395                   /// However, it is ensured that
    398396                   /// \code
    399397                   /// MinCutNodeIt(gomory, s, t, true);
     
    457455    /// \c t.
    458456    /// \code
    459     /// GomoruHu<Graph> gom(g, capacities);
     457    /// GomoryHu<Graph> gom(g, capacities);
    460458    /// gom.run();
    461459    /// int value=0;
    462     /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
     460    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    463461    ///   value+=capacities[e];
    464462    /// \endcode
  • lemon/graph_to_eps.h

    r664 r833  
    143143  ///\param gr  Reference to the graph to be printed.
    144144  ///\param ost Reference to the output stream.
    145   ///By default it is <tt>std::cout</tt>.
     145  ///By default, it is <tt>std::cout</tt>.
    146146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
     
    513513  ///Turn on/off pre-scaling
    514514
    515   ///By default graphToEps() rescales the whole image in order to avoid
     515  ///By default, graphToEps() rescales the whole image in order to avoid
    516516  ///very big or very small bounding boxes.
    517517  ///
     
    11151115///\param g Reference to the graph to be printed.
    11161116///\param os Reference to the output stream.
    1117 ///By default it is <tt>std::cout</tt>.
     1117///By default, it is <tt>std::cout</tt>.
    11181118///
    11191119///This function also has a lot of
     
    11271127///\endcode
    11281128///
    1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
     1129///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
    11301130///
    11311131///\warning Don't forget to put the \ref GraphToEps::run() "run()"
  • lemon/grid_graph.h

    r664 r834  
    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.
     506  ///
     507  /// This class provides constant time counting for nodes, edges and arcs.
    501508  class GridGraph : public ExtendedGridGraphBase {
    502509    typedef ExtendedGridGraphBase Parent;
     
    504511  public:
    505512
    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>.
     513    /// \brief Map to get the indices of the nodes as \ref dim2::Point
     514    /// "dim2::Point<int>".
     515    ///
     516    /// Map to get the indices of the nodes as \ref dim2::Point
     517    /// "dim2::Point<int>".
    509518    class IndexMap {
    510519    public:
     
    515524
    516525      /// \brief Constructor
    517       ///
    518       /// Constructor
    519526      IndexMap(const GridGraph& graph) : _graph(graph) {}
    520527
    521528      /// \brief The subscript operator
    522       ///
    523       /// The subscript operator.
    524529      Value operator[](Key key) const {
    525530        return _graph.pos(key);
     
    541546
    542547      /// \brief Constructor
    543       ///
    544       /// Constructor
    545548      ColMap(const GridGraph& graph) : _graph(graph) {}
    546549
    547550      /// \brief The subscript operator
    548       ///
    549       /// The subscript operator.
    550551      Value operator[](Key key) const {
    551552        return _graph.col(key);
     
    567568
    568569      /// \brief Constructor
    569       ///
    570       /// Constructor
    571570      RowMap(const GridGraph& graph) : _graph(graph) {}
    572571
    573572      /// \brief The subscript operator
    574       ///
    575       /// The subscript operator.
    576573      Value operator[](Key key) const {
    577574        return _graph.row(key);
     
    584581    /// \brief Constructor
    585582    ///
    586     /// Construct a grid graph with given size.
     583    /// Construct a grid graph with the given size.
    587584    GridGraph(int width, int height) { construct(width, height); }
    588585
    589     /// \brief Resize the graph
    590     ///
    591     /// Resize the graph. The function will fully destroy and rebuild
    592     /// the graph.  This cause that the maps of the graph will
    593     /// reallocated automatically and the previous values will be
    594     /// lost.
     586    /// \brief Resizes the graph
     587    ///
     588    /// This function resizes the graph. It fully destroys and
     589    /// rebuilds the structure, therefore the maps of the graph will be
     590    /// reallocated automatically and the previous values will be lost.
    595591    void resize(int width, int height) {
    596592      Parent::notifier(Arc()).clear();
     
    610606    }
    611607
    612     /// \brief Gives back the column index of the node.
     608    /// \brief The column index of the node.
    613609    ///
    614610    /// Gives back the column index of the node.
     
    617613    }
    618614
    619     /// \brief Gives back the row index of the node.
     615    /// \brief The row index of the node.
    620616    ///
    621617    /// Gives back the row index of the node.
     
    624620    }
    625621
    626     /// \brief Gives back the position of the node.
     622    /// \brief The position of the node.
    627623    ///
    628624    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
     
    631627    }
    632628
    633     /// \brief Gives back the number of the columns.
     629    /// \brief The number of the columns.
    634630    ///
    635631    /// Gives back the number of the columns.
     
    638634    }
    639635
    640     /// \brief Gives back the number of the rows.
     636    /// \brief The number of the rows.
    641637    ///
    642638    /// Gives back the number of the rows.
     
    645641    }
    646642
    647     /// \brief Gives back the arc goes right from the node.
     643    /// \brief The arc goes right from the node.
    648644    ///
    649645    /// Gives back the arc goes right from the node. If there is not
     
    653649    }
    654650
    655     /// \brief Gives back the arc goes left from the node.
     651    /// \brief The arc goes left from the node.
    656652    ///
    657653    /// Gives back the arc goes left from the node. If there is not
     
    661657    }
    662658
    663     /// \brief Gives back the arc goes up from the node.
     659    /// \brief The arc goes up from the node.
    664660    ///
    665661    /// Gives back the arc goes up from the node. If there is not
     
    669665    }
    670666
    671     /// \brief Gives back the arc goes down from the node.
     667    /// \brief The arc goes down from the node.
    672668    ///
    673669    /// Gives back the arc goes down from the node. If there is not
  • lemon/hypercube_graph.h

    r664 r835  
    263263    }
    264264
    265     int index(Node node) const {
     265    static int index(Node node) {
    266266      return node._id;
    267267    }
     
    283283  /// \brief Hypercube graph class
    284284  ///
    285   /// This class implements a special graph type. The nodes of the graph
    286   /// are indiced with integers with at most \c dim binary digits.
     285  /// HypercubeGraph implements a special graph type. The nodes of the
     286  /// graph are indexed with integers having at most \c dim binary digits.
    287287  /// Two nodes are connected in the graph if and only if their indices
    288288  /// differ only on one position in the binary form.
     289  /// This class is completely static and it needs constant memory space.
     290  /// Thus you can neither add nor delete nodes or edges, however,
     291  /// the structure can be resized using resize().
     292  ///
     293  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
     294  /// Most of its member functions and nested classes are documented
     295  /// only in the concept class.
     296  ///
     297  /// This class provides constant time counting for nodes, edges and arcs.
    289298  ///
    290299  /// \note The type of the indices is chosen to \c int for efficiency
    291300  /// reasons. Thus the maximum dimension of this implementation is 26
    292301  /// (assuming that the size of \c int is 32 bit).
    293   ///
    294   /// This graph type fully conforms to the \ref concepts::Graph
    295   /// "Graph concept".
    296302  class HypercubeGraph : public ExtendedHypercubeGraphBase {
    297303    typedef ExtendedHypercubeGraphBase Parent;
     
    303309    /// Constructs a hypercube graph with \c dim dimensions.
    304310    HypercubeGraph(int dim) { construct(dim); }
     311
     312    /// \brief Resizes the graph
     313    ///
     314    /// This function resizes the graph. It fully destroys and
     315    /// rebuilds the structure, therefore the maps of the graph will be
     316    /// reallocated automatically and the previous values will be lost.
     317    void resize(int dim) {
     318      Parent::notifier(Arc()).clear();
     319      Parent::notifier(Edge()).clear();
     320      Parent::notifier(Node()).clear();
     321      construct(dim);
     322      Parent::notifier(Node()).build();
     323      Parent::notifier(Edge()).build();
     324      Parent::notifier(Arc()).build();
     325    }
    305326
    306327    /// \brief The number of dimensions.
     
    321342    ///
    322343    /// Gives back the dimension id of the given edge.
    323     /// It is in the [0..dim-1] range.
     344    /// It is in the range <tt>[0..dim-1]</tt>.
    324345    int dimension(Edge edge) const {
    325346      return Parent::dimension(edge);
     
    329350    ///
    330351    /// Gives back the dimension id of the given arc.
    331     /// It is in the [0..dim-1] range.
     352    /// It is in the range <tt>[0..dim-1]</tt>.
    332353    int dimension(Arc arc) const {
    333354      return Parent::dimension(arc);
     
    338359    /// Gives back the index of the given node.
    339360    /// The lower bits of the integer describes the node.
    340     int index(Node node) const {
     361    static int index(Node node) {
    341362      return Parent::index(node);
    342363    }
  • lemon/lgf_reader.h

    r646 r833  
    428428  ///\endcode
    429429  ///
    430   /// By default the reader uses the first section in the file of the
     430  /// By default, the reader uses the first section in the file of the
    431431  /// proper type. If a section has an optional name, then it can be
    432432  /// selected for reading by giving an optional name parameter to the
     
    22222222    /// whitespaces are trimmed from each processed string.
    22232223    ///
    2224     /// For example let's see a section, which contain several
     2224    /// For example, let's see a section, which contain several
    22252225    /// integers, which should be inserted into a vector.
    22262226    ///\code
  • lemon/list_graph.h

    r664 r835  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListDigraph, ListGraph classes.
     24///\brief ListDigraph and ListGraph classes.
    2525
    2626#include <lemon/core.h>
     
    3232
    3333namespace lemon {
     34
     35  class ListDigraph;
    3436
    3537  class ListDigraphBase {
     
    6365    class Node {
    6466      friend class ListDigraphBase;
     67      friend class ListDigraph;
    6568    protected:
    6669
     
    7881    class Arc {
    7982      friend class ListDigraphBase;
     83      friend class ListDigraph;
    8084    protected:
    8185
     
    117121      int n;
    118122      for(n = first_node;
    119           n!=-1 && nodes[n].first_in == -1;
     123          n != -1 && nodes[n].first_out == -1;
    120124          n = nodes[n].next) {}
    121       arc.id = (n == -1) ? -1 : nodes[n].first_in;
     125      arc.id = (n == -1) ? -1 : nodes[n].first_out;
    122126    }
    123127
    124128    void next(Arc& arc) const {
    125       if (arcs[arc.id].next_in != -1) {
    126         arc.id = arcs[arc.id].next_in;
     129      if (arcs[arc.id].next_out != -1) {
     130        arc.id = arcs[arc.id].next_out;
    127131      } else {
    128132        int n;
    129         for(n = nodes[arcs[arc.id].target].next;
    130             n!=-1 && nodes[n].first_in == -1;
     133        for(n = nodes[arcs[arc.id].source].next;
     134            n != -1 && nodes[n].first_out == -1;
    131135            n = nodes[n].next) {}
    132         arc.id = (n == -1) ? -1 : nodes[n].first_in;
     136        arc.id = (n == -1) ? -1 : nodes[n].first_out;
    133137      }
    134138    }
     
    312316  ///A general directed graph structure.
    313317
    314   ///\ref ListDigraph is a simple and fast <em>directed graph</em>
    315   ///implementation based on static linked lists that are stored in
     318  ///\ref ListDigraph is a versatile and fast directed graph
     319  ///implementation based on linked lists that are stored in
    316320  ///\c std::vector structures.
    317321  ///
    318   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
    319   ///also provides several useful additional functionalities.
    320   ///Most of the member functions and nested classes are documented
     322  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
     323  ///and it also provides several useful additional functionalities.
     324  ///Most of its member functions and nested classes are documented
    321325  ///only in the concept class.
    322326  ///
     327  ///This class provides only linear time counting for nodes and arcs.
     328  ///
    323329  ///\sa concepts::Digraph
    324 
     330  ///\sa ListGraph
    325331  class ListDigraph : public ExtendedListDigraphBase {
    326332    typedef ExtendedListDigraphBase Parent;
    327333
    328334  private:
    329     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    330 
    331     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    332     ///
     335    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
    333336    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    334     ///\brief Assignment of ListDigraph to another one is \e not allowed.
    335     ///Use copyDigraph() instead.
    336 
    337     ///Assignment of ListDigraph to another one is \e not allowed.
    338     ///Use copyDigraph() instead.
     337    /// \brief Assignment of a digraph to another one is \e not allowed.
     338    /// Use DigraphCopy instead.
    339339    void operator=(const ListDigraph &) {}
    340340  public:
     
    348348    ///Add a new node to the digraph.
    349349
    350     ///Add a new node to the digraph.
     350    ///This function adds a new node to the digraph.
    351351    ///\return The new node.
    352352    Node addNode() { return Parent::addNode(); }
     
    354354    ///Add a new arc to the digraph.
    355355
    356     ///Add a new arc to the digraph with source node \c s
     356    ///This function adds a new arc to the digraph with source node \c s
    357357    ///and target node \c t.
    358358    ///\return The new arc.
    359     Arc addArc(const Node& s, const Node& t) {
     359    Arc addArc(Node s, Node t) {
    360360      return Parent::addArc(s, t);
    361361    }
     
    363363    ///\brief Erase a node from the digraph.
    364364    ///
    365     ///Erase a node from the digraph.
    366     ///
    367     void erase(const Node& n) { Parent::erase(n); }
     365    ///This function erases the given node along with its outgoing and
     366    ///incoming arcs from the digraph.
     367    ///
     368    ///\note All iterators referencing the removed node or the connected
     369    ///arcs are invalidated, of course.
     370    void erase(Node n) { Parent::erase(n); }
    368371
    369372    ///\brief Erase an arc from the digraph.
    370373    ///
    371     ///Erase an arc from the digraph.
    372     ///
    373     void erase(const Arc& a) { Parent::erase(a); }
     374    ///This function erases the given arc from the digraph.
     375    ///
     376    ///\note All iterators referencing the removed arc are invalidated,
     377    ///of course.
     378    void erase(Arc a) { Parent::erase(a); }
    374379
    375380    /// Node validity check
    376381
    377     /// This function gives back true if the given node is valid,
    378     /// ie. it is a real node of the graph.
    379     ///
    380     /// \warning A Node pointing to a removed item
    381     /// could become valid again later if new nodes are
    382     /// added to the graph.
     382    /// This function gives back \c true if the given node is valid,
     383    /// i.e. it is a real node of the digraph.
     384    ///
     385    /// \warning A removed node could become valid again if new nodes are
     386    /// added to the digraph.
    383387    bool valid(Node n) const { return Parent::valid(n); }
    384388
    385389    /// Arc validity check
    386390
    387     /// This function gives back true if the given arc is valid,
    388     /// ie. it is a real arc of the graph.
    389     ///
    390     /// \warning An Arc pointing to a removed item
    391     /// could become valid again later if new nodes are
    392     /// added to the graph.
     391    /// This function gives back \c true if the given arc is valid,
     392    /// i.e. it is a real arc of the digraph.
     393    ///
     394    /// \warning A removed arc could become valid again if new arcs are
     395    /// added to the digraph.
    393396    bool valid(Arc a) const { return Parent::valid(a); }
    394397
    395     /// Change the target of \c a to \c n
    396 
    397     /// Change the target of \c a to \c n
    398     ///
    399     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    400     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    401     ///invalidated.
     398    /// Change the target node of an arc
     399
     400    /// This function changes the target node of the given arc \c a to \c n.
     401    ///
     402    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
     403    ///arc remain valid, but \c InArcIt iterators are invalidated.
    402404    ///
    403405    ///\warning This functionality cannot be used together with the Snapshot
     
    406408      Parent::changeTarget(a,n);
    407409    }
    408     /// Change the source of \c a to \c n
    409 
    410     /// Change the source of \c a to \c n
    411     ///
    412     ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
    413     ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
    414     ///invalidated.
     410    /// Change the source node of an arc
     411
     412    /// This function changes the source node of the given arc \c a to \c n.
     413    ///
     414    ///\note \c InArcIt iterators referencing the changed arc remain
     415    ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
    415416    ///
    416417    ///\warning This functionality cannot be used together with the Snapshot
     
    420421    }
    421422
    422     /// Invert the direction of an arc.
    423 
    424     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
    425     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
    426     ///invalidated.
     423    /// Reverse the direction of an arc.
     424
     425    /// This function reverses the direction of the given arc.
     426    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
     427    ///the changed arc are invalidated.
    427428    ///
    428429    ///\warning This functionality cannot be used together with the Snapshot
    429430    ///feature.
    430     void reverseArc(Arc e) {
    431       Node t=target(e);
    432       changeTarget(e,source(e));
    433       changeSource(e,t);
    434     }
    435 
    436     /// Reserve memory for nodes.
    437 
    438     /// Using this function it is possible to avoid the superfluous memory
    439     /// allocation: if you know that the digraph you want to build will
    440     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    441     /// then it is worth reserving space for this amount before starting
    442     /// to build the digraph.
    443     /// \sa reserveArc
    444     void reserveNode(int n) { nodes.reserve(n); };
    445 
    446     /// Reserve memory for arcs.
    447 
    448     /// Using this function it is possible to avoid the superfluous memory
    449     /// allocation: if you know that the digraph you want to build will
    450     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    451     /// then it is worth reserving space for this amount before starting
    452     /// to build the digraph.
    453     /// \sa reserveNode
    454     void reserveArc(int m) { arcs.reserve(m); };
     431    void reverseArc(Arc a) {
     432      Node t=target(a);
     433      changeTarget(a,source(a));
     434      changeSource(a,t);
     435    }
    455436
    456437    ///Contract two nodes.
    457438
    458     ///This function contracts two nodes.
    459     ///Node \p b will be removed but instead of deleting
    460     ///incident arcs, they will be joined to \p a.
    461     ///The last parameter \p r controls whether to remove loops. \c true
    462     ///means that loops will be removed.
    463     ///
    464     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    465     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
    466     ///may be invalidated.
     439    ///This function contracts the given two nodes.
     440    ///Node \c v is removed, but instead of deleting its
     441    ///incident arcs, they are joined to node \c u.
     442    ///If the last parameter \c r is \c true (this is the default value),
     443    ///then the newly created loops are removed.
     444    ///
     445    ///\note The moved arcs are joined to node \c u using changeSource()
     446    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
     447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
     448    ///iterators are invalidated for the incomming arcs of \c v.
     449    ///Moreover all iterators referencing node \c v or the removed
     450    ///loops are also invalidated. Other iterators remain valid.
    467451    ///
    468452    ///\warning This functionality cannot be used together with the Snapshot
    469453    ///feature.
    470     void contract(Node a, Node b, bool r = true)
     454    void contract(Node u, Node v, bool r = true)
    471455    {
    472       for(OutArcIt e(*this,b);e!=INVALID;) {
     456      for(OutArcIt e(*this,v);e!=INVALID;) {
    473457        OutArcIt f=e;
    474458        ++f;
    475         if(r && target(e)==a) erase(e);
    476         else changeSource(e,a);
     459        if(r && target(e)==u) erase(e);
     460        else changeSource(e,u);
    477461        e=f;
    478462      }
    479       for(InArcIt e(*this,b);e!=INVALID;) {
     463      for(InArcIt e(*this,v);e!=INVALID;) {
    480464        InArcIt f=e;
    481465        ++f;
    482         if(r && source(e)==a) erase(e);
    483         else changeTarget(e,a);
     466        if(r && source(e)==u) erase(e);
     467        else changeTarget(e,u);
    484468        e=f;
    485469      }
    486       erase(b);
     470      erase(v);
    487471    }
    488472
    489473    ///Split a node.
    490474
    491     ///This function splits a node. First a new node is added to the digraph,
    492     ///then the source of each outgoing arc of \c n is moved to this new node.
    493     ///If \c connect is \c true (this is the default value), then a new arc
    494     ///from \c n to the newly created node is also added.
     475    ///This function splits the given node. First, a new node is added
     476    ///to the digraph, then the source of each outgoing arc of node \c n
     477    ///is moved to this new node.
     478    ///If the second parameter \c connect is \c true (this is the default
     479    ///value), then a new arc from node \c n to the newly created node
     480    ///is also added.
    495481    ///\return The newly created node.
    496482    ///
    497     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    498     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
    499     ///be invalidated.
    500     ///
    501     ///\warning This functionality cannot be used in conjunction with the
     483    ///\note All iterators remain valid.
     484    ///
     485    ///\warning This functionality cannot be used together with the
    502486    ///Snapshot feature.
    503487    Node split(Node n, bool connect = true) {
    504488      Node b = addNode();
    505       for(OutArcIt e(*this,n);e!=INVALID;) {
    506         OutArcIt f=e;
    507         ++f;
    508         changeSource(e,b);
    509         e=f;
     489      nodes[b.id].first_out=nodes[n.id].first_out;
     490      nodes[n.id].first_out=-1;
     491      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
     492        arcs[i].source=b.id;
    510493      }
    511494      if (connect) addArc(n,b);
     
    515498    ///Split an arc.
    516499
    517     ///This function splits an arc. First a new node \c b is added to
    518     ///the digraph, then the original arc is re-targeted to \c
    519     ///b. Finally an arc from \c b to the original target is added.
    520     ///
     500    ///This function splits the given arc. First, a new node \c v is
     501    ///added to the digraph, then the target node of the original arc
     502    ///is set to \c v. Finally, an arc from \c v to the original target
     503    ///is added.
    521504    ///\return The newly created node.
     505    ///
     506    ///\note \c InArcIt iterators referencing the original arc are
     507    ///invalidated. Other iterators remain valid.
    522508    ///
    523509    ///\warning This functionality cannot be used together with the
    524510    ///Snapshot feature.
    525     Node split(Arc e) {
    526       Node b = addNode();
    527       addArc(b,target(e));
    528       changeTarget(e,b);
    529       return b;
    530     }
     511    Node split(Arc a) {
     512      Node v = addNode();
     513      addArc(v,target(a));
     514      changeTarget(a,v);
     515      return v;
     516    }
     517
     518    ///Clear the digraph.
     519
     520    ///This function erases all nodes and arcs from the digraph.
     521    ///
     522    ///\note All iterators of the digraph are invalidated, of course.
     523    void clear() {
     524      Parent::clear();
     525    }
     526
     527    /// Reserve memory for nodes.
     528
     529    /// Using this function, it is possible to avoid superfluous memory
     530    /// allocation: if you know that the digraph you want to build will
     531    /// be large (e.g. it will contain millions of nodes and/or arcs),
     532    /// then it is worth reserving space for this amount before starting
     533    /// to build the digraph.
     534    /// \sa reserveArc()
     535    void reserveNode(int n) { nodes.reserve(n); };
     536
     537    /// Reserve memory for arcs.
     538
     539    /// Using this function, it is possible to avoid superfluous memory
     540    /// allocation: if you know that the digraph you want to build will
     541    /// be large (e.g. it will contain millions of nodes and/or arcs),
     542    /// then it is worth reserving space for this amount before starting
     543    /// to build the digraph.
     544    /// \sa reserveNode()
     545    void reserveArc(int m) { arcs.reserve(m); };
    531546
    532547    /// \brief Class to make a snapshot of the digraph and restore
     
    538553    /// restore() function.
    539554    ///
    540     /// \warning Arc and node deletions and other modifications (e.g.
    541     /// contracting, splitting, reversing arcs or nodes) cannot be
     555    /// \note After a state is restored, you cannot restore a later state,
     556    /// i.e. you cannot add the removed nodes and arcs again using
     557    /// another Snapshot instance.
     558    ///
     559    /// \warning Node and arc deletions and other modifications (e.g.
     560    /// reversing, contracting, splitting arcs or nodes) cannot be
    542561    /// restored. These events invalidate the snapshot.
     562    /// However, the arcs and nodes that were added to the digraph after
     563    /// making the current snapshot can be removed without invalidating it.
    543564    class Snapshot {
    544565    protected:
     
    710731      ///
    711732      /// Default constructor.
    712       /// To actually make a snapshot you must call save().
     733      /// You have to call save() to actually make a snapshot.
    713734      Snapshot()
    714735        : digraph(0), node_observer_proxy(*this),
     
    717738      /// \brief Constructor that immediately makes a snapshot.
    718739      ///
    719       /// This constructor immediately makes a snapshot of the digraph.
    720       /// \param _digraph The digraph we make a snapshot of.
    721       Snapshot(ListDigraph &_digraph)
     740      /// This constructor immediately makes a snapshot of the given digraph.
     741      Snapshot(ListDigraph &gr)
    722742        : node_observer_proxy(*this),
    723743          arc_observer_proxy(*this) {
    724         attach(_digraph);
     744        attach(gr);
    725745      }
    726746
    727747      /// \brief Make a snapshot.
    728748      ///
    729       /// Make a snapshot of the digraph.
    730       ///
    731       /// This function can be called more than once. In case of a repeated
     749      /// This function makes a snapshot of the given digraph.
     750      /// It can be called more than once. In case of a repeated
    732751      /// call, the previous snapshot gets lost.
    733       /// \param _digraph The digraph we make the snapshot of.
    734       void save(ListDigraph &_digraph) {
     752      void save(ListDigraph &gr) {
    735753        if (attached()) {
    736754          detach();
    737755          clear();
    738756        }
    739         attach(_digraph);
     757        attach(gr);
    740758      }
    741759
    742760      /// \brief Undo the changes until the last snapshot.
    743       //
    744       /// Undo the changes until the last snapshot created by save().
     761      ///
     762      /// This function undos the changes until the last snapshot
     763      /// created by save() or Snapshot(ListDigraph&).
     764      ///
     765      /// \warning This method invalidates the snapshot, i.e. repeated
     766      /// restoring is not supported unless you call save() again.
    745767      void restore() {
    746768        detach();
     
    756778      }
    757779
    758       /// \brief Gives back true when the snapshot is valid.
     780      /// \brief Returns \c true if the snapshot is valid.
    759781      ///
    760       /// Gives back true when the snapshot is valid.
     782      /// This function returns \c true if the snapshot is valid.
    761783      bool valid() const {
    762784        return attached();
     
    795817
    796818    typedef ListGraphBase Graph;
    797 
    798     class Node;
    799     class Arc;
    800     class Edge;
    801819
    802820    class Node {
     
    848866      bool operator<(const Arc& arc) const {return id < arc.id;}
    849867    };
    850 
    851 
    852868
    853869    ListGraphBase()
     
    11651181  ///A general undirected graph structure.
    11661182
    1167   ///\ref ListGraph is a simple and fast <em>undirected graph</em>
    1168   ///implementation based on static linked lists that are stored in
     1183  ///\ref ListGraph is a versatile and fast undirected graph
     1184  ///implementation based on linked lists that are stored in
    11691185  ///\c std::vector structures.
    11701186  ///
    1171   ///It conforms to the \ref concepts::Graph "Graph concept" and it
    1172   ///also provides several useful additional functionalities.
    1173   ///Most of the member functions and nested classes are documented
     1187  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
     1188  ///and it also provides several useful additional functionalities.
     1189  ///Most of its member functions and nested classes are documented
    11741190  ///only in the concept class.
    11751191  ///
     1192  ///This class provides only linear time counting for nodes, edges and arcs.
     1193  ///
    11761194  ///\sa concepts::Graph
    1177 
     1195  ///\sa ListDigraph
    11781196  class ListGraph : public ExtendedListGraphBase {
    11791197    typedef ExtendedListGraphBase Parent;
    11801198
    11811199  private:
    1182     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1183 
    1184     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1185     ///
     1200    /// Graphs are \e not copy constructible. Use GraphCopy instead.
    11861201    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    1187     ///\brief Assignment of ListGraph to another one is \e not allowed.
    1188     ///Use copyGraph() instead.
    1189 
    1190     ///Assignment of ListGraph to another one is \e not allowed.
    1191     ///Use copyGraph() instead.
     1202    /// \brief Assignment of a graph to another one is \e not allowed.
     1203    /// Use GraphCopy instead.
    11921204    void operator=(const ListGraph &) {}
    11931205  public:
     
    12021214    /// \brief Add a new node to the graph.
    12031215    ///
    1204     /// Add a new node to the graph.
     1216    /// This function adds a new node to the graph.
    12051217    /// \return The new node.
    12061218    Node addNode() { return Parent::addNode(); }
     
    12081220    /// \brief Add a new edge to the graph.
    12091221    ///
    1210     /// Add a new edge to the graph with source node \c s
    1211     /// and target node \c t.
     1222    /// This function adds a new edge to the graph between nodes
     1223    /// \c u and \c v with inherent orientation from node \c u to
     1224    /// node \c v.
    12121225    /// \return The new edge.
    1213     Edge addEdge(const Node& s, const Node& t) {
    1214       return Parent::addEdge(s, t);
    1215     }
    1216 
    1217     /// \brief Erase a node from the graph.
    1218     ///
    1219     /// Erase a node from the graph.
    1220     ///
    1221     void erase(const Node& n) { Parent::erase(n); }
    1222 
    1223     /// \brief Erase an edge from the graph.
    1224     ///
    1225     /// Erase an edge from the graph.
    1226     ///
    1227     void erase(const Edge& e) { Parent::erase(e); }
     1226    Edge addEdge(Node u, Node v) {
     1227      return Parent::addEdge(u, v);
     1228    }
     1229
     1230    ///\brief Erase a node from the graph.
     1231    ///
     1232    /// This function erases the given node along with its incident arcs
     1233    /// from the graph.
     1234    ///
     1235    /// \note All iterators referencing the removed node or the incident
     1236    /// edges are invalidated, of course.
     1237    void erase(Node n) { Parent::erase(n); }
     1238
     1239    ///\brief Erase an edge from the graph.
     1240    ///
     1241    /// This function erases the given edge from the graph.
     1242    ///
     1243    /// \note All iterators referencing the removed edge are invalidated,
     1244    /// of course.
     1245    void erase(Edge e) { Parent::erase(e); }
    12281246    /// Node validity check
    12291247
    1230     /// This function gives back true if the given node is valid,
    1231     /// ie. it is a real node of the graph.
    1232     ///
    1233     /// \warning A Node pointing to a removed item
    1234     /// could become valid again later if new nodes are
     1248    /// This function gives back \c true if the given node is valid,
     1249    /// i.e. it is a real node of the graph.
     1250    ///
     1251    /// \warning A removed node could become valid again if new nodes are
    12351252    /// added to the graph.
    12361253    bool valid(Node n) const { return Parent::valid(n); }
     1254    /// Edge validity check
     1255
     1256    /// This function gives back \c true if the given edge is valid,
     1257    /// i.e. it is a real edge of the graph.
     1258    ///
     1259    /// \warning A removed edge could become valid again if new edges are
     1260    /// added to the graph.
     1261    bool valid(Edge e) const { return Parent::valid(e); }
    12371262    /// Arc validity check
    12381263
    1239     /// This function gives back true if the given arc is valid,
    1240     /// ie. it is a real arc of the graph.
    1241     ///
    1242     /// \warning An Arc pointing to a removed item
    1243     /// could become valid again later if new edges are
     1264    /// This function gives back \c true if the given arc is valid,
     1265    /// i.e. it is a real arc of the graph.
     1266    ///
     1267    /// \warning A removed arc could become valid again if new edges are
    12441268    /// added to the graph.
    12451269    bool valid(Arc a) const { return Parent::valid(a); }
    1246     /// Edge validity check
    1247 
    1248     /// This function gives back true if the given edge is valid,
    1249     /// ie. it is a real arc of the graph.
    1250     ///
    1251     /// \warning A Edge pointing to a removed item
    1252     /// could become valid again later if new edges are
    1253     /// added to the graph.
    1254     bool valid(Edge e) const { return Parent::valid(e); }
    1255     /// \brief Change the end \c u of \c e to \c n
    1256     ///
    1257     /// This function changes the end \c u of \c e to node \c n.
    1258     ///
    1259     ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
    1260     ///changed edge are invalidated and if the changed node is the
    1261     ///base node of an iterator then this iterator is also
    1262     ///invalidated.
     1270
     1271    /// \brief Change the first node of an edge.
     1272    ///
     1273    /// This function changes the first node of the given edge \c e to \c n.
     1274    ///
     1275    ///\note \c EdgeIt and \c ArcIt iterators referencing the
     1276    ///changed edge are invalidated and all other iterators whose
     1277    ///base node is the changed node are also invalidated.
    12631278    ///
    12641279    ///\warning This functionality cannot be used together with the
     
    12671282      Parent::changeU(e,n);
    12681283    }
    1269     /// \brief Change the end \c v of \c e to \c n
    1270     ///
    1271     /// This function changes the end \c v of \c e to \c n.
    1272     ///
    1273     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
    1274     ///valid, however <tt>ArcIt</tt>s and if the changed node is the
    1275     ///base node of an iterator then this iterator is invalidated.
     1284    /// \brief Change the second node of an edge.
     1285    ///
     1286    /// This function changes the second node of the given edge \c e to \c n.
     1287    ///
     1288    ///\note \c EdgeIt iterators referencing the changed edge remain
     1289    ///valid, but \c ArcIt iterators referencing the changed edge and
     1290    ///all other iterators whose base node is the changed node are also
     1291    ///invalidated.
    12761292    ///
    12771293    ///\warning This functionality cannot be used together with the
     
    12801296      Parent::changeV(e,n);
    12811297    }
     1298
    12821299    /// \brief Contract two nodes.
    12831300    ///
    1284     /// This function contracts two nodes.
    1285     /// Node \p b will be removed but instead of deleting
    1286     /// its neighboring arcs, they will be joined to \p a.
    1287     /// The last parameter \p r controls whether to remove loops. \c true
    1288     /// means that loops will be removed.
    1289     ///
    1290     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
    1291     /// valid.
     1301    /// This function contracts the given two nodes.
     1302    /// Node \c b is removed, but instead of deleting
     1303    /// its incident edges, they are joined to node \c a.
     1304    /// If the last parameter \c r is \c true (this is the default value),
     1305    /// then the newly created loops are removed.
     1306    ///
     1307    /// \note The moved edges are joined to node \c a using changeU()
     1308    /// or changeV(), thus all edge and arc iterators whose base node is
     1309    /// \c b are invalidated.
     1310    /// Moreover all iterators referencing node \c b or the removed
     1311    /// loops are also invalidated. Other iterators remain valid.
    12921312    ///
    12931313    ///\warning This functionality cannot be used together with the
     
    13081328    }
    13091329
     1330    ///Clear the graph.
     1331
     1332    ///This function erases all nodes and arcs from the graph.
     1333    ///
     1334    ///\note All iterators of the graph are invalidated, of course.
     1335    void clear() {
     1336      Parent::clear();
     1337    }
     1338
     1339    /// Reserve memory for nodes.
     1340
     1341    /// Using this function, it is possible to avoid superfluous memory
     1342    /// allocation: if you know that the graph you want to build will
     1343    /// be large (e.g. it will contain millions of nodes and/or edges),
     1344    /// then it is worth reserving space for this amount before starting
     1345    /// to build the graph.
     1346    /// \sa reserveEdge()
     1347    void reserveNode(int n) { nodes.reserve(n); };
     1348
     1349    /// Reserve memory for edges.
     1350
     1351    /// Using this function, it is possible to avoid superfluous memory
     1352    /// allocation: if you know that the graph you want to build will
     1353    /// be large (e.g. it will contain millions of nodes and/or edges),
     1354    /// then it is worth reserving space for this amount before starting
     1355    /// to build the graph.
     1356    /// \sa reserveNode()
     1357    void reserveEdge(int m) { arcs.reserve(2 * m); };
    13101358
    13111359    /// \brief Class to make a snapshot of the graph and restore
     
    13171365    /// using the restore() function.
    13181366    ///
    1319     /// \warning Edge and node deletions and other modifications
    1320     /// (e.g. changing nodes of edges, contracting nodes) cannot be
    1321     /// restored. These events invalidate the snapshot.
     1367    /// \note After a state is restored, you cannot restore a later state,
     1368    /// i.e. you cannot add the removed nodes and edges again using
     1369    /// another Snapshot instance.
     1370    ///
     1371    /// \warning Node and edge deletions and other modifications
     1372    /// (e.g. changing the end-nodes of edges or contracting nodes)
     1373    /// cannot be restored. These events invalidate the snapshot.
     1374    /// However, the edges and nodes that were added to the graph after
     1375    /// making the current snapshot can be removed without invalidating it.
    13221376    class Snapshot {
    13231377    protected:
     
    14891543      ///
    14901544      /// Default constructor.
    1491       /// To actually make a snapshot you must call save().
     1545      /// You have to call save() to actually make a snapshot.
    14921546      Snapshot()
    14931547        : graph(0), node_observer_proxy(*this),
     
    14961550      /// \brief Constructor that immediately makes a snapshot.
    14971551      ///
    1498       /// This constructor immediately makes a snapshot of the graph.
    1499       /// \param _graph The graph we make a snapshot of.
    1500       Snapshot(ListGraph &_graph)
     1552      /// This constructor immediately makes a snapshot of the given graph.
     1553      Snapshot(ListGraph &gr)
    15011554        : node_observer_proxy(*this),
    15021555          edge_observer_proxy(*this) {
    1503         attach(_graph);
     1556        attach(gr);
    15041557      }
    15051558
    15061559      /// \brief Make a snapshot.
    15071560      ///
    1508       /// Make a snapshot of the graph.
    1509       ///
    1510       /// This function can be called more than once. In case of a repeated
     1561      /// This function makes a snapshot of the given graph.
     1562      /// It can be called more than once. In case of a repeated
    15111563      /// call, the previous snapshot gets lost.
    1512       /// \param _graph The graph we make the snapshot of.
    1513       void save(ListGraph &_graph) {
     1564      void save(ListGraph &gr) {
    15141565        if (attached()) {
    15151566          detach();
    15161567          clear();
    15171568        }
    1518         attach(_graph);
     1569        attach(gr);
    15191570      }
    15201571
    15211572      /// \brief Undo the changes until the last snapshot.
    1522       //
    1523       /// Undo the changes until the last snapshot created by save().
     1573      ///
     1574      /// This function undos the changes until the last snapshot
     1575      /// created by save() or Snapshot(ListGraph&).
     1576      ///
     1577      /// \warning This method invalidates the snapshot, i.e. repeated
     1578      /// restoring is not supported unless you call save() again.
    15241579      void restore() {
    15251580        detach()