Changeset 788:10c9c3a35b83 in lemon
- Timestamp:
- 09/30/09 08:36:43 (15 years ago)
- Branch:
- default
- Parents:
- 787:819ca5b50de0 (diff), 786:32baeb8e5c8f (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:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r786 r788 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 … … 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 /// 323 327 ///\sa concepts::Digraph 324 328 ///\sa ListGraph 325 329 class ListDigraph : public ExtendedListDigraphBase { 326 330 typedef ExtendedListDigraphBase Parent; 327 331 328 332 private: 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 330 331 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 332 /// 333 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 333 334 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. 335 /// \brief Assignment of a digraph to another one is \e not allowed. 336 /// Use DigraphCopy instead. 339 337 void operator=(const ListDigraph &) {} 340 338 public: … … 348 346 ///Add a new node to the digraph. 349 347 350 /// Adda new node to the digraph.348 ///This function adds a new node to the digraph. 351 349 ///\return The new node. 352 350 Node addNode() { return Parent::addNode(); } … … 354 352 ///Add a new arc to the digraph. 355 353 356 /// Adda new arc to the digraph with source node \c s354 ///This function adds a new arc to the digraph with source node \c s 357 355 ///and target node \c t. 358 356 ///\return The new arc. 359 Arc addArc( const Node& s, const Node&t) {357 Arc addArc(Node s, Node t) { 360 358 return Parent::addArc(s, t); 361 359 } … … 363 361 ///\brief Erase a node from the digraph. 364 362 /// 365 ///Erase a node from the digraph. 366 /// 367 void erase(const Node& n) { Parent::erase(n); } 363 ///This function erases the given node from the digraph. 364 void erase(Node n) { Parent::erase(n); } 368 365 369 366 ///\brief Erase an arc from the digraph. 370 367 /// 371 ///Erase an arc from the digraph. 372 /// 373 void erase(const Arc& a) { Parent::erase(a); } 368 ///This function erases the given arc from the digraph. 369 void erase(Arc a) { Parent::erase(a); } 374 370 375 371 /// Node validity check 376 372 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. 373 /// This function gives back \c true if the given node is valid, 374 /// i.e. it is a real node of the digraph. 375 /// 376 /// \warning A removed node could become valid again if new nodes are 377 /// added to the digraph. 383 378 bool valid(Node n) const { return Parent::valid(n); } 384 379 385 380 /// Arc validity check 386 381 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. 382 /// This function gives back \c true if the given arc is valid, 383 /// i.e. it is a real arc of the digraph. 384 /// 385 /// \warning A removed arc could become valid again if new arcs are 386 /// added to the digraph. 393 387 bool valid(Arc a) const { return Parent::valid(a); } 394 388 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. 389 /// Change the target node of an arc 390 391 /// This function changes the target node of the given arc \c a to \c n. 392 /// 393 ///\note \c ArcIt and \c OutArcIt iterators referencing the changed 394 ///arc remain valid, however \c InArcIt iterators are invalidated. 402 395 /// 403 396 ///\warning This functionality cannot be used together with the Snapshot … … 406 399 Parent::changeTarget(a,n); 407 400 } 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. 401 /// Change the source node of an arc 402 403 /// This function changes the source node of the given arc \c a to \c n. 404 /// 405 ///\note \c InArcIt iterators referencing the changed arc remain 406 ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. 415 407 /// 416 408 ///\warning This functionality cannot be used together with the Snapshot … … 420 412 } 421 413 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.414 /// Reverse the direction of an arc. 415 416 /// This function reverses the direction of the given arc. 417 ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing 418 ///the changed arc are invalidated. 427 419 /// 428 420 ///\warning This functionality cannot be used together with the Snapshot 429 421 ///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); }; 422 void reverseArc(Arc a) { 423 Node t=target(a); 424 changeTarget(a,source(a)); 425 changeSource(a,t); 426 } 455 427 456 428 ///Contract two nodes. 457 429 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. 430 ///This function contracts the given two nodes. 431 ///Node \c v is removed, but instead of deleting its 432 ///incident arcs, they are joined to node \c u. 433 ///If the last parameter \c r is \c true (this is the default value), 434 ///then the newly created loops are removed. 435 /// 436 ///\note The moved arcs are joined to node \c u using changeSource() 437 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 438 ///invalidated for the outgoing arcs of node \c v and \c InArcIt 439 ///iterators are invalidated for the incomming arcs of \c v. 440 ///Moreover all iterators referencing node \c v or the removed 441 ///loops are also invalidated. Other iterators remain valid. 467 442 /// 468 443 ///\warning This functionality cannot be used together with the Snapshot 469 444 ///feature. 470 void contract(Node a, Node b, bool r = true)445 void contract(Node u, Node v, bool r = true) 471 446 { 472 for(OutArcIt e(*this, b);e!=INVALID;) {447 for(OutArcIt e(*this,v);e!=INVALID;) { 473 448 OutArcIt f=e; 474 449 ++f; 475 if(r && target(e)== a) erase(e);476 else changeSource(e, a);450 if(r && target(e)==u) erase(e); 451 else changeSource(e,u); 477 452 e=f; 478 453 } 479 for(InArcIt e(*this, b);e!=INVALID;) {454 for(InArcIt e(*this,v);e!=INVALID;) { 480 455 InArcIt f=e; 481 456 ++f; 482 if(r && source(e)== a) erase(e);483 else changeTarget(e, a);457 if(r && source(e)==u) erase(e); 458 else changeTarget(e,u); 484 459 e=f; 485 460 } 486 erase( b);461 erase(v); 487 462 } 488 463 489 464 ///Split a node. 490 465 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. 466 ///This function splits the given node. First, a new node is added 467 ///to the digraph, then the source of each outgoing arc of node \c n 468 ///is moved to this new node. 469 ///If the second parameter \c connect is \c true (this is the default 470 ///value), then a new arc from node \c n to the newly created node 471 ///is also added. 495 472 ///\return The newly created node. 496 473 /// 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 474 ///\note All iterators remain valid. 475 /// 476 ///\warning This functionality cannot be used together with the 502 477 ///Snapshot feature. 503 478 Node split(Node n, bool connect = true) { 504 479 Node b = addNode(); 505 for(OutArcIt e(*this,n);e!=INVALID;) { 506 OutArcIt f=e; 507 ++f; 508 changeSource(e,b); 509 e=f; 480 nodes[b.id].first_out=nodes[n.id].first_out; 481 nodes[n.id].first_out=-1; 482 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) { 483 arcs[i].source=b.id; 510 484 } 511 485 if (connect) addArc(n,b); … … 515 489 ///Split an arc. 516 490 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 /// 491 ///This function splits the given arc. First, a new node \c v is 492 ///added to the digraph, then the target node of the original arc 493 ///is set to \c v. Finally, an arc from \c v to the original target 494 ///is added. 521 495 ///\return The newly created node. 496 /// 497 ///\note \c InArcIt iterators referencing the original arc are 498 ///invalidated. Other iterators remain valid. 522 499 /// 523 500 ///\warning This functionality cannot be used together with the 524 501 ///Snapshot feature. 525 Node split(Arc e) { 526 Node b = addNode(); 527 addArc(b,target(e)); 528 changeTarget(e,b); 529 return b; 530 } 502 Node split(Arc a) { 503 Node v = addNode(); 504 addArc(v,target(a)); 505 changeTarget(a,v); 506 return v; 507 } 508 509 ///Clear the digraph. 510 511 ///This function erases all nodes and arcs from the digraph. 512 /// 513 void clear() { 514 Parent::clear(); 515 } 516 517 /// Reserve memory for nodes. 518 519 /// Using this function, it is possible to avoid superfluous memory 520 /// allocation: if you know that the digraph you want to build will 521 /// be large (e.g. it will contain millions of nodes and/or arcs), 522 /// then it is worth reserving space for this amount before starting 523 /// to build the digraph. 524 /// \sa reserveArc() 525 void reserveNode(int n) { nodes.reserve(n); }; 526 527 /// Reserve memory for arcs. 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 reserveNode() 535 void reserveArc(int m) { arcs.reserve(m); }; 531 536 532 537 /// \brief Class to make a snapshot of the digraph and restore … … 538 543 /// restore() function. 539 544 /// 540 /// \warning Arc and node deletions and other modifications (e.g. 541 /// contracting, splitting, reversing arcs or nodes) cannot be 545 /// \note After a state is restored, you cannot restore a later state, 546 /// i.e. you cannot add the removed nodes and arcs again using 547 /// another Snapshot instance. 548 /// 549 /// \warning Node and arc deletions and other modifications (e.g. 550 /// reversing, contracting, splitting arcs or nodes) cannot be 542 551 /// restored. These events invalidate the snapshot. 552 /// However the arcs and nodes that were added to the digraph after 553 /// making the current snapshot can be removed without invalidating it. 543 554 class Snapshot { 544 555 protected: … … 710 721 /// 711 722 /// Default constructor. 712 /// To actually make a snapshot you must call save().723 /// You have to call save() to actually make a snapshot. 713 724 Snapshot() 714 725 : digraph(0), node_observer_proxy(*this), … … 717 728 /// \brief Constructor that immediately makes a snapshot. 718 729 /// 719 /// This constructor immediately makes a snapshot of the digraph. 720 /// \param _digraph The digraph we make a snapshot of. 721 Snapshot(ListDigraph &_digraph) 730 /// This constructor immediately makes a snapshot of the given digraph. 731 Snapshot(ListDigraph &gr) 722 732 : node_observer_proxy(*this), 723 733 arc_observer_proxy(*this) { 724 attach( _digraph);734 attach(gr); 725 735 } 726 736 727 737 /// \brief Make a snapshot. 728 738 /// 729 /// Make a snapshot of the digraph. 730 /// 731 /// This function can be called more than once. In case of a repeated 739 /// This function makes a snapshot of the given digraph. 740 /// It can be called more than once. In case of a repeated 732 741 /// call, the previous snapshot gets lost. 733 /// \param _digraph The digraph we make the snapshot of. 734 void save(ListDigraph &_digraph) { 742 void save(ListDigraph &gr) { 735 743 if (attached()) { 736 744 detach(); 737 745 clear(); 738 746 } 739 attach( _digraph);747 attach(gr); 740 748 } 741 749 742 750 /// \brief Undo the changes until the last snapshot. 743 // 744 /// Undo the changes until the last snapshot created by save(). 751 /// 752 /// This function undos the changes until the last snapshot 753 /// created by save() or Snapshot(ListDigraph&). 754 /// 755 /// \warning This method invalidates the snapshot, i.e. repeated 756 /// restoring is not supported unless you call save() again. 745 757 void restore() { 746 758 detach(); … … 756 768 } 757 769 758 /// \brief Gives back true whenthe snapshot is valid.770 /// \brief Returns \c true if the snapshot is valid. 759 771 /// 760 /// Gives back true whenthe snapshot is valid.772 /// This function returns \c true if the snapshot is valid. 761 773 bool valid() const { 762 774 return attached(); … … 795 807 796 808 typedef ListGraphBase Graph; 797 798 class Node;799 class Arc;800 class Edge;801 809 802 810 class Node { … … 848 856 bool operator<(const Arc& arc) const {return id < arc.id;} 849 857 }; 850 851 852 858 853 859 ListGraphBase() … … 1165 1171 ///A general undirected graph structure. 1166 1172 1167 ///\ref ListGraph is a simple and fast <em>undirected graph</em>1168 ///implementation based on staticlinked lists that are stored in1173 ///\ref ListGraph is a versatile and fast undirected graph 1174 ///implementation based on linked lists that are stored in 1169 1175 ///\c std::vector structures. 1170 1176 /// 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 documented1177 ///This type fully conforms to the \ref concepts::Graph "Graph concept" 1178 ///and it also provides several useful additional functionalities. 1179 ///Most of its member functions and nested classes are documented 1174 1180 ///only in the concept class. 1175 1181 /// 1176 1182 ///\sa concepts::Graph 1177 1183 ///\sa ListDigraph 1178 1184 class ListGraph : public ExtendedListGraphBase { 1179 1185 typedef ExtendedListGraphBase Parent; 1180 1186 1181 1187 private: 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1183 1184 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1185 /// 1188 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1186 1189 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. 1190 /// \brief Assignment of a graph to another one is \e not allowed. 1191 /// Use GraphCopy instead. 1192 1192 void operator=(const ListGraph &) {} 1193 1193 public: … … 1202 1202 /// \brief Add a new node to the graph. 1203 1203 /// 1204 /// Adda new node to the graph.1204 /// This function adds a new node to the graph. 1205 1205 /// \return The new node. 1206 1206 Node addNode() { return Parent::addNode(); } … … 1208 1208 /// \brief Add a new edge to the graph. 1209 1209 /// 1210 /// Add a new edge to the graph with source node \c s 1211 /// and target node \c t. 1210 /// This function adds a new edge to the graph between nodes 1211 /// \c u and \c v with inherent orientation from node \c u to 1212 /// node \c v. 1212 1213 /// \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); } 1214 Edge addEdge(Node u, Node v) { 1215 return Parent::addEdge(u, v); 1216 } 1217 1218 ///\brief Erase a node from the graph. 1219 /// 1220 /// This function erases the given node from the graph. 1221 void erase(Node n) { Parent::erase(n); } 1222 1223 ///\brief Erase an edge from the graph. 1224 /// 1225 /// This function erases the given edge from the graph. 1226 void erase(Edge e) { Parent::erase(e); } 1228 1227 /// Node validity check 1229 1228 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 1229 /// This function gives back \c true if the given node is valid, 1230 /// i.e. it is a real node of the graph. 1231 /// 1232 /// \warning A removed node could become valid again if new nodes are 1235 1233 /// added to the graph. 1236 1234 bool valid(Node n) const { return Parent::valid(n); } 1235 /// Edge validity check 1236 1237 /// This function gives back \c true if the given edge is valid, 1238 /// i.e. it is a real edge of the graph. 1239 /// 1240 /// \warning A removed edge could become valid again if new edges are 1241 /// added to the graph. 1242 bool valid(Edge e) const { return Parent::valid(e); } 1237 1243 /// Arc validity check 1238 1244 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 1245 /// This function gives back \c true if the given arc is valid, 1246 /// i.e. it is a real arc of the graph. 1247 /// 1248 /// \warning A removed arc could become valid again if new edges are 1244 1249 /// added to the graph. 1245 1250 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. 1251 1252 /// \brief Change the first node of an edge. 1253 /// 1254 /// This function changes the first node of the given edge \c e to \c n. 1255 /// 1256 ///\note \c EdgeIt and \c ArcIt iterators referencing the 1257 ///changed edge are invalidated and all other iterators whose 1258 ///base node is the changed node are also invalidated. 1263 1259 /// 1264 1260 ///\warning This functionality cannot be used together with the … … 1267 1263 Parent::changeU(e,n); 1268 1264 } 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. 1265 /// \brief Change the second node of an edge. 1266 /// 1267 /// This function changes the second node of the given edge \c e to \c n. 1268 /// 1269 ///\note \c EdgeIt iterators referencing the changed edge remain 1270 ///valid, however \c ArcIt iterators referencing the changed edge and 1271 ///all other iterators whose base node is the changed node are also 1272 ///invalidated. 1276 1273 /// 1277 1274 ///\warning This functionality cannot be used together with the … … 1280 1277 Parent::changeV(e,n); 1281 1278 } 1279 1282 1280 /// \brief Contract two nodes. 1283 1281 /// 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. 1282 /// This function contracts the given two nodes. 1283 /// Node \c b is removed, but instead of deleting 1284 /// its incident edges, they are joined to node \c a. 1285 /// If the last parameter \c r is \c true (this is the default value), 1286 /// then the newly created loops are removed. 1287 /// 1288 /// \note The moved edges are joined to node \c a using changeU() 1289 /// or changeV(), thus all edge and arc iterators whose base node is 1290 /// \c b are invalidated. 1291 /// Moreover all iterators referencing node \c b or the removed 1292 /// loops are also invalidated. Other iterators remain valid. 1292 1293 /// 1293 1294 ///\warning This functionality cannot be used together with the … … 1308 1309 } 1309 1310 1311 ///Clear the graph. 1312 1313 ///This function erases all nodes and arcs from the graph. 1314 /// 1315 void clear() { 1316 Parent::clear(); 1317 } 1318 1319 /// Reserve memory for nodes. 1320 1321 /// Using this function, it is possible to avoid superfluous memory 1322 /// allocation: if you know that the graph you want to build will 1323 /// be large (e.g. it will contain millions of nodes and/or edges), 1324 /// then it is worth reserving space for this amount before starting 1325 /// to build the graph. 1326 /// \sa reserveEdge() 1327 void reserveNode(int n) { nodes.reserve(n); }; 1328 1329 /// Reserve memory for edges. 1330 1331 /// Using this function, it is possible to avoid superfluous memory 1332 /// allocation: if you know that the graph you want to build will 1333 /// be large (e.g. it will contain millions of nodes and/or edges), 1334 /// then it is worth reserving space for this amount before starting 1335 /// to build the graph. 1336 /// \sa reserveNode() 1337 void reserveEdge(int m) { arcs.reserve(2 * m); }; 1310 1338 1311 1339 /// \brief Class to make a snapshot of the graph and restore … … 1317 1345 /// using the restore() function. 1318 1346 /// 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. 1347 /// \note After a state is restored, you cannot restore a later state, 1348 /// i.e. you cannot add the removed nodes and edges again using 1349 /// another Snapshot instance. 1350 /// 1351 /// \warning Node and edge deletions and other modifications 1352 /// (e.g. changing the end-nodes of edges or contracting nodes) 1353 /// cannot be restored. These events invalidate the snapshot. 1354 /// However the edges and nodes that were added to the graph after 1355 /// making the current snapshot can be removed without invalidating it. 1322 1356 class Snapshot { 1323 1357 protected: … … 1489 1523 /// 1490 1524 /// Default constructor. 1491 /// To actually make a snapshot you must call save().1525 /// You have to call save() to actually make a snapshot. 1492 1526 Snapshot() 1493 1527 : graph(0), node_observer_proxy(*this), … … 1496 1530 /// \brief Constructor that immediately makes a snapshot. 1497 1531 /// 1498 /// This constructor immediately makes a snapshot of the graph. 1499 /// \param _graph The graph we make a snapshot of. 1500 Snapshot(ListGraph &_graph) 1532 /// This constructor immediately makes a snapshot of the given graph. 1533 Snapshot(ListGraph &gr) 1501 1534 : node_observer_proxy(*this), 1502 1535 edge_observer_proxy(*this) { 1503 attach( _graph);1536 attach(gr); 1504 1537 } 1505 1538 1506 1539 /// \brief Make a snapshot. 1507 1540 /// 1508 /// Make a snapshot of the graph. 1509 /// 1510 /// This function can be called more than once. In case of a repeated 1541 /// This function makes a snapshot of the given graph. 1542 /// It can be called more than once. In case of a repeated 1511 1543 /// call, the previous snapshot gets lost. 1512 /// \param _graph The graph we make the snapshot of. 1513 void save(ListGraph &_graph) { 1544 void save(ListGraph &gr) { 1514 1545 if (attached()) { 1515 1546 detach(); 1516 1547 clear(); 1517 1548 } 1518 attach( _graph);1549 attach(gr); 1519 1550 } 1520 1551 1521 1552 /// \brief Undo the changes until the last snapshot. 1522 // 1523 /// Undo the changes until the last snapshot created by save(). 1553 /// 1554 /// This function undos the changes until the last snapshot 1555 /// created by save() or Snapshot(ListGraph&). 1556 /// 1557 /// \warning This method invalidates the snapshot, i.e. repeated 1558 /// restoring is not supported unless you call save() again. 1524 1559 void restore() { 1525 1560 detach(); … … 1535 1570 } 1536 1571 1537 /// \brief Gives back true whenthe snapshot is valid.1572 /// \brief Returns \c true if the snapshot is valid. 1538 1573 /// 1539 /// Gives back true whenthe snapshot is valid.1574 /// This function returns \c true if the snapshot is valid. 1540 1575 bool valid() const { 1541 1576 return attached(); -
lemon/list_graph.h
r787 r788 121 121 int n; 122 122 for(n = first_node; 123 n !=-1 && nodes[n].first_in== -1;123 n != -1 && nodes[n].first_out == -1; 124 124 n = nodes[n].next) {} 125 arc.id = (n == -1) ? -1 : nodes[n].first_ in;125 arc.id = (n == -1) ? -1 : nodes[n].first_out; 126 126 } 127 127 128 128 void next(Arc& arc) const { 129 if (arcs[arc.id].next_ in!= -1) {130 arc.id = arcs[arc.id].next_ in;129 if (arcs[arc.id].next_out != -1) { 130 arc.id = arcs[arc.id].next_out; 131 131 } else { 132 132 int n; 133 for(n = nodes[arcs[arc.id]. target].next;134 n !=-1 && nodes[n].first_in== -1;133 for(n = nodes[arcs[arc.id].source].next; 134 n != -1 && nodes[n].first_out == -1; 135 135 n = nodes[n].next) {} 136 arc.id = (n == -1) ? -1 : nodes[n].first_ in;136 arc.id = (n == -1) ? -1 : nodes[n].first_out; 137 137 } 138 138 }
Note: See TracChangeset
for help on using the changeset viewer.