Changeset 686:72ac25ad276e in lemon for lemon/core.h
 Timestamp:
 04/29/09 17:55:27 (10 years ago)
 Branch:
 default
 Parents:
 685:57e6f560fb13 (diff), 543:32fb28fc9d42 (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
r543 r686 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). … … 1035 1035 ///\sa findArc() 1036 1036 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1037 template <typename _Graph> 1038 class ConArcIt : public _Graph::Arc { 1037 template <typename GR> 1038 class ConArcIt : public GR::Arc { 1039 typedef typename GR::Arc Parent; 1040 1039 1041 public: 1040 1042 1041 typedef _Graph Graph; 1042 typedef typename Graph::Arc Parent; 1043 1044 typedef typename Graph::Arc Arc; 1045 typedef typename Graph::Node Node; 1043 typedef typename GR::Arc Arc; 1044 typedef typename GR::Node Node; 1046 1045 1047 1046 /// \brief Constructor. … … 1049 1048 /// Construct a new ConArcIt iterating on the arcs that 1050 1049 /// connects nodes \c u and \c v. 1051 ConArcIt(const G raph& g, Node u, Node v) : _graph(g) {1050 ConArcIt(const GR& g, Node u, Node v) : _graph(g) { 1052 1051 Parent::operator=(findArc(_graph, u, v)); 1053 1052 } … … 1056 1055 /// 1057 1056 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1058 ConArcIt(const G raph& g, Arc a) : Parent(a), _graph(g) {}1057 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {} 1059 1058 1060 1059 /// \brief Increment operator. … … 1067 1066 } 1068 1067 private: 1069 const G raph& _graph;1068 const GR& _graph; 1070 1069 }; 1071 1070 … … 1158 1157 /// 1159 1158 ///\sa findEdge() 1160 template <typename _Graph> 1161 class ConEdgeIt : public _Graph::Edge { 1159 template <typename GR> 1160 class ConEdgeIt : public GR::Edge { 1161 typedef typename GR::Edge Parent; 1162 1162 1163 public: 1163 1164 1164 typedef _Graph Graph; 1165 typedef typename Graph::Edge Parent; 1166 1167 typedef typename Graph::Edge Edge; 1168 typedef typename Graph::Node Node; 1165 typedef typename GR::Edge Edge; 1166 typedef typename GR::Node Node; 1169 1167 1170 1168 /// \brief Constructor. … … 1172 1170 /// Construct a new ConEdgeIt iterating on the edges that 1173 1171 /// connects nodes \c u and \c v. 1174 ConEdgeIt(const G raph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {1172 ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) { 1175 1173 Parent::operator=(findEdge(_graph, _u, _v)); 1176 1174 } … … 1179 1177 /// 1180 1178 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1181 ConEdgeIt(const G raph& g, Edge e) : Parent(e), _graph(g) {}1179 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {} 1182 1180 1183 1181 /// \brief Increment operator. … … 1189 1187 } 1190 1188 private: 1191 const G raph& _graph;1189 const GR& _graph; 1192 1190 Node _u, _v; 1193 1191 }; … … 1212 1210 ///queries. 1213 1211 /// 1214 ///\tparam G The type of the underlying digraph.1212 ///\tparam GR The type of the underlying digraph. 1215 1213 /// 1216 1214 ///\sa ArcLookUp 1217 1215 ///\sa AllArcLookUp 1218 template <class G>1216 template <typename GR> 1219 1217 class DynArcLookUp 1220 : protected ItemSetTraits<G , typename G::Arc>::ItemNotifier::ObserverBase1218 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1221 1219 { 1220 typedef typename ItemSetTraits<GR, typename GR::Arc> 1221 ::ItemNotifier::ObserverBase Parent; 1222 1223 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1224 1222 1225 public: 1223 typedef typename ItemSetTraits<G, typename G::Arc> 1224 ::ItemNotifier::ObserverBase Parent; 1225 1226 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1227 typedef G Digraph; 1226 1227 /// The Digraph type 1228 typedef GR Digraph; 1228 1229 1229 1230 protected: 1230 1231 1231 class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type { 1232 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1233 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1234 1232 1235 public: 1233 1236 1234 typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent; 1235 1236 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {} 1237 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {} 1237 1238 1238 1239 virtual void add(const Node& node) { … … 1257 1258 } 1258 1259 }; 1259 1260 const Digraph &_g;1261 AutoNodeMap _head;1262 typename Digraph::template ArcMap<Arc> _parent;1263 typename Digraph::template ArcMap<Arc> _left;1264 typename Digraph::template ArcMap<Arc> _right;1265 1260 1266 1261 class ArcLess { … … 1274 1269 }; 1275 1270 1271 protected: 1272 1273 const Digraph &_g; 1274 AutoNodeMap _head; 1275 typename Digraph::template ArcMap<Arc> _parent; 1276 typename Digraph::template ArcMap<Arc> _left; 1277 typename Digraph::template ArcMap<Arc> _right; 1278 1276 1279 public: 1277 1280 … … 1316 1319 virtual void clear() { 1317 1320 for(NodeIt n(_g);n!=INVALID;++n) { 1318 _head .set(n, INVALID);1321 _head[n] = INVALID; 1319 1322 } 1320 1323 } … … 1323 1326 Node s = _g.source(arc); 1324 1327 Node t = _g.target(arc); 1325 _left .set(arc, INVALID);1326 _right .set(arc, INVALID);1328 _left[arc] = INVALID; 1329 _right[arc] = INVALID; 1327 1330 1328 1331 Arc e = _head[s]; 1329 1332 if (e == INVALID) { 1330 _head .set(s, arc);1331 _parent .set(arc, INVALID);1333 _head[s] = arc; 1334 _parent[arc] = INVALID; 1332 1335 return; 1333 1336 } … … 1335 1338 if (t < _g.target(e)) { 1336 1339 if (_left[e] == INVALID) { 1337 _left .set(e, arc);1338 _parent .set(arc, e);1340 _left[e] = arc; 1341 _parent[arc] = e; 1339 1342 splay(arc); 1340 1343 return; … … 1344 1347 } else { 1345 1348 if (_right[e] == INVALID) { 1346 _right .set(e, arc);1347 _parent .set(arc, e);1349 _right[e] = arc; 1350 _parent[arc] = e; 1348 1351 splay(arc); 1349 1352 return; … … 1358 1361 if (_left[arc] == INVALID) { 1359 1362 if (_right[arc] != INVALID) { 1360 _parent .set(_right[arc], _parent[arc]);1363 _parent[_right[arc]] = _parent[arc]; 1361 1364 } 1362 1365 if (_parent[arc] != INVALID) { 1363 1366 if (_left[_parent[arc]] == arc) { 1364 _left .set(_parent[arc], _right[arc]);1367 _left[_parent[arc]] = _right[arc]; 1365 1368 } else { 1366 _right .set(_parent[arc], _right[arc]);1369 _right[_parent[arc]] = _right[arc]; 1367 1370 } 1368 1371 } else { 1369 _head .set(_g.source(arc), _right[arc]);1372 _head[_g.source(arc)] = _right[arc]; 1370 1373 } 1371 1374 } else if (_right[arc] == INVALID) { 1372 _parent .set(_left[arc], _parent[arc]);1375 _parent[_left[arc]] = _parent[arc]; 1373 1376 if (_parent[arc] != INVALID) { 1374 1377 if (_left[_parent[arc]] == arc) { 1375 _left .set(_parent[arc], _left[arc]);1378 _left[_parent[arc]] = _left[arc]; 1376 1379 } else { 1377 _right .set(_parent[arc], _left[arc]);1380 _right[_parent[arc]] = _left[arc]; 1378 1381 } 1379 1382 } else { 1380 _head .set(_g.source(arc), _left[arc]);1383 _head[_g.source(arc)] = _left[arc]; 1381 1384 } 1382 1385 } else { … … 1388 1391 } 1389 1392 Arc s = _parent[e]; 1390 _right .set(_parent[e], _left[e]);1393 _right[_parent[e]] = _left[e]; 1391 1394 if (_left[e] != INVALID) { 1392 _parent .set(_left[e], _parent[e]);1395 _parent[_left[e]] = _parent[e]; 1393 1396 } 1394 1397 1395 _left .set(e, _left[arc]);1396 _parent .set(_left[arc], e);1397 _right .set(e, _right[arc]);1398 _parent .set(_right[arc], e);1399 1400 _parent .set(e, _parent[arc]);1398 _left[e] = _left[arc]; 1399 _parent[_left[arc]] = e; 1400 _right[e] = _right[arc]; 1401 _parent[_right[arc]] = e; 1402 1403 _parent[e] = _parent[arc]; 1401 1404 if (_parent[arc] != INVALID) { 1402 1405 if (_left[_parent[arc]] == arc) { 1403 _left .set(_parent[arc], e);1406 _left[_parent[arc]] = e; 1404 1407 } else { 1405 _right .set(_parent[arc], e);1408 _right[_parent[arc]] = e; 1406 1409 } 1407 1410 } 1408 1411 splay(s); 1409 1412 } else { 1410 _right .set(e, _right[arc]);1411 _parent .set(_right[arc], e);1412 _parent .set(e, _parent[arc]);1413 _right[e] = _right[arc]; 1414 _parent[_right[arc]] = e; 1415 _parent[e] = _parent[arc]; 1413 1416 1414 1417 if (_parent[arc] != INVALID) { 1415 1418 if (_left[_parent[arc]] == arc) { 1416 _left .set(_parent[arc], e);1419 _left[_parent[arc]] = e; 1417 1420 } else { 1418 _right .set(_parent[arc], e);1421 _right[_parent[arc]] = e; 1419 1422 } 1420 1423 } else { 1421 _head .set(_g.source(arc), e);1424 _head[_g.source(arc)] = e; 1422 1425 } 1423 1426 } … … 1431 1434 if (a < m) { 1432 1435 Arc left = refreshRec(v,a,m1); 1433 _left .set(me, left);1434 _parent .set(left, me);1436 _left[me] = left; 1437 _parent[left] = me; 1435 1438 } else { 1436 _left .set(me, INVALID);1439 _left[me] = INVALID; 1437 1440 } 1438 1441 if (m < b) { 1439 1442 Arc right = refreshRec(v,m+1,b); 1440 _right .set(me, right);1441 _parent .set(right, me);1443 _right[me] = right; 1444 _parent[right] = me; 1442 1445 } else { 1443 _right .set(me, INVALID);1446 _right[me] = INVALID; 1444 1447 } 1445 1448 return me; … … 1453 1456 std::sort(v.begin(),v.end(),ArcLess(_g)); 1454 1457 Arc head = refreshRec(v,0,v.size()1); 1455 _head .set(n, head);1456 _parent .set(head, INVALID);1457 } 1458 else _head .set(n, INVALID);1458 _head[n] = head; 1459 _parent[head] = INVALID; 1460 } 1461 else _head[n] = INVALID; 1459 1462 } 1460 1463 } … … 1462 1465 void zig(Arc v) { 1463 1466 Arc w = _parent[v]; 1464 _parent .set(v, _parent[w]);1465 _parent .set(w, v);1466 _left .set(w, _right[v]);1467 _right .set(v, w);1467 _parent[v] = _parent[w]; 1468 _parent[w] = v; 1469 _left[w] = _right[v]; 1470 _right[v] = w; 1468 1471 if (_parent[v] != INVALID) { 1469 1472 if (_right[_parent[v]] == w) { 1470 _right .set(_parent[v], v);1473 _right[_parent[v]] = v; 1471 1474 } else { 1472 _left .set(_parent[v], v);1475 _left[_parent[v]] = v; 1473 1476 } 1474 1477 } 1475 1478 if (_left[w] != INVALID){ 1476 _parent .set(_left[w], w);1479 _parent[_left[w]] = w; 1477 1480 } 1478 1481 } … … 1480 1483 void zag(Arc v) { 1481 1484 Arc w = _parent[v]; 1482 _parent .set(v, _parent[w]);1483 _parent .set(w, v);1484 _right .set(w, _left[v]);1485 _left .set(v, w);1485 _parent[v] = _parent[w]; 1486 _parent[w] = v; 1487 _right[w] = _left[v]; 1488 _left[v] = w; 1486 1489 if (_parent[v] != INVALID){ 1487 1490 if (_left[_parent[v]] == w) { 1488 _left .set(_parent[v], v);1491 _left[_parent[v]] = v; 1489 1492 } else { 1490 _right .set(_parent[v], v);1493 _right[_parent[v]] = v; 1491 1494 } 1492 1495 } 1493 1496 if (_right[w] != INVALID){ 1494 _parent .set(_right[w], w);1497 _parent[_right[w]] = w; 1495 1498 } 1496 1499 } … … 1624 1627 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1625 1628 /// 1626 ///\tparam G The type of the underlying digraph.1629 ///\tparam GR The type of the underlying digraph. 1627 1630 /// 1628 1631 ///\sa DynArcLookUp 1629 1632 ///\sa AllArcLookUp 1630 template<class G >1633 template<class GR> 1631 1634 class ArcLookUp 1632 1635 { 1636 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1637 1633 1638 public: 1634 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1635 typedef G Digraph; 1639 1640 /// The Digraph type 1641 typedef GR Digraph; 1636 1642 1637 1643 protected: … … 1734 1740 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1735 1741 /// 1736 ///\tparam G The type of the underlying digraph.1742 ///\tparam GR The type of the underlying digraph. 1737 1743 /// 1738 1744 ///\sa DynArcLookUp 1739 1745 ///\sa ArcLookUp 1740 template<class G >1741 class AllArcLookUp : public ArcLookUp<G >1746 template<class GR> 1747 class AllArcLookUp : public ArcLookUp<GR> 1742 1748 { 1743 using ArcLookUp<G>::_g; 1744 using ArcLookUp<G>::_right; 1745 using ArcLookUp<G>::_left; 1746 using ArcLookUp<G>::_head; 1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1749 typedef G Digraph; 1750 1751 typename Digraph::template ArcMap<Arc> _next; 1749 using ArcLookUp<GR>::_g; 1750 using ArcLookUp<GR>::_right; 1751 using ArcLookUp<GR>::_left; 1752 using ArcLookUp<GR>::_head; 1753 1754 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1755 1756 typename GR::template ArcMap<Arc> _next; 1752 1757 1753 1758 Arc refreshNext(Arc head,Arc next=INVALID) … … 1768 1773 1769 1774 public: 1775 1776 /// The Digraph type 1777 typedef GR Digraph; 1778 1770 1779 ///Constructor 1771 1780 … … 1774 1783 ///It builds up the search database, which remains valid until the digraph 1775 1784 ///changes. 1776 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1785 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1777 1786 1778 1787 ///Refresh the data structure at a node. … … 1784 1793 void refresh(Node n) 1785 1794 { 1786 ArcLookUp<G >::refresh(n);1795 ArcLookUp<GR>::refresh(n); 1787 1796 refreshNext(_head[n]); 1788 1797 } … … 1831 1840 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1832 1841 #else 1833 using ArcLookUp<G >::operator() ;1842 using ArcLookUp<GR>::operator() ; 1834 1843 Arc operator()(Node s, Node t, Arc prev) const 1835 1844 { 
lemon/core.h
r664 r686 23 23 #include <algorithm> 24 24 25 #include <lemon/co re.h>25 #include <lemon/config.h> 26 26 #include <lemon/bits/enable_if.h> 27 27 #include <lemon/bits/traits.h>
Note: See TracChangeset
for help on using the changeset viewer.