Changeset 97:ee1324c91288 in lemon for lemon/path.h
- Timestamp:
- 01/24/08 17:49:10 (17 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/path.h
r96 r97 44 44 /// 45 45 /// In a sense, the path can be treated as a list of arcs. The 46 /// lemon path type stores just this list. As a consequence it47 /// cannot enumerate the nodes in the path and the zero length paths48 /// cannot store the source.46 /// lemon path type stores just this list. As a consequence, it 47 /// cannot enumerate the nodes of the path and the source node of 48 /// a zero length path is undefined. 49 49 /// 50 50 /// This implementation is a back and front insertable and erasable 51 51 /// path type. It can be indexed in O(1) time. The front and back 52 /// insertion and erasure is amortized O(1) time. The 53 /// impelementation is based on two opposite organized vectors. 52 /// insertion and erase is done in O(1) (amortized) time. The 53 /// implementation uses two vectors for storing the front and back 54 /// insertions. 54 55 template <typename _Digraph> 55 56 class Path { … … 66 67 /// \brief Template copy constructor 67 68 /// 68 /// This path can be initialized with any other path type. It just69 /// makes a copy of the given path.69 /// This constuctor initializes the path from any other path type. 70 /// It simply makes a copy of the given path. 70 71 template <typename CPath> 71 72 Path(const CPath& cpath) { … … 75 76 /// \brief Template copy assignment 76 77 /// 77 /// This path can be initialized with any other path type. It just 78 /// makes a copy of the given path. 78 /// This operator makes a copy of a path of any other type. 79 79 template <typename CPath> 80 80 Path& operator=(const CPath& cpath) { … … 93 93 /// \brief Invalid constructor 94 94 ArcIt(Invalid) : path(0), idx(-1) {} 95 /// \brief Initializate the constructor to the first arc of path95 /// \brief Initializate the iterator to the first arc of path 96 96 ArcIt(const Path &_path) 97 97 : path(&_path), idx(_path.empty() ? -1 : 0) {} … … 130 130 /// \brief Length of the path. 131 131 int length() const { return head.size() + tail.size(); } 132 /// \brief Return swhether the path is empty.132 /// \brief Return whether the path is empty. 133 133 bool empty() const { return head.empty() && tail.empty(); } 134 134 135 /// \brief Reset s the path to an empty path.135 /// \brief Reset the path to an empty one. 136 136 void clear() { head.clear(); tail.clear(); } 137 137 138 /// \brief Gives back the nth arc.138 /// \brief The nth arc. 139 139 /// 140 140 /// \pre n is in the [0..length() - 1] range … … 144 144 } 145 145 146 /// \brief Initialize sarc iterator to point to the nth arc146 /// \brief Initialize arc iterator to point to the nth arc 147 147 /// 148 148 /// \pre n is in the [0..length() - 1] range … … 151 151 } 152 152 153 /// \brief Gives back the first arc of the path153 /// \brief The first arc of the path 154 154 const Arc& front() const { 155 155 return head.empty() ? tail.front() : head.back(); … … 176 176 } 177 177 178 /// \brief Gives back the last arc of the path178 /// \brief The last arc of the path 179 179 const Arc& back() const { 180 180 return tail.empty() ? head.front() : tail.back(); … … 200 200 } 201 201 202 203 204 202 typedef True BuildTag; 205 203 … … 324 322 /// \brief Length of the path. 325 323 int length() const { return data.size(); } 326 /// \brief Return s whetherthe path is empty.324 /// \brief Return true if the path is empty. 327 325 bool empty() const { return data.empty(); } 328 326 329 /// \brief Reset s the path to an empty path.327 /// \brief Reset the path to an empty one. 330 328 void clear() { data.clear(); } 331 329 332 /// \brief Gives back the nth arc.330 /// \brief The nth arc. 333 331 /// 334 332 /// \pre n is in the [0..length() - 1] range … … 342 340 } 343 341 344 /// \brief Gives back the first arc of the path.342 /// \brief The first arc of the path. 345 343 const Arc& front() const { 346 344 return data.front(); 347 345 } 348 346 349 /// \brief Gives back the last arc of the path.347 /// \brief The last arc of the path. 350 348 const Arc& back() const { 351 349 return data.back(); … … 507 505 }; 508 506 509 /// \brief Gives back the nth arc.510 /// 511 /// Gives backthe nth arc in O(n) time.507 /// \brief The nth arc. 508 /// 509 /// This function looks for the nth arc in O(n) time. 512 510 /// \pre n is in the [0..length() - 1] range 513 511 const Arc& nth(int n) const { … … 539 537 } 540 538 541 /// \brief Return s whetherthe path is empty.539 /// \brief Return true if the path is empty. 542 540 bool empty() const { return first == 0; } 543 541 544 /// \brief Reset s the path to an empty path.542 /// \brief Reset the path to an empty one. 545 543 void clear() { 546 544 while (first != 0) { … … 552 550 } 553 551 554 /// \brief Gives back the first arc of the path552 /// \brief The first arc of the path 555 553 const Arc& front() const { 556 554 return first->arc; … … 585 583 } 586 584 587 /// \brief Gives back the last arc of the path.585 /// \brief The last arc of the path. 588 586 const Arc& back() const { 589 587 return last->arc; … … 618 616 } 619 617 620 /// \brief Splic ing the given path tothe current path.621 /// 622 /// It splices the\c tpath to the back of the current path and \c618 /// \brief Splice a path to the back of the current path. 619 /// 620 /// It splices \c tpath to the back of the current path and \c 623 621 /// tpath becomes empty. The time complexity of this function is 624 622 /// O(1). … … 637 635 } 638 636 639 /// \brief Splic ing the given path tothe current path.640 /// 641 /// It splices the\c tpath before the current path and \c tpath637 /// \brief Splice a path to the front of the current path. 638 /// 639 /// It splices \c tpath before the current path and \c tpath 642 640 /// becomes empty. The time complexity of this function 643 641 /// is O(1). … … 656 654 } 657 655 658 /// \brief Splic ing the givenpath into the current path.656 /// \brief Splice a path into the current path. 659 657 /// 660 658 /// It splices the \c tpath into the current path before the 661 659 /// position of \c it iterator and \c tpath becomes empty. The 662 /// time complexity of this function is O(1). If the \c it is \c663 /// INVALID then it will splice behind the current path.660 /// time complexity of this function is O(1). If the \c it is 661 /// \c INVALID then it will splice behind the current path. 664 662 void splice(ArcIt it, ListPath& tpath) { 665 663 if (it.node) { … … 689 687 } 690 688 691 /// \brief Split ingthe current path.692 /// 693 /// It splits the current path into two parts. The part before \c694 /// it iterator will remain in the current path and the part from695 /// the it will put into the \c tpath. If the \c tpath had arcs696 /// before the operation they will be removed first. The time697 /// complexity of this function is O(1) plus the clearing of \c698 /// tpath. If the \c it is \c INVALID then it just clears \c699 /// tpath.689 /// \brief Split the current path. 690 /// 691 /// It splits the current path into two parts. The part before 692 /// the iterator \c it will remain in the current path and the part 693 /// starting with 694 /// \c it will put into \c tpath. If \c tpath have arcs 695 /// before the operation they are removed first. The time 696 /// complexity of this function is O(1) plus the the time of emtying 697 /// \c tpath. If \c it is \c INVALID then it just clears \c tpath 700 698 void split(ArcIt it, ListPath& tpath) { 701 699 tpath.clear(); … … 739 737 /// In a sense, the path can be treated as a list of arcs. The 740 738 /// lemon path type stores just this list. As a consequence it 741 /// cannot enumerate the nodes in the path and the zero length paths 742 /// cannot store the source. 743 /// 744 /// This implementation is completly static, so it cannot be 745 /// modified exclude the assign an other path. It is intented to be 746 /// used when you want to store a large number of paths because it is 747 /// the most memory efficient path type in the lemon. 739 /// cannot enumerate the nodes in the path and the source node of 740 /// a zero length path is undefined. 741 /// 742 /// This implementation is completly static, i.e. it can be copy constucted 743 /// or copy assigned from another path, but otherwise it cannot be 744 /// modified. 745 /// 746 /// Being the the most memory efficient path type in LEMON, 747 /// it is intented to be 748 /// used when you want to store a large number of paths. 748 749 template <typename _Digraph> 749 750 class StaticPath { … … 760 761 /// \brief Template copy constructor 761 762 /// 762 /// This path can be initialized with any other path type. It just 763 /// makes a copy of the given path. 763 /// This path can be initialized from any other path type. 764 764 template <typename CPath> 765 765 StaticPath(const CPath& cpath) : arcs(0) { … … 776 776 /// \brief Template copy assignment 777 777 /// 778 /// This path can be initialized with any other path type. It just778 /// This path can be made equal to any other path type. It simply 779 779 /// makes a copy of the given path. 780 780 template <typename CPath> … … 832 832 }; 833 833 834 /// \brief Gives back the nth arc.834 /// \brief The nth arc. 835 835 /// 836 836 /// \pre n is in the [0..length() - 1] range … … 839 839 } 840 840 841 /// \brief Initializes arc iterator to pointto the nth arc.841 /// \brief The arc iterator pointing to the nth arc. 842 842 ArcIt nthIt(int n) const { 843 843 return ArcIt(*this, n); 844 844 } 845 845 846 /// \brief Gives back the length of the path.846 /// \brief The length of the path. 847 847 int length() const { return len; } 848 848 849 /// \brief Return strue when the path is empty.849 /// \brief Return true when the path is empty. 850 850 int empty() const { return len == 0; } 851 851 852 /// \break Erase all arc in the digraph.852 /// \break Erase all arcs in the digraph. 853 853 void clear() { 854 854 len = 0; … … 857 857 } 858 858 859 /// \brief Gives back the first arc of the path.859 /// \brief The first arc of the path. 860 860 const Arc& front() const { 861 861 return arcs[0]; 862 862 } 863 863 864 /// \brief Gives back the last arc of the path.864 /// \brief The last arc of the path. 865 865 const Arc& back() const { 866 866 return arcs[len - 1];
Note: See TracChangeset
for help on using the changeset viewer.