COIN-OR::LEMON - Graph Library

Changeset 893:d395358592df in lemon-main


Ignore:
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:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r890 r893  
    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
     
    437447
    438448  }
     449
     450  /// Check whether a graph is undirected.
     451  ///
     452  /// This function returns \c true if the given graph is undirected.
     453#ifdef DOXYGEN
     454  template <typename GR>
     455  bool undirected(const GR& g) { return false; }
     456#else
     457  template <typename GR>
     458  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
     459  undirected(const GR&) {
     460    return true;
     461  }
     462  template <typename GR>
     463  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
     464  undirected(const GR&) {
     465    return false;
     466  }
     467#endif
    439468
    440469  /// \brief Class to copy a digraph.
     
    10371066  ///\sa findArc()
    10381067  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1039   template <typename _Graph>
    1040   class ConArcIt : public _Graph::Arc {
     1068  template <typename GR>
     1069  class ConArcIt : public GR::Arc {
     1070    typedef typename GR::Arc Parent;
     1071
    10411072  public:
    10421073
    1043     typedef _Graph Graph;
    1044     typedef typename Graph::Arc Parent;
    1045 
    1046     typedef typename Graph::Arc Arc;
    1047     typedef typename Graph::Node Node;
     1074    typedef typename GR::Arc Arc;
     1075    typedef typename GR::Node Node;
    10481076
    10491077    /// \brief Constructor.
     
    10511079    /// Construct a new ConArcIt iterating on the arcs that
    10521080    /// connects nodes \c u and \c v.
    1053     ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
     1081    ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
    10541082      Parent::operator=(findArc(_graph, u, v));
    10551083    }
     
    10581086    ///
    10591087    /// Construct a new ConArcIt that continues the iterating from arc \c a.
    1060     ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
     1088    ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
    10611089
    10621090    /// \brief Increment operator.
     
    10691097    }
    10701098  private:
    1071     const Graph& _graph;
     1099    const GR& _graph;
    10721100  };
    10731101
     
    11601188  ///
    11611189  ///\sa findEdge()
    1162   template <typename _Graph>
    1163   class ConEdgeIt : public _Graph::Edge {
     1190  template <typename GR>
     1191  class ConEdgeIt : public GR::Edge {
     1192    typedef typename GR::Edge Parent;
     1193
    11641194  public:
    11651195
    1166     typedef _Graph Graph;
    1167     typedef typename Graph::Edge Parent;
    1168 
    1169     typedef typename Graph::Edge Edge;
    1170     typedef typename Graph::Node Node;
     1196    typedef typename GR::Edge Edge;
     1197    typedef typename GR::Node Node;
    11711198
    11721199    /// \brief Constructor.
     
    11741201    /// Construct a new ConEdgeIt iterating on the edges that
    11751202    /// connects nodes \c u and \c v.
    1176     ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
     1203    ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
    11771204      Parent::operator=(findEdge(_graph, _u, _v));
    11781205    }
     
    11811208    ///
    11821209    /// Construct a new ConEdgeIt that continues iterating from edge \c e.
    1183     ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
     1210    ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
    11841211
    11851212    /// \brief Increment operator.
     
    11911218    }
    11921219  private:
    1193     const Graph& _graph;
     1220    const GR& _graph;
    11941221    Node _u, _v;
    11951222  };
     
    12141241  ///queries.
    12151242  ///
    1216   ///\tparam G The type of the underlying digraph.
     1243  ///\tparam GR The type of the underlying digraph.
    12171244  ///
    12181245  ///\sa ArcLookUp
    12191246  ///\sa AllArcLookUp
    1220   template<class G>
     1247  template <typename GR>
    12211248  class DynArcLookUp
    1222     : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
     1249    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
    12231250  {
     1251    typedef typename ItemSetTraits<GR, typename GR::Arc>
     1252    ::ItemNotifier::ObserverBase Parent;
     1253
     1254    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1255
    12241256  public:
    1225     typedef typename ItemSetTraits<G, typename G::Arc>
    1226     ::ItemNotifier::ObserverBase Parent;
    1227 
    1228     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1229     typedef G Digraph;
     1257
     1258    /// The Digraph type
     1259    typedef GR Digraph;
    12301260
    12311261  protected:
    12321262
    1233     class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
     1263    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1264    {
     1265      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
     1266
    12341267    public:
    12351268
    1236       typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
    1237 
    1238       AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
     1269      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
    12391270
    12401271      virtual void add(const Node& node) {
     
    12591290      }
    12601291    };
    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;
    12671292
    12681293    class ArcLess {
     
    12761301    };
    12771302
     1303  protected:
     1304
     1305    const Digraph &_g;
     1306    AutoNodeMap _head;
     1307    typename Digraph::template ArcMap<Arc> _parent;
     1308    typename Digraph::template ArcMap<Arc> _left;
     1309    typename Digraph::template ArcMap<Arc> _right;
     1310
    12781311  public:
    12791312
     
    13181351    virtual void clear() {
    13191352      for(NodeIt n(_g);n!=INVALID;++n) {
    1320         _head.set(n, INVALID);
     1353        _head[n] = INVALID;
    13211354      }
    13221355    }
     
    13251358      Node s = _g.source(arc);
    13261359      Node t = _g.target(arc);
    1327       _left.set(arc, INVALID);
    1328       _right.set(arc, INVALID);
     1360      _left[arc] = INVALID;
     1361      _right[arc] = INVALID;
    13291362
    13301363      Arc e = _head[s];
    13311364      if (e == INVALID) {
    1332         _head.set(s, arc);
    1333         _parent.set(arc, INVALID);
     1365        _head[s] = arc;
     1366        _parent[arc] = INVALID;
    13341367        return;
    13351368      }
     
    13371370        if (t < _g.target(e)) {
    13381371          if (_left[e] == INVALID) {
    1339             _left.set(e, arc);
    1340             _parent.set(arc, e);
     1372            _left[e] = arc;
     1373            _parent[arc] = e;
    13411374            splay(arc);
    13421375            return;
     
    13461379        } else {
    13471380          if (_right[e] == INVALID) {
    1348             _right.set(e, arc);
    1349             _parent.set(arc, e);
     1381            _right[e] = arc;
     1382            _parent[arc] = e;
    13501383            splay(arc);
    13511384            return;
     
    13601393      if (_left[arc] == INVALID) {
    13611394        if (_right[arc] != INVALID) {
    1362           _parent.set(_right[arc], _parent[arc]);
     1395          _parent[_right[arc]] = _parent[arc];
    13631396        }
    13641397        if (_parent[arc] != INVALID) {
    13651398          if (_left[_parent[arc]] == arc) {
    1366             _left.set(_parent[arc], _right[arc]);
     1399            _left[_parent[arc]] = _right[arc];
    13671400          } else {
    1368             _right.set(_parent[arc], _right[arc]);
     1401            _right[_parent[arc]] = _right[arc];
    13691402          }
    13701403        } else {
    1371           _head.set(_g.source(arc), _right[arc]);
     1404          _head[_g.source(arc)] = _right[arc];
    13721405        }
    13731406      } else if (_right[arc] == INVALID) {
    1374         _parent.set(_left[arc], _parent[arc]);
     1407        _parent[_left[arc]] = _parent[arc];
    13751408        if (_parent[arc] != INVALID) {
    13761409          if (_left[_parent[arc]] == arc) {
    1377             _left.set(_parent[arc], _left[arc]);
     1410            _left[_parent[arc]] = _left[arc];
    13781411          } else {
    1379             _right.set(_parent[arc], _left[arc]);
     1412            _right[_parent[arc]] = _left[arc];
    13801413          }
    13811414        } else {
    1382           _head.set(_g.source(arc), _left[arc]);
     1415          _head[_g.source(arc)] = _left[arc];
    13831416        }
    13841417      } else {
     
    13901423          }
    13911424          Arc s = _parent[e];
    1392           _right.set(_parent[e], _left[e]);
     1425          _right[_parent[e]] = _left[e];
    13931426          if (_left[e] != INVALID) {
    1394             _parent.set(_left[e], _parent[e]);
     1427            _parent[_left[e]] = _parent[e];
    13951428          }
    13961429
    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]);
     1430          _left[e] = _left[arc];
     1431          _parent[_left[arc]] = e;
     1432          _right[e] = _right[arc];
     1433          _parent[_right[arc]] = e;
     1434
     1435          _parent[e] = _parent[arc];
    14031436          if (_parent[arc] != INVALID) {
    14041437            if (_left[_parent[arc]] == arc) {
    1405               _left.set(_parent[arc], e);
     1438              _left[_parent[arc]] = e;
    14061439            } else {
    1407               _right.set(_parent[arc], e);
     1440              _right[_parent[arc]] = e;
    14081441            }
    14091442          }
    14101443          splay(s);
    14111444        } else {
    1412           _right.set(e, _right[arc]);
    1413           _parent.set(_right[arc], e);
    1414           _parent.set(e, _parent[arc]);
     1445          _right[e] = _right[arc];
     1446          _parent[_right[arc]] = e;
     1447          _parent[e] = _parent[arc];
    14151448
    14161449          if (_parent[arc] != INVALID) {
    14171450            if (_left[_parent[arc]] == arc) {
    1418               _left.set(_parent[arc], e);
     1451              _left[_parent[arc]] = e;
    14191452            } else {
    1420               _right.set(_parent[arc], e);
     1453              _right[_parent[arc]] = e;
    14211454            }
    14221455          } else {
    1423             _head.set(_g.source(arc), e);
     1456            _head[_g.source(arc)] = e;
    14241457          }
    14251458        }
     
    14331466      if (a < m) {
    14341467        Arc left = refreshRec(v,a,m-1);
    1435         _left.set(me, left);
    1436         _parent.set(left, me);
     1468        _left[me] = left;
     1469        _parent[left] = me;
    14371470      } else {
    1438         _left.set(me, INVALID);
     1471        _left[me] = INVALID;
    14391472      }
    14401473      if (m < b) {
    14411474        Arc right = refreshRec(v,m+1,b);
    1442         _right.set(me, right);
    1443         _parent.set(right, me);
     1475        _right[me] = right;
     1476        _parent[right] = me;
    14441477      } else {
    1445         _right.set(me, INVALID);
     1478        _right[me] = INVALID;
    14461479      }
    14471480      return me;
     
    14551488          std::sort(v.begin(),v.end(),ArcLess(_g));
    14561489          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);
     1490          _head[n] = head;
     1491          _parent[head] = INVALID;
     1492        }
     1493        else _head[n] = INVALID;
    14611494      }
    14621495    }
     
    14641497    void zig(Arc v) {
    14651498      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);
     1499      _parent[v] = _parent[w];
     1500      _parent[w] = v;
     1501      _left[w] = _right[v];
     1502      _right[v] = w;
    14701503      if (_parent[v] != INVALID) {
    14711504        if (_right[_parent[v]] == w) {
    1472           _right.set(_parent[v], v);
     1505          _right[_parent[v]] = v;
    14731506        } else {
    1474           _left.set(_parent[v], v);
     1507          _left[_parent[v]] = v;
    14751508        }
    14761509      }
    14771510      if (_left[w] != INVALID){
    1478         _parent.set(_left[w], w);
     1511        _parent[_left[w]] = w;
    14791512      }
    14801513    }
     
    14821515    void zag(Arc v) {
    14831516      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);
     1517      _parent[v] = _parent[w];
     1518      _parent[w] = v;
     1519      _right[w] = _left[v];
     1520      _left[v] = w;
    14881521      if (_parent[v] != INVALID){
    14891522        if (_left[_parent[v]] == w) {
    1490           _left.set(_parent[v], v);
     1523          _left[_parent[v]] = v;
    14911524        } else {
    1492           _right.set(_parent[v], v);
     1525          _right[_parent[v]] = v;
    14931526        }
    14941527      }
    14951528      if (_right[w] != INVALID){
    1496         _parent.set(_right[w], w);
     1529        _parent[_right[w]] = w;
    14971530      }
    14981531    }
     
    16261659  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    16271660  ///
    1628   ///\tparam G The type of the underlying digraph.
     1661  ///\tparam GR The type of the underlying digraph.
    16291662  ///
    16301663  ///\sa DynArcLookUp
    16311664  ///\sa AllArcLookUp
    1632   template<class G>
     1665  template<class GR>
    16331666  class ArcLookUp
    16341667  {
     1668    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1669
    16351670  public:
    1636     TEMPLATE_DIGRAPH_TYPEDEFS(G);
    1637     typedef G Digraph;
     1671
     1672    /// The Digraph type
     1673    typedef GR Digraph;
    16381674
    16391675  protected:
     
    17361772  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
    17371773  ///
    1738   ///\tparam G The type of the underlying digraph.
     1774  ///\tparam GR The type of the underlying digraph.
    17391775  ///
    17401776  ///\sa DynArcLookUp
    17411777  ///\sa ArcLookUp
    1742   template<class G>
    1743   class AllArcLookUp : public ArcLookUp<G>
     1778  template<class GR>
     1779  class AllArcLookUp : public ArcLookUp<GR>
    17441780  {
    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;
     1781    using ArcLookUp<GR>::_g;
     1782    using ArcLookUp<GR>::_right;
     1783    using ArcLookUp<GR>::_left;
     1784    using ArcLookUp<GR>::_head;
     1785
     1786    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1787
     1788    typename GR::template ArcMap<Arc> _next;
    17541789
    17551790    Arc refreshNext(Arc head,Arc next=INVALID)
     
    17701805
    17711806  public:
     1807
     1808    /// The Digraph type
     1809    typedef GR Digraph;
     1810
    17721811    ///Constructor
    17731812
     
    17761815    ///It builds up the search database, which remains valid until the digraph
    17771816    ///changes.
    1778     AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
     1817    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
    17791818
    17801819    ///Refresh the data structure at a node.
     
    17861825    void refresh(Node n)
    17871826    {
    1788       ArcLookUp<G>::refresh(n);
     1827      ArcLookUp<GR>::refresh(n);
    17891828      refreshNext(_head[n]);
    17901829    }
     
    18331872    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    18341873#else
    1835     using ArcLookUp<G>::operator() ;
     1874    using ArcLookUp<GR>::operator() ;
    18361875    Arc operator()(Node s, Node t, Arc prev) const
    18371876    {
  • lemon/core.h

    r883 r893  
    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

    r890 r893  
    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 r893  
    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.