Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt	(revision 678)
+++ CMakeLists.txt	(revision 668)
@@ -18,4 +18,6 @@
 FIND_PACKAGE(COIN)
 
+ADD_DEFINITIONS(-DHAVE_CONFIG_H)
+
 IF(MSVC)
   SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
@@ -28,5 +30,5 @@
 
 INCLUDE(CheckTypeSize)
-CHECK_TYPE_SIZE("long long" LEMON_LONG_LONG)
+CHECK_TYPE_SIZE("long long" LONG_LONG)
 
 ENABLE_TESTING()
Index: Makefile.am
===================================================================
--- Makefile.am	(revision 676)
+++ Makefile.am	(revision 614)
@@ -12,10 +12,9 @@
 	m4/lx_check_glpk.m4 \
 	m4/lx_check_soplex.m4 \
-	m4/lx_check_coin.m4 \
+	m4/lx_check_clp.m4 \
+	m4/lx_check_cbc.m4 \
 	CMakeLists.txt \
 	cmake/FindGhostscript.cmake \
-	cmake/FindCPLEX.cmake \
 	cmake/FindGLPK.cmake \
-	cmake/FindCOIN.cmake \
 	cmake/version.cmake.in \
 	cmake/version.cmake \
Index: cmake/FindCOIN.cmake
===================================================================
--- cmake/FindCOIN.cmake	(revision 681)
+++ cmake/FindCOIN.cmake	(revision 668)
@@ -2,46 +2,26 @@
 
 FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h
-  HINTS ${COIN_ROOT_DIR}/include
-)
-FIND_LIBRARY(COIN_CBC_LIBRARY
-  NAMES Cbc libCbc
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
-  NAMES CbcSolver libCbcSolver
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_CGL_LIBRARY
-  NAMES Cgl libCgl
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_CLP_LIBRARY
-  NAMES Clp libClp
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
-  NAMES CoinUtils libCoinUtils
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_OSI_LIBRARY
-  NAMES Osi libOsi
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
-  NAMES OsiCbc libOsiCbc
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
-  NAMES OsiClp libOsiClp
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
-  NAMES OsiVol libOsiVol
-  HINTS ${COIN_ROOT_DIR}/lib
-)
-FIND_LIBRARY(COIN_VOL_LIBRARY
-  NAMES Vol libVol
-  HINTS ${COIN_ROOT_DIR}/lib
-)
+  PATHS ${COIN_ROOT_DIR}/include)
+
+FIND_LIBRARY(COIN_CBC_LIBRARY libCbc
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY libCbcSolver
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_CGL_LIBRARY libCgl
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_CLP_LIBRARY libClp
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY libCoinUtils
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_OSI_LIBRARY libOsi
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_OSI_CBC_LIBRARY libOsiCbc
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_OSI_CLP_LIBRARY libOsiClp
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_OSI_VOL_LIBRARY libOsiVol
+  PATHS ${COIN_ROOT_DIR}/lib)
+FIND_LIBRARY(COIN_VOL_LIBRARY libVol
+  PATHS ${COIN_ROOT_DIR}/lib)
 
 INCLUDE(FindPackageHandleStandardArgs)
@@ -82,7 +62,7 @@
 
 IF(COIN_FOUND)
-  SET(LEMON_HAVE_LP TRUE)
-  SET(LEMON_HAVE_MIP TRUE)
-  SET(LEMON_HAVE_CLP TRUE)
-  SET(LEMON_HAVE_CBC TRUE)
+  SET(HAVE_LP TRUE)
+  SET(HAVE_MIP TRUE)
+  SET(HAVE_CLP TRUE)
+  SET(HAVE_CBC TRUE)
 ENDIF(COIN_FOUND)
Index: cmake/FindCPLEX.cmake
===================================================================
--- cmake/FindCPLEX.cmake	(revision 683)
+++ cmake/FindCPLEX.cmake	(revision 667)
@@ -1,16 +1,9 @@
-SET(CPLEX_ROOT_DIR "" CACHE PATH "CPLEX root directory")
-
 FIND_PATH(CPLEX_INCLUDE_DIR
   ilcplex/cplex.h
-  PATHS "C:/ILOG/CPLEX91/include"
-  PATHS "/opt/ilog/cplex91/include"
-  HINTS ${CPLEX_ROOT_DIR}/include
-)
+  PATHS "C:/ILOG/CPLEX91/include")
+
 FIND_LIBRARY(CPLEX_LIBRARY
-  cplex91
-  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda"
-  PATHS "/opt/ilog/cplex91/bin"
-  HINTS ${CPLEX_ROOT_DIR}/bin
-)
+  NAMES cplex91
+  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda")
 
 INCLUDE(FindPackageHandleStandardArgs)
@@ -19,13 +12,9 @@
 FIND_PATH(CPLEX_BIN_DIR
   cplex91.dll
-  PATHS "C:/ILOG/CPLEX91/bin/x86_win32"
-)
+  PATHS "C:/ILOG/CPLEX91/bin/x86_win32")
 
 IF(CPLEX_FOUND)
   SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})
   SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})
-  IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
-    SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")
-  ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
 ENDIF(CPLEX_FOUND)
 
@@ -33,6 +22,6 @@
 
 IF(CPLEX_FOUND)
-  SET(LEMON_HAVE_LP TRUE)
-  SET(LEMON_HAVE_MIP TRUE)
-  SET(LEMON_HAVE_CPLEX TRUE)
+  SET(HAVE_LP TRUE)
+  SET(HAVE_MIP TRUE)
+  SET(HAVE_CPLEX TRUE)
 ENDIF(CPLEX_FOUND)
Index: cmake/FindGLPK.cmake
===================================================================
--- cmake/FindGLPK.cmake	(revision 685)
+++ cmake/FindGLPK.cmake	(revision 666)
@@ -1,4 +1,2 @@
-SET(GLPK_ROOT_DIR "" CACHE PATH "GLPK root directory")
-
 SET(GLPK_REGKEY "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GnuWin32\\Glpk;InstallPath]")
 GET_FILENAME_COMPONENT(GLPK_ROOT_PATH ${GLPK_REGKEY} ABSOLUTE)
@@ -6,44 +4,12 @@
 FIND_PATH(GLPK_INCLUDE_DIR
   glpk.h
-  PATHS ${GLPK_REGKEY}/include
-  HINTS ${GLPK_ROOT_DIR}/include
-)
+  PATHS ${GLPK_REGKEY}/include)
+
 FIND_LIBRARY(GLPK_LIBRARY
-  glpk
-  PATHS ${GLPK_REGKEY}/lib
-  HINTS ${GLPK_ROOT_DIR}/lib
-)
-
-IF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
-  FILE(READ ${GLPK_INCLUDE_DIR}/glpk.h GLPK_GLPK_H)
-
-  STRING(REGEX MATCH "define[ ]+GLP_MAJOR_VERSION[ ]+[0-9]+" GLPK_MAJOR_VERSION_LINE "${GLPK_GLPK_H}")
-  STRING(REGEX REPLACE "define[ ]+GLP_MAJOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MAJOR "${GLPK_MAJOR_VERSION_LINE}")
-
-  STRING(REGEX MATCH "define[ ]+GLP_MINOR_VERSION[ ]+[0-9]+" GLPK_MINOR_VERSION_LINE "${GLPK_GLPK_H}")
-  STRING(REGEX REPLACE "define[ ]+GLP_MINOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MINOR "${GLPK_MINOR_VERSION_LINE}")
-
-  SET(GLPK_VERSION_STRING "${GLPK_VERSION_MAJOR}.${GLPK_VERSION_MINOR}")
-
-  IF(GLPK_FIND_VERSION)
-    IF(GLPK_FIND_VERSION_COUNT GREATER 2)
-      MESSAGE(SEND_ERROR "unexpected version string")
-    ENDIF(GLPK_FIND_VERSION_COUNT GREATER 2)
-
-    MATH(EXPR GLPK_REQUESTED_VERSION "${GLPK_FIND_VERSION_MAJOR}*100 + ${GLPK_FIND_VERSION_MINOR}")
-    MATH(EXPR GLPK_FOUND_VERSION "${GLPK_VERSION_MAJOR}*100 + ${GLPK_VERSION_MINOR}")
-
-    IF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
-      SET(GLPK_PROPER_VERSION_FOUND FALSE)
-    ELSE(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
-      SET(GLPK_PROPER_VERSION_FOUND TRUE)
-    ENDIF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
-  ELSE(GLPK_FIND_VERSION)
-    SET(GLPK_PROPER_VERSION_FOUND TRUE)
-  ENDIF(GLPK_FIND_VERSION)
-ENDIF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
+  NAMES glpk
+  PATHS ${GLPK_REGKEY}/lib)
 
 INCLUDE(FindPackageHandleStandardArgs)
-FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_PROPER_VERSION_FOUND)
+FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR)
 
 IF(GLPK_FOUND)
