# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1242126595 -3600
# Node ID c01a98ce01fd88fb40ab5e4b1e2c0c5be2ad93b5
# Parent  189760a7cdd0d71c2d3ae8727ab5d589944f374d# Parent  e652b6f9a29f6654b2a48148cd5243587baf0b6d
Merge

diff -r 189760a7cdd0 -r c01a98ce01fd CMakeLists.txt
--- a/CMakeLists.txt	Thu May 07 02:05:12 2009 +0200
+++ b/CMakeLists.txt	Tue May 12 12:09:55 2009 +0100
@@ -44,7 +44,7 @@
     SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
     SET(CPACK_PACKAGE_VENDOR "EGRES")
     SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY
-      "LEMON - Library of Efficient Models and Optimization in Networks")
+      "LEMON - Library for Efficient Modeling and Optimization in Networks")
     SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
 
     SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
diff -r 189760a7cdd0 -r c01a98ce01fd NEWS
--- a/NEWS	Thu May 07 02:05:12 2009 +0200
+++ b/NEWS	Tue May 12 12:09:55 2009 +0100
@@ -1,3 +1,90 @@
+2009-05-13 Version 1.1 released
+
+        This is the second stable release of the 1.x series. It
+        features a better coverage of the tools available in the 0.x
+        series, a thoroughly reworked LP/MIP interface plus various
+        improvements in the existing tools.
+
+        * Much improved M$ Windows support
+          * Various improvements in the CMAKE build system
+          * Compilation warnings are fixed/suppressed
+        * Support IBM xlC compiler
+        * New algorithms
+          * Connectivity related algorithms (#61)
+          * Euler walks (#65)
+          * Preflow push-relabel max. flow algorithm (#176)
+          * Circulation algorithm (push-relabel based) (#175)
+          * Suurballe algorithm (#47)
+          * Gomory-Hu algorithm (#66)
+          * Hao-Orlin algorithm (#58)
+          * Edmond's maximum cardinality and weighted matching algorithms
+            in general graphs (#48,#265)
+          * Minimum cost arborescence/branching (#60)
+          * Network Simplex min. cost flow algorithm (#234)
+        * New data structures
+          * Full graph structure (#57)
+          * Grid graph structure (#57)
+          * Hypercube graph structure (#57)
+          * Graph adaptors (#67)
+          * ArcSet and EdgeSet classes (#67)
+          * Elevator class (#174)
+        * Other new tools
+          * LP/MIP interface (#44)
+            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
+          * Reader for the Nauty file format (#55)
+          * DIMACS readers (#167)
+          * Radix sort algorithms (#72)
+          * RangeIdMap and CrossRefMap (#160)
+        * New command line tools
+          * DIMACS to LGF converter (#182)
+          * lgf-gen - a graph generator (#45)
+          * DIMACS solver utility (#226)
+        * Other code improvements
+          * Lognormal distribution added to Random (#102)
+          * Better (i.e. O(1) time) item counting in SmartGraph (#3)
+          * The standard maps of graphs are guaranteed to be
+            reference maps (#190)
+        * Miscellaneous
+          * Various doc improvements
+          * Improved 0.x -> 1.x converter script
+
+        * Several bugfixes (compared to release 1.0):
+          #170: Bugfix SmartDigraph::split()
+          #171: Bugfix in SmartGraph::restoreSnapshot()
+          #172: Extended test cases for graphs and digraphs
+          #173: Bugfix in Random
+                * operator()s always return a double now
+                * the faulty real<Num>(Num) and real<Num>(Num,Num)
+                  have been removed
+          #187: Remove DijkstraWidestPathOperationTraits
+          #61:  Bugfix in DfsVisit
+          #193: Bugfix in GraphReader::skipSection()
+          #195: Bugfix in ConEdgeIt()
+          #197: Bugfix in heap unionfind
+                * This bug affects Edmond's general matching algorithms
+          #207: Fix 'make install' without 'make html' using CMAKE
+          #208: Suppress or fix VS2008 compilation warnings
+          ----: Update the LEMON icon
+          ----: Enable the component-based installer
+                (in installers made by CPACK)
+          ----: Set the proper version for CMAKE in the tarballs
+                (made by autotools)
+          ----: Minor clarification in the LICENSE file
+          ----: Add missing unistd.h include to time_measure.h
+          #204: Compilation bug fixed in graph_to_eps.h with VS2005
+          #214,#215: windows.h should never be included by lemon headers
+          #230: Build systems check the availability of 'long long' type
+          #229: Default implementation of Tolerance<> is used for integer types
+          #211,#212: Various fixes for compiling on AIX
+          ----: Improvements in CMAKE config
+                - docs is installed in share/doc/
+                - detects newer versions of Ghostscript
+          #239: Fix missing 'inline' specifier in time_measure.h
+          #274,#280: Install lemon/config.h
+          #275: Prefix macro names with LEMON_ in lemon/config.h
+          ----: Small script for making the release tarballs added
+          ----: Minor improvement in unify-sources.sh (a76f55d7d397)
+
 2009-03-27 LEMON joins to the COIN-OR initiative
 
         COIN-OR (Computational Infrastructure for Operations Research,
diff -r 189760a7cdd0 -r c01a98ce01fd README
--- a/README	Thu May 07 02:05:12 2009 +0200
+++ b/README	Tue May 12 12:09:55 2009 +0100
@@ -1,6 +1,6 @@
-==================================================================
-LEMON - a Library of Efficient Models and Optimization in Networks
-==================================================================
+=====================================================================
+LEMON - a Library for Efficient Modeling and Optimization in Networks
+=====================================================================
 
 LEMON is an open source library written in C++. It provides
 easy-to-use implementations of common data structures and algorithms
diff -r 189760a7cdd0 -r c01a98ce01fd doc/Makefile.am
--- a/doc/Makefile.am	Thu May 07 02:05:12 2009 +0200
+++ b/doc/Makefile.am	Tue May 12 12:09:55 2009 +0100
@@ -8,6 +8,7 @@
 	doc/license.dox \
 	doc/mainpage.dox \
 	doc/migration.dox \
+	doc/min_cost_flow.dox \
 	doc/named-param.dox \
 	doc/namespaces.dox \
 	doc/html \
diff -r 189760a7cdd0 -r c01a98ce01fd doc/groups.dox
--- a/doc/groups.dox	Thu May 07 02:05:12 2009 +0200
+++ b/doc/groups.dox	Tue May 12 12:09:55 2009 +0100
@@ -138,16 +138,6 @@
 */
 
 /**
-@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
-@ingroup graphs
-\brief Graph types between real graphs and graph adaptors.
-
-This group contains some graph types between real graphs and graph adaptors.
-These classes wrap graphs to give new functionality as the adaptors do it.
-On the other hand they are not light-weight structures as the adaptors.
-*/
-
-/**
 @defgroup maps Maps
 @ingroup datas
 \brief Map structures implemented in LEMON.
@@ -315,6 +305,7 @@
 Tarjan for solving this problem. It also provides functions to query the
 minimum cut, which is the dual problem of maximum flow.
 
+
 \ref Circulation is a preflow push-relabel algorithm implemented directly 
 for finding feasible circulations, which is a somewhat different problem,
 but it is strongly related to maximum flow.
@@ -322,86 +313,14 @@
 */
 
 /**
-@defgroup min_cost_flow Minimum Cost Flow Algorithms
+@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 @ingroup algs
 
 \brief Algorithms for finding minimum cost flows and circulations.
 
 This group contains the algorithms for finding minimum cost flows and
-circulations.
-
-The \e minimum \e cost \e flow \e problem is to find a feasible flow of
-minimum total cost from a set of supply nodes to a set of demand nodes
-in a network with capacity constraints (lower and upper bounds)
-and arc costs.
-Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
-\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
-upper bounds for the flow values on the arcs, for which
-\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
-\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
-on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
-signed supply values of the nodes.
-If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
-supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
-\f$-sup(u)\f$ demand.
-A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
-of the following optimization problem.
-
-\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]
-
-The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
-zero or negative in order to have a feasible solution (since the sum
-of the expressions on the left-hand side of the inequalities is zero).
-It means that the total demand must be greater or equal to the total
-supply and all the supplies have to be carried out from the supply nodes,
-but there could be demands that are not satisfied.
-If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
-constraints have to be satisfied with equality, i.e. all demands
-have to be satisfied and all supplies have to be used.
-
-If you need the opposite inequalities in the supply/demand constraints
-(i.e. the total demand is less than the total supply and all the demands
-have to be satisfied while there could be supplies that are not used),
-then you could easily transform the problem to the above form by reversing
-the direction of the arcs and taking the negative of the supply values
-(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
-However \ref NetworkSimplex algorithm also supports this form directly
-for the sake of convenience.
-
-A feasible solution for this problem can be found using \ref Circulation.
-
-Note that the above formulation is actually more general than the usual
-definition of the minimum cost flow problem, in which strict equalities
-are required in the supply/demand contraints, i.e.
-
-\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
-    sup(u) \quad \forall u\in V. \f]
-
-However if the sum of the supply values is zero, then these two problems
-are equivalent. So if you need the equality form, you have to ensure this
-additional contraint for the algorithms.
-
-The dual solution of the minimum cost flow problem is represented by node 
-potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
-An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
-is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
-node potentials the following \e complementary \e slackness optimality
-conditions hold.
-
- - For all \f$uv\in A\f$ arcs:
-   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
-   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
-   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- - For all \f$u\in V\f$ nodes:
-   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
-     then \f$\pi(u)=0\f$.
- 
-Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
-\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
-\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
+circulations. For more information about this problem and its dual
+solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 
 \ref NetworkSimplex is an efficient implementation of the primal Network
 Simplex algorithm for finding minimum cost flows. It also provides dual
@@ -479,10 +398,10 @@
 /**
 @defgroup spantree Minimum Spanning Tree Algorithms
 @ingroup algs
-\brief Algorithms for finding a minimum cost spanning tree in a graph.
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
 
-This group contains the algorithms for finding a minimum cost spanning
-tree in a graph.
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
 */
 
 /**
diff -r 189760a7cdd0 -r c01a98ce01fd doc/mainpage.dox
--- a/doc/mainpage.dox	Thu May 07 02:05:12 2009 +0200
+++ b/doc/mainpage.dox	Tue May 12 12:09:55 2009 +0100
@@ -23,8 +23,7 @@
 
 \subsection whatis What is LEMON
 
-LEMON stands for
-<b>L</b>ibrary of <b>E</b>fficient <b>M</b>odels
+LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 and <b>O</b>ptimization in <b>N</b>etworks.
 It is a C++ template
 library aimed at combinatorial optimization tasks which
@@ -41,14 +40,10 @@
 
 \subsection howtoread How to read the documentation
 
-If you want to get a quick start and see the most important features then
-take a look at our \ref quicktour
-"Quick Tour to LEMON" which will guide you along.
-
-If you already feel like using our library, see the
+If you would like to get to know the library, see
 <a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 
-If you know what you are looking for then try to find it under the
+If you know what you are looking for, then try to find it under the
 <a class="el" href="modules.html">Modules</a> section.
 
 If you are a user of the old (0.x) series of LEMON, please check out the
diff -r 189760a7cdd0 -r c01a98ce01fd doc/min_cost_flow.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/min_cost_flow.dox	Tue May 12 12:09:55 2009 +0100
@@ -0,0 +1,153 @@
+/* -*- 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.
+ *
+ */
+
+namespace lemon {
+
+/**
+\page min_cost_flow Minimum Cost Flow Problem
+
+\section mcf_def Definition (GEQ form)
+
+The \e minimum \e cost \e flow \e problem is to find a feasible flow of
+minimum total cost from a set of supply nodes to a set of demand nodes
+in a network with capacity constraints (lower and upper bounds)
+and arc costs.
+
+Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
+\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
+upper bounds for the flow values on the arcs, for which
+\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
+\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
+on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
+signed supply values of the nodes.
+If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
+supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
+\f$-sup(u)\f$ demand.
+A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
+of the following optimization problem.
+
+\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]
+
+The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
+zero or negative in order to have a feasible solution (since the sum
+of the expressions on the left-hand side of the inequalities is zero).
+It means that the total demand must be greater or equal to the total
+supply and all the supplies have to be carried out from the supply nodes,
+but there could be demands that are not satisfied.
+If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
+constraints have to be satisfied with equality, i.e. all demands
+have to be satisfied and all supplies have to be used.
+
+
+\section mcf_algs Algorithms
+
+LEMON contains several algorithms for solving this problem, for more
+information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
+
+A feasible solution for this problem can be found using \ref Circulation.
+
+
+\section mcf_dual Dual Solution
+
+The dual solution of the minimum cost flow problem is represented by
+node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
+An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
+if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
+the following \e complementary \e slackness optimality conditions hold.
+
+ - For all \f$uv\in A\f$ arcs:
+   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
+   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
+   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
+ - For all \f$u\in V\f$ nodes:
+   - \f$\pi(u)<=0\f$;
+   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
+     then \f$\pi(u)=0\f$.
+ 
+Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
+\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
+\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
+
+All algorithms provide dual solution (node potentials), as well,
+if an optimal flow is found.
+
+
+\section mcf_eq Equality Form
+
+The above \ref mcf_def "definition" is actually more general than the
+usual formulation of the minimum cost flow problem, in which strict
+equalities are required in the supply/demand contraints.
+
+\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) =
+    sup(u) \quad \forall u\in V \f]
+\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
+
+However if the sum of the supply values is zero, then these two problems
+are equivalent.
+The \ref min_cost_flow_algs "algorithms" in LEMON support the general
+form, so if you need the equality form, you have to ensure this additional
+contraint manually.
+
+
+\section mcf_leq Opposite Inequalites (LEQ Form)
+
+Another possible definition of the minimum cost flow problem is
+when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
+instead of the <em>"greater or equal"</em> (GEQ) constraints.
+
+\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.
+The equality form is also a special case of this form, of course.
+
+You could easily transform this case to the \ref mcf_def "GEQ form"
+of the problem by reversing the direction of the arcs and taking the
+negative of the supply values (e.g. using \ref ReverseDigraph and
+\ref NegMap adaptors).
+However \ref NetworkSimplex algorithm also supports this form directly
+for the sake of convenience.
+
+Note that the optimality conditions for this supply constraint type are
+slightly differ from the conditions that are discussed for the GEQ form,
+namely the potentials have to be non-negative instead of non-positive.
+An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
+is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
+node potentials the following conditions hold.
+
+ - For all \f$uv\in A\f$ arcs:
+   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
+   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
+   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
+ - For all \f$u\in V\f$ nodes:
+   - \f$\pi(u)>=0\f$;
+   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
+     then \f$\pi(u)=0\f$.
+
+*/
+}
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/Makefile.am
--- a/lemon/Makefile.am	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/Makefile.am	Tue May 12 12:09:55 2009 +0100
@@ -111,7 +111,6 @@
 bits_HEADERS += \
 	lemon/bits/alteration_notifier.h \
 	lemon/bits/array_map.h \
-	lemon/bits/base_extender.h \
 	lemon/bits/bezier.h \
 	lemon/bits/default_map.h \
 	lemon/bits/edge_set_extender.h \
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/adaptors.h
--- a/lemon/adaptors.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/adaptors.h	Tue May 12 12:09:55 2009 +0100
@@ -1839,31 +1839,31 @@
     typedef typename Digraph::Arc Edge;
     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);
       }
     };
 
@@ -1876,7 +1876,7 @@
     }
 
     void first(Arc& a) const {
-      _digraph->first(a);
+      _digraph->first(a._edge);
       a._forward = true;
     }
 
@@ -1884,7 +1884,7 @@
       if (a._forward) {
         a._forward = false;
       } else {
-        _digraph->next(a);
+        _digraph->next(a._edge);
         a._forward = true;
       }
     }
@@ -1898,48 +1898,48 @@
     }
 
     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;
       }
     }
     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;
       }
     }
     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);
       }
     }
 
@@ -1972,19 +1972,16 @@
     }
 
     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);
-    }
 
     static bool direction(const Arc &a) { return a._forward; }
 
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/bits/base_extender.h
--- a/lemon/bits/base_extender.h	Thu May 07 02:05:12 2009 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,495 +0,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
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/concepts/graph.h
--- a/lemon/concepts/graph.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/concepts/graph.h	Tue May 12 12:09:55 2009 +0100
@@ -310,8 +310,8 @@
 
       /// 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
 
@@ -322,7 +322,7 @@
 
         /// Copy constructor.
         ///
-        Arc(const Arc& e) : Edge(e) { }
+        Arc(const Arc&) { }
         /// Initialize the iterator to be invalid.
 
         /// Initialize the iterator to be invalid.
@@ -349,6 +349,8 @@
         /// ordering of the items.
         bool operator<(Arc) const { return false; }
 
+        /// Converison to Edge
+        operator Edge() const { return Edge(); }
       };
       /// This iterator goes through each directed arc.
 
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/connectivity.h
--- a/lemon/connectivity.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/connectivity.h	Tue May 12 12:09:55 2009 +0100
@@ -42,12 +42,16 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check whether the given undirected graph is connected.
+  /// \brief Check whether an 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.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -67,12 +71,18 @@
   ///
   /// \brief Count the number of connected components of an undirected graph
   ///
-  /// Count the number of connected components of an undirected graph
+  /// This function counts the number of connected components of the given
+  /// undirected graph.
   ///
-  /// \param graph The graph. It must be undirected.
-  /// \return The number of components
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -109,17 +119,26 @@
   ///
   /// \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) {
     checkConcept<concepts::Graph, Graph>();
@@ -231,15 +250,17 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check whether the given directed graph is strongly connected.
+  /// \brief Check whether a 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
+  /// 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) {
     checkConcept<concepts::Digraph, Digraph>();
@@ -270,7 +291,7 @@
     typedef typename RDigraph::NodeIt RNodeIt;
     RDigraph rdigraph(digraph);
 
-    typedef DfsVisitor<Digraph> RVisitor;
+    typedef DfsVisitor<RDigraph> RVisitor;
     RVisitor rvisitor;
 
     DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
@@ -289,18 +310,22 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Count the strongly connected components of a directed graph
+  /// \brief Count the number of strongly connected components of a 
+  /// directed graph
   ///
-  /// Count the 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) {
     checkConcept<concepts::Digraph, Digraph>();
@@ -355,13 +380,15 @@
   ///
   /// \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
   /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth
@@ -369,9 +396,13 @@
   /// \param digraph The digraph.
   /// \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) {
     checkConcept<concepts::Digraph, Digraph>();
@@ -424,19 +455,24 @@
   ///
   /// \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.
+  /// \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.
   ///
-  /// \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;
     typedef typename Digraph::Arc Arc;
@@ -448,13 +484,13 @@
     typedef std::vector<Node> Container;
     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);
         dfs.start();
@@ -464,14 +500,14 @@
     typedef typename Container::reverse_iterator RIterator;
     typedef ReverseDigraph<const Digraph> RDigraph;
 
-    RDigraph rgraph(graph);
+    RDigraph rdigraph(digraph);
 
     int cutNum = 0;
 
     typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
-    RVisitor rvisitor(rgraph, cutMap, cutNum);
+    RVisitor rvisitor(rdigraph, cutMap, cutNum);
 
-    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
+    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 
     rdfs.init();
     for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
@@ -706,14 +742,15 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Checks the graph is bi-node-connected.
+  /// \brief Check whether an undirected 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.
+  /// This function checks whether the given undirected graph is 
+  /// bi-node-connected, i.e. any two edges are on same circle.
   ///
-  /// \param graph The graph.
-  /// \return \c true when the graph bi-node-connected.
+  /// \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) {
     return countBiNodeConnectedComponents(graph) <= 1;
@@ -721,15 +758,19 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Count the biconnected components.
+  /// \brief Count the number of bi-node-connected components of an 
+  /// undirected graph.
   ///
-  /// 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.
+  /// This function counts the number of bi-node-connected components of
+  /// the given undirected graph.
   ///
-  /// \param graph The graph.
-  /// \return The number of components.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -756,22 +797,26 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-node-connected components.
+  /// \brief Find the bi-node-connected components of an undirected graph.
   ///
-  /// 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.
+  /// 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,
                                 EdgeMap& compMap) {
@@ -801,18 +846,25 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-node-connected cut nodes.
+  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
   ///
-  /// 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.
+  /// This function finds the bi-node-connected cut nodes in the given
+  /// undirected graph.
   ///
-  /// \param graph The graph.
-  /// \retval cutMap A writable edge map. The values will be set true when
-  /// the node separate two or more components.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -1031,14 +1083,16 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Checks that the graph is bi-edge-connected.
+  /// \brief Check whether an undirected 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.
+  /// 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.
   ///
-  /// \param graph The undirected graph.
-  /// \return The number of components.
+  /// \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) {
     return countBiEdgeConnectedComponents(graph) <= 1;
@@ -1046,15 +1100,20 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Count the bi-edge-connected components.
+  /// \brief Count the number of bi-edge-connected components of an
+  /// undirected graph.
   ///
-  /// 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.
+  /// This function counts the number of bi-edge-connected components of
+  /// the given undirected graph.
   ///
-  /// \param graph The undirected graph.
-  /// \return The number of components.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -1081,22 +1140,27 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-edge-connected components.
+  /// \brief Find the bi-edge-connected components of an undirected graph.
   ///
-  /// 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.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -1125,19 +1189,25 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Find the bi-edge-connected cut edges.
+  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
   ///
-  /// 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.
+  /// This function finds the bi-edge-connected cut edges in the given
+  /// undirected graph. 
   ///
-  /// \param graph The graph.
-  /// \retval cutMap A writable node map. The values will be set true when the
-  /// edge is a cut edge.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -1189,19 +1259,62 @@
 
   /// \ingroup graph_properties
   ///
+  /// \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>();
+
+    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 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.
   ///
-  /// Sort the nodes of a DAG into topolgical order.
+  /// This function sorts the nodes of the given acyclic digraph (DAG)
+  /// into topolgical order.
   ///
-  /// \param graph The graph. It must be directed and acyclic.
+  /// \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 graph minus one. Each values of the map
-  /// will be set exactly once, the values  will be set descending order.
+  /// 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 checkedTopologicalSort
-  /// \see dag
+  /// \see dag(), checkedTopologicalSort()
   template <typename Digraph, typename NodeMap>
-  void topologicalSort(const Digraph& graph, NodeMap& order) {
+  void topologicalSort(const Digraph& digraph, NodeMap& order) {
     using namespace _connectivity_bits;
 
     checkConcept<concepts::Digraph, Digraph>();
@@ -1212,13 +1325,13 @@
     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);
         dfs.start();
@@ -1230,18 +1343,18 @@
   ///
   /// \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.
+  /// 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 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.
+  /// \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 topologicalSort
-  /// \see dag
+  /// \see dag(), topologicalSort()
   template <typename Digraph, typename NodeMap>
   bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
     using namespace _connectivity_bits;
@@ -1283,54 +1396,11 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check that the given directed graph is a DAG.
+  /// \brief Check whether an undirected graph is acyclic.
   ///
-  /// 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
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
@@ -1343,11 +1413,11 @@
       if (!dfs.reached(it)) {
         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;
           }
           dfs.processNextArc();
@@ -1359,26 +1429,27 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check that the given undirected graph is tree.
+  /// \brief Check whether an 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.
+  /// 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) {
     checkConcept<concepts::Graph, Graph>();
     typedef typename Graph::Node Node;
     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;
       }
       dfs.processNextArc();
@@ -1451,15 +1522,14 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check if the given undirected graph is bipartite or not
+  /// \brief Check whether an undirected graph is bipartite.
   ///
-  /// 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
+  /// 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;
 
     checkConcept<concepts::Graph, Graph>();
@@ -1488,25 +1558,27 @@
 
   /// \ingroup graph_properties
   ///
-  /// \brief Check if the given undirected graph is bipartite or not
+  /// \brief Find the bipartite partitions of an undirected graph.
   ///
-  /// 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.
+  /// This function checks whether the given undirected graph is bipartite
+  /// and gives back the bipartite partitions.
   ///
   /// \image html bipartite_partitions.png
   /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth
   ///
   /// \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;
     typedef typename Graph::NodeIt NodeIt;
@@ -1531,53 +1603,59 @@
     return true;
   }
 
-  /// \brief Returns true when there are not loop edges in the graph.
+  /// \ingroup graph_properties
   ///
-  /// 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;
+  /// \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.
+  /// \ingroup graph_properties
   ///
-  /// 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);
+  /// \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;
       }
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        reached.set(digraph.target(a), false);
-      }
+      ++cnt;
     }
     return true;
   }
 
-  /// \brief Returns true when there are not loop edges and parallel
-  /// edges in the graph.
+  /// \ingroup graph_properties
   ///
-  /// 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);
+  /// \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;
       }
-      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-        reached.set(digraph.target(a), false);
-      }
-      reached.set(n, false);
+      ++cnt;
     }
     return true;
   }
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/edge_set.h
--- a/lemon/edge_set.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/edge_set.h	Tue May 12 12:09:55 2009 +0100
@@ -22,7 +22,7 @@
 #include <lemon/core.h>
 #include <lemon/bits/edge_set_extender.h>
 
-/// \ingroup semi_adaptors
+/// \ingroup graphs
 /// \file
 /// \brief ArcSet and EdgeSet classes.
 ///
@@ -230,7 +230,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
   /// an own arc set.
@@ -654,7 +654,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
   /// own edge set.
@@ -913,7 +913,7 @@
   };
 
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Digraph using a node set of another digraph or graph and
   /// an own arc set.
