Changes in / [912:37f440367057:913:2f9d9bcc1867] in lemon

Files:

• .hgtags (added)
• Makefile.am (modified) (1 diff)
• NEWS (modified) (1 diff)
• doc/groups.dox (modified) (9 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/bits/edge_set_extender.h (modified) (2 diffs)
• lemon/bits/graph_extender.h (modified) (3 diffs)
• lemon/bits/map_extender.h (modified) (6 diffs)
• lemon/circulation.h (modified) (2 diffs)
• lemon/glpk.h (modified) (3 diffs)
• lemon/graph_to_eps.h (modified) (1 diff)
• lemon/maps.h (modified) (8 diffs)
• lemon/path.h (modified) (11 diffs)
• lemon/preflow.h (modified) (2 diffs)
• lemon/suurballe.h (modified) (1 diff)
• lemon/unionfind.h (modified) (1 diff)
• m4/lx_check_coin.m4 (modified) (1 diff)
• test/maps_test.cc (modified) (2 diffs)
• test/mip_test.cc (modified) (1 diff)

Makefile.am

@@ -18 +18 @@
         cmake/FindGLPK.cmake \
         cmake/FindCOIN.cmake \
+        cmake/LEMONConfig.cmake.in \
         cmake/version.cmake.in \
         cmake/version.cmake \

NEWS

@@ +1 @@
+2009-10-03 Version 1.1.1 released
+
+        Bugfix release.
+
+        #295: Suppress MSVC warnings using pragmas
+        ----: Various CMAKE related improvements
+              * Remove duplications from doc/CMakeLists.txt
+              * Rename documentation install folder from 'docs' to 'html'
+              * Add tools/CMakeLists.txt to the tarball
+              * Generate and install LEMONConfig.cmake
+              * Change the label of the html project in Visual Studio
+              * Fix the check for the 'long long' type
+              * Put the version string into config.h
+              * Minor CMake improvements
+              * Set the version to 'hg-tip' if everything fails
+        #311: Add missing 'explicit' keywords
+        #302: Fix the implementation and doc of CrossRefMap
+        #308: Remove duplicate list_graph.h entry from source list
+        #307: Bug fix in Preflow and Circulation
+
 2009-05-13 Version 1.1 released
 

doc/groups.dox

@@ -227 +227 @@
 
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup paths Path Structures
 @ingroup datas
@@ -284 +276 @@
 This group contains the algorithms for finding shortest paths in digraphs.
 
- - \ref Dijkstra algorithm for finding shortest paths from a source node
-   when all arc lengths are non-negative.
- - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
-   from a source node when arc lenghts can be either positive or negative,
-   but the digraph should not contain directed cycles with negative total
-   length.
- - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
-   for solving the \e all-pairs \e shortest \e paths \e problem when arc
-   lenghts can be either positive or negative, but the digraph should
-   not contain directed cycles with negative total length.
+ - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 
+   source node when all arc lengths are non-negative.
  - \ref Suurballe A successive shortest path algorithm for finding
    arc-disjoint paths between two nodes having minimum total length.
@@ -318 +302 @@
 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 
-LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
-
-In most cases the \ref Preflow "Preflow" algorithm provides the
-fastest method for computing a maximum flow. All implementations
-also provide functions to query the minimum cut, which is the dual
-problem of maximum flow.
+\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
+Tarjan for solving this problem. It also provides functions to query the
+minimum cut, which is the dual problem of maximum flow.
+
 
 \ref Circulation is a preflow push-relabel algorithm implemented directly 
@@ -345 +323 @@
 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 
-LEMON contains several algorithms for this problem.
- - \ref NetworkSimplex Primal Network Simplex algorithm with various
-   pivot strategies.
- - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-   cost scaling.
- - \ref CapacityScaling Successive Shortest %Path algorithm with optional
-   capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
-
-In general NetworkSimplex is the most efficient implementation,
-but in special cases other algorithms could be faster.
-For example, if the total supply and/or capacities are rather small,
-CapacityScaling is usually the fastest algorithm (without effective scaling).
+\ref NetworkSimplex is an efficient implementation of the primal Network
+Simplex algorithm for finding minimum cost flows. It also provides dual
+solution (node potentials), if an optimal flow is found.
 */
 
@@ -382 +349 @@
 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   in directed graphs.
-- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
-  calculating minimum cut in undirected graphs.
 - \ref GomoryHu "Gomory-Hu tree computation" for calculating
   all-pairs minimum cut in undirected graphs.
@@ -404 +369 @@
 
 /**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
-*/
-
-/**
 @defgroup matching Matching Algorithms
 @ingroup algs
 \brief Algorithms for finding matchings in graphs and bipartite graphs.
 
-This group contains the algorithms for calculating
-matchings in graphs and bipartite graphs. The general matching problem is
-finding a subset of the edges for which each node has at most one incident
-edge.
+This group contains the algorithms for calculating matchings in graphs.
+The general matching problem is finding a subset of the edges for which
+each node has at most one incident edge.
 
 There are several different algorithms for calculate matchings in
-graphs.  The matching problems in bipartite graphs are generally
-easier than in general graphs. The goal of the matching optimization
+graphs. The goal of the matching optimization
 can be finding maximum cardinality, maximum weight or minimum cost
 matching. The search can be constrained to find perfect or
@@ -433 +384 @@
 
 The matching algorithms implemented in LEMON:
-- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref PrBipartiteMatching Push-relabel algorithm
-  for calculating maximum cardinality matching in bipartite graphs.
-- \ref MaxWeightedBipartiteMatching
-  Successive shortest path algorithm for calculating maximum weighted
-  matching and maximum weighted bipartite matching in bipartite graphs.
-- \ref MinCostMaxBipartiteMatching
-  Successive shortest path algorithm for calculating minimum cost maximum
-  matching in bipartite graphs.
 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   maximum cardinality matching in general graphs.
@@ -474 +415 @@
 
 /**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
-*/
-
-/**
 @defgroup gen_opt_group General Optimization Tools
 \brief This group contains some general optimization frameworks
@@ -499 +431 @@
 various LP solvers could be used in the same manner with this
 interface.
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip Solvers
-@ingroup lp_group
-\brief Helper tools to the Lp and Mip solvers.
-
-This group adds some helper tools to general optimization framework
-implemented in LEMON.
-*/
-
-/**
-@defgroup metah Metaheuristics
-@ingroup gen_opt_group
-\brief Metaheuristics for LEMON library.
-
-This group contains some metaheuristic optimization tools.
 */
 

lemon/Makefile.am

@@ -91 +91 @@
         lemon/lp_base.h \
         lemon/lp_skeleton.h \
-        lemon/list_graph.h \
         lemon/maps.h \
         lemon/matching.h \

lemon/bits/edge_set_extender.h

@@ -538 +538 @@
 
     public:
-      ArcMap(const Graph& _g) 
+      explicit ArcMap(const Graph& _g) 
         : Parent(_g) {}
       ArcMap(const Graph& _g, const _Value& _v) 
@@ -562 +562 @@
 
     public:
-      EdgeMap(const Graph& _g) 
+      explicit EdgeMap(const Graph& _g) 
         : Parent(_g) {}
 

lemon/bits/graph_extender.h

@@ -605 +605 @@
 
     public:
-      NodeMap(const Graph& graph)
+      explicit NodeMap(const Graph& graph)
         : Parent(graph) {}
       NodeMap(const Graph& graph, const _Value& value)
@@ -629 +629 @@
 
     public:
-      ArcMap(const Graph& graph)
+      explicit ArcMap(const Graph& graph)
         : Parent(graph) {}
       ArcMap(const Graph& graph, const _Value& value)
@@ -653 +653 @@
 
     public:
-      EdgeMap(const Graph& graph)
+      explicit EdgeMap(const Graph& graph)
         : Parent(graph) {}
 

lemon/bits/map_extender.h

@@ -83 +83 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
+        : Parent(item), map(&_map) {}
+
+      MapIt& operator++() {
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+      typename MapTraits<Map>::ConstReturnValue operator*() const {
+        return (*map)[*this];
+      }
+
+      typename MapTraits<Map>::ReturnValue operator*() {
+        return (*map)[*this];
+      }
+
+      void set(const Value& value) {
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
+
+    };
+
+    class ConstMapIt : public Item {
+      typedef Item Parent;
+
+    public:
+
+      typedef typename Map::Value Value;
+
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
+      }
+
+      ConstMapIt(const Map& _map, const Item& item)
         : Parent(item), map(_map) {}
 
-      MapIt& operator++() {
-        map.notifier()->next(*this);
+      ConstMapIt& operator++() {
+        map->notifier()->next(*this);
         return *this;
       }
@@ -103 +143 @@
       }
 
-      typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
-      }
-
-      void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
-
-    };
-
-    class ConstMapIt : public Item {
-      typedef Item Parent;
-
-    public:
-
-      typedef typename Map::Value Value;
-
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
-      }
-
-      ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
-
-      ConstMapIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-      typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+    protected:
+      const Map* map;
     };
 
