Changeset 986:e997802b855c in lemon0.x for src/work/peter/path/path.h
 Timestamp:
 11/13/04 13:53:28 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1376
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/peter/path/path.h
r959 r986 109 109 /// Returns INVALID if the path is empty. 110 110 GraphNode from() const { 111 return empty() ? INVALID : gr> tail(edges[0]);111 return empty() ? INVALID : gr>source(edges[0]); 112 112 } 113 113 /// \brief End point of the path. … … 116 116 /// Returns INVALID if the path is empty. 117 117 GraphNode to() const { 118 return empty() ? INVALID : gr> head(edges[length()1]);118 return empty() ? INVALID : gr>target(edges[length()1]); 119 119 } 120 120 … … 154 154 } 155 155 156 /// \brief Returns node iterator pointing to the headnode of the156 /// \brief Returns node iterator pointing to the target node of the 157 157 /// given edge iterator. 158 NodeIt head(const EdgeIt& e) const {158 NodeIt target(const EdgeIt& e) const { 159 159 if( DM::range_check && !e.valid() ) 160 fault("DirPath:: head() on invalid iterator");160 fault("DirPath::target() on invalid iterator"); 161 161 return NodeIt(*this, e.idx+1); 162 162 } 163 163 164 /// \brief Returns node iterator pointing to the tailnode of the164 /// \brief Returns node iterator pointing to the source node of the 165 165 /// given edge iterator. 166 NodeIt tail(const EdgeIt& e) const {166 NodeIt source(const EdgeIt& e) const { 167 167 if( DM::range_check && !e.valid() ) 168 fault("DirPath:: tail() on invalid iterator");168 fault("DirPath::source() on invalid iterator"); 169 169 return NodeIt(*this, e.idx); 170 170 } … … 255 255 return p>to(); 256 256 else if(idx >= 0) 257 return p>gr> tail(p>edges[idx]);257 return p>gr>source(p>edges[idx]); 258 258 else 259 259 return INVALID; … … 313 313 ///\sa setStartNode 314 314 void pushFront(const GraphEdge& e) { 315 if( DM::consistensy_check && !empty() && P.gr> head(e)!=from() ) {315 if( DM::consistensy_check && !empty() && P.gr>target(e)!=from() ) { 316 316 fault("DirPath::Builder::pushFront: nonincident edge"); 317 317 } … … 324 324 ///\sa setStartNode 325 325 void pushBack(const GraphEdge& e) { 326 if( DM::consistensy_check && !empty() && P.gr> tail(e)!=to() ) {326 if( DM::consistensy_check && !empty() && P.gr>source(e)!=to() ) { 327 327 fault("DirPath::Builder::pushBack: nonincident edge"); 328 328 } … … 363 363 GraphNode from() const { 364 364 if( ! front.empty() ) 365 return P.gr> tail(front[front.size()1]);365 return P.gr>source(front[front.size()1]); 366 366 else if( ! P.empty() ) 367 return P.gr> tail(P.edges[0]);367 return P.gr>source(P.edges[0]); 368 368 else if( ! back.empty() ) 369 return P.gr> tail(back[0]);369 return P.gr>source(back[0]); 370 370 else 371 371 return INVALID; … … 373 373 GraphNode to() const { 374 374 if( ! back.empty() ) 375 return P.gr> head(back[back.size()1]);375 return P.gr>target(back[back.size()1]); 376 376 else if( ! P.empty() ) 377 return P.gr> head(P.edges[P.length()1]);377 return P.gr>target(P.edges[P.length()1]); 378 378 else if( ! front.empty() ) 379 return P.gr> head(front[0]);379 return P.gr>target(front[0]); 380 380 else 381 381 return INVALID; … … 472 472 /// Returns INVALID if the path is empty. 473 473 GraphNode from() const { 474 return empty() ? INVALID : gr> tail(edges[0]);474 return empty() ? INVALID : gr>source(edges[0]); 475 475 } 476 476 /// \brief End point of the path. … … 479 479 /// Returns INVALID if the path is empty. 480 480 GraphNode to() const { 481 return empty() ? INVALID : gr> head(edges[length()1]);481 return empty() ? INVALID : gr>target(edges[length()1]); 482 482 } 483 483 … … 517 517 } 518 518 519 /// \brief Returns node iterator pointing to the headnode of the519 /// \brief Returns node iterator pointing to the target node of the 520 520 /// given edge iterator. 521 NodeIt head(const EdgeIt& e) const {521 NodeIt target(const EdgeIt& e) const { 522 522 if( DM::range_check && !e.valid() ) 523 fault("UndirPath:: head() on invalid iterator");523 fault("UndirPath::target() on invalid iterator"); 524 524 return NodeIt(*this, e.idx+1); 525 525 } 526 526 527 /// \brief Returns node iterator pointing to the tailnode of the527 /// \brief Returns node iterator pointing to the source node of the 528 528 /// given edge iterator. 529 NodeIt tail(const EdgeIt& e) const {529 NodeIt source(const EdgeIt& e) const { 530 530 if( DM::range_check && !e.valid() ) 531 fault("UndirPath:: tail() on invalid iterator");531 fault("UndirPath::source() on invalid iterator"); 532 532 return NodeIt(*this, e.idx); 533 533 } … … 616 616 return p>to(); 617 617 else if(idx >= 0) 618 return p>gr> tail(p>edges[idx]);618 return p>gr>source(p>edges[idx]); 619 619 else 620 620 return INVALID; … … 674 674 ///\sa setStartNode 675 675 void pushFront(const GraphEdge& e) { 676 if( DM::consistensy_check && !empty() && P.gr> head(e)!=from() ) {676 if( DM::consistensy_check && !empty() && P.gr>target(e)!=from() ) { 677 677 fault("UndirPath::Builder::pushFront: nonincident edge"); 678 678 } … … 685 685 ///\sa setStartNode 686 686 void pushBack(const GraphEdge& e) { 687 if( DM::consistensy_check && !empty() && P.gr> tail(e)!=to() ) {687 if( DM::consistensy_check && !empty() && P.gr>source(e)!=to() ) { 688 688 fault("UndirPath::Builder::pushBack: nonincident edge"); 689 689 } … … 724 724 GraphNode from() const { 725 725 if( ! front.empty() ) 726 return P.gr> tail(front[front.size()1]);726 return P.gr>source(front[front.size()1]); 727 727 else if( ! P.empty() ) 728 return P.gr> tail(P.edges[0]);728 return P.gr>source(P.edges[0]); 729 729 else if( ! back.empty() ) 730 return P.gr> tail(back[0]);730 return P.gr>source(back[0]); 731 731 else 732 732 return INVALID; … … 734 734 GraphNode to() const { 735 735 if( ! back.empty() ) 736 return P.gr> head(back[back.size()1]);736 return P.gr>target(back[back.size()1]); 737 737 else if( ! P.empty() ) 738 return P.gr> head(P.edges[P.length()1]);738 return P.gr>target(P.edges[P.length()1]); 739 739 else if( ! front.empty() ) 740 return P.gr> head(front[0]);740 return P.gr>target(front[0]); 741 741 else 742 742 return INVALID; … … 841 841 bool setTo(const GraphNode &n); 842 842 843 // WARNING: these two functions return the head/tailof an edge with843 // WARNING: these two functions return the target/source of an edge with 844 844 // respect to the direction of the path! 845 // So G. head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if845 // So G.target(P.graphEdge(e)) == P.graphNode(P.target(e)) holds only if 846 846 // P.forward(e) is true (or the edge is a loop)! 847 NodeIt head(const EdgeIt& e) const;848 NodeIt tail(const EdgeIt& e) const;847 NodeIt target(const EdgeIt& e) const; 848 NodeIt source(const EdgeIt& e) const; 849 849 850 850 // FIXME: ezeknek valami jobb nev kellene!!! … … 874 874 875 875 size_t idx; 876 bool tail; // Is this node the tailof the edge with same idx?876 bool source; // Is this node the source of the edge with same idx? 877 877 878 878 public: … … 897 897 return e; 898 898 899 GraphNode common_node = ( e.forw ? G. head(*e.it) : G.tail(*e.it) );899 GraphNode common_node = ( e.forw ? G.target(*e.it) : G.source(*e.it) ); 900 900 ++e.it; 901 901 … … 906 906 } 907 907 908 e.forw = ( G. tail(*e.it) == common_node );908 e.forw = ( G.source(*e.it) == common_node ); 909 909 return e; 910 910 } … … 919 919 920 920 921 GraphNode next_node = ( n. tail ? G.head(edges[n.idx]) :922 G. tail(edges[n.idx]) );921 GraphNode next_node = ( n.source ? G.target(edges[n.idx]) : 922 G.source(edges[n.idx]) ); 923 923 ++n.idx; 924 924 if( n.idx < length() ) { 925 n. tail = ( next_node == G.tail(edges[n.idx]) );925 n.source = ( next_node == G.source(edges[n.idx]) ); 926 926 } 927 927 else { 928 n. tail= true;928 n.source = true; 929 929 } 930 930 … … 935 935 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a, 936 936 GraphNode &b) { 937 if( G. tail(e) == a ) {938 b=G. head(e);937 if( G.source(e) == a ) { 938 b=G.target(e); 939 939 return true; 940 940 } 941 if( G. head(e) == a ) {942 b=G. tail(e);941 if( G.target(e) == a ) { 942 b=G.source(e); 943 943 return true; 944 944 } … … 949 949 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e, 950 950 const GraphEdge &f) { 951 if( edgeIncident(f, G. tail(e), _last) ) {952 _first = G. head(e);951 if( edgeIncident(f, G.source(e), _last) ) { 952 _first = G.target(e); 953 953 return true; 954 954 } 955 if( edgeIncident(f, G. head(e), _last) ) {956 _first = G. tail(e);955 if( edgeIncident(f, G.target(e), _last) ) { 956 _first = G.source(e); 957 957 return true; 958 958 } … … 1040 1040 template<typename Gr> 1041 1041 typename DynamicPath<Gr>::NodeIt 1042 DynamicPath<Gr>:: tail(const EdgeIt& e) const {1042 DynamicPath<Gr>::source(const EdgeIt& e) const { 1043 1043 NodeIt n; 1044 1044 … … 1046 1046 // FIXME: invalid> invalid 1047 1047 n.idx = length() + 1; 1048 n. tail= true;1048 n.source = true; 1049 1049 return n; 1050 1050 } 1051 1051 1052 1052 n.idx = e.itedges.begin(); 1053 n. tail= e.forw;1053 n.source = e.forw; 1054 1054 return n; 1055 1055 } … … 1057 1057 template<typename Gr> 1058 1058 typename DynamicPath<Gr>::NodeIt 1059 DynamicPath<Gr>:: head(const EdgeIt& e) const {1059 DynamicPath<Gr>::target(const EdgeIt& e) const { 1060 1060 if( e.it == edges.end()1 ) { 1061 1061 return _last; … … 1064 1064 EdgeIt next_edge = e; 1065 1065 next(next_edge); 1066 return tail(next_edge);1066 return source(next_edge); 1067 1067 } 1068 1068 … … 1082 1082 DynamicPath<Gr>::graphNode(const NodeIt& n) const { 1083 1083 if( n.idx < length() ) { 1084 return n. tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);1084 return n.source ? G.source(edges[n.idx]) : G.target(edges[n.idx]); 1085 1085 } 1086 1086 else if( n.idx == length() ) { … … 1104 1104 e.it = edges.begin()+k; 1105 1105 if(k==0) { 1106 e.forw = ( G. tail(*e.it) == _first );1106 e.forw = ( G.source(*e.it) == _first ); 1107 1107 } 1108 1108 else { 1109 e.forw = ( G. tail(*e.it) == G.tail(edges[k1]) 1110 G. tail(*e.it) == G.head(edges[k1]) );1109 e.forw = ( G.source(*e.it) == G.source(edges[k1])  1110 G.source(*e.it) == G.target(edges[k1]) ); 1111 1111 } 1112 1112 return e; … … 1119 1119 // FIXME: invalid NodeIt 1120 1120 n.idx = length()+1; 1121 n. tail= true;1121 n.source = true; 1122 1122 return n; 1123 1123 } 1124 1124 if( k==length() ) { 1125 1125 n.idx = length(); 1126 n. tail= true;1126 n.source = true; 1127 1127 return n; 1128 1128 } 1129 n = tail(nth<EdgeIt>(k));1129 n = source(nth<EdgeIt>(k)); 1130 1130 return n; 1131 1131 } … … 1140 1140 { 1141 1141 if( G.valid(P._first) && a.it < P.edges.end() ) { 1142 _first = ( a.forw ? G. tail(*a.it) : G.head(*a.it) );1142 _first = ( a.forw ? G.source(*a.it) : G.target(*a.it) ); 1143 1143 if( b.it < P.edges.end() ) { 1144 _last = ( b.forw ? G. tail(*b.it) : G.head(*b.it) );1144 _last = ( b.forw ? G.source(*b.it) : G.target(*b.it) ); 1145 1145 } 1146 1146 else {
Note: See TracChangeset
for help on using the changeset viewer.