@@ -1257,7 +1257,7 @@
 
   };
 
-  /// \ingroup semi_adaptors
+  /// \ingroup graphs
   ///
   /// \brief Graph using a node set of another digraph or graph and an
   /// own edge set.
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/euler.h
--- a/lemon/euler.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/euler.h	Tue May 12 12:09:55 2009 +0100
@@ -244,10 +244,10 @@
   };
 
 
-  ///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.
   ///
   ///By definition, a digraph is called \e Eulerian if
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/glpk.h
--- a/lemon/glpk.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/glpk.h	Tue May 12 12:09:55 2009 +0100
@@ -26,9 +26,10 @@
 #include <lemon/lp_base.h>
 
 // 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
 
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/lemon.pc.in
--- a/lemon/lemon.pc.in	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/lemon.pc.in	Tue May 12 12:09:55 2009 +0100
@@ -4,7 +4,7 @@
 includedir=@includedir@
 
 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@
 Cflags: -I${includedir}
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/matching.h
--- a/lemon/matching.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/matching.h	Tue May 12 12:09:55 2009 +0100
@@ -499,7 +499,7 @@
     ///
     /// 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() {
       for(NodeIt n(_graph); n != INVALID; ++n) {
@@ -518,7 +518,7 @@
     /// This function runs Edmonds' algorithm with a heuristic of postponing
     /// 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() {
       for(NodeIt n(_graph); n != INVALID; ++n) {
diff -r 189760a7cdd0 -r c01a98ce01fd lemon/network_simplex.h
--- a/lemon/network_simplex.h	Thu May 07 02:05:12 2009 +0200
+++ b/lemon/network_simplex.h	Tue May 12 12:09:55 2009 +0100
@@ -19,7 +19,7 @@
 #ifndef LEMON_NETWORK_SIMPLEX_H
 #define LEMON_NETWORK_SIMPLEX_H
 
-/// \ingroup min_cost_flow
+/// \ingroup min_cost_flow_algs
 ///
 /// \file
 /// \brief Network Simplex algorithm for finding a minimum cost flow.
@@ -33,7 +33,7 @@
 
 namespace lemon {
 
-  /// \addtogroup min_cost_flow
+  /// \addtogroup min_cost_flow_algs
   /// @{
 
   /// \brief Implementation of the primal Network Simplex algorithm
@@ -102,50 +102,16 @@
     /// i.e. the direction of the inequalities in the supply/demand
     /// 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
     };
     
     /// \brief Constants for selecting the pivot rule.
@@ -215,6 +181,8 @@
     const GR &_graph;
     int _node_num;
     int _arc_num;
+    int _all_arc_num;
+    int _search_arc_num;
 
     // Parameters of the problem
     bool _have_lower;
@@ -277,7 +245,7 @@
       const IntVector  &_state;
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
       int _next_arc;
@@ -288,13 +256,14 @@
       FirstEligiblePivotRule(NetworkSimplex &ns) :
         _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)
       {}
 
       // Find next entering arc
       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) {
             _in_arc = e;
@@ -328,7 +297,7 @@
       const IntVector  &_state;
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
     public:
 
@@ -336,13 +305,13 @@
       BestEligiblePivotRule(NetworkSimplex &ns) :
         _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)
       {}
 
       // Find next entering arc
       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) {
             min = c;
@@ -367,7 +336,7 @@
       const IntVector  &_state;
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
       int _block_size;
@@ -379,14 +348,15 @@
       BlockSearchPivotRule(NetworkSimplex &ns) :
         _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 );
       }
 
