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 1081)
@@ -3,5 +3,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2011
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -37,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.
-    typedef _Graph Graph;
-    // The item type of the map.
+    // The graph type.
+    typedef _Graph GraphType;
+    // The item type.
     typedef _Item Item;
     // The reference map tag.
     typedef True ReferenceMapTag;
 
-    // The key type of the maps.
+    // The key type of the map.
     typedef _Item Key;
     // The value type of the map.
@@ -65,11 +64,15 @@
     typedef _Value& Reference;
 
+    // The map type.
+    typedef ArrayMap Map;
+
     // The notifier type.
     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 
+  private:
+
     // The MapBase of the Map which imlements the core regisitry function.
     typedef typename Notifier::ObserverBase Parent;
 
-  private:
     typedef std::allocator<Value> Allocator;
 
@@ -79,5 +82,5 @@
     //
     // Graph initialized map constructor.
-    explicit ArrayMap(const Graph& graph) {
+    explicit ArrayMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
@@ -93,5 +96,5 @@
     //
     // It constructs a map and initialize all of the the map.
-    ArrayMap(const Graph& graph, const Value& value) {
+    ArrayMap(const GraphType& graph, const Value& value) {
       Parent::attach(graph.notifier(Item()));
       allocate_memory();
@@ -137,5 +140,5 @@
     // \brief Template assign operator.
     //
-    // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
@@ -201,5 +204,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 +232,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 +276,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 +285,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 +294,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 +310,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)
+++ 	(revision )
@@ -1,494 +1,0 @@
-/* -*- 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_BASE_EXTENDER_H
-#define LEMON_BITS_BASE_EXTENDER_H
-
-#include <lemon/core.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/map_extender.h>
-#include <lemon/bits/default_map.h>
-
-#include <lemon/concept_check.h>
-#include <lemon/concepts/maps.h>
-
-//\ingroup digraphbits
-//\file
-//\brief Extenders for the digraph types
-namespace lemon {
-
-  // \ingroup digraphbits
-  //
-  // \brief BaseDigraph to BaseGraph extender
-  template <typename Base>
-  class UndirDigraphExtender : public Base {
-
-  public:
-
-    typedef Base Parent;
-    typedef typename Parent::Arc Edge;
-    typedef typename Parent::Node Node;
-
-    typedef True UndirectedTag;
-
-    class Arc : public Edge {
-      friend class UndirDigraphExtender;
-
-    protected:
-      bool forward;
-
-      Arc(const Edge &ue, bool _forward) :
-        Edge(ue), forward(_forward) {}
-
-    public:
-      Arc() {}
-
-      // Invalid arc constructor
-      Arc(Invalid i) : Edge(i), forward(true) {}
-
-      bool operator==(const Arc &that) const {
-        return forward==that.forward && Edge(*this)==Edge(that);
-      }
-      bool operator!=(const Arc &that) const {
-        return forward!=that.forward || Edge(*this)!=Edge(that);
-      }
-      bool operator<(const Arc &that) const {
-        return forward<that.forward ||
-          (!(that.forward<forward) && Edge(*this)<Edge(that));
-      }
-    };
-
-    // First node of the edge
-    Node u(const Edge &e) const {
-      return Parent::source(e);
-    }
-
-    // Source of the given arc
-    Node source(const Arc &e) const {
-      return e.forward ? Parent::source(e) : Parent::target(e);
-    }
-
-    // Second node of the edge
-    Node v(const Edge &e) const {
-      return Parent::target(e);
-    }
-
-    // Target of the given arc
-    Node target(const Arc &e) const {
-      return e.forward ? Parent::target(e) : Parent::source(e);
-    }
-
-    // \brief Directed arc from an edge.
-    //
-    // Returns a directed arc corresponding to the specified edge.
-    // If the given bool is true, the first node of the given edge and
-    // the source node of the returned arc are the same.
-    static Arc direct(const Edge &e, bool d) {
-      return Arc(e, d);
-    }
-
-    // Returns whether the given directed arc has the same orientation
-    // as the corresponding edge.
-    static bool direction(const Arc &a) { return a.forward; }
-
-    using Parent::first;
-    using Parent::next;
-
-    void first(Arc &e) const {
-      Parent::first(e);
-      e.forward=true;
-    }
-
-    void next(Arc &e) const {
-      if( e.forward ) {
-        e.forward = false;
-      }
-      else {
-        Parent::next(e);
-        e.forward = true;
-      }
-    }
-
-    void firstOut(Arc &e, const Node &n) const {
-      Parent::firstIn(e,n);
-      if( Edge(e) != INVALID ) {
-        e.forward = false;
-      }
-      else {
-        Parent::firstOut(e,n);
-        e.forward = true;
-      }
-    }
-    void nextOut(Arc &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::target(e);
-        Parent::nextIn(e);
-        if( Edge(e) == INVALID ) {
-          Parent::firstOut(e, n);
-          e.forward = true;
-        }
-      }
-      else {
-        Parent::nextOut(e);
-      }
-    }
-
-    void firstIn(Arc &e, const Node &n) const {
-      Parent::firstOut(e,n);
-      if( Edge(e) != INVALID ) {
-        e.forward = false;
-      }
-      else {
-        Parent::firstIn(e,n);
-        e.forward = true;
-      }
-    }
-    void nextIn(Arc &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::source(e);
-        Parent::nextOut(e);
-        if( Edge(e) == INVALID ) {
-          Parent::firstIn(e, n);
-          e.forward = true;
-        }
-      }
-      else {
-        Parent::nextIn(e);
-      }
-    }
-
-    void firstInc(Edge &e, bool &d, const Node &n) const {
-      d = true;
-      Parent::firstOut(e, n);
-      if (e != INVALID) return;
-      d = false;
-      Parent::firstIn(e, n);
-    }
-
-    void nextInc(Edge &e, bool &d) const {
-      if (d) {
-        Node s = Parent::source(e);
-        Parent::nextOut(e);
-        if (e != INVALID) return;
-        d = false;
-        Parent::firstIn(e, s);
-      } else {
-        Parent::nextIn(e);
-      }
-    }
-
-    Node nodeFromId(int ix) const {
-      return Parent::nodeFromId(ix);
-    }
-
-    Arc arcFromId(int ix) const {
-      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
-    }
-
-    Edge edgeFromId(int ix) const {
-      return Parent::arcFromId(ix);
-    }
-
-    int id(const Node &n) const {
-      return Parent::id(n);
-    }
-
-    int id(const Edge &e) const {
-      return Parent::id(e);
-    }
-
-    int id(const Arc &e) const {
-      return 2 * Parent::id(e) + int(e.forward);
-    }
-
-    int maxNodeId() const {
-      return Parent::maxNodeId();
-    }
-
-    int maxArcId() const {
-      return 2 * Parent::maxArcId() + 1;
-    }
-
-    int maxEdgeId() const {
-      return Parent::maxArcId();
-    }
-
-    int arcNum() const {
-      return 2 * Parent::arcNum();
-    }
-
-    int edgeNum() const {
-      return Parent::arcNum();
-    }
-
-    Arc findArc(Node s, Node t, Arc p = INVALID) const {
-      if (p == INVALID) {
-        Edge arc = Parent::findArc(s, t);
-        if (arc != INVALID) return direct(arc, true);
-        arc = Parent::findArc(t, s);
-        if (arc != INVALID) return direct(arc, false);
-      } else if (direction(p)) {
-        Edge arc = Parent::findArc(s, t, p);
-        if (arc != INVALID) return direct(arc, true);
-        arc = Parent::findArc(t, s);
-        if (arc != INVALID) return direct(arc, false);
-      } else {
-        Edge arc = Parent::findArc(t, s, p);
-        if (arc != INVALID) return direct(arc, false);
-      }
-      return INVALID;
-    }
-
-    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
-      if (s != t) {
-        if (p == INVALID) {
-          Edge arc = Parent::findArc(s, t);
-          if (arc != INVALID) return arc;
-          arc = Parent::findArc(t, s);
-          if (arc != INVALID) return arc;
-        } else if (Parent::s(p) == s) {
-          Edge arc = Parent::findArc(s, t, p);
-          if (arc != INVALID) return arc;
-          arc = Parent::findArc(t, s);
-          if (arc != INVALID) return arc;
-        } else {
-          Edge arc = Parent::findArc(t, s, p);
-          if (arc != INVALID) return arc;
-        }
-      } else {
-        return Parent::findArc(s, t, p);
-      }
-      return INVALID;
-    }
-  };
-
-  template <typename Base>
-  class BidirBpGraphExtender : public Base {
-  public:
-    typedef Base Parent;
-    typedef BidirBpGraphExtender Digraph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-
-    using Parent::first;
-    using Parent::next;
-
-    using Parent::id;
-
-    class Red : public Node {
-      friend class BidirBpGraphExtender;
-    public:
-      Red() {}
-      Red(const Node& node) : Node(node) {
-        LEMON_DEBUG(Parent::red(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-      }
-      Red& operator=(const Node& node) {
-        LEMON_DEBUG(Parent::red(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-        Node::operator=(node);
-        return *this;
-      }
-      Red(Invalid) : Node(INVALID) {}
-      Red& operator=(Invalid) {
-        Node::operator=(INVALID);
-        return *this;
-      }
-    };
-
-    void first(Red& node) const {
-      Parent::firstRed(static_cast<Node&>(node));
-    }
-    void next(Red& node) const {
-      Parent::nextRed(static_cast<Node&>(node));
-    }
-
-    int id(const Red& node) const {
-      return Parent::redId(node);
-    }
-
-    class Blue : public Node {
-      friend class BidirBpGraphExtender;
-    public:
-      Blue() {}
-      Blue(const Node& node) : Node(node) {
-        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-      }
-      Blue& operator=(const Node& node) {
-        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-        Node::operator=(node);
-        return *this;
-      }
-      Blue(Invalid) : Node(INVALID) {}
-      Blue& operator=(Invalid) {
-        Node::operator=(INVALID);
-        return *this;
-      }
-    };
-
-    void first(Blue& node) const {
-      Parent::firstBlue(static_cast<Node&>(node));
-    }
-    void next(Blue& node) const {
-      Parent::nextBlue(static_cast<Node&>(node));
-    }
-
-    int id(const Blue& node) const {
-      return Parent::redId(node);
-    }
-
-    Node source(const Edge& arc) const {
-      return red(arc);
-    }
-    Node target(const Edge& arc) const {
-      return blue(arc);
-    }
-
-    void firstInc(Edge& arc, bool& dir, const Node& node) const {
-      if (Parent::red(node)) {
-        Parent::firstFromRed(arc, node);
-        dir = true;
-      } else {
-        Parent::firstFromBlue(arc, node);
-        dir = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextInc(Edge& arc, bool& dir) const {
-      if (dir) {
-        Parent::nextFromRed(arc);
-      } else {
-        Parent::nextFromBlue(arc);
-        if (arc == INVALID) dir = true;
-      }
-    }
-
-    class Arc : public Edge {
-      friend class BidirBpGraphExtender;
-    protected:
-      bool forward;
-
-      Arc(const Edge& arc, bool _forward)
-        : Edge(arc), forward(_forward) {}
-
-    public:
-      Arc() {}
-      Arc (Invalid) : Edge(INVALID), forward(true) {}
-      bool operator==(const Arc& i) const {
-        return Edge::operator==(i) && forward == i.forward;
-      }
-      bool operator!=(const Arc& i) const {
-        return Edge::operator!=(i) || forward != i.forward;
-      }
-      bool operator<(const Arc& i) const {
-        return Edge::operator<(i) ||
-          (!(i.forward<forward) && Edge(*this)<Edge(i));
-      }
-    };
-
-    void first(Arc& arc) const {
-      Parent::first(static_cast<Edge&>(arc));
-      arc.forward = true;
-    }
-
-    void next(Arc& arc) const {
-      if (!arc.forward) {
-        Parent::next(static_cast<Edge&>(arc));
-      }
-      arc.forward = !arc.forward;
-    }
-
-    void firstOut(Arc& arc, const Node& node) const {
-      if (Parent::red(node)) {
-        Parent::firstFromRed(arc, node);
-        arc.forward = true;
-      } else {
-        Parent::firstFromBlue(arc, node);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextOut(Arc& arc) const {
-      if (arc.forward) {
-        Parent::nextFromRed(arc);
-      } else {
-        Parent::nextFromBlue(arc);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-
-    void firstIn(Arc& arc, const Node& node) const {
-      if (Parent::blue(node)) {
-        Parent::firstFromBlue(arc, node);
-        arc.forward = true;
-      } else {
-        Parent::firstFromRed(arc, node);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextIn(Arc& arc) const {
-      if (arc.forward) {
-        Parent::nextFromBlue(arc);
-      } else {
-        Parent::nextFromRed(arc);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-
-    Node source(const Arc& arc) const {
-      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
-    }
-    Node target(const Arc& arc) const {
-      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
-    }
-
-    int id(const Arc& arc) const {
-      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
-        (arc.forward ? 0 : 1);
-    }
-    Arc arcFromId(int ix) const {
-      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
-    }
-    int maxArcId() const {
-      return (Parent::maxEdgeId() << 1) + 1;
-    }
-
-    bool direction(const Arc& arc) const {
-      return arc.forward;
-    }
-
-    Arc direct(const Edge& arc, bool dir) const {
-      return Arc(arc, dir);
-    }
-
-    int arcNum() const {
-      return 2 * Parent::edgeNum();
-    }
-
-    int edgeNum() const {
-      return Parent::edgeNum();
-    }
-
-
-  };
-}
-
-#endif
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 1078)
+++ lemon/bits/default_map.h	(revision 1081)
@@ -154,13 +154,14 @@
   class DefaultMap
     : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
+    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
+
   public:
-    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     typedef DefaultMap<_Graph, _Item, _Value> Map;
 
-    typedef typename Parent::Graph Graph;
+    typedef typename Parent::GraphType GraphType;
     typedef typename Parent::Value Value;
 
-    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
-    DefaultMap(const Graph& graph, const Value& value)
+    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
+    DefaultMap(const GraphType& graph, const Value& value)
       : Parent(graph, value) {}
 
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h	(revision 1081)
+++ lemon/bits/edge_set_extender.h	(revision 1081)
@@ -0,0 +1,627 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2011
+ * 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/core.h>
+#include <lemon/error.h>
+#include <lemon/bits/default_map.h>
+#include <lemon/bits/map_extender.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 {
+    typedef Base Parent;
+
+  public:
+
+    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;
+
+    // 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> > {
+      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
+
+    public:
+      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 {
+    typedef Base Parent;
+
+  public:
+
+    typedef EdgeSetExtender Graph;
+
+    typedef True UndirectedTag;
+
+    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 Graph* graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node)
+        : Node(node), graph(&_graph) {}
+
+      NodeIt& operator++() {
+        graph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
+      const Graph* graph;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const Graph& _graph, const Arc& e) :
+        Arc(e), graph(&_graph) { }
+
+      ArcIt& operator++() {
+        graph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
+      const Graph* graph;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const Graph& _graph, const Node& node)
+        : graph(&_graph) {
+        _graph.firstOut(*this, node);
+      }
+
+      OutArcIt(const Graph& _graph, const Arc& arc)
+        : Arc(arc), graph(&_graph) {}
+
+      OutArcIt& operator++() {
+        graph->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
+      const Graph* graph;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const Graph& _graph, const Node& node)
+        : graph(&_graph) {
+        _graph.firstIn(*this, node);
+      }
+
+      InArcIt(const Graph& _graph, const Arc& arc) :
+        Arc(arc), graph(&_graph) {}
+
+      InArcIt& operator++() {
+        graph->nextIn(*this);
+        return *this;
+      }
+
+    };
+
+
+    class EdgeIt : public Parent::Edge {
+      const Graph* graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) :
+        Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() {
+        graph->next(*this);
+        return *this;
+      }
+
+    };
+
+    class IncEdgeIt : public Parent::Edge {
+      friend class EdgeSetExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
+
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+        _graph.firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
+        : graph(&_graph), Edge(ue) {
+        direction = (_graph.source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+        graph->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<Graph, Arc, _Value> > {
+      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
+
+    public:
+      explicit ArcMap(const Graph& _g)
+        : Parent(_g) {}
+      ArcMap(const Graph& _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<Graph, Edge, _Value> > {
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+
+    public:
+      explicit EdgeMap(const Graph& _g)
+        : Parent(_g) {}
+
+      EdgeMap(const Graph& _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 1081)
+++ lemon/bits/graph_adaptor_extender.h	(revision 1081)
@@ -0,0 +1,401 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2011
+ * 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>
+
+namespace lemon {
+
+  template <typename _Digraph>
+  class DigraphAdaptorExtender : public _Digraph {
+    typedef _Digraph Parent;
+
+  public:
+
+    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 {
+    typedef _Graph Parent;
+
+  public:
+
+    typedef _Graph Graph;
+    typedef GraphAdaptorExtender Adaptor;
+
+    typedef True UndirectedTag;
+
+    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 732)
@@ -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,15 +30,16 @@
 //\ingroup graphbits
 //\file
-//\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
 
   // \ingroup graphbits
   //
-  // \brief Extender for the Digraphs
+  // \brief Extender for the digraph implementations
   template <typename Base>
   class DigraphExtender : public Base {
+    typedef Base Parent;
+
   public:
 
-    typedef Base Parent;
     typedef DigraphExtender Digraph;
 
@@ -219,8 +220,7 @@
     class NodeMap
       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
-    public:
-      typedef DigraphExtender Digraph;
       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
 
+    public:
       explicit NodeMap(const Digraph& digraph)
         : Parent(digraph) {}
@@ -244,8 +244,7 @@
     class ArcMap
       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
-    public:
-      typedef DigraphExtender Digraph;
       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 
+    public:
       explicit ArcMap(const Digraph& digraph)
         : Parent(digraph) {}
@@ -331,7 +330,8 @@
   template <typename Base>
   class GraphExtender : public Base {
+    typedef Base Parent;
+
   public:
 
-    typedef Base Parent;
     typedef GraphExtender Graph;
 
@@ -602,9 +602,8 @@
     class NodeMap
       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
 
-      NodeMap(const Graph& graph)
+    public:
+      explicit NodeMap(const Graph& graph)
         : Parent(graph) {}
       NodeMap(const Graph& graph, const _Value& value)
@@ -627,9 +626,8 @@
     class ArcMap
       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 
-      ArcMap(const Graph& graph)
+    public:
+      explicit ArcMap(const Graph& graph)
         : Parent(graph) {}
       ArcMap(const Graph& graph, const _Value& value)
@@ -652,9 +650,8 @@
     class EdgeMap
       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
-    public:
-      typedef GraphExtender Graph;
       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 
-      EdgeMap(const Graph& graph)
+    public:
+      explicit EdgeMap(const Graph& graph)
         : Parent(graph) {}
 
Index: lemon/bits/map_extender.h
===================================================================
--- lemon/bits/map_extender.h	(revision 1078)
+++ lemon/bits/map_extender.h	(revision 1081)
@@ -37,15 +37,18 @@
   template <typename _Map>
   class MapExtender : public _Map {
-  public:
-
     typedef _Map Parent;
+    typedef typename Parent::GraphType GraphType;
+
+  public:
+
     typedef MapExtender Map;
-
-
-    typedef typename Parent::Graph Graph;
     typedef typename Parent::Key Item;
 
     typedef typename Parent::Key Key;
     typedef typename Parent::Value Value;
+    typedef typename Parent::Reference Reference;
+    typedef typename Parent::ConstReference ConstReference;
+
+    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 
     class MapIt;
@@ -57,8 +60,8 @@
   public:
 
-    MapExtender(const Graph& graph)
+    MapExtender(const GraphType& graph)
       : Parent(graph) {}
 
-    MapExtender(const Graph& graph, const Value& value)
+    MapExtender(const GraphType& graph, const Value& value)
       : Parent(graph, value) {}
 
@@ -76,7 +79,8 @@
   public:
     class MapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
+
       typedef typename Map::Value Value;
 
@@ -115,7 +119,7 @@
 
     class ConstMapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
 
       typedef typename Map::Value Value;
@@ -146,9 +150,9 @@
 
     class ItemIt : public Item {
-    public:
-
-      typedef Item Parent;
-
+      typedef Item Parent;
+
+    public:
       ItemIt() : map(NULL) {}
+
 
       ItemIt(Invalid i) : Parent(i), map(NULL) {}
@@ -177,15 +181,18 @@
   template <typename _Graph, typename _Map>
   class SubMapExtender : public _Map {
-  public:
-
     typedef _Map Parent;
+    typedef _Graph GraphType;
+
+  public:
+
     typedef SubMapExtender Map;
-
-    typedef _Graph Graph;
-
     typedef typename Parent::Key Item;
 
     typedef typename Parent::Key Key;
     typedef typename Parent::Value Value;
+    typedef typename Parent::Reference Reference;
+    typedef typename Parent::ConstReference ConstReference;
+
+    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 
     class MapIt;
@@ -197,8 +204,8 @@
   public:
 
-    SubMapExtender(const Graph& _graph)
+    SubMapExtender(const GraphType& _graph)
       : Parent(_graph), graph(_graph) {}
 
-    SubMapExtender(const Graph& _graph, const Value& _value)
+    SubMapExtender(const GraphType& _graph, const Value& _value)
       : Parent(_graph, _value), graph(_graph) {}
 
@@ -220,7 +227,7 @@
   public:
     class MapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
       typedef typename Map::Value Value;
 
@@ -259,7 +266,7 @@
 
     class ConstMapIt : public Item {
-    public:
-
-      typedef Item Parent;
+      typedef Item Parent;
+
+    public:
 
       typedef typename Map::Value Value;
@@ -290,9 +297,9 @@
 
     class ItemIt : public Item {
-    public:
-
-      typedef Item Parent;
-
+      typedef Item Parent;
+
+    public:
       ItemIt() : map(NULL) {}
+
 
       ItemIt(Invalid i) : Parent(i), map(NULL) { }
@@ -317,5 +324,5 @@
   private:
 
-    const Graph& graph;
+    const GraphType& graph;
 
   };
Index: lemon/bits/path_dump.h
===================================================================
--- lemon/bits/path_dump.h	(revision 1078)
+++ lemon/bits/path_dump.h	(revision 1081)
@@ -17,6 +17,9 @@
  */
 
-#ifndef LEMON_BITS_PRED_MAP_PATH_H
-#define LEMON_BITS_PRED_MAP_PATH_H
+#ifndef LEMON_BITS_PATH_DUMP_H
+#define LEMON_BITS_PATH_DUMP_H
+
+#include <lemon/core.h>
+#include <lemon/concept_check.h>
 
 namespace lemon {
Index: lemon/bits/solver_bits.h
===================================================================
--- lemon/bits/solver_bits.h	(revision 1081)
+++ lemon/bits/solver_bits.h	(revision 1081)
@@ -0,0 +1,193 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2011
+ * 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
+
+#include <vector>
+
+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 663)
@@ -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,40 +30,42 @@
   struct InvalidType {};
 
-  template <typename _Graph, typename _Item>
+  template <typename GR, typename _Item>
   class ItemSetTraits {};
 
 
-  template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct NodeNotifierIndicator {
     typedef InvalidType Type;
   };
-  template <typename Graph>
+  template <typename GR>
   struct NodeNotifierIndicator<
-    Graph,
-    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
-  > {
-    typedef typename Graph::NodeNotifier Type;
-  };
-
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Node> {
+    GR,
+    typename enable_if<typename GR::NodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::NodeNotifier Type;
+  };
+
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Node> {
   public:
 
-    typedef _Graph Graph;
-
-    typedef typename Graph::Node Item;
-    typedef typename Graph::NodeIt ItemIt;
-
-    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
-
-    template <typename _Value>
-    class Map : public Graph::template NodeMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+
+    typedef typename GR::Node Item;
+    typedef typename GR::NodeIt ItemIt;
+
+    typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier;
+
+    template <typename V>
+    class Map : public GR::template NodeMap<V> {
+      typedef typename GR::template NodeMap<V> Parent;
+
     public:
-      typedef typename Graph::template NodeMap<_Value> Parent;
-      typedef typename Graph::template NodeMap<_Value> Type;
+      typedef typename GR::template NodeMap<V> Type;
       typedef typename Parent::Value Value;
 
-      Map(const Graph& _digraph) : Parent(_digraph) {}
-      Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
 
@@ -72,36 +74,38 @@
   };
 
-  template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct ArcNotifierIndicator {
     typedef InvalidType Type;
   };
-  template <typename Graph>
+  template <typename GR>
   struct ArcNotifierIndicator<
-    Graph,
-    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type
-  > {
-    typedef typename Graph::ArcNotifier Type;
-  };
-
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Arc> {
+    GR,
+    typename enable_if<typename GR::ArcNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::ArcNotifier Type;
+  };
+
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Arc> {
   public:
 
-    typedef _Graph Graph;
-
-    typedef typename Graph::Arc Item;
-    typedef typename Graph::ArcIt ItemIt;
-
-    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;
-
-    template <typename _Value>
-    class Map : public Graph::template ArcMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+
+    typedef typename GR::Arc Item;
+    typedef typename GR::ArcIt ItemIt;
+
+    typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier;
+
+    template <typename V>
+    class Map : public GR::template ArcMap<V> {
+      typedef typename GR::template ArcMap<V> Parent;
+
     public:
-      typedef typename Graph::template ArcMap<_Value> Parent;
-      typedef typename Graph::template ArcMap<_Value> Type;
+      typedef typename GR::template ArcMap<V> Type;
       typedef typename Parent::Value Value;
 
-      Map(const Graph& _digraph) : Parent(_digraph) {}
-      Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
     };
@@ -109,36 +113,38 @@
   };
 
-  template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct EdgeNotifierIndicator {
     typedef InvalidType Type;
   };
-  template <typename Graph>
+  template <typename GR>
   struct EdgeNotifierIndicator<
-    Graph,
-    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
-  > {
-    typedef typename Graph::EdgeNotifier Type;
-  };
-
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Edge> {
+    GR,
+    typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::EdgeNotifier Type;
+  };
+
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::Edge> {
   public:
 
-    typedef _Graph Graph;
-
-    typedef typename Graph::Edge Item;
-    typedef typename Graph::EdgeIt ItemIt;
-
-    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
-
-    template <typename _Value>
-    class Map : public Graph::template EdgeMap<_Value> {
+    typedef GR Graph;
+    typedef GR Digraph;
+
+    typedef typename GR::Edge Item;
+    typedef typename GR::EdgeIt ItemIt;
+
+    typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier;
+
+    template <typename V>
+    class Map : public GR::template EdgeMap<V> {
+      typedef typename GR::template EdgeMap<V> Parent;
+
     public:
-      typedef typename Graph::template EdgeMap<_Value> Parent;
-      typedef typename Graph::template EdgeMap<_Value> Type;
+      typedef typename GR::template EdgeMap<V> Type;
       typedef typename Parent::Value Value;
 
-      Map(const Graph& _digraph) : Parent(_digraph) {}
-      Map(const Graph& _digraph, const Value& _value)
+      Map(const GR& _digraph) : Parent(_digraph) {}
+      Map(const GR& _digraph, const Value& _value)
         : Parent(_digraph, _value) {}
     };
@@ -205,65 +211,91 @@
   // Indicators for the tags
 
-  template <typename Graph, typename Enable = void>
+  template <typename GR, typename Enable = void>
   struct NodeNumTagIndicator {
     static const bool value = false;
   };
 
-  template <typename Graph>
+  template <typename GR>
   struct NodeNumTagIndicator<
-    Graph,
-    typename enable_if<typename Graph::NodeNumTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::NodeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
+  struct ArcNumTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename GR>
+  struct ArcNumTagIndicator<
+    GR,
+    typename enable_if<typename GR::ArcNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
   struct EdgeNumTagIndicator {
     static const bool value = false;
   };
 
-  template <typename Graph>
+  template <typename GR>
   struct EdgeNumTagIndicator<
-    Graph,
-    typename enable_if<typename Graph::EdgeNumTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::EdgeNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
+  struct FindArcTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename GR>
+  struct FindArcTagIndicator<
+    GR,
+    typename enable_if<typename GR::FindArcTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
   struct FindEdgeTagIndicator {
     static const bool value = false;
   };
 
-  template <typename Graph>
+  template <typename GR>
   struct FindEdgeTagIndicator<
-    Graph,
-    typename enable_if<typename Graph::FindEdgeTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::FindEdgeTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
   struct UndirectedTagIndicator {
     static const bool value = false;
   };
 
-  template <typename Graph>
+  template <typename GR>
   struct UndirectedTagIndicator<
-    Graph,
-    typename enable_if<typename Graph::UndirectedTag, void>::type
-  > {
-    static const bool value = true;
-  };
-
-  template <typename Graph, typename Enable = void>
+    GR,
+    typename enable_if<typename GR::UndirectedTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename GR, typename Enable = void>
   struct BuildTagIndicator {
     static const bool value = false;
   };
 
-  template <typename Graph>
+  template <typename GR>
   struct BuildTagIndicator<
-    Graph,
-    typename enable_if<typename Graph::BuildTag, void>::type
+    GR,
+    typename enable_if<typename GR::BuildTag, void>::type
   > {
     static const bool value = true;
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 664)
@@ -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.
@@ -57,5 +57,5 @@
 
     // The graph type of the map.
-    typedef _Graph Graph;
+    typedef _Graph GraphType;
     // The item type of the map.
     typedef _Item Item;
@@ -73,6 +73,4 @@
     // The map type.
     typedef VectorMap Map;
-    // The base class of the map.
-    typedef typename Notifier::ObserverBase Parent;
 
     // The reference type of the map;
@@ -81,4 +79,10 @@
     typedef typename Container::const_reference ConstReference;
 
+  private:
+
+    // The base class of the map.
+    typedef typename Notifier::ObserverBase Parent;
+
+  public:
 
     // \brief Constructor to attach the new map into the notifier.
@@ -86,5 +90,5 @@
     // It constructs a map and attachs it into the notifier.
     // It adds all the items of the graph to the map.
-    VectorMap(const Graph& graph) {
+    VectorMap(const GraphType& graph) {
       Parent::attach(graph.notifier(Item()));
       container.resize(Parent::notifier()->maxId() + 1);
@@ -95,5 +99,5 @@
     // It constructs a map uses a given value to initialize the map.
     // It adds all the items of the graph to the map.
-    VectorMap(const Graph& graph, const Value& value) {
+    VectorMap(const GraphType& graph, const Value& value) {
       Parent::attach(graph.notifier(Item()));
       container.resize(Parent::notifier()->maxId() + 1, value);
@@ -125,5 +129,5 @@
     // \brief Template assign operator.
     //
-    // The given parameter should be conform to the ReadMap
+    // The given parameter should conform to the ReadMap
     // concecpt and could be indiced by the current item set of
     // the NodeMap. In this case the value for each item
@@ -170,5 +174,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 +185,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 +200,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 +208,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 +216,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 +228,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() {
Index: lemon/bits/windows.cc
===================================================================
--- lemon/bits/windows.cc	(revision 1078)
+++ lemon/bits/windows.cc	(revision 1081)
@@ -41,5 +41,7 @@
 #include <unistd.h>
 #include <ctime>
+#ifndef WIN32
 #include <sys/times.h>
+#endif
 #include <sys/time.h>
 #endif
Index: lemon/bits/windows.h
===================================================================
--- lemon/bits/windows.h	(revision 511)
+++ lemon/bits/windows.h	(revision 576)
@@ -17,6 +17,6 @@
  */
 
-#ifndef LEMON_WINDOWS_H
-#define LEMON_WINDOWS_H
+#ifndef LEMON_BITS_WINDOWS_H
+#define LEMON_BITS_WINDOWS_H
 
 #include <string>
