Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 686)
+++ lemon/Makefile.am	(revision 708)
@@ -112,5 +112,4 @@
 	lemon/bits/alteration_notifier.h \
 	lemon/bits/array_map.h \
-	lemon/bits/base_extender.h \
 	lemon/bits/bezier.h \
 	lemon/bits/default_map.h \
Index: lemon/adaptors.h
===================================================================
--- lemon/adaptors.h	(revision 664)
+++ lemon/adaptors.h	(revision 703)
@@ -1840,29 +1840,29 @@
     typedef typename Digraph::Node Node;
 
-    class Arc : public Edge {
+    class Arc {
       friend class UndirectorBase;
     protected:
+      Edge _edge;
       bool _forward;
 
-      Arc(const Edge& edge, bool forward) :
-        Edge(edge), _forward(forward) {}
+      Arc(const Edge& edge, bool forward) 
+        : _edge(edge), _forward(forward) {}
 
     public:
       Arc() {}
 
-      Arc(Invalid) : Edge(INVALID), _forward(true) {}
+      Arc(Invalid) : _edge(INVALID), _forward(true) {}
+
+      operator const Edge&() const { return _edge; }
 
       bool operator==(const Arc &other) const {
-        return _forward == other._forward &&
-          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
+        return _forward == other._forward && _edge == other._edge;
       }
       bool operator!=(const Arc &other) const {
-        return _forward != other._forward ||
-          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
+        return _forward != other._forward || _edge != other._edge;
       }
       bool operator<(const Arc &other) const {
         return _forward < other._forward ||
-          (_forward == other._forward &&
-           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
+          (_forward == other._forward && _edge < other._edge);
       }
     };
@@ -1877,5 +1877,5 @@
 
     void first(Arc& a) const {
-      _digraph->first(a);
+      _digraph->first(a._edge);
       a._forward = true;
     }
@@ -1885,5 +1885,5 @@
         a._forward = false;
       } else {
-        _digraph->next(a);
+        _digraph->next(a._edge);
         a._forward = true;
       }
@@ -1899,9 +1899,9 @@
 
     void firstOut(Arc& a, const Node& n) const {
-      _digraph->firstIn(a, n);
-      if( static_cast<const Edge&>(a) != INVALID ) {
+      _digraph->firstIn(a._edge, n);
+      if (a._edge != INVALID ) {
         a._forward = false;
       } else {
-        _digraph->firstOut(a, n);
+        _digraph->firstOut(a._edge, n);
         a._forward = true;
       }
@@ -1909,22 +1909,22 @@
     void nextOut(Arc &a) const {
       if (!a._forward) {
-        Node n = _digraph->target(a);
-        _digraph->nextIn(a);
-        if (static_cast<const Edge&>(a) == INVALID ) {
-          _digraph->firstOut(a, n);
+        Node n = _digraph->target(a._edge);
+        _digraph->nextIn(a._edge);
+        if (a._edge == INVALID) {
+          _digraph->firstOut(a._edge, n);
           a._forward = true;
         }
       }
       else {
-        _digraph->nextOut(a);
+        _digraph->nextOut(a._edge);
       }
     }
 
     void firstIn(Arc &a, const Node &n) const {
-      _digraph->firstOut(a, n);
-      if (static_cast<const Edge&>(a) != INVALID ) {
+      _digraph->firstOut(a._edge, n);
+      if (a._edge != INVALID ) {
         a._forward = false;
       } else {
-        _digraph->firstIn(a, n);
+        _digraph->firstIn(a._edge, n);
         a._forward = true;
       }
@@ -1932,13 +1932,13 @@
     void nextIn(Arc &a) const {
       if (!a._forward) {
-        Node n = _digraph->source(a);
-        _digraph->nextOut(a);
-        if( static_cast<const Edge&>(a) == INVALID ) {
-          _digraph->firstIn(a, n);
+        Node n = _digraph->source(a._edge);
+        _digraph->nextOut(a._edge);
+        if (a._edge == INVALID ) {
+          _digraph->firstIn(a._edge, n);
           a._forward = true;
         }
       }
       else {
-        _digraph->nextIn(a);
+        _digraph->nextIn(a._edge);
       }
     }
@@ -1973,16 +1973,13 @@
 
     Node source(const Arc &a) const {
-      return a._forward ? _digraph->source(a) : _digraph->target(a);
+      return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge);
     }
 
     Node target(const Arc &a) const {
-      return a._forward ? _digraph->target(a) : _digraph->source(a);
+      return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge);
     }
 
     static Arc direct(const Edge &e, bool d) {
       return Arc(e, d);
-    }
-    Arc direct(const Edge &e, const Node& n) const {
-      return Arc(e, _digraph->source(e) == n);
     }
 
Index: lemon/bits/base_extender.h
===================================================================
--- lemon/bits/base_extender.h	(revision 664)
+++ 	(revision )
@@ -1,495 +1,0 @@
-/* -*- mode: C++; indent-tabs-mode: nil; -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library.
- *
- * Copyright (C) 2003-2009
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_BITS_BASE_EXTENDER_H
-#define LEMON_BITS_BASE_EXTENDER_H
-
-#include <lemon/core.h>
-#include <lemon/error.h>
-
-#include <lemon/bits/map_extender.h>
-#include <lemon/bits/default_map.h>
-
-#include <lemon/concept_check.h>
-#include <lemon/concepts/maps.h>
-
-//\ingroup digraphbits
-//\file
-//\brief Extenders for the graph types
-namespace lemon {
-
-  // \ingroup digraphbits
-  //
-  // \brief BaseDigraph to BaseGraph extender
-  template <typename Base>
-  class UndirDigraphExtender : public Base {
-    typedef Base Parent;
-
-  public:
-
-    typedef typename Parent::Arc Edge;
-    typedef typename Parent::Node Node;
-
-    typedef True UndirectedTag;
-
-    class Arc : public Edge {
-      friend class UndirDigraphExtender;
-
-    protected:
-      bool forward;
-
-      Arc(const Edge &ue, bool _forward) :
-        Edge(ue), forward(_forward) {}
-
-    public:
-      Arc() {}
-
-      // Invalid arc constructor
-      Arc(Invalid i) : Edge(i), forward(true) {}
-
-      bool operator==(const Arc &that) const {
-        return forward==that.forward && Edge(*this)==Edge(that);
-      }
-      bool operator!=(const Arc &that) const {
-        return forward!=that.forward || Edge(*this)!=Edge(that);
-      }
-      bool operator<(const Arc &that) const {
-        return forward<that.forward ||
-          (!(that.forward<forward) && Edge(*this)<Edge(that));
-      }
-    };
-
-    // First node of the edge
-    Node u(const Edge &e) const {
-      return Parent::source(e);
-    }
-
-    // Source of the given arc
-    Node source(const Arc &e) const {
-      return e.forward ? Parent::source(e) : Parent::target(e);
-    }
-
-    // Second node of the edge
-    Node v(const Edge &e) const {
-      return Parent::target(e);
-    }
-
-    // Target of the given arc
-    Node target(const Arc &e) const {
-      return e.forward ? Parent::target(e) : Parent::source(e);
-    }
-
-    // \brief Directed arc from an edge.
-    //
-    // Returns a directed arc corresponding to the specified edge.
-    // If the given bool is true, the first node of the given edge and
-    // the source node of the returned arc are the same.
-    static Arc direct(const Edge &e, bool d) {
-      return Arc(e, d);
-    }
-
-    // Returns whether the given directed arc has the same orientation
-    // as the corresponding edge.
-    static bool direction(const Arc &a) { return a.forward; }
-
-    using Parent::first;
-    using Parent::next;
-
-    void first(Arc &e) const {
-      Parent::first(e);
-      e.forward=true;
-    }
-
-    void next(Arc &e) const {
-      if( e.forward ) {
-        e.forward = false;
-      }
-      else {
-        Parent::next(e);
-        e.forward = true;
-      }
-    }
-
-    void firstOut(Arc &e, const Node &n) const {
-      Parent::firstIn(e,n);
-      if( Edge(e) != INVALID ) {
-        e.forward = false;
-      }
-      else {
-        Parent::firstOut(e,n);
-        e.forward = true;
-      }
-    }
-    void nextOut(Arc &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::target(e);
-        Parent::nextIn(e);
-        if( Edge(e) == INVALID ) {
-          Parent::firstOut(e, n);
-          e.forward = true;
-        }
-      }
-      else {
-        Parent::nextOut(e);
-      }
-    }
-
-    void firstIn(Arc &e, const Node &n) const {
-      Parent::firstOut(e,n);
-      if( Edge(e) != INVALID ) {
-        e.forward = false;
-      }
-      else {
-        Parent::firstIn(e,n);
-        e.forward = true;
-      }
-    }
-    void nextIn(Arc &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::source(e);
-        Parent::nextOut(e);
-        if( Edge(e) == INVALID ) {
-          Parent::firstIn(e, n);
-          e.forward = true;
-        }
-      }
-      else {
-        Parent::nextIn(e);
-      }
-    }
-
-    void firstInc(Edge &e, bool &d, const Node &n) const {
-      d = true;
-      Parent::firstOut(e, n);
-      if (e != INVALID) return;
-      d = false;
-      Parent::firstIn(e, n);
-    }
-
-    void nextInc(Edge &e, bool &d) const {
-      if (d) {
-        Node s = Parent::source(e);
-        Parent::nextOut(e);
-        if (e != INVALID) return;
-        d = false;
-        Parent::firstIn(e, s);
-      } else {
-        Parent::nextIn(e);
-      }
-    }
-
-    Node nodeFromId(int ix) const {
-      return Parent::nodeFromId(ix);
-    }
-
-    Arc arcFromId(int ix) const {
-      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
-    }
-
-    Edge edgeFromId(int ix) const {
-      return Parent::arcFromId(ix);
-    }
-
-    int id(const Node &n) const {
-      return Parent::id(n);
-    }
-
-    int id(const Edge &e) const {
-      return Parent::id(e);
-    }
-
-    int id(const Arc &e) const {
-      return 2 * Parent::id(e) + int(e.forward);
-    }
-
-    int maxNodeId() const {
-      return Parent::maxNodeId();
-    }
-
-    int maxArcId() const {
-      return 2 * Parent::maxArcId() + 1;
-    }
-
-    int maxEdgeId() const {
-      return Parent::maxArcId();
-    }
-
-    int arcNum() const {
-      return 2 * Parent::arcNum();
-    }
-
-    int edgeNum() const {
-      return Parent::arcNum();
-    }
-
-    Arc findArc(Node s, Node t, Arc p = INVALID) const {
-      if (p == INVALID) {
-        Edge arc = Parent::findArc(s, t);
-        if (arc != INVALID) return direct(arc, true);
-        arc = Parent::findArc(t, s);
-        if (arc != INVALID) return direct(arc, false);
-      } else if (direction(p)) {
-        Edge arc = Parent::findArc(s, t, p);
-        if (arc != INVALID) return direct(arc, true);
-        arc = Parent::findArc(t, s);
-        if (arc != INVALID) return direct(arc, false);
-      } else {
-        Edge arc = Parent::findArc(t, s, p);
-        if (arc != INVALID) return direct(arc, false);
-      }
-      return INVALID;
-    }
-
-    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
-      if (s != t) {
-        if (p == INVALID) {
-          Edge arc = Parent::findArc(s, t);
-          if (arc != INVALID) return arc;
-          arc = Parent::findArc(t, s);
-          if (arc != INVALID) return arc;
-        } else if (Parent::s(p) == s) {
-          Edge arc = Parent::findArc(s, t, p);
-          if (arc != INVALID) return arc;
-          arc = Parent::findArc(t, s);
-          if (arc != INVALID) return arc;
-        } else {
-          Edge arc = Parent::findArc(t, s, p);
-          if (arc != INVALID) return arc;
-        }
-      } else {
-        return Parent::findArc(s, t, p);
-      }
-      return INVALID;
-    }
-  };
-
-  template <typename Base>
-  class BidirBpGraphExtender : public Base {
-    typedef Base Parent;
-
-  public:
-    typedef BidirBpGraphExtender Digraph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-
-    using Parent::first;
-    using Parent::next;
-
-    using Parent::id;
-
-    class Red : public Node {
-      friend class BidirBpGraphExtender;
-    public:
-      Red() {}
-      Red(const Node& node) : Node(node) {
-        LEMON_DEBUG(Parent::red(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-      }
-      Red& operator=(const Node& node) {
-        LEMON_DEBUG(Parent::red(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-        Node::operator=(node);
-        return *this;
-      }
-      Red(Invalid) : Node(INVALID) {}
-      Red& operator=(Invalid) {
-        Node::operator=(INVALID);
-        return *this;
-      }
-    };
-
-    void first(Red& node) const {
-      Parent::firstRed(static_cast<Node&>(node));
-    }
-    void next(Red& node) const {
-      Parent::nextRed(static_cast<Node&>(node));
-    }
-
-    int id(const Red& node) const {
-      return Parent::redId(node);
-    }
-
-    class Blue : public Node {
-      friend class BidirBpGraphExtender;
-    public:
-      Blue() {}
-      Blue(const Node& node) : Node(node) {
-        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-      }
-      Blue& operator=(const Node& node) {
-        LEMON_DEBUG(Parent::blue(node) || node == INVALID,
-                    typename Parent::NodeSetError());
-        Node::operator=(node);
-        return *this;
-      }
-      Blue(Invalid) : Node(INVALID) {}
-      Blue& operator=(Invalid) {
-        Node::operator=(INVALID);
-        return *this;
-      }
-    };
-
-    void first(Blue& node) const {
-      Parent::firstBlue(static_cast<Node&>(node));
-    }
-    void next(Blue& node) const {
-      Parent::nextBlue(static_cast<Node&>(node));
-    }
-
-    int id(const Blue& node) const {
-      return Parent::redId(node);
-    }
-
-    Node source(const Edge& arc) const {
-      return red(arc);
-    }
-    Node target(const Edge& arc) const {
-      return blue(arc);
-    }
-
-    void firstInc(Edge& arc, bool& dir, const Node& node) const {
-      if (Parent::red(node)) {
-        Parent::firstFromRed(arc, node);
-        dir = true;
-      } else {
-        Parent::firstFromBlue(arc, node);
-        dir = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextInc(Edge& arc, bool& dir) const {
-      if (dir) {
-        Parent::nextFromRed(arc);
-      } else {
-        Parent::nextFromBlue(arc);
-        if (arc == INVALID) dir = true;
-      }
-    }
-
-    class Arc : public Edge {
-      friend class BidirBpGraphExtender;
-    protected:
-      bool forward;
-
-      Arc(const Edge& arc, bool _forward)
-        : Edge(arc), forward(_forward) {}
-
-    public:
-      Arc() {}
-      Arc (Invalid) : Edge(INVALID), forward(true) {}
-      bool operator==(const Arc& i) const {
-        return Edge::operator==(i) && forward == i.forward;
-      }
-      bool operator!=(const Arc& i) const {
-        return Edge::operator!=(i) || forward != i.forward;
-      }
-      bool operator<(const Arc& i) const {
-        return Edge::operator<(i) ||
-          (!(i.forward<forward) && Edge(*this)<Edge(i));
-      }
-    };
-
-    void first(Arc& arc) const {
-      Parent::first(static_cast<Edge&>(arc));
-      arc.forward = true;
-    }
-
-    void next(Arc& arc) const {
-      if (!arc.forward) {
-        Parent::next(static_cast<Edge&>(arc));
-      }
-      arc.forward = !arc.forward;
-    }
-
-    void firstOut(Arc& arc, const Node& node) const {
-      if (Parent::red(node)) {
-        Parent::firstFromRed(arc, node);
-        arc.forward = true;
-      } else {
-        Parent::firstFromBlue(arc, node);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextOut(Arc& arc) const {
-      if (arc.forward) {
-        Parent::nextFromRed(arc);
-      } else {
-        Parent::nextFromBlue(arc);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-
-    void firstIn(Arc& arc, const Node& node) const {
-      if (Parent::blue(node)) {
-        Parent::firstFromBlue(arc, node);
-        arc.forward = true;
-      } else {
-        Parent::firstFromRed(arc, node);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-    void nextIn(Arc& arc) const {
-      if (arc.forward) {
-        Parent::nextFromBlue(arc);
-      } else {
-        Parent::nextFromRed(arc);
-        arc.forward = static_cast<Edge&>(arc) == INVALID;
-      }
-    }
-
-    Node source(const Arc& arc) const {
-      return arc.forward ? Parent::red(arc) : Parent::blue(arc);
-    }
-    Node target(const Arc& arc) const {
-      return arc.forward ? Parent::blue(arc) : Parent::red(arc);
-    }
-
-    int id(const Arc& arc) const {
-      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
-        (arc.forward ? 0 : 1);
-    }
-    Arc arcFromId(int ix) const {
-      return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
-    }
-    int maxArcId() const {
-      return (Parent::maxEdgeId() << 1) + 1;
-    }
-
-    bool direction(const Arc& arc) const {
-      return arc.forward;
-    }
-
-    Arc direct(const Edge& arc, bool dir) const {
-      return Arc(arc, dir);
-    }
-
-    int arcNum() const {
-      return 2 * Parent::edgeNum();
-    }
-
-    int edgeNum() const {
-      return Parent::edgeNum();
-    }
-
-
-  };
-}
-
-#endif
Index: lemon/concepts/graph.h
===================================================================
--- lemon/concepts/graph.h	(revision 627)
+++ lemon/concepts/graph.h	(revision 704)
@@ -311,6 +311,6 @@
       /// The directed arc type. It can be converted to the
       /// edge or it should be inherited from the undirected
-      /// arc.
-      class Arc : public Edge {
+      /// edge.
+      class Arc {
       public:
         /// Default constructor
@@ -323,5 +323,5 @@
         /// Copy constructor.
         ///
-        Arc(const Arc& e) : Edge(e) { }
+        Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
 
@@ -350,4 +350,6 @@
         bool operator<(Arc) const { return false; }
 
+        /// Converison to Edge
+        operator Edge() const { return Edge(); }
       };
       /// This iterator goes through each directed arc.
Index: lemon/connectivity.h
===================================================================
--- lemon/connectivity.h	(revision 633)
+++ lemon/connectivity.h	(revision 695)
@@ -43,10 +43,14 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check whether the given undirected graph is connected.
-  ///
-  /// Check whether the given undirected graph is connected.
-  /// \param graph The undirected graph.
-  /// \return \c true when there is path between any two nodes in the graph.
+  /// \brief Check whether an undirected graph is connected.
+  ///
+  /// This function checks whether the given undirected graph is connected,
+  /// i.e. there is a path between any two nodes in the graph.
+  ///
+  /// \return \c true if the graph is connected.
   /// \note By definition, the empty graph is connected.
+  ///
+  /// \see countConnectedComponents(), connectedComponents()
+  /// \see stronglyConnected()
   template <typename Graph>
   bool connected(const Graph& graph) {
@@ -68,10 +72,16 @@
   /// \brief Count the number of connected components of an undirected graph
   ///
-  /// Count the number of connected components of an undirected graph
-  ///
-  /// \param graph The graph. It must be undirected.
-  /// \return The number of components
+  /// This function counts the number of connected components of the given
+  /// undirected graph.
+  ///
+  /// The connected components are the classes of an equivalence relation
+  /// on the nodes of an undirected graph. Two nodes are in the same class
+  /// if they are connected with a path.
+  ///
+  /// \return The number of connected components.
   /// \note By definition, the empty graph consists
   /// of zero connected components.
+  ///
+  /// \see connected(), connectedComponents()
   template <typename Graph>
   int countConnectedComponents(const Graph &graph) {
@@ -110,15 +120,24 @@
   /// \brief Find the connected components of an undirected graph
   ///
-  /// Find the connected components of an undirected graph.
+  /// This function finds the connected components of the given undirected
+  /// graph.
+  ///
+  /// The connected components are the classes of an equivalence relation
+  /// on the nodes of an undirected graph. Two nodes are in the same class
+  /// if they are connected with a path.
   ///
   /// \image html connected_components.png
   /// \image latex connected_components.eps "Connected components" width=\textwidth
   ///
-  /// \param graph The graph. It must be undirected.
+  /// \param graph The undirected graph.
   /// \retval compMap A writable node map. The values will be set from 0 to
-  /// the number of the connected components minus one. Each values of the map
-  /// will be set exactly once, the values of a certain component will be
+  /// the number of the connected components minus one. Each value of the map
+  /// will be set exactly once, and the values of a certain component will be
   /// set continuously.
-  /// \return The number of components
+  /// \return The number of connected components.
+  /// \note By definition, the empty graph consists
+  /// of zero connected components.
+  ///
+  /// \see connected(), countConnectedComponents()
   template <class Graph, class NodeMap>
   int connectedComponents(const Graph &graph, NodeMap &compMap) {
@@ -232,13 +251,15 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check whether the given directed graph is strongly connected.
-  ///
-  /// Check whether the given directed graph is strongly connected. The
-  /// graph is strongly connected when any two nodes of the graph are
+  /// \brief Check whether a directed graph is strongly connected.
+  ///
+  /// This function checks whether the given directed graph is strongly
+  /// connected, i.e. any two nodes of the digraph are
   /// connected with directed paths in both direction.
-  /// \return \c false when the graph is not strongly connected.
-  /// \see connected
-  ///
-  /// \note By definition, the empty graph is strongly connected.
+  ///
+  /// \return \c true if the digraph is strongly connected.
+  /// \note By definition, the empty digraph is strongly connected.
+  /// 
+  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
+  /// \see connected()
   template <typename Digraph>
   bool stronglyConnected(const Digraph& digraph) {
@@ -271,5 +292,5 @@
     RDigraph rdigraph(digraph);
 
-    typedef DfsVisitor<Digraph> RVisitor;
+    typedef DfsVisitor<RDigraph> RVisitor;
     RVisitor rvisitor;
 
@@ -290,16 +311,20 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Count the strongly connected components of a directed graph
-  ///
-  /// Count the strongly connected components of a directed graph.
+  /// \brief Count the number of strongly connected components of a 
+  /// directed graph
+  ///
+  /// This function counts the number of strongly connected components of
+  /// the given directed graph.
+  ///
   /// The strongly connected components are the classes of an
-  /// equivalence relation on the nodes of the graph. Two nodes are in
+  /// equivalence relation on the nodes of a digraph. Two nodes are in
   /// the same class if they are connected with directed paths in both
   /// direction.
   ///
-  /// \param digraph The graph.
-  /// \return The number of components
-  /// \note By definition, the empty graph has zero
+  /// \return The number of strongly connected components.
+  /// \note By definition, the empty digraph has zero
   /// strongly connected components.
+  ///
+  /// \see stronglyConnected(), stronglyConnectedComponents()
   template <typename Digraph>
   int countStronglyConnectedComponents(const Digraph& digraph) {
@@ -356,11 +381,13 @@
   /// \brief Find the strongly connected components of a directed graph
   ///
-  /// Find the strongly connected components of a directed graph.  The
-  /// strongly connected components are the classes of an equivalence
-  /// relation on the nodes of the graph. Two nodes are in
-  /// relationship when there are directed paths between them in both
-  /// direction. In addition, the numbering of components will satisfy
-  /// that there is no arc going from a higher numbered component to
-  /// a lower.
+  /// This function finds the strongly connected components of the given
+  /// directed graph. In addition, the numbering of the components will
+  /// satisfy that there is no arc going from a higher numbered component
+  /// to a lower one (i.e. it provides a topological order of the components).
+  ///
+  /// The strongly connected components are the classes of an
+  /// equivalence relation on the nodes of a digraph. Two nodes are in
+  /// the same class if they are connected with directed paths in both
+  /// direction.
   ///
   /// \image html strongly_connected_components.png
@@ -370,7 +397,11 @@
   /// \retval compMap A writable node map. The values will be set from 0 to
   /// the number of the strongly connected components minus one. Each value
-  /// of the map will be set exactly once, the values of a certain component
-  /// will be set continuously.
-  /// \return The number of components
+  /// of the map will be set exactly once, and the values of a certain
+  /// component will be set continuously.
+  /// \return The number of strongly connected components.
+  /// \note By definition, the empty digraph has zero
+  /// strongly connected components.
+  ///
+  /// \see stronglyConnected(), countStronglyConnectedComponents()
   template <typename Digraph, typename NodeMap>
   int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
@@ -425,17 +456,22 @@
   /// \brief Find the cut arcs of the strongly connected components.
   ///
-  /// Find the cut arcs of the strongly connected components.
-  /// The strongly connected components are the classes of an equivalence
-  /// relation on the nodes of the graph. Two nodes are in relationship
-  /// when there are directed paths between them in both direction.
+  /// This function finds the cut arcs of the strongly connected components
+  /// of the given digraph.
+  ///
+  /// The strongly connected components are the classes of an
+  /// equivalence relation on the nodes of a digraph. Two nodes are in
+  /// the same class if they are connected with directed paths in both
+  /// direction.
   /// The strongly connected components are separated by the cut arcs.
   ///
-  /// \param graph The graph.
-  /// \retval cutMap A writable node map. The values will be set true when the
-  /// arc is a cut arc.
-  ///
-  /// \return The number of cut arcs
+  /// \param digraph The digraph.
+  /// \retval cutMap A writable arc map. The values will be set to \c true
+  /// for the cut arcs (exactly once for each cut arc), and will not be
+  /// changed for other arcs.
+  /// \return The number of cut arcs.
+  ///
+  /// \see stronglyConnected(), stronglyConnectedComponents()
   template <typename Digraph, typename ArcMap>
-  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
+  int stronglyConnectedCutArcs(const Digraph& digraph, ArcMap& cutMap) {
     checkConcept<concepts::Digraph, Digraph>();
     typedef typename Digraph::Node Node;
@@ -449,11 +485,11 @@
     typedef typename Container::iterator Iterator;
 
-    Container nodes(countNodes(graph));
+    Container nodes(countNodes(digraph));
     typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
     Visitor visitor(nodes.begin());
 
-    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
+    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
     dfs.init();
-    for (NodeIt it(graph); it != INVALID; ++it) {
+    for (NodeIt it(digraph); it != INVALID; ++it) {
       if (!dfs.reached(it)) {
         dfs.addSource(it);
@@ -465,12 +501,12 @@
     typedef ReverseDigraph<const Digraph> RDigraph;
 
-    RDigraph rgraph(graph);
+    RDigraph rdigraph(digraph);
 
     int cutNum = 0;
 
     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
-    RVisitor rvisitor(rgraph, cutMap, cutNum);
-
-    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
+    RVisitor rvisitor(rdigraph, cutMap, cutNum);
+
+    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 
     rdfs.init();
@@ -707,12 +743,13 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Checks the graph is bi-node-connected.
-  ///
-  /// This function checks that the undirected graph is bi-node-connected
-  /// graph. The graph is bi-node-connected if any two undirected edge is
-  /// on same circle.
-  ///
-  /// \param graph The graph.
-  /// \return \c true when the graph bi-node-connected.
+  /// \brief Check whether an undirected graph is bi-node-connected.
+  ///
+  /// This function checks whether the given undirected graph is 
+  /// bi-node-connected, i.e. any two edges are on same circle.
+  ///
+  /// \return \c true if the graph bi-node-connected.
+  /// \note By definition, the empty graph is bi-node-connected.
+  ///
+  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
   template <typename Graph>
   bool biNodeConnected(const Graph& graph) {
@@ -722,13 +759,17 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Count the biconnected components.
-  ///
-  /// This function finds the bi-node-connected components in an undirected
-  /// graph. The biconnected components are the classes of an equivalence
-  /// relation on the undirected edges. Two undirected edge is in relationship
-  /// when they are on same circle.
-  ///
-  /// \param graph The graph.
-  /// \return The number of components.
+  /// \brief Count the number of bi-node-connected components of an 
+  /// undirected graph.
+  ///
+  /// This function counts the number of bi-node-connected components of
+  /// the given undirected graph.
+  ///
+  /// The bi-node-connected components are the classes of an equivalence
+  /// relation on the edges of a undirected graph. Two edges are in the
+  /// same class if they are on same circle.
+  ///
+  /// \return The number of bi-node-connected components.
+  ///
+  /// \see biNodeConnected(), biNodeConnectedComponents()
   template <typename Graph>
   int countBiNodeConnectedComponents(const Graph& graph) {
@@ -757,20 +798,24 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-node-connected components.
-  ///
-  /// This function finds the bi-node-connected components in an undirected
-  /// graph. The bi-node-connected components are the classes of an equivalence
-  /// relation on the undirected edges. Two undirected edge are in relationship
-  /// when they are on same circle.
+  /// \brief Find the bi-node-connected components of an undirected graph.
+  ///
+  /// This function finds the bi-node-connected components of the given
+  /// undirected graph.
+  ///
+  /// The bi-node-connected components are the classes of an equivalence
+  /// relation on the edges of a undirected graph. Two edges are in the
+  /// same class if they are on same circle.
   ///
   /// \image html node_biconnected_components.png
   /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
   ///
-  /// \param graph The graph.
-  /// \retval compMap A writable uedge map. The values will be set from 0
-  /// to the number of the biconnected components minus one. Each values
-  /// of the map will be set exactly once, the values of a certain component
-  /// will be set continuously.
-  /// \return The number of components.
+  /// \param graph The undirected graph.
+  /// \retval compMap A writable edge map. The values will be set from 0
+  /// to the number of the bi-node-connected components minus one. Each
+  /// value of the map will be set exactly once, and the values of a 
+  /// certain component will be set continuously.
+  /// \return The number of bi-node-connected components.
+  ///
+  /// \see biNodeConnected(), countBiNodeConnectedComponents()
   template <typename Graph, typename EdgeMap>
   int biNodeConnectedComponents(const Graph& graph,
@@ -802,16 +847,23 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-node-connected cut nodes.
-  ///
-  /// This function finds the bi-node-connected cut nodes in an undirected
-  /// graph. The bi-node-connected components are the classes of an equivalence
-  /// relation on the undirected edges. Two undirected edges are in
-  /// relationship when they are on same circle. The biconnected components
-  /// are separted by nodes which are the cut nodes of the components.
-  ///
-  /// \param graph The graph.
-  /// \retval cutMap A writable edge map. The values will be set true when
-  /// the node separate two or more components.
+  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
+  ///
+  /// This function finds the bi-node-connected cut nodes in the given
+  /// undirected graph.
+  ///
+  /// The bi-node-connected components are the classes of an equivalence
+  /// relation on the edges of a undirected graph. Two edges are in the
+  /// same class if they are on same circle.
+  /// The bi-node-connected components are separted by the cut nodes of
+  /// the components.
+  ///
+  /// \param graph The undirected graph.
+  /// \retval cutMap A writable node map. The values will be set to 
+  /// \c true for the nodes that separate two or more components
+  /// (exactly once for each cut node), and will not be changed for
+  /// other nodes.
   /// \return The number of the cut nodes.
+  ///
+  /// \see biNodeConnected(), biNodeConnectedComponents()
   template <typename Graph, typename NodeMap>
   int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
@@ -1032,12 +1084,14 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Checks that the graph is bi-edge-connected.
-  ///
-  /// This function checks that the graph is bi-edge-connected. The undirected
-  /// graph is bi-edge-connected when any two nodes are connected with two
-  /// edge-disjoint paths.
-  ///
-  /// \param graph The undirected graph.
-  /// \return The number of components.
+  /// \brief Check whether an undirected graph is bi-edge-connected.
+  ///
+  /// This function checks whether the given undirected graph is 
+  /// bi-edge-connected, i.e. any two nodes are connected with at least
+  /// two edge-disjoint paths.
+  ///
+  /// \return \c true if the graph is bi-edge-connected.
+  /// \note By definition, the empty graph is bi-edge-connected.
+  ///
+  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
   template <typename Graph>
   bool biEdgeConnected(const Graph& graph) {
@@ -1047,13 +1101,18 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Count the bi-edge-connected components.
-  ///
-  /// This function count the bi-edge-connected components in an undirected
-  /// graph. The bi-edge-connected components are the classes of an equivalence
-  /// relation on the nodes. Two nodes are in relationship when they are
-  /// connected with at least two edge-disjoint paths.
-  ///
-  /// \param graph The undirected graph.
-  /// \return The number of components.
+  /// \brief Count the number of bi-edge-connected components of an
+  /// undirected graph.
+  ///
+  /// This function counts the number of bi-edge-connected components of
+  /// the given undirected graph.
+  ///
+  /// The bi-edge-connected components are the classes of an equivalence
+  /// relation on the nodes of an undirected graph. Two nodes are in the
+  /// same class if they are connected with at least two edge-disjoint
+  /// paths.
+  ///
+  /// \return The number of bi-edge-connected components.
+  ///
+  /// \see biEdgeConnected(), biEdgeConnectedComponents()
   template <typename Graph>
   int countBiEdgeConnectedComponents(const Graph& graph) {
@@ -1082,20 +1141,25 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-edge-connected components.
-  ///
-  /// This function finds the bi-edge-connected components in an undirected
-  /// graph. The bi-edge-connected components are the classes of an equivalence
-  /// relation on the nodes. Two nodes are in relationship when they are
-  /// connected at least two edge-disjoint paths.
+  /// \brief Find the bi-edge-connected components of an undirected graph.
+  ///
+  /// This function finds the bi-edge-connected components of the given
+  /// undirected graph.
+  ///
+  /// The bi-edge-connected components are the classes of an equivalence
+  /// relation on the nodes of an undirected graph. Two nodes are in the
+  /// same class if they are connected with at least two edge-disjoint
+  /// paths.
   ///
   /// \image html edge_biconnected_components.png
   /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   ///
-  /// \param graph The graph.
+  /// \param graph The undirected graph.
   /// \retval compMap A writable node map. The values will be set from 0 to
-  /// the number of the biconnected components minus one. Each values
-  /// of the map will be set exactly once, the values of a certain component
-  /// will be set continuously.
-  /// \return The number of components.
+  /// the number of the bi-edge-connected components minus one. Each value
+  /// of the map will be set exactly once, and the values of a certain
+  /// component will be set continuously.
+  /// \return The number of bi-edge-connected components.
+  ///
+  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()
   template <typename Graph, typename NodeMap>
   int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
@@ -1126,17 +1190,23 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-edge-connected cut edges.
-  ///
-  /// This function finds the bi-edge-connected components in an undirected
-  /// graph. The bi-edge-connected components are the classes of an equivalence
-  /// relation on the nodes. Two nodes are in relationship when they are
-  /// connected with at least two edge-disjoint paths. The bi-edge-connected
-  /// components are separted by edges which are the cut edges of the
-  /// components.
-  ///
-  /// \param graph The graph.
-  /// \retval cutMap A writable node map. The values will be set true when the
-  /// edge is a cut edge.
+  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
+  ///
+  /// This function finds the bi-edge-connected cut edges in the given
+  /// undirected graph. 
+  ///
+  /// The bi-edge-connected components are the classes of an equivalence
+  /// relation on the nodes of an undirected graph. Two nodes are in the
+  /// same class if they are connected with at least two edge-disjoint
+  /// paths.
+  /// The bi-edge-connected components are separted by the cut edges of
+  /// the components.
+  ///
+  /// \param graph The undirected graph.
+  /// \retval cutMap A writable edge map. The values will be set to \c true
+  /// for the cut edges (exactly once for each cut edge), and will not be
+  /// changed for other edges.
   /// \return The number of cut edges.
+  ///
+  /// \see biEdgeConnected(), biEdgeConnectedComponents()
   template <typename Graph, typename EdgeMap>
   int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
@@ -1190,21 +1260,14 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Sort the nodes of a DAG into topolgical order.
-  ///
-  /// Sort the nodes of a DAG into topolgical order.
-  ///
-  /// \param graph The graph. It must be directed and acyclic.
-  /// \retval order A writable node map. The values will be set from 0 to
-  /// the number of the nodes in the graph minus one. Each values of the map
-  /// will be set exactly once, the values  will be set descending order.
-  ///
-  /// \see checkedTopologicalSort
-  /// \see dag
-  template <typename Digraph, typename NodeMap>
-  void topologicalSort(const Digraph& graph, NodeMap& order) {
-    using namespace _connectivity_bits;
+  /// \brief Check whether a digraph is DAG.
+  ///
+  /// This function checks whether the given digraph is DAG, i.e.
+  /// \e Directed \e Acyclic \e Graph.
+  /// \return \c true if there is no directed cycle in the digraph.
+  /// \see acyclic()
+  template <typename Digraph>
+  bool dag(const Digraph& digraph) {
 
     checkConcept<concepts::Digraph, Digraph>();
-    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
 
     typedef typename Digraph::Node Node;
@@ -1212,12 +1275,62 @@
     typedef typename Digraph::Arc Arc;
 
+    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
+
+    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
+      Create dfs(digraph);
+
+    ProcessedMap processed(digraph);
+    dfs.processedMap(processed);
+
+    dfs.init();
+    for (NodeIt it(digraph); it != INVALID; ++it) {
+      if (!dfs.reached(it)) {
+        dfs.addSource(it);
+        while (!dfs.emptyQueue()) {
+          Arc arc = dfs.nextArc();
+          Node target = digraph.target(arc);
+          if (dfs.reached(target) && !processed[target]) {
+            return false;
+          }
+          dfs.processNextArc();
+        }
+      }
+    }
+    return true;
+  }
+
+  /// \ingroup graph_properties
+  ///
+  /// \brief Sort the nodes of a DAG into topolgical order.
+  ///
+  /// This function sorts the nodes of the given acyclic digraph (DAG)
+  /// into topolgical order.
+  ///
+  /// \param digraph The digraph, which must be DAG.
+  /// \retval order A writable node map. The values will be set from 0 to
+  /// the number of the nodes in the digraph minus one. Each value of the
+  /// map will be set exactly once, and the values will be set descending
+  /// order.
+  ///
+  /// \see dag(), checkedTopologicalSort()
+  template <typename Digraph, typename NodeMap>
+  void topologicalSort(const Digraph& digraph, NodeMap& order) {
+    using namespace _connectivity_bits;
+
+    checkConcept<concepts::Digraph, Digraph>();
+    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
+
+    typedef typename Digraph::Node Node;
+    typedef typename Digraph::NodeIt NodeIt;
+    typedef typename Digraph::Arc Arc;
+
     TopologicalSortVisitor<Digraph, NodeMap>
-      visitor(order, countNodes(graph));
+      visitor(order, countNodes(digraph));
 
     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
-      dfs(graph, visitor);
+      dfs(digraph, visitor);
 
     dfs.init();
-    for (NodeIt it(graph); it != INVALID; ++it) {
+    for (NodeIt it(digraph); it != INVALID; ++it) {
       if (!dfs.reached(it)) {
         dfs.addSource(it);
@@ -1231,16 +1344,16 @@
   /// \brief Sort the nodes of a DAG into topolgical order.
   ///
-  /// Sort the nodes of a DAG into topolgical order. It also checks
-  /// that the given graph is DAG.
-  ///
-  /// \param digraph The graph. It must be directed and acyclic.
-  /// \retval order A readable - writable node map. The values will be set
-  /// from 0 to the number of the nodes in the graph minus one. Each values
-  /// of the map will be set exactly once, the values will be set descending
-  /// order.
-  /// \return \c false when the graph is not DAG.
-  ///
-  /// \see topologicalSort
-  /// \see dag
+  /// This function sorts the nodes of the given acyclic digraph (DAG)
+  /// into topolgical order and also checks whether the given digraph
+  /// is DAG.
+  ///
+  /// \param digraph The digraph.
+  /// \retval order A readable and writable node map. The values will be
+  /// set from 0 to the number of the nodes in the digraph minus one. 
+  /// Each value of the map will be set exactly once, and the values will
+  /// be set descending order.
+  /// \return \c false if the digraph is not DAG.
+  ///
+  /// \see dag(), topologicalSort()
   template <typename Digraph, typename NodeMap>
   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
@@ -1284,52 +1397,9 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check that the given directed graph is a DAG.
-  ///
-  /// Check that the given directed graph is a DAG. The DAG is
-  /// an Directed Acyclic Digraph.
-  /// \return \c false when the graph is not DAG.
-  /// \see acyclic
-  template <typename Digraph>
-  bool dag(const Digraph& digraph) {
-
-    checkConcept<concepts::Digraph, Digraph>();
-
-    typedef typename Digraph::Node Node;
-    typedef typename Digraph::NodeIt NodeIt;
-    typedef typename Digraph::Arc Arc;
-
-    typedef typename Digraph::template NodeMap<bool> ProcessedMap;
-
-    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
-      Create dfs(digraph);
-
-    ProcessedMap processed(digraph);
-    dfs.processedMap(processed);
-
-    dfs.init();
-    for (NodeIt it(digraph); it != INVALID; ++it) {
-      if (!dfs.reached(it)) {
-        dfs.addSource(it);
-        while (!dfs.emptyQueue()) {
-          Arc edge = dfs.nextArc();
-          Node target = digraph.target(edge);
-          if (dfs.reached(target) && !processed[target]) {
-            return false;
-          }
-          dfs.processNextArc();
-        }
-      }
-    }
-    return true;
-  }
-
-  /// \ingroup graph_properties
-  ///
-  /// \brief Check that the given undirected graph is acyclic.
-  ///
-  /// Check that the given undirected graph acyclic.
-  /// \param graph The undirected graph.
-  /// \return \c true when there is no circle in the graph.
-  /// \see dag
+  /// \brief Check whether an undirected graph is acyclic.
+  ///
+  /// This function checks whether the given undirected graph is acyclic.
+  /// \return \c true if there is no cycle in the graph.
+  /// \see dag()
   template <typename Graph>
   bool acyclic(const Graph& graph) {
@@ -1344,9 +1414,9 @@
         dfs.addSource(it);
         while (!dfs.emptyQueue()) {
-          Arc edge = dfs.nextArc();
-          Node source = graph.source(edge);
-          Node target = graph.target(edge);
+          Arc arc = dfs.nextArc();
+          Node source = graph.source(arc);
+          Node target = graph.target(arc);
           if (dfs.reached(target) &&
-              dfs.predArc(source) != graph.oppositeArc(edge)) {
+              dfs.predArc(source) != graph.oppositeArc(arc)) {
             return false;
           }
@@ -1360,9 +1430,9 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check that the given undirected graph is tree.
-  ///
-  /// Check that the given undirected graph is tree.
-  /// \param graph The undirected graph.
-  /// \return \c true when the graph is acyclic and connected.
+  /// \brief Check whether an undirected graph is tree.
+  ///
+  /// This function checks whether the given undirected graph is tree.
+  /// \return \c true if the graph is acyclic and connected.
+  /// \see acyclic(), connected()
   template <typename Graph>
   bool tree(const Graph& graph) {
@@ -1371,13 +1441,14 @@
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Arc Arc;
+    if (NodeIt(graph) == INVALID) return true;
     Dfs<Graph> dfs(graph);
     dfs.init();
     dfs.addSource(NodeIt(graph));
     while (!dfs.emptyQueue()) {
-      Arc edge = dfs.nextArc();
-      Node source = graph.source(edge);
-      Node target = graph.target(edge);
+      Arc arc = dfs.nextArc();
+      Node source = graph.source(arc);
+      Node target = graph.target(arc);
       if (dfs.reached(target) &&
-          dfs.predArc(source) != graph.oppositeArc(edge)) {
+          dfs.predArc(source) != graph.oppositeArc(arc)) {
         return false;
       }
@@ -1452,13 +1523,12 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check if the given undirected graph is bipartite or not
-  ///
-  /// The function checks if the given undirected \c graph graph is bipartite
-  /// or not. The \ref Bfs algorithm is used to calculate the result.
-  /// \param graph The undirected graph.
-  /// \return \c true if \c graph is bipartite, \c false otherwise.
-  /// \sa bipartitePartitions
+  /// \brief Check whether an undirected graph is bipartite.
+  ///
+  /// The function checks whether the given undirected graph is bipartite.
+  /// \return \c true if the graph is bipartite.
+  ///
+  /// \see bipartitePartitions()
   template<typename Graph>
-  inline bool bipartite(const Graph &graph){
+  bool bipartite(const Graph &graph){
     using namespace _connectivity_bits;
 
@@ -1489,10 +1559,8 @@
   /// \ingroup graph_properties
   ///
-  /// \brief Check if the given undirected graph is bipartite or not
-  ///
-  /// The function checks if the given undirected graph is bipartite
-  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
-  /// During the execution, the \c partMap will be set as the two
-  /// partitions of the graph.
+  /// \brief Find the bipartite partitions of an undirected graph.
+  ///
+  /// This function checks whether the given undirected graph is bipartite
+  /// and gives back the bipartite partitions.
   ///
   /// \image html bipartite_partitions.png
@@ -1500,12 +1568,16 @@
   ///
   /// \param graph The undirected graph.
-  /// \retval partMap A writable bool map of nodes. It will be set as the
-  /// two partitions of the graph.
-  /// \return \c true if \c graph is bipartite, \c false otherwise.
+  /// \retval partMap A writable node map of \c bool (or convertible) value
+  /// type. The values will be set to \c true for one component and
+  /// \c false for the other one.
+  /// \return \c true if the graph is bipartite, \c false otherwise.
+  ///
+  /// \see bipartite()
   template<typename Graph, typename NodeMap>
-  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
+  bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
     using namespace _connectivity_bits;
 
     checkConcept<concepts::Graph, Graph>();
+    checkConcept<concepts::WriteMap<typename Graph::Node, bool>, NodeMap>();
 
     typedef typename Graph::Node Node;
@@ -1532,51 +1604,57 @@
   }
 
-  /// \brief Returns true when there are not loop edges in the graph.
-  ///
-  /// Returns true when there are not loop edges in the graph.
-  template <typename Digraph>
-  bool loopFree(const Digraph& digraph) {
-    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
-      if (digraph.source(it) == digraph.target(it)) return false;
+  /// \ingroup graph_properties
+  ///
+  /// \brief Check whether the given graph contains no loop arcs/edges.
+  ///
+  /// This function returns \c true if there are no loop arcs/edges in
+  /// the given graph. It works for both directed and undirected graphs.
+  template <typename Graph>
+  bool loopFree(const Graph& graph) {
+    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {
+      if (graph.source(it) == graph.target(it)) return false;
     }
     return true;
   }
 
-  /// \brief Returns true when there are not parallel edges in the graph.
-  ///
-  /// Returns true when there are not parallel edges in the graph.
-  template <typename Digraph>
-  bool parallelFree(const Digraph& digraph) {
-    typename Digraph::template NodeMap<bool> reached(digraph, false);
-    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        if (reached[digraph.target(a)]) return false;
-        reached.set(digraph.target(a), true);
-      }
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        reached.set(digraph.target(a), false);
-      }
+  /// \ingroup graph_properties
+  ///
+  /// \brief Check whether the given graph contains no parallel arcs/edges.
+  ///
+  /// This function returns \c true if there are no parallel arcs/edges in
+  /// the given graph. It works for both directed and undirected graphs.
+  template <typename Graph>
+  bool parallelFree(const Graph& graph) {
+    typename Graph::template NodeMap<int> reached(graph, 0);
+    int cnt = 1;
+    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
+        if (reached[graph.target(a)] == cnt) return false;
+        reached[graph.target(a)] = cnt;
+      }
+      ++cnt;
     }
     return true;
   }
 
-  /// \brief Returns true when there are not loop edges and parallel
-  /// edges in the graph.
-  ///
-  /// Returns true when there are not loop edges and parallel edges in
-  /// the graph.
-  template <typename Digraph>
-  bool simpleDigraph(const Digraph& digraph) {
-    typename Digraph::template NodeMap<bool> reached(digraph, false);
-    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
-      reached.set(n, true);
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        if (reached[digraph.target(a)]) return false;
-        reached.set(digraph.target(a), true);
-      }
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        reached.set(digraph.target(a), false);
-      }
-      reached.set(n, false);
+  /// \ingroup graph_properties
+  ///
+  /// \brief Check whether the given graph is simple.
+  ///
+  /// This function returns \c true if the given graph is simple, i.e.
+  /// it contains no loop arcs/edges and no parallel arcs/edges.
+  /// The function works for both directed and undirected graphs.
+  /// \see loopFree(), parallelFree()
+  template <typename Graph>
+  bool simpleGraph(const Graph& graph) {
+    typename Graph::template NodeMap<int> reached(graph, 0);
+    int cnt = 1;
+    for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
+      reached[n] = cnt;
+      for (typename Graph::OutArcIt a(graph, n); a != INVALID; ++a) {
+        if (reached[graph.target(a)] == cnt) return false;
+        reached[graph.target(a)] = cnt;
+      }
+      ++cnt;
     }
     return true;
Index: lemon/edge_set.h
===================================================================
--- lemon/edge_set.h	(revision 664)
+++ lemon/edge_set.h	(revision 707)
@@ -23,5 +23,5 @@
 #include <lemon/bits/edge_set_extender.h>
 
-/// \ingroup semi_adaptors
+/// \ingroup graphs
 /// \file
 /// \brief ArcSet and EdgeSet classes.
@@ -231,5 +231,5 @@
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
@@ -655,5 +655,5 @@
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
@@ -914,5 +914,5 @@
 
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
@@ -1258,5 +1258,5 @@
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
Index: lemon/euler.h
===================================================================
--- lemon/euler.h	(revision 639)
+++ lemon/euler.h	(revision 695)
@@ -245,8 +245,8 @@
 
 
-  ///Check if the given graph is \e Eulerian
+  ///Check if the given graph is Eulerian
 
   /// \ingroup graph_properties
-  ///This function checks if the given graph is \e Eulerian.
+  ///This function checks if the given graph is Eulerian.
   ///It works for both directed and undirected graphs.
   ///
Index: lemon/glpk.h
===================================================================
--- lemon/glpk.h	(revision 623)
+++ lemon/glpk.h	(revision 697)
@@ -27,7 +27,8 @@
 
 // forward declaration
-#ifndef _GLP_PROB
+#if !defined _GLP_PROB && !defined GLP_PROB
 #define _GLP_PROB
-typedef struct { double _prob; } glp_prob;
+#define GLP_PROB
+typedef struct { double _opaque_prob; } glp_prob;
 /* LP/MIP problem object */
 #endif
Index: lemon/lemon.pc.in
===================================================================
--- lemon/lemon.pc.in	(revision 692)
+++ lemon/lemon.pc.in	(revision 705)
@@ -5,5 +5,5 @@
 
 Name: @PACKAGE_NAME@
-Description: Library of Efficient Models and Optimization in Networks
+Description: Library for Efficient Modeling and Optimization in Networks
 Version: @PACKAGE_VERSION@
 Libs: -L${libdir} -lemon @GLPK_LIBS@ @CPLEX_LIBS@ @SOPLEX_LIBS@ @CLP_LIBS@ @CBC_LIBS@
Index: lemon/matching.h
===================================================================
--- lemon/matching.h	(revision 641)
+++ lemon/matching.h	(revision 698)
@@ -500,5 +500,5 @@
     /// This function runs the original Edmonds' algorithm.
     ///
-    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     /// called before using this function.
     void startSparse() {
@@ -519,5 +519,5 @@
     /// shrinks, therefore resulting in a faster algorithm for dense graphs.
     ///
-    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
+    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     /// called before using this function.
     void startDense() {
Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 690)
+++ lemon/network_simplex.h	(revision 710)
@@ -20,5 +20,5 @@
 #define LEMON_NETWORK_SIMPLEX_H
 
-/// \ingroup min_cost_flow
+/// \ingroup min_cost_flow_algs
 ///
 /// \file
@@ -34,5 +34,5 @@
 namespace lemon {
 
-  /// \addtogroup min_cost_flow
+  /// \addtogroup min_cost_flow_algs
   /// @{
 
@@ -103,48 +103,14 @@
     /// constraints of the \ref min_cost_flow "minimum cost flow problem".
     ///
-    /// The default supply type is \c GEQ, since this form is supported
-    /// by other minimum cost flow algorithms and the \ref Circulation
-    /// algorithm, as well.
-    /// The \c LEQ problem type can be selected using the \ref supplyType()
-    /// function.
-    ///
-    /// Note that the equality form is a special case of both supply types.
+    /// The default supply type is \c GEQ, the \c LEQ type can be
+    /// selected using \ref supplyType().
+    /// The equality form is a special case of both supply types.
     enum SupplyType {
-
       /// This option means that there are <em>"greater or equal"</em>
-      /// supply/demand constraints in the definition, i.e. the exact
-      /// formulation of the problem is the following.
-      /**
-          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
-          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
-              sup(u) \quad \forall u\in V \f]
-          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-      */
-      /// It means that the total demand must be greater or equal to the 
-      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
-      /// negative) and all the supplies have to be carried out from 
-      /// the supply nodes, but there could be demands that are not 
-      /// satisfied.
+      /// supply/demand constraints in the definition of the problem.
       GEQ,
-      /// It is just an alias for the \c GEQ option.
-      CARRY_SUPPLIES = GEQ,
-
       /// This option means that there are <em>"less or equal"</em>
-      /// supply/demand constraints in the definition, i.e. the exact
-      /// formulation of the problem is the following.
-      /**
-          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
-          \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
-              sup(u) \quad \forall u\in V \f]
-          \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
-      */
-      /// It means that the total demand must be less or equal to the 
-      /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
-      /// positive) and all the demands have to be satisfied, but there
-      /// could be supplies that are not carried out from the supply
-      /// nodes.
-      LEQ,
-      /// It is just an alias for the \c LEQ option.
-      SATISFY_DEMANDS = LEQ
+      /// supply/demand constraints in the definition of the problem.
+      LEQ
     };
     
@@ -216,4 +182,6 @@
     int _node_num;
     int _arc_num;
+    int _all_arc_num;
+    int _search_arc_num;
 
     // Parameters of the problem
@@ -278,5 +246,5 @@
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
@@ -289,5 +257,6 @@
         _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+        _next_arc(0)
       {}
 
@@ -295,5 +264,5 @@
       bool findEnteringArc() {
         Cost c;
-        for (int e = _next_arc; e < _arc_num; ++e) {
+        for (int e = _next_arc; e < _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
@@ -329,5 +298,5 @@
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
     public:
@@ -337,5 +306,5 @@
         _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns.in_arc), _arc_num(ns._arc_num)
+        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num)
       {}
 
@@ -343,5 +312,5 @@
       bool findEnteringArc() {
         Cost c, min = 0;
-        for (int e = 0; e < _arc_num; ++e) {
+        for (int e = 0; e < _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
@@ -368,5 +337,5 @@
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
@@ -380,12 +349,13 @@
         _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+        _next_arc(0)
       {
         // The main parameters of the pivot rule
-        const double BLOCK_SIZE_FACTOR = 2.0;
+        const double BLOCK_SIZE_FACTOR = 0.5;
         const int MIN_BLOCK_SIZE = 10;
 
         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
-                                    std::sqrt(double(_arc_num))),
+                                    std::sqrt(double(_search_arc_num))),
                                 MIN_BLOCK_SIZE );
       }
@@ -396,5 +366,5 @@
         int cnt = _block_size;
         int e, min_arc = _next_arc;
-        for (e = _next_arc; e < _arc_num; ++e) {
+        for (e = _next_arc; e < _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
@@ -441,5 +411,5 @@
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
@@ -455,5 +425,6 @@
         _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+        _next_arc(0)
       {
         // The main parameters of the pivot rule
@@ -464,5 +435,5 @@
 
         _list_length = std::max( int(LIST_LENGTH_FACTOR *
-                                     std::sqrt(double(_arc_num))),
+                                     std::sqrt(double(_search_arc_num))),
                                  MIN_LIST_LENGTH );
         _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length),
@@ -501,5 +472,5 @@
         min = 0;
         _curr_length = 0;
-        for (e = _next_arc; e < _arc_num; ++e) {
+        for (e = _next_arc; e < _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < 0) {
@@ -547,5 +518,5 @@
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
@@ -575,6 +546,6 @@
         _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns.in_arc), _arc_num(ns._arc_num),
-        _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
+        _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num),
+        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
       {
         // The main parameters of the pivot rule
@@ -585,5 +556,5 @@
 
         _block_size = std::max( int(BLOCK_SIZE_FACTOR *
-                                    std::sqrt(double(_arc_num))),
+                                    std::sqrt(double(_search_arc_num))),
                                 MIN_BLOCK_SIZE );
         _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size),
@@ -611,5 +582,5 @@
         int limit = _head_length;
 
-        for (int e = _next_arc; e < _arc_num; ++e) {
+        for (int e = _next_arc; e < _search_arc_num; ++e) {
           _cand_cost[e] = _state[e] *
             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
@@ -679,15 +650,15 @@
       _arc_num = countArcs(_graph);
       int all_node_num = _node_num + 1;
-      int all_arc_num = _arc_num + _node_num;
-
-      _source.resize(all_arc_num);
-      _target.resize(all_arc_num);
-
-      _lower.resize(all_arc_num);
-      _upper.resize(all_arc_num);
-      _cap.resize(all_arc_num);
-      _cost.resize(all_arc_num);
+      int max_arc_num = _arc_num + 2 * _node_num;
+
+      _source.resize(max_arc_num);
+      _target.resize(max_arc_num);
+
+      _lower.resize(_arc_num);
+      _upper.resize(_arc_num);
+      _cap.resize(max_arc_num);
+      _cost.resize(max_arc_num);
       _supply.resize(all_node_num);
-      _flow.resize(all_arc_num);
+      _flow.resize(max_arc_num);
       _pi.resize(all_node_num);
 
@@ -699,5 +670,5 @@
       _succ_num.resize(all_node_num);
       _last_succ.resize(all_node_num);
-      _state.resize(all_arc_num);
+      _state.resize(max_arc_num);
 
       // Copy the graph (store the arcs in a mixed order)
@@ -1070,5 +1041,5 @@
       Cost ART_COST;
       if (std::numeric_limits<Cost>::is_exact) {
-        ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;
+        ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
       } else {
         ART_COST = std::numeric_limits<Cost>::min();
@@ -1094,26 +1065,118 @@
       _last_succ[_root] = _root - 1;
       _supply[_root] = -_sum_supply;
-      _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;
+      _pi[_root] = 0;
 
       // Add artificial arcs and initialize the spanning tree data structure
-      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
-        _parent[u] = _root;
-        _pred[u] = e;
-        _thread[u] = u + 1;
-        _rev_thread[u + 1] = u;
-        _succ_num[u] = 1;
-        _last_succ[u] = u;
-        _cost[e] = ART_COST;
-        _cap[e] = INF;
-        _state[e] = STATE_TREE;
-        if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
-          _flow[e] = _supply[u];
-          _forward[u] = true;
-          _pi[u] = -ART_COST + _pi[_root];
-        } else {
-          _flow[e] = -_supply[u];
-          _forward[u] = false;
-          _pi[u] = ART_COST + _pi[_root];
-        }
+      if (_sum_supply == 0) {
+        // EQ supply constraints
+        _search_arc_num = _arc_num;
+        _all_arc_num = _arc_num + _node_num;
+        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+          _parent[u] = _root;
+          _pred[u] = e;
+          _thread[u] = u + 1;
+          _rev_thread[u + 1] = u;
+          _succ_num[u] = 1;
+          _last_succ[u] = u;
+          _cap[e] = INF;
+          _state[e] = STATE_TREE;
+          if (_supply[u] >= 0) {
+            _forward[u] = true;
+            _pi[u] = 0;
+            _source[e] = u;
+            _target[e] = _root;
+            _flow[e] = _supply[u];
+            _cost[e] = 0;
+          } else {
+            _forward[u] = false;
+            _pi[u] = ART_COST;
+            _source[e] = _root;
+            _target[e] = u;
+            _flow[e] = -_supply[u];
+            _cost[e] = ART_COST;
+          }
+        }
+      }
+      else if (_sum_supply > 0) {
+        // LEQ supply constraints
+        _search_arc_num = _arc_num + _node_num;
+        int f = _arc_num + _node_num;
+        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+          _parent[u] = _root;
+          _thread[u] = u + 1;
+          _rev_thread[u + 1] = u;
+          _succ_num[u] = 1;
+          _last_succ[u] = u;
+          if (_supply[u] >= 0) {
+            _forward[u] = true;
+            _pi[u] = 0;
+            _pred[u] = e;
+            _source[e] = u;
+            _target[e] = _root;
+            _cap[e] = INF;
+            _flow[e] = _supply[u];
+            _cost[e] = 0;
+            _state[e] = STATE_TREE;
+          } else {
+            _forward[u] = false;
+            _pi[u] = ART_COST;
+            _pred[u] = f;
+            _source[f] = _root;
+            _target[f] = u;
+            _cap[f] = INF;
+            _flow[f] = -_supply[u];
+            _cost[f] = ART_COST;
+            _state[f] = STATE_TREE;
+            _source[e] = u;
+            _target[e] = _root;
+            _cap[e] = INF;
+            _flow[e] = 0;
+            _cost[e] = 0;
+            _state[e] = STATE_LOWER;
+            ++f;
+          }
+        }
+        _all_arc_num = f;
+      }
+      else {
+        // GEQ supply constraints
+        _search_arc_num = _arc_num + _node_num;
+        int f = _arc_num + _node_num;
+        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
+          _parent[u] = _root;
+          _thread[u] = u + 1;
+          _rev_thread[u + 1] = u;
+          _succ_num[u] = 1;
+          _last_succ[u] = u;
+          if (_supply[u] <= 0) {
+            _forward[u] = false;
+            _pi[u] = 0;
+            _pred[u] = e;
+            _source[e] = _root;
+            _target[e] = u;
+            _cap[e] = INF;
+            _flow[e] = -_supply[u];
+            _cost[e] = 0;
+            _state[e] = STATE_TREE;
+          } else {
+            _forward[u] = true;
+            _pi[u] = -ART_COST;
+            _pred[u] = f;
+            _source[f] = u;
+            _target[f] = _root;
+            _cap[f] = INF;
+            _flow[f] = _supply[u];
+            _state[f] = STATE_TREE;
+            _cost[f] = ART_COST;
+            _source[e] = _root;
+            _target[e] = u;
+            _cap[e] = INF;
+            _flow[e] = 0;
+            _cost[e] = 0;
+            _state[e] = STATE_LOWER;
+            ++f;
+          }
+        }
+        _all_arc_num = f;
       }
 
@@ -1375,18 +1438,6 @@
       
       // Check feasibility
-      if (_sum_supply < 0) {
-        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
-          if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE;
-        }
-      }
-      else if (_sum_supply > 0) {
-        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
-          if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE;
-        }
-      }
-      else {
-        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
-          if (_flow[e] != 0) return INFEASIBLE;
-        }
+      for (int e = _search_arc_num; e != _all_arc_num; ++e) {
+        if (_flow[e] != 0) return INFEASIBLE;
       }
 
@@ -1402,4 +1453,28 @@
         }
       }
+      
+      // Shift potentials to meet the requirements of the GEQ/LEQ type
+      // optimality conditions
+      if (_sum_supply == 0) {
+        if (_stype == GEQ) {
+          Cost max_pot = std::numeric_limits<Cost>::min();
+          for (int i = 0; i != _node_num; ++i) {
+            if (_pi[i] > max_pot) max_pot = _pi[i];
+          }
+          if (max_pot > 0) {
+            for (int i = 0; i != _node_num; ++i)
+              _pi[i] -= max_pot;
+          }
+        } else {
+          Cost min_pot = std::numeric_limits<Cost>::max();
+          for (int i = 0; i != _node_num; ++i) {
+            if (_pi[i] < min_pot) min_pot = _pi[i];
+          }
+          if (min_pot < 0) {
+            for (int i = 0; i != _node_num; ++i)
+              _pi[i] -= min_pot;
+          }
+        }
+      }
 
       return OPTIMAL;