@@ -395,7 +365,7 @@
         Cost c, min = 0;
         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) {
             min = c;
@@ -440,7 +410,7 @@
       const IntVector  &_state;
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
       IntVector _candidates;
@@ -454,7 +424,8 @@
       CandidateListPivotRule(NetworkSimplex &ns) :
         _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 LIST_LENGTH_FACTOR = 1.0;
@@ -463,7 +434,7 @@
         const int MIN_MINOR_LIMIT = 3;
 
         _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),
                                  MIN_MINOR_LIMIT );
@@ -500,7 +471,7 @@
         // Major iteration: build a new candidate list
         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) {
             _candidates[_curr_length++] = e;
@@ -546,7 +517,7 @@
       const IntVector  &_state;
       const CostVector &_pi;
       int &_in_arc;
-      int _arc_num;
+      int _search_arc_num;
 
       // Pivot rule data
       int _block_size, _head_length, _curr_length;
@@ -574,8 +545,8 @@
       AlteringListPivotRule(NetworkSimplex &ns) :
         _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
         const double BLOCK_SIZE_FACTOR = 1.5;
@@ -584,7 +555,7 @@
         const int MIN_HEAD_LENGTH = 3;
 
         _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),
                                  MIN_HEAD_LENGTH );
@@ -610,7 +581,7 @@
         int last_arc = 0;
         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]]);
           if (_cand_cost[e] < 0) {
@@ -678,17 +649,17 @@
       _node_num = countNodes(_graph);
       _arc_num = countArcs(_graph);
       int all_node_num = _node_num + 1;
-      int all_arc_num = _arc_num + _node_num;
+      int max_arc_num = _arc_num + 2 * _node_num;
 
-      _source.resize(all_arc_num);
-      _target.resize(all_arc_num);
+      _source.resize(max_arc_num);
+      _target.resize(max_arc_num);
 
-      _lower.resize(all_arc_num);
-      _upper.resize(all_arc_num);
-      _cap.resize(all_arc_num);
-      _cost.resize(all_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);
 
       _parent.resize(all_node_num);
@@ -698,7 +669,7 @@
       _rev_thread.resize(all_node_num);
       _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)
       int i = 0;
