Changes in / [1247:115031ac8001:1249:2c2e8df67ddc] in lemon

Files:

• .hgignore (modified) (1 diff)
• .hgtags (added)
• CMakeLists.txt (modified) (1 diff)
• INSTALL (modified) (1 diff)
• LICENSE (modified) (1 diff)
• Makefile.am (modified) (1 diff)
• NEWS (modified) (3 diffs)
• README (modified) (2 diffs)
• configure.ac (modified) (3 diffs)
• demo/arg_parser_demo.cc (modified) (2 diffs)
• doc/CMakeLists.txt (modified) (3 diffs)
• doc/Doxyfile.in (modified) (1 diff)
• doc/Makefile.am (modified) (3 diffs)
• doc/groups.dox (modified) (22 diffs)
• doc/images/matching.eps (added)
• doc/images/planar.eps (added)
• doc/lgf.dox (modified) (1 diff)
• doc/mainpage.dox.in (modified) (3 diffs)
• doc/min_cost_flow.dox (modified) (5 diffs)
• doc/references.bib (added)
• lemon/Makefile.am (modified) (6 diffs)
• lemon/adaptors.h (modified) (37 diffs)
• lemon/arg_parser.cc (modified) (5 diffs)
• lemon/arg_parser.h (modified) (4 diffs)
• lemon/assert.h (modified) (1 diff)
• lemon/bellman_ford.h (added)
• lemon/bfs.h (modified) (39 diffs)
• lemon/bin_heap.h (modified) (14 diffs)
• lemon/binomial_heap.h (added)
• lemon/bits/array_map.h (modified) (2 diffs)
• lemon/bits/default_map.h (modified) (2 diffs)
• lemon/bits/edge_set_extender.h (modified) (25 diffs)
• lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
• lemon/bits/graph_extender.h (modified) (2 diffs)
• lemon/bits/path_dump.h (modified) (1 diff)
• lemon/bits/solver_bits.h (modified) (1 diff)
• lemon/bits/windows.cc (modified) (2 diffs)
• lemon/bucket_heap.h (modified) (28 diffs)
• lemon/capacity_scaling.h (added)
• lemon/cbc.cc (modified) (1 diff)
• lemon/cbc.h (modified) (3 diffs)
• lemon/circulation.h (modified) (12 diffs)
• lemon/clp.cc (modified) (2 diffs)
• lemon/clp.h (modified) (3 diffs)
• lemon/concepts/digraph.h (modified) (15 diffs)
• lemon/concepts/graph.h (modified) (27 diffs)
• lemon/concepts/graph_components.h (modified) (20 diffs)
• lemon/concepts/heap.h (modified) (6 diffs)
• lemon/concepts/path.h (modified) (12 diffs)
• lemon/connectivity.h (modified) (10 diffs)
• lemon/core.h (modified) (3 diffs)
• lemon/cost_scaling.h (added)
• lemon/counter.h (modified) (1 diff)
• lemon/cplex.cc (modified) (3 diffs)
• lemon/cplex.h (modified) (1 diff)
• lemon/cycle_canceling.h (added)
• lemon/dfs.h (modified) (39 diffs)
• lemon/dheap.h (added)
• lemon/dijkstra.h (modified) (35 diffs)
• lemon/dim2.h (modified) (2 diffs)
• lemon/dimacs.h (modified) (6 diffs)
• lemon/edge_set.h (modified) (8 diffs)
• lemon/euler.h (modified) (6 diffs)
• lemon/fib_heap.h (modified) (12 diffs)
• lemon/fractional_matching.h (added)
• lemon/full_graph.h (modified) (14 diffs)
• lemon/glpk.cc (modified) (2 diffs)
• lemon/glpk.h (modified) (5 diffs)
• lemon/gomory_hu.h (modified) (28 diffs)
• lemon/graph_to_eps.h (modified) (5 diffs)
• lemon/grid_graph.h (modified) (16 diffs)
• lemon/hao_orlin.h (modified) (11 diffs)
• lemon/hartmann_orlin_mmc.h (added)
• lemon/howard_mmc.h (added)
• lemon/hypercube_graph.h (modified) (6 diffs)
• lemon/karp_mmc.h (added)
• lemon/lgf_reader.h (modified) (8 diffs)
• lemon/lgf_writer.h (modified) (7 diffs)
• lemon/list_graph.h (modified) (29 diffs)
• lemon/lp.h (modified) (2 diffs)
• lemon/lp_base.cc (modified) (1 diff)
• lemon/lp_base.h (modified) (33 diffs)
• lemon/lp_skeleton.cc (modified) (2 diffs)
• lemon/lp_skeleton.h (modified) (4 diffs)
• lemon/maps.h (modified) (37 diffs)
• lemon/matching.h (modified) (65 diffs)
• lemon/math.h (modified) (2 diffs)
• lemon/min_cost_arborescence.h (modified) (5 diffs)
• lemon/network_simplex.h (modified) (42 diffs)
• lemon/pairing_heap.h (added)
• lemon/path.h (modified) (4 diffs)
• lemon/planarity.h (added)
• lemon/preflow.h (modified) (11 diffs)
• lemon/quad_heap.h (added)
• lemon/radix_heap.h (modified) (9 diffs)
• lemon/smart_graph.h (modified) (16 diffs)
• lemon/soplex.cc (modified) (3 diffs)
• lemon/soplex.h (modified) (2 diffs)
• lemon/static_graph.h (added)
• lemon/suurballe.h (modified) (21 diffs)
• lemon/time_measure.h (modified) (1 diff)
• lemon/unionfind.h (modified) (2 diffs)
• 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) (3 diffs)
• test/Makefile.am (modified) (7 diffs)
• test/adaptors_test.cc (modified) (3 diffs)
• test/bellman_ford_test.cc (added)
• test/bfs_test.cc (modified) (5 diffs)
• test/circulation_test.cc (modified) (4 diffs)
• test/connectivity_test.cc (modified) (12 diffs)
• test/dfs_test.cc (modified) (5 diffs)
• test/digraph_test.cc (modified) (7 diffs)
• test/dijkstra_test.cc (modified) (5 diffs)
• test/edge_set_test.cc (modified) (1 diff)
• test/euler_test.cc (modified) (5 diffs)
• test/fractional_matching_test.cc (added)
• test/gomory_hu_test.cc (modified) (5 diffs)
• test/graph_copy_test.cc (modified) (4 diffs)
• test/graph_test.cc (modified) (6 diffs)
• test/hao_orlin_test.cc (modified) (6 diffs)
• test/heap_test.cc (modified) (11 diffs)
• test/lgf_test.cc (modified) (5 diffs)
• test/lp_test.cc (modified) (1 diff)
• test/maps_test.cc (modified) (7 diffs)
• test/matching_test.cc (modified) (8 diffs)
• test/min_cost_arborescence_test.cc (modified) (3 diffs)
• test/min_cost_flow_test.cc (modified) (16 diffs)
• test/min_mean_cycle_test.cc (added)
• test/planarity_test.cc (added)
• test/preflow_test.cc (modified) (5 diffs)
• test/suurballe_test.cc (modified) (9 diffs)
• test/test_tools.h (modified) (2 diffs)
• tools/dimacs-solver.cc (modified) (7 diffs)
• tools/lemon-0.x-to-1.x.sh (modified) (2 diffs)

.hgignore

@@ -23 +23 @@
 lemon/stamp-h2
 doc/Doxyfile
+doc/references.dox
 cmake/version.cmake
 .dirstamp

CMakeLists.txt

@@ -115 +115 @@
 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"'.

LICENSE

@@ -2 +2 @@
 copyright/license.
 
-Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
+Copyright (C) 2003-2010 Egervary Jeno Kombinatorikus Optimalizalasi
 Kutatocsoport (Egervary Combinatorial Optimization Research Group,
 EGRES).

Makefile.am

@@ -45 +45 @@
 include doc/Makefile.am
 include tools/Makefile.am
+include scripts/Makefile.am
 
 DIST_SUBDIRS = demo

NEWS

@@ +1 @@
+2011-11-09 Version 1.2.3 released
+
+        Bugfix release.
+
+        #428: Add missing lemon/lemon.pc.cmake to the release tarball
+        #429: Fix VS warnings
+        #430: Fix LpBase::Constr two-side limit bug
+
+2011-08-08 Version 1.2.2 released
+
+        Bugfix release.
+
+        #392: Bug fix in Dfs::start(s,t)
+        #414: Fix wrong initialization in Preflow
+        #404: Update Doxygen configuration
+        #416: Support tests with valgrind
+        #418: Better Win CodeBlock/MinGW support
+        #419: Backport build environment improvements from the main branch
+              - Build of mip_test and lp_test precede the running of the tests
+              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
+              - Do not look for COIN_VOL libraries
+        #382: Allow lgf file without Arc maps
+        #417: Bug fix in CostScaling
+
+2010-10-21 Version 1.2.1 released
+
+        Bugfix release.
+
+        #366: Fix Pred[Matrix]MapPath::empty()
+        #371: Bug fix in (di)graphCopy()
+              The target graph is cleared before adding nodes and arcs/edges.
+
+        #364: Add missing UndirectedTags
+        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
+        #372: Fix a critical bug in preflow
+
+2010-03-19 Version 1.2 released
+
+        This is major feature release
+
+        * New algorithms
+          * Bellman-Ford algorithm (#51)
+          * Minimum mean cycle algorithms (#179)
+            * Karp, Hartman-Orlin and Howard algorithms
+          * New minimum cost flow algorithms (#180)
+            * Cost Scaling algorithms
+            * Capacity Scaling algorithm
+            * Cycle-Canceling algorithms
+          * Planarity related algorithms (#62)
+            * Planarity checking algorithm
+            * Planar embedding algorithm
+            * Schnyder's planar drawing algorithm
+            * Coloring planar graphs with five or six colors
+          * Fractional matching algorithms (#314)
+        * New data structures
+          * StaticDigraph structure (#68)
+          * Several new priority queue structures (#50, #301)
+            * Fibonacci, Radix, Bucket, Pairing, Binomial
+              D-ary and fourary heaps (#301)
+          * Iterable map structures (#73)
+        * Other new tools and functionality
+          * Map utility functions (#320)
+          * Reserve functions are added to ListGraph and SmartGraph (#311)
+          * A resize() function is added to HypercubeGraph (#311)
+          * A count() function is added to CrossRefMap (#302)
+          * Support for multiple targets in Suurballe using fullInit() (#181)
+          * Traits class and named parameters for Suurballe (#323)
+          * Separate reset() and resetParams() functions in NetworkSimplex
+            to handle graph changes (#327)
+          * tolerance() functions are added to HaoOrlin (#306)
+        * Implementation improvements
+          * Improvements in weighted matching algorithms (#314)
+            * Jumpstart initialization
+          * ArcIt iteration is based on out-arc lists instead of in-arc lists
+            in ListDigraph (#311)
+          * Faster add row operation in CbcMip (#203)
+          * Better implementation for split() in ListDigraph (#311)
+          * ArgParser can also throw exception instead of exit(1) (#332)
+        * Miscellaneous
+          * A simple interactive bootstrap script
+          * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
+                #316,#319)
+            * BibTeX references in the doc (#184)
+          * Optionally use valgrind when running tests
+          * Also check ReferenceMapTag in concept checks (#312)
+          * dimacs-solver uses long long type by default.
+        * Several bugfixes (compared to release 1.1):
+          #295: Suppress MSVC warnings using pragmas
+          ----: Various CMAKE related improvements
+                * Remove duplications from doc/CMakeLists.txt
+                * Rename documentation install folder from 'docs' to 'html'
+                * Add tools/CMakeLists.txt to the tarball
+                * Generate and install LEMONConfig.cmake
+                * Change the label of the html project in Visual Studio
+                * Fix the check for the 'long long' type
+                * Put the version string into config.h
+                * Minor CMake improvements
+                * Set the version to 'hg-tip' if everything fails
+          #311: Add missing 'explicit' keywords
+          #302: Fix the implementation and doc of CrossRefMap
+          #308: Remove duplicate list_graph.h entry from source list
+          #307: Bugfix in Preflow and Circulation
+          #305: Bugfix and extension in the rename script
+          #312: Also check ReferenceMapTag in concept checks
+          #250: Bugfix in pathSource() and pathTarget()
+          #321: Use pathCopy(from,to) instead of copyPath(to,from)
+          #322: Distribure LEMONConfig.cmake.in
+          #330: Bug fix in map_extender.h
+          #336: Fix the date field comment of graphToEps() output
+          #323: Bug fix in Suurballe
+          #335: Fix clear() function in ExtendFindEnum
+          #337: Use void* as the LPX object pointer
+          #317: Fix (and improve) error message in mip_test.cc
+                Remove unnecessary OsiCbc dependency
+          #356: Allow multiple executions of weighted matching algorithms (#356)
+
 2009-05-13 Version 1.1 released
 
@@ -73 +189 @@
           ----: Add missing unistd.h include to time_measure.h
           #204: Compilation bug fixed in graph_to_eps.h with VS2005
-          #214,#215: windows.h should never be included by lemon headers
+          #214,#215: windows.h should never be included by LEMON headers
           #230: Build systems check the availability of 'long long' type
           #229: Default implementation of Tolerance<> is used for integer types
@@ -95 +211 @@
 2008-10-13 Version 1.0 released
 
-        This is the first stable release of LEMON. Compared to the 0.x
-        release series, it features a considerably smaller but more
-        matured set of tools. The API has also completely revised and
-        changed in several places.
-
-        * The major name changes compared to the 0.x series (see the
+        This is the first stable release of LEMON. Compared to the 0.x
+        release series, it features a considerably smaller but more
+        matured set of tools. The API has also completely revised and
+        changed in several places.
+
+        * The major name changes compared to the 0.x series (see the
           Migration Guide in the doc for more details)
           * Graph -> Digraph, UGraph -> Graph
           * Edge -> Arc, UEdge -> Edge
-          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
-        * Other improvements
-          * Better documentation
-          * Reviewed and cleaned up codebase
-          * CMake based build system (along with the autotools based one)
-        * Contents of the library (ported from 0.x)
-          * Algorithms
-            * breadth-first search (bfs.h)
-            * depth-first search (dfs.h)
-            * Dijkstra's algorithm (dijkstra.h)
-            * Kruskal's algorithm (kruskal.h)
-          * Data structures
-            * graph data structures (list_graph.h, smart_graph.h)
-            * path data structures (path.h)
-            * binary heap data structure (bin_heap.h)
-            * union-find data structures (unionfind.h)
-            * miscellaneous property maps (maps.h)
-            * two dimensional vector and bounding box (dim2.h)
+          * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
+        * Other improvements
+          * Better documentation
+          * Reviewed and cleaned up codebase
+          * CMake based build system (along with the autotools based one)
+        * Contents of the library (ported from 0.x)
+          * Algorithms
+            * breadth-first search (bfs.h)
+            * depth-first search (dfs.h)
+            * Dijkstra's algorithm (dijkstra.h)
+            * Kruskal's algorithm (kruskal.h)
+          * Data structures
+            * graph data structures (list_graph.h, smart_graph.h)
+            * path data structures (path.h)
+            * binary heap data structure (bin_heap.h)
+            * union-find data structures (unionfind.h)
+            * miscellaneous property maps (maps.h)
+            * two dimensional vector and bounding box (dim2.h)
           * Concepts
-            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
+            * graph structure concepts (concepts/digraph.h, concepts/graph.h,
               concepts/graph_components.h)
-            * concepts for other structures (concepts/heap.h, concepts/maps.h,
-              concepts/path.h)
-          * Tools
-            * Mersenne twister random number generator (random.h)
-            * tools for measuring cpu and wall clock time (time_measure.h)
-            * tools for counting steps and events (counter.h)
-            * tool for parsing command line arguments (arg_parser.h)
-            * tool for visualizing graphs (graph_to_eps.h)
-            * tools for reading and writing data in LEMON Graph Format
+            * concepts for other structures (concepts/heap.h, concepts/maps.h,
+              concepts/path.h)
+          * Tools
+            * Mersenne twister random number generator (random.h)
+            * tools for measuring cpu and wall clock time (time_measure.h)
+            * tools for counting steps and events (counter.h)
+            * tool for parsing command line arguments (arg_parser.h)
+            * tool for visualizing graphs (graph_to_eps.h)
+            * tools for reading and writing data in LEMON Graph Format
               (lgf_reader.h, lgf_writer.h)
             * tools to handle the anomalies of calculations with
-              floating point numbers (tolerance.h)
+              floating point numbers (tolerance.h)
             * tools to manage RGB colors (color.h)
-          * Infrastructure
-            * extended assertion handling (assert.h)
-            * exception classes and error handling (error.h)
-            * concept checking (concept_check.h)
-            * commonly used mathematical constants (math.h)
+          * Infrastructure
+            * extended assertion handling (assert.h)
+            * exception classes and error handling (error.h)
+            * concept checking (concept_check.h)
+            * commonly used mathematical constants (math.h)

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.
@@ -129 +145 @@
 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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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

@@ -18 +18 @@
 )
 
-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)
@@ -29 +29 @@
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/matching.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps
     COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
@@ -35 +36 @@
     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

@@ -98 +98 @@
                          "@abs_top_srcdir@/tools" \
                          "@abs_top_srcdir@/test/test_tools.h" \
-                         "@abs_top_builddir@/doc/mainpage.dox"
+                         "@abs_top_builddir@/doc/mainpage.dox" \
+                         "@abs_top_builddir@/doc/references.dox"
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          = *.h \

doc/Makefile.am

@@ -12 +12 @@
         doc/named-param.dox \
         doc/namespaces.dox \
+        doc/references.bib \
         doc/template.h \
         doc/html \
@@ -29 +30 @@
         connected_components.eps \
         edge_biconnected_components.eps \
+        matching.eps \
         node_biconnected_components.eps \
+        planar.eps \
         strongly_connected_components.eps
 
@@ -68 +71 @@
         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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -227 +227 @@
 
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup paths Path Structures
 @ingroup datas
@@ -247 +239 @@
 any kind of path structure.
 
-\sa lemon::concepts::Path
+\sa \ref concepts::Path "Path concept"
+*/
+
+/**
+@defgroup heaps Heap Structures
+@ingroup datas
+\brief %Heap structures implemented in LEMON.
+
+This group contains the heap structures implemented in LEMON.
+
+LEMON provides several heap classes. They are efficient implementations
+of the abstract data type \e priority \e queue. They store items with
+specified values called \e priorities in such a way that finding and
+removing the item with minimum priority are efficient.
+The basic operations are adding and erasing items, changing the priority
+of an item, etc.
+
+Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+The heap implementations have the same interface, thus any of them can be
+used easily in such algorithms.
+
+\sa \ref concepts::Heap "Heap concept"
 */
 
@@ -260 +273 @@
 
 /**
+@defgroup geomdat Geometric Data Structures
+@ingroup auxdat
+\brief Geometric data structures implemented in LEMON.
+
+This group contains geometric data structures implemented in LEMON.
+
+ - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
+   vector with the usual operations.
+ - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
+   rectangular bounding box of a set of \ref lemon::dim2::Point
+   "dim2::Point"'s.
+*/
+
+/**
 @defgroup algs Algorithms
 \brief This group contains the several algorithms
@@ -274 +301 @@
 
 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.
 */
 
@@ -282 +310 @@
 \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
@@ -290 +319 @@
    but the digraph should not contain directed cycles with negative total
    length.
- - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
-   for solving the \e all-pairs \e shortest \e paths \e problem when arc
-   lenghts can be either positive or negative, but the digraph should
-   not contain directed cycles with negative total length.
  - \ref Suurballe A successive shortest path algorithm for finding
    arc-disjoint paths between two nodes having minimum total length.
@@ -299 +324 @@
 
 /**
+@defgroup spantree Minimum Spanning Tree Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences \ref clrs01algorithms.
+*/
+
+/**
 @defgroup max_flow Maximum Flow Algorithms
 @ingroup algs
@@ -304 +338 @@
 
 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
@@ -318 +352 @@
 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 
-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
-fastest method for computing a maximum flow. All implementations
-also provide functions to query the minimum cut, which is the dual
-problem of maximum flow.
-
-\ref Circulation is a preflow push-relabel algorithm implemented directly 
+\ref Preflow is an efficient implementation of Goldberg-Tarjan's
+preflow push-relabel algorithm \ref goldberg88newapproach for finding
+maximum flows. It also provides functions to query the minimum cut,
+which is the dual problem of maximum flow.
+
+\ref Circulation is a preflow push-relabel algorithm implemented directly
 for finding feasible circulations, which is a somewhat different problem,
 but it is strongly related to maximum flow.
@@ -342 +370 @@
 
 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,
@@ -376 +406 @@
 
 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
+    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
 
 LEMON contains several algorithms related to minimum cut problems:
@@ -382 +412 @@
 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   in directed graphs.
-- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
-  calculating minimum cut in undirected graphs.
 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   all-pairs minimum cut in undirected graphs.
@@ -392 +420 @@
 
 /**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html edge_biconnected_components.png
-\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
-*/
-
-/**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
+@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 KarpMmc Karp's original algorithm \ref amo93networkflows,
+  \ref dasdan98minmeancycle.
+- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
+  version of Karp's algorithm \ref dasdan98minmeancycle.
+- \ref HowardMmc Howard's policy iteration algorithm
+  \ref dasdan98minmeancycle.
+
+In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+most efficient one, though the best known theoretical bound on its running
+time is exponential.
+Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" 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.
 */
 
@@ -433 +474 @@
 
 The matching algorithms implemented in LEMON:
-- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref PrBipartiteMatching Push-relabel algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref MaxWeightedBipartiteMatching
-  Successive shortest path algorithm for calculating maximum weighted
-  matching and maximum weighted bipartite matching in bipartite graphs.
-- \ref MinCostMaxBipartiteMatching
-  Successive shortest path algorithm for calculating minimum cost maximum
-  matching in bipartite graphs.
 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   maximum cardinality matching in general graphs.
@@ -450 +481 @@
   Edmond's blossom shrinking algorithm for calculating maximum weighted
   perfect matching in general graphs.
-
-\image html bipartite_matching.png
-\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
-*/
-
-/**
-@defgroup spantree Minimum Spanning Tree Algorithms
-@ingroup algs
-\brief Algorithms for finding minimum cost spanning trees and arborescences.
-
-This group contains the algorithms for finding minimum cost spanning
-trees and arborescences.
+- \ref MaxFractionalMatching Push-relabel algorithm for calculating
+  maximum cardinality fractional matching in general graphs.
+- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
+  maximum weighted fractional matching in general graphs.
+- \ref MaxWeightedPerfectFractionalMatching
+  Augmenting path algorithm for calculating maximum weighted
+  perfect fractional matching in general graphs.
+
+\image html matching.png
+\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
+*/
+
+/**
+@defgroup graph_properties Connectivity and Other Graph Properties
+@ingroup algs
+\brief Algorithms for discovering the graph properties
+
+This group contains the algorithms for discovering the graph properties
+like connectivity, bipartiteness, euler property, simplicity etc.
+
+\image html connected_components.png
+\image latex connected_components.eps "Connected components" width=\textwidth
+*/
+
+/**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group contains the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
 */
 
@@ -471 +524 @@
 This group contains some algorithms implemented in LEMON
 in order to make it easier to implement complex algorithms.
-*/
-
-/**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
 */
 
@@ -492 +536 @@
 
 /**
-@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.
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip Solvers
-@ingroup lp_group
-\brief Helper tools to the Lp and Mip solvers.
-
-This group adds some helper tools to general optimization framework
-implemented in LEMON.
-*/
-
-/**
-@defgroup metah Metaheuristics
-@ingroup gen_opt_group
-\brief Metaheuristics for LEMON library.
-
-This group contains some metaheuristic optimization tools.
+\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.
 */
 
@@ -588 +618 @@
 
 /**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
 @ingroup io_group
 \brief Read and write files in DIMACS format
@@ -637 +667 @@
 \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.
 */
 
@@ -650 +680 @@
 
 /**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (<tt>./configure;make</tt>) will compile
+them, as well.
+*/
+
+/**
 \anchor demoprograms
 
@@ -661 +700 @@
 */
 
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (<tt>./configure;make</tt>) will compile
-them, as well.
-*/
-
 }

doc/lgf.dox

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/mainpage.dox.in

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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$.
- 
+
 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
@@ -120 +120 @@
 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 
-It means that the total demand must be less or equal to the 
+It means that the total demand must be less or equal to the
 total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 positive) and all the demands have to be satisfied, but there
@@ -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

@@ -59 +59 @@
         lemon/arg_parser.h \
         lemon/assert.h \
+        lemon/bellman_ford.h \
         lemon/bfs.h \
         lemon/bin_heap.h \
+        lemon/binomial_heap.h \
         lemon/bucket_heap.h \
+        lemon/capacity_scaling.h \
         lemon/cbc.h \
         lemon/circulation.h \
@@ -68 +71 @@
         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 \
         lemon/dijkstra.h \
         lemon/dim2.h \
@@ -80 +86 @@
         lemon/euler.h \
         lemon/fib_heap.h \
+        lemon/fractional_matching.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -85 +92 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/hartmann_orlin_mmc.h \
+        lemon/howard_mmc.h \
         lemon/hypercube_graph.h \
+        lemon/karp_mmc.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \
@@ -100 +110 @@
         lemon/nauty_reader.h \
         lemon/network_simplex.h \
+        lemon/pairing_heap.h \
         lemon/path.h \
+        lemon/planarity.h \
         lemon/preflow.h \
+        lemon/quad_heap.h \
         lemon/radix_heap.h \
         lemon/radix_sort.h \
@@ -107 +120 @@
         lemon/smart_graph.h \
         lemon/soplex.h \
+        lemon/static_graph.h \
         lemon/suurballe.h \
         lemon/time_measure.h \

lemon/adaptors.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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.
@@ -419 +422 @@
       Parent::initialize(digraph);
       _node_filter = &node_filter;
-      _arc_filter = &arc_filter;      
+      _arc_filter = &arc_filter;
     }
 
@@ -506 +509 @@
 
     template <typename V>
-    class NodeMap 
-      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
-              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
+    class NodeMap
+      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
+              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
+        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 
     public:
@@ -533 +536 @@
 
     template <typename V>
-    class ArcMap 
+    class ArcMap
       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
+              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
@@ -580 +583 @@
       Parent::initialize(digraph);
       _node_filter = &node_filter;
-      _arc_filter = &arc_filter;      
+      _arc_filter = &arc_filter;
     }
 
@@ -649 +652 @@
 
     template <typename V>
-    class NodeMap 
+    class NodeMap
       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
-      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
+      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 
@@ -676 +679 @@
 
     template <typename V>
-    class ArcMap 
+    class ArcMap
       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
@@ -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.
@@ -1017 +1022 @@
 
     template <typename V>
-    class NodeMap 
+    class NodeMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 
@@ -1044 +1049 @@
 
     template <typename V>
-    class ArcMap 
+    class ArcMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 
@@ -1071 +1076 @@
 
     template <typename V>
-    class EdgeMap 
+    class EdgeMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 
@@ -1113 +1118 @@
     NF* _node_filter;
     EF* _edge_filter;
-    SubGraphBase() 
-          : Parent(), _node_filter(0), _edge_filter(0) { }
+    SubGraphBase()
+          : Parent(), _node_filter(0), _edge_filter(0) { }
 
     void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
@@ -1215 +1220 @@
 
     template <typename V>
-    class NodeMap 
+    class NodeMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 
@@ -1242 +1247 @@
 
     template <typename V>
-    class ArcMap 
+    class ArcMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 
@@ -1269 +1274 @@
 
     template <typename V>
-    class EdgeMap 
+    class EdgeMap
       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
-      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
-        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
+      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
+        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 
     public:
@@ -1314 +1319 @@
   /// 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.
@@ -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.
@@ -1496 +1505 @@
 #endif
     typedef DigraphAdaptorExtender<
-      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
+      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
                      true> > Parent;
 
@@ -1517 +1526 @@
     /// Creates a subgraph for the given digraph or graph with the
     /// given node filter map.
-    FilterNodes(GR& graph, NF& node_filter) 
+    FilterNodes(GR& graph, NF& node_filter)
       : Parent(), const_true_map()
     {
@@ -1555 +1564 @@
                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
     public GraphAdaptorExtender<
-      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
+      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
                    true> > {
 
     typedef GraphAdaptorExtender<
-      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
+      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
                    true> > Parent;
 
@@ -1619 +1628 @@
   /// 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.
@@ -1643 +1654 @@
 #endif
     typedef DigraphAdaptorExtender<
-      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
+      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
                      AF, false> > Parent;
 
@@ -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.
@@ -1749 +1762 @@
   class FilterEdges :
     public GraphAdaptorExtender<
-      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
+      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
                    EF, false> > {
 #endif
     typedef GraphAdaptorExtender<
-      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
+      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
                    EF, false> > Parent;
 
@@ -1778 +1791 @@
     /// Creates a subgraph for the given graph with the given edge
     /// filter map.
-    FilterEdges(GR& graph, EF& edge_filter) 
+    FilterEdges(GR& graph, EF& edge_filter)
       : Parent(), const_true_map() {
       Parent::initialize(graph, const_true_map, edge_filter);
@@ -1846 +1859 @@
       bool _forward;
 
-      Arc(const Edge& edge, bool forward) 
+      Arc(const Edge& edge, bool forward)
         : _edge(edge), _forward(forward) {}
 
@@ -2086 +2099 @@
 
       ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
-        : _forward(*adaptor._digraph, value), 
+        : _forward(*adaptor._digraph, value),
           _backward(*adaptor._digraph, value) {}
 
@@ -2204 +2217 @@
     typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
     EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
-    
+
     typedef EdgeNotifier ArcNotifier;
     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
@@ -2232 +2245 @@
   /// by adding or removing nodes or edges, unless the \c GR template
   /// 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.
@@ -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.
@@ -2679 +2698 @@
   /// 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.
   /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2708 +2729 @@
            typename FM = CM,
            typename TL = Tolerance<typename CM::Value> >
-  class ResidualDigraph 
+  class ResidualDigraph
     : public SubDigraph<
         Undirector<const DGR>,
@@ -2765 +2786 @@
     ResidualDigraph(const DGR& digraph, const CM& capacity,
                     FM& flow, const TL& tolerance = Tolerance())
-      : Parent(), _capacity(&capacity), _flow(&flow), 
+      : Parent(), _capacity(&capacity), _flow(&flow),
         _graph(digraph), _node_filter(),
         _forward_filter(capacity, flow, tolerance),
@@ -2847 +2868 @@
 
       /// Constructor
-      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
+      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
         : _adaptor(&adaptor) {}
 
@@ -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.
@@ -3424 +3448 @@
     /// to get a node map of the split digraph.
     /// Its value type is inherited from the first node map type (\c IN).
-    /// \tparam IN The type of the node map for the in-nodes. 
+    /// \tparam IN The type of the node map for the in-nodes.
     /// \tparam OUT The type of the node map for the out-nodes.
     template <typename IN, typename OUT>

lemon/arg_parser.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -35 +35 @@
 namespace lemon {
 
+  ///Exception used by ArgParser
+
+  ///Exception used by ArgParser.
+  ///
+  class ArgParserException : public Exception {
+  public:
+    /// Reasons for failure
+
+    /// Reasons for failure.
+    ///
+    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
 
@@ -116 +161 @@
                     const std::string &help,
                     void (*func)(void *),void *data);
+
+    bool _exit_on_problems;
+
+    void _terminate(ArgParserException::Reason reason) const;
 
   public:
@@ -381 +430 @@
     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/assert.h

@@ -200 +200 @@
                              ::lemon::_assert_bits::cstringify(msg),    \
                              #exp), 0)))
-#    if LEMON_ENABLE_DEBUG
+#    if defined LEMON_ENABLE_DEBUG
 #      define LEMON_DEBUG(exp, msg)                                     \
          (static_cast<void> (!!(exp) ? 0 : (                            \

lemon/bfs.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -48 +48 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a \c PredMap.
@@ -63 +63 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -82 +83 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must conform to
+    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a \c ReachedMap.
@@ -97 +99 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a \c DistMap.
@@ -121 +123 @@
   ///\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,
@@ -226 +233 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c PredMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
@@ -246 +253 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c DistMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
@@ -266 +273 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ReachedMap type.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must conform to
+    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
@@ -286 +294 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ProcessedMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
@@ -414 +422 @@
     ///The simplest way to execute the BFS algorithm is to use one of the
     ///member functions called \ref run(Node) "run()".\n
-    ///If you need more control on the execution, first you have to call
-    ///\ref init(), then you can add several source nodes with
+    ///If you need better control on the execution, you have to call
+    ///\ref init() first, then you can add several source nodes with
     ///\ref addSource(). Finally the actual path computation can be
     ///performed with one of the \ref start() functions.
@@ -701 +709 @@
     ///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.
@@ -738 +742 @@
     ///@{
 
-    ///The shortest path to a node.
-
-    ///Returns the shortest path to a node.
+    ///The shortest path to the given node.
+
+    ///Returns the shortest path to the given node from the root(s).
     ///
     ///\warning \c t should be reached from the root(s).
@@ -748 +752 @@
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
-    ///The distance of a node from the root(s).
-
-    ///Returns the distance of a node from the root(s).
+    ///The distance of the given node from the root(s).
+
+    ///Returns the distance of the given node from the root(s).
     ///
     ///\warning If node \c v is not reached from the root(s), then
@@ -759 +763 @@
     int dist(Node v) const { return (*_dist)[v]; }
 
-    ///Returns the 'previous arc' of the shortest path tree for a node.
-
+    ///\brief Returns the 'previous arc' of the shortest path tree for
+    ///the given node.
+    ///
     ///This function returns the 'previous arc' of the shortest path
     ///tree for the node \c v, i.e. it returns the last arc of a
@@ -767 +772 @@
     ///
     ///The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref predNode().
+    ///tree used in \ref predNode() and \ref predMap().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -773 +778 @@
     Arc predArc(Node v) const { return (*_pred)[v];}
 
-    ///Returns the 'previous node' of the shortest path tree for a node.
-
+    ///\brief Returns the 'previous node' of the shortest path tree for
+    ///the given node.
+    ///
     ///This function returns the 'previous node' of the shortest path
     ///tree for the node \c v, i.e. it returns the last but one node
-    ///from a shortest path from a root to \c v. It is \c INVALID
+    ///of a shortest path from a root to \c v. It is \c INVALID
     ///if \c v is not reached from the root(s) or if \c v is a root.
     ///
     ///The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref predArc().
+    ///tree used in \ref predArc() and \ref predMap().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -802 +808 @@
     ///
     ///Returns a const reference to the node map that stores the predecessor
-    ///arcs, which form the shortest path tree.
+    ///arcs, which form the shortest path tree (forest).
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -808 +814 @@
     const PredMap &predMap() const { return *_pred;}
 
-    ///Checks if a node is reached from the root(s).
+    ///Checks if the given node is reached from the root(s).
 
     ///Returns \c true if \c v is reached from the root(s).
@@ -834 +840 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a PredMap.
@@ -849 +855 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///By default, it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
@@ -869 +875 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must conform to
+    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a ReachedMap.
@@ -884 +891 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
@@ -899 +906 @@
 
     ///The type of the shortest paths.
-    ///It must meet the \ref concepts::Path "Path" concept.
+    ///It must conform to the \ref concepts::Path "Path" concept.
     typedef lemon::Path<Digraph> Path;
   };
@@ -905 +912 @@
   /// Default traits class used by BfsWizard
 
-  /// To make it easier to use Bfs algorithm
-  /// we have created a wizard class.
-  /// This \ref BfsWizard class needs default traits,
-  /// as well as the \ref Bfs class.
-  /// The \ref BfsWizardBase is a class to be the default traits of the
-  /// \ref BfsWizard class.
+  /// Default traits class used by BfsWizard.
+  /// \tparam GR The type of the digraph.
   template<class GR>
   class BfsWizardBase : public BfsWizardDefaultTraits<GR>
@@ -938 +941 @@
     /// Constructor.
 
-    /// This constructor does not require parameters, therefore it initiates
+    /// This constructor does not require parameters, it initiates
     /// all of the attributes to \c 0.
     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -963 +966 @@
   /// 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
@@ -968 +974 @@
     typedef TR Base;
 
-    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
 
@@ -976 +981 @@
     typedef typename Digraph::OutArcIt OutArcIt;
 
-    ///\brief The type of the map that stores the predecessor
-    ///arcs of the shortest paths.
     typedef typename TR::PredMap PredMap;
-    ///\brief The type of the map that stores the distances of the nodes.
     typedef typename TR::DistMap DistMap;
-    ///\brief The type of the map that indicates which nodes are reached.
     typedef typename TR::ReachedMap ReachedMap;
-    ///\brief The type of the map that indicates which nodes are processed.
     typedef typename TR::ProcessedMap ProcessedMap;
-    ///The type of the shortest paths
     typedef typename TR::Path Path;
 
@@ -1055 +1054 @@
     ///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()
     {
@@ -1068 +1067 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
-    ///for setting PredMap object.
-    ///
-    ///\ref named-func-param "Named parameter"
-    ///for setting PredMap object.
+
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///the predecessor map.
+    ///
+    ///\ref named-templ-param "Named parameter" function for setting
+    ///the map that stores the predecessor arcs of the nodes.
     template<class T>
     BfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1086 +1086 @@
       SetReachedMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
-    ///for setting ReachedMap object.
-    ///
-    /// \ref named-func-param "Named parameter"
-    ///for setting ReachedMap object.
+
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///the reached map.
+    ///
+    ///\ref named-templ-param "Named parameter" function for setting
+    ///the map that indicates which nodes are reached.
     template<class T>
     BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1104 +1105 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
-    ///for setting DistMap object.
-    ///
-    /// \ref named-func-param "Named parameter"
-    ///for setting DistMap object.
+
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///the distance map.
+    ///
+    ///\ref named-templ-param "Named parameter" function for setting
+    ///the map that stores the distances of the nodes calculated
+    ///by the algorithm.
     template<class T>
     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
@@ -1122 +1125 @@
       SetProcessedMapBase(const TR &b) : TR(b) {}
     };
-    ///\brief \ref named-func-param "Named parameter"
-    ///for setting ProcessedMap object.
-    ///
-    /// \ref named-func-param "Named parameter"
-    ///for setting ProcessedMap object.
+
+    ///\brief \ref named-func-param "Named parameter" for setting
+    ///the processed map.
+    ///
+    ///\ref named-templ-param "Named parameter" function for setting
+    ///the map that indicates which nodes are processed.
     template<class T>
     BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1266 +1270 @@
     ///
     /// The type of the map that indicates which nodes are reached.
-    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    /// It must conform to
+    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
 
@@ -1304 +1309 @@
   /// 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>
@@ -1427 +1432 @@
     /// The simplest way to execute the BFS algorithm is to use one of the
     /// member functions called \ref run(Node) "run()".\n
-    /// If you need more control on the execution, first you have to call
-    /// \ref init(), then you can add several source nodes with
+    /// If you need better control on the execution, you have to call
+    /// \ref init() first, then you can add several source nodes with
     /// \ref addSource(). Finally the actual path computation can be
     /// performed with one of the \ref start() functions.
@@ -1700 +1705 @@
     /// \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.
@@ -1737 +1738 @@
     ///@{
 
-    /// \brief Checks if a node is reached from the root(s).
+    /// \brief Checks if the given node is reached from the root(s).
     ///
     /// Returns \c true if \c v is reached from the root(s).

lemon/bin_heap.h

@@ -20 +20 @@
 #define LEMON_BIN_HEAP_H
 
-///\ingroup auxdat
+///\ingroup heaps
 ///\file
-///\brief Binary Heap implementation.
+///\brief Binary heap implementation.
 
 #include <vector>
@@ -30 +30 @@
 namespace lemon {
 
-  ///\ingroup auxdat
+  /// \ingroup heaps
   ///
-  ///\brief A Binary Heap implementation.
+  /// \brief Binary heap data structure.
   ///
-  ///This class implements the \e binary \e heap data structure.
+  /// This class implements the \e binary \e heap data structure.
+  /// It fully conforms to the \ref concepts::Heap "heap concept".
   ///
-  ///A \e heap is a data structure for storing items with specified values
-  ///called \e priorities in such a way that finding the item with minimum
-  ///priority is efficient. \c CMP specifies the ordering of the priorities.
-  ///In a heap one can change the priority of an item, add or erase an
-  ///item, etc.
-  ///
-  ///\tparam PR Type of the priority of the items.
-  ///\tparam IM A read and writable item map with int values, used internally
-  ///to handle the cross references.
-  ///\tparam CMP A functor class for the ordering of the priorities.
-  ///The default is \c std::less<PR>.
-  ///
-  ///\sa FibHeap
-  ///\sa Dijkstra
+  /// \tparam PR Type of the priorities of the items.
+  /// \tparam IM A read-writable item map with \c int values, used
+  /// internally to handle the cross references.
+  /// \tparam CMP A functor class for comparing the priorities.
+  /// The default is \c std::less<PR>.
+#ifdef DOXYGEN
+  template <typename PR, typename IM, typename CMP>
+#else
   template <typename PR, typename IM, typename CMP = std::less<PR> >
+#endif
   class BinHeap {
-
   public:
-    ///\e
+
+    /// Type of the item-int map.
     typedef IM ItemIntMap;
-    ///\e
+    /// Type of the priorities.
     typedef PR Prio;
-    ///\e
+    /// Type of the items stored in the heap.
     typedef typename ItemIntMap::Key Item;
-    ///\e
+    /// Type of the item-priority pairs.
     typedef std::pair<Item,Prio> Pair;
-    ///\e
+    /// Functor type for comparing the priorities.
     typedef CMP Compare;
 
-    /// \brief Type to represent the items states.
-    ///
-    /// Each Item element have a state associated to it. It may be "in heap",
-    /// "pre heap" or "post heap". The latter two are indifferent from the
+    /// \brief Type to represent the states of the items.
+    ///
+    /// Each item has a state associated to it. It can be "in heap",
+    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -85 +81 @@
 
   public:
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param map should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
+
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    /// \param map A map that assigns \c int values to the items.
+    /// It is used internally to handle the cross references.
+    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param map should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
-    ///
-    /// \param comp The comparator function object.
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    /// \param map A map that assigns \c int values to the items.
+    /// It is used internally to handle the cross references.
+    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+    /// \param comp The function object used for comparing the priorities.
     BinHeap(ItemIntMap &map, const Compare &comp)
       : _iim(map), _comp(comp) {}
 
 
-    /// The number of items stored in the heap.
-    ///
-    /// \brief Returns the number of items stored in the heap.
+    /// \brief The number of items stored in the heap.
+    ///
+    /// This function returns the number of items stored in the heap.
     int size() const { return _data.size(); }
 
-    /// \brief Checks if the heap stores no items.
-    ///
-    /// Returns \c true if and only if the heap stores no items.
+    /// \brief Check if the heap is empty.
+    ///
+    /// This function returns \c true if the heap is empty.
     bool empty() const { return _data.empty(); }
 
-    /// \brief Make empty this heap.
-    ///
-    /// Make empty this heap. It does not change the cross reference map.
-    /// If you want to reuse what is not surely empty you should first clear
-    /// the heap and after that you should set the cross reference map for
-    /// each item to \c PRE_HEAP.
+    /// \brief Make the heap empty.
+    ///
+    /// This functon makes the heap empty.
+    /// It does not change the cross reference map. If you want to reuse
+    /// a heap that is not surely empty, you should first clear it and
+    /// then you should set the cross reference map to \c PRE_HEAP
+    /// for each item.
     void clear() {
       _data.clear();
@@ -128 +125 @@
     static int parent(int i) { return (i-1)/2; }
 
-    static int second_child(int i) { return 2*i+2; }
+    static int secondChild(int i) { return 2*i+2; }
     bool less(const Pair &p1, const Pair &p2) const {
       return _comp(p1.second, p2.second);
     }
 
-    int bubble_up(int hole, Pair p) {
+    int bubbleUp(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,_data[par]) ) {
@@ -144 +141 @@
     }
 
-    int bubble_down(int hole, Pair p, int length) {
-      int child = second_child(hole);
+    int bubbleDown(int hole, Pair p, int length) {
+      int child = secondChild(hole);
       while(child < length) {
         if( less(_data[child-1], _data[child]) ) {
@@ -154 +151 @@
         move(_data[child], hole);
         hole = child;
-        child = second_child(hole);
+        child = secondChild(hole);
       }
       child--;
@@ -172 +169 @@
 
   public:
+
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// Adds \c p.first to the heap with priority \c p.second.
+    /// This function inserts \c p.first to the heap with priority
+    /// \c p.second.
     /// \param p The pair to insert.
+    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair &p) {
       int n = _data.size();
       _data.resize(n+1);
-      bubble_up(n, p);
-    }
-
-    /// \brief Insert an item into the heap with the given heap.
-    ///
-    /// Adds \c i to the heap with priority \c p.
+      bubbleUp(n, p);
+    }
+
+    /// \brief Insert an item into the heap with the given priority.
+    ///
+    /// This function inserts the given item into the heap with the
+    /// given priority.
     /// \param i The item to insert.
     /// \param p The priority of the item.
+    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 
-    /// \brief Returns the item with minimum priority relative to \c Compare.
-    ///
-    /// This method returns the item with minimum priority relative to \c
-    /// Compare.
-    /// \pre The heap must be nonempty.
+    /// \brief Return the item having minimum priority.
+    ///
+    /// This function returns the item having minimum priority.
+    /// \pre The heap must be non-empty.
     Item top() const {
       return _data[0].first;
     }
 
-    /// \brief Returns the minimum priority relative to \c Compare.
-    ///
-    /// It returns the minimum priority relative to \c Compare.
-    /// \pre The heap must be nonempty.
+    /// \brief The minimum priority.
+    ///
+    /// This function returns the minimum priority.
+    /// \pre The heap must be non-empty.
     Prio prio() const {
       return _data[0].second;
     }
 
-    /// \brief Deletes the item with minimum priority relative to \c Compare.
-    ///
-    /// This method deletes the item with minimum priority relative to \c
-    /// Compare from the heap.
+    /// \brief Remove the item having minimum priority.
+    ///
+    /// This function removes the item having minimum priority.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -215 +215 @@
       _iim.set(_data[0].first, POST_HEAP);
       if (n > 0) {
-        bubble_down(0, _data[n], n);
+        bubbleDown(0, _data[n], n);
       }
       _data.pop_back();
     }
 
-    /// \brief Deletes \c i from the heap.
-    ///
-    /// This method deletes item \c i from the heap.
-    /// \param i The item to erase.
-    /// \pre The item should be in the heap.
+    /// \brief Remove the given item from the heap.
+    ///
+    /// This function removes the given item from the heap if it is
+    /// already stored.
+    /// \param i The item to delete.
+    /// \pre \e i must be in the heap.
     void erase(const Item &i) {
       int h = _iim[i];
@@ -230 +231 @@
       _iim.set(_data[h].first, POST_HEAP);
       if( h < n ) {
-        if ( bubble_up(h, _data[n]) == h) {
-          bubble_down(h, _data[n], n);
+        if ( bubbleUp(h, _data[n]) == h) {
+          bubbleDown(h, _data[n], n);
         }
       }
@@ -237 +238 @@
     }
 
-
-    /// \brief Returns the priority of \c i.
-    ///
-    /// This function returns the priority of item \c i.
-    /// \param i The item.
-    /// \pre \c i must be in the heap.
+    /// \brief The priority of the given item.
+    ///
+    /// This function returns the priority of the given item.
+    /// \param i The item.
+    /// \pre \e i must be in the heap.
     Prio operator[](const Item &i) const {
       int idx = _iim[i];
@@ -248 +248 @@
     }
 
-    /// \brief \c i gets to the heap with priority \c p independently
-    /// if \c i was already there.
-    ///
-    /// This method calls \ref push(\c i, \c p) if \c i is not stored
-    /// in the heap and sets the priority of \c i to \c p otherwise.
+    /// \brief Set the priority of an item or insert it, if it is
+    /// not stored in the heap.
+    ///
+    /// This method sets the priority of the given item if it is
+    /// already stored in the heap. Otherwise it inserts the given
+    /// item into the heap with the given priority.
     /// \param i The item.
     /// \param p The priority.
@@ -261 +262 @@
       }
       else if( _comp(p, _data[idx].second) ) {
-        bubble_up(idx, Pair(i,p));
+        bubbleUp(idx, Pair(i,p));
       }
       else {
-        bubble_down(idx, Pair(i,p), _data.size());
-      }
-    }
-
-    /// \brief Decreases the priority of \c i to \c p.
-    ///
-    /// This method decreases the priority of item \c i to \c p.
+        bubbleDown(idx, Pair(i,p), _data.size());
+      }
+    }
+
+    /// \brief Decrease the priority of an item to the given value.
+    ///
+    /// This function decreases the priority of an item to the given value.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \c i must be stored in the heap with priority at least \c
-    /// p relative to \c Compare.
+    /// \pre \e i must be stored in the heap with priority at least \e p.
     void decrease(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      bubble_up(idx, Pair(i,p));
-    }
-
-    /// \brief Increases the priority of \c i to \c p.
-    ///
-    /// This method sets the priority of item \c i to \c p.
+      bubbleUp(idx, Pair(i,p));
+    }
+
+    /// \brief Increase the priority of an item to the given value.
+    ///
+    /// This function increases the priority of an item to the given value.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \c i must be stored in the heap with priority at most \c
-    /// p relative to \c Compare.
+    /// \pre \e i must be stored in the heap with priority at most \e p.
     void increase(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      bubble_down(idx, Pair(i,p), _data.size());
-    }
-
-    /// \brief Returns if \c item is in, has already been in, or has
-    /// never been in the heap.
-    ///
-    /// This method returns PRE_HEAP if \c item has never been in the
-    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-    /// otherwise. In the latter case it is possible that \c item will
-    /// get back to the heap again.
+      bubbleDown(idx, Pair(i,p), _data.size());
+    }
+
+    /// \brief Return the state of an item.
+    ///
+    /// This method returns \c PRE_HEAP if the given item has never
+    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+    /// and \c POST_HEAP otherwise.
+    /// In the latter case it is possible that the item will get back
+    /// to the heap again.
     /// \param i The item.
     State state(const Item &i) const {
@@ -307 +306 @@
     }
 
-    /// \brief Sets the state of the \c item in the heap.
-    ///
-    /// Sets the state of the \c item in the heap. It can be used to
-    /// manually clear the heap when it is important to achive the
-    /// better time complexity.
+    /// \brief Set the state of an item in the heap.
+    ///
+    /// This function sets the state of the given item in the heap.
+    /// It can be used to manually clear the heap when it is important
+    /// to achive better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.
@@ -328 +327 @@
     }
 
-    /// \brief Replaces an item in the heap.
-    ///
-    /// The \c i item is replaced with \c j item. The \c i item should
-    /// be in the heap, while the \c j should be out of the heap. The
-    /// \c i item will out of the heap and \c j will be in the heap
-    /// with the same prioriority as prevoiusly the \c i item.
+    /// \brief Replace an item in the heap.
+    ///
+    /// This function replaces item \c i with item \c j.
+    /// Item \c i must be in the heap, while \c j must be out of the heap.
+    /// After calling this method, item \c i will be out of the
+    /// heap and \c j will be in the heap with the same prioriority
+    /// as item \c i had before.
     void replace(const Item& i, const Item& j) {
       int idx = _iim[i];

lemon/bits/array_map.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -71 +71 @@
 
   private:
-  
+
     // The MapBase of the Map which imlements the core regisitry function.
     typedef typename Notifier::ObserverBase Parent;

lemon/bits/default_map.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -158 +158 @@
   public:
     typedef DefaultMap<_Graph, _Item, _Value> Map;
-    
+
     typedef typename Parent::GraphType GraphType;
     typedef typename Parent::Value Value;

lemon/bits/edge_set_extender.h

@@ -1 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -64 +64 @@
     Node oppositeNode(const Node &n, const Arc &e) const {
       if (n == Parent::source(e))
-        return Parent::target(e);
+        return Parent::target(e);
       else if(n==Parent::target(e))
-        return Parent::source(e);
+        return Parent::source(e);
       else
-        return INVALID;
+        return INVALID;
     }
 
@@ -92 +92 @@
     // Iterable extensions
 
-    class NodeIt : public Node { 
+    class NodeIt : public Node {
       const Digraph* digraph;
     public:
@@ -101 +101 @@
 
       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
-        _graph.first(static_cast<Node&>(*this));
-      }
-
-      NodeIt(const Digraph& _graph, const Node& node) 
-        : Node(node), digraph(&_graph) {}
-
-      NodeIt& operator++() { 
-        digraph->next(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class ArcIt : public Arc { 
+        _graph.first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Digraph& _graph, const Node& node)
+        : Node(node), digraph(&_graph) {}
+
+      NodeIt& operator++() {
+        digraph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
       const Digraph* digraph;
     public:
@@ -124 +124 @@
 
       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
-        _graph.first(static_cast<Arc&>(*this));
-      }
-
-      ArcIt(const Digraph& _graph, const Arc& e) : 
-        Arc(e), digraph(&_graph) { }
-
-      ArcIt& operator++() { 
-        digraph->next(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class OutArcIt : public Arc { 
+        _graph.first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Digraph& _graph, const Arc& e) :
+        Arc(e), digraph(&_graph) { }
+
+      ArcIt& operator++() {
+        digraph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
       const Digraph* digraph;
     public:
@@ -146 +146 @@
       OutArcIt(Invalid i) : Arc(i) { }
 
-      OutArcIt(const Digraph& _graph, const Node& node) 
-        : digraph(&_graph) {
-        _graph.firstOut(*this, node);
-      }
-
-      OutArcIt(const Digraph& _graph, const Arc& arc) 
-        : Arc(arc), digraph(&_graph) {}
-
-      OutArcIt& operator++() { 
-        digraph->nextOut(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class InArcIt : public Arc { 
+      OutArcIt(const Digraph& _graph, const Node& node)
+        : digraph(&_graph) {
+        _graph.firstOut(*this, node);
+      }
+
+      OutArcIt(const Digraph& _graph, const Arc& arc)
+        : Arc(arc), digraph(&_graph) {}
+
+      OutArcIt& operator++() {
+        digraph->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
       const Digraph* digraph;
     public:
@@ -170 +170 @@
       InArcIt(Invalid i) : Arc(i) { }
 
-      InArcIt(const Digraph& _graph, const Node& node) 
-        : digraph(&_graph) {
-        _graph.firstIn(*this, node);
-      }
-
-      InArcIt(const Digraph& _graph, const Arc& arc) : 
-        Arc(arc), digraph(&_graph) {}
-
-      InArcIt& operator++() { 
-        digraph->nextIn(*this);
-        return *this; 
+      InArcIt(const Digraph& _graph, const Node& node)
+        : digraph(&_graph) {
+        _graph.firstIn(*this, node);
+      }
+
+      InArcIt(const Digraph& _graph, const Arc& arc) :
+        Arc(arc), digraph(&_graph) {}
+
+      InArcIt& operator++() {
+        digraph->nextIn(*this);
+        return *this;
       }
 
@@ -216 +216 @@
 
     // Mappable extension
-    
+
     template <typename _Value>
-    class ArcMap 
+    class ArcMap
       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 
     public:
-      explicit ArcMap(const Digraph& _g) 
-        : Parent(_g) {}
-      ArcMap(const Digraph& _g, const _Value& _v) 
-        : Parent(_g, _v) {}
+      explicit ArcMap(const Digraph& _g)
+        : Parent(_g) {}
+      ArcMap(const Digraph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
 
       ArcMap& operator=(const ArcMap& cmap) {
-        return operator=<ArcMap>(cmap);
+        return operator=<ArcMap>(cmap);
       }
 
@@ -235 +235 @@
       ArcMap& operator=(const CMap& cmap) {
         Parent::operator=(cmap);
-        return *this;
+        return *this;
       }
 
@@ -248 +248 @@
       return arc;
     }
-    
+
     void clear() {
       notifier(Arc()).clear();
@@ -313 +313 @@
     Node oppositeNode(const Node &n, const Edge &e) const {
       if( n == Parent::u(e))
-        return Parent::v(e);
+        return Parent::v(e);
       else if( n == Parent::v(e))
-        return Parent::u(e);
+        return Parent::u(e);
       else
-        return INVALID;
+        return INVALID;
     }
 
@@ -341 +341 @@
 
     using Parent::notifier;
-    
+
     ArcNotifier& notifier(Arc) const {
       return arc_notifier;
@@ -351 +351 @@
 
 
-    class NodeIt : public Node { 
+    class NodeIt : public Node {
       const Graph* graph;
     public:
@@ -360 +360 @@
 
       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
-        _graph.first(static_cast<Node&>(*this));
-      }
-
-      NodeIt(const Graph& _graph, const Node& node) 
-        : Node(node), graph(&_graph) {}
-
-      NodeIt& operator++() { 
-        graph->next(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class ArcIt : public Arc { 
+        _graph.first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node)
+        : Node(node), graph(&_graph) {}
+
+      NodeIt& operator++() {
+        graph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
       const Graph* graph;
     public:
@@ -383 +383 @@
 
       explicit ArcIt(const Graph& _graph) : graph(&_graph) {
-        _graph.first(static_cast<Arc&>(*this));
-      }
-
-      ArcIt(const Graph& _graph, const Arc& e) : 
-        Arc(e), graph(&_graph) { }
-
-      ArcIt& operator++() { 
-        graph->next(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class OutArcIt : public Arc { 
+        _graph.first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Graph& _graph, const Arc& e) :
+        Arc(e), graph(&_graph) { }
+
+      ArcIt& operator++() {
+        graph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
       const Graph* graph;
     public:
@@ -405 +405 @@
       OutArcIt(Invalid i) : Arc(i) { }
 
-      OutArcIt(const Graph& _graph, const Node& node) 
-        : graph(&_graph) {
-        _graph.firstOut(*this, node);
-      }
-
-      OutArcIt(const Graph& _graph, const Arc& arc) 
-        : Arc(arc), graph(&_graph) {}
-
-      OutArcIt& operator++() { 
-        graph->nextOut(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class InArcIt : public Arc { 
+      OutArcIt(const Graph& _graph, const Node& node)
+        : graph(&_graph) {
+        _graph.firstOut(*this, node);
+      }
+
+      OutArcIt(const Graph& _graph, const Arc& arc)
+        : Arc(arc), graph(&_graph) {}
+
+      OutArcIt& operator++() {
+        graph->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
       const Graph* graph;
     public:
@@ -429 +429 @@
       InArcIt(Invalid i) : Arc(i) { }
 
-      InArcIt(const Graph& _graph, const Node& node) 
-        : graph(&_graph) {
-        _graph.firstIn(*this, node);
-      }
-
-      InArcIt(const Graph& _graph, const Arc& arc) : 
-        Arc(arc), graph(&_graph) {}
-
-      InArcIt& operator++() { 
-        graph->nextIn(*this);
-        return *this; 
-      }
-
-    };
-
-
-    class EdgeIt : public Parent::Edge { 
+      InArcIt(const Graph& _graph, const Node& node)
+        : graph(&_graph) {
+        _graph.firstIn(*this, node);
+      }
+
+      InArcIt(const Graph& _graph, const Arc& arc) :
+        Arc(arc), graph(&_graph) {}
+
+      InArcIt& operator++() {
+        graph->nextIn(*this);
+        return *this;
+      }
+
+    };
+
+
+    class EdgeIt : public Parent::Edge {
       const Graph* graph;
     public:
@@ -454 +454 @@
 
       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
-        _graph.first(static_cast<Edge&>(*this));
-      }
-
-      EdgeIt(const Graph& _graph, const Edge& e) : 
-        Edge(e), graph(&_graph) { }
-
-      EdgeIt& operator++() { 
-        graph->next(*this);
-        return *this; 
+        _graph.first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) :
+        Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() {
+        graph->next(*this);
+        return *this;
       }
 
@@ -478 +478 @@
 
       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
-        _graph.firstInc(*this, direction, n);
+        _graph.firstInc(*this, direction, n);
       }
 
       IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
-        : graph(&_graph), Edge(ue) {
-        direction = (_graph.source(ue) == n);
+        : graph(&_graph), Edge(ue) {
+        direction = (_graph.source(ue) == n);
       }
 
       IncEdgeIt& operator++() {
-        graph->nextInc(*this, direction);
-        return *this; 
+        graph->nextInc(*this, direction);
+        return *this;
       }
     };
@@ -535 +535 @@
 
     template <typename _Value>
-    class ArcMap 
+    class ArcMap
       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 
     public:
-      explicit ArcMap(const Graph& _g) 
-        : Parent(_g) {}
-      ArcMap(const Graph& _g, const _Value& _v) 
-        : Parent(_g, _v) {}
+      explicit ArcMap(const Graph& _g)
+        : Parent(_g) {}
+      ArcMap(const Graph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
 
       ArcMap& operator=(const ArcMap& cmap) {
-        return operator=<ArcMap>(cmap);
+        return operator=<ArcMap>(cmap);
       }
 
@@ -552 +552 @@
       ArcMap& operator=(const CMap& cmap) {
         Parent::operator=(cmap);
-        return *this;
+        return *this;
       }
 
@@ -559 +559 @@
 
     template <typename _Value>
-    class EdgeMap 
+    class EdgeMap
       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 
     public:
-      explicit EdgeMap(const Graph& _g) 
-        : Parent(_g) {}
-
-      EdgeMap(const Graph& _g, const _Value& _v) 
-        : Parent(_g, _v) {}
+      explicit EdgeMap(const Graph& _g)
+        : Parent(_g) {}
+
+      EdgeMap(const Graph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
 
       EdgeMap& operator=(const EdgeMap& cmap) {
-        return operator=<EdgeMap>(cmap);
+        return operator=<EdgeMap>(cmap);
       }
 
@@ -577 +577 @@
       EdgeMap& operator=(const CMap& cmap) {
         Parent::operator=(cmap);
-        return *this;
+        return *this;
       }
 
@@ -594 +594 @@
       return edge;
     }
-    
+
     void clear() {
       notifier(Arc()).clear();
@@ -620 +620 @@
       arc_notifier.clear();
     }
-    
+
   };
 

lemon/bits/graph_adaptor_extender.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

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/path_dump.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/solver_bits.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/windows.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -99 +99 @@
       GetSystemTime(&time);
       char buf1[11], buf2[9], buf3[5];
-          if (GetDateFormat(MY_LOCALE, 0, &time,
+          if (GetDateFormat(MY_LOCALE, 0, &time,
                         ("ddd MMM dd"), buf1, 11) &&
           GetTimeFormat(MY_LOCALE, 0, &time,

lemon/bucket_heap.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -20 +20 @@
 #define LEMON_BUCKET_HEAP_H
 
-///\ingroup auxdat
+///\ingroup heaps
 ///\file
-///\brief Bucket Heap implementation.
+///\brief Bucket heap implementation.
 
 #include <vector>
@@ -54 +54 @@
   }
 
-  /// \ingroup auxdat
-  ///
-  /// \brief A Bucket Heap implementation.
-  ///
-  /// This class implements the \e bucket \e heap data structure. A \e heap
-  /// is a data structure for storing items with specified values called \e
-  /// priorities in such a way that finding the item with minimum priority is
-  /// efficient. The bucket heap is very simple implementation, it can store
-  /// only integer priorities and it stores for each priority in the
-  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
-  /// the priorities are small. It is not intended to use as dijkstra heap.
-  ///
-  /// \param IM A read and write Item int map, used internally
-  /// to handle the cross references.
-  /// \param MIN If the given parameter is false then instead of the
-  /// minimum value the maximum can be retrivied with the top() and
-  /// prio() member functions.
+  /// \ingroup heaps
+  ///
+  /// \brief Bucket heap data structure.
+  ///
+  /// This class implements the \e bucket \e heap data structure.
+  /// It practically conforms to the \ref concepts::Heap "heap concept",
+  /// but it has some limitations.
+  ///
+  /// The bucket heap is a very simple structure. It can store only
+  /// \c int priorities and it maintains a list of items for each priority
+  /// in the range <tt>[0..C)</tt>. So it should only be used when the
+  /// priorities are small. It is not intended to use as a Dijkstra heap.
+  ///
+  /// \tparam IM A read-writable item map with \c int values, used
+  /// internally to handle the cross references.
+  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+  /// The default is \e min-heap. If this parameter is set to \c false,
+  /// then the comparison is reversed, so the top(), prio() and pop()
+  /// functions deal with the item having maximum priority instead of the
+  /// minimum.
+  ///
+  /// \sa SimpleBucketHeap
   template <typename IM, bool MIN = true>
   class BucketHeap {
 
   public:
-    /// \e
-    typedef typename IM::Key Item;
-    /// \e
+
+    /// Type of the item-int map.
+    typedef IM ItemIntMap;
+    /// Type of the priorities.
     typedef int Prio;
-    /// \e
-    typedef std::pair<Item, Prio> Pair;
-    /// \e
-    typedef IM ItemIntMap;
+    /// Type of the items stored in the heap.
+    typedef typename ItemIntMap::Key Item;
+    /// Type of the item-priority pairs.
+    typedef std::pair<Item,Prio> Pair;
 
   private:
@@ -90 +96 @@
   public:
 
-    /// \brief Type to represent the items states.
-    ///
-    /// Each Item element have a state associated to it. It may be "in heap",
-    /// "pre heap" or "post heap". The latter two are indifferent from the
+    /// \brief Type to represent the states of the items.
+    ///
+    /// Each item has a state associated to it. It can be "in heap",
+    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -105 +111 @@
 
   public:
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param map should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
+
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    /// \param map A map that assigns \c int values to the items.
+    /// It is used internally to handle the cross references.
+    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 
-    /// The number of items stored in the heap.
-    ///
-    /// \brief Returns the number of items stored in the heap.
+    /// \brief The number of items stored in the heap.
+    ///
+    /// This function returns the number of items stored in the heap.
     int size() const { return _data.size(); }
 
-    /// \brief Checks if the heap stores no items.
-    ///
-    /// Returns \c true if and only if the heap stores no items.
+    /// \brief Check if the heap is empty.
+    ///
+    /// This function returns \c true if the heap is empty.
     bool empty() const { return _data.empty(); }
 
-    /// \brief Make empty this heap.
-    ///
-    /// Make empty this heap. It does not change the cross reference
-    /// map.  If you want to reuse a heap what is not surely empty you
-    /// should first clear the heap and after that you should set the
-    /// cross reference map for each item to \c PRE_HEAP.
+    /// \brief Make the heap empty.
+    ///
+    /// This functon makes the heap empty.
+    /// It does not change the cross reference map. If you want to reuse
+    /// a heap that is not surely empty, you should first clear it and
+    /// then you should set the cross reference map to \c PRE_HEAP
+    /// for each item.
     void clear() {
       _data.clear(); _first.clear(); _minimum = 0;
@@ -135 +143 @@
   private:
 
-    void relocate_last(int idx) {
+    void relocateLast(int idx) {
       if (idx + 1 < int(_data.size())) {
         _data[idx] = _data.back();
@@ -175 +183 @@
 
   public:
+
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// Adds \c p.first to the heap with priority \c p.second.
+    /// This function inserts \c p.first to the heap with priority
+    /// \c p.second.
     /// \param p The pair to insert.
+    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair& p) {
       push(p.first, p.second);
@@ -185 +196 @@
     /// \brief Insert an item into the heap with the given priority.
     ///
-    /// Adds \c i to the heap with priority \c p.
+    /// This function inserts the given item into the heap with the
+    /// given priority.
     /// \param i The item to insert.
     /// \param p The priority of the item.
+    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) {
       int idx = _data.size();
@@ -198 +211 @@
     }
 
-    /// \brief Returns the item with minimum priority.
-    ///
-    /// This method returns the item with minimum priority.
-    /// \pre The heap must be nonempty.
+    /// \brief Return the item having minimum priority.
+    ///
+    /// This function returns the item having minimum priority.
+    /// \pre The heap must be non-empty.
     Item top() const {
       while (_first[_minimum] == -1) {
@@ -209 +222 @@
     }
 
-    /// \brief Returns the minimum priority.
-    ///
-    /// It returns the minimum priority.
-    /// \pre The heap must be nonempty.
+    /// \brief The minimum priority.
+    ///
+    /// This function returns the minimum priority.
+    /// \pre The heap must be non-empty.
     Prio prio() const {
       while (_first[_minimum] == -1) {
@@ -220 +233 @@
     }
 
-    /// \brief Deletes the item with minimum priority.
-    ///
-    /// This method deletes the item with minimum priority from the heap.
+    /// \brief Remove the item having minimum priority.
+    ///
+    /// This function removes the item having minimum priority.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -231 +244 @@
       _iim[_data[idx].item] = -2;
       unlace(idx);
-      relocate_last(idx);
-    }
-
-    /// \brief Deletes \c i from the heap.
-    ///
-    /// This method deletes item \c i from the heap, if \c i was
-    /// already stored in the heap.
-    /// \param i The item to erase.
+      relocateLast(idx);
+    }
+
+    /// \brief Remove the given item from the heap.
+    ///
+    /// This function removes the given item from the heap if it is
+    /// already stored.
+    /// \param i The item to delete.
+    /// \pre \e i must be in the heap.
     void erase(const Item &i) {
       int idx = _iim[i];
       _iim[_data[idx].item] = -2;
       unlace(idx);
-      relocate_last(idx);
-    }
-
-
-    /// \brief Returns the priority of \c i.
-    ///
-    /// This function returns the priority of item \c i.
-    /// \pre \c i must be in the heap.
-    /// \param i The item.
+      relocateLast(idx);
+    }
+
+    /// \brief The priority of the given item.
+    ///
+    /// This function returns the priority of the given item.
+    /// \param i The item.
+    /// \pre \e i must be in the heap.
     Prio operator[](const Item &i) const {
       int idx = _iim[i];
@@ -257 +270 @@
     }
 
-    /// \brief \c i gets to the heap with priority \c p independently
-    /// if \c i was already there.
-    ///
-    /// This method calls \ref push(\c i, \c p) if \c i is not stored
-    /// in the heap and sets the priority of \c i to \c p otherwise.
+    /// \brief Set the priority of an item or insert it, if it is
+    /// not stored in the heap.
+    ///
+    /// This method sets the priority of the given item if it is
+    /// already stored in the heap. Otherwise it inserts the given
+    /// item into the heap with the given priority.
     /// \param i The item.
     /// \param p The priority.
@@ -275 +289 @@
     }
 
-    /// \brief Decreases the priority of \c i to \c p.
-    ///
-    /// This method decreases the priority of item \c i to \c p.
-    /// \pre \c i must be stored in the heap with priority at least \c
-    /// p relative to \c Compare.
+    /// \brief Decrease the priority of an item to the given value.
+    ///
+    /// This function decreases the priority of an item to the given value.
     /// \param i The item.
     /// \param p The priority.
+    /// \pre \e i must be stored in the heap with priority at least \e p.
     void decrease(const Item &i, const Prio &p) {
       int idx = _iim[i];
@@ -292 +305 @@
     }
 
-    /// \brief Increases the priority of \c i to \c p.
-    ///
-    /// This method sets the priority of item \c i to \c p.
-    /// \pre \c i must be stored in the heap with priority at most \c
-    /// p relative to \c Compare.
+    /// \brief Increase the priority of an item to the given value.
+    ///
+    /// This function increases the priority of an item to the given value.
     /// \param i The item.
     /// \param p The priority.
+    /// \pre \e i must be stored in the heap with priority at most \e p.
     void increase(const Item &i, const Prio &p) {
       int idx = _iim[i];
@@ -306 +318 @@
     }
 
-    /// \brief Returns if \c item is in, has already been in, or has
-    /// never been in the heap.
-    ///
-    /// This method returns PRE_HEAP if \c item has never been in the
-    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-    /// otherwise. In the latter case it is possible that \c item will
-    /// get back to the heap again.
+    /// \brief Return the state of an item.
+    ///
+    /// This method returns \c PRE_HEAP if the given item has never
+    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+    /// and \c POST_HEAP otherwise.
+    /// In the latter case it is possible that the item will get back
+    /// to the heap again.
     /// \param i The item.
     State state(const Item &i) const {
@@ -320 +332 @@
     }
 
-    /// \brief Sets the state of the \c item in the heap.
-    ///
-    /// Sets the state of the \c item in the heap. It can be used to
-    /// manually clear the heap when it is important to achive the
-    /// better time complexity.
+    /// \brief Set the state of an item in the heap.
+    ///
+    /// This function sets the state of the given item in the heap.
+    /// It can be used to manually clear the heap when it is important
+    /// to achive better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.
@@ -360 +372 @@
   }; // class BucketHeap
 
-  /// \ingroup auxdat
-  ///
-  /// \brief A Simplified Bucket Heap implementation.
+  /// \ingroup heaps
+  ///
+  /// \brief Simplified bucket heap data structure.
   ///
   /// This class implements a simplified \e bucket \e heap data
-  /// structure.  It does not provide some functionality but it faster
-  /// and simplier data structure than the BucketHeap. The main
-  /// difference is that the BucketHeap stores for every key a double
-  /// linked list while this class stores just simple lists. In the
-  /// other way it does not support erasing each elements just the
-  /// minimal and it does not supports key increasing, decreasing.
-  ///
-  /// \param IM A read and write Item int map, used internally
-  /// to handle the cross references.
-  /// \param MIN If the given parameter is false then instead of the
-  /// minimum value the maximum can be retrivied with the top() and
-  /// prio() member functions.
+  /// structure. It does not provide some functionality, but it is
+  /// faster and simpler than BucketHeap. The main difference is
+  /// that BucketHeap stores a doubly-linked list for each key while
+  /// this class stores only simply-linked lists. It supports erasing
+  /// only for the item having minimum priority and it does not support
+  /// key increasing and decreasing.
+  ///
+  /// Note that this implementation does not conform to the
+  /// \ref concepts::Heap "heap concept" due to the lack of some
+  /// functionality.
+  ///
+  /// \tparam IM A read-writable item map with \c int values, used
+  /// internally to handle the cross references.
+  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+  /// The default is \e min-heap. If this parameter is set to \c false,
+  /// then the comparison is reversed, so the top(), prio() and pop()
+  /// functions deal with the item having maximum priority instead of the
+  /// minimum.
   ///
   /// \sa BucketHeap
@@ -383 +401 @@
 
   public:
-    typedef typename IM::Key Item;
+
+    /// Type of the item-int map.
+    typedef IM ItemIntMap;
+    /// Type of the priorities.
     typedef int Prio;
-    typedef std::pair<Item, Prio> Pair;
-    typedef IM ItemIntMap;
+    /// Type of the items stored in the heap.
+    typedef typename ItemIntMap::Key Item;
+    /// Type of the item-priority pairs.
+    typedef std::pair<Item,Prio> Pair;
 
   private:
@@ -394 +417 @@
   public:
 
-    /// \brief Type to represent the items states.
-    ///
-    /// Each Item element have a state associated to it. It may be "in heap",
-    /// "pre heap" or "post heap". The latter two are indifferent from the
+    /// \brief Type to represent the states of the items.
+    ///
+    /// Each item has a state associated to it. It can be "in heap",
+    /// "pre-heap" or "post-heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -410 +433 @@
   public:
 
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param map should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    /// \param map A map that assigns \c int values to the items.
+    /// It is used internally to handle the cross references.
+    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     explicit SimpleBucketHeap(ItemIntMap &map)
       : _iim(map), _free(-1), _num(0), _minimum(0) {}
 
-    /// \brief Returns the number of items stored in the heap.
-    ///
-    /// The number of items stored in the heap.
+    /// \brief The number of items stored in the heap.
+    ///
+    /// This function returns the number of items stored in the heap.
     int size() const { return _num; }
 
-    /// \brief Checks if the heap stores no items.
-    ///
-    /// Returns \c true if and only if the heap stores no items.
+    /// \brief Check if the heap is empty.
+    ///
+    /// This function returns \c true if the heap is empty.
     bool empty() const { return _num == 0; }
 
-    /// \brief Make empty this heap.
-    ///
-    /// Make empty this heap. It does not change the cross reference
-    /// map.  If you want to reuse a heap what is not surely empty you
-    /// should first clear the heap and after that you should set the
-    /// cross reference map for each item to \c PRE_HEAP.
+    /// \brief Make the heap empty.
+    ///
+    /// This functon makes the heap empty.
+    /// It does not change the cross reference map. If you want to reuse
+    /// a heap that is not surely empty, you should first clear it and
+    /// then you should set the cross reference map to \c PRE_HEAP
+    /// for each item.
     void clear() {
       _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
@@ -441 +465 @@
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// Adds \c p.first to the heap with priority \c p.second.
+    /// This function inserts \c p.first to the heap with priority
+    /// \c p.second.
     /// \param p The pair to insert.
+    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair& p) {
       push(p.first, p.second);
@@ -449 +475 @@
     /// \brief Insert an item into the heap with the given priority.
     ///
-    /// Adds \c i to the heap with priority \c p.
+    /// This function inserts the given item into the heap with the
+    /// given priority.
     /// \param i The item to insert.
     /// \param p The priority of the item.
+    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) {
       int idx;
@@ -472 +500 @@
     }
 
-    /// \brief Returns the item with minimum priority.
-    ///
-    /// This method returns the item with minimum priority.
-    /// \pre The heap must be nonempty.
+    /// \brief Return the item having minimum priority.
+    ///
+    /// This function returns the item having minimum priority.
+    /// \pre The heap must be non-empty.
     Item top() const {
       while (_first[_minimum] == -1) {
@@ -483 +511 @@
     }
 
-    /// \brief Returns the minimum priority.
-    ///
-    /// It returns the minimum priority.
-    /// \pre The heap must be nonempty.
+    /// \brief The minimum priority.
+    ///
+    /// This function returns the minimum priority.
+    /// \pre The heap must be non-empty.
     Prio prio() const {
       while (_first[_minimum] == -1) {
@@ -494 +522 @@
     }
 
-    /// \brief Deletes the item with minimum priority.
-    ///
-    /// This method deletes the item with minimum priority from the heap.
+    /// \brief Remove the item having minimum priority.
+    ///
+    /// This function removes the item having minimum priority.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -510 +538 @@
     }
 
-    /// \brief Returns the priority of \c i.
-    ///
-    /// This function returns the priority of item \c i.
-    /// \warning This operator is not a constant time function
-    /// because it scans the whole data structure to find the proper
-    /// value.
-    /// \pre \c i must be in the heap.
-    /// \param i The item.
+    /// \brief The priority of the given item.
+    ///
+    /// This function returns the priority of the given item.
+    /// \param i The item.
+    /// \pre \e i must be in the heap.
+    /// \warning This operator is not a constant time function because
+    /// it scans the whole data structure to find the proper value.
     Prio operator[](const Item &i) const {
-      for (int k = 0; k < _first.size(); ++k) {
+      for (int k = 0; k < int(_first.size()); ++k) {
         int idx = _first[k];
         while (idx != -1) {
@@ -531 +558 @@
     }
 
-    /// \brief Returns if \c item is in, has already been in, or has
-    /// never been in the heap.
-    ///
-    /// This method returns PRE_HEAP if \c item has never been in the
-    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-    /// otherwise. In the latter case it is possible that \c item will
-    /// get back to the heap again.
+    /// \brief Return the state of an item.
+    ///
+    /// This method returns \c PRE_HEAP if the given item has never
+    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+    /// and \c POST_HEAP otherwise.
+    /// In the latter case it is possible that the item will get back
+    /// to the heap again.
     /// \param i The item.
     State state(const Item &i) const {

lemon/cbc.cc

@@ -90 +90 @@
   }
 
+  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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -63 +63 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
@@ -121 +122 @@
     int _message_level;
 
-    
+
 
   };

lemon/circulation.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -60 +60 @@
     /// \brief The type of supply map.
     ///
-    /// The type of the map that stores the signed supply values of the 
-    /// nodes. 
+    /// The type of the map that stores the signed supply values of the
+    /// nodes.
     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     typedef SM SupplyMap;
@@ -73 +73 @@
     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
     /// concept.
+#ifdef DOXYGEN
+    typedef GR::ArcMap<Value> FlowMap;
+#else
     typedef typename Digraph::template ArcMap<Value> FlowMap;
+#endif
 
     /// \brief Instantiates a FlowMap.
@@ -88 +92 @@
     /// The elevator type used by the algorithm.
     ///
-    /// \sa Elevator
-    /// \sa LinkedElevator
+    /// \sa Elevator, LinkedElevator
+#ifdef DOXYGEN
+    typedef lemon::Elevator<GR, GR::Node> Elevator;
+#else
     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
+#endif
 
     /// \brief Instantiates an Elevator.
@@ -135 +142 @@
      \geq sup(u) \quad \forall u\in V, \f]
      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
-     
+
      The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
      zero or negative in order to have a feasible solution (since the sum
@@ -145 +152 @@
      constraints have to be satisfied with equality, i.e. all demands
      have to be satisfied and all supplies have to be used.
-     
+
      If you need the opposite inequalities in the supply/demand constraints
      (i.e. the total demand is less than the total supply and all the demands
@@ -167 +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
@@ -300 +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().
@@ -326 +338 @@
     /// \param graph The digraph the algorithm runs on.
     /// \param lower The lower bounds for the flow values on the arcs.
-    /// \param upper The upper bounds (capacities) for the flow values 
+    /// \param upper The upper bounds (capacities) for the flow values
     /// on the arcs.
     /// \param supply The signed supply values of the nodes.
@@ -451 +463 @@
     }
 
-    /// \brief Sets the tolerance used by algorithm.
-    ///
-    /// Sets the tolerance used by algorithm.
+    /// \brief Sets the tolerance used by the algorithm.
+    ///
+    /// Sets the tolerance object used by the algorithm.
+    /// \return <tt>(*this)</tt>
     Circulation& tolerance(const Tolerance& tolerance) {
       _tol = tolerance;
@@ -461 +474 @@
     /// \brief Returns a const reference to the tolerance.
     ///
-    /// Returns a const reference to the tolerance.
+    /// Returns a const reference to the tolerance object used by
+    /// the algorithm.
     const Tolerance& tolerance() const {
       return _tol;
@@ -468 +482 @@
     /// \name Execution Control
     /// The simplest way to execute the algorithm is to call \ref run().\n
-    /// If you need more control on the initial solution or the execution,
-    /// first you have to call one of the \ref init() functions, then
+    /// If you need better control on the initial solution or the execution,
+    /// you have to call one of the \ref init() functions first, then
     /// the \ref start() function.
 

lemon/clp.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -76 +76 @@
   int ClpLp::_addRow() {
     _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
+    return _prob->numberRows() - 1;
+  }
+
+  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;
   }

lemon/clp.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -76 +76 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
@@ -138 +139 @@
 
     virtual void _messageLevel(MessageLevel);
-    
+
   public:
 

lemon/concepts/digraph.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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) { }
 
       private:
         ///Copy constructor
-        NodeMap(const NodeMap& nm) : 
+        NodeMap(const NodeMap& nm) :
           ReferenceMap<Node, T, T&, const T&>(nm) { }
         ///Assignment operator
@@ -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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -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; }