Diff [41bdb4d6c8c32c29a1eaebc3eef9bef7ef1f9862:c05bb175d3ee489dba6371623a73519da808b408] for / – LEMON

.hgignore

-                      r514
+                      r610
 lemon/stamp-h2
 doc/Doxyfile
 cmake/cmake.version
+cmake/version.cmake
 .dirstamp
 .libs/*
 .deps/*
 demo/*.eps
+m4/libtool.m4
+m4/ltoptions.m4
+m4/ltsugar.m4
+m4/ltversion.m4
+m4/lt~obsolete.m4
 syntax: regexp
 …
 ^autom4te.cache/.*
 ^build-aux/.*
 ^objs.*/.*
+^.*objs.*/.*
 ^test/[a-z_]*$
+^tools/[a-z-_]*$
 ^demo/.*_demo$
 ^build/.*
+^.*build.*/.*
 ^doc/gen-images/.*
 CMakeFiles

CMakeLists.txt

-                      r540
+                      r727
 CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
+IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
+  INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
+ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
+  SET(PROJECT_NAME "LEMON")
+  SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.")
+ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
+SET(PROJECT_NAME "LEMON")
 PROJECT(${PROJECT_NAME})
+SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
+IF(EXISTS ${PROJECT_SOURCE_DIR}/cmake/version.cmake)
+  INCLUDE(${PROJECT_SOURCE_DIR}/cmake/version.cmake)
+ELSEIF(DEFINED ENV{LEMON_VERSION})
+  SET(LEMON_VERSION $ENV{LEMON_VERSION} CACHE STRING "LEMON version string.")
+ELSE()
+  EXECUTE_PROCESS(
+    COMMAND hg id -i
+    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
+    OUTPUT_VARIABLE HG_REVISION
+    ERROR_QUIET
+    OUTPUT_STRIP_TRAILING_WHITESPACE
+  )
+  IF(HG_REVISION STREQUAL "")
+    SET(HG_REVISION "hg-tip")
+  ENDIF()
+  SET(LEMON_VERSION ${HG_REVISION} CACHE STRING "LEMON version string.")
+ENDIF()
+INCLUDE(FindDoxygen)
+INCLUDE(FindGhostscript)
+SET(PROJECT_VERSION ${LEMON_VERSION})
+ADD_DEFINITIONS(-DHAVE_CONFIG_H)
+SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
+FIND_PACKAGE(Doxygen)
+FIND_PACKAGE(Ghostscript)
+FIND_PACKAGE(GLPK 4.33)
+FIND_PACKAGE(CPLEX)
+FIND_PACKAGE(COIN)
 INCLUDE(CheckTypeSize)
+CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
+CHECK_TYPE_SIZE("long long" LONG_LONG)
+SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
 ENABLE_TESTING()
 ADD_SUBDIRECTORY(lemon)
+ADD_SUBDIRECTORY(demo)
+ADD_SUBDIRECTORY(doc)
+ADD_SUBDIRECTORY(test)
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+  ADD_SUBDIRECTORY(demo)
+  ADD_SUBDIRECTORY(tools)
+  ADD_SUBDIRECTORY(doc)
+  ADD_SUBDIRECTORY(test)
+ENDIF()
+IF(WIN32)
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/cmake/LEMONConfig.cmake.in
+  ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
+  @ONLY
+)
+IF(UNIX)
+  INSTALL(
+    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
+    DESTINATION share/lemon/cmake
+  )
+ELSEIF(WIN32)
+  INSTALL(
+    FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake
+    DESTINATION cmake
+  )
+ENDIF()
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR} AND WIN32)
   SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
   SET(CPACK_PACKAGE_VENDOR "EGRES")
   SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
     "LEMON - Library of Efficient Models and Optimization in Networks")
   SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+    "LEMON - Library for Efficient Modeling and Optimization in Networks")
+  SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
   SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
 …
     "${PROJECT_NAME} ${PROJECT_VERSION}")
   SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+  SET(CPACK_COMPONENTS_ALL headers library html_documentation bin)
   SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
   SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library")
+  SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
 …
   SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
     "DLL and import library")
+  SET(CPACK_COMPONENT_BIN_DESCRIPTION
+    "Command line utilities")
   SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
     "Doxygen generated documentation")
 …
   SET(CPACK_GENERATOR "NSIS")
   SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
   SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
   #SET(CPACK_PACKAGE_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
+  SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
+  SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
+  #SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
   SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
   SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
 …
   INCLUDE(CPack)
 ENDIF(WIN32)
+ENDIF()

INSTALL

-                      r526
+                      r615
       This command compiles the non-template part of LEMON into libemon.a
       file. It also compiles the programs in the tools and demo subdirectories
       when enabled.