@@ -151 +151 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.notifier()->first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) {}
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->notifier()->first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.notifier()->next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->notifier()->next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };
@@ -228 +228 @@
       typedef typename Map::Value Value;
 
-      MapIt() {}
-
-      MapIt(Invalid i) : Parent(i) { }
-
-      explicit MapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      MapIt() : map(NULL) {}
+
+      MapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit MapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       MapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       MapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
+        return (*map)[*this];
       }
 
       typename MapTraits<Map>::ReturnValue operator*() {
-        return map[*this];
+        return (*map)[*this];
       }
 
       void set(const Value& value) {
-        map.set(*this, value);
-      }
-
-    protected:
-      Map& map;
+        map->set(*this, value);
+      }
+
+    protected:
+      Map* map;
 
     };
@@ -268 +268 @@
       typedef typename Map::Value Value;
 
-      ConstMapIt() {}
-
-      ConstMapIt(Invalid i) : Parent(i) { }
-
-      explicit ConstMapIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ConstMapIt() : map(NULL) {}
+
+      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ConstMapIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ConstMapIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ConstMapIt& operator++() {
-        map.graph.next(*this);
+        map->graph.next(*this);
         return *this;
       }
 
       typename MapTraits<Map>::ConstReturnValue operator*() const {
-        return map[*this];
-      }
-
-    protected:
-      const Map& map;
+        return (*map)[*this];
+      }
+
+    protected:
+      const Map* map;
     };
 
