Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 755)
+++ lemon/Makefile.am	(revision 827)
@@ -87,5 +87,8 @@
 	lemon/graph_to_eps.h \
 	lemon/grid_graph.h \
+	lemon/hartmann_orlin.h \
+	lemon/howard.h \
 	lemon/hypercube_graph.h \
+	lemon/karp.h \
 	lemon/kary_heap.h \
 	lemon/kruskal.h \
@@ -111,4 +114,5 @@
 	lemon/smart_graph.h \
 	lemon/soplex.h \
+	lemon/static_graph.h \
 	lemon/suurballe.h \
 	lemon/time_measure.h \
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h	(revision 732)
+++ lemon/bits/graph_extender.h	(revision 825)
@@ -57,9 +57,9 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
@@ -356,13 +356,13 @@
     }
 
-    Node fromId(int id, Node) const {
+    static Node fromId(int id, Node) {
       return Parent::nodeFromId(id);
     }
 
-    Arc fromId(int id, Arc) const {
+    static Arc fromId(int id, Arc) {
       return Parent::arcFromId(id);
     }
 
-    Edge fromId(int id, Edge) const {
+    static Edge fromId(int id, Edge) {
       return Parent::edgeFromId(id);
     }
Index: lemon/cbc.cc
===================================================================
--- lemon/cbc.cc	(revision 623)
+++ lemon/cbc.cc	(revision 793)
@@ -95,4 +95,16 @@
   }
 
+  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+    return _prob->numberRows() - 1;
+  }
 
   void CbcMip::_eraseCol(int i) {
Index: lemon/cbc.h
===================================================================
--- lemon/cbc.h	(revision 623)
+++ lemon/cbc.h	(revision 793)
@@ -63,4 +63,5 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
Index: lemon/clp.cc
===================================================================
--- lemon/clp.cc	(revision 623)
+++ lemon/clp.cc	(revision 793)
@@ -79,4 +79,17 @@
   }
 
+  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
+    return _prob->numberRows() - 1;
+  }
+
 
   void ClpLp::_eraseCol(int c) {
Index: lemon/clp.h
===================================================================
--- lemon/clp.h	(revision 623)
+++ lemon/clp.h	(revision 793)
@@ -76,4 +76,5 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
Index: lemon/concepts/digraph.h
===================================================================
--- lemon/concepts/digraph.h	(revision 627)
+++ lemon/concepts/digraph.h	(revision 781)
@@ -36,44 +36,38 @@
     /// \brief Class describing the concept of directed graphs.
     ///
-    /// This class describes the \ref concept "concept" of the
-    /// immutable directed digraphs.
+    /// This class describes the common interface of all directed
+    /// graphs (digraphs).
     ///
-    /// Note that actual digraph implementation like @ref ListDigraph or
-    /// @ref SmartDigraph may have several additional functionality.
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// directed graphs should compile with this class, but it will not
+    /// run properly, of course.
+    /// An actual digraph implementation like \ref ListDigraph or
+    /// \ref SmartDigraph may have additional functionality.
     ///
-    /// \sa concept
+    /// \sa Graph
     class Digraph {
     private:
-      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
-
-      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
-      ///
-      Digraph(const Digraph &) {};
-      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
-      ///\e not allowed. Use DigraphCopy() instead.
-
-      ///Assignment of \ref Digraph "Digraph"s to another ones are
-      ///\e not allowed.  Use DigraphCopy() instead.
-
+      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
+      Digraph(const Digraph &) {}
+      /// \brief Assignment of a digraph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
       void operator=(const Digraph &) {}
+
     public:
-      ///\e
-
-      /// Defalult constructor.
-
-      /// Defalult constructor.
-      ///
+      /// Default constructor.
       Digraph() { }
-      /// Class for identifying a node of the digraph
+
+      /// The node type of the digraph
 
       /// This class identifies a node of the digraph. It also serves
       /// as a base class of the node iterators,
-      /// thus they will convert to this type.
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
@@ -83,38 +77,37 @@
         Node(const Node&) { }
 
-        /// Invalid constructor \& conversion.
-
-        /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
 
         /// Inequality operator
 
-        /// \sa operator==(Node n)
-        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of digraph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the nodes; this order has nothing to do with the iteration
+        /// ordering of the nodes.
         bool operator<(Node) const { return false; }
-
-      };
-
-      /// This iterator goes through each node.
-
-      /// This iterator goes through each node.
+      };
+
+      /// Iterator class for the nodes.
+
+      /// This iterator goes through each node of the digraph.
       /// Its usage is quite simple, for example you can count the number
-      /// of nodes in digraph \c g of type \c Digraph like this:
+      /// of nodes in a digraph \c g of type \c %Digraph like this:
       ///\code
       /// int count=0;
@@ -125,6 +118,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
@@ -133,20 +126,18 @@
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
-        /// Invalid constructor \& conversion.
-
-        /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
 
-        /// Sets the iterator to the first node of \c g.
-        ///
-        NodeIt(const Digraph&) { }
-        /// Node -> NodeIt conversion.
-
-        /// Sets the iterator to the node of \c the digraph pointed by
-        /// the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Digraph&) { }
+        /// Sets the iterator to the given node.
+
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Digraph&, const Node&) { }
         /// Next node.
@@ -158,5 +149,5 @@
 
 
-      /// Class for identifying an arc of the digraph
+      /// The arc type of the digraph
 
       /// This class identifies an arc of the digraph. It also serves
@@ -167,6 +158,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
@@ -175,32 +166,32 @@
         ///
         Arc(const Arc&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Arc n)
-        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of digraph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
       };
 
-      /// This iterator goes trough the outgoing arcs of a node.
+      /// Iterator class for the outgoing arcs of a node.
 
       /// This iterator goes trough the \e outgoing arcs of a certain node
@@ -208,16 +199,15 @@
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
-      /// in digraph \c g of type \c Digraph as follows.
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
-      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class OutArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
@@ -226,21 +216,20 @@
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first outgoing arc.
-
-        /// This constructor sets the iterator to the first outgoing arc of
-        /// the node.
+        /// Sets the iterator to the first outgoing arc.
+
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Digraph&, const Node&) { }
-        /// Arc -> OutArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         OutArcIt(const Digraph&, const Arc&) { }
-        ///Next outgoing arc
+        /// Next outgoing arc
 
         /// Assign the iterator to the next
@@ -249,22 +238,21 @@
       };
 
-      /// This iterator goes trough the incoming arcs of a node.
+      /// Iterator class for the incoming arcs of a node.
 
       /// This iterator goes trough the \e incoming arcs of a certain node
       /// of a digraph.
       /// Its usage is quite simple, for example you can count the number
-      /// of outgoing arcs of a node \c n
-      /// in digraph \c g of type \c Digraph as follows.
+      /// of incoming arcs of a node \c n
+      /// in a digraph \c g of type \c %Digraph as follows.
       ///\code
       /// int count=0;
-      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class InArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
@@ -273,34 +261,34 @@
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
-        /// This constructor sets the iterator to first incoming arc.
-
-        /// This constructor set the iterator to the first incoming arc of
-        /// the node.
+        /// Sets the iterator to the first incoming arc.
+
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Digraph&, const Node&) { }
-        /// Arc -> InArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         InArcIt(const Digraph&, const Arc&) { }
         /// Next incoming arc
 
-        /// Assign the iterator to the next inarc of the corresponding node.
-        ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
-      /// This iterator goes through each arc.
-
-      /// This iterator goes through each arc of a digraph.
+
+      /// Iterator class for the arcs.
+
+      /// This iterator goes through each arc of the digraph.
       /// Its usage is quite simple, for example you can count the number
-      /// of arcs in a digraph \c g of type \c Digraph as follows:
+      /// of arcs in a digraph \c g of type \c %Digraph as follows:
       ///\code
       /// int count=0;
-      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
@@ -308,6 +296,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
@@ -316,56 +304,66 @@
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first arc.
-
-        /// This constructor sets the iterator to the first arc of \c g.
-        ///@param g the digraph
-        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
-        /// Arc -> ArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+
+        /// Sets the iterator to the first arc of the given digraph.
+        ///
+        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given digraph.
+        ///
         ArcIt(const Digraph&, const Arc&) { }
-        ///Next arc
+        /// Next arc
 
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
-      ///Gives back the target node of an arc.
-
-      ///Gives back the target node of an arc.
-      ///
+
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
+      Node source(Arc) const { return INVALID; }
+
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
-      ///Gives back the source node of an arc.
-
-      ///Gives back the source node of an arc.
-      ///
-      Node source(Arc) const { return INVALID; }
-
-      /// \brief Returns the ID of the node.
+
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
 
-      /// \brief Returns the ID of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
 
-      /// \brief Returns the node with the given ID.
-      ///
-      /// \pre The argument should be a valid node ID in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the digraph.
       Node nodeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the arc with the given ID.
-      ///
-      /// \pre The argument should be a valid arc ID in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the digraph.
       Arc arcFromId(int) const { return INVALID; }
 
-      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
 
@@ -393,43 +391,44 @@
       int maxId(Arc) const { return -1; }
 
+      /// \brief The opposite node on the arc.
+      ///
+      /// Returns the opposite node on the given arc.
+      Node oppositeNode(Node, Arc) const { return INVALID; }
+
       /// \brief The base node of the iterator.
       ///
-      /// Gives back the base node of the iterator.
-      /// It is always the target of the pointed arc.
-      Node baseNode(const InArcIt&) const { return INVALID; }
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
 
       /// \brief The running node of the iterator.
       ///
-      /// Gives back the running node of the iterator.
-      /// It is always the source of the pointed arc.
-      Node runningNode(const InArcIt&) const { return INVALID; }
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
 
       /// \brief The base node of the iterator.
       ///
-      /// Gives back the base node of the iterator.
-      /// It is always the source of the pointed arc.
-      Node baseNode(const OutArcIt&) const { return INVALID; }
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
 
       /// \brief The running node of the iterator.
       ///
-      /// Gives back the running node of the iterator.
-      /// It is always the target of the pointed arc.
-      Node runningNode(const OutArcIt&) const { return INVALID; }
-
-      /// \brief The opposite node on the given arc.
-      ///
-      /// Gives back the opposite node on the given arc.
-      Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
-
-      /// \brief Reference map of the nodes to type \c T.
-      ///
-      /// Reference map of the nodes to type \c T.
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
+
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
       public:
 
-        ///\e
-        NodeMap(const Digraph&) { }
-        ///\e
+        /// Constructor
+        explicit NodeMap(const Digraph&) { }
+        /// Constructor with given initial value
         NodeMap(const Digraph&, T) { }
 
@@ -446,15 +445,17 @@
       };
 
-      /// \brief Reference map of the arcs to type \c T.
-      ///
-      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
       public:
 
-        ///\e
-        ArcMap(const Digraph&) { }
-        ///\e
+        /// Constructor
+        explicit ArcMap(const Digraph&) { }
+        /// Constructor with given initial value
         ArcMap(const Digraph&, T) { }
+
       private:
         ///Copy constructor
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h	(revision 704)
+++ lemon/concepts/graph.h	(revision 781)
@@ -19,5 +19,5 @@
 ///\ingroup graph_concepts
 ///\file
-///\brief The concept of Undirected Graphs.
+///\brief The concept of undirected graphs.
 
 #ifndef LEMON_CONCEPTS_GRAPH_H
@@ -25,4 +25,6 @@
 
 #include <lemon/concepts/graph_components.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/concept_check.h>
 #include <lemon/core.h>
 
@@ -32,61 +34,72 @@
     /// \ingroup graph_concepts
     ///
-    /// \brief Class describing the concept of Undirected Graphs.
+    /// \brief Class describing the concept of undirected graphs.
     ///
-    /// This class describes the common interface of all Undirected
-    /// Graphs.
+    /// This class describes the common interface of all undirected
+    /// graphs.
     ///
-    /// As all concept describing classes it provides only interface
-    /// without any sensible implementation. So any algorithm for
-    /// undirected graph should compile with this class, but it will not
+    /// Like all concept classes, it only provides an interface
+    /// without any sensible implementation. So any general algorithm for
+    /// undirected graphs should compile with this class, but it will not
     /// run properly, of course.
+    /// An actual graph implementation like \ref ListGraph or
+    /// \ref SmartGraph may have additional functionality.    
     ///
-    /// The LEMON undirected graphs also fulfill the concept of
-    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
-    /// Concept"). Each edges can be seen as two opposite
-    /// directed arc and consequently the undirected graph can be
-    /// seen as the direceted graph of these directed arcs. The
-    /// Graph has the Edge inner class for the edges and
-    /// the Arc type for the directed arcs. The Arc type is
-    /// convertible to Edge or inherited from it so from a directed
-    /// arc we can get the represented edge.
+    /// The undirected graphs also fulfill the concept of \ref Digraph
+    /// "directed graphs", since each edge can also be regarded as two
+    /// oppositely directed arcs.
+    /// Undirected graphs provide an Edge type for the undirected edges and
+    /// an Arc type for the directed arcs. The Arc type is convertible to
+    /// Edge or inherited from it, i.e. the corresponding edge can be
+    /// obtained from an arc.
+    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
+    /// and ArcMap classes can be used for the arcs (just like in digraphs).
+    /// Both InArcIt and OutArcIt iterates on the same edges but with
+    /// opposite direction. IncEdgeIt also iterates on the same edges
+    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
+    /// only to Edge.
     ///
-    /// In the sense of the LEMON each edge has a default
-    /// direction (it should be in every computer implementation,
-    /// because the order of edge's nodes defines an
-    /// orientation). With the default orientation we can define that
-    /// the directed arc is forward or backward directed. With the \c
-    /// direction() and \c direct() function we can get the direction
-    /// of the directed arc and we can direct an edge.
+    /// In LEMON, each undirected edge has an inherent orientation.
+    /// Thus it can defined if an arc is forward or backward oriented in
+    /// an undirected graph with respect to this default oriantation of
+    /// the represented edge.
+    /// With the direction() and direct() functions the direction
+    /// of an arc can be obtained and set, respectively.
     ///
-    /// The EdgeIt is an iterator for the edges. We can use
-    /// the EdgeMap to map values for the edges. The InArcIt and
-    /// OutArcIt iterates on the same edges but with opposite
-    /// direction. The IncEdgeIt iterates also on the same edges
-    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
-    /// to Edge.
+    /// Only nodes and edges can be added to or removed from an undirected
+    /// graph and the corresponding arcs are added or removed automatically.
+    ///
+    /// \sa Digraph
     class Graph {
+    private:
+      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
+      Graph(const Graph&) {}
+      /// \brief Assignment of a graph to another one is \e not allowed.
+      /// Use DigraphCopy instead.
+      void operator=(const Graph&) {}
+
     public:
-      /// \brief The undirected graph should be tagged by the
-      /// UndirectedTag.
-      ///
-      /// The undirected graph should be tagged by the UndirectedTag. This
-      /// tag helps the enable_if technics to make compile time
+      /// Default constructor.
+      Graph() {}
+
+      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
+      ///
+      /// Undirected graphs should be tagged with \c UndirectedTag.
+      /// 
+      /// This tag helps the \c enable_if technics to make compile time
       /// specializations for undirected graphs.
       typedef True UndirectedTag;
 
-      /// \brief The base type of node iterators,
-      /// or in other words, the trivial node iterator.
-      ///
-      /// This is the base type of each node iterator,
-      /// thus each kind of node iterator converts to this.
-      /// More precisely each kind of node iterator should be inherited
-      /// from the trivial node iterator.
+      /// The node type of the graph
+
+      /// This class identifies a node of the graph. It also serves
+      /// as a base class of the node iterators,
+      /// thus they convert to this type.
       class Node {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Node() { }
         /// Copy constructor.
@@ -96,27 +109,27 @@
         Node(const Node&) { }
 
-        /// Invalid constructor \& conversion.
-
-        /// This constructor initializes the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
         /// \sa Invalid for more details.
         Node(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Node) const { return true; }
 
         /// Inequality operator
 
-        /// \sa operator==(Node n)
-        ///
+        /// Inequality operator.
         bool operator!=(Node) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
         /// the items; this order has nothing to do with the iteration
         /// ordering of the items.
@@ -125,9 +138,9 @@
       };
 
-      /// This iterator goes through each node.
-
-      /// This iterator goes through each node.
+      /// Iterator class for the nodes.
+
+      /// This iterator goes through each node of the graph.
       /// Its usage is quite simple, for example you can count the number
-      /// of nodes in graph \c g of type \c Graph like this:
+      /// of nodes in a graph \c g of type \c %Graph like this:
       ///\code
       /// int count=0;
@@ -138,6 +151,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         NodeIt() { }
         /// Copy constructor.
@@ -146,20 +159,18 @@
         ///
         NodeIt(const NodeIt& n) : Node(n) { }
-        /// Invalid constructor \& conversion.
-
-        /// Initialize the iterator to be invalid.
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
         /// \sa Invalid for more details.
         NodeIt(Invalid) { }
         /// Sets the iterator to the first node.
 
-        /// Sets the iterator to the first node of \c g.
-        ///
-        NodeIt(const Graph&) { }
-        /// Node -> NodeIt conversion.
-
-        /// Sets the iterator to the node of \c the graph pointed by
-        /// the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first node of the given digraph.
+        ///
+        explicit NodeIt(const Graph&) { }
+        /// Sets the iterator to the given node.
+
+        /// Sets the iterator to the given node of the given digraph.
+        ///
         NodeIt(const Graph&, const Node&) { }
         /// Next node.
@@ -171,14 +182,15 @@
 
 
-      /// The base type of the edge iterators.
-
-      /// The base type of the edge iterators.
-      ///
+      /// The edge type of the graph
+
+      /// This class identifies an edge of the graph. It also serves
+      /// as a base class of the edge iterators,
+      /// thus they will convert to this type.
       class Edge {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Edge() { }
         /// Copy constructor.
@@ -187,36 +199,36 @@
         ///
         Edge(const Edge&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Edge(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Edge) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Edge n)
-        ///
+        /// Inequality operator.
         bool operator!=(Edge) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the edges; this order has nothing to do with the iteration
+        /// ordering of the edges.
         bool operator<(Edge) const { return false; }
       };
 
-      /// This iterator goes through each edge.
-
-      /// This iterator goes through each edge of a graph.
+      /// Iterator class for the edges.
+
+      /// This iterator goes through each edge of the graph.
       /// Its usage is quite simple, for example you can count the number
-      /// of edges in a graph \c g of type \c Graph as follows:
+      /// of edges in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
@@ -227,6 +239,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         EdgeIt() { }
         /// Copy constructor.
@@ -235,36 +247,33 @@
         ///
         EdgeIt(const EdgeIt& e) : Edge(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         EdgeIt(Invalid) { }
-        /// This constructor sets the iterator to the first edge.
-
-        /// This constructor sets the iterator to the first edge.
-        EdgeIt(const Graph&) { }
-        /// Edge -> EdgeIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the edge-set, the iteration order is the
-        /// same.
+        /// Sets the iterator to the first edge.
+
+        /// Sets the iterator to the first edge of the given graph.
+        ///
+        explicit EdgeIt(const Graph&) { }
+        /// Sets the iterator to the given edge.
+
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         EdgeIt(const Graph&, const Edge&) { }
         /// Next edge
 
         /// Assign the iterator to the next edge.
+        ///
         EdgeIt& operator++() { return *this; }
       };
 
-      /// \brief This iterator goes trough the incident undirected
-      /// arcs of a node.
-      ///
-      /// This iterator goes trough the incident edges
-      /// of a certain node of a graph. You should assume that the
-      /// loop arcs will be iterated twice.
-      ///
+      /// Iterator class for the incident edges of a node.
+
+      /// This iterator goes trough the incident undirected edges
+      /// of a certain node of a graph.
       /// Its usage is quite simple, for example you can compute the
-      /// degree (i.e. count the number of incident arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// degree (i.e. the number of incident edges) of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///
       ///\code
@@ -272,10 +281,12 @@
       /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
       ///\endcode
+      ///
+      /// \warning Loop edges will be iterated twice.
       class IncEdgeIt : public Edge {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         IncEdgeIt() { }
         /// Copy constructor.
@@ -284,38 +295,37 @@
         ///
         IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         IncEdgeIt(Invalid) { }
-        /// This constructor sets the iterator to first incident arc.
-
-        /// This constructor set the iterator to the first incident arc of
-        /// the node.
+        /// Sets the iterator to the first incident edge.
+
+        /// Sets the iterator to the first incident edge of the given node.
+        ///
         IncEdgeIt(const Graph&, const Node&) { }
-        /// Edge -> IncEdgeIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given edge.
+
+        /// Sets the iterator to the given edge of the given graph.
+        ///
         IncEdgeIt(const Graph&, const Edge&) { }
-        /// Next incident arc
-
-        /// Assign the iterator to the next incident arc
+        /// Next incident edge
+
+        /// Assign the iterator to the next incident edge
         /// of the corresponding node.
         IncEdgeIt& operator++() { return *this; }
       };
 
-      /// The directed arc type.
-
-      /// The directed arc type. It can be converted to the
-      /// edge or it should be inherited from the undirected
-      /// edge.
+      /// The arc type of the graph
+
+      /// This class identifies a directed arc of the graph. It also serves
+      /// as a base class of the arc iterators,
+      /// thus they will convert to this type.
       class Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the object to an undefined value.
         Arc() { }
         /// Copy constructor.
@@ -324,41 +334,45 @@
         ///
         Arc(const Arc&) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the object to be invalid.
+        /// \sa Invalid for more details.
         Arc(Invalid) { }
         /// Equality operator
 
+        /// Equality operator.
+        ///
         /// Two iterators are equal if and only if they point to the
-        /// same object or both are invalid.
+        /// same object or both are \c INVALID.
         bool operator==(Arc) const { return true; }
         /// Inequality operator
 
-        /// \sa operator==(Arc n)
-        ///
+        /// Inequality operator.
         bool operator!=(Arc) const { return true; }
 
         /// Artificial ordering operator.
 
-        /// To allow the use of graph descriptors as key type in std::map or
-        /// similar associative container we require this.
-        ///
-        /// \note This operator only have to define some strict ordering of
-        /// the items; this order has nothing to do with the iteration
-        /// ordering of the items.
+        /// Artificial ordering operator.
+        ///
+        /// \note This operator only has to define some strict ordering of
+        /// the arcs; this order has nothing to do with the iteration
+        /// ordering of the arcs.
         bool operator<(Arc) const { return false; }
 
-        /// Converison to Edge
+        /// Converison to \c Edge
+        
+        /// Converison to \c Edge.
+        ///
         operator Edge() const { return Edge(); }
       };