@@ -1069,7 +1040,7 @@
       // Initialize artifical cost
       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();
         for (int i = 0; i != _arc_num; ++i) {
@@ -1093,29 +1064,121 @@
       _succ_num[_root] = _node_num + 1;
       _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;
+      }
 
       return true;
     }
@@ -1374,20 +1437,8 @@
       }
       
       // 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;
       }
 
       // Transform the solution and the supply map to the original form
@@ -1401,6 +1452,30 @@
           }
         }
       }
+      
+      // 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;
     }
diff -r 189760a7cdd0 -r c01a98ce01fd scripts/unify-sources.sh
--- a/scripts/unify-sources.sh	Thu May 07 02:05:12 2009 +0200
+++ b/scripts/unify-sources.sh	Tue May 12 12:09:55 2009 +0100
@@ -6,6 +6,10 @@
 function hg_year() {
     if [ -n "$(hg st $1)" ]; then
         echo $YEAR
+    else
+        hg log -l 1 --template='{date|isodate}\n' $1 |
+        cut -d '-' -f 1
+    fi
 }
 
 # file enumaration modes
diff -r 189760a7cdd0 -r c01a98ce01fd test/CMakeLists.txt
--- a/test/CMakeLists.txt	Thu May 07 02:05:12 2009 +0200
+++ b/test/CMakeLists.txt	Tue May 12 12:09:55 2009 +0100
@@ -9,6 +9,7 @@
   adaptors_test
   bfs_test
   circulation_test
