Changes in / [1087:b96574ff36ec:1089:2b47dbd6612c] in lemon

Files:

• .hgignore (modified) (2 diffs)
• .hgtags (added)
• CMakeLists.txt (modified) (5 diffs)
• INSTALL (modified) (3 diffs)
• LICENSE (modified) (1 diff)
• Makefile.am (modified) (4 diffs)
• NEWS (modified) (1 diff)
• README (modified) (1 diff)
• cmake/FindCOIN.cmake (added)
• cmake/FindCPLEX.cmake (added)
• cmake/FindGLPK.cmake (added)
• cmake/LEMONConfig.cmake.in (added)
• cmake/version.cmake.in (modified) (1 diff)
• configure.ac (modified) (5 diffs)
• demo/CMakeLists.txt (modified) (1 diff)
• demo/Makefile.am (modified) (1 diff)
• demo/arg_parser_demo.cc (modified) (1 diff)
• demo/graph_to_eps_demo.cc (modified) (9 diffs)
• demo/lgf_demo.cc (modified) (1 diff)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/Doxyfile.in (modified) (15 diffs)
• doc/DoxygenLayout.xml (modified) (1 diff)
• doc/Makefile.am (modified) (6 diffs)
• doc/coding_style.dox (modified) (1 diff)
• doc/dirs.dox (modified) (2 diffs)
• doc/groups.dox (modified) (29 diffs)
• doc/images/bipartite_matching.eps (added)
• doc/images/bipartite_partitions.eps (added)
• doc/images/connected_components.eps (added)
• doc/images/edge_biconnected_components.eps (added)
• doc/images/grid_graph.eps (added)
• doc/images/node_biconnected_components.eps (added)
• doc/images/strongly_connected_components.eps (added)
• doc/lgf.dox (modified) (1 diff)
• doc/license.dox (modified) (1 diff)
• doc/mainpage.dox (deleted)
• doc/mainpage.dox.in (added)
• doc/migration.dox (modified) (3 diffs)
• doc/min_cost_flow.dox (added)
• doc/named-param.dox (modified) (1 diff)
• doc/namespaces.dox (modified) (1 diff)
• doc/template.h (modified) (1 diff)
• lemon/CMakeLists.txt (modified) (3 diffs)
• lemon/Makefile.am (modified) (3 diffs)
• lemon/adaptors.h (added)
• lemon/arg_parser.cc (modified) (1 diff)
• lemon/arg_parser.h (modified) (1 diff)
• lemon/assert.h (modified) (1 diff)
• lemon/base.cc (modified) (2 diffs)
• lemon/bfs.h (modified) (39 diffs)
• lemon/bin_heap.h (modified) (21 diffs)
• lemon/bits/alteration_notifier.h (modified) (4 diffs)
• lemon/bits/array_map.h (modified) (13 diffs)
• lemon/bits/base_extender.h (deleted)
• lemon/bits/bezier.h (modified) (1 diff)
• lemon/bits/default_map.h (modified) (2 diffs)
• lemon/bits/edge_set_extender.h (added)
• lemon/bits/enable_if.h (modified) (1 diff)
• lemon/bits/graph_adaptor_extender.h (added)
• lemon/bits/graph_extender.h (modified) (8 diffs)
• lemon/bits/map_extender.h (modified) (12 diffs)
• lemon/bits/path_dump.h (modified) (2 diffs)
• lemon/bits/solver_bits.h (added)
• lemon/bits/traits.h (modified) (5 diffs)
• lemon/bits/variant.h (added)
• lemon/bits/vector_map.h (modified) (14 diffs)
• lemon/bits/windows.cc (modified) (3 diffs)
• lemon/bits/windows.h (modified) (1 diff)
• lemon/bucket_heap.h (added)
• lemon/cbc.cc (added)
• lemon/cbc.h (added)
• lemon/circulation.h (added)
• lemon/clp.cc (added)
• lemon/clp.h (added)
• lemon/color.cc (modified) (1 diff)
• lemon/color.h (modified) (1 diff)
• lemon/concept_check.h (modified) (1 diff)
• lemon/concepts/digraph.h (modified) (8 diffs)
• lemon/concepts/graph.h (modified) (13 diffs)
• lemon/concepts/graph_components.h (modified) (56 diffs)
• lemon/concepts/heap.h (modified) (7 diffs)
• lemon/concepts/maps.h (modified) (4 diffs)
• lemon/concepts/path.h (modified) (6 diffs)
• lemon/config.h.cmake (modified) (1 diff)
• lemon/config.h.in (modified) (2 diffs)
• lemon/connectivity.h (added)
• lemon/core.h (modified) (29 diffs)
• lemon/counter.h (modified) (1 diff)
• lemon/cplex.cc (added)
• lemon/cplex.h (added)
• lemon/dfs.h (modified) (43 diffs)
• lemon/dijkstra.h (modified) (46 diffs)
• lemon/dim2.h (modified) (1 diff)
• lemon/dimacs.h (added)
• lemon/edge_set.h (added)
• lemon/elevator.h (added)
• lemon/error.h (modified) (1 diff)
• lemon/euler.h (added)
• lemon/fib_heap.h (added)
• lemon/full_graph.h (added)
• lemon/glpk.cc (added)
• lemon/glpk.h (added)
• lemon/gomory_hu.h (added)
• lemon/graph_to_eps.h (modified) (11 diffs)
• lemon/grid_graph.h (added)
• lemon/hao_orlin.h (added)
• lemon/hypercube_graph.h (added)
• lemon/kruskal.h (modified) (6 diffs)
• lemon/lemon.pc.cmake (added)
• lemon/lemon.pc.in (modified) (1 diff)
• lemon/lgf_reader.h (modified) (45 diffs)
• lemon/lgf_writer.h (modified) (39 diffs)
• lemon/list_graph.h (modified) (11 diffs)
• lemon/lp.h (added)
• lemon/lp_base.cc (added)
• lemon/lp_base.h (added)
• lemon/lp_skeleton.cc (added)
• lemon/lp_skeleton.h (added)
• lemon/maps.h (modified) (75 diffs)
• lemon/matching.h (added)
• lemon/math.h (modified) (2 diffs)
• lemon/min_cost_arborescence.h (added)
• lemon/nauty_reader.h (added)
• lemon/network_simplex.h (added)
• lemon/path.h (modified) (17 diffs)
• lemon/preflow.h (added)
• lemon/radix_heap.h (added)
• lemon/radix_sort.h (added)
• lemon/random.cc (modified) (1 diff)
• lemon/random.h (modified) (13 diffs)
• lemon/smart_graph.h (modified) (15 diffs)
• lemon/soplex.cc (added)
• lemon/soplex.h (added)
• lemon/suurballe.h (added)
• lemon/time_measure.h (modified) (3 diffs)
• lemon/tolerance.h (modified) (1 diff)
• lemon/unionfind.h (modified) (11 diffs)
• m4/lx_check_coin.m4 (added)
• m4/lx_check_cplex.m4 (modified) (1 diff)
• m4/lx_check_glpk.m4 (modified) (2 diffs)
• m4/lx_check_soplex.m4 (modified) (3 diffs)
• scripts/chg-len.py (modified) (2 diffs)
• scripts/mk-release.sh (modified) (1 diff)
• scripts/unify-sources.sh (modified) (4 diffs)
• test/CMakeLists.txt (modified) (2 diffs)
• test/Makefile.am (modified) (1 diff)
• test/adaptors_test.cc (added)
• test/bfs_test.cc (modified) (4 diffs)
• test/circulation_test.cc (added)
• test/connectivity_test.cc (added)
• test/counter_test.cc (modified) (4 diffs)
• test/dfs_test.cc (modified) (5 diffs)
• test/digraph_test.cc (modified) (7 diffs)
• test/dijkstra_test.cc (modified) (4 diffs)
• test/dim_test.cc (modified) (1 diff)
• test/edge_set_test.cc (added)
• test/error_test.cc (modified) (1 diff)
• test/euler_test.cc (added)
• test/gomory_hu_test.cc (added)
• test/graph_copy_test.cc (modified) (4 diffs)
• test/graph_test.cc (modified) (8 diffs)
• test/graph_test.h (modified) (2 diffs)
• test/graph_utils_test.cc (modified) (5 diffs)
• test/hao_orlin_test.cc (added)
• test/heap_test.cc (modified) (3 diffs)
• test/kruskal_test.cc (modified) (2 diffs)
• test/lgf_test.cc (modified) (4 diffs)
• test/lp_test.cc (added)
• test/maps_test.cc (modified) (7 diffs)
• test/matching_test.cc (added)
• test/min_cost_arborescence_test.cc (added)
• test/min_cost_flow_test.cc (added)
• test/mip_test.cc (added)
• test/path_test.cc (modified) (1 diff)
• test/preflow_test.cc (added)
• test/radix_sort_test.cc (added)
• test/random_test.cc (modified) (1 diff)
• test/suurballe_test.cc (added)
• test/test_tools.h (modified) (1 diff)
• test/test_tools_fail.cc (modified) (1 diff)
• test/test_tools_pass.cc (modified) (1 diff)
• test/time_measure_test.cc (modified) (2 diffs)
• test/unionfind_test.cc (modified) (1 diff)
• tools/CMakeLists.txt (added)
• tools/Makefile.am (modified) (1 diff)
• tools/dimacs-solver.cc (added)
• tools/dimacs-to-lgf.cc (added)
• tools/lemon-0.x-to-1.x.sh (modified) (1 diff)
• tools/lgf-gen.cc (added)