+      file. It also compiles the programs in the tools subdirectory by
+      default.
 . `make check'
 …
   Set the installation prefix to PREFIX. By default it is /usr/local.
---enable-demo
-   Build the examples in the demo subdirectory.
---disable-demo
-   Do not build the examples in the demo subdirectory (default).
 --enable-tools
 …
    Disable SoPlex support.
+--with-coin[=PREFIX]
+   Enable support for COIN-OR solvers (CLP and CBC). You should
+   specify the prefix too. (by default, COIN-OR tools install
+   themselves to the source code directory). This command enables the
+   solvers that are actually found.
+--with-coin-includedir=DIR
+   The directory where the COIN-OR header files are located. This is
+   only useful when the COIN-OR headers and libraries are not under
+   the same prefix (which is unlikely).
+--with-coin-libdir=DIR
+   The directory where the COIN-OR libraries are located. This is only
+   useful when the COIN-OR headers and libraries are not under the
+   same prefix (which is unlikely).
+--without-coin
+   Disable COIN-OR support.

LICENSE

r530	r600
2	2	copyright/license.
3	3
4		Copyright (C) 2003-2008 Egervary Jeno Kombinatorikus Optimalizalasi
	4	Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi
5	5	Kutatocsoport (Egervary Combinatorial Optimization Research Group,
6	6	EGRES).

Makefile.am

-                      r503
+                      r676
 ACLOCAL_AMFLAGS = -I m4
+AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
 …
         m4/lx_check_glpk.m4 \
         m4/lx_check_soplex.m4 \
+        m4/lx_check_coin.m4 \
         CMakeLists.txt \
         cmake/FindGhostscript.cmake \
+        cmake/FindCPLEX.cmake \
+        cmake/FindGLPK.cmake \
+        cmake/FindCOIN.cmake \
         cmake/version.cmake.in \
         cmake/version.cmake \
 …
 include test/Makefile.am
 include doc/Makefile.am
-include demo/Makefile.am
 include tools/Makefile.am
+DIST_SUBDIRS = demo
+demo:
+        $(MAKE) $(AM_MAKEFLAGS) -C demo
 MRPROPERFILES = \
 …
         bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
 .PHONY: mrproper dist-bz2 distcheck-bz2
+.PHONY: demo mrproper dist-bz2 distcheck-bz2

NEWS

-                      r534
+                      r853
+-10-03 Version 1.1.1 released
+        Bugfix release.
+        #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: Bug fix in Preflow and Circulation
+-05-13 Version 1.1 released
+        This is the second stable release of the 1.x series. It
+        features a better coverage of the tools available in the 0.x
+        series, a thoroughly reworked LP/MIP interface plus various
+        improvements in the existing tools.
+        * Much improved M$ Windows support
+          * Various improvements in the CMAKE build system
+          * Compilation warnings are fixed/suppressed
+        * Support IBM xlC compiler
+        * New algorithms
+          * Connectivity related algorithms (#61)
+          * Euler walks (#65)
+          * Preflow push-relabel max. flow algorithm (#176)
+          * Circulation algorithm (push-relabel based) (#175)
+          * Suurballe algorithm (#47)
+          * Gomory-Hu algorithm (#66)
+          * Hao-Orlin algorithm (#58)
+          * Edmond's maximum cardinality and weighted matching algorithms
+            in general graphs (#48,#265)
+          * Minimum cost arborescence/branching (#60)
+          * Network Simplex min. cost flow algorithm (#234)
+        * New data structures
+          * Full graph structure (#57)
+          * Grid graph structure (#57)
+          * Hypercube graph structure (#57)
+          * Graph adaptors (#67)
+          * ArcSet and EdgeSet classes (#67)
+          * Elevator class (#174)
+        * Other new tools
+          * LP/MIP interface (#44)
+            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
+          * Reader for the Nauty file format (#55)
+          * DIMACS readers (#167)
+          * Radix sort algorithms (#72)
+          * RangeIdMap and CrossRefMap (#160)
+        * New command line tools
+          * DIMACS to LGF converter (#182)
+          * lgf-gen - a graph generator (#45)
+          * DIMACS solver utility (#226)
+        * Other code improvements
+          * Lognormal distribution added to Random (#102)
+          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
+          * The standard maps of graphs are guaranteed to be
+            reference maps (#190)
+        * Miscellaneous
+          * Various doc improvements
+          * Improved 0.x -> 1.x converter script
+        * Several bugfixes (compared to release 1.0):
+          #170: Bugfix SmartDigraph::split()
+          #171: Bugfix in SmartGraph::restoreSnapshot()
+          #172: Extended test cases for graphs and digraphs
+          #173: Bugfix in Random
+                * operator()s always return a double now
+                * the faulty real<Num>(Num) and real<Num>(Num,Num)
+                  have been removed
+          #187: Remove DijkstraWidestPathOperationTraits
+          #61:  Bugfix in DfsVisit
+          #193: Bugfix in GraphReader::skipSection()
+          #195: Bugfix in ConEdgeIt()
+          #197: Bugfix in heap unionfind
+                * This bug affects Edmond's general matching algorithms
+          #207: Fix 'make install' without 'make html' using CMAKE
+          #208: Suppress or fix VS2008 compilation warnings
+          ----: Update the LEMON icon
+          ----: Enable the component-based installer
+                (in installers made by CPACK)
+          ----: Set the proper version for CMAKE in the tarballs
+                (made by autotools)
+          ----: Minor clarification in the LICENSE file
+          ----: 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
+          #230: Build systems check the availability of 'long long' type
+          #229: Default implementation of Tolerance<> is used for integer types
+          #211,#212: Various fixes for compiling on AIX
+          ----: Improvements in CMAKE config
+                - docs is installed in share/doc/
+                - detects newer versions of Ghostscript
+          #239: Fix missing 'inline' specifier in time_measure.h
+          #274,#280: Install lemon/config.h
+          #275: Prefix macro names with LEMON_ in lemon/config.h
+          ----: Small script for making the release tarballs added
+          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
 -03-27 LEMON joins to the COIN-OR initiative

README

-                      r318
+                      r705
 ==================================================================
 LEMON - a Library of Efficient Models and Optimization in Networks
 ==================================================================
+=====================================================================
+LEMON - a Library for Efficient Modeling and Optimization in Networks
+=====================================================================
 LEMON is an open source library written in C++. It provides

cmake/version.cmake.in

r503	r725
1		SET(PROJECT_NAME "@PACKAGE_NAME@")
2		SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
	1	SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")

configure.ac

-                      r540
+                      r727
 dnl Version information.
 m4_define([lemon_version_number],
         [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
+          [m4_normalize(esyscmd([echo ${LEMON_VERSION}]))])
 dnl m4_define([lemon_version_number], [])
 m4_define([lemon_hg_path], [m4_normalize(esyscmd([./scripts/chg-len.py]))])
 m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i]))])
+m4_define([lemon_hg_revision], [m4_normalize(esyscmd([hg id -i 2> /dev/null]))])
 m4_define([lemon_version], [ifelse(lemon_version_number(),
+                           [],
+                           [lemon_hg_path().lemon_hg_revision()],
+                           [lemon_version_number()])])
+                           [],
+                           [ifelse(lemon_hg_revision(),
+                           [],
+                           [hg-tip],
+                           [lemon_hg_path().lemon_hg_revision()])],
+                           [lemon_version_number()])])
 AC_PREREQ([2.59])
 …
 AC_CONFIG_HEADERS([config.h lemon/config.h])
+lx_cmdline_cxxflags_set=${CXXFLAGS+set}
+AC_DEFINE([LEMON_VERSION], [lemon_version()], [The version string])
 dnl Do compilation tests using the C++ compiler.
 …
 dnl Set custom compiler flags when using g++.
 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
   CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
+if test "$GXX" = yes -a "$ICC" = no; then
+  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 fi
+AC_SUBST([WARNINGCXXFLAGS])
 dnl Checks for libraries.
+#LX_CHECK_GLPK
+#LX_CHECK_CPLEX
+#LX_CHECK_SOPLEX
+LX_CHECK_GLPK
+LX_CHECK_CPLEX
+LX_CHECK_SOPLEX
+LX_CHECK_COIN
+dnl Disable/enable building the demo programs.
+AC_ARG_ENABLE([demo],
+AS_HELP_STRING([--enable-demo], [build the demo programs])
+AS_HELP_STRING([--disable-demo], [do not build the demo programs @<:@default@:>@]),
+              [], [enable_demo=no])
+AC_MSG_CHECKING([whether to build the demo programs])
+if test x"$enable_demo" != x"no"; then
+  AC_MSG_RESULT([yes])
+else
+  AC_MSG_RESULT([no])
+fi
+AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
+AM_CONDITIONAL([HAVE_LP], [test x"$lx_lp_found" = x"yes"])
+AM_CONDITIONAL([HAVE_MIP], [test x"$lx_mip_found" = x"yes"])
 dnl Disable/enable building the binary tools.
 …
 AC_CONFIG_FILES([
 Makefile
+demo/Makefile
 cmake/version.cmake
 doc/Doxyfile
 …
 echo
 echo C++ compiler.................. : $CXX
 echo C++ compiles flags............ : $CXXFLAGS
+echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
 echo
 echo Compiler supports long long... : $long_long_found
 echo
+#echo GLPK support.................. : $lx_glpk_found
+#echo CPLEX support................. : $lx_cplex_found
+#echo SOPLEX support................ : $lx_soplex_found
+#echo
+echo Build demo programs........... : $enable_demo
+echo GLPK support.................. : $lx_glpk_found
+echo CPLEX support................. : $lx_cplex_found
+echo SOPLEX support................ : $lx_soplex_found
+echo CLP support................... : $lx_clp_found
+echo CBC support................... : $lx_cbc_found
+echo
 echo Build additional tools........ : $enable_tools
 echo

demo/CMakeLists.txt

-                      r539
+                      r726
 INCLUDE_DIRECTORIES(
   ${CMAKE_SOURCE_DIR}
+  ${PROJECT_SOURCE_DIR}
   ${PROJECT_BINARY_DIR}
+)
+LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(
+  ${PROJECT_BINARY_DIR}/lemon
+)
 SET(DEMOS
   arg_parser_demo
   graph_to_eps_demo
+  lgf_demo)
+  lgf_demo
+)
 FOREACH(DEMO_NAME ${DEMOS})
   ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
   TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
 ENDFOREACH(DEMO_NAME)
+ENDFOREACH()

demo/Makefile.am

-                      r164
+                      r611
+EXTRA_DIST += \
+        demo/CMakeLists.txt \
+        demo/digraph.lgf
+AM_CXXFLAGS = $(WARNINGCXXFLAGS)
+if WANT_DEMO
+AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
+LDADD = $(top_builddir)/lemon/libemon.la
+noinst_PROGRAMS += \
+        demo/arg_parser_demo \
+        demo/graph_to_eps_demo \
+        demo/lgf_demo
+EXTRA_DIST = \
+        CMakeLists.txt \
+        digraph.lgf
+endif WANT_DEMO
+noinst_PROGRAMS = \
+        arg_parser_demo \
+        graph_to_eps_demo \
+        lgf_demo
 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
 demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
 demo_lgf_demo_SOURCES = demo/lgf_demo.cc
+arg_parser_demo_SOURCES = arg_parser_demo.cc
+graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
+lgf_demo_SOURCES = lgf_demo.cc

demo/arg_parser_demo.cc

r311	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

demo/graph_to_eps_demo.cc

-                      r313
+                      r659
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
     coords(coords).
     title("Sample .eps figure").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     run();
 …
     coords(coords).
     title("Sample .eps figure").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     absoluteNodeSizes().absoluteArcWidths().
     nodeScale(2).nodeSizes(sizes).
 …
   graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").
     title("Sample .eps figure (with arrowheads)").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     absoluteNodeSizes().absoluteArcWidths().
     nodeColors(composeMap(palette,colors)).
 …
   graphToEps(g,"graph_to_eps_demo_out_4_par.eps").
     title("Sample .eps figure (parallel arcs)").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     absoluteNodeSizes().absoluteArcWidths().
     nodeShapes(shapes).
 …
   graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").
     title("Sample .eps figure (parallel arcs and arrowheads)").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     absoluteNodeSizes().absoluteArcWidths().
     nodeScale(2).nodeSizes(sizes).
 …
   graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").
     title("Sample .eps figure (fits to A4)").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     scaleToA4().
     absoluteNodeSizes().absoluteArcWidths().
 …
   ListDigraph::NodeMap<Point> hcoords(h);
   int cols=int(sqrt(double(palette.size())));
+  int cols=int(std::sqrt(double(palette.size())));
   for(int i=0;i<int(paletteW.size());i++) {
     Node n=h.addNode();
 …
     scale(60).
     title("Sample .eps figure (Palette demo)").
     copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     coords(hcoords).
     absoluteNodeSizes().absoluteArcWidths().

demo/lgf_demo.cc

r294	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/CMakeLists.txt

-                      r520
+                      r726
 SET(PACKAGE_NAME ${PROJECT_NAME})
 SET(PACKAGE_VERSION ${PROJECT_VERSION})
 SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
 SET(abs_top_builddir ${CMAKE_BINARY_DIR})
+SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
+SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 CONFIGURE_FILE(
+  ${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
+  ${CMAKE_BINARY_DIR}/doc/Doxyfile
+  @ONLY)
+  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
+  ${PROJECT_BINARY_DIR}/doc/Doxyfile
+  @ONLY
+)
 IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
   FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
+  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)
+  ADD_CUSTOM_TARGET(html
+    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images
+    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps
+    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/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
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+    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/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
+    COMMAND ${CMAKE_COMMAND} -E remove_directory html
+    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)
   IF(UNIX)
+    ADD_CUSTOM_TARGET(html
+      COMMAND rm -rf gen-images
+      COMMAND mkdir gen-images
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+      COMMAND rm -rf html
+      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+    INSTALL(
+      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+      DESTINATION share/doc/lemon/html
+      COMPONENT html_documentation
+    )
   ELSEIF(WIN32)
+    ADD_CUSTOM_TARGET(html
+      COMMAND if exist gen-images rmdir /s /q gen-images
+      COMMAND mkdir gen-images
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
+      COMMAND if exist html rmdir /s /q html
+      COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
+      WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+  ENDIF(UNIX)
+  INSTALL(
+    DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+    DESTINATION share/doc
+    COMPONENT html_documentation)
+ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
+    INSTALL(
+      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
+      DESTINATION doc
+      COMPONENT html_documentation
+    )
+  ENDIF()
+ENDIF()

doc/Doxyfile.in

r316	r379
67	67	ENABLED_SECTIONS =
68	68	MAX_INITIALIZER_LINES = 5
69		SHOW_USED_FILES = ~~YES~~
	69	SHOW_USED_FILES = NO
70	70	SHOW_DIRECTORIES = YES
71	71	SHOW_FILES = YES

doc/Makefile.am

-                      r317
+                      r720
         doc/mainpage.dox \
         doc/migration.dox \
+        doc/min_cost_flow.dox \
         doc/named-param.dox \
         doc/namespaces.dox \
 …
 DOC_EPS_IMAGES18 = \
+        grid_graph.eps \
         nodeshape_0.eps \
         nodeshape_1.eps \
 …
         nodeshape_4.eps
+DOC_EPS_IMAGES27 = \
+        bipartite_matching.eps \
+        bipartite_partitions.eps \
+        connected_components.eps \
+        edge_biconnected_components.eps \
+        node_biconnected_components.eps \
+        strongly_connected_components.eps
 DOC_EPS_IMAGES = \
+        $(DOC_EPS_IMAGES18)
+        $(DOC_EPS_IMAGES18) \
+        $(DOC_EPS_IMAGES27)
 DOC_PNG_IMAGES = \
 …
         if test ${gs_found} = yes; then \
           $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \
+        else \
+          echo; \
+          echo "Ghostscript not found."; \
+          echo; \
+          exit 1; \
+        fi
+$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps
+        -mkdir doc/gen-images
+        if test ${gs_found} = yes; then \
+          $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \
         else \
           echo; \
 …
 install-html-local: doc/html
         @$(NORMAL_INSTALL)
         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
+        $(mkinstalldirs) $(DESTDIR)$(htmldir)/html
         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
+          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f"; \
+          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/html/$$f; \
         done
 …
         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
+          echo " rm -f $(DESTDIR)$(htmldir)/html/$$f"; \
+          rm -f $(DESTDIR)$(htmldir)/html/$$f; \
         done

doc/coding_style.dox

r210	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/dirs.dox

-                      r318
+                      r463
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 \brief Auxiliary tools for implementation.
 This directory contains some auxiliary classes for implementing graphs,
+This directory contains some auxiliary classes for implementing graphs,
 maps and some other classes.
 As a user you typically don't have to deal with these files.

doc/groups.dox

-                      r318
+                      r844
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
  */
+namespace lemon {
 /**
 @defgroup datas Data Structures
 This group describes the several data structures implemented in LEMON.
+This group contains the several data structures implemented in LEMON.
 */
 …
 /**
 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
+@defgroup graph_adaptors Adaptor Classes for Graphs
 @ingroup graphs
+\brief Graph types between real graphs and graph adaptors.
+This group describes some graph types between real graphs and graph adaptors.
+These classes wrap graphs to give new functionality as the adaptors do it.
+On the other hand they are not light-weight structures as the adaptors.
+\brief Adaptor classes for digraphs and graphs
+This group contains several useful adaptor classes for digraphs and graphs.
+The main parts of LEMON are the different graph structures, generic
+graph algorithms, graph concepts, which couple them, and graph
+adaptors. While the previous notions are more or less clear, the
+latter one needs further explanation. Graph adaptors are graph classes
+which serve for considering graph structures in different ways.
+A short example makes this much clearer.  Suppose that we have an
+instance \c g of a directed graph type, say ListDigraph and an algorithm
+\code
+template <typename Digraph>
+int algorithm(const Digraph&);
+\endcode
+is needed to run on the reverse oriented graph.  It may be expensive
+(in time or in memory usage) to copy \c g with the reversed
+arcs.  In this case, an adaptor class is used, which (according
+to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
+The adaptor uses the original digraph structure and digraph operations when
+methods of the reversed oriented graph are called.  This means that the adaptor
+have minor memory usage, and do not perform sophisticated algorithmic
+actions.  The purpose of it is to give a tool for the cases when a
+graph have to be used in a specific alteration.  If this alteration is
+obtained by a usual construction like filtering the node or the arc set or
+considering a new orientation, then an adaptor is worthwhile to use.
+To come back to the reverse oriented graph, in this situation
+\code
+template<typename Digraph> class ReverseDigraph;
+\endcode
+template class can be used. The code looks as follows
+\code
+ListDigraph g;
+ReverseDigraph<ListDigraph> rg(g);
+int result = algorithm(rg);
+\endcode
+During running the algorithm, the original digraph \c g is untouched.
+This techniques give rise to an elegant code, and based on stable
+graph adaptors, complex algorithms can be implemented easily.
+In flow, circulation and matching problems, the residual
+graph is of particular importance. Combining an adaptor implementing
+this with shortest path algorithms or minimum mean cycle algorithms,
+a range of weighted and cardinality optimization algorithms can be
+obtained. For other examples, the interested user is referred to the
+detailed documentation of particular adaptors.
+The behavior of graph adaptors can be very different. Some of them keep
+capabilities of the original graph while in other cases this would be
+meaningless. This means that the concepts that they meet depend
+on the graph adaptor, and the wrapped graph.
+For example, if an arc of a reversed digraph is deleted, this is carried
+out by deleting the corresponding arc of the original digraph, thus the
+adaptor modifies the original digraph.
+However in case of a residual digraph, this operation has no sense.
+Let us stand one more example here to simplify your work.
+ReverseDigraph has constructor
+\code
+ReverseDigraph(Digraph& digraph);
+\endcode
+This means that in a situation, when a <tt>const %ListDigraph&</tt>
+reference to a graph is given, then it have to be instantiated with
+<tt>Digraph=const %ListDigraph</tt>.
+\code
+int algorithm1(const ListDigraph& g) {
+  ReverseDigraph<const ListDigraph> rg(g);
+  return algorithm2(rg);
+}
+\endcode
 */
 …
 \brief Map structures implemented in LEMON.
 This group describes the map structures implemented in LEMON.
+This group contains the map structures implemented in LEMON.
 LEMON provides several special purpose maps and map adaptors that e.g. combine
 …
 \brief Special graph-related maps.
+This group describes maps that are specifically designed to assign
+values to the nodes and arcs of graphs.
+This group contains maps that are specifically designed to assign
+values to the nodes and arcs/edges of graphs.
+If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
+\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 */
 …
 \brief Tools to create new maps from existing ones
 This group describes map adaptors that are used to create "implicit"
+This group contains map adaptors that are used to create "implicit"
 maps from other maps.
 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
+Most of them are \ref concepts::ReadMap "read-only maps".
 They can make arithmetic and logical operations between one or two maps
 (negation, shifting, addition, multiplication, logical 'and', 'or',
 …
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-This group describes two dimensional data storages implemented in LEMON.
-*/
-/**
 @defgroup paths Path Structures
 @ingroup datas
 \brief %Path structures implemented in LEMON.
 This group describes the path structures implemented in LEMON.
+This group contains the path structures implemented in LEMON.
 LEMON provides flexible data structures to work with paths.
 …
 \brief Auxiliary data structures implemented in LEMON.
 This group describes some data structures implemented in LEMON in
+This group contains some data structures implemented in LEMON in
 order to make it easier to implement combinatorial algorithms.
 */
 …
 /**
 @defgroup algs Algorithms
 \brief This group describes the several algorithms
+\brief This group contains the several algorithms
 implemented in LEMON.
 This group describes the several algorithms
+This group contains the several algorithms
 implemented in LEMON.
 */
 …
 \brief Common graph search algorithms.
 This group describes the common graph search algorithms like
 Breadth-First Search (BFS) and Depth-First Search (DFS).
+This group contains the common graph search algorithms, namely
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 */
 …
 \brief Algorithms for finding shortest paths.
+This group describes the algorithms for finding shortest paths in graphs.
+This group contains the algorithms for finding shortest paths in digraphs.
+ - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
+   source node when all arc lengths are non-negative.
+ - \ref Suurballe A successive shortest path algorithm for finding
+   arc-disjoint paths between two nodes having minimum total length.
 */
 …
 \brief Algorithms for finding maximum flows.
 This group describes the algorithms for finding maximum flows and
+This group contains the algorithms for finding maximum flows and
 feasible circulations.
 The maximum flow problem is to find a flow between a single source and
 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
+function and given \f$s, t \in V\f$ source and target node. The
+maximum flow is the \f$f_a\f$ solution of the next optimization problem:
+\f[ 0 \le f_a \le c_a \f]
 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
 \qquad \forall u \in V \setminus \{s,t\}\f]
 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
+LEMON contains several algorithms for solving maximum flow problems:
+- \ref lemon::EdmondsKarp "Edmonds-Karp"
+- \ref lemon::Preflow "Goldberg's Preflow algorithm"
+- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
+- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
+In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
 fastest method to compute the maximum flow. All impelementations
+provides functions to query the minimum cut, which is the dual linear
 programming problem of the maximum flow.
 */
 /**
 @defgroup min_cost_flow Minimum Cost Flow Algorithms
+The \e maximum \e flow \e problem is to find a flow of maximum value between
+a single source and a single target. Formally, there is a \f$G=(V,A)\f$
+digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
+\f$s, t \in V\f$ source and target nodes.
+A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
+following optimization problem.
+\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
+\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
+    \quad \forall u\in V\setminus\{s,t\} \f]
+\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
+\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
+Tarjan for solving this problem. 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.
+For more information, see \ref Circulation.
+*/
+/**
+@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 @ingroup algs
 \brief Algorithms for finding minimum cost flows and circulations.
+This group describes the algorithms for finding minimum cost flows and
+circulations.
+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".
+\ref NetworkSimplex is an efficient implementation of the primal Network
+Simplex algorithm for finding minimum cost flows. It also provides dual
+solution (node potentials), if an optimal flow is found.
 */
 …
 \brief Algorithms for finding minimum cut in graphs.
 This group describes the algorithms for finding minimum cut in graphs.
 The minimum cut problem is to find a non-empty and non-complete
 \f$X\f$ subset of the vertices with minimum overall capacity on
 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
+This group contains the algorithms for finding minimum cut in graphs.
+The \e minimum \e cut \e problem is to find a non-empty and non-complete
+\f$X\f$ subset of the nodes with minimum overall capacity on
+outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
+\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 cut is the \f$X\f$ solution of the next optimization problem:
 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 \sum_{uv\in A, u\in X, v\not\in X}c_{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:
+- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
+  in directed graphs
+- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
+  calculate minimum cut in undirected graphs
+- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
+  pairs minimum cut in undirected graphs
+- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
+  in directed graphs.
+- \ref GomoryHu "Gomory-Hu tree computation" for calculating
+  all-pairs minimum cut in undirected graphs.
 If you want to find minimum cut just between two distinict nodes,
 please see the \ref max_flow "Maximum Flow page".
 */
 /**
 @defgroup graph_prop Connectivity and Other Graph Properties
+see the \ref max_flow "maximum flow problem".
+*/
+/**
+@defgroup graph_properties Connectivity and Other Graph Properties
 @ingroup algs
 \brief Algorithms for discovering the graph properties
 This group describes the algorithms for discovering the graph properties
+This group contains the algorithms for discovering the graph properties
 like connectivity, bipartiteness, euler property, simplicity etc.
 …
 /**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-This group describes the algorithms for planarity checking,
-embedding and drawing.
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
-*/
-/**
 @defgroup matching Matching Algorithms
 @ingroup algs
 \brief Algorithms for finding matchings in graphs and bipartite graphs.
 This group contains algorithm objects and functions to calculate
+matchings in graphs and bipartite graphs. The general matching problem is
 finding a subset of the arcs which does not shares common endpoints.
+This group contains the algorithms for calculating matchings in graphs.
+The general matching problem is finding a subset of the edges for which
+each node has at most one incident edge.
 There are several different algorithms for calculate matchings in
+graphs.  The matching problems in bipartite graphs are generally
+easier than in general graphs. The goal of the matching optimization
+can be the finding maximum cardinality, maximum weight or minimum cost
+graphs. The goal of the matching optimization
+can be finding maximum cardinality, maximum weight or minimum cost
 matching. The search can be constrained to find perfect or
 maximum cardinality matching.
+LEMON contains the next algorithms:
+- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
+  augmenting path algorithm for calculate maximum cardinality matching in
+  bipartite graphs
+- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
+  algorithm for calculate maximum cardinality matching in bipartite graphs
+- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
+  Successive shortest path algorithm for calculate maximum weighted matching
+  and maximum weighted bipartite matching in bipartite graph
+- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
+  Successive shortest path algorithm for calculate minimum cost maximum
+  matching in bipartite graph
+- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
+  for calculate maximum cardinality matching in general graph
+- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
+  shrinking algorithm for calculate maximum weighted matching in general
+  graph
+- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
+  Edmond's blossom shrinking algorithm for calculate maximum weighted
+  perfect matching in general graph
+The matching algorithms implemented in LEMON:
+- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
+  maximum cardinality matching in general graphs.
+- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
+  maximum weighted matching in general graphs.
+- \ref MaxWeightedPerfectMatching
+  Edmond's blossom shrinking algorithm for calculating maximum weighted
+  perfect matching in general graphs.
 \image html bipartite_matching.png
 …
 @defgroup spantree Minimum Spanning Tree Algorithms
 @ingroup algs
 \brief Algorithms for finding a minimum cost spanning tree in a graph.
 This group describes the algorithms for finding a minimum cost spanning
 tree in a graph
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
 */
 …
 \brief Auxiliary algorithms implemented in LEMON.
 This group describes some algorithms implemented in LEMON
+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 describes the approximation and heuristic algorithms
+@defgroup gen_opt_group General Optimization Tools
+\brief This group contains some general optimization frameworks
 implemented in LEMON.
+*/
+/**
+@defgroup gen_opt_group General Optimization Tools
+\brief This group describes some general optimization frameworks
+implemented in LEMON.
+This group describes some general optimization frameworks
+This group contains some general optimization frameworks
 implemented in LEMON.
 */
 …
 \brief Lp and Mip solver interfaces for LEMON.
 This group describes Lp and Mip solver interfaces for LEMON. The
+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 describes some metaheuristic optimization tools.
 */
 …
 \brief Simple basic graph utilities.
 This group describes some simple basic graph utilities.
+This group contains some simple basic graph utilities.
 */
 …
 \brief Tools for development, debugging and testing.
 This group describes several useful tools for development,
+This group contains several useful tools for development,
 debugging and testing.
 */
 …
 \brief Simple tools for measuring the performance of algorithms.
 This group describes simple tools for measuring the performance
+This group contains simple tools for measuring the performance
 of algorithms.
 */
 …
 \brief Exceptions defined in LEMON.
 This group describes the exceptions defined in LEMON.
+This group contains the exceptions defined in LEMON.
 */
 …
 \brief Graph Input-Output methods
 This group describes the tools for importing and exporting graphs
+This group contains the tools for importing and exporting graphs
 and graph related data. Now it supports the \ref lgf-format
 "LEMON Graph Format", the \c DIMACS format and the encapsulated
 …
 /**
 @defgroup lemon_io LEMON Input-Output
+@defgroup lemon_io LEMON Graph Format
 @ingroup io_group
 \brief Reading and writing LEMON Graph Format.
 This group describes methods for reading and writing
+This group contains methods for reading and writing
 \ref lgf-format "LEMON Graph Format".
 */
 …
 \brief General \c EPS drawer and graph exporter
 This group describes general \c EPS drawing methods and special
+This group contains general \c EPS drawing methods and special
 graph exporting tools.
+*/
+/**
+@defgroup dimacs_group DIMACS format
+@ingroup io_group
+\brief Read and write files in DIMACS format
+Tools to read a digraph from or write it to a file in DIMACS format data.
+*/
+/**
+@defgroup nauty_group NAUTY Format
+@ingroup io_group
+\brief Read \e Nauty format
+Tool to read graphs from \e Nauty format data.
 */
 …
 \brief Skeleton classes and concept checking classes
 This group describes the data/algorithm skeletons and concept checking
+This group contains the data/algorithm skeletons and concept checking
 classes implemented in LEMON.
 …
 \brief Skeleton and concept checking classes for graph structures
 This group describes the skeletons and concept checking classes of LEMON's
+This group contains the skeletons and concept checking classes of LEMON's
 graph structures and helper classes used to implement these.
 */
 …
 \brief Skeleton and concept checking classes for maps
 This group describes the skeletons and concept checking classes of maps.
+This group contains the skeletons and concept checking classes of maps.
 */
 …
 \anchor demoprograms
 @defgroup demos Demo programs
+@defgroup demos Demo Programs
 Some demo programs are listed here. Their full source codes can be found in
 the \c demo subdirectory of the source tree.
 It order to compile them, use <tt>--enable-demo</tt> configure option when
 build the library.
 */
 /**
 @defgroup tools Standalone utility applications
+In order to compile them, use the <tt>make demo</tt> or the
+<tt>make check</tt> commands.
+*/
+/**
+@defgroup tools Standalone Utility Applications
 Some utility applications are listed here.
 …
 */
+}

doc/lgf.dox

r313	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/license.dox

r209	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/mainpage.dox

-                      r314
+                      r705
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 \subsection whatis What is LEMON
+LEMON stands for
+<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
+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
 …
 \subsection howtoread How to read the documentation
+If you want to get a quick start and see the most important features then
+take a look at our \ref quicktour
+"Quick Tour to LEMON" which will guide you along.
+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 already feel like using our library, see the page that tells you
+\ref getstart "How to start using LEMON".
+If you
+want to see how LEMON works, see
+some \ref demoprograms "demo programs".
+If you know what you are looking for then try to find it under the
+<a class="el" href="modules.html">Modules</a>
+section.
+If you know what you are looking for, then try to find it under the
+<a class="el" href="modules.html">Modules</a> section.
 If you are a user of the old (0.x) series of LEMON, please check out the

doc/migration.dox

-                      r314
+                      r463
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 Many of these changes adjusted automatically by the
 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
+<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
 update are typeset <b>boldface</b>.
 …
 \warning
+<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
+the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
+in strings, comments etc. as well as in all identifiers.</b>
+<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
+\c ugraph, \c edge and \c uedge in your own identifiers and in
+strings, comments etc. as well as in all LEMON specific identifiers.
+So use the script carefully and make a backup copy of your source files
+before applying the script to them.</b>
 \section migration-lgf LGF tools

doc/named-param.dox

r269	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/namespaces.dox

r209	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

doc/template.h

r209	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/CMakeLists.txt

-                      r539
+                      r726
 INCLUDE_DIRECTORIES(
   ${CMAKE_SOURCE_DIR}
+  ${PROJECT_SOURCE_DIR}
   ${PROJECT_BINARY_DIR}
+)
 …
+)
+ADD_LIBRARY(lemon
+SET(LEMON_SOURCES
   arg_parser.cc
   base.cc
   color.cc
+  lp_base.cc
+  lp_skeleton.cc
   random.cc
   bits/windows.cc
+)
+IF(LEMON_HAVE_GLPK)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
+  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
+  IF(WIN32)
+    INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
+    INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
+    INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
+  ENDIF()
+ENDIF()
+IF(LEMON_HAVE_CPLEX)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
+  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
+ENDIF()
+IF(LEMON_HAVE_CLP)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
+  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
+ENDIF()
+IF(LEMON_HAVE_CBC)
+  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
+  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
+ENDIF()
+ADD_LIBRARY(lemon ${LEMON_SOURCES})
+IF(UNIX)
+  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
+ENDIF()
 INSTALL(
   TARGETS lemon
   ARCHIVE DESTINATION lib
+  COMPONENT library)
+  COMPONENT library
+)
 INSTALL(
 …
   DESTINATION include/lemon
   COMPONENT headers
+  FILES_MATCHING PATTERN "*.h")
+  FILES_MATCHING PATTERN "*.h"
+)
 INSTALL(
   FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
   DESTINATION include/lemon
+  COMPONENT headers)
+  COMPONENT headers
+)

lemon/Makefile.am

-                      r543
+                      r850
 EXTRA_DIST += \
         lemon/lemon.pc.in \
+        lemon/CMakeLists.txt
+        lemon/CMakeLists.txt \
+        lemon/config.h.cmake
 pkgconfig_DATA += lemon/lemon.pc
 …
 lemon_libemon_la_SOURCES = \
+        lemon/arg_parser.cc \
+        lemon/base.cc \
+        lemon/color.cc \
+        lemon/random.cc \
+        lemon/arg_parser.cc \
+        lemon/base.cc \
+        lemon/color.cc \
+        lemon/lp_base.cc \
+        lemon/lp_skeleton.cc \
+        lemon/random.cc \
         lemon/bits/windows.cc
+#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
+#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
+nodist_lemon_HEADERS = lemon/config.h
+nodist_lemon_HEADERS = lemon/config.h
+lemon_libemon_la_CXXFLAGS = \
+        $(AM_CXXFLAGS) \
+        $(GLPK_CFLAGS) \
+        $(CPLEX_CFLAGS) \
+        $(SOPLEX_CXXFLAGS) \
+        $(CLP_CXXFLAGS) \
+        $(CBC_CXXFLAGS)
+lemon_libemon_la_LDFLAGS = \
+        $(GLPK_LIBS) \
+        $(CPLEX_LIBS) \
+        $(SOPLEX_LIBS) \
+        $(CLP_LIBS) \
+        $(CBC_LIBS)
+if HAVE_GLPK
+lemon_libemon_la_SOURCES += lemon/glpk.cc
+endif
+if HAVE_CPLEX
+lemon_libemon_la_SOURCES += lemon/cplex.cc
+endif
+if HAVE_SOPLEX
+lemon_libemon_la_SOURCES += lemon/soplex.cc
+endif
+if HAVE_CLP
+lemon_libemon_la_SOURCES += lemon/clp.cc
+endif
+if HAVE_CBC
+lemon_libemon_la_SOURCES += lemon/cbc.cc
+endif
 lemon_HEADERS += \
+        lemon/arg_parser.h \
+        lemon/adaptors.h \
+        lemon/arg_parser.h \
         lemon/assert.h \
+        lemon/bfs.h \
+        lemon/bin_heap.h \
+        lemon/color.h \
+        lemon/bfs.h \
+        lemon/bin_heap.h \
+        lemon/cbc.h \
+        lemon/circulation.h \
+        lemon/clp.h \
+        lemon/color.h \
         lemon/concept_check.h \
+        lemon/counter.h \
+        lemon/connectivity.h \
+        lemon/counter.h \
         lemon/core.h \
+        lemon/dfs.h \
+        lemon/dijkstra.h \
+        lemon/dim2.h \
+        lemon/cplex.h \
+        lemon/dfs.h \
+        lemon/dijkstra.h \
+        lemon/dim2.h \
+        lemon/dimacs.h \
+        lemon/edge_set.h \
+        lemon/elevator.h \
         lemon/error.h \
+        lemon/graph_to_eps.h \
+        lemon/euler.h \
+        lemon/full_graph.h \
+        lemon/glpk.h \
+        lemon/gomory_hu.h \
+        lemon/graph_to_eps.h \
+        lemon/grid_graph.h \
+        lemon/hypercube_graph.h \
         lemon/kruskal.h \
+        lemon/hao_orlin.h \
         lemon/lgf_reader.h \
         lemon/lgf_writer.h \
         lemon/list_graph.h \
+        lemon/lp.h \
+        lemon/lp_base.h \
+        lemon/lp_skeleton.h \
         lemon/maps.h \
+        lemon/matching.h \
         lemon/math.h \
+        lemon/min_cost_arborescence.h \
+        lemon/nauty_reader.h \
+        lemon/network_simplex.h \
         lemon/path.h \
+        lemon/random.h \
+        lemon/preflow.h \
+        lemon/radix_sort.h \
+        lemon/random.h \
         lemon/smart_graph.h \
+        lemon/time_measure.h \
+        lemon/tolerance.h \
+        lemon/soplex.h \
+        lemon/suurballe.h \
+        lemon/time_measure.h \
+        lemon/tolerance.h \
         lemon/unionfind.h \
         lemon/bits/windows.h
 …
         lemon/bits/alteration_notifier.h \
         lemon/bits/array_map.h \
+        lemon/bits/base_extender.h \
+        lemon/bits/bezier.h \
+        lemon/bits/bezier.h \
         lemon/bits/default_map.h \
+        lemon/bits/enable_if.h \
+        lemon/bits/edge_set_extender.h \
+        lemon/bits/enable_if.h \
+        lemon/bits/graph_adaptor_extender.h \
         lemon/bits/graph_extender.h \
         lemon/bits/map_extender.h \
         lemon/bits/path_dump.h \
+        lemon/bits/solver_bits.h \
         lemon/bits/traits.h \
+        lemon/bits/variant.h \
         lemon/bits/vector_map.h

lemon/arg_parser.cc

r311	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/arg_parser.h

r311	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/assert.h

r290	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/base.cc

-                      r220
+                      r554
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 namespace lemon {
   float Tolerance<float>::def_epsilon = 1e-4;
+  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
   double Tolerance<double>::def_epsilon = 1e-10;
   long double Tolerance<long double>::def_epsilon = 1e-14;

lemon/bfs.h

-                      r301
+                      r525
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a PredMap.
     ///This function instantiates a PredMap.
+    ///Instantiates a \c PredMap.
+    ///This function instantiates a \ref PredMap.
     ///\param g is the digraph, to which we would like to define the
     ///PredMap.
+    ///\ref PredMap.
     static PredMap *createPredMap(const Digraph &g)
+    {
 …
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
     ///This function instantiates a ProcessedMap.
+    ///Instantiates a \c ProcessedMap.
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the ProcessedMap
+    ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const Digraph &g)
 …
     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a ReachedMap.
     ///This function instantiates a ReachedMap.
+    ///Instantiates a \c ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
     ///\param g is the digraph, to which
     ///we would like to define the ReachedMap.
+    ///we would like to define the \ref ReachedMap.
     static ReachedMap *createReachedMap(const Digraph &g)
+    {
 …
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
     ///This function instantiates a DistMap.
+    ///Instantiates a \c DistMap.
+    ///This function instantiates a \ref DistMap.
     ///\param g is the digraph, to which we would like to define the
     ///DistMap.
+    ///\ref DistMap.
     static DistMap *createDistMap(const Digraph &g)
+    {
 …
   ///
   ///\tparam GR The type of the digraph the algorithm runs on.
+  ///The default value is \ref ListDigraph. The value of GR is not used
+  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
+  ///\tparam TR Traits class to set various data types used by the algorithm.
+  ///The default traits class is
+  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
+  ///See \ref BfsDefaultTraits for the documentation of
+  ///a Bfs traits class.
+  ///The default type is \ref ListDigraph.
 #ifdef DOXYGEN
   template <typename GR,
 …
     typedef PredMapPath<Digraph, PredMap> Path;
     ///The traits class.
+    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     typedef TR Traits;
 …
     typedef Bfs Create;
     ///\name Named template parameters
+    ///\name Named Template Parameters
     ///@{
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///PredMap type.
+    ///\c PredMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
+    ///PredMap type.
+    ///\c PredMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///DistMap type.
+    ///\c DistMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
+    ///DistMap type.
+    ///\c DistMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ReachedMap type.
+    ///\c ReachedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
+    ///ReachedMap type.
+    ///\c ReachedMap type.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type.
+    ///\c ProcessedMap type.
     ///
     ///\ref named-templ-param "Named parameter" for setting
+    ///ProcessedMap type.
+    ///\c ProcessedMap type.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///
     ///\ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     struct SetStandardProcessedMap :
 …
     ///Sets the map that stores the predecessor arcs.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &predMap(PredMap &m)
 …
     ///Sets the map that indicates which nodes are reached.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &reachedMap(ReachedMap &m)
 …
     ///Sets the map that indicates which nodes are processed.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &processedMap(ProcessedMap &m)
 …
     ///Sets the map that stores the distances of the nodes calculated by
     ///the algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///If you don't use this function before calling \ref run(Node) "run()"
+    ///or \ref init(), an instance will be allocated automatically.
+    ///The destructor deallocates this automatically allocated map,
+    ///of course.
     ///\return <tt> (*this) </tt>
     Bfs &distMap(DistMap &m)
 …
   public:
+    ///\name Execution control
+    ///The simplest way to execute the algorithm is to use
+    ///one of the member functions called \ref lemon::Bfs::run() "run()".
+    ///\n
+    ///If you need more control on the execution, first you must call
+    ///\ref lemon::Bfs::init() "init()", then you can add several source
+    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
+    ///Finally \ref lemon::Bfs::start() "start()" will perform the
+    ///actual path computation.
+    ///\name Execution Control
+    ///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
+    ///\ref addSource(). Finally the actual path computation can be
+    ///performed with one of the \ref start() functions.
     ///@{
+    ///\brief Initializes the internal data structures.
+    ///
     ///Initializes the internal data structures.
-    ///Initializes the internal data structures.
-    ///
     void init()
+    {
 …
+    }
+    ///\brief Returns \c false if there are nodes
+    ///to be processed.
+    ///
+    ///Returns \c false if there are nodes
+    ///to be processed in the queue.
+    ///Returns \c false if there are nodes to be processed.
+    ///Returns \c false if there are nodes to be processed
+    ///in the queue.
     bool emptyQueue() const { return _queue_tail==_queue_head; }
     ///Returns the number of the nodes to be processed.
+    ///Returns the number of the nodes to be processed in the queue.
+    ///Returns the number of the nodes to be processed
+    ///in the queue.
     int queueSize() const { return _queue_head-_queue_tail; }
 …
     ///\name Query Functions
     ///The result of the %BFS algorithm can be obtained using these
+    ///The results of the BFS algorithm can be obtained using these
     ///functions.\n
     ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
     ///"start()" must be called before using them.
+    ///Either \ref run(Node) "run()" or \ref start() should be called
+    ///before using them.
     ///@{
 …
     ///Returns the shortest path to a node.
     ///
     ///\warning \c t should be reachable from the root(s).
     ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
+    ///\warning \c t should be reached from the root(s).
+    ///
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Path path(Node t) const { return Path(*G, *_pred, t); }
 …
     ///Returns the distance of a node from the root(s).
     ///
     ///\warning If node \c v is not reachable from the root(s), then
+    ///\warning If node \c v is not reached from the root(s), then
     ///the return value of this function is undefined.
     ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     int dist(Node v) const { return (*_dist)[v]; }
 …
     ///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
     ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
     ///is not reachable from the root(s) or if \c v is a root.
+    ///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 predNode().
     ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Arc predArc(Node v) const { return (*_pred)[v];}
 …
     ///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 the root(s) to \c v. It is \c INVALID
     ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///from 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().
     ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
+    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///must be called before using this function.
     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
                                   G->source((*_pred)[v]); }
 …
     ///of the nodes calculated by the algorithm.
     ///
     ///\pre Either \ref run() or \ref init()
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
 …
     ///arcs, which form the shortest path tree.
     ///
     ///\pre Either \ref run() or \ref init()
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
+    ///Checks if a node is reachable from the root(s).
+    ///Returns \c true if \c v is reachable from the root(s).
+    ///\pre Either \ref run() or \ref start()
+    ///Checks if a node is reached from the root(s).
+    ///Returns \c true if \c v is reached from the root(s).
+    ///
+    ///\pre Either \ref run(Node) "run()" or \ref init()
     ///must be called before using this function.
     bool reached(Node v) const { return (*_reached)[v]; }
 …
   /// This auxiliary class is created to implement the
   /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   /// It does not have own \ref run() method, it uses the functions
   /// and features of the plain \ref Bfs.
+  /// It does not have own \ref run(Node) "run()" method, it uses the
+  /// functions and features of the plain \ref Bfs.
   ///
   /// This class should only be used through the \ref bfs() function,
 …
   ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
   ///\endcode
   ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
   ///to the end of the parameter list.
   ///\sa BfsWizard
 …
   /// This class defines the interface of the BfsVisit events, and
   /// it could be the base of a real visitor class.
   template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
     typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
 …
   };
 #else
   template <typename _Digraph>
+  template <typename GR>
   struct BfsVisitor {
     typedef _Digraph Digraph;
+    typedef GR Digraph;
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
 …
   ///
   /// Default traits class of BfsVisit class.
   /// \tparam _Digraph The type of the digraph the algorithm runs on.
   template<class _Digraph>
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  template<class GR>
   struct BfsVisitDefaultTraits {
     /// \brief The type of the digraph the algorithm runs on.
     typedef _Digraph Digraph;
+    typedef GR Digraph;
     /// \brief The type of the map that indicates which nodes are reached.
 …
   /// \ingroup search
   ///
   /// \brief %BFS algorithm class with visitor interface.
+  /// \brief BFS algorithm class with visitor interface.
   ///
   /// This class provides an efficient implementation of the %BFS algorithm
+  /// This class provides an efficient implementation of the BFS algorithm
   /// with visitor interface.
   ///
   /// The %BfsVisit class provides an alternative interface to the Bfs
+  /// The BfsVisit class provides an alternative interface to the Bfs
   /// class. It works with callback mechanism, the BfsVisit object calls
   /// the member functions of the \c Visitor class on every BFS event.
 …
   /// instead.
   ///
   /// \tparam _Digraph The type of the digraph the algorithm runs on.
   /// The default value is
   /// \ref ListDigraph. The value of _Digraph is not used directly by
   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
   /// \tparam _Visitor The Visitor type that is used by the algorithm.
   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// The default type is \ref ListDigraph.
+  /// The value of GR is not used directly by \ref BfsVisit,
+  /// it is only passed to \ref BfsVisitDefaultTraits.
+  /// \tparam VS The Visitor type that is used by the algorithm.
+  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
   /// does not observe the BFS events. If you want to observe the BFS
   /// events, you should implement your own visitor class.
   /// \tparam _Traits Traits class to set various data types used by the
+  /// \tparam TR Traits class to set various data types used by the
   /// algorithm. The default traits class is
   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
+  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a BFS visit traits class.
 #ifdef DOXYGEN
   template <typename _Digraph, typename _Visitor, typename _Traits>
+  template <typename GR, typename VS, typename TR>
 #else
   template <typename _Digraph = ListDigraph,
             typename _Visitor = BfsVisitor<_Digraph>,
             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
+  template <typename GR = ListDigraph,
+            typename VS = BfsVisitor<GR>,
+            typename TR = BfsVisitDefaultTraits<GR> >
 #endif
   class BfsVisit {
 …
     ///The traits class.
     typedef _Traits Traits;
+    typedef TR Traits;
     ///The type of the digraph the algorithm runs on.
 …
     ///The visitor type used by the algorithm.
     typedef _Visitor Visitor;
+    typedef VS Visitor;
     ///The type of the map that indicates which nodes are reached.
 …
     typedef BfsVisit Create;
     /// \name Named template parameters
+    /// \name Named Template Parameters
     ///@{
 …
     ///
     /// Sets the map that indicates which nodes are reached.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destructor deallocates this
+    /// automatically allocated map, of course.
+    /// If you don't use this function before calling \ref run(Node) "run()"
+    /// or \ref init(), an instance will be allocated automatically.
+    /// The destructor deallocates this automatically allocated map,
+    /// of course.
     /// \return <tt> (*this) </tt>
     BfsVisit &reachedMap(ReachedMap &m) {
 …
   public:
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \ref lemon::BfsVisit::run()
+    /// "run()".
+    /// \n
+    /// If you need more control on the execution, first you must call
+    /// \ref lemon::BfsVisit::init() "init()", then you can add several
+    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
+    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
+    /// actual path computation.
+    /// \name Execution Control
+    /// 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
+    /// \ref addSource(). Finally the actual path computation can be
+    /// performed with one of the \ref start() functions.
     /// @{
 …
     /// \name Query Functions
     /// The result of the %BFS algorithm can be obtained using these
+    /// The results of the BFS algorithm can be obtained using these
     /// functions.\n
     /// Either \ref lemon::BfsVisit::run() "run()" or
     /// \ref lemon::BfsVisit::start() "start()" must be called before
+    /// using them.
+    /// Either \ref run(Node) "run()" or \ref start() should be called
+    /// before using them.
     ///@{
+    /// \brief Checks if a node is reachable from the root(s).
+    ///
+    /// Returns \c true if \c v is reachable from the root(s).
+    /// \pre Either \ref run() or \ref start()
+    /// \brief Checks if a node is reached from the root(s).
+    ///
+    /// Returns \c true if \c v is reached from the root(s).
+    ///
+    /// \pre Either \ref run(Node) "run()" or \ref init()
     /// must be called before using this function.
     bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
     ///@}

lemon/bin_heap.h

-                      r209
+                      r631
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   ///\brief A Binary Heap implementation.
   ///
+  ///This class implements the \e binary \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. \c Compare specifies the ordering of the priorities. In a heap
+  ///one can change the priority of an item, add or erase an item, etc.
+  ///This class implements the \e binary \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. \c Comp specifies the ordering of the priorities.
+  ///In a heap one can change the priority of an item, add or erase an
+  ///item, etc.
   ///
   ///\tparam _Prio Type of the priority of the items.
   ///\tparam _ItemIntMap A read and writable Item int map, used internally
+  ///\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 _Compare A class for the ordering of the priorities. The
   ///default is \c std::less<_Prio>.
+  ///\tparam Comp A functor class for the ordering of the priorities.
+  ///The default is \c std::less<PR>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
+  template <typename _Prio, typename _ItemIntMap,
+            typename _Compare = std::less<_Prio> >
+  template <typename PR, typename IM, typename Comp = std::less<PR> >
   class BinHeap {
   public:
     ///\e
     typedef _ItemIntMap ItemIntMap;
     ///\e
     typedef _Prio Prio;
+    typedef IM ItemIntMap;
+    ///\e
+    typedef PR Prio;
     ///\e
     typedef typename ItemIntMap::Key Item;
 …
     typedef std::pair<Item,Prio> Pair;
     ///\e
     typedef _Compare Compare;
+    typedef Comp Compare;
     /// \brief Type to represent the items states.
 …
     /// heap's point of view, but may be useful to the user.
     ///
     /// The ItemIntMap \e should be initialized in such way that it maps
     /// PRE_HEAP (-1) to any element to be put in the heap...
+    /// The item-int map must be initialized in such way that it assigns
+    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
+      IN_HEAP = 0,    ///< = 0.
+      PRE_HEAP = -1,  ///< = -1.
+      POST_HEAP = -2  ///< = -2.
     };
   private:
     std::vector<Pair> data;
     Compare comp;
     ItemIntMap &iim;
+    std::vector<Pair> _data;
+    Compare _comp;
+    ItemIntMap &_iim;
   public:
 …
     ///
     /// The constructor.
+    /// \param _iim should be given to the constructor, since it is used
+    /// \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.
+    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.
+    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _iim 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.
+    BinHeap(ItemIntMap &_iim, const Compare &_comp)
+      : iim(_iim), comp(_comp) {}
+    ///
+    /// \param comp The comparator function object.
+    BinHeap(ItemIntMap &map, const Compare &comp)
+      : _iim(map), _comp(comp) {}
 …
     ///
     /// \brief Returns the number of items stored in the heap.
     int size() const { return data.size(); }
+    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.
     bool empty() const { return data.empty(); }
+    bool empty() const { return _data.empty(); }
     /// \brief Make empty this heap.
 …
     /// each item to \c PRE_HEAP.
     void clear() {
       data.clear();
+      _data.clear();
+    }
 …
     static int second_child(int i) { return 2*i+2; }
     bool less(const Pair &p1, const Pair &p2) const {
       return comp(p1.second, p2.second);
+      return _comp(p1.second, p2.second);
+    }
     int bubble_up(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,data[par]) ) {
         move(data[par],hole);
+      while( hole>0 && less(p,_data[par]) ) {
+        move(_data[par],hole);
         hole = par;
         par = parent(hole);
 …
       int child = second_child(hole);
       while(child < length) {
         if( less(data[child-1], data[child]) ) {
+        if( less(_data[child-1], _data[child]) ) {
           --child;
+        }
         if( !less(data[child], p) )
+        if( !less(_data[child], p) )
           goto ok;
         move(data[child], hole);
+        move(_data[child], hole);
         hole = child;
         child = second_child(hole);
+      }
       child--;
       if( child<length && less(data[child], p) ) {
         move(data[child], hole);
+      if( child<length && less(_data[child], p) ) {
+        move(_data[child], hole);
         hole=child;
+      }
 …
     void move(const Pair &p, int i) {
       data[i] = p;
       iim.set(p.first, i);
+      _data[i] = p;
+      _iim.set(p.first, i);
+    }
 …
     /// \param p The pair to insert.
     void push(const Pair &p) {
       int n = data.size();
       data.resize(n+1);
+      int n = _data.size();
+      _data.resize(n+1);
       bubble_up(n, p);
+    }
 …
     /// \pre The heap must be nonempty.
     Item top() const {
       return data[0].first;
+      return _data[0].first;
+    }
 …
     /// \pre The heap must be nonempty.
     Prio prio() const {
       return data[0].second;
+      return _data[0].second;
+    }
 …
     /// \pre The heap must be non-empty.
     void pop() {
       int n = data.size()-1;
       iim.set(data[0].first, POST_HEAP);
+      int n = _data.size()-1;
+      _iim.set(_data[0].first, POST_HEAP);
       if (n > 0) {
         bubble_down(0, data[n], n);
+      }
       data.pop_back();
+        bubble_down(0, _data[n], n);
+      }
+      _data.pop_back();
+    }
 …
     /// \pre The item should be in the heap.
     void erase(const Item &i) {
       int h = iim[i];
       int n = data.size()-1;
       iim.set(data[h].first, POST_HEAP);
+      int h = _iim[i];
+      int n = _data.size()-1;
+      _iim.set(_data[h].first, POST_HEAP);
       if( h < n ) {
         if ( bubble_up(h, data[n]) == h) {
           bubble_down(h, data[n], n);
+        if ( bubble_up(h, _data[n]) == h) {
+          bubble_down(h, _data[n], n);
+        }
+      }
       data.pop_back();
+      _data.pop_back();
+    }
 …
     ///
     /// This function returns the priority of item \c i.
+    /// \param i The item.
     /// \pre \c i must be in the heap.
-    /// \param i The item.
     Prio operator[](const Item &i) const {
       int idx = iim[i];
       return data[idx].second;
+      int idx = _iim[i];
+      return _data[idx].second;
+    }
 …
     /// \param p The priority.
     void set(const Item &i, const Prio &p) {
       int idx = iim[i];
+      int idx = _iim[i];
       if( idx < 0 ) {
         push(i,p);
+      }
       else if( comp(p, data[idx].second) ) {
+      else if( _comp(p, _data[idx].second) ) {
         bubble_up(idx, Pair(i,p));
+      }
       else {
         bubble_down(idx, Pair(i,p), data.size());
+        bubble_down(idx, Pair(i,p), _data.size());
+      }
+    }
 …
     ///
     /// This method decreases the priority of item \c i to \c p.
+    /// \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.
+    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.
     /// \param i The item.
     /// \param p The priority.
-    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.
     /// \pre \c i must be stored in the heap with priority at most \c
     /// p relative to \c Compare.
-    /// \param i The item.
-    /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
       bubble_down(idx, Pair(i,p), data.size());
+      int idx = _iim[i];
+      bubble_down(idx, Pair(i,p), _data.size());
+    }
 …
     /// \param i The item.
     State state(const Item &i) const {
       int s = iim[i];
+      int s = _iim[i];
       if( s>=0 )
         s=0;
 …
           erase(i);
+        }
         iim[i] = st;
+        _iim[i] = st;
         break;
       case IN_HEAP:
 …
     /// with the same prioriority as prevoiusly the \c i item.
     void replace(const Item& i, const Item& j) {
       int idx = iim[i];
       iim.set(i, iim[j]);
       iim.set(j, idx);
       data[idx].first = j;
+      int idx = _iim[i];
+      _iim.set(i, _iim[j]);
+      _iim.set(j, idx);
+      _data[idx].first = j;
+    }

lemon/bits/alteration_notifier.h

-                      r314
+                      r463
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   // a container.
   //
   // The simple graph's can be refered as two containers, one node container
   // and one edge container. But they are not standard containers they
   // does not store values directly they are just key continars for more
   // value containers which are the node and edge maps.
   //
   // The graph's node and edge sets can be changed as we add or erase
+  // The simple graphs can be refered as two containers: a node container
+  // and an edge container. But they do not store values directly, they
+  // are just key continars for more value containers, which are the
+  // node and edge maps.
+  //
+  // The node and edge sets of the graphs can be changed as we add or erase
   // nodes and edges in the graph. LEMON would like to handle easily
   // that the node and edge maps should contain values for all nodes or
   // edges. If we want to check on every indicing if the map contains
   // the current indicing key that cause a drawback in the performance
   // in the library. We use another solution we notify all maps about
+  // in the library. We use another solution: we notify all maps about
   // an alteration in the graph, which cause only drawback on the
   // alteration of the graph.
   //
+  // This class provides an interface to the container. The \e first() and \e
+  // next() member functions make possible to iterate on the keys of the
+  // container. The \e id() function returns an integer id for each key.
+  // The \e maxId() function gives back an upper bound of the ids.
+  // This class provides an interface to a node or edge container.
+  // The first() and next() member functions make possible
+  // to iterate on the keys of the container.
+  // The id() function returns an integer id for each key.
+  // The maxId() function gives back an upper bound of the ids.
   //
   // For the proper functonality of this class, we should notify it
   // about each alteration in the container. The alterations have four type
   // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
   // \e erase() signals that only one or few items added or erased to or
   // from the graph. If all items are erased from the graph or from an empty
   // graph a new graph is builded then it can be signaled with the
+  // about each alteration in the container. The alterations have four type:
+  // add(), erase(), build() and clear(). The add() and
+  // erase() signal that only one or few items added or erased to or
+  // from the graph. If all items are erased from the graph or if a new graph
+  // is built from an empty graph, then it can be signaled with the
   // clear() and build() members. Important rule that if we erase items
   // from graph we should first signal the alteration and after that erase
+  // from graphs we should first signal the alteration and after that erase
   // them from the container, on the other way on item addition we should
   // first extend the container and just after that signal the alteration.
   //
   // The alteration can be observed with a class inherited from the
   // \e ObserverBase nested class. The signals can be handled with
+  // ObserverBase nested class. The signals can be handled with
   // overriding the virtual functions defined in the base class.  The
   // observer base can be attached to the notifier with the
   // \e attach() member and can be detached with detach() function. The
+  // attach() member and can be detached with detach() function. The
   // alteration handlers should not call any function which signals
   // an other alteration in the same notifier and should not
   // detach any observer from the notifier.
   //
   // Alteration observers try to be exception safe. If an \e add() or
   // a \e clear() function throws an exception then the remaining
+  // Alteration observers try to be exception safe. If an add() or
+  // a clear() function throws an exception then the remaining
   // observeres will not be notified and the fulfilled additions will
   // be rolled back by calling the \e erase() or \e clear()
   // functions. Thence the \e erase() and \e clear() should not throw
   // exception. Actullay, it can be throw only \ref ImmediateDetach
   // exception which detach the observer from the notifier.
   //
   // There are some place when the alteration observing is not completly
+  // be rolled back by calling the erase() or clear() functions.
+  // Hence erase() and clear() should not throw exception.
+  // Actullay, they can throw only \ref ImmediateDetach exception,
+  // which detach the observer from the notifier.
+  //
+  // There are some cases, when the alteration observing is not completly
   // reliable. If we want to carry out the node degree in the graph
   // as in the \ref InDegMap and we use the reverseEdge that cause
+  // as in the \ref InDegMap and we use the reverseArc(), then it cause
   // unreliable functionality. Because the alteration observing signals
   // only erasing and adding but not the reversing it will stores bad
   // degrees. The sub graph adaptors cannot signal the alterations because
   // just a setting in the filter map can modify the graph and this cannot
   // be watched in any way.
+  // only erasing and adding but not the reversing, it will stores bad
+  // degrees. Apart form that the subgraph adaptors cannot even signal
+  // the alterations because just a setting in the filter map can modify
+  // the graph and this cannot be watched in any way.
   //
   // \param _Container The container which is observed.
 …
     typedef _Item Item;
     // \brief Exception which can be called from \e clear() and
     // \e erase().
     //
     // From the \e clear() and \e erase() function only this
+    // \brief Exception which can be called from clear() and
+    // erase().
+    //
+    // From the clear() and erase() function only this
     // exception is allowed to throw. The exception immediatly
     // detaches the current observer from the notifier. Because the
     // \e clear() and \e erase() should not throw other exceptions
+    // clear() and erase() should not throw other exceptions
     // it can be used to invalidate the observer.
     struct ImmediateDetach {};
 …
     // The observer interface contains some pure virtual functions
     // to override. The add() and erase() functions are
+    // to notify the oberver when one item is added or
+    // erased.
+    // to notify the oberver when one item is added or erased.
     //
     // The build() and clear() members are to notify the observer

lemon/bits/array_map.h

-                      r314
+                      r664
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   // \brief Graph map based on the array storage.
   //
+  // The ArrayMap template class is graph map structure what
+  // automatically updates the map when a key is added to or erased from
+  // the map. This map uses the allocators to implement
+  // the container functionality.
+  // The ArrayMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map uses the allocators to implement the container functionality.
   //
   // The template parameters are the Graph the current Item type and
+  // The template parameters are the Graph, the current Item type and
   // the Value type of the map.
   template <typename _Graph, typename _Item, typename _Value>
 …
     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
   public:
     // The graph type of the maps.
     typedef _Graph Graph;
     // The item type of the map.
+    // The graph type.
+    typedef _Graph GraphType;
+    // The item type.
     typedef _Item Item;
     // The reference map tag.
     typedef True ReferenceMapTag;
     // The key type of the maps.
+    // The key type of the map.
     typedef _Item Key;
     // The value type of the map.
 …
     typedef _Value& Reference;
+    // The map type.
+    typedef ArrayMap Map;
     // The notifier type.
     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
+  private:
     // The MapBase of the Map which imlements the core regisitry function.
     typedef typename Notifier::ObserverBase Parent;
-  private:
     typedef std::allocator<Value> Allocator;
 …
     //
     // Graph initialized map constructor.
     explicit ArrayMap(const Graph& graph) {
+    explicit ArrayMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
 …
     //
     // It constructs a map and initialize all of the the map.
     ArrayMap(const Graph& graph, const Value& value) {
+    ArrayMap(const GraphType& graph, const Value& value) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
 …
     // \brief Template assign operator.
     //
     // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
 …
     // \brief Adds a new key to the map.
     //
     // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
 …
     // \brief Adds more new keys to the map.
     //
     // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
 …
     // \brief Erase a key from the map.
     //
     // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
 …
     // \brief Erase more keys from the map.
     //
     // Erase more keys from the map. It called by the observer notifier
+    // Erase more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
 …
+    }
     // \brief Buildes the map.
     //
     // It buildes the map. It called by the observer notifier
+    // \brief Builds the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
 …
     // \brief Clear the map.
     //
     // It erase all items from the map. It called by the observer notifier
+    // It erase all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {

lemon/bits/bezier.h

r314	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/default_map.h

-                      r540
+                      r674
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   class DefaultMap
     : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
+    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
   public:
-    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     typedef DefaultMap<_Graph, _Item, _Value> Map;
     typedef typename Parent::Graph Graph;
+    typedef typename Parent::GraphType GraphType;
     typedef typename Parent::Value Value;
     explicit DefaultMap(const Graph& graph) : Parent(graph) {}
     DefaultMap(const Graph& graph, const Value& value)
+    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
+    DefaultMap(const GraphType& graph, const Value& value)
       : Parent(graph, value) {}

lemon/bits/enable_if.h

r314	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/bits/graph_extender.h

-                      r314
+                      r732
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 //\ingroup graphbits
 //\file
 //\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
   // \ingroup graphbits
   //
   // \brief Extender for the Digraphs
+  // \brief Extender for the digraph implementations
   template <typename Base>
   class DigraphExtender : public Base {
+    typedef Base Parent;
   public:
-    typedef Base Parent;
     typedef DigraphExtender Digraph;
 …
     class NodeMap
       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
-    public:
-      typedef DigraphExtender Digraph;
       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
+    public:
       explicit NodeMap(const Digraph& digraph)
         : Parent(digraph) {}
 …
     class ArcMap
       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
-    public:
-      typedef DigraphExtender Digraph;
       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
+    public:
       explicit ArcMap(const Digraph& digraph)
         : Parent(digraph) {}
 …
   template <typename Base>
   class GraphExtender : public Base {
+    typedef Base Parent;
   public:
-    typedef Base Parent;
     typedef GraphExtender Graph;
 …
     class NodeMap
       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
+      NodeMap(const Graph& graph)
+    public:
+      explicit NodeMap(const Graph& graph)
         : Parent(graph) {}
       NodeMap(const Graph& graph, const _Value& value)
 …
     class ArcMap
       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
+      ArcMap(const Graph& graph)
+    public:
+      explicit ArcMap(const Graph& graph)
         : Parent(graph) {}
       ArcMap(const Graph& graph, const _Value& value)
 …
     class EdgeMap
       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      EdgeMap(const Graph& graph)
+    public:
+      explicit EdgeMap(const Graph& graph)
         : Parent(graph) {}

lemon/bits/map_extender.h

-                      r314
+                      r664
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   template <typename _Map>
   class MapExtender : public _Map {
-  public:
     typedef _Map Parent;
+    typedef typename Parent::GraphType GraphType;
+  public:
     typedef MapExtender Map;
-    typedef typename Parent::Graph Graph;
     typedef typename Parent::Key Item;
     typedef typename Parent::Key Key;
     typedef typename Parent::Value Value;
+    typedef typename Parent::Reference Reference;
+    typedef typename Parent::ConstReference ConstReference;
     class MapIt;
 …
   public:
     MapExtender(const Graph& graph)
+    MapExtender(const GraphType& graph)
       : Parent(graph) {}
     MapExtender(const Graph& graph, const Value& value)
+    MapExtender(const GraphType& graph, const Value& value)
       : Parent(graph, value) {}
 …
   public:
     class MapIt : public Item {
+    public:
+      typedef Item Parent;
+      typedef Item Parent;
+    public:
       typedef typename Map::Value Value;
 …
     class ConstMapIt : public Item {
     public:
       typedef Item Parent;
+      typedef Item Parent;
+    public:
       typedef typename Map::Value Value;
 …
     class ItemIt : public Item {
     public:
       typedef Item Parent;
+      typedef Item Parent;
+    public:
       ItemIt() {}
 …
   template <typename _Graph, typename _Map>
   class SubMapExtender : public _Map {
-  public:
     typedef _Map Parent;
+    typedef _Graph GraphType;
+  public:
     typedef SubMapExtender Map;
-    typedef _Graph Graph;
     typedef typename Parent::Key Item;
     typedef typename Parent::Key Key;
     typedef typename Parent::Value Value;
+    typedef typename Parent::Reference Reference;
+    typedef typename Parent::ConstReference ConstReference;
     class MapIt;
 …
   public:
     SubMapExtender(const Graph& _graph)
+    SubMapExtender(const GraphType& _graph)
       : Parent(_graph), graph(_graph) {}
     SubMapExtender(const Graph& _graph, const Value& _value)
+    SubMapExtender(const GraphType& _graph, const Value& _value)
       : Parent(_graph, _value), graph(_graph) {}
 …
   public:
     class MapIt : public Item {
     public:
       typedef Item Parent;
+      typedef Item Parent;
+    public:
       typedef typename Map::Value Value;
 …
     class ConstMapIt : public Item {
     public:
       typedef Item Parent;
+      typedef Item Parent;
+    public:
       typedef typename Map::Value Value;
 …
     class ItemIt : public Item {
     public:
       typedef Item Parent;
+      typedef Item Parent;
+    public:
       ItemIt() {}
 …
   private:
     const Graph& graph;
+    const GraphType& graph;
   };

lemon/bits/path_dump.h

-                      r209
+                      r576
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
  */
+#ifndef LEMON_BITS_PRED_MAP_PATH_H
+#define LEMON_BITS_PRED_MAP_PATH_H
+#ifndef LEMON_BITS_PATH_DUMP_H
+#define LEMON_BITS_PATH_DUMP_H
+#include <lemon/core.h>
+#include <lemon/concept_check.h>
 namespace lemon {

lemon/bits/traits.h

-                      r314
+                      r663
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   struct InvalidType {};
   template <typename _Graph, typename _Item>
+  template <typename GR, typename _Item>
   class ItemSetTraits {};
   template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct NodeNotifierIndicator {
     typedef InvalidType Type;
   };
   template <typename Graph>
+  template <typename GR>
   struct NodeNotifierIndicator<
     Graph,
     typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
   > {
     typedef typename Graph::NodeNotifier Type;
   };
   template <typename _Graph>
   class ItemSetTraits<_Graph, typename _Graph::Node> {
+    GR,
+    typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::NodeNotifier Type;
+  };
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Node> {
   public:
+    typedef _Graph Graph;
+    typedef typename Graph::Node Item;
+    typedef typename Graph::NodeIt ItemIt;
+    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
+    template <typename _Value>
+    class Map : public Graph::template NodeMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+    typedef typename GR::Node Item;
+    typedef typename GR::NodeIt ItemIt;
+    typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
+    template <typename V>
+    class Map : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
     public:
+      typedef typename Graph::template NodeMap<_Value> Parent;
+      typedef typename Graph::template NodeMap<_Value> Type;
+      typedef typename GR::template NodeMap<V> Type;
       typedef typename Parent::Value Value;
       Map(const Graph& _digraph) : Parent(_digraph) {}
       Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
 …
   };
   template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct ArcNotifierIndicator {
     typedef InvalidType Type;
   };
   template <typename Graph>
+  template <typename GR>
   struct ArcNotifierIndicator<
     Graph,
     typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
   > {
     typedef typename Graph::ArcNotifier Type;
   };
   template <typename _Graph>
   class ItemSetTraits<_Graph, typename _Graph::Arc> {
+    GR,
+    typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::ArcNotifier Type;
+  };
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Arc> {
   public:
+    typedef _Graph Graph;
+    typedef typename Graph::Arc Item;
+    typedef typename Graph::ArcIt ItemIt;
+    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
+    template <typename _Value>
+    class Map : public Graph::template ArcMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+    typedef typename GR::Arc Item;
+    typedef typename GR::ArcIt ItemIt;
+    typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
+    template <typename V>
+    class Map : public GR::template ArcMap<V> {
+      typedef typename GR::template ArcMap<V> Parent;
     public:
+      typedef typename Graph::template ArcMap<_Value> Parent;
+      typedef typename Graph::template ArcMap<_Value> Type;
+      typedef typename GR::template ArcMap<V> Type;
       typedef typename Parent::Value Value;
       Map(const Graph& _digraph) : Parent(_digraph) {}
       Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
     };
 …
   };
   template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct EdgeNotifierIndicator {
     typedef InvalidType Type;
   };
   template <typename Graph>
+  template <typename GR>
   struct EdgeNotifierIndicator<
     Graph,
     typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
   > {
     typedef typename Graph::EdgeNotifier Type;
   };
   template <typename _Graph>
   class ItemSetTraits<_Graph, typename _Graph::Edge> {
+    GR,
+    typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::EdgeNotifier Type;
+  };
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Edge> {
   public:
+    typedef _Graph Graph;
+    typedef typename Graph::Edge Item;
+    typedef typename Graph::EdgeIt ItemIt;
+    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
+    template <typename _Value>
+    class Map : public Graph::template EdgeMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+    typedef typename GR::Edge Item;
+    typedef typename GR::EdgeIt ItemIt;
+    typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
+    template <typename V>
+    class Map : public GR::template EdgeMap<V> {
+      typedef typename GR::template EdgeMap<V> Parent;
     public:
+      typedef typename Graph::template EdgeMap<_Value> Parent;
+      typedef typename Graph::template EdgeMap<_Value> Type;
+      typedef typename GR::template EdgeMap<V> Type;
       typedef typename Parent::Value Value;
       Map(const Graph& _digraph) : Parent(_digraph) {}
       Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
     };
 …
   // Indicators for the tags
   template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct NodeNumTagIndicator {
     static const bool value = false;
   };
   template <typename Graph>
+  template <typename GR>
   struct NodeNumTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::NodeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::NodeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
+  struct ArcNumTagIndicator {
+    static const bool value = false;
+  };
+  template <typename GR>
+  struct ArcNumTagIndicator<
+    GR,
+    typename enable_if<typename GR::ArcNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
   struct EdgeNumTagIndicator {
     static const bool value = false;
   };
   template <typename Graph>
+  template <typename GR>
   struct EdgeNumTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::EdgeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::EdgeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
+  struct FindArcTagIndicator {
+    static const bool value = false;
+  };
+  template <typename GR>
+  struct FindArcTagIndicator<
+    GR,
+    typename enable_if<typename GR::FindArcTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
   struct FindEdgeTagIndicator {
     static const bool value = false;
   };
   template <typename Graph>
+  template <typename GR>
   struct FindEdgeTagIndicator<
     Graph,
     typename enable_if<typename Graph::FindEdgeTag, void>::type
   > {
     static const bool value = true;
   };
   template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::FindEdgeTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
   struct UndirectedTagIndicator {
     static const bool value = false;
   };
   template <typename Graph>
+  template <typename GR>
   struct UndirectedTagIndicator<
     Graph,
     typename enable_if<typename Graph::UndirectedTag, void>::type
   > {
     static const bool value = true;
   };
   template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::UndirectedTag, void>::type
+  > {
+    static const bool value = true;
+  };
+  template <typename GR, typename Enable = void>
   struct BuildTagIndicator {
     static const bool value = false;
   };
   template <typename Graph>
+  template <typename GR>
   struct BuildTagIndicator<
     Graph,
     typename enable_if<typename Graph::BuildTag, void>::type
+    GR,
+    typename enable_if<typename GR::BuildTag, void>::type
   > {
     static const bool value = true;

lemon/bits/vector_map.h

-                      r314
+                      r664
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
   // \brief Graph map based on the std::vector storage.
   //
   // The VectorMap template class is graph map structure what
   // automatically updates the map when a key is added to or erased from
   // the map. This map type uses the std::vector to store the values.
+  // The VectorMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map type uses std::vector to store the values.
   //
   // \tparam _Graph The graph this map is attached to.
 …
     // The graph type of the map.
     typedef _Graph Graph;
+    typedef _Graph GraphType;
     // The item type of the map.
     typedef _Item Item;
 …
     // The map type.
     typedef VectorMap Map;
-    // The base class of the map.
-    typedef typename Notifier::ObserverBase Parent;
     // The reference type of the map;
 …
     typedef typename Container::const_reference ConstReference;
+  private:
+    // The base class of the map.
+    typedef typename Notifier::ObserverBase Parent;
+  public:
     // \brief Constructor to attach the new map into the notifier.
 …
     // It constructs a map and attachs it into the notifier.
     // It adds all the items of the graph to the map.
     VectorMap(const Graph& graph) {
+    VectorMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       container.resize(Parent::notifier()->maxId() + 1);
 …
     // It constructs a map uses a given value to initialize the map.
     // It adds all the items of the graph to the map.
     VectorMap(const Graph& graph, const Value& value) {
+    VectorMap(const GraphType& graph, const Value& value) {
       Parent::attach(graph.notifier(Item()));
       container.resize(Parent::notifier()->maxId() + 1, value);
 …
     // \brief Template assign operator.
     //
     // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
 …
     // \brief Adds a new key to the map.
     //
     // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
 …
     // \brief Adds more new keys to the map.
     //
     // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
 …
     // \brief Erase a key from the map.
     //
     // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
 …
     // \brief Erase more keys from the map.
     //
     // Erase more keys from the map. It called by the observer notifier
+    // It erases more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
 …
+    }
     // \brief Buildes the map.
     //
     // It buildes the map. It called by the observer notifier
+    // \brief Build the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
 …
     // \brief Clear the map.
     //
     // It erase all items from the map. It called by the observer notifier
+    // It erases all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {

lemon/bits/windows.h

-                      r511
+                      r576
  */
 #ifndef LEMON_WINDOWS_H
 #define LEMON_WINDOWS_H
+#ifndef LEMON_BITS_WINDOWS_H
+#define LEMON_BITS_WINDOWS_H
 #include <string>

lemon/color.cc

r209	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/color.h

r313	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/concept_check.h

r285	r463
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-2008
	5	* Copyright (C) 2003-2009
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).

lemon/concepts/digraph.h

-                      r263
+                      r627
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
  */
 #ifndef LEMON_CONCEPT_DIGRAPH_H
 #define LEMON_CONCEPT_DIGRAPH_H
+#ifndef LEMON_CONCEPTS_DIGRAPH_H
+#define LEMON_CONCEPTS_DIGRAPH_H
 ///\ingroup graph_concepts
 …
       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
+      /// \brief Read write map of the nodes to type \c T.
+      ///
+      /// ReadWrite map of the nodes to type \c T.
+      /// \sa Reference
+      /// \brief Reference map of the nodes to type \c T.
+      ///
+      /// Reference map of the nodes to type \c T.
       template<class T>
       class NodeMap : public ReadWriteMap< Node, T > {
+      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
       public:
 …
       private:
         ///Copy constructor
+        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+        NodeMap(const NodeMap& nm) :
+          ReferenceMap<Node, T, T&, const T&>(nm) { }
         ///Assignment operator
         template <typename CMap>
 …
       };
       /// \brief Read write map of the arcs to type \c T.
+      /// \brief Reference map of the arcs to type \c T.
       ///
       /// Reference map of the arcs to type \c T.
-      /// \sa Reference
       template<class T>
       class ArcMap : public ReadWriteMap<Arc,T> {
+      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
       public:
 …
       private:
         ///Copy constructor
+        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
+        ArcMap(const ArcMap& em) :
+          ReferenceMap<Arc, T, T&, const T&>(em) { }
         ///Assignment operator
         template <typename CMap>
 …
       struct Constraints {
         void constraints() {
+          checkConcept<BaseDigraphComponent, _Digraph>();
           checkConcept<IterableDigraphComponent<>, _Digraph>();
           checkConcept<IDableDigraphComponent<>, _Digraph>();
 …
 #endif // LEMON_CONCEPT_DIGRAPH_H
+#endif

lemon/concepts/graph.h

-                      r263
+                      r704
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 ///\brief The concept of Undirected Graphs.
 #ifndef LEMON_CONCEPT_GRAPH_H
 #define LEMON_CONCEPT_GRAPH_H
+#ifndef LEMON_CONCEPTS_GRAPH_H
+#define LEMON_CONCEPTS_GRAPH_H
 #include <lemon/concepts/graph_components.h>
-#include <lemon/concepts/graph.h>
 #include <lemon/core.h>
 …
       /// The directed arc type. It can be converted to the
       /// edge or it should be inherited from the undirected
       /// arc.
       class Arc : public Edge {
+      /// edge.
+      class Arc {
       public:
         /// Default constructor
 …
         /// Copy constructor.
         ///
         Arc(const Arc& e) : Edge(e) { }
+        Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
 …
         bool operator<(Arc) const { return false; }
+        /// Converison to Edge
+        operator Edge() const { return Edge(); }
       };
       /// This iterator goes through each directed arc.
 …
       };
+      /// \brief Read write map of the nodes to type \c T.
+      ///
+      /// ReadWrite map of the nodes to type \c T.
+      /// \sa Reference
+      /// \brief Reference map of the nodes to type \c T.
+      ///
+      /// Reference map of the nodes to type \c T.
       template<class T>
       class NodeMap : public ReadWriteMap< Node, T >
+      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
+      {
       public:
 …
       private:
         ///Copy constructor
+        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
+        NodeMap(const NodeMap& nm) :
+          ReferenceMap<Node, T, T&, const T&>(nm) { }
         ///Assignment operator
         template <typename CMap>
 …
       };
+      /// \brief Read write map of the directed arcs to type \c T.
+      ///
+      /// Reference map of the directed arcs to type \c T.
+      /// \sa Reference
+      /// \brief Reference map of the arcs to type \c T.
+      ///
+      /// Reference map of the arcs to type \c T.
       template<class T>
       class ArcMap : public ReadWriteMap<Arc,T>
+      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
+      {
       public:
 …
       private:
         ///Copy constructor
+        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
+        ArcMap(const ArcMap& em) :
+          ReferenceMap<Arc, T, T&, const T&>(em) { }
         ///Assignment operator
         template <typename CMap>
 …
       };
+      /// Read write map of the edges to type \c T.
+      /// Reference map of the arcs to type \c T.
+      /// \sa Reference
+      /// Reference map of the edges to type \c T.
+      /// Reference map of the edges to type \c T.
       template<class T>
       class EdgeMap : public ReadWriteMap<Edge,T>
+      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
+      {
       public:
 …
       private:
         ///Copy constructor
+        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
+        EdgeMap(const EdgeMap& em) :
+          ReferenceMap<Edge, T, T&, const T&>(em) {}
         ///Assignment operator
         template <typename CMap>
 …
       /// \brief Opposite node on an arc
       ///
       /// \return the opposite of the given Node on the given Edge
+      /// \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.
+      /// \return The first node of the given edge.
       ///
       /// Naturally edges don't have direction and thus
       /// don't have source and target node. But we use these two 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
+      /// 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.
+      /// \sa direction
+      /// \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.
+      /// \sa u()
+      /// \sa direction()
       Node v(Edge) const { return INVALID; }
 …
       struct Constraints {
         void constraints() {
+          checkConcept<BaseGraphComponent, _Graph>();
           checkConcept<IterableGraphComponent<>, _Graph>();
           checkConcept<IDableGraphComponent<>, _Graph>();

lemon/concepts/graph_components.h

-                      r313
+                      r713
  * This file is a part of LEMON, a generic C++ optimization library.
+ *
  * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 …
 ///\brief The concept of graph components.
+#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H
+#define LEMON_CONCEPT_GRAPH_COMPONENTS_H
+#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
+#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 #include <lemon/core.h>
 …
   namespace concepts {
     /// \brief Skeleton class for graph Node and Arc types
     ///
     /// This class describes the interface of Node and Arc (and Edge
     /// in undirected graphs) subtypes of graph types.
+    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
+    ///
+    /// This class describes the concept of \c Node, \c Arc and \c Edge
+    /// subtypes of digraph and graph types.
     ///
     /// \note This class is a template class so that we can use it to
+    /// create graph skeleton classes. The reason for this is than Node
+    /// and Arc types should \em not derive from the same base class.
+    /// For Node you should instantiate it with character 'n' and for Arc
+    /// with 'a'.
+    /// create graph skeleton classes. The reason for this is that \c Node
+    /// and \c Arc (or \c Edge) types should \e not derive from the same
+    /// base class. For \c Node you should instantiate it with character
+    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 #ifndef DOXYGEN
     template <char _selector = '0'>
+    template <char sel = '0'>
 #endif
     class GraphItem {
 …
       /// \brief Default constructor.
       ///
+      /// Default constructor.
       /// \warning The default constructor is not required to set
       /// the item to some well-defined value. So you should consider it
       /// as uninitialized.
       GraphItem() {}
       /// \brief Copy constructor.
       ///
       /// Copy constructor.
-      ///
       GraphItem(const GraphItem &) {}
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      /// \brief Constructor for conversion from \c INVALID.
+      ///
+      /// Constructor for conversion from \c INVALID.
+      /// It initializes the item to be invalid.
       /// \sa Invalid for more details.
       GraphItem(Invalid) {}
+      /// \brief Assign operator for nodes.
+      ///
+      /// The nodes are assignable.
+      ///
+      GraphItem& operator=(GraphItem const&) { return *this; }
+      /// \brief Assignment operator.
+      ///
+      /// Assignment operator for the item.
+      GraphItem& operator=(const GraphItem&) { return *this; }
+      /// \brief Assignment operator for INVALID.
+      ///
+      /// This operator makes the item invalid.
+      GraphItem& operator=(Invalid) { return *this; }
       /// \brief Equality operator.
       ///
       /// Two iterators are equal if and only if they represents the
       /// same node in the graph or both are invalid.
+      bool operator==(GraphItem) const { return false; }
+      /// Equality operator.
+      bool operator==(const GraphItem&) const { return false; }
       /// \brief Inequality operator.
       ///
       /// \sa operator==(const Node& n)
       ///
+      bool operator!=(GraphItem) const { return false; }
       /// \brief Artificial ordering operator.
       ///
       /// To allow the use of graph descriptors as key type in std::map or
       /// similar associative container we require this.
+      /// Inequality operator.
+      bool operator!=(const GraphItem&) const { return false; }
+      /// \brief Ordering operator.
+      ///
+      /// This operator defines an ordering of the items.
+      /// It makes possible to use graph item types as key types in
+      /// associative containers (e.g. \c std::map).
       ///
       /// \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.
       bool operator<(GraphItem) const { return false; }
+      bool operator<(const GraphItem&) const { return false; }
       template<typename _GraphItem>
 …
         void constraints() {
           _GraphItem i1;
+          i1=INVALID;
           _GraphItem i2 = i1;
           _GraphItem i3 = INVALID;
 …
           bool b;
-          //          b = (ia == ib) && (ia != ib) && (ia < ib);
           b = (ia == ib) && (ia != ib);
           b = (ia == INVALID) && (ib != INVALID);
 …
     };
+    /// \brief An empty base directed graph class.
+    ///
+    /// This class provides the minimal set of features needed for a
+    /// directed graph structure. All digraph concepts have to be
+    /// conform to this base directed graph. It just provides types
+    /// for nodes and arcs and functions to get the source and the
+    /// target of the arcs.
+    /// \brief Base skeleton class for directed graphs.
+    ///
+    /// This class describes the base interface of directed graph types.
+    /// All digraph %concepts have to conform to this class.
+    /// It just provides types for nodes and arcs and functions
+    /// to get the source and the target nodes of arcs.
     class BaseDigraphComponent {
     public:
 …
       /// \brief Node class of the digraph.
       ///
+      /// This class represents the Nodes of the digraph.
+      ///
+      /// This class represents the nodes of the digraph.
       typedef GraphItem<'n'> Node;
       /// \brief Arc class of the digraph.
       ///
+      /// This class represents the Arcs of the digraph.
+      ///
+      typedef GraphItem<'e'> Arc;
+      /// \brief Gives back the target node of an arc.
+      ///
+      /// Gives back the target node of an arc.
+      ///
+      Node target(const Arc&) const { return INVALID;}
+      /// \brief Gives back the source node of an arc.
+      ///
+      /// Gives back the source node of an arc.
+      ///
+      Node source(const Arc&) const { return INVALID;}
+      /// \brief Gives back the opposite node on the given arc.
+      ///
+      /// Gives back the opposite node on the given arc.
+      /// This class represents the arcs of the digraph.
+      typedef GraphItem<'a'> Arc;
+      /// \brief Return the source node of an arc.
+      ///
+      /// This function returns the source node of an arc.
+      Node source(const Arc&) const { return INVALID; }
+      /// \brief Return the target node of an arc.
+      ///
+      /// This function returns the target node of an arc.
+      Node target(const Arc&) const { return INVALID; }
+      /// \brief Return the opposite node on the given arc.
+      ///
+      /// This function returns the opposite node on the given arc.
       Node oppositeNode(const Node&, const Arc&) const {
         return INVALID;
 …
     };
+    /// \brief An empty base undirected graph class.
+    ///
+    /// This class provides the minimal set of features needed for an
+    /// undirected graph structure. All undirected graph concepts have
+    /// to be conform to this base graph. It just provides types for
+    /// nodes, arcs and edges and functions to get the
+    /// source and the target of the arcs and edges,
+    /// conversion from arcs to edges and function to get
+    /// both direction of the edges.
+    /// \brief Base skeleton class for undirected graphs.
+    ///
+    /// This class describes the base interface of undirected graph types.
+    /// All graph %concepts have to conform to this class.
+    /// It extends the interface of \ref BaseDigraphComponent with an
+    /// \c Edge type and functions to get the end nodes of edges,
+    /// to convert from arcs to edges and to get both direction of edges.
     class BaseGraphComponent : public BaseDigraphComponent {
     public:
+      typedef BaseGraphComponent Graph;
       typedef BaseDigraphComponent::Node Node;
       typedef BaseDigraphComponent::Arc Arc;
+      /// \brief Undirected arc class of the graph.
+      ///
+      /// This class represents the edges of the graph.
+      /// The undirected graphs can be used as a directed graph which
+      /// for each arc contains the opposite arc too so the graph is
+      /// bidirected. The edge represents two opposite
+      /// directed arcs.
+      class Edge : public GraphItem<'u'> {
+      /// \brief Undirected edge class of the graph.
+      ///
+      /// This class represents the undirected edges of the graph.
+      /// Undirected graphs can be used as directed graphs, each edge is
+      /// represented by two opposite directed arcs.
+      class Edge : public GraphItem<'e'> {
+        typedef GraphItem<'e'> Parent;
       public:
-        typedef GraphItem<'u'> Parent;
         /// \brief Default constructor.
         ///
+        /// Default constructor.
         /// \warning The default constructor is not required to set
         /// the item to some well-defined value. So you should consider it
         /// as uninitialized.
         Edge() {}
         /// \brief Copy constructor.
         ///
         /// Copy constructor.
+        Edge(const Edge &) : Parent() {}
+        /// \brief Constructor for conversion from \c INVALID.
         ///
+        Edge(const Edge &) : Parent() {}
+        /// \brief Invalid constructor \& conversion.
+        ///
+        /// This constructor initializes the item to be invalid.
+        /// Constructor for conversion from \c INVALID.
+        /// It initializes the item to be invalid.
         /// \sa Invalid for more details.
         Edge(Invalid) {}
+        /// \brief Converter from arc to edge.
+        /// \brief Constructor for conversion from an arc.
         ///
+        /// Constructor for conversion from an arc.
         /// Besides the core graph item functionality each arc should
         /// be convertible to the represented edge.
         Edge(const Arc&) {}
+        /// \brief Assign arc to edge.
+        ///
+        /// Besides the core graph item functionality each arc should
+        /// be convertible to the represented edge.
+        Edge& operator=(const Arc&) { return *this; }
+      };
+      /// \brief Returns the direction of the arc.
+     };
+      /// \brief Return one end node of an edge.
+      ///
+      /// This function returns one end node of an edge.
+      Node u(const Edge&) const { return INVALID; }
+      /// \brief Return the other end node of an edge.
+      ///
+      /// This function returns the other end node of an edge.
+      Node v(const Edge&) const { return INVALID; }
+      /// \brief Return a directed arc related to an edge.
+      ///
+      /// This function returns a directed arc from its direction and the
+      /// represented edge.
+      Arc direct(const Edge&, bool) const { return INVALID; }
+      /// \brief Return a directed arc related to an edge.
+      ///
+      /// This function returns a directed arc from its source node and the
+      /// represented edge.
+      Arc direct(const Edge&, const Node&) const { return INVALID; }
+      /// \brief Return the direction of the arc.
       ///
       /// Returns the direction of the arc. Each arc represents an
 …
       bool direction(const Arc&) const { return true; }
+      /// \brief Returns the directed arc.
+      ///
+      /// Returns the directed arc from its direction and the
+      /// represented edge.
+      Arc direct(const Edge&, bool) const { return INVALID;}
+      /// \brief Returns the directed arc.
+      ///
+      /// Returns the directed arc from its source and the
+      /// represented edge.
+      Arc direct(const Edge&, const Node&) const { return INVALID;}
+      /// \brief Returns the opposite arc.
+      ///
+      /// Returns the opposite arc. It is the arc representing the
+      /// same edge and has opposite direction.
+      Arc oppositeArc(const Arc&) const { return INVALID;}
+      /// \brief Gives back one ending of an edge.
+      ///
+      /// Gives back one ending of an edge.
+      Node u(const Edge&) const { return INVALID;}
+      /// \brief Gives back the other ending of an edge.
+      ///
+      /// Gives back the other ending of an edge.
+      Node v(const Edge&) const { return INVALID;}
+      /// \brief Return the opposite arc.
+      ///
+      /// This function returns the opposite arc, i.e. the arc representing
+      /// the same edge and has opposite direction.
+      Arc oppositeArc(const Arc&) const { return INVALID; }
       template <typename _Graph>
 …
         void constraints() {
           checkConcept<BaseDigraphComponent, _Graph>();
           checkConcept<GraphItem<'u'>, Edge>();
+          checkConcept<GraphItem<'e'>, Edge>();
+          {
             Node n;
 …
             n = graph.v(ue);
             e = graph.direct(ue, true);
+            e = graph.direct(ue, false);
             e = graph.direct(ue, n);
             e = graph.oppositeArc(e);
 …
     };
     /// \brief An empty idable base digraph class.
     ///
     /// This class provides beside the core digraph features
     /// core id functions for the digraph structure.
     /// The most of the base digraphs should be conform to this concept.
     /// The id's are unique and immutable.
     template <typename _Base = BaseDigraphComponent>
     class IDableDigraphComponent : public _Base {
     public:
       typedef _Base Base;
+    /// \brief Skeleton class for \e idable directed graphs.
+    ///
+    /// This class describes the interface of \e idable directed graphs.
+    /// It extends \ref BaseDigraphComponent with the core ID functions.
+    /// The ids of the items must be unique and immutable.
+    /// This concept is part of the Digraph concept.
+    template <typename BAS = BaseDigraphComponent>
+    class IDableDigraphComponent : public BAS {
+    public:
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
+      /// \brief Gives back an unique integer id for the Node.
+      ///
+      /// Gives back an unique integer id for the Node.
+      ///
+      int id(const Node&) const { return -1;}
+      /// \brief Gives back the node by the unique id.
+      ///
+      /// Gives back the node by the unique id.
+      /// If the digraph does not contain node with the given id
+      /// then the result of the function is undetermined.
+      Node nodeFromId(int) const { return INVALID;}
+      /// \brief Gives back an unique integer id for the Arc.
+      ///
+      /// Gives back an unique integer id for the Arc.
+      ///
+      int id(const Arc&) const { return -1;}
+      /// \brief Gives back the arc by the unique id.
+      ///
+      /// Gives back the arc by the unique id.
+      /// If the digraph does not contain arc with the given id
+      /// then the result of the function is undetermined.
+      Arc arcFromId(int) const { return INVALID;}
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// Node id.
+      ///
+      /// Gives back an integer greater or equal to the maximum Node
+      /// id.
+      int maxNodeId() const { return -1;}
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// Arc id.
+      ///
+      /// Gives back an integer greater or equal to the maximum Arc
+      /// id.
+      int maxArcId() const { return -1;}
+      /// \brief Return a unique integer id for the given node.
+      ///
+      /// This function returns a unique integer id for the given node.
+      int id(const Node&) const { return -1; }
+      /// \brief Return the node by its unique id.
+      ///
+      /// This function returns the node by its unique id.
+      /// If the digraph does not contain a node with the given id,
+      /// then the result of the function is undefined.
+      Node nodeFromId(int) const { return INVALID; }
+      /// \brief Return a unique integer id for the given arc.
+      ///
+      /// This function returns a unique integer id for the given arc.
+      int id(const Arc&) const { return -1; }
+      /// \brief Return the arc by its unique id.
+      ///
+      /// This function returns the arc by its unique id.
+      /// If the digraph does not contain an arc with the given id,
+      /// then the result of the function is undefined.
+      Arc arcFromId(int) const { return INVALID; }
+      /// \brief Return an integer greater or equal to the maximum
+      /// node id.
+      ///
+      /// This function returns an integer greater or equal to the
+      /// maximum node id.
+      int maxNodeId() const { return -1; }
+      /// \brief Return an integer greater or equal to the maximum
+      /// arc id.
+      ///
+      /// This function returns an integer greater or equal to the
+      /// maximum arc id.
+      int maxArcId() const { return -1; }
       template <typename _Digraph>
 …
           checkConcept<Base, _Digraph >();
           typename _Digraph::Node node;
+          node=INVALID;
           int nid = digraph.id(node);
           nid = digraph.id(node);
           node = digraph.nodeFromId(nid);
           typename _Digraph::Arc arc;
+          arc=INVALID;
           int eid = digraph.id(arc);
           eid = digraph.id(arc);
 …
     };
+    /// \brief An empty idable base undirected graph class.
+    ///
+    /// This class provides beside the core undirected graph features
+    /// core id functions for the undirected graph structure.  The
+    /// most of the base undirected graphs should be conform to this
+    /// concept.  The id's are unique and immutable.
+    template <typename _Base = BaseGraphComponent>
+    class IDableGraphComponent : public IDableDigraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+    /// \brief Skeleton class for \e idable undirected graphs.
+    ///
+    /// This class describes the interface of \e idable undirected
+    /// graphs. It extends \ref IDableDigraphComponent with the core ID
+    /// functions of undirected graphs.
+    /// The ids of the items must be unique and immutable.
+    /// This concept is part of the Graph concept.
+    template <typename BAS = BaseGraphComponent>
+    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
+    public:
+      typedef BAS Base;
       typedef typename Base::Edge Edge;
+      using IDableDigraphComponent<_Base>::id;
+      /// \brief Gives back an unique integer id for the Edge.
+      ///
+      /// Gives back an unique integer id for the Edge.
+      ///
+      int id(const Edge&) const { return -1;}
+      /// \brief Gives back the edge by the unique id.
+      ///
+      /// Gives back the edge by the unique id.  If the
+      /// graph does not contain arc with the given id then the
+      /// result of the function is undetermined.
+      Edge edgeFromId(int) const { return INVALID;}
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// Edge id.
+      ///
+      /// Gives back an integer greater or equal to the maximum Edge
+      /// id.
+      int maxEdgeId() const { return -1;}
+      using IDableDigraphComponent<Base>::id;
+      /// \brief Return a unique integer id for the given edge.
+      ///
+      /// This function returns a unique integer id for the given edge.
+      int id(const Edge&) const { return -1; }
+      /// \brief Return the edge by its unique id.
+      ///
+      /// This function returns the edge by its unique id.
+      /// If the graph does not contain an edge with the given id,
+      /// then the result of the function is undefined.
+      Edge edgeFromId(int) const { return INVALID; }
+      /// \brief Return an integer greater or equal to the maximum
+      /// edge id.
+      ///
+      /// This function returns an integer greater or equal to the
+      /// maximum edge id.
+      int maxEdgeId() const { return -1; }
       template <typename _Graph>
 …
         void constraints() {
-          checkConcept<Base, _Graph >();
           checkConcept<IDableDigraphComponent<Base>, _Graph >();
           typename _Graph::Edge edge;
 …
     };
     /// \brief Skeleton class for graph NodeIt and ArcIt
     ///
     /// Skeleton class for graph NodeIt and ArcIt.
     ///
     template <typename _Graph, typename _Item>
     class GraphItemIt : public _Item {
+    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
+    ///
+    /// This class describes the concept of \c NodeIt, \c ArcIt and
+    /// \c EdgeIt subtypes of digraph and graph types.
+    template <typename GR, typename Item>
+    class GraphItemIt : public Item {
     public:
       /// \brief Default constructor.
       ///
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      /// Default constructor.
+      /// \warning The default constructor is not required to set
+      /// the iterator to some well-defined value. So you should consider it
+      /// as uninitialized.
       GraphItemIt() {}
       /// \brief Copy constructor.
       ///
       /// Copy constructor.
+      ///
+      GraphItemIt(const GraphItemIt& ) {}
+      /// \brief Sets the iterator to the first item.
+      ///
+      /// Sets the iterator to the first item of \c the graph.
+      ///
+      explicit GraphItemIt(const _Graph&) {}
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      GraphItemIt(const GraphItemIt& it) : Item(it) {}
+      /// \brief Constructor that sets the iterator to the first item.
+      ///
+      /// Constructor that sets the iterator to the first item.
+      explicit GraphItemIt(const GR&) {}
+      /// \brief Constructor for conversion from \c INVALID.
+      ///
+      /// Constructor for conversion from \c INVALID.
+      /// It initializes the iterator to be invalid.
       /// \sa Invalid for more details.
       GraphItemIt(Invalid) {}
+      /// \brief Assign operator for items.
       ///
       /// The items are assignable.
       ///
+      /// \brief Assignment operator.
+      ///
+      /// Assignment operator for the iterator.
       GraphItemIt& operator=(const GraphItemIt&) { return *this; }
+      /// \brief Next item.
+      ///
+      /// Assign the iterator to the next item.
+      ///
+      /// \brief Increment the iterator.
+      ///
+      /// This operator increments the iterator, i.e. assigns it to the
+      /// next item.
       GraphItemIt& operator++() { return *this; }
       /// \brief Equality operator
       ///
+      /// Equality operator.
       /// Two iterators are equal if and only if they point to the
       /// same object or both are invalid.
       bool operator==(const GraphItemIt&) const { return true;}
       /// \brief Inequality operator
       ///
+      /// \sa operator==(Node n)
+      ///
+      /// Inequality operator.
+      /// Two iterators are equal if and only if they point to the
+      /// same object or both are invalid.
       bool operator!=(const GraphItemIt&) const { return true;}
 …
       struct Constraints {
         void constraints() {
+          checkConcept<GraphItem<>, _GraphItemIt>();
           _GraphItemIt it1(g);
           _GraphItemIt it2;
+          _GraphItemIt it3 = it1;
+          _GraphItemIt it4 = INVALID;
           it2 = ++it1;
 …
           ++(++it1);
           _Item bi = it1;
+          Item bi = it1;
           bi = it2;
+        }
+        _Graph& g;
+      };
+    };
+    /// \brief Skeleton class for graph InArcIt and OutArcIt
+    ///
+    /// \note Because InArcIt and OutArcIt may not inherit from the same
+    /// base class, the _selector is a additional template parameter. For
+    /// InArcIt you should instantiate it with character 'i' and for
+    /// OutArcIt with 'o'.
+    template <typename _Graph,
+              typename _Item = typename _Graph::Arc,
+              typename _Base = typename _Graph::Node,
+              char _selector = '0'>
+    class GraphIncIt : public _Item {
+        const GR& g;
+      };
+    };
+    /// \brief Concept class for \c InArcIt, \c OutArcIt and
+    /// \c IncEdgeIt types.
+    ///
+    /// This class describes the concept of \c InArcIt, \c OutArcIt
+    /// and \c IncEdgeIt subtypes of digraph and graph types.
+    ///
+    /// \note Since these iterator classes do not inherit from the same
+    /// base class, there is an additional template parameter (selector)
+    /// \c sel. For \c InArcIt you should instantiate it with character
+    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
+    template <typename GR,
+              typename Item = typename GR::Arc,
+              typename Base = typename GR::Node,
+              char sel = '0'>
+    class GraphIncIt : public Item {
     public:
       /// \brief Default constructor.
       ///
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      /// Default constructor.
+      /// \warning The default constructor is not required to set
+      /// the iterator to some well-defined value. So you should consider it
+      /// as uninitialized.
       GraphIncIt() {}
       /// \brief Copy constructor.
       ///
       /// Copy constructor.
+      ///
+      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
+      /// \brief Sets the iterator to the first arc incoming into or outgoing
+      /// from the node.
+      ///
+      /// Sets the iterator to the first arc incoming into or outgoing
+      /// from the node.
+      ///
+      explicit GraphIncIt(const _Graph&, const _Base&) {}
+      /// \brief Invalid constructor \& conversion.
+      ///
+      /// This constructor initializes the item to be invalid.
+      GraphIncIt(const GraphIncIt& it) : Item(it) {}
+      /// \brief Constructor that sets the iterator to the first
+      /// incoming or outgoing arc.
+      ///
+      /// Constructor that sets the iterator to the first arc
+      /// incoming to or outgoing from the given node.
+      explicit GraphIncIt(const GR&, const Base&) {}
+      /// \brief Constructor for conversion from \c INVALID.
+      ///
+      /// Constructor for conversion from \c INVALID.
+      /// It initializes the iterator to be invalid.
       /// \sa Invalid for more details.
       GraphIncIt(Invalid) {}
+      /// \brief Assign operator for iterators.
+      ///
+      /// The iterators are assignable.
+      ///
+      GraphIncIt& operator=(GraphIncIt const&) { return *this; }
+      /// \brief Next item.
+      ///
+      /// Assign the iterator to the next item.
+      ///
+      /// \brief Assignment operator.
+      ///
+      /// Assignment operator for the iterator.
+      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
+      /// \brief Increment the iterator.
+      ///
+      /// This operator increments the iterator, i.e. assigns it to the
+      /// next arc incoming to or outgoing from the given node.
       GraphIncIt& operator++() { return *this; }
       /// \brief Equality operator
       ///
+      /// Equality operator.
       /// Two iterators are equal if and only if they point to the
       /// same object or both are invalid.
 …
       /// \brief Inequality operator
       ///
+      /// \sa operator==(Node n)
+      ///
+      /// Inequality operator.
+      /// Two iterators are equal if and only if they point to the
+      /// same object or both are invalid.
       bool operator!=(const GraphIncIt&) const { return true;}
 …
       struct Constraints {
         void constraints() {
           checkConcept<GraphItem<_selector>, _GraphIncIt>();
+          checkConcept<GraphItem<sel>, _GraphIncIt>();
           _GraphIncIt it1(graph, node);
           _GraphIncIt it2;
+          _GraphIncIt it3 = it1;
+          _GraphIncIt it4 = INVALID;
           it2 = ++it1;
           ++it2 = it1;
           ++(++it1);
           _Item e = it1;
+          Item e = it1;
           e = it2;
+        }
+        _Item arc;
+        _Base node;
+        _Graph graph;
+        _GraphIncIt it;
+      };
+    };
+    /// \brief An empty iterable digraph class.
+    ///
+    /// This class provides beside the core digraph features
+    /// iterator based iterable interface for the digraph structure.
+        }
+        const Base& node;
+        const GR& graph;
+      };
+    };
+    /// \brief Skeleton class for iterable directed graphs.
+    ///
+    /// This class describes the interface of iterable directed
+    /// graphs. It extends \ref BaseDigraphComponent with the core
+    /// iterable interface.
     /// This concept is part of the Digraph concept.
     template <typename _Base = BaseDigraphComponent>
     class IterableDigraphComponent : public _Base {
     public:
       typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class IterableDigraphComponent : public BAS {
+    public:
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
 …
       typedef IterableDigraphComponent Digraph;
       /// \name Base iteration
       ///
       /// This interface provides functions for iteration on digraph items
+      /// \name Base Iteration
+      ///
+      /// This interface provides functions for iteration on digraph items.
       ///
       /// @{
+      /// \brief Gives back the first node in the iterating order.
+      ///
+      /// Gives back the first node in the iterating order.
+      ///
+      /// \brief Return the first node.
+      ///
+      /// This function gives back the first node in the iteration order.
       void first(Node&) const {}
+      /// \brief Gives back the next node in the iterating order.
+      ///
+      /// Gives back the next node in the iterating order.
+      ///
+      /// \brief Return the next node.
+      ///
+      /// This function gives back the next node in the iteration order.
       void next(Node&) const {}
+      /// \brief Gives back the first arc in the iterating order.
+      ///
+      /// Gives back the first arc in the iterating order.
+      ///
+      /// \brief Return the first arc.
+      ///
+      /// This function gives back the first arc in the iteration order.
       void first(Arc&) const {}
+      /// \brief Gives back the next arc in the iterating order.
+      ///
+      /// Gives back the next arc in the iterating order.
+      ///
+      /// \brief Return the next arc.
+      ///
+      /// This function gives back the next arc in the iteration order.
       void next(Arc&) const {}
+      /// \brief Gives back the first of the arcs point to the given
+      /// node.
+      ///
+      /// Gives back the first of the arcs point to the given node.
+      ///
+      /// \brief Return the first arc incomming to the given node.
+      ///
+      /// This function gives back the first arc incomming to the
+      /// given node.
       void firstIn(Arc&, const Node&) const {}
+      /// \brief Gives back the next of the arcs points to the given
+      /// node.
+      ///
+      /// Gives back the next of the arcs points to the given node.
+      ///
+      /// \brief Return the next arc incomming to the given node.
+      ///
+      /// This function gives back the next arc incomming to the
+      /// given node.
       void nextIn(Arc&) const {}
+      /// \brief Gives back the first of the arcs start from the
+      /// \brief Return the first arc outgoing form the given node.
+      ///
+      /// This function gives back the first arc outgoing form the
       /// given node.
-      ///
-      /// Gives back the first of the arcs start from the given node.
-      ///
       void firstOut(Arc&, const Node&) const {}
+      /// \brief Gives back the next of the arcs start from the given
+      /// node.
+      ///
+      /// Gives back the next of the arcs start from the given node.
+      ///
+      /// \brief Return the next arc outgoing form the given node.
+      ///
+      /// This function gives back the next arc outgoing form the
+      /// given node.
       void nextOut(Arc&) const {}
       /// @}
       /// \name Class based iteration
       ///
       /// This interface provides functions for iteration on digraph items
+      /// \name Class Based Iteration
+      ///
+      /// This interface provides iterator classes for digraph items.
       ///
       /// @{
 …
       typedef GraphItemIt<Digraph, Node> NodeIt;
       /// \brief This iterator goes through each node.
       ///
       /// This iterator goes through each node.
+      /// \brief This iterator goes through each arc.
+      ///
+      /// This iterator goes through each arc.
       ///
       typedef GraphItemIt<Digraph, Arc> ArcIt;
 …
       /// \brief This iterator goes trough the incoming arcs of a node.
       ///
       /// This iterator goes trough the \e inccoming arcs of a certain node
+      /// This iterator goes trough the \e incoming arcs of a certain node
       /// of a digraph.
       typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
 …
       /// \brief The base node of the iterator.
       ///
       /// Gives back the base node of the iterator.
       /// It is always the target of the pointed arc.
+      /// This function gives back the base node of the iterator.
+      /// It is always the target node of the pointed arc.
       Node baseNode(const InArcIt&) 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.
+      /// This function gives back the running node of the iterator.
+      /// It is always the source node of the pointed arc.
       Node runningNode(const InArcIt&) 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.
+      /// This function gives back the base node of the iterator.
+      /// It is always the source node of the pointed arc.
       Node baseNode(const OutArcIt&) 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.
+      /// This function gives back the running node of the iterator.
+      /// It is always the target node of the pointed arc.
       Node runningNode(const OutArcIt&) const { return INVALID; }
 …
             typename _Digraph::Node n;
             typename _Digraph::InArcIt ieit(INVALID);
             typename _Digraph::OutArcIt oeit(INVALID);
             n = digraph.baseNode(ieit);
             n = digraph.runningNode(ieit);
             n = digraph.baseNode(oeit);
             n = digraph.runningNode(oeit);
+            const typename _Digraph::InArcIt iait(INVALID);
+            const typename _Digraph::OutArcIt oait(INVALID);
+            n = digraph.baseNode(iait);
+            n = digraph.runningNode(iait);
+            n = digraph.baseNode(oait);
+            n = digraph.runningNode(oait);
             ignore_unused_variable_warning(n);
+          }
 …
         const _Digraph& digraph;
       };
+    };
     /// \brief An empty iterable undirected graph class.
     ///
     /// This class provides beside the core graph features iterator
     /// based iterable interface for the undirected graph structure.
+      };
+    };
+    /// \brief Skeleton class for iterable undirected graphs.
+    ///
+    /// This class describes the interface of iterable undirected
+    /// graphs. It extends \ref IterableDigraphComponent with the core
+    /// iterable interface of undirected graphs.
     /// This concept is part of the Graph concept.
     template <typename _Base = BaseGraphComponent>
     class IterableGraphComponent : public IterableDigraphComponent<_Base> {
     public:
       typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
+    public:
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
 …
       typedef IterableGraphComponent Graph;
+      /// \name Base iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      /// \name Base Iteration
+      ///
+      /// This interface provides functions for iteration on edges.
+      ///
       /// @{
+      using IterableDigraphComponent<_Base>::first;
+      using IterableDigraphComponent<_Base>::next;
+      /// \brief Gives back the first edge in the iterating
+      /// order.
+      ///
+      /// Gives back the first edge in the iterating order.
+      ///
+      using IterableDigraphComponent<Base>::first;
+      using IterableDigraphComponent<Base>::next;
+      /// \brief Return the first edge.
+      ///
+      /// This function gives back the first edge in the iteration order.
       void first(Edge&) const {}
+      /// \brief Gives back the next edge in the iterating
+      /// order.
+      ///
+      /// Gives back the next edge in the iterating order.
+      ///
+      /// \brief Return the next edge.
+      ///
+      /// This function gives back the next edge in the iteration order.
       void next(Edge&) const {}
+      /// \brief Gives back the first of the edges from the
+      /// \brief Return the first edge incident to the given node.
+      ///
+      /// This function gives back the first edge incident to the given
+      /// node. The bool parameter gives back the direction for which the
+      /// source node of the directed arc representing the edge is the
       /// given node.
-      ///
-      /// Gives back the first of the edges from the given
-      /// node. The bool parameter gives back that direction which
-      /// gives a good direction of the edge so the source of the
-      /// directed arc is the given node.
       void firstInc(Edge&, bool&, const Node&) const {}
 …
       /// given node.
       ///
+      /// Gives back the next of the edges from the given
+      /// node. The bool parameter should be used as the \c firstInc()
+      /// use it.
+      /// This function gives back the next edge incident to the given
+      /// node. The bool parameter should be used as \c firstInc() use it.
       void nextInc(Edge&, bool&) const {}
       using IterableDigraphComponent<_Base>::baseNode;
       using IterableDigraphComponent<_Base>::runningNode;
+      using IterableDigraphComponent<Base>::baseNode;
+      using IterableDigraphComponent<Base>::runningNode;
       /// @}
       /// \name Class based iteration
       ///
       /// This interface provides functions for iteration on graph items
+      /// \name Class Based Iteration
+      ///
+      /// This interface provides iterator classes for edges.
       ///
       /// @{
       /// \brief This iterator goes through each node.
       ///
       /// This iterator goes through each node.
+      /// \brief This iterator goes through each edge.
+      ///
+      /// This iterator goes through each edge.
       typedef GraphItemIt<Graph, Edge> EdgeIt;
+      /// \brief This iterator goes trough the incident arcs of a
+      /// \brief This iterator goes trough the incident edges of a
       /// node.
       ///
       /// This iterator goes trough the incident arcs of a certain
+      /// This iterator goes trough the incident edges of a certain
       /// node of a graph.
+      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
+      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
       /// \brief The base node of the iterator.
       ///
       /// Gives back the base node of the iterator.
+      /// This function gives back the base node of the iterator.
       Node baseNode(const IncEdgeIt&) const { return INVALID; }
       /// \brief The running node of the iterator.
       ///
       /// Gives back the running node of the iterator.
+      /// This function gives back the running node of the iterator.
       Node runningNode(const IncEdgeIt&) const { return INVALID; }
 …
               typename _Graph::EdgeIt >();
             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
               typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
+              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
             typename _Graph::Node n;
             typename _Graph::IncEdgeIt ueit(INVALID);
             n = graph.baseNode(ueit);
             n = graph.runningNode(ueit);
+            const typename _Graph::IncEdgeIt ieit(INVALID);
+            n = graph.baseNode(ieit);
+            n = graph.runningNode(ieit);
+          }
+        }
         const _Graph& graph;

Context Navigation

Changes in / [548:41bdb4d6c8c3:856:c05bb175d3ee] in lemon

Legend: