Changes in / [244:c30731a37f91:247:f1158744a112] in lemon-main

Files:

• CMakeLists.txt (modified) (1 diff)
• INSTALL (modified) (3 diffs)
• Makefile.am (modified) (1 diff)
• README (modified) (1 diff)
• cmake/FindGhostscript.cmake (added)
• cmake/nsis/lemon.ico (added)
• cmake/nsis/uninstall.ico (added)
• configure.ac (modified) (6 diffs)
• demo/CMakeLists.txt (modified) (1 diff)
• demo/graph_to_eps_demo.cc (modified) (1 diff)
• doc/CMakeLists.txt (added)
• doc/Doxyfile.in (modified) (4 diffs)
• doc/Makefile.am (modified) (1 diff)
• doc/groups.dox (modified) (2 diffs)
• doc/lgf.dox (modified) (1 diff)
• lemon/CMakeLists.txt (modified) (1 diff)
• lemon/Makefile.am (modified) (3 diffs)
• lemon/assert.h (modified) (1 diff)
• lemon/base.cc (modified) (1 diff)
• lemon/bfs.h (modified) (1 diff)
• lemon/bits/alteration_notifier.h (modified) (5 diffs)
• lemon/bits/base_extender.h (modified) (1 diff)
• lemon/bits/enable_if.h (added)
• lemon/bits/graph_extender.h (modified) (1 diff)
• lemon/bits/invalid.h (deleted)
• lemon/bits/traits.h (modified) (1 diff)
• lemon/bits/utility.h (deleted)
• lemon/bits/vector_map.h (modified) (1 diff)
• lemon/concepts/digraph.h (modified) (1 diff)
• lemon/concepts/graph.h (modified) (1 diff)
• lemon/concepts/graph_components.h (modified) (1 diff)
• lemon/concepts/heap.h (modified) (1 diff)
• lemon/concepts/maps.h (modified) (1 diff)
• lemon/concepts/path.h (modified) (5 diffs)
• lemon/core.h (added)
• lemon/dfs.h (modified) (1 diff)
• lemon/dijkstra.h (modified) (1 diff)
• lemon/dim2.h (modified) (31 diffs)
• lemon/graph_to_eps.h (modified) (1 diff)
• lemon/graph_utils.h (deleted)
• lemon/kruskal.h (modified) (2 diffs)
• lemon/lgf_reader.h (modified) (3 diffs)
• lemon/lgf_writer.h (modified) (3 diffs)
• lemon/list_graph.h (modified) (10 diffs)
• lemon/maps.h (modified) (2 diffs)
• lemon/path.h (modified) (2 diffs)
• lemon/smart_graph.h (modified) (2 diffs)
• lemon/unionfind.h (modified) (6 diffs)
• test/CMakeLists.txt (modified) (2 diffs)
• test/Makefile.am (modified) (1 diff)
• test/bfs_test.cc (modified) (5 diffs)
• test/dfs_test.cc (modified) (6 diffs)
• test/digraph_test.cc (modified) (5 diffs)
• test/dijkstra_test.cc (modified) (5 diffs)
• test/dim_test.cc (modified) (1 diff)
• test/error_test.cc (modified) (1 diff)
• test/graph_copy_test.cc (modified) (1 diff)
• test/graph_maps_test.h (deleted)
• test/graph_test.cc (modified) (7 diffs)
• test/graph_test.h (modified) (7 diffs)
• test/graph_utils_test.cc (modified) (1 diff)

CMakeLists.txt

