Changes in / [1063:0dba9b96550a:1064:40bbb450143e] in lemon

Files:

• .hgtags (added)
• CMakeLists.txt (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) (3 diffs)
• lemon/bits/graph_adaptor_extender.h (modified) (1 diff)
• lemon/bits/graph_extender.h (modified) (3 diffs)
• lemon/bits/path_dump.h (modified) (2 diffs)
• lemon/bits/windows.cc (modified) (1 diff)
• lemon/core.h (modified) (2 diffs)
• lemon/dfs.h (modified) (2 diffs)
• lemon/graph_to_eps.h (modified) (1 diff)
• lemon/maps.h (modified) (8 diffs)
• lemon/suurballe.h (modified) (1 diff)
• test/dfs_test.cc (modified) (4 diffs)
• test/graph_copy_test.cc (modified) (8 diffs)
• test/maps_test.cc (modified) (2 diffs)

CMakeLists.txt

@@ -52 +52 @@
 ELSE()
   IF(CMAKE_COMPILER_IS_GNUCXX)
-    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
+    SET(CXX_WARNING "-Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas")
     SET(CMAKE_CXX_FLAGS_DEBUG CACHE STRING "-ggdb")
     SET(CMAKE_C_FLAGS_DEBUG CACHE STRING "-ggdb")

NEWS

@@ +1 @@
+2010-10-21 Version 1.1.3 released
+
+        Bugfix release.
+
+        #366: Fix Pred[Matrix]MapPath::empty()
+        #371: Bug fix in (di)graphCopy()
+              The target graph is cleared before adding nodes and arcs/edges.
+
+        #356: Fix multiple execution bug in weighted matchings
+        #364: Add missing UndirectedTags
+        #368: Fix the usage of std::numeric_limits<>::min() in Network Simplex
+        #372: Fix a critical bug in preflow
+
+2010-03-08 Version 1.1.2 released
+
+        Bugfix release.
+
+        #317: Fix (and improve) error message in mip_test.cc
+              Remove unnecessary OsiCbc dependency
+        #250: Fix in pathSource() and pathTarget()
+        #322: Distribute LEMONConfig.cmake.in
+        #321: Use pathCopy(from,to) instead of copyPath(to,from)
+        #330: Bug fix in map_extender.h
+        #335: Fix clear() function in ExtendFindEnum
+        #337: Use void* as LPX object pointer
+        #336: Fix the date field comment of graphToEps() output
+        #323: Bug fix in Suurballe
+
+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

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

lemon/bits/edge_set_extender.h

@@ -281 +281 @@
     typedef EdgeSetExtender Graph;
 
+    typedef True UndirectedTag;
+
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;
@@ -538 +540 @@
 
     public:
-      ArcMap(const Graph& _g) 
+      explicit ArcMap(const Graph& _g) 
         : Parent(_g) {}
       ArcMap(const Graph& _g, const _Value& _v) 
@@ -562 +564 @@
 
     public:
-      EdgeMap(const Graph& _g) 
+      explicit EdgeMap(const Graph& _g) 
         : Parent(_g) {}
 

lemon/bits/graph_adaptor_extender.h

@@ -182 +182 @@
     typedef GraphAdaptorExtender Adaptor;
 
+    typedef True UndirectedTag;
+
     typedef typename Parent::Node Node;
     typedef typename Parent::Arc Arc;

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/path_dump.h

@@ -50 +50 @@
 
     bool empty() const {
-      return predMap[target] != INVALID;
+      return predMap[target] == INVALID;
     }
 
@@ -124 +124 @@
 
     bool empty() const {
-      return source != target;
+      return predMatrixMap(source, target) == INVALID;
     }
 

lemon/bits/windows.cc

@@ -41 +41 @@
 #include <unistd.h>
 #include <ctime>
+#ifndef WIN32
 #include <sys/times.h>
+#endif
 #include <sys/time.h>
 #endif

lemon/core.h

@@ -395 +395 @@
       static void copy(const From& from, Digraph &to,
                        NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
+        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();
@@ -422 +423 @@
       static void copy(const From& from, Graph &to,
                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
+        to.clear();
         for (typename From::NodeIt it(from); it != INVALID; ++it) {
           nodeRefMap[it] = to.addNode();

lemon/dfs.h

@@ -558 +558 @@
     void start(Node t)
     {
-      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }
@@ -1510 +1510 @@
     /// with addSource() before using this function.
     void start(Node t) {
-      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
+      while ( !emptyQueue() && !(*_reached)[t] )
         processNextArc();
     }

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/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

test/dfs_test.cc

@@ -51 +51 @@
   "@attributes\n"
   "source 0\n"
-  "target 5\n";
+  "target 5\n"
+  "source1 6\n"
+  "target1 3\n";
+
 
 void checkDfsCompile()
@@ -180 +183 @@
   Digraph G;
   Node s, t;
+  Node s1, t1;
 
   std::istringstream input(test_lgf);
@@ -185 +189 @@
     node("source", s).
     node("target", t).
+    node("source1", s1).
+    node("target1", t1).
     run();
 
@@ -211 +217 @@
 
   {
+  Dfs<Digraph> dfs(G);
+  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
+  }
+  
+  {
     NullMap<Node,Arc> myPredMap;
     dfs(G).predMap(myPredMap).run(s);

test/graph_copy_test.cc

@@ -30 +30 @@
   const int nn = 10;
 
+  // Build a digraph
   SmartDigraph from;
   SmartDigraph::NodeMap<int> fnm(from);
@@ -52 +53 @@
   }
 
+  // Test digraph copy
   ListDigraph to;
   ListDigraph::NodeMap<int> tnm(to);
@@ -69 +71 @@
     nodeCrossRef(ncr).arcCrossRef(ecr).
     node(fn, tn).arc(fa, ta).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
@@ -91 +96 @@
   check(tn == nr[fn], "Wrong copy.");
   check(ta == er[fa], "Wrong copy.");
+
+  // Test repeated copy
+  digraphCopy(from, to).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 
@@ -96 +107 @@
   const int nn = 10;
 
+  // Build a graph
   SmartGraph from;
   SmartGraph::NodeMap<int> fnm(from);
@@ -123 +135 @@
   }
 
+  // Test graph copy
   ListGraph to;
   ListGraph::NodeMap<int> tnm(to);
@@ -144 +157 @@
     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
     node(fn, tn).arc(fa, ta).edge(fe, te).run();
+
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countEdges(from) == countEdges(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 
   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
@@ -181 +198 @@
   check(ta == ar[fa], "Wrong copy.");
   check(te == er[fe], "Wrong copy.");
+
+  // Test repeated copy
+  graphCopy(from, to).run();
+  
+  check(countNodes(from) == countNodes(to), "Wrong copy.");
+  check(countEdges(from) == countEdges(to), "Wrong copy.");
+  check(countArcs(from) == countArcs(to), "Wrong copy.");
 }
 

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;