.hgignore

@@ -23 +23 @@
 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
@@ -36 +41 @@
 ^autom4te.cache/.*
 ^build-aux/.*
-^objs.*/.*
+^.*objs.*/.*
 ^test/[a-z_]*$
+^tools/[a-z-_]*$
 ^demo/.*_demo$
-^build/.*
+^.*build.*/.*
 ^doc/gen-images/.*
 CMakeFiles

CMakeLists.txt

@@ -1 +1 @@
 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)
-
-INCLUDE(FindDoxygen)
-INCLUDE(FindGhostscript)
-
-ADD_DEFINITIONS(-DHAVE_CONFIG_H)
+INCLUDE(FindPythonInterp)
+INCLUDE(FindWget)
+
+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 ${PYTHON_EXECUTABLE} ./scripts/chg-len.py
+    WORKING_DIRECTORY ${PROJECT_SOURCE_DIR}
+    OUTPUT_VARIABLE HG_REVISION_PATH
+    ERROR_QUIET
+    OUTPUT_STRIP_TRAILING_WHITESPACE
+  )
+  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_ID "hg-tip")
+  ELSE()
+    IF(HG_REVISION_PATH STREQUAL "")
+      SET(HG_REVISION_ID ${HG_REVISION})
+    ELSE()
+      SET(HG_REVISION_ID ${HG_REVISION_PATH}.${HG_REVISION})
+    ENDIF()
+  ENDIF()
+  SET(LEMON_VERSION ${HG_REVISION_ID} CACHE STRING "LEMON version string.")
+ENDIF()
+
+SET(PROJECT_VERSION ${LEMON_VERSION})
+
+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)
+
+IF(DEFINED ENV{LEMON_CXX_WARNING})
+  SET(CXX_WARNING $ENV{LEMON_CXX_WARNING})
+ELSE()
+  IF(CMAKE_COMPILER_IS_GNUCXX)
+    SET(CXX_WARNING "-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 -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
+    SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
+    SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")
+  ELSEIF(MSVC)
+    # This part is unnecessary 'casue the same is set by the lemon/core.h.
+    # Still keep it as an example.
+    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
+    # Suppressed warnings:
+    # C4250: 'class1' : inherits 'class2::member' via dominance
+    # C4355: 'this' : used in base member initializer list
+    # C4503: 'function' : decorated name length exceeded, name was truncated
+    # C4800: 'type' : forcing value to bool 'true' or 'false'
+    #        (performance warning)
+    # C4996: 'function': was declared deprecated
+  ELSE()
+    SET(CXX_WARNING "-Wall -W")
+  ENDIF()
+ENDIF()
+SET(LEMON_CXX_WARNING_FLAGS ${CXX_WARNING} CACHE STRING "LEMON warning flags.")
+
+SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
+
+SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
+    "Flags used by the C++ compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
+    "Flags used by the C compiler during maintainer builds."
+    FORCE )
+SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "Flags used for linking binaries during maintainer builds."
+    FORCE )
+SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
+    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "Flags used by the shared libraries linker during maintainer builds."
+    FORCE )
+MARK_AS_ADVANCED(
+    CMAKE_CXX_FLAGS_MAINTAINER
+    CMAKE_C_FLAGS_MAINTAINER
+    CMAKE_EXE_LINKER_FLAGS_MAINTAINER
+    CMAKE_SHARED_LINKER_FLAGS_MAINTAINER )
+
+IF(CMAKE_CONFIGURATION_TYPES)
+  LIST(APPEND CMAKE_CONFIGURATION_TYPES Maintainer)
+  LIST(REMOVE_DUPLICATES CMAKE_CONFIGURATION_TYPES)
+  SET(CMAKE_CONFIGURATION_TYPES "${CMAKE_CONFIGURATION_TYPES}" CACHE STRING
+      "Add the configurations that we need"
+      FORCE)
+ endif()
+
+IF(NOT CMAKE_BUILD_TYPE)
+  SET(CMAKE_BUILD_TYPE "Release")
+ENDIF()
+
+SET( CMAKE_BUILD_TYPE "${CMAKE_BUILD_TYPE}" CACHE STRING
+    "Choose the type of build, options are: None(CMAKE_CXX_FLAGS or CMAKE_C_FLAGS used) Debug Release RelWithDebInfo MinSizeRel Maintainer."
+    FORCE )
+
 
 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()
 
+IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer")
+  ADD_CUSTOM_TARGET(check ALL COMMAND ${CMAKE_CTEST_COMMAND})
+ELSE()
+  ADD_CUSTOM_TARGET(check COMMAND ${CMAKE_CTEST_COMMAND})
+ENDIF()
+
 ADD_SUBDIRECTORY(lemon)
-ADD_SUBDIRECTORY(demo)
-ADD_SUBDIRECTORY(doc)
-ADD_SUBDIRECTORY(test)
-
-IF(WIN32)
+IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
+  ADD_SUBDIRECTORY(demo)
+  ADD_SUBDIRECTORY(tools)
+  ADD_SUBDIRECTORY(doc)
+  ADD_SUBDIRECTORY(test)
+ENDIF()
+
+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})
   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})
@@ -41 +162 @@
     "${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")
 
@@ -51 +173 @@
   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")
@@ -72 +196 @@
 
   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}")
@@ -89 +213 @@
 
   INCLUDE(CPack)
-ENDIF(WIN32)
+ENDIF()

INSTALL

@@ -28 +28 @@
 
       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.
 
    4. `make check'
@@ -75 +75 @@
 
   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
@@ -159 +151 @@
 
    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

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

Makefile.am

@@ -1 +1 @@
 ACLOCAL_AMFLAGS = -I m4
+
+AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 
 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
@@ -10 +12 @@
         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/LEMONConfig.cmake.in \
         cmake/version.cmake.in \
         cmake/version.cmake \
@@ -37 +44 @@
 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 = \
@@ -66 +77 @@
         bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2
 
-.PHONY: mrproper dist-bz2 distcheck-bz2
+.PHONY: demo mrproper dist-bz2 distcheck-bz2

NEWS

@@ +1 @@
+2011-08-08 Version 1.1.4 released
+
+        Bugfix release.
+
+        #392: Bug fix in Dfs::start(s,t)
+        #414: Fix wrong initialization in Preflow
+        #404: Update Doxygen configuration
+        #416: Support tests with valgrind
+        #418: Better Win CodeBlock/MinGW support
+        #419: Backport build environment improvements from the main branch
+              - Build of mip_test and lp_test precede the running of the tests
+              - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
+              - Do not look for COIN_VOL libraries
+        #382: Allow lgf file without Arc maps
+        
+2010-10-21 Version 1.1.3 released
+
+        Bugfix release.
+
+        #366: Fix Pred[Matrix]MapPath::empty()
+        #371: Bug fix in (di)graphCopy()
+              The target graph is cleared before adding nodes and arcs/edges.
+
+        #356: Fix multiple execution bug in weighted matchings
+        #364: Add missing UndirectedTags
+        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
+        #372: Fix a critical bug in preflow
+
+2010-03-08 Version 1.1.2 released
+
+        Bugfix release.
+
+        #317: Fix (and improve) error message in mip_test.cc
+              Remove unnecessary OsiCbc dependency
+        #250: Fix in pathSource() and pathTarget()
+        #322: Distribute LEMONConfig.cmake.in
+        #321: Use pathCopy(from,to) instead of copyPath(to,from)
+        #330: Bug fix in map_extender.h
+        #335: Fix clear() function in ExtendFindEnum
+        #337: Use void* as LPX object pointer
+        #336: Fix the date field comment of graphToEps() output
+        #323: Bug fix in Suurballe
+
+2009-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
+
+2009-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)
+
 2009-03-27 LEMON joins to the COIN-OR initiative
 

README

@@ -1 @@
-==================================================================
-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

@@ -1 @@
-SET(PROJECT_NAME "@PACKAGE_NAME@")
-SET(PROJECT_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")
+SET(LEMON_VERSION "@PACKAGE_VERSION@" CACHE STRING "LEMON version string.")

configure.ac

@@ -3 +3 @@
 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])
@@ -20 +23 @@
 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.
@@ -53 +56 @@
 
 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.
@@ -104 +99 @@
 dnl Add dependencies on files generated by configure.
 AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
-  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
+  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/doc/mainpage.dox.in $(top_srcdir)/lemon/lemon.pc.in $(top_srcdir)/cmake/version.cmake.in'])
 
 AC_CONFIG_FILES([
 Makefile
+demo/Makefile
 cmake/version.cmake
 doc/Doxyfile
+doc/mainpage.dox
 lemon/lemon.pc
 ])
@@ -121 +118 @@
 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

@@ -1 +1 @@
 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

@@ -1 @@
-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

@@ -3 +3 @@
  * 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).

demo/graph_to_eps_demo.cc

@@ -3 +3 @@
  * 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).
@@ -86 +86 @@
     coords(coords).
     title("Sample .eps figure").
-    copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     run();
 
@@ -93 +93 @@
     coords(coords).
     title("Sample .eps figure").
-    copyright("(C) 2003-2008 LEMON Project").
+    copyright("(C) 2003-2009 LEMON Project").
     absoluteNodeSizes().absoluteArcWidths().
     nodeScale(2).nodeSizes(sizes).
@@ -106 +106 @@
   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)).
@@ -133 +133 @@
   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).
@@ -148 +148 @@
   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).
@@ -164 +164 @@
   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().
@@ -183 +183 @@
   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();
@@ -194 +194 @@
     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

@@ -3 +3 @@
  * 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).

doc/CMakeLists.txt

@@ -1 +1 @@
 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})
+
+SET(LEMON_DOC_SOURCE_BROWSER "NO" CACHE STRING "Include source into the doc (YES/NO).")
 
 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
+)
+
+CONFIGURE_FILE(
+  ${PROJECT_SOURCE_DIR}/doc/mainpage.dox.in
+  ${PROJECT_BINARY_DIR}/doc/mainpage.dox
+  @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()
+
+IF(WGET_FOUND)
+ADD_CUSTOM_TARGET(update-external-tags
+  COMMAND ${CMAKE_COMMAND} -E make_directory dl
+  # COMMAND ${CMAKE_COMMAND} -E copy libstdc++.tag dl
+  COMMAND ${WGET_EXECUTABLE} wget -P dl -N libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E rename dl/libstdc++.tag libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove dl/libstdc++.tag
+  COMMAND ${CMAKE_COMMAND} -E remove_directory dl
+  WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+  )
+ENDIF()

doc/Doxyfile.in

@@ -1 @@
-# Doxyfile 1.5.7.1
+# Doxyfile 1.7.3
 
 #---------------------------------------------------------------------------
@@ -5 +5 @@
 #---------------------------------------------------------------------------
 DOXYFILE_ENCODING      = UTF-8
-PROJECT_NAME           = @PACKAGE_NAME@
-PROJECT_NUMBER         = @PACKAGE_VERSION@
+PROJECT_NAME           = 
+PROJECT_NUMBER         = 
+PROJECT_BRIEF          =
+PROJECT_LOGO           =
 OUTPUT_DIRECTORY       = 
 CREATE_SUBDIRS         = NO
@@ -22 +24 @@
 QT_AUTOBRIEF           = NO
 MULTILINE_CPP_IS_BRIEF = NO
-DETAILS_AT_TOP         = YES
 INHERIT_DOCS           = NO
 SEPARATE_MEMBER_PAGES  = NO
@@ -31 +32 @@
 OPTIMIZE_FOR_FORTRAN   = NO
 OPTIMIZE_OUTPUT_VHDL   = NO
+EXTENSION_MAPPING      =
 BUILTIN_STL_SUPPORT    = YES
 CPP_CLI_SUPPORT        = NO
@@ -56 +58 @@
 HIDE_SCOPE_NAMES       = YES
 SHOW_INCLUDE_FILES     = YES
+FORCE_LOCAL_INCLUDES   = NO
 INLINE_INFO            = YES
 SORT_MEMBER_DOCS       = NO
 SORT_BRIEF_DOCS        = NO
+SORT_MEMBERS_CTORS_1ST = NO
 SORT_GROUP_NAMES       = NO
 SORT_BY_SCOPE_NAME     = NO
+STRICT_PROTO_MATCHING  = NO
 GENERATE_TODOLIST      = YES
 GENERATE_TESTLIST      = YES
@@ -67 +72 @@
 ENABLED_SECTIONS       = 
 MAX_INITIALIZER_LINES  = 5
-SHOW_USED_FILES        = YES
+SHOW_USED_FILES        = NO
 SHOW_DIRECTORIES       = YES
 SHOW_FILES             = YES
 SHOW_NAMESPACES        = YES
 FILE_VERSION_FILTER    = 
-LAYOUT_FILE            = DoxygenLayout.xml
+LAYOUT_FILE            = "@abs_top_srcdir@/doc/DoxygenLayout.xml"
 #---------------------------------------------------------------------------
 # configuration options related to warning and progress messages
@@ -92 +97 @@
                          "@abs_top_srcdir@/demo" \
                          "@abs_top_srcdir@/tools" \
-                         "@abs_top_srcdir@/test/test_tools.h"
+                         "@abs_top_srcdir@/test/test_tools.h" \
+                         "@abs_top_builddir@/doc/mainpage.dox"
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          = *.h \
@@ -112 +118 @@
 FILTER_PATTERNS        = 
 FILTER_SOURCE_FILES    = NO
+FILTER_SOURCE_PATTERNS =
 #---------------------------------------------------------------------------
 # configuration options related to source browsing
 #---------------------------------------------------------------------------
-SOURCE_BROWSER         = NO
+SOURCE_BROWSER         = @LEMON_DOC_SOURCE_BROWSER@
 INLINE_SOURCES         = NO
 STRIP_CODE_COMMENTS    = YES
@@ -138 +145 @@
 HTML_FOOTER            = 
 HTML_STYLESHEET        = 
+HTML_COLORSTYLE_HUE    = 220
+HTML_COLORSTYLE_SAT    = 100
+HTML_COLORSTYLE_GAMMA  = 80
+HTML_TIMESTAMP         = YES
 HTML_ALIGN_MEMBERS     = YES
-HTML_DYNAMIC_SECTIONS  = NO
+HTML_DYNAMIC_SECTIONS  = YES
 GENERATE_DOCSET        = NO
 DOCSET_FEEDNAME        = "Doxygen generated docs"
 DOCSET_BUNDLE_ID       = org.doxygen.Project
+DOCSET_PUBLISHER_ID    = org.doxygen.Publisher
+DOCSET_PUBLISHER_NAME  = Publisher
 GENERATE_HTMLHELP      = NO
 CHM_FILE               = 
@@ -154 +167 @@
 QHP_NAMESPACE          = org.doxygen.Project
 QHP_VIRTUAL_FOLDER     = doc
+QHP_CUST_FILTER_NAME   =
+QHP_CUST_FILTER_ATTRS  =
+QHP_SECT_FILTER_ATTRS  =
 QHG_LOCATION           = 
+GENERATE_ECLIPSEHELP   = NO
+ECLIPSE_DOC_ID         = org.doxygen.Project
 DISABLE_INDEX          = NO
 ENUM_VALUES_PER_LINE   = 4
 GENERATE_TREEVIEW      = NO
+USE_INLINE_TREES       = NO
 TREEVIEW_WIDTH         = 250
+EXT_LINKS_IN_WINDOW    = NO
 FORMULA_FONTSIZE       = 10
+FORMULA_TRANSPARENT    = YES
+USE_MATHJAX            = NO
+MATHJAX_RELPATH        = http://www.mathjax.org/mathjax
+SEARCHENGINE           = YES
+SERVER_BASED_SEARCH    = NO
 #---------------------------------------------------------------------------
 # configuration options related to the LaTeX output
@@ -176 +201 @@
 LATEX_BATCHMODE        = NO
 LATEX_HIDE_INDICES     = NO
+LATEX_SOURCE_CODE      = NO
 #---------------------------------------------------------------------------
 # configuration options related to the RTF output
@@ -224 +250 @@
 SKIP_FUNCTION_MACROS   = YES
 #---------------------------------------------------------------------------
-# Configuration::additions related to external references   
-#---------------------------------------------------------------------------
-TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
+# Configuration::additions related to external references
+#---------------------------------------------------------------------------
+TAGFILES               = "@abs_top_builddir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
 GENERATE_TAGFILE       = html/lemon.tag
 ALLEXTERNALS           = NO
@@ -238 +264 @@
 HIDE_UNDOC_RELATIONS   = YES
 HAVE_DOT               = YES
+DOT_NUM_THREADS        = 0
 DOT_FONTNAME           = FreeSans
 DOT_FONTSIZE           = 10
@@ -255 +282 @@
 DOT_PATH               = 
 DOTFILE_DIRS           = 
+MSCFILE_DIRS           =
 DOT_GRAPH_MAX_NODES    = 50
 MAX_DOT_GRAPH_DEPTH    = 0
@@ -261 +289 @@
 GENERATE_LEGEND        = YES
 DOT_CLEANUP            = YES
-#---------------------------------------------------------------------------
-# Configuration::additions related to the search engine   
-#---------------------------------------------------------------------------
-SEARCHENGINE           = NO

doc/DoxygenLayout.xml

@@ -3 +3 @@
   <navindex>
     <tab type="mainpage" visible="yes" title=""/>
-    <tab type="modules" visible="yes" title=""/>
+    <tab type="modules" visible="yes" title="" intro=""/>
     <tab type="classes" visible="yes" title="">
-      <tab type="classes" visible="yes" title=""/>
-      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/> 
-      <tab type="hierarchy" visible="yes" title=""/>
-      <tab type="classmembers" visible="yes" title=""/>
+      <tab type="classes" visible="yes" title="" intro=""/>
+      <tab type="classindex" visible="$ALPHABETICAL_INDEX" title=""/>
+      <tab type="hierarchy" visible="yes" title="" intro=""/>
+      <tab type="classmembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="namespaces" visible="yes" title="">
-      <tab type="namespaces" visible="yes" title=""/>
-      <tab type="namespacemembers" visible="yes" title=""/>
+      <tab type="namespaces" visible="yes" title="" intro=""/>
+      <tab type="namespacemembers" visible="yes" title="" intro=""/>
     </tab>
     <tab type="files" visible="yes" title="">
-      <tab type="files" visible="yes" title=""/>
-      <tab type="globals" visible="yes" title=""/>
+      <tab type="files" visible="yes" title="" intro=""/>
+      <tab type="globals" visible="yes" title="" intro=""/>
     </tab>
-    <tab type="dirs" visible="yes" title=""/>
-    <tab type="examples" visible="yes" title=""/>  
-    <tab type="pages" visible="yes" title=""/>
+    <tab type="dirs" visible="yes" title="" intro=""/>
+    <tab type="examples" visible="yes" title="" intro=""/>
+    <tab type="pages" visible="yes" title="" intro=""/>
   </navindex>
 

doc/Makefile.am

@@ -9 +9 @@
         doc/mainpage.dox \
         doc/migration.dox \
+        doc/min_cost_flow.dox \
         doc/named-param.dox \
         doc/namespaces.dox \
@@ -15 +16 @@
 
 DOC_EPS_IMAGES18 = \
+        grid_graph.eps \
         nodeshape_0.eps \
         nodeshape_1.eps \
@@ -21 +23 @@
         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 = \
@@ -38 +49 @@
         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; \
@@ -70 +92 @@
 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
 
@@ -81 +103 @@
         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

@@ -3 +3 @@
  * 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).

doc/dirs.dox

@@ -3 +3 @@
  * 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).
@@ -72 +72 @@
 \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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -17 +17 @@
  */
 
+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.
 */
 
@@ -61 +63 @@
 
 /**
-@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
 */
 
@@ -75 +143 @@
 \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
@@ -88 +156 @@
 \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".
 */
 
@@ -97 +168 @@
 \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',
@@ -156 +227 @@
 
 /**
-@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.
@@ -184 +247 @@
 \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.
 */
@@ -190 +253 @@
 /**
 @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.
 */
@@ -202 +265 @@
 \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).
 */
 
@@ -211 +274 @@
 \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.
 */
 
@@ -219 +287 @@
 \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.
 */
 
@@ -261 +334 @@
 \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.
 
@@ -298 +369 @@
 
 /**
-@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
@@ -353 +399 @@
 @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.
 */
 
@@ -364 +410 @@
 \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.
 */
@@ -391 +428 @@
 \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.
 */
 
@@ -425 +445 @@
 \brief Simple basic graph utilities.
 
-This group describes some simple basic graph utilities.
+This group contains some simple basic graph utilities.
 */
 
@@ -433 +453 @@
 \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.
 */
@@ -442 +462 @@
 \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.
 */
@@ -451 +471 @@
 \brief Exceptions defined in LEMON.
 
-This group describes the exceptions defined in LEMON.
+This group contains the exceptions defined in LEMON.
 */
 
@@ -458 +478 @@
 \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
@@ -465 +485 @@
 
 /**
-@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".
 */
@@ -478 +498 @@
 \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.
 */
 
@@ -486 +522 @@
 \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.
 
@@ -516 +552 @@
 \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.
 */
@@ -525 +561 @@
 \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.
 */
 
@@ -531 +567 @@
 \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.
@@ -549 +585 @@
 */
 
+}

doc/lgf.dox

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

doc/license.dox

@@ -3 +3 @@
  * 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).

doc/migration.dox

@@ -3 +3 @@
  * 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).
@@ -26 +26 @@
 
 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>.
 
@@ -54 +54 @@
 
 \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

@@ -3 +3 @@
  * 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).

doc/namespaces.dox

@@ -3 +3 @@
  * 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).

doc/template.h

@@ -3 +3 @@
  * 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).

lemon/CMakeLists.txt

@@ -1 +1 @@
 INCLUDE_DIRECTORIES(
-  ${CMAKE_SOURCE_DIR}
+  ${PROJECT_SOURCE_DIR}
   ${PROJECT_BINARY_DIR}
 )
@@ -9 +9 @@
 )
 
-ADD_LIBRARY(lemon
+CONFIGURE_FILE(
+  ${CMAKE_CURRENT_SOURCE_DIR}/lemon.pc.cmake
+  ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  @ONLY
+)
+
+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(
@@ -26 +65 @@
   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
+)
+
+INSTALL(
+  FILES ${CMAKE_CURRENT_BINARY_DIR}/lemon.pc
+  DESTINATION lib/pkgconfig
+)
+

lemon/Makefile.am

@@ -2 +2 @@
         lemon/lemon.pc.in \
         lemon/lemon.pc.cmake \
-        lemon/CMakeLists.txt
+        lemon/CMakeLists.txt \
+        lemon/config.h.cmake
 
 pkgconfig_DATA += lemon/lemon.pc
@@ -9 +10 @@
 
 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/bucket_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/fib_heap.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_heap.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
@@ -51 +116 @@
         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

@@ -3 +3 @@
  * 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).

lemon/arg_parser.h

@@ -3 +3 @@
  * 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).

lemon/assert.h

@@ -3 +3 @@
  * 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).

lemon/base.cc

@@ -3 +3 @@
  * 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).
@@ -24 +24 @@
 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

@@ -3 +3 @@
  * 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).
@@ -50 +50 @@
     ///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)
     {
@@ -65 +65 @@
     ///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)
@@ -84 +84 @@
     ///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)
     {
@@ -99 +99 @@
     ///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)
     {
@@ -120 +120 @@
   ///
   ///\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,
@@ -152 +146 @@
     typedef PredMapPath<Digraph, PredMap> Path;
 
-    ///The traits class.
+    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
     typedef TR Traits;
 
@@ -214 +208 @@
     typedef Bfs Create;
 
-    ///\name Named template parameters
+    ///\name Named Template Parameters
 
     ///@{
@@ -228 +222 @@
     };
     ///\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> > {
@@ -247 +242 @@
     };
     ///\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> > {
@@ -266 +262 @@
     };
     ///\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> > {
@@ -285 +282 @@
     };
     ///\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> > {
@@ -303 +301 @@
     };
     ///\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 :
@@ -341 +339 @@
 
     ///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)
@@ -358 +357 @@
 
     ///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)
@@ -375 +375 @@
 
     ///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)
@@ -393 +394 @@
     ///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)
@@ -409 +411 @@
   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()
     {
@@ -558 +557 @@
     }
 
-    ///\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; }
 
@@ -732 +731 @@
 
     ///\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.
 
     ///@{
@@ -743 +742 @@
     ///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); }
 
@@ -753 +752 @@
     ///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]; }
 
@@ -764 +763 @@
     ///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];}
 
@@ -778 +777 @@
     ///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]); }
@@ -795 +794 @@
     ///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;}
@@ -805 +804 @@
     ///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]; }
@@ -958 +958 @@
   /// 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,
@@ -1179 +1179 @@
   ///  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
@@ -1195 +1195 @@
   /// 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;
@@ -1225 +1225 @@
   };
 #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;
@@ -1255 +1255 @@
   ///
   /// 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.
@@ -1281 +1281 @@
   /// \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.
@@ -1295 +1295 @@
   /// 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 {
@@ -1319 +1319 @@
 
     ///The traits class.
-    typedef _Traits Traits;
+    typedef TR Traits;
 
     ///The type of the digraph the algorithm runs on.
@@ -1325 +1325 @@
 
     ///The visitor type used by the algorithm.
-    typedef _Visitor Visitor;
+    typedef VS Visitor;
 
     ///The type of the map that indicates which nodes are reached.
@@ -1365 +1365 @@
     typedef BfsVisit Create;
 
-    /// \name Named template parameters
+    /// \name Named Template Parameters
 
     ///@{
@@ -1407 +1407 @@
     ///
     /// 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) {
@@ -1422 +1423 @@
   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.
 
     /// @{
@@ -1731 +1729 @@
 
     /// \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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -34 +34 @@
   ///\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.
-  ///
-  ///\tparam _Prio Type of the priority of the items.
-  ///\tparam _ItemIntMap A read and writable Item int map, used internally
+  ///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 CMP specifies the ordering of the priorities.
+  ///In a heap one can change the priority of an item, add or erase an
+  ///item, etc.
+  ///
+  ///\tparam PR Type of the priority of the items.
+  ///\tparam IM A read and writable item map with int values, used internally
   ///to handle the cross references.
-  ///\tparam _Compare A class for the ordering of the priorities. The
-  ///default is \c std::less<_Prio>.
+  ///\tparam CMP 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 CMP = 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;
@@ -62 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef _Compare Compare;
+    typedef CMP Compare;
 
     /// \brief Type to represent the items states.
@@ -70 +71 @@
     /// 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:
@@ -87 +88 @@
     ///
     /// 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) {}
 
 
@@ -107 +108 @@
     ///
     /// \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.
@@ -121 +122 @@
     /// each item to \c PRE_HEAP.
     void clear() {
-      data.clear();
+      _data.clear();
     }
 
@@ -129 +130 @@
     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);
@@ -146 +147 @@
       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;
       }
@@ -166 +167 @@
 
     void move(const Pair &p, int i) {
-      data[i] = p;
-      iim.set(p.first, i);
+      _data[i] = p;
+      _iim.set(p.first, i);
     }
 
@@ -176 +177 @@
     /// \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);
     }
@@ -194 +195 @@
     /// \pre The heap must be nonempty.
     Item top() const {
-      return data[0].first;
+      return _data[0].first;
     }
 
@@ -202 +203 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      return data[0].second;
+      return _data[0].second;
     }
 
@@ -211 +212 @@
     /// \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();
     }
 
@@ -225 +226 @@
     /// \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();
     }
 
@@ -240 +241 @@
     ///
     /// 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;
     }
 
@@ -255 +256 @@
     /// \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());
       }
     }
@@ -270 +271 @@
     ///
     /// 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());
     }
 
@@ -300 +301 @@
     /// \param i The item.
     State state(const Item &i) const {
-      int s = iim[i];
+      int s = _iim[i];
       if( s>=0 )
         s=0;
@@ -320 +321 @@
           erase(i);
         }
-        iim[i] = st;
+        _iim[i] = st;
         break;
       case IN_HEAP:
@@ -334 +335 @@
     /// 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

@@ -3 +3 @@
  * 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).
@@ -36 +36 @@
   // 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.
@@ -104 +105 @@
     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 {};
@@ -122 +123 @@
     // 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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37 +37 @@
   // \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>
@@ -48 +47 @@
     : 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.
@@ -65 +64 @@
     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;
 
@@ -79 +82 @@
     //
     // Graph initialized map constructor.
-    explicit ArrayMap(const Graph& graph) {
+    explicit ArrayMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
@@ -93 +96 @@
     //
     // 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();
@@ -137 +140 @@
     // \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
@@ -201 +204 @@
     // \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) {
@@ -229 +232 @@
     // \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) {
@@ -273 +276 @@
     // \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) {
@@ -282 +285 @@
     // \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) {
@@ -291 +294 @@
     }
 
-    // \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() {
@@ -307 +310 @@
     // \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

@@ -3 +3 @@
  * 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).

lemon/bits/default_map.h

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

@@ -3 +3 @@
  * 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).

lemon/bits/graph_extender.h

@@ -3 +3 @@
  * 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).
@@ -30 +30 @@
 //\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;
 
@@ -219 +220 @@
     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) {}
@@ -244 +244 @@
     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) {}
@@ -331 +330 @@
   template <typename Base>
   class GraphExtender : public Base {
+    typedef Base Parent;
+
   public:
 
-    typedef Base Parent;
     typedef GraphExtender Graph;
 
@@ -602 +602 @@
     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)
@@ -627 +626 @@
     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)
@@ -652 +650 @@
     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

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37 +37 @@
   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;
+
+    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 
     class MapIt;
@@ -57 +60 @@
   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) {}
 
@@ -76 +79 @@
   public:
     class MapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
+
       typedef typename Map::Value Value;
 
@@ -115 +119 @@
 
     class ConstMapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
 
       typedef typename Map::Value Value;
@@ -146 +150 @@
 
     class ItemIt : public Item {
-    public:
-
-      typedef Item Parent;
-
+      typedef Item Parent;
+
+    public:
       ItemIt() : map(NULL) {}
+
 
       ItemIt(Invalid i) : Parent(i), map(NULL) {}
@@ -177 +181 @@
   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;
+
+    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 
     class MapIt;
@@ -197 +204 @@
   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) {}
 
@@ -220 +227 @@
   public:
     class MapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
       typedef typename Map::Value Value;
 
@@ -259 +266 @@
 
     class ConstMapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
 
       typedef typename Map::Value Value;
@@ -290 +297 @@
 
     class ItemIt : public Item {
-    public:
-
-      typedef Item Parent;
-
+      typedef Item Parent;
+
+    public:
       ItemIt() : map(NULL) {}
+
 
       ItemIt(Invalid i) : Parent(i), map(NULL) { }
@@ -317 +324 @@
   private:
 
-    const Graph& graph;
+    const GraphType& graph;
 
   };

lemon/bits/path_dump.h

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

@@ -3 +3 @@
  * 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).
@@ -30 +30 @@
   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) {}
 
@@ -72 +74 @@
   };
 
-  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) {}
     };
@@ -109 +113 @@
   };
 
-  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) {}
     };
@@ -205 +211 @@
   // 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

@@ -3 +3 @@
  * 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).
@@ -39 +39 @@
   // \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.
@@ -57 +57 @@
 
     // The graph type of the map.
-    typedef _Graph Graph;
+    typedef _Graph GraphType;
     // The item type of the map.
     typedef _Item Item;
@@ -73 +73 @@
     // The map type.
     typedef VectorMap Map;
-    // The base class of the map.
-    typedef typename Notifier::ObserverBase Parent;
 
     // The reference type of the map;
@@ -81 +79 @@
     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.
@@ -86 +90 @@
     // 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);
@@ -95 +99 @@
     // 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);
@@ -125 +129 @@
     // \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
@@ -170 +174 @@
     // \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) {
@@ -181 +185 @@
     // \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) {
@@ -196 +200 @@
     // \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) {
@@ -204 +208 @@
     // \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) {
@@ -212 +216 @@
     }
 
-    // \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() {
@@ -224 +228 @@
     // \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.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -41 +41 @@
 #include <unistd.h>
 #include <ctime>
+#ifndef WIN32
 #include <sys/times.h>
+#endif
 #include <sys/time.h>
 #endif
@@ -97 +99 @@
       GetSystemTime(&time);
       char buf1[11], buf2[9], buf3[5];
-          if (GetDateFormat(MY_LOCALE, 0, &time,
+          if (GetDateFormat(MY_LOCALE, 0, &time,
                         ("ddd MMM dd"), buf1, 11) &&
           GetTimeFormat(MY_LOCALE, 0, &time,

lemon/bits/windows.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_WINDOWS_H
-#define LEMON_WINDOWS_H
+#ifndef LEMON_BITS_WINDOWS_H
+#define LEMON_BITS_WINDOWS_H
 
 #include <string>

lemon/color.cc

@@ -3 +3 @@
  * 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).

lemon/color.h

@@ -3 +3 @@
  * 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).

lemon/concept_check.h

@@ -3 +3 @@
  * 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).

lemon/concepts/digraph.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -17 +17 @@
  */
 
-#ifndef LEMON_CONCEPT_DIGRAPH_H
-#define LEMON_CONCEPT_DIGRAPH_H
+#ifndef LEMON_CONCEPTS_DIGRAPH_H
+#define LEMON_CONCEPTS_DIGRAPH_H
 
 ///\ingroup graph_concepts
@@ -422 +422 @@
       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:
 
@@ -437 +436 @@
       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>
@@ -446 +446 @@
       };
 
-      /// \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:
 
@@ -460 +459 @@
       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>
@@ -472 +472 @@
       struct Constraints {
         void constraints() {
+          checkConcept<BaseDigraphComponent, _Digraph>();
           checkConcept<IterableDigraphComponent<>, _Digraph>();
           checkConcept<IDableDigraphComponent<>, _Digraph>();
@@ -485 +486 @@
 
 
-#endif // LEMON_CONCEPT_DIGRAPH_H
+#endif

lemon/concepts/graph.h

@@ -3 +3 @@
  * 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).
@@ -21 +21 @@
 ///\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>
 
@@ -312 +311 @@
       /// 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
@@ -324 +323 @@
         /// Copy constructor.
         ///
-        Arc(const Arc& e) : Edge(e) { }
+        Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
 
@@ -351 +350 @@
         bool operator<(Arc) const { return false; }
 
+        /// Converison to Edge
+        operator Edge() const { return Edge(); }
       };
       /// This iterator goes through each directed arc.
@@ -499 +500 @@
       };
 
-      /// \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:
@@ -515 +515 @@
       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>
@@ -524 +525 @@
       };
 
-      /// \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:
@@ -539 +539 @@
       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>
@@ -548 +549 @@
       };
 
-      /// 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:
@@ -563 +563 @@
       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>
@@ -603 +604 @@
       /// \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; }
 
@@ -738 +751 @@
       struct Constraints {
         void constraints() {
+          checkConcept<BaseGraphComponent, _Graph>();
           checkConcept<IterableGraphComponent<>, _Graph>();
           checkConcept<IDableGraphComponent<>, _Graph>();

lemon/concepts/graph_components.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -21 +21 @@
 ///\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>
@@ -33 +32 @@
   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 {
@@ -51 +49 @@
       /// \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>
@@ -95 +102 @@
         void constraints() {
           _GraphItem i1;
+          i1=INVALID;
           _GraphItem i2 = i1;
           _GraphItem i3 = INVALID;
@@ -101 +109 @@
 
           bool b;
-          //          b = (ia == ib) && (ia != ib) && (ia < ib);
           b = (ia == ib) && (ia != ib);
           b = (ia == INVALID) && (ib != INVALID);
@@ -112 +119 @@
     };
 
-    /// \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:
@@ -126 +132 @@
       /// \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;
@@ -176 +178 @@
     };
 
-    /// \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
@@ -234 +259 @@
       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>
@@ -270 +273 @@
         void constraints() {
           checkConcept<BaseDigraphComponent, _Graph>();
-          checkConcept<GraphItem<'u'>, Edge>();
+          checkConcept<GraphItem<'e'>, Edge>();
           {
             Node n;
@@ -278 +281 @@
             n = graph.v(ue);
             e = graph.direct(ue, true);
+            e = graph.direct(ue, false);
             e = graph.direct(ue, n);
             e = graph.oppositeArc(e);
@@ -291 +295 @@
     };
 
-    /// \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>
@@ -351 +353 @@
           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);
@@ -369 +373 @@
     };
 
-    /// \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>
@@ -408 +412 @@
 
         void constraints() {
-          checkConcept<Base, _Graph >();
           checkConcept<IDableDigraphComponent<Base>, _Graph >();
           typename _Graph::Edge edge;
@@ -422 +425 @@
     };
 
-    /// \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;}
 
@@ -473 +485 @@
       struct Constraints {
         void constraints() {
+          checkConcept<GraphItem<>, _GraphItemIt>();
           _GraphItemIt it1(g);
           _GraphItemIt it2;
+          _GraphItemIt it3 = it1;
+          _GraphItemIt it4 = INVALID;
 
           it2 = ++it1;
@@ -480 +495 @@
           ++(++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.
@@ -540 +565 @@
       /// \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;}
 
@@ -547 +573 @@
       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