@@ -1 @@
-project (LEMON)
-enable_testing ()
-add_subdirectory (lemon)
-add_subdirectory (demo)
-add_subdirectory (test)
+CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
+
+#EXECUTE_PROCESS(
+#  COMMAND hg id -i
+#  OUTPUT_VARIABLE HG_REVISION
+#  OUTPUT_STRIP_TRAILING_WHITESPACE)
+
+SET(PROJECT_NAME "LEMON")
+SET(PROJECT_VERSION_MAJOR "0")
+SET(PROJECT_VERSION_MINOR "99")
+SET(PROJECT_VERSION_PATCH "0")
+SET(PROJECT_VERSION
+  "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
+
+PROJECT(${PROJECT_NAME})
+
+SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
+
+INCLUDE(FindDoxygen)
+INCLUDE(FindGhostscript)
+
+ENABLE_TESTING()
+
+ADD_SUBDIRECTORY(lemon)
+ADD_SUBDIRECTORY(demo)
+ADD_SUBDIRECTORY(doc)
+ADD_SUBDIRECTORY(test)
+
+IF(WIN32)
+  INSTALL(FILES ${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico
+    DESTINATION bin)
+ENDIF(WIN32)
+
+IF(WIN32)
+  SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
+  SET(CPACK_PACKAGE_VENDOR
+    "EGRES - Egervary Research Group on Combinatorial Optimization")
+  SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
+    "LEMON - Library of Efficient Models and Optimization in Networks")
+  SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_SOURCE_DIR}/LICENSE")
+
+  SET(CPACK_PACKAGE_VERSION_MAJOR ${PROJECT_VERSION_MAJOR})
+  SET(CPACK_PACKAGE_VERSION_MINOR ${PROJECT_VERSION_MINOR})
+  SET(CPACK_PACKAGE_VERSION_PATCH ${PROJECT_VERSION_PATCH})
+  SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
+
+  SET(CPACK_PACKAGE_INSTALL_DIRECTORY
+    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")
+  SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY
+    "${PROJECT_NAME} ${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
+
+  # Variables to generate a component-based installer.
+  #SET(CPACK_COMPONENTS_ALL headers library html_documentation)
+
+  #SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers")
+  #SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Static library")
+  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation")
+
+  #SET(CPACK_COMPONENT_HEADERS_DESCRIPTION
+  #  "C++ header files for use with the LEMON library")
+  #SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION
+  #  "Static library used to build programs with LEMON")
+  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION
+  #  "Doxygen generated documentation")
+
+  #SET(CPACK_COMPONENT_HEADERS_DEPENDS library)
+
+  #SET(CPACK_COMPONENT_HEADERS_GROUP "Development")
+  #SET(CPACK_COMPONENT_LIBRARY_GROUP "Development")
+  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation")
+
+  #SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION
+  #  "Components needed to develop software using LEMON")
+  #SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION
+  #  "Documentation of LEMON")
+
+  #SET(CPACK_ALL_INSTALL_TYPES Full Developer)
+
+  #SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full)
+  #SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full)
+  #SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full)
+
+  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_INSTALLED_ICON_NAME "bin\\\\lemon.ico")
+  SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
+  SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu")
+  SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu")
+  SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu")
+  SET(CPACK_NSIS_CREATE_ICONS_EXTRA "
+    CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\doc\\\\index.html\\\"
+    ")
+  SET(CPACK_NSIS_DELETE_ICONS_EXTRA "
+    !insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP
+    Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\"
+    ")
+
+  INCLUDE(CPack)
+ENDIF(WIN32)

INSTALL

@@ -4 +4 @@
    Since you are reading this I assume you already obtained one of the release
 tarballs and successfully extracted it. The latest version of LEMON is
-available at our webpage (http://lemon.cs.elte.hu/).
+available at our web page (http://lemon.cs.elte.hu/).
 
    In order to install LEMON from the extracted source tarball you have to
 issue the following commands:
 
-  1. `cd lemon-x.y.z'
+   1. `cd lemon-x.y.z'
 
-     This changes to the directory which was created when you extracted the
-     sources. The x.y.z part is a version number.
+      This command changes to the directory which was created when you
+      extracted the sources. The x.y.z part is a version number.
 
-  2. `./configure'
+   2. `./configure'
 
-     This runs the configure shell script, which does some checks and
-     configuration (creates makefiles etc).
+      This command runs the configure shell script, which does some checks and
+      creates the makefiles.
 
-  3. `make'
+   3. `make'
 
-     This command compiles the non-template part of LEMON into libemon.a file.
-     It also compiles the benchmark and demo programs when enabled.
+      This command compiles the non-template part of LEMON into libemon.a
+      file. It also compiles the programs in the tools, benchmark and demo
+      subdirectories when enabled.
 
-  4. `make check'
+   4. `make check'
 
-     This step is optional, but recommended. It runs the test programs that we
-     developed for LEMON to check whether the library works properly on your
-     platform.
+      This step is optional, but recommended. It runs the test programs that
+      we developed for LEMON to check whether the library works properly on
+      your platform.
 
-  5. `make install'
+   5. `make install'
 
-     This command installs LEMON under /usr/local (you will need root
-     privileges to be able to do that). If you want to install it to some
-     other location, then pass the --prefix=DIRECTORY flag to configure in
-     step 1. For example: `./configure --prefix=/home/username/lemon'
+      This command installs LEMON under /usr/local (you will need root
+      privileges to be able to do that). If you want to install it to some
+      other location, then pass the --prefix=DIRECTORY flag to configure in
+      step 2. For example: `./configure --prefix=/home/username/lemon'.
+
+   6. `make install-html'
+
+      This command installs the documentation under share/doc/lemon/docs. The
+      generated documentation is included in the tarball. If you want to
+      generate it yourself, then run `make html'. Note that for this you need
+      to have the following programs installed: Doxygen, Graphviz, Ghostscript,
+      Latex.
 
 
-Configure Flags
-===============
+Configure Options and Variables
+===============================
 
-   You can pass the following flags to configure in step 1
-(see ./configure --help for more):
+   In step 2 you can customize the actions of configure by setting variables
+and passing options to it. This can be done like this:
+`./configure [OPTION]... [VARIABLE=VALUE]...'
 
-CXX=comp
+   Below you will find some useful variables and options (see
+`./configure --help' for more):
+
+CXX='comp'
 
   Change the C++ compiler to 'comp'.
@@ -50 +63 @@
 CXXFLAGS='flags'
 
-  Pass the 'flags' to the compiler. For example
-  CXXFLAGS='-O3 -march=pentium-m'
-  turns  on generation of aggressively optimized
-  Pentium-M specific code.
+  Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'
+  turns on generation of aggressively optimized Pentium-M specific code.
+
+--prefix=PREFIX
+
+  Set the installation prefix to PREFIX. By default it is /usr/local.
 
 --enable-demo
 
-   Build the demo programs too.
+   Build the examples in the demo subdirectory.
 
 --disable-demo
 
-   Do not build the demo programs (default).
+   Do not build the examples in the demo subdirectory (default).
 
 --enable-benchmark
 
-   Build the benchmark programs too.
+   Build the programs in the benchmark subdirectory.
 
 --disable-benchmark
 
-   Do not build the benchmark programs (default).
+   Do not build the programs in the benchmark subdirectory (default).
+
+--enable-tools
+
+   Build the programs in the tools subdirectory (default).
+
+--disable-tools
+
+   Do not build the programs in the tools subdirectory.
 
 --with-glpk[=PREFIX]
@@ -116 +139 @@
 
    Disable CPLEX support.
+
+--with-soplex[=PREFIX]
+
+   Enable SoPlex support (default). You should specify the prefix too if
+   you installed SoPlex to some non-standard location (e.g. your home
+   directory). If it is not found, SoPlex support will be disabled.
+
+--with-soplex-includedir=DIR
+
+   The directory where the SoPlex header files are located. This is only
+   useful when the SoPlex headers and libraries are not under the same
+   prefix (which is unlikely).
+
+--with-soplex-libdir=DIR
+
+   The directory where the SoPlex libraries are located. This is only
+   useful when the SoPlex headers and libraries are not under the same
+   prefix (which is unlikely).
+
+--without-soplex
+
+   Disable SoPlex support.

Makefile.am

@@ -9 +9 @@
         m4/lx_check_glpk.m4 \
         m4/lx_check_soplex.m4 \
-        CMakeLists.txt
+        CMakeLists.txt \
+        cmake
 
 pkgconfigdir = $(libdir)/pkgconfig

README

@@ -1 @@
-------------------------------------------------------------------
+==================================================================
 LEMON - a Library of Efficient Models and Optimization in Networks
-------------------------------------------------------------------
+==================================================================
 
-LEMON is the abbreviation of Library of Efficient Models and
-Optimization in Networks. It is an open source library written in
-C++. It provides a set of easy-to-use implementation of common data
-structures and algorithms in the area of optimization and helps
-implementing new ones. It is an especially suitable tool to solve the
-design and optimization problems of telecommunications networks. To
-achieve wide usability, a fundamental design requirement is the
-genericity of interface of data structures and algorithms. LEMON is an
-open source library end invites people all around the world in its
-development.
+LEMON is an open source library written in C++. It provides
+easy-to-use implementations of common data structures and algorithms
+in the area of optimization and helps implementing new ones. The main
+focus is on graphs and graph algorithms, thus it is especially
+suitable for solving design and optimization problems of
+telecommunication networks. To achieve wide usability its data
+structures and algorithms provide generic interfaces.
 
---------
 Contents
---------
+========
 
-COPYING, LICENSE
+LICENSE
 
-  Copying, distribution and modification conditions and terms.
+   Copying, distribution and modification conditions and terms.
 
 INSTALL
 
-  For general building and installation instructions, see the file.
+   General building and installation instructions.
 
 lemon/
 
-  Source code of LEMON itself.
+   Source code of LEMON library.
 
 doc/
 
-  Documentation of LEMON. The starting page is doc/html/index.html.
-  The documentation installs into the directory
-
-    /usr/local/share/doc/lemon/html
-
-  or -- if you use different prefix -- into
-
-    ${prefix}/share/doc/lemon/html
-
-  (see also INSTALL).
+   Documentation of LEMON. The starting page is doc/html/index.html.
 
 demo/
 
-  Some demonstration programs to make you easier to get familiar with
-  LEMON. Use --enable-demo configure option to also compile these codes
-  (see also INSTALL).
+   Some example programs to make you easier to get familiar with LEMON.
 
 test/
 
-  Contains programs to check the integrity and correctness of
-  LEMON. The command 'make check' performs these tests.
+   Contains programs to check the integrity and correctness of LEMON.
 
 benchmark/
   
-  Contains programs measuring the performance of LEMON. Use
-  --enable-benchmark configure option to also compile these codes (see
-  also INSTALL).
+   Contains programs for measuring the performance of algorithms.
+
+tools/
+
+   Various utilities related to LEMON.

configure.ac

@@ -7 +7 @@
 
 AC_PREREQ([2.59])
-AC_INIT([LEMON], [lemon_version()], [lemon-devel@lemon.cs.elte.hu], [lemon])
+AC_INIT([LEMON], [lemon_version()], [lemon-user@lemon.cs.elte.hu], [lemon])
 AC_CONFIG_AUX_DIR([build-aux])
 AC_CONFIG_MACRO_DIR([m4])
@@ -26 +26 @@
 AC_CHECK_PROG([gs_found],[gs],[yes],[no])
 
+dnl Set custom compiler flags when using g++.
 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; 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"
@@ -35 +36 @@
 LX_CHECK_SOPLEX
 
-dnl Disable/enable building the demo programs
+dnl Disable/enable building the demo programs.
 AC_ARG_ENABLE([demo],
 AS_HELP_STRING([--enable-demo], [build the demo programs])
@@ -48 +49 @@
 AM_CONDITIONAL([WANT_DEMO], [test x"$enable_demo" != x"no"])
 
-dnl Disable/enable building the binary tools
+dnl Disable/enable building the binary tools.
 AC_ARG_ENABLE([tools],
 AS_HELP_STRING([--enable-tools], [build additional tools @<:@default@:>@])
@@ -61 +62 @@
 AM_CONDITIONAL([WANT_TOOLS], [test x"$enable_tools" != x"no"])
 
-dnl Disable/enable building the benchmarks
+dnl Disable/enable building the benchmarks.
 AC_ARG_ENABLE([benchmark],
 AS_HELP_STRING([--enable-benchmark], [build the benchmarks])
@@ -87 +88 @@
 AC_HEADER_STDC
 AC_CHECK_FUNCS(gettimeofday times ctime_r)
+
+dnl Add dependencies on files generated by configure.
+AC_SUBST([CONFIG_STATUS_DEPENDENCIES],
+  ['$(top_srcdir)/doc/Doxyfile.in $(top_srcdir)/lemon/lemon.pc.in'])
 
 AC_CONFIG_FILES([

demo/CMakeLists.txt

@@ -1 @@
-include_directories (${LEMON_SOURCE_DIR})
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
 
-link_directories (${LEMON_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
 
-set (DEMOS
+SET(DEMOS
   arg_parser_demo
   graph_to_eps_demo
   lgf_demo)
 
-foreach (DEMO_NAME ${DEMOS})
-  add_executable (${DEMO_NAME} ${DEMO_NAME}.cc)
-  target_link_libraries (${DEMO_NAME} lemon)
-  endforeach (DEMO_NAME)
+FOREACH(DEMO_NAME ${DEMOS})
+  ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
+  TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
+ENDFOREACH(DEMO_NAME)

demo/graph_to_eps_demo.cc

@@ -32 +32 @@
 
 #include<lemon/list_graph.h>
-#include<lemon/graph_utils.h>
 #include<lemon/graph_to_eps.h>
 #include<lemon/math.h>

doc/Doxyfile.in

@@ -16 +16 @@
 INLINE_INHERITED_MEMB  = NO
 FULL_PATH_NAMES        = YES
-STRIP_FROM_PATH        = @abs_top_srcdir@
-STRIP_FROM_INC_PATH    = @abs_top_srcdir@
+STRIP_FROM_PATH        = "@abs_top_srcdir@"
+STRIP_FROM_INC_PATH    = "@abs_top_srcdir@"
 SHORT_NAMES            = YES
 JAVADOC_AUTOBRIEF      = NO
@@ -81 +81 @@
 # configuration options related to the input files
 #---------------------------------------------------------------------------
-INPUT                  = @abs_top_srcdir@/doc \
-                         @abs_top_srcdir@/lemon \
-                         @abs_top_srcdir@/lemon/bits \
-                         @abs_top_srcdir@/lemon/concepts \
-                         @abs_top_srcdir@/demo \
-                         @abs_top_srcdir@/tools \
-                         @abs_top_srcdir@/test/test_tools.h
+INPUT                  = "@abs_top_srcdir@/doc" \
+                         "@abs_top_srcdir@/lemon" \
+                         "@abs_top_srcdir@/lemon/bits" \
+                         "@abs_top_srcdir@/lemon/concepts" \
+                         "@abs_top_srcdir@/demo" \
+                         "@abs_top_srcdir@/tools" \
+                         "@abs_top_srcdir@/test/test_tools.h"
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          = *.h \
@@ -97 +97 @@
 EXCLUDE_PATTERNS       = 
 EXCLUDE_SYMBOLS        = 
-EXAMPLE_PATH           = @abs_top_srcdir@/demo \
-                         @abs_top_srcdir@/LICENSE \
-                         @abs_top_srcdir@/doc
+EXAMPLE_PATH           = "@abs_top_srcdir@/demo" \
+                         "@abs_top_srcdir@/LICENSE" \
+                         "@abs_top_srcdir@/doc"
 EXAMPLE_PATTERNS       = 
 EXAMPLE_RECURSIVE      = NO
-IMAGE_PATH             = @abs_top_srcdir@/doc/images \
-                         @abs_top_builddir@/doc/gen-images
+IMAGE_PATH             = "@abs_top_srcdir@/doc/images" \
+                         "@abs_top_builddir@/doc/gen-images"
 INPUT_FILTER           = 
 FILTER_PATTERNS        = 
@@ -146 +146 @@
 DISABLE_INDEX          = NO
 ENUM_VALUES_PER_LINE   = 4
-GENERATE_TREEVIEW      = YES
+GENERATE_TREEVIEW      = NO
 TREEVIEW_WIDTH         = 250
 #---------------------------------------------------------------------------

doc/Makefile.am

@@ -8 +8 @@
         doc/mainpage.dox \
         doc/namespaces.dox \
-        doc/html
+        doc/html \
+        doc/CMakeLists.txt
 
 DOC_EPS_IMAGES18 = \

doc/groups.dox

@@ -326 +326 @@
 maximum cardinality matching.
 
-Lemon contains the next algorithms:
+LEMON contains the next algorithms:
 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
   augmenting path algorithm for calculate maximum cardinality matching in
@@ -477 +477 @@
 
 /**
-@defgroup lemon_io Lemon Input-Output
+@defgroup lemon_io LEMON Input-Output
 @ingroup io_group
-\brief Reading and writing \ref lgf-format "Lemon Graph Format".
+\brief Reading and writing \ref lgf-format "LEMON Graph Format".
 
 This group describes methods for reading and writing
-\ref lgf-format "Lemon Graph Format".
+\ref lgf-format "LEMON Graph Format".
 */
 

doc/lgf.dox

@@ -22 +22 @@
 
 
-\page lgf-format Lemon Graph Format (LGF)
+\page lgf-format LEMON Graph Format (LGF)
 
 The \e LGF is a <em>column oriented</em>

lemon/CMakeLists.txt

@@ -1 @@
-include_directories (${LEMON_SOURCE_DIR})
-add_library (lemon arg_parser.cc base.cc color.cc random.cc)
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
+
+ADD_LIBRARY(lemon
+  arg_parser.cc
+  base.cc
+  color.cc
+  random.cc)
+
+INSTALL(
+  TARGETS lemon
+  ARCHIVE DESTINATION lib
+  COMPONENT library)
+
+INSTALL(
+  DIRECTORY . bits concepts
+  DESTINATION include/lemon
+  COMPONENT headers
+  FILES_MATCHING PATTERN "*.h")

lemon/Makefile.am

@@ -25 +25 @@
         lemon/concept_check.h \
         lemon/counter.h \
+        lemon/core.h \
         lemon/dfs.h \
         lemon/dijkstra.h \
@@ -30 +31 @@
         lemon/error.h \
         lemon/graph_to_eps.h \
-        lemon/graph_utils.h \
         lemon/kruskal.h \
         lemon/lgf_reader.h \
@@ -50 +50 @@
         lemon/bits/bezier.h \
         lemon/bits/default_map.h \
+        lemon/bits/enable_if.h \
         lemon/bits/graph_extender.h \
-        lemon/bits/invalid.h \
         lemon/bits/map_extender.h \
         lemon/bits/path_dump.h \
         lemon/bits/traits.h \
-        lemon/bits/utility.h \
         lemon/bits/vector_map.h
 

lemon/assert.h

@@ -238 +238 @@
 
 #    if LEMON_ENABLE_DEBUG
-#      define LEMON_DEBUG(exp, msg)
+#      define LEMON_DEBUG(exp, msg)                                     \
          (static_cast<void> (!!(exp) ? 0 : (                            \
            LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                     \

lemon/base.cc

@@ -21 +21 @@
 
 #include<lemon/tolerance.h>
-#include<lemon/bits/invalid.h>
+#include<lemon/core.h>
 namespace lemon {
 

lemon/bfs.h

@@ -25 +25 @@
 
 #include <lemon/list_graph.h>
-#include <lemon/graph_utils.h>
 #include <lemon/bits/path_dump.h>
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>

lemon/bits/alteration_notifier.h

@@ -23 +23 @@
 #include <list>
 
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 
 ///\ingroup graphbits
@@ -42 +42 @@
   ///
   /// The graph's node and edge sets can be changed as we add or erase
-  /// nodes and edges in the graph. Lemon would like to handle easily
+  /// 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
@@ -410 +410 @@
           ++it;
         } catch (const ImmediateDetach&) {
-          it = _observers.erase(it);
           (*it)->_index = _observers.end();
           (*it)->_notifier = 0;
+          it = _observers.erase(it);
         }
       }
@@ -430 +430 @@
           ++it;
         } catch (const ImmediateDetach&) {
-          it = _observers.erase(it);
           (*it)->_index = _observers.end();
           (*it)->_notifier = 0;
+          it = _observers.erase(it);
         }
       }
@@ -469 +469 @@
           ++it;
         } catch (const ImmediateDetach&) {
-          it = _observers.erase(it);
           (*it)->_index = _observers.end();
           (*it)->_notifier = 0;
+          it = _observers.erase(it);
         }
       }

lemon/bits/base_extender.h

@@ -20 +20 @@
 #define LEMON_BITS_BASE_EXTENDER_H
 
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/error.h>
 

lemon/bits/graph_extender.h

@@ -20 +20 @@
 #define LEMON_BITS_GRAPH_EXTENDER_H
 
-#include <lemon/bits/invalid.h>
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 
 #include <lemon/bits/map_extender.h>

lemon/bits/traits.h

@@ -20 +20 @@
 #define LEMON_BITS_TRAITS_H
 
-#include <lemon/bits/utility.h>
-
 ///\file
 ///\brief Traits for graphs and maps
 ///
 
+#include <lemon/bits/enable_if.h>
+
 namespace lemon {
+
+  struct InvalidType {};
+
   template <typename _Graph, typename _Item>
   class ItemSetTraits {};

lemon/bits/vector_map.h

@@ -23 +23 @@
 #include <algorithm>
 
-#include <lemon/bits/traits.h>
-#include <lemon/bits/utility.h>
-
+#include <lemon/core.h>
 #include <lemon/bits/alteration_notifier.h>
 

lemon/concepts/digraph.h

@@ -24 +24 @@
 ///\brief The concept of directed graphs.
 
-#include <lemon/bits/invalid.h>
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 #include <lemon/concepts/maps.h>
 #include <lemon/concept_check.h>

lemon/concepts/graph.h

@@ -26 +26 @@
 #include <lemon/concepts/graph_components.h>
 #include <lemon/concepts/graph.h>
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 
 namespace lemon {

lemon/concepts/graph_components.h

@@ -25 +25 @@
 #define LEMON_CONCEPT_GRAPH_COMPONENTS_H
 
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/concepts/maps.h>
 

lemon/concepts/heap.h

@@ -24 +24 @@
 #define LEMON_CONCEPT_HEAP_H
 
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 
 namespace lemon {

lemon/concepts/maps.h

@@ -20 +20 @@
 #define LEMON_CONCEPT_MAPS_H
 
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 #include <lemon/concept_check.h>
 

lemon/concepts/path.h

@@ -26 +26 @@
 #define LEMON_CONCEPT_PATH_H
 
-#include <lemon/bits/invalid.h>
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 #include <lemon/concept_check.h>
 
@@ -79 +78 @@
       void clear() {}
 
-      /// \brief Lemon style iterator for path arcs
+      /// \brief LEMON style iterator for path arcs
       ///
       /// This class is used to iterate on the arcs of the paths.
@@ -202 +201 @@
     /// If we would like to give back a real path from these
     /// algorithms then we should create a temporarly path object. In
-    /// Lemon such algorithms gives back a path dumper what can
+    /// LEMON such algorithms gives back a path dumper what can
     /// assigned to a real path and the dumpers can be implemented as
     /// an adaptor class to the predecessor map.
@@ -234 +233 @@
       typedef False RevPathTag;
 
-      /// \brief Lemon style iterator for path arcs
+      /// \brief LEMON style iterator for path arcs
       ///
       /// This class is used to iterate on the arcs of the paths.
@@ -261 +260 @@
       };
 
-      /// \brief Lemon style iterator for path arcs
+      /// \brief LEMON style iterator for path arcs
       ///
       /// This class is used to iterate on the arcs of the paths in

lemon/dfs.h

@@ -25 +25 @@
 
 #include <lemon/list_graph.h>
-#include <lemon/graph_utils.h>
 #include <lemon/bits/path_dump.h>
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/assert.h>

lemon/dijkstra.h

@@ -28 +28 @@
 #include <lemon/bin_heap.h>
 #include <lemon/bits/path_dump.h>
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/error.h>
 #include <lemon/maps.h>

lemon/dim2.h

@@ -21 +21 @@
 
 #include <iostream>
-#include <lemon/bits/utility.h>
 
 ///\ingroup misc
@@ -46 +45 @@
   /// @{
 
-  /// A simple two dimensional vector (plainvector) implementation
-
-  /// A simple two dimensional vector (plainvector) implementation
+  /// A simple two dimensional vector (plain vector) implementation
+
+  /// A simple two dimensional vector (plain vector) implementation
   /// with the usual vector operations.
   template<typename T>
@@ -187 +186 @@
   }
 
-  ///Read a plainvector from a stream
-
-  ///Read a plainvector from a stream.
+  ///Read a plain vector from a stream
+
+  ///Read a plain vector from a stream.
   ///\relates Point
   ///
@@ -215 +214 @@
   }
 
-  ///Write a plainvector to a stream
-
-  ///Write a plainvector to a stream.
+  ///Write a plain vector to a stream
+
+  ///Write a plain vector to a stream.
   ///\relates Point
   ///
@@ -262 +261 @@
 
 
-  /// A class to calculate or store the bounding box of plainvectors.
-
-  /// A class to calculate or store the bounding box of plainvectors.
-  ///
+    /// A class to calculate or store the bounding box of plain vectors.
+
+    /// A class to calculate or store the bounding box of plain vectors.
+    ///
     template<typename T>
     class BoundingBox {
-      Point<T> bottom_left, top_right;
+      Point<T> _bottom_left, _top_right;
       bool _empty;
     public:
@@ -276 +275 @@
 
       ///Construct an instance from one point
-      BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
+      BoundingBox(Point<T> a) {
+        _bottom_left = _top_right = a;
+        _empty = false;
+      }
 
       ///Construct an instance from two points
@@ -287 +289 @@
       BoundingBox(Point<T> a,Point<T> b)
       {
-        bottom_left=a;
-        top_right=b;
+        _bottom_left = a;
+        _top_right = b;
         _empty = false;
       }
@@ -303 +305 @@
       BoundingBox(T l,T b,T r,T t)
       {
-        bottom_left=Point<T>(l,b);
-        top_right=Point<T>(r,t);
+        _bottom_left=Point<T>(l,b);
+        _top_right=Point<T>(r,t);
         _empty = false;
       }
@@ -321 +323 @@
       ///Make the BoundingBox empty
       void clear() {
-        _empty=1;
+        _empty = true;
       }
 
@@ -329 +331 @@
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> bottomLeft() const {
-        return bottom_left;
+        return _bottom_left;
       }
 
@@ -335 +337 @@
 
       ///Set the bottom left corner of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void bottomLeft(Point<T> p) {
-        bottom_left = p;
+        _bottom_left = p;
       }
 
@@ -345 +347 @@
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> topRight() const {
-        return top_right;
+        return _top_right;
       }
 
@@ -351 +353 @@
 
       ///Set the top right corner of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void topRight(Point<T> p) {
-        top_right = p;
+        _top_right = p;
       }
 
@@ -361 +363 @@
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> bottomRight() const {
-        return Point<T>(top_right.x,bottom_left.y);
+        return Point<T>(_top_right.x,_bottom_left.y);
       }
 
@@ -367 +369 @@
 
       ///Set the bottom right corner of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void bottomRight(Point<T> p) {
-        top_right.x = p.x;
-        bottom_left.y = p.y;
+        _top_right.x = p.x;
+        _bottom_left.y = p.y;
       }
 
@@ -378 +380 @@
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> topLeft() const {
-        return Point<T>(bottom_left.x,top_right.y);
+        return Point<T>(_bottom_left.x,_top_right.y);
       }
 
@@ -384 +386 @@
 
       ///Set the top left corner of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void topLeft(Point<T> p) {
-        top_right.y = p.y;
-        bottom_left.x = p.x;
+        _top_right.y = p.y;
+        _bottom_left.x = p.x;
       }
 
@@ -395 +397 @@
       ///If the bounding box is empty, then the return value is not defined.
       T bottom() const {
-        return bottom_left.y;
+        return _bottom_left.y;
       }
 
@@ -401 +403 @@
 
       ///Set the bottom of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void bottom(T t) {
-        bottom_left.y = t;
+        _bottom_left.y = t;
       }
 
@@ -411 +413 @@
       ///If the bounding box is empty, then the return value is not defined.
       T top() const {
-        return top_right.y;
+        return _top_right.y;
       }
 
@@ -417 +419 @@
 
       ///Set the top of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void top(T t) {
-        top_right.y = t;
+        _top_right.y = t;
       }
 
@@ -427 +429 @@
       ///If the bounding box is empty, then the return value is not defined.
       T left() const {
-        return bottom_left.x;
+        return _bottom_left.x;
       }
 
@@ -433 +435 @@
 
       ///Set the left side of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void left(T t) {
-        bottom_left.x = t;
+        _bottom_left.x = t;
       }
 
@@ -443 +445 @@
       ///If the bounding box is empty, then the return value is not defined.
       T right() const {
-        return top_right.x;
+        return _top_right.x;
       }
 
@@ -449 +451 @@
 
       ///Set the right side of the box.
-      ///It should only be used for non-empty box.
+      ///\pre The box must not be empty.
       void right(T t) {
-        top_right.x = t;
+        _top_right.x = t;
       }
 
@@ -459 +461 @@
       ///If the bounding box is empty, then the return value is not defined.
       T height() const {
-        return top_right.y-bottom_left.y;
+        return _top_right.y-_bottom_left.y;
       }
 
@@ -467 +469 @@
       ///If the bounding box is empty, then the return value is not defined.
       T width() const {
-        return top_right.x-bottom_left.x;
+        return _top_right.x-_bottom_left.x;
       }
 
@@ -474 +476 @@
         if (_empty)
           return false;
-        else{
-          return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
-              (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
+        else {
+          return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
+                   (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
         }
       }
@@ -485 +487 @@
       ///
       BoundingBox& add(const Point<T>& u){
-        if (_empty){
-          bottom_left=top_right=u;
+        if (_empty) {
+          _bottom_left = _top_right = u;
           _empty = false;
         }
-        else{
-          if (bottom_left.x > u.x) bottom_left.x = u.x;
-          if (bottom_left.y > u.y) bottom_left.y = u.y;
-          if (top_right.x < u.x) top_right.x = u.x;
-          if (top_right.y < u.y) top_right.y = u.y;
+        else {
+          if (_bottom_left.x > u.x) _bottom_left.x = u.x;
+          if (_bottom_left.y > u.y) _bottom_left.y = u.y;
+          if (_top_right.x < u.x) _top_right.x = u.x;
+          if (_top_right.y < u.y) _top_right.y = u.y;
         }
         return *this;
@@ -504 +506 @@
       BoundingBox& add(const BoundingBox &u){
         if ( !u.empty() ){
-          this->add(u.bottomLeft());
-          this->add(u.topRight());
+          add(u._bottom_left);
+          add(u._top_right);
         }
         return *this;
@@ -516 +518 @@
       BoundingBox operator&(const BoundingBox& u) const {
         BoundingBox b;
-        if (this->_empty || u._empty) {
+        if (_empty || u._empty) {
           b._empty = true;
         } else {
-          b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
-          b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
-          b.top_right.x = std::min(this->top_right.x,u.top_right.x);
-          b.top_right.y = std::min(this->top_right.y,u.top_right.y);
-          b._empty = b.bottom_left.x > b.top_right.x ||
-                     b.bottom_left.y > b.top_right.y;
+          b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
+          b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
+          b._top_right.x = std::min(_top_right.x, u._top_right.x);
+          b._top_right.y = std::min(_top_right.y, u._top_right.y);
+          b._empty = b._bottom_left.x > b._top_right.x ||
+                     b._bottom_left.y > b._top_right.y;
         }
         return b;

lemon/graph_to_eps.h

@@ -36 +36 @@
 
 #include<lemon/math.h>
-#include<lemon/bits/invalid.h>
+#include<lemon/core.h>
 #include<lemon/dim2.h>
 #include<lemon/maps.h>

lemon/kruskal.h

@@ -23 +23 @@
 #include <vector>
 #include <lemon/unionfind.h>
-// #include <lemon/graph_utils.h>
 #include <lemon/maps.h>
 
-// #include <lemon/radix_sort.h>
-
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 #include <lemon/bits/traits.h>
 
@@ -301 +298 @@
   /// \return The total cost of the found spanning tree.
   ///
-  /// \note If the input graph is not (weakly) connected, a spanning 
+  /// \note If the input graph is not (weakly) connected, a spanning
   /// forest is calculated instead of a spanning tree.
 

lemon/lgf_reader.h

@@ -19 +19 @@
 ///\ingroup lemon_io
 ///\file
-///\brief \ref lgf-format "Lemon Graph Format" reader.
+///\brief \ref lgf-format "LEMON Graph Format" reader.
 
 
@@ -33 +33 @@
 
 #include <lemon/assert.h>
-#include <lemon/graph_utils.h>
+#include <lemon/core.h>
 
 #include <lemon/lgf_writer.h>
@@ -2302 +2302 @@
   ///
   /// This class can be used to read the sections, the map names and
-  /// the attributes from a file. Usually, the Lemon programs know
+  /// the attributes from a file. Usually, the LEMON programs know
   /// that, which type of graph, which maps and which attributes
   /// should be read from a file, but in general tools (like glemon)

lemon/lgf_writer.h

@@ -19 +19 @@
 ///\ingroup lemon_io
 ///\file
-///\brief \ref lgf-format "Lemon Graph Format" writer.
+///\brief \ref lgf-format "LEMON Graph Format" writer.
 
 
@@ -35 +35 @@
 
 #include <lemon/assert.h>
-#include <lemon/graph_utils.h>
+#include <lemon/core.h>
+#include <lemon/maps.h>
 
 namespace lemon {
@@ -934 +935 @@
     bool local_os;
 
-    Graph& _graph;
+    const Graph& _graph;
 
     std::string _nodes_caption;

lemon/list_graph.h

@@ -24 +24 @@
 ///\brief ListDigraph, ListGraph classes.
 
+#include <lemon/core.h>
+#include <lemon/error.h>
 #include <lemon/bits/graph_extender.h>
 
@@ -362 +364 @@
     }
 
+    ///\brief Erase a node from the digraph.
+    ///
+    ///Erase a node from the digraph.
+    ///
+    void erase(const Node& n) { Parent::erase(n); }
+
+    ///\brief Erase an arc from the digraph.
+    ///
+    ///Erase an arc from the digraph.
+    ///
+    void erase(const Arc& a) { Parent::erase(a); }
+
     /// Node validity check
 
@@ -382 +396 @@
     bool valid(Arc a) const { return Parent::valid(a); }
 
-    /// Change the target of \c e to \c n
-
-    /// Change the target of \c e to \c n
+    /// Change the target of \c a to \c n
+
+    /// Change the target of \c a to \c n
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
@@ -392 +406 @@
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void changeTarget(Arc e, Node n) {
-      Parent::changeTarget(e,n);
-    }
-    /// Change the source of \c e to \c n
-
-    /// Change the source of \c e to \c n
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
-    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
+    void changeTarget(Arc a, Node n) {
+      Parent::changeTarget(a,n);
+    }
+    /// Change the source of \c a to \c n
+
+    /// Change the source of \c a to \c n
+    ///
+    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
+    ///valid. However the <tt>ArcIt<tt>s and <tt>OutArcIt</tt>s are
     ///invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void changeSource(Arc e, Node n) {
-      Parent::changeSource(e,n);
+    void changeSource(Arc a, Node n) {
+      Parent::changeSource(a,n);
     }
 
@@ -829 +843 @@
 
     public:
-      operator Edge() const { return edgeFromId(id / 2); }
+      operator Edge() const { 
+        return id != -1 ? edgeFromId(id / 2) : INVALID; 
+      }
 
       Arc() {}
@@ -1101 +1117 @@
   protected:
 
-    void changeTarget(Edge e, Node n) {
+    void changeV(Edge e, Node n) {
       if(arcs[2 * e.id].next_out != -1) {
         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
@@ -1122 +1138 @@
     }
 
-    void changeSource(Edge e, Node n) {
+    void changeU(Edge e, Node n) {
       if(arcs[(2 * e.id) | 1].next_out != -1) {
         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
@@ -1206 +1222 @@
       return Parent::addEdge(s, t);
     }
+
+    /// \brief Erase a node from the graph.
+    ///
+    /// Erase a node from the graph.
+    ///
+    void erase(const Node& n) { Parent::erase(n); }
+
+    /// \brief Erase an edge from the graph.
+    ///
+    /// Erase an edge from the graph.
+    ///
+    void erase(const Edge& e) { Parent::erase(e); }
     /// Node validity check
 
@@ -1233 +1261 @@
     /// added to the graph.
     bool valid(Edge e) const { return Parent::valid(e); }
-    /// \brief Change the source of \c e to \c n
-    ///
-    /// This function changes the source of \c e to \c n.
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
-    ///referencing the changed arc remain
-    ///valid. However <tt>OutArcIt</tt>s are invalidated.
+    /// \brief Change the end \c u of \c e to \c n
+    ///
+    /// This function changes the end \c u of \c e to node \c n.
+    ///
+    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
+    ///changed edge are invalidated and if the changed node is the
+    ///base node of an iterator then this iterator is also
+    ///invalidated.
     ///
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    void changeSource(Edge e, Node n) {
-      Parent::changeSource(e,n);
-    }
-    /// \brief Change the target of \c e to \c n
-    ///
-    /// This function changes the target of \c e to \c n.
-    ///
-    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
-    /// valid. However the other iterators may be invalidated.
+    void changeU(Edge e, Node n) {
+      Parent::changeU(e,n);
+    }
+    /// \brief Change the end \c v of \c e to \c n
+    ///
+    /// This function changes the end \c v of \c e to \c n.
+    ///
+    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
+    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
+    ///base node of an iterator then this iterator is invalidated.
     ///
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    void changeTarget(Edge e, Node n) {
-      Parent::changeTarget(e,n);
-    }
-    /// \brief Change the source of \c e to \c n
-    ///
-    /// This function changes the source of \c e to \c n.
-    /// It also changes the proper node of the represented edge.
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
-    ///referencing the changed arc remain
-    ///valid. However <tt>OutArcIt</tt>s are invalidated.
-    ///
-    ///\warning This functionality cannot be used together with the
-    ///Snapshot feature.
-    void changeSource(Arc e, Node n) {
-      if (Parent::direction(e)) {
-        Parent::changeSource(e,n);
-      } else {
-        Parent::changeTarget(e,n);
-      }
-    }
-    /// \brief Change the target of \c e to \c n
-    ///
-    /// This function changes the target of \c e to \c n.
-    /// It also changes the proper node of the represented edge.
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
-    ///referencing the changed arc remain
-    ///valid. However <tt>InArcIt</tt>s are invalidated.
-    ///
-    ///\warning This functionality cannot be used together with the
-    ///Snapshot feature.
-    void changeTarget(Arc e, Node n) {
-      if (Parent::direction(e)) {
-        Parent::changeTarget(e,n);
-      } else {
-        Parent::changeSource(e,n);
-      }
+    void changeV(Edge e, Node n) {
+      Parent::changeV(e,n);
     }
     /// \brief Contract two nodes.
@@ -1312 +1306 @@
         if (r && runningNode(e) == a) {
           erase(e);
-        } else if (source(e) == b) {
-          changeSource(e, a);
+        } else if (u(e) == b) {
+          changeU(e, a);
         } else {
-          changeTarget(e, a);
+          changeV(e, a);
         }
         e = f;

lemon/maps.h

@@ -24 +24 @@
 #include <vector>
 
-#include <lemon/bits/utility.h>
-#include <lemon/bits/traits.h>
+#include <lemon/core.h>
 
 ///\file
@@ -1781 +1780 @@
   }
 
+  /// Provides an immutable and unique id for each item in the graph.
+
+  /// The IdMap class provides a unique and immutable id for each item of the
+  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
+  /// different items (nodes) get different ids <li>\b immutable: the id of an
+  /// item (node) does not change (even if you delete other nodes).  </ul>
+  /// Through this map you get access (i.e. can read) the inner id values of
+  /// the items stored in the graph. This map can be inverted with its member
+  /// class \c InverseMap or with the \c operator() member.
+  ///
+  template <typename _Graph, typename _Item>
+  class IdMap {
+  public:
+    typedef _Graph Graph;
+    typedef int Value;
+    typedef _Item Item;
+    typedef _Item Key;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor of the map.
+    explicit IdMap(const Graph& graph) : _graph(&graph) {}
+
+    /// \brief Gives back the \e id of the item.
+    ///
+    /// Gives back the immutable and unique \e id of the item.
+    int operator[](const Item& item) const { return _graph->id(item);}
+
+    /// \brief Gives back the item by its id.
+    ///
+    /// Gives back the item by its id.
+    Item operator()(int id) { return _graph->fromId(id, Item()); }
+
+  private:
+    const Graph* _graph;
+
+  public:
+
+    /// \brief The class represents the inverse of its owner (IdMap).
+    ///
+    /// The class represents the inverse of its owner (IdMap).
+    /// \see inverse()
+    class InverseMap {
+    public:
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for creating an id-to-item map.
+      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for creating an id-to-item map.
+      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
+
+      /// \brief Gives back the given item from its id.
+      ///
+      /// Gives back the given item from its id.
+      ///
+      Item operator[](int id) const { return _graph->fromId(id, Item());}
+
+    private:
+      const Graph* _graph;
+    };
+
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the IdMap.
+    InverseMap inverse() const { return InverseMap(*_graph);}
+
+  };
+
+
+  /// \brief General invertable graph-map type.
+
+  /// This type provides simple invertable graph-maps.
+  /// The InvertableMap wraps an arbitrary ReadWriteMap
+  /// and if a key is set to a new value then store it
+  /// in the inverse map.
+  ///
+  /// The values of the map can be accessed
+  /// with stl compatible forward iterator.
+  ///
+  /// \tparam _Graph The graph type.
+  /// \tparam _Item The item type of the graph.
+  /// \tparam _Value The value type of the map.
+  ///
+  /// \see IterableValueMap
+  template <typename _Graph, typename _Item, typename _Value>
+  class InvertableMap
+    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
+  private:
+
+    typedef typename ItemSetTraits<_Graph, _Item>::
+    template Map<_Value>::Type Map;
+    typedef _Graph Graph;
+
+    typedef std::map<_Value, _Item> Container;
+    Container _inv_map;
+
+  public:
+
+    /// The key type of InvertableMap (Node, Arc, Edge).
+    typedef typename Map::Key Key;
+    /// The value type of the InvertableMap.
+    typedef typename Map::Value Value;
+
+
+
+    /// \brief Constructor.
+    ///
+    /// Construct a new InvertableMap for the graph.
+    ///
+    explicit InvertableMap(const Graph& graph) : Map(graph) {}
+
+    /// \brief Forward iterator for values.
+    ///
+    /// This iterator is an stl compatible forward
+    /// iterator on the values of the map. The values can
+    /// be accessed in the [beginValue, endValue) range.
+    ///
+    class ValueIterator
+      : public std::iterator<std::forward_iterator_tag, Value> {
+      friend class InvertableMap;
+    private:
+      ValueIterator(typename Container::const_iterator _it)
+        : it(_it) {}
+    public:
+
+      ValueIterator() {}
+
+      ValueIterator& operator++() { ++it; return *this; }
+      ValueIterator operator++(int) {
+        ValueIterator tmp(*this);
+        operator++();
+        return tmp;
+      }
+
+      const Value& operator*() const { return it->first; }
+      const Value* operator->() const { return &(it->first); }
+
+      bool operator==(ValueIterator jt) const { return it == jt.it; }
+      bool operator!=(ValueIterator jt) const { return it != jt.it; }
+
+    private:
+      typename Container::const_iterator it;
+    };
+
+    /// \brief Returns an iterator to the first value.
+    ///
+    /// Returns an stl compatible iterator to the
+    /// first value of the map. The values of the
+    /// map can be accessed in the [beginValue, endValue)
+    /// range.
+    ValueIterator beginValue() const {
+      return ValueIterator(_inv_map.begin());
+    }
+
+    /// \brief Returns an iterator after the last value.
+    ///
+    /// Returns an stl compatible iterator after the
+    /// last value of the map. The values of the
+    /// map can be accessed in the [beginValue, endValue)
+    /// range.
+    ValueIterator endValue() const {
+      return ValueIterator(_inv_map.end());
+    }
+
+    /// \brief The setter function of the map.
+    ///
+    /// Sets the mapped value.
+    void set(const Key& key, const Value& val) {
+      Value oldval = Map::operator[](key);
+      typename Container::iterator it = _inv_map.find(oldval);
+      if (it != _inv_map.end() && it->second == key) {
+        _inv_map.erase(it);
+      }
+      _inv_map.insert(make_pair(val, key));
+      Map::set(key, val);
+    }
+
+    /// \brief The getter function of the map.
+    ///
+    /// It gives back the value associated with the key.
+    typename MapTraits<Map>::ConstReturnValue
+    operator[](const Key& key) const {
+      return Map::operator[](key);
+    }
+
+    /// \brief Gives back the item by its value.
+    ///
+    /// Gives back the item by its value.
+    Key operator()(const Value& key) const {
+      typename Container::const_iterator it = _inv_map.find(key);
+      return it != _inv_map.end() ? it->second : INVALID;
+    }
+
+  protected:
+
+    /// \brief Erase the key from the map.
+    ///
+    /// Erase the key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const Key& key) {
+      Value val = Map::operator[](key);
+      typename Container::iterator it = _inv_map.find(val);
+      if (it != _inv_map.end() && it->second == key) {
+        _inv_map.erase(it);
+      }
+      Map::erase(key);
+    }
+
+    /// \brief Erase more keys from the map.
+    ///
+    /// Erase more keys from the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const std::vector<Key>& keys) {
+      for (int i = 0; i < int(keys.size()); ++i) {
+        Value val = Map::operator[](keys[i]);
+        typename Container::iterator it = _inv_map.find(val);
+        if (it != _inv_map.end() && it->second == keys[i]) {
+          _inv_map.erase(it);
+        }
+      }
+      Map::erase(keys);
+    }
+
+    /// \brief Clear the keys from the map and inverse map.
+    ///
+    /// Clear the keys from the map and inverse map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void clear() {
+      _inv_map.clear();
+      Map::clear();
+    }
+
+  public:
+
+    /// \brief The inverse map type.
+    ///
+    /// The inverse of this map. The subscript operator of the map
+    /// gives back always the item what was last assigned to the value.
+    class InverseMap {
+    public:
+      /// \brief Constructor of the InverseMap.
+      ///
+      /// Constructor of the InverseMap.
+      explicit InverseMap(const InvertableMap& inverted)
+        : _inverted(inverted) {}
+
+      /// The value type of the InverseMap.
+      typedef typename InvertableMap::Key Value;
+      /// The key type of the InverseMap.
+      typedef typename InvertableMap::Value Key;
+
+      /// \brief Subscript operator.
+      ///
+      /// Subscript operator. It gives back always the item
+      /// what was last assigned to the value.
+      Value operator[](const Key& key) const {
+        return _inverted(key);
+      }
+
+    private:
+      const InvertableMap& _inverted;
+    };
+
+    /// \brief It gives back the just readable inverse map.
+    ///
+    /// It gives back the just readable inverse map.
+    InverseMap inverse() const {
+      return InverseMap(*this);
+    }
+
+
+
+  };
+
+  /// \brief Provides a mutable, continuous and unique descriptor for each
+  /// item in the graph.
+  ///
+  /// The DescriptorMap class provides a unique and continuous (but mutable)
+  /// descriptor (id) for each item of the same type (e.g. node) in the
+  /// graph. This id is <ul><li>\b unique: different items (nodes) get
+  /// different ids <li>\b continuous: the range of the ids is the set of
+  /// integers between 0 and \c n-1, where \c n is the number of the items of
+  /// this type (e.g. nodes) (so the id of a node can change if you delete an
+  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
+  /// with its member class \c InverseMap, or with the \c operator() member.
+  ///
+  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
+  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
+  /// Edge.
+  template <typename _Graph, typename _Item>
+  class DescriptorMap
+    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
+
+    typedef _Item Item;
+    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
+
+  public:
+    /// The graph class of DescriptorMap.
+    typedef _Graph Graph;
+
+    /// The key type of DescriptorMap (Node, Arc, Edge).
+    typedef typename Map::Key Key;
+    /// The value type of DescriptorMap.
+    typedef typename Map::Value Value;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for descriptor map.
+    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
+      Item it;
+      const typename Map::Notifier* nf = Map::notifier();
+      for (nf->first(it); it != INVALID; nf->next(it)) {
+        Map::set(it, _inv_map.size());
+        _inv_map.push_back(it);
+      }
+    }
+
+  protected:
+
+    /// \brief Add a new key to the map.
+    ///
+    /// Add a new key to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void add(const Item& item) {
+      Map::add(item);
+      Map::set(item, _inv_map.size());
+      _inv_map.push_back(item);
+    }
+
+    /// \brief Add more new keys to the map.
+    ///
+    /// Add more new keys to the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void add(const std::vector<Item>& items) {
+      Map::add(items);
+      for (int i = 0; i < int(items.size()); ++i) {
+        Map::set(items[i], _inv_map.size());
+        _inv_map.push_back(items[i]);
+      }
+    }
+
+    /// \brief Erase the key from the map.
+    ///
+    /// Erase the key from the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const Item& item) {
+      Map::set(_inv_map.back(), Map::operator[](item));
+      _inv_map[Map::operator[](item)] = _inv_map.back();
+      _inv_map.pop_back();
+      Map::erase(item);
+    }
+
+    /// \brief Erase more keys from the map.
+    ///
+    /// Erase more keys from the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void erase(const std::vector<Item>& items) {
+      for (int i = 0; i < int(items.size()); ++i) {
+        Map::set(_inv_map.back(), Map::operator[](items[i]));
+        _inv_map[Map::operator[](items[i])] = _inv_map.back();
+        _inv_map.pop_back();
+      }
+      Map::erase(items);
+    }
+
+    /// \brief Build the unique map.
+    ///
+    /// Build the unique map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void build() {
+      Map::build();
+      Item it;
+      const typename Map::Notifier* nf = Map::notifier();
+      for (nf->first(it); it != INVALID; nf->next(it)) {
+        Map::set(it, _inv_map.size());
+        _inv_map.push_back(it);
+      }
+    }
+
+    /// \brief Clear the keys from the map.
+    ///
+    /// Clear the keys from the map. It is called by the
+    /// \c AlterationNotifier.
+    virtual void clear() {
+      _inv_map.clear();
+      Map::clear();
+    }
+
+  public:
+
+    /// \brief Returns the maximal value plus one.
+    ///
+    /// Returns the maximal value plus one in the map.
+    unsigned int size() const {
+      return _inv_map.size();
+    }
+
+    /// \brief Swaps the position of the two items in the map.
+    ///
+    /// Swaps the position of the two items in the map.
+    void swap(const Item& p, const Item& q) {
+      int pi = Map::operator[](p);
+      int qi = Map::operator[](q);
+      Map::set(p, qi);
+      _inv_map[qi] = p;
+      Map::set(q, pi);
+      _inv_map[pi] = q;
+    }
+
+    /// \brief Gives back the \e descriptor of the item.
+    ///
+    /// Gives back the mutable and unique \e descriptor of the map.
+    int operator[](const Item& item) const {
+      return Map::operator[](item);
+    }
+
+    /// \brief Gives back the item by its descriptor.
+    ///
+    /// Gives back th item by its descriptor.
+    Item operator()(int id) const {
+      return _inv_map[id];
+    }
+
+  private:
+
+    typedef std::vector<Item> Container;
+    Container _inv_map;
+
+  public:
+    /// \brief The inverse map type of DescriptorMap.
+    ///
+    /// The inverse map type of DescriptorMap.
+    class InverseMap {
+    public:
+      /// \brief Constructor of the InverseMap.
+      ///
+      /// Constructor of the InverseMap.
+      explicit InverseMap(const DescriptorMap& inverted)
+        : _inverted(inverted) {}
+
+
+      /// The value type of the InverseMap.
+      typedef typename DescriptorMap::Key Value;
+      /// The key type of the InverseMap.
+      typedef typename DescriptorMap::Value Key;
+
+      /// \brief Subscript operator.
+      ///
+      /// Subscript operator. It gives back the item
+      /// that the descriptor belongs to currently.
+      Value operator[](const Key& key) const {
+        return _inverted(key);
+      }
+
+      /// \brief Size of the map.
+      ///
+      /// Returns the size of the map.
+      unsigned int size() const {
+        return _inverted.size();
+      }
+
+    private:
+      const DescriptorMap& _inverted;
+    };
+
+    /// \brief Gives back the inverse of the map.
+    ///
+    /// Gives back the inverse of the map.
+    const InverseMap inverse() const {
+      return InverseMap(*this);
+    }
+  };
+
+  /// \brief Returns the source of the given arc.
+  ///
+  /// The SourceMap gives back the source Node of the given arc.
+  /// \see TargetMap
+  template <typename Digraph>
+  class SourceMap {
+  public:
+
+    typedef typename Digraph::Node Value;
+    typedef typename Digraph::Arc Key;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \param _digraph The digraph that the map belongs to.
+    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
+
+    /// \brief The subscript operator.
+    ///
+    /// The subscript operator.
+    /// \param arc The arc
+    /// \return The source of the arc
+    Value operator[](const Key& arc) const {
+      return _digraph.source(arc);
+    }
+
+  private:
+    const Digraph& _digraph;
+  };
+
+  /// \brief Returns a \ref SourceMap class.
+  ///
+  /// This function just returns an \ref SourceMap class.
+  /// \relates SourceMap
+  template <typename Digraph>
+  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
+    return SourceMap<Digraph>(digraph);
+  }
+
+  /// \brief Returns the target of the given arc.
+  ///
+  /// The TargetMap gives back the target Node of the given arc.
+  /// \see SourceMap
+  template <typename Digraph>
+  class TargetMap {
+  public:
+
+    typedef typename Digraph::Node Value;
+    typedef typename Digraph::Arc Key;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \param _digraph The digraph that the map belongs to.
+    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
+
+    /// \brief The subscript operator.
+    ///
+    /// The subscript operator.
+    /// \param e The arc
+    /// \return The target of the arc
+    Value operator[](const Key& e) const {
+      return _digraph.target(e);
+    }
+
+  private:
+    const Digraph& _digraph;
+  };
+
+  /// \brief Returns a \ref TargetMap class.
+  ///
+  /// This function just returns a \ref TargetMap class.
+  /// \relates TargetMap
+  template <typename Digraph>
+  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
+    return TargetMap<Digraph>(digraph);
+  }
+
+  /// \brief Returns the "forward" directed arc view of an edge.
+  ///
+  /// Returns the "forward" directed arc view of an edge.
+  /// \see BackwardMap
+  template <typename Graph>
+  class ForwardMap {
+  public:
+
+    typedef typename Graph::Arc Value;
+    typedef typename Graph::Edge Key;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \param _graph The graph that the map belongs to.
+    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
+
+    /// \brief The subscript operator.
+    ///
+    /// The subscript operator.
+    /// \param key An edge
+    /// \return The "forward" directed arc view of edge
+    Value operator[](const Key& key) const {
+      return _graph.direct(key, true);
+    }
+
+  private:
+    const Graph& _graph;
+  };
+
+  /// \brief Returns a \ref ForwardMap class.
+  ///
+  /// This function just returns an \ref ForwardMap class.
+  /// \relates ForwardMap
+  template <typename Graph>
+  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
+    return ForwardMap<Graph>(graph);
+  }
+
+  /// \brief Returns the "backward" directed arc view of an edge.
+  ///
+  /// Returns the "backward" directed arc view of an edge.
+  /// \see ForwardMap
+  template <typename Graph>
+  class BackwardMap {
+  public:
+
+    typedef typename Graph::Arc Value;
+    typedef typename Graph::Edge Key;
+
+    /// \brief Constructor
+    ///
+    /// Constructor
+    /// \param _graph The graph that the map belongs to.
+    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
+
+    /// \brief The subscript operator.
+    ///
+    /// The subscript operator.
+    /// \param key An edge
+    /// \return The "backward" directed arc view of edge
+    Value operator[](const Key& key) const {
+      return _graph.direct(key, false);
+    }
+
+  private:
+    const Graph& _graph;
+  };
+
+  /// \brief Returns a \ref BackwardMap class
+
+  /// This function just returns a \ref BackwardMap class.
+  /// \relates BackwardMap
+  template <typename Graph>
+  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
+    return BackwardMap<Graph>(graph);
+  }
+
+  /// \brief Potential difference map
+  ///
+  /// If there is an potential map on the nodes then we
+  /// can get an arc map as we get the substraction of the
+  /// values of the target and source.
+  template <typename Digraph, typename NodeMap>
+  class PotentialDifferenceMap {
+  public:
+    typedef typename Digraph::Arc Key;
+    typedef typename NodeMap::Value Value;
+
+    /// \brief Constructor
+    ///
+    /// Contructor of the map
+    explicit PotentialDifferenceMap(const Digraph& digraph,
+                                    const NodeMap& potential)
+      : _digraph(digraph), _potential(potential) {}
+
+    /// \brief Const subscription operator
+    ///
+    /// Const subscription operator
+    Value operator[](const Key& arc) const {
+      return _potential[_digraph.target(arc)] -
+        _potential[_digraph.source(arc)];
+    }
+
+  private:
+    const Digraph& _digraph;
+    const NodeMap& _potential;
+  };
+
+  /// \brief Returns a PotentialDifferenceMap.
+  ///
+  /// This function just returns a PotentialDifferenceMap.
+  /// \relates PotentialDifferenceMap
+  template <typename Digraph, typename NodeMap>
+  PotentialDifferenceMap<Digraph, NodeMap>
+  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
+    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
+  }
+
+  /// \brief Map of the node in-degrees.
+  ///
+  /// This map returns the in-degree of a node. Once it is constructed,
+  /// the degrees are stored in a standard NodeMap, so each query is done
+  /// in constant time. On the other hand, the values are updated automatically
+  /// whenever the digraph changes.
+  ///
+  /// \warning Besides addNode() and addArc(), a digraph structure may provide
+  /// alternative ways to modify the digraph. The correct behavior of InDegMap
+  /// is not guarantied if these additional features are used. For example
+  /// the functions \ref ListDigraph::changeSource() "changeSource()",
+  /// \ref ListDigraph::changeTarget() "changeTarget()" and
+  /// \ref ListDigraph::reverseArc() "reverseArc()"
+  /// of \ref ListDigraph will \e not update the degree values correctly.
+  ///
+  /// \sa OutDegMap
+
+  template <typename _Digraph>
+  class InDegMap
+    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
+      ::ItemNotifier::ObserverBase {
+
+  public:
+
+    typedef _Digraph Digraph;
+    typedef int Value;
+    typedef typename Digraph::Node Key;
+
+    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
+    ::ItemNotifier::ObserverBase Parent;
+
+  private:
+
+    class AutoNodeMap
+      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
+    public:
+
+      typedef typename ItemSetTraits<Digraph, Key>::
+      template Map<int>::Type Parent;
+
+      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
+
+      virtual void add(const Key& key) {
+        Parent::add(key);
+        Parent::set(key, 0);
+      }
+
+      virtual void add(const std::vector<Key>& keys) {
+        Parent::add(keys);
+        for (int i = 0; i < int(keys.size()); ++i) {
+          Parent::set(keys[i], 0);
+        }
+      }
+
+      virtual void build() {
+        Parent::build();
+        Key it;
+        typename Parent::Notifier* nf = Parent::notifier();
+        for (nf->first(it); it != INVALID; nf->next(it)) {
+          Parent::set(it, 0);
+        }
+      }
+    };
+
+  public:
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating in-degree map.
+    explicit InDegMap(const Digraph& digraph)
+      : _digraph(digraph), _deg(digraph) {
+      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
+
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = countInArcs(_digraph, it);
+      }
+    }
+
+    /// Gives back the in-degree of a Node.
+    int operator[](const Key& key) const {
+      return _deg[key];
+    }
+
+  protected:
+
+    typedef typename Digraph::Arc Arc;
+
+    virtual void add(const Arc& arc) {
+      ++_deg[_digraph.target(arc)];
+    }
+
+    virtual void add(const std::vector<Arc>& arcs) {
+      for (int i = 0; i < int(arcs.size()); ++i) {
+        ++_deg[_digraph.target(arcs[i])];
+      }
+    }
+
+    virtual void erase(const Arc& arc) {
+      --_deg[_digraph.target(arc)];
+    }
+
+    virtual void erase(const std::vector<Arc>& arcs) {
+      for (int i = 0; i < int(arcs.size()); ++i) {
+        --_deg[_digraph.target(arcs[i])];
+      }
+    }
+
+    virtual void build() {
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = countInArcs(_digraph, it);
+      }
+    }
+
+    virtual void clear() {
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = 0;
+      }
+    }
+  private:
+
+    const Digraph& _digraph;
+    AutoNodeMap _deg;
+  };
+
+  /// \brief Map of the node out-degrees.
+  ///
+  /// This map returns the out-degree of a node. Once it is constructed,
+  /// the degrees are stored in a standard NodeMap, so each query is done
+  /// in constant time. On the other hand, the values are updated automatically
+  /// whenever the digraph changes.
+  ///
+  /// \warning Besides addNode() and addArc(), a digraph structure may provide
+  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
+  /// is not guarantied if these additional features are used. For example
+  /// the functions \ref ListDigraph::changeSource() "changeSource()",
+  /// \ref ListDigraph::changeTarget() "changeTarget()" and
+  /// \ref ListDigraph::reverseArc() "reverseArc()"
+  /// of \ref ListDigraph will \e not update the degree values correctly.
+  ///
+  /// \sa InDegMap
+
+  template <typename _Digraph>
+  class OutDegMap
+    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
+      ::ItemNotifier::ObserverBase {
+
+  public:
+
+    typedef _Digraph Digraph;
+    typedef int Value;
+    typedef typename Digraph::Node Key;
+
+    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
+    ::ItemNotifier::ObserverBase Parent;
+
+  private:
+
+    class AutoNodeMap
+      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
+    public:
+
+      typedef typename ItemSetTraits<Digraph, Key>::
+      template Map<int>::Type Parent;
+
+      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
+
+      virtual void add(const Key& key) {
+        Parent::add(key);
+        Parent::set(key, 0);
+      }
+      virtual void add(const std::vector<Key>& keys) {
+        Parent::add(keys);
+        for (int i = 0; i < int(keys.size()); ++i) {
+          Parent::set(keys[i], 0);
+        }
+      }
+      virtual void build() {
+        Parent::build();
+        Key it;
+        typename Parent::Notifier* nf = Parent::notifier();
+        for (nf->first(it); it != INVALID; nf->next(it)) {
+          Parent::set(it, 0);
+        }
+      }
+    };
+
+  public:
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating out-degree map.
+    explicit OutDegMap(const Digraph& digraph)
+      : _digraph(digraph), _deg(digraph) {
+      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
+
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = countOutArcs(_digraph, it);
+      }
+    }
+
+    /// Gives back the out-degree of a Node.
+    int operator[](const Key& key) const {
+      return _deg[key];
+    }
+
+  protected:
+
+    typedef typename Digraph::Arc Arc;
+
+    virtual void add(const Arc& arc) {
+      ++_deg[_digraph.source(arc)];
+    }
+
+    virtual void add(const std::vector<Arc>& arcs) {
+      for (int i = 0; i < int(arcs.size()); ++i) {
+        ++_deg[_digraph.source(arcs[i])];
+      }
+    }
+
+    virtual void erase(const Arc& arc) {
+      --_deg[_digraph.source(arc)];
+    }
+
+    virtual void erase(const std::vector<Arc>& arcs) {
+      for (int i = 0; i < int(arcs.size()); ++i) {
+        --_deg[_digraph.source(arcs[i])];
+      }
+    }
+
+    virtual void build() {
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = countOutArcs(_digraph, it);
+      }
+    }
+
+    virtual void clear() {
+      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
+        _deg[it] = 0;
+      }
+    }
+  private:
+
+    const Digraph& _digraph;
+    AutoNodeMap _deg;
+  };
+
   /// @}
 }

