Changeset 735:853fcddcf282 in lemon-main
- Timestamp:
- 08/23/09 11:09:22 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r663 r735 637 637 \brief Skeleton and concept checking classes for graph structures 638 638 639 This group contains the skeletons and concept checking classes of LEMON's640 graph structures and helper classes used to implement these.639 This group contains the skeletons and concept checking classes of 640 graph structures. 641 641 */ 642 642 -
lemon/full_graph.h
r617 r735 25 25 ///\ingroup graphs 26 26 ///\file 27 ///\brief Full Graph and FullDigraph classes.27 ///\brief FullDigraph and FullGraph classes. 28 28 29 29 namespace lemon { … … 149 149 /// \ingroup graphs 150 150 /// 151 /// \brief A full digraph class. 152 /// 153 /// This is a simple and fast directed full graph implementation. 154 /// From each node go arcs to each node (including the source node), 155 /// therefore the number of the arcs in the digraph is the square of 156 /// the node number. This digraph type is completely static, so you 157 /// can neither add nor delete either arcs or nodes, and it needs 158 /// constant space in memory. 159 /// 160 /// This class fully conforms to the \ref concepts::Digraph 161 /// "Digraph concept". 162 /// 163 /// The \c FullDigraph and \c FullGraph classes are very similar, 151 /// \brief A directed full graph class. 152 /// 153 /// FullDigraph is a simple and fast implmenetation of directed full 154 /// (complete) graphs. It contains an arc from each node to each node 155 /// (including a loop for each node), therefore the number of arcs 156 /// is the square of the number of nodes. 157 /// This class is completely static and it needs constant memory space. 158 /// Thus you can neither add nor delete nodes or arcs, however 159 /// the structure can be resized using resize(). 160 /// 161 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". 162 /// Most of its member functions and nested classes are documented 163 /// only in the concept class. 164 /// 165 /// \note FullDigraph and FullGraph classes are very similar, 164 166 /// but there are two differences. While this class conforms only 165 /// to the \ref concepts::Digraph "Digraph" concept, the \cFullGraph166 /// c lass conforms to the \ref concepts::Graph "Graph" concept,167 /// moreover \c FullGraph does not contain a loop arcfor each168 /// node as \c FullDigraphdoes.167 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph 168 /// conforms to the \ref concepts::Graph "Graph" concept, 169 /// moreover FullGraph does not contain a loop for each 170 /// node as this class does. 169 171 /// 170 172 /// \sa FullGraph … … 174 176 public: 175 177 176 /// \brief Constructor 178 /// \brief Default constructor. 179 /// 180 /// Default constructor. The number of nodes and arcs will be zero. 177 181 FullDigraph() { construct(0); } 178 182 … … 185 189 /// \brief Resizes the digraph 186 190 /// 187 /// Resizes the digraph. The function will fully destroyand188 /// rebuild the digraph. This cause that the maps of the digraph will191 /// This function resizes the digraph. It fully destroys and 192 /// rebuilds the structure, therefore the maps of the digraph will be 189 193 /// reallocated automatically and the previous values will be lost. 190 194 void resize(int n) { … … 198 202 /// \brief Returns the node with the given index. 199 203 /// 200 /// Returns the node with the given index. Since it is a static201 /// digraph its nodes can be indexed with integers from the range202 /// <tt>[0..nodeNum()-1]</tt>.204 /// Returns the node with the given index. Since this structure is 205 /// completely static, the nodes can be indexed with integers from 206 /// the range <tt>[0..nodeNum()-1]</tt>. 203 207 /// \sa index() 204 208 Node operator()(int ix) const { return Parent::operator()(ix); } … … 206 210 /// \brief Returns the index of the given node. 207 211 /// 208 /// Returns the index of the given node. Since it is a static209 /// digraph its nodes can be indexed with integers from the range210 /// <tt>[0..nodeNum()-1]</tt>.211 /// \sa operator() 212 int index( const Node&node) const { return Parent::index(node); }212 /// Returns the index of the given node. Since this structure is 213 /// completely static, the nodes can be indexed with integers from 214 /// the range <tt>[0..nodeNum()-1]</tt>. 215 /// \sa operator()() 216 int index(Node node) const { return Parent::index(node); } 213 217 214 218 /// \brief Returns the arc connecting the given nodes. 215 219 /// 216 220 /// Returns the arc connecting the given nodes. 217 Arc arc( const Node& u, const Node&v) const {221 Arc arc(Node u, Node v) const { 218 222 return Parent::arc(u, v); 219 223 } … … 521 525 /// \brief An undirected full graph class. 522 526 /// 523 /// This is a simple and fast undirected full graph 524 /// implementation. From each node go edge to each other node, 525 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 526 /// This graph type is completely static, so you can neither 527 /// add nor delete either edges or nodes, and it needs constant 528 /// space in memory. 529 /// 530 /// This class fully conforms to the \ref concepts::Graph "Graph concept". 531 /// 532 /// The \c FullGraph and \c FullDigraph classes are very similar, 533 /// but there are two differences. While the \c FullDigraph class 527 /// FullGraph is a simple and fast implmenetation of undirected full 528 /// (complete) graphs. It contains an edge between every distinct pair 529 /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. 530 /// This class is completely static and it needs constant memory space. 531 /// Thus you can neither add nor delete nodes or edges, however 532 /// the structure can be resized using resize(). 533 /// 534 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 535 /// Most of its member functions and nested classes are documented 536 /// only in the concept class. 537 /// 538 /// \note FullDigraph and FullGraph classes are very similar, 539 /// but there are two differences. While FullDigraph 534 540 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 535 541 /// this class conforms to the \ref concepts::Graph "Graph" concept, 536 /// moreover \c FullGraph does not contain a loop arcfor each537 /// node as \cFullDigraph does.542 /// moreover this class does not contain a loop for each 543 /// node as FullDigraph does. 538 544 /// 539 545 /// \sa FullDigraph … … 543 549 public: 544 550 545 /// \brief Constructor 551 /// \brief Default constructor. 552 /// 553 /// Default constructor. The number of nodes and edges will be zero. 546 554 FullGraph() { construct(0); } 547 555 … … 554 562 /// \brief Resizes the graph 555 563 /// 556 /// Resizes the graph. The function will fully destroyand557 /// rebuild the graph. This cause that the maps of the graph will564 /// This function resizes the graph. It fully destroys and 565 /// rebuilds the structure, therefore the maps of the graph will be 558 566 /// reallocated automatically and the previous values will be lost. 559 567 void resize(int n) { … … 569 577 /// \brief Returns the node with the given index. 570 578 /// 571 /// Returns the node with the given index. Since it is a static572 /// graph its nodes can be indexed with integers from the range573 /// <tt>[0..nodeNum()-1]</tt>.579 /// Returns the node with the given index. Since this structure is 580 /// completely static, the nodes can be indexed with integers from 581 /// the range <tt>[0..nodeNum()-1]</tt>. 574 582 /// \sa index() 575 583 Node operator()(int ix) const { return Parent::operator()(ix); } … … 577 585 /// \brief Returns the index of the given node. 578 586 /// 579 /// Returns the index of the given node. Since it is a static580 /// graph its nodes can be indexed with integers from the range581 /// <tt>[0..nodeNum()-1]</tt>.582 /// \sa operator() 583 int index( const Node&node) const { return Parent::index(node); }587 /// Returns the index of the given node. Since this structure is 588 /// completely static, the nodes can be indexed with integers from 589 /// the range <tt>[0..nodeNum()-1]</tt>. 590 /// \sa operator()() 591 int index(Node node) const { return Parent::index(node); } 584 592 585 593 /// \brief Returns the arc connecting the given nodes. 586 594 /// 587 595 /// Returns the arc connecting the given nodes. 588 Arc arc( const Node& s, const Node&t) const {596 Arc arc(Node s, Node t) const { 589 597 return Parent::arc(s, t); 590 598 } 591 599 592 /// \brief Returns the edge connect sthe given nodes.593 /// 594 /// Returns the edge connect sthe given nodes.595 Edge edge( const Node& u, const Node&v) const {600 /// \brief Returns the edge connecting the given nodes. 601 /// 602 /// Returns the edge connecting the given nodes. 603 Edge edge(Node u, Node v) const { 596 604 return Parent::edge(u, v); 597 605 } -
lemon/grid_graph.h
r617 r735 471 471 /// \brief Grid graph class 472 472 /// 473 /// This classimplements a special graph type. The nodes of the474 /// graph can be indexed by two integer \c (i,j) valuewhere \c i is475 /// in the \c [0..width()-1] range and j is in the \c476 /// [0..height()-1] range.Two nodes are connected in the graph if477 /// the ind exes differ exactly on one position and exactly one is478 /// the difference. The nodes of the graph can be indexed by position479 /// with the \c operator()() function. The positions of the nodes can be480 /// get with\c pos(), \c col() and \c row() members. The outgoing473 /// GridGraph implements a special graph type. The nodes of the 474 /// graph can be indexed by two integer values \c (i,j) where \c i is 475 /// in the range <tt>[0..width()-1]</tt> and j is in the range 476 /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if 477 /// the indices differ exactly on one position and the difference is 478 /// also exactly one. The nodes of the graph can be obtained by position 479 /// using the \c operator()() function and the indices of the nodes can 480 /// be obtained using \c pos(), \c col() and \c row() members. The outgoing 481 481 /// arcs can be retrieved with the \c right(), \c up(), \c left() 482 482 /// and \c down() functions, where the bottom-left corner is the 483 483 /// origin. 484 /// 485 /// This class is completely static and it needs constant memory space. 486 /// Thus you can neither add nor delete nodes or edges, however 487 /// the structure can be resized using resize(). 484 488 /// 485 489 /// \image html grid_graph.png … … 497 501 ///\endcode 498 502 /// 499 /// This graph type fully conforms to the \ref concepts::Graph 500 /// "Graph concept". 503 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 504 /// Most of its member functions and nested classes are documented 505 /// only in the concept class. 501 506 class GridGraph : public ExtendedGridGraphBase { 502 507 typedef ExtendedGridGraphBase Parent; … … 504 509 public: 505 510 506 /// \brief Map to get the indices of the nodes as dim2::Point<int>. 507 /// 508 /// Map to get the indices of the nodes as dim2::Point<int>. 511 /// \brief Map to get the indices of the nodes as \ref dim2::Point 512 /// "dim2::Point<int>". 513 /// 514 /// Map to get the indices of the nodes as \ref dim2::Point 515 /// "dim2::Point<int>". 509 516 class IndexMap { 510 517 public: … … 515 522 516 523 /// \brief Constructor 517 ///518 /// Constructor519 524 IndexMap(const GridGraph& graph) : _graph(graph) {} 520 525 521 526 /// \brief The subscript operator 522 ///523 /// The subscript operator.524 527 Value operator[](Key key) const { 525 528 return _graph.pos(key); … … 541 544 542 545 /// \brief Constructor 543 ///544 /// Constructor545 546 ColMap(const GridGraph& graph) : _graph(graph) {} 546 547 547 548 /// \brief The subscript operator 548 ///549 /// The subscript operator.550 549 Value operator[](Key key) const { 551 550 return _graph.col(key); … … 567 566 568 567 /// \brief Constructor 569 ///570 /// Constructor571 568 RowMap(const GridGraph& graph) : _graph(graph) {} 572 569 573 570 /// \brief The subscript operator 574 ///575 /// The subscript operator.576 571 Value operator[](Key key) const { 577 572 return _graph.row(key); … … 584 579 /// \brief Constructor 585 580 /// 586 /// Construct a grid graph with given size.581 /// Construct a grid graph with the given size. 587 582 GridGraph(int width, int height) { construct(width, height); } 588 583 589 /// \brief Resize the graph 590 /// 591 /// Resize the graph. The function will fully destroy and rebuild 592 /// the graph. This cause that the maps of the graph will 593 /// reallocated automatically and the previous values will be 594 /// lost. 584 /// \brief Resizes the graph 585 /// 586 /// This function resizes the graph. It fully destroys and 587 /// rebuilds the structure, therefore the maps of the graph will be 588 /// reallocated automatically and the previous values will be lost. 595 589 void resize(int width, int height) { 596 590 Parent::notifier(Arc()).clear(); … … 610 604 } 611 605 612 /// \brief Gives back the column index of the node.606 /// \brief The column index of the node. 613 607 /// 614 608 /// Gives back the column index of the node. … … 617 611 } 618 612 619 /// \brief Gives back the row index of the node.613 /// \brief The row index of the node. 620 614 /// 621 615 /// Gives back the row index of the node. … … 624 618 } 625 619 626 /// \brief Gives back the position of the node.620 /// \brief The position of the node. 627 621 /// 628 622 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. … … 631 625 } 632 626 633 /// \brief Gives back the number of the columns.627 /// \brief The number of the columns. 634 628 /// 635 629 /// Gives back the number of the columns. … … 638 632 } 639 633 640 /// \brief Gives back the number of the rows.634 /// \brief The number of the rows. 641 635 /// 642 636 /// Gives back the number of the rows. … … 645 639 } 646 640 647 /// \brief Gives back the arc goes right from the node.641 /// \brief The arc goes right from the node. 648 642 /// 649 643 /// Gives back the arc goes right from the node. If there is not … … 653 647 } 654 648 655 /// \brief Gives back the arc goes left from the node.649 /// \brief The arc goes left from the node. 656 650 /// 657 651 /// Gives back the arc goes left from the node. If there is not … … 661 655 } 662 656 663 /// \brief Gives back the arc goes up from the node.657 /// \brief The arc goes up from the node. 664 658 /// 665 659 /// Gives back the arc goes up from the node. If there is not … … 669 663 } 670 664 671 /// \brief Gives back the arc goes down from the node.665 /// \brief The arc goes down from the node. 672 666 /// 673 667 /// Gives back the arc goes down from the node. If there is not -
lemon/hypercube_graph.h
r617 r735 283 283 /// \brief Hypercube graph class 284 284 /// 285 /// This class implements a special graph type. The nodes of the graph286 /// are indiced with integers withat most \c dim binary digits.285 /// HypercubeGraph implements a special graph type. The nodes of the 286 /// graph are indexed with integers having at most \c dim binary digits. 287 287 /// Two nodes are connected in the graph if and only if their indices 288 288 /// differ only on one position in the binary form. 289 /// This class is completely static and it needs constant memory space. 290 /// Thus you can neither add nor delete nodes or edges. 291 /// 292 /// This type fully conforms to the \ref concepts::Graph "Graph concept". 293 /// Most of its member functions and nested classes are documented 294 /// only in the concept class. 289 295 /// 290 296 /// \note The type of the indices is chosen to \c int for efficiency 291 297 /// reasons. Thus the maximum dimension of this implementation is 26 292 298 /// (assuming that the size of \c int is 32 bit). 293 ///294 /// This graph type fully conforms to the \ref concepts::Graph295 /// "Graph concept".296 299 class HypercubeGraph : public ExtendedHypercubeGraphBase { 297 300 typedef ExtendedHypercubeGraphBase Parent; … … 321 324 /// 322 325 /// Gives back the dimension id of the given edge. 323 /// It is in the [0..dim-1] range.326 /// It is in the range <tt>[0..dim-1]</tt>. 324 327 int dimension(Edge edge) const { 325 328 return Parent::dimension(edge); … … 329 332 /// 330 333 /// Gives back the dimension id of the given arc. 331 /// It is in the [0..dim-1] range.334 /// It is in the range <tt>[0..dim-1]</tt>. 332 335 int dimension(Arc arc) const { 333 336 return Parent::dimension(arc); -
lemon/list_graph.h
r617 r735 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> … … 312 312 ///A general directed graph structure. 313 313 314 ///\ref ListDigraph is a simple and fast <em>directed graph</em>315 ///implementation based on staticlinked lists that are stored in314 ///\ref ListDigraph is a versatile and fast directed graph 315 ///implementation based on linked lists that are stored in 316 316 ///\c std::vector structures. 317 317 /// 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 documented318 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 319 ///and it also provides several useful additional functionalities. 320 ///Most of its member functions and nested classes are documented 321 321 ///only in the concept class. 322 322 /// 323 323 ///\sa concepts::Digraph 324 324 ///\sa ListGraph 325 325 class ListDigraph : public ExtendedListDigraphBase { 326 326 typedef ExtendedListDigraphBase Parent; 327 327 328 328 private: 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 330 331 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 332 /// 329 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 333 330 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. 331 /// \brief Assignment of a digraph to another one is \e not allowed. 332 /// Use DigraphCopy instead. 339 333 void operator=(const ListDigraph &) {} 340 334 public: … … 348 342 ///Add a new node to the digraph. 349 343 350 /// Adda new node to the digraph.344 ///This function adds a new node to the digraph. 351 345 ///\return The new node. 352 346 Node addNode() { return Parent::addNode(); } … … 354 348 ///Add a new arc to the digraph. 355 349 356 /// Adda new arc to the digraph with source node \c s350 ///This function adds a new arc to the digraph with source node \c s 357 351 ///and target node \c t. 358 352 ///\return The new arc. 359 Arc addArc( const Node& s, const Node&t) {353 Arc addArc(Node s, Node t) { 360 354 return Parent::addArc(s, t); 361 355 } … … 363 357 ///\brief Erase a node from the digraph. 364 358 /// 365 ///Erase a node from the digraph. 366 /// 367 void erase(const Node& n) { Parent::erase(n); } 359 ///This function erases the given node from the digraph. 360 void erase(Node n) { Parent::erase(n); } 368 361 369 362 ///\brief Erase an arc from the digraph. 370 363 /// 371 ///Erase an arc from the digraph. 372 /// 373 void erase(const Arc& a) { Parent::erase(a); } 364 ///This function erases the given arc from the digraph. 365 void erase(Arc a) { Parent::erase(a); } 374 366 375 367 /// Node validity check 376 368 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. 369 /// This function gives back \c true if the given node is valid, 370 /// i.e. it is a real node of the digraph. 371 /// 372 /// \warning A removed node could become valid again if new nodes are 373 /// added to the digraph. 383 374 bool valid(Node n) const { return Parent::valid(n); } 384 375 385 376 /// Arc validity check 386 377 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. 378 /// This function gives back \c true if the given arc is valid, 379 /// i.e. it is a real arc of the digraph. 380 /// 381 /// \warning A removed arc could become valid again if new arcs are 382 /// added to the digraph. 393 383 bool valid(Arc a) const { return Parent::valid(a); } 394 384 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. 385 /// Change the target node of an arc 386 387 /// This function changes the target node of the given arc \c a to \c n. 388 /// 389 ///\note \c ArcIt and \c OutArcIt iterators referencing the changed 390 ///arc remain valid, however \c InArcIt iterators are invalidated. 402 391 /// 403 392 ///\warning This functionality cannot be used together with the Snapshot … … 406 395 Parent::changeTarget(a,n); 407 396 } 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. 397 /// Change the source node of an arc 398 399 /// This function changes the source node of the given arc \c a to \c n. 400 /// 401 ///\note \c InArcIt iterators referencing the changed arc remain 402 ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. 415 403 /// 416 404 ///\warning This functionality cannot be used together with the Snapshot … … 420 408 } 421 409 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.410 /// Reverse the direction of an arc. 411 412 /// This function reverses the direction of the given arc. 413 ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing 414 ///the changed arc are invalidated. 427 415 /// 428 416 ///\warning This functionality cannot be used together with the Snapshot 429 417 ///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); }; 418 void reverseArc(Arc a) { 419 Node t=target(a); 420 changeTarget(a,source(a)); 421 changeSource(a,t); 422 } 455 423 456 424 ///Contract two nodes. 457 425 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. 426 ///This function contracts the given two nodes. 427 ///Node \c v is removed, but instead of deleting its 428 ///incident arcs, they are joined to node \c u. 429 ///If the last parameter \c r is \c true (this is the default value), 430 ///then the newly created loops are removed. 431 /// 432 ///\note The moved arcs are joined to node \c u using changeSource() 433 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are 434 ///invalidated for the outgoing arcs of node \c v and \c InArcIt 435 ///iterators are invalidated for the incomming arcs of \c v. 436 ///Moreover all iterators referencing node \c v or the removed 437 ///loops are also invalidated. Other iterators remain valid. 467 438 /// 468 439 ///\warning This functionality cannot be used together with the Snapshot 469 440 ///feature. 470 void contract(Node a, Node b, bool r = true)441 void contract(Node u, Node v, bool r = true) 471 442 { 472 for(OutArcIt e(*this, b);e!=INVALID;) {443 for(OutArcIt e(*this,v);e!=INVALID;) { 473 444 OutArcIt f=e; 474 445 ++f; 475 if(r && target(e)== a) erase(e);476 else changeSource(e, a);446 if(r && target(e)==u) erase(e); 447 else changeSource(e,u); 477 448 e=f; 478 449 } 479 for(InArcIt e(*this, b);e!=INVALID;) {450 for(InArcIt e(*this,v);e!=INVALID;) { 480 451 InArcIt f=e; 481 452 ++f; 482 if(r && source(e)== a) erase(e);483 else changeTarget(e, a);453 if(r && source(e)==u) erase(e); 454 else changeTarget(e,u); 484 455 e=f; 485 456 } 486 erase( b);457 erase(v); 487 458 } 488 459 489 460 ///Split a node. 490 461 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. 462 ///This function splits the given node. First, a new node is added 463 ///to the digraph, then the source of each outgoing arc of node \c n 464 ///is moved to this new node. 465 ///If the second parameter \c connect is \c true (this is the default 466 ///value), then a new arc from node \c n to the newly created node 467 ///is also added. 495 468 ///\return The newly created node. 496 469 /// 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 470 ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing 471 ///arcs of node \c n are invalidated. Other iterators remain valid. 472 /// 473 ///\warning This functionality cannot be used together with the 502 474 ///Snapshot feature. 503 475 Node split(Node n, bool connect = true) { … … 515 487 ///Split an arc. 516 488 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 /// 489 ///This function splits the given arc. First, a new node \c v is 490 ///added to the digraph, then the target node of the original arc 491 ///is set to \c v. Finally, an arc from \c v to the original target 492 ///is added. 521 493 ///\return The newly created node. 494 /// 495 ///\note \c InArcIt iterators referencing the original arc are 496 ///invalidated. Other iterators remain valid. 522 497 /// 523 498 ///\warning This functionality cannot be used together with the 524 499 ///Snapshot feature. 525 Node split(Arc e) { 526 Node b = addNode(); 527 addArc(b,target(e)); 528 changeTarget(e,b); 529 return b; 530 } 500 Node split(Arc a) { 501 Node v = addNode(); 502 addArc(v,target(a)); 503 changeTarget(a,v); 504 return v; 505 } 506 507 ///Clear the digraph. 508 509 ///This function erases all nodes and arcs from the digraph. 510 /// 511 void clear() { 512 Parent::clear(); 513 } 514 515 /// Reserve memory for nodes. 516 517 /// Using this function, it is possible to avoid superfluous memory 518 /// allocation: if you know that the digraph you want to build will 519 /// be large (e.g. it will contain millions of nodes and/or arcs), 520 /// then it is worth reserving space for this amount before starting 521 /// to build the digraph. 522 /// \sa reserveArc() 523 void reserveNode(int n) { nodes.reserve(n); }; 524 525 /// Reserve memory for arcs. 526 527 /// Using this function, it is possible to avoid superfluous memory 528 /// allocation: if you know that the digraph you want to build will 529 /// be large (e.g. it will contain millions of nodes and/or arcs), 530 /// then it is worth reserving space for this amount before starting 531 /// to build the digraph. 532 /// \sa reserveNode() 533 void reserveArc(int m) { arcs.reserve(m); }; 531 534 532 535 /// \brief Class to make a snapshot of the digraph and restore … … 538 541 /// restore() function. 539 542 /// 540 /// \warning Arc and node deletions and other modifications (e.g. 541 /// contracting, splitting, reversing arcs or nodes) cannot be 543 /// \note After a state is restored, you cannot restore a later state, 544 /// i.e. you cannot add the removed nodes and arcs again using 545 /// another Snapshot instance. 546 /// 547 /// \warning Node and arc deletions and other modifications (e.g. 548 /// reversing, contracting, splitting arcs or nodes) cannot be 542 549 /// restored. These events invalidate the snapshot. 550 /// However the arcs and nodes that were added to the digraph after 551 /// making the current snapshot can be removed without invalidating it. 543 552 class Snapshot { 544 553 protected: … … 710 719 /// 711 720 /// Default constructor. 712 /// To actually make a snapshot you must call save().721 /// You have to call save() to actually make a snapshot. 713 722 Snapshot() 714 723 : digraph(0), node_observer_proxy(*this), … … 717 726 /// \brief Constructor that immediately makes a snapshot. 718 727 /// 719 /// This constructor immediately makes a snapshot of the digraph. 720 /// \param _digraph The digraph we make a snapshot of. 721 Snapshot(ListDigraph &_digraph) 728 /// This constructor immediately makes a snapshot of the given digraph. 729 Snapshot(ListDigraph &gr) 722 730 : node_observer_proxy(*this), 723 731 arc_observer_proxy(*this) { 724 attach( _digraph);732 attach(gr); 725 733 } 726 734 727 735 /// \brief Make a snapshot. 728 736 /// 729 /// Make a snapshot of the digraph. 730 /// 731 /// This function can be called more than once. In case of a repeated 737 /// This function makes a snapshot of the given digraph. 738 /// It can be called more than once. In case of a repeated 732 739 /// call, the previous snapshot gets lost. 733 /// \param _digraph The digraph we make the snapshot of. 734 void save(ListDigraph &_digraph) { 740 void save(ListDigraph &gr) { 735 741 if (attached()) { 736 742 detach(); 737 743 clear(); 738 744 } 739 attach( _digraph);745 attach(gr); 740 746 } 741 747 742 748 /// \brief Undo the changes until the last snapshot. 743 // 744 /// Undo the changes until the last snapshot created by save(). 749 /// 750 /// This function undos the changes until the last snapshot 751 /// created by save() or Snapshot(ListDigraph&). 745 752 void restore() { 746 753 detach(); … … 756 763 } 757 764 758 /// \brief Gives back true whenthe snapshot is valid.765 /// \brief Returns \c true if the snapshot is valid. 759 766 /// 760 /// Gives back true whenthe snapshot is valid.767 /// This function returns \c true if the snapshot is valid. 761 768 bool valid() const { 762 769 return attached(); … … 795 802 796 803 typedef ListGraphBase Graph; 797 798 class Node;799 class Arc;800 class Edge;801 804 802 805 class Node { … … 848 851 bool operator<(const Arc& arc) const {return id < arc.id;} 849 852 }; 850 851 852 853 853 854 ListGraphBase() … … 1165 1166 ///A general undirected graph structure. 1166 1167 1167 ///\ref ListGraph is a simple and fast <em>undirected graph</em>1168 ///implementation based on staticlinked lists that are stored in1168 ///\ref ListGraph is a versatile and fast undirected graph 1169 ///implementation based on linked lists that are stored in 1169 1170 ///\c std::vector structures. 1170 1171 /// 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 documented1172 ///This type fully conforms to the \ref concepts::Graph "Graph concept" 1173 ///and it also provides several useful additional functionalities. 1174 ///Most of its member functions and nested classes are documented 1174 1175 ///only in the concept class. 1175 1176 /// 1176 1177 ///\sa concepts::Graph 1177 1178 ///\sa ListDigraph 1178 1179 class ListGraph : public ExtendedListGraphBase { 1179 1180 typedef ExtendedListGraphBase Parent; 1180 1181 1181 1182 private: 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1183 1184 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1185 /// 1183 /// Graphs are \e not copy constructible. Use GraphCopy instead. 1186 1184 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. 1185 /// \brief Assignment of a graph to another one is \e not allowed. 1186 /// Use GraphCopy instead. 1192 1187 void operator=(const ListGraph &) {} 1193 1188 public: … … 1202 1197 /// \brief Add a new node to the graph. 1203 1198 /// 1204 /// Adda new node to the graph.1199 /// This function adds a new node to the graph. 1205 1200 /// \return The new node. 1206 1201 Node addNode() { return Parent::addNode(); } … … 1208 1203 /// \brief Add a new edge to the graph. 1209 1204 /// 1210 /// Add a new edge to the graph with source node \c s 1211 /// and target node \c t. 1205 /// This function adds a new edge to the graph between nodes 1206 /// \c u and \c v with inherent orientation from node \c u to 1207 /// node \c v. 1212 1208 /// \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); } 1209 Edge addEdge(Node u, Node v) { 1210 return Parent::addEdge(u, v); 1211 } 1212 1213 ///\brief Erase a node from the graph. 1214 /// 1215 /// This function erases the given node from the graph. 1216 void erase(Node n) { Parent::erase(n); } 1217 1218 ///\brief Erase an edge from the graph. 1219 /// 1220 /// This function erases the given edge from the graph. 1221 void erase(Edge e) { Parent::erase(e); } 1228 1222 /// Node validity check 1229 1223 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 1224 /// This function gives back \c true if the given node is valid, 1225 /// i.e. it is a real node of the graph. 1226 /// 1227 /// \warning A removed node could become valid again if new nodes are 1235 1228 /// added to the graph. 1236 1229 bool valid(Node n) const { return Parent::valid(n); } 1230 /// Edge validity check 1231 1232 /// This function gives back \c true if the given edge is valid, 1233 /// i.e. it is a real edge of the graph. 1234 /// 1235 /// \warning A removed edge could become valid again if new edges are 1236 /// added to the graph. 1237 bool valid(Edge e) const { return Parent::valid(e); } 1237 1238 /// Arc validity check 1238 1239 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 1240 /// This function gives back \c true if the given arc is valid, 1241 /// i.e. it is a real arc of the graph. 1242 /// 1243 /// \warning A removed arc could become valid again if new edges are 1244 1244 /// added to the graph. 1245 1245 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. 1246 1247 /// \brief Change the first node of an edge. 1248 /// 1249 /// This function changes the first node of the given edge \c e to \c n. 1250 /// 1251 ///\note \c EdgeIt and \c ArcIt iterators referencing the 1252 ///changed edge are invalidated and all other iterators whose 1253 ///base node is the changed node are also invalidated. 1263 1254 /// 1264 1255 ///\warning This functionality cannot be used together with the … … 1267 1258 Parent::changeU(e,n); 1268 1259 } 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. 1260 /// \brief Change the second node of an edge. 1261 /// 1262 /// This function changes the second node of the given edge \c e to \c n. 1263 /// 1264 ///\note \c EdgeIt iterators referencing the changed edge remain 1265 ///valid, however \c ArcIt iterators referencing the changed edge and 1266 ///all other iterators whose base node is the changed node are also 1267 ///invalidated. 1276 1268 /// 1277 1269 ///\warning This functionality cannot be used together with the … … 1280 1272 Parent::changeV(e,n); 1281 1273 } 1274 1282 1275 /// \brief Contract two nodes. 1283 1276 /// 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. 1277 /// This function contracts the given two nodes. 1278 /// Node \c b is removed, but instead of deleting 1279 /// its incident edges, they are joined to node \c a. 1280 /// If the last parameter \c r is \c true (this is the default value), 1281 /// then the newly created loops are removed. 1282 /// 1283 /// \note The moved edges are joined to node \c a using changeU() 1284 /// or changeV(), thus all edge and arc iterators whose base node is 1285 /// \c b are invalidated. 1286 /// Moreover all iterators referencing node \c b or the removed 1287 /// loops are also invalidated. Other iterators remain valid. 1292 1288 /// 1293 1289 ///\warning This functionality cannot be used together with the … … 1308 1304 } 1309 1305 1306 ///Clear the graph. 1307 1308 ///This function erases all nodes and arcs from the graph. 1309 /// 1310 void clear() { 1311 Parent::clear(); 1312 } 1310 1313 1311 1314 /// \brief Class to make a snapshot of the graph and restore … … 1317 1320 /// using the restore() function. 1318 1321 /// 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. 1322 /// \note After a state is restored, you cannot restore a later state, 1323 /// i.e. you cannot add the removed nodes and edges again using 1324 /// another Snapshot instance. 1325 /// 1326 /// \warning Node and edge deletions and other modifications 1327 /// (e.g. changing the end-nodes of edges or contracting nodes) 1328 /// cannot be restored. These events invalidate the snapshot. 1329 /// However the edges and nodes that were added to the graph after 1330 /// making the current snapshot can be removed without invalidating it. 1322 1331 class Snapshot { 1323 1332 protected: … … 1489 1498 /// 1490 1499 /// Default constructor. 1491 /// To actually make a snapshot you must call save().1500 /// You have to call save() to actually make a snapshot. 1492 1501 Snapshot() 1493 1502 : graph(0), node_observer_proxy(*this), … … 1496 1505 /// \brief Constructor that immediately makes a snapshot. 1497 1506 /// 1498 /// This constructor immediately makes a snapshot of the graph. 1499 /// \param _graph The graph we make a snapshot of. 1500 Snapshot(ListGraph &_graph) 1507 /// This constructor immediately makes a snapshot of the given graph. 1508 Snapshot(ListGraph &gr) 1501 1509 : node_observer_proxy(*this), 1502 1510 edge_observer_proxy(*this) { 1503 attach( _graph);1511 attach(gr); 1504 1512 } 1505 1513 1506 1514 /// \brief Make a snapshot. 1507 1515 /// 1508 /// Make a snapshot of the graph. 1509 /// 1510 /// This function can be called more than once. In case of a repeated 1516 /// This function makes a snapshot of the given graph. 1517 /// It can be called more than once. In case of a repeated 1511 1518 /// call, the previous snapshot gets lost. 1512 /// \param _graph The graph we make the snapshot of. 1513 void save(ListGraph &_graph) { 1519 void save(ListGraph &gr) { 1514 1520 if (attached()) { 1515 1521 detach(); 1516 1522 clear(); 1517 1523 } 1518 attach( _graph);1524 attach(gr); 1519 1525 } 1520 1526 1521 1527 /// \brief Undo the changes until the last snapshot. 1522 // 1523 /// Undo the changes until the last snapshot created by save(). 1528 /// 1529 /// This function undos the changes until the last snapshot 1530 /// created by save() or Snapshot(ListGraph&). 1524 1531 void restore() { 1525 1532 detach(); … … 1535 1542 } 1536 1543 1537 /// \brief Gives back true whenthe snapshot is valid.1544 /// \brief Returns \c true if the snapshot is valid. 1538 1545 /// 1539 /// Gives back true whenthe snapshot is valid.1546 /// This function returns \c true if the snapshot is valid. 1540 1547 bool valid() const { 1541 1548 return attached(); -
lemon/smart_graph.h
r617 r735 33 33 34 34 class SmartDigraph; 35 ///Base of SmartDigraph 36 37 ///Base of SmartDigraph 38 /// 35 39 36 class SmartDigraphBase { 40 37 protected: … … 188 185 ///\brief A smart directed graph class. 189 186 /// 190 ///This is a simple and fast digraph implementation. 191 ///It is also quite memory efficient, but at the price 192 ///that <b> it does support only limited (only stack-like) 193 ///node and arc deletions</b>. 194 ///It fully conforms to the \ref concepts::Digraph "Digraph concept". 187 ///\ref SmartDigraph is a simple and fast digraph implementation. 188 ///It is also quite memory efficient but at the price 189 ///that it does not support node and arc deletion 190 ///(except for the Snapshot feature). 195 191 /// 196 ///\sa concepts::Digraph. 192 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" 193 ///and it also provides some additional functionalities. 194 ///Most of its member functions and nested classes are documented 195 ///only in the concept class. 196 /// 197 ///\sa concepts::Digraph 198 ///\sa SmartGraph 197 199 class SmartDigraph : public ExtendedSmartDigraphBase { 198 200 typedef ExtendedSmartDigraphBase Parent; 199 201 200 202 private: 201 202 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 203 204 ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. 205 /// 203 /// Digraphs are \e not copy constructible. Use DigraphCopy instead. 206 204 SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; 207 ///\brief Assignment of SmartDigraph to another one is \e not allowed. 208 ///Use DigraphCopy() instead. 209 210 ///Assignment of SmartDigraph to another one is \e not allowed. 211 ///Use DigraphCopy() instead. 205 /// \brief Assignment of a digraph to another one is \e not allowed. 206 /// Use DigraphCopy instead. 212 207 void operator=(const SmartDigraph &) {} 213 208 … … 222 217 ///Add a new node to the digraph. 223 218 224 /// Adda new node to the digraph.225 /// 219 ///This function adds a new node to the digraph. 220 ///\return The new node. 226 221 Node addNode() { return Parent::addNode(); } 227 222 228 223 ///Add a new arc to the digraph. 229 224 230 /// Adda new arc to the digraph with source node \c s225 ///This function adds a new arc to the digraph with source node \c s 231 226 ///and target node \c t. 232 227 ///\return The new arc. 233 Arc addArc( const Node& s, const Node&t) {228 Arc addArc(Node s, Node t) { 234 229 return Parent::addArc(s, t); 235 230 } 236 231 237 /// \brief Using this it is possible to avoid the superfluous memory238 /// allocation.239 240 /// Using this it is possible to avoid the superfluous memory241 /// allocation: if you know that the digraph you want to build will242 /// be very large (e.g. it will contain millions of nodes and/or arcs)243 /// then it is worth reserving space for this amount before starting244 /// to build the digraph.245 /// \sa reserveArc246 void reserveNode(int n) { nodes.reserve(n); };247 248 /// \brief Using this it is possible to avoid the superfluous memory249 /// allocation.250 251 /// Using this it is possible to avoid the superfluous memory252 /// allocation: if you know that the digraph you want to build will253 /// be very large (e.g. it will contain millions of nodes and/or arcs)254 /// then it is worth reserving space for this amount before starting255 /// to build the digraph.256 /// \sa reserveNode257 void reserveArc(int m) { arcs.reserve(m); };258 259 232 /// \brief Node validity check 260 233 /// 261 /// This function gives back true if the given node is valid,262 /// i e. it is a real node of thegraph.234 /// This function gives back \c true if the given node is valid, 235 /// i.e. it is a real node of the digraph. 263 236 /// 264 237 /// \warning A removed node (using Snapshot) could become valid again 265 /// when new nodes are added to thegraph.238 /// if new nodes are added to the digraph. 266 239 bool valid(Node n) const { return Parent::valid(n); } 267 240 268 241 /// \brief Arc validity check 269 242 /// 270 /// This function gives back true if the given arc is valid,271 /// i e. it is a real arc of thegraph.243 /// This function gives back \c true if the given arc is valid, 244 /// i.e. it is a real arc of the digraph. 272 245 /// 273 246 /// \warning A removed arc (using Snapshot) could become valid again 274 /// whennew arcs are added to the graph.247 /// if new arcs are added to the graph. 275 248 bool valid(Arc a) const { return Parent::valid(a); } 276 249 277 ///Clear the digraph.278 279 ///Erase all the nodes and arcs from the digraph.280 ///281 void clear() {282 Parent::clear();283 }284 285 250 ///Split a node. 286 251 287 ///This function splits a node. First a new node is added to the digraph, 288 ///then the source of each outgoing arc of \c n is moved to this new node. 289 ///If \c connect is \c true (this is the default value), then a new arc 290 ///from \c n to the newly created node is also added. 252 ///This function splits the given node. First, a new node is added 253 ///to the digraph, then the source of each outgoing arc of node \c n 254 ///is moved to this new node. 255 ///If the second parameter \c connect is \c true (this is the default 256 ///value), then a new arc from node \c n to the newly created node 257 ///is also added. 291 258 ///\return The newly created node. 292 259 /// 293 ///\note The <tt>Arc</tt>s 294 ///referencing a moved arc remain 295 ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s 296 ///may be invalidated. 260 ///\note All iterators remain valid. 261 /// 297 262 ///\warning This functionality cannot be used together with the Snapshot 298 263 ///feature. … … 309 274 } 310 275 276 ///Clear the digraph. 277 278 ///This function erases all nodes and arcs from the digraph. 279 /// 280 void clear() { 281 Parent::clear(); 282 } 283 284 /// Reserve memory for nodes. 285 286 /// Using this function, it is possible to avoid superfluous memory 287 /// allocation: if you know that the digraph you want to build will 288 /// be large (e.g. it will contain millions of nodes and/or arcs), 289 /// then it is worth reserving space for this amount before starting 290 /// to build the digraph. 291 /// \sa reserveArc() 292 void reserveNode(int n) { nodes.reserve(n); }; 293 294 /// Reserve memory for arcs. 295 296 /// Using this function, it is possible to avoid superfluous memory 297 /// allocation: if you know that the digraph you want to build will 298 /// be large (e.g. it will contain millions of nodes and/or arcs), 299 /// then it is worth reserving space for this amount before starting 300 /// to build the digraph. 301 /// \sa reserveNode() 302 void reserveArc(int m) { arcs.reserve(m); }; 303 311 304 public: 312 305 … … 333 326 public: 334 327 335 ///Class to make a snapshot of the digraph and to rest rore toit later.336 337 ///Class to make a snapshot of the digraph and to rest rore toit later.328 ///Class to make a snapshot of the digraph and to restore it later. 329 330 ///Class to make a snapshot of the digraph and to restore it later. 338 331 /// 339 332 ///The newly added nodes and arcs can be removed using the 340 ///restore() function. 341 ///\note After you restore a state, you cannot restore 342 ///a later state, in other word you cannot add again the arcs deleted 343 ///by restore() using another one Snapshot instance. 344 /// 345 ///\warning If you do not use correctly the snapshot that can cause 346 ///either broken program, invalid state of the digraph, valid but 347 ///not the restored digraph or no change. Because the runtime performance 348 ///the validity of the snapshot is not stored. 333 ///restore() function. This is the only way for deleting nodes and/or 334 ///arcs from a SmartDigraph structure. 335 /// 336 ///\note After a state is restored, you cannot restore a later state, 337 ///i.e. you cannot add the removed nodes and arcs again using 338 ///another Snapshot instance. 339 /// 340 ///\warning Node splitting cannot be restored. 341 ///\warning The validity of the snapshot is not stored due to 342 ///performance reasons. If you do not use the snapshot correctly, 343 ///it can cause broken program, invalid or not restored state of 344 ///the digraph or no change. 349 345 class Snapshot 350 346 { … … 358 354 359 355 ///Default constructor. 360 ///To actually make a snapshot you must call save(). 361 /// 356 ///You have to call save() to actually make a snapshot. 362 357 Snapshot() : _graph(0) {} 363 358 ///Constructor that immediately makes a snapshot 364 359 365 ///This constructor immediately makes a snapshot of the digraph.366 /// \param graph The digraph we make a snapshot of.367 Snapshot(SmartDigraph &gr aph) : _graph(&graph) {360 ///This constructor immediately makes a snapshot of the given digraph. 361 /// 362 Snapshot(SmartDigraph &gr) : _graph(&gr) { 368 363 node_num=_graph->nodes.size(); 369 364 arc_num=_graph->arcs.size(); … … 372 367 ///Make a snapshot. 373 368 374 ///Make a snapshot of the digraph. 375 /// 376 ///This function can be called more than once. In case of a repeated 369 ///This function makes a snapshot of the given digraph. 370 ///It can be called more than once. In case of a repeated 377 371 ///call, the previous snapshot gets lost. 378 ///\param graph The digraph we make the snapshot of. 379 void save(SmartDigraph &graph) 380 { 381 _graph=&graph; 372 void save(SmartDigraph &gr) { 373 _graph=&gr; 382 374 node_num=_graph->nodes.size(); 383 375 arc_num=_graph->arcs.size(); … … 386 378 ///Undo the changes until a snapshot. 387 379 388 ///Undo the changes until a snapshot created by save(). 389 /// 390 ///\note After you restored a state, you cannot restore 391 ///a later state, in other word you cannot add again the arcs deleted 392 ///by restore(). 380 ///This function undos the changes until the last snapshot 381 ///created by save() or Snapshot(SmartDigraph&). 393 382 void restore() 394 383 { … … 622 611 /// \brief A smart undirected graph class. 623 612 /// 624 /// This is a simple and fast graph implementation. 625 /// It is also quite memory efficient, but at the price 626 /// that <b> it does support only limited (only stack-like) 627 /// node and arc deletions</b>. 628 /// It fully conforms to the \ref concepts::Graph "Graph concept". 613 /// \ref SmartGraph is a simple and fast graph implementation. 614 /// It is also quite memory efficient but at the price 615 /// that it does not support node and edge deletion 616 /// (except for the Snapshot feature). 629 617 /// 630 /// \sa concepts::Graph. 618 /// This type fully conforms to the \ref concepts::Graph "Graph concept" 619 /// and it also provides some additional functionalities. 620 /// Most of its member functions and nested classes are documented 621 /// only in the concept class. 622 /// 623 /// \sa concepts::Graph 624 /// \sa SmartDigraph 631 625 class SmartGraph : public ExtendedSmartGraphBase { 632 626 typedef ExtendedSmartGraphBase Parent; 633 627 634 628 private: 635 636 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 637 638 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 639 /// 629 /// Graphs are \e not copy constructible. Use GraphCopy instead. 640 630 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 641 642 ///\brief Assignment of SmartGraph to another one is \e not allowed. 643 ///Use GraphCopy() instead. 644 645 ///Assignment of SmartGraph to another one is \e not allowed. 646 ///Use GraphCopy() instead. 631 /// \brief Assignment of a graph to another one is \e not allowed. 632 /// Use GraphCopy instead. 647 633 void operator=(const SmartGraph &) {} 648 634 … … 655 641 SmartGraph() {} 656 642 657 /// Add a new node to the graph.658 659 /// Adda new node to the graph.643 /// \brief Add a new node to the graph. 644 /// 645 /// This function adds a new node to the graph. 660 646 /// \return The new node. 661 647 Node addNode() { return Parent::addNode(); } 662 648 663 ///Add a new edge to the graph. 664 665 ///Add a new edge to the graph with node \c s 666 ///and \c t. 667 ///\return The new edge. 668 Edge addEdge(const Node& s, const Node& t) { 669 return Parent::addEdge(s, t); 649 /// \brief Add a new edge to the graph. 650 /// 651 /// This function adds a new edge to the graph between nodes 652 /// \c u and \c v with inherent orientation from node \c u to 653 /// node \c v. 654 /// \return The new edge. 655 Edge addEdge(Node u, Node v) { 656 return Parent::addEdge(u, v); 670 657 } 671 658 672 659 /// \brief Node validity check 673 660 /// 674 /// This function gives back true if the given node is valid,675 /// i e. it is a real node of the graph.661 /// This function gives back \c true if the given node is valid, 662 /// i.e. it is a real node of the graph. 676 663 /// 677 664 /// \warning A removed node (using Snapshot) could become valid again 678 /// whennew nodes are added to the graph.665 /// if new nodes are added to the graph. 679 666 bool valid(Node n) const { return Parent::valid(n); } 680 667 668 /// \brief Edge validity check 669 /// 670 /// This function gives back \c true if the given edge is valid, 671 /// i.e. it is a real edge of the graph. 672 /// 673 /// \warning A removed edge (using Snapshot) could become valid again 674 /// if new edges are added to the graph. 675 bool valid(Edge e) const { return Parent::valid(e); } 676 681 677 /// \brief Arc validity check 682 678 /// 683 /// This function gives back true if the given arc is valid,684 /// i e. it is a real arc of the graph.679 /// This function gives back \c true if the given arc is valid, 680 /// i.e. it is a real arc of the graph. 685 681 /// 686 682 /// \warning A removed arc (using Snapshot) could become valid again 687 /// whennew edges are added to the graph.683 /// if new edges are added to the graph. 688 684 bool valid(Arc a) const { return Parent::valid(a); } 689 685 690 /// \brief Edge validity check691 ///692 /// This function gives back true if the given edge is valid,693 /// ie. it is a real edge of the graph.694 ///695 /// \warning A removed edge (using Snapshot) could become valid again696 /// when new edges are added to the graph.697 bool valid(Edge e) const { return Parent::valid(e); }698 699 686 ///Clear the graph. 700 687 701 /// Erase all the nodes and edges from the graph.688 ///This function erases all nodes and arcs from the graph. 702 689 /// 703 690 void clear() { … … 743 730 public: 744 731 745 ///Class to make a snapshot of the digraph and to restrore to it later. 746 747 ///Class to make a snapshot of the digraph and to restrore to it later. 748 /// 749 ///The newly added nodes and arcs can be removed using the 750 ///restore() function. 751 /// 752 ///\note After you restore a state, you cannot restore 753 ///a later state, in other word you cannot add again the arcs deleted 754 ///by restore() using another one Snapshot instance. 755 /// 756 ///\warning If you do not use correctly the snapshot that can cause 757 ///either broken program, invalid state of the digraph, valid but 758 ///not the restored digraph or no change. Because the runtime performance 759 ///the validity of the snapshot is not stored. 732 ///Class to make a snapshot of the graph and to restore it later. 733 734 ///Class to make a snapshot of the graph and to restore it later. 735 /// 736 ///The newly added nodes and edges can be removed using the 737 ///restore() function. This is the only way for deleting nodes and/or 738 ///edges from a SmartGraph structure. 739 /// 740 ///\note After a state is restored, you cannot restore a later state, 741 ///i.e. you cannot add the removed nodes and edges again using 742 ///another Snapshot instance. 743 /// 744 ///\warning The validity of the snapshot is not stored due to 745 ///performance reasons. If you do not use the snapshot correctly, 746 ///it can cause broken program, invalid or not restored state of 747 ///the graph or no change. 760 748 class Snapshot 761 749 { … … 769 757 770 758 ///Default constructor. 771 ///To actually make a snapshot you must call save(). 772 /// 759 ///You have to call save() to actually make a snapshot. 773 760 Snapshot() : _graph(0) {} 774 761 ///Constructor that immediately makes a snapshot 775 762 776 /// This constructor immediately makes a snapshot of the digraph.777 /// \param graph The digraph we make a snapshot of.778 Snapshot(SmartGraph &gr aph) {779 gr aph.saveSnapshot(*this);763 /// This constructor immediately makes a snapshot of the given graph. 764 /// 765 Snapshot(SmartGraph &gr) { 766 gr.saveSnapshot(*this); 780 767 } 781 768 782 769 ///Make a snapshot. 783 770 784 ///Make a snapshot of the graph. 785 /// 786 ///This function can be called more than once. In case of a repeated 771 ///This function makes a snapshot of the given graph. 772 ///It can be called more than once. In case of a repeated 787 773 ///call, the previous snapshot gets lost. 788 ///\param graph The digraph we make the snapshot of. 789 void save(SmartGraph &graph) 774 void save(SmartGraph &gr) 790 775 { 791 graph.saveSnapshot(*this); 792 } 793 794 ///Undo the changes until a snapshot. 795 796 ///Undo the changes until a snapshot created by save(). 797 /// 798 ///\note After you restored a state, you cannot restore 799 ///a later state, in other word you cannot add again the arcs deleted 800 ///by restore(). 776 gr.saveSnapshot(*this); 777 } 778 779 ///Undo the changes until the last snapshot. 780 781 ///This function undos the changes until the last snapshot 782 ///created by save() or Snapshot(SmartGraph&). 801 783 void restore() 802 784 {
Note: See TracChangeset
for help on using the changeset viewer.