Index: lemon/bits/alteration_notifier.h
===================================================================
--- lemon/bits/alteration_notifier.h	(revision 314)
+++ lemon/bits/alteration_notifier.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -36,59 +36,60 @@
   // a container.
   //
-  // The simple graph's can be refered as two containers, one node container
-  // and one edge container. But they are not standard containers they
-  // does not store values directly they are just key continars for more
-  // value containers which are the node and edge maps.
-  //
-  // The graph's node and edge sets can be changed as we add or erase
+  // The simple graphs can be refered as two containers: a node container
+  // and an edge container. But they do not store values directly, they
+  // are just key continars for more value containers, which are the
+  // node and edge maps.
+  //
+  // The node and edge sets of the graphs can be changed as we add or erase
   // nodes and edges in the graph. LEMON would like to handle easily
   // that the node and edge maps should contain values for all nodes or
   // edges. If we want to check on every indicing if the map contains
   // the current indicing key that cause a drawback in the performance
-  // in the library. We use another solution we notify all maps about
+  // in the library. We use another solution: we notify all maps about
   // an alteration in the graph, which cause only drawback on the
   // alteration of the graph.
   //
-  // This class provides an interface to the container. The \e first() and \e
-  // next() member functions make possible to iterate on the keys of the
-  // container. The \e id() function returns an integer id for each key.
-  // The \e maxId() function gives back an upper bound of the ids.
+  // This class provides an interface to a node or edge container.
+  // The first() and next() member functions make possible
+  // to iterate on the keys of the container.
+  // The id() function returns an integer id for each key.
+  // The maxId() function gives back an upper bound of the ids.
   //
   // For the proper functonality of this class, we should notify it
-  // about each alteration in the container. The alterations have four type
-  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
-  // \e erase() signals that only one or few items added or erased to or
-  // from the graph. If all items are erased from the graph or from an empty
-  // graph a new graph is builded then it can be signaled with the
+  // about each alteration in the container. The alterations have four type:
+  // add(), erase(), build() and clear(). The add() and
+  // erase() signal that only one or few items added or erased to or
+  // from the graph. If all items are erased from the graph or if a new graph
+  // is built from an empty graph, then it can be signaled with the
   // clear() and build() members. Important rule that if we erase items
-  // from graph we should first signal the alteration and after that erase
+  // from graphs we should first signal the alteration and after that erase
   // them from the container, on the other way on item addition we should
   // first extend the container and just after that signal the alteration.
   //
   // The alteration can be observed with a class inherited from the
-  // \e ObserverBase nested class. The signals can be handled with
+  // ObserverBase nested class. The signals can be handled with
   // overriding the virtual functions defined in the base class.  The
   // observer base can be attached to the notifier with the
-  // \e attach() member and can be detached with detach() function. The
+  // attach() member and can be detached with detach() function. The
   // alteration handlers should not call any function which signals
   // an other alteration in the same notifier and should not
   // detach any observer from the notifier.
   //
-  // Alteration observers try to be exception safe. If an \e add() or
-  // a \e clear() function throws an exception then the remaining
+  // Alteration observers try to be exception safe. If an add() or
+  // a clear() function throws an exception then the remaining
   // observeres will not be notified and the fulfilled additions will
-  // be rolled back by calling the \e erase() or \e clear()
-  // functions. Thence the \e erase() and \e clear() should not throw
-  // exception. Actullay, it can be throw only \ref ImmediateDetach
-  // exception which detach the observer from the notifier.
-  //
-  // There are some place when the alteration observing is not completly
+  // be rolled back by calling the erase() or clear() functions.
+  // Hence erase() and clear() should not throw exception.
+  // Actullay, they can throw only \ref ImmediateDetach exception,
+  // which detach the observer from the notifier.
+  //
+  // There are some cases, when the alteration observing is not completly
   // reliable. If we want to carry out the node degree in the graph
-  // as in the \ref InDegMap and we use the reverseEdge that cause
+  // as in the \ref InDegMap and we use the reverseArc(), then it cause
   // unreliable functionality. Because the alteration observing signals
-  // only erasing and adding but not the reversing it will stores bad
-  // degrees. The sub graph adaptors cannot signal the alterations because
-  // just a setting in the filter map can modify the graph and this cannot
-  // be watched in any way.
+  // only erasing and adding but not the reversing, it will stores bad
+  // degrees. Apart form that the subgraph adaptors cannot even signal
+  // the alterations because just a setting in the filter map can modify
+  // the graph and this cannot be watched in any way.
   //
   // \param _Container The container which is observed.
@@ -104,11 +105,11 @@
     typedef _Item Item;
 
-    // \brief Exception which can be called from \e clear() and
-    // \e erase().
-    //
-    // From the \e clear() and \e erase() function only this
+    // \brief Exception which can be called from clear() and
+    // erase().
+    //
+    // From the clear() and erase() function only this
     // exception is allowed to throw. The exception immediatly
     // detaches the current observer from the notifier. Because the
-    // \e clear() and \e erase() should not throw other exceptions
+    // clear() and erase() should not throw other exceptions
     // it can be used to invalidate the observer.
     struct ImmediateDetach {};
@@ -122,6 +123,5 @@
     // The observer interface contains some pure virtual functions
     // to override. The add() and erase() functions are
-    // to notify the oberver when one item is added or
-    // erased.
+    // to notify the oberver when one item is added or erased.
     //
     // The build() and clear() members are to notify the observer
Index: lemon/bits/array_map.h
===================================================================
--- lemon/bits/array_map.h	(revision 314)
+++ lemon/bits/array_map.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37,10 +37,9 @@
   // \brief Graph map based on the array storage.
   //
