Changeset 686:72ac25ad276e in lemon
- Timestamp:
- 04/29/09 17:55:27 (15 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
- Location:
- lemon
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r543 r686 8 8 9 9 lemon_libemon_la_SOURCES = \ 10 lemon/arg_parser.cc \ 11 lemon/base.cc \ 12 lemon/color.cc \ 13 lemon/random.cc \ 10 lemon/arg_parser.cc \ 11 lemon/base.cc \ 12 lemon/color.cc \ 13 lemon/lp_base.cc \ 14 lemon/lp_skeleton.cc \ 15 lemon/random.cc \ 14 16 lemon/bits/windows.cc 15 17 16 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 17 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 18 nodist_lemon_HEADERS = lemon/config.h 19 20 lemon_libemon_la_CXXFLAGS = \ 21 $(AM_CXXFLAGS) \ 22 $(GLPK_CFLAGS) \ 23 $(CPLEX_CFLAGS) \ 24 $(SOPLEX_CXXFLAGS) \ 25 $(CLP_CXXFLAGS) \ 26 $(CBC_CXXFLAGS) 18 27 19 nodist_lemon_HEADERS = lemon/config.h 28 lemon_libemon_la_LDFLAGS = \ 29 $(GLPK_LIBS) \ 30 $(CPLEX_LIBS) \ 31 $(SOPLEX_LIBS) \ 32 $(CLP_LIBS) \ 33 $(CBC_LIBS) 34 35 if HAVE_GLPK 36 lemon_libemon_la_SOURCES += lemon/glpk.cc 37 endif 38 39 if HAVE_CPLEX 40 lemon_libemon_la_SOURCES += lemon/cplex.cc 41 endif 42 43 if HAVE_SOPLEX 44 lemon_libemon_la_SOURCES += lemon/soplex.cc 45 endif 46 47 if HAVE_CLP 48 lemon_libemon_la_SOURCES += lemon/clp.cc 49 endif 50 51 if HAVE_CBC 52 lemon_libemon_la_SOURCES += lemon/cbc.cc 53 endif 20 54 21 55 lemon_HEADERS += \ 22 lemon/arg_parser.h \ 56 lemon/adaptors.h \ 57 lemon/arg_parser.h \ 23 58 lemon/assert.h \ 24 lemon/bfs.h \ 25 lemon/bin_heap.h \ 26 lemon/color.h \ 59 lemon/bfs.h \ 60 lemon/bin_heap.h \ 61 lemon/cbc.h \ 62 lemon/circulation.h \ 63 lemon/clp.h \ 64 lemon/color.h \ 27 65 lemon/concept_check.h \ 28 lemon/counter.h \ 66 lemon/connectivity.h \ 67 lemon/counter.h \ 29 68 lemon/core.h \ 30 lemon/dfs.h \ 31 lemon/dijkstra.h \ 32 lemon/dim2.h \ 69 lemon/cplex.h \ 70 lemon/dfs.h \ 71 lemon/dijkstra.h \ 72 lemon/dim2.h \ 73 lemon/dimacs.h \ 74 lemon/edge_set.h \ 75 lemon/elevator.h \ 33 76 lemon/error.h \ 34 lemon/graph_to_eps.h \ 77 lemon/euler.h \ 78 lemon/full_graph.h \ 79 lemon/glpk.h \ 80 lemon/gomory_hu.h \ 81 lemon/graph_to_eps.h \ 82 lemon/grid_graph.h \ 83 lemon/hypercube_graph.h \ 35 84 lemon/kruskal.h \ 85 lemon/hao_orlin.h \ 36 86 lemon/lgf_reader.h \ 37 87 lemon/lgf_writer.h \ 38 88 lemon/list_graph.h \ 89 lemon/lp.h \ 90 lemon/lp_base.h \ 91 lemon/lp_skeleton.h \ 92 lemon/list_graph.h \ 39 93 lemon/maps.h \ 94 lemon/matching.h \ 40 95 lemon/math.h \ 96 lemon/min_cost_arborescence.h \ 97 lemon/nauty_reader.h \ 98 lemon/network_simplex.h \ 41 99 lemon/path.h \ 42 lemon/random.h \ 100 lemon/preflow.h \ 101 lemon/radix_sort.h \ 102 lemon/random.h \ 43 103 lemon/smart_graph.h \ 44 lemon/time_measure.h \ 45 lemon/tolerance.h \ 104 lemon/soplex.h \ 105 lemon/suurballe.h \ 106 lemon/time_measure.h \ 107 lemon/tolerance.h \ 46 108 lemon/unionfind.h \ 47 109 lemon/bits/windows.h … … 51 113 lemon/bits/array_map.h \ 52 114 lemon/bits/base_extender.h \ 53 115 lemon/bits/bezier.h \ 54 116 lemon/bits/default_map.h \ 55 lemon/bits/enable_if.h \ 117 lemon/bits/edge_set_extender.h \ 118 lemon/bits/enable_if.h \ 119 lemon/bits/graph_adaptor_extender.h \ 56 120 lemon/bits/graph_extender.h \ 57 121 lemon/bits/map_extender.h \ 58 122 lemon/bits/path_dump.h \ 123 lemon/bits/solver_bits.h \ 59 124 lemon/bits/traits.h \ 125 lemon/bits/variant.h \ 60 126 lemon/bits/vector_map.h 61 127 -
lemon/Makefile.am
r677 r686 16 16 lemon/bits/windows.cc 17 17 18 18 nodist_lemon_HEADERS = lemon/config.h 19 19 20 lemon_libemon_la_CXXFLAGS = \ 20 21 $(AM_CXXFLAGS) \ … … 63 64 lemon/color.h \ 64 65 lemon/concept_check.h \ 65 lemon/config.h \66 66 lemon/connectivity.h \ 67 67 lemon/counter.h \ -
lemon/core.h
r543 r686 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 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,m-1); 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.