COIN-OR::LEMON - Graph Library

Changeset 984:9f22c22fe227 in lemon for lemon


Ignore:
Timestamp:
06/25/10 06:15:43 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Parents:
983:949510b70df9 (diff), 980: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.1

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r980 r984  
    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).
     
    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      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1246
    12341247    public:
    12351248
    1236       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1237 
    1238       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1249      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12391250
    12401251      virtual void add(const Node& node) {
     
    12591270      }
    12601271    };
    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;
    12671272
    12681273    class ArcLess {
     
    12761281    };
    12771282
     1283  protected:
     1284
     1285    const Digraph &_g;
     1286    AutoNodeMap _head;
     1287    typename Digraph::template ArcMap<Arc> _parent;
     1288    typename Digraph::template ArcMap<Arc> _left;
     1289    typename Digraph::template ArcMap<Arc> _right;
     1290
    12781291  public:
    12791292
     
    13181331    virtual void clear() {
    13191332      for(NodeIt n(_g);n!=INVALID;++n) {
    1320         _head.set(n, INVALID);
     1333        _head[n] = INVALID;
    13211334      }
    13221335    }
     
    13251338      Node s = _g.source(arc);
    13261339      Node t = _g.target(arc);
    1327       _left.set(arc, INVALID);
    1328       _right.set(arc, INVALID);
     1340      _left[arc] = INVALID;
     1341      _right[arc] = INVALID;
    13291342
    13301343      Arc e = _head[s];
    13311344      if (e == INVALID) {
    1332         _head.set(s, arc);
    1333         _parent.set(arc, INVALID);
     1345        _head[s] = arc;
     1346        _parent[arc] = INVALID;
    13341347        return;
    13351348      }
     
    13371350        if (t < _g.target(e)) {
    13381351          if (_left[e] == INVALID) {
    1339             _left.set(e, arc);
    1340             _parent.set(arc, e);
     1352            _left[e] = arc;
     1353            _parent[arc] = e;
    13411354            splay(arc);
    13421355            return;
     
    13461359        } else {
    13471360          if (_right[e] == INVALID) {
    1348             _right.set(e, arc);
    1349             _parent.set(arc, e);
     1361            _right[e] = arc;
     1362            _parent[arc] = e;
    13501363            splay(arc);
    13511364            return;
     
    13601373      if (_left[arc] == INVALID) {
    13611374        if (_right[arc] != INVALID) {
    1362           _parent.set(_right[arc], _parent[arc]);
     1375          _parent[_right[arc]] = _parent[arc];
    13631376        }
    13641377        if (_parent[arc] != INVALID) {
    13651378          if (_left[_parent[arc]] == arc) {
    1366             _left.set(_parent[arc], _right[arc]);
     1379            _left[_parent[arc]] = _right[arc];
    13671380          } else {
    1368             _right.set(_parent[arc], _right[arc]);
     1381            _right[_parent[arc]] = _right[arc];
    13691382          }
    13701383        } else {
    1371           _head.set(_g.source(arc), _right[arc]);
     1384          _head[_g.source(arc)] = _right[arc];
    13721385        }
    13731386      } else if (_right[arc] == INVALID) {
    1374         _parent.set(_left[arc], _parent[arc]);
     1387        _parent[_left[arc]] = _parent[arc];
    13751388        if (_parent[arc] != INVALID) {
    13761389          if (_left[_parent[arc]] == arc) {
    1377             _left.set(_parent[arc], _left[arc]);
     1390            _left[_parent[arc]] = _left[arc];
    13781391          } else {
    1379             _right.set(_parent[arc], _left[arc]);
     1392            _right[_parent[arc]] = _left[arc];
    13801393          }
    13811394        } else {
    1382           _head.set(_g.source(arc), _left[arc]);
     1395          _head[_g.source(arc)] = _left[arc];
    13831396        }
    13841397      } else {
     
    13901403          }
    13911404          Arc s = _parent[e];
    1392           _right.set(_parent[e], _left[e]);
     1405          _right[_parent[e]] = _left[e];
    13931406          if (_left[e] != INVALID) {
    1394             _parent.set(_left[e], _parent[e]);
     1407            _parent[_left[e]] = _parent[e];
    13951408          }
    13961409
    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]);
     1410          _left[e] = _left[arc];
     1411          _parent[_left[arc]] = e;
     1412          _right[e] = _right[arc];
     1413          _parent[_right[arc]] = e;
     1414
     1415          _parent[e] = _parent[arc];
    14031416          if (_parent[arc] != INVALID) {
    14041417            if (_left[_parent[arc]] == arc) {
    1405               _left.set(_parent[arc], e);
     1418              _left[_parent[arc]] = e;
    14061419            } else {
    1407               _right.set(_parent[arc], e);
     1420              _right[_parent[arc]] = e;
    14081421            }
    14091422          }
    14101423          splay(s);
    14111424        } else {
    1412           _right.set(e, _right[arc]);
    1413           _parent.set(_right[arc], e);
    1414           _parent.set(e, _parent[arc]);
     1425          _right[e] = _right[arc];
     1426          _parent[_right[arc]] = e;
     1427          _parent[e] = _parent[arc];
    14151428
    14161429          if (_parent[arc] != INVALID) {
    14171430            if (_left[_parent[arc]] == arc) {
    1418               _left.set(_parent[arc], e);
     1431              _left[_parent[arc]] = e;
    14191432            } else {
    1420               _right.set(_parent[arc], e);
     1433              _right[_parent[arc]] = e;
    14211434            }
    14221435          } else {
    1423             _head.set(_g.source(arc), e);
     1436            _head[_g.source(arc)] = e;
    14241437          }
    14251438        }
     
    14331446      if (a < m) {
    14341447        Arc left = refreshRec(v,a,m-1);
    1435         _left.set(me, left);
    1436         _parent.set(left, me);
     1448        _left[me] = left;
     1449        _parent[left] = me;
    14371450      } else {
    1438         _left.set(me, INVALID);
     1451        _left[me] = INVALID;
    14391452      }
    14401453      if (m < b) {
    14411454        Arc right = refreshRec(v,m+1,b);
    1442         _right.set(me, right);
    1443         _parent.set(right, me);
     1455        _right[me] = right;
     1456        _parent[right] = me;
    14441457      } else {
    1445         _right.set(me, INVALID);
     1458        _right[me] = INVALID;
    14461459      }
    14471460      return me;
     
    14551468          std::sort(v.begin(),v.end(),ArcLess(_g));
    14561469          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);
     1470          _head[n] = head;
     1471          _parent[head] = INVALID;
     1472        }
     1473        else _head[n] = INVALID;
    14611474      }
    14621475    }
     
    14641477    void zig(Arc v) {
    14651478      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);
     1479      _parent[v] = _parent[w];
     1480      _parent[w] = v;
     1481      _left[w] = _right[v];
     1482      _right[v] = w;
    14701483      if (_parent[v] != INVALID) {
    14711484        if (_right[_parent[v]] == w) {
    1472           _right.set(_parent[v], v);
     1485          _right[_parent[v]] = v;
    14731486        } else {
    1474           _left.set(_parent[v], v);
     1487          _left[_parent[v]] = v;
    14751488        }
    14761489      }
    14771490      if (_left[w] != INVALID){
    1478         _parent.set(_left[w], w);
     1491        _parent[_left[w]] = w;
    14791492      }
    14801493    }
     
    14821495    void zag(Arc v) {
    14831496      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);
     1497      _parent[v] = _parent[w];
     1498      _parent[w] = v;
     1499      _right[w] = _left[v];
     1500      _left[v] = w;
    14881501      if (_parent[v] != INVALID){
    14891502        if (_left[_parent[v]] == w) {
    1490           _left.set(_parent[v], v);
     1503          _left[_parent[v]] = v;
    14911504        } else {
    1492           _right.set(_parent[v], v);
     1505          _right[_parent[v]] = v;
    14931506        }
    14941507      }
    14951508      if (_right[w] != INVALID){
    1496         _parent.set(_right[w], w);
     1509        _parent[_right[w]] = w;
    14971510      }
    14981511    }
     
    16261639  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16271640  ///
    1628   ///\tparam G The type of the underlying digraph.
     1641  ///\tparam GR The type of the underlying digraph.
    16291642  ///
    16301643  ///\sa DynArcLookUp
    16311644  ///\sa AllArcLookUp
    1632   template<class G>
     1645  template<class GR>
    16331646  class ArcLookUp
    16341647  {
     1648    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1649
    16351650  public:
    1636     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1637     typedef G Digraph;
     1651
     1652    /// The Digraph type
     1653    typedef GR Digraph;
    16381654
    16391655  protected:
     
    17361752  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17371753  ///
    1738   ///\tparam G The type of the underlying digraph.
     1754  ///\tparam GR The type of the underlying digraph.
    17391755  ///
    17401756  ///\sa DynArcLookUp
    17411757  ///\sa ArcLookUp
    1742   template<class G>
    1743   class AllArcLookUp : public ArcLookUp<G>
     1758  template<class GR>
     1759  class AllArcLookUp : public ArcLookUp<GR>
    17441760  {
    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;
     1761    using ArcLookUp<GR>::_g;
     1762    using ArcLookUp<GR>::_right;
     1763    using ArcLookUp<GR>::_left;
     1764    using ArcLookUp<GR>::_head;
     1765
     1766    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1767
     1768    typename GR::template ArcMap<Arc> _next;
    17541769
    17551770    Arc refreshNext(Arc head,Arc next=INVALID)
     
    17701785
    17711786  public:
     1787
     1788    /// The Digraph type
     1789    typedef GR Digraph;
     1790
    17721791    ///Constructor
    17731792
     
    17761795    ///It builds up the search database, which remains valid until the digraph
    17771796    ///changes.
    1778     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1797    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17791798
    17801799    ///Refresh the data structure at a node.
     
    17861805    void refresh(Node n)
    17871806    {
    1788       ArcLookUp<G>::refresh(n);
     1807      ArcLookUp<GR>::refresh(n);
    17891808      refreshNext(_head[n]);
    17901809    }
     
    18331852    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18341853#else
    1835     using ArcLookUp<G>::operator() ;
     1854    using ArcLookUp<GR>::operator() ;
    18361855    Arc operator()(Node s, Node t, Arc prev) const
    18371856    {
  • lemon/core.h

    r718 r984  
    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();
Note: See TracChangeset for help on using the changeset viewer.