Changeset 893:d395358592df in lemon-main

Timestamp:

06/25/10 06:41:55 (14 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

892:a22b3f1bf83e (diff), 890:bb871cb8ac06 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge bugfix #371

Files:

• lemon/core.h (modified) (30 diffs)
• lemon/core.h (modified) (2 diffs)
• test/graph_copy_test.cc (modified) (1 diff)
• test/graph_copy_test.cc (modified) (8 diffs)

lemon/core.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -27 +27 @@
 #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
 
 ///\file
@@ -437 +447 @@
 
   }
+
+  /// Check whether a graph is undirected.
+  ///
+  /// This function returns \c true if the given graph is undirected.
+#ifdef DOXYGEN
+  template <typename GR>
+  bool undirected(const GR& g) { return false; }
+#else
+  template <typename GR>
+  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
+  undirected(const GR&) {
+    return true;
+  }
+  template <typename GR>
+  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
+  undirected(const GR&) {
+    return false;
+  }
+#endif
 
   /// \brief Class to copy a digraph.
@@ -1037 +1066 @@
   ///\sa findArc()
   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
-  template <typename _Graph>
-  class ConArcIt : public _Graph::Arc {
+  template <typename GR>
+  class ConArcIt : public GR::Arc {
+    typedef typename GR::Arc Parent;
+
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Arc Parent;
-
-    typedef typename Graph::Arc Arc;
-    typedef typename Graph::Node Node;
+    typedef typename GR::Arc Arc;
+    typedef typename GR::Node Node;
 
     /// \brief Constructor.
@@ -1051 +1079 @@
     /// Construct a new ConArcIt iterating on the arcs that
     /// connects nodes \c u and \c v.
-    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
+    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
       Parent::operator=(findArc(_graph, u, v));
     }
@@ -1058 +1086 @@
     ///
     /// Construct a new ConArcIt that continues the iterating from arc \c a.
-    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
+    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
 
     /// \brief Increment operator.
@@ -1069 +1097 @@
     }
   private:
-    const Graph& _graph;
+    const GR& _graph;
   };
 
@@ -1160 +1188 @@
   ///
   ///\sa findEdge()
-  template <typename _Graph>
-  class ConEdgeIt : public _Graph::Edge {
+  template <typename GR>
+  class ConEdgeIt : public GR::Edge {
+    typedef typename GR::Edge Parent;
+
   public:
 
-    typedef _Graph Graph;
-    typedef typename Graph::Edge Parent;
-
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::Node Node;
+    typedef typename GR::Edge Edge;
+    typedef typename GR::Node Node;
 
     /// \brief Constructor.
@@ -1174 +1201 @@
     /// Construct a new ConEdgeIt iterating on the edges that
     /// connects nodes \c u and \c v.
-    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
+    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
       Parent::operator=(findEdge(_graph, _u, _v));
     }
@@ -1181 +1208 @@
     ///
     /// Construct a new ConEdgeIt that continues iterating from edge \c e.
-    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
+    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
 
     /// \brief Increment operator.
@@ -1191 +1218 @@
     }
   private:
-    const Graph& _graph;
+    const GR& _graph;
     Node _u, _v;
   };
@@ -1214 +1241 @@
   ///queries.
   ///
-  ///\tparam G The type of the underlying digraph.
+  ///\tparam GR The type of the underlying digraph.
   ///
   ///\sa ArcLookUp
   ///\sa AllArcLookUp
-  template<class G>
+  template <typename GR>
   class DynArcLookUp
-    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
+    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
   {
+    typedef typename ItemSetTraits<GR, typename GR::Arc>
+    ::ItemNotifier::ObserverBase Parent;
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
   public:
-    typedef typename ItemSetTraits<G, typename G::Arc>
-    ::ItemNotifier::ObserverBase Parent;
-
-    TEMPLATE_DIGRAPH_TYPEDEFS(G);
-    typedef G Digraph;
+
+    /// The Digraph type
+    typedef GR Digraph;
 
   protected:
 
-    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
+    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
+    {
+      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
+
     public:
 
-      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
-
-      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
+      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
 
       virtual void add(const Node& node) {
@@ -1259 +1290 @@
       }
     };
-
-    const Digraph &_g;
-    AutoNodeMap _head;
-    typename Digraph::template ArcMap<Arc> _parent;
-    typename Digraph::template ArcMap<Arc> _left;
-    typename Digraph::template ArcMap<Arc> _right;
 
     class ArcLess {
@@ -1276 +1301 @@
     };
 
+  protected:
+
+    const Digraph &_g;
+    AutoNodeMap _head;
+    typename Digraph::template ArcMap<Arc> _parent;
+    typename Digraph::template ArcMap<Arc> _left;
+    typename Digraph::template ArcMap<Arc> _right;
+
   public:
 
@@ -1318 +1351 @@
     virtual void clear() {
       for(NodeIt n(_g);n!=INVALID;++n) {
-        _head.set(n, INVALID);
+        _head[n] = INVALID;
       }
     }
@@ -1325 +1358 @@
       Node s = _g.source(arc);
       Node t = _g.target(arc);
-      _left.set(arc, INVALID);
-      _right.set(arc, INVALID);
+      _left[arc] = INVALID;
+      _right[arc] = INVALID;
 
       Arc e = _head[s];
       if (e == INVALID) {
-        _head.set(s, arc);
-        _parent.set(arc, INVALID);
+        _head[s] = arc;
+        _parent[arc] = INVALID;
         return;
       }
@@ -1337 +1370 @@
         if (t < _g.target(e)) {
           if (_left[e] == INVALID) {
-            _left.set(e, arc);
-            _parent.set(arc, e);
+            _left[e] = arc;
+            _parent[arc] = e;
             splay(arc);
             return;
@@ -1346 +1379 @@
         } else {
           if (_right[e] == INVALID) {
-            _right.set(e, arc);
-            _parent.set(arc, e);
+            _right[e] = arc;
+            _parent[arc] = e;
             splay(arc);
             return;
@@ -1360 +1393 @@
       if (_left[arc] == INVALID) {
         if (_right[arc] != INVALID) {
-          _parent.set(_right[arc], _parent[arc]);
+          _parent[_right[arc]] = _parent[arc];
         }
         if (_parent[arc] != INVALID) {
           if (_left[_parent[arc]] == arc) {
-            _left.set(_parent[arc], _right[arc]);
+            _left[_parent[arc]] = _right[arc];
           } else {
-            _right.set(_parent[arc], _right[arc]);
+            _right[_parent[arc]] = _right[arc];
           }
         } else {
-          _head.set(_g.source(arc), _right[arc]);
+          _head[_g.source(arc)] = _right[arc];
         }
       } else if (_right[arc] == INVALID) {
-        _parent.set(_left[arc], _parent[arc]);
+        _parent[_left[arc]] = _parent[arc];
         if (_parent[arc] != INVALID) {
           if (_left[_parent[arc]] == arc) {
-            _left.set(_parent[arc], _left[arc]);
+            _left[_parent[arc]] = _left[arc];
           } else {
-            _right.set(_parent[arc], _left[arc]);
+            _right[_parent[arc]] = _left[arc];
           }
         } else {
-          _head.set(_g.source(arc), _left[arc]);
+          _head[_g.source(arc)] = _left[arc];
         }
       } else {
@@ -1390 +1423 @@
           }
           Arc s = _parent[e];
-          _right.set(_parent[e], _left[e]);
+          _right[_parent[e]] = _left[e];
           if (_left[e] != INVALID) {
-            _parent.set(_left[e], _parent[e]);
+            _parent[_left[e]] = _parent[e];
           }
 
-          _left.set(e, _left[arc]);
-          _parent.set(_left[arc], e);
-          _right.set(e, _right[arc]);
-          _parent.set(_right[arc], e);
-
-          _parent.set(e, _parent[arc]);
+          _left[e] = _left[arc];
+          _parent[_left[arc]] = e;
+          _right[e] = _right[arc];
+          _parent[_right[arc]] = e;
+
+          _parent[e] = _parent[arc];
           if (_parent[arc] != INVALID) {
             if (_left[_parent[arc]] == arc) {
-              _left.set(_parent[arc], e);
+              _left[_parent[arc]] = e;
             } else {
-              _right.set(_parent[arc], e);
+              _right[_parent[arc]] = e;
             }
           }
           splay(s);
         } else {
-          _right.set(e, _right[arc]);
-          _parent.set(_right[arc], e);
-          _parent.set(e, _parent[arc]);
+          _right[e] = _right[arc];
+          _parent[_right[arc]] = e;
+          _parent[e] = _parent[arc];
 
           if (_parent[arc] != INVALID) {
             if (_left[_parent[arc]] == arc) {
-              _left.set(_parent[arc], e);
+              _left[_parent[arc]] = e;
             } else {
-              _right.set(_parent[arc], e);
+              _right[_parent[arc]] = e;
             }
           } else {
-            _head.set(_g.source(arc), e);
+            _head[_g.source(arc)] = e;
           }
         }
@@ -1433 +1466 @@
       if (a < m) {
         Arc left = refreshRec(v,a,m-1);
-        _left.set(me, left);
-        _parent.set(left, me);
+        _left[me] = left;
+        _parent[left] = me;
       } else {
-        _left.set(me, INVALID);
+        _left[me] = INVALID;
       }
       if (m < b) {
         Arc right = refreshRec(v,m+1,b);
-        _right.set(me, right);
-        _parent.set(right, me);
+        _right[me] = right;
+        _parent[right] = me;
       } else {
-        _right.set(me, INVALID);
+        _right[me] = INVALID;
       }
       return me;
@@ -1455 +1488 @@
           std::sort(v.begin(),v.end(),ArcLess(_g));
           Arc head = refreshRec(v,0,v.size()-1);
-          _head.set(n, head);
-          _parent.set(head, INVALID);
-        }
-        else _head.set(n, INVALID);
+          _head[n] = head;
+          _parent[head] = INVALID;
+        }
+        else _head[n] = INVALID;
       }
     }