@@ -296 +296 @@
 
     public:
-
-      ItemIt() {}
-
-      ItemIt(Invalid i) : Parent(i) { }
-
-      explicit ItemIt(Map& _map) : map(_map) {
-        map.graph.first(*this);
+      ItemIt() : map(NULL) {}
+
+
+      ItemIt(Invalid i) : Parent(i), map(NULL) { }
+
+      explicit ItemIt(Map& _map) : map(&_map) {
+        map->graph.first(*this);
       }
 
       ItemIt(const Map& _map, const Item& item)
-        : Parent(item), map(_map) {}
+        : Parent(item), map(&_map) {}
 
       ItemIt& operator++() {
-        map.graph.next(*this);
-        return *this;
-      }
-
-    protected:
-      const Map& map;
+        map->graph.next(*this);
+        return *this;
+      }
+
+    protected:
+      const Map* map;
 
     };

lemon/circulation.h

@@ -454 +454 @@
     ///
     /// Sets the tolerance used by algorithm.
-    Circulation& tolerance(const Tolerance& tolerance) const {
+    Circulation& tolerance(const Tolerance& tolerance) {
       _tol = tolerance;
       return *this;
@@ -463 +463 @@
     /// Returns a const reference to the tolerance.
     const Tolerance& tolerance() const {
-      return tolerance;
+      return _tol;
     }
 

lemon/glpk.h

@@ -26 +26 @@
 #include <lemon/lp_base.h>
 
-// forward declaration
-#if !defined _GLP_PROB && !defined GLP_PROB
-#define _GLP_PROB
-#define GLP_PROB
-typedef struct { double _opaque_prob; } glp_prob;
-/* LP/MIP problem object */
-#endif
-
 namespace lemon {
 
+  namespace _solver_bits {
+    class VoidPtr {
+    private:
+      void *_ptr;      
+    public:
+      VoidPtr() : _ptr(0) {}
+
+      template <typename T>
+      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
+
+      template <typename T>
+      VoidPtr& operator=(T* ptr) { 
+        _ptr = reinterpret_cast<void*>(ptr); 
+        return *this;
+      }
+
+      template <typename T>
+      operator T*() const { return reinterpret_cast<T*>(_ptr); }
+    };
+  }
 
   /// \brief Base interface for the GLPK LP and MIP solver
@@ -44 +56 @@
   protected:
 
-    typedef glp_prob LPX;
-    glp_prob* lp;
+    _solver_bits::VoidPtr lp;
 
     GlpkBase();
@@ -123 +134 @@
 
     ///Pointer to the underlying GLPK data structure.
-    LPX *lpx() {return lp;}
+    _solver_bits::VoidPtr lpx() {return lp;}
     ///Const pointer to the underlying GLPK data structure.
-    const LPX *lpx() const {return lp;}
+    _solver_bits::VoidPtr lpx() const {return lp;}
 
     ///Returns the constraint identifier understood by GLPK.

lemon/graph_to_eps.h

@@ -685 +685 @@
 #else
       os << bits::getWinFormattedDate();
+      os << std::endl;
 #endif
     }
-    os << std::endl;
 
     if (_autoArcWidthScale) {

lemon/maps.h

@@ -1903 +1903 @@
 
   /// This class provides simple invertable graph maps.
-  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
-  /// and if a key is set to a new value then store it
-  /// in the inverse map.
-  ///
+  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
+  /// and if a key is set to a new value, then stores it in the inverse map.
   /// The values of the map can be accessed
   /// with stl compatible forward iterator.
+  ///
+  /// This type is not reference map, so it cannot be modified with
+  /// the subscript operator.
   ///
   /// \tparam GR The graph type.
@@ -1924 +1925 @@
       template Map<V>::Type Map;
 
-    typedef std::map<V, K> Container;
+    typedef std::multimap<V, K> Container;
     Container _inv_map;
 
@@ -1949 +1950 @@
     /// iterator on the values of the map. The values can
     /// be accessed in the <tt>[beginValue, endValue)</tt> range.
+    /// They are considered with multiplicity, so each value is
+    /// traversed for each item it is assigned to.
     class ValueIterator
       : public std::iterator<std::forward_iterator_tag, Value> {
@@ -2001 +2004 @@
     void set(const Key& key, const Value& val) {
       Value oldval = Map::operator[](key);
-      typename Container::iterator it = _inv_map.find(oldval);
-      if (it != _inv_map.end() && it->second == key) {
-        _inv_map.erase(it);
+      typename Container::iterator it;
+      for (it = _inv_map.equal_range(oldval).first;
+           it != _inv_map.equal_range(oldval).second; ++it) {
+        if (it->second == key) {
+          _inv_map.erase(it);
+          break;
+        }
       }
-      _inv_map.insert(make_pair(val, key));
+      _inv_map.insert(std::make_pair(val, key));
       Map::set(key, val);
     }
@@ -2017 +2024 @@
     }
 
-    /// \brief Gives back the item by its value.
-    ///
-    /// Gives back the item by its value.
-    Key operator()(const Value& key) const {
-      typename Container::const_iterator it = _inv_map.find(key);
+    /// \brief Gives back an item by its value.
+    ///
+    /// This function gives back an item that is assigned to
+    /// the given value or \c INVALID if no such item exists.
+    /// If there are more items with the same associated value,
+    /// only one of them is returned.
+    Key operator()(const Value& val) const {
+      typename Container::const_iterator it = _inv_map.find(val);
       return it != _inv_map.end() ? it->second : INVALID;
     }
@@ -2033 +2043 @@
     virtual void erase(const Key& key) {
       Value val = Map::operator[](key);
-      typename Container::iterator it = _inv_map.find(val);
-      if (it != _inv_map.end() && it->second == key) {
-        _inv_map.erase(it);
+      typename Container::iterator it;
+      for (it = _inv_map.equal_range(val).first;
+           it != _inv_map.equal_range(val).second; ++it) {
+        if (it->second == key) {
+          _inv_map.erase(it);
+          break;
+        }
       }
       Map::erase(key);
@@ -2047 +2061 @@
       for (int i = 0; i < int(keys.size()); ++i) {
         Value val = Map::operator[](keys[i]);
-        typename Container::iterator it = _inv_map.find(val);
-        if (it != _inv_map.end() && it->second == keys[i]) {
-          _inv_map.erase(it);
+        typename Container::iterator it;
+        for (it = _inv_map.equal_range(val).first;
+             it != _inv_map.equal_range(val).second; ++it) {
+          if (it->second == keys[i]) {
+            _inv_map.erase(it);
+            break;
+          }
         }
       }
@@ -2085 +2103 @@
       /// \brief Subscript operator.
       ///
-      /// Subscript operator. It gives back the item
-      /// that was last assigned to the given value.
+      /// Subscript operator. It gives back an item
+      /// that is assigned to the given value or \c INVALID
+      /// if no such item exists.
       Value operator[](const Key& key) const {
         return _inverted(key);

lemon/path.h

@@ -71 +71 @@
     template <typename CPath>
     Path(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -79 +79 @@
     template <typename CPath>
     Path& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -259 +259 @@
     template <typename CPath>
     SimplePath(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -268 +268 @@
     template <typename CPath>
     SimplePath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -438 +438 @@
     template <typename CPath>
     ListPath(const CPath& cpath) : first(0), last(0) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -454 +454 @@
     template <typename CPath>
     ListPath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -764 +764 @@
     template <typename CPath>
     StaticPath(const CPath& cpath) : arcs(0) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
     }
 
@@ -780 +780 @@
     template <typename CPath>
     StaticPath& operator=(const CPath& cpath) {
-      copyPath(*this, cpath);
+      pathCopy(cpath, *this);
       return *this;
     }
@@ -929 +929 @@
     };
 
-    template <typename Target, typename Source,
-              bool buildEnable = BuildTagIndicator<Target>::value>
+    template <typename From, typename To,
+              bool buildEnable = BuildTagIndicator<To>::value>
     struct PathCopySelectorForward {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        for (typename Source::ArcIt it(source); it != INVALID; ++it) {
-          target.addBack(it);
+      static void copy(const From& from, To& to) {
+        to.clear();
+        for (typename From::ArcIt it(from); it != INVALID; ++it) {
+          to.addBack(it);
         }
       }
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelectorForward<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        target.build(source);
-      }
-    };
-
-    template <typename Target, typename Source,
-              bool buildEnable = BuildTagIndicator<Target>::value>
+    template <typename From, typename To>
+    struct PathCopySelectorForward<From, To, true> {
+      static void copy(const From& from, To& to) {
+        to.clear();
+        to.build(from);
+      }
+    };
+
+    template <typename From, typename To,
+              bool buildEnable = BuildTagIndicator<To>::value>
     struct PathCopySelectorBackward {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
-          target.addFront(it);
+      static void copy(const From& from, To& to) {
+        to.clear();
+        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
+          to.addFront(it);
         }
       }
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelectorBackward<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        target.clear();
-        target.buildRev(source);
+    template <typename From, typename To>
+    struct PathCopySelectorBackward<From, To, true> {
+      static void copy(const From& from, To& to) {
+        to.clear();
+        to.buildRev(from);
       }
     };
 
     
-    template <typename Target, typename Source,
-              bool revEnable = RevPathTagIndicator<Source>::value>
+    template <typename From, typename To,
+              bool revEnable = RevPathTagIndicator<From>::value>
     struct PathCopySelector {
-      static void copy(Target& target, const Source& source) {
-        PathCopySelectorForward<Target, Source>::copy(target, source);
+      static void copy(const From& from, To& to) {
+        PathCopySelectorForward<From, To>::copy(from, to);
       }      
     };
 
-    template <typename Target, typename Source>
-    struct PathCopySelector<Target, Source, true> {
-      static void copy(Target& target, const Source& source) {
-        PathCopySelectorBackward<Target, Source>::copy(target, source);
+    template <typename From, typename To>
+    struct PathCopySelector<From, To, true> {
+      static void copy(const From& from, To& to) {
+        PathCopySelectorBackward<From, To>::copy(from, to);
       }      
     };
@@ -988 +988 @@
   /// \brief Make a copy of a path.
   ///
-  ///  This function makes a copy of a path.
-  template <typename Target, typename Source>
-  void copyPath(Target& target, const Source& source) {
-    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
-    _path_bits::PathCopySelector<Target, Source>::copy(target, source);
+  /// This function makes a copy of a path.
+  template <typename From, typename To>
+  void pathCopy(const From& from, To& to) {
+    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
+    _path_bits::PathCopySelector<From, To>::copy(from, to);
+  }
+
+  /// \brief Deprecated version of \ref pathCopy().
+  ///
+  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
+  template <typename To, typename From>
+  void copyPath(To& to, const From& from) {
+    pathCopy(from, to);
   }
 
@@ -1016 +1024 @@
   /// \brief The source of a path
   ///
-  /// This function returns the source of the given path.
+  /// This function returns the source node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
-    return digraph.source(path.front());
+    return path.empty() ? INVALID : digraph.source(path.front());
   }
 
   /// \brief The target of a path
   ///
-  /// This function returns the target of the given path.
+  /// This function returns the target node of the given path.
+  /// If the path is empty, then it returns \c INVALID.
   template <typename Digraph, typename Path>
   typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
-    return digraph.target(path.back());
+    return path.empty() ? INVALID : digraph.target(path.back());
   }
 

lemon/preflow.h

@@ -375 +375 @@
     ///
     /// Sets the tolerance used by algorithm.
-    Preflow& tolerance(const Tolerance& tolerance) const {
+    Preflow& tolerance(const Tolerance& tolerance) {
       _tolerance = tolerance;
       return *this;
@@ -384 +384 @@
     /// Returns a const reference to the tolerance.
     const Tolerance& tolerance() const {
-      return tolerance;
+      return _tolerance;
     }
 

lemon/suurballe.h

@@ -46 +46 @@
   /// Note that this problem is a special case of the \ref min_cost_flow
   /// "minimum cost flow problem". This implementation is actually an
-  /// efficient specialized version of the \ref CapacityScaling
-  /// "Successive Shortest Path" algorithm directly for this problem.
+  /// efficient specialized version of the Successive Shortest Path
+  /// algorithm directly for this problem.
   /// Therefore this class provides query functions for flow values and
   /// node potentials (the dual solution) just like the minimum cost flow

lemon/unionfind.h

@@ -740 +740 @@
     void clear() {
       items.clear();
-      classes.clear;
+      classes.clear();
       firstClass = firstFreeClass = firstFreeItem = -1;
     }

m4/lx_check_coin.m4

@@ -89 +89 @@
         CBC_LDFLAGS="-L$with_coin/lib"
       fi
-      CBC_LIBS="-lOsi -lCbc -lOsiCbc -lCbcSolver -lClp -lOsiClp -lCoinUtils -lVol -lOsiVol -lCgl -lm -llapack -lblas"
+      CBC_LIBS="-lOsi -lCbc -lCbcSolver -lClp -lOsiClp -lCoinUtils -lVol -lOsiVol -lCgl -lm -llapack -lblas"
 
       lx_save_cxxflags="$CXXFLAGS"

test/maps_test.cc

@@ -23 +23 @@
 #include <lemon/concepts/maps.h>
 #include <lemon/maps.h>
+#include <lemon/list_graph.h>
 
 #include "test_tools.h"
@@ -349 +350 @@
       check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
   }
+  
+  // CrossRefMap
+  {
+    typedef ListDigraph Graph;
+    DIGRAPH_TYPEDEFS(Graph);
+
+    checkConcept<ReadWriteMap<Node, int>,
+                 CrossRefMap<Graph, Node, int> >();
+    
+    Graph gr;
+    typedef CrossRefMap<Graph, Node, char> CRMap;
+    typedef CRMap::ValueIterator ValueIt;
+    CRMap map(gr);
+    
+    Node n0 = gr.addNode();
+    Node n1 = gr.addNode();
+    Node n2 = gr.addNode();
+    
+    map.set(n0, 'A');
+    map.set(n1, 'B');
+    map.set(n2, 'C');
+    map.set(n2, 'A');
+    map.set(n0, 'C');
+
+    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
+          "Wrong CrossRefMap");
+    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
+    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
+    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
+
+    ValueIt it = map.beginValue();
+    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
+          it == map.endValue(), "Wrong value iterator");
+  }
 
   return 0;

test/mip_test.cc

@@ -51 +51 @@
   if (stat ==  MipSolver::OPTIMAL) {
     std::ostringstream sbuf;
-    buf << "Wrong optimal value: the right optimum is " << exp_opt;
+    sbuf << "Wrong optimal value ("<< mip.solValue()
+         <<" instead of " << exp_opt << ")";
     check(std::abs(mip.solValue()-exp_opt) < 1e-3, sbuf.str());
     //+ecvt(exp_opt,2)