Changeset 984:9f22c22fe227 in lemon for lemon/core.h
 Timestamp:
 06/25/10 06:15:43 (9 years ago)
 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
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/core.h
r980 r984 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003200 85 * Copyright (C) 20032009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 27 27 #include <lemon/bits/traits.h> 28 28 #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 29 39 30 40 ///\file … … 1037 1047 ///\sa findArc() 1038 1048 ///\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 1041 1053 public: 1042 1054 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; 1048 1057 1049 1058 /// \brief Constructor. … … 1051 1060 /// Construct a new ConArcIt iterating on the arcs that 1052 1061 /// connects nodes \c u and \c v. 1053 ConArcIt(const G raph& g, Node u, Node v) : _graph(g) {1062 ConArcIt(const GR& g, Node u, Node v) : _graph(g) { 1054 1063 Parent::operator=(findArc(_graph, u, v)); 1055 1064 } … … 1058 1067 /// 1059 1068 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1060 ConArcIt(const G raph& g, Arc a) : Parent(a), _graph(g) {}1069 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {} 1061 1070 1062 1071 /// \brief Increment operator. … … 1069 1078 } 1070 1079 private: 1071 const G raph& _graph;1080 const GR& _graph; 1072 1081 }; 1073 1082 … … 1160 1169 /// 1161 1170 ///\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 1164 1175 public: 1165 1176 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; 1171 1179 1172 1180 /// \brief Constructor. … … 1174 1182 /// Construct a new ConEdgeIt iterating on the edges that 1175 1183 /// connects nodes \c u and \c v. 1176 ConEdgeIt(const G raph& 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) { 1177 1185 Parent::operator=(findEdge(_graph, _u, _v)); 1178 1186 } … … 1181 1189 /// 1182 1190 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1183 ConEdgeIt(const G raph& g, Edge e) : Parent(e), _graph(g) {}1191 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {} 1184 1192 1185 1193 /// \brief Increment operator. … … 1191 1199 } 1192 1200 private: 1193 const G raph& _graph;1201 const GR& _graph; 1194 1202 Node _u, _v; 1195 1203 }; … … 1214 1222 ///queries. 1215 1223 /// 1216 ///\tparam G The type of the underlying digraph.1224 ///\tparam GR The type of the underlying digraph. 1217 1225 /// 1218 1226 ///\sa ArcLookUp 1219 1227 ///\sa AllArcLookUp 1220 template <class G>1228 template <typename GR> 1221 1229 class DynArcLookUp 1222 : protected ItemSetTraits<G , typename G::Arc>::ItemNotifier::ObserverBase1230 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1223 1231 { 1232 typedef typename ItemSetTraits<GR, typename GR::Arc> 1233 ::ItemNotifier::ObserverBase Parent; 1234 1235 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1236 1224 1237 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; 1230 1241 1231 1242 protected: 1232 1243 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 1234 1247 public: 1235 1248 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) {} 1239 1250 1240 1251 virtual void add(const Node& node) { … … 1259 1270 } 1260 1271 }; 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;1267 1272 1268 1273 class ArcLess { … … 1276 1281 }; 1277 1282 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 1278 1291 public: 1279 1292 … … 1318 1331 virtual void clear() { 1319 1332 for(NodeIt n(_g);n!=INVALID;++n) { 1320 _head .set(n, INVALID);1333 _head[n] = INVALID; 1321 1334 } 1322 1335 } … … 1325 1338 Node s = _g.source(arc); 1326 1339 Node t = _g.target(arc); 1327 _left .set(arc, INVALID);1328 _right .set(arc, INVALID);1340 _left[arc] = INVALID; 1341 _right[arc] = INVALID; 1329 1342 1330 1343 Arc e = _head[s]; 1331 1344 if (e == INVALID) { 1332 _head .set(s, arc);1333 _parent .set(arc, INVALID);1345 _head[s] = arc; 1346 _parent[arc] = INVALID; 1334 1347 return; 1335 1348 } … … 1337 1350 if (t < _g.target(e)) { 1338 1351 if (_left[e] == INVALID) { 1339 _left .set(e, arc);1340 _parent .set(arc, e);1352 _left[e] = arc; 1353 _parent[arc] = e; 1341 1354 splay(arc); 1342 1355 return; … … 1346 1359 } else { 1347 1360 if (_right[e] == INVALID) { 1348 _right .set(e, arc);1349 _parent .set(arc, e);1361 _right[e] = arc; 1362 _parent[arc] = e; 1350 1363 splay(arc); 1351 1364 return; … … 1360 1373 if (_left[arc] == INVALID) { 1361 1374 if (_right[arc] != INVALID) { 1362 _parent .set(_right[arc], _parent[arc]);1375 _parent[_right[arc]] = _parent[arc]; 1363 1376 } 1364 1377 if (_parent[arc] != INVALID) { 1365 1378 if (_left[_parent[arc]] == arc) { 1366 _left .set(_parent[arc], _right[arc]);1379 _left[_parent[arc]] = _right[arc]; 1367 1380 } else { 1368 _right .set(_parent[arc], _right[arc]);1381 _right[_parent[arc]] = _right[arc]; 1369 1382 } 1370 1383 } else { 1371 _head .set(_g.source(arc), _right[arc]);1384 _head[_g.source(arc)] = _right[arc]; 1372 1385 } 1373 1386 } else if (_right[arc] == INVALID) { 1374 _parent .set(_left[arc], _parent[arc]);1387 _parent[_left[arc]] = _parent[arc]; 1375 1388 if (_parent[arc] != INVALID) { 1376 1389 if (_left[_parent[arc]] == arc) { 1377 _left .set(_parent[arc], _left[arc]);1390 _left[_parent[arc]] = _left[arc]; 1378 1391 } else { 1379 _right .set(_parent[arc], _left[arc]);1392 _right[_parent[arc]] = _left[arc]; 1380 1393 } 1381 1394 } else { 1382 _head .set(_g.source(arc), _left[arc]);1395 _head[_g.source(arc)] = _left[arc]; 1383 1396 } 1384 1397 } else { … … 1390 1403 } 1391 1404 Arc s = _parent[e]; 1392 _right .set(_parent[e], _left[e]);1405 _right[_parent[e]] = _left[e]; 1393 1406 if (_left[e] != INVALID) { 1394 _parent .set(_left[e], _parent[e]);1407 _parent[_left[e]] = _parent[e]; 1395 1408 } 1396 1409 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]; 1403 1416 if (_parent[arc] != INVALID) { 1404 1417 if (_left[_parent[arc]] == arc) { 1405 _left .set(_parent[arc], e);1418 _left[_parent[arc]] = e; 1406 1419 } else { 1407 _right .set(_parent[arc], e);1420 _right[_parent[arc]] = e; 1408 1421 } 1409 1422 } 1410 1423 splay(s); 1411 1424 } 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]; 1415 1428 1416 1429 if (_parent[arc] != INVALID) { 1417 1430 if (_left[_parent[arc]] == arc) { 1418 _left .set(_parent[arc], e);1431 _left[_parent[arc]] = e; 1419 1432 } else { 1420 _right .set(_parent[arc], e);1433 _right[_parent[arc]] = e; 1421 1434 } 1422 1435 } else { 1423 _head .set(_g.source(arc), e);1436 _head[_g.source(arc)] = e; 1424 1437 } 1425 1438 } … … 1433 1446 if (a < m) { 1434 1447 Arc left = refreshRec(v,a,m1); 1435 _left .set(me, left);1436 _parent .set(left, me);1448 _left[me] = left; 1449 _parent[left] = me; 1437 1450 } else { 1438 _left .set(me, INVALID);1451 _left[me] = INVALID; 1439 1452 } 1440 1453 if (m < b) { 1441 1454 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; 1444 1457 } else { 1445 _right .set(me, INVALID);1458 _right[me] = INVALID; 1446 1459 } 1447 1460 return me; … … 1455 1468 std::sort(v.begin(),v.end(),ArcLess(_g)); 1456 1469 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; 1461 1474 } 1462 1475 } … … 1464 1477 void zig(Arc v) { 1465 1478 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; 1470 1483 if (_parent[v] != INVALID) { 1471 1484 if (_right[_parent[v]] == w) { 1472 _right .set(_parent[v], v);1485 _right[_parent[v]] = v; 1473 1486 } else { 1474 _left .set(_parent[v], v);1487 _left[_parent[v]] = v; 1475 1488 } 1476 1489 } 1477 1490 if (_left[w] != INVALID){ 1478 _parent .set(_left[w], w);1491 _parent[_left[w]] = w; 1479 1492 } 1480 1493 } … … 1482 1495 void zag(Arc v) { 1483 1496 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; 1488 1501 if (_parent[v] != INVALID){ 1489 1502 if (_left[_parent[v]] == w) { 1490 _left .set(_parent[v], v);1503 _left[_parent[v]] = v; 1491 1504 } else { 1492 _right .set(_parent[v], v);1505 _right[_parent[v]] = v; 1493 1506 } 1494 1507 } 1495 1508 if (_right[w] != INVALID){ 1496 _parent .set(_right[w], w);1509 _parent[_right[w]] = w; 1497 1510 } 1498 1511 } … … 1626 1639 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1627 1640 /// 1628 ///\tparam G The type of the underlying digraph.1641 ///\tparam GR The type of the underlying digraph. 1629 1642 /// 1630 1643 ///\sa DynArcLookUp 1631 1644 ///\sa AllArcLookUp 1632 template<class G >1645 template<class GR> 1633 1646 class ArcLookUp 1634 1647 { 1648 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1649 1635 1650 public: 1636 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1637 typedef G Digraph; 1651 1652 /// The Digraph type 1653 typedef GR Digraph; 1638 1654 1639 1655 protected: … … 1736 1752 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1737 1753 /// 1738 ///\tparam G The type of the underlying digraph.1754 ///\tparam GR The type of the underlying digraph. 1739 1755 /// 1740 1756 ///\sa DynArcLookUp 1741 1757 ///\sa ArcLookUp 1742 template<class G >1743 class AllArcLookUp : public ArcLookUp<G >1758 template<class GR> 1759 class AllArcLookUp : public ArcLookUp<GR> 1744 1760 { 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; 1754 1769 1755 1770 Arc refreshNext(Arc head,Arc next=INVALID) … … 1770 1785 1771 1786 public: 1787 1788 /// The Digraph type 1789 typedef GR Digraph; 1790 1772 1791 ///Constructor 1773 1792 … … 1776 1795 ///It builds up the search database, which remains valid until the digraph 1777 1796 ///changes. 1778 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1797 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1779 1798 1780 1799 ///Refresh the data structure at a node. … … 1786 1805 void refresh(Node n) 1787 1806 { 1788 ArcLookUp<G >::refresh(n);1807 ArcLookUp<GR>::refresh(n); 1789 1808 refreshNext(_head[n]); 1790 1809 } … … 1833 1852 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1834 1853 #else 1835 using ArcLookUp<G >::operator() ;1854 using ArcLookUp<GR>::operator() ; 1836 1855 Arc operator()(Node s, Node t, Arc prev) const 1837 1856 { 
lemon/core.h
r718 r984 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear(); 397 398 for (typename From::NodeIt it(from); it != INVALID; ++it) { 398 399 nodeRefMap[it] = to.addNode(); … … 422 423 static void copy(const From& from, Graph &to, 423 424 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear(); 424 426 for (typename From::NodeIt it(from); it != INVALID; ++it) { 425 427 nodeRefMap[it] = to.addNode();
Note: See TracChangeset
for help on using the changeset viewer.