-      /// This iterator goes through each directed arc.
-
-      /// This iterator goes through each arc of a graph.
+
+      /// Iterator class for the arcs.
+
+      /// This iterator goes through each directed arc of the graph.
       /// Its usage is quite simple, for example you can count the number
-      /// of arcs in a graph \c g of type \c Graph as follows:
+      /// of arcs in a graph \c g of type \c %Graph as follows:
       ///\code
       /// int count=0;
-      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
+      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
       ///\endcode
       class ArcIt : public Arc {
@@ -366,6 +380,6 @@
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         ArcIt() { }
         /// Copy constructor.
@@ -374,44 +388,43 @@
         ///
         ArcIt(const ArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         ArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first arc.
-
-        /// This constructor sets the iterator to the first arc of \c g.
-        ///@param g the graph
-        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
-        /// Arc -> ArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the first arc.
+
+        /// Sets the iterator to the first arc of the given graph.
+        ///
+        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         ArcIt(const Graph&, const Arc&) { }
-        ///Next arc
+        /// Next arc
 
         /// Assign the iterator to the next arc.
+        ///
         ArcIt& operator++() { return *this; }
       };
 
-      /// This iterator goes trough the outgoing directed arcs of a node.
-
-      /// This iterator goes trough the \e outgoing arcs of a certain node
-      /// of a graph.
+      /// Iterator class for the outgoing arcs of a node.
+
+      /// This iterator goes trough the \e outgoing directed arcs of a
+      /// certain node of a graph.
       /// Its usage is quite simple, for example you can count the number
       /// of outgoing arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
-      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class OutArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         OutArcIt() { }
         /// Copy constructor.
@@ -420,26 +433,23 @@
         ///
         OutArcIt(const OutArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         OutArcIt(Invalid) { }
-        /// This constructor sets the iterator to the first outgoing arc.
-
-        /// This constructor sets the iterator to the first outgoing arc of
-        /// the node.
-        ///@param n the node
-        ///@param g the graph
+        /// Sets the iterator to the first outgoing arc.
+
+        /// Sets the iterator to the first outgoing arc of the given node.
+        ///
         OutArcIt(const Graph& n, const Node& g) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
         }
-        /// Arc -> OutArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         OutArcIt(const Graph&, const Arc&) { }
-        ///Next outgoing arc
+        /// Next outgoing arc
 
         /// Assign the iterator to the next
@@ -448,22 +458,21 @@
       };
 
-      /// This iterator goes trough the incoming directed arcs of a node.
-
-      /// This iterator goes trough the \e incoming arcs of a certain node
-      /// of a graph.
+      /// Iterator class for the incoming arcs of a node.
+
+      /// This iterator goes trough the \e incoming directed arcs of a
+      /// certain node of a graph.
       /// Its usage is quite simple, for example you can count the number
-      /// of outgoing arcs of a node \c n
-      /// in graph \c g of type \c Graph as follows.
+      /// of incoming arcs of a node \c n
+      /// in a graph \c g of type \c %Graph as follows.
       ///\code
       /// int count=0;
-      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
+      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
       ///\endcode
-
       class InArcIt : public Arc {
       public:
         /// Default constructor
 
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
+        /// Default constructor.
+        /// \warning It sets the iterator to an undefined value.
         InArcIt() { }
         /// Copy constructor.
@@ -472,35 +481,33 @@
         ///
         InArcIt(const InArcIt& e) : Arc(e) { }
-        /// Initialize the iterator to be invalid.
-
-        /// Initialize the iterator to be invalid.
-        ///
+        /// %Invalid constructor \& conversion.
+
+        /// Initializes the iterator to be invalid.
+        /// \sa Invalid for more details.
         InArcIt(Invalid) { }
-        /// This constructor sets the iterator to first incoming arc.
-
-        /// This constructor set the iterator to the first incoming arc of
-        /// the node.
-        ///@param n the node
-        ///@param g the graph
+        /// Sets the iterator to the first incoming arc.
+
+        /// Sets the iterator to the first incoming arc of the given node.
+        ///
         InArcIt(const Graph& g, const Node& n) {
           ignore_unused_variable_warning(n);
           ignore_unused_variable_warning(g);
         }
-        /// Arc -> InArcIt conversion
-
-        /// Sets the iterator to the value of the trivial iterator \c e.
-        /// This feature necessitates that each time we
-        /// iterate the arc-set, the iteration order is the same.
+        /// Sets the iterator to the given arc.
+
+        /// Sets the iterator to the given arc of the given graph.
+        ///
         InArcIt(const Graph&, const Arc&) { }
         /// Next incoming arc
 
-        /// Assign the iterator to the next inarc of the corresponding node.
-        ///
+        /// Assign the iterator to the next
+        /// incoming arc of the corresponding node.
         InArcIt& operator++() { return *this; }
       };
 
-      /// \brief Reference map of the nodes to type \c T.
-      ///
-      /// Reference map of the nodes to type \c T.
+      /// \brief Standard graph map type for the nodes.
+      ///
+      /// Standard graph map type for the nodes.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class NodeMap : public ReferenceMap<Node, T, T&, const T&>
@@ -508,7 +515,7 @@
       public:
 
-        ///\e
-        NodeMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit NodeMap(const Graph&) { }
+        /// Constructor with given initial value
         NodeMap(const Graph&, T) { }
 
@@ -525,7 +532,8 @@
       };
 
-      /// \brief Reference map of the arcs to type \c T.
-      ///
-      /// Reference map of the arcs to type \c T.
+      /// \brief Standard graph map type for the arcs.
+      ///
+      /// Standard graph map type for the arcs.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
@@ -533,8 +541,9 @@
       public:
 
-        ///\e
-        ArcMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit ArcMap(const Graph&) { }
+        /// Constructor with given initial value
         ArcMap(const Graph&, T) { }
+
       private:
         ///Copy constructor
@@ -549,7 +558,8 @@
       };
 
-      /// Reference map of the edges to type \c T.
-
-      /// Reference map of the edges to type \c T.
+      /// \brief Standard graph map type for the edges.
+      ///
+      /// Standard graph map type for the edges.
+      /// It conforms to the ReferenceMap concept.
       template<class T>
       class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
@@ -557,8 +567,9 @@
       public:
 
-        ///\e
-        EdgeMap(const Graph&) { }
-        ///\e
+        /// Constructor
+        explicit EdgeMap(const Graph&) { }
+        /// Constructor with given initial value
         EdgeMap(const Graph&, T) { }
+
       private:
         ///Copy constructor
@@ -573,104 +584,121 @@
       };
 
-      /// \brief Direct the given edge.
-      ///
-      /// Direct the given edge. The returned arc source
-      /// will be the given node.
-      Arc direct(const Edge&, const Node&) const {
-        return INVALID;
-      }
-
-      /// \brief Direct the given edge.
-      ///
-      /// Direct the given edge. The returned arc
-      /// represents the given edge and the direction comes
-      /// from the bool parameter. The source of the edge and
-      /// the directed arc is the same when the given bool is true.
-      Arc direct(const Edge&, bool) const {
-        return INVALID;
-      }
-
-      /// \brief Returns true if the arc has default orientation.
-      ///
-      /// Returns whether the given directed arc is same orientation as
-      /// the corresponding edge's default orientation.
-      bool direction(Arc) const { return true; }
-
-      /// \brief Returns the opposite directed arc.
-      ///
-      /// Returns the opposite directed arc.
-      Arc oppositeArc(Arc) const { return INVALID; }
-
-      /// \brief Opposite node on an arc
-      ///
-      /// \return The opposite of the given node on the given edge.
-      Node oppositeNode(Node, Edge) const { return INVALID; }
-
-      /// \brief First node of the edge.
-      ///
-      /// \return The first node of the given edge.
-      ///
-      /// Naturally edges don't have direction and thus
-      /// don't have source and target node. However we use \c u() and \c v()
-      /// methods to query the two nodes of the arc. The direction of the
-      /// arc which arises this way is called the inherent direction of the
-      /// edge, and is used to define the "default" direction
-      /// of the directed versions of the arcs.
+      /// \brief The first node of the edge.
+      ///
+      /// Returns the first node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa v()
       /// \sa direction()
       Node u(Edge) const { return INVALID; }
 
-      /// \brief Second node of the edge.
-      ///
-      /// \return The second node of the given edge.
-      ///
-      /// Naturally edges don't have direction and thus
-      /// don't have source and target node. However we use \c u() and \c v()
-      /// methods to query the two nodes of the arc. The direction of the
-      /// arc which arises this way is called the inherent direction of the
-      /// edge, and is used to define the "default" direction
-      /// of the directed versions of the arcs.
+      /// \brief The second node of the edge.
+      ///
+      /// Returns the second node of the given edge.
+      ///
+      /// Edges don't have source and target nodes, however methods
+      /// u() and v() are used to query the two end-nodes of an edge.
+      /// The orientation of an edge that arises this way is called
+      /// the inherent direction, it is used to define the default
+      /// direction for the corresponding arcs.
       /// \sa u()
       /// \sa direction()
       Node v(Edge) const { return INVALID; }
 
-      /// \brief Source node of the directed arc.
+      /// \brief The source node of the arc.
+      ///
+      /// Returns the source node of the given arc.
       Node source(Arc) const { return INVALID; }
 
-      /// \brief Target node of the directed arc.
+      /// \brief The target node of the arc.
+      ///
+      /// Returns the target node of the given arc.
       Node target(Arc) const { return INVALID; }
 
-      /// \brief Returns the id of the node.
+      /// \brief The ID of the node.
+      ///
+      /// Returns the ID of the given node.
       int id(Node) const { return -1; }
 
-      /// \brief Returns the id of the edge.
+      /// \brief The ID of the edge.
+      ///
+      /// Returns the ID of the given edge.
       int id(Edge) const { return -1; }
 
-      /// \brief Returns the id of the arc.
+      /// \brief The ID of the arc.
+      ///
+      /// Returns the ID of the given arc.
       int id(Arc) const { return -1; }
 
-      /// \brief Returns the node with the given id.
-      ///
-      /// \pre The argument should be a valid node id in the graph.
+      /// \brief The node with the given ID.
+      ///
+      /// Returns the node with the given ID.
+      /// \pre The argument should be a valid node ID in the graph.
       Node nodeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the edge with the given id.
-      ///
-      /// \pre The argument should be a valid edge id in the graph.
+      /// \brief The edge with the given ID.
+      ///
+      /// Returns the edge with the given ID.
+      /// \pre The argument should be a valid edge ID in the graph.
       Edge edgeFromId(int) const { return INVALID; }
 
-      /// \brief Returns the arc with the given id.
-      ///
-      /// \pre The argument should be a valid arc id in the graph.
+      /// \brief The arc with the given ID.
+      ///
+      /// Returns the arc with the given ID.
+      /// \pre The argument should be a valid arc ID in the graph.
       Arc arcFromId(int) const { return INVALID; }
 
-      /// \brief Returns an upper bound on the node IDs.
+      /// \brief An upper bound on the node IDs.
+      ///
+      /// Returns an upper bound on the node IDs.
       int maxNodeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the edge IDs.
+      /// \brief An upper bound on the edge IDs.
+      ///
+      /// Returns an upper bound on the edge IDs.
       int maxEdgeId() const { return -1; }
 
-      /// \brief Returns an upper bound on the arc IDs.
+      /// \brief An upper bound on the arc IDs.
+      ///
+      /// Returns an upper bound on the arc IDs.
       int maxArcId() const { return -1; }
+
+      /// \brief The direction of the arc.
+      ///
+      /// Returns \c true if the direction of the given arc is the same as
+      /// the inherent orientation of the represented edge.
+      bool direction(Arc) const { return true; }
+
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc
+      /// represents the given edge and its direction comes
+      /// from the bool parameter. If it is \c true, then the direction
+      /// of the arc is the same as the inherent orientation of the edge.
+      Arc direct(Edge, bool) const {
+        return INVALID;
+      }
+
+      /// \brief Direct the edge.
+      ///
+      /// Direct the given edge. The returned arc represents the given
+      /// edge and its source node is the given node.
+      Arc direct(Edge, Node) const {
+        return INVALID;
+      }
+
+      /// \brief The oppositely directed arc.
+      ///
+      /// Returns the oppositely directed arc representing the same edge.
+      Arc oppositeArc(Arc) const { return INVALID; }
+
+      /// \brief The opposite node on the edge.
+      ///
+      /// Returns the opposite node on the given edge.
+      Node oppositeNode(Node, Edge) const { return INVALID; }
 
       void first(Node&) const {}
@@ -706,45 +734,37 @@
       int maxId(Arc) const { return -1; }
 
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node (the source in this case) of the iterator
-      Node baseNode(OutArcIt e) const {
-        return source(e);
-      }
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node (the target in this case) of the
-      /// iterator
-      Node runningNode(OutArcIt e) const {
-        return target(e);
-      }
-
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node (the target in this case) of the iterator
-      Node baseNode(InArcIt e) const {
-        return target(e);
-      }
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node (the source in this case) of the
-      /// iterator
-      Node runningNode(InArcIt e) const {
-        return source(e);
-      }
-
-      /// \brief Base node of the iterator
-      ///
-      /// Returns the base node of the iterator
-      Node baseNode(IncEdgeIt) const {
-        return INVALID;
-      }
-
-      /// \brief Running node of the iterator
-      ///
-      /// Returns the running node of the iterator
-      Node runningNode(IncEdgeIt) const {
-        return INVALID;
-      }
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incident edge iterator.
+      Node baseNode(IncEdgeIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incident edge iterator.
+      Node runningNode(IncEdgeIt) const { return INVALID; }
+
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given outgoing arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node baseNode(OutArcIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given outgoing arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node runningNode(OutArcIt) const { return INVALID; }
+
+      /// \brief The base node of the iterator.
+      ///
+      /// Returns the base node of the given incomming arc iterator
+      /// (i.e. the target node of the corresponding arc).
+      Node baseNode(InArcIt) const { return INVALID; }
+
+      /// \brief The running node of the iterator.
+      ///
+      /// Returns the running node of the given incomming arc iterator
+      /// (i.e. the source node of the corresponding arc).
+      Node runningNode(InArcIt) const { return INVALID; }
 
       template <typename _Graph>
Index: lemon/concepts/graph_components.h
===================================================================
--- lemon/concepts/graph_components.h	(revision 713)
+++ lemon/concepts/graph_components.h	(revision 781)
@@ -93,5 +93,5 @@
       /// associative containers (e.g. \c std::map).
       ///
-      /// \note This operator only have to define some strict ordering of
+      /// \note This operator only has to define some strict ordering of
       /// the items; this order has nothing to do with the iteration
       /// ordering of the items.
Index: lemon/cplex.cc
===================================================================
--- lemon/cplex.cc	(revision 623)
+++ lemon/cplex.cc	(revision 793)
@@ -112,4 +112,37 @@
   }
 
+  int CplexBase::_addRow(Value lb, ExprIterator b, 
+                         ExprIterator e, Value ub) {
+    int i = CPXgetnumrows(cplexEnv(), _prob);
+    if (lb == -INF) {
+      const char s = 'L';
+      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
+    } else if (ub == INF) {
+      const char s = 'G';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+    } else if (lb == ub){
+      const char s = 'E';
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
+    } else {
+      const char s = 'R';
+      double len = ub - lb;
+      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
+    }
+
+    std::vector<int> indices;
+    std::vector<int> rowlist;
+    std::vector<Value> values;
+
+    for(ExprIterator it=b; it!=e; ++it) {
+      indices.push_back(it->first);
+      values.push_back(it->second);
+      rowlist.push_back(i);
+    }
+
+    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
+                   &rowlist.front(), &indices.front(), &values.front());
+
+    return i;
+  }
 
   void CplexBase::_eraseCol(int i) {
Index: lemon/cplex.h
===================================================================
--- lemon/cplex.h	(revision 623)
+++ lemon/cplex.h	(revision 793)
@@ -94,4 +94,5 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
Index: lemon/edge_set.h
===================================================================
--- lemon/edge_set.h	(revision 717)
+++ lemon/edge_set.h	(revision 825)
@@ -868,5 +868,5 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -1174,5 +1174,5 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc.id;
     }