-  // The ArrayMap template class is graph map structure what
-  // automatically updates the map when a key is added to or erased from
-  // the map. This map uses the allocators to implement
-  // the container functionality.
+  // The ArrayMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map uses the allocators to implement the container functionality.
   //
-  // The template parameters are the Graph the current Item type and
+  // The template parameters are the Graph, the current Item type and
   // the Value type of the map.
   template <typename _Graph, typename _Item, typename _Value>
@@ -48,12 +47,12 @@
     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
   public:
-    // The graph type of the maps.
+    // The graph type.
     typedef _Graph Graph;
-    // The item type of the map.
+    // The item type.
     typedef _Item Item;
     // The reference map tag.
     typedef True ReferenceMapTag;
 
-    // The key type of the maps.
+    // The key type of the map.
     typedef _Item Key;
     // The value type of the map.
@@ -201,5 +200,5 @@
     // \brief Adds a new key to the map.
     //
-    // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
@@ -229,5 +228,5 @@
     // \brief Adds more new keys to the map.
     //
-    // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
@@ -273,5 +272,5 @@
     // \brief Erase a key from the map.
     //
-    // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
@@ -282,5 +281,5 @@
     // \brief Erase more keys from the map.
     //
-    // Erase more keys from the map. It called by the observer notifier
+    // Erase more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
@@ -291,7 +290,7 @@
     }
 
-    // \brief Buildes the map.
-    //
-    // It buildes the map. It called by the observer notifier
+    // \brief Builds the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
@@ -307,5 +306,5 @@
     // \brief Clear the map.
     //
-    // It erase all items from the map. It called by the observer notifier
+    // It erase all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {
Index: lemon/bits/base_extender.h
===================================================================
--- lemon/bits/base_extender.h	(revision 314)
+++ lemon/bits/base_extender.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -31,5 +31,5 @@
 //\ingroup digraphbits
 //\file
-//\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
 
Index: lemon/bits/bezier.h
===================================================================
--- lemon/bits/bezier.h	(revision 314)
+++ lemon/bits/bezier.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h	(revision 540)
+++ lemon/bits/default_map.h	(revision 564)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -20,5 +20,4 @@
 #define LEMON_BITS_DEFAULT_MAP_H
 
-#include <lemon/config.h>
 #include <lemon/bits/array_map.h>
 #include <lemon/bits/vector_map.h>