+  connectivity_test
   counter_test
   dfs_test
   digraph_test
diff -r 189760a7cdd0 -r c01a98ce01fd test/Makefile.am
--- a/test/Makefile.am	Thu May 07 02:05:12 2009 +0200
+++ b/test/Makefile.am	Tue May 12 12:09:55 2009 +0100
@@ -9,6 +9,7 @@
 	test/adaptors_test \
 	test/bfs_test \
 	test/circulation_test \
+	test/connectivity_test \
 	test/counter_test \
 	test/dfs_test \
 	test/digraph_test \
@@ -54,6 +55,7 @@
 test_bfs_test_SOURCES = test/bfs_test.cc
 test_circulation_test_SOURCES = test/circulation_test.cc
 test_counter_test_SOURCES = test/counter_test.cc
+test_connectivity_test_SOURCES = test/connectivity_test.cc
 test_dfs_test_SOURCES = test/dfs_test.cc
 test_digraph_test_SOURCES = test/digraph_test.cc
 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
diff -r 189760a7cdd0 -r c01a98ce01fd test/connectivity_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/connectivity_test.cc	Tue May 12 12:09:55 2009 +0100
@@ -0,0 +1,297 @@
+/* -*- 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.
+ *
+ */
+
+#include <lemon/connectivity.h>
+#include <lemon/list_graph.h>
+#include <lemon/adaptors.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+
+int main()
+{
+  typedef ListDigraph Digraph;
+  typedef Undirector<Digraph> Graph;
+  
+  {
+    Digraph d;
+    Digraph::NodeMap<int> order(d);
+    Graph g(d);
+    
+    check(stronglyConnected(d), "The empty digraph is strongly connected");
+    check(countStronglyConnectedComponents(d) == 0,
+          "The empty digraph has 0 strongly connected component");
+    check(connected(g), "The empty graph is connected");
+    check(countConnectedComponents(g) == 0,
+          "The empty graph has 0 connected component");
+
+    check(biNodeConnected(g), "The empty graph is bi-node-connected");
+    check(countBiNodeConnectedComponents(g) == 0,
+          "The empty graph has 0 bi-node-connected component");
+    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
+    check(countBiEdgeConnectedComponents(g) == 0,
+          "The empty graph has 0 bi-edge-connected component");
+          
+    check(dag(d), "The empty digraph is DAG.");
+    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
+    check(loopFree(d), "The empty digraph is loop-free.");
+    check(parallelFree(d), "The empty digraph is parallel-free.");
+    check(simpleGraph(d), "The empty digraph is simple.");
+
+    check(acyclic(g), "The empty graph is acyclic.");
+    check(tree(g), "The empty graph is tree.");
+    check(bipartite(g), "The empty graph is bipartite.");
+    check(loopFree(g), "The empty graph is loop-free.");
+    check(parallelFree(g), "The empty graph is parallel-free.");
+    check(simpleGraph(g), "The empty graph is simple.");
+  }
+
+  {
+    Digraph d;
+    Digraph::NodeMap<int> order(d);
+    Graph g(d);
+    Digraph::Node n = d.addNode();
+
+    check(stronglyConnected(d), "This digraph is strongly connected");
+    check(countStronglyConnectedComponents(d) == 1,
+          "This digraph has 1 strongly connected component");
+    check(connected(g), "This graph is connected");
+    check(countConnectedComponents(g) == 1,
+          "This graph has 1 connected component");
+
+    check(biNodeConnected(g), "This graph is bi-node-connected");
+    check(countBiNodeConnectedComponents(g) == 0,
+          "This graph has 0 bi-node-connected component");
+    check(biEdgeConnected(g), "This graph is bi-edge-connected");
+    check(countBiEdgeConnectedComponents(g) == 1,
+          "This graph has 1 bi-edge-connected component");
+          
+    check(dag(d), "This digraph is DAG.");
+    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
+    check(loopFree(d), "This digraph is loop-free.");
+    check(parallelFree(d), "This digraph is parallel-free.");
+    check(simpleGraph(d), "This digraph is simple.");
+
+    check(acyclic(g), "This graph is acyclic.");
+    check(tree(g), "This graph is tree.");
+    check(bipartite(g), "This graph is bipartite.");
+    check(loopFree(g), "This graph is loop-free.");
+    check(parallelFree(g), "This graph is parallel-free.");
+    check(simpleGraph(g), "This graph is simple.");
+  }
+
+  {
+    Digraph d;
+    Digraph::NodeMap<int> order(d);
+    Graph g(d);
+    
+    Digraph::Node n1 = d.addNode();
+    Digraph::Node n2 = d.addNode();
+    Digraph::Node n3 = d.addNode();
+    Digraph::Node n4 = d.addNode();
+    Digraph::Node n5 = d.addNode();
+    Digraph::Node n6 = d.addNode();
+    
+    d.addArc(n1, n3);
+    d.addArc(n3, n2);
+    d.addArc(n2, n1);
+    d.addArc(n4, n2);
+    d.addArc(n4, n3);
+    d.addArc(n5, n6);
+    d.addArc(n6, n5);
+
+    check(!stronglyConnected(d), "This digraph is not strongly connected");
+    check(countStronglyConnectedComponents(d) == 3,
+          "This digraph has 3 strongly connected components");
+    check(!connected(g), "This graph is not connected");
+    check(countConnectedComponents(g) == 2,
+          "This graph has 2 connected components");
+
+    check(!dag(d), "This digraph is not DAG.");
+    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
+    check(loopFree(d), "This digraph is loop-free.");
+    check(parallelFree(d), "This digraph is parallel-free.");
+    check(simpleGraph(d), "This digraph is simple.");
+
+    check(!acyclic(g), "This graph is not acyclic.");
+    check(!tree(g), "This graph is not tree.");
+    check(!bipartite(g), "This graph is not bipartite.");
+    check(loopFree(g), "This graph is loop-free.");
+    check(!parallelFree(g), "This graph is not parallel-free.");
+    check(!simpleGraph(g), "This graph is not simple.");
+    
+    d.addArc(n3, n3);
+    
+    check(!loopFree(d), "This digraph is not loop-free.");
+    check(!loopFree(g), "This graph is not loop-free.");
+    check(!simpleGraph(d), "This digraph is not simple.");
+    
+    d.addArc(n3, n2);
+    
+    check(!parallelFree(d), "This digraph is not parallel-free.");
+  }
+  
+  {
+    Digraph d;
+    Digraph::ArcMap<bool> cutarcs(d, false);
+    Graph g(d);
+    
+    Digraph::Node n1 = d.addNode();
+    Digraph::Node n2 = d.addNode();
+    Digraph::Node n3 = d.addNode();
+    Digraph::Node n4 = d.addNode();
+    Digraph::Node n5 = d.addNode();
+    Digraph::Node n6 = d.addNode();
+    Digraph::Node n7 = d.addNode();
+    Digraph::Node n8 = d.addNode();
+
+    d.addArc(n1, n2);
+    d.addArc(n5, n1);
+    d.addArc(n2, n8);
+    d.addArc(n8, n5);
+    d.addArc(n6, n4);
+    d.addArc(n4, n6);
+    d.addArc(n2, n5);
+    d.addArc(n1, n8);
+    d.addArc(n6, n7);
+    d.addArc(n7, n6);
+   
+    check(!stronglyConnected(d), "This digraph is not strongly connected");
+    check(countStronglyConnectedComponents(d) == 3,
+          "This digraph has 3 strongly connected components");
+    Digraph::NodeMap<int> scomp1(d);
+    check(stronglyConnectedComponents(d, scomp1) == 3,
+          "This digraph has 3 strongly connected components");
+    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
+          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
+    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
+          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
+    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
+          "Wrong stronglyConnectedComponents()");
+    Digraph::ArcMap<bool> scut1(d, false);
+    check(stronglyConnectedCutArcs(d, scut1) == 0,
+          "This digraph has 0 strongly connected cut arc.");
+    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
+    }
+
+    check(!connected(g), "This graph is not connected");
+    check(countConnectedComponents(g) == 3,
+          "This graph has 3 connected components");
+    Graph::NodeMap<int> comp(g);
+    check(connectedComponents(g, comp) == 3,
+          "This graph has 3 connected components");
+    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
+          comp[n3] != comp[n4], "Wrong connectedComponents()");
+    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
+          comp[n1] == comp[n8], "Wrong connectedComponents()");
+    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
+          "Wrong connectedComponents()");
+
+    cutarcs[d.addArc(n3, n1)] = true;
+    cutarcs[d.addArc(n3, n5)] = true;
+    cutarcs[d.addArc(n3, n8)] = true;
+    cutarcs[d.addArc(n8, n6)] = true;
+    cutarcs[d.addArc(n8, n7)] = true;
+
+    check(!stronglyConnected(d), "This digraph is not strongly connected");
+    check(countStronglyConnectedComponents(d) == 3,
+          "This digraph has 3 strongly connected components");
+    Digraph::NodeMap<int> scomp2(d);
+    check(stronglyConnectedComponents(d, scomp2) == 3,
+          "This digraph has 3 strongly connected components");
+    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
+    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
+          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
+    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
+          "Wrong stronglyConnectedComponents()");
+    Digraph::ArcMap<bool> scut2(d, false);
+    check(stronglyConnectedCutArcs(d, scut2) == 5,
+          "This digraph has 5 strongly connected cut arcs.");
+    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
+    }
+  }
+
+  {
+    // DAG example for topological sort from the book New Algorithms
+    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
+    Digraph d;
+    Digraph::NodeMap<int> order(d);
+    
+    Digraph::Node belt = d.addNode();
+    Digraph::Node trousers = d.addNode();
+    Digraph::Node necktie = d.addNode();
+    Digraph::Node coat = d.addNode();
+    Digraph::Node socks = d.addNode();
+    Digraph::Node shirt = d.addNode();
+    Digraph::Node shoe = d.addNode();
+    Digraph::Node watch = d.addNode();
+    Digraph::Node pants = d.addNode();
+
+    d.addArc(socks, shoe);
+    d.addArc(pants, shoe);
+    d.addArc(pants, trousers);
+    d.addArc(trousers, shoe);
+    d.addArc(trousers, belt);
+    d.addArc(belt, coat);
+    d.addArc(shirt, belt);
+    d.addArc(shirt, necktie);
+    d.addArc(necktie, coat);
+    
+    check(dag(d), "This digraph is DAG.");
+    topologicalSort(d, order);
+    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
+      check(order[d.source(a)] < order[d.target(a)],
+            "Wrong topologicalSort()");
+    }
+  }
+
+  {
+    ListGraph g;
+    ListGraph::NodeMap<bool> map(g);
+    
+    ListGraph::Node n1 = g.addNode();
+    ListGraph::Node n2 = g.addNode();
+    ListGraph::Node n3 = g.addNode();
+    ListGraph::Node n4 = g.addNode();
+    ListGraph::Node n5 = g.addNode();
+    ListGraph::Node n6 = g.addNode();
+    ListGraph::Node n7 = g.addNode();
+
+    g.addEdge(n1, n3);
+    g.addEdge(n1, n4);
+    g.addEdge(n2, n5);
+    g.addEdge(n3, n6);
+    g.addEdge(n4, n6);
+    g.addEdge(n4, n7);
+    g.addEdge(n5, n7);
+   
+    check(bipartite(g), "This graph is bipartite");
+    check(bipartitePartitions(g, map), "This graph is bipartite");
+    
+    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
+          "Wrong bipartitePartitions()");
+    check(map[n3] == map[n4] && map[n3] == map[n5],
+          "Wrong bipartitePartitions()");
+  }
+
+  return 0;
+}
diff -r 189760a7cdd0 -r c01a98ce01fd test/min_cost_flow_test.cc
--- a/test/min_cost_flow_test.cc	Thu May 07 02:05:12 2009 +0200
+++ b/test/min_cost_flow_test.cc	Tue May 12 12:09:55 2009 +0100
@@ -174,7 +174,7 @@
            typename CM, typename SM, typename FM, typename PM >
 bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
                      const CM& cost, const SM& supply, const FM& flow, 
