Changes in / [1386:ad22262328b3:1395:f425c93848fa] in lemon

Files:

• CMakeLists.txt (modified) (7 diffs)
• NEWS (modified) (1 diff)
• cmake/FindILOG.cmake (modified) (2 diffs)
• lemon/CMakeLists.txt (modified) (1 diff)
• lemon/arg_parser.h (modified) (1 diff)
• lemon/bits/windows.cc (modified) (9 diffs)
• lemon/bits/windows.h (modified) (2 diffs)
• lemon/capacity_scaling.h (modified) (7 diffs)
• lemon/config.h.in (modified) (2 diffs)
• lemon/core.h (modified) (2 diffs)
• lemon/cost_scaling.h (modified) (7 diffs)
• lemon/counter.h (modified) (1 diff)
• lemon/cplex.cc (modified) (2 diffs)
• lemon/cplex.h (modified) (2 diffs)
• lemon/cycle_canceling.h (modified) (7 diffs)
• lemon/dim2.h (modified) (1 diff)
• lemon/dimacs.h (modified) (7 diffs)
• lemon/elevator.h (modified) (2 diffs)
• lemon/graph_to_eps.h (modified) (3 diffs)
• lemon/list_graph.h (modified) (6 diffs)
• lemon/lp.h (modified) (4 diffs)
• lemon/math.h (modified) (1 diff)
• lemon/nearest_neighbor_tsp.h (modified) (2 diffs)
• lemon/network_simplex.h (modified) (7 diffs)
• lemon/preflow.h (modified) (6 diffs)
• lemon/radix_sort.h (modified) (1 diff)
• lemon/random.h (modified) (7 diffs)
• lemon/static_graph.h (modified) (1 diff)
• lemon/time_measure.h (modified) (2 diffs)
• test/arc_look_up_test.cc (modified) (1 diff)
• test/bpgraph_test.cc (modified) (5 diffs)
• test/lp_test.cc (modified) (2 diffs)
• test/max_flow_test.cc (modified) (14 diffs)
• test/min_cost_flow_test.cc (modified) (1 diff)
• test/mip_test.cc (modified) (2 diffs)
• test/radix_sort_test.cc (modified) (1 diff)
• test/tsp_test.cc (modified) (1 diff)
• tools/lgf-gen.cc (modified) (8 diffs)

CMakeLists.txt

@@ -1 @@
-CMAKE_MINIMUM_REQUIRED(VERSION 2.6)
+CMAKE_MINIMUM_REQUIRED(VERSION 2.8)
+
+IF(POLICY CMP0048) 
+  CMAKE_POLICY(SET CMP0048 OLD) 
+ENDIF(POLICY CMP0048)
+
+IF(POLICY CMP0026)
+  #This is for copying the dll's needed by glpk (in lp_test and mip_test)
+  CMAKE_POLICY(SET CMP0026 OLD) 
+ENDIF(POLICY CMP0026)
 
 SET(PROJECT_NAME "LEMON")
@@ -62 +71 @@
 FIND_PACKAGE(Doxygen)
 FIND_PACKAGE(Ghostscript)
+
+IF(WIN32)
+  SET(LEMON_WIN32 TRUE)
+ENDIF(WIN32)
 
 SET(LEMON_ENABLE_GLPK YES CACHE STRING "Enable GLPK solver backend.")
@@ -122 +135 @@
   SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
     "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)" FORCE)
+ELSE()
+  SET(LEMON_DEFAULT_LP ${DEFAULT_LP} CACHE STRING
+    "Default LP solver backend (GLPK, CPLEX, CLP or SOPLEX)")
 ENDIF()
 IF(NOT LEMON_DEFAULT_MIP OR
@@ -129 +145 @@
   SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
     "Default MIP solver backend (GLPK, CPLEX or CBC)" FORCE)
+ELSE()
+  SET(LEMON_DEFAULT_MIP ${DEFAULT_MIP} CACHE STRING
+    "Default MIP solver backend (GLPK, CPLEX or CBC)")
 ENDIF()
 
@@ -141 +160 @@
   ELSEIF(MSVC)
     # This part is unnecessary 'casue the same is set by the lemon/core.h.
-    # Still keep it as an example.
-    SET(CXX_WARNING "/wd4250 /wd4355 /wd4503 /wd4800 /wd4996")
+    # Still kept as an example.
+
+    # SET(CXX_WARNING "/wd4250 /wd4267 /wd4355 /wd4503 /wd4800 /wd4996")
+
     # Suppressed warnings:
     # C4250: 'class1' : inherits 'class2::member' via dominance
+    # C4267: conversion from 'size_t' to 'type', possible loss of data
     # C4355: 'this' : used in base member initializer list
     # C4503: 'function' : decorated name length exceeded, name was truncated
@@ -159 +181 @@
 
 IF(MSVC)
+  SET(CMAKE_CXX_FLAGS "/bigobj ${CMAKE_CXX_FLAGS}")
   SET( CMAKE_CXX_FLAGS_MAINTAINER "/WX ${CMAKE_CXX_FLAGS_DEBUG}" CACHE STRING
     "Flags used by the C++ compiler during maintainer builds."
@@ -181 +204 @@
     )
   SET( CMAKE_EXE_LINKER_FLAGS_MAINTAINER
-    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "${CMAKE_EXE_LINKER_FLAGS_DEBUG}" CACHE STRING
     "Flags used for linking binaries during maintainer builds."
     )
   SET( CMAKE_SHARED_LINKER_FLAGS_MAINTAINER
-    "-Wl,--warn-unresolved-symbols,--warn-once" CACHE STRING
+    "${CMAKE_SHARED_LINKER_FLAGS_DEBUG}" CACHE STRING
     "Flags used by the shared libraries linker during maintainer builds."
     )

NEWS