lemon/path.h

@@ -29 +29 @@
 
 #include <lemon/error.h>
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 #include <lemon/concepts/path.h>
 
@@ -83 +83 @@
     }
 
-    /// \brief Lemon style iterator for path arcs
+    /// \brief LEMON style iterator for path arcs
     ///
     /// This class is used to iterate on the arcs of the paths.

lemon/smart_graph.h

@@ -26 +26 @@
 #include <vector>
 
-#include <lemon/bits/invalid.h>
-
-#include <lemon/bits/base_extender.h>
-#include <lemon/bits/graph_extender.h>
-
-#include <lemon/bits/utility.h>
+#include <lemon/core.h>
 #include <lemon/error.h>
-
 #include <lemon/bits/graph_extender.h>
 
@@ -472 +466 @@
 
     public:
-      operator Edge() const { return edgeFromId(_id / 2); }
+      operator Edge() const { 
+        return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
+      }
 
       Arc() {}

lemon/unionfind.h

@@ -31 +31 @@
 #include <functional>
 
-#include <lemon/bits/invalid.h>
+#include <lemon/core.h>
 
 namespace lemon {
@@ -498 +498 @@
     }
 
-    /// \brief Lemon style iterator for the representant items.
+    /// \brief LEMON style iterator for the representant items.
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
@@ -550 +550 @@
     };
 
