Changeset 837:2d50d1f045c5 in lemon0.x
 Timestamp:
 09/13/04 17:30:01 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1136
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/path.h
r835 r837 41 41 //! \param Graph The graph type in which the path is. 42 42 //! \param DM DebugMode, defaults to DefaultDebugMode. 43 //! 43 //! 44 44 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 45 45 //! and \c EdgeIt with the same usage. These types converts to the \c Node … … 51 51 public: 52 52 /// Edge type of the underlying graph. 53 typedef typename Graph::Edge GraphEdge; 53 typedef typename Graph::Edge GraphEdge; 54 54 /// Node type of the underlying graph. 55 55 typedef typename Graph::Node GraphNode; … … 155 155 /** 156 156 * \brief Iterator class to iterate on the edges of the paths 157 * 157 * 158 158 * \ingroup paths 159 159 * This class is used to iterate on the edges of the paths 160 160 * 161 161 * Of course it converts to Graph::Edge 162 * 162 * 163 163 * \todo Its interface differs from the standard edge iterator. 164 164 * Yes, it shouldn't. … … 204 204 /** 205 205 * \brief Iterator class to iterate on the nodes of the paths 206 * 206 * 207 207 * \ingroup paths 208 208 * This class is used to iterate on the nodes of the paths 209 209 * 210 210 * Of course it converts to Graph::Node 211 * 211 * 212 212 * \todo Its interface differs from the standard node iterator. 213 213 * Yes, it shouldn't. … … 253 253 }; 254 254 255 friend class Builder; 255 friend class Builder; 256 256 257 257 /** 258 258 * \brief Class to build paths 259 * 259 * 260 260 * \ingroup paths 261 261 * This class is used to fill a path with edges. … … 281 281 282 282 /// Sets the starting node of the path. 283 283 284 284 /// Sets the starting node of the path. Edge added to the path 285 285 /// afterwards have to be incident to this node. … … 306 306 ///Commit the changes to the path. 307 307 void commit() { 308 if( ! (front.empty() && back.empty()) ) {308 if( !front.empty()  !back.empty() ) { 309 309 Container tmp; 310 310 tmp.reserve(front.size()+back.size()+P.length()); … … 318 318 } 319 319 320 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?321 // Hogy kenyelmes egy ilyet hasznalni?322 323 320 ///Reserve storage for the builder in advance. 324 321 325 ///If you know an reasonable upper bound of the number of the edges 326 ///to add, using this function you can speed up the building. 327 void reserve(size_t r) { 328 front.reserve(r); 329 back.reserve(r); 330 } 331 332 void reserveFront(size_t r) {} 333 void reserveBack(size_t r) {} 322 ///If you know a reasonable upper bound of the number of the edges 323 ///to add to the front, using this function you can speed up the building. 324 325 void reserveFront(size_t r) {front.reserve(r);} 326 327 ///Reserve storage for the builder in advance. 328 329 ///If you know a reasonable upper bound of the number of the edges 330 ///to add to the back, using this function you can speed up the building. 331 332 void reserveBack(size_t r) {back.reserve(r);} 334 333 335 334 private: … … 383 382 //! \param Graph The graph type in which the path is. 384 383 //! \param DM DebugMode, defaults to DefaultDebugMode. 385 //! 384 //! 386 385 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 387 386 //! and \c EdgeIt with the same usage. These types converts to the \c Node … … 496 495 /** 497 496 * \brief Iterator class to iterate on the edges of the paths 498 * 497 * 499 498 * \ingroup paths 500 499 * This class is used to iterate on the edges of the paths 501 500 * 502 501 * Of course it converts to Graph::Edge 503 * 502 * 504 503 * \todo Its interface differs from the standard edge iterator. 505 504 * Yes, it shouldn't. … … 544 543 /** 545 544 * \brief Iterator class to iterate on the nodes of the paths 546 * 545 * 547 546 * \ingroup paths 548 547 * This class is used to iterate on the nodes of the paths 549 548 * 550 549 * Of course it converts to Graph::Node 551 * 550 * 552 551 * \todo Its interface differs from the standard node iterator. 553 552 * Yes, it shouldn't. … … 593 592 }; 594 593 595 friend class Builder; 594 friend class Builder; 596 595 597 596 /** 598 597 * \brief Class to build paths 599 * 598 * 600 599 * \ingroup paths 601 600 * This class is used to fill a path with edges. … … 621 620 622 621 /// Sets the starting node of the path. 623 622 624 623 /// Sets the starting node of the path. Edge added to the path 625 624 /// afterwards have to be incident to this node. … … 658 657 } 659 658 660 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?661 // Hogy kenyelmes egy ilyet hasznalni?662 659 663 660 ///Reserve storage for the builder in advance. 664 661 665 ///If you know an reasonable upper bound of the number of the edges 666 ///to add, using this function you can speed up the building. 667 void reserve(size_t r) { 668 front.reserve(r); 669 back.reserve(r); 670 } 671 672 void reserveFront(size_t r) {} 673 void reserveBack(size_t r) {} 662 ///If you know a reasonable upper bound of the number of the edges 663 ///to add to the front, using this function you can speed up the building. 664 665 void reserveFront(size_t r) {front.reserve(r);} 666 667 ///Reserve storage for the builder in advance. 668 669 ///If you know a reasonable upper bound of the number of the edges 670 ///to add to the back, using this function you can speed up the building. 671 672 void reserveBack(size_t r) {back.reserve(r);} 674 673 675 674 private: … … 704 703 705 704 706 707 708 709 710 711 712 713 714 /**********************************************************************/715 716 717 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata718 elott. Eleg bonyinak nez ki, ahogyan azokat az STLben hasznaljak. */719 720 template<typename Graph>721 class DynamicPath {722 723 public:724 typedef typename Graph::Edge GraphEdge;725 typedef typename Graph::Node GraphNode;726 class NodeIt;727 class EdgeIt;728 729 protected:730 Graph& G;731 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el732 // iranyitasat:733 GraphNode _first, _last;734 typedef std::deque<GraphEdge> Container;735 Container edges;736 737 public:738 739 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}740 741 /// Subpath defined by two nodes.742 /// Nodes may be in reversed order, then743 /// we contstruct the reversed path.744 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);745 /// Subpath defined by two edges. Contains edges in [a,b)746 /// It is an error if the two edges are not in order!747 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);748 749 size_t length() const { return edges.size(); }750 GraphNode tail() const { return _first; }751 GraphNode head() const { return _last; }752 753 NodeIt& first(NodeIt &n) const { return nth(n, 0); }754 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }755 template<typename It>756 It first() const {757 It e;758 first(e);759 return e;760 }761 762 NodeIt& nth(NodeIt &, size_t) const;763 EdgeIt& nth(EdgeIt &, size_t) const;764 template<typename It>765 It nth(size_t n) const {766 It e;767 nth(e, n);768 return e;769 }770 771 bool valid(const NodeIt &n) const { return n.idx <= length(); }772 bool valid(const EdgeIt &e) const { return e.it < edges.end(); }773 774 bool isForward(const EdgeIt &e) const { return e.forw; }775 776 /// index of a node on the path. Returns length+2 for the invalid NodeIt777 int index(const NodeIt &n) const { return n.idx; }778 /// index of an edge on the path. Returns length+1 for the invalid EdgeIt779 int index(const EdgeIt &e) const { return e.it  edges.begin(); }780 781 EdgeIt& next(EdgeIt &e) const;782 NodeIt& next(NodeIt &n) const;783 template <typename It>784 It getNext(It it) const {785 It tmp(it); return next(tmp);786 }787 788 // A path is constructed using the following four functions.789 // They return false if the requested operation is inconsistent790 // with the path constructed so far.791 // If your path has only one edge you MUST set either "from" or "to"!792 // So you probably SHOULD call it in any case to be safe (and check the793 // returned value to check if your path is consistent with your idea).794 bool pushFront(const GraphEdge &e);795 bool pushBack(const GraphEdge &e);796 bool setFrom(const GraphNode &n);797 bool setTo(const GraphNode &n);798 799 // WARNING: these two functions return the head/tail of an edge with800 // respect to the direction of the path!801 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if802 // P.forward(e) is true (or the edge is a loop)!803 NodeIt head(const EdgeIt& e) const;804 NodeIt tail(const EdgeIt& e) const;805 806 // FIXME: ezeknek valami jobb nev kellene!!!807 GraphEdge graphEdge(const EdgeIt& e) const;808 GraphNode graphNode(const NodeIt& n) const;809 810 811 /*** Iterator classes ***/812 class EdgeIt {813 friend class DynamicPath;814 815 typename Container::const_iterator it;816 bool forw;817 public:818 // FIXME: jarna neki ilyen is...819 // EdgeIt(Invalid);820 821 bool forward() const { return forw; }822 823 bool operator==(const EdgeIt& e) const { return it==e.it; }824 bool operator!=(const EdgeIt& e) const { return it!=e.it; }825 bool operator<(const EdgeIt& e) const { return it<e.it; }826 };827 828 class NodeIt {829 friend class DynamicPath;830 831 size_t idx;832 bool tail; // Is this node the tail of the edge with same idx?833 834 public:835 // FIXME: jarna neki ilyen is...836 // NodeIt(Invalid);837 838 bool operator==(const NodeIt& n) const { return idx==n.idx; }839 bool operator!=(const NodeIt& n) const { return idx!=n.idx; }840 bool operator<(const NodeIt& n) const { return idx<n.idx; }841 };842 843 private:844 bool edgeIncident(const GraphEdge &e, const GraphNode &a,845 GraphNode &b);846 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);847 };848 849 template<typename Gr>850 typename DynamicPath<Gr>::EdgeIt&851 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {852 if( e.it == edges.end() )853 return e;854 855 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );856 ++e.it;857 858 // Invalid edgeit is always forward :)859 if( e.it == edges.end() ) {860 e.forw = true;861 return e;862 }863 864 e.forw = ( G.tail(*e.it) == common_node );865 return e;866 }867 868 template<typename Gr>869 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {870 if( n.idx >= length() ) {871 // FIXME: invalid872 n.idx = length()+1;873 return n;874 }875 876 877 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :878 G.tail(edges[n.idx]) );879 ++n.idx;880 if( n.idx < length() ) {881 n.tail = ( next_node == G.tail(edges[n.idx]) );882 }883 else {884 n.tail = true;885 }886 887 return n;888 }889 890 template<typename Gr>891 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,892 GraphNode &b) {893 if( G.tail(e) == a ) {894 b=G.head(e);895 return true;896 }897 if( G.head(e) == a ) {898 b=G.tail(e);899 return true;900 }901 return false;902 }903 904 template<typename Gr>905 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,906 const GraphEdge &f) {907 if( edgeIncident(f, G.tail(e), _last) ) {908 _first = G.head(e);909 return true;910 }911 if( edgeIncident(f, G.head(e), _last) ) {912 _first = G.tail(e);913 return true;914 }915 return false;916 }917 918 template<typename Gr>919 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {920 if( G.valid(_first) ) {921 if( edgeIncident(e, _first, _first) ) {922 edges.push_front(e);923 return true;924 }925 else926 return false;927 }928 else if( length() < 1  connectTwoEdges(e, edges[0]) ) {929 edges.push_front(e);930 return true;931 }932 else933 return false;934 }935 936 template<typename Gr>937 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {938 if( G.valid(_last) ) {939 if( edgeIncident(e, _last, _last) ) {940 edges.push_back(e);941 return true;942 }943 else944 return false;945 }946 else if( length() < 1  connectTwoEdges(edges[0], e) ) {947 edges.push_back(e);948 return true;949 }950 else951 return false;952 }953 954 955 template<typename Gr>956 bool DynamicPath<Gr>::setFrom(const GraphNode &n) {957 if( G.valid(_first) ) {958 return _first == n;959 }960 else {961 if( length() > 0) {962 if( edgeIncident(edges[0], n, _last) ) {963 _first = n;964 return true;965 }966 else return false;967 }968 else {969 _first = _last = n;970 return true;971 }972 }973 }974 975 template<typename Gr>976 bool DynamicPath<Gr>::setTo(const GraphNode &n) {977 if( G.valid(_last) ) {978 return _last == n;979 }980 else {981 if( length() > 0) {982 if( edgeIncident(edges[0], n, _first) ) {983 _last = n;984 return true;985 }986 else return false;987 }988 else {989 _first = _last = n;990 return true;991 }992 }993 }994 995 996 template<typename Gr>997 typename DynamicPath<Gr>::NodeIt998 DynamicPath<Gr>::tail(const EdgeIt& e) const {999 NodeIt n;1000 1001 if( e.it == edges.end() ) {1002 // FIXME: invalid> invalid1003 n.idx = length() + 1;1004 n.tail = true;1005 return n;1006 }1007 1008 n.idx = e.itedges.begin();1009 n.tail = e.forw;1010 return n;1011 }1012 1013 template<typename Gr>1014 typename DynamicPath<Gr>::NodeIt1015 DynamicPath<Gr>::head(const EdgeIt& e) const {1016 if( e.it == edges.end()1 ) {1017 return _last;1018 }1019 1020 EdgeIt next_edge = e;1021 next(next_edge);1022 return tail(next_edge);1023 }1024 1025 template<typename Gr>1026 typename DynamicPath<Gr>::GraphEdge1027 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {1028 if( e.it != edges.end() ) {1029 return *e.it;1030 }1031 else {1032 return INVALID;1033 }1034 }1035 1036 template<typename Gr>1037 typename DynamicPath<Gr>::GraphNode1038 DynamicPath<Gr>::graphNode(const NodeIt& n) const {1039 if( n.idx < length() ) {1040 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);1041 }1042 else if( n.idx == length() ) {1043 return _last;1044 }1045 else {1046 return INVALID;1047 }1048 }1049 1050 template<typename Gr>1051 typename DynamicPath<Gr>::EdgeIt&1052 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {1053 if( k>=length() ) {1054 // FIXME: invalid EdgeIt1055 e.it = edges.end();1056 e.forw = true;1057 return e;1058 }1059 1060 e.it = edges.begin()+k;1061 if(k==0) {1062 e.forw = ( G.tail(*e.it) == _first );1063 }1064 else {1065 e.forw = ( G.tail(*e.it) == G.tail(edges[k1]) 1066 G.tail(*e.it) == G.head(edges[k1]) );1067 }1068 return e;1069 }1070 1071 template<typename Gr>1072 typename DynamicPath<Gr>::NodeIt&1073 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {1074 if( k>length() ) {1075 // FIXME: invalid NodeIt1076 n.idx = length()+1;1077 n.tail = true;1078 return n;1079 }1080 if( k==length() ) {1081 n.idx = length();1082 n.tail = true;1083 return n;1084 }1085 n = tail(nth<EdgeIt>(k));1086 return n;1087 }1088 1089 // Reszut konstruktorok:1090 1091 1092 template<typename Gr>1093 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,1094 const EdgeIt &b) :1095 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!1096 {1097 if( G.valid(P._first) && a.it < P.edges.end() ) {1098 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );1099 if( b.it < P.edges.end() ) {1100 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );1101 }1102 else {1103 _last = P._last;1104 }1105 }1106 }1107 1108 template<typename Gr>1109 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,1110 const NodeIt &b) : G(P.G)1111 {1112 if( !P.valid(a)  !P.valid(b) )1113 return;1114 1115 int ai = a.idx, bi = b.idx;1116 if( bi<ai )1117 std::swap(ai,bi);1118 1119 edges.resize(biai);1120 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());1121 1122 _first = P.graphNode(a);1123 _last = P.graphNode(b);1124 }1125 1126 705 ///@} 1127 706
Note: See TracChangeset
for help on using the changeset viewer.