@@ +1 @@
+2013-08-10 Version 1.3 released
+
+        This is major feature release
+
+        * New data structures
+
+          #69 : Bipartite graph concepts and implementations
+
+        * New algorithms
+
+          #177: Port Edmonds-Karp algorithm
+          #380, #405: Heuristic algorithm for the max clique problem
+          #386: Heuristic algorithms for symmetric TSP
+          ----: Nagamochi-Ibaraki algorithm [5087694945e4]
+          #397, #56: Max. cardinality search
+
+        * Other new features
+
+          #223: Thread safe graph and graph map implementations
+          #442: Different TimeStamp print formats
+          #457: File export functionality to LpBase
+          #362: Bidirectional iterator support for radixSort()
+
+        * Implementation improvements
+
+          ----: Network Simplex
+                #391: Better update process, pivot rule and arc mixing
+                #435: Improved Altering List pivot rule
+          #417: Various fine tunings in CostScaling
+          #438: Optional iteration limit in HowardMmc
+          #436: Ensure strongly polynomial running time for CycleCanceling
+                while keeping the same performance
+          ----: Make the CBC interface be compatible with latest CBC releases
+                [ee581a0ecfbf]
+
+        * CMAKE has become the default build environment (#434)
+
+          ----: Autotool support has been dropped
+          ----: Improved LP/MIP configuration
+                #465: Enable/disable options for LP/MIP backends
+                #446: Better CPLEX discovery
+                #460: Add cmake config to find SoPlex
+          ----: Allow CPACK configuration on all platforms
+          #390: Add 'Maintainer' CMAKE build type
+          #388: Add 'check' target.
+          #401: Add contrib dir
+          #389: Better version string setting in CMAKE
+          #433: Support shared library build    
+          #416: Support testing with valgrind
+  
+        * Doc improvements
+
+          #395: SOURCE_BROWSER Doxygen switch is configurable from CMAKE
+                update-external-tags CMAKE target
+          #455: Optionally use MathJax for rendering the math formulae
+          #402, #437, #459, #456, #463: Various doc improvements
+
+        * Bugfixes (compared to release 1.2):
+
+          #432: Add missing doc/template.h and doc/references.bib to release
+                tarball
+          ----: Intel C++ compatibility fixes
+          #441: Fix buggy reinitialization in _solver_bits::VarIndex::clear()
+          #444: Bugfix in path copy constructors and assignment operators
+          #447: Bugfix in AllArcLookUp<>
+          #448: Bugfix in adaptor_test.cc
+          #449: Fix clang compilation warnings and errors
+          #440: Fix a bug + remove redundant typedefs in dimacs-solver
+          #453: Avoid GCC 4.7 compiler warnings
+          #445: Fix missing initialization in CplexEnv::CplexEnv()
+          #428: Add missing lemon/lemon.pc.cmake to the release tarball
+          #393: Create and install lemon.pc
+          #429: Fix VS warnings
+          #430: Fix LpBase::Constr two-side limit bug
+          #392: Bug fix in Dfs::start(s,t)
+          #414: Fix wrong initialization in Preflow
+          #418: Better Win CodeBlock/MinGW support
+          #419: Build environment improvements
+                - Build of mip_test and lp_test precede the running of the tests
+                - Also search for coin libs under ${COIN_ROOT_DIR}/lib/coin
+                - Do not look for COIN_VOL libraries
+          #382: Allow lgf file without Arc maps
+          #417: Bug fix in CostScaling
+          #366: Fix Pred[Matrix]MapPath::empty()
+          #371: Bug fix in (di)graphCopy()
+                The target graph is cleared before adding nodes and arcs/edges.
+          #364: Add missing UndirectedTags
+          #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
+          #372: Fix a critical bug in preflow
+          #461: Bugfix in assert.h
+          #470: Fix compilation issues related to various gcc versions
+          #446: Fix #define indicating CPLEX availability
+          #294: Add explicit namespace to
+                ignore_unused_variable_warning() usages
+          #420: Bugfix in IterableValueMap
+          #439: Bugfix in biNodeConnected()
+
+
 2010-03-19 Version 1.2 released
 

cmake/FindILOG.cmake

@@ -63 +63 @@
   ${ILOG_CPLEX_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
   ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
+  ${ILOG_CPLEX_ROOT_DIR}/lib/x86_linux/static_pic
+  ${ILOG_CPLEX_ROOT_DIR}/lib/x86-64_linux/static_pic
   ${ILOG_CPLEX_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
   NO_DEFAULT_PATH
@@ -73 +75 @@
   ${ILOG_CONCERT_ROOT_DIR}/lib/x86_debian4.0_4.1/static_pic
   ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_debian4.0_4.1/static_pic
+  ${ILOG_CONCERT_ROOT_DIR}/lib/x86_linux/static_pic
+  ${ILOG_CONCERT_ROOT_DIR}/lib/x86-64_linux/static_pic
   ${ILOG_CONCERT_ROOT_DIR}/lib/${ILOG_WIN_COMPILER}/stat_mda
   NO_DEFAULT_PATH

lemon/CMakeLists.txt

@@ -56 +56 @@
 
 ADD_LIBRARY(lemon ${LEMON_SOURCES})
+
+TARGET_LINK_LIBRARIES(lemon
+  ${GLPK_LIBRARIES} ${COIN_LIBRARIES} ${ILOG_LIBRARIES} ${SOPLEX_LIBRARIES}
+  )
+
 IF(UNIX)
-  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon)
+  SET_TARGET_PROPERTIES(lemon PROPERTIES OUTPUT_NAME emon VERSION ${LEMON_VERSION} SOVERSION ${LEMON_VERSION})
 ENDIF()
 

lemon/arg_parser.h

@@ -27 +27 @@
 #include <sstream>
 #include <algorithm>
+#include <lemon/core.h>
 #include <lemon/assert.h>
 

lemon/bits/windows.cc

@@ -22 +22 @@
 #include<lemon/bits/windows.h>
 
-#ifdef WIN32
+#if defined(LEMON_WIN32) && defined(__GNUC__)
+#pragma GCC diagnostic ignored "-Wold-style-cast"
+#endif
+
+#ifdef LEMON_WIN32
 #ifndef WIN32_LEAN_AND_MEAN
 #define WIN32_LEAN_AND_MEAN
@@ -41 +45 @@
 #include <unistd.h>
 #include <ctime>
-#ifndef WIN32
+#ifndef LEMON_WIN32
 #include <sys/times.h>
 #endif
@@ -56 +60 @@
                          double &cutime, double &cstime)
     {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       static const double ch = 4294967296.0e-7;
       static const double cl = 1.0e-7;
@@ -95 +99 @@
     {
       std::ostringstream os;
-#ifdef WIN32
+#ifdef LEMON_WIN32
       SYSTEMTIME time;
       GetSystemTime(&time);
       char buf1[11], buf2[9], buf3[5];
-          if (GetDateFormat(MY_LOCALE, 0, &time,
+      if (GetDateFormat(MY_LOCALE, 0, &time,
                         ("ddd MMM dd"), buf1, 11) &&
           GetTimeFormat(MY_LOCALE, 0, &time,
@@ -121 +125 @@
     int getWinRndSeed()
     {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       FILETIME time;
       GetSystemTimeAsFileTime(&time);
@@ -133 +137 @@
 
     WinLock::WinLock() {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       CRITICAL_SECTION *lock = new CRITICAL_SECTION;
       InitializeCriticalSection(lock);
@@ -143 +147 @@
 
     WinLock::~WinLock() {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
       DeleteCriticalSection(lock);
@@ -151 +155 @@
 
     void WinLock::lock() {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
       EnterCriticalSection(lock);
@@ -158 +162 @@
 
     void WinLock::unlock() {
-#ifdef WIN32
+#ifdef LEMON_WIN32
       CRITICAL_SECTION *lock = static_cast<CRITICAL_SECTION*>(_repr);
       LeaveCriticalSection(lock);

lemon/bits/windows.h

@@ -20 +20 @@
 #define LEMON_BITS_WINDOWS_H
 
+#include <lemon/config.h>
 #include <string>
 
@@ -35 +36 @@
       ~WinLock();
       void lock();
-      void unlock();
+      void unlock();\
     private:
       void *_repr;

lemon/capacity_scaling.h

@@ -28 +28 @@
 #include <limits>
 #include <lemon/core.h>
+#include <lemon/maps.h>
 #include <lemon/bin_heap.h>
 
@@ -164 +165 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
 
@@ -357 +358 @@
     template <typename LowerMap>
     CapacityScaling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
+      _has_lower = true;
       for (ArcIt a(_graph); a != INVALID; ++a) {
         _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
       }
       return *this;
@@ -544 +544 @@
         _cost[j] = _forward[j] ? 1 : -1;
       }
-      _have_lower = false;
+      _has_lower = false;
       return *this;
     }
@@ -755 +755 @@
       const Value MAX = std::numeric_limits<Value>::max();
       int last_out;
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _root; ++i) {
           last_out = _first_out[i+1];
@@ -840 +840 @@
     }
 
-    // Check if the upper bound is greater or equal to the lower bound
-    // on each arc.
+    // Check if the upper bound is greater than or equal to the lower bound
+    // on each forward arc.
     bool checkBoundMaps() {
       for (int j = 0; j != _res_arc_num; ++j) {
-        if (_upper[j] < _lower[j]) return false;
+        if (_forward[j] && _upper[j] < _lower[j]) return false;
       }
       return true;
@@ -858 +858 @@
 
       // Handle non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         int limit = _first_out[_root];
         for (int j = 0; j != limit; ++j) {
-          if (!_forward[j]) _res_cap[j] += _lower[j];
+          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
         }
       }

lemon/config.h.in

@@ +1 @@
+#ifndef LEMON_CONFIG_H
+#define LEMON_CONFIG_H
+
 #define LEMON_VERSION "@PROJECT_VERSION@"
 #cmakedefine LEMON_HAVE_LONG_LONG 1
+
+#cmakedefine LEMON_WIN32 1
+
 #cmakedefine LEMON_HAVE_LP 1
 #cmakedefine LEMON_HAVE_MIP 1
@@ -8 +14 @@
 #cmakedefine LEMON_HAVE_CLP 1
 #cmakedefine LEMON_HAVE_CBC 1
-#cmakedefine LEMON_DEFAULT_LP @LEMON_DEFAULT_LP@
-#cmakedefine LEMON_DEFAULT_MIP @LEMON_DEFAULT_MIP@
+
+#define LEMON_CPLEX_ 1
+#define LEMON_CLP_ 2
+#define LEMON_GLPK_ 3
+#define LEMON_SOPLEX_ 4
+#define LEMON_CBC_ 5
+
+#cmakedefine LEMON_DEFAULT_LP LEMON_@LEMON_DEFAULT_LP@_
+#cmakedefine LEMON_DEFAULT_MIP LEMON_@LEMON_DEFAULT_MIP@_
+
 #cmakedefine LEMON_USE_PTHREAD 1
 #cmakedefine LEMON_USE_WIN32_THREADS 1
+
+#endif

lemon/core.h

@@ -20 +20 @@
 #define LEMON_CORE_H
 
-#include <vector>
-#include <algorithm>
-
-#include <lemon/config.h>
-#include <lemon/bits/enable_if.h>
-#include <lemon/bits/traits.h>
-#include <lemon/assert.h>
-
-// Disable the following warnings when compiling with MSVC:
-// C4250: 'class1' : inherits 'class2::member' via dominance
-// C4355: 'this' : used in base member initializer list
-// C4503: 'function' : decorated name length exceeded, name was truncated
-// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
-// C4996: 'function': was declared deprecated
-#ifdef _MSC_VER
-#pragma warning( disable : 4250 4355 4503 4800 4996 )
-#endif
-
-#ifdef __GNUC__
-#define GCC_VERSION (__GNUC__ * 10000                   \
-                     + __GNUC_MINOR__ * 100             \
-                     + __GNUC_PATCHLEVEL__)
-#endif
-
-#if GCC_VERSION >= 40800
-// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
-#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
-#endif
-
 ///\file
 ///\brief LEMON core utilities.
@@ -55 +26 @@
 ///It is automatically included by all graph types, therefore it usually
 ///do not have to be included directly.
+
+// Disable the following warnings when compiling with MSVC:
+// C4250: 'class1' : inherits 'class2::member' via dominance
+// C4267: conversion from 'size_t' to 'type', possible loss of data
+// C4355: 'this' : used in base member initializer list
+// C4503: 'function' : decorated name length exceeded, name was truncated
+// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
+// C4996: 'function': was declared deprecated
+#ifdef _MSC_VER
+#pragma warning( disable : 4250 4267 4355 4503 4800 4996 )
+#endif
+
+#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)
+// Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8
+#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
+#endif
+
+#include <vector>
+#include <algorithm>
+
+#include <lemon/config.h>
+#include <lemon/bits/enable_if.h>
+#include <lemon/bits/traits.h>
+#include <lemon/assert.h>
+
+
 
 namespace lemon {

lemon/cost_scaling.h

@@ -257 +257 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
     int _sup_node_num;
@@ -373 +373 @@
     template <typename LowerMap>
     CostScaling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
+      _has_lower = true;
       for (ArcIt a(_graph); a != INVALID; ++a) {
         _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
       }
       return *this;
@@ -569 +568 @@
         _scost[_reverse[j]] = 0;
       }
-      _have_lower = false;
+      _has_lower = false;
       return *this;
     }
@@ -781 +780 @@
       const Value MAX = std::numeric_limits<Value>::max();
       int last_out;
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _root; ++i) {
           last_out = _first_out[i+1];
@@ -838 +837 @@
         sup[n] = _supply[_node_id[n]];
       }
-      if (_have_lower) {
+      if (_has_lower) {
         for (ArcIt a(_graph); a != INVALID; ++a) {
           int j = _arc_idf[a];
@@ -908 +907 @@
     }
 
-    // Check if the upper bound is greater or equal to the lower bound
-    // on each arc.
+    // Check if the upper bound is greater than or equal to the lower bound
+    // on each forward arc.
     bool checkBoundMaps() {
       for (int j = 0; j != _res_arc_num; ++j) {
-        if (_upper[j] < _lower[j]) return false;
+        if (_forward[j] && _upper[j] < _lower[j]) return false;
       }
       return true;
@@ -992 +991 @@
 
       // Handle non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         int limit = _first_out[_root];
         for (int j = 0; j != limit; ++j) {
-          if (!_forward[j]) _res_cap[j] += _lower[j];
+          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
         }
       }

lemon/counter.h

@@ -22 +22 @@
 #include <string>
 #include <iostream>
+
+#include <lemon/core.h>
 
 ///\ingroup timecount

lemon/cplex.cc

@@ -38 +38 @@
   }
 
+  void CplexEnv::incCnt()
+  {
+    _cnt_lock->lock();
+    ++(*_cnt);
+    _cnt_lock->unlock();
+  }
+
+  void CplexEnv::decCnt()
+  {
+    _cnt_lock->lock();
+    --(*_cnt);
+    if (*_cnt == 0) {
+      delete _cnt;
+      _cnt_lock->unlock();
+      delete _cnt_lock;
+      CPXcloseCPLEX(&_env);
+    }
+    else _cnt_lock->unlock();
+  }
+  
   CplexEnv::CplexEnv() {
     int status;
+    _env = CPXopenCPLEX(&status);
+    if (_env == 0)
+      throw LicenseError(status);
     _cnt = new int;
     (*_cnt) = 1;
-    _env = CPXopenCPLEX(&status);
-    if (_env == 0) {
-      delete _cnt;
-      _cnt = 0;
-      throw LicenseError(status);
-    }
+    _cnt_lock = new bits::Lock;
   }
 
@@ -53 +71 @@
     _env = other._env;
     _cnt = other._cnt;
-    ++(*_cnt);
+    _cnt_lock = other._cnt_lock;
+    incCnt();
   }
 
   CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
+    decCnt();
     _env = other._env;
     _cnt = other._cnt;
-    ++(*_cnt);
+    _cnt_lock = other._cnt_lock;
+    incCnt();
     return *this;
   }
 
   CplexEnv::~CplexEnv() {
-    --(*_cnt);
-    if (*_cnt == 0) {
-      delete _cnt;
-      CPXcloseCPLEX(&_env);
-    }
+    decCnt();
   }
 

lemon/cplex.h

@@ -24 +24 @@
 
 #include <lemon/lp_base.h>
+#include <lemon/bits/lock.h>
 
 struct cpxenv;
@@ -41 +42 @@
     cpxenv* _env;
     mutable int* _cnt;
-
+    mutable bits::Lock* _cnt_lock;
+
+    void incCnt();
+    void decCnt();
+    
   public:
 

lemon/cycle_canceling.h

@@ -196 +196 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
 
@@ -279 +279 @@
     template <typename LowerMap>
     CycleCanceling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
+      _has_lower = true;
       for (ArcIt a(_graph); a != INVALID; ++a) {
         _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
       }
       return *this;
@@ -472 +471 @@
         _cost[_reverse[j]] = 0;
       }
-      _have_lower = false;
+      _has_lower = false;
       return *this;
     }
@@ -685 +684 @@
       const Value MAX = std::numeric_limits<Value>::max();
       int last_out;
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _root; ++i) {
           last_out = _first_out[i+1];
@@ -728 +727 @@
         sup[n] = _supply[_node_id[n]];
       }
-      if (_have_lower) {
+      if (_has_lower) {
         for (ArcIt a(_graph); a != INVALID; ++a) {
           int j = _arc_idf[a];
@@ -785 +784 @@
     }
 
-    // Check if the upper bound is greater or equal to the lower bound
-    // on each arc.
+    // Check if the upper bound is greater than or equal to the lower bound
+    // on each forward arc.
     bool checkBoundMaps() {
       for (int j = 0; j != _res_arc_num; ++j) {
-        if (_upper[j] < _lower[j]) return false;
+        if (_forward[j] && _upper[j] < _lower[j]) return false;
       }
       return true;
@@ -836 +835 @@
 
       // Handle non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         int limit = _first_out[_root];
         for (int j = 0; j != limit; ++j) {
-          if (!_forward[j]) _res_cap[j] += _lower[j];
+          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
         }
       }

lemon/dim2.h

@@ -21 +21 @@
 
 #include <iostream>
+#include <algorithm>
 
 ///\ingroup geomdat

lemon/dimacs.h

@@ -26 +26 @@
 #include <lemon/maps.h>
 #include <lemon/error.h>
+
 /// \ingroup dimacs_group
 /// \file
@@ -123 +124 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c dest parameter.
+  /// the descriptor struct should be given by the \c desc parameter.
   template <typename Digraph, typename LowerMap,
             typename CapacityMap, typename CostMap,
@@ -277 +278 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c dest parameter.
+  /// the descriptor struct should be given by the \c desc parameter.
   template<typename Digraph, typename CapacityMap>
   void readDimacsMax(std::istream& is,
@@ -304 +305 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c dest parameter.
+  /// the descriptor struct should be given by the \c desc parameter.
   template<typename Digraph, typename LengthMap>
   void readDimacsSp(std::istream& is,
@@ -335 +336 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c dest parameter.
+  /// the descriptor struct should be given by the \c desc parameter.
   template<typename Digraph, typename CapacityMap>
   void readDimacsCap(std::istream& is,
@@ -344 +345 @@
     typename Digraph::Node u,v;
     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
-    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
+    if(desc.type!=DimacsDescriptor::MAX && desc.type!=DimacsDescriptor::SP)
       throw FormatError("Problem type mismatch");
     _readDimacs(is, g, capacity, u, v, infty, desc);
@@ -375 +376 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c dest parameter.
+  /// the descriptor struct should be given by the \c desc parameter.
   template<typename Graph>
   void readDimacsMat(std::istream& is, Graph &g,

lemon/elevator.h

@@ -168 +168 @@
     int onLevel(int l) const
     {
-      return _first[l+1]-_first[l];
+      return static_cast<int>(_first[l+1]-_first[l]);
     }
     ///Return true if level \c l is empty.
@@ -178 +178 @@
     int aboveLevel(int l) const
     {
-      return _first[_max_level+1]-_first[l+1];
+      return static_cast<int>(_first[_max_level+1]-_first[l+1]);
     }
     ///Return the number of active items on level \c l.
     int activesOnLevel(int l) const
     {
-      return _last_active[l]-_first[l]+1;
+      return static_cast<int>(_last_active[l]-_first[l]+1);
     }
     ///Return true if there is no active item on level \c l.

lemon/graph_to_eps.h

@@ -26 +26 @@
 #include<vector>
 
-#ifndef WIN32
+#ifndef LEMON_WIN32
 #include<sys/time.h>
 #include<ctime>
@@ -223 +223 @@
   using T::_copyright;
 
-  using T::NodeTextColorType;
   using T::CUST_COL;
   using T::DIST_COL;
@@ -676 +675 @@
     {
       os << "%%CreationDate: ";
-#ifndef WIN32
+#ifndef LEMON_WIN32
       timeval tv;
       gettimeofday(&tv, 0);

lemon/list_graph.h

@@ -583 +583 @@
         }
         virtual void add(const std::vector<Node>& nodes) {
-          for (int i = nodes.size() - 1; i >= 0; ++i) {
+          for (int i = nodes.size() - 1; i >= 0; --i) {
             snapshot.addNode(nodes[i]);
           }
@@ -633 +633 @@
         }
         virtual void add(const std::vector<Arc>& arcs) {
-          for (int i = arcs.size() - 1; i >= 0; ++i) {
+          for (int i = arcs.size() - 1; i >= 0; --i) {
             snapshot.addArc(arcs[i]);
           }
@@ -1395 +1395 @@
         }
         virtual void add(const std::vector<Node>& nodes) {
-          for (int i = nodes.size() - 1; i >= 0; ++i) {
+          for (int i = nodes.size() - 1; i >= 0; --i) {
             snapshot.addNode(nodes[i]);
           }
@@ -1445 +1445 @@
         }
         virtual void add(const std::vector<Edge>& edges) {
-          for (int i = edges.size() - 1; i >= 0; ++i) {
+          for (int i = edges.size() - 1; i >= 0; --i) {
             snapshot.addEdge(edges[i]);
           }
@@ -2300 +2300 @@
         }
         virtual void add(const std::vector<Node>& nodes) {
-          for (int i = nodes.size() - 1; i >= 0; ++i) {
+          for (int i = nodes.size() - 1; i >= 0; --i) {
             snapshot.addNode(nodes[i]);
           }
@@ -2350 +2350 @@
         }
         virtual void add(const std::vector<Edge>& edges) {
-          for (int i = edges.size() - 1; i >= 0; ++i) {
+          for (int i = edges.size() - 1; i >= 0; --i) {
             snapshot.addEdge(edges[i]);
           }

lemon/lp.h

@@ -23 +23 @@
 
 
-#ifdef LEMON_HAVE_GLPK
+#if LEMON_DEFAULT_LP == LEMON_GLPK_ || LEMON_DEFAULT_MIP == LEMON_GLPK_
 #include <lemon/glpk.h>
-#elif LEMON_HAVE_CPLEX
+#endif
+#if LEMON_DEFAULT_LP == LEMON_CPLEX_ || LEMON_DEFAULT_MIP == LEMON_CPLEX_
 #include <lemon/cplex.h>
-#elif LEMON_HAVE_SOPLEX
+#endif
+#if LEMON_DEFAULT_LP == LEMON_SOPLEX_
 #include <lemon/soplex.h>
-#elif LEMON_HAVE_CLP
+#endif
+#if LEMON_DEFAULT_LP == LEMON_CLP_
 #include <lemon/clp.h>
+#endif
+#if LEMON_DEFAULT_MIP == LEMON_CBC_
+#include <lemon/cbc.h>
 #endif
 
@@ -44 +50 @@
   ///\ingroup lp_group
   ///
-  ///Currently, the possible values are \c GLPK, \c CPLEX,
-  ///\c SOPLEX or \c CLP
+  ///Currently, the possible values are \c LEMON_GLPK_, \c LEMON_CPLEX_,
+  ///\c LEMON_SOPLEX_ or \c LEMON_CLP_
 #define LEMON_DEFAULT_LP SOLVER
   ///The default LP solver
@@ -60 +66 @@
   ///\ingroup lp_group
   ///
-  ///Currently, the possible values are \c GLPK, \c CPLEX or \c CBC
+  ///Currently, the possible values are \c LEMON_GLPK_, \c LEMON_CPLEX_
+  ///or \c LEMON_CBC_
 #define LEMON_DEFAULT_MIP SOLVER
   ///The default MIP solver.
@@ -70 +77 @@
   typedef GlpkMip Mip;
 #else
-#if LEMON_DEFAULT_LP == GLPK
+#if LEMON_DEFAULT_LP == LEMON_GLPK_
   typedef GlpkLp Lp;
-#elif LEMON_DEFAULT_LP == CPLEX
+#elif LEMON_DEFAULT_LP == LEMON_CPLEX_
   typedef CplexLp Lp;
-#elif LEMON_DEFAULT_LP == SOPLEX
+#elif LEMON_DEFAULT_LP == LEMON_SOPLEX_
   typedef SoplexLp Lp;
-#elif LEMON_DEFAULT_LP == CLP
+#elif LEMON_DEFAULT_LP == LEMON_CLP_
   typedef ClpLp Lp;
 #endif
-#if LEMON_DEFAULT_MIP == GLPK
-  typedef GlpkLp Mip;
-#elif LEMON_DEFAULT_MIP == CPLEX
+#if LEMON_DEFAULT_MIP == LEMON_GLPK_
+  typedef GlpkMip Mip;
+#elif LEMON_DEFAULT_MIP == LEMON_CPLEX_
   typedef CplexMip Mip;
-#elif LEMON_DEFAULT_MIP == CBC
+#elif LEMON_DEFAULT_MIP == LEMON_CBC_
   typedef CbcMip Mip;
 #endif

lemon/math.h

@@ -68 +68 @@
   ///Round a value to its closest integer
   inline double round(double r) {
-    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
+    return (r > 0.0) ? std::floor(r + 0.5) : std::ceil(r - 0.5);
   }
 

lemon/nearest_neighbor_tsp.h

@@ -116 +116 @@
             for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) {
               if (!used[_gr.runningNode(e)] &&
-                  (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) {
+                  (min_edge1 == INVALID || _cost[e] < _cost[min_edge1])) {
                 min_edge1 = e;
               }
@@ -125 +125 @@
             for (IncEdgeIt e(_gr, n2); e != INVALID; ++e) {
               if (!used[_gr.runningNode(e)] &&
-                  (_cost[e] < _cost[min_edge2] || min_edge2 == INVALID)) {
+                  (min_edge2 == INVALID||_cost[e] < _cost[min_edge2])) {
                 min_edge2 = e;
               }

lemon/network_simplex.h

@@ -199 +199 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     SupplyType _stype;
     Value _sum_supply;
@@ -683 +683 @@
     template <typename LowerMap>
     NetworkSimplex& lowerMap(const LowerMap& map) {
-      _have_lower = true;
+      _has_lower = true;
       for (ArcIt a(_graph); a != INVALID; ++a) {
         _lower[_arc_id[a]] = map[a];
@@ -880 +880 @@
         _cost[i] = 1;
       }
-      _have_lower = false;
+      _has_lower = false;
       _stype = GEQ;
       return *this;
@@ -937 +937 @@
         _node_id[n] = i;
       }
-      if (_arc_mixing) {
+      if (_arc_mixing && _node_num > 1) {
         // Store the arcs in a mixed order
         const int skip = std::max(_arc_num / _node_num, 3);
@@ -1073 +1073 @@
 
       // Remove non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _arc_num; ++i) {
           Value c = _lower[i];
@@ -1236 +1236 @@
     }
 
-    // Check if the upper bound is greater or equal to the lower bound
+    // Check if the upper bound is greater than or equal to the lower bound
     // on each arc.
     bool checkBoundMaps() {
@@ -1613 +1613 @@
 
       // Transform the solution and the supply map to the original form
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _arc_num; ++i) {
           Value c = _lower[i];

lemon/preflow.h

@@ -477 +477 @@
     /// flow to the given \c flowMap. The \c flowMap should contain a
     /// flow or at least a preflow, i.e. at each node excluding the
-    /// source node the incoming flow should greater or equal to the
+    /// source node the incoming flow should be greater or equal to the
     /// outgoing flow.
     /// \return \c false if the given \c flowMap is not a preflow.
@@ -496 +496 @@
           excess -= (*_flow)[e];
         }
-        if (excess < 0 && n != _source) return false;
+        if (_tolerance.negative(excess) && n != _source) return false;
         (*_excess)[n] = excess;
       }
@@ -640 +640 @@
           (*_excess)[n] = excess;
 
-          if (excess != 0) {
+          if (_tolerance.nonZero(excess)) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftHighestActive(new_level + 1);
@@ -721 +721 @@
           (*_excess)[n] = excess;
 
-          if (excess != 0) {
+          if (_tolerance.nonZero(excess)) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftActiveOn(level, new_level + 1);
@@ -792 +792 @@
         if (!reached[n]) {
           _level->dirtyTopButOne(n);
-        } else if ((*_excess)[n] > 0 && _target != n) {
+        } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
           _level->activate(n);
         }
@@ -853 +853 @@
         (*_excess)[n] = excess;
 
-        if (excess != 0) {
+        if (_tolerance.nonZero(excess)) {
           if (new_level + 1 < _level->maxLevel()) {
             _level->liftHighestActive(new_level + 1);

lemon/radix_sort.h

@@ -329 +329 @@
       Allocator allocator;
 
-      int length = std::distance(first, last);
+      int length = static_cast<int>(std::distance(first, last));
       Key* buffer = allocator.allocate(2 * length);
       try {

lemon/random.h

@@ -63 +63 @@
 #define LEMON_RANDOM_H
 
+#include <lemon/config.h>
+
 #include <algorithm>
 #include <iterator>
@@ -72 +74 @@
 #include <lemon/dim2.h>
 
-#ifndef WIN32
+#ifndef LEMON_WIN32
 #include <sys/time.h>
 #include <ctime>
@@ -200 +202 @@
         initState(init);
 
-        num = length > end - begin ? length : end - begin;
+        num = static_cast<int>(length > end - begin ? length : end - begin);
         while (num--) {
           curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul1))
@@ -214 +216 @@
         }
 
-        num = length - 1; cnt = length - (curr - state) - 1;
+        num = length - 1; cnt = static_cast<int>(length - (curr - state) - 1);
         while (num--) {
           curr[0] = (curr[0] ^ ((curr[1] ^ (curr[1] >> (bits - 2))) * mul2))
@@ -606 +608 @@
     /// \return Currently always \c true.
     bool seed() {
-#ifndef WIN32
+#ifndef LEMON_WIN32
       if (seedFromFile("/dev/urandom", 0)) return true;
 #endif
@@ -626 +628 @@
     /// \param offset The offset, from the file read.
     /// \return \c true when the seeding successes.
-#ifndef WIN32
+#ifndef LEMON_WIN32
     bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
 #else
@@ -648 +650 @@
     /// \return Currently always \c true.
     bool seedFromTime() {
-#ifndef WIN32
+#ifndef LEMON_WIN32
       timeval tv;
       gettimeofday(&tv, 0);

lemon/static_graph.h

@@ -204 +204 @@
 
       node_num = n;
-      arc_num = std::distance(first, last);
+      arc_num = static_cast<int>(std::distance(first, last));
 
       node_first_out = new int[node_num + 1];

lemon/time_measure.h

@@ -24 +24 @@
 ///\brief Tools for measuring cpu usage
 
-#ifdef WIN32
+#include <lemon/config.h>
+
+#ifdef LEMON_WIN32
 #include <lemon/bits/windows.h>
 #else
@@ -103 +105 @@
     void stamp()
     {
-#ifndef WIN32
+#ifndef LEMON_WIN32
       timeval tv;
       gettimeofday(&tv, 0);

test/arc_look_up_test.cc

@@ -25 +25 @@
 using namespace lemon;
 
-const int lgfn = 4;
 const std::string lgf =
   "@nodes\n"

test/bpgraph_test.cc

@@ -79 +79 @@
     e2 = G.addEdge(bn1, rn1),
     e3 = G.addEdge(rn1, bn2);
+  ::lemon::ignore_unused_variable_warning(e2,e3);
 
   checkGraphNodeList(G, 3);
@@ -120 +121 @@
     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
+  ::lemon::ignore_unused_variable_warning(e1,e3,e4);
 
   // Check edge deletion
@@ -168 +170 @@
     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
+  ::lemon::ignore_unused_variable_warning(e1,e3,e4);
 
   G.changeRed(e2, n4);
@@ -220 +223 @@
     e1 = G.addEdge(n1, n2),
     e2 = G.addEdge(n1, n3);
+  ::lemon::ignore_unused_variable_warning(e1,e2);
 
   checkGraphNodeList(G, 3);
@@ -305 +309 @@
     e1 = g.addEdge(n1, n2),
     e2 = g.addEdge(n1, n3);
+  ::lemon::ignore_unused_variable_warning(e2);
 
   check(g.valid(n1), "Wrong validity check");

test/lp_test.cc

@@ -40 +40 @@
 #endif
 
+#ifdef LEMON_HAVE_LP
+#include <lemon/lp.h>
+#endif
 using namespace lemon;
 
@@ -417 +420 @@
   lpTest(lp_skel);
 
+#ifdef LEMON_HAVE_LP
+  {
+    Lp lp,lp2;
+    lpTest(lp);
+    aTest(lp2);
+    cloneTest<Lp>();
+  }
+#endif
+
 #ifdef LEMON_HAVE_GLPK
   {

test/max_flow_test.cc

@@ -27 +27 @@
 #include <lemon/lgf_reader.h>
 #include <lemon/elevator.h>
+#include <lemon/tolerance.h>
 
 using namespace lemon;
@@ -66 +67 @@
   "target 8\n";
 
+char test_lgf_float[] =
+  "@nodes\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "8\n"
+  "9\n"
+  "@arcs\n"
+  "      capacity\n"
+  "0 1 0.1\n"
+  "0 2 0.1\n"
+  "0 3 0.1\n"
+  "1 4 0.1\n"
+  "2 4 0.1\n"
+  "3 4 0.1\n"
+  "4 5 0.3\n"
+  "5 6 0.1\n"
+  "5 7 0.1\n"
+  "5 8 0.1\n"
+  "6 9 0.1\n"
+  "7 9 0.1\n"
+  "8 9 0.1\n"
+  "@attributes\n"
+  "source 0\n"
+  "target 9\n";
 
 // Checks the general interface of a max flow algorithm
@@ -166 +198 @@
   typedef concepts::Digraph Digraph;
   typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
-  typedef Elevator<Digraph, Digraph::Node> Elev;
-  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 
   Digraph g;
@@ -185 +215 @@
 
 template <typename T>
-T cutValue (const SmartDigraph& g,
-              const SmartDigraph::NodeMap<bool>& cut,
-              const SmartDigraph::ArcMap<T>& cap) {
-
-  T c=0;
-  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
-    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
+T cutValue(const SmartDigraph& g,
+           const SmartDigraph::NodeMap<bool>& cut,
+           const SmartDigraph::ArcMap<T>& cap) {
+
+  T c = 0;
+  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
+    if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
   }
   return c;
@@ -200 +230 @@
                const SmartDigraph::ArcMap<T>& flow,
                const SmartDigraph::ArcMap<T>& cap,
-               SmartDigraph::Node s, SmartDigraph::Node t) {
+               SmartDigraph::Node s, SmartDigraph::Node t,
+               const Tolerance<T>& tol) {
 
   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
-    if (flow[e] < 0 || flow[e] > cap[e]) return false;
+    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
   }
 
@@ -215 +246 @@
       sum -= flow[e];
     }
-    if (sum != 0) return false;
+    if (tol.nonZero(sum)) return false;
   }
   return true;
 }
 
-void initFlowTest()
+void checkInitPreflow()
 {
   DIGRAPH_TYPEDEFS(SmartDigraph);
 
   SmartDigraph g;
-  SmartDigraph::ArcMap<int> cap(g),iflow(g);
-  Node s=g.addNode(); Node t=g.addNode();
-  Node n1=g.addNode(); Node n2=g.addNode();
+  SmartDigraph::ArcMap<int> cap(g), iflow(g);
+  Node s = g.addNode(); Node t = g.addNode();
+  Node n1 = g.addNode(); Node n2 = g.addNode();
   Arc a;
-  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
-  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
-  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
-
-  Preflow<SmartDigraph> pre(g,cap,s,t);
+  a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
+  a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
+  a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
+
+  Preflow<SmartDigraph> pre(g, cap, s, t);
   pre.init(iflow);
   pre.startFirstPhase();
-  check(pre.flowValue() == 10, "The incorrect max flow value.");
+
+  check(pre.flowValue() == 10, "Incorrect max flow value.");
   check(pre.minCut(s), "Wrong min cut (Node s).");
   check(pre.minCut(n1), "Wrong min cut (Node n1).");
@@ -244 +276 @@
 
 template <typename MF, typename SF>
-void checkMaxFlowAlg() {
+void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
   typedef SmartDigraph Digraph;
   DIGRAPH_TYPEDEFS(Digraph);
@@ -253 +285 @@
   typedef BoolNodeMap CutMap;
 
+  Tolerance<Value> tol;
+
   Digraph g;
   Node s, t;
   CapMap cap(g);
-  std::istringstream input(test_lgf);
-  DigraphReader<Digraph>(g,input)
+  std::istringstream input(input_lgf);
+  DigraphReader<Digraph>(g, input)
       .arcMap("capacity", cap)
-      .node("source",s)
-      .node("target",t)
+      .node("source", s)
+      .node("target", t)
       .run();
 
@@ -266 +300 @@
   max_flow.run();
 
-  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
+  check(!tol.different(expected, max_flow.flowValue()),
+        "Incorrect max flow value.");
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
         "The flow is not feasible.");
 
@@ -273 +309 @@
   Value min_cut_value = cutValue(g, min_cut, cap);
 
-  check(max_flow.flowValue() == min_cut_value,
-        "The max flow value is not equal to the min cut value.");
+  check(!tol.different(expected, min_cut_value),
+        "Incorrect min cut value.");
 
   FlowMap flow(g);
-  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
-
-  Value flow_value = max_flow.flowValue();
-
-  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
+  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
+  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
   max_flow.init(flow);
 
@@ -290 +323 @@
   min_cut_value = cutValue(g, min_cut1, cap);
 
-  check(max_flow.flowValue() == min_cut_value &&
-        min_cut_value == 2 * flow_value,
-        "The max flow value or the min cut value is wrong.");
+  check(!tol.different(17 * expected, max_flow.flowValue()),
+        "Incorrect max flow value.");
+  check(!tol.different(17 * expected, min_cut_value),
+        "Incorrect min cut value.");
 
   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
 
-  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
         "The flow is not feasible.");
 
@@ -303 +337 @@
   min_cut_value = cutValue(g, min_cut2, cap);
 
-  check(max_flow.flowValue() == min_cut_value &&
-        min_cut_value == 2 * flow_value,
-        "The max flow value or the min cut value was not doubled");
-
+  check(!tol.different(17 * expected, max_flow.flowValue()),
+        "Incorrect max flow value.");
+  check(!tol.different(17 * expected, min_cut_value),
+        "Incorrect min cut value.");
 
   max_flow.flowMap(flow);
@@ -325 +359 @@
   CutMap min_cut3(g);
   max_flow.minCutMap(min_cut3);
-  min_cut_value=cutValue(g, min_cut3, cap);
-
-  check(max_flow.flowValue() == min_cut_value,
+  min_cut_value = cutValue(g, min_cut3, cap);
+
+  check(!tol.different(max_flow.flowValue(), min_cut_value),
         "The max flow value or the min cut value is wrong.");
 }
@@ -380 +414 @@
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
-  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
-  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
-  initFlowTest();
+  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
+
+  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
+  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
+  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
+
+  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
+  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
+
+  checkInitPreflow();
 
   // Check EdmondsKarp
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
-  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
-  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
-
-  initFlowTest();
+  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
+
+  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
+  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
+  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
+
+  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
+  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
 
   return 0;

test/min_cost_flow_test.cc

@@ -396 +396 @@
   checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
            mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
+
+  // Tests for empty graph
+  Digraph gr0;
+  MCF mcf0(gr0);
+  mcf0.run(param);
+  check(mcf0.totalCost() == 0, "Wrong total cost");  
 }
 

test/mip_test.cc

@@ -31 +31 @@
 #ifdef LEMON_HAVE_CBC
 #include <lemon/cbc.h>
+#endif
+
+#ifdef LEMON_HAVE_MIP
+#include <lemon/lp.h>
 #endif
 
@@ -129 +133 @@
 {
 
+#ifdef LEMON_HAVE_MIP
+  {
+    Mip mip1;
+    aTest(mip1);
+    cloneTest<Mip>();
+  }
+#endif
+
 #ifdef LEMON_HAVE_GLPK
   {

test/radix_sort_test.cc

@@ -16 +16 @@
  *
  */
+
+#include <lemon/core.h>
 
 #include <lemon/time_measure.h>

test/tsp_test.cc

@@ -133 +133 @@
     int esize = n <= 1 ? 0 : n;
 
-    TSP alg(g, constMap<Edge, int>(1));
+    ConstMap<Edge, int> cost_map(1);
+    TSP alg(g, cost_map);
 
     check(alg.run() == esize, alg_name + ": Wrong total cost");

tools/lgf-gen.cc

@@ -247 +247 @@
   struct BeachIt;
 
-  typedef std::multimap<double, BeachIt> SpikeHeap;
+  typedef std::multimap<double, BeachIt*> SpikeHeap;
 
   typedef std::multimap<Part, SpikeHeap::iterator, YLess> Beach;
@@ -330 +330 @@
 
       if (bit->second != spikeheap.end()) {
+        delete bit->second->second;
         spikeheap.erase(bit->second);
       }
@@ -343 +344 @@
           circle_form(points[prev], points[curr], points[site])) {
         double x = circle_point(points[prev], points[curr], points[site]);
-        pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));
-        pit->second.it =
+        pit = spikeheap.insert(std::make_pair(x, new BeachIt(beach.end())));
+        pit->second->it =
           beach.insert(std::make_pair(Part(prev, curr, site), pit));
       } else {
@@ -356 +357 @@
           circle_form(points[site], points[curr],points[next])) {
         double x = circle_point(points[site], points[curr], points[next]);
-        nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));
-        nit->second.it =
+        nit = spikeheap.insert(std::make_pair(x, new BeachIt(beach.end())));
+        nit->second->it =
           beach.insert(std::make_pair(Part(site, curr, next), nit));
       } else {
@@ -367 +368 @@
       sweep = spit->first;
 
-      Beach::iterator bit = spit->second.it;
+      Beach::iterator bit = spit->second->it;
 
       int prev = bit->first.prev;
@@ -400 +401 @@
       int nnt = nbit->first.next;
 
-      if (bit->second != spikeheap.end()) spikeheap.erase(bit->second);
-      if (pbit->second != spikeheap.end()) spikeheap.erase(pbit->second);
-      if (nbit->second != spikeheap.end()) spikeheap.erase(nbit->second);
-
+      if (bit->second != spikeheap.end())
+        {
+          delete bit->second->second;
+          spikeheap.erase(bit->second);
+        }
+      if (pbit->second != spikeheap.end())
+        {
+          delete pbit->second->second;
+          spikeheap.erase(pbit->second);
+        }
+      if (nbit->second != spikeheap.end())
+        {
+          delete nbit->second->second;
+          spikeheap.erase(nbit->second);
+        }
+      
       beach.erase(nbit);
       beach.erase(bit);
@@ -413 +426 @@
         double x = circle_point(points[ppv], points[prev], points[next]);
         if (x < sweep) x = sweep;
-        pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));
-        pit->second.it =
+        pit = spikeheap.insert(std::make_pair(x, new BeachIt(beach.end())));
+        pit->second->it =
           beach.insert(std::make_pair(Part(ppv, prev, next), pit));
       } else {
@@ -425 +438 @@
         double x = circle_point(points[prev], points[next], points[nnt]);
         if (x < sweep) x = sweep;
-        nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end())));
-        nit->second.it =
+        nit = spikeheap.insert(std::make_pair(x, new BeachIt(beach.end())));
+        nit->second->it =
           beach.insert(std::make_pair(Part(prev, next, nnt), nit));
       } else {