-    /// \brief Lemon style iterator for the items of a component.
+    /// \brief LEMON style iterator for the items of a component.
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
@@ -808 +808 @@
     }
 
-    /// \brief Lemon style iterator for the classes.
+    /// \brief LEMON style iterator for the classes.
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
@@ -860 +860 @@
     };
 
-    /// \brief Lemon style iterator for the items of a component.
+    /// \brief LEMON style iterator for the items of a component.
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates
@@ -1656 +1656 @@
     }
 
-    /// \brief Lemon style iterator for the items of a class.
+    /// \brief LEMON style iterator for the items of a class.
     ///
     /// ClassIt is a lemon style iterator for the components. It iterates

test/CMakeLists.txt

@@ -1 @@
-include_directories (${LEMON_SOURCE_DIR})
+INCLUDE_DIRECTORIES(${CMAKE_SOURCE_DIR})
 
-link_directories (${LEMON_BINARY_DIR}/lemon)
+LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
 
-set (TESTS
+SET(TESTS
   bfs_test
   counter_test
@@ -17 +17 @@
   kruskal_test
   maps_test
+  random_test
   path_test
-  random_test
   time_measure_test
   unionfind_test)
 
-foreach (TEST_NAME ${TESTS})
-  add_executable (${TEST_NAME} ${TEST_NAME}.cc)
-  target_link_libraries (${TEST_NAME} lemon)
-  add_test(${TEST_NAME} ${TEST_NAME})
-endforeach (TEST_NAME)
+FOREACH(TEST_NAME ${TESTS})
+  ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
+  TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
+  ADD_TEST(${TEST_NAME} ${TEST_NAME})
+ENDFOREACH(TEST_NAME)

test/Makefile.am

@@ -4 +4 @@
 noinst_HEADERS += \
         test/graph_test.h \
-        test/graph_maps_test.h \
         test/test_tools.h
 

test/bfs_test.cc

@@ -20 +20 @@
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
 #include <lemon/bfs.h>
 #include <lemon/path.h>
@@ -27 +28 @@
 
 using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "@arcs\n"
+  "     label\n"
+  "0 1  0\n"
+  "1 2  1\n"
+  "2 3  2\n"
+  "3 4  3\n"
+  "0 3  4\n"
+  "0 3  5\n"
+  "5 2  6\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 4\n";
 
 void checkBfsCompile()
@@ -50 +73 @@
   n  = bfs_test.predNode(n);
   d  = bfs_test.distMap();
+
   p  = bfs_test.predMap();
   //  pn = bfs_test.predNodeMap();
@@ -81 +105 @@
   Digraph G;
   Node s, t;
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  s=ps.outer[2];
-  t=ps.inner[0];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    node("source", s).
+    node("target", t).
+    run();
 
   Bfs<Digraph> bfs_test(G);
   bfs_test.run(s);
 
-  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
+  check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
 
   Path<Digraph> p = bfs_test.path(t);
-  check(p.length()==3,"path() found a wrong path.");
+  check(p.length()==2,"path() found a wrong path.");
   check(checkPath(G, p),"path() found a wrong path.");
   check(pathSource(G, p) == s,"path() found a wrong path.");
@@ -98 +124 @@
 
 
-  for(ArcIt e(G); e==INVALID; ++e) {
-    Node u=G.source(e);
-    Node v=G.target(e);
+  for(ArcIt a(G); a!=INVALID; ++a) {
+    Node u=G.source(a);
+    Node v=G.target(a);
     check( !bfs_test.reached(u) ||
-           (bfs_test.dist(v) > bfs_test.dist(u)+1),
-           "Wrong output.");
+           (bfs_test.dist(v) <= bfs_test.dist(u)+1),
+           "Wrong output." << G.id(v) << ' ' << G.id(u));
   }
 
-  for(NodeIt v(G); v==INVALID; ++v) {
-    check(bfs_test.reached(v),"Each node should be reached.");
-    if ( bfs_test.predArc(v)!=INVALID ) {
-      Arc e=bfs_test.predArc(v);
-      Node u=G.source(e);
-      check(u==bfs_test.predNode(v),"Wrong tree.");
-      check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
-            "Wrong distance. Difference: "
-            << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
-                        - 1));
+  for(NodeIt v(G); v!=INVALID; ++v) {
+    if (bfs_test.reached(v)) {
+      check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (bfs_test.predArc(v)!=INVALID ) {
+        Arc a=bfs_test.predArc(v);
+        Node u=G.source(a);
+        check(u==bfs_test.predNode(v),"Wrong tree.");
+        check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
+              "Wrong distance. Difference: "
+              << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
+                          - 1));
+      }
     }
   }

