Changeset 782:853fcddcf282 in lemon for lemon
- Timestamp:
- 08/23/09 11:09:22 (15 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r664 r782 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
r664 r782 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
r664 r782 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
r664 r782 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
r664 r782 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.