Changeset 771:17e36e175725 in lemon-1.1
- Timestamp:
- 12/20/11 17:35:45 (13 years ago)
- Branch:
- default
- Parents:
- 766:2eebc8f7dca5 (diff), 764: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
- Files:
-
- 22 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/lgf.dox
r756 r757 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). -
doc/lgf.dox
r440 r757 64 64 \endcode 65 65 66 The \c \@arcs section is very similar to the \c \@nodes section, 67 it again starts with a header line describing the names of the maps, 68 butthe \c "label" map is not obligatory here. The following lines69 describe the arcs. The first two tokens of each line are 70 the sourceand the target node of the arc, respectively, then come the map66 The \c \@arcs section is very similar to the \c \@nodes section, it 67 again starts with a header line describing the names of the maps, but 68 the \c "label" map is not obligatory here. The following lines 69 describe the arcs. The first two tokens of each line are the source 70 and the target node of the arc, respectively, then come the map 71 71 values. The source and target tokens must be node labels. 72 72 … … 79 79 \endcode 80 80 81 If there is no map in the \c \@arcs section at all, then it must be 82 indicated by a sole '-' sign in the first line. 83 84 \code 85 @arcs 86 - 87 1 2 88 1 3 89 2 3 90 \endcode 91 81 92 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can 82 93 also store the edge set of an undirected graph. In such case there is 83 94 a conventional method for store arc maps in the file, if two columns 84 ha sthe same caption with \c '+' and \c '-' prefix, then these columns95 have the same caption with \c '+' and \c '-' prefix, then these columns 85 96 can be regarded as the values of an arc map. 86 97 -
lemon/Makefile.am
r763 r771 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
r703 r771 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
r727 r728 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
r514 r728 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
r731 r734 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
r672 r734 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
r737 r738 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
r576 r738 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
r713 r714 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
r609 r714 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
r756 r757 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
r591 r757 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; -
test/CMakeLists.txt
r756 r757 1 1 INCLUDE_DIRECTORIES( 2 ${ CMAKE_SOURCE_DIR}2 ${PROJECT_SOURCE_DIR} 3 3 ${PROJECT_BINARY_DIR} 4 4 ) 5 5 6 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon) 6 LINK_DIRECTORIES( 7 ${PROJECT_BINARY_DIR}/lemon 8 ) 9 10 SET(TEST_WITH_VALGRIND "NO" CACHE STRING 11 "Run the test with valgrind (YES/NO).") 12 SET(VALGRIND_FLAGS "" CACHE STRING "Valgrind flags used by the tests.") 7 13 8 14 SET(TESTS 15 adaptors_test 9 16 bfs_test 17 circulation_test 18 connectivity_test 10 19 counter_test 11 20 dfs_test … … 13 22 dijkstra_test 14 23 dim_test 24 edge_set_test 15 25 error_test 26 euler_test 27 gomory_hu_test 16 28 graph_copy_test 17 29 graph_test 18 30 graph_utils_test 31 hao_orlin_test 19 32 heap_test 20 33 kruskal_test 21 34 lgf_test 22 35 maps_test 36 matching_test 37 min_cost_arborescence_test 38 min_cost_flow_test 39 path_test 40 preflow_test 41 radix_sort_test 23 42 random_test 24 path_test43 suurballe_test 25 44 time_measure_test 26 unionfind_test) 45 unionfind_test 46 ) 47 48 IF(LEMON_HAVE_LP) 49 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 50 ADD_EXECUTABLE(lp_test lp_test.cc) 51 ELSE() 52 ADD_EXECUTABLE(lp_test EXCLUDE_FROM_ALL lp_test.cc) 53 ENDIF() 54 55 SET(LP_TEST_LIBS lemon) 56 57 IF(LEMON_HAVE_GLPK) 58 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES}) 59 ENDIF() 60 IF(LEMON_HAVE_CPLEX) 61 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES}) 62 ENDIF() 63 IF(LEMON_HAVE_CLP) 64 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES}) 65 ENDIF() 66 67 TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS}) 68 ADD_TEST(lp_test lp_test) 69 ADD_DEPENDENCIES(check lp_test) 70 71 IF(WIN32 AND LEMON_HAVE_GLPK) 72 GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) 73 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 74 ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD 75 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH} 76 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH} 77 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} 78 ) 79 ENDIF() 80 81 IF(WIN32 AND LEMON_HAVE_CPLEX) 82 GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) 83 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 84 ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD 85 COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} 86 ) 87 ENDIF() 88 ENDIF() 89 90 IF(LEMON_HAVE_MIP) 91 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 92 ADD_EXECUTABLE(mip_test mip_test.cc) 93 ELSE() 94 ADD_EXECUTABLE(mip_test EXCLUDE_FROM_ALL mip_test.cc) 95 ENDIF() 96 97 SET(MIP_TEST_LIBS lemon) 98 99 IF(LEMON_HAVE_GLPK) 100 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES}) 101 ENDIF() 102 IF(LEMON_HAVE_CPLEX) 103 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES}) 104 ENDIF() 105 IF(LEMON_HAVE_CBC) 106 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES}) 107 ENDIF() 108 109 TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS}) 110 ADD_TEST(mip_test mip_test) 111 ADD_DEPENDENCIES(check mip_test) 112 113 IF(WIN32 AND LEMON_HAVE_GLPK) 114 GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) 115 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 116 ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD 117 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH} 118 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH} 119 COMMAND ${CMAKE_COMMAND} -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} 120 ) 121 ENDIF() 122 123 IF(WIN32 AND LEMON_HAVE_CPLEX) 124 GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) 125 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 126 ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD 127 COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} 128 ) 129 ENDIF() 130 ENDIF() 27 131 28 132 FOREACH(TEST_NAME ${TESTS}) 29 ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) 133 IF(${CMAKE_BUILD_TYPE} STREQUAL "Maintainer") 134 ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc) 135 ELSE() 136 ADD_EXECUTABLE(${TEST_NAME} EXCLUDE_FROM_ALL ${TEST_NAME}.cc) 137 ENDIF() 30 138 TARGET_LINK_LIBRARIES(${TEST_NAME} lemon) 31 ADD_TEST(${TEST_NAME} ${TEST_NAME}) 32 ENDFOREACH(TEST_NAME) 139 IF(TEST_WITH_VALGRIND) 140 ADD_TEST(${TEST_NAME} 141 valgrind --error-exitcode=1 ${VALGRIND_FLAGS} 142 ${CMAKE_CURRENT_BINARY_DIR}/${TEST_NAME} ) 143 ELSE() 144 ADD_TEST(${TEST_NAME} ${TEST_NAME}) 145 ENDIF() 146 ADD_DEPENDENCIES(check ${TEST_NAME}) 147 ENDFOREACH() -
test/CMakeLists.txt
r752 r757 32 32 heap_test 33 33 kruskal_test 34 lgf_test 34 35 maps_test 35 36 matching_test -
test/Makefile.am
r756 r771 4 4 noinst_HEADERS += \ 5 5 test/graph_test.h \ 6 6 test/test_tools.h 7 7 8 8 check_PROGRAMS += \ 9 test/adaptors_test \ 9 10 test/bfs_test \ 10 test/counter_test \ 11 test/circulation_test \ 12 test/connectivity_test \ 13 test/counter_test \ 11 14 test/dfs_test \ 12 15 test/digraph_test \ 13 16 test/dijkstra_test \ 14 test/dim_test \ 17 test/dim_test \ 18 test/edge_set_test \ 15 19 test/error_test \ 20 test/euler_test \ 21 test/gomory_hu_test \ 16 22 test/graph_copy_test \ 17 23 test/graph_test \ 18 24 test/graph_utils_test \ 25 test/hao_orlin_test \ 19 26 test/heap_test \ 20 27 test/kruskal_test \ 21 28 test/lgf_test \ 22 test/maps_test \ 23 test/random_test \ 24 test/path_test \ 25 test/test_tools_fail \ 26 test/test_tools_pass \ 27 test/time_measure_test \ 29 test/maps_test \ 30 test/matching_test \ 31 test/min_cost_arborescence_test \ 32 test/min_cost_flow_test \ 33 test/path_test \ 34 test/preflow_test \ 35 test/radix_sort_test \ 36 test/random_test \ 37 test/suurballe_test \ 38 test/test_tools_fail \ 39 test/test_tools_pass \ 40 test/time_measure_test \ 28 41 test/unionfind_test 42 43 test_test_tools_pass_DEPENDENCIES = demo 44 45 if HAVE_LP 46 check_PROGRAMS += test/lp_test 47 endif HAVE_LP 48 if HAVE_MIP 49 check_PROGRAMS += test/mip_test 50 endif HAVE_MIP 29 51 30 52 TESTS += $(check_PROGRAMS) 31 53 XFAIL_TESTS += test/test_tools_fail$(EXEEXT) 32 54 55 test_adaptors_test_SOURCES = test/adaptors_test.cc 33 56 test_bfs_test_SOURCES = test/bfs_test.cc 57 test_circulation_test_SOURCES = test/circulation_test.cc 34 58 test_counter_test_SOURCES = test/counter_test.cc 59 test_connectivity_test_SOURCES = test/connectivity_test.cc 35 60 test_dfs_test_SOURCES = test/dfs_test.cc 36 61 test_digraph_test_SOURCES = test/digraph_test.cc 37 62 test_dijkstra_test_SOURCES = test/dijkstra_test.cc 38 63 test_dim_test_SOURCES = test/dim_test.cc 64 test_edge_set_test_SOURCES = test/edge_set_test.cc 39 65 test_error_test_SOURCES = test/error_test.cc 66 test_euler_test_SOURCES = test/euler_test.cc 67 test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc 40 68 test_graph_copy_test_SOURCES = test/graph_copy_test.cc 41 69 test_graph_test_SOURCES = test/graph_test.cc … … 43 71 test_heap_test_SOURCES = test/heap_test.cc 44 72 test_kruskal_test_SOURCES = test/kruskal_test.cc 73 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 45 74 test_lgf_test_SOURCES = test/lgf_test.cc 75 test_lp_test_SOURCES = test/lp_test.cc 46 76 test_maps_test_SOURCES = test/maps_test.cc 77 test_mip_test_SOURCES = test/mip_test.cc 78 test_matching_test_SOURCES = test/matching_test.cc 79 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 80 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc 47 81 test_path_test_SOURCES = test/path_test.cc 82 test_preflow_test_SOURCES = test/preflow_test.cc 83 test_radix_sort_test_SOURCES = test/radix_sort_test.cc 84 test_suurballe_test_SOURCES = test/suurballe_test.cc 48 85 test_random_test_SOURCES = test/random_test.cc 49 86 test_test_tools_fail_SOURCES = test/test_tools_fail.cc -
test/Makefile.am
r647 r771 26 26 test/heap_test \ 27 27 test/kruskal_test \ 28 test/lgf_test \ 28 29 test/maps_test \ 29 30 test/matching_test \ … … 71 72 test_kruskal_test_SOURCES = test/kruskal_test.cc 72 73 test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc 74 test_lgf_test_SOURCES = test/lgf_test.cc 73 75 test_lp_test_SOURCES = test/lp_test.cc 74 76 test_maps_test_SOURCES = test/maps_test.cc -
test/dfs_test.cc
r737 r738 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). … … 66 66 Node s, t; 67 67 Arc e; 68 int l ;68 int l, i; 69 69 bool b; 70 70 DType::DistMap d(G); 71 71 DType::PredMap p(G); 72 72 Path<Digraph> pp; 73 concepts::ReadMap<Arc,bool> am; 73 74 74 75 { 75 76 DType dfs_test(G); 77 const DType& const_dfs_test = dfs_test; 76 78 77 79 dfs_test.run(s); … … 79 81 dfs_test.run(); 80 82 81 l = dfs_test.dist(t); 82 e = dfs_test.predArc(t); 83 s = dfs_test.predNode(t); 84 b = dfs_test.reached(t); 85 d = dfs_test.distMap(); 86 p = dfs_test.predMap(); 87 pp = dfs_test.path(t); 83 dfs_test.init(); 84 dfs_test.addSource(s); 85 e = dfs_test.processNextArc(); 86 e = const_dfs_test.nextArc(); 87 b = const_dfs_test.emptyQueue(); 88 i = const_dfs_test.queueSize(); 89 90 dfs_test.start(); 91 dfs_test.start(t); 92 dfs_test.start(am); 93 94 l = const_dfs_test.dist(t); 95 e = const_dfs_test.predArc(t); 96 s = const_dfs_test.predNode(t); 97 b = const_dfs_test.reached(t); 98 d = const_dfs_test.distMap(); 99 p = const_dfs_test.predMap(); 100 pp = const_dfs_test.path(t); 88 101 } 89 102 { … … 92 105 ::SetDistMap<concepts::ReadWriteMap<Node,int> > 93 106 ::SetReachedMap<concepts::ReadWriteMap<Node,bool> > 107 ::SetStandardProcessedMap 94 108 ::SetProcessedMap<concepts::WriteMap<Node,bool> > 95 ::SetStandardProcessedMap96 109 ::Create dfs_test(G); 110 111 concepts::ReadWriteMap<Node,Arc> pred_map; 112 concepts::ReadWriteMap<Node,int> dist_map; 113 concepts::ReadWriteMap<Node,bool> reached_map; 114 concepts::WriteMap<Node,bool> processed_map; 115 116 dfs_test 117 .predMap(pred_map) 118 .distMap(dist_map) 119 .reachedMap(reached_map) 120 .processedMap(processed_map); 97 121 98 122 dfs_test.run(s); 99 123 dfs_test.run(s,t); 100 124 dfs_test.run(); 125 dfs_test.init(); 126 127 dfs_test.addSource(s); 128 e = dfs_test.processNextArc(); 129 e = dfs_test.nextArc(); 130 b = dfs_test.emptyQueue(); 131 i = dfs_test.queueSize(); 132 133 dfs_test.start(); 134 dfs_test.start(t); 135 dfs_test.start(am); 101 136 102 137 l = dfs_test.dist(t); -
test/dfs_test.cc
r577 r738 51 51 "@attributes\n" 52 52 "source 0\n" 53 "target 5\n"; 53 "target 5\n" 54 "source1 6\n" 55 "target1 3\n"; 56 54 57 55 58 void checkDfsCompile() … … 180 183 Digraph G; 181 184 Node s, t; 185 Node s1, t1; 182 186 183 187 std::istringstream input(test_lgf); … … 185 189 node("source", s). 186 190 node("target", t). 191 node("source1", s1). 192 node("target1", t1). 187 193 run(); 188 194 … … 211 217 212 218 { 219 Dfs<Digraph> dfs(G); 220 check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6."); 221 } 222 223 { 213 224 NullMap<Node,Arc> myPredMap; 214 225 dfs(G).predMap(myPredMap).run(s); -
test/graph_copy_test.cc
r731 r734 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). -
test/graph_copy_test.cc
r440 r734 30 30 const int nn = 10; 31 31 32 // Build a digraph 32 33 SmartDigraph from; 33 34 SmartDigraph::NodeMap<int> fnm(from); … … 52 53 } 53 54 55 // Test digraph copy 54 56 ListDigraph to; 55 57 ListDigraph::NodeMap<int> tnm(to); … … 69 71 nodeCrossRef(ncr).arcCrossRef(ecr). 70 72 node(fn, tn).arc(fa, ta).run(); 73 74 check(countNodes(from) == countNodes(to), "Wrong copy."); 75 check(countArcs(from) == countArcs(to), "Wrong copy."); 71 76 72 77 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 91 96 check(tn == nr[fn], "Wrong copy."); 92 97 check(ta == er[fa], "Wrong copy."); 98 99 // Test repeated copy 100 digraphCopy(from, to).run(); 101 102 check(countNodes(from) == countNodes(to), "Wrong copy."); 103 check(countArcs(from) == countArcs(to), "Wrong copy."); 93 104 } 94 105 … … 96 107 const int nn = 10; 97 108 109 // Build a graph 98 110 SmartGraph from; 99 111 SmartGraph::NodeMap<int> fnm(from); … … 123 135 } 124 136 137 // Test graph copy 125 138 ListGraph to; 126 139 ListGraph::NodeMap<int> tnm(to); … … 144 157 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 145 158 node(fn, tn).arc(fa, ta).edge(fe, te).run(); 159 160 check(countNodes(from) == countNodes(to), "Wrong copy."); 161 check(countEdges(from) == countEdges(to), "Wrong copy."); 162 check(countArcs(from) == countArcs(to), "Wrong copy."); 146 163 147 164 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { … … 181 198 check(ta == ar[fa], "Wrong copy."); 182 199 check(te == er[fe], "Wrong copy."); 200 201 // Test repeated copy 202 graphCopy(from, to).run(); 203 204 check(countNodes(from) == countNodes(to), "Wrong copy."); 205 check(countEdges(from) == countEdges(to), "Wrong copy."); 206 check(countArcs(from) == countArcs(to), "Wrong copy."); 183 207 } 184 208
Note: See TracChangeset
for help on using the changeset viewer.