@@ -1182,5 +1182,5 @@
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc.id;
     }
Index: lemon/full_graph.h
===================================================================
--- lemon/full_graph.h	(revision 664)
+++ lemon/full_graph.h	(revision 827)
@@ -25,5 +25,5 @@
 ///\ingroup graphs
 ///\file
-///\brief FullGraph and FullDigraph classes.
+///\brief FullDigraph and FullGraph classes.
 
 namespace lemon {
@@ -52,5 +52,5 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Arc arc(const Node& s, const Node& t) const {
@@ -149,22 +149,24 @@
   /// \ingroup graphs
   ///
-  /// \brief A full digraph class.
-  ///
-  /// This is a simple and fast directed full graph implementation.
-  /// From each node go arcs to each node (including the source node),
-  /// therefore the number of the arcs in the digraph is the square of
-  /// the node number. This digraph type is completely static, so you
-  /// can neither add nor delete either arcs or nodes, and it needs
-  /// constant space in memory.
-  ///
-  /// This class fully conforms to the \ref concepts::Digraph
-  /// "Digraph concept".
-  ///
-  /// The \c FullDigraph and \c FullGraph classes are very similar,
+  /// \brief A directed full graph class.
+  ///
+  /// FullDigraph is a simple and fast implmenetation of directed full
+  /// (complete) graphs. It contains an arc from each node to each node
+  /// (including a loop for each node), therefore the number of arcs
+  /// is the square of the number of nodes.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or arcs, however
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// \note FullDigraph and FullGraph classes are very similar,
   /// but there are two differences. While this class conforms only
-  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
-  /// class conforms to the \ref concepts::Graph "Graph" concept,
-  /// moreover \c FullGraph does not contain a loop arc for each
-  /// node as \c FullDigraph does.
+  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
+  /// conforms to the \ref concepts::Graph "Graph" concept,
+  /// moreover FullGraph does not contain a loop for each
+  /// node as this class does.
   ///
   /// \sa FullGraph
@@ -174,5 +176,7 @@
   public:
 
-    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and arcs will be zero.
     FullDigraph() { construct(0); }
 
@@ -185,6 +189,6 @@
     /// \brief Resizes the digraph
     ///
-    /// Resizes the digraph. The function will fully destroy and
-    /// rebuild the digraph. This cause that the maps of the digraph will
+    /// This function resizes the digraph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the digraph will be
     /// reallocated automatically and the previous values will be lost.
     void resize(int n) {
@@ -198,7 +202,7 @@
     /// \brief Returns the node with the given index.
     ///
-    /// Returns the node with the given index. Since it is a static
-    /// digraph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
+    /// Returns the node with the given index. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -206,14 +210,14 @@
     /// \brief Returns the index of the given node.
     ///
-    /// Returns the index of the given node. Since it is a static
-    /// digraph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
-    /// \sa operator()
-    int index(const Node& node) const { return Parent::index(node); }
+    /// Returns the index of the given node. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// \sa operator()()
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.
     ///
     /// Returns the arc connecting the given nodes.
-    Arc arc(const Node& u, const Node& v) const {
+    Arc arc(Node u, Node v) const {
       return Parent::arc(u, v);
     }
@@ -284,5 +288,5 @@
 
     Node operator()(int ix) const { return Node(ix); }
-    int index(const Node& node) const { return node._id; }
+    static int index(const Node& node) { return node._id; }
 
     Edge edge(const Node& u, const Node& v) const {
@@ -521,19 +525,21 @@
   /// \brief An undirected full graph class.
   ///
-  /// This is a simple and fast undirected full graph
-  /// implementation. From each node go edge to each other node,
-  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
-  /// This graph type is completely static, so you can neither
-  /// add nor delete either edges or nodes, and it needs constant
-  /// space in memory.
-  ///
-  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
-  ///
-  /// The \c FullGraph and \c FullDigraph classes are very similar,
-  /// but there are two differences. While the \c FullDigraph class
+  /// FullGraph is a simple and fast implmenetation of undirected full
+  /// (complete) graphs. It contains an edge between every distinct pair
+  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// \note FullDigraph and FullGraph classes are very similar,
+  /// but there are two differences. While FullDigraph
   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   /// this class conforms to the \ref concepts::Graph "Graph" concept,
-  /// moreover \c FullGraph does not contain a loop arc for each
-  /// node as \c FullDigraph does.
+  /// moreover this class does not contain a loop for each
+  /// node as FullDigraph does.
   ///
   /// \sa FullDigraph
@@ -543,5 +549,7 @@
   public:
 
-    /// \brief Constructor
+    /// \brief Default constructor.
+    ///
+    /// Default constructor. The number of nodes and edges will be zero.
     FullGraph() { construct(0); }
 
@@ -554,6 +562,6 @@
     /// \brief Resizes the graph
     ///
-    /// Resizes the graph. The function will fully destroy and
-    /// rebuild the graph. This cause that the maps of the graph will
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
     /// reallocated automatically and the previous values will be lost.
     void resize(int n) {
@@ -569,7 +577,7 @@
     /// \brief Returns the node with the given index.
     ///
-    /// Returns the node with the given index. Since it is a static
-    /// graph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
+    /// Returns the node with the given index. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
     /// \sa index()
     Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -577,21 +585,21 @@
     /// \brief Returns the index of the given node.
     ///
-    /// Returns the index of the given node. Since it is a static
-    /// graph its nodes can be indexed with integers from the range
-    /// <tt>[0..nodeNum()-1]</tt>.
-    /// \sa operator()
-    int index(const Node& node) const { return Parent::index(node); }
+    /// Returns the index of the given node. Since this structure is 
+    /// completely static, the nodes can be indexed with integers from
+    /// the range <tt>[0..nodeNum()-1]</tt>.
+    /// \sa operator()()
+    static int index(const Node& node) { return Parent::index(node); }
 
     /// \brief Returns the arc connecting the given nodes.
     ///
     /// Returns the arc connecting the given nodes.
-    Arc arc(const Node& s, const Node& t) const {
+    Arc arc(Node s, Node t) const {
       return Parent::arc(s, t);
     }
 
-    /// \brief Returns the edge connects the given nodes.
-    ///
-    /// Returns the edge connects the given nodes.
-    Edge edge(const Node& u, const Node& v) const {
+    /// \brief Returns the edge connecting the given nodes.
+    ///
+    /// Returns the edge connecting the given nodes.
+    Edge edge(Node u, Node v) const {
       return Parent::edge(u, v);
     }
Index: lemon/glpk.cc
===================================================================
--- lemon/glpk.cc	(revision 623)
+++ lemon/glpk.cc	(revision 793)
@@ -57,4 +57,40 @@
     int i = glp_add_rows(lp, 1);
     glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
+    return i;
+  }
+
+  int GlpkBase::_addRow(Value lo, ExprIterator b, 
+                        ExprIterator e, Value up) {
+    int i = glp_add_rows(lp, 1);
+
+    if (lo == -INF) {
+      if (up == INF) {
+        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
+      } else {
+        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
+      }    
+    } else {
+      if (up == INF) {
+        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
+      } else if (lo != up) {        
+        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
+      } else {
+        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
+      }
+    }
+
+    std::vector<int> indexes;
+    std::vector<Value> values;
+
+    indexes.push_back(0);
+    values.push_back(0);
+
+    for(ExprIterator it = b; it != e; ++it) {
+      indexes.push_back(it->first);
+      values.push_back(it->second);
+    }
+
+    glp_set_mat_row(lp, i, values.size() - 1,
+                    &indexes.front(), &values.front());
     return i;
   }
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h	(revision 697)
+++ lemon/glpk.h	(revision 793)
@@ -55,4 +55,5 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
Index: lemon/grid_graph.h
===================================================================
--- lemon/grid_graph.h	(revision 664)
+++ lemon/grid_graph.h	(revision 782)
@@ -471,15 +471,19 @@
   /// \brief Grid graph class
   ///
-  /// This class implements a special graph type. The nodes of the
-  /// graph can be indexed by two integer \c (i,j) value where \c i is
-  /// in the \c [0..width()-1] range and j is in the \c
-  /// [0..height()-1] range.  Two nodes are connected in the graph if
-  /// the indexes differ exactly on one position and exactly one is
-  /// the difference. The nodes of the graph can be indexed by position
-  /// with the \c operator()() function. The positions of the nodes can be
-  /// get with \c pos(), \c col() and \c row() members. The outgoing
+  /// GridGraph implements a special graph type. The nodes of the
+  /// graph can be indexed by two integer values \c (i,j) where \c i is
+  /// in the range <tt>[0..width()-1]</tt> and j is in the range
+  /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
+  /// the indices differ exactly on one position and the difference is
+  /// also exactly one. The nodes of the graph can be obtained by position
+  /// using the \c operator()() function and the indices of the nodes can
+  /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
   /// arcs can be retrieved with the \c right(), \c up(), \c left()
   /// and \c down() functions, where the bottom-left corner is the
   /// origin.
+  ///
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however
+  /// the structure can be resized using resize().
   ///
   /// \image html grid_graph.png
@@ -497,6 +501,7 @@
   ///\endcode
   ///
-  /// This graph type fully conforms to the \ref concepts::Graph
-  /// "Graph concept".
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
   class GridGraph : public ExtendedGridGraphBase {
     typedef ExtendedGridGraphBase Parent;
@@ -504,7 +509,9 @@
   public:
 
-    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
-    ///
-    /// Map to get the indices of the nodes as dim2::Point<int>.
+    /// \brief Map to get the indices of the nodes as \ref dim2::Point
+    /// "dim2::Point<int>".
+    ///
+    /// Map to get the indices of the nodes as \ref dim2::Point
+    /// "dim2::Point<int>".
     class IndexMap {
     public:
@@ -515,11 +522,7 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       IndexMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.pos(key);
@@ -541,11 +544,7 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       ColMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.col(key);
@@ -567,11 +566,7 @@
 
       /// \brief Constructor
-      ///
-      /// Constructor
       RowMap(const GridGraph& graph) : _graph(graph) {}
 
       /// \brief The subscript operator
-      ///
-      /// The subscript operator.
       Value operator[](Key key) const {
         return _graph.row(key);
@@ -584,13 +579,12 @@
     /// \brief Constructor
     ///
-    /// Construct a grid graph with given size.
+    /// Construct a grid graph with the given size.
     GridGraph(int width, int height) { construct(width, height); }
 
-    /// \brief Resize the graph
-    ///
-    /// Resize the graph. The function will fully destroy and rebuild
-    /// the graph.  This cause that the maps of the graph will
-    /// reallocated automatically and the previous values will be
-    /// lost.
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
     void resize(int width, int height) {
       Parent::notifier(Arc()).clear();
@@ -610,5 +604,5 @@
     }
 
-    /// \brief Gives back the column index of the node.
+    /// \brief The column index of the node.
     ///
     /// Gives back the column index of the node.
@@ -617,5 +611,5 @@
     }
 
-    /// \brief Gives back the row index of the node.
+    /// \brief The row index of the node.
     ///
     /// Gives back the row index of the node.
@@ -624,5 +618,5 @@
     }
 
-    /// \brief Gives back the position of the node.
+    /// \brief The position of the node.
     ///
     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
@@ -631,5 +625,5 @@
     }
 
-    /// \brief Gives back the number of the columns.
+    /// \brief The number of the columns.
     ///
     /// Gives back the number of the columns.
@@ -638,5 +632,5 @@
     }
 
-    /// \brief Gives back the number of the rows.
+    /// \brief The number of the rows.
     ///
     /// Gives back the number of the rows.
@@ -645,5 +639,5 @@
     }
 
-    /// \brief Gives back the arc goes right from the node.
+    /// \brief The arc goes right from the node.
     ///
     /// Gives back the arc goes right from the node. If there is not
@@ -653,5 +647,5 @@
     }
 
-    /// \brief Gives back the arc goes left from the node.
+    /// \brief The arc goes left from the node.
     ///
     /// Gives back the arc goes left from the node. If there is not
@@ -661,5 +655,5 @@
     }
 
-    /// \brief Gives back the arc goes up from the node.
+    /// \brief The arc goes up from the node.
     ///
     /// Gives back the arc goes up from the node. If there is not
@@ -669,5 +663,5 @@
     }
 
-    /// \brief Gives back the arc goes down from the node.
+    /// \brief The arc goes down from the node.
     ///
     /// Gives back the arc goes down from the node. If there is not
Index: lemon/hartmann_orlin.h
===================================================================
--- lemon/hartmann_orlin.h	(revision 819)
+++ lemon/hartmann_orlin.h	(revision 819)
@@ -0,0 +1,640 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_HARTMANN_ORLIN_H
+#define LEMON_HARTMANN_ORLIN_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
+
+#include <vector>
+#include <limits>
+#include <lemon/core.h>
+#include <lemon/path.h>
+#include <lemon/tolerance.h>
+#include <lemon/connectivity.h>
+
+namespace lemon {
+
+  /// \brief Default traits class of HartmannOrlin algorithm.
+  ///
+  /// Default traits class of HartmannOrlin algorithm.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  /// It must conform to the \ref concepts::Rea_data "Rea_data" concept.
+#ifdef DOXYGEN
+  template <typename GR, typename LEN>
+#else
+  template <typename GR, typename LEN,
+    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
+#endif
+  struct HartmannOrlinDefaultTraits
+  {
+    /// The type of the digraph
+    typedef GR Digraph;
+    /// The type of the length map
+    typedef LEN LengthMap;
+    /// The type of the arc lengths
+    typedef typename LengthMap::Value Value;
+
+    /// \brief The large value type used for internal computations
+    ///
+    /// The large value type used for internal computations.
+    /// It is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    /// \c Value must be convertible to \c LargeValue.
+    typedef double LargeValue;
+
+    /// The tolerance type used for internal computations
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addFront() function.
+    typedef lemon::Path<Digraph> Path;
+  };
+
+  // Default traits class for integer value types
+  template <typename GR, typename LEN>
+  struct HartmannOrlinDefaultTraits<GR, LEN, true>
+  {
+    typedef GR Digraph;
+    typedef LEN LengthMap;
+    typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+    typedef long long LargeValue;
+#else
+    typedef long LargeValue;
+#endif
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+    typedef lemon::Path<Digraph> Path;
+  };
+
+
+  /// \addtogroup min_mean_cycle
+  /// @{
+
+  /// \brief Implementation of the Hartmann-Orlin algorithm for finding
+  /// a minimum mean cycle.
+  ///
+  /// This class implements the Hartmann-Orlin algorithm for finding
+  /// a directed cycle of minimum mean length (cost) in a digraph
+  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
+  /// it applies an efficient early termination scheme.
+  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
+  ///
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// \tparam LEN The type of the length map. The default
+  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+#ifdef DOXYGEN
+  template <typename GR, typename LEN, typename TR>
+#else
+  template < typename GR,
+             typename LEN = typename GR::template ArcMap<int>,
+             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
+#endif
+  class HartmannOrlin
+  {
+  public:
+
+    /// The type of the digraph
+    typedef typename TR::Digraph Digraph;
+    /// The type of the length map
+    typedef typename TR::LengthMap LengthMap;
+    /// The type of the arc lengths
+    typedef typename TR::Value Value;
+
+    /// \brief The large value type
+    ///
+    /// The large value type used for internal computations.
+    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    typedef typename TR::LargeValue LargeValue;
+
+    /// The tolerance type
+    typedef typename TR::Tolerance Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
+    /// it is \ref lemon::Path "Path<Digraph>".
+    typedef typename TR::Path Path;
+
+    /// The \ref HartmannOrlinDefaultTraits "traits class" of the algorithm
+    typedef TR Traits;
+
+  private:
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+    // Data sturcture for path data
+    struct PathData
+    {
+      LargeValue dist;
+      Arc pred;
+      PathData(LargeValue d, Arc p = INVALID) :
+        dist(d), pred(p) {}
+    };
+
+    typedef typename Digraph::template NodeMap<std::vector<PathData> >
+      PathDataNodeMap;
+
+  private:
+
+    // The digraph the algorithm runs on
+    const Digraph &_gr;
+    // The length of the arcs
+    const LengthMap &_length;
+
+    // Data for storing the strongly connected components
+    int _comp_num;
+    typename Digraph::template NodeMap<int> _comp;
+    std::vector<std::vector<Node> > _comp_nodes;
+    std::vector<Node>* _nodes;
+    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
+
+    // Data for the found cycles
+    bool _curr_found, _best_found;
+    LargeValue _curr_length, _best_length;
+    int _curr_size, _best_size;
+    Node _curr_node, _best_node;
+    int _curr_level, _best_level;
+
+    Path *_cycle_path;
+    bool _local_path;
+
+    // Node map for storing path data
+    PathDataNodeMap _data;
+    // The processed nodes in the last round
+    std::vector<Node> _process;
+
+    Tolerance _tolerance;
+
+    // Infinite constant
+    const LargeValue INF;
+
+  public:
+
+    /// \name Named Template Parameters
+    /// @{
+
+    template <typename T>
+    struct SetLargeValueTraits : public Traits {
+      typedef T LargeValue;
+      typedef lemon::Tolerance<T> Tolerance;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c LargeValue type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+    /// type. It is used for internal computations in the algorithm.
+    template <typename T>
+    struct SetLargeValue
+      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {
+      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;
+    };
+
+    template <typename T>
+    struct SetPathTraits : public Traits {
+      typedef T Path;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c %Path type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting the \c %Path
+    /// type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addFront() function.
+    template <typename T>
+    struct SetPath
+      : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {
+      typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;
+    };
+
+    /// @}
+
+  public:
+
+    /// \brief Constructor.
+    ///
+    /// The constructor of the class.
+    ///
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param length The lengths (costs) of the arcs.
+    HartmannOrlin( const Digraph &digraph,
+                   const LengthMap &length ) :
+      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
+      _best_found(false), _best_length(0), _best_size(1),
+      _cycle_path(NULL), _local_path(false), _data(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
+    {}
+
+    /// Destructor.
+    ~HartmannOrlin() {
+      if (_local_path) delete _cycle_path;
+    }
+
+    /// \brief Set the path structure for storing the found cycle.
+    ///
+    /// This function sets an external path structure for storing the
+    /// found cycle.
+    ///
+    /// If you don't call this function before calling \ref run() or
+    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+    /// structure. The destuctor deallocates this automatically
+    /// allocated object, of course.
+    ///
+    /// \note The algorithm calls only the \ref lemon::Path::addFront()
+    /// "addFront()" function of the given path structure.
+    ///
+    /// \return <tt>(*this)</tt>
+    HartmannOrlin& cycle(Path &path) {
+      if (_local_path) {
+        delete _cycle_path;
+        _local_path = false;
+      }
+      _cycle_path = &path;
+      return *this;
+    }
+
+    /// \brief Set the tolerance used by the algorithm.
+    ///
+    /// This function sets the tolerance object used by the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    HartmannOrlin& tolerance(const Tolerance& tolerance) {
+      _tolerance = tolerance;
+      return *this;
+    }
+
+    /// \brief Return a const reference to the tolerance.
+    ///
+    /// This function returns a const reference to the tolerance object
+    /// used by the algorithm.
+    const Tolerance& tolerance() const {
+      return _tolerance;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to call the \ref run()
+    /// function.\n
+    /// If you only need the minimum mean length, you may call
+    /// \ref findMinMean().
+
+    /// @{
+
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// It can be called more than once (e.g. if the underlying digraph
+    /// and/or the arc lengths have been modified).
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
+    /// \code
+    ///   return mmc.findMinMean() && mmc.findCycle();
+    /// \endcode
+    bool run() {
+      return findMinMean() && findCycle();
+    }
+
+    /// \brief Find the minimum cycle mean.
+    ///
+    /// This function finds the minimum mean length of the directed
+    /// cycles in the digraph.
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    bool findMinMean() {
+      // Initialization and find strongly connected components
+      init();
+      findComponents();
+      
+      // Find the minimum cycle mean in the components
+      for (int comp = 0; comp < _comp_num; ++comp) {
+        if (!initComponent(comp)) continue;
+        processRounds();
+        
+        // Update the best cycle (global minimum mean cycle)
+        if ( _curr_found && (!_best_found || 
+             _curr_length * _best_size < _best_length * _curr_size) ) {
+          _best_found = true;
+          _best_length = _curr_length;
+          _best_size = _curr_size;
+          _best_node = _curr_node;
+          _best_level = _curr_level;
+        }
+      }
+      return _best_found;
+    }
+
+    /// \brief Find a minimum mean directed cycle.
+    ///
+    /// This function finds a directed cycle of minimum mean length
+    /// in the digraph using the data computed by findMinMean().
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \pre \ref findMinMean() must be called before using this function.
+    bool findCycle() {
+      if (!_best_found) return false;
+      IntNodeMap reached(_gr, -1);
+      int r = _best_level + 1;
+      Node u = _best_node;
+      while (reached[u] < 0) {
+        reached[u] = --r;
+        u = _gr.source(_data[u][r].pred);
+      }
+      r = reached[u];
+      Arc e = _data[u][r].pred;
+      _cycle_path->addFront(e);
+      _best_length = _length[e];
+      _best_size = 1;
+      Node v;
+      while ((v = _gr.source(e)) != u) {
+        e = _data[v][--r].pred;
+        _cycle_path->addFront(e);
+        _best_length += _length[e];
+        ++_best_size;
+      }
+      return true;
+    }
+
+    /// @}
+
+    /// \name Query Functions
+    /// The results of the algorithm can be obtained using these
+    /// functions.\n
+    /// The algorithm should be executed before using them.
+
+    /// @{
+
+    /// \brief Return the total length of the found cycle.
+    ///
+    /// This function returns the total length of the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    LargeValue cycleLength() const {
+      return _best_length;
+    }
+
+    /// \brief Return the number of arcs on the found cycle.
+    ///
+    /// This function returns the number of arcs on the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    int cycleArcNum() const {
+      return _best_size;
+    }
+
+    /// \brief Return the mean length of the found cycle.
+    ///
+    /// This function returns the mean length of the found cycle.
+    ///
+    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
+    /// following code.
+    /// \code
+    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+    /// \endcode
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    double cycleMean() const {
+      return static_cast<double>(_best_length) / _best_size;
+    }
+
+    /// \brief Return the found cycle.
+    ///
+    /// This function returns a const reference to the path structure
+    /// storing the found cycle.
+    ///
+    /// \pre \ref run() or \ref findCycle() must be called before using
+    /// this function.
+    const Path& cycle() const {
+      return *_cycle_path;
+    }
+
+    ///@}
+
+  private:
+
+    // Initialization
+    void init() {
+      if (!_cycle_path) {
+        _local_path = true;
+        _cycle_path = new Path;
+      }
+      _cycle_path->clear();
+      _best_found = false;
+      _best_length = 0;
+      _best_size = 1;
+      _cycle_path->clear();
+      for (NodeIt u(_gr); u != INVALID; ++u)
+        _data[u].clear();
+    }
+
+    // Find strongly connected components and initialize _comp_nodes
+    // and _out_arcs
+    void findComponents() {
+      _comp_num = stronglyConnectedComponents(_gr, _comp);
+      _comp_nodes.resize(_comp_num);
+      if (_comp_num == 1) {
+        _comp_nodes[0].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          _comp_nodes[0].push_back(n);
+          _out_arcs[n].clear();
+          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+            _out_arcs[n].push_back(a);
+          }
+        }
+      } else {
+        for (int i = 0; i < _comp_num; ++i)
+          _comp_nodes[i].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          int k = _comp[n];
+          _comp_nodes[k].push_back(n);
+          _out_arcs[n].clear();
+          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+            if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);
+          }
+        }
+      }
+    }
+
+    // Initialize path data for the current component
+    bool initComponent(int comp) {
+      _nodes = &(_comp_nodes[comp]);
+      int n = _nodes->size();
+      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
+        return false;
+      }      
+      for (int i = 0; i < n; ++i) {
+        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+      }
+      return true;
+    }
+
+    // Process all rounds of computing path data for the current component.
+    // _data[v][k] is the length of a shortest directed walk from the root
+    // node to node v containing exactly k arcs.
+    void processRounds() {
+      Node start = (*_nodes)[0];
+      _data[start][0] = PathData(0);
+      _process.clear();
+      _process.push_back(start);
+
+      int k, n = _nodes->size();
+      int next_check = 4;
+      bool terminate = false;
+      for (k = 1; k <= n && int(_process.size()) < n && !terminate; ++k) {
+        processNextBuildRound(k);
+        if (k == next_check || k == n) {
+          terminate = checkTermination(k);
+          next_check = next_check * 3 / 2;
+        }
+      }
+      for ( ; k <= n && !terminate; ++k) {
+        processNextFullRound(k);
+        if (k == next_check || k == n) {
+          terminate = checkTermination(k);
+          next_check = next_check * 3 / 2;
+        }
+      }
+    }
+
+    // Process one round and rebuild _process
+    void processNextBuildRound(int k) {
+      std::vector<Node> next;
+      Node u, v;
+      Arc e;
+      LargeValue d;
+      for (int i = 0; i < int(_process.size()); ++i) {
+        u = _process[i];
+        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+          e = _out_arcs[u][j];
+          v = _gr.target(e);
+          d = _data[u][k-1].dist + _length[e];
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            if (_data[v][k].dist == INF) next.push_back(v);
+            _data[v][k] = PathData(d, e);
+          }
+        }
+      }
+      _process.swap(next);
+    }
+
+    // Process one round using _nodes instead of _process
+    void processNextFullRound(int k) {
+      Node u, v;
+      Arc e;
+      LargeValue d;
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        u = (*_nodes)[i];
+        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+          e = _out_arcs[u][j];
+          v = _gr.target(e);
+          d = _data[u][k-1].dist + _length[e];
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            _data[v][k] = PathData(d, e);
+          }
+        }
+      }
+    }
+    
+    // Check early termination
+    bool checkTermination(int k) {
+      typedef std::pair<int, int> Pair;
+      typename GR::template NodeMap<Pair> level(_gr, Pair(-1, 0));
+      typename GR::template NodeMap<LargeValue> pi(_gr);
+      int n = _nodes->size();
+      LargeValue length;
+      int size;
+      Node u;
+      
+      // Search for cycles that are already found
+      _curr_found = false;
+      for (int i = 0; i < n; ++i) {
+        u = (*_nodes)[i];
+        if (_data[u][k].dist == INF) continue;
+        for (int j = k; j >= 0; --j) {
+          if (level[u].first == i && level[u].second > 0) {
+            // A cycle is found
+            length = _data[u][level[u].second].dist - _data[u][j].dist;
+            size = level[u].second - j;
+            if (!_curr_found || length * _curr_size < _curr_length * size) {
+              _curr_length = length;
+              _curr_size = size;
+              _curr_node = u;
+              _curr_level = level[u].second;
+              _curr_found = true;
+            }
+          }
+          level[u] = Pair(i, j);
+          u = _gr.source(_data[u][j].pred);
+        }
+      }
+
+      // If at least one cycle is found, check the optimality condition
+      LargeValue d;
+      if (_curr_found && k < n) {
+        // Find node potentials
+        for (int i = 0; i < n; ++i) {
+          u = (*_nodes)[i];
+          pi[u] = INF;
+          for (int j = 0; j <= k; ++j) {
+            if (_data[u][j].dist < INF) {
+              d = _data[u][j].dist * _curr_size - j * _curr_length;
+              if (_tolerance.less(d, pi[u])) pi[u] = d;
+            }
+          }
+        }
+
+        // Check the optimality condition for all arcs
+        bool done = true;
+        for (ArcIt a(_gr); a != INVALID; ++a) {
+          if (_tolerance.less(_length[a] * _curr_size - _curr_length,
+                              pi[_gr.target(a)] - pi[_gr.source(a)]) ) {
+            done = false;
+            break;
+          }
+        }
+        return done;
+      }
+      return (k == n);
+    }
+
+  }; //class HartmannOrlin
+
+  ///@}
+
+} //namespace lemon
+
+#endif //LEMON_HARTMANN_ORLIN_H
Index: lemon/howard.h
===================================================================
--- lemon/howard.h	(revision 818)
+++ lemon/howard.h	(revision 818)
@@ -0,0 +1,597 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_HOWARD_H
+#define LEMON_HOWARD_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Howard's algorithm for finding a minimum mean cycle.
+
+#include <vector>
+#include <limits>
+#include <lemon/core.h>
+#include <lemon/path.h>
+#include <lemon/tolerance.h>
+#include <lemon/connectivity.h>
+
+namespace lemon {
+
+  /// \brief Default traits class of Howard class.
+  ///
+  /// Default traits class of Howard class.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+#ifdef DOXYGEN
+  template <typename GR, typename LEN>
+#else
+  template <typename GR, typename LEN,
+    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
+#endif
+  struct HowardDefaultTraits
+  {
+    /// The type of the digraph
+    typedef GR Digraph;
+    /// The type of the length map
+    typedef LEN LengthMap;
+    /// The type of the arc lengths
+    typedef typename LengthMap::Value Value;
+
+    /// \brief The large value type used for internal computations
+    ///
+    /// The large value type used for internal computations.
+    /// It is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    /// \c Value must be convertible to \c LargeValue.
+    typedef double LargeValue;
+
+    /// The tolerance type used for internal computations
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addBack() function.
+    typedef lemon::Path<Digraph> Path;
+  };
+
+  // Default traits class for integer value types
+  template <typename GR, typename LEN>
+  struct HowardDefaultTraits<GR, LEN, true>
+  {
+    typedef GR Digraph;
+    typedef LEN LengthMap;
+    typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+    typedef long long LargeValue;
+#else
+    typedef long LargeValue;
+#endif
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+    typedef lemon::Path<Digraph> Path;
+  };
+
+
+  /// \addtogroup min_mean_cycle
+  /// @{
+
+  /// \brief Implementation of Howard's algorithm for finding a minimum
+  /// mean cycle.
+  ///
+  /// This class implements Howard's policy iteration algorithm for finding
+  /// a directed cycle of minimum mean length (cost) in a digraph
+  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// This class provides the most efficient algorithm for the
+  /// minimum mean cycle problem, though the best known theoretical
+  /// bound on its running time is exponential.
+  ///
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// \tparam LEN The type of the length map. The default
+  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+#ifdef DOXYGEN
+  template <typename GR, typename LEN, typename TR>
+#else
+  template < typename GR,
+             typename LEN = typename GR::template ArcMap<int>,
+             typename TR = HowardDefaultTraits<GR, LEN> >
+#endif
+  class Howard
+  {
+  public:
+  
+    /// The type of the digraph
+    typedef typename TR::Digraph Digraph;
+    /// The type of the length map
+    typedef typename TR::LengthMap LengthMap;
+    /// The type of the arc lengths
+    typedef typename TR::Value Value;
+
+    /// \brief The large value type
+    ///
+    /// The large value type used for internal computations.
+    /// Using the \ref HowardDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    typedef typename TR::LargeValue LargeValue;
+
+    /// The tolerance type
+    typedef typename TR::Tolerance Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// Using the \ref HowardDefaultTraits "default traits class",
+    /// it is \ref lemon::Path "Path<Digraph>".
+    typedef typename TR::Path Path;
+
+    /// The \ref HowardDefaultTraits "traits class" of the algorithm
+    typedef TR Traits;
+
+  private:
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+  
+    // The digraph the algorithm runs on
+    const Digraph &_gr;
+    // The length of the arcs
+    const LengthMap &_length;
+
+    // Data for the found cycles
+    bool _curr_found, _best_found;
+    LargeValue _curr_length, _best_length;
+    int _curr_size, _best_size;
+    Node _curr_node, _best_node;
+
+    Path *_cycle_path;
+    bool _local_path;
+
+    // Internal data used by the algorithm
+    typename Digraph::template NodeMap<Arc> _policy;
+    typename Digraph::template NodeMap<bool> _reached;
+    typename Digraph::template NodeMap<int> _level;
+    typename Digraph::template NodeMap<LargeValue> _dist;
+
+    // Data for storing the strongly connected components
+    int _comp_num;
+    typename Digraph::template NodeMap<int> _comp;
+    std::vector<std::vector<Node> > _comp_nodes;
+    std::vector<Node>* _nodes;
+    typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
+    
+    // Queue used for BFS search
+    std::vector<Node> _queue;
+    int _qfront, _qback;
+
+    Tolerance _tolerance;
+  
+    // Infinite constant
+    const LargeValue INF;
+
+  public:
+  
+    /// \name Named Template Parameters
+    /// @{
+
+    template <typename T>
+    struct SetLargeValueTraits : public Traits {
+      typedef T LargeValue;
+      typedef lemon::Tolerance<T> Tolerance;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c LargeValue type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+    /// type. It is used for internal computations in the algorithm.
+    template <typename T>
+    struct SetLargeValue
+      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
+      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
+    };
+
+    template <typename T>
+    struct SetPathTraits : public Traits {
+      typedef T Path;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c %Path type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting the \c %Path
+    /// type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addBack() function.
+    template <typename T>
+    struct SetPath
+      : public Howard<GR, LEN, SetPathTraits<T> > {
+      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
+    };
+    
+    /// @}
+
+  public:
+
+    /// \brief Constructor.
+    ///
+    /// The constructor of the class.
+    ///
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param length The lengths (costs) of the arcs.
+    Howard( const Digraph &digraph,
+            const LengthMap &length ) :
+      _gr(digraph), _length(length), _best_found(false),
+      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
+      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
+      _comp(digraph), _in_arcs(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
+    {}
+
+    /// Destructor.
+    ~Howard() {
+      if (_local_path) delete _cycle_path;
+    }
+
+    /// \brief Set the path structure for storing the found cycle.
+    ///
+    /// This function sets an external path structure for storing the
+    /// found cycle.
+    ///
+    /// If you don't call this function before calling \ref run() or
+    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+    /// structure. The destuctor deallocates this automatically
+    /// allocated object, of course.
+    ///
+    /// \note The algorithm calls only the \ref lemon::Path::addBack()
+    /// "addBack()" function of the given path structure.
+    ///
+    /// \return <tt>(*this)</tt>
+    Howard& cycle(Path &path) {
+      if (_local_path) {
+        delete _cycle_path;
+        _local_path = false;
+      }
+      _cycle_path = &path;
+      return *this;
+    }
+
+    /// \brief Set the tolerance used by the algorithm.
+    ///
+    /// This function sets the tolerance object used by the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    Howard& tolerance(const Tolerance& tolerance) {
+      _tolerance = tolerance;
+      return *this;
+    }
+
+    /// \brief Return a const reference to the tolerance.
+    ///
+    /// This function returns a const reference to the tolerance object
+    /// used by the algorithm.
+    const Tolerance& tolerance() const {
+      return _tolerance;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to call the \ref run()
+    /// function.\n
+    /// If you only need the minimum mean length, you may call
+    /// \ref findMinMean().
+
+    /// @{
+
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// It can be called more than once (e.g. if the underlying digraph
+    /// and/or the arc lengths have been modified).
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
+    /// \code
+    ///   return mmc.findMinMean() && mmc.findCycle();
+    /// \endcode
+    bool run() {
+      return findMinMean() && findCycle();
+    }
+
+    /// \brief Find the minimum cycle mean.
+    ///
+    /// This function finds the minimum mean length of the directed
+    /// cycles in the digraph.
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    bool findMinMean() {
+      // Initialize and find strongly connected components
+      init();
+      findComponents();
+      
+      // Find the minimum cycle mean in the components
+      for (int comp = 0; comp < _comp_num; ++comp) {
+        // Find the minimum mean cycle in the current component
+        if (!buildPolicyGraph(comp)) continue;
+        while (true) {
+          findPolicyCycle();
+          if (!computeNodeDistances()) break;
+        }
+        // Update the best cycle (global minimum mean cycle)
+        if ( _curr_found && (!_best_found ||
+             _curr_length * _best_size < _best_length * _curr_size) ) {
+          _best_found = true;
+          _best_length = _curr_length;
+          _best_size = _curr_size;
+          _best_node = _curr_node;
+        }
+      }
+      return _best_found;
+    }
+
+    /// \brief Find a minimum mean directed cycle.
+    ///
+    /// This function finds a directed cycle of minimum mean length
+    /// in the digraph using the data computed by findMinMean().
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \pre \ref findMinMean() must be called before using this function.
+    bool findCycle() {
+      if (!_best_found) return false;
+      _cycle_path->addBack(_policy[_best_node]);
+      for ( Node v = _best_node;
+            (v = _gr.target(_policy[v])) != _best_node; ) {
+        _cycle_path->addBack(_policy[v]);
+      }
+      return true;
+    }
+
+    /// @}
+
+    /// \name Query Functions
+    /// The results of the algorithm can be obtained using these
+    /// functions.\n
+    /// The algorithm should be executed before using them.
+
+    /// @{
+
+    /// \brief Return the total length of the found cycle.
+    ///
+    /// This function returns the total length of the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    LargeValue cycleLength() const {
+      return _best_length;
+    }
+
+    /// \brief Return the number of arcs on the found cycle.
+    ///
+    /// This function returns the number of arcs on the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    int cycleArcNum() const {
+      return _best_size;
+    }
+
+    /// \brief Return the mean length of the found cycle.
+    ///
+    /// This function returns the mean length of the found cycle.
+    ///
+    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
+    /// following code.
+    /// \code
+    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+    /// \endcode
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    double cycleMean() const {
+      return static_cast<double>(_best_length) / _best_size;
+    }
+
+    /// \brief Return the found cycle.
+    ///
+    /// This function returns a const reference to the path structure
+    /// storing the found cycle.
+    ///
+    /// \pre \ref run() or \ref findCycle() must be called before using
+    /// this function.
+    const Path& cycle() const {
+      return *_cycle_path;
+    }
+
+    ///@}
+
+  private:
+
+    // Initialize
+    void init() {
+      if (!_cycle_path) {
+        _local_path = true;
+        _cycle_path = new Path;
+      }
+      _queue.resize(countNodes(_gr));
+      _best_found = false;
+      _best_length = 0;
+      _best_size = 1;
+      _cycle_path->clear();
+    }
+    
+    // Find strongly connected components and initialize _comp_nodes
+    // and _in_arcs
+    void findComponents() {
+      _comp_num = stronglyConnectedComponents(_gr, _comp);
+      _comp_nodes.resize(_comp_num);
+      if (_comp_num == 1) {
+        _comp_nodes[0].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          _comp_nodes[0].push_back(n);
+          _in_arcs[n].clear();
+          for (InArcIt a(_gr, n); a != INVALID; ++a) {
+            _in_arcs[n].push_back(a);
+          }
+        }
+      } else {
+        for (int i = 0; i < _comp_num; ++i)
+          _comp_nodes[i].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          int k = _comp[n];
+          _comp_nodes[k].push_back(n);
+          _in_arcs[n].clear();
+          for (InArcIt a(_gr, n); a != INVALID; ++a) {
+            if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
+          }
+        }
+      }
+    }
+
+    // Build the policy graph in the given strongly connected component
+    // (the out-degree of every node is 1)
+    bool buildPolicyGraph(int comp) {
+      _nodes = &(_comp_nodes[comp]);
+      if (_nodes->size() < 1 ||
+          (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
+        return false;
+      }
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        _dist[(*_nodes)[i]] = INF;
+      }
+      Node u, v;
+      Arc e;
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        v = (*_nodes)[i];
+        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+          e = _in_arcs[v][j];
+          u = _gr.source(e);
+          if (_length[e] < _dist[u]) {
+            _dist[u] = _length[e];
+            _policy[u] = e;
+          }
+        }
+      }
+      return true;
+    }
+
+    // Find the minimum mean cycle in the policy graph
+    void findPolicyCycle() {
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        _level[(*_nodes)[i]] = -1;
+      }
+      LargeValue clength;
+      int csize;
+      Node u, v;
+      _curr_found = false;
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        u = (*_nodes)[i];
+        if (_level[u] >= 0) continue;
+        for (; _level[u] < 0; u = _gr.target(_policy[u])) {
+          _level[u] = i;
+        }
+        if (_level[u] == i) {
+          // A cycle is found
+          clength = _length[_policy[u]];
+          csize = 1;
+          for (v = u; (v = _gr.target(_policy[v])) != u; ) {
+            clength += _length[_policy[v]];
+            ++csize;
+          }
+          if ( !_curr_found ||
+               (clength * _curr_size < _curr_length * csize) ) {
+            _curr_found = true;
+            _curr_length = clength;
+            _curr_size = csize;
+            _curr_node = u;
+          }
+        }
+      }
+    }
+
+    // Contract the policy graph and compute node distances
+    bool computeNodeDistances() {
+      // Find the component of the main cycle and compute node distances
+      // using reverse BFS
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        _reached[(*_nodes)[i]] = false;
+      }
+      _qfront = _qback = 0;
+      _queue[0] = _curr_node;
+      _reached[_curr_node] = true;
+      _dist[_curr_node] = 0;
+      Node u, v;
+      Arc e;
+      while (_qfront <= _qback) {
+        v = _queue[_qfront++];
+        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+          e = _in_arcs[v][j];
+          u = _gr.source(e);
+          if (_policy[u] == e && !_reached[u]) {
+            _reached[u] = true;
+            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+            _queue[++_qback] = u;
+          }
+        }
+      }
+
+      // Connect all other nodes to this component and compute node
+      // distances using reverse BFS
+      _qfront = 0;
+      while (_qback < int(_nodes->size())-1) {
+        v = _queue[_qfront++];
+        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+          e = _in_arcs[v][j];
+          u = _gr.source(e);
+          if (!_reached[u]) {
+            _reached[u] = true;
+            _policy[u] = e;
+            _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
+            _queue[++_qback] = u;
+          }
+        }
+      }
+
+      // Improve node distances
+      bool improved = false;
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        v = (*_nodes)[i];
+        for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
+          e = _in_arcs[v][j];
+          u = _gr.source(e);
+          LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
+          if (_tolerance.less(delta, _dist[u])) {
+            _dist[u] = delta;
+            _policy[u] = e;
+            improved = true;
+          }
+        }
+      }
+      return improved;
+    }
+
+  }; //class Howard
+
+  ///@}
+
+} //namespace lemon
+
+#endif //LEMON_HOWARD_H
Index: lemon/hypercube_graph.h
===================================================================
--- lemon/hypercube_graph.h	(revision 664)
+++ lemon/hypercube_graph.h	(revision 827)
@@ -263,5 +263,5 @@
     }
 
