Changes in / [929:65a0521e744e:933:ac5f72c48367] in lemon

Files:

• CMakeLists.txt (modified) (1 diff)
• INSTALL (modified) (1 diff)
• Makefile.am (modified) (2 diffs)
• README (modified) (2 diffs)
• configure.ac (modified) (3 diffs)
• demo/arg_parser_demo.cc (modified) (1 diff)
• doc/CMakeLists.txt (modified) (2 diffs)
• doc/Doxyfile.in (modified) (4 diffs)
• doc/Makefile.am (modified) (2 diffs)
• doc/groups.dox (modified) (9 diffs)
• doc/images/planar.eps (added)
• doc/mainpage.dox (modified) (2 diffs)
• doc/min_cost_flow.dox (modified) (3 diffs)
• doc/references.bib (added)
• lemon/Makefile.am (modified) (5 diffs)
• lemon/adaptors.h (modified) (10 diffs)
• lemon/arg_parser.cc (modified) (4 diffs)
• lemon/arg_parser.h (modified) (4 diffs)
• lemon/bellman_ford.h (modified) (14 diffs)
• lemon/bfs.h (modified) (8 diffs)
• lemon/bits/graph_extender.h (modified) (2 diffs)
• lemon/bits/map_extender.h (modified) (6 diffs)
• lemon/capacity_scaling.h (added)
• lemon/cbc.cc (modified) (1 diff)
• lemon/cbc.h (modified) (1 diff)
• lemon/circulation.h (modified) (2 diffs)
• lemon/clp.cc (modified) (1 diff)
• lemon/clp.h (modified) (1 diff)
• lemon/concepts/digraph.h (modified) (14 diffs)
• lemon/concepts/graph.h (modified) (26 diffs)
• lemon/concepts/graph_components.h (modified) (2 diffs)
• lemon/concepts/heap.h (modified) (12 diffs)
• lemon/concepts/path.h (modified) (12 diffs)
• lemon/cost_scaling.h (added)
• lemon/counter.h (modified) (1 diff)
• lemon/cplex.cc (modified) (1 diff)
• lemon/cplex.h (modified) (1 diff)
• lemon/cycle_canceling.h (added)
• lemon/dfs.h (modified) (8 diffs)
• lemon/dijkstra.h (modified) (7 diffs)
• lemon/edge_set.h (modified) (7 diffs)
• lemon/full_graph.h (modified) (13 diffs)
• lemon/glpk.cc (modified) (1 diff)
• lemon/glpk.h (modified) (4 diffs)
• lemon/gomory_hu.h (modified) (2 diffs)
• lemon/graph_to_eps.h (modified) (5 diffs)
• lemon/grid_graph.h (modified) (16 diffs)
• lemon/hartmann_orlin.h (added)
• lemon/howard.h (added)
• lemon/hypercube_graph.h (modified) (6 diffs)
• lemon/karp.h (added)
• lemon/lgf_reader.h (modified) (2 diffs)
• lemon/list_graph.h (modified) (28 diffs)
• lemon/lp_base.h (modified) (5 diffs)
• lemon/lp_skeleton.cc (modified) (1 diff)
• lemon/lp_skeleton.h (modified) (1 diff)
• lemon/maps.h (modified) (8 diffs)
• lemon/min_cost_arborescence.h (modified) (2 diffs)
• lemon/network_simplex.h (modified) (41 diffs)
• lemon/path.h (modified) (11 diffs)
• lemon/planarity.h (added)
• lemon/preflow.h (modified) (3 diffs)
• lemon/smart_graph.h (modified) (15 diffs)
• lemon/soplex.cc (modified) (1 diff)
• lemon/soplex.h (modified) (1 diff)
• lemon/static_graph.h (added)
• lemon/suurballe.h (modified) (20 diffs)
• lemon/time_measure.h (modified) (1 diff)
• lemon/unionfind.h (modified) (2 diffs)
• m4/lx_check_coin.m4 (modified) (1 diff)
• scripts/Makefile.am (added)
• scripts/bib2dox.py (added)
• scripts/bootstrap.sh (added)
• scripts/chg-len.py (modified) (1 diff)
• scripts/mk-release.sh (modified) (1 diff)
• scripts/unify-sources.sh (modified) (1 diff)
• scripts/valgrind-wrapper.sh (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (3 diffs)
• test/adaptors_test.cc (modified) (3 diffs)
• test/bellman_ford_test.cc (modified) (4 diffs)
• test/digraph_test.cc (modified) (6 diffs)
• test/graph_test.cc (modified) (5 diffs)
• test/maps_test.cc (modified) (6 diffs)
• test/min_cost_flow_test.cc (modified) (7 diffs)
• test/min_mean_cycle_test.cc (added)
• test/mip_test.cc (modified) (1 diff)
• test/planarity_test.cc (added)
• test/suurballe_test.cc (modified) (7 diffs)
• test/test_tools.h (modified) (1 diff)
• tools/dimacs-solver.cc (modified) (5 diffs)

CMakeLists.txt

@@ -35 +35 @@
 CHECK_TYPE_SIZE("long long" LONG_LONG)
 SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
+
+INCLUDE(FindPythonInterp)
 
 ENABLE_TESTING()

INSTALL

@@ -174 +174 @@
 
    Disable COIN-OR support.
+
+
+Makefile Variables
+==================
+
+Some Makefile variables are reserved by the GNU Coding Standards for
+the use of the "user" - the person building the package. For instance,
+CXX and CXXFLAGS are such variables, and have the same meaning as
+explained in the previous section. These variables can be set on the
+command line when invoking `make' like this:
+`make [VARIABLE=VALUE]...'
+
+WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
+to hold several compiler flags related to warnings. Its default value
+can be overridden when invoking `make'. For example to disable all
+warning flags use `make WARNINGCXXFLAGS='.
+
+In order to turn off a single flag from the default set of warning
+flags, you can use the CXXFLAGS variable, since this is passed after
+WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
+used by default when g++ is detected) you can use
+`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

Makefile.am

@@ -18 +18 @@
         cmake/FindGLPK.cmake \
         cmake/FindCOIN.cmake \
+        cmake/LEMONConfig.cmake.in \
         cmake/version.cmake.in \
         cmake/version.cmake \
@@ -44 +45 @@
 include doc/Makefile.am
 include tools/Makefile.am
+include scripts/Makefile.am
 
 DIST_SUBDIRS = demo

README

@@ -18 +18 @@
    Copying, distribution and modification conditions and terms.
 
+NEWS
+
+   News and version history.
+
 INSTALL
 
@@ -34 +38 @@
    Some example programs to make you easier to get familiar with LEMON.
 
+scripts/
+
+   Scripts that make it easier to develop LEMON.
+
 test/
 

configure.ac

@@ -42 +42 @@
 
 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+AC_CHECK_PROG([python_found],[python],[yes],[no])
 AC_CHECK_PROG([gs_found],[gs],[yes],[no])
 
@@ -82 +83 @@
 fi
 AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
+
+dnl Support for running test cases using valgrind.
+use_valgrind=no
+AC_ARG_ENABLE([valgrind],
+AS_HELP_STRING([--enable-valgrind], [use valgrind when running tests]),
+              [use_valgrind=yes])
+
+if [[ "$use_valgrind" = "yes" ]]; then
+  AC_CHECK_PROG(HAVE_VALGRIND, valgrind, yes, no)
+
+  if [[ "$HAVE_VALGRIND" = "no" ]]; then
+    AC_MSG_ERROR([Valgrind not found in PATH.])
+  fi
+fi
+AM_CONDITIONAL(USE_VALGRIND, [test "$use_valgrind" = "yes"])
 
 dnl Checks for header files.
@@ -128 +144 @@
 echo
 echo Build additional tools........ : $enable_tools
+echo Use valgrind for tests........ : $use_valgrind
 echo
 echo The packace will be installed in

demo/arg_parser_demo.cc

@@ -66 +66 @@
     .other("...");
 
+  // Throw an exception when problems occurs. The default behavior is to
+  // exit(1) on these cases, but this makes Valgrind falsely warn
+  // about memory leaks.
+  ap.throwOnProblems();
+  
   // Perform the parsing process
   // (in case of any error it terminates the program)
-  ap.parse();
+  // The try {} construct is necessary only if the ap.trowOnProblems()
+  // setting is in use.
+  try {
+    ap.parse();
+  } catch (ArgParserException &) { return 1; }
 
   // Check each option if it has been given and print its value

doc/CMakeLists.txt

@@ -10 +10 @@
 )
 
-IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)
   FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
   SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
@@ -27 +27 @@
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
     COMMAND ${CMAKE_COMMAND} -E remove_directory html
+    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox
     COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
     WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.5.9
 
 #---------------------------------------------------------------------------
@@ -22 +22 @@
 QT_AUTOBRIEF           = NO
 MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP         = YES
 INHERIT_DOCS           = NO
 SEPARATE_MEMBER_PAGES  = NO
@@ -92 +91 @@
                          "@abs_top_srcdir@/demo" \
                          "@abs_top_srcdir@/tools" \
-                         "@abs_top_srcdir@/test/test_tools.h"
+                         "@abs_top_srcdir@/test/test_tools.h" \
+                         "@abs_top_builddir@/doc/references.dox"
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          = *.h \
@@ -224 +224 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Configuration::additions related to external references   
+# Options related to the search engine   
 #---------------------------------------------------------------------------
 TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "

doc/Makefile.am

@@ -29 +29 @@
         edge_biconnected_components.eps \
         node_biconnected_components.eps \
+        planar.eps \
         strongly_connected_components.eps
 
@@ -67 +68 @@
         fi
 
-html-local: $(DOC_PNG_IMAGES)
+references.dox: doc/references.bib
+        if test ${python_found} = yes; then \
+          cd doc; \
+          python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \
+          cd ..; \
+        else \
+          echo; \
+          echo "Python not found."; \
+          echo; \
+          exit 1; \
+        fi
+
+html-local: $(DOC_PNG_IMAGES) references.dox
         if test ${doxygen_found} = yes; then \
           cd doc; \

doc/groups.dox

@@ -317 +317 @@
 
 This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
+\ref clrs01algorithms.
 */
 
@@ -325 +326 @@
 \brief Algorithms for finding shortest paths.
 
-This group contains the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -347 +349 @@
 
 This group contains the algorithms for finding minimum cost spanning
-trees and arborescences.
+trees and arborescences \ref clrs01algorithms.
 */
 
@@ -356 +358 @@
 
 This group contains the algorithms for finding maximum flows and
-feasible circulations.
+feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -371 +373 @@
 
 LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
-
-In most cases the \ref Preflow "Preflow" algorithm provides the
+- \ref EdmondsKarp Edmonds-Karp algorithm
+  \ref edmondskarp72theoretical.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
+  \ref goldberg88newapproach.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
+  \ref dinic70algorithm, \ref sleator83dynamic.
+- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
+  \ref goldberg88newapproach, \ref sleator83dynamic.
+
+In most cases the \ref Preflow algorithm provides the
 fastest method for computing a maximum flow. All implementations
 also provide functions to query the minimum cut, which is the dual
@@ -394 +400 @@
 
 This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
+"Minimum Cost Flow Problem".
 
 LEMON contains several algorithms for this problem.
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
-   pivot strategies.
- - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-   cost scaling.
- - \ref CapacityScaling Successive Shortest %Path algorithm with optional
-   capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
+   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
+ - \ref CostScaling Cost Scaling algorithm based on push/augment and
+   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
+   \ref bunnagel98efficient.
+ - \ref CapacityScaling Capacity Scaling algorithm based on the successive
+   shortest path method \ref edmondskarp72theoretical.
+ - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
+   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 
 In general NetworkSimplex is the most efficient implementation,
@@ -441 +449 @@
 If you want to find minimum cut just between two distinict nodes,
 see the \ref max_flow "maximum flow problem".
+*/
+
+/**
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles
+\ref clrs01algorithms, \ref amo93networkflows.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
+  \ref dasdan98minmeancycle.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+  version of Karp's algorithm \ref dasdan98minmeancycle.
+- \ref Howard "Howard"'s policy iteration algorithm
+  \ref dasdan98minmeancycle.
+
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
 */
 
@@ -535 +580 @@
 
 /**
-@defgroup lp_group Lp and Mip Solvers
+@defgroup lp_group LP and MIP Solvers
 @ingroup gen_opt_group
-\brief Lp and Mip solver interfaces for LEMON.
-
-This group contains Lp and Mip solver interfaces for LEMON. The
-various LP solvers could be used in the same manner with this
-interface.
+\brief LP and MIP solver interfaces for LEMON.
+
+This group contains LP and MIP solver interfaces for LEMON.
+Various LP solvers could be used in the same manner with this
+high-level interface.
+
+The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
+\ref cplex, \ref soplex.
 */
 
@@ -680 +728 @@
 \brief Skeleton and concept checking classes for graph structures
 
-This group contains the skeletons and concept checking classes of LEMON's
-graph structures and helper classes used to implement these.
+This group contains the skeletons and concept checking classes of
+graph structures.
 */
 

doc/mainpage.dox

@@ -22 +22 @@
 \section intro Introduction
 
-\subsection whatis What is LEMON
-
-LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
-and <b>O</b>ptimization in <b>N</b>etworks.
-It is a C++ template
-library aimed at combinatorial optimization tasks which
-often involve in working
-with graphs.
+<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
+and <b>O</b>ptimization in <b>N</b>etworks</i>.
+It is a C++ template library providing efficient implementations of common
+data structures and algorithms with focus on combinatorial optimization
+tasks connected mainly with graphs and networks. 
 
 <b>
@@ -39 +36 @@
 </b>
 
-\subsection howtoread How to read the documentation
+The project is maintained by the 
+<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
+Combinatorial Optimization</a> \ref egres
+at the Operations Research Department of the
+<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
+Budapest, Hungary.
+LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
+initiative \ref coinor.
+
+\section howtoread How to Read the Documentation
 
 If you would like to get to know the library, see
 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
+
+If you are interested in starting to use the library, see the <a class="el"
+href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
+Guide</a>.
 
 If you know what you are looking for, then try to find it under the

doc/min_cost_flow.dox

@@ -27 +27 @@
 minimum total cost from a set of supply nodes to a set of demand nodes
 in a network with capacity constraints (lower and upper bounds)
-and arc costs.
+and arc costs \ref amo93networkflows.
 
 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
@@ -79 +79 @@
    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
  - For all \f$u\in V\f$ nodes:
-   - \f$\pi(u)<=0\f$;
+   - \f$\pi(u)\leq 0\f$;
    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
      then \f$\pi(u)=0\f$.
@@ -146 +146 @@
    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
  - For all \f$u\in V\f$ nodes:
-   - \f$\pi(u)>=0\f$;
+   - \f$\pi(u)\geq 0\f$;
    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
      then \f$\pi(u)=0\f$.

lemon/Makefile.am

@@ -63 +63 @@
         lemon/binomial_heap.h \
         lemon/bucket_heap.h \
+        lemon/capacity_scaling.h \
         lemon/cbc.h \
         lemon/circulation.h \
@@ -69 +70 @@
         lemon/concept_check.h \
         lemon/connectivity.h \
+        lemon/core.h \
+        lemon/cost_scaling.h \
         lemon/counter.h \
-        lemon/core.h \
         lemon/cplex.h \
+        lemon/cycle_canceling.h \
         lemon/dfs.h \
         lemon/dheap.h \
@@ -87 +90 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/hartmann_orlin.h \
+        lemon/howard.h \
         lemon/hypercube_graph.h \
+        lemon/karp.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \
@@ -104 +110 @@
         lemon/pairing_heap.h \
         lemon/path.h \
+        lemon/planarity.h \
         lemon/preflow.h \
         lemon/quad_heap.h \
@@ -111 +118 @@
         lemon/smart_graph.h \
         lemon/soplex.h \
+        lemon/static_graph.h \
         lemon/suurballe.h \
         lemon/time_measure.h \

lemon/adaptors.h

@@ -361 +361 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -719 +722 @@
   /// by adding or removing nodes or arcs, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time counting for nodes and arcs.
   ///
   /// \tparam DGR The type of the adapted digraph.
@@ -1315 +1320 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \tparam GR The type of the adapted graph.
   /// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -1471 +1478 @@
   /// by adding or removing nodes or arcs/edges, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time item counting.
   ///
   /// \tparam GR The type of the adapted digraph or graph.
@@ -1620 +1629 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides only linear time counting for nodes and arcs.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -1729 +1740 @@
   /// by adding or removing nodes or edges, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides only linear time counting for nodes, edges and arcs.
   ///
   /// \tparam GR The type of the adapted graph.
@@ -2233 +2246 @@
   /// parameter is set to be \c const.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2535 +2551 @@
   /// by adding or removing nodes or arcs, unless the \c GR template
   /// parameter is set to be \c const.
+  ///
+  /// This class provides item counting in the same time as the adapted
+  /// graph structure.
   ///
   /// \tparam GR The type of the adapted graph.
@@ -2678 +2697 @@
   /// arcs).
   /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
+  ///
+  /// This class provides only linear time counting for nodes and arcs.
   ///
   /// \tparam DGR The type of the adapted digraph.
@@ -3326 +3347 @@
   /// in the adaptor.
   ///
+  /// This class provides item counting in the same time as the adapted
+  /// digraph structure.
+  ///
   /// \tparam DGR The type of the adapted digraph.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.

lemon/arg_parser.cc

@@ -21 +21 @@
 namespace lemon {
 
+  void ArgParser::_terminate(ArgParserException::Reason reason) const
+  {
+    if(_exit_on_problems)
+      exit(1);
+    else throw(ArgParserException(reason));
+  }
+  
+  
   void ArgParser::_showHelp(void *p)
   {
     (static_cast<ArgParser*>(p))->showHelp();
-    exit(1);
+    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
   }
 
   ArgParser::ArgParser(int argc, const char * const *argv)
-    :_argc(argc), _argv(argv), _command_name(argv[0]) {
+    :_argc(argc), _argv(argv), _command_name(argv[0]),
+    _exit_on_problems(true) {
     funcOption("-help","Print a short help message",_showHelp,this);
     synonym("help","-help");
@@ -343 +352 @@
         i!=_others_help.end();++i) showHelp(i);
     for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
-    exit(1);
+    _terminate(ArgParserException::HELP);
   }
 
@@ -352 +361 @@
     std::cerr << "\nType '" << _command_name <<
       " --help' to obtain a short summary on the usage.\n\n";
-    exit(1);
+    _terminate(ArgParserException::UNKNOWN_OPT);
   }
 
@@ -415 +424 @@
       std::cerr << "\nType '" << _command_name <<
         " --help' to obtain a short summary on the usage.\n\n";
-      exit(1);
+      _terminate(ArgParserException::INVALID_OPT);
     }
   }

lemon/arg_parser.h

@@ -35 +35 @@
 namespace lemon {
 
+  ///Exception used by ArgParser
+  class ArgParserException : public Exception {
+  public:
+    enum Reason {
+      HELP,         /// <tt>--help</tt> option was given
+      UNKNOWN_OPT,  /// Unknown option was given
+      INVALID_OPT   /// Invalid combination of options
+    };
+    
+  private:
+    Reason _reason;
+    
+  public:
+    ///Constructor
+    ArgParserException(Reason r) throw() : _reason(r) {}
+    ///Virtual destructor
+    virtual ~ArgParserException() throw() {}
+    ///A short description of the exception
+    virtual const char* what() const throw() {
+      switch(_reason)
+        {
+        case HELP:
+          return "lemon::ArgParseException: ask for help";
+          break;
+        case UNKNOWN_OPT:
+          return "lemon::ArgParseException: unknown option";
+          break;
+        case INVALID_OPT:
+          return "lemon::ArgParseException: invalid combination of options";
+          break;
+        }
+      return "";
+    }
+    ///Return the reason for the failure
+    Reason reason() const {return _reason; }
+  };
+
+
   ///Command line arguments parser
 
@@ -104 +142 @@
     std::string _command_name;
 
-
+    
   private:
     //Bind a function to an option.
@@ -116 +154 @@
                     const std::string &help,
                     void (*func)(void *),void *data);
+
+    bool _exit_on_problems;
+    
+    void _terminate(ArgParserException::Reason reason) const;
 
   public:
@@ -381 +423 @@
     const std::vector<std::string> &files() const { return _file_args; }
 
+    ///Throw instead of exit in case of problems
+    void throwOnProblems() 
+    {
+      _exit_on_problems=false;
+    }
   };
 }

lemon/bellman_ford.h

@@ -24 +24 @@
 /// \brief Bellman-Ford algorithm.
 
+#include <lemon/list_graph.h>
 #include <lemon/bits/path_dump.h>
 #include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>
+#include <lemon/tolerance.h>
 #include <lemon/path.h>
 
@@ -34 +36 @@
 namespace lemon {
 
-  /// \brief Default OperationTraits for the BellmanFord algorithm class.
+  /// \brief Default operation traits for the BellmanFord algorithm class.
   ///  
   /// This operation traits class defines all computational operations
@@ -41 +43 @@
   /// If the numeric type does not have infinity value, then the maximum
   /// value is used as extremal infinity value.
+  ///
+  /// \see BellmanFordToleranceOperationTraits
   template <
     typename V, 
     bool has_inf = std::numeric_limits<V>::has_infinity>
   struct BellmanFordDefaultOperationTraits {
-    /// \e
+    /// \brief Value type for the algorithm.
     typedef V Value;
     /// \brief Gives back the zero value of the type.
@@ -84 +88 @@
   };
   
+  /// \brief Operation traits for the BellmanFord algorithm class
+  /// using tolerance.
+  ///
+  /// This operation traits class defines all computational operations
+  /// and constants that are used in the Bellman-Ford algorithm.
+  /// The only difference between this implementation and
+  /// \ref BellmanFordDefaultOperationTraits is that this class uses
+  /// the \ref Tolerance "tolerance technique" in its \ref less()
+  /// function.
+  ///
+  /// \tparam V The value type.
+  /// \tparam eps The epsilon value for the \ref less() function.
+  /// By default, it is the epsilon value used by \ref Tolerance
+  /// "Tolerance<V>".
+  ///
+  /// \see BellmanFordDefaultOperationTraits
+#ifdef DOXYGEN
+  template <typename V, V eps>
+#else
+  template <
+    typename V,
+    V eps = Tolerance<V>::def_epsilon>
+#endif
+  struct BellmanFordToleranceOperationTraits {
+    /// \brief Value type for the algorithm.
+    typedef V Value;
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the positive infinity value of the type.
+    static Value infinity() {
+      return std::numeric_limits<Value>::infinity();
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return left + right;
+    }
+    /// \brief Gives back \c true only if the first value is less than
+    /// the second.
+    static bool less(const Value& left, const Value& right) {
+      return left + eps < right;
+    }
+  };
+
   /// \brief Default traits class of BellmanFord class.
   ///
@@ -107 +156 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
  
@@ -171 +221 @@
   /// the lengths of the arcs. The default map type is
   /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
+  /// "BellmanFordDefaultTraits<GR, LEN>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
@@ -237 +292 @@
         _dist = Traits::createDistMap(*_gr);
       }
-      _mask = new MaskMap(*_gr, false);
+      if(!_mask) {
+        _mask = new MaskMap(*_gr);
+      }
     }
     
@@ -300 +357 @@
     /// \ref named-templ-param "Named parameter" for setting
     /// \c OperationTraits type.
-    /// For more information see \ref BellmanFordDefaultOperationTraits.
+    /// For more information, see \ref BellmanFordDefaultOperationTraits.
     template <class T>
     struct SetOperationTraits
@@ -403 +460 @@
           _process.push_back(it);
           _mask->set(it, true);
+        }
+      } else {
+        for (NodeIt it(*_gr); it != INVALID; ++it) {
+          _mask->set(it, false);
         }
       }
@@ -718 +779 @@
     ///
     /// The shortest path tree used here is equal to the shortest path
-    /// tree used in \ref predNode() and \predMap().
+    /// tree used in \ref predNode() and \ref predMap().
     ///
     /// \pre Either \ref run() or \ref init() must be called before
@@ -733 +794 @@
     ///
     /// The shortest path tree used here is equal to the shortest path
-    /// tree used in \ref predArc() and \predMap().
+    /// tree used in \ref predArc() and \ref predMap().
     ///
     /// \pre Either \ref run() or \ref init() must be called before
@@ -776 +837 @@
     /// length if the algorithm has already found one.
     /// Otherwise it gives back an empty path.
-    lemon::Path<Digraph> negativeCycle() {
+    lemon::Path<Digraph> negativeCycle() const {
       typename Digraph::template NodeMap<int> state(*_gr, -1);
       lemon::Path<Digraph> cycle;
@@ -826 +887 @@
     /// It defines the used operations and the infinity value for the
     /// given \c Value type.
-    /// \see BellmanFordDefaultOperationTraits
+    /// \see BellmanFordDefaultOperationTraits,
+    /// BellmanFordToleranceOperationTraits
     typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
@@ -927 +989 @@
   /// This class should only be used through the \ref bellmanFord()
   /// function, which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class BellmanFordWizard : public TR {

lemon/bfs.h

@@ -64 +64 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -122 +122 @@
   ///\tparam GR The type of the digraph the algorithm runs on.
   ///The default type is \ref ListDigraph.
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref BfsDefaultTraits
+  ///"BfsDefaultTraits<GR>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR,
@@ -702 +707 @@
     ///Runs the algorithm to visit all nodes in the digraph.
 
-    ///This method runs the %BFS algorithm in order to
-    ///compute the shortest path to each node.
-    ///
-    ///The algorithm computes
-    ///- the shortest path tree (forest),
-    ///- the distance of each node from the root(s).
+    ///This method runs the %BFS algorithm in order to visit all nodes
+    ///in the digraph.
     ///
     ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
@@ -853 +854 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
@@ -962 +963 @@
   /// This class should only be used through the \ref bfs() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class BfsWizard : public TR
@@ -1047 +1051 @@
     ///Runs BFS algorithm to visit all nodes in the digraph.
 
-    ///This method runs BFS algorithm in order to compute
-    ///the shortest path to each node.
+    ///This method runs BFS algorithm in order to visit all nodes
+    ///in the digraph.
     void run()
     {
@@ -1300 +1304 @@
   /// does not observe the BFS events. If you want to observe the BFS
   /// events, you should implement your own visitor class.
-  /// \tparam TR Traits class to set various data types used by the
-  /// algorithm. The default traits class is
-  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
-  /// See \ref BfsVisitDefaultTraits for the documentation of
-  /// a BFS visit traits class.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
+  /// "BfsVisitDefaultTraits<GR>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename VS, typename TR>
@@ -1696 +1700 @@
     /// \brief Runs the algorithm to visit all nodes in the digraph.
     ///
-    /// This method runs the %BFS algorithm in order to
-    /// compute the shortest path to each node.
-    ///
-    /// The algorithm computes
-    /// - the shortest path tree (forest),
-    /// - the distance of each node from the root(s).
+    /// This method runs the %BFS algorithm in order to visit all nodes
+    /// in the digraph.
     ///
     /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.

lemon/bits/graph_extender.h

@@ -57 +57 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
@@ -356 +356 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
 
-    Edge fromId(int id, Edge) const {
+    static Edge fromId(int id, Edge) {
       return Parent::edgeFromId(id);
     }

lemon/bits/map_extender.h

@@ -85 +85 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
+        : Parent(item), map(&_map) {}
+
+      MapIt& operator++() {
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+      typename MapTraits<Map>::ConstReturnValue operator*() const {
+        return (*map)[*this];
+      }
+
+      typename MapTraits<Map>::ReturnValue operator*() {
+        return (*map)[*this];
+      }
+
+      void set(const Value& value) {
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
+
+    };
+
+    class ConstMapIt : public Item {
+      typedef Item Parent;
+
+    public:
+
+      typedef typename Map::Value Value;
+
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
+      }
+
+      ConstMapIt(const Map& _map, const Item& item)
         : Parent(item), map(_map) {}
 
-      MapIt& operator++() {
-        map.notifier()->next(*this);
+      ConstMapIt& operator++() {
+        map->notifier()->next(*this);
         return *this;
       }
@@ -105 +145 @@
       }
 
-      typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
-      }
-
-      void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
-
-    };
-
-    class ConstMapIt : public Item {
-      typedef Item Parent;
-
-    public:
-
-      typedef typename Map::Value Value;
-
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
-      }
-
-      ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
-
-      ConstMapIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-      typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+    protected:
+      const Map* map;
     };
 
@@ -153 +153 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };
@@ -232 +232 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       MapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
+        return (*map)[*this];
       }
 
       typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
+        return (*map)[*this];
       }
 
       void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
 
     };
@@ -272 +272 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ConstMapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+        return (*map)[*this];
+      }
+
+    protected:
+      const Map* map;
     };
 
@@ -300 +300 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.graph.next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->graph.next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };

lemon/cbc.cc

@@ -95 +95 @@
   }
 
+  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+    return _prob->numberRows() - 1;
+  }
 
   void CbcMip::_eraseCol(int i) {

lemon/cbc.h

@@ -63 +63 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);

lemon/circulation.h

@@ -174 +174 @@
      \tparam SM The type of the supply map. The default map type is
      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
+     \tparam TR The traits class that defines various types used by the
+     algorithm. By default, it is \ref CirculationDefaultTraits
+     "CirculationDefaultTraits<GR, LM, UM, SM>".
+     In most cases, this parameter should not be set directly,
+     consider to use the named template parameters instead.
   */
 #ifdef DOXYGEN
@@ -307 +312 @@
     /// able to automatically created by the algorithm (i.e. the
     /// digraph and the maximum level should be passed to it).
-    /// However an external elevator object could also be passed to the
+    /// However, an external elevator object could also be passed to the
     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
     /// before calling \ref run() or \ref init().

lemon/clp.cc

@@ -79 +79 @@
   }
 
+  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+    return _prob->numberRows() - 1;
+  }
+
 
   void ClpLp::_eraseCol(int c) {

lemon/clp.h

@@ -76 +76 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);

lemon/concepts/digraph.h

@@ -36 +36 @@
     /// \brief Class describing the concept of directed graphs.
     ///
-    /// This class describes the \ref concept "concept" of the
-    /// immutable directed digraphs.
+    /// This class describes the common interface of all directed
+    /// graphs (digraphs).
     ///
-    /// Note that actual digraph implementation like @ref ListDigraph or
-    /// @ref SmartDigraph may have several additional functionality.
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// directed graphs should compile with this class, but it will not
+    /// run properly, of course.
+    /// An actual digraph implementation like \ref ListDigraph or
+    /// \ref SmartDigraph may have additional functionality.
     ///
-    /// \sa concept
+    /// \sa Graph
     class Digraph {
     private:
-      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
-
-      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
-      ///
-      Digraph(const Digraph &) {};
-      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
-      ///\e not allowed. Use DigraphCopy() instead.
-
-      ///Assignment of \ref Digraph "Digraph"s to another ones are
-      ///\e not allowed.  Use DigraphCopy() instead.
-
+      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
+      Digraph(const Digraph &) {}
+      /// \brief Assignment of a digraph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
       void operator=(const Digraph &) {}
+
     public:
-      ///\e
-
-      /// Defalult constructor.
-
-      /// Defalult constructor.
-      ///
+      /// Default constructor.
       Digraph() { }
-      /// Class for identifying a node of the digraph
+
+      /// The node type of the digraph
 
       /// This class identifies a node of the digraph. It also serves
       /// as a base class of the node iterators,
-      /// thus they will convert to this type.
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
@@ -83 +77 @@
         Node(const Node&) { }
 
-        /// Invalid constructor \& conversion.
-
-        /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
 
         /// Inequality operator
 
-        /// \sa operator==(Node n)
-        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of digraph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the nodes; this order has nothing to do with the iteration
+        /// ordering of the nodes.
         bool operator<(Node) const { return false; }
-
-      };
-
-      /// This iterator goes through each node.
-
-      /// This iterator goes through each node.
-      /// Its usage is quite simple, for example you can count the number
-      /// of nodes in digraph \c g of type \c Digraph like this:
+      };
+
+      /// Iterator class for the nodes.
+
+      /// This iterator goes through each node of the digraph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of nodes in a digraph \c g of type \c %Digraph like this:
       ///\code
       /// int count=0;
@@ -125 +118 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
@@ -133 +126 @@
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
-        /// Invalid constructor \& conversion.
-
-        /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
 
-        /// Sets the iterator to the first node of \c g.
-        ///
-        NodeIt(const Digraph&) { }
-        /// Node -> NodeIt conversion.
-
-        /// Sets the iterator to the node of \c the digraph pointed by
-        /// the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Digraph&) { }
+        /// Sets the iterator to the given node.
+
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Digraph&, const Node&) { }
         /// Next node.
@@ -158 +149 @@
 
 
-      /// Class for identifying an arc of the digraph
+      /// The arc type of the digraph
 
       /// This class identifies an arc of the digraph. It also serves
@@ -167 +158 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
@@ -175 +166 @@
         ///
         Arc(const Arc&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Arc n)
-        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of digraph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
       };
 
-      /// This iterator goes trough the outgoing arcs of a node.
+      /// Iterator class for the outgoing arcs of a node.
 
       /// This iterator goes trough the \e outgoing arcs of a certain node
       /// of a digraph.
-      /// Its usage is quite simple, for example you can count the number
+      /// Its usage is quite simple, for example, you can count the number
       /// of outgoing arcs of a node \c n
-      /// in digraph \c g of type \c Digraph as follows.
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
-      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class OutArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
@@ -226 +216 @@
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first outgoing arc.
-
-        /// This constructor sets the iterator to the first outgoing arc of
-        /// the node.
+        /// Sets the iterator to the first outgoing arc.
+
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Digraph&, const Node&) { }
-        /// Arc -> OutArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         OutArcIt(const Digraph&, const Arc&) { }
-        ///Next outgoing arc
+        /// Next outgoing arc
 
         /// Assign the iterator to the next
@@ -249 +238 @@
       };
 
-      /// This iterator goes trough the incoming arcs of a node.
+      /// Iterator class for the incoming arcs of a node.
 
       /// This iterator goes trough the \e incoming arcs of a certain node
       /// of a digraph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of outgoing arcs of a node \c n
-      /// in digraph \c g of type \c Digraph as follows.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of incoming arcs of a node \c n
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
-      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class InArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
@@ -273 +261 @@
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
-        /// This constructor sets the iterator to first incoming arc.
-
-        /// This constructor set the iterator to the first incoming arc of
-        /// the node.
+        /// Sets the iterator to the first incoming arc.
+
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Digraph&, const Node&) { }
-        /// Arc -> InArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         InArcIt(const Digraph&, const Arc&) { }
         /// Next incoming arc
 
-        /// Assign the iterator to the next inarc of the corresponding node.
-        ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
-      /// This iterator goes through each arc.
-
-      /// This iterator goes through each arc of a digraph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of arcs in a digraph \c g of type \c Digraph as follows:
+
+      /// Iterator class for the arcs.
+
+      /// This iterator goes through each arc of the digraph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of arcs in a digraph \c g of type \c %Digraph as follows:
       ///\code
       /// int count=0;
-      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
@@ -308 +296 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
@@ -316 +304 @@
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first arc.
-
-        /// This constructor sets the iterator to the first arc of \c g.
-        ///@param g the digraph
-        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
-        /// Arc -> ArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+
+        /// Sets the iterator to the first arc of the given digraph.
+        ///
+        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         ArcIt(const Digraph&, const Arc&) { }
-        ///Next arc
+        /// Next arc
 
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
-      ///Gives back the target node of an arc.
-
-      ///Gives back the target node of an arc.
-      ///
+
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
+      Node source(Arc) const { return INVALID; }
+
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
-      ///Gives back the source node of an arc.
-
-      ///Gives back the source node of an arc.
-      ///
-      Node source(Arc) const { return INVALID; }
-
-      /// \brief Returns the ID of the node.
+
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
 
-      /// \brief Returns the ID of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
 
-      /// \brief Returns the node with the given ID.
-      ///
-      /// \pre The argument should be a valid node ID in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the digraph.
       Node nodeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the arc with the given ID.
-      ///
-      /// \pre The argument should be a valid arc ID in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the digraph.
       Arc arcFromId(int) const { return INVALID; }
 
-      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
 
@@ -393 +391 @@
       int maxId(Arc) const { return -1; }
 
+      /// \brief The opposite node on the arc.
+      ///
+      /// Returns the opposite node on the given arc.
+      Node oppositeNode(Node, Arc) const { return INVALID; }
+
       /// \brief The base node of the iterator.
       ///
-      /// Gives back the base node of the iterator.
-      /// It is always the target of the pointed arc.
-      Node baseNode(const InArcIt&) const { return INVALID; }
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
 
       /// \brief The running node of the iterator.
       ///
-      /// Gives back the running node of the iterator.
-      /// It is always the source of the pointed arc.
-      Node runningNode(const InArcIt&) const { return INVALID; }
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
 
       /// \brief The base node of the iterator.
       ///
-      /// Gives back the base node of the iterator.
-      /// It is always the source of the pointed arc.
-      Node baseNode(const OutArcIt&) const { return INVALID; }
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
 
       /// \brief The running node of the iterator.
       ///
-      /// Gives back the running node of the iterator.
-      /// It is always the target of the pointed arc.
-      Node runningNode(const OutArcIt&) const { return INVALID; }
-
-      /// \brief The opposite node on the given arc.
-      ///
-      /// Gives back the opposite node on the given arc.
-      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
-
-      /// \brief Reference map of the nodes to type \c T.
-      ///
-      /// Reference map of the nodes to type \c T.
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
+
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
       public:
 
-        ///\e
-        NodeMap(const Digraph&) { }
-        ///\e
+        /// Constructor
+        explicit NodeMap(const Digraph&) { }
+        /// Constructor with given initial value
         NodeMap(const Digraph&, T) { }
 
@@ -446 +445 @@
       };
 
-      /// \brief Reference map of the arcs to type \c T.
-      ///
-      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
       public:
 
-        ///\e
-        ArcMap(const Digraph&) { }
-        ///\e
+        /// Constructor
+        explicit ArcMap(const Digraph&) { }
+        /// Constructor with given initial value
         ArcMap(const Digraph&, T) { }
+
       private:
         ///Copy constructor

lemon/concepts/graph.h

@@ -19 +19 @@
 ///\ingroup graph_concepts
 ///\file
-///\brief The concept of Undirected Graphs.
+///\brief The concept of undirected graphs.
 
 #ifndef LEMON_CONCEPTS_GRAPH_H
@@ -25 +25 @@
 
 #include <lemon/concepts/graph_components.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/concept_check.h>
 #include <lemon/core.h>
 
@@ -32 +34 @@
     /// \ingroup graph_concepts
     ///
-    /// \brief Class describing the concept of Undirected Graphs.
+    /// \brief Class describing the concept of undirected graphs.
     ///
-    /// This class describes the common interface of all Undirected
-    /// Graphs.
+    /// This class describes the common interface of all undirected
+    /// graphs.
     ///
-    /// As all concept describing classes it provides only interface
-    /// without any sensible implementation. So any algorithm for
-    /// undirected graph should compile with this class, but it will not
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// undirected graphs should compile with this class, but it will not
     /// run properly, of course.
+    /// An actual graph implementation like \ref ListGraph or
+    /// \ref SmartGraph may have additional functionality.    
     ///
-    /// The LEMON undirected graphs also fulfill the concept of
-    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
-    /// Concept"). Each edges can be seen as two opposite
-    /// directed arc and consequently the undirected graph can be
-    /// seen as the direceted graph of these directed arcs. The
-    /// Graph has the Edge inner class for the edges and
-    /// the Arc type for the directed arcs. The Arc type is
-    /// convertible to Edge or inherited from it so from a directed
-    /// arc we can get the represented edge.
+    /// The undirected graphs also fulfill the concept of \ref Digraph
+    /// "directed graphs", since each edge can also be regarded as two
+    /// oppositely directed arcs.
+    /// Undirected graphs provide an Edge type for the undirected edges and
+    /// an Arc type for the directed arcs. The Arc type is convertible to
+    /// Edge or inherited from it, i.e. the corresponding edge can be
+    /// obtained from an arc.
+    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
+    /// and ArcMap classes can be used for the arcs (just like in digraphs).
+    /// Both InArcIt and OutArcIt iterates on the same edges but with
+    /// opposite direction. IncEdgeIt also iterates on the same edges
+    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
+    /// only to Edge.
     ///
-    /// In the sense of the LEMON each edge has a default
-    /// direction (it should be in every computer implementation,
-    /// because the order of edge's nodes defines an
-    /// orientation). With the default orientation we can define that
-    /// the directed arc is forward or backward directed. With the \c
-    /// direction() and \c direct() function we can get the direction
-    /// of the directed arc and we can direct an edge.
+    /// In LEMON, each undirected edge has an inherent orientation.
+    /// Thus it can defined if an arc is forward or backward oriented in
+    /// an undirected graph with respect to this default oriantation of
+    /// the represented edge.
+    /// With the direction() and direct() functions the direction
+    /// of an arc can be obtained and set, respectively.
     ///
-    /// The EdgeIt is an iterator for the edges. We can use
-    /// the EdgeMap to map values for the edges. The InArcIt and
-    /// OutArcIt iterates on the same edges but with opposite
-    /// direction. The IncEdgeIt iterates also on the same edges
-    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
-    /// to Edge.
+    /// Only nodes and edges can be added to or removed from an undirected
+    /// graph and the corresponding arcs are added or removed automatically.
+    ///
+    /// \sa Digraph
     class Graph {
+    private:
+      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+      Graph(const Graph&) {}
+      /// \brief Assignment of a graph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
+      void operator=(const Graph&) {}
+
     public:
-      /// \brief The undirected graph should be tagged by the
-      /// UndirectedTag.
-      ///
-      /// The undirected graph should be tagged by the UndirectedTag. This
-      /// tag helps the enable_if technics to make compile time
+      /// Default constructor.
+      Graph() {}
+
+      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
+      ///
+      /// Undirected graphs should be tagged with \c UndirectedTag.
+      /// 
+      /// This tag helps the \c enable_if technics to make compile time
       /// specializations for undirected graphs.
       typedef True UndirectedTag;
 
-      /// \brief The base type of node iterators,
-      /// or in other words, the trivial node iterator.
-      ///
-      /// This is the base type of each node iterator,
-      /// thus each kind of node iterator converts to this.
-      /// More precisely each kind of node iterator should be inherited
-      /// from the trivial node iterator.
+      /// The node type of the graph
+
+      /// This class identifies a node of the graph. It also serves
+      /// as a base class of the node iterators,
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
@@ -96 +109 @@
         Node(const Node&) { }
 
-        /// Invalid constructor \& conversion.
-
-        /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
 
         /// Inequality operator
 
-        /// \sa operator==(Node n)
-        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
         /// the items; this order has nothing to do with the iteration
         /// ordering of the items.
@@ -125 +138 @@
       };
 
-      /// This iterator goes through each node.
-
-      /// This iterator goes through each node.
-      /// Its usage is quite simple, for example you can count the number
-      /// of nodes in graph \c g of type \c Graph like this:
+      /// Iterator class for the nodes.
+
+      /// This iterator goes through each node of the graph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of nodes in a graph \c g of type \c %Graph like this:
       ///\code
       /// int count=0;
@@ -138 +151 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
@@ -146 +159 @@
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
-        /// Invalid constructor \& conversion.
-
-        /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
 
-        /// Sets the iterator to the first node of \c g.
-        ///
-        NodeIt(const Graph&) { }
-        /// Node -> NodeIt conversion.
-
-        /// Sets the iterator to the node of \c the graph pointed by
-        /// the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Graph&) { }
+        /// Sets the iterator to the given node.
+
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Graph&, const Node&) { }
         /// Next node.
@@ -171 +182 @@
 
 
-      /// The base type of the edge iterators.
-
-      /// The base type of the edge iterators.
-      ///
+      /// The edge type of the graph
+
+      /// This class identifies an edge of the graph. It also serves
+      /// as a base class of the edge iterators,
+      /// thus they will convert to this type.
       class Edge {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Edge() { }
         /// Copy constructor.
@@ -187 +199 @@
         ///
         Edge(const Edge&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Edge(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Edge) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Edge n)
-        ///
+        /// Inequality operator.
         bool operator!=(Edge) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the edges; this order has nothing to do with the iteration
+        /// ordering of the edges.
         bool operator<(Edge) const { return false; }
       };
 
-      /// This iterator goes through each edge.
-
-      /// This iterator goes through each edge of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of edges in a graph \c g of type \c Graph as follows:
+      /// Iterator class for the edges.
+
+      /// This iterator goes through each edge of the graph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of edges in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
@@ -227 +239 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         EdgeIt() { }
         /// Copy constructor.
@@ -235 +247 @@
         ///
         EdgeIt(const EdgeIt& e) : Edge(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         EdgeIt(Invalid) { }
-        /// This constructor sets the iterator to the first edge.
-
-        /// This constructor sets the iterator to the first edge.
-        EdgeIt(const Graph&) { }
-        /// Edge -> EdgeIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the edge-set, the iteration order is the
-        /// same.
+        /// Sets the iterator to the first edge.
+
+        /// Sets the iterator to the first edge of the given graph.
+        ///
+        explicit EdgeIt(const Graph&) { }
+        /// Sets the iterator to the given edge.
+
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         EdgeIt(const Graph&, const Edge&) { }
         /// Next edge
 
         /// Assign the iterator to the next edge.
+        ///
         EdgeIt& operator++() { return *this; }
       };
 
-      /// \brief This iterator goes trough the incident undirected
-      /// arcs of a node.
-      ///
-      /// This iterator goes trough the incident edges
-      /// of a certain node of a graph. You should assume that the
-      /// loop arcs will be iterated twice.
-      ///
-      /// Its usage is quite simple, for example you can compute the
-      /// degree (i.e. count the number of incident arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// Iterator class for the incident edges of a node.
+
+      /// This iterator goes trough the incident undirected edges
+      /// of a certain node of a graph.
+      /// Its usage is quite simple, for example, you can compute the
+      /// degree (i.e. the number of incident edges) of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///
       ///\code
@@ -272 +281 @@
       /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
       ///\endcode
+      ///
+      /// \warning Loop edges will be iterated twice.
       class IncEdgeIt : public Edge {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         IncEdgeIt() { }
         /// Copy constructor.
@@ -284 +295 @@
         ///
         IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         IncEdgeIt(Invalid) { }
-        /// This constructor sets the iterator to first incident arc.
-
-        /// This constructor set the iterator to the first incident arc of
-        /// the node.
+        /// Sets the iterator to the first incident edge.
+
+        /// Sets the iterator to the first incident edge of the given node.
+        ///
         IncEdgeIt(const Graph&, const Node&) { }
-        /// Edge -> IncEdgeIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given edge.
+
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         IncEdgeIt(const Graph&, const Edge&) { }
-        /// Next incident arc
-
-        /// Assign the iterator to the next incident arc
+        /// Next incident edge
+
+        /// Assign the iterator to the next incident edge
         /// of the corresponding node.
         IncEdgeIt& operator++() { return *this; }
       };
 
-      /// The directed arc type.
-
-      /// The directed arc type. It can be converted to the
-      /// edge or it should be inherited from the undirected
-      /// edge.
+      /// The arc type of the graph
+
+      /// This class identifies a directed arc of the graph. It also serves
+      /// as a base class of the arc iterators,
+      /// thus they will convert to this type.
       class Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
@@ -324 +334 @@
         ///
         Arc(const Arc&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Arc n)
-        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
 
-        /// Converison to Edge
+        /// Converison to \c Edge
+        
+        /// Converison to \c Edge.
+        ///
         operator Edge() const { return Edge(); }
       };
-      /// This iterator goes through each directed arc.
-
-      /// This iterator goes through each arc of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of arcs in a graph \c g of type \c Graph as follows:
+
+      /// Iterator class for the arcs.
+
+      /// This iterator goes through each directed arc of the graph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of arcs in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
-      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
@@ -366 +380 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
@@ -374 +388 @@
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first arc.
-
-        /// This constructor sets the iterator to the first arc of \c g.
-        ///@param g the graph
-        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
-        /// Arc -> ArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+
+        /// Sets the iterator to the first arc of the given graph.
+        ///
+        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         ArcIt(const Graph&, const Arc&) { }
-        ///Next arc
+        /// Next arc
 
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
 
-      /// This iterator goes trough the outgoing directed arcs of a node.
-
-      /// This iterator goes trough the \e outgoing arcs of a certain node
-      /// of a graph.
-      /// Its usage is quite simple, for example you can count the number
+      /// Iterator class for the outgoing arcs of a node.
+
+      /// This iterator goes trough the \e outgoing directed arcs of a
+      /// certain node of a graph.
+      /// Its usage is quite simple, for example, you can count the number
       /// of outgoing arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
-      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class OutArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
@@ -420 +433 @@
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first outgoing arc.
-
-        /// This constructor sets the iterator to the first outgoing arc of
-        /// the node.
-        ///@param n the node
-        ///@param g the graph
+        /// Sets the iterator to the first outgoing arc.
+
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Graph& n, const Node& g) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
         }
-        /// Arc -> OutArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         OutArcIt(const Graph&, const Arc&) { }
-        ///Next outgoing arc
+        /// Next outgoing arc
 
         /// Assign the iterator to the next
@@ -448 +458 @@
       };
 
-      /// This iterator goes trough the incoming directed arcs of a node.
-
-      /// This iterator goes trough the \e incoming arcs of a certain node
-      /// of a graph.
-      /// Its usage is quite simple, for example you can count the number
-      /// of outgoing arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// Iterator class for the incoming arcs of a node.
+
+      /// This iterator goes trough the \e incoming directed arcs of a
+      /// certain node of a graph.
+      /// Its usage is quite simple, for example, you can count the number
+      /// of incoming arcs of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
-      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class InArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
@@ -472 +481 @@
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
-        /// This constructor sets the iterator to first incoming arc.
-
-        /// This constructor set the iterator to the first incoming arc of
-        /// the node.
-        ///@param n the node
-        ///@param g the graph
+        /// Sets the iterator to the first incoming arc.
+
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Graph& g, const Node& n) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
         }
-        /// Arc -> InArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         InArcIt(const Graph&, const Arc&) { }
         /// Next incoming arc
 
-        /// Assign the iterator to the next inarc of the corresponding node.
-        ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
 
-      /// \brief Reference map of the nodes to type \c T.
-      ///
-      /// Reference map of the nodes to type \c T.
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
@@ -508 +515 @@
       public:
 
-        ///\e
-        NodeMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit NodeMap(const Graph&) { }
+        /// Constructor with given initial value
         NodeMap(const Graph&, T) { }
 
@@ -525 +532 @@
       };
 
-      /// \brief Reference map of the arcs to type \c T.
-      ///
-      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
@@ -533 +541 @@
       public:
 
-        ///\e
-        ArcMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit ArcMap(const Graph&) { }
+        /// Constructor with given initial value
         ArcMap(const Graph&, T) { }
+
       private:
         ///Copy constructor
@@ -549 +558 @@
       };
 
-      /// Reference map of the edges to type \c T.
-
-      /// Reference map of the edges to type \c T.
+      /// \brief Standard graph map type for the edges.
+      ///
+      /// Standard graph map type for the edges.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
@@ -557 +567 @@
       public:
 
-        ///\e
-        EdgeMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit EdgeMap(const Graph&) { }
+        /// Constructor with given initial value
         EdgeMap(const Graph&, T) { }
+
       private:
         ///Copy constructor
@@ -573 +584 @@
       };
 
-      /// \brief Direct the given edge.
-      ///
-      /// Direct the given edge. The returned arc source
-      /// will be the given node.
-      Arc direct(const Edge&, const Node&) const {
-        return INVALID;
-      }
-
-      /// \brief Direct the given edge.
-      ///
-      /// Direct the given edge. The returned arc
-      /// represents the given edge and the direction comes
-      /// from the bool parameter. The source of the edge and
-      /// the directed arc is the same when the given bool is true.
-      Arc direct(const Edge&, bool) const {
-        return INVALID;
-      }
-
-      /// \brief Returns true if the arc has default orientation.
-      ///
-      /// Returns whether the given directed arc is same orientation as
-      /// the corresponding edge's default orientation.
-      bool direction(Arc) const { return true; }
-
-      /// \brief Returns the opposite directed arc.
-      ///
-      /// Returns the opposite directed arc.
-      Arc oppositeArc(Arc) const { return INVALID; }
-
-      /// \brief Opposite node on an arc
-      ///
-      /// \return The opposite of the given node on the given edge.
-      Node oppositeNode(Node, Edge) const { return INVALID; }
-
-      /// \brief First node of the edge.
-      ///
-      /// \return The first node of the given edge.
-      ///
-      /// Naturally edges don't have direction and thus
-      /// don't have source and target node. However we use \c u() and \c v()
-      /// methods to query the two nodes of the arc. The direction of the
-      /// arc which arises this way is called the inherent direction of the
-      /// edge, and is used to define the "default" direction
-      /// of the directed versions of the arcs.
+      /// \brief The first node of the edge.
+      ///
+      /// Returns the first node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however, methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa v()
       /// \sa direction()
       Node u(Edge) const { return INVALID; }
 
-      /// \brief Second node of the edge.
-      ///
-      /// \return The second node of the given edge.
-      ///
-      /// Naturally edges don't have direction and thus
-      /// don't have source and target node. However we use \c u() and \c v()
-      /// methods to query the two nodes of the arc. The direction of the
-      /// arc which arises this way is called the inherent direction of the
-      /// edge, and is used to define the "default" direction
-      /// of the directed versions of the arcs.
+      /// \brief The second node of the edge.
+      ///
+      /// Returns the second node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however, methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa u()
       /// \sa direction()
       Node v(Edge) const { return INVALID; }
 
-      /// \brief Source node of the directed arc.
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
       Node source(Arc) const { return INVALID; }
 
-      /// \brief Target node of the directed arc.
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
 
-      /// \brief Returns the id of the node.
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
 
-      /// \brief Returns the id of the edge.
+      /// \brief The ID of the edge.
+      ///
+      /// Returns the ID of the given edge.
       int id(Edge) const { return -1; }
 
-      /// \brief Returns the id of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
 
-      /// \brief Returns the node with the given id.
-      ///
-      /// \pre The argument should be a valid node id in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the graph.
       Node nodeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the edge with the given id.
-      ///
-      /// \pre The argument should be a valid edge id in the graph.
+      /// \brief The edge with the given ID.
+      ///
+      /// Returns the edge with the given ID.
+      /// \pre The argument should be a valid edge ID in the graph.
       Edge edgeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the arc with the given id.
-      ///
-      /// \pre The argument should be a valid arc id in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the graph.
       Arc arcFromId(int) const { return INVALID; }
 
-      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the edge IDs.
+      /// \brief An upper bound on the edge IDs.
+      ///
+      /// Returns an upper bound on the edge IDs.
       int maxEdgeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
+
+      /// \brief The direction of the arc.
+      ///
+      /// Returns \c true if the direction of the given arc is the same as
+      /// the inherent orientation of the represented edge.
+      bool direction(Arc) const { return true; }
+
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc
+      /// represents the given edge and its direction comes
+      /// from the bool parameter. If it is \c true, then the direction
+      /// of the arc is the same as the inherent orientation of the edge.
+      Arc direct(Edge, bool) const {
+        return INVALID;
+      }
+
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc represents the given
+      /// edge and its source node is the given node.
+      Arc direct(Edge, Node) const {
+        return INVALID;
+      }
+
+      /// \brief The oppositely directed arc.
+      ///
+      /// Returns the oppositely directed arc representing the same edge.
+      Arc oppositeArc(Arc) const { return INVALID; }
+
+      /// \brief The opposite node on the edge.
+      ///
+      /// Returns the opposite node on the given edge.
+      Node oppositeNode(Node, Edge) const { return INVALID; }
 
       void first(Node&) const {}
@@ -706 +734 @@
       int maxId(Arc) const { return -1; }
 
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node (the source in this case) of the iterator
-      Node baseNode(OutArcIt e) const {
-        return source(e);
-      }
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node (the target in this case) of the
-      /// iterator
-      Node runningNode(OutArcIt e) const {
-        return target(e);
-      }
-
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node (the target in this case) of the iterator
-      Node baseNode(InArcIt e) const {
-        return target(e);
-      }
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node (the source in this case) of the
-      /// iterator
-      Node runningNode(InArcIt e) const {
-        return source(e);
-      }
-
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node of the iterator
-      Node baseNode(IncEdgeIt) const {
-        return INVALID;
-      }
-
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node of the iterator
-      Node runningNode(IncEdgeIt) const {
-        return INVALID;
-      }
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incident edge iterator.
+      Node baseNode(IncEdgeIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incident edge iterator.
+      Node runningNode(IncEdgeIt) const { return INVALID; }
+
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
+
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
 
       template <typename _Graph>

lemon/concepts/graph_components.h

@@ -19 +19 @@
 ///\ingroup graph_concepts
 ///\file
-///\brief The concept of graph components.
+///\brief The concepts of graph components.
 
 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
@@ -93 +93 @@
       /// associative containers (e.g. \c std::map).
       ///
-      /// \note This operator only have to define some strict ordering of
+      /// \note This operator only has to define some strict ordering of
       /// the items; this order has nothing to do with the iteration
       /// ordering of the items.

lemon/concepts/heap.h

@@ -89 +89 @@
       /// handle the cross references. The assigned value must be
       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
+#ifdef DOXYGEN
       explicit Heap(ItemIntMap &map) {}
+#else
+      explicit Heap(ItemIntMap&) {}
+#endif      
 
       /// \brief Constructor.
@@ -99 +103 @@
       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
       /// \param comp The function object used for comparing the priorities.
+#ifdef DOXYGEN
       explicit Heap(ItemIntMap &map, const CMP &comp) {}
+#else
+      explicit Heap(ItemIntMap&, const CMP&) {}
+#endif      
 
       /// \brief The number of items stored in the heap.
@@ -127 +135 @@
       /// \param p The priority of the item.
       /// \pre \e i must not be stored in the heap.
+#ifdef DOXYGEN
       void push(const Item &i, const Prio &p) {}
+#else
+      void push(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Return the item having minimum priority.
@@ -133 +145 @@
       /// This function returns the item having minimum priority.
       /// \pre The heap must be non-empty.
-      Item top() const {}
+      Item top() const { return Item(); }
 
       /// \brief The minimum priority.
@@ -139 +151 @@
       /// This function returns the minimum priority.
       /// \pre The heap must be non-empty.
-      Prio prio() const {}
+      Prio prio() const { return Prio(); }
 
       /// \brief Remove the item having minimum priority.
@@ -153 +165 @@
       /// \param i The item to delete.
       /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
       void erase(const Item &i) {}
+#else
+      void erase(const Item&) {}
+#endif      
 
       /// \brief The priority of the given item.
@@ -160 +176 @@
       /// \param i The item.
       /// \pre \e i must be in the heap.
+#ifdef DOXYGEN
       Prio operator[](const Item &i) const {}
+#else
+      Prio operator[](const Item&) const { return Prio(); }
+#endif      
 
       /// \brief Set the priority of an item or insert it, if it is
@@ -171 +191 @@
       /// \param i The item.
       /// \param p The priority.
+#ifdef DOXYGEN
       void set(const Item &i, const Prio &p) {}
+#else
+      void set(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Decrease the priority of an item to the given value.
@@ -179 +203 @@
       /// \param p The priority.
       /// \pre \e i must be stored in the heap with priority at least \e p.
+#ifdef DOXYGEN
       void decrease(const Item &i, const Prio &p) {}
+#else
+      void decrease(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Increase the priority of an item to the given value.
@@ -187 +215 @@
       /// \param p The priority.
       /// \pre \e i must be stored in the heap with priority at most \e p.
+#ifdef DOXYGEN
       void increase(const Item &i, const Prio &p) {}
+#else
+      void increase(const Item&, const Prio&) {}
+#endif      
 
       /// \brief Return the state of an item.
@@ -197 +229 @@
       /// to the heap again.
       /// \param i The item.
+#ifdef DOXYGEN
       State state(const Item &i) const {}
+#else
+      State state(const Item&) const { return PRE_HEAP; }
+#endif      
 
       /// \brief Set the state of an item in the heap.
@@ -206 +242 @@
       /// \param i The item.
       /// \param st The state. It should not be \c IN_HEAP.
+#ifdef DOXYGEN
       void state(const Item& i, State st) {}
+#else
+      void state(const Item&, State) {}
+#endif      
 
 

lemon/concepts/path.h

@@ -19 +19 @@
 ///\ingroup concept
 ///\file
-///\brief Classes for representing paths in digraphs.
+///\brief The concept of paths
 ///
 
@@ -39 +39 @@
     /// A skeleton structure for representing directed paths in a
     /// digraph.
+    /// In a sense, a path can be treated as a list of arcs.
+    /// LEMON path types just store this list. As a consequence, they cannot
+    /// enumerate the nodes on the path directly and a zero length path
+    /// cannot store its source node.
+    ///
+    /// The arcs of a path should be stored in the order of their directions,
+    /// i.e. the target node of each arc should be the same as the source
+    /// node of the next arc. This consistency could be checked using
+    /// \ref checkPath().
+    /// The source and target nodes of a (consistent) path can be obtained
+    /// using \ref pathSource() and \ref pathTarget().
+    ///
+    /// A path can be constructed from another path of any type using the
+    /// copy constructor or the assignment operator.
+    ///
     /// \tparam GR The digraph type in which the path is.
-    ///
-    /// In a sense, the path can be treated as a list of arcs. The
-    /// lemon path type stores just this list. As a consequence it
-    /// cannot enumerate the nodes in the path and the zero length
-    /// paths cannot store the source.
-    ///
     template <typename GR>
     class Path {
@@ -60 +69 @@
       Path() {}
 
-      /// \brief Template constructor
+      /// \brief Template copy constructor
       template <typename CPath>
       Path(const CPath& cpath) {}
 
-      /// \brief Template assigment
+      /// \brief Template assigment operator
       template <typename CPath>
       Path& operator=(const CPath& cpath) {
@@ -71 +80 @@
       }
 
-      /// Length of the path ie. the number of arcs in the path.
+      /// Length of the path, i.e. the number of arcs on the path.
       int length() const { return 0;}
 
@@ -80 +89 @@
       void clear() {}
 
-      /// \brief LEMON style iterator for path arcs
+      /// \brief LEMON style iterator for enumerating the arcs of a path.
       ///
-      /// This class is used to iterate on the arcs of the paths.
+      /// LEMON style iterator class for enumerating the arcs of a path.
       class ArcIt {
       public:
@@ -89 +98 @@
         /// Invalid constructor
         ArcIt(Invalid) {}
-        /// Constructor for first arc
+        /// Sets the iterator to the first arc of the given path
         ArcIt(const Path &) {}
 
-        /// Conversion to Arc
+        /// Conversion to \c Arc
         operator Arc() const { return INVALID; }
 
@@ -193 +202 @@
     ///
     /// A skeleton structure for path dumpers. The path dumpers are
-    /// the generalization of the paths. The path dumpers can
-    /// enumerate the arcs of the path wheter in forward or in
-    /// backward order.  In most time these classes are not used
-    /// directly rather it used to assign a dumped class to a real
-    /// path type.
+    /// the generalization of the paths, they can enumerate the arcs
+    /// of the path either in forward or in backward order.
+    /// These classes are typically not used directly, they are rather
+    /// used to be assigned to a real path type.
     ///
     /// The main purpose of this concept is that the shortest path
-    /// algorithms can enumerate easily the arcs in reverse order.
-    /// If we would like to give back a real path from these
-    /// algorithms then we should create a temporarly path object. In
-    /// LEMON such algorithms gives back a path dumper what can
-    /// assigned to a real path and the dumpers can be implemented as
+    /// algorithms can enumerate the arcs easily in reverse order.
+    /// In LEMON, such algorithms give back a (reverse) path dumper that
+    /// can be assigned to a real path. The dumpers can be implemented as
     /// an adaptor class to the predecessor map.
     ///
     /// \tparam GR The digraph type in which the path is.
-    ///
-    /// The paths can be constructed from any path type by a
-    /// template constructor or a template assignment operator.
     template <typename GR>
     class PathDumper {
@@ -220 +223 @@
       typedef typename Digraph::Arc Arc;
 
-      /// Length of the path ie. the number of arcs in the path.
+      /// Length of the path, i.e. the number of arcs on the path.
       int length() const { return 0;}
 
@@ -228 +231 @@
       /// \brief Forward or reverse dumping
       ///
-      /// If the RevPathTag is defined and true then reverse dumping
-      /// is provided in the path dumper. In this case instead of the
-      /// ArcIt the RevArcIt iterator should be implemented in the
-      /// dumper.
+      /// If this tag is defined to be \c True, then reverse dumping
+      /// is provided in the path dumper. In this case, \c RevArcIt
+      /// iterator should be implemented instead of \c ArcIt iterator.
       typedef False RevPathTag;
 
-      /// \brief LEMON style iterator for path arcs
+      /// \brief LEMON style iterator for enumerating the arcs of a path.
       ///
-      /// This class is used to iterate on the arcs of the paths.
+      /// LEMON style iterator class for enumerating the arcs of a path.
       class ArcIt {
       public:
@@ -243 +245 @@
         /// Invalid constructor
         ArcIt(Invalid) {}
-        /// Constructor for first arc
+        /// Sets the iterator to the first arc of the given path
         ArcIt(const PathDumper&) {}
 
-        /// Conversion to Arc
+        /// Conversion to \c Arc
         operator Arc() const { return INVALID; }
 
@@ -261 +263 @@
       };
 
-      /// \brief LEMON style iterator for path arcs
+      /// \brief LEMON style iterator for enumerating the arcs of a path
+      /// in reverse direction.
       ///
-      /// This class is used to iterate on the arcs of the paths in
-      /// reverse direction.
+      /// LEMON style iterator class for enumerating the arcs of a path
+      /// in reverse direction.
       class RevArcIt {
       public:
@@ -271 +274 @@
         /// Invalid constructor
         RevArcIt(Invalid) {}
-        /// Constructor for first arc
+        /// Sets the iterator to the last arc of the given path
         RevArcIt(const PathDumper &) {}
 
-        /// Conversion to Arc
+        /// Conversion to \c Arc
         operator Arc() const { return INVALID; }
 

lemon/counter.h

@@ -213 +213 @@
   /// 'Do nothing' version of Counter.
 
-  /// This class can be used in the same way as \ref Counter however it
+  /// This class can be used in the same way as \ref Counter, but it
   /// does not count at all and does not print report on destruction.
   ///

lemon/cplex.cc

@@ -112 +112 @@
   }
 
+  int CplexBase::_addRow(Value lb, ExprIterator b, 
+                         ExprIterator e, Value ub) {
+    int i = CPXgetnumrows(cplexEnv(), _prob);
+    if (lb == -INF) {
+      const char s = 'L';
+      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
+    } else if (ub == INF) {
+      const char s = 'G';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+    } else if (lb == ub){
+      const char s = 'E';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+    } else {
+      const char s = 'R';
+      double len = ub - lb;
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+    }
+
+    std::vector<int> indices;
+    std::vector<int> rowlist;
+    std::vector<Value> values;
+
+    for(ExprIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+      rowlist.push_back(i);
+    }
+
+    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+                   &rowlist.front(), &indices.front(), &values.front());
+
+    return i;
+  }
 
   void CplexBase::_eraseCol(int i) {

lemon/cplex.h

@@ -94 +94 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);

lemon/dfs.h

@@ -64 +64 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -122 +122 @@
   ///\tparam GR The type of the digraph the algorithm runs on.
   ///The default type is \ref ListDigraph.
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref DfsDefaultTraits
+  ///"DfsDefaultTraits<GR>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR,
@@ -634 +639 @@
     ///Runs the algorithm to visit all nodes in the digraph.
 
-    ///This method runs the %DFS algorithm in order to compute the
-    ///%DFS path to each node.
-    ///
-    ///The algorithm computes
-    ///- the %DFS tree (forest),
-    ///- the distance of each node from the root(s) in the %DFS tree.
+    ///This method runs the %DFS algorithm in order to visit all nodes
+    ///in the digraph.
     ///
     ///\note <tt>d.run()</tt> is just a shortcut of the following code.
@@ -783 +784 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
@@ -892 +893 @@
   /// This class should only be used through the \ref dfs() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class DfsWizard : public TR
@@ -977 +981 @@
     ///Runs DFS algorithm to visit all nodes in the digraph.
 
-    ///This method runs DFS algorithm in order to compute
-    ///the DFS path to each node.
+    ///This method runs DFS algorithm in order to visit all nodes
+    ///in the digraph.
     void run()
     {
@@ -1242 +1246 @@
   /// does not observe the DFS events. If you want to observe the DFS
   /// events, you should implement your own visitor class.
-  /// \tparam TR Traits class to set various data types used by the
-  /// algorithm. The default traits class is
-  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
-  /// See \ref DfsVisitDefaultTraits for the documentation of
-  /// a DFS visit traits class.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
+  /// "DfsVisitDefaultTraits<GR>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename VS, typename TR>
@@ -1579 +1583 @@
     /// \brief Runs the algorithm to visit all nodes in the digraph.
 
-    /// This method runs the %DFS algorithm in order to
-    /// compute the %DFS path to each node.
-    ///
-    /// The algorithm computes
-    /// - the %DFS tree (forest),
-    /// - the distance of each node from the root(s) in the %DFS tree.
+    /// This method runs the %DFS algorithm in order to visit all nodes
+    /// in the digraph.
     ///
     /// \note <tt>d.run()</tt> is just a shortcut of the following code.

lemon/dijkstra.h

@@ -133 +133 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -193 +193 @@
   ///it is necessary. The default map type is \ref
   ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  ///\tparam TR The traits class that defines various types used by the
+  ///algorithm. By default, it is \ref DijkstraDefaultTraits
+  ///"DijkstraDefaultTraits<GR, LEN>".
+  ///In most cases, this parameter should not be set directly,
+  ///consider to use the named template parameters instead.
 #ifdef DOXYGEN
   template <typename GR, typename LEN, typename TR>
@@ -207 +212 @@
 
     ///The type of the arc lengths.
-    typedef typename TR::LengthMap::Value Value;
+    typedef typename TR::Value Value;
     ///The type of the map that stores the arc lengths.
     typedef typename TR::LengthMap LengthMap;
@@ -427 +432 @@
     ///passed to the constructor of the cross reference and the cross
     ///reference should be passed to the constructor of the heap).
-    ///However external heap and cross reference objects could also be
+    ///However, external heap and cross reference objects could also be
     ///passed to the algorithm using the \ref heap() function before
     ///calling \ref run(Node) "run()" or \ref init().
@@ -448 +453 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c OperationTraits type.
-    /// For more information see \ref DijkstraDefaultOperationTraits.
+    /// For more information, see \ref DijkstraDefaultOperationTraits.
     template <class T>
     struct SetOperationTraits
@@ -997 +1002 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
@@ -1093 +1098 @@
   /// This class should only be used through the \ref dijkstra() function,
   /// which makes it easier to use the algorithm.
+  ///
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm.
   template<class TR>
   class DijkstraWizard : public TR

lemon/edge_set.h

@@ -256 +256 @@
   /// all arcs incident to the given node is erased from the arc set.
   ///
+  /// This class fully conforms to the \ref concepts::Digraph
+  /// "Digraph" concept.
+  /// It provides only linear time counting for nodes and arcs.
+  ///
   /// \param GR The type of the graph which shares its node set with
   /// this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   /// concept.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph" concept.
   template <typename GR>
   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
@@ -686 +687 @@
   /// incident to the given node is erased from the arc set.
   ///
+  /// This class fully conforms to the \ref concepts::Graph "Graph"
+  /// concept.
+  /// It provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \param GR The type of the graph which shares its node set
   /// with this class. Its interface must conform to the
   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
-  /// concept.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph "Graph"
   /// concept.
   template <typename GR>
@@ -868 +870 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -955 +957 @@
   /// arcs. Therefore the arcs cannot be erased from the arc sets.
   ///
+  /// This class fully conforms to the \ref concepts::Digraph "Digraph"
+  /// concept.
+  /// It provides only linear time counting for nodes and arcs.
+  ///
   /// \warning If a node is erased from the underlying graph and this
   /// node is the source or target of one arc in the arc set, then
   /// the arc set is invalidated, and it cannot be used anymore. The
   /// validity can be checked with the \c valid() member function.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph" concept.
   template <typename GR>
   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
@@ -1174 +1177 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -1182 +1185 @@
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc.id;
     }
@@ -1305 +1308 @@
   /// edges cannot be erased from the edge sets.
   ///
+  /// This class fully conforms to the \ref concepts::Graph "Graph"
+  /// concept.
+  /// It provides only linear time counting for nodes, edges and arcs.
+  ///
   /// \warning If a node is erased from the underlying graph and this
   /// node is incident to one edge in the edge set, then the edge set
   /// is invalidated, and it cannot be used anymore. The validity can
   /// be checked with the \c valid() member function.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph
-  /// "Graph" concept.
   template <typename GR>
   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {

lemon/full_graph.h

@@ -25 +25 @@
 ///\ingroup graphs
 ///\file
-///\brief FullGraph and FullDigraph classes.
+///\brief FullDigraph and FullGraph classes.
 
 namespace lemon {
@@ -52 +52 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Arc arc(const Node& s, const Node& t) const {
@@ -149 +149 @@
   /// \ingroup graphs
   ///
-  /// \brief A full digraph class.
-  ///
-  /// This is a simple and fast directed full graph implementation.
-  /// From each node go arcs to each node (including the source node),
-  /// therefore the number of the arcs in the digraph is the square of
-  /// the node number. This digraph type is completely static, so you
-  /// can neither add nor delete either arcs or nodes, and it needs
-  /// constant space in memory.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph concept".
-  ///
-  /// The \c FullDigraph and \c FullGraph classes are very similar,
+  /// \brief A directed full graph class.
+  ///
+  /// FullDigraph is a simple and fast implmenetation of directed full
+  /// (complete) graphs. It contains an arc from each node to each node
+  /// (including a loop for each node), therefore the number of arcs
+  /// is the square of the number of nodes.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or arcs, however
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes and arcs.
+  ///
+  /// \note FullDigraph and FullGraph classes are very similar,
   /// but there are two differences. While this class conforms only
-  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
-  /// class conforms to the \ref concepts::Graph "Graph" concept,
-  /// moreover \c FullGraph does not contain a loop arc for each
-  /// node as \c FullDigraph does.
+  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
+  /// conforms to the \ref concepts::Graph "Graph" concept,
+  /// moreover FullGraph does not contain a loop for each
+  /// node as this class does.
   ///
   /// \sa FullGraph
@@ -174 +178 @@
   public:
 
-    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and arcs will be zero.
     FullDigraph() { construct(0); }
 
@@ -185 +191 @@
     /// \brief Resizes the digraph
     ///
-    /// Resizes the digraph. The function will fully destroy and
-    /// rebuild the digraph. This cause that the maps of the digraph will
+    /// This function resizes the digraph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the digraph will be
     /// reallocated automatically and the previous values will be lost.
     void resize(int n) {
@@ -198 +204 @@
     /// \brief Returns the node with the given index.
     ///
-    /// Returns the node with the given index. Since it is a static
-    /// digraph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
+    /// Returns the node with the given index. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -206 +213 @@
     /// \brief Returns the index of the given node.
     ///
-    /// Returns the index of the given node. Since it is a static
-    /// digraph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
-    /// \sa operator()
-    int index(const Node& node) const { return Parent::index(node); }
+    /// Returns the index of the given node. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
+    /// \sa operator()()
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.
     ///
     /// Returns the arc connecting the given nodes.
-    Arc arc(const Node& u, const Node& v) const {
+    Arc arc(Node u, Node v) const {
       return Parent::arc(u, v);
     }
@@ -284 +292 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Edge edge(const Node& u, const Node& v) const {
@@ -521 +529 @@
   /// \brief An undirected full graph class.
   ///
-  /// This is a simple and fast undirected full graph
-  /// implementation. From each node go edge to each other node,
-  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
-  /// This graph type is completely static, so you can neither
-  /// add nor delete either edges or nodes, and it needs constant
-  /// space in memory.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
-  ///
-  /// The \c FullGraph and \c FullDigraph classes are very similar,
-  /// but there are two differences. While the \c FullDigraph class
+  /// FullGraph is a simple and fast implmenetation of undirected full
+  /// (complete) graphs. It contains an edge between every distinct pair
+  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
+  ///
+  /// \note FullDigraph and FullGraph classes are very similar,
+  /// but there are two differences. While FullDigraph
   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   /// this class conforms to the \ref concepts::Graph "Graph" concept,
-  /// moreover \c FullGraph does not contain a loop arc for each
-  /// node as \c FullDigraph does.
+  /// moreover this class does not contain a loop for each
+  /// node as FullDigraph does.
   ///
   /// \sa FullDigraph
@@ -543 +555 @@
   public:
 
-    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and edges will be zero.
     FullGraph() { construct(0); }
 
@@ -554 +568 @@
     /// \brief Resizes the graph
     ///
-    /// Resizes the graph. The function will fully destroy and
-    /// rebuild the graph. This cause that the maps of the graph will
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
     /// reallocated automatically and the previous values will be lost.
     void resize(int n) {
@@ -569 +583 @@
     /// \brief Returns the node with the given index.
     ///
-    /// Returns the node with the given index. Since it is a static
-    /// graph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
+    /// Returns the node with the given index. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -577 +592 @@
     /// \brief Returns the index of the given node.
     ///
-    /// Returns the index of the given node. Since it is a static
-    /// graph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
-    /// \sa operator()
-    int index(const Node& node) const { return Parent::index(node); }
+    /// Returns the index of the given node. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// The index of a node is the same as its ID.
+    /// \sa operator()()
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.
     ///
     /// Returns the arc connecting the given nodes.
-    Arc arc(const Node& s, const Node& t) const {
+    Arc arc(Node s, Node t) const {
       return Parent::arc(s, t);
     }
 
-    /// \brief Returns the edge connects the given nodes.
-    ///
-    /// Returns the edge connects the given nodes.
-    Edge edge(const Node& u, const Node& v) const {
+    /// \brief Returns the edge connecting the given nodes.
+    ///
+    /// Returns the edge connecting the given nodes.
+    Edge edge(Node u, Node v) const {
       return Parent::edge(u, v);
     }

lemon/glpk.cc

@@ -57 +57 @@
     int i = glp_add_rows(lp, 1);
     glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
+    return i;
+  }
+
+  int GlpkBase::_addRow(Value lo, ExprIterator b, 
+                        ExprIterator e, Value up) {
+    int i = glp_add_rows(lp, 1);
+
+    if (lo == -INF) {
+      if (up == INF) {
+        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
+      } else {
+        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+      }    
+    } else {
+      if (up == INF) {
+        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
+      } else if (lo != up) {        
+        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
+      } else {
+        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+      }
+    }
+
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    indexes.push_back(0);
+    values.push_back(0);
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    glp_set_mat_row(lp, i, values.size() - 1,
+                    &indexes.front(), &values.front());
     return i;
   }

lemon/glpk.h

@@ -26 +26 @@
 #include <lemon/lp_base.h>
 
-// forward declaration
-#if !defined _GLP_PROB && !defined GLP_PROB
-#define _GLP_PROB
-#define GLP_PROB
-typedef struct { double _opaque_prob; } glp_prob;
-/* LP/MIP problem object */
-#endif
-
 namespace lemon {
 
+  namespace _solver_bits {
+    class VoidPtr {
+    private:
+      void *_ptr;      
+    public:
+      VoidPtr() : _ptr(0) {}
+
+      template <typename T>
+      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
+
+      template <typename T>
+      VoidPtr& operator=(T* ptr) { 
+        _ptr = reinterpret_cast<void*>(ptr); 
+        return *this;
+      }
+
+      template <typename T>
+      operator T*() const { return reinterpret_cast<T*>(_ptr); }
+    };
+  }
 
   /// \brief Base interface for the GLPK LP and MIP solver
@@ -44 +56 @@
   protected:
 
-    typedef glp_prob LPX;
-    glp_prob* lp;
+    _solver_bits::VoidPtr lp;
 
     GlpkBase();
@@ -55 +66 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
@@ -123 +135 @@
 
     ///Pointer to the underlying GLPK data structure.
-    LPX *lpx() {return lp;}
+    _solver_bits::VoidPtr lpx() {return lp;}
     ///Const pointer to the underlying GLPK data structure.
-    const LPX *lpx() const {return lp;}
+    _solver_bits::VoidPtr lpx() const {return lp;}
 
     ///Returns the constraint identifier understood by GLPK.

lemon/gomory_hu.h

@@ -295 +295 @@
     /// \pre \ref run() must be called before using this function.
     template <typename CutMap>
-    Value minCutMap(const Node& s, ///< 
+    Value minCutMap(const Node& s,
                     const Node& t,
-                    ///< 
                     CutMap& cutMap
-                    ///< 
                     ) const {
       Node sn = s, tn = t;
@@ -395 +393 @@
                    /// \endcode
                    /// does not necessarily give the same set of nodes.
-                   /// However it is ensured that
+                   /// However, it is ensured that
                    /// \code
                    /// MinCutNodeIt(gomory, s, t, true);

lemon/graph_to_eps.h

@@ -143 +143 @@
   ///\param gr  Reference to the graph to be printed.
   ///\param ost Reference to the output stream.
-  ///By default it is <tt>std::cout</tt>.
+  ///By default, it is <tt>std::cout</tt>.
   ///\param pros If it is \c true, then the \c ostream referenced by \c os
   ///will be explicitly deallocated by the destructor.
@@ -513 +513 @@
   ///Turn on/off pre-scaling
 
-  ///By default graphToEps() rescales the whole image in order to avoid
+  ///By default, graphToEps() rescales the whole image in order to avoid
   ///very big or very small bounding boxes.
   ///
@@ -685 +685 @@
 #else
       os << bits::getWinFormattedDate();
+      os << std::endl;
 #endif
     }
-    os << std::endl;
 
     if (_autoArcWidthScale) {
@@ -1115 +1115 @@
 ///\param g Reference to the graph to be printed.
 ///\param os Reference to the output stream.
-///By default it is <tt>std::cout</tt>.
+///By default, it is <tt>std::cout</tt>.
 ///
 ///This function also has a lot of
@@ -1127 +1127 @@
 ///\endcode
 ///
-///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
+///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
 ///
 ///\warning Don't forget to put the \ref GraphToEps::run() "run()"

lemon/grid_graph.h

@@ -471 +471 @@
   /// \brief Grid graph class
   ///
-  /// This class implements a special graph type. The nodes of the
-  /// graph can be indexed by two integer \c (i,j) value where \c i is
-  /// in the \c [0..width()-1] range and j is in the \c
-  /// [0..height()-1] range.  Two nodes are connected in the graph if
-  /// the indexes differ exactly on one position and exactly one is
-  /// the difference. The nodes of the graph can be indexed by position
-  /// with the \c operator()() function. The positions of the nodes can be
-  /// get with \c pos(), \c col() and \c row() members. The outgoing
+  /// GridGraph implements a special graph type. The nodes of the
+  /// graph can be indexed by two integer values \c (i,j) where \c i is
+  /// in the range <tt>[0..width()-1]</tt> and j is in the range
+  /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
+  /// the indices differ exactly on one position and the difference is
+  /// also exactly one. The nodes of the graph can be obtained by position
+  /// using the \c operator()() function and the indices of the nodes can
+  /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
   /// arcs can be retrieved with the \c right(), \c up(), \c left()
   /// and \c down() functions, where the bottom-left corner is the
   /// origin.
+  ///
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however
+  /// the structure can be resized using resize().
   ///
   /// \image html grid_graph.png
@@ -497 +501 @@
   ///\endcode
   ///
-  /// This graph type fully conforms to the \ref concepts::Graph
-  /// "Graph concept".
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
   class GridGraph : public ExtendedGridGraphBase {
     typedef ExtendedGridGraphBase Parent;
@@ -504 +511 @@
   public:
 
-    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
-    ///
-    /// Map to get the indices of the nodes as dim2::Point<int>.
+    /// \brief Map to get the indices of the nodes as \ref dim2::Point
+    /// "dim2::Point<int>".
+    ///
+    /// Map to get the indices of the nodes as \ref dim2::Point
+    /// "dim2::Point<int>".
     class IndexMap {
     public:
@@ -515 +524 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       IndexMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.pos(key);
@@ -541 +546 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       ColMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.col(key);
@@ -567 +568 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       RowMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.row(key);
@@ -584 +581 @@
     /// \brief Constructor
     ///
-    /// Construct a grid graph with given size.
+    /// Construct a grid graph with the given size.
     GridGraph(int width, int height) { construct(width, height); }
 
-    /// \brief Resize the graph
-    ///
-    /// Resize the graph. The function will fully destroy and rebuild
-    /// the graph.  This cause that the maps of the graph will
-    /// reallocated automatically and the previous values will be
-    /// lost.
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
     void resize(int width, int height) {
       Parent::notifier(Arc()).clear();
@@ -610 +606 @@
     }
 
-    /// \brief Gives back the column index of the node.
+    /// \brief The column index of the node.
     ///
     /// Gives back the column index of the node.
@@ -617 +613 @@
     }
 
-    /// \brief Gives back the row index of the node.
+    /// \brief The row index of the node.
     ///
     /// Gives back the row index of the node.
@@ -624 +620 @@
     }
 
-    /// \brief Gives back the position of the node.
+    /// \brief The position of the node.
     ///
     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
@@ -631 +627 @@
     }
 
-    /// \brief Gives back the number of the columns.
+    /// \brief The number of the columns.
     ///
     /// Gives back the number of the columns.
@@ -638 +634 @@
     }
 
-    /// \brief Gives back the number of the rows.
+    /// \brief The number of the rows.
     ///
     /// Gives back the number of the rows.
@@ -645 +641 @@
     }
 
-    /// \brief Gives back the arc goes right from the node.
+    /// \brief The arc goes right from the node.
     ///
     /// Gives back the arc goes right from the node. If there is not
@@ -653 +649 @@
     }
 
-    /// \brief Gives back the arc goes left from the node.
+    /// \brief The arc goes left from the node.
     ///
     /// Gives back the arc goes left from the node. If there is not
@@ -661 +657 @@
     }
 
-    /// \brief Gives back the arc goes up from the node.
+    /// \brief The arc goes up from the node.
     ///
     /// Gives back the arc goes up from the node. If there is not
@@ -669 +665 @@
     }
 
-    /// \brief Gives back the arc goes down from the node.
+    /// \brief The arc goes down from the node.
     ///
     /// Gives back the arc goes down from the node. If there is not

lemon/hypercube_graph.h

@@ -263 +263 @@
     }
 
-    int index(Node node) const {
+    static int index(Node node) {
       return node._id;
     }
@@ -283 +283 @@
   /// \brief Hypercube graph class
   ///
-  /// This class implements a special graph type. The nodes of the graph
-  /// are indiced with integers with at most \c dim binary digits.
+  /// HypercubeGraph implements a special graph type. The nodes of the
+  /// graph are indexed with integers having at most \c dim binary digits.
   /// Two nodes are connected in the graph if and only if their indices
   /// differ only on one position in the binary form.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however,
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// This class provides constant time counting for nodes, edges and arcs.
   ///
   /// \note The type of the indices is chosen to \c int for efficiency
   /// reasons. Thus the maximum dimension of this implementation is 26
   /// (assuming that the size of \c int is 32 bit).
-  ///
-  /// This graph type fully conforms to the \ref concepts::Graph
-  /// "Graph concept".
   class HypercubeGraph : public ExtendedHypercubeGraphBase {
     typedef ExtendedHypercubeGraphBase Parent;
@@ -303 +309 @@
     /// Constructs a hypercube graph with \c dim dimensions.
     HypercubeGraph(int dim) { construct(dim); }
+
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
+    void resize(int dim) {
+      Parent::notifier(Arc()).clear();
+      Parent::notifier(Edge()).clear();
+      Parent::notifier(Node()).clear();
+      construct(dim);
+      Parent::notifier(Node()).build();
+      Parent::notifier(Edge()).build();
+      Parent::notifier(Arc()).build();
+    }
 
     /// \brief The number of dimensions.
@@ -321 +342 @@
     ///
     /// Gives back the dimension id of the given edge.
-    /// It is in the [0..dim-1] range.
+    /// It is in the range <tt>[0..dim-1]</tt>.
     int dimension(Edge edge) const {
       return Parent::dimension(edge);
@@ -329 +350 @@
     ///
     /// Gives back the dimension id of the given arc.
-    /// It is in the [0..dim-1] range.
+    /// It is in the range <tt>[0..dim-1]</tt>.
     int dimension(Arc arc) const {
       return Parent::dimension(arc);
@@ -338 +359 @@
     /// Gives back the index of the given node.
     /// The lower bits of the integer describes the node.
-    int index(Node node) const {
+    static int index(Node node) {
       return Parent::index(node);
     }

lemon/lgf_reader.h

@@ -428 +428 @@
   ///\endcode
   ///
-  /// By default the reader uses the first section in the file of the
+  /// By default, the reader uses the first section in the file of the
   /// proper type. If a section has an optional name, then it can be
   /// selected for reading by giving an optional name parameter to the
@@ -2222 +2222 @@
     /// whitespaces are trimmed from each processed string.
     ///
-    /// For example let's see a section, which contain several
+    /// For example, let's see a section, which contain several
     /// integers, which should be inserted into a vector.
     ///\code

lemon/list_graph.h

@@ -22 +22 @@
 ///\ingroup graphs
 ///\file
-///\brief ListDigraph, ListGraph classes.
+///\brief ListDigraph and ListGraph classes.
 
 #include <lemon/core.h>
@@ -32 +32 @@
 
 namespace lemon {
+
+  class ListDigraph;
 
   class ListDigraphBase {
@@ -63 +65 @@
     class Node {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -78 +81 @@
     class Arc {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -117 +121 @@
       int n;
       for(n = first_node;
-          n!=-1 && nodes[n].first_in == -1;
+          n != -1 && nodes[n].first_out == -1;
           n = nodes[n].next) {}
-      arc.id = (n == -1) ? -1 : nodes[n].first_in;
+      arc.id = (n == -1) ? -1 : nodes[n].first_out;
     }
 
     void next(Arc& arc) const {
-      if (arcs[arc.id].next_in != -1) {
-        arc.id = arcs[arc.id].next_in;
+      if (arcs[arc.id].next_out != -1) {
+        arc.id = arcs[arc.id].next_out;
       } else {
         int n;
-        for(n = nodes[arcs[arc.id].target].next;
-            n!=-1 && nodes[n].first_in == -1;
+        for(n = nodes[arcs[arc.id].source].next;
+            n != -1 && nodes[n].first_out == -1;
             n = nodes[n].next) {}
-        arc.id = (n == -1) ? -1 : nodes[n].first_in;
+        arc.id = (n == -1) ? -1 : nodes[n].first_out;
       }
     }
@@ -312 +316 @@
   ///A general directed graph structure.
 
-  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
-  ///implementation based on static linked lists that are stored in
+  ///\ref ListDigraph is a versatile and fast directed graph
+  ///implementation based on linked lists that are stored in
   ///\c std::vector structures.
   ///
-  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
-  ///also provides several useful additional functionalities.
-  ///Most of the member functions and nested classes are documented
+  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
+  ///and it also provides several useful additional functionalities.
+  ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes and arcs.
+  ///
   ///\sa concepts::Digraph
-
+  ///\sa ListGraph
   class ListDigraph : public ExtendedListDigraphBase {
     typedef ExtendedListDigraphBase Parent;
 
   private:
-    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
-
-    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
-    ///
+    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
-    ///\brief Assignment of ListDigraph to another one is \e not allowed.
-    ///Use copyDigraph() instead.
-
-    ///Assignment of ListDigraph to another one is \e not allowed.
-    ///Use copyDigraph() instead.
+    /// \brief Assignment of a digraph to another one is \e not allowed.
+    /// Use DigraphCopy instead.
     void operator=(const ListDigraph &) {}
   public:
@@ -348 +348 @@
     ///Add a new node to the digraph.
 
-    ///Add a new node to the digraph.
+    ///This function adds a new node to the digraph.
     ///\return The new node.
     Node addNode() { return Parent::addNode(); }
@@ -354 +354 @@
     ///Add a new arc to the digraph.
 
-    ///Add a new arc to the digraph with source node \c s
+    ///This function adds a new arc to the digraph with source node \c s
     ///and target node \c t.
     ///\return The new arc.
-    Arc addArc(const Node& s, const Node& t) {
+    Arc addArc(Node s, Node t) {
       return Parent::addArc(s, t);
     }
@@ -363 +363 @@
     ///\brief Erase a node from the digraph.
     ///
-    ///Erase a node from the digraph.
-    ///
-    void erase(const Node& n) { Parent::erase(n); }
+    ///This function erases the given node along with its outgoing and
+    ///incoming arcs from the digraph.
+    ///
+    ///\note All iterators referencing the removed node or the connected
+    ///arcs are invalidated, of course.
+    void erase(Node n) { Parent::erase(n); }
 
     ///\brief Erase an arc from the digraph.
     ///
-    ///Erase an arc from the digraph.
-    ///
-    void erase(const Arc& a) { Parent::erase(a); }
+    ///This function erases the given arc from the digraph.
+    ///
+    ///\note All iterators referencing the removed arc are invalidated,
+    ///of course.
+    void erase(Arc a) { Parent::erase(a); }
 
     /// Node validity check
 
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
-    ///
-    /// \warning A Node pointing to a removed item
-    /// could become valid again later if new nodes are
-    /// added to the graph.
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the digraph.
+    ///
+    /// \warning A removed node could become valid again if new nodes are
+    /// added to the digraph.
     bool valid(Node n) const { return Parent::valid(n); }
 
     /// Arc validity check
 
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning An Arc pointing to a removed item
-    /// could become valid again later if new nodes are
-    /// added to the graph.
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the digraph.
+    ///
+    /// \warning A removed arc could become valid again if new arcs are
+    /// added to the digraph.
     bool valid(Arc a) const { return Parent::valid(a); }
 
-    /// Change the target of \c a to \c n
-
-    /// Change the target of \c a to \c n
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
-    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
-    ///invalidated.
+    /// Change the target node of an arc
+
+    /// This function changes the target node of the given arc \c a to \c n.
+    ///
+    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
+    ///arc remain valid, but \c InArcIt iterators are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
@@ -406 +408 @@
       Parent::changeTarget(a,n);
     }
-    /// Change the source of \c a to \c n
-
-    /// Change the source of \c a to \c n
-    ///
-    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
-    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
-    ///invalidated.
+    /// Change the source node of an arc
+
+    /// This function changes the source node of the given arc \c a to \c n.
+    ///
+    ///\note \c InArcIt iterators referencing the changed arc remain
+    ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
@@ -420 +421 @@
     }
 
-    /// Invert the direction of an arc.
-
-    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
-    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
-    ///invalidated.
+    /// Reverse the direction of an arc.
+
+    /// This function reverses the direction of the given arc.
+    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
+    ///the changed arc are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void reverseArc(Arc e) {
-      Node t=target(e);
-      changeTarget(e,source(e));
-      changeSource(e,t);
-    }
-
-    /// Reserve memory for nodes.
-
-    /// Using this function it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveArc
-    void reserveNode(int n) { nodes.reserve(n); };
-
-    /// Reserve memory for arcs.
-
-    /// Using this function it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveNode
-    void reserveArc(int m) { arcs.reserve(m); };
+    void reverseArc(Arc a) {
+      Node t=target(a);
+      changeTarget(a,source(a));
+      changeSource(a,t);
+    }
 
     ///Contract two nodes.
 
-    ///This function contracts two nodes.
-    ///Node \p b will be removed but instead of deleting
-    ///incident arcs, they will be joined to \p a.
-    ///The last parameter \p r controls whether to remove loops. \c true
-    ///means that loops will be removed.
-    ///
-    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
-    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
-    ///may be invalidated.
+    ///This function contracts the given two nodes.
+    ///Node \c v is removed, but instead of deleting its
+    ///incident arcs, they are joined to node \c u.
+    ///If the last parameter \c r is \c true (this is the default value),
+    ///then the newly created loops are removed.
+    ///
+    ///\note The moved arcs are joined to node \c u using changeSource()
+    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
+    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
+    ///iterators are invalidated for the incomming arcs of \c v.
+    ///Moreover all iterators referencing node \c v or the removed 
+    ///loops are also invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void contract(Node a, Node b, bool r = true)
+    void contract(Node u, Node v, bool r = true)
     {
-      for(OutArcIt e(*this,b);e!=INVALID;) {
+      for(OutArcIt e(*this,v);e!=INVALID;) {
         OutArcIt f=e;
         ++f;
-        if(r && target(e)==a) erase(e);
-        else changeSource(e,a);
+        if(r && target(e)==u) erase(e);
+        else changeSource(e,u);
         e=f;
       }
-      for(InArcIt e(*this,b);e!=INVALID;) {
+      for(InArcIt e(*this,v);e!=INVALID;) {
         InArcIt f=e;
         ++f;
-        if(r && source(e)==a) erase(e);
-        else changeTarget(e,a);
+        if(r && source(e)==u) erase(e);
+        else changeTarget(e,u);
         e=f;
       }
-      erase(b);
+      erase(v);
     }
 
     ///Split a node.
 
-    ///This function splits a node. First a new node is added to the digraph,
-    ///then the source of each outgoing arc of \c n is moved to this new node.
-    ///If \c connect is \c true (this is the default value), then a new arc
-    ///from \c n to the newly created node is also added.
+    ///This function splits the given node. First, a new node is added
+    ///to the digraph, then the source of each outgoing arc of node \c n
+    ///is moved to this new node.
+    ///If the second parameter \c connect is \c true (this is the default
+    ///value), then a new arc from node \c n to the newly created node
+    ///is also added.
     ///\return The newly created node.
     ///
-    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
-    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
-    ///be invalidated.
-    ///
-    ///\warning This functionality cannot be used in conjunction with the
+    ///\note All iterators remain valid.
+    ///
+    ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
     Node split(Node n, bool connect = true) {
       Node b = addNode();
-      for(OutArcIt e(*this,n);e!=INVALID;) {
-        OutArcIt f=e;
-        ++f;
-        changeSource(e,b);
-        e=f;
+      nodes[b.id].first_out=nodes[n.id].first_out;
+      nodes[n.id].first_out=-1;
+      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
+        arcs[i].source=b.id;
       }
       if (connect) addArc(n,b);
@@ -515 +498 @@
     ///Split an arc.
 
-    ///This function splits an arc. First a new node \c b is added to
-    ///the digraph, then the original arc is re-targeted to \c
-    ///b. Finally an arc from \c b to the original target is added.
-    ///
+    ///This function splits the given arc. First, a new node \c v is
+    ///added to the digraph, then the target node of the original arc
+    ///is set to \c v. Finally, an arc from \c v to the original target
+    ///is added.
     ///\return The newly created node.
+    ///
+    ///\note \c InArcIt iterators referencing the original arc are
+    ///invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    Node split(Arc e) {
-      Node b = addNode();
-      addArc(b,target(e));
-      changeTarget(e,b);
-      return b;
-    }
+    Node split(Arc a) {
+      Node v = addNode();
+      addArc(v,target(a));
+      changeTarget(a,v);
+      return v;
+    }
+
+    ///Clear the digraph.
+
+    ///This function erases all nodes and arcs from the digraph.
+    ///
+    ///\note All iterators of the digraph are invalidated, of course.
+    void clear() {
+      Parent::clear();
+    }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveArc()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for arcs.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveNode()
+    void reserveArc(int m) { arcs.reserve(m); };
 
     /// \brief Class to make a snapshot of the digraph and restore
@@ -538 +553 @@
     /// restore() function.
     ///
-    /// \warning Arc and node deletions and other modifications (e.g.
-    /// contracting, splitting, reversing arcs or nodes) cannot be
+    /// \note After a state is restored, you cannot restore a later state, 
+    /// i.e. you cannot add the removed nodes and arcs again using
+    /// another Snapshot instance.
+    ///
+    /// \warning Node and arc deletions and other modifications (e.g.
+    /// reversing, contracting, splitting arcs or nodes) cannot be
     /// restored. These events invalidate the snapshot.
+    /// However, the arcs and nodes that were added to the digraph after
+    /// making the current snapshot can be removed without invalidating it.
     class Snapshot {
     protected:
@@ -710 +731 @@
       ///
       /// Default constructor.
-      /// To actually make a snapshot you must call save().
+      /// You have to call save() to actually make a snapshot.
       Snapshot()
         : digraph(0), node_observer_proxy(*this),
@@ -717 +738 @@
       /// \brief Constructor that immediately makes a snapshot.
       ///
-      /// This constructor immediately makes a snapshot of the digraph.
-      /// \param _digraph The digraph we make a snapshot of.
-      Snapshot(ListDigraph &_digraph)
+      /// This constructor immediately makes a snapshot of the given digraph.
+      Snapshot(ListDigraph &gr)
         : node_observer_proxy(*this),
           arc_observer_proxy(*this) {
-        attach(_digraph);
+        attach(gr);
       }
 
       /// \brief Make a snapshot.
       ///
-      /// Make a snapshot of the digraph.
-      ///
-      /// This function can be called more than once. In case of a repeated
+      /// This function makes a snapshot of the given digraph.
+      /// It can be called more than once. In case of a repeated
       /// call, the previous snapshot gets lost.
-      /// \param _digraph The digraph we make the snapshot of.
-      void save(ListDigraph &_digraph) {
+      void save(ListDigraph &gr) {
         if (attached()) {
           detach();
           clear();
         }
-        attach(_digraph);
+        attach(gr);
       }
 
       /// \brief Undo the changes until the last snapshot.
-      //
-      /// Undo the changes until the last snapshot created by save().
+      ///
+      /// This function undos the changes until the last snapshot
+      /// created by save() or Snapshot(ListDigraph&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
@@ -756 +778 @@
       }
 
-      /// \brief Gives back true when the snapshot is valid.
+      /// \brief Returns \c true if the snapshot is valid.
       ///
-      /// Gives back true when the snapshot is valid.
+      /// This function returns \c true if the snapshot is valid.
       bool valid() const {
         return attached();
@@ -795 +817 @@
 
     typedef ListGraphBase Graph;
-
-    class Node;
-    class Arc;
-    class Edge;
 
     class Node {
@@ -848 +866 @@
       bool operator<(const Arc& arc) const {return id < arc.id;}
     };
-
-
 
     ListGraphBase()
@@ -1165 +1181 @@
   ///A general undirected graph structure.
 
-  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
-  ///implementation based on static linked lists that are stored in
+  ///\ref ListGraph is a versatile and fast undirected graph
+  ///implementation based on linked lists that are stored in
   ///\c std::vector structures.
   ///
-  ///It conforms to the \ref concepts::Graph "Graph concept" and it
-  ///also provides several useful additional functionalities.
-  ///Most of the member functions and nested classes are documented
+  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
+  ///and it also provides several useful additional functionalities.
+  ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
+  ///This class provides only linear time counting for nodes, edges and arcs.
+  ///
   ///\sa concepts::Graph
-
+  ///\sa ListDigraph
   class ListGraph : public ExtendedListGraphBase {
     typedef ExtendedListGraphBase Parent;
 
   private:
-    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
-
-    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
-    ///
+    /// Graphs are \e not copy constructible. Use GraphCopy instead.
     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
-    ///\brief Assignment of ListGraph to another one is \e not allowed.
-    ///Use copyGraph() instead.
-
-    ///Assignment of ListGraph to another one is \e not allowed.
-    ///Use copyGraph() instead.
+    /// \brief Assignment of a graph to another one is \e not allowed.
+    /// Use GraphCopy instead.
     void operator=(const ListGraph &) {}
   public:
@@ -1202 +1214 @@
     /// \brief Add a new node to the graph.
     ///
-    /// Add a new node to the graph.
+    /// This function adds a new node to the graph.
     /// \return The new node.
     Node addNode() { return Parent::addNode(); }
@@ -1208 +1220 @@
     /// \brief Add a new edge to the graph.
     ///
-    /// Add a new edge to the graph with source node \c s
-    /// and target node \c t.
+    /// This function adds a new edge to the graph between nodes
+    /// \c u and \c v with inherent orientation from node \c u to
+    /// node \c v.
     /// \return The new edge.
-    Edge addEdge(const Node& s, const Node& t) {
-      return Parent::addEdge(s, t);
-    }
-
-    /// \brief Erase a node from the graph.
-    ///
-    /// Erase a node from the graph.
-    ///
-    void erase(const Node& n) { Parent::erase(n); }
-
-    /// \brief Erase an edge from the graph.
-    ///
-    /// Erase an edge from the graph.
-    ///
-    void erase(const Edge& e) { Parent::erase(e); }
+    Edge addEdge(Node u, Node v) {
+      return Parent::addEdge(u, v);
+    }
+
+    ///\brief Erase a node from the graph.
+    ///
+    /// This function erases the given node along with its incident arcs
+    /// from the graph.
+    ///
+    /// \note All iterators referencing the removed node or the incident
+    /// edges are invalidated, of course.
+    void erase(Node n) { Parent::erase(n); }
+
+    ///\brief Erase an edge from the graph.
+    ///
+    /// This function erases the given edge from the graph.
+    ///
+    /// \note All iterators referencing the removed edge are invalidated,
+    /// of course.
+    void erase(Edge e) { Parent::erase(e); }
     /// Node validity check
 
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
-    ///
-    /// \warning A Node pointing to a removed item
-    /// could become valid again later if new nodes are
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the graph.
+    ///
+    /// \warning A removed node could become valid again if new nodes are
     /// added to the graph.
     bool valid(Node n) const { return Parent::valid(n); }
+    /// Edge validity check
+
+    /// This function gives back \c true if the given edge is valid,
+    /// i.e. it is a real edge of the graph.
+    ///
+    /// \warning A removed edge could become valid again if new edges are
+    /// added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
     /// Arc validity check
 
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning An Arc pointing to a removed item
-    /// could become valid again later if new edges are
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the graph.
+    ///
+    /// \warning A removed arc could become valid again if new edges are
     /// added to the graph.
     bool valid(Arc a) const { return Parent::valid(a); }
-    /// Edge validity check
-
-    /// This function gives back true if the given edge is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning A Edge pointing to a removed item
-    /// could become valid again later if new edges are
-    /// added to the graph.
-    bool valid(Edge e) const { return Parent::valid(e); }
-    /// \brief Change the end \c u of \c e to \c n
-    ///
-    /// This function changes the end \c u of \c e to node \c n.
-    ///
-    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
-    ///changed edge are invalidated and if the changed node is the
-    ///base node of an iterator then this iterator is also
-    ///invalidated.
+
+    /// \brief Change the first node of an edge.
+    ///
+    /// This function changes the first node of the given edge \c e to \c n.
+    ///
+    ///\note \c EdgeIt and \c ArcIt iterators referencing the
+    ///changed edge are invalidated and all other iterators whose
+    ///base node is the changed node are also invalidated.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1267 +1282 @@
       Parent::changeU(e,n);
     }
-    /// \brief Change the end \c v of \c e to \c n
-    ///
-    /// This function changes the end \c v of \c e to \c n.
-    ///
-    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
-    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
-    ///base node of an iterator then this iterator is invalidated.
+    /// \brief Change the second node of an edge.
+    ///
+    /// This function changes the second node of the given edge \c e to \c n.
+    ///
+    ///\note \c EdgeIt iterators referencing the changed edge remain
+    ///valid, but \c ArcIt iterators referencing the changed edge and
+    ///all other iterators whose base node is the changed node are also
+    ///invalidated.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1280 +1296 @@
       Parent::changeV(e,n);
     }
+
     /// \brief Contract two nodes.
     ///
-    /// This function contracts two nodes.
-    /// Node \p b will be removed but instead of deleting
-    /// its neighboring arcs, they will be joined to \p a.
-    /// The last parameter \p r controls whether to remove loops. \c true
-    /// means that loops will be removed.
-    ///
-    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
-    /// valid.
+    /// This function contracts the given two nodes.
+    /// Node \c b is removed, but instead of deleting
+    /// its incident edges, they are joined to node \c a.
+    /// If the last parameter \c r is \c true (this is the default value),
+    /// then the newly created loops are removed.
+    ///
+    /// \note The moved edges are joined to node \c a using changeU()
+    /// or changeV(), thus all edge and arc iterators whose base node is
+    /// \c b are invalidated.
+    /// Moreover all iterators referencing node \c b or the removed 
+    /// loops are also invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1308 +1328 @@
     }
 
+    ///Clear the graph.
+
+    ///This function erases all nodes and arcs from the graph.
+    ///
+    ///\note All iterators of the graph are invalidated, of course.
+    void clear() {
+      Parent::clear();
+    }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for edges.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
 
     /// \brief Class to make a snapshot of the graph and restore
@@ -1317 +1365 @@
     /// using the restore() function.
     ///
-    /// \warning Edge and node deletions and other modifications
-    /// (e.g. changing nodes of edges, contracting nodes) cannot be
-    /// restored. These events invalidate the snapshot.
+    /// \note After a state is restored, you cannot restore a later state, 
+    /// i.e. you cannot add the removed nodes and edges again using
+    /// another Snapshot instance.
+    ///
+    /// \warning Node and edge deletions and other modifications
+    /// (e.g. changing the end-nodes of edges or contracting nodes)
+    /// cannot be restored. These events invalidate the snapshot.
+    /// However, the edges and nodes that were added to the graph after
+    /// making the current snapshot can be removed without invalidating it.
     class Snapshot {
     protected:
@@ -1489 +1543 @@
       ///
       /// Default constructor.
-      /// To actually make a snapshot you must call save().
+      /// You have to call save() to actually make a snapshot.
       Snapshot()
         : graph(0), node_observer_proxy(*this),
@@ -1496 +1550 @@
       /// \brief Constructor that immediately makes a snapshot.
       ///
-      /// This constructor immediately makes a snapshot of the graph.
-      /// \param _graph The graph we make a snapshot of.
-      Snapshot(ListGraph &_graph)
+      /// This constructor immediately makes a snapshot of the given graph.
+      Snapshot(ListGraph &gr)
         : node_observer_proxy(*this),
           edge_observer_proxy(*this) {
-        attach(_graph);
+        attach(gr);
       }
 
       /// \brief Make a snapshot.
       ///
-      /// Make a snapshot of the graph.
-      ///
-      /// This function can be called more than once. In case of a repeated
+      /// This function makes a snapshot of the given graph.
+      /// It can be called more than once. In case of a repeated
       /// call, the previous snapshot gets lost.
-      /// \param _graph The graph we make the snapshot of.
-      void save(ListGraph &_graph) {
+      void save(ListGraph &gr) {
         if (attached()) {
           detach();
           clear();
         }
-        attach(_graph);
+        attach(gr);
       }
 
       /// \brief Undo the changes until the last snapshot.
-      //
-      /// Undo the changes until the last snapshot created by save().
+      ///
+      /// This function undos the changes until the last snapshot
+      /// created by save() or Snapshot(ListGraph&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
@@ -1535 +1590 @@
       }
 
-      /// \brief Gives back true when the snapshot is valid.
+      /// \brief Returns \c true if the snapshot is valid.
       ///
-      /// Gives back true when the snapshot is valid.
+      /// This function returns \c true if the snapshot is valid.
       bool valid() const {
         return attached();

lemon/lp_base.h

@@ -147 +147 @@
     ///Iterator for iterate over the columns of an LP problem
 
-    /// Its usage is quite simple, for example you can count the number
+    /// Its usage is quite simple, for example, you can count the number
     /// of columns in an LP \c lp:
     ///\code
@@ -242 +242 @@
     ///Iterator for iterate over the rows of an LP problem
 
-    /// Its usage is quite simple, for example you can count the number
+    /// Its usage is quite simple, for example, you can count the number
     /// of rows in an LP \c lp:
     ///\code
@@ -944 +944 @@
     virtual int _addRow() = 0;
 
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+      int row = _addRow();
+      _setRowCoeffs(row, b, e);
+      _setRowLowerBound(row, l);
+      _setRowUpperBound(row, u);
+      return row;
+    }
+
     virtual void _eraseCol(int col) = 0;
     virtual void _eraseRow(int row) = 0;
@@ -1208 +1216 @@
     ///\return The created row.
     Row addRow(Value l,const Expr &e, Value u) {
-      Row r=addRow();
-      row(r,l,e,u);
+      Row r;
+      e.simplify();
+      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
+                                ExprIterator(e.comps.end(), cols), u - *e));
       return r;
     }
@@ -1218 +1228 @@
     ///\return The created row.
     Row addRow(const Constr &c) {
-      Row r=addRow();
-      row(r,c);
+      Row r;
+      c.expr().simplify();
+      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 
+                                ExprIterator(c.expr().comps.begin(), cols),
+                                ExprIterator(c.expr().comps.end(), cols),
+                                c.upperBounded()?c.upperBound()-*c.expr():INF));
       return r;
     }

lemon/lp_skeleton.cc

@@ -29 +29 @@
 
   int SkeletonSolverBase::_addRow()
+  {
+    return ++row_num;
+  }
+
+  int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value)
   {
     return ++row_num;

lemon/lp_skeleton.h

@@ -45 +45 @@
     /// \e
     virtual int _addRow();
+    /// \e
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     /// \e
     virtual void _eraseCol(int i);

lemon/maps.h

@@ -231 +231 @@
   /// This map is essentially a wrapper for \c std::vector. It assigns
   /// values to integer keys from the range <tt>[0..size-1]</tt>.
-  /// It can be used with some data structures, for example
-  /// \c UnionFind, \c BinHeap, when the used items are small
+  /// It can be used together with some data structures, e.g.
+  /// heap types and \c UnionFind, when the used items are small
   /// integers. This map conforms to the \ref concepts::ReferenceMap
-  /// "ReferenceMap" concept.
+  /// "ReferenceMap" concept. 
   ///
   /// The simplest way of using this map is through the rangeMap()
@@ -349 +349 @@
   /// The name of this type also refers to this important usage.
   ///
-  /// Apart form that this map can be used in many other cases since it
+  /// Apart form that, this map can be used in many other cases since it
   /// is based on \c std::map, which is a general associative container.
-  /// However keep in mind that it is usually not as efficient as other
+  /// However, keep in mind that it is usually not as efficient as other
   /// maps.
   ///
@@ -1786 +1786 @@
   /// The most important usage of it is storing certain nodes or arcs
   /// that were marked \c true by an algorithm.
-  /// For example it makes easier to store the nodes in the processing
+  /// For example, it makes easier to store the nodes in the processing
   /// order of Dfs algorithm, as the following examples show.
   /// \code
@@ -1801 +1801 @@
   ///
   /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
-  /// it cannot be used when a readable map is needed, for example as
+  /// it cannot be used when a readable map is needed, for example, as
   /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
   ///
@@ -1923 +1923 @@
   /// Otherwise consider to use \c IterableValueMap, which is more 
   /// suitable and more efficient for such cases. It provides iterators
-  /// to traverse the items with the same associated value, however
+  /// to traverse the items with the same associated value, but
   /// it does not have \c InverseMap.
   ///
@@ -3467 +3467 @@
   /// may provide alternative ways to modify the digraph.
   /// The correct behavior of InDegMap is not guarantied if these additional
-  /// features are used. For example the functions
+  /// features are used. For example, the functions
   /// \ref ListDigraph::changeSource() "changeSource()",
   /// \ref ListDigraph::changeTarget() "changeTarget()" and
@@ -3597 +3597 @@
   /// may provide alternative ways to modify the digraph.
   /// The correct behavior of OutDegMap is not guarantied if these additional
-  /// features are used. For example the functions
+  /// features are used. For example, the functions
   /// \ref ListDigraph::changeSource() "changeSource()",
   /// \ref ListDigraph::changeTarget() "changeTarget()" and
@@ -3765 +3765 @@
   }
 
+
+  /// \brief Copy the values of a graph map to another map.
+  ///
+  /// This function copies the values of a graph map to another graph map.
+  /// \c To::Key must be equal or convertible to \c From::Key and
+  /// \c From::Value must be equal or convertible to \c To::Value.
+  ///
+  /// For example, an edge map of \c int value type can be copied to
+  /// an arc map of \c double value type in an undirected graph, but
+  /// an arc map cannot be copied to an edge map.
+  /// Note that even a \ref ConstMap can be copied to a standard graph map,
+  /// but \ref mapFill() can also be used for this purpose.
+  ///
+  /// \param gr The graph for which the maps are defined.
+  /// \param from The map from which the values have to be copied.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+  /// \param to The map to which the values have to be copied.
+  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+  template <typename GR, typename From, typename To>
+  void mapCopy(const GR& gr, const From& from, To& to) {
+    typedef typename To::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+    
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      to.set(it, from[it]);
+    }
+  }
+
+  /// \brief Compare two graph maps.
+  ///
+  /// This function compares the values of two graph maps. It returns 
+  /// \c true if the maps assign the same value for all items in the graph.
+  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
+  /// and their \c Value types must be comparable using \c %operator==().
+  ///
+  /// \param gr The graph for which the maps are defined.
+  /// \param map1 The first map.
+  /// \param map2 The second map.
+  template <typename GR, typename Map1, typename Map2>
+  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
+    typedef typename Map2::Key Item;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+    
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (!(map1[it] == map2[it])) return false;
+    }
+    return true;
+  }
+
+  /// \brief Return an item having minimum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// minimum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Key mapMin(const GR& gr, const Map& map) {
+    return mapMin(gr, map, std::less<typename Map::Value>());
+  }
+
+  /// \brief Return an item having minimum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// minimum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
+    typedef typename Map::Key Item;
+    typedef typename Map::Value Value;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    ItemIt min_item(gr);
+    if (min_item == INVALID) return INVALID;
+    Value min = map[min_item];
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (comp(map[it], min)) {
+        min = map[it];
+        min_item = it;
+      }
+    }
+    return min_item;
+  }
+
+  /// \brief Return an item having maximum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// maximum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Key mapMax(const GR& gr, const Map& map) {
+    return mapMax(gr, map, std::less<typename Map::Value>());
+  }
+
+  /// \brief Return an item having maximum value of a graph map.
+  ///
+  /// This function returns an item (\c Node, \c Arc or \c Edge) having
+  /// maximum value of the given graph map.
+  /// If the item set is empty, it returns \c INVALID.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  /// \param comp Comparison function object.
+  template <typename GR, typename Map, typename Comp>
+  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
+    typedef typename Map::Key Item;
+    typedef typename Map::Value Value;
+    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
+
+    ItemIt max_item(gr);
+    if (max_item == INVALID) return INVALID;
+    Value max = map[max_item];
+    for (ItemIt it(gr); it != INVALID; ++it) {
+      if (comp(max, map[it])) {
+        max = map[it];
+        max_item = it;
+      }
+    }
+    return max_item;
+  }
+
+  /// \brief Return the minimum value of a graph map.
+  ///
+  /// This function returns the minimum value of the given graph map.
+  /// The corresponding item set of the graph must not be empty.
+  ///
+  /// \param gr The graph for which the map is defined.
+  /// \param map The graph map.
+  template <typename GR, typename Map>
+  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
+    return map[mapMin(gr, map, std::