@@ -56,6 +22,6 @@
 
 IF(GLPK_FOUND)
-  SET(LEMON_HAVE_LP TRUE)
-  SET(LEMON_HAVE_MIP TRUE)
-  SET(LEMON_HAVE_GLPK TRUE)
+  SET(HAVE_LP TRUE)
+  SET(HAVE_MIP TRUE)
+  SET(HAVE_GLPK TRUE)
 ENDIF(GLPK_FOUND)
Index: configure.ac
===================================================================
--- configure.ac	(revision 674)
+++ configure.ac	(revision 615)
@@ -26,5 +26,5 @@
 AC_CHECK_TYPE(long long, [long_long_found=yes], [long_long_found=no])
 if test x"$long_long_found" = x"yes"; then
-  AC_DEFINE([LEMON_HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
+  AC_DEFINE([HAVE_LONG_LONG], [1], [Define to 1 if you have long long.])
 fi
 
Index: doc/groups.dox
===================================================================
--- doc/groups.dox	(revision 658)
+++ doc/groups.dox	(revision 687)
@@ -353,15 +353,15 @@
 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, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
+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$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
-\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
-on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
+\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}^+_0\f$ solution
+A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
 of the following optimization problem.
 
@@ -405,5 +405,5 @@
 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}^+_0\f$ feasible solution of the problem
+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
@@ -414,13 +414,13 @@
    - 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$:
+ - 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 node potentials \f$\pi\f$, i.e.
+\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
+All algorithms provide dual solution (node potentials) as well,
 if an optimal flow is found.
 
Index: lemon/CMakeLists.txt
===================================================================
--- lemon/CMakeLists.txt	(revision 674)
+++ lemon/CMakeLists.txt	(revision 668)
@@ -19,5 +19,5 @@
 )
 
-IF(LEMON_HAVE_GLPK)
+IF(HAVE_GLPK)
   SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
   INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
@@ -27,20 +27,20 @@
     INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
   ENDIF(WIN32)
-ENDIF(LEMON_HAVE_GLPK)
+ENDIF(HAVE_GLPK)
 
-IF(LEMON_HAVE_CPLEX)
+IF(HAVE_CPLEX)
   SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
   INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
-ENDIF(LEMON_HAVE_CPLEX)
+ENDIF(HAVE_CPLEX)
 
-IF(LEMON_HAVE_CLP)
+IF(HAVE_CLP)
   SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
-ENDIF(LEMON_HAVE_CLP)
+ENDIF(HAVE_CLP)
 
-IF(LEMON_HAVE_CBC)
+IF(HAVE_CBC)
   SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
   INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
-ENDIF(LEMON_HAVE_CBC)
+ENDIF(HAVE_CBC)
 
 ADD_LIBRARY(lemon ${LEMON_SOURCES})
@@ -56,7 +56,2 @@
   COMPONENT headers
   FILES_MATCHING PATTERN "*.h")
-
-INSTALL(
-  FILES ${CMAKE_CURRENT_BINARY_DIR}/config.h
-  DESTINATION include/lemon
-  COMPONENT headers)
Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 686)
+++ lemon/Makefile.am	(revision 658)
@@ -16,6 +16,5 @@
 	lemon/bits/windows.cc
 
-nodist_lemon_HEADERS = lemon/config.h	
-	
+
 lemon_libemon_la_CXXFLAGS = \
 	$(AM_CXXFLAGS) \
@@ -59,5 +58,4 @@
 	lemon/bfs.h \
 	lemon/bin_heap.h \
-	lemon/cbc.h \
 	lemon/circulation.h \
 	lemon/clp.h \
Index: lemon/bits/default_map.h
===================================================================
--- lemon/bits/default_map.h	(revision 674)
+++ lemon/bits/default_map.h	(revision 664)
@@ -98,5 +98,5 @@
 
 
-#if defined LEMON_HAVE_LONG_LONG
+#if defined HAVE_LONG_LONG
 
   // long long
Index: lemon/config.h.cmake
===================================================================
--- lemon/config.h.cmake	(revision 674)
+++ lemon/config.h.cmake	(revision 668)
@@ -1,7 +1,7 @@
-#cmakedefine LEMON_HAVE_LONG_LONG 1
-#cmakedefine LEMON_HAVE_LP 1
-#cmakedefine LEMON_HAVE_MIP 1
-#cmakedefine LEMON_HAVE_GLPK 1
-#cmakedefine LEMON_HAVE_CPLEX 1
-#cmakedefine LEMON_HAVE_CLP 1
-#cmakedefine LEMON_HAVE_CBC 1
+#cmakedefine HAVE_LONG_LONG 1
+#cmakedefine HAVE_LP 1
+#cmakedefine HAVE_MIP 1
+#cmakedefine HAVE_GLPK 1
+#cmakedefine HAVE_CPLEX 1
+#cmakedefine HAVE_CLP 1
+#cmakedefine HAVE_CBC 1
Index: lemon/config.h.in
===================================================================
--- lemon/config.h.in	(revision 674)
+++ lemon/config.h.in	(revision 614)
@@ -1,23 +1,23 @@
 /* Define to 1 if you have long long */
-#undef LEMON_HAVE_LONG_LONG
+#undef HAVE_LONG_LONG
 
 /* Define to 1 if you have any LP solver. */
-#undef LEMON_HAVE_LP
+#undef HAVE_LP
 
 /* Define to 1 if you have any MIP solver. */
-#undef LEMON_HAVE_MIP
+#undef HAVE_MIP
 
 /* Define to 1 if you have CPLEX. */
-#undef LEMON_HAVE_CPLEX
+#undef HAVE_CPLEX
 
 /* Define to 1 if you have GLPK. */
-#undef LEMON_HAVE_GLPK
+#undef HAVE_GLPK
 
 /* Define to 1 if you have SOPLEX */
-#undef LEMON_HAVE_SOPLEX
+#undef HAVE_SOPLEX
 
 /* Define to 1 if you have CLP */
-#undef LEMON_HAVE_CLP
+#undef HAVE_CLP
 
 /* Define to 1 if you have CBC */
-#undef LEMON_HAVE_CBC
+#undef HAVE_CBC
Index: lemon/core.h
===================================================================
--- lemon/core.h	(revision 686)
+++ lemon/core.h	(revision 664)
@@ -23,5 +23,5 @@
 #include <algorithm>
 
-#include <lemon/config.h>
+#include <lemon/core.h>
 #include <lemon/bits/enable_if.h>
 #include <lemon/bits/traits.h>