-    int index(Node node) const {
+    static int index(Node node) {
       return node._id;
     }
@@ -283,15 +283,19 @@
   /// \brief Hypercube graph class
   ///
-  /// This class implements a special graph type. The nodes of the graph
-  /// are indiced with integers with at most \c dim binary digits.
+  /// HypercubeGraph implements a special graph type. The nodes of the
+  /// graph are indexed with integers having at most \c dim binary digits.
   /// Two nodes are connected in the graph if and only if their indices
   /// differ only on one position in the binary form.
+  /// This class is completely static and it needs constant memory space.
+  /// Thus you can neither add nor delete nodes or edges, however 
+  /// the structure can be resized using resize().
+  ///
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
   ///
   /// \note The type of the indices is chosen to \c int for efficiency
   /// reasons. Thus the maximum dimension of this implementation is 26
   /// (assuming that the size of \c int is 32 bit).
-  ///
-  /// This graph type fully conforms to the \ref concepts::Graph
-  /// "Graph concept".
   class HypercubeGraph : public ExtendedHypercubeGraphBase {
     typedef ExtendedHypercubeGraphBase Parent;
@@ -303,4 +307,19 @@
     /// Constructs a hypercube graph with \c dim dimensions.
     HypercubeGraph(int dim) { construct(dim); }
+
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
+    void resize(int dim) {
+      Parent::notifier(Arc()).clear();
+      Parent::notifier(Edge()).clear();
+      Parent::notifier(Node()).clear();
+      construct(dim);
+      Parent::notifier(Node()).build();
+      Parent::notifier(Edge()).build();
+      Parent::notifier(Arc()).build();
+    }
 
     /// \brief The number of dimensions.
@@ -321,5 +340,5 @@
     ///
     /// Gives back the dimension id of the given edge.
-    /// It is in the [0..dim-1] range.
+    /// It is in the range <tt>[0..dim-1]</tt>.
     int dimension(Edge edge) const {
       return Parent::dimension(edge);
@@ -329,5 +348,5 @@
     ///
     /// Gives back the dimension id of the given arc.
-    /// It is in the [0..dim-1] range.
+    /// It is in the range <tt>[0..dim-1]</tt>.
     int dimension(Arc arc) const {
       return Parent::dimension(arc);
@@ -338,5 +357,5 @@
     /// Gives back the index of the given node.
     /// The lower bits of the integer describes the node.
-    int index(Node node) const {
+    static int index(Node node) {
       return Parent::index(node);
     }
Index: lemon/karp.h
===================================================================
--- lemon/karp.h	(revision 819)
+++ lemon/karp.h	(revision 819)
@@ -0,0 +1,582 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_KARP_H
+#define LEMON_KARP_H
+
+/// \ingroup min_mean_cycle
+///
+/// \file
+/// \brief Karp's algorithm for finding a minimum mean cycle.
+
+#include <vector>
+#include <limits>
+#include <lemon/core.h>
+#include <lemon/path.h>
+#include <lemon/tolerance.h>
+#include <lemon/connectivity.h>
+
+namespace lemon {
+
+  /// \brief Default traits class of Karp algorithm.
+  ///
+  /// Default traits class of Karp algorithm.
+  /// \tparam GR The type of the digraph.
+  /// \tparam LEN The type of the length map.
+  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+#ifdef DOXYGEN
+  template <typename GR, typename LEN>
+#else
+  template <typename GR, typename LEN,
+    bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
+#endif
+  struct KarpDefaultTraits
+  {
+    /// The type of the digraph
+    typedef GR Digraph;
+    /// The type of the length map
+    typedef LEN LengthMap;
+    /// The type of the arc lengths
+    typedef typename LengthMap::Value Value;
+
+    /// \brief The large value type used for internal computations
+    ///
+    /// The large value type used for internal computations.
+    /// It is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    /// \c Value must be convertible to \c LargeValue.
+    typedef double LargeValue;
+
+    /// The tolerance type used for internal computations
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addFront() function.
+    typedef lemon::Path<Digraph> Path;
+  };
+
+  // Default traits class for integer value types
+  template <typename GR, typename LEN>
+  struct KarpDefaultTraits<GR, LEN, true>
+  {
+    typedef GR Digraph;
+    typedef LEN LengthMap;
+    typedef typename LengthMap::Value Value;
+#ifdef LEMON_HAVE_LONG_LONG
+    typedef long long LargeValue;
+#else
+    typedef long LargeValue;
+#endif
+    typedef lemon::Tolerance<LargeValue> Tolerance;
+    typedef lemon::Path<Digraph> Path;
+  };
+
+
+  /// \addtogroup min_mean_cycle
+  /// @{
+
+  /// \brief Implementation of Karp's algorithm for finding a minimum
+  /// mean cycle.
+  ///
+  /// This class implements Karp's algorithm for finding a directed
+  /// cycle of minimum mean length (cost) in a digraph
+  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
+  ///
+  /// \tparam GR The type of the digraph the algorithm runs on.
+  /// \tparam LEN The type of the length map. The default
+  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
+#ifdef DOXYGEN
+  template <typename GR, typename LEN, typename TR>
+#else
+  template < typename GR,
+             typename LEN = typename GR::template ArcMap<int>,
+             typename TR = KarpDefaultTraits<GR, LEN> >
+#endif
+  class Karp
+  {
+  public:
+
+    /// The type of the digraph
+    typedef typename TR::Digraph Digraph;
+    /// The type of the length map
+    typedef typename TR::LengthMap LengthMap;
+    /// The type of the arc lengths
+    typedef typename TR::Value Value;
+
+    /// \brief The large value type
+    ///
+    /// The large value type used for internal computations.
+    /// Using the \ref KarpDefaultTraits "default traits class",
+    /// it is \c long \c long if the \c Value type is integer,
+    /// otherwise it is \c double.
+    typedef typename TR::LargeValue LargeValue;
+
+    /// The tolerance type
+    typedef typename TR::Tolerance Tolerance;
+
+    /// \brief The path type of the found cycles
+    ///
+    /// The path type of the found cycles.
+    /// Using the \ref KarpDefaultTraits "default traits class",
+    /// it is \ref lemon::Path "Path<Digraph>".
+    typedef typename TR::Path Path;
+
+    /// The \ref KarpDefaultTraits "traits class" of the algorithm
+    typedef TR Traits;
+
+  private:
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+    // Data sturcture for path data
+    struct PathData
+    {
+      LargeValue dist;
+      Arc pred;
+      PathData(LargeValue d, Arc p = INVALID) :
+        dist(d), pred(p) {}
+    };
+
+    typedef typename Digraph::template NodeMap<std::vector<PathData> >
+      PathDataNodeMap;
+
+  private:
+
+    // The digraph the algorithm runs on
+    const Digraph &_gr;
+    // The length of the arcs
+    const LengthMap &_length;
+
+    // Data for storing the strongly connected components
+    int _comp_num;
+    typename Digraph::template NodeMap<int> _comp;
+    std::vector<std::vector<Node> > _comp_nodes;
+    std::vector<Node>* _nodes;
+    typename Digraph::template NodeMap<std::vector<Arc> > _out_arcs;
+
+    // Data for the found cycle
+    LargeValue _cycle_length;
+    int _cycle_size;
+    Node _cycle_node;
+
+    Path *_cycle_path;
+    bool _local_path;
+
+    // Node map for storing path data
+    PathDataNodeMap _data;
+    // The processed nodes in the last round
+    std::vector<Node> _process;
+
+    Tolerance _tolerance;
+    
+    // Infinite constant
+    const LargeValue INF;
+
+  public:
+
+    /// \name Named Template Parameters
+    /// @{
+
+    template <typename T>
+    struct SetLargeValueTraits : public Traits {
+      typedef T LargeValue;
+      typedef lemon::Tolerance<T> Tolerance;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c LargeValue type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting \c LargeValue
+    /// type. It is used for internal computations in the algorithm.
+    template <typename T>
+    struct SetLargeValue
+      : public Karp<GR, LEN, SetLargeValueTraits<T> > {
+      typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;
+    };
+
+    template <typename T>
+    struct SetPathTraits : public Traits {
+      typedef T Path;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c %Path type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting the \c %Path
+    /// type of the found cycles.
+    /// It must conform to the \ref lemon::concepts::Path "Path" concept
+    /// and it must have an \c addFront() function.
+    template <typename T>
+    struct SetPath
+      : public Karp<GR, LEN, SetPathTraits<T> > {
+      typedef Karp<GR, LEN, SetPathTraits<T> > Create;
+    };
+
+    /// @}
+
+  public:
+
+    /// \brief Constructor.
+    ///
+    /// The constructor of the class.
+    ///
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param length The lengths (costs) of the arcs.
+    Karp( const Digraph &digraph,
+          const LengthMap &length ) :
+      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
+      _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
+      _cycle_path(NULL), _local_path(false), _data(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
+    {}
+
+    /// Destructor.
+    ~Karp() {
+      if (_local_path) delete _cycle_path;
+    }
+
+    /// \brief Set the path structure for storing the found cycle.
+    ///
+    /// This function sets an external path structure for storing the
+    /// found cycle.
+    ///
+    /// If you don't call this function before calling \ref run() or
+    /// \ref findMinMean(), it will allocate a local \ref Path "path"
+    /// structure. The destuctor deallocates this automatically
+    /// allocated object, of course.
+    ///
+    /// \note The algorithm calls only the \ref lemon::Path::addFront()
+    /// "addFront()" function of the given path structure.
+    ///
+    /// \return <tt>(*this)</tt>
+    Karp& cycle(Path &path) {
+      if (_local_path) {
+        delete _cycle_path;
+        _local_path = false;
+      }
+      _cycle_path = &path;
+      return *this;
+    }
+
+    /// \brief Set the tolerance used by the algorithm.
+    ///
+    /// This function sets the tolerance object used by the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    Karp& tolerance(const Tolerance& tolerance) {
+      _tolerance = tolerance;
+      return *this;
+    }
+
+    /// \brief Return a const reference to the tolerance.
+    ///
+    /// This function returns a const reference to the tolerance object
+    /// used by the algorithm.
+    const Tolerance& tolerance() const {
+      return _tolerance;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to call the \ref run()
+    /// function.\n
+    /// If you only need the minimum mean length, you may call
+    /// \ref findMinMean().
+
+    /// @{
+
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// It can be called more than once (e.g. if the underlying digraph
+    /// and/or the arc lengths have been modified).
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
+    /// \code
+    ///   return mmc.findMinMean() && mmc.findCycle();
+    /// \endcode
+    bool run() {
+      return findMinMean() && findCycle();
+    }
+
+    /// \brief Find the minimum cycle mean.
+    ///
+    /// This function finds the minimum mean length of the directed
+    /// cycles in the digraph.
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    bool findMinMean() {
+      // Initialization and find strongly connected components
+      init();
+      findComponents();
+      
+      // Find the minimum cycle mean in the components
+      for (int comp = 0; comp < _comp_num; ++comp) {
+        if (!initComponent(comp)) continue;
+        processRounds();
+        updateMinMean();
+      }
+      return (_cycle_node != INVALID);
+    }
+
+    /// \brief Find a minimum mean directed cycle.
+    ///
+    /// This function finds a directed cycle of minimum mean length
+    /// in the digraph using the data computed by findMinMean().
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    ///
+    /// \pre \ref findMinMean() must be called before using this function.
+    bool findCycle() {
+      if (_cycle_node == INVALID) return false;
+      IntNodeMap reached(_gr, -1);
+      int r = _data[_cycle_node].size();
+      Node u = _cycle_node;
+      while (reached[u] < 0) {
+        reached[u] = --r;
+        u = _gr.source(_data[u][r].pred);
+      }
+      r = reached[u];
+      Arc e = _data[u][r].pred;
+      _cycle_path->addFront(e);
+      _cycle_length = _length[e];
+      _cycle_size = 1;
+      Node v;
+      while ((v = _gr.source(e)) != u) {
+        e = _data[v][--r].pred;
+        _cycle_path->addFront(e);
+        _cycle_length += _length[e];
+        ++_cycle_size;
+      }
+      return true;
+    }
+
+    /// @}
+
+    /// \name Query Functions
+    /// The results of the algorithm can be obtained using these
+    /// functions.\n
+    /// The algorithm should be executed before using them.
+
+    /// @{
+
+    /// \brief Return the total length of the found cycle.
+    ///
+    /// This function returns the total length of the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    LargeValue cycleLength() const {
+      return _cycle_length;
+    }
+
+    /// \brief Return the number of arcs on the found cycle.
+    ///
+    /// This function returns the number of arcs on the found cycle.
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    int cycleArcNum() const {
+      return _cycle_size;
+    }
+
+    /// \brief Return the mean length of the found cycle.
+    ///
+    /// This function returns the mean length of the found cycle.
+    ///
+    /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
+    /// following code.
+    /// \code
+    ///   return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
+    /// \endcode
+    ///
+    /// \pre \ref run() or \ref findMinMean() must be called before
+    /// using this function.
+    double cycleMean() const {
+      return static_cast<double>(_cycle_length) / _cycle_size;
+    }
+
+    /// \brief Return the found cycle.
+    ///
+    /// This function returns a const reference to the path structure
+    /// storing the found cycle.
+    ///
+    /// \pre \ref run() or \ref findCycle() must be called before using
+    /// this function.
+    const Path& cycle() const {
+      return *_cycle_path;
+    }
+
+    ///@}
+
+  private:
+
+    // Initialization
+    void init() {
+      if (!_cycle_path) {
+        _local_path = true;
+        _cycle_path = new Path;
+      }
+      _cycle_path->clear();
+      _cycle_length = 0;
+      _cycle_size = 1;
+      _cycle_node = INVALID;
+      for (NodeIt u(_gr); u != INVALID; ++u)
+        _data[u].clear();
+    }
+
+    // Find strongly connected components and initialize _comp_nodes
+    // and _out_arcs
+    void findComponents() {
+      _comp_num = stronglyConnectedComponents(_gr, _comp);
+      _comp_nodes.resize(_comp_num);
+      if (_comp_num == 1) {
+        _comp_nodes[0].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          _comp_nodes[0].push_back(n);
+          _out_arcs[n].clear();
+          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+            _out_arcs[n].push_back(a);
+          }
+        }
+      } else {
+        for (int i = 0; i < _comp_num; ++i)
+          _comp_nodes[i].clear();
+        for (NodeIt n(_gr); n != INVALID; ++n) {
+          int k = _comp[n];
+          _comp_nodes[k].push_back(n);
+          _out_arcs[n].clear();
+          for (OutArcIt a(_gr, n); a != INVALID; ++a) {
+            if (_comp[_gr.target(a)] == k) _out_arcs[n].push_back(a);
+          }
+        }
+      }
+    }
+
+    // Initialize path data for the current component
+    bool initComponent(int comp) {
+      _nodes = &(_comp_nodes[comp]);
+      int n = _nodes->size();
+      if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
+        return false;
+      }      
+      for (int i = 0; i < n; ++i) {
+        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+      }
+      return true;
+    }
+
+    // Process all rounds of computing path data for the current component.
+    // _data[v][k] is the length of a shortest directed walk from the root
+    // node to node v containing exactly k arcs.
+    void processRounds() {
+      Node start = (*_nodes)[0];
+      _data[start][0] = PathData(0);
+      _process.clear();
+      _process.push_back(start);
+
+      int k, n = _nodes->size();
+      for (k = 1; k <= n && int(_process.size()) < n; ++k) {
+        processNextBuildRound(k);
+      }
+      for ( ; k <= n; ++k) {
+        processNextFullRound(k);
+      }
+    }
+
+    // Process one round and rebuild _process
+    void processNextBuildRound(int k) {
+      std::vector<Node> next;
+      Node u, v;
+      Arc e;
+      LargeValue d;
+      for (int i = 0; i < int(_process.size()); ++i) {
+        u = _process[i];
+        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+          e = _out_arcs[u][j];
+          v = _gr.target(e);
+          d = _data[u][k-1].dist + _length[e];
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            if (_data[v][k].dist == INF) next.push_back(v);
+            _data[v][k] = PathData(d, e);
+          }
+        }
+      }
+      _process.swap(next);
+    }
+
+    // Process one round using _nodes instead of _process
+    void processNextFullRound(int k) {
+      Node u, v;
+      Arc e;
+      LargeValue d;
+      for (int i = 0; i < int(_nodes->size()); ++i) {
+        u = (*_nodes)[i];
+        for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
+          e = _out_arcs[u][j];
+          v = _gr.target(e);
+          d = _data[u][k-1].dist + _length[e];
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            _data[v][k] = PathData(d, e);
+          }
+        }
+      }
+    }
+
+    // Update the minimum cycle mean
+    void updateMinMean() {
+      int n = _nodes->size();
+      for (int i = 0; i < n; ++i) {
+        Node u = (*_nodes)[i];
+        if (_data[u][n].dist == INF) continue;
+        LargeValue length, max_length = 0;
+        int size, max_size = 1;
+        bool found_curr = false;
+        for (int k = 0; k < n; ++k) {
+          if (_data[u][k].dist == INF) continue;
+          length = _data[u][n].dist - _data[u][k].dist;
+          size = n - k;
+          if (!found_curr || length * max_size > max_length * size) {
+            found_curr = true;
+            max_length = length;
+            max_size = size;
+          }
+        }
+        if ( found_curr && (_cycle_node == INVALID ||
+             max_length * _cycle_size < _cycle_length * max_size) ) {
+          _cycle_length = max_length;
+          _cycle_size = max_size;
+          _cycle_node = u;
+        }
+      }
+    }
+
+  }; //class Karp
+
+  ///@}
+
+} //namespace lemon
+
+#endif //LEMON_KARP_H
Index: lemon/list_graph.h
===================================================================
--- lemon/list_graph.h	(revision 664)
+++ lemon/list_graph.h	(revision 788)
@@ -22,5 +22,5 @@
 ///\ingroup graphs
 ///\file