test/dfs_test.cc

@@ -20 +20 @@
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
+#include <lemon/lgf_reader.h>
+
 #include <lemon/dfs.h>
 #include <lemon/path.h>
@@ -27 +29 @@
 
 using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "@arcs\n"
+  "     label\n"
+  "0 1  0\n"
+  "1 2  1\n"
+  "2 3  2\n"
+  "1 4  3\n"
+  "4 2  4\n"
+  "4 5  5\n"
+  "5 0  6\n"
+  "6 3  7\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 5\n";
 
 void checkDfsCompile()
@@ -40 +66 @@
   DType::DistMap d(G);
   DType::PredMap p(G);
-  //  DType::PredNodeMap pn(G);
 
   DType dfs_test(G);
@@ -51 +76 @@
   d  = dfs_test.distMap();
   p  = dfs_test.predMap();
-  //  pn = dfs_test.predNodeMap();
   b  = dfs_test.reached(n);
 
@@ -81 +105 @@
   Digraph G;
   Node s, t;
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  s=ps.outer[2];
-  t=ps.inner[0];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    node("source", s).
+    node("target", t).
+    run();
 
   Dfs<Digraph> dfs_test(G);
@@ -96 +122 @@
 
   for(NodeIt v(G); v!=INVALID; ++v) {
-    check(dfs_test.reached(v),"Each node should be reached.");
-    if ( dfs_test.predArc(v)!=INVALID ) {
-      Arc e=dfs_test.predArc(v);
-      Node u=G.source(e);
-      check(u==dfs_test.predNode(v),"Wrong tree.");
-      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
-            "Wrong distance. (" << dfs_test.dist(u) << "->"
-            <<dfs_test.dist(v) << ')');
+    if (dfs_test.reached(v)) {
+      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (dfs_test.predArc(v)!=INVALID ) {
+        Arc e=dfs_test.predArc(v);
+        Node u=G.source(e);
+        check(u==dfs_test.predNode(v),"Wrong tree.");
+        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
+              "Wrong distance. (" << dfs_test.dist(u) << "->"
+              <<dfs_test.dist(v) << ')');
+      }
     }
   }