Index: lemon/lp.h
===================================================================
--- lemon/lp.h	(revision 674)
+++ lemon/lp.h	(revision 485)
@@ -23,11 +23,11 @@
 
 
-#ifdef LEMON_HAVE_GLPK
+#ifdef HAVE_GLPK
 #include <lemon/glpk.h>
-#elif LEMON_HAVE_CPLEX
+#elif HAVE_CPLEX
 #include <lemon/cplex.h>
-#elif LEMON_HAVE_SOPLEX
+#elif HAVE_SOPLEX
 #include <lemon/soplex.h>
-#elif LEMON_HAVE_CLP
+#elif HAVE_CLP
 #include <lemon/clp.h>
 #endif
@@ -70,18 +70,18 @@
   typedef GlpkMip Mip;
 #else
-#ifdef LEMON_HAVE_GLPK
+#ifdef HAVE_GLPK
 # define LEMON_DEFAULT_LP GLPK
   typedef GlpkLp Lp;
 # define LEMON_DEFAULT_MIP GLPK
   typedef GlpkMip Mip;
-#elif LEMON_HAVE_CPLEX
+#elif HAVE_CPLEX
 # define LEMON_DEFAULT_LP CPLEX
   typedef CplexLp Lp;
 # define LEMON_DEFAULT_MIP CPLEX
   typedef CplexMip Mip;
-#elif LEMON_HAVE_SOPLEX
+#elif HAVE_SOPLEX
 # define DEFAULT_LP SOPLEX
   typedef SoplexLp Lp;
-#elif LEMON_HAVE_CLP
+#elif HAVE_CLP
 # define DEFAULT_LP CLP
   typedef ClpLp Lp;  
Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 665)
+++ lemon/network_simplex.h	(revision 687)
@@ -31,7 +31,4 @@
 #include <lemon/core.h>
 #include <lemon/math.h>
-#include <lemon/maps.h>
-#include <lemon/circulation.h>
-#include <lemon/adaptors.h>
 
 namespace lemon {
@@ -51,6 +48,11 @@
   /// In general this class is the fastest implementation available
   /// in LEMON for the minimum cost flow problem.
-  /// Moreover it supports both direction of the supply/demand inequality
-  /// constraints. For more information see \ref ProblemType.
+  /// Moreover it supports both directions of the supply/demand inequality
+  /// constraints. For more information see \ref SupplyType.
+  ///
+  /// Most of the parameters of the problem (except for the digraph)
+  /// can be given using separate functions, and the algorithm can be
+  /// executed using the \ref run() function. If some parameters are not
+  /// specified, then default values will be used.
   ///
   /// \tparam GR The digraph type the algorithm runs on.
@@ -89,65 +91,39 @@
   public:
 
-    /// \brief Enum type for selecting the pivot rule.
-    ///
-    /// Enum type for selecting the pivot rule for the \ref run()
-    /// function.
-    ///
-    /// \ref NetworkSimplex provides five different pivot rule
-    /// implementations that significantly affect the running time
-    /// of the algorithm.
-    /// By default \ref BLOCK_SEARCH "Block Search" is used, which
-    /// proved to be the most efficient and the most robust on various
-    /// test inputs according to our benchmark tests.
-    /// However another pivot rule can be selected using the \ref run()
-    /// function with the proper parameter.
-    enum PivotRule {
-
-      /// The First Eligible pivot rule.
-      /// The next eligible arc is selected in a wraparound fashion
-      /// in every iteration.
-      FIRST_ELIGIBLE,
-
-      /// The Best Eligible pivot rule.
-      /// The best eligible arc is selected in every iteration.
-      BEST_ELIGIBLE,
-
-      /// The Block Search pivot rule.
-      /// A specified number of arcs are examined in every iteration
-      /// in a wraparound fashion and the best eligible arc is selected
-      /// from this block.
-      BLOCK_SEARCH,
-
-      /// The Candidate List pivot rule.
-      /// In a major iteration a candidate list is built from eligible arcs
-      /// in a wraparound fashion and in the following minor iterations
-      /// the best eligible arc is selected from this list.
-      CANDIDATE_LIST,
-
-      /// The Altering Candidate List pivot rule.
-      /// It is a modified version of the Candidate List method.
-      /// It keeps only the several best eligible arcs from the former
-      /// candidate list and extends this list in every iteration.
-      ALTERING_LIST
+    /// \brief Problem type constants for the \c run() function.
+    ///
+    /// Enum type containing the problem type constants that can be
+    /// returned by the \ref run() function of the algorithm.
+    enum ProblemType {
+      /// The problem has no feasible solution (flow).
+      INFEASIBLE,
+      /// The problem has optimal solution (i.e. it is feasible and
+      /// bounded), and the algorithm has found optimal flow and node
+      /// potentials (primal and dual solutions).
+      OPTIMAL,
+      /// The objective function of the problem is unbounded, i.e.
+      /// there is a directed cycle having negative total cost and
+      /// infinite upper bound.
+      UNBOUNDED
     };
     
-    /// \brief Enum type for selecting the problem type.
-    ///
-    /// Enum type for selecting the problem type, i.e. the direction of
-    /// the inequalities in the supply/demand constraints of the
-    /// \ref min_cost_flow "minimum cost flow problem".
-    ///
-    /// The default problem type is \c GEQ, since this form is supported
+    /// \brief Constants for selecting the type of the supply constraints.
+    ///
+    /// Enum type containing constants for selecting the supply type,
+    /// 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 problemType()
+    /// 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 problem type.
-    enum ProblemType {
-
-      /// This option means that there are "<em>greater or equal</em>"
-      /// constraints in the defintion, i.e. the exact formulation of the
-      /// problem is the following.
+    /// Note that 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]
@@ -165,7 +141,7 @@
       CARRY_SUPPLIES = GEQ,
 
-      /// This option means that there are "<em>less or equal</em>"
-      /// constraints in the defintion, i.e. the exact formulation of the
-      /// problem is the following.
+      /// 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]
@@ -183,5 +159,48 @@
       SATISFY_DEMANDS = LEQ
     };
-
+    
+    /// \brief Constants for selecting the pivot rule.
+    ///
+    /// Enum type containing constants for selecting the pivot rule for
+    /// the \ref run() function.
+    ///
+    /// \ref NetworkSimplex provides five different pivot rule
+    /// implementations that significantly affect the running time
+    /// of the algorithm.
+    /// By default \ref BLOCK_SEARCH "Block Search" is used, which
+    /// proved to be the most efficient and the most robust on various
+    /// test inputs according to our benchmark tests.
+    /// However another pivot rule can be selected using the \ref run()
+    /// function with the proper parameter.
+    enum PivotRule {
+
+      /// The First Eligible pivot rule.
+      /// The next eligible arc is selected in a wraparound fashion
+      /// in every iteration.
+      FIRST_ELIGIBLE,
+
+      /// The Best Eligible pivot rule.
+      /// The best eligible arc is selected in every iteration.
+      BEST_ELIGIBLE,
+
+      /// The Block Search pivot rule.
+      /// A specified number of arcs are examined in every iteration
+      /// in a wraparound fashion and the best eligible arc is selected
+      /// from this block.
+      BLOCK_SEARCH,
+
+      /// The Candidate List pivot rule.
+      /// In a major iteration a candidate list is built from eligible arcs
+      /// in a wraparound fashion and in the following minor iterations
+      /// the best eligible arc is selected from this list.
+      CANDIDATE_LIST,
+
+      /// The Altering Candidate List pivot rule.
+      /// It is a modified version of the Candidate List method.
+      /// It keeps only the several best eligible arcs from the former
+      /// candidate list and extends this list in every iteration.
+      ALTERING_LIST
+    };
+    
   private:
 
@@ -221,5 +240,7 @@
     Node _psource, _ptarget;
     Flow _pstflow;
-    ProblemType _ptype;
+    SupplyType _stype;
+    
+    Flow _sum_supply;
 
     // Result maps
@@ -259,4 +280,13 @@
     int stem, par_stem, new_stem;
     Flow delta;
+
+  public:
+  
+    /// \brief Constant for infinite upper bounds (capacities).
+    ///
+    /// Constant for infinite upper bounds (capacities).
+    /// It is \c std::numeric_limits<Flow>::infinity() if available,
+    /// \c std::numeric_limits<Flow>::max() otherwise.
+    const Flow INF;
 
   private:
@@ -662,15 +692,17 @@
       _graph(graph),
       _plower(NULL), _pupper(NULL), _pcost(NULL),
-      _psupply(NULL), _pstsup(false), _ptype(GEQ),
+      _psupply(NULL), _pstsup(false), _stype(GEQ),
       _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(graph)
+      _node_id(graph),
+      INF(std::numeric_limits<Flow>::has_infinity ?
+          std::numeric_limits<Flow>::infinity() :
+          std::numeric_limits<Flow>::max())
     {
-      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
-                   std::numeric_limits<Flow>::is_signed,
-        "The flow type of NetworkSimplex must be signed integer");
-      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
-                   std::numeric_limits<Cost>::is_signed,
-        "The cost type of NetworkSimplex must be signed integer");
+      // Check the value types
+      LEMON_ASSERT(std::numeric_limits<Flow>::is_signed,
+        "The flow type of NetworkSimplex must be signed");
+      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
+        "The cost type of NetworkSimplex must be signed");
     }
 