@@ -98,5 +97,5 @@
 
 
-#if defined LEMON_HAVE_LONG_LONG
+#if defined HAVE_LONG_LONG
 
   // long long
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h	(revision 491)
+++ lemon/bits/edge_set_extender.h	(revision 491)
@@ -0,0 +1,628 @@
+/* -*- 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_BITS_EDGE_SET_EXTENDER_H
+#define LEMON_BITS_EDGE_SET_EXTENDER_H
+
+#include <lemon/error.h>
+#include <lemon/bits/default_map.h>
+
+///\ingroup digraphbits
+///\file
+///\brief Extenders for the arc set types
+namespace lemon {
+
+  /// \ingroup digraphbits
+  ///
+  /// \brief Extender for the ArcSets
+  template <typename Base>
+  class ArcSetExtender : public Base {
+  public:
+
+    typedef Base Parent;
+    typedef ArcSetExtender Digraph;
+
+    // Base extensions
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Arc Arc;
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Arc fromId(int id, Arc) const {
+      return Parent::arcFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Arc &e) const {
+      if (n == Parent::source(e))
+	return Parent::target(e);
+      else if(n==Parent::target(e))
+	return Parent::source(e);
+      else
+	return INVALID;
+    }
+
+
+    // Alteration notifier extensions
+
+    /// The arc observer registry.
+    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
+
+  protected:
+
+    mutable ArcNotifier arc_notifier;
+
+  public:
+
+    using Parent::notifier;
+
+    /// \brief Gives back the arc alteration notifier.
+    ///
+    /// Gives back the arc alteration notifier.
+    ArcNotifier& notifier(Arc) const {
+      return arc_notifier;
+    }
+
+    // Iterable extensions
+
+    class NodeIt : public Node { 
+      const Digraph* digraph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
+	_graph.first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Digraph& _graph, const Node& node) 
+	: Node(node), digraph(&_graph) {}
+
+      NodeIt& operator++() { 
+	digraph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class ArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
+	_graph.first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Digraph& _graph, const Arc& e) : 
+	Arc(e), digraph(&_graph) { }
+
+      ArcIt& operator++() { 
+	digraph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class OutArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const Digraph& _graph, const Node& node) 
+	: digraph(&_graph) {
+	_graph.firstOut(*this, node);
+      }
+
+      OutArcIt(const Digraph& _graph, const Arc& arc) 
+	: Arc(arc), digraph(&_graph) {}
+
+      OutArcIt& operator++() { 
+	digraph->nextOut(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class InArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const Digraph& _graph, const Node& node) 
+	: digraph(&_graph) {
+	_graph.firstIn(*this, node);
+      }
+
+      InArcIt(const Digraph& _graph, const Arc& arc) : 
+	Arc(arc), digraph(&_graph) {}
+
+      InArcIt& operator++() { 
+	digraph->nextIn(*this);
+	return *this; 
+      }
+
+    };
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutArcIt &e) const {
+      return Parent::source(static_cast<const Arc&>(e));
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutArcIt &e) const {
+      return Parent::target(static_cast<const Arc&>(e));
+    }
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InArcIt &e) const {
+      return Parent::target(static_cast<const Arc&>(e));
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InArcIt &e) const {
+      return Parent::source(static_cast<const Arc&>(e));
+    }
+
+    using Parent::first;
+
+    // Mappable extension
+    
+    template <typename _Value>
+    class ArcMap 
+      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
+    public:
+      typedef ArcSetExtender Digraph;
+      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
+
+      explicit ArcMap(const Digraph& _g) 
+	: Parent(_g) {}
+      ArcMap(const Digraph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+
+      ArcMap& operator=(const ArcMap& cmap) {
+	return operator=<ArcMap>(cmap);
+      }
+
+      template <typename CMap>
+      ArcMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+
+    };
+
+
+    // Alteration extension
+
+    Arc addArc(const Node& from, const Node& to) {
+      Arc arc = Parent::addArc(from, to);
+      notifier(Arc()).add(arc);
+      return arc;
+    }
+    
+    void clear() {
+      notifier(Arc()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Arc& arc) {
+      notifier(Arc()).erase(arc);
+      Parent::erase(arc);
+    }
+
+    ArcSetExtender() {
+      arc_notifier.setContainer(*this);
+    }
+
+    ~ArcSetExtender() {
+      arc_notifier.clear();
+    }
+
+  };
+
+
+  /// \ingroup digraphbits
+  ///
+  /// \brief Extender for the EdgeSets
+  template <typename Base>
+  class EdgeSetExtender : public Base {
+
+  public:
+
+    typedef Base Parent;
+    typedef EdgeSetExtender Digraph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Arc Arc;
+    typedef typename Parent::Edge Edge;
+
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Arc fromId(int id, Arc) const {
+      return Parent::arcFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if( n == Parent::u(e))
+	return Parent::v(e);
+      else if( n == Parent::v(e))
+	return Parent::u(e);
+      else
+	return INVALID;
+    }
+
+    Arc oppositeArc(const Arc &e) const {
+      return Parent::direct(e, !Parent::direction(e));
+    }
+
+    using Parent::direct;
+    Arc direct(const Edge &e, const Node &s) const {
+      return Parent::direct(e, Parent::u(e) == s);
+    }
+
+    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
+    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
+
+
+  protected:
+
+    mutable ArcNotifier arc_notifier;
+    mutable EdgeNotifier edge_notifier;
+
+  public:
+
+    using Parent::notifier;
+    
+    ArcNotifier& notifier(Arc) const {
+      return arc_notifier;
+    }
+
+    EdgeNotifier& notifier(Edge) const {
+      return edge_notifier;
+    }
+
+
+    class NodeIt : public Node { 
+      const Digraph* digraph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
+	_graph.first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Digraph& _graph, const Node& node) 
+	: Node(node), digraph(&_graph) {}
+
+      NodeIt& operator++() { 
+	digraph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class ArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
+	_graph.first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Digraph& _graph, const Arc& e) : 
+	Arc(e), digraph(&_graph) { }
+
+      ArcIt& operator++() { 
+	digraph->next(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class OutArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const Digraph& _graph, const Node& node) 
+	: digraph(&_graph) {
+	_graph.firstOut(*this, node);
+      }
+
+      OutArcIt(const Digraph& _graph, const Arc& arc) 
+	: Arc(arc), digraph(&_graph) {}
+
+      OutArcIt& operator++() { 
+	digraph->nextOut(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class InArcIt : public Arc { 
+      const Digraph* digraph;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const Digraph& _graph, const Node& node) 
+	: digraph(&_graph) {
+	_graph.firstIn(*this, node);
+      }
+
+      InArcIt(const Digraph& _graph, const Arc& arc) : 
+	Arc(arc), digraph(&_graph) {}
+
+      InArcIt& operator++() { 
+	digraph->nextIn(*this);
+	return *this; 
+      }
+
+    };
+
+
+    class EdgeIt : public Parent::Edge { 
+      const Digraph* digraph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
+	_graph.first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Digraph& _graph, const Edge& e) : 
+	Edge(e), digraph(&_graph) { }
+
+      EdgeIt& operator++() { 
+	digraph->next(*this);
+	return *this; 
+      }
+
+    };
+
+    class IncEdgeIt : public Parent::Edge {
+      friend class EdgeSetExtender;
+      const Digraph* digraph;
+      bool direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
+
+      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
+	_graph.firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
+	: digraph(&_graph), Edge(ue) {
+	direction = (_graph.source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+	digraph->nextInc(*this, direction);
+	return *this; 
+      }
+    };
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutArcIt &e) const {
+      return Parent::source(static_cast<const Arc&>(e));
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutArcIt &e) const {
+      return Parent::target(static_cast<const Arc&>(e));
+    }
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InArcIt &e) const {
+      return Parent::target(static_cast<const Arc&>(e));
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InArcIt &e) const {
+      return Parent::source(static_cast<const Arc&>(e));
+    }
+
+    /// Base node of the iterator
+    ///
+    /// Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &e) const {
+      return e.direction ? u(e) : v(e);
+    }
+    /// Running node of the iterator
+    ///
+    /// Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &e) const {
+      return e.direction ? v(e) : u(e);
+    }
+
+
+    template <typename _Value>
+    class ArcMap 
+      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
+    public:
+      typedef EdgeSetExtender Digraph;
+      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
+
+      ArcMap(const Digraph& _g) 
+	: Parent(_g) {}
+      ArcMap(const Digraph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+
+      ArcMap& operator=(const ArcMap& cmap) {
+	return operator=<ArcMap>(cmap);
+      }
+
+      template <typename CMap>
+      ArcMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+
+    };
+
+
+    template <typename _Value>
+    class EdgeMap 
+      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
+    public:
+      typedef EdgeSetExtender Digraph;
+      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
+
+      EdgeMap(const Digraph& _g) 
+	: Parent(_g) {}
+
+      EdgeMap(const Digraph& _g, const _Value& _v) 
+	: Parent(_g, _v) {}
+
+      EdgeMap& operator=(const EdgeMap& cmap) {
+	return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+	return *this;
+      }
+
+    };
+
+
+    // Alteration extension
+
+    Edge addEdge(const Node& from, const Node& to) {
+      Edge edge = Parent::addEdge(from, to);
+      notifier(Edge()).add(edge);
+      std::vector<Arc> arcs;
+      arcs.push_back(Parent::direct(edge, true));
+      arcs.push_back(Parent::direct(edge, false));
+      notifier(Arc()).add(arcs);
+      return edge;
+    }
+    
+    void clear() {
+      notifier(Arc()).clear();
+      notifier(Edge()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Edge& edge) {
+      std::vector<Arc> arcs;
+      arcs.push_back(Parent::direct(edge, true));
+      arcs.push_back(Parent::direct(edge, false));
+      notifier(Arc()).erase(arcs);
+      notifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+
+
+    EdgeSetExtender() {
+      arc_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+    }
+
+    ~EdgeSetExtender() {
+      edge_notifier.clear();
+      arc_notifier.clear();
+    }
+    
+  };
+
+}
+
+#endif
Index: lemon/bits/enable_if.h
===================================================================
--- lemon/bits/enable_if.h	(revision 314)
+++ lemon/bits/enable_if.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/bits/graph_adaptor_extender.h
===================================================================
--- lemon/bits/graph_adaptor_extender.h	(revision 478)
+++ lemon/bits/graph_adaptor_extender.h	(revision 478)
@@ -0,0 +1,399 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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_BITS_GRAPH_ADAPTOR_EXTENDER_H
+#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
+
+#include <lemon/core.h>
+#include <lemon/error.h>
+
+#include <lemon/bits/default_map.h>
+
+namespace lemon {
+
+  template <typename _Digraph>
+  class DigraphAdaptorExtender : public _Digraph {
+  public:
+
+    typedef _Digraph Parent;
+    typedef _Digraph Digraph;
+    typedef DigraphAdaptorExtender Adaptor;
+
+    // Base extensions
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Arc Arc;
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Arc fromId(int id, Arc) const {
+      return Parent::arcFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Arc &e) const {
+      if (n == Parent::source(e))
+        return Parent::target(e);
+      else if(n==Parent::target(e))
+        return Parent::source(e);
+      else
+        return INVALID;
+    }
+
+    class NodeIt : public Node {
+      const Adaptor* _adaptor;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
+        _adaptor->first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Adaptor& adaptor, const Node& node)
+        : Node(node), _adaptor(&adaptor) {}
+
+      NodeIt& operator++() {
+        _adaptor->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
+        _adaptor->first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Adaptor& adaptor, const Arc& e) :
+        Arc(e), _adaptor(&adaptor) { }
+
+      ArcIt& operator++() {
+        _adaptor->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const Adaptor& adaptor, const Node& node)
+        : _adaptor(&adaptor) {
+        _adaptor->firstOut(*this, node);
+      }
+
+      OutArcIt(const Adaptor& adaptor, const Arc& arc)
+        : Arc(arc), _adaptor(&adaptor) {}
+
+      OutArcIt& operator++() {
+        _adaptor->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const Adaptor& adaptor, const Node& node)
+        : _adaptor(&adaptor) {
+        _adaptor->firstIn(*this, node);
+      }
+
+      InArcIt(const Adaptor& adaptor, const Arc& arc) :
+        Arc(arc), _adaptor(&adaptor) {}
+
+      InArcIt& operator++() {
+        _adaptor->nextIn(*this);
+        return *this;
+      }
+
+    };
+
+    Node baseNode(const OutArcIt &e) const {
+      return Parent::source(e);
+    }
+    Node runningNode(const OutArcIt &e) const {
+      return Parent::target(e);
+    }
+
+    Node baseNode(const InArcIt &e) const {
+      return Parent::target(e);
+    }
+    Node runningNode(const InArcIt &e) const {
+      return Parent::source(e);
+    }
+
+  };
+
+  template <typename _Graph>
+  class GraphAdaptorExtender : public _Graph {
+  public:
+
+    typedef _Graph Parent;
+    typedef _Graph Graph;
+    typedef GraphAdaptorExtender Adaptor;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Arc Arc;
+    typedef typename Parent::Edge Edge;
+
+    // Graph extension
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Arc fromId(int id, Arc) const {
+      return Parent::arcFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if( n == Parent::u(e))
+        return Parent::v(e);
+      else if( n == Parent::v(e))
+        return Parent::u(e);
+      else
+        return INVALID;
+    }
+
+    Arc oppositeArc(const Arc &a) const {
+      return Parent::direct(a, !Parent::direction(a));
+    }
+
+    using Parent::direct;
+    Arc direct(const Edge &e, const Node &s) const {
+      return Parent::direct(e, Parent::u(e) == s);
+    }
+
+
+    class NodeIt : public Node {
+      const Adaptor* _adaptor;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
+        _adaptor->first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Adaptor& adaptor, const Node& node)
+        : Node(node), _adaptor(&adaptor) {}
+
+      NodeIt& operator++() {
+        _adaptor->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
+        _adaptor->first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Adaptor& adaptor, const Arc& e) :
+        Arc(e), _adaptor(&adaptor) { }
+
+      ArcIt& operator++() {
+        _adaptor->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const Adaptor& adaptor, const Node& node)
+        : _adaptor(&adaptor) {
+        _adaptor->firstOut(*this, node);
+      }
+
+      OutArcIt(const Adaptor& adaptor, const Arc& arc)
+        : Arc(arc), _adaptor(&adaptor) {}
+
+      OutArcIt& operator++() {
+        _adaptor->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
+      const Adaptor* _adaptor;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const Adaptor& adaptor, const Node& node)
+        : _adaptor(&adaptor) {
+        _adaptor->firstIn(*this, node);
+      }
+
+      InArcIt(const Adaptor& adaptor, const Arc& arc) :
+        Arc(arc), _adaptor(&adaptor) {}
+
+      InArcIt& operator++() {
+        _adaptor->nextIn(*this);
+        return *this;
+      }
+
+    };
+
+    class EdgeIt : public Parent::Edge {
+      const Adaptor* _adaptor;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
+        _adaptor->first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Adaptor& adaptor, const Edge& e) :
+        Edge(e), _adaptor(&adaptor) { }
+
+      EdgeIt& operator++() {
+        _adaptor->next(*this);
+        return *this;
+      }
+
+    };
+
+    class IncEdgeIt : public Edge {
+      friend class GraphAdaptorExtender;
+      const Adaptor* _adaptor;
+      bool direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
+
+      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
+        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
+      }
+
+      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
+        : _adaptor(&adaptor), Edge(e) {
+        direction = (_adaptor->u(e) == n);
+      }
+
+      IncEdgeIt& operator++() {
+        _adaptor->nextInc(*this, direction);
+        return *this;
+      }
+    };
+
+    Node baseNode(const OutArcIt &a) const {
+      return Parent::source(a);
+    }
+    Node runningNode(const OutArcIt &a) const {
+      return Parent::target(a);
+    }
+
+    Node baseNode(const InArcIt &a) const {
+      return Parent::target(a);
+    }
+    Node runningNode(const InArcIt &a) const {
+      return Parent::source(a);
+    }
+
+    Node baseNode(const IncEdgeIt &e) const {
+      return e.direction ? Parent::u(e) : Parent::v(e);
+    }
+    Node runningNode(const IncEdgeIt &e) const {
+      return e.direction ? Parent::v(e) : Parent::u(e);
+    }
+
+  };
+
+}
+
+
+#endif
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h	(revision 314)
+++ lemon/bits/graph_extender.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -30,10 +30,10 @@
 //\ingroup graphbits
 //\file
-//\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
 
   // \ingroup graphbits
   //
-  // \brief Extender for the Digraphs
+  // \brief Extender for the digraph implementations
   template <typename Base>
   class DigraphExtender : public Base {
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h	(revision 314)
+++ lemon/bits/map_extender.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/bits/path_dump.h
===================================================================
--- lemon/bits/path_dump.h	(revision 209)
+++ lemon/bits/path_dump.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: lemon/bits/solver_bits.h
===================================================================
--- lemon/bits/solver_bits.h	(revision 482)
+++ lemon/bits/solver_bits.h	(revision 482)
@@ -0,0 +1,191 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * 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_BITS_SOLVER_BITS_H
+#define LEMON_BITS_SOLVER_BITS_H
+
+namespace lemon {
+
+  namespace _solver_bits {
+
+    class VarIndex {
+    private:
+      struct ItemT {
+        int prev, next;
+        int index;
+      };
+      std::vector<ItemT> items;
+      int first_item, last_item, first_free_item;
+
+      std::vector<int> cross;
+
+    public:
+
+      VarIndex()
+        : first_item(-1), last_item(-1), first_free_item(-1) {
+      }
+
+      void clear() {
+        first_item = -1;
+        first_free_item = -1;
+        items.clear();
+        cross.clear();
+      }
+
+      int addIndex(int idx) {
+        int n;
+        if (first_free_item == -1) {
+          n = items.size();
+          items.push_back(ItemT());
+        } else {
+          n = first_free_item;
+          first_free_item = items[n].next;
+          if (first_free_item != -1) {
+            items[first_free_item].prev = -1;
+          }
+        }
+        items[n].index = idx;
+        if (static_cast<int>(cross.size()) <= idx) {
+          cross.resize(idx + 1, -1);
+        }
+        cross[idx] = n;
+
+        items[n].prev = last_item;
+        items[n].next = -1;
+        if (last_item != -1) {
+          items[last_item].next = n;
+        } else {
+          first_item = n;
+        }
+        last_item = n;
+
+        return n;
+      }
+
+      int addIndex(int idx, int n) {
+        while (n >= static_cast<int>(items.size())) {
+          items.push_back(ItemT());
+          items.back().prev = -1;
+          items.back().next = first_free_item;
+          if (first_free_item != -1) {
+            items[first_free_item].prev = items.size() - 1;
+          }
+          first_free_item = items.size() - 1;
+        }
+        if (items[n].next != -1) {
+          items[items[n].next].prev = items[n].prev;
+        }
+        if (items[n].prev != -1) {
+          items[items[n].prev].next = items[n].next;
+        } else {
+          first_free_item = items[n].next;
+        }
+
+        items[n].index = idx;
+        if (static_cast<int>(cross.size()) <= idx) {
+          cross.resize(idx + 1, -1);
+        }
+        cross[idx] = n;
+
+        items[n].prev = last_item;
+        items[n].next = -1;
+        if (last_item != -1) {
+          items[last_item].next = n;
+        } else {
+          first_item = n;
+        }
+        last_item = n;
+
+        return n;
+      }
+
+      void eraseIndex(int idx) {
+        int n = cross[idx];
+
+        if (items[n].prev != -1) {
+          items[items[n].prev].next = items[n].next;
+        } else {
+          first_item = items[n].next;
+        }
+        if (items[n].next != -1) {
+          items[items[n].next].prev = items[n].prev;
+        } else {
+          last_item = items[n].prev;
+        }
+
+        if (first_free_item != -1) {
+          items[first_free_item].prev = n;
+        }
+        items[n].next = first_free_item;
+        items[n].prev = -1;
+        first_free_item = n;
+
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      int maxIndex() const {
+        return cross.size() - 1;
+      }
+
+      void shiftIndices(int idx) {
+        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
+          cross[i - 1] = cross[i];
+          if (cross[i] != -1) {
+            --items[cross[i]].index;
+          }
+        }
+        cross.back() = -1;
+        cross.pop_back();
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      void relocateIndex(int idx, int jdx) {
+        cross[idx] = cross[jdx];
+        items[cross[jdx]].index = idx;
+        cross[jdx] = -1;
+
+        while (!cross.empty() && cross.back() == -1) {
+          cross.pop_back();
+        }
+      }
+
+      int operator[](int idx) const {
+        return cross[idx];
+      }
+
+      int operator()(int fdx) const {
+        return items[fdx].index;
+      }
+
+      void firstItem(int& fdx) const {
+        fdx = first_item;
+      }
+
+      void nextItem(int& fdx) const {
+        fdx = items[fdx].next;
+      }
+
+    };
+  }
+}
+
+#endif
Index: lemon/bits/traits.h
===================================================================
--- lemon/bits/traits.h	(revision 314)
+++ lemon/bits/traits.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -219,4 +219,17 @@
 
   template <typename Graph, typename Enable = void>
+  struct ArcNumTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename Graph>
+  struct ArcNumTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::ArcNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename Graph, typename Enable = void>
   struct EdgeNumTagIndicator {
     static const bool value = false;
@@ -232,4 +245,17 @@
 
   template <typename Graph, typename Enable = void>
+  struct FindArcTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename Graph>
+  struct FindArcTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::FindArcTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename Graph, typename Enable = void>
   struct FindEdgeTagIndicator {
     static const bool value = false;
Index: lemon/bits/variant.h
===================================================================
--- lemon/bits/variant.h	(revision 463)
+++ lemon/bits/variant.h	(revision 463)
@@ -0,0 +1,494 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * 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_BITS_VARIANT_H
+#define LEMON_BITS_VARIANT_H
+
+#include <lemon/assert.h>
+
+// \file
+// \brief Variant types
+
+namespace lemon {
+
+  namespace _variant_bits {
+
+    template <int left, int right>
+    struct CTMax {
+      static const int value = left < right ? right : left;
+    };
+
+  }
+
+
+  // \brief Simple Variant type for two types
+  //
+  // Simple Variant type for two types. The Variant type is a type-safe
+  // union. C++ has strong limitations for using unions, for
+  // example you cannot store a type with non-default constructor or
+  // destructor in a union. This class always knowns the current
+  // state of the variant and it cares for the proper construction
+  // and destruction.
+  template <typename _First, typename _Second>
+  class BiVariant {
+  public:
+
+    // \brief The \c First type.
+    typedef _First First;
+    // \brief The \c Second type.
+    typedef _Second Second;
+
+    // \brief Constructor
+    //
+    // This constructor initalizes to the default value of the \c First
+    // type.
+    BiVariant() {
+      flag = true;
+      new(reinterpret_cast<First*>(data)) First();
+    }
+
+    // \brief Constructor
+    //
+    // This constructor initalizes to the given value of the \c First
+    // type.
+    BiVariant(const First& f) {
+      flag = true;
+      new(reinterpret_cast<First*>(data)) First(f);
+    }
+
+    // \brief Constructor
+    //
+    // This constructor initalizes to the given value of the \c
+    // Second type.
+    BiVariant(const Second& s) {
+      flag = false;
+      new(reinterpret_cast<Second*>(data)) Second(s);
+    }
+
+    // \brief Copy constructor
+    //
+    // Copy constructor
+    BiVariant(const BiVariant& bivariant) {
+      flag = bivariant.flag;
+      if (flag) {
+        new(reinterpret_cast<First*>(data)) First(bivariant.first());
+      } else {
+        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
+      }
+    }
+
+    // \brief Destrcutor
+    //
+    // Destructor
+    ~BiVariant() {
+      destroy();
+    }
+
+    // \brief Set to the default value of the \c First type.
+    //
+    // This function sets the variant to the default value of the \c
+    // First type.
+    BiVariant& setFirst() {
+      destroy();
+      flag = true;
+      new(reinterpret_cast<First*>(data)) First();
+      return *this;
+    }
+
+    // \brief Set to the given value of the \c First type.
+    //
+    // This function sets the variant to the given value of the \c
+    // First type.
+    BiVariant& setFirst(const First& f) {
+      destroy();
+      flag = true;
+      new(reinterpret_cast<First*>(data)) First(f);
+      return *this;
+    }
+
+    // \brief Set to the default value of the \c Second type.
+    //
+    // This function sets the variant to the default value of the \c
+    // Second type.
+    BiVariant& setSecond() {
+      destroy();
+      flag = false;
+      new(reinterpret_cast<Second*>(data)) Second();
+      return *this;
+    }
+
+    // \brief Set to the given value of the \c Second type.
+    //
+    // This function sets the variant to the given value of the \c
+    // Second type.
+    BiVariant& setSecond(const Second& s) {
+      destroy();
+      flag = false;
+      new(reinterpret_cast<Second*>(data)) Second(s);
+      return *this;
+    }
+
+    // \brief Operator form of the \c setFirst()
+    BiVariant& operator=(const First& f) {
+      return setFirst(f);
+    }
+
+    // \brief Operator form of the \c setSecond()
+    BiVariant& operator=(const Second& s) {
+      return setSecond(s);
+    }
+
+    // \brief Assign operator
+    BiVariant& operator=(const BiVariant& bivariant) {
+      if (this == &bivariant) return *this;
+      destroy();
+      flag = bivariant.flag;
+      if (flag) {
+        new(reinterpret_cast<First*>(data)) First(bivariant.first());
+      } else {
+        new(reinterpret_cast<Second*>(data)) Second(bivariant.second());
+      }
+      return *this;
+    }
+
+    // \brief Reference to the value
+    //
+    // Reference to the value of the \c First type.
+    // \pre The BiVariant should store value of \c First type.
+    First& first() {
+      LEMON_DEBUG(flag, "Variant wrong state");
+      return *reinterpret_cast<First*>(data);
+    }
+
+    // \brief Const reference to the value
+    //
+    // Const reference to the value of the \c First type.
+    // \pre The BiVariant should store value of \c First type.
+    const First& first() const {
+      LEMON_DEBUG(flag, "Variant wrong state");
+      return *reinterpret_cast<const First*>(data);
+    }
+
+    // \brief Operator form of the \c first()
+    operator First&() { return first(); }
+    // \brief Operator form of the const \c first()
+    operator const First&() const { return first(); }
+
+    // \brief Reference to the value
+    //
+    // Reference to the value of the \c Second type.
+    // \pre The BiVariant should store value of \c Second type.
+    Second& second() {
+      LEMON_DEBUG(!flag, "Variant wrong state");
+      return *reinterpret_cast<Second*>(data);
+    }
+
+    // \brief Const reference to the value
+    //
+    // Const reference to the value of the \c Second type.
+    // \pre The BiVariant should store value of \c Second type.
+    const Second& second() const {
+      LEMON_DEBUG(!flag, "Variant wrong state");
+      return *reinterpret_cast<const Second*>(data);
+    }
+
+    // \brief Operator form of the \c second()
+    operator Second&() { return second(); }
+    // \brief Operator form of the const \c second()
+    operator const Second&() const { return second(); }
+
+    // \brief %True when the variant is in the first state
+    //
+    // %True when the variant stores value of the \c First type.
+    bool firstState() const { return flag; }
+
+    // \brief %True when the variant is in the second state
+    //
+    // %True when the variant stores value of the \c Second type.
+    bool secondState() const { return !flag; }
+
+  private:
+
+    void destroy() {
+      if (flag) {
+        reinterpret_cast<First*>(data)->~First();
+      } else {
+        reinterpret_cast<Second*>(data)->~Second();
+      }
+    }
+
+    char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value];
+    bool flag;
+  };
+
+  namespace _variant_bits {
+
+    template <int _idx, typename _TypeMap>
+    struct Memory {
+
+      typedef typename _TypeMap::template Map<_idx>::Type Current;
+
+      static void destroy(int index, char* place) {
+        if (index == _idx) {
+          reinterpret_cast<Current*>(place)->~Current();
+        } else {
+          Memory<_idx - 1, _TypeMap>::destroy(index, place);
+        }
+      }
+
+      static void copy(int index, char* to, const char* from) {
+        if (index == _idx) {
+          new (reinterpret_cast<Current*>(to))
+            Current(reinterpret_cast<const Current*>(from));
+        } else {
+          Memory<_idx - 1, _TypeMap>::copy(index, to, from);
+        }
+      }
+
+    };
+
+    template <typename _TypeMap>
+    struct Memory<-1, _TypeMap> {
+
+      static void destroy(int, char*) {
+        LEMON_DEBUG(false, "Variant wrong index.");
+      }
+
+      static void copy(int, char*, const char*) {
+        LEMON_DEBUG(false, "Variant wrong index.");
+      }
+    };
+
+    template <int _idx, typename _TypeMap>
+    struct Size {
+      static const int value =
+      CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type),
+            Size<_idx - 1, _TypeMap>::value>::value;
+    };
+
+    template <typename _TypeMap>
+    struct Size<0, _TypeMap> {
+      static const int value =
+      sizeof(typename _TypeMap::template Map<0>::Type);
+    };
+
+  }
+
+  // \brief Variant type
+  //
+  // Simple Variant type. The Variant type is a type-safe union.
+  // C++ has strong limitations for using unions, for example you
+  // cannot store type with non-default constructor or destructor in
+  // a union. This class always knowns the current state of the
+  // variant and it cares for the proper construction and
+  // destruction.
+  //
+  // \param _num The number of the types which can be stored in the
+  // variant type.
+  // \param _TypeMap This class describes the types of the Variant. The
+  // _TypeMap::Map<index>::Type should be a valid type for each index
+  // in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper
+  // class to define such type mappings up to 10 types.
+  //
+  // And the usage of the class:
+  //\code
+  // typedef Variant<3, VariantTypeMap<int, std::string, double> > MyVariant;
+  // MyVariant var;
+  // var.set<0>(12);
+  // std::cout << var.get<0>() << std::endl;
+  // var.set<1>("alpha");
+  // std::cout << var.get<1>() << std::endl;
+  // var.set<2>(0.75);
+  // std::cout << var.get<2>() << std::endl;
+  //\endcode
+  //
+  // The result of course:
+  //\code
+  // 12
+  // alpha
+  // 0.75
+  //\endcode
+  template <int _num, typename _TypeMap>
+  class Variant {
+  public:
+
+    static const int num = _num;
+
+    typedef _TypeMap TypeMap;
+
+    // \brief Constructor
+    //
+    // This constructor initalizes to the default value of the \c type
+    // with 0 index.
+    Variant() {
+      flag = 0;
+      new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data))
+        typename TypeMap::template Map<0>::Type();
+    }
+
+
+    // \brief Copy constructor
+    //
+    // Copy constructor
+    Variant(const Variant& variant) {
+      flag = variant.flag;
+      _variant_bits::Memory<num - 1, TypeMap>::copy(flag, data, variant.data);
+    }
+
+    // \brief Assign operator
+    //
+    // Assign operator
+    Variant& operator=(const Variant& variant) {
+      if (this == &variant) return *this;
+      _variant_bits::Memory<num - 1, TypeMap>::
+        destroy(flag, data);
+      flag = variant.flag;
+      _variant_bits::Memory<num - 1, TypeMap>::
+        copy(flag, data, variant.data);
+      return *this;
+    }
+
+    // \brief Destrcutor
+    //
+    // Destructor
+    ~Variant() {
+      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
+    }
+
+    // \brief Set to the default value of the type with \c _idx index.
+    //
+    // This function sets the variant to the default value of the
+    // type with \c _idx index.
+    template <int _idx>
+    Variant& set() {
+      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
+      flag = _idx;
+      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
+        typename TypeMap::template Map<_idx>::Type();
+      return *this;
+    }
+
+    // \brief Set to the given value of the type with \c _idx index.
+    //
+    // This function sets the variant to the given value of the type
+    // with \c _idx index.
+    template <int _idx>
+    Variant& set(const typename _TypeMap::template Map<_idx>::Type& init) {
+      _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data);
+      flag = _idx;
+      new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data))
+        typename TypeMap::template Map<_idx>::Type(init);
+      return *this;
+    }
+
+    // \brief Gets the current value of the type with \c _idx index.
+    //
+    // Gets the current value of the type with \c _idx index.
+    template <int _idx>
+    const typename TypeMap::template Map<_idx>::Type& get() const {
+      LEMON_DEBUG(_idx == flag, "Variant wrong index");
+      return *reinterpret_cast<const typename TypeMap::
+        template Map<_idx>::Type*>(data);
+    }
+
+    // \brief Gets the current value of the type with \c _idx index.
+    //
+    // Gets the current value of the type with \c _idx index.
+    template <int _idx>
+    typename _TypeMap::template Map<_idx>::Type& get() {
+      LEMON_DEBUG(_idx == flag, "Variant wrong index");
+      return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>
+        (data);
+    }
+
+    // \brief Returns the current state of the variant.
+    //
+    // Returns the current state of the variant.
+    int state() const {
+      return flag;
+    }
+
+  private:
+
+    char data[_variant_bits::Size<num - 1, TypeMap>::value];
+    int flag;
+  };
+
+  namespace _variant_bits {
+
+    template <int _index, typename _List>
+    struct Get {
+      typedef typename Get<_index - 1, typename _List::Next>::Type Type;
+    };
+
+    template <typename _List>
+    struct Get<0, _List> {
+      typedef typename _List::Type Type;
+    };
+
+    struct List {};
+
+    template <typename _Type, typename _List>
+    struct Insert {
+      typedef _List Next;
+      typedef _Type Type;
+    };
+
+    template <int _idx, typename _T0, typename _T1, typename _T2,
+              typename _T3, typename _T4, typename _T5, typename _T6,
+              typename _T7, typename _T8, typename _T9>
+    struct Mapper {
+      typedef List L10;
+      typedef Insert<_T9, L10> L9;
+      typedef Insert<_T8, L9> L8;
+      typedef Insert<_T7, L8> L7;
+      typedef Insert<_T6, L7> L6;
+      typedef Insert<_T5, L6> L5;
+      typedef Insert<_T4, L5> L4;
+      typedef Insert<_T3, L4> L3;
+      typedef Insert<_T2, L3> L2;
+      typedef Insert<_T1, L2> L1;
+      typedef Insert<_T0, L1> L0;
+      typedef typename Get<_idx, L0>::Type Type;
+    };
+
+  }
+
+  // \brief Helper class for Variant
+  //
+  // Helper class to define type mappings for Variant. This class
+  // converts the template parameters to be mappable by integer.
+  // \see Variant
+  template <
+    typename _T0,
+    typename _T1 = void, typename _T2 = void, typename _T3 = void,
+    typename _T4 = void, typename _T5 = void, typename _T6 = void,
+    typename _T7 = void, typename _T8 = void, typename _T9 = void>
+  struct VariantTypeMap {
+    template <int _idx>
+    struct Map {
+      typedef typename _variant_bits::
+      Mapper<_idx, _T0, _T1, _T2, _T3, _T4, _T5, _T6, _T7, _T8, _T9>::Type
+      Type;
+    };
+  };
+
+}
+
+
+#endif
Index: lemon/bits/vector_map.h
===================================================================
--- lemon/bits/vector_map.h	(revision 314)
+++ lemon/bits/vector_map.h	(revision 463)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -39,7 +39,7 @@
   // \brief Graph map based on the std::vector storage.
   //
-  // The VectorMap template class is graph map structure what
-  // automatically updates the map when a key is added to or erased from
-  // the map. This map type uses the std::vector to store the values.
+  // The VectorMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map type uses std::vector to store the values.
   //
   // \tparam _Graph The graph this map is attached to.
@@ -170,5 +170,5 @@
     // \brief Adds a new key to the map.
     //
-    // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
@@ -181,5 +181,5 @@
     // \brief Adds more new keys to the map.
     //
-    // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
@@ -196,5 +196,5 @@
     // \brief Erase a key from the map.
     //
-    // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
@@ -204,5 +204,5 @@
     // \brief Erase more keys from the map.
     //
-    // Erase more keys from the map. It called by the observer notifier
+    // It erases more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
@@ -212,7 +212,7 @@
     }
 
-    // \brief Buildes the map.
-    //
-    // It buildes the map. It called by the observer notifier
+    // \brief Build the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
@@ -224,5 +224,5 @@
     // \brief Clear the map.
     //
-    // It erase all items from the map. It called by the observer notifier
+    // It erases all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {
