COIN-OR::LEMON - Graph Library

Changeset 896:e958855b8186 in lemon-1.2


Ignore:
Timestamp:
06/25/10 06:20:28 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
895:f63fd24c0aea (diff), 893: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 to branch 1.2

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r893 r896  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2727#include <lemon/bits/traits.h>
    2828#include <lemon/assert.h>
     29
     30// Disable the following warnings when compiling with MSVC:
     31// C4250: 'class1' : inherits 'class2::member' via dominance
     32// C4355: 'this' : used in base member initializer list
     33// C4503: 'function' : decorated name length exceeded, name was truncated
     34// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     35// C4996: 'function': was declared deprecated
     36#ifdef _MSC_VER
     37#pragma warning( disable : 4250 4355 4503 4800 4996 )
     38#endif
    2939
    3040///\file
     
    10371047  ///\sa findArc()
    10381048  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1039   template <typename _Graph>
    1040   class ConArcIt : public _Graph::Arc {
     1049  template <typename GR>
     1050  class ConArcIt : public GR::Arc {
     1051    typedef typename GR::Arc Parent;
     1052
    10411053  public:
    10421054
    1043     typedef _Graph Graph;
    1044     typedef typename Graph::Arc Parent;
    1045 
    1046     typedef typename Graph::Arc Arc;
    1047     typedef typename Graph::Node Node;
     1055    typedef typename GR::Arc Arc;
     1056    typedef typename GR::Node Node;
    10481057
    10491058    /// \brief Constructor.
     
    10511060    /// Construct a new ConArcIt iterating on the arcs that
    10521061    /// connects nodes \c u and \c v.
    1053     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     1062    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
    10541063      Parent::operator=(findArc(_graph, u, v));
    10551064    }
     
    10581067    ///
    10591068    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1060     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     1069    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
    10611070
    10621071    /// \brief Increment operator.
     
    10691078    }
    10701079  private:
    1071     const Graph& _graph;
     1080    const GR& _graph;
    10721081  };
    10731082
     
    11601169  ///
    11611170  ///\sa findEdge()
    1162   template <typename _Graph>
    1163   class ConEdgeIt : public _Graph::Edge {
     1171  template <typename GR>
     1172  class ConEdgeIt : public GR::Edge {
     1173    typedef typename GR::Edge Parent;
     1174
    11641175  public:
    11651176
    1166     typedef _Graph Graph;
    1167     typedef typename Graph::Edge Parent;
    1168 
    1169     typedef typename Graph::Edge Edge;
    1170     typedef typename Graph::Node Node;
     1177    typedef typename GR::Edge Edge;
     1178    typedef typename GR::Node Node;
    11711179
    11721180    /// \brief Constructor.
     
    11741182    /// Construct a new ConEdgeIt iterating on the edges that
    11751183    /// connects nodes \c u and \c v.
    1176     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1184    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11771185      Parent::operator=(findEdge(_graph, _u, _v));
    11781186    }
     
    11811189    ///
    11821190    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1183     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     1191    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
    11841192
    11851193    /// \brief Increment operator.
     
    11911199    }
    11921200  private:
    1193     const Graph& _graph;
     1201    const GR& _graph;
    11941202    Node _u, _v;
    11951203  };
     
    12141222  ///queries.
    12151223  ///
    1216   ///\tparam G The type of the underlying digraph.
     1224  ///\tparam GR The type of the underlying digraph.
    12171225  ///
    12181226  ///\sa ArcLookUp
    12191227  ///\sa AllArcLookUp
    1220   template<class G>
     1228  template <typename GR>
    12211229  class DynArcLookUp
    1222     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1230    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12231231  {
     1232    typedef typename ItemSetTraits<GR, typename GR::Arc>
     1233    ::ItemNotifier::ObserverBase Parent;
     1234
     1235    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1236
    12241237  public:
    1225     typedef typename ItemSetTraits<G, typename G::Arc>
    1226     ::ItemNotifier::ObserverBase Parent;
    1227 
    1228     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1229     typedef G Digraph;
     1238
     1239    /// The Digraph type
     1240    typedef GR Digraph;
    12301241
    12311242  protected:
    12321243
    1233     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1244    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1245    {
     1246      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1247
    12341248    public:
    12351249
    1236       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1237 
    1238       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1250      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12391251
    12401252      virtual void add(const Node& node) {
     
    12591271      }
    12601272    };
    1261 
    1262     const Digraph &_g;
    1263     AutoNodeMap _head;
    1264     typename Digraph::template ArcMap<Arc> _parent;
    1265     typename Digraph::template ArcMap<Arc> _left;
    1266     typename Digraph::template ArcMap<Arc> _right;
    12671273
    12681274    class ArcLess {
     
    12761282    };
    12771283
     1284  protected:
     1285
     1286    const Digraph &_g;
     1287    AutoNodeMap _head;
     1288    typename Digraph::template ArcMap<Arc> _parent;
     1289    typename Digraph::template ArcMap<Arc> _left;
     1290    typename Digraph::template ArcMap<Arc> _right;
     1291
    12781292  public:
    12791293
     
    13181332    virtual void clear() {
    13191333      for(NodeIt n(_g);n!=INVALID;++n) {
    1320         _head.set(n, INVALID);
     1334        _head[n] = INVALID;
    13211335      }
    13221336    }
     
    13251339      Node s = _g.source(arc);
    13261340      Node t = _g.target(arc);
    1327       _left.set(arc, INVALID);
    1328       _right.set(arc, INVALID);
     1341      _left[arc] = INVALID;
     1342      _right[arc] = INVALID;
    13291343
    13301344      Arc e = _head[s];
    13311345      if (e == INVALID) {
    1332         _head.set(s, arc);
    1333         _parent.set(arc, INVALID);
     1346        _head[s] = arc;
     1347        _parent[arc] = INVALID;
    13341348        return;
    13351349      }
     
    13371351        if (t < _g.target(e)) {
    13381352          if (_left[e] == INVALID) {
    1339             _left.set(e, arc);
    1340             _parent.set(arc, e);
     1353            _left[e] = arc;
     1354            _parent[arc] = e;
    13411355            splay(arc);
    13421356            return;
     
    13461360        } else {
    13471361          if (_right[e] == INVALID) {
    1348             _right.set(e, arc);
    1349             _parent.set(arc, e);
     1362            _right[e] = arc;
     1363            _parent[arc] = e;
    13501364            splay(arc);
    13511365            return;
     
    13601374      if (_left[arc] == INVALID) {
    13611375        if (_right[arc] != INVALID) {
    1362           _parent.set(_right[arc], _parent[arc]);
     1376          _parent[_right[arc]] = _parent[arc];
    13631377        }
    13641378        if (_parent[arc] != INVALID) {
    13651379          if (_left[_parent[arc]] == arc) {
    1366             _left.set(_parent[arc], _right[arc]);
     1380            _left[_parent[arc]] = _right[arc];
    13671381          } else {
    1368             _right.set(_parent[arc], _right[arc]);
     1382            _right[_parent[arc]] = _right[arc];
    13691383          }
    13701384        } else {
    1371           _head.set(_g.source(arc), _right[arc]);
     1385          _head[_g.source(arc)] = _right[arc];
    13721386        }
    13731387      } else if (_right[arc] == INVALID) {
    1374         _parent.set(_left[arc], _parent[arc]);
     1388        _parent[_left[arc]] = _parent[arc];
    13751389        if (_parent[arc] != INVALID) {
    13761390          if (_left[_parent[arc]] == arc) {
    1377             _left.set(_parent[arc], _left[arc]);
     1391            _left[_parent[arc]] = _left[arc];
    13781392          } else {
    1379             _right.set(_parent[arc], _left[arc]);
     1393            _right[_parent[arc]] = _left[arc];
    13801394          }
    13811395        } else {
    1382           _head.set(_g.source(arc), _left[arc]);
     1396          _head[_g.source(arc)] = _left[arc];
    13831397        }
    13841398      } else {
     
    13901404          }
    13911405          Arc s = _parent[e];
    1392           _right.set(_parent[e], _left[e]);
     1406          _right[_parent[e]] = _left[e];
    13931407          if (_left[e] != INVALID) {
    1394             _parent.set(_left[e], _parent[e]);
     1408            _parent[_left[e]] = _parent[e];
    13951409          }
    13961410
    1397           _left.set(e, _left[arc]);
    1398           _parent.set(_left[arc], e);
    1399           _right.set(e, _right[arc]);
    1400           _parent.set(_right[arc], e);
    1401 
    1402           _parent.set(e, _parent[arc]);
     1411          _left[e] = _left[arc];
     1412          _parent[_left[arc]] = e;
     1413          _right[e] = _right[arc];
     1414          _parent[_right[arc]] = e;
     1415
     1416          _parent[e] = _parent[arc];
    14031417          if (_parent[arc] != INVALID) {
    14041418            if (_left[_parent[arc]] == arc) {
    1405               _left.set(_parent[arc], e);
     1419              _left[_parent[arc]] = e;
    14061420            } else {
    1407               _right.set(_parent[arc], e);
     1421              _right[_parent[arc]] = e;
    14081422            }
    14091423          }
    14101424          splay(s);
    14111425        } else {
    1412           _right.set(e, _right[arc]);
    1413           _parent.set(_right[arc], e);
    1414           _parent.set(e, _parent[arc]);
     1426          _right[e] = _right[arc];
     1427          _parent[_right[arc]] = e;
     1428          _parent[e] = _parent[arc];
    14151429
    14161430          if (_parent[arc] != INVALID) {
    14171431            if (_left[_parent[arc]] == arc) {
    1418               _left.set(_parent[arc], e);
     1432              _left[_parent[arc]] = e;
    14191433            } else {
    1420               _right.set(_parent[arc], e);
     1434              _right[_parent[arc]] = e;
    14211435            }
    14221436          } else {
    1423             _head.set(_g.source(arc), e);
     1437            _head[_g.source(arc)] = e;
    14241438          }
    14251439        }
     
    14331447      if (a < m) {
    14341448        Arc left = refreshRec(v,a,m-1);
    1435         _left.set(me, left);
    1436         _parent.set(left, me);
     1449        _left[me] = left;
     1450        _parent[left] = me;
    14371451      } else {
    1438         _left.set(me, INVALID);
     1452        _left[me] = INVALID;
    14391453      }
    14401454      if (m < b) {
    14411455        Arc right = refreshRec(v,m+1,b);
    1442         _right.set(me, right);
    1443         _parent.set(right, me);
     1456        _right[me] = right;
     1457        _parent[right] = me;
    14441458      } else {
    1445         _right.set(me, INVALID);
     1459        _right[me] = INVALID;
    14461460      }
    14471461      return me;
     
    14551469          std::sort(v.begin(),v.end(),ArcLess(_g));
    14561470          Arc head = refreshRec(v,0,v.size()-1);
    1457           _head.set(n, head);
    1458           _parent.set(head, INVALID);
    1459         }
    1460         else _head.set(n, INVALID);
     1471          _head[n] = head;
     1472          _parent[head] = INVALID;
     1473        }
     1474        else _head[n] = INVALID;
    14611475      }
    14621476    }
     
    14641478    void zig(Arc v) {
    14651479      Arc w = _parent[v];
    1466       _parent.set(v, _parent[w]);
    1467       _parent.set(w, v);
    1468       _left.set(w, _right[v]);
    1469       _right.set(v, w);
     1480      _parent[v] = _parent[w];
     1481      _parent[w] = v;
     1482      _left[w] = _right[v];
     1483      _right[v] = w;
    14701484      if (_parent[v] != INVALID) {
    14711485        if (_right[_parent[v]] == w) {
    1472           _right.set(_parent[v], v);
     1486          _right[_parent[v]] = v;
    14731487        } else {
    1474           _left.set(_parent[v], v);
     1488          _left[_parent[v]] = v;
    14751489        }
    14761490      }
    14771491      if (_left[w] != INVALID){
    1478         _parent.set(_left[w], w);
     1492        _parent[_left[w]] = w;
    14791493      }
    14801494    }
     
    14821496    void zag(Arc v) {
    14831497      Arc w = _parent[v];
    1484       _parent.set(v, _parent[w]);
    1485       _parent.set(w, v);
    1486       _right.set(w, _left[v]);
    1487       _left.set(v, w);
     1498      _parent[v] = _parent[w];
     1499      _parent[w] = v;
     1500      _right[w] = _left[v];
     1501      _left[v] = w;
    14881502      if (_parent[v] != INVALID){
    14891503        if (_left[_parent[v]] == w) {
    1490           _left.set(_parent[v], v);
     1504          _left[_parent[v]] = v;
    14911505        } else {
    1492           _right.set(_parent[v], v);
     1506          _right[_parent[v]] = v;
    14931507        }
    14941508      }
    14951509      if (_right[w] != INVALID){
    1496         _parent.set(_right[w], w);
     1510        _parent[_right[w]] = w;
    14971511      }
    14981512    }
     
    16261640  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16271641  ///
    1628   ///\tparam G The type of the underlying digraph.
     1642  ///\tparam GR The type of the underlying digraph.
    16291643  ///
    16301644  ///\sa DynArcLookUp
    16311645  ///\sa AllArcLookUp
    1632   template<class G>
     1646  template<class GR>
    16331647  class ArcLookUp
    16341648  {
     1649    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1650
    16351651  public:
    1636     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1637     typedef G Digraph;
     1652
     1653    /// The Digraph type
     1654    typedef GR Digraph;
    16381655
    16391656  protected:
     
    17361753  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17371754  ///
    1738   ///\tparam G The type of the underlying digraph.
     1755  ///\tparam GR The type of the underlying digraph.
    17391756  ///
    17401757  ///\sa DynArcLookUp
    17411758  ///\sa ArcLookUp
    1742   template<class G>
    1743   class AllArcLookUp : public ArcLookUp<G>
     1759  template<class GR>
     1760  class AllArcLookUp : public ArcLookUp<GR>
    17441761  {
    1745     using ArcLookUp<G>::_g;
    1746     using ArcLookUp<G>::_right;
    1747     using ArcLookUp<G>::_left;
    1748     using ArcLookUp<G>::_head;
    1749 
    1750     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1751     typedef G Digraph;
    1752 
    1753     typename Digraph::template ArcMap<Arc> _next;
     1762    using ArcLookUp<GR>::_g;
     1763    using ArcLookUp<GR>::_right;
     1764    using ArcLookUp<GR>::_left;
     1765    using ArcLookUp<GR>::_head;
     1766
     1767    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1768
     1769    typename GR::template ArcMap<Arc> _next;
    17541770
    17551771    Arc refreshNext(Arc head,Arc next=INVALID)
     
    17701786
    17711787  public:
     1788
     1789    /// The Digraph type
     1790    typedef GR Digraph;
     1791
    17721792    ///Constructor
    17731793
     
    17761796    ///It builds up the search database, which remains valid until the digraph
    17771797    ///changes.
    1778     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1798    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17791799
    17801800    ///Refresh the data structure at a node.
     
    17861806    void refresh(Node n)
    17871807    {
    1788       ArcLookUp<G>::refresh(n);
     1808      ArcLookUp<GR>::refresh(n);
    17891809      refreshNext(_head[n]);
    17901810    }
     
    18331853    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18341854#else
    1835     using ArcLookUp<G>::operator() ;
     1855    using ArcLookUp<GR>::operator() ;
    18361856    Arc operator()(Node s, Node t, Arc prev) const
    18371857    {
  • lemon/core.h

    r877 r896  
    395395      static void copy(const From& from, Digraph &to,
    396396                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
     397        to.clear();
    397398        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    398399          nodeRefMap[it] = to.addNode();
     
    422423      static void copy(const From& from, Graph &to,
    423424                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     425        to.clear();
    424426        for (typename From::NodeIt it(from); it != INVALID; ++it) {
    425427          nodeRefMap[it] = to.addNode();
  • test/graph_copy_test.cc

    r893 r896  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/graph_copy_test.cc

    r440 r896  
    3030  const int nn = 10;
    3131
     32  // Build a digraph
    3233  SmartDigraph from;
    3334  SmartDigraph::NodeMap<int> fnm(from);
     
    5253  }
    5354
     55  // Test digraph copy
    5456  ListDigraph to;
    5557  ListDigraph::NodeMap<int> tnm(to);
     
    6971    nodeCrossRef(ncr).arcCrossRef(ecr).
    7072    node(fn, tn).arc(fa, ta).run();
     73 
     74  check(countNodes(from) == countNodes(to), "Wrong copy.");
     75  check(countArcs(from) == countArcs(to), "Wrong copy.");
    7176
    7277  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
     
    9196  check(tn == nr[fn], "Wrong copy.");
    9297  check(ta == er[fa], "Wrong copy.");
     98
     99  // Test repeated copy
     100  digraphCopy(from, to).run();
     101 
     102  check(countNodes(from) == countNodes(to), "Wrong copy.");
     103  check(countArcs(from) == countArcs(to), "Wrong copy.");
    93104}
    94105
     
    96107  const int nn = 10;
    97108
     109  // Build a graph
    98110  SmartGraph from;
    99111  SmartGraph::NodeMap<int> fnm(from);
     
    123135  }
    124136
     137  // Test graph copy
    125138  ListGraph to;
    126139  ListGraph::NodeMap<int> tnm(to);
     
    144157    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
    145158    node(fn, tn).arc(fa, ta).edge(fe, te).run();
     159
     160  check(countNodes(from) == countNodes(to), "Wrong copy.");
     161  check(countEdges(from) == countEdges(to), "Wrong copy.");
     162  check(countArcs(from) == countArcs(to), "Wrong copy.");
    146163
    147164  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
     
    181198  check(ta == ar[fa], "Wrong copy.");
    182199  check(te == er[fe], "Wrong copy.");
     200
     201  // Test repeated copy
     202  graphCopy(from, to).run();
     203 
     204  check(countNodes(from) == countNodes(to), "Wrong copy.");
     205  check(countEdges(from) == countEdges(to), "Wrong copy.");
     206  check(countArcs(from) == countArcs(to), "Wrong copy.");
    183207}
    184208
Note: See TracChangeset for help on using the changeset viewer.