@@ -1464 +1497 @@
     void zig(Arc v) {
       Arc w = _parent[v];
-      _parent.set(v, _parent[w]);
-      _parent.set(w, v);
-      _left.set(w, _right[v]);
-      _right.set(v, w);
+      _parent[v] = _parent[w];
+      _parent[w] = v;
+      _left[w] = _right[v];
+      _right[v] = w;
       if (_parent[v] != INVALID) {
         if (_right[_parent[v]] == w) {
-          _right.set(_parent[v], v);
+          _right[_parent[v]] = v;
         } else {
-          _left.set(_parent[v], v);
+          _left[_parent[v]] = v;
         }
       }
       if (_left[w] != INVALID){
-        _parent.set(_left[w], w);
+        _parent[_left[w]] = w;
       }
     }
@@ -1482 +1515 @@
     void zag(Arc v) {
       Arc w = _parent[v];
-      _parent.set(v, _parent[w]);
-      _parent.set(w, v);
-      _right.set(w, _left[v]);
-      _left.set(v, w);
+      _parent[v] = _parent[w];
+      _parent[w] = v;
+      _right[w] = _left[v];
+      _left[v] = w;
       if (_parent[v] != INVALID){
         if (_left[_parent[v]] == w) {
-          _left.set(_parent[v], v);
+          _left[_parent[v]] = v;
         } else {
-          _right.set(_parent[v], v);
+          _right[_parent[v]] = v;
         }
       }
       if (_right[w] != INVALID){
-        _parent.set(_right[w], w);
+        _parent[_right[w]] = w;
       }
     }
@@ -1626 +1659 @@
   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
   ///
-  ///\tparam G The type of the underlying digraph.
+  ///\tparam GR The type of the underlying digraph.
   ///
   ///\sa DynArcLookUp
   ///\sa AllArcLookUp
-  template<class G>
+  template<class GR>
   class ArcLookUp
   {
+    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
   public:
-    TEMPLATE_DIGRAPH_TYPEDEFS(G);
-    typedef G Digraph;
+
+    /// The Digraph type
+    typedef GR Digraph;
 
   protected:
@@ -1736 +1772 @@
   ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
   ///
-  ///\tparam G The type of the underlying digraph.
+  ///\tparam GR The type of the underlying digraph.
   ///
   ///\sa DynArcLookUp
   ///\sa ArcLookUp
-  template<class G>
-  class AllArcLookUp : public ArcLookUp<G>
+  template<class GR>
+  class AllArcLookUp : public ArcLookUp<GR>
   {
-    using ArcLookUp<G>::_g;
-    using ArcLookUp<G>::_right;
-    using ArcLookUp<G>::_left;
-    using ArcLookUp<G>::_head;
-
-    TEMPLATE_DIGRAPH_TYPEDEFS(G);
-    typedef G Digraph;
-
-    typename Digraph::template ArcMap<Arc> _next;
+    using ArcLookUp<GR>::_g;
+    using ArcLookUp<GR>::_right;
+    using ArcLookUp<GR>::_left;
+    using ArcLookUp<GR>::_head;
+
+    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
+
+    typename GR::template ArcMap<Arc> _next;
 
     Arc refreshNext(Arc head,Arc next=INVALID)
@@ -1770 +1805 @@
 
   public:
+
+    /// The Digraph type
+    typedef GR Digraph;
+
     ///Constructor
 
@@ -1776 +1815 @@
     ///It builds up the search database, which remains valid until the digraph
     ///changes.
-    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
+    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
 
     ///Refresh the data structure at a node.
@@ -1786 +1825 @@
     void refresh(Node n)
     {
-      ArcLookUp<G>::refresh(n);
+      ArcLookUp<GR>::refresh(n);
       refreshNext(_head[n]);
     }
@@ -1833 +1872 @@
     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
 #else
-    using ArcLookUp<G>::operator() ;
+    using ArcLookUp<GR>::operator() ;
     Arc operator()(Node s, Node t, Arc prev) const
     {

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();

test/graph_copy_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).

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.");
 }