-                     const PM& pi )
+                     const PM& pi, SupplyType type )
 {
   TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 
@@ -193,12 +193,50 @@
       sum += flow[e];
     for (InArcIt e(gr, n); e != INVALID; ++e)
       sum -= flow[e];
-    opt = (sum == supply[n]) || (pi[n] == 0);
+    if (type != LEQ) {
+      opt = (pi[n] <= 0) && (sum == supply[n] || pi[n] == 0);
+    } else {
+      opt = (pi[n] >= 0) && (sum == supply[n] || pi[n] == 0);
+    }
   }
   
   return opt;
 }
 
+// Check whether the dual cost is equal to the primal cost
+template < typename GR, typename LM, typename UM,
+           typename CM, typename SM, typename PM >
+bool checkDualCost( const GR& gr, const LM& lower, const UM& upper,
+                    const CM& cost, const SM& supply, const PM& pi,
+                    typename CM::Value total )
+{
+  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
+  typename CM::Value dual_cost = 0;
+  SM red_supply(gr);
+  for (NodeIt n(gr); n != INVALID; ++n) {
+    red_supply[n] = supply[n];
+  }
+  for (ArcIt a(gr); a != INVALID; ++a) {
+    if (lower[a] != 0) {
+      dual_cost += lower[a] * cost[a];
+      red_supply[gr.source(a)] -= lower[a];
+      red_supply[gr.target(a)] += lower[a];
+    }
+  }
+  
+  for (NodeIt n(gr); n != INVALID; ++n) {
+    dual_cost -= red_supply[n] * pi[n];
+  }
+  for (ArcIt a(gr); a != INVALID; ++a) {
+    typename CM::Value red_cost =
+      cost[a] + pi[gr.source(a)] - pi[gr.target(a)];
+    dual_cost -= (upper[a] - lower[a]) * std::max(-red_cost, 0);
+  }
+  
+  return dual_cost == total;
+}
+
 // Run a minimum cost flow algorithm and check the results
 template < typename MCF, typename GR,
            typename LM, typename UM,
