Changes in / [65:bfbc57a51fbb:67:9de02aa380de] in lemon-main

Files:

• configure.ac (modified) (6 diffs)
• doc/Makefile.am (modified) (2 diffs)
• doc/coding_style.dox (added)
• doc/dirs.dox (added)
• doc/groups.dox (added)
• doc/license.dox (added)
• doc/mainpage.dox (added)
• doc/namespaces.dox (added)
• doc/template.h (added)
• lemon/Makefile.am (modified) (1 diff)
• lemon/base.cc (modified) (2 diffs)
• lemon/bits/alteration_notifier.h (added)
• lemon/bits/array_map.h (added)
• lemon/bits/base_extender.h (added)
• lemon/bits/default_map.h (added)
• lemon/bits/graph_extender.h (added)
• lemon/bits/invalid.h (modified) (2 diffs)
• lemon/bits/map_extender.h (added)
• lemon/bits/traits.h (added)
• lemon/bits/utility.h (modified) (1 diff)
• lemon/bits/vector_map.h (added)
• lemon/concept_check.h (modified) (5 diffs)
• lemon/concepts/digraph.h (added)
• lemon/concepts/graph.h (added)
• lemon/concepts/graph_components.h (added)
• lemon/concepts/maps.h (modified) (8 diffs)
• lemon/dim2.h (modified) (16 diffs)
• lemon/error.h (added)
• lemon/list_graph.h (modified) (1 diff)
• lemon/maps.h (modified) (43 diffs)
• lemon/random.cc (modified) (1 diff)
• lemon/random.h (modified) (9 diffs)
• lemon/tolerance.h (modified) (16 diffs)
• scripts/update-copyright-header.sh (added)
• test/Makefile.am (modified) (2 diffs)
• test/digraph_test.cc (added)
• test/digraph_test.h (added)
• test/dim_test.cc (modified) (1 diff)
• test/error_test.cc (added)
• test/graph_test.cc (added)
• test/map_test.h (added)
• test/maps_test.cc (modified) (1 diff)
• test/random_test.cc (modified) (1 diff)
• test/test_tools.h (modified) (1 diff)
• test/test_tools_fail.cc (modified) (1 diff)
• test/test_tools_pass.cc (modified) (1 diff)

configure.ac

@@ -3 +3 @@
 dnl Version information.
 m4_define([lemon_version_major], [0])
-m4_define([lemon_version_minor], [6])
-m4_define([lemon_version_micro], [90])
+m4_define([lemon_version_minor], [99])
+m4_define([lemon_version_micro], [])
 m4_define([lemon_version_nano], [])
 m4_define([lemon_version_tag], [hg])
@@ -14 +14 @@
 AC_CONFIG_AUX_DIR([build-aux])
 AC_CONFIG_MACRO_DIR([m4])
-AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects])
+AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
 AC_CONFIG_SRCDIR([lemon/list_graph.h])
 AC_CONFIG_HEADERS([config.h lemon/config.h])
@@ -27 +27 @@
 AC_PROG_LIBTOOL
 
+AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
+
 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"
 fi
-
-AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
 
 dnl Checks for libraries.
@@ -37 +37 @@
 LX_CHECK_CPLEX
 LX_CHECK_SOPLEX
-
-dnl Enable/disable installing the documentation
-AC_ARG_ENABLE([doc],
-AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@])
-AS_HELP_STRING([--disable-doc], [do not build the documentation]),
-              [], [enable_doc=yes])
-
-AC_MSG_CHECKING([whether to build the documention])
-case "$enable_doc" in
-  yes)
-    DOXYGEN_INTERNAL_DOCS=NO
-    AC_MSG_RESULT([yes])
-    ;;
-  full)
-    DOXYGEN_INTERNAL_DOCS=YES
-    AC_MSG_RESULT([full])
-    ;;
-  no)
-    DOXYGEN_INTERNAL_DOCS=NO
-    AC_MSG_RESULT([no])
-    ;;
-  *)
-    AC_MSG_ERROR([bad value $enable_doc for option --enable-doc])
-    ;;
-esac
-AC_SUBST(DOXYGEN_INTERNAL_DOCS)
-AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"])
 
 dnl Disable/enable building the demo programs
@@ -138 +111 @@
 echo SOPLEX support................ : $lx_soplex_found
 echo
-echo build benchmarks.............. : $enable_benchmark
-echo build demo programs........... : $enable_demo
-echo build additional tools........ : $enable_tools
+echo Build benchmarks.............. : $enable_benchmark
+echo Build demo programs........... : $enable_demo
+echo Build additional tools........ : $enable_tools
 echo
 echo The packace will be installed in
@@ -146 +119 @@
 echo $prefix.
 echo
-echo The documentation will be installed in
-echo -n '  '
-eval echo ${datadir}/doc/$PACKAGE.
-echo
 echo '*********************************************************************'
 
 echo
-echo configure complete, now type \'make\' and then \'make install\'.
+echo Configure complete, now type \'make\' and then \'make install\'.
 echo

doc/Makefile.am

@@ -1 @@
-htmldir = $(datadir)/doc/$(PACKAGE)/html
-
 EXTRA_DIST += \
         doc/Makefile \
-        doc/Doxyfile.in
+        doc/Doxyfile.in \
+        doc/coding_style.dox \
+        doc/dirs.dox \
+        doc/groups.dox \
+        doc/license.dox \
+        doc/mainpage.dox \
+        doc/namespaces.dox \
+        doc/html
 
-doc:
+doc/html:
+        $(MAKE) $(AM_MAKEFLAGS) html
+
+html-local:
         if test ${doxygen_found} = yes; then \
           cd doc; \
           doxygen Doxyfile; \
           cd ..; \
-        fi
-
-doc-clean:
-        if test ${doxygen_found} = yes; then \
-          rm -rf doc/html; \
-          rm -f doc/doxygen.log; \
-          cd doc; \
-          doxygen Doxyfile; \
-          cd ..; \
+        else \
+          echo; \
+          echo "Doxygen not found."; \
+          echo; \
+          exit 1; \
         fi
 
@@ -25 +29 @@
         -rm -f doc/doxygen.log
 
-doc/html:
-        $(MAKE) $(AM_MAKEFLAGS) doc-clean
+update-external-tags:
+        wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
+        mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \
+        rm doc/libstdc++.tag.tmp
 
-if WANT_DOC
-
-install-data-local: doc/html
+install-html-local: doc/html
         @$(NORMAL_INSTALL)
-        $(mkinstalldirs) $(DESTDIR)$(htmldir)
-        @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
+        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
+        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
-          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f"; \
-          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f; \
+          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
+          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
         done
 
-uninstall-local: doc/html
+uninstall-local:
         @$(NORMAL_UNINSTALL)
-        @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
+        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
           f="`echo $$p | sed -e 's|^.*/||'`"; \
-          echo " rm -f $(DESTDIR)$(htmldir)/$$f"; \
-          rm -f $(DESTDIR)$(htmldir)/$$f; \
+          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
+          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
         done
 
-endif WANT_DOC
-
-.PHONY: doc doc-clean
+.PHONY: update-external-tags

lemon/Makefile.am

@@ -18 +18 @@
         lemon/concept_check.h \
         lemon/dim2.h \
+        lemon/error.h \
+        lemon/list_graph.h \
+        lemon/maps.h \
         lemon/random.h \
-        lemon/list_graph.h \
-        lemon/maps.h \
         lemon/tolerance.h
 
 bits_HEADERS += \
+        lemon/bits/alteration_notifier.h \
+        lemon/bits/array_map.h \
+        lemon/bits/base_extender.h \
+        lemon/bits/default_map.h \
+        lemon/bits/graph_extender.h \
         lemon/bits/invalid.h \
-        lemon/bits/utility.h
+        lemon/bits/map_extender.h \
+        lemon/bits/traits.h \
+        lemon/bits/utility.h \
+        lemon/bits/vector_map.h
 
 concept_HEADERS += \
-        lemon/concepts/maps.h
+        lemon/concept_check.h \
+        lemon/concepts/digraph.h \
+        lemon/concepts/graph.h \
+        lemon/concepts/maps.h \
+        lemon/concepts/graph_components.h

lemon/base.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -18 +18 @@
 
 ///\file
-///\brief Some basic non inline function and static global data.
+///\brief Some basic non-inline functions and static global data.
 
 #include<lemon/tolerance.h>

lemon/bits/invalid.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -27 +27 @@
   /// \brief Dummy type to make it easier to create invalid iterators.
   ///