-///\brief ListDigraph, ListGraph classes.
+///\brief ListDigraph and ListGraph classes.
 
 #include <lemon/core.h>
@@ -32,4 +32,6 @@
 
 namespace lemon {
+
+  class ListDigraph;
 
   class ListDigraphBase {
@@ -63,4 +65,5 @@
     class Node {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -78,4 +81,5 @@
     class Arc {
       friend class ListDigraphBase;
+      friend class ListDigraph;
     protected:
 
@@ -117,18 +121,18 @@
       int n;
       for(n = first_node;
-          n!=-1 && nodes[n].first_in == -1;
+          n != -1 && nodes[n].first_out == -1;
           n = nodes[n].next) {}
-      arc.id = (n == -1) ? -1 : nodes[n].first_in;
+      arc.id = (n == -1) ? -1 : nodes[n].first_out;
     }
 
     void next(Arc& arc) const {
-      if (arcs[arc.id].next_in != -1) {
-        arc.id = arcs[arc.id].next_in;
+      if (arcs[arc.id].next_out != -1) {
+        arc.id = arcs[arc.id].next_out;
       } else {
         int n;
-        for(n = nodes[arcs[arc.id].target].next;
-            n!=-1 && nodes[n].first_in == -1;
+        for(n = nodes[arcs[arc.id].source].next;
+            n != -1 && nodes[n].first_out == -1;
             n = nodes[n].next) {}
-        arc.id = (n == -1) ? -1 : nodes[n].first_in;
+        arc.id = (n == -1) ? -1 : nodes[n].first_out;
       }
     }
@@ -312,29 +316,23 @@
   ///A general directed graph structure.
 
-  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
-  ///implementation based on static linked lists that are stored in
+  ///\ref ListDigraph is a versatile and fast directed graph
+  ///implementation based on linked lists that are stored in
   ///\c std::vector structures.
   ///
-  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
-  ///also provides several useful additional functionalities.
-  ///Most of the member functions and nested classes are documented
+  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
+  ///and it also provides several useful additional functionalities.
+  ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
   ///\sa concepts::Digraph
-
+  ///\sa ListGraph
   class ListDigraph : public ExtendedListDigraphBase {
     typedef ExtendedListDigraphBase Parent;
 
   private:
-    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
-
-    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
-    ///
+    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
-    ///\brief Assignment of ListDigraph to another one is \e not allowed.
-    ///Use copyDigraph() instead.
-
-    ///Assignment of ListDigraph to another one is \e not allowed.
-    ///Use copyDigraph() instead.
+    /// \brief Assignment of a digraph to another one is \e not allowed.
+    /// Use DigraphCopy instead.
     void operator=(const ListDigraph &) {}
   public:
@@ -348,5 +346,5 @@
     ///Add a new node to the digraph.
 
-    ///Add a new node to the digraph.
+    ///This function adds a new node to the digraph.
     ///\return The new node.
     Node addNode() { return Parent::addNode(); }
@@ -354,8 +352,8 @@
     ///Add a new arc to the digraph.
 
-    ///Add a new arc to the digraph with source node \c s
+    ///This function adds a new arc to the digraph with source node \c s
     ///and target node \c t.
     ///\return The new arc.
-    Arc addArc(const Node& s, const Node& t) {
+    Arc addArc(Node s, Node t) {
       return Parent::addArc(s, t);
     }
@@ -363,41 +361,36 @@
     ///\brief Erase a node from the digraph.
     ///
-    ///Erase a node from the digraph.
-    ///
-    void erase(const Node& n) { Parent::erase(n); }
+    ///This function erases the given node from the digraph.
+    void erase(Node n) { Parent::erase(n); }
 
     ///\brief Erase an arc from the digraph.
     ///
-    ///Erase an arc from the digraph.
-    ///
-    void erase(const Arc& a) { Parent::erase(a); }
+    ///This function erases the given arc from the digraph.
+    void erase(Arc a) { Parent::erase(a); }
 
     /// Node validity check
 
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
-    ///
-    /// \warning A Node pointing to a removed item
-    /// could become valid again later if new nodes are
-    /// added to the graph.
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the digraph.
+    ///
+    /// \warning A removed node could become valid again if new nodes are
+    /// added to the digraph.
     bool valid(Node n) const { return Parent::valid(n); }
 
     /// Arc validity check
 
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning An Arc pointing to a removed item
-    /// could become valid again later if new nodes are
-    /// added to the graph.
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the digraph.
+    ///
+    /// \warning A removed arc could become valid again if new arcs are
+    /// added to the digraph.
     bool valid(Arc a) const { return Parent::valid(a); }
 
-    /// Change the target of \c a to \c n
-
-    /// Change the target of \c a to \c n
-    ///
-    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
-    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
-    ///invalidated.
+    /// Change the target node of an arc
+
+    /// This function changes the target node of the given arc \c a to \c n.
+    ///
+    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
+    ///arc remain valid, however \c InArcIt iterators are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
@@ -406,11 +399,10 @@
       Parent::changeTarget(a,n);
     }
-    /// Change the source of \c a to \c n
-
-    /// Change the source of \c a to \c n
-    ///
-    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
-    ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
-    ///invalidated.
+    /// Change the source node of an arc
+
+    /// This function changes the source node of the given arc \c a to \c n.
+    ///
+    ///\note \c InArcIt iterators referencing the changed arc remain
+    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
@@ -420,92 +412,74 @@
     }
 
-    /// Invert the direction of an arc.
-
-    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
-    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
-    ///invalidated.
+    /// Reverse the direction of an arc.
+
+    /// This function reverses the direction of the given arc.
+    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
+    ///the changed arc are invalidated.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void reverseArc(Arc e) {
-      Node t=target(e);
-      changeTarget(e,source(e));
-      changeSource(e,t);
-    }
-
-    /// Reserve memory for nodes.
-
-    /// Using this function it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveArc
-    void reserveNode(int n) { nodes.reserve(n); };
-
-    /// Reserve memory for arcs.
-
-    /// Using this function it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveNode
-    void reserveArc(int m) { arcs.reserve(m); };
+    void reverseArc(Arc a) {
+      Node t=target(a);
+      changeTarget(a,source(a));
+      changeSource(a,t);
+    }
 
     ///Contract two nodes.
 
-    ///This function contracts two nodes.
-    ///Node \p b will be removed but instead of deleting
-    ///incident arcs, they will be joined to \p a.
-    ///The last parameter \p r controls whether to remove loops. \c true
-    ///means that loops will be removed.
-    ///
-    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
-    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
-    ///may be invalidated.
+    ///This function contracts the given two nodes.
+    ///Node \c v is removed, but instead of deleting its
+    ///incident arcs, they are joined to node \c u.
+    ///If the last parameter \c r is \c true (this is the default value),
+    ///then the newly created loops are removed.
+    ///
+    ///\note The moved arcs are joined to node \c u using changeSource()
+    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
+    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
+    ///iterators are invalidated for the incomming arcs of \c v.
+    ///Moreover all iterators referencing node \c v or the removed 
+    ///loops are also invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
-    void contract(Node a, Node b, bool r = true)
+    void contract(Node u, Node v, bool r = true)
     {
-      for(OutArcIt e(*this,b);e!=INVALID;) {
+      for(OutArcIt e(*this,v);e!=INVALID;) {
         OutArcIt f=e;
         ++f;
-        if(r && target(e)==a) erase(e);
-        else changeSource(e,a);
+        if(r && target(e)==u) erase(e);
+        else changeSource(e,u);
         e=f;
       }
-      for(InArcIt e(*this,b);e!=INVALID;) {
+      for(InArcIt e(*this,v);e!=INVALID;) {
         InArcIt f=e;
         ++f;
-        if(r && source(e)==a) erase(e);
-        else changeTarget(e,a);
+        if(r && source(e)==u) erase(e);
+        else changeTarget(e,u);
         e=f;
       }
-      erase(b);
+      erase(v);
     }
 
     ///Split a node.
 
-    ///This function splits a node. First a new node is added to the digraph,
-    ///then the source of each outgoing arc of \c n is moved to this new node.
-    ///If \c connect is \c true (this is the default value), then a new arc
-    ///from \c n to the newly created node is also added.
+    ///This function splits the given node. First, a new node is added
+    ///to the digraph, then the source of each outgoing arc of node \c n
+    ///is moved to this new node.
+    ///If the second parameter \c connect is \c true (this is the default
+    ///value), then a new arc from node \c n to the newly created node
+    ///is also added.
     ///\return The newly created node.
     ///
-    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
-    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
-    ///be invalidated.
-    ///
-    ///\warning This functionality cannot be used in conjunction with the
+    ///\note All iterators remain valid.
+    ///
+    ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
     Node split(Node n, bool connect = true) {
       Node b = addNode();
-      for(OutArcIt e(*this,n);e!=INVALID;) {
-        OutArcIt f=e;
-        ++f;
-        changeSource(e,b);
-        e=f;
+      nodes[b.id].first_out=nodes[n.id].first_out;
+      nodes[n.id].first_out=-1;
+      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
+        arcs[i].source=b.id;
       }
       if (connect) addArc(n,b);
@@ -515,18 +489,49 @@
     ///Split an arc.
 
-    ///This function splits an arc. First a new node \c b is added to
-    ///the digraph, then the original arc is re-targeted to \c
-    ///b. Finally an arc from \c b to the original target is added.
-    ///
+    ///This function splits the given arc. First, a new node \c v is
+    ///added to the digraph, then the target node of the original arc
+    ///is set to \c v. Finally, an arc from \c v to the original target
+    ///is added.
     ///\return The newly created node.
+    ///
+    ///\note \c InArcIt iterators referencing the original arc are
+    ///invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the
     ///Snapshot feature.
-    Node split(Arc e) {
-      Node b = addNode();
-      addArc(b,target(e));
-      changeTarget(e,b);
-      return b;
-    }
+    Node split(Arc a) {
+      Node v = addNode();
+      addArc(v,target(a));
+      changeTarget(a,v);
+      return v;
+    }
+
+    ///Clear the digraph.
+
+    ///This function erases all nodes and arcs from the digraph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveArc()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for arcs.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveNode()
+    void reserveArc(int m) { arcs.reserve(m); };
 
     /// \brief Class to make a snapshot of the digraph and restore
@@ -538,7 +543,13 @@
     /// restore() function.
     ///
-    /// \warning Arc and node deletions and other modifications (e.g.
-    /// contracting, splitting, reversing arcs or nodes) cannot be
+    /// \note After a state is restored, you cannot restore a later state, 
+    /// i.e. you cannot add the removed nodes and arcs again using
+    /// another Snapshot instance.
+    ///
+    /// \warning Node and arc deletions and other modifications (e.g.
+    /// reversing, contracting, splitting arcs or nodes) cannot be
     /// restored. These events invalidate the snapshot.
+    /// However the arcs and nodes that were added to the digraph after
+    /// making the current snapshot can be removed without invalidating it.
     class Snapshot {
     protected:
@@ -710,5 +721,5 @@
       ///
       /// Default constructor.
-      /// To actually make a snapshot you must call save().
+      /// You have to call save() to actually make a snapshot.
       Snapshot()
         : digraph(0), node_observer_proxy(*this),
@@ -717,30 +728,31 @@
       /// \brief Constructor that immediately makes a snapshot.
       ///
-      /// This constructor immediately makes a snapshot of the digraph.
-      /// \param _digraph The digraph we make a snapshot of.
-      Snapshot(ListDigraph &_digraph)
+      /// This constructor immediately makes a snapshot of the given digraph.
+      Snapshot(ListDigraph &gr)
         : node_observer_proxy(*this),
           arc_observer_proxy(*this) {
-        attach(_digraph);
+        attach(gr);
       }
 
       /// \brief Make a snapshot.
       ///
-      /// Make a snapshot of the digraph.
-      ///
-      /// This function can be called more than once. In case of a repeated
+      /// This function makes a snapshot of the given digraph.
+      /// It can be called more than once. In case of a repeated
       /// call, the previous snapshot gets lost.
-      /// \param _digraph The digraph we make the snapshot of.
-      void save(ListDigraph &_digraph) {
+      void save(ListDigraph &gr) {
         if (attached()) {
           detach();
           clear();
         }
-        attach(_digraph);
+        attach(gr);
       }
 
       /// \brief Undo the changes until the last snapshot.
-      //
-      /// Undo the changes until the last snapshot created by save().
+      ///
+      /// This function undos the changes until the last snapshot
+      /// created by save() or Snapshot(ListDigraph&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
@@ -756,7 +768,7 @@
       }
 
-      /// \brief Gives back true when the snapshot is valid.
+      /// \brief Returns \c true if the snapshot is valid.
       ///
-      /// Gives back true when the snapshot is valid.
+      /// This function returns \c true if the snapshot is valid.
       bool valid() const {
         return attached();
@@ -795,8 +807,4 @@
 
     typedef ListGraphBase Graph;
-
-    class Node;
-    class Arc;
-    class Edge;
 
     class Node {
@@ -848,6 +856,4 @@
       bool operator<(const Arc& arc) const {return id < arc.id;}
     };
-
-
 
     ListGraphBase()
@@ -1165,29 +1171,23 @@
   ///A general undirected graph structure.
 
-  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
-  ///implementation based on static linked lists that are stored in
+  ///\ref ListGraph is a versatile and fast undirected graph
+  ///implementation based on linked lists that are stored in
   ///\c std::vector structures.
   ///
-  ///It conforms to the \ref concepts::Graph "Graph concept" and it
-  ///also provides several useful additional functionalities.
-  ///Most of the member functions and nested classes are documented
+  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
+  ///and it also provides several useful additional functionalities.
+  ///Most of its member functions and nested classes are documented
   ///only in the concept class.
   ///
   ///\sa concepts::Graph
-
+  ///\sa ListDigraph
   class ListGraph : public ExtendedListGraphBase {
     typedef ExtendedListGraphBase Parent;
 
   private:
-    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
-
-    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
-    ///
+    /// Graphs are \e not copy constructible. Use GraphCopy instead.
     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
-    ///\brief Assignment of ListGraph to another one is \e not allowed.
-    ///Use copyGraph() instead.
-
-    ///Assignment of ListGraph to another one is \e not allowed.
-    ///Use copyGraph() instead.
+    /// \brief Assignment of a graph to another one is \e not allowed.
+    /// Use GraphCopy instead.
     void operator=(const ListGraph &) {}
   public:
@@ -1202,5 +1202,5 @@
     /// \brief Add a new node to the graph.
     ///
-    /// Add a new node to the graph.
+    /// This function adds a new node to the graph.
     /// \return The new node.
     Node addNode() { return Parent::addNode(); }
@@ -1208,57 +1208,53 @@
     /// \brief Add a new edge to the graph.
     ///
-    /// Add a new edge to the graph with source node \c s
-    /// and target node \c t.
+    /// This function adds a new edge to the graph between nodes
+    /// \c u and \c v with inherent orientation from node \c u to
+    /// node \c v.
     /// \return The new edge.
-    Edge addEdge(const Node& s, const Node& t) {
-      return Parent::addEdge(s, t);
-    }
-
-    /// \brief Erase a node from the graph.
-    ///
-    /// Erase a node from the graph.
-    ///
-    void erase(const Node& n) { Parent::erase(n); }
-
-    /// \brief Erase an edge from the graph.
-    ///
-    /// Erase an edge from the graph.
-    ///
-    void erase(const Edge& e) { Parent::erase(e); }
+    Edge addEdge(Node u, Node v) {
+      return Parent::addEdge(u, v);
+    }
+
+    ///\brief Erase a node from the graph.
+    ///
+    /// This function erases the given node from the graph.
+    void erase(Node n) { Parent::erase(n); }
+
+    ///\brief Erase an edge from the graph.
+    ///
+    /// This function erases the given edge from the graph.
+    void erase(Edge e) { Parent::erase(e); }
     /// Node validity check
 
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
-    ///
-    /// \warning A Node pointing to a removed item
-    /// could become valid again later if new nodes are
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the graph.
+    ///
+    /// \warning A removed node could become valid again if new nodes are
     /// added to the graph.
     bool valid(Node n) const { return Parent::valid(n); }
+    /// Edge validity check
+
+    /// This function gives back \c true if the given edge is valid,
+    /// i.e. it is a real edge of the graph.
+    ///
+    /// \warning A removed edge could become valid again if new edges are
+    /// added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
     /// Arc validity check
 
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning An Arc pointing to a removed item
-    /// could become valid again later if new edges are
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the graph.
+    ///
+    /// \warning A removed arc could become valid again if new edges are
     /// added to the graph.
     bool valid(Arc a) const { return Parent::valid(a); }
-    /// Edge validity check
-
-    /// This function gives back true if the given edge is valid,
-    /// ie. it is a real arc of the graph.
-    ///
-    /// \warning A Edge pointing to a removed item
-    /// could become valid again later if new edges are
-    /// added to the graph.
-    bool valid(Edge e) const { return Parent::valid(e); }
-    /// \brief Change the end \c u of \c e to \c n
-    ///
-    /// This function changes the end \c u of \c e to node \c n.
-    ///
-    ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
-    ///changed edge are invalidated and if the changed node is the
-    ///base node of an iterator then this iterator is also
-    ///invalidated.
+
+    /// \brief Change the first node of an edge.
+    ///
+    /// This function changes the first node of the given edge \c e to \c n.
+    ///
+    ///\note \c EdgeIt and \c ArcIt iterators referencing the
+    ///changed edge are invalidated and all other iterators whose
+    ///base node is the changed node are also invalidated.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1267,11 +1263,12 @@
       Parent::changeU(e,n);
     }
-    /// \brief Change the end \c v of \c e to \c n
-    ///
-    /// This function changes the end \c v of \c e to \c n.
-    ///
-    ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
-    ///valid, however <tt>ArcIt</tt>s and if the changed node is the
-    ///base node of an iterator then this iterator is invalidated.
+    /// \brief Change the second node of an edge.
+    ///
+    /// This function changes the second node of the given edge \c e to \c n.
+    ///
+    ///\note \c EdgeIt iterators referencing the changed edge remain
+    ///valid, however \c ArcIt iterators referencing the changed edge and
+    ///all other iterators whose base node is the changed node are also
+    ///invalidated.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1280,14 +1277,18 @@
       Parent::changeV(e,n);
     }
+
     /// \brief Contract two nodes.
     ///
-    /// This function contracts two nodes.
-    /// Node \p b will be removed but instead of deleting
-    /// its neighboring arcs, they will be joined to \p a.
-    /// The last parameter \p r controls whether to remove loops. \c true
-    /// means that loops will be removed.
-    ///
-    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
-    /// valid.
+    /// This function contracts the given two nodes.
+    /// Node \c b is removed, but instead of deleting
+    /// its incident edges, they are joined to node \c a.
+    /// If the last parameter \c r is \c true (this is the default value),
+    /// then the newly created loops are removed.
+    ///
+    /// \note The moved edges are joined to node \c a using changeU()
+    /// or changeV(), thus all edge and arc iterators whose base node is
+    /// \c b are invalidated.
+    /// Moreover all iterators referencing node \c b or the removed 
+    /// loops are also invalidated. Other iterators remain valid.
     ///
     ///\warning This functionality cannot be used together with the
@@ -1308,4 +1309,31 @@
     }
 
+    ///Clear the graph.
+
+    ///This function erases all nodes and arcs from the graph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for edges.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
 
     /// \brief Class to make a snapshot of the graph and restore
@@ -1317,7 +1345,13 @@
     /// using the restore() function.
     ///
-    /// \warning Edge and node deletions and other modifications
-    /// (e.g. changing nodes of edges, contracting nodes) cannot be
-    /// restored. These events invalidate the snapshot.
+    /// \note After a state is restored, you cannot restore a later state, 
+    /// i.e. you cannot add the removed nodes and edges again using
+    /// another Snapshot instance.
+    ///
+    /// \warning Node and edge deletions and other modifications
+    /// (e.g. changing the end-nodes of edges or contracting nodes)
+    /// cannot be restored. These events invalidate the snapshot.
+    /// However the edges and nodes that were added to the graph after
+    /// making the current snapshot can be removed without invalidating it.
     class Snapshot {
     protected:
@@ -1489,5 +1523,5 @@
       ///
       /// Default constructor.
-      /// To actually make a snapshot you must call save().
+      /// You have to call save() to actually make a snapshot.
       Snapshot()
         : graph(0), node_observer_proxy(*this),
@@ -1496,30 +1530,31 @@
       /// \brief Constructor that immediately makes a snapshot.
       ///
-      /// This constructor immediately makes a snapshot of the graph.
-      /// \param _graph The graph we make a snapshot of.
-      Snapshot(ListGraph &_graph)
+      /// This constructor immediately makes a snapshot of the given graph.
+      Snapshot(ListGraph &gr)
         : node_observer_proxy(*this),
           edge_observer_proxy(*this) {
-        attach(_graph);
+        attach(gr);
       }
 
       /// \brief Make a snapshot.
       ///
-      /// Make a snapshot of the graph.
-      ///
-      /// This function can be called more than once. In case of a repeated
+      /// This function makes a snapshot of the given graph.
+      /// It can be called more than once. In case of a repeated
       /// call, the previous snapshot gets lost.
-      /// \param _graph The graph we make the snapshot of.
-      void save(ListGraph &_graph) {
+      void save(ListGraph &gr) {
         if (attached()) {
           detach();
           clear();
         }
-        attach(_graph);
+        attach(gr);
       }
 
       /// \brief Undo the changes until the last snapshot.
-      //
-      /// Undo the changes until the last snapshot created by save().
+      ///
+      /// This function undos the changes until the last snapshot
+      /// created by save() or Snapshot(ListGraph&).
+      ///
+      /// \warning This method invalidates the snapshot, i.e. repeated
+      /// restoring is not supported unless you call save() again.
       void restore() {
         detach();
@@ -1535,7 +1570,7 @@
       }
 
-      /// \brief Gives back true when the snapshot is valid.
+      /// \brief Returns \c true if the snapshot is valid.
       ///
-      /// Gives back true when the snapshot is valid.
+      /// This function returns \c true if the snapshot is valid.
       bool valid() const {
         return attached();
Index: lemon/lp_base.h
===================================================================
--- lemon/lp_base.h	(revision 631)
+++ lemon/lp_base.h	(revision 793)
@@ -944,4 +944,12 @@
     virtual int _addRow() = 0;
 
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+      int row = _addRow();
+      _setRowCoeffs(row, b, e);
+      _setRowLowerBound(row, l);
+      _setRowUpperBound(row, u);
+      return row;
+    }
+
     virtual void _eraseCol(int col) = 0;
     virtual void _eraseRow(int row) = 0;
@@ -1208,6 +1216,8 @@
     ///\return The created row.
     Row addRow(Value l,const Expr &e, Value u) {
-      Row r=addRow();
-      row(r,l,e,u);
+      Row r;
+      e.simplify();
+      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
+                                ExprIterator(e.comps.end(), cols), u - *e));
       return r;
     }
@@ -1218,6 +1228,10 @@
     ///\return The created row.
     Row addRow(const Constr &c) {
-      Row r=addRow();
-      row(r,c);
+      Row r;
+      c.expr().simplify();
+      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF, 
+                                ExprIterator(c.expr().comps.begin(), cols),
+                                ExprIterator(c.expr().comps.end(), cols),
+                                c.upperBounded()?c.upperBound():INF));
       return r;
     }
Index: lemon/lp_skeleton.cc
===================================================================
--- lemon/lp_skeleton.cc	(revision 623)
+++ lemon/lp_skeleton.cc	(revision 793)
@@ -29,4 +29,9 @@
 
   int SkeletonSolverBase::_addRow()
+  {
+    return ++row_num;
+  }
+
+  int SkeletonSolverBase::_addRow(Value, ExprIterator, ExprIterator, Value)
   {
     return ++row_num;
Index: lemon/lp_skeleton.h
===================================================================
--- lemon/lp_skeleton.h	(revision 623)
+++ lemon/lp_skeleton.h	(revision 793)
@@ -45,4 +45,6 @@
     /// \e
     virtual int _addRow();
+    /// \e
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
     /// \e
     virtual void _eraseCol(int i);
Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 777)
+++ lemon/network_simplex.h	(revision 802)
@@ -41,5 +41,7 @@
   ///
   /// \ref NetworkSimplex implements the primal Network Simplex algorithm
-  /// for finding a \ref min_cost_flow "minimum cost flow".
+  /// for finding a \ref min_cost_flow "minimum cost flow"
+  /// \ref amo93networkflows, \ref dantzig63linearprog,
+  /// \ref kellyoneill91netsimplex.
   /// This algorithm is a specialized version of the linear programming
   /// simplex method directly for the minimum cost flow problem.
Index: lemon/path.h
===================================================================
--- lemon/path.h	(revision 606)
+++ lemon/path.h	(revision 798)
@@ -1016,16 +1016,18 @@
   /// \brief The source of a path
   ///
-  /// This function returns the source of the given path.
+  /// This function returns the source node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
-    return digraph.source(path.front());
+    return path.empty() ? INVALID : digraph.source(path.front());
   }
 
   /// \brief The target of a path
   ///
-  /// This function returns the target of the given path.
+  /// This function returns the target node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
-    return digraph.target(path.back());
+    return path.empty() ? INVALID : digraph.target(path.back());
   }
 
Index: lemon/preflow.h
===================================================================
--- lemon/preflow.h	(revision 762)
+++ lemon/preflow.h	(revision 802)
@@ -103,5 +103,6 @@
   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   /// \e push-relabel algorithm producing a \ref max_flow
-  /// "flow of maximum value" in a digraph.
+  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
+  /// \ref amo93networkflows, \ref goldberg88newapproach.
   /// The preflow algorithms are the fastest known maximum
   /// flow algorithms. The current implementation uses a mixture of the
Index: lemon/smart_graph.h
===================================================================
--- lemon/smart_graph.h	(revision 664)
+++ lemon/smart_graph.h	(revision 827)
@@ -33,8 +33,5 @@
 
   class SmartDigraph;
-  ///Base of SmartDigraph
-
-  ///Base of SmartDigraph
-  ///
+
   class SmartDigraphBase {
   protected:
@@ -188,26 +185,24 @@
   ///\brief A smart directed graph class.
   ///
-  ///This is a simple and fast digraph implementation.
-  ///It is also quite memory efficient, but at the price
-  ///that <b> it does support only limited (only stack-like)
-  ///node and arc deletions</b>.
-  ///It fully conforms to the \ref concepts::Digraph "Digraph concept".
+  ///\ref SmartDigraph is a simple and fast digraph implementation.
+  ///It is also quite memory efficient but at the price
+  ///that it does not support node and arc deletion 
+  ///(except for the Snapshot feature).
   ///
-  ///\sa concepts::Digraph.
+  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
+  ///and it also provides some additional functionalities.
+  ///Most of its member functions and nested classes are documented
+  ///only in the concept class.
+  ///
+  ///\sa concepts::Digraph
+  ///\sa SmartGraph
   class SmartDigraph : public ExtendedSmartDigraphBase {
     typedef ExtendedSmartDigraphBase Parent;
 
   private:
-
-    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
-
-    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.
-    ///
+    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
     SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};
-    ///\brief Assignment of SmartDigraph to another one is \e not allowed.
-    ///Use DigraphCopy() instead.
-
-    ///Assignment of SmartDigraph to another one is \e not allowed.
-    ///Use DigraphCopy() instead.
+    /// \brief Assignment of a digraph to another one is \e not allowed.
+    /// Use DigraphCopy instead.
     void operator=(const SmartDigraph &) {}
 
@@ -222,77 +217,47 @@
     ///Add a new node to the digraph.
 
-    /// Add a new node to the digraph.
-    /// \return The new node.
+    ///This function adds a new node to the digraph.
+    ///\return The new node.
     Node addNode() { return Parent::addNode(); }
 
     ///Add a new arc to the digraph.
 
-    ///Add a new arc to the digraph with source node \c s
+    ///This function adds a new arc to the digraph with source node \c s
     ///and target node \c t.
     ///\return The new arc.
-    Arc addArc(const Node& s, const Node& t) {
+    Arc addArc(Node s, Node t) {
       return Parent::addArc(s, t);
     }
 
-    /// \brief Using this it is possible to avoid the superfluous memory
-    /// allocation.
-
-    /// Using this it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveArc
-    void reserveNode(int n) { nodes.reserve(n); };
-
-    /// \brief Using this it is possible to avoid the superfluous memory
-    /// allocation.
-
-    /// Using this it is possible to avoid the superfluous memory
-    /// allocation: if you know that the digraph you want to build will
-    /// be very large (e.g. it will contain millions of nodes and/or arcs)
-    /// then it is worth reserving space for this amount before starting
-    /// to build the digraph.
-    /// \sa reserveNode
-    void reserveArc(int m) { arcs.reserve(m); };
-
     /// \brief Node validity check
     ///
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the digraph.
     ///
     /// \warning A removed node (using Snapshot) could become valid again
-    /// when new nodes are added to the graph.
+    /// if new nodes are added to the digraph.
     bool valid(Node n) const { return Parent::valid(n); }
 
     /// \brief Arc validity check
     ///
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the digraph.
     ///
     /// \warning A removed arc (using Snapshot) could become valid again
-    /// when new arcs are added to the graph.
+    /// if new arcs are added to the graph.
     bool valid(Arc a) const { return Parent::valid(a); }
 
-    ///Clear the digraph.
-
-    ///Erase all the nodes and arcs from the digraph.
-    ///
-    void clear() {
-      Parent::clear();
-    }
-
     ///Split a node.
 
-    ///This function splits a node. First a new node is added to the digraph,
-    ///then the source of each outgoing arc of \c n is moved to this new node.
-    ///If \c connect is \c true (this is the default value), then a new arc
-    ///from \c n to the newly created node is also added.
+    ///This function splits the given node. First, a new node is added
+    ///to the digraph, then the source of each outgoing arc of node \c n
+    ///is moved to this new node.
+    ///If the second parameter \c connect is \c true (this is the default
+    ///value), then a new arc from node \c n to the newly created node
+    ///is also added.
     ///\return The newly created node.
     ///
-    ///\note The <tt>Arc</tt>s
-    ///referencing a moved arc remain
-    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s
-    ///may be invalidated.
+    ///\note All iterators remain valid.
+    ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
@@ -309,4 +274,32 @@
     }
 
+    ///Clear the digraph.
+
+    ///This function erases all nodes and arcs from the digraph.
+    ///
+    void clear() {
+      Parent::clear();
+    }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveArc()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for arcs.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the digraph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or arcs),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the digraph.
+    /// \sa reserveNode()
+    void reserveArc(int m) { arcs.reserve(m); };
+
   public:
 
@@ -333,18 +326,21 @@
   public:
 
-    ///Class to make a snapshot of the digraph and to restrore to it later.
-
-    ///Class to make a snapshot of the digraph and to restrore to it later.
+    ///Class to make a snapshot of the digraph and to restore it later.
+
+    ///Class to make a snapshot of the digraph and to restore it later.
     ///
     ///The newly added nodes and arcs can be removed using the
-    ///restore() function.
-    ///\note After you restore a state, you cannot restore
-    ///a later state, in other word you cannot add again the arcs deleted
-    ///by restore() using another one Snapshot instance.
-    ///
-    ///\warning If you do not use correctly the snapshot that can cause
-    ///either broken program, invalid state of the digraph, valid but
-    ///not the restored digraph or no change. Because the runtime performance
-    ///the validity of the snapshot is not stored.
+    ///restore() function. This is the only way for deleting nodes and/or
+    ///arcs from a SmartDigraph structure.
+    ///
+    ///\note After a state is restored, you cannot restore a later state, 
+    ///i.e. you cannot add the removed nodes and arcs again using
+    ///another Snapshot instance.
+    ///
+    ///\warning Node splitting cannot be restored.
+    ///\warning The validity of the snapshot is not stored due to
+    ///performance reasons. If you do not use the snapshot correctly,
+    ///it can cause broken program, invalid or not restored state of
+    ///the digraph or no change.
     class Snapshot
     {
@@ -358,12 +354,11 @@
 
       ///Default constructor.
-      ///To actually make a snapshot you must call save().
-      ///
+      ///You have to call save() to actually make a snapshot.
       Snapshot() : _graph(0) {}
       ///Constructor that immediately makes a snapshot
 
-      ///This constructor immediately makes a snapshot of the digraph.
-      ///\param graph The digraph we make a snapshot of.
-      Snapshot(SmartDigraph &graph) : _graph(&graph) {
+      ///This constructor immediately makes a snapshot of the given digraph.
+      ///
+      Snapshot(SmartDigraph &gr) : _graph(&gr) {
         node_num=_graph->nodes.size();
         arc_num=_graph->arcs.size();
@@ -372,12 +367,9 @@
       ///Make a snapshot.
 
-      ///Make a snapshot of the digraph.
-      ///
-      ///This function can be called more than once. In case of a repeated
+      ///This function makes a snapshot of the given digraph.
+      ///It can be called more than once. In case of a repeated
       ///call, the previous snapshot gets lost.
-      ///\param graph The digraph we make the snapshot of.
-      void save(SmartDigraph &graph)
-      {
-        _graph=&graph;
+      void save(SmartDigraph &gr) {
+        _graph=&gr;
         node_num=_graph->nodes.size();
         arc_num=_graph->arcs.size();
@@ -386,9 +378,6 @@
       ///Undo the changes until a snapshot.
 
-      ///Undo the changes until a snapshot created by save().
-      ///
-      ///\note After you restored a state, you cannot restore
-      ///a later state, in other word you cannot add again the arcs deleted
-      ///by restore().
+      ///This function undos the changes until the last snapshot
+      ///created by save() or Snapshot(SmartDigraph&).
       void restore()
       {
@@ -509,5 +498,5 @@
     }
 
-    void next(Node& node) const {
+    static void next(Node& node) {
       --node._id;
     }
@@ -517,5 +506,5 @@
     }
 
-    void next(Arc& arc) const {
+    static void next(Arc& arc) {
       --arc._id;
     }
@@ -525,5 +514,5 @@
     }
 
-    void next(Edge& arc) const {
+    static void next(Edge& arc) {
       --arc._id;
     }
@@ -622,27 +611,24 @@
   /// \brief A smart undirected graph class.
   ///
-  /// This is a simple and fast graph implementation.
-  /// It is also quite memory efficient, but at the price
-  /// that <b> it does support only limited (only stack-like)
-  /// node and arc deletions</b>.
-  /// It fully conforms to the \ref concepts::Graph "Graph concept".
+  /// \ref SmartGraph is a simple and fast graph implementation.
+  /// It is also quite memory efficient but at the price
+  /// that it does not support node and edge deletion 
+  /// (except for the Snapshot feature).
   ///
-  /// \sa concepts::Graph.
+  /// This type fully conforms to the \ref concepts::Graph "Graph concept"
+  /// and it also provides some additional functionalities.
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// \sa concepts::Graph
+  /// \sa SmartDigraph
   class SmartGraph : public ExtendedSmartGraphBase {
     typedef ExtendedSmartGraphBase Parent;
 
   private:
-
-    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
-
-    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
-    ///
+    /// Graphs are \e not copy constructible. Use GraphCopy instead.
     SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
-
-    ///\brief Assignment of SmartGraph to another one is \e not allowed.
-    ///Use GraphCopy() instead.
-
-    ///Assignment of SmartGraph to another one is \e not allowed.
-    ///Use GraphCopy() instead.
+    /// \brief Assignment of a graph to another one is \e not allowed.
+    /// Use GraphCopy instead.
     void operator=(const SmartGraph &) {}
 
@@ -655,53 +641,74 @@
     SmartGraph() {}
 
-    ///Add a new node to the graph.
-
-    /// Add a new node to the graph.
+    /// \brief Add a new node to the graph.
+    ///
+    /// This function adds a new node to the graph.
     /// \return The new node.
     Node addNode() { return Parent::addNode(); }
 
-    ///Add a new edge to the graph.
-
-    ///Add a new edge to the graph with node \c s
-    ///and \c t.
-    ///\return The new edge.
-    Edge addEdge(const Node& s, const Node& t) {
-      return Parent::addEdge(s, t);
+    /// \brief Add a new edge to the graph.
+    ///
+    /// This function adds a new edge to the graph between nodes
+    /// \c u and \c v with inherent orientation from node \c u to
+    /// node \c v.
+    /// \return The new edge.
+    Edge addEdge(Node u, Node v) {
+      return Parent::addEdge(u, v);
     }
 
     /// \brief Node validity check
     ///
-    /// This function gives back true if the given node is valid,
-    /// ie. it is a real node of the graph.
+    /// This function gives back \c true if the given node is valid,
+    /// i.e. it is a real node of the graph.
     ///
     /// \warning A removed node (using Snapshot) could become valid again
-    /// when new nodes are added to the graph.
+    /// if new nodes are added to the graph.
     bool valid(Node n) const { return Parent::valid(n); }
 
+    /// \brief Edge validity check
+    ///
+    /// This function gives back \c true if the given edge is valid,
+    /// i.e. it is a real edge of the graph.
+    ///
+    /// \warning A removed edge (using Snapshot) could become valid again
+    /// if new edges are added to the graph.
+    bool valid(Edge e) const { return Parent::valid(e); }
+
     /// \brief Arc validity check
     ///
-    /// This function gives back true if the given arc is valid,
-    /// ie. it is a real arc of the graph.
+    /// This function gives back \c true if the given arc is valid,
+    /// i.e. it is a real arc of the graph.
     ///
     /// \warning A removed arc (using Snapshot) could become valid again
-    /// when new edges are added to the graph.
+    /// if new edges are added to the graph.
     bool valid(Arc a) const { return Parent::valid(a); }
 
-    /// \brief Edge validity check
-    ///
-    /// This function gives back true if the given edge is valid,
-    /// ie. it is a real edge of the graph.
-    ///
-    /// \warning A removed edge (using Snapshot) could become valid again
-    /// when new edges are added to the graph.
-    bool valid(Edge e) const { return Parent::valid(e); }
-
     ///Clear the graph.
 
-    ///Erase all the nodes and edges from the graph.
+    ///This function erases all nodes and arcs from the graph.
     ///
     void clear() {
       Parent::clear();
     }
+
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for edges.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
 
   public:
@@ -743,19 +750,20 @@
   public:
 
-    ///Class to make a snapshot of the digraph and to restrore to it later.
-
-    ///Class to make a snapshot of the digraph and to restrore to it later.
-    ///
-    ///The newly added nodes and arcs can be removed using the
-    ///restore() function.
-    ///
-    ///\note After you restore a state, you cannot restore
-    ///a later state, in other word you cannot add again the arcs deleted
-    ///by restore() using another one Snapshot instance.
-    ///
-    ///\warning If you do not use correctly the snapshot that can cause
-    ///either broken program, invalid state of the digraph, valid but
-    ///not the restored digraph or no change. Because the runtime performance
-    ///the validity of the snapshot is not stored.
+    ///Class to make a snapshot of the graph and to restore it later.
+
+    ///Class to make a snapshot of the graph and to restore it later.
+    ///
+    ///The newly added nodes and edges can be removed using the
+    ///restore() function. This is the only way for deleting nodes and/or
+    ///edges from a SmartGraph structure.
+    ///
+    ///\note After a state is restored, you cannot restore a later state, 
+    ///i.e. you cannot add the removed nodes and edges again using
+    ///another Snapshot instance.
+    ///
+    ///\warning The validity of the snapshot is not stored due to
+    ///performance reasons. If you do not use the snapshot correctly,
+    ///it can cause broken program, invalid or not restored state of
+    ///the graph or no change.
     class Snapshot
     {
@@ -769,34 +777,28 @@
 
       ///Default constructor.
-      ///To actually make a snapshot you must call save().
-      ///
+      ///You have to call save() to actually make a snapshot.
       Snapshot() : _graph(0) {}
       ///Constructor that immediately makes a snapshot
 
-      ///This constructor immediately makes a snapshot of the digraph.
-      ///\param graph The digraph we make a snapshot of.
-      Snapshot(SmartGraph &graph) {
-        graph.saveSnapshot(*this);
+      /// This constructor immediately makes a snapshot of the given graph.
+      ///
+      Snapshot(SmartGraph &gr) {
+        gr.saveSnapshot(*this);
       }
 
       ///Make a snapshot.
 
-      ///Make a snapshot of the graph.
-      ///
-      ///This function can be called more than once. In case of a repeated
+      ///This function makes a snapshot of the given graph.
+      ///It can be called more than once. In case of a repeated
       ///call, the previous snapshot gets lost.
-      ///\param graph The digraph we make the snapshot of.
-      void save(SmartGraph &graph)
+      void save(SmartGraph &gr)
       {
-        graph.saveSnapshot(*this);
-      }
-
-      ///Undo the changes until a snapshot.
-
-      ///Undo the changes until a snapshot created by save().
-      ///
-      ///\note After you restored a state, you cannot restore
-      ///a later state, in other word you cannot add again the arcs deleted
-      ///by restore().
+        gr.saveSnapshot(*this);
+      }
+
+      ///Undo the changes until the last snapshot.
+
+      ///This function undos the changes until the last snapshot
+      ///created by save() or Snapshot(SmartGraph&).
       void restore()
       {
Index: lemon/soplex.cc
===================================================================
--- lemon/soplex.cc	(revision 623)
+++ lemon/soplex.cc	(revision 793)
@@ -92,4 +92,17 @@
   }
 
+  int SoplexLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
+    soplex::DSVector v;
+    for (ExprIterator it = b; it != e; ++it) {
+      v.add(it->first, it->second);
+    }
+    soplex::LPRow r(l, v, u);
+    soplex->addRow(r);
+
+    _row_names.push_back(std::string());
+
+    return soplex->nRows() - 1;
+  }
+
 
   void SoplexLp::_eraseCol(int i) {
Index: lemon/soplex.h
===================================================================
--- lemon/soplex.h	(revision 623)
+++ lemon/soplex.h	(revision 793)
@@ -85,4 +85,5 @@
     virtual int _addCol();
     virtual int _addRow();
+    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
 
     virtual void _eraseCol(int i);
Index: lemon/static_graph.h
===================================================================
--- lemon/static_graph.h	(revision 826)
+++ lemon/static_graph.h	(revision 826)
@@ -0,0 +1,474 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_STATIC_GRAPH_H
+#define LEMON_STATIC_GRAPH_H
+
+///\ingroup graphs
+///\file
+///\brief StaticDigraph class.
+
+#include <lemon/core.h>
+#include <lemon/bits/graph_extender.h>
+
+namespace lemon {
+
+  class StaticDigraphBase {
+  public:
+
+    StaticDigraphBase() 
+      : built(false), node_num(0), arc_num(0), 
+        node_first_out(NULL), node_first_in(NULL),
+        arc_source(NULL), arc_target(NULL), 
+        arc_next_in(NULL), arc_next_out(NULL) {}
+    
+    ~StaticDigraphBase() {
+      if (built) {
+        delete[] node_first_out;
+        delete[] node_first_in;
+        delete[] arc_source;
+        delete[] arc_target;
+        delete[] arc_next_out;
+        delete[] arc_next_in;
+      }
+    }
+
+    class Node {
+      friend class StaticDigraphBase;
+    protected:
+      int id;
+      Node(int _id) : id(_id) {}
+    public:
+      Node() {}
+      Node (Invalid) : id(-1) {}
+      bool operator==(const Node& node) const { return id == node.id; }
+      bool operator!=(const Node& node) const { return id != node.id; }
+      bool operator<(const Node& node) const { return id < node.id; }
+    };
+
+    class Arc {
+      friend class StaticDigraphBase;      
+    protected:
+      int id;
+      Arc(int _id) : id(_id) {}
+    public:
+      Arc() { }
+      Arc (Invalid) : id(-1) {}
+      bool operator==(const Arc& arc) const { return id == arc.id; }
+      bool operator!=(const Arc& arc) const { return id != arc.id; }
+      bool operator<(const Arc& arc) const { return id < arc.id; }
+    };
+
+    Node source(const Arc& e) const { return Node(arc_source[e.id]); }
+    Node target(const Arc& e) const { return Node(arc_target[e.id]); }
+
+    void first(Node& n) const { n.id = node_num - 1; }
+    static void next(Node& n) { --n.id; }
+
+    void first(Arc& e) const { e.id = arc_num - 1; }
+    static void next(Arc& e) { --e.id; }
+
+    void firstOut(Arc& e, const Node& n) const { 
+      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? 
+        node_first_out[n.id] : -1;
+    }
+    void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
+
+    void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
+    void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
+
+    static int id(const Node& n) { return n.id; }
+    static Node nodeFromId(int id) { return Node(id); }
+    int maxNodeId() const { return node_num - 1; }
+
+    static int id(const Arc& e) { return e.id; }
+    static Arc arcFromId(int id) { return Arc(id); }
+    int maxArcId() const { return arc_num - 1; }
+
+    typedef True NodeNumTag;
+    typedef True ArcNumTag;
+
+    int nodeNum() const { return node_num; }
+    int arcNum() const { return arc_num; }
+
+  private:
+
+    template <typename Digraph, typename NodeRefMap>
+    class ArcLess {
+    public:
+      typedef typename Digraph::Arc Arc;
+
+      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) 
+        : digraph(_graph), nodeRef(_nodeRef) {}
+      
+      bool operator()(const Arc& left, const Arc& right) const {
+	return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
+      }
+    private:
+      const Digraph& digraph;
+      const NodeRefMap& nodeRef;
+    };
+    
+  public:
+
+    typedef True BuildTag;
+    
+    void clear() {
+      if (built) {
+        delete[] node_first_out;
+        delete[] node_first_in;
+        delete[] arc_source;
+        delete[] arc_target;
+        delete[] arc_next_out;
+        delete[] arc_next_in;
+      }
+      built = false;
+      node_num = 0;
+      arc_num = 0;
+    }
+    
+    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
+    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
+      typedef typename Digraph::Node GNode;
+      typedef typename Digraph::Arc GArc;
+
+      built = true;
+
+      node_num = countNodes(digraph);
+      arc_num = countArcs(digraph);
+
+      node_first_out = new int[node_num + 1];
+      node_first_in = new int[node_num];
+
+      arc_source = new int[arc_num];
+      arc_target = new int[arc_num];
+      arc_next_out = new int[arc_num];
+      arc_next_in = new int[arc_num];
+
+      int node_index = 0;
+      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
+        nodeRef[n] = Node(node_index);
+        node_first_in[node_index] = -1;
+        ++node_index;
+      }
+
+      ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
+
+      int arc_index = 0;
+      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
+        int source = nodeRef[n].id;
+        std::vector<GArc> arcs;
+        for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
+          arcs.push_back(e);
+        }
+        if (!arcs.empty()) {
+          node_first_out[source] = arc_index;
+          std::sort(arcs.begin(), arcs.end(), arcLess);
+          for (typename std::vector<GArc>::iterator it = arcs.begin();
+               it != arcs.end(); ++it) {
+            int target = nodeRef[digraph.target(*it)].id;
+            arcRef[*it] = Arc(arc_index);
+            arc_source[arc_index] = source; 
+            arc_target[arc_index] = target;
+            arc_next_in[arc_index] = node_first_in[target];
+            node_first_in[target] = arc_index;
+            arc_next_out[arc_index] = arc_index + 1;
+            ++arc_index;
+          }
+          arc_next_out[arc_index - 1] = -1;
+        } else {
+          node_first_out[source] = arc_index;
+        }
+      }
+      node_first_out[node_num] = arc_num;
+    }
+    
+    template <typename ArcListIterator>
+    void build(int n, ArcListIterator first, ArcListIterator last) {
+      built = true;
+
+      node_num = n;
+      arc_num = std::distance(first, last);
+
+      node_first_out = new int[node_num + 1];
+      node_first_in = new int[node_num];
+
+      arc_source = new int[arc_num];
+      arc_target = new int[arc_num];
+      arc_next_out = new int[arc_num];
+      arc_next_in = new int[arc_num];
+      
+      for (int i = 0; i != node_num; ++i) {
+        node_first_in[i] = -1;
+      }      
+      
+      int arc_index = 0;
+      for (int i = 0; i != node_num; ++i) {
+        node_first_out[i] = arc_index;
+        for ( ; first != last && (*first).first == i; ++first) {
+          int j = (*first).second;
+          LEMON_ASSERT(j >= 0 && j < node_num,
+            "Wrong arc list for StaticDigraph::build()");
+          arc_source[arc_index] = i;
+          arc_target[arc_index] = j;
+          arc_next_in[arc_index] = node_first_in[j];
+          node_first_in[j] = arc_index;
+          arc_next_out[arc_index] = arc_index + 1;
+          ++arc_index;
+        }
+        if (arc_index > node_first_out[i])
+          arc_next_out[arc_index - 1] = -1;
+      }
+      LEMON_ASSERT(first == last,
+        "Wrong arc list for StaticDigraph::build()");
+      node_first_out[node_num] = arc_num;
+    }
+
+  protected:
+
+    void fastFirstOut(Arc& e, const Node& n) const {
+      e.id = node_first_out[n.id];
+    }
+
+    static void fastNextOut(Arc& e) {
+      ++e.id;
+    }
+    void fastLastOut(Arc& e, const Node& n) const {
+      e.id = node_first_out[n.id + 1];
+    }
+
+  protected:
+    bool built;
+    int node_num;
+    int arc_num;
+    int *node_first_out;
+    int *node_first_in;
+    int *arc_source;
+    int *arc_target;
+    int *arc_next_in;
+    int *arc_next_out;
+  };
+
+  typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
+
+
+  /// \ingroup graphs
+  ///
+  /// \brief A static directed graph class.
+  ///
+  /// \ref StaticDigraph is a highly efficient digraph implementation,
+  /// but it is fully static.
+  /// It stores only two \c int values for each node and only four \c int
+  /// values for each arc. Moreover it provides faster item iteration than
+  /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
+  /// iterators, since its arcs are stored in an appropriate order.
+  /// However it only provides build() and clear() functions and does not
+  /// support any other modification of the digraph.
+  ///
+  /// Since this digraph structure is completely static, its nodes and arcs
+  /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
+  /// and <tt>[0..arcNum()-1]</tt>, respectively. 
+  /// The index of an item is the same as its ID, it can be obtained
+  /// using the corresponding \ref index() or \ref concepts::Digraph::id()
+  /// "id()" function. A node or arc with a certain index can be obtained
+  /// using node() or arc().
+  ///
+  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
+  /// Most of its member functions and nested classes are documented
+  /// only in the concept class.
+  ///
+  /// \sa concepts::Digraph
+  class StaticDigraph : public ExtendedStaticDigraphBase {
+  public:
+
+    typedef ExtendedStaticDigraphBase Parent;
+  
+  public:
+  
+    /// \brief Constructor
+    ///
+    /// Default constructor.
+    StaticDigraph() : Parent() {}
+
+    /// \brief The node with the given index.
+    ///
+    /// This function returns the node with the given index.
+    /// \sa index()
+    static Node node(int ix) { return Parent::nodeFromId(ix); }
+
+    /// \brief The arc with the given index.
+    ///
+    /// This function returns the arc with the given index.
+    /// \sa index()
+    static Arc arc(int ix) { return Parent::arcFromId(ix); }
+
+    /// \brief The index of the given node.
+    ///
+    /// This function returns the index of the the given node.
+    /// \sa node()
+    static int index(Node node) { return Parent::id(node); }
+
+    /// \brief The index of the given arc.
+    ///
+    /// This function returns the index of the the given arc.
+    /// \sa arc()
+    static int index(Arc arc) { return Parent::id(arc); }
+
+    /// \brief Number of nodes.
+    ///
+    /// This function returns the number of nodes.
+    int nodeNum() const { return node_num; }
+
+    /// \brief Number of arcs.
+    ///
+    /// This function returns the number of arcs.
+    int arcNum() const { return arc_num; }
+
+    /// \brief Build the digraph copying another digraph.
+    ///
+    /// This function builds the digraph copying another digraph of any
+    /// kind. It can be called more than once, but in such case, the whole
+    /// structure and all maps will be cleared and rebuilt.
+    ///
+    /// This method also makes possible to copy a digraph to a StaticDigraph
+    /// structure using \ref DigraphCopy.
+    /// 
+    /// \param digraph An existing digraph to be copied.
+    /// \param nodeRef The node references will be copied into this map.
+    /// Its key type must be \c Digraph::Node and its value type must be
+    /// \c StaticDigraph::Node.
+    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
+    /// concept.
+    /// \param arcRef The arc references will be copied into this map.
+    /// Its key type must be \c Digraph::Arc and its value type must be
+    /// \c StaticDigraph::Arc.
+    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    /// \note If you do not need the arc references, then you could use
+    /// \ref NullMap for the last parameter. However the node references
+    /// are required by the function itself, thus they must be readable
+    /// from the map.
+    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
+    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
+      if (built) Parent::clear();
+      Parent::build(digraph, nodeRef, arcRef);
+    }
+  
+    /// \brief Build the digraph from an arc list.
+    ///
+    /// This function builds the digraph from the given arc list.
+    /// It can be called more than once, but in such case, the whole
+    /// structure and all maps will be cleared and rebuilt.
+    ///
+    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
+    /// specified by STL compatible itartors whose \c value_type must be
+    /// <tt>std::pair<int,int></tt>.
+    /// Each arc must be specified by a pair of integer indices
+    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
+    /// non-decreasing order with respect to their first values.</i>
+    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
+    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
+    ///
+    /// \param n The number of nodes.
+    /// \param begin An iterator pointing to the beginning of the arc list.
+    /// \param end An iterator pointing to the end of the arc list.
+    ///
+    /// For example, a simple digraph can be constructed like this.
+    /// \code
+    ///   std::vector<std::pair<int,int> > arcs;
+    ///   arcs.push_back(std::make_pair(0,1));
+    ///   arcs.push_back(std::make_pair(0,2));
+    ///   arcs.push_back(std::make_pair(1,3));
+    ///   arcs.push_back(std::make_pair(1,2));
+    ///   arcs.push_back(std::make_pair(3,0));
+    ///   StaticDigraph gr;
+    ///   gr.build(4, arcs.begin(), arcs.end());
+    /// \endcode
+    template <typename ArcListIterator>
+    void build(int n, ArcListIterator begin, ArcListIterator end) {
+      if (built) Parent::clear();
+      StaticDigraphBase::build(n, begin, end);
+      notifier(Node()).build();
+      notifier(Arc()).build();
+    }
+
+    /// \brief Clear the digraph.
+    ///
+    /// This function erases all nodes and arcs from the digraph.
+    void clear() {
+      Parent::clear();
+    }
+
+  protected:
+
+    using Parent::fastFirstOut;
+    using Parent::fastNextOut;
+    using Parent::fastLastOut;
+    
+  public:
+
+    class OutArcIt : public Arc {
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const StaticDigraph& digraph, const Node& node) {
+	digraph.fastFirstOut(*this, node);
+	digraph.fastLastOut(last, node);
+        if (last == *this) *this = INVALID;
+      }
+
+      OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
+        if (arc != INVALID) {
+          digraph.fastLastOut(last, digraph.source(arc));
+        }
+      }
+
+      OutArcIt& operator++() { 
+        StaticDigraph::fastNextOut(*this);
+        if (last == *this) *this = INVALID;
+        return *this; 
+      }
+
+    private:
+      Arc last;
+    };
+
+    Node baseNode(const OutArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+
+    Node runningNode(const OutArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+
+    Node baseNode(const InArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+
+    Node runningNode(const InArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+
+  };
+
+}
+
+#endif
