Changes in lemon/list_graph.h [73:c56b7389dc78:57:c1acf0018c0a] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r73 r57 112 112 113 113 114 void first(Arc& arc) const {114 void first(Arc& e) const { 115 115 int n; 116 116 for(n = first_node; 117 117 n!=-1 && nodes[n].first_in == -1; 118 118 n = nodes[n].next); 119 arc.id = (n == -1) ? -1 : nodes[n].first_in;119 e.id = (n == -1) ? -1 : nodes[n].first_in; 120 120 } 121 121 … … 294 294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; 295 295 296 /// \addtogroup graphs296 /// \addtogroup digraphs 297 297 /// @{ 298 298 299 ///A general directed graph structure. 300 301 ///\ref ListDigraph is a simple and fast <em>directed graph</em> 302 ///implementation based on static linked lists that are stored in 303 ///\c std::vector structures. 299 ///A list digraph class. 300 301 ///This is a simple and fast digraph implementation. 304 302 /// 305 303 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it 306 ///also provides several useful additionalfunctionalities.307 /// Most of the member functions and nested classes are documented308 /// only in the concept class.304 ///also provides several additional useful extra functionalities. 305 ///The most of the member functions and nested classes are 306 ///documented only in the concept class. 309 307 /// 310 308 ///An important extra feature of this digraph implementation is that 311 309 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 312 310 /// 313 ///\sa concepts::Digraph 311 ///\sa concepts::Digraph. 314 312 315 313 class ListDigraph : public ExtendedListDigraphBase { 316 314 private: 317 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.318 319 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. 316 317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. 320 318 /// 321 319 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 322 320 ///\brief Assignment of ListDigraph to another one is \e not allowed. 323 ///Use copyDigraph() instead.321 ///Use DigraphCopy() instead. 324 322 325 323 ///Assignment of ListDigraph to another one is \e not allowed. 326 ///Use copyDigraph() instead.324 ///Use DigraphCopy() instead. 327 325 void operator=(const ListDigraph &) {} 328 326 public: … … 338 336 ///Add a new node to the digraph. 339 337 340 /// Add a new node to the digraph.341 /// \return the new node.338 /// \return the new node. 339 /// 342 340 Node addNode() { return Parent::addNode(); } 343 341 … … 351 349 } 352 350 353 /// Change the target of \c e to \c n354 355 /// Change the target of \c e to \c n351 /// Changes the target of \c e to \c n 352 353 /// Changes the target of \c e to \c n 356 354 /// 357 355 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 358 356 ///the changed arc remain valid. However <tt>InArcIt</tt>s are 359 357 ///invalidated. 360 ///361 358 ///\warning This functionality cannot be used together with the Snapshot 362 359 ///feature. … … 364 361 Parent::changeTarget(e,n); 365 362 } 366 /// Change the source of \c e to \c n367 368 /// Change the source of \c e to \c n363 /// Changes the source of \c e to \c n 364 365 /// Changes the source of \c e to \c n 369 366 /// 370 367 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing 371 368 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are 372 369 ///invalidated. 373 ///374 370 ///\warning This functionality cannot be used together with the Snapshot 375 371 ///feature. … … 383 379 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are 384 380 ///invalidated. 385 ///386 381 ///\warning This functionality cannot be used together with the Snapshot 387 382 ///feature. … … 392 387 } 393 388 394 /// Reserve memory for nodes. 395 396 /// Using this function it is possible to avoid the superfluous memory 389 /// Using this it is possible to avoid the superfluous memory 397 390 /// allocation: if you know that the digraph you want to build will 398 391 /// be very large (e.g. it will contain millions of nodes and/or arcs) … … 402 395 void reserveNode(int n) { nodes.reserve(n); }; 403 396 404 /// Reserve memory for arcs. 405 406 /// Using this function it is possible to avoid the superfluous memory 397 /// \brief Using this it is possible to avoid the superfluous memory 398 /// allocation. 399 400 /// Using this it is possible to avoid the superfluous memory 407 401 /// allocation: if you know that the digraph you want to build will 408 402 /// be very large (e.g. it will contain millions of nodes and/or arcs) … … 415 409 416 410 ///This function contracts two nodes. 411 /// 417 412 ///Node \p b will be removed but instead of deleting 418 413 ///incident arcs, they will be joined to \p a. … … 420 415 ///means that loops will be removed. 421 416 /// 422 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 417 ///\note The <tt>ArcIt</tt>s 418 ///referencing a moved arc remain 423 419 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 424 420 ///may be invalidated. 425 ///426 421 ///\warning This functionality cannot be used together with the Snapshot 427 422 ///feature. … … 458 453 /// 459 454 ///\warning This functionality cannot be used together with the 460 ///Snapshot feature. 461 /// 462 ///\todo It could be implemented in a bit faster way. 455 ///Snapshot feature. \todo It could be implemented in a bit 456 ///faster way. 463 457 Node split(Node n, bool connect = true) { 464 458 Node b = addNode(); … … 478 472 ///the digraph, then the original arc is re-targeted to \c 479 473 ///b. Finally an arc from \c b to the original target is added. 480 /// 481 ///\return The newly created node. 482 /// 483 ///\warning This functionality cannot be used together with the 484 ///Snapshot feature. 474 ///\return The newly created node. 475 ///\warning This functionality 476 ///cannot be used together with the Snapshot feature. 485 477 Node split(Arc e) { 486 478 Node b = addNode(); … … 491 483 492 484 /// \brief Class to make a snapshot of the digraph and restore 493 /// it later. 494 /// 495 /// Class to make a snapshot of the digraph and restore it later. 485 /// to it later. 486 /// 487 /// Class to make a snapshot of the digraph and to restore it 488 /// later. 496 489 /// 497 490 /// The newly added nodes and arcs can be removed using the 498 491 /// restore() function. 499 492 /// 500 /// \warning Arc and node deletions and other modifications (e.g. 501 /// contracting, splitting, reversing arcs or nodes) cannot be 502 /// restored. These events invalidate the snapshot. 493 /// \warning Arc and node deletions cannot be restored. This 494 /// events invalidate the snapshot. 503 495 class Snapshot { 504 496 protected: … … 785 777 Edge() {} 786 778 Edge (Invalid) { id = -1; } 787 bool operator==(const Edge& edge) const {return id == edge.id;}788 bool operator!=(const Edge& edge) const {return id != edge.id;}789 bool operator<(const Edge& edge) const {return id < edge.id;}779 bool operator==(const Edge& arc) const {return id == arc.id;} 780 bool operator!=(const Edge& arc) const {return id != arc.id;} 781 bool operator<(const Edge& arc) const {return id < arc.id;} 790 782 }; 791 783 … … 918 910 919 911 void firstInc(Edge &e, bool& d, const Node& v) const { 920 int a= nodes[v.id].first_out;921 if ( a!= -1 ) {922 e.id = a/ 2;923 d = (( a& 1) == 1);912 int de = nodes[v.id].first_out; 913 if (de != -1 ) { 914 e.id = de / 2; 915 d = ((de & 1) == 1); 924 916 } else { 925 917 e.id = -1; … … 928 920 } 929 921 void nextInc(Edge &e, bool& d) const { 930 int a= (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);931 if ( a!= -1 ) {932 e.id = a/ 2;933 d = (( a& 1) == 1);922 int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 923 if (de != -1 ) { 924 e.id = de / 2; 925 d = ((de & 1) == 1); 934 926 } else { 935 927 e.id = -1; … … 1017 1009 } 1018 1010 1019 void erase(const Edge& edge) {1020 int n = edge.id * 2;1011 void erase(const Edge& arc) { 1012 int n = arc.id * 2; 1021 1013 1022 1014 if (arcs[n].next_out != -1) { … … 1098 1090 }; 1099 1091 1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 1093 // ExtendedListGraphBase; 1094 1100 1095 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 1101 1096 1102 1097 1103 /// \addtogroup graphs 1098 1099 /// \addtogroup digraphs 1104 1100 /// @{ 1105 1101 1106 ///A general undirected graph structure. 1107 1108 ///\ref ListGraph is a simple and fast <em>undirected graph</em> 1109 ///implementation based on static linked lists that are stored in 1110 ///\c std::vector structures. 1102 ///An undirected list digraph class. 1103 1104 ///This is a simple and fast undirected digraph implementation. 1111 1105 /// 1112 ///It conforms to the \ref concepts::Graph "Graph concept" and it 1113 ///also provides several useful additional functionalities. 1114 ///Most of the member functions and nested classes are documented 1115 ///only in the concept class. 1116 /// 1117 ///An important extra feature of this graph implementation is that 1106 ///An important extra feature of this digraph implementation is that 1118 1107 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 1119 1108 /// 1120 ///\sa concepts::Graph 1121 1109 ///It conforms to the 1110 ///\ref concepts::Graph "Graph concept". 1111 /// 1112 ///\sa concepts::Graph. 1113 /// 1122 1114 class ListGraph : public ExtendedListGraphBase { 1123 1115 private: 1124 ///ListGraph is \e not copy constructible. Use copyGraph() instead.1125 1126 ///ListGraph is \e not copy constructible. Use copyGraph() instead.1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. 1117 1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. 1127 1119 /// 1128 1120 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 1129 1121 ///\brief Assignment of ListGraph to another one is \e not allowed. 1130 ///Use copyGraph() instead.1122 ///Use GraphCopy() instead. 1131 1123 1132 1124 ///Assignment of ListGraph to another one is \e not allowed. 1133 ///Use copyGraph() instead.1125 ///Use GraphCopy() instead. 1134 1126 void operator=(const ListGraph &) {} 1135 1127 public: … … 1142 1134 typedef ExtendedListGraphBase Parent; 1143 1135 1144 typedef Parent::OutArcIt IncEdgeIt; 1145 1146 /// \brief Add a new node to the graph. 1147 /// 1148 /// Add a new node to the graph. 1136 typedef Parent::OutArcIt IncArcIt; 1137 1138 /// \brief Add a new node to the digraph. 1139 /// 1149 1140 /// \return the new node. 1141 /// 1150 1142 Node addNode() { return Parent::addNode(); } 1151 1143 1152 /// \brief Add a new edge to the graph.1153 /// 1154 /// Add a new edge to thegraph with source node \c s1144 /// \brief Add a new edge to the digraph. 1145 /// 1146 /// Add a new arc to the digraph with source node \c s 1155 1147 /// and target node \c t. 1156 1148 /// \return the new edge. … … 1158 1150 return Parent::addEdge(s, t); 1159 1151 } 1160 /// \brief Change the source of \c e to \c n1161 /// 1162 /// This function changes the source of \c e to \c n.1152 /// \brief Changes the source of \c e to \c n 1153 /// 1154 /// Changes the source of \c e to \c n 1163 1155 /// 1164 1156 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1165 1157 ///referencing the changed arc remain 1166 1158 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1167 ///1168 ///\warning This functionality cannot be used together with the1169 ///Snapshot feature.1170 1159 void changeSource(Edge e, Node n) { 1171 1160 Parent::changeSource(e,n); 1172 1161 } 1173 /// \brief Change the target of \c e to \c n1174 /// 1175 /// This function changes the target of \c e to \c n.1162 /// \brief Changes the target of \c e to \c n 1163 /// 1164 /// Changes the target of \c e to \c n 1176 1165 /// 1177 1166 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain 1178 1167 /// valid. However the other iterators may be invalidated. 1179 ///1180 ///\warning This functionality cannot be used together with the1181 ///Snapshot feature.1182 1168 void changeTarget(Edge e, Node n) { 1183 1169 Parent::changeTarget(e,n); 1184 1170 } 1185 /// \brief Change the source of \c e to \c n1186 /// 1187 /// This function changes the source of \c e to \c n.1188 /// It also changes the propernode of the represented edge.1171 /// \brief Changes the source of \c e to \c n 1172 /// 1173 /// Changes the source of \c e to \c n. It changes the proper 1174 /// node of the represented edge. 1189 1175 /// 1190 1176 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1191 1177 ///referencing the changed arc remain 1192 1178 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1193 ///1194 ///\warning This functionality cannot be used together with the1195 ///Snapshot feature.1196 1179 void changeSource(Arc e, Node n) { 1197 1180 if (Parent::direction(e)) { … … 1201 1184 } 1202 1185 } 1203 /// \brief Change the target of \c e to \c n1204 /// 1205 /// This function changes the target of \c e to \c n.1206 /// It also changes the propernode of the represented edge.1186 /// \brief Changes the target of \c e to \c n 1187 /// 1188 /// Changes the target of \c e to \c n. It changes the proper 1189 /// node of the represented edge. 1207 1190 /// 1208 1191 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s 1209 1192 ///referencing the changed arc remain 1210 1193 ///valid. However <tt>InArcIt</tt>s are invalidated. 1211 ///1212 ///\warning This functionality cannot be used together with the1213 ///Snapshot feature.1214 1194 void changeTarget(Arc e, Node n) { 1215 1195 if (Parent::direction(e)) { … … 1222 1202 /// 1223 1203 /// This function contracts two nodes. 1204 /// 1224 1205 /// Node \p b will be removed but instead of deleting 1225 1206 /// its neighboring arcs, they will be joined to \p a. … … 1229 1210 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 1230 1211 /// valid. 1231 ///1232 ///\warning This functionality cannot be used together with the1233 ///Snapshot feature.1234 1212 void contract(Node a, Node b, bool r = true) { 1235 for(Inc EdgeIt e(*this, b); e!=INVALID;) {1236 Inc EdgeIt f = e; ++f;1213 for(IncArcIt e(*this, b); e!=INVALID;) { 1214 IncArcIt f = e; ++f; 1237 1215 if (r && runningNode(e) == a) { 1238 1216 erase(e); … … 1248 1226 1249 1227 1250 /// \brief Class to make a snapshot of the graph and restore 1251 /// it later. 1252 /// 1253 /// Class to make a snapshot of the graph and restore it later. 1228 /// \brief Class to make a snapshot of the digraph and restore 1229 /// to it later. 1230 /// 1231 /// Class to make a snapshot of the digraph and to restore it 1232 /// later. 1254 1233 /// 1255 1234 /// The newly added nodes and edges can be removed 1256 1235 /// using the restore() function. 1257 1236 /// 1258 /// \warning Edge and node deletions and other modifications 1259 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1260 /// restored. These events invalidate the snapshot. 1237 /// \warning Arc and node deletions cannot be restored. This 1238 /// events invalidate the snapshot. 1261 1239 class Snapshot { 1262 1240 protected: … … 1326 1304 protected: 1327 1305 1328 virtual void add(const Edge& edge) {1329 snapshot.addEdge( edge);1330 } 1331 virtual void add(const std::vector<Edge>& edges) {1332 for (int i = edges.size() - 1; i >= 0; ++i) {1333 snapshot.addEdge( edges[i]);1334 } 1335 } 1336 virtual void erase(const Edge& edge) {1337 snapshot.eraseEdge( edge);1338 } 1339 virtual void erase(const std::vector<Edge>& edges) {1340 for (int i = 0; i < int( edges.size()); ++i) {1341 snapshot.eraseEdge( edges[i]);1306 virtual void add(const Edge& arc) { 1307 snapshot.addEdge(arc); 1308 } 1309 virtual void add(const std::vector<Edge>& arcs) { 1310 for (int i = arcs.size() - 1; i >= 0; ++i) { 1311 snapshot.addEdge(arcs[i]); 1312 } 1313 } 1314 virtual void erase(const Edge& arc) { 1315 snapshot.eraseEdge(arc); 1316 } 1317 virtual void erase(const std::vector<Edge>& arcs) { 1318 for (int i = 0; i < int(arcs.size()); ++i) { 1319 snapshot.eraseEdge(arcs[i]); 1342 1320 } 1343 1321 } 1344 1322 virtual void build() { 1345 Edge edge;1346 std::vector<Edge> edges;1347 for (notifier()->first( edge); edge!= INVALID;1348 notifier()->next( edge)) {1349 edges.push_back(edge);1350 } 1351 for (int i = edges.size() - 1; i >= 0; --i) {1352 snapshot.addEdge( edges[i]);1323 Edge arc; 1324 std::vector<Edge> arcs; 1325 for (notifier()->first(arc); arc != INVALID; 1326 notifier()->next(arc)) { 1327 arcs.push_back(arc); 1328 } 1329 for (int i = arcs.size() - 1; i >= 0; --i) { 1330 snapshot.addEdge(arcs[i]); 1353 1331 } 1354 1332 } 1355 1333 virtual void clear() { 1356 Edge edge;1357 for (notifier()->first( edge); edge!= INVALID;1358 notifier()->next( edge)) {1359 snapshot.eraseEdge( edge);1334 Edge arc; 1335 for (notifier()->first(arc); arc != INVALID; 1336 notifier()->next(arc)) { 1337 snapshot.eraseEdge(arc); 1360 1338 } 1361 1339 } … … 1363 1341 Snapshot& snapshot; 1364 1342 }; 1365 1366 ListGraph * graph;1343 1344 ListGraph *digraph; 1367 1345 1368 1346 NodeObserverProxy node_observer_proxy; 1369 EdgeObserverProxy edge_observer_proxy;1347 EdgeObserverProxy arc_observer_proxy; 1370 1348 1371 1349 std::list<Node> added_nodes; 1372 std::list<Edge> added_ edges;1350 std::list<Edge> added_arcs; 1373 1351 1374 1352 … … 1381 1359 if (it == added_nodes.end()) { 1382 1360 clear(); 1383 edge_observer_proxy.detach();1361 arc_observer_proxy.detach(); 1384 1362 throw NodeNotifier::ImmediateDetach(); 1385 1363 } else { … … 1388 1366 } 1389 1367 1390 void addEdge(const Edge& edge) {1391 added_ edges.push_front(edge);1392 } 1393 void eraseEdge(const Edge& edge) {1368 void addEdge(const Edge& arc) { 1369 added_arcs.push_front(arc); 1370 } 1371 void eraseEdge(const Edge& arc) { 1394 1372 std::list<Edge>::iterator it = 1395 std::find(added_ edges.begin(), added_edges.end(), edge);1396 if (it == added_ edges.end()) {1373 std::find(added_arcs.begin(), added_arcs.end(), arc); 1374 if (it == added_arcs.end()) { 1397 1375 clear(); 1398 1376 node_observer_proxy.detach(); 1399 1377 throw EdgeNotifier::ImmediateDetach(); 1400 1378 } else { 1401 added_ edges.erase(it);1402 } 1403 } 1404 1405 void attach(ListGraph &_ graph) {1406 graph = &_graph;1407 node_observer_proxy.attach( graph->notifier(Node()));1408 edge_observer_proxy.attach(graph->notifier(Edge()));1379 added_arcs.erase(it); 1380 } 1381 } 1382 1383 void attach(ListGraph &_digraph) { 1384 digraph = &_digraph; 1385 node_observer_proxy.attach(digraph->notifier(Node())); 1386 arc_observer_proxy.attach(digraph->notifier(Edge())); 1409 1387 } 1410 1388 1411 1389 void detach() { 1412 1390 node_observer_proxy.detach(); 1413 edge_observer_proxy.detach();1391 arc_observer_proxy.detach(); 1414 1392 } 1415 1393 … … 1420 1398 void clear() { 1421 1399 added_nodes.clear(); 1422 added_ edges.clear();1400 added_arcs.clear(); 1423 1401 } 1424 1402 … … 1430 1408 /// To actually make a snapshot you must call save(). 1431 1409 Snapshot() 1432 : graph(0), node_observer_proxy(*this),1433 edge_observer_proxy(*this) {}1410 : digraph(0), node_observer_proxy(*this), 1411 arc_observer_proxy(*this) {} 1434 1412 1435 1413 /// \brief Constructor that immediately makes a snapshot. 1436 1414 /// 1437 /// This constructor immediately makes a snapshot of the graph.1438 /// \param _ graph Thegraph we make a snapshot of.1439 Snapshot(ListGraph &_ graph)1415 /// This constructor immediately makes a snapshot of the digraph. 1416 /// \param _digraph The digraph we make a snapshot of. 1417 Snapshot(ListGraph &_digraph) 1440 1418 : node_observer_proxy(*this), 1441 edge_observer_proxy(*this) {1442 attach(_ graph);1419 arc_observer_proxy(*this) { 1420 attach(_digraph); 1443 1421 } 1444 1422 1445 1423 /// \brief Make a snapshot. 1446 1424 /// 1447 /// Make a snapshot of the graph.1425 /// Make a snapshot of the digraph. 1448 1426 /// 1449 1427 /// This function can be called more than once. In case of a repeated 1450 1428 /// call, the previous snapshot gets lost. 1451 /// \param _ graph Thegraph we make the snapshot of.1452 void save(ListGraph &_ graph) {1429 /// \param _digraph The digraph we make the snapshot of. 1430 void save(ListGraph &_digraph) { 1453 1431 if (attached()) { 1454 1432 detach(); 1455 1433 clear(); 1456 1434 } 1457 attach(_ graph);1435 attach(_digraph); 1458 1436 } 1459 1437 … … 1463 1441 void restore() { 1464 1442 detach(); 1465 for(std::list<Edge>::iterator it = added_ edges.begin();1466 it != added_ edges.end(); ++it) {1467 graph->erase(*it);1443 for(std::list<Edge>::iterator it = added_arcs.begin(); 1444 it != added_arcs.end(); ++it) { 1445 digraph->erase(*it); 1468 1446 } 1469 1447 for(std::list<Node>::iterator it = added_nodes.begin(); 1470 1448 it != added_nodes.end(); ++it) { 1471 graph->erase(*it);1449 digraph->erase(*it); 1472 1450 } 1473 1451 clear();
Note: See TracChangeset
for help on using the changeset viewer.