Changeset 1102:17e36e175725 in lemon for lemon
- Timestamp:
- 12/20/11 17:35:45 (12 years ago)
- Branch:
- default
- Parents:
- 1092:2eebc8f7dca5 (diff), 1087:b96574ff36ec (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:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r1086 r1102 2 2 lemon/lemon.pc.in \ 3 3 lemon/lemon.pc.cmake \ 4 lemon/CMakeLists.txt 4 lemon/CMakeLists.txt \ 5 lemon/config.h.cmake 5 6 6 7 pkgconfig_DATA += lemon/lemon.pc … … 9 10 10 11 lemon_libemon_la_SOURCES = \ 11 lemon/arg_parser.cc \ 12 lemon/base.cc \ 13 lemon/color.cc \ 14 lemon/random.cc \ 12 lemon/arg_parser.cc \ 13 lemon/base.cc \ 14 lemon/color.cc \ 15 lemon/lp_base.cc \ 16 lemon/lp_skeleton.cc \ 17 lemon/random.cc \ 15 18 lemon/bits/windows.cc 16 19 17 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 18 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 20 nodist_lemon_HEADERS = lemon/config.h 19 21 20 nodist_lemon_HEADERS = lemon/config.h 22 lemon_libemon_la_CXXFLAGS = \ 23 $(AM_CXXFLAGS) \ 24 $(GLPK_CFLAGS) \ 25 $(CPLEX_CFLAGS) \ 26 $(SOPLEX_CXXFLAGS) \ 27 $(CLP_CXXFLAGS) \ 28 $(CBC_CXXFLAGS) 29 30 lemon_libemon_la_LDFLAGS = \ 31 $(GLPK_LIBS) \ 32 $(CPLEX_LIBS) \ 33 $(SOPLEX_LIBS) \ 34 $(CLP_LIBS) \ 35 $(CBC_LIBS) 36 37 if HAVE_GLPK 38 lemon_libemon_la_SOURCES += lemon/glpk.cc 39 endif 40 41 if HAVE_CPLEX 42 lemon_libemon_la_SOURCES += lemon/cplex.cc 43 endif 44 45 if HAVE_SOPLEX 46 lemon_libemon_la_SOURCES += lemon/soplex.cc 47 endif 48 49 if HAVE_CLP 50 lemon_libemon_la_SOURCES += lemon/clp.cc 51 endif 52 53 if HAVE_CBC 54 lemon_libemon_la_SOURCES += lemon/cbc.cc 55 endif 21 56 22 57 lemon_HEADERS += \ 23 lemon/arg_parser.h \ 58 lemon/adaptors.h \ 59 lemon/arg_parser.h \ 24 60 lemon/assert.h \ 25 lemon/bfs.h \ 26 lemon/bin_heap.h \ 27 lemon/color.h \ 61 lemon/bfs.h \ 62 lemon/bin_heap.h \ 63 lemon/bucket_heap.h \ 64 lemon/cbc.h \ 65 lemon/circulation.h \ 66 lemon/clp.h \ 67 lemon/color.h \ 28 68 lemon/concept_check.h \ 29 lemon/counter.h \ 69 lemon/connectivity.h \ 70 lemon/counter.h \ 30 71 lemon/core.h \ 31 lemon/dfs.h \ 32 lemon/dijkstra.h \ 33 lemon/dim2.h \ 72 lemon/cplex.h \ 73 lemon/dfs.h \ 74 lemon/dijkstra.h \ 75 lemon/dim2.h \ 76 lemon/dimacs.h \ 77 lemon/edge_set.h \ 78 lemon/elevator.h \ 34 79 lemon/error.h \ 35 lemon/graph_to_eps.h \ 80 lemon/euler.h \ 81 lemon/fib_heap.h \ 82 lemon/full_graph.h \ 83 lemon/glpk.h \ 84 lemon/gomory_hu.h \ 85 lemon/graph_to_eps.h \ 86 lemon/grid_graph.h \ 87 lemon/hypercube_graph.h \ 36 88 lemon/kruskal.h \ 89 lemon/hao_orlin.h \ 37 90 lemon/lgf_reader.h \ 38 91 lemon/lgf_writer.h \ 39 92 lemon/list_graph.h \ 93 lemon/lp.h \ 94 lemon/lp_base.h \ 95 lemon/lp_skeleton.h \ 96 lemon/list_graph.h \ 40 97 lemon/maps.h \ 98 lemon/matching.h \ 41 99 lemon/math.h \ 100 lemon/min_cost_arborescence.h \ 101 lemon/nauty_reader.h \ 102 lemon/network_simplex.h \ 42 103 lemon/path.h \ 43 lemon/random.h \ 104 lemon/preflow.h \ 105 lemon/radix_heap.h \ 106 lemon/radix_sort.h \ 107 lemon/random.h \ 44 108 lemon/smart_graph.h \ 45 lemon/time_measure.h \ 46 lemon/tolerance.h \ 109 lemon/soplex.h \ 110 lemon/suurballe.h \ 111 lemon/time_measure.h \ 112 lemon/tolerance.h \ 47 113 lemon/unionfind.h \ 48 114 lemon/bits/windows.h … … 51 117 lemon/bits/alteration_notifier.h \ 52 118 lemon/bits/array_map.h \ 53 lemon/bits/base_extender.h \ 54 lemon/bits/bezier.h \ 119 lemon/bits/bezier.h \ 55 120 lemon/bits/default_map.h \ 56 lemon/bits/enable_if.h \ 121 lemon/bits/edge_set_extender.h \ 122 lemon/bits/enable_if.h \ 123 lemon/bits/graph_adaptor_extender.h \ 57 124 lemon/bits/graph_extender.h \ 58 125 lemon/bits/map_extender.h \ 59 126 lemon/bits/path_dump.h \ 127 lemon/bits/solver_bits.h \ 60 128 lemon/bits/traits.h \ 129 lemon/bits/variant.h \ 61 130 lemon/bits/vector_map.h 62 131 -
lemon/Makefile.am
r728 r1102 1 1 EXTRA_DIST += \ 2 2 lemon/lemon.pc.in \ 3 lemon/lemon.pc.cmake \ 3 4 lemon/CMakeLists.txt \ 4 5 lemon/config.h.cmake -
lemon/bits/path_dump.h
r971 r973 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). … … 17 17 */ 18 18 19 #ifndef LEMON_BITS_PRED_MAP_PATH_H 20 #define LEMON_BITS_PRED_MAP_PATH_H 19 #ifndef LEMON_BITS_PATH_DUMP_H 20 #define LEMON_BITS_PATH_DUMP_H 21 22 #include <lemon/core.h> 23 #include <lemon/concept_check.h> 21 24 22 25 namespace lemon { -
lemon/bits/path_dump.h
r576 r973 50 50 51 51 bool empty() const { 52 return predMap[target] != INVALID;52 return predMap[target] == INVALID; 53 53 } 54 54 … … 124 124 125 125 bool empty() const { 126 return source != target;126 return predMatrixMap(source, target) == INVALID; 127 127 } 128 128 -
lemon/core.h
r980 r984 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). … … 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,m-1); 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(); -
lemon/dfs.h
r1007 r1009 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). … … 50 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a PredMap.53 54 ///This function instantiates a PredMap.52 ///Instantiates a \c PredMap. 53 54 ///This function instantiates a \ref PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// PredMap.56 ///\ref PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.67 ///Instantiates a \c ProcessedMap. 68 69 ///This function instantiates a \ref ProcessedMap. 70 70 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap71 ///we would like to define the \ref ProcessedMap. 72 72 #ifdef DOXYGEN 73 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 84 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 85 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a ReachedMap.87 88 ///This function instantiates a ReachedMap.86 ///Instantiates a \c ReachedMap. 87 88 ///This function instantiates a \ref ReachedMap. 89 89 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.90 ///we would like to define the \ref ReachedMap. 91 91 static ReachedMap *createReachedMap(const Digraph &g) 92 92 { … … 99 99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 100 100 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a DistMap.102 103 ///This function instantiates a DistMap.101 ///Instantiates a \c DistMap. 102 103 ///This function instantiates a \ref DistMap. 104 104 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.105 ///\ref DistMap. 106 106 static DistMap *createDistMap(const Digraph &g) 107 107 { … … 120 120 /// 121 121 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". 127 ///See \ref DfsDefaultTraits for the documentation of 128 ///a Dfs traits class. 122 ///The default type is \ref ListDigraph. 129 123 #ifdef DOXYGEN 130 124 template <typename GR, … … 152 146 typedef PredMapPath<Digraph, PredMap> Path; 153 147 154 ///The traits class.148 ///The \ref DfsDefaultTraits "traits class" of the algorithm. 155 149 typedef TR Traits; 156 150 … … 213 207 typedef Dfs Create; 214 208 215 ///\name Named template parameters209 ///\name Named Template Parameters 216 210 217 211 ///@{ … … 227 221 }; 228 222 ///\brief \ref named-templ-param "Named parameter" for setting 229 /// PredMap type.223 ///\c PredMap type. 230 224 /// 231 225 ///\ref named-templ-param "Named parameter" for setting 232 ///PredMap type. 226 ///\c PredMap type. 227 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 233 228 template <class T> 234 229 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 246 241 }; 247 242 ///\brief \ref named-templ-param "Named parameter" for setting 248 /// DistMap type.243 ///\c DistMap type. 249 244 /// 250 245 ///\ref named-templ-param "Named parameter" for setting 251 ///DistMap type. 246 ///\c DistMap type. 247 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 252 248 template <class T> 253 249 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 261 }; 266 262 ///\brief \ref named-templ-param "Named parameter" for setting 267 /// ReachedMap type.263 ///\c ReachedMap type. 268 264 /// 269 265 ///\ref named-templ-param "Named parameter" for setting 270 ///ReachedMap type. 266 ///\c ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 271 268 template <class T> 272 269 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 284 281 }; 285 282 ///\brief \ref named-templ-param "Named parameter" for setting 286 /// ProcessedMap type.283 ///\c ProcessedMap type. 287 284 /// 288 285 ///\ref named-templ-param "Named parameter" for setting 289 ///ProcessedMap type. 286 ///\c ProcessedMap type. 287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 290 288 template <class T> 291 289 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 301 299 }; 302 300 ///\brief \ref named-templ-param "Named parameter" for setting 303 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.301 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 304 302 /// 305 303 ///\ref named-templ-param "Named parameter" for setting 306 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.304 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 307 305 ///If you don't set it explicitly, it will be automatically allocated. 308 306 struct SetStandardProcessedMap : … … 339 337 340 338 ///Sets the map that stores the predecessor arcs. 341 ///If you don't use this function before calling \ref run(), 342 ///it will allocate one. The destructor deallocates this 343 ///automatically allocated map, of course. 339 ///If you don't use this function before calling \ref run(Node) "run()" 340 ///or \ref init(), an instance will be allocated automatically. 341 ///The destructor deallocates this automatically allocated map, 342 ///of course. 344 343 ///\return <tt> (*this) </tt> 345 344 Dfs &predMap(PredMap &m) … … 356 355 357 356 ///Sets the map that indicates which nodes are reached. 358 ///If you don't use this function before calling \ref run(), 359 ///it will allocate one. The destructor deallocates this 360 ///automatically allocated map, of course. 357 ///If you don't use this function before calling \ref run(Node) "run()" 358 ///or \ref init(), an instance will be allocated automatically. 359 ///The destructor deallocates this automatically allocated map, 360 ///of course. 361 361 ///\return <tt> (*this) </tt> 362 362 Dfs &reachedMap(ReachedMap &m) … … 373 373 374 374 ///Sets the map that indicates which nodes are processed. 375 ///If you don't use this function before calling \ref run(), 376 ///it will allocate one. The destructor deallocates this 377 ///automatically allocated map, of course. 375 ///If you don't use this function before calling \ref run(Node) "run()" 376 ///or \ref init(), an instance will be allocated automatically. 377 ///The destructor deallocates this automatically allocated map, 378 ///of course. 378 379 ///\return <tt> (*this) </tt> 379 380 Dfs &processedMap(ProcessedMap &m) … … 391 392 ///Sets the map that stores the distances of the nodes calculated by 392 393 ///the algorithm. 393 ///If you don't use this function before calling \ref run(), 394 ///it will allocate one. The destructor deallocates this 395 ///automatically allocated map, of course. 394 ///If you don't use this function before calling \ref run(Node) "run()" 395 ///or \ref init(), an instance will be allocated automatically. 396 ///The destructor deallocates this automatically allocated map, 397 ///of course. 396 398 ///\return <tt> (*this) </tt> 397 399 Dfs &distMap(DistMap &m) … … 407 409 public: 408 410 409 ///\name Execution control 410 ///The simplest way to execute the algorithm is to use 411 ///one of the member functions called \ref lemon::Dfs::run() "run()". 412 ///\n 413 ///If you need more control on the execution, first you must call 414 ///\ref lemon::Dfs::init() "init()", then you can add a source node 415 ///with \ref lemon::Dfs::addSource() "addSource()". 416 ///Finally \ref lemon::Dfs::start() "start()" will perform the 417 ///actual path computation. 411 ///\name Execution Control 412 ///The simplest way to execute the DFS algorithm is to use one of the 413 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, first you have to call 415 ///\ref init(), then you can add a source node with \ref addSource() 416 ///and perform the actual computation with \ref start(). 417 ///This procedure can be repeated if there are nodes that have not 418 ///been reached. 418 419 419 420 ///@{ 420 421 422 ///\brief Initializes the internal data structures. 423 /// 421 424 ///Initializes the internal data structures. 422 423 ///Initializes the internal data structures.424 ///425 425 void init() 426 426 { … … 439 439 ///Adds a new source node to the set of nodes to be processed. 440 440 /// 441 ///\pre The stack must be empty. (Otherwise the algorithm gives 442 ///false results.) 443 /// 444 ///\warning Distances will be wrong (or at least strange) in case of 445 ///multiple sources. 441 ///\pre The stack must be empty. Otherwise the algorithm gives 442 ///wrong results. (One of the outgoing arcs of all the source nodes 443 ///except for the last one will not be visited and distances will 444 ///also be wrong.) 446 445 void addSource(Node s) 447 446 { … … 507 506 } 508 507 509 ///\brief Returns \c false if there are nodes 510 ///to be processed. 511 /// 512 ///Returns \c false if there are nodes 513 ///to be processed in the queue (stack). 508 ///Returns \c false if there are nodes to be processed. 509 510 ///Returns \c false if there are nodes to be processed 511 ///in the queue (stack). 514 512 bool emptyQueue() const { return _stack_head<0; } 515 513 516 514 ///Returns the number of the nodes to be processed. 517 515 518 ///Returns the number of the nodes to be processed in the queue (stack). 516 ///Returns the number of the nodes to be processed 517 ///in the queue (stack). 519 518 int queueSize() const { return _stack_head+1; } 520 519 … … 638 637 /// 639 638 ///The algorithm computes 640 ///- the %DFS tree ,641 ///- the distance of each node from the root in the %DFS tree.639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 642 641 /// 643 642 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 664 663 665 664 ///\name Query Functions 666 ///The result of the %DFS algorithm can be obtained using these665 ///The results of the DFS algorithm can be obtained using these 667 666 ///functions.\n 668 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()669 /// "start()" must be calledbefore using them.667 ///Either \ref run(Node) "run()" or \ref start() should be called 668 ///before using them. 670 669 671 670 ///@{ … … 675 674 ///Returns the DFS path to a node. 676 675 /// 677 ///\warning \c t should be reach able from the root.678 /// 679 ///\pre Either \ref run( ) or \ref start() must be called before680 /// using this function.676 ///\warning \c t should be reached from the root(s). 677 /// 678 ///\pre Either \ref run(Node) "run()" or \ref init() 679 ///must be called before using this function. 681 680 Path path(Node t) const { return Path(*G, *_pred, t); } 682 681 683 ///The distance of a node from the root .684 685 ///Returns the distance of a node from the root .686 /// 687 ///\warning If node \c v is not reach able from the root, then682 ///The distance of a node from the root(s). 683 684 ///Returns the distance of a node from the root(s). 685 /// 686 ///\warning If node \c v is not reached from the root(s), then 688 687 ///the return value of this function is undefined. 689 688 /// 690 ///\pre Either \ref run( ) or \ref start() must be called before691 /// using this function.689 ///\pre Either \ref run(Node) "run()" or \ref init() 690 ///must be called before using this function. 692 691 int dist(Node v) const { return (*_dist)[v]; } 693 692 … … 695 694 696 695 ///This function returns the 'previous arc' of the %DFS tree for the 697 ///node \c v, i.e. it returns the last arc of a %DFS path from the698 ///root to \c v. It is \c INVALID 699 /// if \c v is not reachable from theroot(s) or if \c v is a root.696 ///node \c v, i.e. it returns the last arc of a %DFS path from a 697 ///root to \c v. It is \c INVALID if \c v is not reached from the 698 ///root(s) or if \c v is a root. 700 699 /// 701 700 ///The %DFS tree used here is equal to the %DFS tree used in 702 701 ///\ref predNode(). 703 702 /// 704 ///\pre Either \ref run( ) or \ref start() must be called before using705 /// this function.703 ///\pre Either \ref run(Node) "run()" or \ref init() 704 ///must be called before using this function. 706 705 Arc predArc(Node v) const { return (*_pred)[v];} 707 706 … … 710 709 ///This function returns the 'previous node' of the %DFS 711 710 ///tree for the node \c v, i.e. it returns the last but one node 712 ///from a %DFS path from theroot to \c v. It is \c INVALID713 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.711 ///from a %DFS path from a root to \c v. It is \c INVALID 712 ///if \c v is not reached from the root(s) or if \c v is a root. 714 713 /// 715 714 ///The %DFS tree used here is equal to the %DFS tree used in 716 715 ///\ref predArc(). 717 716 /// 718 ///\pre Either \ref run( ) or \ref start() must be called before719 /// using this function.717 ///\pre Either \ref run(Node) "run()" or \ref init() 718 ///must be called before using this function. 720 719 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 721 720 G->source((*_pred)[v]); } … … 727 726 ///distances of the nodes calculated by the algorithm. 728 727 /// 729 ///\pre Either \ref run( )or \ref init()728 ///\pre Either \ref run(Node) "run()" or \ref init() 730 729 ///must be called before using this function. 731 730 const DistMap &distMap() const { return *_dist;} … … 737 736 ///arcs, which form the DFS tree. 738 737 /// 739 ///\pre Either \ref run( )or \ref init()738 ///\pre Either \ref run(Node) "run()" or \ref init() 740 739 ///must be called before using this function. 741 740 const PredMap &predMap() const { return *_pred;} 742 741 743 ///Checks if a node is reachable from the root(s). 744 745 ///Returns \c true if \c v is reachable from the root(s). 746 ///\pre Either \ref run() or \ref start() 742 ///Checks if a node is reached from the root(s). 743 744 ///Returns \c true if \c v is reached from the root(s). 745 /// 746 ///\pre Either \ref run(Node) "run()" or \ref init() 747 747 ///must be called before using this function. 748 748 bool reached(Node v) const { return (*_reached)[v]; } … … 890 890 /// This auxiliary class is created to implement the 891 891 /// \ref dfs() "function-type interface" of \ref Dfs algorithm. 892 /// It does not have own \ref run( ) method, it uses the functions893 /// and features of the plain \ref Dfs.892 /// It does not have own \ref run(Node) "run()" method, it uses the 893 /// functions and features of the plain \ref Dfs. 894 894 /// 895 895 /// This class should only be used through the \ref dfs() function, … … 1111 1111 /// bool reached = dfs(g).path(p).dist(d).run(s,t); 1112 1112 ///\endcode 1113 1114 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1113 ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" 1115 1114 ///to the end of the parameter list. 1116 1115 ///\sa DfsWizard … … 1128 1127 /// This class defines the interface of the DfsVisit events, and 1129 1128 /// it could be the base of a real visitor class. 1130 template <typename _Digraph>1129 template <typename GR> 1131 1130 struct DfsVisitor { 1132 typedef _DigraphDigraph;1131 typedef GR Digraph; 1133 1132 typedef typename Digraph::Arc Arc; 1134 1133 typedef typename Digraph::Node Node; … … 1166 1165 }; 1167 1166 #else 1168 template <typename _Digraph>1167 template <typename GR> 1169 1168 struct DfsVisitor { 1170 typedef _DigraphDigraph;1169 typedef GR Digraph; 1171 1170 typedef typename Digraph::Arc Arc; 1172 1171 typedef typename Digraph::Node Node; … … 1201 1200 /// Default traits class of DfsVisit class. 1202 1201 /// \tparam _Digraph The type of the digraph the algorithm runs on. 1203 template<class _Digraph>1202 template<class GR> 1204 1203 struct DfsVisitDefaultTraits { 1205 1204 1206 1205 /// \brief The type of the digraph the algorithm runs on. 1207 typedef _DigraphDigraph;1206 typedef GR Digraph; 1208 1207 1209 1208 /// \brief The type of the map that indicates which nodes are reached. … … 1226 1225 /// \ingroup search 1227 1226 /// 1228 /// \brief %DFS algorithm class with visitor interface.1227 /// \brief DFS algorithm class with visitor interface. 1229 1228 /// 1230 /// This class provides an efficient implementation of the %DFS algorithm1229 /// This class provides an efficient implementation of the DFS algorithm 1231 1230 /// with visitor interface. 1232 1231 /// 1233 /// The %DfsVisit class provides an alternative interface to the Dfs1232 /// The DfsVisit class provides an alternative interface to the Dfs 1234 1233 /// class. It works with callback mechanism, the DfsVisit object calls 1235 1234 /// the member functions of the \c Visitor class on every DFS event. … … 1240 1239 /// instead. 1241 1240 /// 1242 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1243 /// The default value is1244 /// \ref ListDigraph. The value of _Digraph is not used directly by1245 /// \ref DfsVisit,it is only passed to \ref DfsVisitDefaultTraits.1246 /// \tparam _VisitorThe Visitor type that is used by the algorithm.1247 /// \ref DfsVisitor "DfsVisitor< _Digraph>" is an empty visitor, which1241 /// \tparam GR The type of the digraph the algorithm runs on. 1242 /// The default type is \ref ListDigraph. 1243 /// The value of GR is not used directly by \ref DfsVisit, 1244 /// it is only passed to \ref DfsVisitDefaultTraits. 1245 /// \tparam VS The Visitor type that is used by the algorithm. 1246 /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which 1248 1247 /// does not observe the DFS events. If you want to observe the DFS 1249 1248 /// events, you should implement your own visitor class. 1250 /// \tparam _TraitsTraits class to set various data types used by the1249 /// \tparam TR Traits class to set various data types used by the 1251 1250 /// algorithm. The default traits class is 1252 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits< _Digraph>".1251 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>". 1253 1252 /// See \ref DfsVisitDefaultTraits for the documentation of 1254 1253 /// a DFS visit traits class. 1255 1254 #ifdef DOXYGEN 1256 template <typename _Digraph, typename _Visitor, typename _Traits>1255 template <typename GR, typename VS, typename TR> 1257 1256 #else 1258 template <typename _Digraph= ListDigraph,1259 typename _Visitor = DfsVisitor<_Digraph>,1260 typename _Traits = DfsVisitDefaultTraits<_Digraph> >1257 template <typename GR = ListDigraph, 1258 typename VS = DfsVisitor<GR>, 1259 typename TR = DfsVisitDefaultTraits<GR> > 1261 1260 #endif 1262 1261 class DfsVisit { … … 1264 1263 1265 1264 ///The traits class. 1266 typedef _TraitsTraits;1265 typedef TR Traits; 1267 1266 1268 1267 ///The type of the digraph the algorithm runs on. … … 1270 1269 1271 1270 ///The visitor type used by the algorithm. 1272 typedef _VisitorVisitor;1271 typedef VS Visitor; 1273 1272 1274 1273 ///The type of the map that indicates which nodes are reached. … … 1310 1309 typedef DfsVisit Create; 1311 1310 1312 /// \name Named template parameters1311 /// \name Named Template Parameters 1313 1312 1314 1313 ///@{ … … 1352 1351 /// 1353 1352 /// Sets the map that indicates which nodes are reached. 1354 /// If you don't use this function before calling \ref run(), 1355 /// it will allocate one. The destructor deallocates this 1356 /// automatically allocated map, of course. 1353 /// If you don't use this function before calling \ref run(Node) "run()" 1354 /// or \ref init(), an instance will be allocated automatically. 1355 /// The destructor deallocates this automatically allocated map, 1356 /// of course. 1357 1357 /// \return <tt> (*this) </tt> 1358 1358 DfsVisit &reachedMap(ReachedMap &m) { … … 1367 1367 public: 1368 1368 1369 /// \name Execution control 1370 /// The simplest way to execute the algorithm is to use 1371 /// one of the member functions called \ref lemon::DfsVisit::run() 1372 /// "run()". 1373 /// \n 1374 /// If you need more control on the execution, first you must call 1375 /// \ref lemon::DfsVisit::init() "init()", then you can add several 1376 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". 1377 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the 1378 /// actual path computation. 1369 /// \name Execution Control 1370 /// The simplest way to execute the DFS algorithm is to use one of the 1371 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, first you have to call 1373 /// \ref init(), then you can add a source node with \ref addSource() 1374 /// and perform the actual computation with \ref start(). 1375 /// This procedure can be repeated if there are nodes that have not 1376 /// been reached. 1379 1377 1380 1378 /// @{ … … 1392 1390 } 1393 1391 1394 ///Adds a new source node. 1395 1396 ///Adds a new source node to the set of nodes to be processed. 1397 /// 1398 ///\pre The stack must be empty. (Otherwise the algorithm gives 1399 ///false results.) 1400 /// 1401 ///\warning Distances will be wrong (or at least strange) in case of 1402 ///multiple sources. 1392 /// \brief Adds a new source node. 1393 /// 1394 /// Adds a new source node to the set of nodes to be processed. 1395 /// 1396 /// \pre The stack must be empty. Otherwise the algorithm gives 1397 /// wrong results. (One of the outgoing arcs of all the source nodes 1398 /// except for the last one will not be visited and distances will 1399 /// also be wrong.) 1403 1400 void addSource(Node s) 1404 1401 { … … 1414 1411 } else { 1415 1412 _visitor->leave(s); 1413 _visitor->stop(s); 1416 1414 } 1417 1415 } … … 1590 1588 /// 1591 1589 /// The algorithm computes 1592 /// - the %DFS tree ,1593 /// - the distance of each node from the root in the %DFS tree.1590 /// - the %DFS tree (forest), 1591 /// - the distance of each node from the root(s) in the %DFS tree. 1594 1592 /// 1595 1593 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1616 1614 1617 1615 /// \name Query Functions 1618 /// The result of the %DFS algorithm can be obtained using these1616 /// The results of the DFS algorithm can be obtained using these 1619 1617 /// functions.\n 1620 /// Either \ref lemon::DfsVisit::run() "run()" or1621 /// \ref lemon::DfsVisit::start() "start()" must be called before1622 /// using them. 1618 /// Either \ref run(Node) "run()" or \ref start() should be called 1619 /// before using them. 1620 1623 1621 ///@{ 1624 1622 1625 /// \brief Checks if a node is reachable from the root(s). 1626 /// 1627 /// Returns \c true if \c v is reachable from the root(s). 1628 /// \pre Either \ref run() or \ref start() 1623 /// \brief Checks if a node is reached from the root(s). 1624 /// 1625 /// Returns \c true if \c v is reached from the root(s). 1626 /// 1627 /// \pre Either \ref run(Node) "run()" or \ref init() 1629 1628 /// must be called before using this function. 1630 bool reached(Node v) { return (*_reached)[v]; }1629 bool reached(Node v) const { return (*_reached)[v]; } 1631 1630 1632 1631 ///@} -
lemon/dfs.h
r631 r1009 558 558 void start(Node t) 559 559 { 560 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t)560 while ( !emptyQueue() && !(*_reached)[t] ) 561 561 processNextArc(); 562 562 } … … 1510 1510 /// with addSource() before using this function. 1511 1511 void start(Node t) { 1512 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t)1512 while ( !emptyQueue() && !(*_reached)[t] ) 1513 1513 processNextArc(); 1514 1514 } -
lemon/graph_to_eps.h
r906 r908 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). … … 65 65 ///Default traits class of \ref GraphToEps. 66 66 /// 67 ///\ c Gis the type of the underlying graph.68 template<class G >67 ///\param GR is the type of the underlying graph. 68 template<class GR> 69 69 struct DefaultGraphToEpsTraits 70 70 { 71 typedef G Graph; 71 typedef GR Graph; 72 typedef GR Digraph; 72 73 typedef typename Graph::Node Node; 73 74 typedef typename Graph::NodeIt NodeIt; … … 140 141 141 142 ///Constructor 142 ///\param _g Reference to the graph to be printed. 143 ///\param _os Reference to the output stream. 144 ///\param _os Reference to the output stream. 143 ///\param gr Reference to the graph to be printed. 144 ///\param ost Reference to the output stream. 145 145 ///By default it is <tt>std::cout</tt>. 146 ///\param _pros If it is \c true, then the \c ostream referenced by \c _os146 ///\param pros If it is \c true, then the \c ostream referenced by \c os 147 147 ///will be explicitly deallocated by the destructor. 148 DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,149 bool _pros=false) :150 g( _g), os(_os),148 DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout, 149 bool pros = false) : 150 g(gr), os(ost), 151 151 _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0), 152 152 _nodeColors(WHITE), _arcColors(BLACK), … … 159 159 _showNodeText(false), _nodeTexts(false), _nodeTextSize(1), 160 160 _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0), 161 _undirected(lemon::UndirectedTagIndicator<G >::value),162 _pleaseRemoveOsStream( _pros), _scaleToA4(false),161 _undirected(lemon::UndirectedTagIndicator<GR>::value), 162 _pleaseRemoveOsStream(pros), _scaleToA4(false), 163 163 _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK), 164 164 _autoNodeScale(false), … … 243 243 244 244 typedef typename T::Graph Graph; 245 typedef typename T::Digraph Digraph; 245 246 typedef typename Graph::Node Node; 246 247 typedef typename Graph::NodeIt NodeIt; … … 270 271 ///\image html nodeshape_1.png 271 272 ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm 272 ///273 273 SQUARE=1, 274 274 /// = 2 275 275 ///\image html nodeshape_2.png 276 276 ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm 277 ///278 277 DIAMOND=2, 279 278 /// = 3 280 279 ///\image html nodeshape_3.png 281 ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm 282 /// 280 ///\image latex nodeshape_3.eps "MALE shape (3)" width=2cm 283 281 MALE=3, 284 282 /// = 4 285 283 ///\image html nodeshape_4.png 286 ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm 287 /// 284 ///\image latex nodeshape_4.eps "FEMALE shape (4)" width=2cm 288 285 FEMALE=4 289 286 }; … … 1135 1132 ///to the end of the parameter list. 1136 1133 ///\sa GraphToEps 1137 ///\sa graphToEps(G &g, const char *file_name)1138 template<class G >1139 GraphToEps<DefaultGraphToEpsTraits<G > >1140 graphToEps(G &g, std::ostream& os=std::cout)1134 ///\sa graphToEps(GR &g, const char *file_name) 1135 template<class GR> 1136 GraphToEps<DefaultGraphToEpsTraits<GR> > 1137 graphToEps(GR &g, std::ostream& os=std::cout) 1141 1138 { 1142 1139 return 1143 GraphToEps<DefaultGraphToEpsTraits<G > >(DefaultGraphToEpsTraits<G>(g,os));1140 GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os)); 1144 1141 } 1145 1142 … … 1148 1145 ///\ingroup eps_io 1149 1146 ///This function does the same as 1150 ///\ref graphToEps(G &g,std::ostream& os)1147 ///\ref graphToEps(GR &g,std::ostream& os) 1151 1148 ///but it writes its output into the file \c file_name 1152 1149 ///instead of a stream. 1153 ///\sa graphToEps(G &g, std::ostream& os)1154 template<class G >1155 GraphToEps<DefaultGraphToEpsTraits<G > >1156 graphToEps(G &g,const char *file_name)1150 ///\sa graphToEps(GR &g, std::ostream& os) 1151 template<class GR> 1152 GraphToEps<DefaultGraphToEpsTraits<GR> > 1153 graphToEps(GR &g,const char *file_name) 1157 1154 { 1158 1155 std::ostream* os = new std::ofstream(file_name); … … 1161 1158 throw IoError("Cannot write file", file_name); 1162 1159 } 1163 return GraphToEps<DefaultGraphToEpsTraits<G > >1164 (DefaultGraphToEpsTraits<G >(g,*os,true));1160 return GraphToEps<DefaultGraphToEpsTraits<GR> > 1161 (DefaultGraphToEpsTraits<GR>(g,*os,true)); 1165 1162 } 1166 1163 … … 1169 1166 ///\ingroup eps_io 1170 1167 ///This function does the same as 1171 ///\ref graphToEps(G &g,std::ostream& os)1168 ///\ref graphToEps(GR &g,std::ostream& os) 1172 1169 ///but it writes its output into the file \c file_name 1173 1170 ///instead of a stream. 1174 ///\sa graphToEps(G &g, std::ostream& os)1175 template<class G >1176 GraphToEps<DefaultGraphToEpsTraits<G > >1177 graphToEps(G &g,const std::string& file_name)1171 ///\sa graphToEps(GR &g, std::ostream& os) 1172 template<class GR> 1173 GraphToEps<DefaultGraphToEpsTraits<GR> > 1174 graphToEps(GR &g,const std::string& file_name) 1178 1175 { 1179 1176 std::ostream* os = new std::ofstream(file_name.c_str()); … … 1182 1179 throw IoError("Cannot write file", file_name); 1183 1180 } 1184 return GraphToEps<DefaultGraphToEpsTraits<G > >1185 (DefaultGraphToEpsTraits<G >(g,*os,true));1181 return GraphToEps<DefaultGraphToEpsTraits<GR> > 1182 (DefaultGraphToEpsTraits<GR>(g,*os,true)); 1186 1183 } 1187 1184 -
lemon/graph_to_eps.h
r664 r908 685 685 #else 686 686 os << bits::getWinFormattedDate(); 687 os << std::endl; 687 688 #endif 688 689 } 689 os << std::endl;690 690 691 691 if (_autoArcWidthScale) { -
lemon/lgf_reader.h
r1067 r1069 102 102 }; 103 103 104 template <typename _G raph, bool _dir, typename _Map,104 template <typename _GR, bool _dir, typename _Map, 105 105 typename _Converter = DefaultConverter<typename _Map::Value> > 106 class GraphArcMapStorage : public MapStorageBase<typename _G raph::Edge> {106 class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> { 107 107 public: 108 108 typedef _Map Map; 109 109 typedef _Converter Converter; 110 typedef _G raph Graph;111 typedef typename G raph::Edge Item;110 typedef _GR GR; 111 typedef typename GR::Edge Item; 112 112 static const bool dir = _dir; 113 113 114 114 private: 115 const G raph& _graph;115 const GR& _graph; 116 116 Map& _map; 117 117 Converter _converter; 118 118 119 119 public: 120 GraphArcMapStorage(const G raph& graph, Map& map,120 GraphArcMapStorage(const GR& graph, Map& map, 121 121 const Converter& converter = Converter()) 122 122 : _graph(graph), _map(map), _converter(converter) {} … … 174 174 }; 175 175 176 template <typename G raph>176 template <typename GR> 177 177 struct GraphArcLookUpConverter { 178 const G raph& _graph;179 const std::map<std::string, typename G raph::Edge>& _map;180 181 GraphArcLookUpConverter(const G raph& graph,178 const GR& _graph; 179 const std::map<std::string, typename GR::Edge>& _map; 180 181 GraphArcLookUpConverter(const GR& graph, 182 182 const std::map<std::string, 183 typename G raph::Edge>& map)183 typename GR::Edge>& map) 184 184 : _graph(graph), _map(map) {} 185 185 186 typename G raph::Arc operator()(const std::string& str) {186 typename GR::Arc operator()(const std::string& str) { 187 187 if (str.empty() || (str[0] != '+' && str[0] != '-')) { 188 188 throw FormatError("Item must start with '+' or '-'"); 189 189 } 190 typename std::map<std::string, typename G raph::Edge>190 typename std::map<std::string, typename GR::Edge> 191 191 ::const_iterator it = _map.find(str.substr(1)); 192 192 if (it == _map.end()) { … … 388 388 } 389 389 390 template <typename D igraph>390 template <typename DGR> 391 391 class DigraphReader; 392 392 393 template <typename Digraph> 394 DigraphReader<Digraph> digraphReader(Digraph& digraph, 395 std::istream& is = std::cin); 396 template <typename Digraph> 397 DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn); 398 template <typename Digraph> 399 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn); 393 template <typename TDGR> 394 DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin); 395 template <typename TDGR> 396 DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn); 397 template <typename TDGR> 398 DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn); 400 399 401 400 /// \ingroup lemon_io … … 420 419 /// 421 420 ///\code 422 /// DigraphReader<D igraph>(digraph, std::cin).421 /// DigraphReader<DGR>(digraph, std::cin). 423 422 /// nodeMap("coordinates", coord_map). 424 423 /// arcMap("capacity", cap_map). … … 449 448 /// a single pass, because the arcs are not constructed when the node 450 449 /// maps are read. 451 template <typename _Digraph>450 template <typename DGR> 452 451 class DigraphReader { 453 452 public: 454 453 455 typedef _Digraph Digraph; 456 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 454 typedef DGR Digraph; 457 455 458 456 private: 459 457 458 TEMPLATE_DIGRAPH_TYPEDEFS(DGR); 460 459 461 460 std::istream* _is; … … 463 462 std::string _filename; 464 463 465 D igraph& _digraph;464 DGR& _digraph; 466 465 467 466 std::string _nodes_caption; … … 501 500 /// Construct a directed graph reader, which reads from the given 502 501 /// input stream. 503 DigraphReader(D igraph& digraph, std::istream& is = std::cin)502 DigraphReader(DGR& digraph, std::istream& is = std::cin) 504 503 : _is(&is), local_is(false), _digraph(digraph), 505 504 _use_nodes(false), _use_arcs(false), … … 510 509 /// Construct a directed graph reader, which reads from the given 511 510 /// file. 512 DigraphReader(D igraph& digraph, const std::string& fn)511 DigraphReader(DGR& digraph, const std::string& fn) 513 512 : _is(new std::ifstream(fn.c_str())), local_is(true), 514 513 _filename(fn), _digraph(digraph), … … 525 524 /// Construct a directed graph reader, which reads from the given 526 525 /// file. 527 DigraphReader(D igraph& digraph, const char* fn)526 DigraphReader(DGR& digraph, const char* fn) 528 527 : _is(new std::ifstream(fn)), local_is(true), 529 528 _filename(fn), _digraph(digraph), … … 561 560 private: 562 561 563 template <typename DGR>564 friend DigraphReader< DGR> digraphReader(DGR& digraph, std::istream& is);565 template <typename DGR>566 friend DigraphReader< DGR> digraphReader(DGR& digraph,567 const std::string& fn);568 template <typename DGR>569 friend DigraphReader< DGR> digraphReader(DGR& digraph, const char *fn);562 template <typename TDGR> 563 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is); 564 template <typename TDGR> 565 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 566 const std::string& fn); 567 template <typename TDGR> 568 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn); 570 569 571 570 DigraphReader(DigraphReader& other) … … 594 593 public: 595 594 596 /// \name Reading rules595 /// \name Reading Rules 597 596 /// @{ 598 597 … … 699 698 /// @} 700 699 701 /// \name Select section by name700 /// \name Select Section by Name 702 701 /// @{ 703 702 … … 728 727 /// @} 729 728 730 /// \name Using previously constructed node or arc set729 /// \name Using Previously Constructed Node or Arc Set 731 730 /// @{ 732 731 … … 848 847 readLine(); 849 848 } 850 line.putback(c); 849 if (readSuccess()) { 850 line.putback(c); 851 } 851 852 } 852 853 … … 1122 1123 public: 1123 1124 1124 /// \name Execution of the reader1125 /// \name Execution of the Reader 1125 1126 /// @{ 1126 1127 … … 1194 1195 1195 1196 }; 1197 1198 /// \ingroup lemon_io 1199 /// 1200 /// \brief Return a \ref DigraphReader class 1201 /// 1202 /// This function just returns a \ref DigraphReader class. 1203 /// 1204 /// With this function a digraph can be read from an 1205 /// \ref lgf-format "LGF" file or input stream with several maps and 1206 /// attributes. For example, there is network flow problem on a 1207 /// digraph, i.e. a digraph with a \e capacity map on the arcs and 1208 /// \e source and \e target nodes. This digraph can be read with the 1209 /// following code: 1210 /// 1211 ///\code 1212 ///ListDigraph digraph; 1213 ///ListDigraph::ArcMap<int> cm(digraph); 1214 ///ListDigraph::Node src, trg; 1215 ///digraphReader(digraph, std::cin). 1216 /// arcMap("capacity", cap). 1217 /// node("source", src). 1218 /// node("target", trg). 1219 /// run(); 1220 ///\endcode 1221 /// 1222 /// For a complete documentation, please see the \ref DigraphReader 1223 /// class documentation. 1224 /// \warning Don't forget to put the \ref DigraphReader::run() "run()" 1225 /// to the end of the parameter list. 1226 /// \relates DigraphReader 1227 /// \sa digraphReader(TDGR& digraph, const std::string& fn) 1228 /// \sa digraphReader(TDGR& digraph, const char* fn) 1229 template <typename TDGR> 1230 DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) { 1231 DigraphReader<TDGR> tmp(digraph, is); 1232 return tmp; 1233 } 1196 1234 1197 1235 /// \brief Return a \ref DigraphReader class … … 1199 1237 /// This function just returns a \ref DigraphReader class. 1200 1238 /// \relates DigraphReader 1201 template <typename Digraph> 1202 DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) { 1203 DigraphReader<Digraph> tmp(digraph, is); 1239 /// \sa digraphReader(TDGR& digraph, std::istream& is) 1240 template <typename TDGR> 1241 DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) { 1242 DigraphReader<TDGR> tmp(digraph, fn); 1204 1243 return tmp; 1205 1244 } … … 1209 1248 /// This function just returns a \ref DigraphReader class. 1210 1249 /// \relates DigraphReader 1211 template <typename Digraph>1212 DigraphReader<Digraph> digraphReader(Digraph& digraph,1213 const std::string&fn) {1214 DigraphReader< Digraph> tmp(digraph, fn);1250 /// \sa digraphReader(TDGR& digraph, std::istream& is) 1251 template <typename TDGR> 1252 DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) { 1253 DigraphReader<TDGR> tmp(digraph, fn); 1215 1254 return tmp; 1216 1255 } 1217 1256 1218 /// \brief Return a \ref DigraphReader class 1219 /// 1220 /// This function just returns a \ref DigraphReader class. 1221 /// \relates DigraphReader 1222 template <typename Digraph> 1223 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) { 1224 DigraphReader<Digraph> tmp(digraph, fn); 1225 return tmp; 1226 } 1227 1228 template <typename Graph> 1257 template <typename GR> 1229 1258 class GraphReader; 1230 1259 1231 template <typename Graph> 1232 GraphReader<Graph> graphReader(Graph& graph, 1233 std::istream& is = std::cin); 1234 template <typename Graph> 1235 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn); 1236 template <typename Graph> 1237 GraphReader<Graph> graphReader(Graph& graph, const char *fn); 1260 template <typename TGR> 1261 GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin); 1262 template <typename TGR> 1263 GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1264 template <typename TGR> 1265 GraphReader<TGR> graphReader(TGR& graph, const char *fn); 1238 1266 1239 1267 /// \ingroup lemon_io … … 1252 1280 /// arc map. Similarly, an attribute can be read into an arc, if 1253 1281 /// it's value is an edge label prefixed with \c '+' or \c '-'. 1254 template <typename _Graph>1282 template <typename GR> 1255 1283 class GraphReader { 1256 1284 public: 1257 1285 1258 typedef _Graph Graph; 1259 TEMPLATE_GRAPH_TYPEDEFS(Graph); 1286 typedef GR Graph; 1260 1287 1261 1288 private: 1289 1290 TEMPLATE_GRAPH_TYPEDEFS(GR); 1262 1291 1263 1292 std::istream* _is; … … 1265 1294 std::string _filename; 1266 1295 1267 G raph& _graph;1296 GR& _graph; 1268 1297 1269 1298 std::string _nodes_caption; … … 1303 1332 /// Construct an undirected graph reader, which reads from the given 1304 1333 /// input stream. 1305 GraphReader(G raph& graph, std::istream& is = std::cin)1334 GraphReader(GR& graph, std::istream& is = std::cin) 1306 1335 : _is(&is), local_is(false), _graph(graph), 1307 1336 _use_nodes(false), _use_edges(false), … … 1312 1341 /// Construct an undirected graph reader, which reads from the given 1313 1342 /// file. 1314 GraphReader(G raph& graph, const std::string& fn)1343 GraphReader(GR& graph, const std::string& fn) 1315 1344 : _is(new std::ifstream(fn.c_str())), local_is(true), 1316 1345 _filename(fn), _graph(graph), … … 1327 1356 /// Construct an undirected graph reader, which reads from the given 1328 1357 /// file. 1329 GraphReader(G raph& graph, const char* fn)1358 GraphReader(GR& graph, const char* fn) 1330 1359 : _is(new std::ifstream(fn)), local_is(true), 1331 1360 _filename(fn), _graph(graph), … … 1362 1391 1363 1392 private: 1364 template <typename GR>1365 friend GraphReader< GR> graphReader(GR& graph, std::istream& is);1366 template <typename GR>1367 friend GraphReader< GR> graphReader(GR& graph, const std::string& fn);1368 template <typename GR>1369 friend GraphReader< GR> graphReader(GR& graph, const char *fn);1393 template <typename TGR> 1394 friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is); 1395 template <typename TGR> 1396 friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1397 template <typename TGR> 1398 friend GraphReader<TGR> graphReader(TGR& graph, const char *fn); 1370 1399 1371 1400 GraphReader(GraphReader& other) … … 1394 1423 public: 1395 1424 1396 /// \name Reading rules1425 /// \name Reading Rules 1397 1426 /// @{ 1398 1427 … … 1459 1488 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1460 1489 _reader_bits::MapStorageBase<Edge>* backward_storage = 1461 new _reader_bits::GraphArcMapStorage<G raph, false, Map>(_graph, map);1490 new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map); 1462 1491 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 1463 1492 return *this; … … 1473 1502 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>(); 1474 1503 _reader_bits::MapStorageBase<Edge>* forward_storage = 1475 new _reader_bits::GraphArcMapStorage<G raph, true, Map, Converter>1504 new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter> 1476 1505 (_graph, map, converter); 1477 1506 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1478 1507 _reader_bits::MapStorageBase<Edge>* backward_storage = 1479 new _reader_bits::GraphArcMapStorage<G raph, false, Map, Converter>1508 new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter> 1480 1509 (_graph, map, converter); 1481 1510 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); … … 1535 1564 /// Add an arc reading rule to reader. 1536 1565 GraphReader& arc(const std::string& caption, Arc& arc) { 1537 typedef _reader_bits::GraphArcLookUpConverter<G raph> Converter;1566 typedef _reader_bits::GraphArcLookUpConverter<GR> Converter; 1538 1567 Converter converter(_graph, _edge_index); 1539 1568 _reader_bits::ValueStorageBase* storage = … … 1545 1574 /// @} 1546 1575 1547 /// \name Select section by name1576 /// \name Select Section by Name 1548 1577 /// @{ 1549 1578 … … 1574 1603 /// @} 1575 1604 1576 /// \name Using previously constructed node or edge set1605 /// \name Using Previously Constructed Node or Edge Set 1577 1606 /// @{ 1578 1607 … … 1695 1724 readLine(); 1696 1725 } 1697 line.putback(c); 1726 if (readSuccess()) { 1727 line.putback(c); 1728 } 1698 1729 } 1699 1730 … … 1969 2000 public: 1970 2001 1971 /// \name Execution of the reader2002 /// \name Execution of the Reader 1972 2003 /// @{ 1973 2004 … … 2043 2074 }; 2044 2075 2076 /// \ingroup lemon_io 2077 /// 2078 /// \brief Return a \ref GraphReader class 2079 /// 2080 /// This function just returns a \ref GraphReader class. 2081 /// 2082 /// With this function a graph can be read from an 2083 /// \ref lgf-format "LGF" file or input stream with several maps and 2084 /// attributes. For example, there is weighted matching problem on a 2085 /// graph, i.e. a graph with a \e weight map on the edges. This 2086 /// graph can be read with the following code: 2087 /// 2088 ///\code 2089 ///ListGraph graph; 2090 ///ListGraph::EdgeMap<int> weight(graph); 2091 ///graphReader(graph, std::cin). 2092 /// edgeMap("weight", weight). 2093 /// run(); 2094 ///\endcode 2095 /// 2096 /// For a complete documentation, please see the \ref GraphReader 2097 /// class documentation. 2098 /// \warning Don't forget to put the \ref GraphReader::run() "run()" 2099 /// to the end of the parameter list. 2100 /// \relates GraphReader 2101 /// \sa graphReader(TGR& graph, const std::string& fn) 2102 /// \sa graphReader(TGR& graph, const char* fn) 2103 template <typename TGR> 2104 GraphReader<TGR> graphReader(TGR& graph, std::istream& is) { 2105 GraphReader<TGR> tmp(graph, is); 2106 return tmp; 2107 } 2108 2045 2109 /// \brief Return a \ref GraphReader class 2046 2110 /// 2047 2111 /// This function just returns a \ref GraphReader class. 2048 2112 /// \relates GraphReader 2049 template <typename Graph> 2050 GraphReader<Graph> graphReader(Graph& graph, std::istream& is) { 2051 GraphReader<Graph> tmp(graph, is); 2113 /// \sa graphReader(TGR& graph, std::istream& is) 2114 template <typename TGR> 2115 GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) { 2116 GraphReader<TGR> tmp(graph, fn); 2052 2117 return tmp; 2053 2118 } … … 2057 2122 /// This function just returns a \ref GraphReader class. 2058 2123 /// \relates GraphReader 2059 template <typename Graph> 2060 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) { 2061 GraphReader<Graph> tmp(graph, fn); 2062 return tmp; 2063 } 2064 2065 /// \brief Return a \ref GraphReader class 2066 /// 2067 /// This function just returns a \ref GraphReader class. 2068 /// \relates GraphReader 2069 template <typename Graph> 2070 GraphReader<Graph> graphReader(Graph& graph, const char* fn) { 2071 GraphReader<Graph> tmp(graph, fn); 2124 /// \sa graphReader(TGR& graph, std::istream& is) 2125 template <typename TGR> 2126 GraphReader<TGR> graphReader(TGR& graph, const char* fn) { 2127 GraphReader<TGR> tmp(graph, fn); 2072 2128 return tmp; 2073 2129 } … … 2168 2224 public: 2169 2225 2170 /// \name Section readers2226 /// \name Section Readers 2171 2227 /// @{ 2172 2228 … … 2259 2315 readLine(); 2260 2316 } 2261 line.putback(c); 2317 if (readSuccess()) { 2318 line.putback(c); 2319 } 2262 2320 } 2263 2321 … … 2265 2323 2266 2324 2267 /// \name Execution of the reader2325 /// \name Execution of the Reader 2268 2326 /// @{ 2269 2327 … … 2324 2382 }; 2325 2383 2384 /// \ingroup lemon_io 2385 /// 2326 2386 /// \brief Return a \ref SectionReader class 2327 2387 /// 2328 2388 /// This function just returns a \ref SectionReader class. 2389 /// 2390 /// Please see SectionReader documentation about the custom section 2391 /// input. 2392 /// 2329 2393 /// \relates SectionReader 2394 /// \sa sectionReader(const std::string& fn) 2395 /// \sa sectionReader(const char *fn) 2330 2396 inline SectionReader sectionReader(std::istream& is) { 2331 2397 SectionReader tmp(is); … … 2337 2403 /// This function just returns a \ref SectionReader class. 2338 2404 /// \relates SectionReader 2405 /// \sa sectionReader(std::istream& is) 2339 2406 inline SectionReader sectionReader(const std::string& fn) { 2340 2407 SectionReader tmp(fn); … … 2346 2413 /// This function just returns a \ref SectionReader class. 2347 2414 /// \relates SectionReader 2415 /// \sa sectionReader(std::istream& is) 2348 2416 inline SectionReader sectionReader(const char* fn) { 2349 2417 SectionReader tmp(fn); … … 2447 2515 2448 2516 2449 /// \name Node sections2517 /// \name Node Sections 2450 2518 /// @{ 2451 2519 … … 2473 2541 /// @} 2474 2542 2475 /// \name Arc/Edge sections2543 /// \name Arc/Edge Sections 2476 2544 /// @{ 2477 2545 … … 2531 2599 /// @} 2532 2600 2533 /// \name Attribute sections2601 /// \name Attribute Sections 2534 2602 /// @{ 2535 2603 … … 2557 2625 /// @} 2558 2626 2559 /// \name Extra sections2627 /// \name Extra Sections 2560 2628 /// @{ 2561 2629 … … 2600 2668 readLine(); 2601 2669 } 2602 line.putback(c); 2670 if (readSuccess()) { 2671 line.putback(c); 2672 } 2603 2673 } 2604 2674 … … 2631 2701 public: 2632 2702 2633 /// \name Execution of the contents reader2703 /// \name Execution of the Contents Reader 2634 2704 /// @{ 2635 2705 -
lemon/lgf_reader.h
r646 r1069 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 965 965 int index = 0; 966 966 while (_reader_bits::readToken(line, map)) { 967 if(map == "-") { 968 if(index!=0) 969 throw FormatError("'-' is not allowed as a map name"); 970 else if (line >> std::ws >> c) 971 throw FormatError("Extra character at the end of line"); 972 else break; 973 } 967 974 if (maps.find(map) != maps.end()) { 968 975 std::ostringstream msg; … … 1835 1842 int index = 0; 1836 1843 while (_reader_bits::readToken(line, map)) { 1844 if(map == "-") { 1845 if(index!=0) 1846 throw FormatError("'-' is not allowed as a map name"); 1847 else if (line >> std::ws >> c) 1848 throw FormatError("Extra character at the end of line"); 1849 else break; 1850 } 1837 1851 if (maps.find(map) != maps.end()) { 1838 1852 std::ostringstream msg;
Note: See TracChangeset
for help on using the changeset viewer.