test/digraph_test.cc

@@ -25 +25 @@
 #include "test_tools.h"
 #include "graph_test.h"
-#include "graph_maps_test.h"
 
 using namespace lemon;
 using namespace lemon::concepts;
 
-void check_concepts() {
+template <class Digraph>
+void checkDigraph() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G;
+
+  checkGraphNodeList(G, 0);
+  checkGraphArcList(G, 0);
+
+  Node
+    n1 = G.addNode(),
+    n2 = G.addNode(),
+    n3 = G.addNode();
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 0);
+
+  Arc a1 = G.addArc(n1, n2);
+  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 1);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 0);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 0);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 0);
+
+  checkGraphConArcList(G, 1);
+
+  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+
+  checkGraphConArcList(G, 4);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+}
+
+
+void checkConcepts() {
   { // Checking digraph components
     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
@@ -52 +103 @@
     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
-    checkDigraphIterators<ListDigraph>();
   }
   { // Checking SmartDigraph
@@ -59 +109 @@
     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
-    checkDigraphIterators<SmartDigraph>();
   }
 //  { // Checking FullDigraph
 //    checkConcept<Digraph, FullDigraph>();
-//    checkDigraphIterators<FullDigraph>();
 //  }
 //  { // Checking HyperCubeDigraph
 //    checkConcept<Digraph, HyperCubeDigraph>();
-//    checkDigraphIterators<HyperCubeDigraph>();
 //  }
 }
 
 template <typename Digraph>