@@ -220,8 +258,10 @@
     check(checkFlow(gr, lower, upper, supply, flow, type),
           "The flow is not feasible " + test_id);
     check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
-    check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
+    check(checkPotential(gr, lower, upper, cost, supply, flow, pi, type),
           "Wrong potentials " + test_id);
+    check(checkDualCost(gr, lower, upper, cost, supply, pi, total),
+          "Wrong dual cost " + test_id);
   }
 }
 
@@ -266,45 +306,56 @@
     .node("target", w)
     .run();
   
-  // Build a test digraph for testing negative costs
-  Digraph ngr;
-  Node n1 = ngr.addNode();
-  Node n2 = ngr.addNode();
-  Node n3 = ngr.addNode();
-  Node n4 = ngr.addNode();
-  Node n5 = ngr.addNode();
-  Node n6 = ngr.addNode();
-  Node n7 = ngr.addNode();
+  // Build test digraphs with negative costs
+  Digraph neg_gr;
+  Node n1 = neg_gr.addNode();
+  Node n2 = neg_gr.addNode();
+  Node n3 = neg_gr.addNode();
+  Node n4 = neg_gr.addNode();
+  Node n5 = neg_gr.addNode();
+  Node n6 = neg_gr.addNode();
+  Node n7 = neg_gr.addNode();
   
-  Arc a1 = ngr.addArc(n1, n2);
-  Arc a2 = ngr.addArc(n1, n3);
-  Arc a3 = ngr.addArc(n2, n4);
-  Arc a4 = ngr.addArc(n3, n4);
-  Arc a5 = ngr.addArc(n3, n2);
-  Arc a6 = ngr.addArc(n5, n3);
-  Arc a7 = ngr.addArc(n5, n6);
-  Arc a8 = ngr.addArc(n6, n7);
-  Arc a9 = ngr.addArc(n7, n5);
+  Arc a1 = neg_gr.addArc(n1, n2);
+  Arc a2 = neg_gr.addArc(n1, n3);
+  Arc a3 = neg_gr.addArc(n2, n4);
+  Arc a4 = neg_gr.addArc(n3, n4);
+  Arc a5 = neg_gr.addArc(n3, n2);
+  Arc a6 = neg_gr.addArc(n5, n3);
+  Arc a7 = neg_gr.addArc(n5, n6);
+  Arc a8 = neg_gr.addArc(n6, n7);
+  Arc a9 = neg_gr.addArc(n7, n5);
   
