Changeset 986:e958855b8186 in lemon for lemon
 Timestamp:
 06/25/10 06:20:28 (10 years ago)
 Branch:
 1.2
 Parents:
 985:f63fd24c0aea (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 r986 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 085 * Copyright (C) 20032010 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 { 1246 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1247 1234 1248 public: 1235 1249 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) {} 1239 1251 1240 1252 virtual void add(const Node& node) { … … 1259 1271 } 1260 1272 }; 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 1273 1268 1274 class ArcLess { … … 1276 1282 }; 1277 1283 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 1278 1292 public: 1279 1293 … … 1318 1332 virtual void clear() { 1319 1333 for(NodeIt n(_g);n!=INVALID;++n) { 1320 _head .set(n, INVALID);1334 _head[n] = INVALID; 1321 1335 } 1322 1336 } … … 1325 1339 Node s = _g.source(arc); 1326 1340 Node t = _g.target(arc); 1327 _left .set(arc, INVALID);1328 _right .set(arc, INVALID);1341 _left[arc] = INVALID; 1342 _right[arc] = INVALID; 1329 1343 1330 1344 Arc e = _head[s]; 1331 1345 if (e == INVALID) { 1332 _head .set(s, arc);1333 _parent .set(arc, INVALID);1346 _head[s] = arc; 1347 _parent[arc] = INVALID; 1334 1348 return; 1335 1349 } … … 1337 1351 if (t < _g.target(e)) { 1338 1352 if (_left[e] == INVALID) { 1339 _left .set(e, arc);1340 _parent .set(arc, e);1353 _left[e] = arc; 1354 _parent[arc] = e; 1341 1355 splay(arc); 1342 1356 return; … … 1346 1360 } else { 1347 1361 if (_right[e] == INVALID) { 1348 _right .set(e, arc);1349 _parent .set(arc, e);1362 _right[e] = arc; 1363 _parent[arc] = e; 1350 1364 splay(arc); 1351 1365 return; … … 1360 1374 if (_left[arc] == INVALID) { 1361 1375 if (_right[arc] != INVALID) { 1362 _parent .set(_right[arc], _parent[arc]);1376 _parent[_right[arc]] = _parent[arc]; 1363 1377 } 1364 1378 if (_parent[arc] != INVALID) { 1365 1379 if (_left[_parent[arc]] == arc) { 1366 _left .set(_parent[arc], _right[arc]);1380 _left[_parent[arc]] = _right[arc]; 1367 1381 } else { 1368 _right .set(_parent[arc], _right[arc]);1382 _right[_parent[arc]] = _right[arc]; 1369 1383 } 1370 1384 } else { 1371 _head .set(_g.source(arc), _right[arc]);1385 _head[_g.source(arc)] = _right[arc]; 1372 1386 } 1373 1387 } else if (_right[arc] == INVALID) { 1374 _parent .set(_left[arc], _parent[arc]);1388 _parent[_left[arc]] = _parent[arc]; 1375 1389 if (_parent[arc] != INVALID) { 1376 1390 if (_left[_parent[arc]] == arc) { 1377 _left .set(_parent[arc], _left[arc]);1391 _left[_parent[arc]] = _left[arc]; 1378 1392 } else { 1379 _right .set(_parent[arc], _left[arc]);1393 _right[_parent[arc]] = _left[arc]; 1380 1394 } 1381 1395 } else { 1382 _head .set(_g.source(arc), _left[arc]);1396 _head[_g.source(arc)] = _left[arc]; 1383 1397 } 1384 1398 } else { … … 1390 1404 } 1391 1405 Arc s = _parent[e]; 1392 _right .set(_parent[e], _left[e]);1406 _right[_parent[e]] = _left[e]; 1393 1407 if (_left[e] != INVALID) { 1394 _parent .set(_left[e], _parent[e]);1408 _parent[_left[e]] = _parent[e]; 1395 1409 } 1396 1410 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]; 1403 1417 if (_parent[arc] != INVALID) { 1404 1418 if (_left[_parent[arc]] == arc) { 1405 _left .set(_parent[arc], e);1419 _left[_parent[arc]] = e; 1406 1420 } else { 1407 _right .set(_parent[arc], e);1421 _right[_parent[arc]] = e; 1408 1422 } 1409 1423 } 1410 1424 splay(s); 1411 1425 } 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]; 1415 1429 1416 1430 if (_parent[arc] != INVALID) { 1417 1431 if (_left[_parent[arc]] == arc) { 1418 _left .set(_parent[arc], e);1432 _left[_parent[arc]] = e; 1419 1433 } else { 1420 _right .set(_parent[arc], e);1434 _right[_parent[arc]] = e; 1421 1435 } 1422 1436 } else { 1423 _head .set(_g.source(arc), e);1437 _head[_g.source(arc)] = e; 1424 1438 } 1425 1439 } … … 1433 1447 if (a < m) { 1434 1448 Arc left = refreshRec(v,a,m1); 1435 _left .set(me, left);1436 _parent .set(left, me);1449 _left[me] = left; 1450 _parent[left] = me; 1437 1451 } else { 1438 _left .set(me, INVALID);1452 _left[me] = INVALID; 1439 1453 } 1440 1454 if (m < b) { 1441 1455 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; 1444 1458 } else { 1445 _right .set(me, INVALID);1459 _right[me] = INVALID; 1446 1460 } 1447 1461 return me; … … 1455 1469 std::sort(v.begin(),v.end(),ArcLess(_g)); 1456 1470 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; 1461 1475 } 1462 1476 } … … 1464 1478 void zig(Arc v) { 1465 1479 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; 1470 1484 if (_parent[v] != INVALID) { 1471 1485 if (_right[_parent[v]] == w) { 1472 _right .set(_parent[v], v);1486 _right[_parent[v]] = v; 1473 1487 } else { 1474 _left .set(_parent[v], v);1488 _left[_parent[v]] = v; 1475 1489 } 1476 1490 } 1477 1491 if (_left[w] != INVALID){ 1478 _parent .set(_left[w], w);1492 _parent[_left[w]] = w; 1479 1493 } 1480 1494 } … … 1482 1496 void zag(Arc v) { 1483 1497 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; 1488 1502 if (_parent[v] != INVALID){ 1489 1503 if (_left[_parent[v]] == w) { 1490 _left .set(_parent[v], v);1504 _left[_parent[v]] = v; 1491 1505 } else { 1492 _right .set(_parent[v], v);1506 _right[_parent[v]] = v; 1493 1507 } 1494 1508 } 1495 1509 if (_right[w] != INVALID){ 1496 _parent .set(_right[w], w);1510 _parent[_right[w]] = w; 1497 1511 } 1498 1512 } … … 1626 1640 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1627 1641 /// 1628 ///\tparam G The type of the underlying digraph.1642 ///\tparam GR The type of the underlying digraph. 1629 1643 /// 1630 1644 ///\sa DynArcLookUp 1631 1645 ///\sa AllArcLookUp 1632 template<class G >1646 template<class GR> 1633 1647 class ArcLookUp 1634 1648 { 1649 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1650 1635 1651 public: 1636 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1637 typedef G Digraph; 1652 1653 /// The Digraph type 1654 typedef GR Digraph; 1638 1655 1639 1656 protected: … … 1736 1753 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1737 1754 /// 1738 ///\tparam G The type of the underlying digraph.1755 ///\tparam GR The type of the underlying digraph. 1739 1756 /// 1740 1757 ///\sa DynArcLookUp 1741 1758 ///\sa ArcLookUp 1742 template<class G >1743 class AllArcLookUp : public ArcLookUp<G >1759 template<class GR> 1760 class AllArcLookUp : public ArcLookUp<GR> 1744 1761 { 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; 1754 1770 1755 1771 Arc refreshNext(Arc head,Arc next=INVALID) … … 1770 1786 1771 1787 public: 1788 1789 /// The Digraph type 1790 typedef GR Digraph; 1791 1772 1792 ///Constructor 1773 1793 … … 1776 1796 ///It builds up the search database, which remains valid until the digraph 1777 1797 ///changes. 1778 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1798 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1779 1799 1780 1800 ///Refresh the data structure at a node. … … 1786 1806 void refresh(Node n) 1787 1807 { 1788 ArcLookUp<G >::refresh(n);1808 ArcLookUp<GR>::refresh(n); 1789 1809 refreshNext(_head[n]); 1790 1810 } … … 1833 1853 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1834 1854 #else 1835 using ArcLookUp<G >::operator() ;1855 using ArcLookUp<GR>::operator() ; 1836 1856 Arc operator()(Node s, Node t, Arc prev) const 1837 1857 { 
lemon/core.h
r956 r986 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.