Changeset 988:d395358592df in lemon for lemon
 Timestamp:
 06/25/10 06:41:55 (10 years ago)
 Branch:
 default
 Parents:
 987:a22b3f1bf83e (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 r988 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 … … 437 447 438 448 } 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 439 468 440 469 /// \brief Class to copy a digraph. … … 1037 1066 ///\sa findArc() 1038 1067 ///\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 1041 1072 public: 1042 1073 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; 1048 1076 1049 1077 /// \brief Constructor. … … 1051 1079 /// Construct a new ConArcIt iterating on the arcs that 1052 1080 /// connects nodes \c u and \c v. 1053 ConArcIt(const G raph& g, Node u, Node v) : _graph(g) {1081 ConArcIt(const GR& g, Node u, Node v) : _graph(g) { 1054 1082 Parent::operator=(findArc(_graph, u, v)); 1055 1083 } … … 1058 1086 /// 1059 1087 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1060 ConArcIt(const G raph& g, Arc a) : Parent(a), _graph(g) {}1088 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {} 1061 1089 1062 1090 /// \brief Increment operator. … … 1069 1097 } 1070 1098 private: 1071 const G raph& _graph;1099 const GR& _graph; 1072 1100 }; 1073 1101 … … 1160 1188 /// 1161 1189 ///\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 1164 1194 public: 1165 1195 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; 1171 1198 1172 1199 /// \brief Constructor. … … 1174 1201 /// Construct a new ConEdgeIt iterating on the edges that 1175 1202 /// connects nodes \c u and \c v. 1176 ConEdgeIt(const G raph& 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) { 1177 1204 Parent::operator=(findEdge(_graph, _u, _v)); 1178 1205 } … … 1181 1208 /// 1182 1209 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1183 ConEdgeIt(const G raph& g, Edge e) : Parent(e), _graph(g) {}1210 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {} 1184 1211 1185 1212 /// \brief Increment operator. … … 1191 1218 } 1192 1219 private: 1193 const G raph& _graph;1220 const GR& _graph; 1194 1221 Node _u, _v; 1195 1222 }; … … 1214 1241 ///queries. 1215 1242 /// 1216 ///\tparam G The type of the underlying digraph.1243 ///\tparam GR The type of the underlying digraph. 1217 1244 /// 1218 1245 ///\sa ArcLookUp 1219 1246 ///\sa AllArcLookUp 1220 template <class G>1247 template <typename GR> 1221 1248 class DynArcLookUp 1222 : protected ItemSetTraits<G , typename G::Arc>::ItemNotifier::ObserverBase1249 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1223 1250 { 1251 typedef typename ItemSetTraits<GR, typename GR::Arc> 1252 ::ItemNotifier::ObserverBase Parent; 1253 1254 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1255 1224 1256 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; 1230 1260 1231 1261 protected: 1232 1262 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 1234 1267 public: 1235 1268 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) {} 1239 1270 1240 1271 virtual void add(const Node& node) { … … 1259 1290 } 1260 1291 }; 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 1292 1268 1293 class ArcLess { … … 1276 1301 }; 1277 1302 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 1278 1311 public: 1279 1312 … … 1318 1351 virtual void clear() { 1319 1352 for(NodeIt n(_g);n!=INVALID;++n) { 1320 _head .set(n, INVALID);1353 _head[n] = INVALID; 1321 1354 } 1322 1355 } … … 1325 1358 Node s = _g.source(arc); 1326 1359 Node t = _g.target(arc); 1327 _left .set(arc, INVALID);1328 _right .set(arc, INVALID);1360 _left[arc] = INVALID; 1361 _right[arc] = INVALID; 1329 1362 1330 1363 Arc e = _head[s]; 1331 1364 if (e == INVALID) { 1332 _head .set(s, arc);1333 _parent .set(arc, INVALID);1365 _head[s] = arc; 1366 _parent[arc] = INVALID; 1334 1367 return; 1335 1368 } … … 1337 1370 if (t < _g.target(e)) { 1338 1371 if (_left[e] == INVALID) { 1339 _left .set(e, arc);1340 _parent .set(arc, e);1372 _left[e] = arc; 1373 _parent[arc] = e; 1341 1374 splay(arc); 1342 1375 return; … … 1346 1379 } else { 1347 1380 if (_right[e] == INVALID) { 1348 _right .set(e, arc);1349 _parent .set(arc, e);1381 _right[e] = arc; 1382 _parent[arc] = e; 1350 1383 splay(arc); 1351 1384 return; … … 1360 1393 if (_left[arc] == INVALID) { 1361 1394 if (_right[arc] != INVALID) { 1362 _parent .set(_right[arc], _parent[arc]);1395 _parent[_right[arc]] = _parent[arc]; 1363 1396 } 1364 1397 if (_parent[arc] != INVALID) { 1365 1398 if (_left[_parent[arc]] == arc) { 1366 _left .set(_parent[arc], _right[arc]);1399 _left[_parent[arc]] = _right[arc]; 1367 1400 } else { 1368 _right .set(_parent[arc], _right[arc]);1401 _right[_parent[arc]] = _right[arc]; 1369 1402 } 1370 1403 } else { 1371 _head .set(_g.source(arc), _right[arc]);1404 _head[_g.source(arc)] = _right[arc]; 1372 1405 } 1373 1406 } else if (_right[arc] == INVALID) { 1374 _parent .set(_left[arc], _parent[arc]);1407 _parent[_left[arc]] = _parent[arc]; 1375 1408 if (_parent[arc] != INVALID) { 1376 1409 if (_left[_parent[arc]] == arc) { 1377 _left .set(_parent[arc], _left[arc]);1410 _left[_parent[arc]] = _left[arc]; 1378 1411 } else { 1379 _right .set(_parent[arc], _left[arc]);1412 _right[_parent[arc]] = _left[arc]; 1380 1413 } 1381 1414 } else { 1382 _head .set(_g.source(arc), _left[arc]);1415 _head[_g.source(arc)] = _left[arc]; 1383 1416 } 1384 1417 } else { … … 1390 1423 } 1391 1424 Arc s = _parent[e]; 1392 _right .set(_parent[e], _left[e]);1425 _right[_parent[e]] = _left[e]; 1393 1426 if (_left[e] != INVALID) { 1394 _parent .set(_left[e], _parent[e]);1427 _parent[_left[e]] = _parent[e]; 1395 1428 } 1396 1429 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]; 1403 1436 if (_parent[arc] != INVALID) { 1404 1437 if (_left[_parent[arc]] == arc) { 1405 _left .set(_parent[arc], e);1438 _left[_parent[arc]] = e; 1406 1439 } else { 1407 _right .set(_parent[arc], e);1440 _right[_parent[arc]] = e; 1408 1441 } 1409 1442 } 1410 1443 splay(s); 1411 1444 } 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]; 1415 1448 1416 1449 if (_parent[arc] != INVALID) { 1417 1450 if (_left[_parent[arc]] == arc) { 1418 _left .set(_parent[arc], e);1451 _left[_parent[arc]] = e; 1419 1452 } else { 1420 _right .set(_parent[arc], e);1453 _right[_parent[arc]] = e; 1421 1454 } 1422 1455 } else { 1423 _head .set(_g.source(arc), e);1456 _head[_g.source(arc)] = e; 1424 1457 } 1425 1458 } … … 1433 1466 if (a < m) { 1434 1467 Arc left = refreshRec(v,a,m1); 1435 _left .set(me, left);1436 _parent .set(left, me);1468 _left[me] = left; 1469 _parent[left] = me; 1437 1470 } else { 1438 _left .set(me, INVALID);1471 _left[me] = INVALID; 1439 1472 } 1440 1473 if (m < b) { 1441 1474 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; 1444 1477 } else { 1445 _right .set(me, INVALID);1478 _right[me] = INVALID; 1446 1479 } 1447 1480 return me; … … 1455 1488 std::sort(v.begin(),v.end(),ArcLess(_g)); 1456 1489 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; 1461 1494 } 1462 1495 } … … 1464 1497 void zig(Arc v) { 1465 1498 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; 1470 1503 if (_parent[v] != INVALID) { 1471 1504 if (_right[_parent[v]] == w) { 1472 _right .set(_parent[v], v);1505 _right[_parent[v]] = v; 1473 1506 } else { 1474 _left .set(_parent[v], v);1507 _left[_parent[v]] = v; 1475 1508 } 1476 1509 } 1477 1510 if (_left[w] != INVALID){ 1478 _parent .set(_left[w], w);1511 _parent[_left[w]] = w; 1479 1512 } 1480 1513 } … … 1482 1515 void zag(Arc v) { 1483 1516 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; 1488 1521 if (_parent[v] != INVALID){ 1489 1522 if (_left[_parent[v]] == w) { 1490 _left .set(_parent[v], v);1523 _left[_parent[v]] = v; 1491 1524 } else { 1492 _right .set(_parent[v], v);1525 _right[_parent[v]] = v; 1493 1526 } 1494 1527 } 1495 1528 if (_right[w] != INVALID){ 1496 _parent .set(_right[w], w);1529 _parent[_right[w]] = w; 1497 1530 } 1498 1531 } … … 1626 1659 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1627 1660 /// 1628 ///\tparam G The type of the underlying digraph.1661 ///\tparam GR The type of the underlying digraph. 1629 1662 /// 1630 1663 ///\sa DynArcLookUp 1631 1664 ///\sa AllArcLookUp 1632 template<class G >1665 template<class GR> 1633 1666 class ArcLookUp 1634 1667 { 1668 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1669 1635 1670 public: 1636 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1637 typedef G Digraph; 1671 1672 /// The Digraph type 1673 typedef GR Digraph; 1638 1674 1639 1675 protected: … … 1736 1772 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1737 1773 /// 1738 ///\tparam G The type of the underlying digraph.1774 ///\tparam GR The type of the underlying digraph. 1739 1775 /// 1740 1776 ///\sa DynArcLookUp 1741 1777 ///\sa ArcLookUp 1742 template<class G >1743 class AllArcLookUp : public ArcLookUp<G >1778 template<class GR> 1779 class AllArcLookUp : public ArcLookUp<GR> 1744 1780 { 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; 1754 1789 1755 1790 Arc refreshNext(Arc head,Arc next=INVALID) … … 1770 1805 1771 1806 public: 1807 1808 /// The Digraph type 1809 typedef GR Digraph; 1810 1772 1811 ///Constructor 1773 1812 … … 1776 1815 ///It builds up the search database, which remains valid until the digraph 1777 1816 ///changes. 1778 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1817 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1779 1818 1780 1819 ///Refresh the data structure at a node. … … 1786 1825 void refresh(Node n) 1787 1826 { 1788 ArcLookUp<G >::refresh(n);1827 ArcLookUp<GR>::refresh(n); 1789 1828 refreshNext(_head[n]); 1790 1829 } … … 1833 1872 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1834 1873 #else 1835 using ArcLookUp<G >::operator() ;1874 using ArcLookUp<GR>::operator() ; 1836 1875 Arc operator()(Node s, Node t, Arc prev) const 1837 1876 { 
lemon/core.h
r966 r988 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.