-  Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
-  ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
-  Digraph::NodeMap<int> ns(ngr, 0);
+  Digraph::ArcMap<int> neg_c(neg_gr), neg_l1(neg_gr, 0), neg_l2(neg_gr, 0);
+  ConstMap<Arc, int> neg_u1(std::numeric_limits<int>::max()), neg_u2(5000);
+  Digraph::NodeMap<int> neg_s(neg_gr, 0);
   
-  nl2[a7] =  1000;
-  nl2[a8] = -1000;
+  neg_l2[a7] =  1000;
+  neg_l2[a8] = -1000;
   
-  ns[n1] =  100;
-  ns[n4] = -100;
+  neg_s[n1] =  100;
+  neg_s[n4] = -100;
   
-  nc[a1] =  100;
-  nc[a2] =   30;
-  nc[a3] =   20;
-  nc[a4] =   80;
-  nc[a5] =   50;
-  nc[a6] =   10;
-  nc[a7] =   80;
-  nc[a8] =   30;
-  nc[a9] = -120;
+  neg_c[a1] =  100;
+  neg_c[a2] =   30;
+  neg_c[a3] =   20;
+  neg_c[a4] =   80;
+  neg_c[a5] =   50;
+  neg_c[a6] =   10;
+  neg_c[a7] =   80;
+  neg_c[a8] =   30;
+  neg_c[a9] = -120;
+
+  Digraph negs_gr;
+  Digraph::NodeMap<int> negs_s(negs_gr);
+  Digraph::ArcMap<int> negs_c(negs_gr);
+  ConstMap<Arc, int> negs_l(0), negs_u(1000);
+  n1 = negs_gr.addNode();
+  n2 = negs_gr.addNode();
+  negs_s[n1] = 100;
+  negs_s[n2] = -300;
+  negs_c[negs_gr.addArc(n1, n2)] = -1;
+
 
   // A. Test NetworkSimplex with the default pivot rule
   {
@@ -342,7 +393,7 @@
     mcf.supplyType(mcf.GEQ);
     checkMcf(mcf, mcf.lowerMap(l2).run(),
              gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
-    mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
+    mcf.supplyMap(s6);
     checkMcf(mcf, mcf.run(),
              gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
 
@@ -353,20 +404,26 @@
              gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
     checkMcf(mcf, mcf.lowerMap(l2).run(),
              gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
-    mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
+    mcf.supplyMap(s5);
     checkMcf(mcf, mcf.run(),
              gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
 
     // Check negative costs
-    NetworkSimplex<Digraph> nmcf(ngr);
-    nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
-    checkMcf(nmcf, nmcf.run(),
-      ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A16");
-    checkMcf(nmcf, nmcf.upperMap(nu2).run(),
-      ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true,  -40000, "#A17");
-    nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
-    checkMcf(nmcf, nmcf.run(),
-      ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A18");
+    NetworkSimplex<Digraph> neg_mcf(neg_gr);
+    neg_mcf.lowerMap(neg_l1).costMap(neg_c).supplyMap(neg_s);
+    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u1,
+      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A16");
+    neg_mcf.upperMap(neg_u2);
+    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l1, neg_u2,
+      neg_c, neg_s, neg_mcf.OPTIMAL, true,  -40000, "#A17");
+    neg_mcf.reset().lowerMap(neg_l2).costMap(neg_c).supplyMap(neg_s);
+    checkMcf(neg_mcf, neg_mcf.run(), neg_gr, neg_l2, neg_u1,
+      neg_c, neg_s, neg_mcf.UNBOUNDED, false,    0, "#A18");
+      
+    NetworkSimplex<Digraph> negs_mcf(negs_gr);
+    negs_mcf.costMap(negs_c).supplyMap(negs_s);
+    checkMcf(negs_mcf, negs_mcf.run(), negs_gr, negs_l, negs_u,
+      negs_c, negs_s, negs_mcf.OPTIMAL, true, -300, "#A19", GEQ);
   }
 
   // B. Test NetworkSimplex with each pivot rule
diff -r 189760a7cdd0 -r c01a98ce01fd tools/lgf-gen.cc
--- a/tools/lgf-gen.cc	Thu May 07 02:05:12 2009 +0200
+++ b/tools/lgf-gen.cc	Tue May 12 12:09:55 2009 +0100
@@ -18,7 +18,7 @@
 
 /// \ingroup tools
 /// \file
-/// \brief Special plane digraph generator.
+/// \brief Special plane graph generator.
 ///
 /// Graph generator application for various types of plane graphs.
 ///
@@ -26,7 +26,7 @@
 /// \code
 ///   lgf-gen --help
 /// \endcode
-/// for more info on the usage.
+/// for more information on the usage.
 
 #include <algorithm>
 #include <set>
@@ -686,20 +686,21 @@
     .intOption("g", "Girth parameter (default is 10)", 10)
     .refOption("cities", "Number of cities (default is 1)", num_of_cities)
     .refOption("area", "Full relative area of the cities (default is 1)", area)
-    .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d)
+    .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",
+               disc_d)
     .optionGroup("dist", "disc")
-    .refOption("square", "Nodes are evenly distributed on a unit square", square_d)
+    .refOption("square", "Nodes are evenly distributed on a unit square",
+               square_d)
     .optionGroup("dist", "square")
-    .refOption("gauss",
-            "Nodes are located according to a two-dim gauss distribution",
-            gauss_d)
+    .refOption("gauss", "Nodes are located according to a two-dim Gauss "
+               "distribution", gauss_d)
     .optionGroup("dist", "gauss")
-//     .mandatoryGroup("dist")
     .onlyOneGroup("dist")
-    .boolOption("eps", "Also generate .eps output (prefix.eps)")
-    .boolOption("nonodes", "Draw the edges only in the generated .eps")
-    .boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)")
-    .boolOption("2con", "Create a two connected planar digraph")
+    .boolOption("eps", "Also generate .eps output (<prefix>.eps)")
+    .boolOption("nonodes", "Draw only the edges in the generated .eps output")
+    .boolOption("dir", "Directed graph is generated (each edge is replaced by "
+                "two directed arcs)")
+    .boolOption("2con", "Create a two connected planar graph")
     .optionGroup("alg","2con")
     .boolOption("tree", "Create a min. cost spanning tree")
     .optionGroup("alg","tree")
@@ -707,7 +708,7 @@
     .optionGroup("alg","tsp")
     .boolOption("tsp2", "Create a TSP tour (tree based)")
     .optionGroup("alg","tsp2")
-    .boolOption("dela", "Delaunay triangulation digraph")
+    .boolOption("dela", "Delaunay triangulation graph")
     .optionGroup("alg","dela")
     .onlyOneGroup("alg")
     .boolOption("rand", "Use time seed for random number generator")