+  /// Dummy type to make it easier to create invalid iterators.
   /// See \ref INVALID for the usage.
   struct Invalid {

lemon/bits/utility.h

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

lemon/concept_check.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -34 +34 @@
 // See http://www.boost.org/libs/concept_check for documentation.
 
-#ifndef LEMON_CONCEPT_CHECKS_H
-#define LEMON_CONCEPT_CHECKS_H
+///\file
+///\brief Basic utilities for concept checking.
+///
+///\todo Are we still using BOOST concept checking utility? 
+///Is the BOOST copyright notice necessary?
+
+#ifndef LEMON_CONCEPT_CHECK_H
+#define LEMON_CONCEPT_CHECK_H
 
 namespace lemon {
@@ -47 +53 @@
   template <class T> inline void ignore_unused_variable_warning(const T&) { }
 
+  ///\e
   template <class Concept>
   inline void function_requires()
@@ -56 +63 @@
   }
 
+  ///\e
   template <typename Concept, typename Type>
   inline void checkConcept() {
@@ -65 +73 @@
   }
 
-#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
-  typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
-  template <func##type_var##concept Tp1_> \
-  struct concept_checking_##type_var##concept { }; \
-  typedef concept_checking_##type_var##concept< \
-    BOOST_FPTR ns::concept<type_var>::constraints> \
-    concept_checking_typedef_##type_var##concept
-
-#define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
-  typedef void (ns::concept <type_var1,type_var2>::* \
-     func##type_var1##type_var2##concept)(); \
-  template <func##type_var1##type_var2##concept Tp1_> \
-  struct concept_checking_##type_var1##type_var2##concept { }; \
-  typedef concept_checking_##type_var1##type_var2##concept< \
-    BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \
-    concept_checking_typedef_##type_var1##type_var2##concept
-
-#define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
-  typedef void (ns::concept <tv1,tv2,tv3>::* \
-     func##tv1##tv2##tv3##concept)(); \
-  template <func##tv1##tv2##tv3##concept Tp1_> \
-  struct concept_checking_##tv1##tv2##tv3##concept { }; \
-  typedef concept_checking_##tv1##tv2##tv3##concept< \
-    BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \
-    concept_checking_typedef_##tv1##tv2##tv3##concept
-
-#define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
-  typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \
-     func##tv1##tv2##tv3##tv4##concept)(); \
-  template <func##tv1##tv2##tv3##tv4##concept Tp1_> \
-  struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \
-  typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \
-    BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \
-    concept_checking_typedef_##tv1##tv2##tv3##tv4##concept
-
-
 } // namespace lemon
 
-#endif // LEMON_CONCEPT_CHECKS_H
+#endif // LEMON_CONCEPT_CHECK_H

lemon/concepts/maps.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -42 +42 @@
     {
     public:
-      /// Map's key type.
-      typedef K Key;    
-      /// Map's value type. (The type of objects associated with the keys).
+      /// The key type of the map.
+      typedef K Key;    
+      /// The value type of the map. (The type of objects associated with the keys).
       typedef T Value;
 
       /// Returns the value associated with a key.
 
+      /// Returns the value associated with a key.
       /// \bug Value shouldn't need to be default constructible.
       ///
@@ -82 +83 @@
     {
     public:
-      /// Map's key type.
-      typedef K Key;    
-      /// Map's value type. (The type of objects associated with the keys).
+      /// The key type of the map.
+      typedef K Key;    
+      /// The value type of the map. (The type of objects associated with the keys).
       typedef T Value;
 
@@ -114 +115 @@
     };
 
-    /// Read/Writable map concept
+    /// Read/writable map concept
     
     /// Read/writable map concept.
@@ -120 +121 @@
     template<typename K, typename T>
     class ReadWriteMap : public ReadMap<K,T>,
-                            public WriteMap<K,T>
-    {
-    public:
-      /// Map's key type.
-      typedef K Key;    
-      /// Map's value type. (The type of objects associated with the keys).
+                         public WriteMap<K,T>
+    {
+    public:
+      /// The key type of the map.
+      typedef K Key;    
+      /// The value type of the map. (The type of objects associated with the keys).
       typedef T Value;
 
@@ -147 +148 @@
     /// Dereferable map concept.
     ///
+    /// \todo Rethink this concept.
     template<typename K, typename T, typename R, typename CR>
     class ReferenceMap : public ReadWriteMap<K,T>
@@ -153 +155 @@
       /// Tag for reference maps.
       typedef True ReferenceMapTag;
-      /// Map's key type.
-      typedef K Key;    
-      /// Map's value type. (The type of objects associated with the keys).
-      typedef T Value;
-      /// Map's reference type.
+      /// The key type of the map.
+      typedef K Key;    
+      /// The value type of the map. (The type of objects associated with the keys).
+      typedef T Value;
+      /// The reference type of the map.
       typedef R Reference;
-      /// Map's const reference type.
+      /// The const reference type of the map.
       typedef CR ConstReference;
 
@@ -166 +168 @@
     public:
 
-      ///Returns a reference to the value associated to a key.
+      ///Returns a reference to the value associated with a key.
       Reference operator[](const Key &) { return tmp; }
-      ///Returns a const reference to the value associated to a key.
+      ///Returns a const reference to the value associated with a key.
       ConstReference operator[](const Key &) const { return tmp; }
       /// Sets the value associated with a key.
       void set(const Key &k,const Value &t) { operator[](k)=t; }
 
-      /// \todo Rethink this concept. 
       template<typename _ReferenceMap>
       struct ReferenceMapConcept {

lemon/dim2.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -28 +28 @@
 ///
 /// The class \ref lemon::dim2::Point "dim2::Point" implements
-///a two dimensional vector with the usual
-/// operations.
+/// a two dimensional vector with the usual operations.
 ///
 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
@@ -50 +49 @@
 
   /// A simple two dimensional vector (plainvector) implementation
-  ///with the usual vector
-  /// operators.
-  ///
+  /// with the usual vector operations.
   template<typename T>
     class Point {
@@ -71 +68 @@
       Point(T a, T b) : x(a), y(b) { }
 
-      ///The dimension of the vector.
+      ///Returns the dimension of the vector (i.e. returns 2).
 
       ///The dimension of the vector.
@@ -97 +94 @@
       }
   
-      ///Increment the left hand side by u
+      ///Increment the left hand side by \c u
       Point<T>& operator +=(const Point<T>& u) {
         x += u.x;
@@ -104 +101 @@
       }
   
-      ///Decrement the left hand side by u
+      ///Decrement the left hand side by \c u
       Point<T>& operator -=(const Point<T>& u) {
         x -= u.x;
@@ -316 +313 @@
       ///if at least one point was added to the box or the coordinates of
       ///the box were set).
+      ///
       ///The coordinates of an empty bounding box are not defined. 
       bool empty() const {
@@ -326 +324 @@
       }
 
-      ///Give back the bottom left corner
-
-      ///Give back the bottom left corner.
+      ///Give back the bottom left corner of the box
+
+      ///Give back the bottom left corner of the box.
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> bottomLeft() const {
@@ -334 +332 @@
       }
 
-      ///Set the bottom left corner
-
-      ///Set the bottom left corner.
+      ///Set the bottom left corner of the box
+
+      ///Set the bottom left corner of the box.
       ///It should only be used for non-empty box.
       void bottomLeft(Point<T> p) {
@@ -342 +340 @@
       }
 
-      ///Give back the top right corner
-
-      ///Give back the top right corner.
+      ///Give back the top right corner of the box
+
+      ///Give back the top right corner of the box.
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> topRight() const {
@@ -350 +348 @@
       }
 
-      ///Set the top right corner
-
-      ///Set the top right corner.
+      ///Set the top right corner of the box
+
+      ///Set the top right corner of the box.
       ///It should only be used for non-empty box.
       void topRight(Point<T> p) {
@@ -358 +356 @@
       }
 
-      ///Give back the bottom right corner
-
-      ///Give back the bottom right corner.
+      ///Give back the bottom right corner of the box
+
+      ///Give back the bottom right corner of the box.
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> bottomRight() const {
@@ -366 +364 @@
       }
 
-      ///Set the bottom right corner
-
-      ///Set the bottom right corner.
+      ///Set the bottom right corner of the box
+
+      ///Set the bottom right corner of the box.
       ///It should only be used for non-empty box.
       void bottomRight(Point<T> p) {
@@ -375 +373 @@
       }
  
-      ///Give back the top left corner
-
-      ///Give back the top left corner.
+      ///Give back the top left corner of the box
+
+      ///Give back the top left corner of the box.
       ///If the bounding box is empty, then the return value is not defined.
       Point<T> topLeft() const {
@@ -383 +381 @@
       }
 
-      ///Set the top left corner
-
-      ///Set the top left corner.
+      ///Set the top left corner of the box
+
+      ///Set the top left corner of the box.
       ///It should only be used for non-empty box.
       void topLeft(Point<T> p) {
@@ -669 +667 @@
 
 
-    ///\brief Map of the \ref Point::normSquare() "normSquare()"
-    ///of a \ref Point "Point"-map
-    ///
-    ///Map of the \ref Point::normSquare() "normSquare()"
-    ///of a \ref Point "Point"-map.
-    ///\ingroup maps
-    ///
+  ///\brief Map of the \ref Point::normSquare() "normSquare()"
+  ///of a \ref Point "Point"-map
+  ///
+  ///Map of the \ref Point::normSquare() "normSquare()"
+  ///of a \ref Point "Point"-map.
+  ///\ingroup maps
   template<class M>
   class NormSquareMap 

lemon/list_graph.h

@@ +1 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_LIST_GRAPH_H
+#define LEMON_LIST_GRAPH_H
+
+///\ingroup graphs
+///\file
+///\brief ListDigraph, ListGraph classes.
+
+#include <lemon/bits/graph_extender.h>
+
+#include <vector>
+#include <list>
+
+namespace lemon {
+
+  class ListDigraphBase {
+
+  protected:
+    struct NodeT {
+      int first_in, first_out;
+      int prev, next;
+    };
+ 
+    struct ArcT {
+      int target, source;
+      int prev_in, prev_out;
+      int next_in, next_out;
+    };
+
+    std::vector<NodeT> nodes;
+
+    int first_node;
+
+    int first_free_node;
+
+    std::vector<ArcT> arcs;
+
+    int first_free_arc;
+    
+  public:
+    
+    typedef ListDigraphBase Digraph;
+    
+    class Node {
+      friend class ListDigraphBase;
+    protected:
+
+      int id;
+      explicit Node(int pid) { id = pid;}
+
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node& node) const {return id == node.id;}
+      bool operator!=(const Node& node) const {return id != node.id;}
+      bool operator<(const Node& node) const {return id < node.id;}
+    };
+
+    class Arc {
+      friend class ListDigraphBase;
+    protected:
+
+      int id;
+      explicit Arc(int pid) { id = pid;}
+
+    public:
+      Arc() {}
+      Arc (Invalid) { id = -1; }
+      bool operator==(const Arc& arc) const {return id == arc.id;}
+      bool operator!=(const Arc& arc) const {return id != arc.id;}
+      bool operator<(const Arc& arc) const {return id < arc.id;}
+    };
+
+
+
+    ListDigraphBase()
+      : nodes(), first_node(-1),
+        first_free_node(-1), arcs(), first_free_arc(-1) {}
+
+    
+    int maxNodeId() const { return nodes.size()-1; } 
+    int maxArcId() const { return arcs.size()-1; }
+
+    Node source(Arc e) const { return Node(arcs[e.id].source); }
+    Node target(Arc e) const { return Node(arcs[e.id].target); }
+
+
+    void first(Node& node) const { 
+      node.id = first_node;
+    }
+
+    void next(Node& node) const {
+      node.id = nodes[node.id].next;
+    }
+
+
+    void first(Arc& e) const { 
+      int n;
+      for(n = first_node; 
+          n!=-1 && nodes[n].first_in == -1; 
+          n = nodes[n].next);
+      e.id = (n == -1) ? -1 : nodes[n].first_in;
+    }
+
+    void next(Arc& arc) const {
+      if (arcs[arc.id].next_in != -1) {
+        arc.id = arcs[arc.id].next_in;
+      } else {
+        int n;
+        for(n = nodes[arcs[arc.id].target].next;
+          n!=-1 && nodes[n].first_in == -1; 
+          n = nodes[n].next);
+        arc.id = (n == -1) ? -1 : nodes[n].first_in;
+      }      
+    }
+
+    void firstOut(Arc &e, const Node& v) const {
+      e.id = nodes[v.id].first_out;
+    }
+    void nextOut(Arc &e) const {
+      e.id=arcs[e.id].next_out;
+    }
+
+    void firstIn(Arc &e, const Node& v) const {
+      e.id = nodes[v.id].first_in;
+    }
+    void nextIn(Arc &e) const {
+      e.id=arcs[e.id].next_in;
+    }
+
+    
+    static int id(Node v) { return v.id; }
+    static int id(Arc e) { return e.id; }
+
+    static Node nodeFromId(int id) { return Node(id);}
+    static Arc arcFromId(int id) { return Arc(id);}
+
+    Node addNode() {     
+      int n;
+      
+      if(first_free_node==-1) {
+        n = nodes.size();
+        nodes.push_back(NodeT());
+      } else {
+        n = first_free_node;
+        first_free_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_node;
+      if(first_node != -1) nodes[first_node].prev = n;
+      first_node = n;
+      nodes[n].prev = -1;
+      
+      nodes[n].first_in = nodes[n].first_out = -1;
+      
+      return Node(n);
+    }
+    
+    Arc addArc(Node u, Node v) {
+      int n;      
+
+      if (first_free_arc == -1) {
+        n = arcs.size();
+        arcs.push_back(ArcT());
+      } else {
+        n = first_free_arc;
+        first_free_arc = arcs[n].next_in;
+      }
+      
+      arcs[n].source = u.id; 
+      arcs[n].target = v.id;
+
+      arcs[n].next_out = nodes[u.id].first_out;
+      if(nodes[u.id].first_out != -1) {
+        arcs[nodes[u.id].first_out].prev_out = n;
+      }
+      
+      arcs[n].next_in = nodes[v.id].first_in;
+      if(nodes[v.id].first_in != -1) {
+        arcs[nodes[v.id].first_in].prev_in = n;
+      }
+      
+      arcs[n].prev_in = arcs[n].prev_out = -1;
+        
+      nodes[u.id].first_out = nodes[v.id].first_in = n;
+
+      return Arc(n);
+    }
+    
+    void erase(const Node& node) {
+      int n = node.id;
+      
+      if(nodes[n].next != -1) {
+        nodes[nodes[n].next].prev = nodes[n].prev;
+      }
+      
+      if(nodes[n].prev != -1) {
+        nodes[nodes[n].prev].next = nodes[n].next;
+      } else {
+        first_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_free_node;
+      first_free_node = n;
+
+    }
+    
+    void erase(const Arc& arc) {
+      int n = arc.id;
+      
+      if(arcs[n].next_in!=-1) {
+        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+      }
+
+      if(arcs[n].prev_in!=-1) {
+        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
+      } else {
+        nodes[arcs[n].target].first_in = arcs[n].next_in;
+      }
+
+      
+      if(arcs[n].next_out!=-1) {
+        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+      } 
+
+      if(arcs[n].prev_out!=-1) {
+        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
+      } else {
+        nodes[arcs[n].source].first_out = arcs[n].next_out;
+      }
+      
+      arcs[n].next_in = first_free_arc;
+      first_free_arc = n;      
+
+    }
+
+    void clear() {
+      arcs.clear();
+      nodes.clear();
+      first_node = first_free_node = first_free_arc = -1;
+    }
+
+  protected:
+    void changeTarget(Arc e, Node n) 
+    {
+      if(arcs[e.id].next_in != -1)
+        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
+      if(arcs[e.id].prev_in != -1)
+        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
+      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
+      if (nodes[n.id].first_in != -1) {
+        arcs[nodes[n.id].first_in].prev_in = e.id;
+      }
+      arcs[e.id].target = n.id;
+      arcs[e.id].prev_in = -1;
+      arcs[e.id].next_in = nodes[n.id].first_in;
+      nodes[n.id].first_in = e.id;
+    }
+    void changeSource(Arc e, Node n) 
+    {
+      if(arcs[e.id].next_out != -1)
+        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
+      if(arcs[e.id].prev_out != -1)
+        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
+      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
+      if (nodes[n.id].first_out != -1) {
+        arcs[nodes[n.id].first_out].prev_out = e.id;
+      }
+      arcs[e.id].source = n.id;
+      arcs[e.id].prev_out = -1;
+      arcs[e.id].next_out = nodes[n.id].first_out;
+      nodes[n.id].first_out = e.id;
+    }
+
+  };
+
+  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
+
+  /// \addtogroup digraphs
+  /// @{
+
+  ///A list digraph class.
+
+  ///This is a simple and fast digraph implementation.
+  ///
+  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
+  ///also provides several additional useful extra functionalities.
+  ///The most of the member functions and nested classes are
+  ///documented only in the concept class.
+  ///
+  ///An important extra feature of this digraph implementation is that
+  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
+  ///
+  ///\sa concepts::Digraph.
+
+  class ListDigraph : public ExtendedListDigraphBase {
+  private:
+    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
+    
+    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
+    ///
+    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
+    ///\brief Assignment of ListDigraph to another one is \e not allowed.
+    ///Use DigraphCopy() instead.
+
+    ///Assignment of ListDigraph to another one is \e not allowed.
+    ///Use DigraphCopy() instead.
+    void operator=(const ListDigraph &) {}
+  public:
+
+    typedef ExtendedListDigraphBase Parent;
+
+    /// Constructor
+    
+    /// Constructor.
+    ///
+    ListDigraph() {}
+
+    ///Add a new node to the digraph.
+    
+    /// \return the new node.
+    ///
+    Node addNode() { return Parent::addNode(); }
+
+    ///Add a new arc to the digraph.
+    
+    ///Add a new arc to the digraph with source node \c s
+    ///and target node \c t.
+    ///\return the new arc.
+    Arc addArc(const Node& s, const Node& t) { 
+      return Parent::addArc(s, t); 
+    }
+
+    /// Changes the target of \c e to \c n
+
+    /// Changes the target of \c e to \c n
+    ///
+    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
+    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
+    ///invalidated.
+    ///\warning This functionality cannot be used together with the Snapshot
+    ///feature.
+    void changeTarget(Arc e, Node n) { 
+      Parent::changeTarget(e,n); 
+    }
+    /// Changes the source of \c e to \c n
+
+    /// 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.
+    ///\warning This functionality cannot be used together with the Snapshot
+    ///feature.
+    void changeSource(Arc e, Node n) { 
+      Parent::changeSource(e,n);
+    }
+
+    /// Invert the direction of an arc.
+
+    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
+    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
+    ///invalidated.
+    ///\warning This functionality cannot be used together with the Snapshot
+    ///feature.
+    void reverseArc(Arc e) {
+      Node t=target(e);
+      changeTarget(e,source(e));
+      changeSource(e,t);
+    }
+
+    /// Using this it is possible to avoid the superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be very large (e.g. it will contain millions of nodes and/or arcs)
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveArc
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// \brief Using this it is possible to avoid the superfluous memory
+    /// allocation.
+
+    /// Using this it is possible to avoid the superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be very large (e.g. it will contain millions of nodes and/or arcs)
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveNode
+    void reserveArc(int m) { arcs.reserve(m); };
+
+    ///Contract two nodes.
+
+    ///This function contracts two nodes.
+    ///
+    ///Node \p b will be removed but instead of deleting
+    ///incident arcs, they will be joined to \p a.
+    ///The last parameter \p r controls whether to remove loops. \c true
+    ///means that loops will be removed.
+    ///
+    ///\note The <tt>ArcIt</tt>s
+    ///referencing a moved arc remain
+    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
+    ///may be invalidated.
+    ///\warning This functionality cannot be used together with the Snapshot
+    ///feature.
+    void contract(Node a, Node b, bool r = true) 
+    {
+      for(OutArcIt e(*this,b);e!=INVALID;) {
+        OutArcIt f=e;
+        ++f;
+        if(r && target(e)==a) erase(e);
+        else changeSource(e,a);
+        e=f;
+      }
+      for(InArcIt e(*this,b);e!=INVALID;) {
+        InArcIt f=e;
+        ++f;
+        if(r && source(e)==a) erase(e);
+        else changeTarget(e,a);
+        e=f;
+      }
+      erase(b);
+    }
+
+    ///Split a node.
+
+    ///This function splits a node. First a new node is added to the digraph,
+    ///then the source of each outgoing arc of \c n is moved to this new node.
+    ///If \c connect is \c true (this is the default value), then a new arc
+    ///from \c n to the newly created node is also added.
+    ///\return The newly created node.
+    ///
+    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
+    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
+    ///be invalidated.  
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.  \todo It could be implemented in a bit
+    ///faster way.
+    Node split(Node n, bool connect = true) {
+      Node b = addNode();
+      for(OutArcIt e(*this,n);e!=INVALID;) {
+        OutArcIt f=e;
+        ++f;
+        changeSource(e,b);
+        e=f;
+      }
+      if (connect) addArc(n,b);
+      return b;
+    }
+      
+    ///Split an arc.
+
+    ///This function splits an arc. First a new node \c b is added to
+    ///the digraph, then the original arc is re-targeted to \c
+    ///b. Finally an arc from \c b to the original target is added.
+    ///\return The newly created node.  
+    ///\warning This functionality
+    ///cannot be used together with the Snapshot feature.
+    Node split(Arc e) {
+      Node b = addNode();
+      addArc(b,target(e));
+      changeTarget(e,b);
+      return b;
+    }
+      
+    /// \brief Class to make a snapshot of the digraph and restore
+    /// to it later.
+    ///
+    /// Class to make a snapshot of the digraph and to restore it
+    /// later.
+    ///
+    /// The newly added nodes and arcs can be removed using the
+    /// restore() function.
+    ///
+    /// \warning Arc and node deletions cannot be restored. This
+    /// events invalidate the snapshot. 
+    class Snapshot {
+    protected:
+
+      typedef Parent::NodeNotifier NodeNotifier;
+
+      class NodeObserverProxy : public NodeNotifier::ObserverBase {
+      public:
+
+        NodeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using NodeNotifier::ObserverBase::attach;
+        using NodeNotifier::ObserverBase::detach;
+        using NodeNotifier::ObserverBase::attached;
+        
+      protected:
+        
+        virtual void add(const Node& node) {
+          snapshot.addNode(node);
+        }
+        virtual void add(const std::vector<Node>& nodes) {
+          for (int i = nodes.size() - 1; i >= 0; ++i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void erase(const Node& node) {
+          snapshot.eraseNode(node);
+        }
+        virtual void erase(const std::vector<Node>& nodes) {
+          for (int i = 0; i < int(nodes.size()); ++i) {
+            snapshot.eraseNode(nodes[i]);
+          }
+        }
+        virtual void build() {
+          Node node;
+          std::vector<Node> nodes;
+          for (notifier()->first(node); node != INVALID; 
+               notifier()->next(node)) {
+            nodes.push_back(node);
+          }
+          for (int i = nodes.size() - 1; i >= 0; --i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void clear() {
+          Node node;
+          for (notifier()->first(node); node != INVALID; 
+               notifier()->next(node)) {
+            snapshot.eraseNode(node);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+
+      class ArcObserverProxy : public ArcNotifier::ObserverBase {
+      public:
+
+        ArcObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using ArcNotifier::ObserverBase::attach;
+        using ArcNotifier::ObserverBase::detach;
+        using ArcNotifier::ObserverBase::attached;
+        
+      protected:
+
+        virtual void add(const Arc& arc) {
+          snapshot.addArc(arc);
+        }
+        virtual void add(const std::vector<Arc>& arcs) {
+          for (int i = arcs.size() - 1; i >= 0; ++i) {
+            snapshot.addArc(arcs[i]);
+          }
+        }
+        virtual void erase(const Arc& arc) {
+          snapshot.eraseArc(arc);
+        }
+        virtual void erase(const std::vector<Arc>& arcs) {
+          for (int i = 0; i < int(arcs.size()); ++i) {
+            snapshot.eraseArc(arcs[i]);
+          }
+        }
+        virtual void build() {
+          Arc arc;
+          std::vector<Arc> arcs;
+          for (notifier()->first(arc); arc != INVALID; 
+               notifier()->next(arc)) {
+            arcs.push_back(arc);
+          }
+          for (int i = arcs.size() - 1; i >= 0; --i) {
+            snapshot.addArc(arcs[i]);
+          }
+        }
+        virtual void clear() {
+          Arc arc;
+          for (notifier()->first(arc); arc != INVALID; 
+               notifier()->next(arc)) {
+            snapshot.eraseArc(arc);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+      
+      ListDigraph *digraph;
+
+      NodeObserverProxy node_observer_proxy;
+      ArcObserverProxy arc_observer_proxy;
+
+      std::list<Node> added_nodes;
+      std::list<Arc> added_arcs;
+
+
+      void addNode(const Node& node) {
+        added_nodes.push_front(node);        
+      }
+      void eraseNode(const Node& node) {
+        std::list<Node>::iterator it = 
+          std::find(added_nodes.begin(), added_nodes.end(), node);
+        if (it == added_nodes.end()) {
+          clear();
+          arc_observer_proxy.detach();
+          throw NodeNotifier::ImmediateDetach();
+        } else {
+          added_nodes.erase(it);
+        }
+      }
+
+      void addArc(const Arc& arc) {
+        added_arcs.push_front(arc);        
+      }
+      void eraseArc(const Arc& arc) {
+        std::list<Arc>::iterator it = 
+          std::find(added_arcs.begin(), added_arcs.end(), arc);
+        if (it == added_arcs.end()) {
+          clear();
+          node_observer_proxy.detach(); 
+          throw ArcNotifier::ImmediateDetach();
+        } else {
+          added_arcs.erase(it);
+        }        
+      }
+
+      void attach(ListDigraph &_digraph) {
+        digraph = &_digraph;
+        node_observer_proxy.attach(digraph->notifier(Node()));
+        arc_observer_proxy.attach(digraph->notifier(Arc()));
+      }
+            
+      void detach() {
+        node_observer_proxy.detach();
+        arc_observer_proxy.detach();
+      }
+
+      bool attached() const {
+        return node_observer_proxy.attached();
+      }
+
+      void clear() {
+        added_nodes.clear();
+        added_arcs.clear();        
+      }
+
+    public:
+
+      /// \brief Default constructor.
+      ///
+      /// Default constructor.
+      /// To actually make a snapshot you must call save().
+      Snapshot() 
+        : digraph(0), node_observer_proxy(*this), 
+          arc_observer_proxy(*this) {}
+      
+      /// \brief Constructor that immediately makes a snapshot.
+      ///      
+      /// This constructor immediately makes a snapshot of the digraph.
+      /// \param _digraph The digraph we make a snapshot of.
+      Snapshot(ListDigraph &_digraph) 
+        : node_observer_proxy(*this), 
+          arc_observer_proxy(*this) {
+        attach(_digraph);
+      }
+      
+      /// \brief Make a snapshot.
+      ///
+      /// Make a snapshot of the digraph.
+      ///
+      /// This function can be called more than once. In case of a repeated
+      /// call, the previous snapshot gets lost.
+      /// \param _digraph The digraph we make the snapshot of.
+      void save(ListDigraph &_digraph) {
+        if (attached()) {
+          detach();
+          clear();
+        }
+        attach(_digraph);
+      }
+      
+      /// \brief Undo the changes until the last snapshot.
+      // 
+      /// Undo the changes until the last snapshot created by save().
+      void restore() {
+        detach();
+        for(std::list<Arc>::iterator it = added_arcs.begin(); 
+            it != added_arcs.end(); ++it) {
+          digraph->erase(*it);
+        }
+        for(std::list<Node>::iterator it = added_nodes.begin(); 
+            it != added_nodes.end(); ++it) {
+          digraph->erase(*it);
+        }
+        clear();
+      }
+
+      /// \brief Gives back true when the snapshot is valid.
+      ///
+      /// Gives back true when the snapshot is valid.
+      bool valid() const {
+        return attached();
+      }
+    };
+    
+  };
+
+  ///@}
+
+  class ListGraphBase {
+
+  protected:
+
+    struct NodeT {
+      int first_out;
+      int prev, next;
+    };
+ 
+    struct ArcT {
+      int target;
+      int prev_out, next_out;
+    };
+
+    std::vector<NodeT> nodes;
+
+    int first_node;
+
+    int first_free_node;
+
+    std::vector<ArcT> arcs;
+
+    int first_free_arc;
+    
+  public:
+    
+    typedef ListGraphBase Digraph;
+
+    class Node;
+    class Arc;
+    class Edge;
+    
+    class Node {
+      friend class ListGraphBase;
+    protected:
+
+      int id;
+      explicit Node(int pid) { id = pid;}
+
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node& node) const {return id == node.id;}
+      bool operator!=(const Node& node) const {return id != node.id;}
+      bool operator<(const Node& node) const {return id < node.id;}
+    };
+
+    class Edge {
+      friend class ListGraphBase;
+    protected:
+
+      int id;
+      explicit Edge(int pid) { id = pid;}
+
+    public:
+      Edge() {}
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge& arc) const {return id == arc.id;}
+      bool operator!=(const Edge& arc) const {return id != arc.id;}
+      bool operator<(const Edge& arc) const {return id < arc.id;}
+    };
+
+    class Arc {
+      friend class ListGraphBase;
+    protected:
+
+      int id;
+      explicit Arc(int pid) { id = pid;}
+
+    public:
+      operator Edge() const { return edgeFromId(id / 2); }
+
+      Arc() {}
+      Arc (Invalid) { id = -1; }
+      bool operator==(const Arc& arc) const {return id == arc.id;}
+      bool operator!=(const Arc& arc) const {return id != arc.id;}
+      bool operator<(const Arc& arc) const {return id < arc.id;}
+    };
+
+
+
+    ListGraphBase()
+      : nodes(), first_node(-1),
+        first_free_node(-1), arcs(), first_free_arc(-1) {}
+
+    
+    int maxNodeId() const { return nodes.size()-1; } 
+    int maxEdgeId() const { return arcs.size() / 2 - 1; }
+    int maxArcId() const { return arcs.size()-1; }
+
+    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
+    Node target(Arc e) const { return Node(arcs[e.id].target); }
+
+    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
+    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
+
+    static bool direction(Arc e) {
+      return (e.id & 1) == 1;
+    }
+
+    static Arc direct(Edge e, bool d) {
+      return Arc(e.id * 2 + (d ? 1 : 0));
+    }
+
+    void first(Node& node) const { 
+      node.id = first_node;
+    }
+
+    void next(Node& node) const {
+      node.id = nodes[node.id].next;
+    }
+
+    void first(Arc& e) const { 
+      int n = first_node;
+      while (n != -1 && nodes[n].first_out == -1) {
+        n = nodes[n].next;
+      }
+      e.id = (n == -1) ? -1 : nodes[n].first_out;
+    }
+
+    void next(Arc& e) const {
+      if (arcs[e.id].next_out != -1) {
+        e.id = arcs[e.id].next_out;
+      } else {
+        int n = nodes[arcs[e.id ^ 1].target].next;
+        while(n != -1 && nodes[n].first_out == -1) {
+          n = nodes[n].next;
+        }
+        e.id = (n == -1) ? -1 : nodes[n].first_out;
+      }      
+    }
+
+    void first(Edge& e) const { 
+      int n = first_node;
+      while (n != -1) {
+        e.id = nodes[n].first_out;
+        while ((e.id & 1) != 1) {
+          e.id = arcs[e.id].next_out;
+        }
+        if (e.id != -1) {
+          e.id /= 2;
+          return;
+        } 
+        n = nodes[n].next;
+      }
+      e.id = -1;
+    }
+
+    void next(Edge& e) const {
+      int n = arcs[e.id * 2].target;
+      e.id = arcs[(e.id * 2) | 1].next_out;
+      while ((e.id & 1) != 1) {
+        e.id = arcs[e.id].next_out;
+      }
+      if (e.id != -1) {
+        e.id /= 2;
+        return;
+      } 
+      n = nodes[n].next;
+      while (n != -1) {
+        e.id = nodes[n].first_out;
+        while ((e.id & 1) != 1) {
+          e.id = arcs[e.id].next_out;
+        }
+        if (e.id != -1) {
+          e.id /= 2;
+          return;
+        } 
+        n = nodes[n].next;
+      }
+      e.id = -1;
+    }
+
+    void firstOut(Arc &e, const Node& v) const {
+      e.id = nodes[v.id].first_out;
+    }
+    void nextOut(Arc &e) const {
+      e.id = arcs[e.id].next_out;
+    }
+
+    void firstIn(Arc &e, const Node& v) const {
+      e.id = ((nodes[v.id].first_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+    void nextIn(Arc &e) const {
+      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
+      if (e.id == -2) e.id = -1;
+    }
+
+    void firstInc(Edge &e, bool& d, const Node& v) const {
+      int de = nodes[v.id].first_out;
+      if (de != -1 ) {
+        e.id = de / 2;
+        d = ((de & 1) == 1);
+      } else {
+        e.id = -1;
+        d = true;
+      }
+    }
+    void nextInc(Edge &e, bool& d) const {
+      int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
+      if (de != -1 ) {
+        e.id = de / 2;
+        d = ((de & 1) == 1);
+      } else {
+        e.id = -1;
+        d = true;
+      }
+    }
+    
+    static int id(Node v) { return v.id; }
+    static int id(Arc e) { return e.id; }
+    static int id(Edge e) { return e.id; }
+
+    static Node nodeFromId(int id) { return Node(id);}
+    static Arc arcFromId(int id) { return Arc(id);}
+    static Edge edgeFromId(int id) { return Edge(id);}
+
+    Node addNode() {     
+      int n;
+      
+      if(first_free_node==-1) {
+        n = nodes.size();
+        nodes.push_back(NodeT());
+      } else {
+        n = first_free_node;
+        first_free_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_node;
+      if (first_node != -1) nodes[first_node].prev = n;
+      first_node = n;
+      nodes[n].prev = -1;
+      
+      nodes[n].first_out = -1;
+      
+      return Node(n);
+    }
+    
+    Edge addEdge(Node u, Node v) {
+      int n;      
+
+      if (first_free_arc == -1) {
+        n = arcs.size();
+        arcs.push_back(ArcT());
+        arcs.push_back(ArcT());
+      } else {
+        n = first_free_arc;
+        first_free_arc = arcs[n].next_out;
+      }
+      
+      arcs[n].target = u.id;
+      arcs[n | 1].target = v.id;
+
+      arcs[n].next_out = nodes[v.id].first_out;
+      if (nodes[v.id].first_out != -1) {
+        arcs[nodes[v.id].first_out].prev_out = n;
+      }      
+      arcs[n].prev_out = -1;
+      nodes[v.id].first_out = n;
+      
+      arcs[n | 1].next_out = nodes[u.id].first_out;
+      if (nodes[u.id].first_out != -1) {
+        arcs[nodes[u.id].first_out].prev_out = (n | 1);
+      }
+      arcs[n | 1].prev_out = -1;      
+      nodes[u.id].first_out = (n | 1);
+
+      return Edge(n / 2);
+    }
+    
+    void erase(const Node& node) {
+      int n = node.id;
+      
+      if(nodes[n].next != -1) {
+        nodes[nodes[n].next].prev = nodes[n].prev;
+      }
+      
+      if(nodes[n].prev != -1) {
+        nodes[nodes[n].prev].next = nodes[n].next;
+      } else {
+        first_node = nodes[n].next;
+      }
+      
+      nodes[n].next = first_free_node;
+      first_free_node = n;
+
+    }
+    
+    void erase(const Edge& arc) {
+      int n = arc.id * 2;
+      
+      if (arcs[n].next_out != -1) {
+        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+      } 
+
+      if (arcs[n].prev_out != -1) {
+        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
+      } else {
+        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
+      }
+
+      if (arcs[n | 1].next_out != -1) {
+        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+      } 
+
+      if (arcs[n | 1].prev_out != -1) {
+        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
+      } else {
+        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
+      }
+      
+      arcs[n].next_out = first_free_arc;
+      first_free_arc = n;      
+
+    }
+
+    void clear() {
+      arcs.clear();
+      nodes.clear();
+      first_node = first_free_node = first_free_arc = -1;
+    }
+
+  protected:
+
+    void changeTarget(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;
+      }
+      if(arcs[2 * e.id].prev_out != -1) {
+        arcs[arcs[2 * e.id].prev_out].next_out = 
+          arcs[2 * e.id].next_out;
+      } else {
+        nodes[arcs[(2 * e.id) | 1].target].first_out = 
+          arcs[2 * e.id].next_out;
+      }
+
+      if (nodes[n.id].first_out != -1) {
+        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
+      }
+      arcs[(2 * e.id) | 1].target = n.id;
+      arcs[2 * e.id].prev_out = -1;
+      arcs[2 * e.id].next_out = nodes[n.id].first_out;
+      nodes[n.id].first_out = 2 * e.id;
+    }
+
+    void changeSource(Edge e, Node n) {
+      if(arcs[(2 * e.id) | 1].next_out != -1) {
+        arcs[arcs[(2 * e.id) | 1].next_out].prev_out = 
+          arcs[(2 * e.id) | 1].prev_out;
+      }
+      if(arcs[(2 * e.id) | 1].prev_out != -1) {
+        arcs[arcs[(2 * e.id) | 1].prev_out].next_out = 
+          arcs[(2 * e.id) | 1].next_out;
+      } else {
+        nodes[arcs[2 * e.id].target].first_out = 
+          arcs[(2 * e.id) | 1].next_out;
+      }
+
+      if (nodes[n.id].first_out != -1) {
+        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
+      }
+      arcs[2 * e.id].target = n.id;
+      arcs[(2 * e.id) | 1].prev_out = -1;
+      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
+      nodes[n.id].first_out = ((2 * e.id) | 1);
+    }
+
+  };
+
+//   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 
+//   ExtendedListGraphBase;
+
+  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
+
+
+
+  /// \addtogroup digraphs
+  /// @{
+
+  ///An undirected list digraph class.
+
+  ///This is a simple and fast undirected digraph implementation.
+  ///
+  ///An important extra feature of this digraph implementation is that
+  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
+  ///
+  ///It conforms to the
+  ///\ref concepts::Graph "Graph concept".
+  ///
+  ///\sa concepts::Graph.
+  ///
+  class ListGraph : public ExtendedListGraphBase {
+  private:
+    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
+
+    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
+    ///
+    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
+    ///\brief Assignment of ListGraph to another one is \e not allowed.
+    ///Use GraphCopy() instead.
+
+    ///Assignment of ListGraph to another one is \e not allowed.
+    ///Use GraphCopy() instead.
+    void operator=(const ListGraph &) {}
+  public:
+    /// Constructor
+    
+    /// Constructor.
+    ///
+    ListGraph() {}
+
+    typedef ExtendedListGraphBase Parent;
+
+    typedef Parent::OutArcIt IncArcIt;
+
+    /// \brief Add a new node to the digraph.
+    ///
+    /// \return the new node.
+    ///
+    Node addNode() { return Parent::addNode(); }
+
+    /// \brief Add a new edge to the digraph.
+    ///
+    /// Add a new arc to the digraph with source node \c s
+    /// and target node \c t.
+    /// \return the new edge.
+    Edge addEdge(const Node& s, const Node& t) { 
+      return Parent::addEdge(s, t); 
+    }
+    /// \brief Changes the source of \c e to \c n
+    ///
+    /// 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.
+    void changeSource(Edge e, Node n) { 
+      Parent::changeSource(e,n); 
+    }    
+    /// \brief Changes the target of \c e to \c n
+    ///
+    /// 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 changeTarget(Edge e, Node n) { 
+      Parent::changeTarget(e,n); 
+    }
+    /// \brief Changes the source of \c e to \c n
+    ///
+    /// Changes the source of \c e to \c n. It 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.
+    void changeSource(Arc e, Node n) { 
+      if (Parent::direction(e)) {
+        Parent::changeSource(e,n);
+      } else {
+        Parent::changeTarget(e,n);
+      } 
+    }
+    /// \brief Changes the target of \c e to \c n
+    ///
+    /// Changes the target of \c e to \c n. It 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.
+    void changeTarget(Arc e, Node n) { 
+      if (Parent::direction(e)) {
+        Parent::changeTarget(e,n);
+      } else {
+        Parent::changeSource(e,n);
+      } 
+    }
+    /// \brief Contract two nodes.
+    ///
+    /// This function contracts two nodes.
+    ///
+    /// Node \p b will be removed but instead of deleting
+    /// its neighboring arcs, they will be joined to \p a.
+    /// The last parameter \p r controls whether to remove loops. \c true
+    /// means that loops will be removed.
+    ///
+    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
+    /// valid.
+    void contract(Node a, Node b, bool r = true) {
+      for(IncArcIt e(*this, b); e!=INVALID;) {
+        IncArcIt f = e; ++f;
+        if (r && runningNode(e) == a) {
+          erase(e);
+        } else if (source(e) == b) {
+          changeSource(e, a);
+        } else {
+          changeTarget(e, a);
+        }
+        e = f;
+      }
+      erase(b);
+    }
+
+
+    /// \brief Class to make a snapshot of the digraph and restore
+    /// to it later.
+    ///
+    /// Class to make a snapshot of the digraph and to restore it
+    /// later.
+    ///
+    /// The newly added nodes and edges can be removed
+    /// using the restore() function.
+    ///
+    /// \warning Arc and node deletions cannot be restored. This
+    /// events invalidate the snapshot. 
+    class Snapshot {
+    protected:
+
+      typedef Parent::NodeNotifier NodeNotifier;
+
+      class NodeObserverProxy : public NodeNotifier::ObserverBase {
+      public:
+
+        NodeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using NodeNotifier::ObserverBase::attach;
+        using NodeNotifier::ObserverBase::detach;
+        using NodeNotifier::ObserverBase::attached;
+        
+      protected:
+        
+        virtual void add(const Node& node) {
+          snapshot.addNode(node);
+        }
+        virtual void add(const std::vector<Node>& nodes) {
+          for (int i = nodes.size() - 1; i >= 0; ++i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void erase(const Node& node) {
+          snapshot.eraseNode(node);
+        }
+        virtual void erase(const std::vector<Node>& nodes) {
+          for (int i = 0; i < int(nodes.size()); ++i) {
+            snapshot.eraseNode(nodes[i]);
+          }
+        }
+        virtual void build() {
+          Node node;
+          std::vector<Node> nodes;
+          for (notifier()->first(node); node != INVALID; 
+               notifier()->next(node)) {
+            nodes.push_back(node);
+          }
+          for (int i = nodes.size() - 1; i >= 0; --i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void clear() {
+          Node node;
+          for (notifier()->first(node); node != INVALID; 
+               notifier()->next(node)) {
+            snapshot.eraseNode(node);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+
+      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
+      public:
+
+        EdgeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using EdgeNotifier::ObserverBase::attach;
+        using EdgeNotifier::ObserverBase::detach;
+        using EdgeNotifier::ObserverBase::attached;
+        
+      protected:
+
+        virtual void add(const Edge& arc) {
+          snapshot.addEdge(arc);
+        }
+        virtual void add(const std::vector<Edge>& arcs) {
+          for (int i = arcs.size() - 1; i >= 0; ++i) {
+            snapshot.addEdge(arcs[i]);
+          }
+        }
+        virtual void erase(const Edge& arc) {
+          snapshot.eraseEdge(arc);
+        }
+        virtual void erase(const std::vector<Edge>& arcs) {
+          for (int i = 0; i < int(arcs.size()); ++i) {
+            snapshot.eraseEdge(arcs[i]);
+          }
+        }
+        virtual void build() {
+          Edge arc;
+          std::vector<Edge> arcs;
+          for (notifier()->first(arc); arc != INVALID; 
+               notifier()->next(arc)) {
+            arcs.push_back(arc);
+          }
+          for (int i = arcs.size() - 1; i >= 0; --i) {
+            snapshot.addEdge(arcs[i]);
+          }
+        }
+        virtual void clear() {
+          Edge arc;
+          for (notifier()->first(arc); arc != INVALID; 
+               notifier()->next(arc)) {
+            snapshot.eraseEdge(arc);
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+      
+      ListGraph *digraph;
+
+      NodeObserverProxy node_observer_proxy;
+      EdgeObserverProxy arc_observer_proxy;
+
+      std::list<Node> added_nodes;
+      std::list<Edge> added_arcs;
+
+
+      void addNode(const Node& node) {
+        added_nodes.push_front(node);        
+      }
+      void eraseNode(const Node& node) {
+        std::list<Node>::iterator it = 
+          std::find(added_nodes.begin(), added_nodes.end(), node);
+        if (it == added_nodes.end()) {
+          clear();
+          arc_observer_proxy.detach();
+          throw NodeNotifier::ImmediateDetach();
+        } else {
+          added_nodes.erase(it);
+        }
+      }
+
+      void addEdge(const Edge& arc) {
+        added_arcs.push_front(arc);        
+      }
+      void eraseEdge(const Edge& arc) {
+        std::list<Edge>::iterator it = 
+          std::find(added_arcs.begin(), added_arcs.end(), arc);
+        if (it == added_arcs.end()) {
+          clear();
+          node_observer_proxy.detach();
+          throw EdgeNotifier::ImmediateDetach();
+        } else {
+          added_arcs.erase(it);
+        }        
+      }
+
+      void attach(ListGraph &_digraph) {
+        digraph = &_digraph;
+        node_observer_proxy.attach(digraph->notifier(Node()));
+        arc_observer_proxy.attach(digraph->notifier(Edge()));
+      }
+            
+      void detach() {
+        node_observer_proxy.detach();
+        arc_observer_proxy.detach();
+      }
+
+      bool attached() const {
+        return node_observer_proxy.attached();
+      }
+
+      void clear() {
+        added_nodes.clear();
+        added_arcs.clear();        
+      }
+
+    public:
+
+      /// \brief Default constructor.
+      ///
+      /// Default constructor.
+      /// To actually make a snapshot you must call save().
+      Snapshot() 
+        : digraph(0), node_observer_proxy(*this), 
+          arc_observer_proxy(*this) {}
+      
+      /// \brief Constructor that immediately makes a snapshot.
+      ///      
+      /// This constructor immediately makes a snapshot of the digraph.
+      /// \param _digraph The digraph we make a snapshot of.
+      Snapshot(ListGraph &_digraph) 
+        : node_observer_proxy(*this), 
+          arc_observer_proxy(*this) {
+        attach(_digraph);
+      }
+      
+      /// \brief Make a snapshot.
+      ///
+      /// Make a snapshot of the digraph.
+      ///
+      /// This function can be called more than once. In case of a repeated
+      /// call, the previous snapshot gets lost.
+      /// \param _digraph The digraph we make the snapshot of.
+      void save(ListGraph &_digraph) {
+        if (attached()) {
+          detach();
+          clear();
+        }
+        attach(_digraph);
+      }
+      
+      /// \brief Undo the changes until the last snapshot.
+      // 
+      /// Undo the changes until the last snapshot created by save().
+      void restore() {
+        detach();
+        for(std::list<Edge>::iterator it = added_arcs.begin(); 
+            it != added_arcs.end(); ++it) {
+          digraph->erase(*it);
+        }
+        for(std::list<Node>::iterator it = added_nodes.begin(); 
+            it != added_nodes.end(); ++it) {
+          digraph->erase(*it);
+        }
+        clear();
+      }
+
+      /// \brief Gives back true when the snapshot is valid.
+      ///
+      /// Gives back true when the snapshot is valid.
+      bool valid() const {
+        return attached();
+      }
+    };
+  };
+  
+  /// @}  
+} //namespace lemon
+  
+
+#endif

lemon/maps.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -45 +45 @@
   class MapBase {
   public:
-    ///\e
+    /// The key type of the map.
     typedef K Key;
-    ///\e
+    /// The value type of the map. (The type of objects associated with the keys).
     typedef T Value;
   };
@@ -82 +82 @@
   /// Constant map.
 
-  /// This is a readable map which assigns a specified value to each key.
-  /// In other aspects it is equivalent to the \c NullMap.
+  /// This is a \ref concepts::ReadMap "readable" map which assigns a 
+  /// specified value to each key.
+  /// In other aspects it is equivalent to \c NullMap.
   template<typename K, typename T>
   class ConstMap : public MapBase<K, T> {
@@ -116 +117 @@
 
     template<typename T1>
-    struct rebind {
-      typedef ConstMap<K, T1> other;
-    };
-
-    template<typename T1>
     ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
   };
@@ -139 +135 @@
   /// Constant map with inlined constant value.
 
-  /// This is a readable map which assigns a specified value to each key.
-  /// In other aspects it is equivalent to the \c NullMap.
+  /// This is a \ref concepts::ReadMap "readable" map which assigns a 
+  /// specified value to each key.
+  /// In other aspects it is equivalent to \c NullMap.
   template<typename K, typename V, V v>
   class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
@@ -155 +152 @@
   };
 
-  ///Returns a \c ConstMap class
+  ///Returns a \c ConstMap class with inlined value
 
   ///This function just returns a \c ConstMap class with inlined value.
@@ -164 +161 @@
   }
 
-  ///Map based on std::map
+  ///Map based on \c std::map
 
   ///This is essentially a wrapper for \c std::map with addition that
   ///you can specify a default value different from \c Value().
+  ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   template <typename K, typename T, typename Compare = std::less<K> >
-  class StdMap {
+  class StdMap : public MapBase<K, T> {
     template <typename K1, typename T1, typename C1>
     friend class StdMap;
   public:
 
+    typedef MapBase<K, T> Parent;
+    ///Key type
+    typedef typename Parent::Key Key;
+    ///Value type
+    typedef typename Parent::Value Value;
+    ///Reference Type
+    typedef T& Reference;
+    ///Const reference type
+    typedef const T& ConstReference;
+
     typedef True ReferenceMapTag;
-    ///\e
-    typedef K Key;
-    ///\e
-    typedef T Value;
-    ///\e
-    typedef T& Reference;
-    ///\e
-    typedef const T& ConstReference;
 
   private:
@@ -194 +194 @@
     /// Constructor with specified default value
     StdMap(const T& value = T()) : _value(value) {}
-    /// \brief Constructs the map from an appropriate std::map, and explicitly
-    /// specifies a default value.
+    /// \brief Constructs the map from an appropriate \c std::map, and 
+    /// explicitly specifies a default value.
     template <typename T1, typename Comp1>
     StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 
       : _map(map.begin(), map.end()), _value(value) {}
     
-    /// \brief Constructs a map from an other StdMap.
+    /// \brief Constructs a map from an other \ref StdMap.
     template<typename T1, typename Comp1>
     StdMap(const StdMap<Key, T1, Comp1> &c) 
@@ -244 +244 @@
     }    
 
-    template <typename T1, typename C1 = std::less<T1> >
-    struct rebind {
-      typedef StdMap<Key, T1, C1> other;
-    };
-  };
-
-  /// \brief Map for storing values for the range \c [0..size-1] range keys
-  ///
-  /// The current map has the \c [0..size-1] keyset and the values
+  };
+  
+  ///Returns a \c StdMap class
+
+  ///This function just returns a \c StdMap class with specified 
+  ///default value.
+  ///\relates StdMap
+  template<typename K, typename V, typename Compare> 
+  inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
+    return StdMap<K, V, Compare>(value);
+  }
+  
+  ///Returns a \c StdMap class
+
+  ///This function just returns a \c StdMap class with specified 
+  ///default value.
+  ///\relates StdMap
+  template<typename K, typename V> 
+  inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
+    return StdMap<K, V, std::less<K> >(value);
+  }
+  
+  ///Returns a \c StdMap class created from an appropriate std::map
+
+  ///This function just returns a \c StdMap class created from an 
+  ///appropriate std::map.
+  ///\relates StdMap
+  template<typename K, typename V, typename Compare> 
+  inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map, 
+                                       const V& value = V() ) {
+    return StdMap<K, V, Compare>(map, value);
+  }
+
+  ///Returns a \c StdMap class created from an appropriate std::map
+
+  ///This function just returns a \c StdMap class created from an 
+  ///appropriate std::map.
+  ///\relates StdMap
+  template<typename K, typename V> 
+  inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map, 
+                                             const V& value = V() ) {
+    return StdMap<K, V, std::less<K> >(map, value);
+  }
+
+  /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
+  ///
+  /// This map has the <tt>[0..size-1]</tt> keyset and the values
   /// are stored in a \c std::vector<T>  container. It can be used with
   /// some data structures, for example \c UnionFind, \c BinHeap, when 
-  /// the used items are small integer numbers. 
+  /// the used items are small integer numbers.
+  /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
   ///
   /// \todo Revise its name
   template <typename T>
-  class IntegerMap {
+  class IntegerMap : public MapBase<int, T> {
 
     template <typename T1>
@@ -266 +305 @@
   public:
 
+    typedef MapBase<int, T> Parent;
+    ///\e
+    typedef typename Parent::Key Key;
+    ///\e
+    typedef typename Parent::Value Value;
+    ///\e
+    typedef T& Reference;
+    ///\e
+    typedef const T& ConstReference;
+
     typedef True ReferenceMapTag;
-    ///\e
-    typedef int Key;
-    ///\e
-    typedef T Value;
-    ///\e
-    typedef T& Reference;
-    ///\e
-    typedef const T& ConstReference;
 
   private:
@@ -286 +327 @@
     IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
 
-    /// \brief Constructs the map from an appropriate std::vector.
+    /// \brief Constructs the map from an appropriate \c std::vector.
     template <typename T1>
     IntegerMap(const std::vector<T1>& vector) 
       : _vector(vector.begin(), vector.end()) {}
     
-    /// \brief Constructs a map from an other IntegerMap.
+    /// \brief Constructs a map from an other \ref IntegerMap.
     template <typename T1>
     IntegerMap(const IntegerMap<T1> &c) 
@@ -323 +364 @@
 
   };
+  
+  ///Returns an \c IntegerMap class
+
+  ///This function just returns an \c IntegerMap class.
+  ///\relates IntegerMap
+  template<typename T>
+  inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
+    return IntegerMap<T>(size, value);
+  }
 
   /// @}
@@ -359 +409 @@
   ///the default conversion.
   ///
-  ///This \c concepts::ReadMap "read only map"
+  ///This \ref concepts::ReadMap "read only map"
   ///converts the \c Value of a map to type \c T.
   ///Its \c Key is inherited from \c M.
@@ -376 +426 @@
     ConvertMap(const M &_m) : m(_m) {};
 
-    /// \brief The subscript operator.
-    ///
-    /// The subscript operator.
+    ///\e
     Value operator[](const Key& k) const {return m[k];}
   };
@@ -393 +441 @@
   ///Simple wrapping of a map
 
-  ///This \c concepts::ReadMap "read only map" returns the simple
+  ///This \ref concepts::ReadMap "read only map" returns the simple
   ///wrapping of the given map. Sometimes the reference maps cannot be
   ///combined with simple read maps. This map adaptor wraps the given
@@ -415 +463 @@
     Value operator[](Key k) const {return m[k];}
   };
-
-  ///Simple writable wrapping of the map
-
-  ///This \c concepts::WriteMap "write map" returns the simple
+  
+  ///Returns a \c SimpleMap class
+
+  ///This function just returns a \c SimpleMap class.
+  ///\relates SimpleMap
+  template<typename M>
+  inline SimpleMap<M> simpleMap(const M &m) {
+    return SimpleMap<M>(m);
+  }
+
+  ///Simple writable wrapping of a map
+
+  ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
   ///wrapping of the given map. Sometimes the reference maps cannot be
   ///combined with simple read-write maps. This map adaptor wraps the
@@ -443 +500 @@
   };
 
+  ///Returns a \c SimpleWriteMap class
+
+  ///This function just returns a \c SimpleWriteMap class.
+  ///\relates SimpleWriteMap
+  template<typename M>
+  inline SimpleWriteMap<M> simpleWriteMap(M &m) {
+    return SimpleWriteMap<M>(m);
+  }
+
   ///Sum of two maps
 
-  ///This \c concepts::ReadMap "read only map" returns the sum of the two
+  ///This \ref concepts::ReadMap "read only map" returns the sum of the two
   ///given maps.
   ///Its \c Key and \c Value are inherited from \c M1.
-  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
+  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
   template<typename M1, typename M2> 
   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
@@ -468 +534 @@
 
   ///This function just returns an \c AddMap class.
-  ///\todo How to call these type of functions?
+  ///\todo Extend the documentation: how to call these type of functions?
   ///
   ///\relates AddMap
@@ -478 +544 @@
   ///Shift a map with a constant.
 
-  ///This \c concepts::ReadMap "read only map" returns the sum of the
+  ///This \ref concepts::ReadMap "read only map" returns the sum of the
   ///given map and a constant value.
   ///Its \c Key and \c Value are inherited from \c M.
@@ -514 +580 @@
   ///Shift a map with a constant (ReadWrite version).
 
-  ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
+  ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
   ///given map and a constant value. It makes also possible to write the map.
   ///Its \c Key and \c Value are inherited from \c M.
@@ -560 +626 @@
   ///Difference of two maps
 
-  ///This \c concepts::ReadMap "read only map" returns the difference
+  ///This \ref concepts::ReadMap "read only map" returns the difference
   ///of the values of the two given maps.
   ///Its \c Key and \c Value are inherited from \c M1.
@@ -593 +659 @@
   ///Product of two maps
 
-  ///This \c concepts::ReadMap "read only map" returns the product of the
+  ///This \ref concepts::ReadMap "read only map" returns the product of the
   ///values of the two given maps.
   ///Its \c Key and \c Value are inherited from \c M1.
@@ -623 +689 @@
   ///Scales a map with a constant.
 
-  ///This \c concepts::ReadMap "read only map" returns the value of the
+  ///This \ref concepts::ReadMap "read only map" returns the value of the
   ///given map multiplied from the left side with a constant value.
   ///Its \c Key and \c Value are inherited from \c M.
@@ -659 +725 @@
   ///Scales a map with a constant (ReadWrite version).
 
-  ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
+  ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
   ///given map multiplied from the left side with a constant value. It can
   ///also be used as write map if the \c / operator is defined between
@@ -707 +773 @@
   ///Quotient of two maps
 
-  ///This \c concepts::ReadMap "read only map" returns the quotient of the
+  ///This \ref concepts::ReadMap "read only map" returns the quotient of the
   ///values of the two given maps.
   ///Its \c Key and \c Value are inherited from \c M1.
@@ -737 +803 @@
   ///Composition of two maps
 
-  ///This \c concepts::ReadMap "read only map" returns the composition of
+  ///This \ref concepts::ReadMap "read only map" returns the composition of
   ///two given maps.
   ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
@@ -788 +854 @@
   ///Combine of two maps using an STL (binary) functor.
   ///
-  ///This \c concepts::ReadMap "read only map" takes two maps and a
+  ///This \ref concepts::ReadMap "read only map" takes two maps and a
   ///binary functor and returns the composition of the two
   ///given maps unsing the functor. 
@@ -830 +896 @@
   ///For example if \c m1 and \c m2 are both \c double valued maps, then 
   ///\code
-  ///combineMap<double>(m1,m2,std::plus<double>())
+  ///combineMap(m1,m2,std::plus<double>())
   ///\endcode
   ///is equivalent to
@@ -861 +927 @@
   ///Negative value of a map
 
-  ///This \c concepts::ReadMap "read only map" returns the negative
+  ///This \ref concepts::ReadMap "read only map" returns the negative
   ///value of the value returned by the given map.
   ///Its \c Key and \c Value are inherited from \c M.
@@ -883 +949 @@
   ///Negative value of a map (ReadWrite version)
 
-  ///This \c concepts::ReadWriteMap "read-write map" returns the negative
+  ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
   ///value of the value returned by the given map.
   ///Its \c Key and \c Value are inherited from \c M.
@@ -925 +991 @@
   ///Absolute value of a map
 
-  ///This \c concepts::ReadMap "read only map" returns the absolute value
+  ///This \ref concepts::ReadMap "read only map" returns the absolute value
   ///of the value returned by the given map.
   ///Its \c Key and \c Value are inherited from \c M. 
@@ -959 +1025 @@
   ///Converts an STL style functor to a map
 
-  ///This \c concepts::ReadMap "read only map" returns the value
+  ///This \ref concepts::ReadMap "read only map" returns the value
   ///of a given functor.
   ///
   ///Template parameters \c K and \c V will become its
-  ///\c Key and \c Value. They must be given explicitly
-  ///because a functor does not provide such typedefs.
+  ///\c Key and \c Value. 
+  ///In most cases they have to be given explicitly because a 
+  ///functor typically does not provide \c argument_type and 
+  ///\c result_type typedefs.
   ///
   ///Parameter \c F is the type of the used functor.
@@ -989 +1057 @@
   ///This function just returns a \c FunctorMap class.
   ///
-  ///It is specialized for adaptable function classes and
-  ///C++ functions.
+  ///This function is specialized for adaptable binary function
+  ///classes and C++ functions.
+  ///
   ///\relates FunctorMap
   template<typename K, typename V, typename F> inline 
@@ -1013 +1082 @@
 
   ///This class Converts a map to an STL style (unary) functor.
-  ///that is it provides an <tt>operator()</tt> to read its values.
+  ///That is it provides an <tt>operator()</tt> to read its values.
   ///
   ///For the sake of convenience it also works as
-  ///a ususal \c concepts::ReadMap "readable map",
+  ///a ususal \ref concepts::ReadMap "readable map",
   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
   ///
@@ -1048 +1117 @@
   }
 
-  ///Applies all map setting operations to two maps
-
-  ///This map has two \c concepts::ReadMap "readable map"
+  ///Just readable version of \ref ForkWriteMap
+
+  ///This map has two \ref concepts::ReadMap "readable map"
   ///parameters and each read request will be passed just to the
-  ///first map. This class is the just readable map type of the ForkWriteMap.
+  ///first map. This class is the just readable map type of \c ForkWriteMap.
   ///
   ///The \c Key and \c Value are inherited from \c M1.
-  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
   ///
   ///\sa ForkWriteMap
@@ -1078 +1147 @@
   ///Applies all map setting operations to two maps
 
-  ///This map has two \c concepts::WriteMap "writable map"
+  ///This map has two \ref concepts::WriteMap "writable map"
   ///parameters and each write request will be passed to both of them.
-  ///If \c M1 is also \c concepts::ReadMap "readable",
+  ///If \c M1 is also \ref concepts::ReadMap "readable",
   ///then the read operations will return the
   ///corresponding values of \c M1.
   ///
   ///The \c Key and \c Value are inherited from \c M1.
-  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
+  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
   ///
   ///\sa ForkMap
@@ -1129 +1198 @@
   ///Logical 'not' of a map
   
-  ///This bool \c concepts::ReadMap "read only map" returns the 
+  ///This bool \ref concepts::ReadMap "read only map" returns the 
   ///logical negation of the value returned by the given map.
-  ///Its \c Key is inherited from \c M, its Value is \c bool.
+  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
   ///
   ///\sa NotWriteMap
@@ -1150 +1219 @@
   ///Logical 'not' of a map (ReadWrie version)
   
-  ///This bool \c concepts::ReadWriteMap "read-write map" returns the 
+  ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 
   ///logical negation of the value returned by the given map. When it is set,
   ///the opposite value is set to the original map.
-  ///Its \c Key is inherited from \c M, its Value is \c bool.
+  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
   ///
   ///\sa NotMap
@@ -1218 +1287 @@
   /// \brief Writable bool map for logging each \c true assigned element
   ///
-  /// Writable bool map for logging each \c true assigned element, i.e it
-  /// copies all the keys set to \c true to the given iterator.
+  /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 
+  /// each \c true assigned element, i.e it copies all the keys set 
+  /// to \c true to the given iterator.
   ///
   /// \note The container of the iterator should contain space 
   /// for each element.
   ///
-  /// The following example shows how you can write the edges found by the Prim
-  /// algorithm directly
-  /// to the standard output.
+  /// The following example shows how you can write the edges found by 
+  /// the \ref Prim algorithm directly to the standard output.
   ///\code
   /// typedef IdMap<Graph, Edge> EdgeIdMap;
@@ -1241 +1310 @@
   ///
   ///\sa BackInserterBoolMap 
+  ///\sa FrontInserterBoolMap 
+  ///\sa InserterBoolMap 
   ///
   ///\todo Revise the name of this class and the related ones.
@@ -1306 +1377 @@
   class BackInserterBoolMap {
   public:
-    typedef typename Container::value_type Key;
+    typedef typename Functor::argument_type Key;
     typedef bool Value;
 
@@ -1341 +1412 @@
   class FrontInserterBoolMap {
   public:
-    typedef typename Container::value_type Key;
+    typedef typename Functor::argument_type Key;
     typedef bool Value;
 
@@ -1551 +1622 @@
     }
 
-    /// Setter function of the map
+    /// The \c set function of the map
     void set(const Key& key, Value value) {
       if (value) {

lemon/random.cc

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

lemon/random.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -255 +255 @@
           --curr;
         }
-        curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
+        state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
           curr[length - shift] ^ mask[curr[length - 1] & 1ul];
 
@@ -511 +511 @@
   ///\endcode
   ///
-  /// The lemon provides a global instance of the random number
+  /// LEMON provides a global instance of the random number
   /// generator which name is \ref lemon::rnd "rnd". Usually it is a
   /// good programming convenience to use this global generator to get
@@ -527 +527 @@
   public:
 
-    /// \brief Constructor
+    /// \brief Default constructor
     ///
     /// Constructor with constant seeding.
     Random() { core.initState(); }
 
-    /// \brief Constructor
+    /// \brief Constructor with seed
     ///
     /// Constructor with seed. The current number type will be converted
@@ -541 +541 @@
     }
 
-    /// \brief Constructor
+    /// \brief Constructor with array seeding
     ///
     /// Constructor with array seeding. The given range should contain
@@ -578 +578 @@
     ///
     /// It returns a random real number from the range [0, 1). The
-    /// default Number type is double.
+    /// default Number type is \c double.
     template <typename Number>
     Number real() {
@@ -654 +654 @@
     ///
     /// It returns a random non-negative integer uniformly from the
-    /// whole range of the current \c Number type.  The default result
-    /// type of this function is unsigned int.
+    /// whole range of the current \c Number type. The default result
+    /// type of this function is <tt>unsigned int</tt>.
     template <typename Number>
     Number uinteger() {
@@ -669 +669 @@
     /// It returns a random integer uniformly from the whole range of
     /// the current \c Number type. The default result type of this
-    /// function is int.
+    /// function is \c int.
     template <typename Number>
     Number integer() {
@@ -690 +690 @@
     }
 
-    ///\name Nonuniform distributions
+    ///\name Non-uniform distributions
     ///
     

lemon/tolerance.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library
  *
- * Copyright (C) 2003-2007
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37 +37 @@
   ///as a result of a probably inexact computation.
   ///
-  ///Tolerance is a class to provide a basic way to
+  ///\ref Tolerance is a class to provide a basic way to
   ///handle the comparison of numbers that are obtained
   ///as a result of a probably inexact computation.
   ///
   ///This is an abstract class, it should be specialized for all numerical
-  ///data types. These specialized classes like \ref Tolerance\<double\>
+  ///data types. These specialized classes like \ref Tolerance<double>
   ///may offer additional tuning parameters.
   ///
@@ -49 +49 @@
   ///\sa Tolerance<long double>
   ///\sa Tolerance<int>
-#if defined __GNUC__ && !defined __STRICT_ANSI__  
   ///\sa Tolerance<long long int>
-#endif
   ///\sa Tolerance<unsigned int>
-#if defined __GNUC__ && !defined __STRICT_ANSI__  
   ///\sa Tolerance<unsigned long long int>
-#endif
 
   template<class T>
@@ -64 +60 @@
 
     ///\name Comparisons
-    ///The concept is that these bool functions return with \c true only if
+    ///The concept is that these bool functions return \c true only if
     ///the related comparisons hold even if some numerical error appeared
     ///during the computations.
@@ -92 +88 @@
 
 
-  ///Float specialization of \ref Tolerance.
-
-  ///Float specialization of \ref Tolerance.
+  ///Float specialization of Tolerance.
+
+  ///Float specialization of Tolerance.
   ///\sa Tolerance
   ///\relates Tolerance
@@ -108 +104 @@
     ///Constructor setting the epsilon tolerance to the default value.
     Tolerance() : _epsilon(def_epsilon) {}
-    ///Constructor setting the epsilon tolerance.
+    ///Constructor setting the epsilon tolerance to the given value.
     Tolerance(float e) : _epsilon(e) {}
 
-    ///Return the epsilon value.
+    ///Returns the epsilon value.
     Value epsilon() const {return _epsilon;}
-    ///Set the epsilon value.
+    ///Sets the epsilon value.
     void epsilon(Value e) {_epsilon=e;}
 
-    ///Return the default epsilon value.
+    ///Returns the default epsilon value.
     static Value defaultEpsilon() {return def_epsilon;}
-    ///Set the default epsilon value.
+    ///Sets the default epsilon value.
     static void defaultEpsilon(Value e) {def_epsilon=e;}
 
     ///\name Comparisons
-    ///See class Tolerance for more details.
+    ///See \ref Tolerance for more details.
 
     ///@{
@@ -143 +139 @@
   };
 
-  ///Double specialization of \ref Tolerance.
-
-  ///Double specialization of \ref Tolerance.
+  ///Double specialization of Tolerance.
+
+  ///Double specialization of Tolerance.
   ///\sa Tolerance
   ///\relates Tolerance
@@ -159 +155 @@
     ///Constructor setting the epsilon tolerance to the default value.
     Tolerance() : _epsilon(def_epsilon) {}
-    ///Constructor setting the epsilon tolerance.
+    ///Constructor setting the epsilon tolerance to the given value.
     Tolerance(double e) : _epsilon(e) {}
 
-    ///Return the epsilon value.
+    ///Returns the epsilon value.
     Value epsilon() const {return _epsilon;}
-    ///Set the epsilon value.
+    ///Sets the epsilon value.
     void epsilon(Value e) {_epsilon=e;}
 
-    ///Return the default epsilon value.
+    ///Returns the default epsilon value.
     static Value defaultEpsilon() {return def_epsilon;}
-    ///Set the default epsilon value.
+    ///Sets the default epsilon value.
     static void defaultEpsilon(Value e) {def_epsilon=e;}
 
     ///\name Comparisons
-    ///See class Tolerance for more details.
+    ///See \ref Tolerance for more details.
 
     ///@{
@@ -194 +190 @@
   };
 
-  ///Long double specialization of \ref Tolerance.
-
-  ///Long double specialization of \ref Tolerance.
+  ///Long double specialization of Tolerance.
+
+  ///Long double specialization of Tolerance.
   ///\sa Tolerance
   ///\relates Tolerance
@@ -210 +206 @@
     ///Constructor setting the epsilon tolerance to the default value.
     Tolerance() : _epsilon(def_epsilon) {}
-    ///Constructor setting the epsilon tolerance.
+    ///Constructor setting the epsilon tolerance to the given value.
     Tolerance(long double e) : _epsilon(e) {}
 
-    ///Return the epsilon value.
+    ///Returns the epsilon value.
     Value epsilon() const {return _epsilon;}
-    ///Set the epsilon value.
+    ///Sets the epsilon value.
     void epsilon(Value e) {_epsilon=e;}
 
-    ///Return the default epsilon value.
+    ///Returns the default epsilon value.
     static Value defaultEpsilon() {return def_epsilon;}
-    ///Set the default epsilon value.
+    ///Sets the default epsilon value.
     static void defaultEpsilon(Value e) {def_epsilon=e;}
 
     ///\name Comparisons
-    ///See class Tolerance for more details.
+    ///See \ref Tolerance for more details.
 
     ///@{
@@ -245 +241 @@
   };
 
-  ///Integer specialization of \ref Tolerance.
-
-  ///Integer specialization of \ref Tolerance.
+  ///Integer specialization of Tolerance.
+
+  ///Integer specialization of Tolerance.
   ///\sa Tolerance
   template<>
@@ -278 +274 @@
   };
 
+  ///Unsigned integer specialization of Tolerance.
+
   ///Unsigned integer specialization of \ref Tolerance.
-
-  ///Unsigned integer specialization of \ref Tolerance.
   ///\sa Tolerance
   template<>
@@ -312 +308 @@
   
 
-  ///Long integer specialization of \ref Tolerance.
-
-  ///Long integer specialization of \ref Tolerance.
+  ///Long integer specialization of Tolerance.
+
+  ///Long integer specialization of Tolerance.
   ///\sa Tolerance
   template<>
@@ -345 +341 @@
   };
 
+  ///Unsigned long integer specialization of Tolerance.
+
   ///Unsigned long integer specialization of \ref Tolerance.
-
-  ///Unsigned long integer specialization of \ref Tolerance.
   ///\sa Tolerance
   template<>
@@ -380 +376 @@
 #if defined __GNUC__ && !defined __STRICT_ANSI__
 
-  ///Long long integer specialization of \ref Tolerance.
+  ///Long long integer specialization of Tolerance.
 
   ///Long long integer specialization of \ref Tolerance.
@@ -415 +411 @@
   };
 
-  ///Unsigned long long integer specialization of \ref Tolerance.
+  ///Unsigned long long integer specialization of Tolerance.
 
   ///Unsigned long long integer specialization of \ref Tolerance.

test/Makefile.am

@@ -3 +3 @@
 
 noinst_HEADERS += \
+        test/digraph_test.h \
+        test/map_test.h \
         test/test_tools.h
 
 check_PROGRAMS += \
+        test/digraph_test \
         test/dim_test \
+        test/graph_test \
         test/maps_test \
         test/random_test \
@@ -15 +19 @@
 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 
+test_digraph_test_SOURCES = test/digraph_test.cc
 test_dim_test_SOURCES = test/dim_test.cc
+#test_error_test_SOURCES = test/error_test.cc
+test_graph_test_SOURCES = test/graph_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
 test_random_test_SOURCES = test/random_test.cc

test/dim_test.cc

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

test/maps_test.cc

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

test/random_test.cc

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

test/test_tools.h

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

test/test_tools_fail.cc

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

test/test_tools_pass.cc

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