Changes in lemon/list_graph.h [664:4137ef9aacc6:835:c92296660262] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r664 r835 22 22 ///\ingroup graphs 23 23 ///\file 24 ///\brief ListDigraph ,ListGraph classes.24 ///\brief ListDigraph and ListGraph classes. 25 25 26 26 #include <lemon/core.h> … … 32 32 33 33 namespace lemon { 34 35 class ListDigraph; 34 36 35 37 class ListDigraphBase { … … 63 65 class Node { 64 66 friend class ListDigraphBase; 67 friend class ListDigraph; 65 68 protected: 66 69 … … 78 81 class Arc { 79 82 friend class ListDigraphBase; 83 friend class ListDigraph; 80 84 protected: 81 85 … … 117 121 int n; 118 122 for(n = first_node; 119 n !=-1 && nodes[n].first_in== -1;123 n != -1 && nodes[n].first_out == -1; 120 124 n = nodes[n].next) {} 121 arc.id = (n == -1) ? -1 : nodes[n].first_ in;125 arc.id = (n == -1) ? -1 : nodes[n].first_out; 122 126 } 123 127 124 128 void next(Arc& arc) const { 125 if (arcs[arc.id].next_ in!= -1) {126 arc.id = arcs[arc.id].next_ in;129 if (arcs[arc.id].next_out != -1) { 130 arc.id = arcs[arc.id].next_out; 127 131 } else { 128 132 int n; 129 for(n = nodes[arcs[arc.id]. target].next;130 n !=-1 && nodes[n].first_in== -1;133 for(n = nodes[arcs[arc.id].source].next; 134 n != -1 && nodes[n].first_out == -1; 131 135 n = nodes[n].next) {} 132 arc.id = (n == -1) ? -1 : nodes[n].first_ in;136 arc.id = (n == -1) ? -1 : nodes[n].first_out; 133 137 } 134 138 } … … 312 316 ///A general directed graph structure. 313 317 314 ///\ref ListDigraph is a simple and fast <em>directed graph</em>315 ///implementation based on staticlinked lists that are stored in318 ///\ref ListDigraph is a versatile and fast directed graph 319 ///implementation based on linked lists that are stored in 316 320 ///\c std::vector structures. 317 321 /// 318 /// It conforms to the \ref concepts::Digraph "Digraph concept" and it319 ///a lso provides several useful additional functionalities.320 ///Most of themember functions and nested classes are documented322 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 323 ///and it also provides several useful additional functionalities. 324 ///Most of its member functions and nested classes are documented 321 325 ///only in the concept class. 322 326 /// 327 ///This class provides only linear time counting for nodes and arcs. 328 /// 323 329 ///\sa concepts::Digraph 324 330 ///\sa ListGraph 325 331 class ListDigraph : public ExtendedListDigraphBase { 326 332 typedef ExtendedListDigraphBase Parent; 327 333 328 334 private: 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 330 331 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 332 /// 335 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 333 336 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 334 ///\brief Assignment of ListDigraph to another one is \e not allowed. 335 ///Use copyDigraph() instead. 336 337 ///Assignment of ListDigraph to another one is \e not allowed. 338 ///Use copyDigraph() instead. 337 /// \brief Assignment of a digraph to another one is \e not allowed. 338 /// Use DigraphCopy instead. 339 339 void operator=(const ListDigraph &) {} 340 340 public: … … 348 348 ///Add a new node to the digraph. 349 349 350 /// Adda new node to the digraph.350 ///This function adds a new node to the digraph. 351 351 ///\return The new node. 352 352 Node addNode() { return Parent::addNode(); } … … 354 354 ///Add a new arc to the digraph. 355 355 356 /// Adda new arc to the digraph with source node \c s356 ///This function adds a new arc to the digraph with source node \c s 357 357 ///and target node \c t. 358 358 ///\return The new arc. 359 Arc addArc( const Node& s, const Node&t) {359 Arc addArc(Node s, Node t) { 360 360 return Parent::addArc(s, t); 361 361 } … … 363 363 ///\brief Erase a node from the digraph. 364 364 /// 365 ///Erase a node from the digraph. 366 /// 367 void erase(const Node& n) { Parent::erase(n); } 365 ///This function erases the given node along with its outgoing and 366 ///incoming arcs from the digraph. 367 /// 368 ///\note All iterators referencing the removed node or the connected 369 ///arcs are invalidated, of course. 370 void erase(Node n) { Parent::erase(n); } 368 371 369 372 ///\brief Erase an arc from the digraph. 370 373 /// 371 ///Erase an arc from the digraph. 372 /// 373 void erase(const Arc& a) { Parent::erase(a); } 374 ///This function erases the given arc from the digraph. 375 /// 376 ///\note All iterators referencing the removed arc are invalidated, 377 ///of course. 378 void erase(Arc a) { Parent::erase(a); } 374 379 375 380 /// Node validity check 376 381 377 /// This function gives back true if the given node is valid, 378 /// ie. it is a real node of the graph. 379 /// 380 /// \warning A Node pointing to a removed item 381 /// could become valid again later if new nodes are 382 /// added to the graph. 382 /// This function gives back \c true if the given node is valid, 383 /// i.e. it is a real node of the digraph. 384 /// 385 /// \warning A removed node could become valid again if new nodes are 386 /// added to the digraph. 383 387 bool valid(Node n) const { return Parent::valid(n); } 384 388 385 389 /// Arc validity check 386 390 387 /// This function gives back true if the given arc is valid, 388 /// ie. it is a real arc of the graph. 389 /// 390 /// \warning An Arc pointing to a removed item 391 /// could become valid again later if new nodes are 392 /// added to the graph. 391 /// This function gives back \c true if the given arc is valid, 392 /// i.e. it is a real arc of the digraph. 393 /// 394 /// \warning A removed arc could become valid again if new arcs are 395 /// added to the digraph. 393 396 bool valid(Arc a) const { return Parent::valid(a); } 394 397 395 /// Change the target of \c a to \c n 396 397 /// Change the target of \c a to \c n 398 /// 399 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 400 ///the changed arc remain valid. However <tt>InArcIt</tt>s are 401 ///invalidated. 398 /// Change the target node of an arc 399 400 /// This function changes the target node of the given arc \c a to \c n. 401 /// 402 ///\note \c ArcIt and \c OutArcIt iterators referencing the changed 403 ///arc remain valid, but \c InArcIt iterators are invalidated. 402 404 /// 403 405 ///\warning This functionality cannot be used together with the Snapshot … … 406 408 Parent::changeTarget(a,n); 407 409 } 408 /// Change the source of \c a to \c n 409 410 /// Change the source of \c a to \c n 411 /// 412 ///\note The <tt>InArcIt</tt>s referencing the changed arc remain 413 ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are 414 ///invalidated. 410 /// Change the source node of an arc 411 412 /// This function changes the source node of the given arc \c a to \c n. 413 /// 414 ///\note \c InArcIt iterators referencing the changed arc remain 415 ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated. 415 416 /// 416 417 ///\warning This functionality cannot be used together with the Snapshot … … 420 421 } 421 422 422 /// Invertthe direction of an arc.423 424 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain425 /// valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are426 /// invalidated.423 /// Reverse the direction of an arc. 424 425 /// This function reverses the direction of the given arc. 426 ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing 427 ///the changed arc are invalidated. 427 428 /// 428 429 ///\warning This functionality cannot be used together with the Snapshot 429 430 ///feature. 430 void reverseArc(Arc e) { 431 Node t=target(e); 432 changeTarget(e,source(e)); 433 changeSource(e,t); 434 } 435 436 /// Reserve memory for nodes. 437 438 /// Using this function it is possible to avoid the superfluous memory 439 /// allocation: if you know that the digraph you want to build will 440 /// be very large (e.g. it will contain millions of nodes and/or arcs) 441 /// then it is worth reserving space for this amount before starting 442 /// to build the digraph. 443 /// \sa reserveArc 444 void reserveNode(int n) { nodes.reserve(n); }; 445 446 /// Reserve memory for arcs. 447 448 /// Using this function it is possible to avoid the superfluous memory 449 /// allocation: if you know that the digraph you want to build will 450 /// be very large (e.g. it will contain millions of nodes and/or arcs) 451 /// then it is worth reserving space for this amount before starting 452 /// to build the digraph. 453 /// \sa reserveNode 454 void reserveArc(int m) { arcs.reserve(m); }; 431 void reverseArc(Arc a) { 432 Node t=target(a); 433 changeTarget(a,source(a)); 434 changeSource(a,t); 435 } 455 436 456 437 ///Contract two nodes. 457 438 458 ///This function contracts two nodes. 459 ///Node \p b will be removed but instead of deleting 460 ///incident arcs, they will be joined to \p a. 461 ///The last parameter \p r controls whether to remove loops. \c true 462 ///means that loops will be removed. 463 /// 464 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 465 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 466 ///may be invalidated. 439 ///This function contracts the given two nodes. 440 ///Node \c v is removed, but instead of deleting its 441 ///incident arcs, they are joined to node \c u. 442 ///If the last parameter \c r is \c true (this is the default value), 443 ///then the newly created loops are removed. 444 /// 445 ///\note The moved arcs are joined to node \c u using changeSource() 446 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 447 ///invalidated for the outgoing arcs of node \c v and \c InArcIt 448 ///iterators are invalidated for the incomming arcs of \c v. 449 ///Moreover all iterators referencing node \c v or the removed 450 ///loops are also invalidated. Other iterators remain valid. 467 451 /// 468 452 ///\warning This functionality cannot be used together with the Snapshot 469 453 ///feature. 470 void contract(Node a, Node b, bool r = true)454 void contract(Node u, Node v, bool r = true) 471 455 { 472 for(OutArcIt e(*this, b);e!=INVALID;) {456 for(OutArcIt e(*this,v);e!=INVALID;) { 473 457 OutArcIt f=e; 474 458 ++f; 475 if(r && target(e)== a) erase(e);476 else changeSource(e, a);459 if(r && target(e)==u) erase(e); 460 else changeSource(e,u); 477 461 e=f; 478 462 } 479 for(InArcIt e(*this, b);e!=INVALID;) {463 for(InArcIt e(*this,v);e!=INVALID;) { 480 464 InArcIt f=e; 481 465 ++f; 482 if(r && source(e)== a) erase(e);483 else changeTarget(e, a);466 if(r && source(e)==u) erase(e); 467 else changeTarget(e,u); 484 468 e=f; 485 469 } 486 erase( b);470 erase(v); 487 471 } 488 472 489 473 ///Split a node. 490 474 491 ///This function splits a node. First a new node is added to the digraph, 492 ///then the source of each outgoing arc of \c n is moved to this new node. 493 ///If \c connect is \c true (this is the default value), then a new arc 494 ///from \c n to the newly created node is also added. 475 ///This function splits the given node. First, a new node is added 476 ///to the digraph, then the source of each outgoing arc of node \c n 477 ///is moved to this new node. 478 ///If the second parameter \c connect is \c true (this is the default 479 ///value), then a new arc from node \c n to the newly created node 480 ///is also added. 495 481 ///\return The newly created node. 496 482 /// 497 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 498 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may 499 ///be invalidated. 500 /// 501 ///\warning This functionality cannot be used in conjunction with the 483 ///\note All iterators remain valid. 484 /// 485 ///\warning This functionality cannot be used together with the 502 486 ///Snapshot feature. 503 487 Node split(Node n, bool connect = true) { 504 488 Node b = addNode(); 505 for(OutArcIt e(*this,n);e!=INVALID;) { 506 OutArcIt f=e; 507 ++f; 508 changeSource(e,b); 509 e=f; 489 nodes[b.id].first_out=nodes[n.id].first_out; 490 nodes[n.id].first_out=-1; 491 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { 492 arcs[i].source=b.id; 510 493 } 511 494 if (connect) addArc(n,b); … … 515 498 ///Split an arc. 516 499 517 ///This function splits an arc. First a new node \c b is added to518 /// the digraph, then the original arc is re-targeted to \c519 /// b. Finally an arc from \c b to the original target is added.520 /// 500 ///This function splits the given arc. First, a new node \c v is 501 ///added to the digraph, then the target node of the original arc 502 ///is set to \c v. Finally, an arc from \c v to the original target 503 ///is added. 521 504 ///\return The newly created node. 505 /// 506 ///\note \c InArcIt iterators referencing the original arc are 507 ///invalidated. Other iterators remain valid. 522 508 /// 523 509 ///\warning This functionality cannot be used together with the 524 510 ///Snapshot feature. 525 Node split(Arc e) { 526 Node b = addNode(); 527 addArc(b,target(e)); 528 changeTarget(e,b); 529 return b; 530 } 511 Node split(Arc a) { 512 Node v = addNode(); 513 addArc(v,target(a)); 514 changeTarget(a,v); 515 return v; 516 } 517 518 ///Clear the digraph. 519 520 ///This function erases all nodes and arcs from the digraph. 521 /// 522 ///\note All iterators of the digraph are invalidated, of course. 523 void clear() { 524 Parent::clear(); 525 } 526 527 /// Reserve memory for nodes. 528 529 /// Using this function, it is possible to avoid superfluous memory 530 /// allocation: if you know that the digraph you want to build will 531 /// be large (e.g. it will contain millions of nodes and/or arcs), 532 /// then it is worth reserving space for this amount before starting 533 /// to build the digraph. 534 /// \sa reserveArc() 535 void reserveNode(int n) { nodes.reserve(n); }; 536 537 /// Reserve memory for arcs. 538 539 /// Using this function, it is possible to avoid superfluous memory 540 /// allocation: if you know that the digraph you want to build will 541 /// be large (e.g. it will contain millions of nodes and/or arcs), 542 /// then it is worth reserving space for this amount before starting 543 /// to build the digraph. 544 /// \sa reserveNode() 545 void reserveArc(int m) { arcs.reserve(m); }; 531 546 532 547 /// \brief Class to make a snapshot of the digraph and restore … … 538 553 /// restore() function. 539 554 /// 540 /// \warning Arc and node deletions and other modifications (e.g. 541 /// contracting, splitting, reversing arcs or nodes) cannot be 555 /// \note After a state is restored, you cannot restore a later state, 556 /// i.e. you cannot add the removed nodes and arcs again using 557 /// another Snapshot instance. 558 /// 559 /// \warning Node and arc deletions and other modifications (e.g. 560 /// reversing, contracting, splitting arcs or nodes) cannot be 542 561 /// restored. These events invalidate the snapshot. 562 /// However, the arcs and nodes that were added to the digraph after 563 /// making the current snapshot can be removed without invalidating it. 543 564 class Snapshot { 544 565 protected: … … 710 731 /// 711 732 /// Default constructor. 712 /// To actually make a snapshot you must call save().733 /// You have to call save() to actually make a snapshot. 713 734 Snapshot() 714 735 : digraph(0), node_observer_proxy(*this), … … 717 738 /// \brief Constructor that immediately makes a snapshot. 718 739 /// 719 /// This constructor immediately makes a snapshot of the digraph. 720 /// \param _digraph The digraph we make a snapshot of. 721 Snapshot(ListDigraph &_digraph) 740 /// This constructor immediately makes a snapshot of the given digraph. 741 Snapshot(ListDigraph &gr) 722 742 : node_observer_proxy(*this), 723 743 arc_observer_proxy(*this) { 724 attach( _digraph);744 attach(gr); 725 745 } 726 746 727 747 /// \brief Make a snapshot. 728 748 /// 729 /// Make a snapshot of the digraph. 730 /// 731 /// This function can be called more than once. In case of a repeated 749 /// This function makes a snapshot of the given digraph. 750 /// It can be called more than once. In case of a repeated 732 751 /// call, the previous snapshot gets lost. 733 /// \param _digraph The digraph we make the snapshot of. 734 void save(ListDigraph &_digraph) { 752 void save(ListDigraph &gr) { 735 753 if (attached()) { 736 754 detach(); 737 755 clear(); 738 756 } 739 attach( _digraph);757 attach(gr); 740 758 } 741 759 742 760 /// \brief Undo the changes until the last snapshot. 743 // 744 /// Undo the changes until the last snapshot created by save(). 761 /// 762 /// This function undos the changes until the last snapshot 763 /// created by save() or Snapshot(ListDigraph&). 764 /// 765 /// \warning This method invalidates the snapshot, i.e. repeated 766 /// restoring is not supported unless you call save() again. 745 767 void restore() { 746 768 detach(); … … 756 778 } 757 779 758 /// \brief Gives back true whenthe snapshot is valid.780 /// \brief Returns \c true if the snapshot is valid. 759 781 /// 760 /// Gives back true whenthe snapshot is valid.782 /// This function returns \c true if the snapshot is valid. 761 783 bool valid() const { 762 784 return attached(); … … 795 817 796 818 typedef ListGraphBase Graph; 797 798 class Node;799 class Arc;800 class Edge;801 819 802 820 class Node { … … 848 866 bool operator<(const Arc& arc) const {return id < arc.id;} 849 867 }; 850 851 852 868 853 869 ListGraphBase() … … 1165 1181 ///A general undirected graph structure. 1166 1182 1167 ///\ref ListGraph is a simple and fast <em>undirected graph</em>1168 ///implementation based on staticlinked lists that are stored in1183 ///\ref ListGraph is a versatile and fast undirected graph 1184 ///implementation based on linked lists that are stored in 1169 1185 ///\c std::vector structures. 1170 1186 /// 1171 /// It conforms to the \ref concepts::Graph "Graph concept" and it1172 ///a lso provides several useful additional functionalities.1173 ///Most of themember functions and nested classes are documented1187 ///This type fully conforms to the \ref concepts::Graph "Graph concept" 1188 ///and it also provides several useful additional functionalities. 1189 ///Most of its member functions and nested classes are documented 1174 1190 ///only in the concept class. 1175 1191 /// 1192 ///This class provides only linear time counting for nodes, edges and arcs. 1193 /// 1176 1194 ///\sa concepts::Graph 1177 1195 ///\sa ListDigraph 1178 1196 class ListGraph : public ExtendedListGraphBase { 1179 1197 typedef ExtendedListGraphBase Parent; 1180 1198 1181 1199 private: 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1183 1184 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1185 /// 1200 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1186 1201 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 1187 ///\brief Assignment of ListGraph to another one is \e not allowed. 1188 ///Use copyGraph() instead. 1189 1190 ///Assignment of ListGraph to another one is \e not allowed. 1191 ///Use copyGraph() instead. 1202 /// \brief Assignment of a graph to another one is \e not allowed. 1203 /// Use GraphCopy instead. 1192 1204 void operator=(const ListGraph &) {} 1193 1205 public: … … 1202 1214 /// \brief Add a new node to the graph. 1203 1215 /// 1204 /// Adda new node to the graph.1216 /// This function adds a new node to the graph. 1205 1217 /// \return The new node. 1206 1218 Node addNode() { return Parent::addNode(); } … … 1208 1220 /// \brief Add a new edge to the graph. 1209 1221 /// 1210 /// Add a new edge to the graph with source node \c s 1211 /// and target node \c t. 1222 /// This function adds a new edge to the graph between nodes 1223 /// \c u and \c v with inherent orientation from node \c u to 1224 /// node \c v. 1212 1225 /// \return The new edge. 1213 Edge addEdge(const Node& s, const Node& t) { 1214 return Parent::addEdge(s, t); 1215 } 1216 1217 /// \brief Erase a node from the graph. 1218 /// 1219 /// Erase a node from the graph. 1220 /// 1221 void erase(const Node& n) { Parent::erase(n); } 1222 1223 /// \brief Erase an edge from the graph. 1224 /// 1225 /// Erase an edge from the graph. 1226 /// 1227 void erase(const Edge& e) { Parent::erase(e); } 1226 Edge addEdge(Node u, Node v) { 1227 return Parent::addEdge(u, v); 1228 } 1229 1230 ///\brief Erase a node from the graph. 1231 /// 1232 /// This function erases the given node along with its incident arcs 1233 /// from the graph. 1234 /// 1235 /// \note All iterators referencing the removed node or the incident 1236 /// edges are invalidated, of course. 1237 void erase(Node n) { Parent::erase(n); } 1238 1239 ///\brief Erase an edge from the graph. 1240 /// 1241 /// This function erases the given edge from the graph. 1242 /// 1243 /// \note All iterators referencing the removed edge are invalidated, 1244 /// of course. 1245 void erase(Edge e) { Parent::erase(e); } 1228 1246 /// Node validity check 1229 1247 1230 /// This function gives back true if the given node is valid, 1231 /// ie. it is a real node of the graph. 1232 /// 1233 /// \warning A Node pointing to a removed item 1234 /// could become valid again later if new nodes are 1248 /// This function gives back \c true if the given node is valid, 1249 /// i.e. it is a real node of the graph. 1250 /// 1251 /// \warning A removed node could become valid again if new nodes are 1235 1252 /// added to the graph. 1236 1253 bool valid(Node n) const { return Parent::valid(n); } 1254 /// Edge validity check 1255 1256 /// This function gives back \c true if the given edge is valid, 1257 /// i.e. it is a real edge of the graph. 1258 /// 1259 /// \warning A removed edge could become valid again if new edges are 1260 /// added to the graph. 1261 bool valid(Edge e) const { return Parent::valid(e); } 1237 1262 /// Arc validity check 1238 1263 1239 /// This function gives back true if the given arc is valid, 1240 /// ie. it is a real arc of the graph. 1241 /// 1242 /// \warning An Arc pointing to a removed item 1243 /// could become valid again later if new edges are 1264 /// This function gives back \c true if the given arc is valid, 1265 /// i.e. it is a real arc of the graph. 1266 /// 1267 /// \warning A removed arc could become valid again if new edges are 1244 1268 /// added to the graph. 1245 1269 bool valid(Arc a) const { return Parent::valid(a); } 1246 /// Edge validity check 1247 1248 /// This function gives back true if the given edge is valid, 1249 /// ie. it is a real arc of the graph. 1250 /// 1251 /// \warning A Edge pointing to a removed item 1252 /// could become valid again later if new edges are 1253 /// added to the graph. 1254 bool valid(Edge e) const { return Parent::valid(e); } 1255 /// \brief Change the end \c u of \c e to \c n 1256 /// 1257 /// This function changes the end \c u of \c e to node \c n. 1258 /// 1259 ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the 1260 ///changed edge are invalidated and if the changed node is the 1261 ///base node of an iterator then this iterator is also 1262 ///invalidated. 1270 1271 /// \brief Change the first node of an edge. 1272 /// 1273 /// This function changes the first node of the given edge \c e to \c n. 1274 /// 1275 ///\note \c EdgeIt and \c ArcIt iterators referencing the 1276 ///changed edge are invalidated and all other iterators whose 1277 ///base node is the changed node are also invalidated. 1263 1278 /// 1264 1279 ///\warning This functionality cannot be used together with the … … 1267 1282 Parent::changeU(e,n); 1268 1283 } 1269 /// \brief Change the end \c v of \c e to \c n 1270 /// 1271 /// This function changes the end \c v of \c e to \c n. 1272 /// 1273 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain 1274 ///valid, however <tt>ArcIt</tt>s and if the changed node is the 1275 ///base node of an iterator then this iterator is invalidated. 1284 /// \brief Change the second node of an edge. 1285 /// 1286 /// This function changes the second node of the given edge \c e to \c n. 1287 /// 1288 ///\note \c EdgeIt iterators referencing the changed edge remain 1289 ///valid, but \c ArcIt iterators referencing the changed edge and 1290 ///all other iterators whose base node is the changed node are also 1291 ///invalidated. 1276 1292 /// 1277 1293 ///\warning This functionality cannot be used together with the … … 1280 1296 Parent::changeV(e,n); 1281 1297 } 1298 1282 1299 /// \brief Contract two nodes. 1283 1300 /// 1284 /// This function contracts two nodes. 1285 /// Node \p b will be removed but instead of deleting 1286 /// its neighboring arcs, they will be joined to \p a. 1287 /// The last parameter \p r controls whether to remove loops. \c true 1288 /// means that loops will be removed. 1289 /// 1290 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 1291 /// valid. 1301 /// This function contracts the given two nodes. 1302 /// Node \c b is removed, but instead of deleting 1303 /// its incident edges, they are joined to node \c a. 1304 /// If the last parameter \c r is \c true (this is the default value), 1305 /// then the newly created loops are removed. 1306 /// 1307 /// \note The moved edges are joined to node \c a using changeU() 1308 /// or changeV(), thus all edge and arc iterators whose base node is 1309 /// \c b are invalidated. 1310 /// Moreover all iterators referencing node \c b or the removed 1311 /// loops are also invalidated. Other iterators remain valid. 1292 1312 /// 1293 1313 ///\warning This functionality cannot be used together with the … … 1308 1328 } 1309 1329 1330 ///Clear the graph. 1331 1332 ///This function erases all nodes and arcs from the graph. 1333 /// 1334 ///\note All iterators of the graph are invalidated, of course. 1335 void clear() { 1336 Parent::clear(); 1337 } 1338 1339 /// Reserve memory for nodes. 1340 1341 /// Using this function, it is possible to avoid superfluous memory 1342 /// allocation: if you know that the graph you want to build will 1343 /// be large (e.g. it will contain millions of nodes and/or edges), 1344 /// then it is worth reserving space for this amount before starting 1345 /// to build the graph. 1346 /// \sa reserveEdge() 1347 void reserveNode(int n) { nodes.reserve(n); }; 1348 1349 /// Reserve memory for edges. 1350 1351 /// Using this function, it is possible to avoid superfluous memory 1352 /// allocation: if you know that the graph you want to build will 1353 /// be large (e.g. it will contain millions of nodes and/or edges), 1354 /// then it is worth reserving space for this amount before starting 1355 /// to build the graph. 1356 /// \sa reserveNode() 1357 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1310 1358 1311 1359 /// \brief Class to make a snapshot of the graph and restore … … 1317 1365 /// using the restore() function. 1318 1366 /// 1319 /// \warning Edge and node deletions and other modifications 1320 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1321 /// restored. These events invalidate the snapshot. 1367 /// \note After a state is restored, you cannot restore a later state, 1368 /// i.e. you cannot add the removed nodes and edges again using 1369 /// another Snapshot instance. 1370 /// 1371 /// \warning Node and edge deletions and other modifications 1372 /// (e.g. changing the end-nodes of edges or contracting nodes) 1373 /// cannot be restored. These events invalidate the snapshot. 1374 /// However, the edges and nodes that were added to the graph after 1375 /// making the current snapshot can be removed without invalidating it. 1322 1376 class Snapshot { 1323 1377 protected: … … 1489 1543 /// 1490 1544 /// Default constructor. 1491 /// To actually make a snapshot you must call save().1545 /// You have to call save() to actually make a snapshot. 1492 1546 Snapshot() 1493 1547 : graph(0), node_observer_proxy(*this), … … 1496 1550 /// \brief Constructor that immediately makes a snapshot. 1497 1551 /// 1498 /// This constructor immediately makes a snapshot of the graph. 1499 /// \param _graph The graph we make a snapshot of. 1500 Snapshot(ListGraph &_graph) 1552 /// This constructor immediately makes a snapshot of the given graph. 1553 Snapshot(ListGraph &gr) 1501 1554 : node_observer_proxy(*this), 1502 1555 edge_observer_proxy(*this) { 1503 attach( _graph);1556 attach(gr); 1504 1557 } 1505 1558 1506 1559 /// \brief Make a snapshot. 1507 1560 /// 1508 /// Make a snapshot of the graph. 1509 /// 1510 /// This function can be called more than once. In case of a repeated 1561 /// This function makes a snapshot of the given graph. 1562 /// It can be called more than once. In case of a repeated 1511 1563 /// call, the previous snapshot gets lost. 1512 /// \param _graph The graph we make the snapshot of. 1513 void save(ListGraph &_graph) { 1564 void save(ListGraph &gr) { 1514 1565 if (attached()) { 1515 1566 detach(); 1516 1567 clear(); 1517 1568 } 1518 attach( _graph);1569 attach(gr); 1519 1570 } 1520 1571 1521 1572 /// \brief Undo the changes until the last snapshot. 1522 // 1523 /// Undo the changes until the last snapshot created by save(). 1573 /// 1574 /// This function undos the changes until the last snapshot 1575 /// created by save() or Snapshot(ListGraph&). 1576 /// 1577 /// \warning This method invalidates the snapshot, i.e. repeated 1578 /// restoring is not supported unless you call save() again. 1524 1579 void restore() { 1525 1580 detach(); … … 1535 1590 } 1536 1591 1537 /// \brief Gives back true whenthe snapshot is valid.1592 /// \brief Returns \c true if the snapshot is valid. 1538 1593 /// 1539 /// Gives back true whenthe snapshot is valid.1594 /// This function returns \c true if the snapshot is valid. 1540 1595 bool valid() const { 1541 1596 return attached();
Note: See TracChangeset
for help on using the changeset viewer.