@@ -690,7 +722,6 @@
     ///
     /// This function sets the lower bounds on the arcs.
-    /// If neither this function nor \ref boundMaps() is used before
-    /// calling \ref run(), the lower bounds will be set to zero
-    /// on all arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
     ///
     /// \param map An arc map storing the lower bounds.
@@ -699,6 +730,6 @@
     ///
     /// \return <tt>(*this)</tt>
-    template <typename LOWER>
-    NetworkSimplex& lowerMap(const LOWER& map) {
+    template <typename LowerMap>
+    NetworkSimplex& lowerMap(const LowerMap& map) {
       delete _plower;
       _plower = new FlowArcMap(_graph);
@@ -712,8 +743,7 @@
     ///
     /// This function sets the upper bounds (capacities) on the arcs.
-    /// If none of the functions \ref upperMap(), \ref capacityMap()
-    /// and \ref boundMaps() is used before calling \ref run(),
-    /// the upper bounds (capacities) will be set to
-    /// \c std::numeric_limits<Flow>::max() on all arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above on each arc).
     ///
     /// \param map An arc map storing the upper bounds.
@@ -722,6 +752,6 @@
     ///
     /// \return <tt>(*this)</tt>
-    template<typename UPPER>
-    NetworkSimplex& upperMap(const UPPER& map) {
+    template<typename UpperMap>
+    NetworkSimplex& upperMap(const UpperMap& map) {
       delete _pupper;
       _pupper = new FlowArcMap(_graph);
@@ -732,41 +762,4 @@
     }
 
-    /// \brief Set the upper bounds (capacities) on the arcs.
-    ///
-    /// This function sets the upper bounds (capacities) on the arcs.
-    /// It is just an alias for \ref upperMap().
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename CAP>
-    NetworkSimplex& capacityMap(const CAP& map) {
-      return upperMap(map);
-    }
-
-    /// \brief Set the lower and upper bounds on the arcs.
-    ///
-    /// This function sets the lower and upper bounds on the arcs.
-    /// If neither this function nor \ref lowerMap() is used before
-    /// calling \ref run(), the lower bounds will be set to zero
-    /// on all arcs.
-    /// If none of the functions \ref upperMap(), \ref capacityMap()
-    /// and \ref boundMaps() is used before calling \ref run(),
-    /// the upper bounds (capacities) will be set to
-    /// \c std::numeric_limits<Flow>::max() on all arcs.
-    ///
-    /// \param lower An arc map storing the lower bounds.
-    /// \param upper An arc map storing the upper bounds.
-    ///
-    /// The \c Value type of the maps must be convertible to the
-    /// \c Flow type of the algorithm.
-    ///
-    /// \note This function is just a shortcut of calling \ref lowerMap()
-    /// and \ref upperMap() separately.
-    ///
-    /// \return <tt>(*this)</tt>
-    template <typename LOWER, typename UPPER>
-    NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) {
-      return lowerMap(lower).upperMap(upper);
-    }
-
     /// \brief Set the costs of the arcs.
     ///
@@ -780,6 +773,6 @@
     ///
     /// \return <tt>(*this)</tt>
-    template<typename COST>
-    NetworkSimplex& costMap(const COST& map) {
+    template<typename CostMap>
+    NetworkSimplex& costMap(const CostMap& map) {
       delete _pcost;
       _pcost = new CostArcMap(_graph);
@@ -802,6 +795,6 @@
     ///
     /// \return <tt>(*this)</tt>
-    template<typename SUP>
-    NetworkSimplex& supplyMap(const SUP& map) {
+    template<typename SupplyMap>
+    NetworkSimplex& supplyMap(const SupplyMap& map) {
       delete _psupply;
       _pstsup = false;
@@ -820,4 +813,8 @@
     /// calling \ref run(), the supply of each node will be set to zero.
     /// (It makes sense only if non-zero lower bounds are given.)
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
     ///
     /// \param s The source node.
@@ -837,15 +834,15 @@
     }
     
-    /// \brief Set the problem type.
-    ///
-    /// This function sets the problem type for the algorithm.
-    /// If it is not used before calling \ref run(), the \ref GEQ problem
+    /// \brief Set the type of the supply constraints.
+    ///
+    /// This function sets the type of the supply/demand constraints.
+    /// If it is not used before calling \ref run(), the \ref GEQ supply
     /// type will be used.
     ///
-    /// For more information see \ref ProblemType.
+    /// For more information see \ref SupplyType.
     ///
     /// \return <tt>(*this)</tt>
-    NetworkSimplex& problemType(ProblemType problem_type) {
-      _ptype = problem_type;
+    NetworkSimplex& supplyType(SupplyType supply_type) {
+      _stype = supply_type;
       return *this;
     }
@@ -897,11 +894,10 @@
     /// This function runs the algorithm.
     /// The paramters can be specified using functions \ref lowerMap(),
-    /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
-    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), 
-    /// \ref problemType(), \ref flowMap() and \ref potentialMap().
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 
+    /// \ref supplyType(), \ref flowMap() and \ref potentialMap().
     /// For example,
     /// \code
     ///   NetworkSimplex<ListDigraph> ns(graph);
-    ///   ns.boundMaps(lower, upper).costMap(cost)
+    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
     ///     .supplyMap(sup).run();
     /// \endcode
@@ -915,7 +911,16 @@
     /// algorithm. For more information see \ref PivotRule.
     ///
-    /// \return \c true if a feasible flow can be found.
-    bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
-      return init() && start(pivot_rule);
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the objective function of the problem is
+    /// unbounded, i.e. there is a directed cycle having negative total
+    /// cost and infinite upper bound.
+    ///
+    /// \see ProblemType, PivotRule
+    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
+      if (!init()) return INFEASIBLE;
+      return start(pivot_rule);
     }
 
@@ -924,6 +929,5 @@
     /// This function resets all the paramaters that have been given
     /// before using functions \ref lowerMap(), \ref upperMap(),
-    /// \ref capacityMap(), \ref boundMaps(), \ref costMap(),
-    /// \ref supplyMap(), \ref stSupply(), \ref problemType(), 
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(),
     /// \ref flowMap() and \ref potentialMap().
     ///
@@ -937,5 +941,5 @@
     ///
     ///   // First run
-    ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
+    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
     ///     .supplyMap(sup).run();
     ///
@@ -948,5 +952,5 @@
     ///   // (the lower bounds will be set to zero on all arcs)
     ///   ns.reset();
-    ///   ns.capacityMap(cap).costMap(cost)
+    ///   ns.upperMap(capacity).costMap(cost)
     ///     .supplyMap(sup).run();
     /// \endcode
@@ -963,5 +967,5 @@
       _psupply = NULL;
       _pstsup = false;
-      _ptype = GEQ;
+      _stype = GEQ;
       if (_local_flow) delete _flow_map;
       if (_local_potential) delete _potential_map;
@@ -986,5 +990,5 @@
     ///
     /// This function returns the total cost of the found flow.
-    /// The complexity of the function is O(e).
+    /// Its complexity is O(e).
     ///
     /// \note The return type of the function can be specified as a
@@ -998,7 +1002,7 @@
     ///
     /// \pre \ref run() must be called before using this function.
-    template <typename Num>
-    Num totalCost() const {
-      Num c = 0;
+    template <typename Value>
+    Value totalCost() const {
+      Value c = 0;
       if (_pcost) {
         for (ArcIt e(_graph); e != INVALID; ++e)
@@ -1051,5 +1055,5 @@
     /// This function returns a const reference to a node map storing
     /// the found potentials, which form the dual solution of the
-    /// \ref min_cost_flow "minimum cost flow" problem.
+    /// \ref min_cost_flow "minimum cost flow problem".
     ///
     /// \pre \ref run() must be called before using this function.
@@ -1102,5 +1106,5 @@
       // Initialize node related data
       bool valid_supply = true;
-      Flow sum_supply = 0;
+      _sum_supply = 0;
       if (!_pstsup && !_psupply) {
         _pstsup = true;
@@ -1113,8 +1117,8 @@
           _node_id[n] = i;
           _supply[i] = (*_psupply)[n];
-          sum_supply += _supply[i];
-        }
-        valid_supply = (_ptype == GEQ && sum_supply <= 0) ||
-                       (_ptype == LEQ && sum_supply >= 0);
+          _sum_supply += _supply[i];
+        }
+        valid_supply = (_stype == GEQ && _sum_supply <= 0) ||
+                       (_stype == LEQ && _sum_supply >= 0);
       } else {
         int i = 0;
@@ -1128,89 +1132,15 @@
       if (!valid_supply) return false;
 
-      // Infinite capacity value
-      Flow inf_cap =
-        std::numeric_limits<Flow>::has_infinity ?
-        std::numeric_limits<Flow>::infinity() :
-        std::numeric_limits<Flow>::max();
-
       // Initialize artifical cost
-      Cost art_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() / 4 + 1;
       } else {
-        art_cost = std::numeric_limits<Cost>::min();
+        ART_COST = std::numeric_limits<Cost>::min();
         for (int i = 0; i != _arc_num; ++i) {
-          if (_cost[i] > art_cost) art_cost = _cost[i];
-        }
-        art_cost = (art_cost + 1) * _node_num;
-      }
-
-      // Run Circulation to check if a feasible solution exists
-      typedef ConstMap<Arc, Flow> ConstArcMap;
-      ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
-      FlowNodeMap *csup = NULL;
-      bool local_csup = false;
-      if (_psupply) {
-        csup = _psupply;
-      } else {
-        csup = new FlowNodeMap(_graph, 0);
-        (*csup)[_psource] =  _pstflow;
-        (*csup)[_ptarget] = -_pstflow;
-        local_csup = true;
-      }
-      bool circ_result = false;
-      if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) {
-        // GEQ problem type
-        if (_plower) {
-          if (_pupper) {
-            Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap>
-              circ(_graph, *_plower, *_pupper, *csup);
-            circ_result = circ.run();
-          } else {
-            Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
-              circ(_graph, *_plower, inf_arc_map, *csup);
-            circ_result = circ.run();
-          }
-        } else {
-          if (_pupper) {
-            Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
-              circ(_graph, zero_arc_map, *_pupper, *csup);
-            circ_result = circ.run();
-          } else {
-            Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
-              circ(_graph, zero_arc_map, inf_arc_map, *csup);
-            circ_result = circ.run();
-          }
-        }
-      } else {
-        // LEQ problem type
-        typedef ReverseDigraph<const GR> RevGraph;
-        typedef NegMap<FlowNodeMap> NegNodeMap;
-        RevGraph rgraph(_graph);
-        NegNodeMap neg_csup(*csup);
-        if (_plower) {
-          if (_pupper) {
-            Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap>
-              circ(rgraph, *_plower, *_pupper, neg_csup);
-            circ_result = circ.run();
-          } else {
-            Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
-              circ(rgraph, *_plower, inf_arc_map, neg_csup);
-            circ_result = circ.run();
-          }
-        } else {
-          if (_pupper) {
-            Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
-              circ(rgraph, zero_arc_map, *_pupper, neg_csup);
-            circ_result = circ.run();
-          } else {
-            Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
-              circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
-            circ_result = circ.run();
-          }
-        }
-      }
-      if (local_csup) delete csup;
-      if (!circ_result) return false;
+          if (_cost[i] > ART_COST) ART_COST = _cost[i];
+        }
+        ART_COST = (ART_COST + 1) * _node_num;
+      }
 
       // Set data for the artificial root node
@@ -1222,9 +1152,9 @@
       _succ_num[_root] = all_node_num;
       _last_succ[_root] = _root - 1;
-      _supply[_root] = -sum_supply;
-      if (sum_supply < 0) {
-        _pi[_root] = -art_cost;
+      _supply[_root] = -_sum_supply;
+      if (_sum_supply < 0) {
+        _pi[_root] = -ART_COST;
       } else {
-        _pi[_root] = art_cost;
+        _pi[_root] = ART_COST;
       }
 
@@ -1261,5 +1191,5 @@
         } else {
           for (int i = 0; i != _arc_num; ++i)
-            _cap[i] = inf_cap;
+            _cap[i] = INF;
         }
         if (_pcost) {
@@ -1276,6 +1206,15 @@
         for (int i = 0; i != _arc_num; ++i) {
           Flow c = (*_plower)[_arc_ref[i]];
-          if (c != 0) {
-            _cap[i] -= c;
+          if (c > 0) {
+            if (_cap[i] < INF) _cap[i] -= c;
+            _supply[_source[i]] -= c;
+            _supply[_target[i]] += c;
+          }
+          else if (c < 0) {
+            if (_cap[i] < INF + c) {
+              _cap[i] -= c;
+            } else {
+              _cap[i] = INF;
+            }
             _supply[_source[i]] -= c;
             _supply[_target[i]] += c;
@@ -1292,15 +1231,15 @@
         _parent[u] = _root;
         _pred[u] = e;
-        _cost[e] = art_cost;
-        _cap[e] = inf_cap;
+        _cost[e] = ART_COST;
+        _cap[e] = INF;
         _state[e] = STATE_TREE;
-        if (_supply[u] > 0 || (_supply[u] == 0 && sum_supply <= 0)) {
+        if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
           _flow[e] = _supply[u];
           _forward[u] = true;
-          _pi[u] = -art_cost + _pi[_root];
+          _pi[u] = -ART_COST + _pi[_root];
         } else {
           _flow[e] = -_supply[u];
           _forward[u] = false;
-          _pi[u] = art_cost + _pi[_root];
+          _pi[u] = ART_COST + _pi[_root];
         }
       }
@@ -1343,5 +1282,6 @@
       for (int u = first; u != join; u = _parent[u]) {
         e = _pred[u];
-        d = _forward[u] ? _flow[e] : _cap[e] - _flow[e];
+        d = _forward[u] ?
+          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
         if (d < delta) {
           delta = d;
@@ -1353,5 +1293,6 @@
       for (int u = second; u != join; u = _parent[u]) {
         e = _pred[u];
-        d = _forward[u] ? _cap[e] - _flow[e] : _flow[e];
+        d = _forward[u] ? 
+          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
         if (d <= delta) {
           delta = d;
@@ -1527,5 +1468,5 @@
 
     // Execute the algorithm
-    bool start(PivotRule pivot_rule) {
+    ProblemType start(PivotRule pivot_rule) {
       // Select the pivot rule implementation
       switch (pivot_rule) {
@@ -1541,9 +1482,9 @@
           return start<AlteringListPivotRule>();
       }
-      return false;
+      return INFEASIBLE; // avoid warning
     }
 
     template <typename PivotRuleImpl>
-    bool start() {
+    ProblemType start() {
       PivotRuleImpl pivot(*this);
 
@@ -1552,8 +1493,26 @@
         findJoinNode();
         bool change = findLeavingArc();
+        if (delta >= INF) return UNBOUNDED;
         changeFlow(change);
         if (change) {
           updateTreeStructure();
           updatePotential();
+        }
+      }
+      
+      // 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;
         }
       }
@@ -1575,5 +1534,5 @@
       }
 
-      return true;
+      return OPTIMAL;
     }
 
Index: m4/lx_check_coin.m4
===================================================================
--- m4/lx_check_coin.m4	(revision 674)
+++ m4/lx_check_coin.m4	(revision 615)
@@ -56,7 +56,7 @@
 
     if test x"$lx_clp_found" = x"yes"; then
-      AC_DEFINE([LEMON_HAVE_CLP], [1], [Define to 1 if you have CLP.])
+      AC_DEFINE([HAVE_CLP], [1], [Define to 1 if you have CLP.])
       lx_lp_found=yes
-      AC_DEFINE([LEMON_HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+      AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
       AC_MSG_RESULT([yes])
     else
@@ -116,9 +116,9 @@
 
       if test x"$lx_cbc_found" = x"yes"; then
-        AC_DEFINE([LEMON_HAVE_CBC], [1], [Define to 1 if you have CBC.])
+        AC_DEFINE([HAVE_CBC], [1], [Define to 1 if you have CBC.])
         lx_lp_found=yes
-        AC_DEFINE([LEMON_HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+        AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
         lx_mip_found=yes
-        AC_DEFINE([LEMON_HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
+        AC_DEFINE([HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
         AC_MSG_RESULT([yes])
       else
Index: m4/lx_check_cplex.m4
===================================================================
--- m4/lx_check_cplex.m4	(revision 674)
+++ m4/lx_check_cplex.m4	(revision 480)
@@ -62,9 +62,9 @@
 
     if test x"$lx_cplex_found" = x"yes"; then
-      AC_DEFINE([LEMON_HAVE_CPLEX], [1], [Define to 1 if you have CPLEX.])
+      AC_DEFINE([HAVE_CPLEX], [1], [Define to 1 if you have CPLEX.])
       lx_lp_found=yes
-      AC_DEFINE([LEMON_HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+      AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
       lx_mip_found=yes
-      AC_DEFINE([LEMON_HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
+      AC_DEFINE([HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
       AC_MSG_RESULT([yes])
     else
Index: m4/lx_check_glpk.m4
===================================================================
--- m4/lx_check_glpk.m4	(revision 674)
+++ m4/lx_check_glpk.m4	(revision 482)
@@ -65,9 +65,9 @@
 
     if test x"$lx_glpk_found" = x"yes"; then
-      AC_DEFINE([LEMON_HAVE_GLPK], [1], [Define to 1 if you have GLPK.])
+      AC_DEFINE([HAVE_GLPK], [1], [Define to 1 if you have GLPK.])
       lx_lp_found=yes
-      AC_DEFINE([LEMON_HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+      AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
       lx_mip_found=yes
-      AC_DEFINE([LEMON_HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
+      AC_DEFINE([HAVE_MIP], [1], [Define to 1 if you have any MIP solver.])
       AC_MSG_RESULT([yes])
     else
Index: m4/lx_check_soplex.m4
===================================================================
--- m4/lx_check_soplex.m4	(revision 674)
+++ m4/lx_check_soplex.m4	(revision 586)
@@ -56,7 +56,7 @@
 
     if test x"$lx_soplex_found" = x"yes"; then
-      AC_DEFINE([LEMON_HAVE_SOPLEX], [1], [Define to 1 if you have SOPLEX.])
+      AC_DEFINE([HAVE_SOPLEX], [1], [Define to 1 if you have SOPLEX.])
       lx_lp_found=yes
-      AC_DEFINE([LEMON_HAVE_LP], [1], [Define to 1 if you have any LP solver.])
+      AC_DEFINE([HAVE_LP], [1], [Define to 1 if you have any LP solver.])
       AC_MSG_RESULT([yes])
     else
Index: scripts/unify-sources.sh
===================================================================
--- scripts/unify-sources.sh	(revision 675)
+++ scripts/unify-sources.sh	(revision 601)
@@ -1,11 +1,6 @@
 #!/bin/bash
 
-YEAR=`date +%Y`
+YEAR=`date +2003-%Y`
 HGROOT=`hg root`
-
-function hg_year() {
-    if [ -n "$(hg st $1)" ]; then
-        echo $YEAR
-}
 
 # file enumaration modes
@@ -197,5 +192,5 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-"$(hg_year $1)"
+ * Copyright (C) "$YEAR"
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
Index: test/CMakeLists.txt
===================================================================
--- test/CMakeLists.txt	(revision 674)
+++ test/CMakeLists.txt	(revision 668)
@@ -37,20 +37,20 @@
   unionfind_test)
 
-IF(LEMON_HAVE_LP)
+IF(HAVE_LP)
   ADD_EXECUTABLE(lp_test lp_test.cc)
   SET(LP_TEST_LIBS lemon)
-  IF(LEMON_HAVE_GLPK)
+  IF(HAVE_GLPK)
     SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
-  ENDIF(LEMON_HAVE_GLPK)
-  IF(LEMON_HAVE_CPLEX)
+  ENDIF(HAVE_GLPK)
+  IF(HAVE_CPLEX)
     SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
-  ENDIF(LEMON_HAVE_CPLEX)
-  IF(LEMON_HAVE_CLP)
+  ENDIF(HAVE_CPLEX)
+  IF(HAVE_CLP)
     SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
-  ENDIF(LEMON_HAVE_CLP)
+  ENDIF(HAVE_CLP)
   TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
   ADD_TEST(lp_test lp_test)
 
-  IF(WIN32 AND LEMON_HAVE_GLPK)
+  IF(WIN32 AND HAVE_GLPK)
     GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
@@ -60,6 +60,6 @@
       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     )
-  ENDIF(WIN32 AND LEMON_HAVE_GLPK)
-  IF(WIN32 AND LEMON_HAVE_CPLEX)
+  ENDIF(WIN32 AND HAVE_GLPK)
+  IF(WIN32 AND HAVE_CPLEX)
     GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
@@ -67,23 +67,23 @@
       COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     )
-  ENDIF(WIN32 AND LEMON_HAVE_CPLEX)
-ENDIF(LEMON_HAVE_LP)
+  ENDIF(WIN32 AND HAVE_CPLEX)
+ENDIF(HAVE_LP)
 
-IF(LEMON_HAVE_MIP)
+IF(HAVE_MIP)
   ADD_EXECUTABLE(mip_test mip_test.cc)
   SET(MIP_TEST_LIBS lemon)
-  IF(LEMON_HAVE_GLPK)
+  IF(HAVE_GLPK)
     SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
-  ENDIF(LEMON_HAVE_GLPK)
-  IF(LEMON_HAVE_CPLEX)
+  ENDIF(HAVE_GLPK)
+  IF(HAVE_CPLEX)
     SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
-  ENDIF(LEMON_HAVE_CPLEX)
-  IF(LEMON_HAVE_CBC)
+  ENDIF(HAVE_CPLEX)
+  IF(HAVE_CBC)
     SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
-  ENDIF(LEMON_HAVE_CBC)
+  ENDIF(HAVE_CBC)
   TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
   ADD_TEST(mip_test mip_test)
 
-  IF(WIN32 AND LEMON_HAVE_GLPK)
+  IF(WIN32 AND HAVE_GLPK)
     GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
@@ -93,6 +93,6 @@
       COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
     )
-  ENDIF(WIN32 AND LEMON_HAVE_GLPK)
-  IF(WIN32 AND LEMON_HAVE_CPLEX)
+  ENDIF(WIN32 AND HAVE_GLPK)
+  IF(WIN32 AND HAVE_CPLEX)
     GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
     GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
@@ -100,6 +100,6 @@
       COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     )
-  ENDIF(WIN32 AND LEMON_HAVE_CPLEX)
-ENDIF(LEMON_HAVE_MIP)
+  ENDIF(WIN32 AND HAVE_CPLEX)
+ENDIF(HAVE_MIP)
 
 FOREACH(TEST_NAME ${TESTS})
Index: test/lp_test.cc
===================================================================
--- test/lp_test.cc	(revision 678)
+++ test/lp_test.cc	(revision 622)
@@ -22,19 +22,21 @@
 #include <lemon/tolerance.h>
 
+#ifdef HAVE_CONFIG_H
 #include <lemon/config.h>
-
-#ifdef LEMON_HAVE_GLPK
+#endif
+
+#ifdef HAVE_GLPK
 #include <lemon/glpk.h>
 #endif
 
-#ifdef LEMON_HAVE_CPLEX
+#ifdef HAVE_CPLEX
 #include <lemon/cplex.h>
 #endif
 
-#ifdef LEMON_HAVE_SOPLEX
+#ifdef HAVE_SOPLEX
 #include <lemon/soplex.h>
 #endif
 
-#ifdef LEMON_HAVE_CLP
+#ifdef HAVE_CLP
 #include <lemon/clp.h>
 #endif
@@ -378,5 +380,5 @@
   lpTest(lp_skel);
 
-#ifdef LEMON_HAVE_GLPK
+#ifdef HAVE_GLPK
   {
     GlpkLp lp_glpk1,lp_glpk2;
@@ -387,5 +389,5 @@
 #endif
 
-#ifdef LEMON_HAVE_CPLEX
+#ifdef HAVE_CPLEX
   try {
     CplexLp lp_cplex1,lp_cplex2;
@@ -398,5 +400,5 @@
 #endif
 
-#ifdef LEMON_HAVE_SOPLEX
+#ifdef HAVE_SOPLEX
   {
     SoplexLp lp_soplex1,lp_soplex2;
@@ -407,5 +409,5 @@
 #endif
 
-#ifdef LEMON_HAVE_CLP
+#ifdef HAVE_CLP
   {
     ClpLp lp_clp1,lp_clp2;
Index: test/min_cost_flow_test.cc
===================================================================
--- test/min_cost_flow_test.cc	(revision 662)
+++ test/min_cost_flow_test.cc	(revision 687)
@@ -19,4 +19,5 @@
 #include <iostream>
 #include <fstream>
+#include <limits>
 
 #include <lemon/list_graph.h>
@@ -34,41 +35,41 @@
 char test_lgf[] =
   "@nodes\n"
-  "label  sup1 sup2 sup3 sup4 sup5\n"
-  "    1    20   27    0   20   30\n"
-  "    2    -4    0    0   -8   -3\n"
-  "    3     0    0    0    0    0\n"
-  "    4     0    0    0    0    0\n"
-  "    5     9    0    0    6   11\n"
-  "    6    -6    0    0   -5   -6\n"
-  "    7     0    0    0    0    0\n"
-  "    8     0    0    0    0    3\n"
-  "    9     3    0    0    0    0\n"
-  "   10    -2    0    0   -7   -2\n"
-  "   11     0    0    0  -10    0\n"
-  "   12   -20  -27    0  -30  -20\n"
-  "\n"
+  "label  sup1 sup2 sup3 sup4 sup5 sup6\n"
+  "    1    20   27    0   30   20   30\n"
+  "    2    -4    0    0    0   -8   -3\n"
+  "    3     0    0    0    0    0    0\n"
+  "    4     0    0    0    0    0    0\n"
+  "    5     9    0    0    0    6   11\n"
+  "    6    -6    0    0    0   -5   -6\n"
+  "    7     0    0    0    0    0    0\n"
+  "    8     0    0    0    0    0    3\n"
+  "    9     3    0    0    0    0    0\n"
+  "   10    -2    0    0    0   -7   -2\n"
+  "   11     0    0    0    0  -10    0\n"
+  "   12   -20  -27    0  -30  -30  -20\n"
+  "\n"                
   "@arcs\n"
-  "       cost  cap low1 low2\n"
-  " 1  2    70   11    0    8\n"
-  " 1  3   150    3    0    1\n"
-  " 1  4    80   15    0    2\n"
-  " 2  8    80   12    0    0\n"
-  " 3  5   140    5    0    3\n"
-  " 4  6    60   10    0    1\n"
-  " 4  7    80    2    0    0\n"
-  " 4  8   110    3    0    0\n"
-  " 5  7    60   14    0    0\n"
-  " 5 11   120   12    0    0\n"
-  " 6  3     0    3    0    0\n"
-  " 6  9   140    4    0    0\n"
-  " 6 10    90    8    0    0\n"
-  " 7  1    30    5    0    0\n"
-  " 8 12    60   16    0    4\n"
-  " 9 12    50    6    0    0\n"
-  "10 12    70   13    0    5\n"
-  "10  2   100    7    0    0\n"
-  "10  7    60   10    0    0\n"
-  "11 10    20   14    0    6\n"
-  "12 11    30   10    0    0\n"
+  "       cost  cap low1 low2 low3\n"
+  " 1  2    70   11    0    8    8\n"
+  " 1  3   150    3    0    1    0\n"
+  " 1  4    80   15    0    2    2\n"
+  " 2  8    80   12    0    0    0\n"
+  " 3  5   140    5    0    3    1\n"
+  " 4  6    60   10    0    1    0\n"
+  " 4  7    80    2    0    0    0\n"
+  " 4  8   110    3    0    0    0\n"
+  " 5  7    60   14    0    0    0\n"
+  " 5 11   120   12    0    0    0\n"
+  " 6  3     0    3    0    0    0\n"
+  " 6  9   140    4    0    0    0\n"
+  " 6 10    90    8    0    0    0\n"
+  " 7  1    30    5    0    0   -5\n"
+  " 8 12    60   16    0    4    3\n"
+  " 9 12    50    6    0    0    0\n"
+  "10 12    70   13    0    5    2\n"
+  "10  2   100    7    0    0    0\n"
+  "10  7    60   10    0    0   -3\n"
+  "11 10    20   14    0    6  -20\n"
+  "12 11    30   10    0    0  -10\n"
   "\n"
   "@attributes\n"
@@ -77,5 +78,5 @@
 
 
-enum ProblemType {
+enum SupplyType {
   EQ,
   GEQ,
@@ -99,6 +100,4 @@
              .lowerMap(lower)
              .upperMap(upper)
-             .capacityMap(upper)
-             .boundMaps(lower, upper)
              .costMap(cost)
              .supplyMap(sup)
@@ -113,8 +112,10 @@
       const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
 
-      v = const_mcf.totalCost();
+      c = const_mcf.totalCost();
       double x = const_mcf.template totalCost<double>();
       v = const_mcf.flow(a);
-      v = const_mcf.potential(n);
+      c = const_mcf.potential(n);
+      
+      v = const_mcf.INF;
 
       ignore_unused_variable_warning(fm);
@@ -138,4 +139,5 @@
     const Flow &k;
     Flow v;
+    Cost c;
     bool b;
 
@@ -152,5 +154,5 @@
 bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
                 const SM& supply, const FM& flow,
-                ProblemType type = EQ )
+                SupplyType type = EQ )
 {
   TEMPLATE_DIGRAPH_TYPEDEFS(GR);
@@ -209,14 +211,15 @@
 template < typename MCF, typename GR,
            typename LM, typename UM,
-           typename CM, typename SM >
-void checkMcf( const MCF& mcf, bool mcf_result,
+           typename CM, typename SM,
+           typename PT >
+void checkMcf( const MCF& mcf, PT mcf_result,
                const GR& gr, const LM& lower, const UM& upper,
                const CM& cost, const SM& supply,
-               bool result, typename CM::Value total,
+               PT result, bool optimal, typename CM::Value total,
                const std::string &test_id = "",
-               ProblemType type = EQ )
+               SupplyType type = EQ )
 {
   check(mcf_result == result, "Wrong result " + test_id);
-  if (result) {
+  if (optimal) {
     check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
           "The flow is not feasible " + test_id);
@@ -245,6 +248,6 @@
   // Read the test digraph
   Digraph gr;
-  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
-  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
+  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
+  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
   ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
   Node v, w;
@@ -256,4 +259,5 @@
     .arcMap("low1", l1)
     .arcMap("low2", l2)
+    .arcMap("low3", l3)
     .nodeMap("sup1", s1)
     .nodeMap("sup2", s2)
@@ -261,7 +265,48 @@
     .nodeMap("sup4", s4)
     .nodeMap("sup5", s5)
+    .nodeMap("sup6", s6)
     .node("source", v)
     .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();
+  
+  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);
+  
+  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);
+  
+  nl2[a7] =  1000;
+  nl2[a8] = -1000;
+  
+  ns[n1] =  100;
+  ns[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;
 
   // A. Test NetworkSimplex with the default pivot rule
@@ -272,44 +317,58 @@
     mcf.upperMap(u).costMap(c);
     checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l1, u, c, s1, true,  5240, "#A1");
+             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
-             gr, l1, u, c, s2, true,  7620, "#A2");
+             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
     mcf.lowerMap(l2);
     checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l2, u, c, s1, true,  5970, "#A3");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
     checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
-             gr, l2, u, c, s2, true,  8010, "#A4");
+             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
     mcf.reset();
     checkMcf(mcf, mcf.supplyMap(s1).run(),
-             gr, l1, cu, cc, s1, true,  74, "#A5");
+             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
     checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
-             gr, l2, cu, cc, s2, true,  94, "#A6");
+             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
     mcf.reset();
     checkMcf(mcf, mcf.run(),
-             gr, l1, cu, cc, s3, true,   0, "#A7");
-    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
-             gr, l2, u, cc, s3, false,   0, "#A8");
+             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
+    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
+             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
+    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
+    checkMcf(mcf, mcf.run(),
+             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
 
     // Check the GEQ form
-    mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
-    checkMcf(mcf, mcf.run(),
-             gr, l1, u, c, s4, true,  3530, "#A9", GEQ);
-    mcf.problemType(mcf.GEQ);
+    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
+    checkMcf(mcf, mcf.run(),
+             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
+    mcf.supplyType(mcf.GEQ);
     checkMcf(mcf, mcf.lowerMap(l2).run(),
-             gr, l2, u, c, s4, true,  4540, "#A10", GEQ);
-    mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
-    checkMcf(mcf, mcf.run(),
-             gr, l2, u, c, s5, false,    0, "#A11", GEQ);
+             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
+    mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
+    checkMcf(mcf, mcf.run(),
+             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
 
     // Check the LEQ form
-    mcf.reset().problemType(mcf.LEQ);
-    mcf.upperMap(u).costMap(c).supplyMap(s5);
-    checkMcf(mcf, mcf.run(),
-             gr, l1, u, c, s5, true,  5080, "#A12", LEQ);
+    mcf.reset().supplyType(mcf.LEQ);
+    mcf.upperMap(u).costMap(c).supplyMap(s6);
+    checkMcf(mcf, mcf.run(),
+             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
     checkMcf(mcf, mcf.lowerMap(l2).run(),
-             gr, l2, u, c, s5, true,  5930, "#A13", LEQ);
-    mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
-    checkMcf(mcf, mcf.run(),
-             gr, l2, u, c, s4, false,    0, "#A14", LEQ);
+             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
+    mcf.supplyType(mcf.SATISFY_DEMANDS).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");
   }
 
@@ -317,16 +376,16 @@
   {
     NetworkSimplex<Digraph> mcf(gr);
-    mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
+    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
 
     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
-             gr, l2, u, c, s1, true,  5970, "#B1");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
-             gr, l2, u, c, s1, true,  5970, "#B2");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
-             gr, l2, u, c, s1, true,  5970, "#B3");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
-             gr, l2, u, c, s1, true,  5970, "#B4");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
     checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
-             gr, l2, u, c, s1, true,  5970, "#B5");
+             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
   }
 
Index: test/mip_test.cc
===================================================================
--- test/mip_test.cc	(revision 678)
+++ test/mip_test.cc	(revision 622)
@@ -19,15 +19,17 @@
 #include "test_tools.h"
 
+#ifdef HAVE_CONFIG_H
 #include <lemon/config.h>
+#endif
 
-#ifdef LEMON_HAVE_CPLEX
+#ifdef HAVE_CPLEX
 #include <lemon/cplex.h>
 #endif
 
-#ifdef LEMON_HAVE_GLPK
+#ifdef HAVE_GLPK
 #include <lemon/glpk.h>
 #endif
 
-#ifdef LEMON_HAVE_CBC
+#ifdef HAVE_CBC
 #include <lemon/cbc.h>
 #endif
@@ -128,5 +130,5 @@
 {
 
-#ifdef LEMON_HAVE_GLPK
+#ifdef HAVE_GLPK
   {
     GlpkMip mip1;
@@ -136,5 +138,5 @@
 #endif
 
-#ifdef LEMON_HAVE_CPLEX
+#ifdef HAVE_CPLEX
   try {
     CplexMip mip2;
@@ -146,5 +148,5 @@
 #endif
 
-#ifdef LEMON_HAVE_CBC
+#ifdef HAVE_CBC
   {
     CbcMip mip1;
Index: tools/dimacs-solver.cc
===================================================================
--- tools/dimacs-solver.cc	(revision 674)
+++ tools/dimacs-solver.cc	(revision 687)
@@ -120,6 +120,6 @@
   ti.restart();
   NetworkSimplex<Digraph, Value> ns(g);
-  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
-  if (sum_sup > 0) ns.problemType(ns.LEQ);
+  ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
+  if (sum_sup > 0) ns.supplyType(ns.LEQ);
   if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
   ti.restart();
@@ -201,5 +201,5 @@
     .boolOption("int","Use 'int' for capacities, costs etc. (default)")
     .optionGroup("datatype","int")
-#ifdef LEMON_HAVE_LONG_LONG
+#ifdef HAVE_LONG_LONG
     .boolOption("long","Use 'long long' for capacities, costs etc.")
     .optionGroup("datatype","long")
@@ -268,5 +268,5 @@
   else if(ap.given("ldouble"))
     solve<long double>(ap,is,os,desc);
-#ifdef LEMON_HAVE_LONG_LONG
+#ifdef HAVE_LONG_LONG
   else if(ap.given("long"))
     solve<long long>(ap,is,os,desc);