-void check_graph_validity() {
+void checkDigraphValidity() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph g;
@@ -93 +140 @@
 
 template <typename Digraph>
-void check_graph_validity_erase() {
+void checkDigraphValidityErase() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph g;
@@ -121 +168 @@
 }
 
-void check_digraphs() {
+void checkDigraphs() {
   { // Checking ListDigraph
     checkDigraph<ListDigraph>();
-    checkGraphNodeMap<ListDigraph>();
-    checkGraphArcMap<ListDigraph>();
-
-    check_graph_validity_erase<ListDigraph>();
+    checkDigraphValidityErase<ListDigraph>();
   }
   { // Checking SmartDigraph
     checkDigraph<SmartDigraph>();
-    checkGraphNodeMap<SmartDigraph>();
-    checkGraphArcMap<SmartDigraph>();
-
-    check_graph_validity<SmartDigraph>();
+    checkDigraphValidity<SmartDigraph>();
   }
 }
 
 int main() {
-  check_concepts();
-  check_digraphs();
+  checkDigraphs();
+  checkConcepts();
   return 0;
 }

test/dijkstra_test.cc

@@ -20 +20 @@
 #include <lemon/smart_graph.h>
 #include <lemon/list_graph.h>
-#include <lemon/graph_utils.h>
+#include <lemon/lgf_reader.h>
+
 #include <lemon/dijkstra.h>
 #include <lemon/path.h>
@@ -28 +29 @@
 
 using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "@arcs\n"
+  "     label length\n"
+  "0 1  0     1\n"
+  "1 2  1     1\n"
+  "2 3  2     1\n"
+  "0 3  4     5\n"
+  "0 3  5     10\n"
+  "0 3  6     7\n"
+  "4 2  7     1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 3\n";
 
 void checkDijkstraCompile()
@@ -86 +108 @@
   Node s, t;
   LengthMap length(G);
-  PetStruct<Digraph> ps = addPetersen(G, 5);
 
-  for(int i=0;i<5;i++) {
-    length[ps.outcir[i]]=4;
-    length[ps.incir[i]]=1;
-    length[ps.chords[i]]=10;
-  }
-  s=ps.outer[0];
-  t=ps.inner[1];
+  std::istringstream input(test_lgf);
+  digraphReader(input, G).
+    arcMap("length", length).
+    node("source", s).
+    node("target", t).
+    run();
 
   Dijkstra<Digraph, LengthMap>
@@ -100 +120 @@
   dijkstra_test.run(s);
 
-  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
+  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
 
   Path<Digraph> p = dijkstra_test.path(t);
-  check(p.length()==4,"getPath() found a wrong path.");
+  check(p.length()==3,"getPath() found a wrong path.");
   check(checkPath(G, p),"path() found a wrong path.");
   check(pathSource(G, p) == s,"path() found a wrong path.");
@@ -117 +137 @@
   }
 
-  for(NodeIt v(G); v!=INVALID; ++v){
-    check(dijkstra_test.reached(v),"Each node should be reached.");
-    if ( dijkstra_test.predArc(v)!=INVALID ) {
-      Arc e=dijkstra_test.predArc(v);
-      Node u=G.source(e);
-      check(u==dijkstra_test.predNode(v),"Wrong tree.");
-      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
-            "Wrong distance! Difference: " <<
-            std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+  for(NodeIt v(G); v!=INVALID; ++v) {
+    if (dijkstra_test.reached(v)) {
+      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
+      if (dijkstra_test.predArc(v)!=INVALID ) {
+        Arc e=dijkstra_test.predArc(v);
+        Node u=G.source(e);
+        check(u==dijkstra_test.predNode(v),"Wrong tree.");
+        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
+              "Wrong distance! Difference: " <<
+              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
+      }
     }
   }

test/dim_test.cc

@@ -59 +59 @@
   box1.add(b);
 
-  check(box1.bottomLeft().x==1 &&
-        box1.bottomLeft().y==2 &&
-        box1.topRight().x==3 &&
-        box1.topRight().y==4,
+  check(box1.left()==1 && box1.bottom()==2 &&
+        box1.right()==3 && box1.top()==4,
         "Wrong addition of points to dim2::BoundingBox.");
 
-  p.x=2; p.y=3;
-  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
+  check(box1.inside(Point(2,3)), "Wrong inside() in dim2::BoundingBox.");
+  check(box1.inside(Point(1,3)), "Wrong inside() in dim2::BoundingBox.");
+  check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::BoundingBox.");
 
-  p.x=1; p.y=3;
-  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
-
-  p.x=0; p.y=3;
-  check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
-
-  BB box2(p);
+  BB box2(Point(2,2));
   check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
-
-  box2.add(box1);
-  check(box2.inside(p), "Wrong inside() in dim2::BoundingBox.");
+  
+  box2.bottomLeft(Point(2,0));
+  box2.topRight(Point(5,3));
+  BB box3 = box1 & box2;
+  check(!box3.empty() &&
+        box3.left()==2 && box3.bottom()==2 && 
+        box3.right()==3 && box3.top()==3,
+        "Wrong intersection of two dim2::BoundingBox objects.");
+  
+  box1.add(box2);
+  check(!box1.empty() &&
+        box1.left()==1 && box1.bottom()==0 &&
+        box1.right()==5 && box1.top()==4,
+        "Wrong addition of two dim2::BoundingBox objects.");
 
   return 0;

test/error_test.cc

@@ -30 +30 @@
 #ifdef LEMON_DISABLE_ASSERTS
 #undef LEMON_DISABLE_ASSERTS
+#endif
+
+#ifdef NDEBUG
+#undef NDEBUG
 #endif
 

test/graph_copy_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/lgf_reader.h>
-#include <lemon/graph_utils.h>
 #include <lemon/error.h>
 

test/graph_test.cc

@@ -25 +25 @@
 #include "test_tools.h"
 #include "graph_test.h"
-#include "graph_maps_test.h"
 
 using namespace lemon;
 using namespace lemon::concepts;
 
-void check_concepts() {
+template <class Graph>
+void checkGraph() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  checkGraphNodeList(G, 0);
+  checkGraphEdgeList(G, 0);
+
+  Node
+    n1 = G.addNode(),
+    n2 = G.addNode(),
+    n3 = G.addNode();
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 0);
+
+  Edge e1 = G.addEdge(n1, n2);
+  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
+        "Wrong edge");
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 2);
+  checkGraphEdgeList(G, 1);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 0);
+
+  checkGraphIncEdgeList(G, n1, 1);
+  checkGraphIncEdgeList(G, n2, 1);
+  checkGraphIncEdgeList(G, n3, 0);
+
+  checkGraphConArcList(G, 2);
+  checkGraphConEdgeList(G, 1);
+
+  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 6);
+  checkGraphEdgeList(G, 3);
+
+  checkGraphOutArcList(G, n1, 2);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 3);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphIncEdgeList(G, n1, 2);
+  checkGraphIncEdgeList(G, n2, 3);
+  checkGraphIncEdgeList(G, n3, 1);
+
+  checkGraphConArcList(G, 6);
+  checkGraphConEdgeList(G, 3);
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+}
+
+void checkConcepts() {
   { // Checking graph components
     checkConcept<BaseGraphComponent, BaseGraphComponent >();
@@ -52 +118 @@
     checkConcept<ClearableGraphComponent<>, ListGraph>();
     checkConcept<ErasableGraphComponent<>, ListGraph>();
-    checkGraphIterators<ListGraph>();
   }
   { // Checking SmartGraph
@@ -59 +124 @@
     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
     checkConcept<ClearableGraphComponent<>, SmartGraph>();
-    checkGraphIterators<SmartGraph>();
   }
 //  { // Checking FullGraph
@@ -72 +136 @@
 
 template <typename Graph>
-void check_graph_validity() {
+void checkGraphValidity() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph g;
@@ -95 +159 @@
 
 template <typename Graph>
-void check_graph_validity_erase() {
+void checkGraphValidityErase() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph g;
@@ -169 +233 @@
 // }
 
-void check_graphs() {
+void checkGraphs() {
   { // Checking ListGraph
     checkGraph<ListGraph>();
-    checkGraphNodeMap<ListGraph>();
-    checkGraphEdgeMap<ListGraph>();
-
-    check_graph_validity_erase<ListGraph>();
+    checkGraphValidityErase<ListGraph>();
   }
   { // Checking SmartGraph
     checkGraph<SmartGraph>();
-    checkGraphNodeMap<SmartGraph>();
-    checkGraphEdgeMap<SmartGraph>();
-
-    check_graph_validity<SmartGraph>();
+    checkGraphValidity<SmartGraph>();
   }
 //   { // Checking FullGraph
@@ -198 +256 @@
 
 int main() {
-  check_concepts();
-  check_graphs();
+  checkConcepts();
+  checkGraphs();
   return 0;
 }

test/graph_test.h

@@ -20 +20 @@
 #define LEMON_TEST_GRAPH_TEST_H
 
-#include <lemon/graph_utils.h>
+#include <set>
+
+#include <lemon/core.h>
+#include <lemon/maps.h>
+
 #include "test_tools.h"
 
@@ -43 +47 @@
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong Arc list linking.");
+      check(G.oppositeNode(G.source(e), e) == G.target(e),
+            "Wrong opposite node");
+      check(G.oppositeNode(G.target(e), e) == G.source(e),
+            "Wrong opposite node");
       ++e;
     }
@@ -56 +64 @@
       check(e!=INVALID,"Wrong OutArc list linking.");
       check(n==G.source(e),"Wrong OutArc list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
       ++e;
     }
@@ -69 +79 @@
       check(e!=INVALID,"Wrong InArc list linking.");
       check(n==G.target(e),"Wrong InArc list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
       ++e;
     }
@@ -81 +93 @@
     for(int i=0;i<cnt;i++) {
       check(e!=INVALID,"Wrong Edge list linking.");
+      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
+      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
       ++e;
     }
@@ -94 +108 @@
       check(e!=INVALID,"Wrong IncEdge list linking.");
       check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
+      check(n==G.baseNode(e),"Wrong OutArc list linking.");
+      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
+            "Wrong OutArc list linking.");
       ++e;
     }
@@ -100 +117 @@
   }
 
-  template <class Digraph>
-  void checkDigraphIterators() {
-    typedef typename Digraph::Node Node;
-    typedef typename Digraph::NodeIt NodeIt;
-    typedef typename Digraph::Arc Arc;
-    typedef typename Digraph::ArcIt ArcIt;
-    typedef typename Digraph::InArcIt InArcIt;
-    typedef typename Digraph::OutArcIt OutArcIt;
-  }
-
   template <class Graph>
-  void checkGraphIterators() {
-    checkDigraphIterators<Graph>();
+  void checkGraphConArcList(const Graph &G, int cnt) {
+    int i = 0;
+    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
+          check(G.source(a) == u, "Wrong iterator.");
+          check(G.target(a) == v, "Wrong iterator.");
+          ++i;
+        }
+      }
+    }
+    check(cnt == i, "Wrong iterator.");
+  }
+
+  template <class Graph>
+  void checkGraphConEdgeList(const Graph &G, int cnt) {
+    int i = 0;
+    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
+      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
+        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
+          check((G.u(e) == u && G.v(e) == v) ||
+                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
+          i += u == v ? 2 : 1;
+        }
+      }
+    }
+    check(2 * cnt == i, "Wrong iterator.");
+  }
+
+  template <typename Graph>
+  void checkArcDirections(const Graph& G) {
+    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
+      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
+      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
+    }
+  }
+
+  template <typename Graph>
+  void checkNodeIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
+      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
+      check(values.find(G.id(n)) == values.end(), "Wrong id");
+      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
+      values.insert(G.id(n));
+    }
+  }
+
+  template <typename Graph>
+  void checkArcIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
+      check(G.arcFromId(G.id(a)) == a, "Wrong id");
+      check(values.find(G.id(a)) == values.end(), "Wrong id");
+      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
+      values.insert(G.id(a));
+    }
+  }
+
+  template <typename Graph>
+  void checkEdgeIds(const Graph& G) {
+    std::set<int> values;
+    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
+      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
+      check(values.find(G.id(e)) == values.end(), "Wrong id");
+      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
+      values.insert(G.id(e));
+    }
+  }
+
+  template <typename Graph>
+  void checkGraphNodeMap(const Graph& G) {
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    IntNodeMap map(G, 42);
+    for (NodeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (NodeIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (NodeIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Node>(12);
+    for (NodeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
+  template <typename Graph>
+  void checkGraphArcMap(const Graph& G) {
+    typedef typename Graph::Arc Arc;
+    typedef typename Graph::ArcIt ArcIt;
+
+    typedef typename Graph::template ArcMap<int> IntArcMap;
+    IntArcMap map(G, 42);
+    for (ArcIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (ArcIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (ArcIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Arc>(12);
+    for (ArcIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
+  template <typename Graph>
+  void checkGraphEdgeMap(const Graph& G) {
     typedef typename Graph::Edge Edge;
     typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::IncEdgeIt IncEdgeIt;
-  }
-
-  // Structure returned by addPetersen()
-  template<class Digraph>
-  struct PetStruct
-  {
-    // Vector containing the outer nodes
-    std::vector<typename Digraph::Node> outer;
-    // Vector containing the inner nodes
-    std::vector<typename Digraph::Node> inner;
-    // Vector containing the arcs of the inner circle
-    std::vector<typename Digraph::Arc> incir;
-    // Vector containing the arcs of the outer circle
-    std::vector<typename Digraph::Arc> outcir;
-    // Vector containing the chord arcs
-    std::vector<typename Digraph::Arc> chords;
-  };
-
-  // Adds the reverse pair of all arcs to a digraph
-  template<class Digraph>
-  void bidirDigraph(Digraph &G)
-  {
-    typedef typename Digraph::Arc Arc;
-    typedef typename Digraph::ArcIt ArcIt;
-
-    std::vector<Arc> ee;
-
-    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
-
-    for(int i=0;i<int(ee.size());++i)
-      G.addArc(G.target(ee[i]),G.source(ee[i]));
-  }
-
-  // Adds a Petersen digraph to G.
-  // Returns the nodes and arcs of the generated digraph.
-  template<typename Digraph>
-  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
-  {
-    PetStruct<Digraph> n;
-
-    for(int i=0;i<num;i++) {
-      n.outer.push_back(G.addNode());
-      n.inner.push_back(G.addNode());
-    }
-
-    for(int i=0;i<num;i++) {
-      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
-      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
-      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
-    }
-
-    return n;
-  }
-
-  // Checks the bidirectioned Petersen digraph
-  template<class Digraph>
-  void checkBidirPetersen(const Digraph &G, int num = 5)
-  {
-    typedef typename Digraph::NodeIt NodeIt;
-
-    checkGraphNodeList(G, 2 * num);
-    checkGraphArcList(G, 6 * num);
-
-    for(NodeIt n(G);n!=INVALID;++n) {
-      checkGraphInArcList(G, n, 3);
-      checkGraphOutArcList(G, n, 3);
-    }
-  }
-
-  // Structure returned by addUPetersen()
-  template<class Graph>
-  struct UPetStruct
-  {
-    // Vector containing the outer nodes
-    std::vector<typename Graph::Node> outer;
-    // Vector containing the inner nodes
-    std::vector<typename Graph::Node> inner;
-    // Vector containing the edges of the inner circle
-    std::vector<typename Graph::Edge> incir;
-    // Vector containing the edges of the outer circle
-    std::vector<typename Graph::Edge> outcir;
-    // Vector containing the chord edges
-    std::vector<typename Graph::Edge> chords;
-  };
-
-  // Adds a Petersen graph to \c G.
-  // Returns the nodes and edges of the generated graph.
-  template<typename Graph>
-  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
-  {
-    UPetStruct<Graph> n;
-
-    for(int i=0;i<num;i++) {
-      n.outer.push_back(G.addNode());
-      n.inner.push_back(G.addNode());
-    }
-
-    for(int i=0;i<num;i++) {
-      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
-      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
-      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
-    }
-
-    return n;
-  }
-
-  // Checks the undirected Petersen graph
-  template<class Graph>
-  void checkUndirPetersen(const Graph &G, int num = 5)
-  {
-    typedef typename Graph::NodeIt NodeIt;
-
-    checkGraphNodeList(G, 2 * num);
-    checkGraphEdgeList(G, 3 * num);
-    checkGraphArcList(G, 6 * num);
-
-    for(NodeIt n(G);n!=INVALID;++n) {
-      checkGraphIncEdgeList(G, n, 3);
-    }
-  }
-
-  template <class Digraph>
-  void checkDigraph() {
-    const int num = 5;
-    Digraph G;
-    checkGraphNodeList(G, 0);
-    checkGraphArcList(G, 0);
-    addPetersen(G, num);
-    bidirDigraph(G);
-    checkBidirPetersen(G, num);
-  }
-
-  template <class Graph>
-  void checkGraph() {
-    const int num = 5;
-    Graph G;
-    checkGraphNodeList(G, 0);
-    checkGraphEdgeList(G, 0);
-    addUPetersen(G, num);
-    checkUndirPetersen(G, num);
-  }
+
+    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
+    IntEdgeMap map(G, 42);
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 42, "Wrong map constructor.");
+    }
+    int s = 0;
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      map[it] = 0;
+      check(map[it] == 0, "Wrong operator[].");
+      map.set(it, s);
+      check(map[it] == s, "Wrong set.");
+      ++s;
+    }
+    s = s * (s - 1) / 2;
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      s -= map[it];
+    }
+    check(s == 0, "Wrong sum.");
+
+    map = constMap<Edge>(12);
+    for (EdgeIt it(G); it != INVALID; ++it) {
+      check(map[it] == 12, "Wrong operator[].");
+    }
+  }
+
 
 } //namespace lemon

test/graph_utils_test.cc

@@ -21 +21 @@
 
 #include <lemon/random.h>
-#include <lemon/graph_utils.h>
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
+#include <lemon/maps.h>
 
 #include "graph_test.h"