Changeset 684:11d480a922b1 in lemon0.x
 Timestamp:
 06/15/04 08:29:27 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@932
 File:

 1 copied
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/path.h
r683 r684 1 1 // * c++ * // 2 2 3 ///\ingroup datas 3 /** 4 @defgroup paths Path Structures 5 @ingroup datas 6 \brief Path structures implemented in Hugo. 7 8 Hugolib provides flexible data structures 9 to work with paths. 10 11 All of them have the same interface, especially they can be built or extended 12 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra 13 algorithm to store its result in any kind of path structure. 14 15 */ 16 17 ///\ingroup paths 4 18 ///\file 5 19 ///\brief Classes for representing paths in graphs. … … 18 32 namespace hugo { 19 33 20 /// \addtogroup datas34 /// \addtogroup paths 21 35 /// @{ 22 36 … … 36 50 class DirPath { 37 51 public: 38 typedef typename Graph::Edge GraphEdge; 52 /// Edge type of the underlying graph. 53 typedef typename Graph::Edge GraphEdge; 54 /// Node type of the underlying graph. 39 55 typedef typename Graph::Node GraphNode; 40 56 class NodeIt; … … 153 169 154 170 155 /*** Iterator classes ***/ 171 /* Iterator classes */ 172 173 /** 174 * \brief Iterator class to iterate on the edges of the paths 175 * 176 * \ingroup paths 177 * This class is used to iterate on the edges of the paths 178 * 179 * Of course it converts to Graph::Edge 180 * 181 * \todo Its interface differs from the standard edge iterator. 182 * Yes, it shouldn't. 183 */ 156 184 class EdgeIt { 157 185 friend class DirPath; … … 160 188 const DirPath *p; 161 189 public: 190 /// Default constructor 162 191 EdgeIt() {} 192 /// Invalid constructor 163 193 EdgeIt(Invalid) : idx(1), p(0) {} 194 /// Constructor with starting point 164 195 EdgeIt(const DirPath &_p, int _idx = 0) : 165 196 idx(_idx), p(&_p) { validate(); } 166 197 198 ///Validity check 167 199 bool valid() const { return idx!=1; } 168 200 201 ///Conversion to Graph::Edge 169 202 operator GraphEdge () const { 170 203 return valid() ? p>edges[idx] : INVALID; 171 204 } 205 206 /// Next edge 172 207 EdgeIt& operator++() { ++idx; validate(); return *this; } 173 208 209 /// Comparison operator 174 210 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 211 /// Comparison operator 175 212 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 213 /// Comparison operator 176 214 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 177 215 … … 182 220 }; 183 221 222 /** 223 * \brief Iterator class to iterate on the nodes of the paths 224 * 225 * \ingroup paths 226 * This class is used to iterate on the nodes of the paths 227 * 228 * Of course it converts to Graph::Node 229 * 230 * \todo Its interface differs from the standard node iterator. 231 * Yes, it shouldn't. 232 */ 184 233 class NodeIt { 185 234 friend class DirPath; … … 188 237 const DirPath *p; 189 238 public: 239 /// Default constructor 190 240 NodeIt() {} 241 /// Invalid constructor 191 242 NodeIt(Invalid) : idx(1), p(0) {} 243 /// Constructor with starting point 192 244 NodeIt(const DirPath &_p, int _idx = 0) : 193 245 idx(_idx), p(&_p) { validate(); } 194 246 247 ///Validity check 195 248 bool valid() const { return idx!=1; } 196 249 250 ///Conversion to Graph::Node 197 251 operator const GraphNode& () const { 198 252 if(idx >= p>length()) … … 203 257 return INVALID; 204 258 } 259 /// Next node 205 260 NodeIt& operator++() { ++idx; validate(); return *this; } 206 261 262 /// Comparison operator 207 263 bool operator==(const NodeIt& e) const { return idx==e.idx; } 264 /// Comparison operator 208 265 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 266 /// Comparison operator 209 267 bool operator<(const NodeIt& e) const { return idx<e.idx; } 210 268 … … 218 276 * \brief Class to build paths 219 277 * 220 * \ingroup datas278 * \ingroup paths 221 279 * This class is used to fill a path with edges. 222 280 * … … 286 344 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 287 345 // Hogy kenyelmes egy ilyet hasznalni? 346 347 ///Reserve storage in advance for the builder 348 349 ///If you know an reasonable upper bound of the number of the edges 350 ///to add, using this function you can speed up the building. 288 351 void reserve(size_t r) { 289 352 front.reserve(r); … … 320 383 321 384 }; 322 323 324 325 326 385 327 386 … … 350 409 class UndirPath { 351 410 public: 411 /// Edge type of the underlying graph. 352 412 typedef typename Graph::Edge GraphEdge; 353 typedef typename Graph::Node GraphNode; 413 /// Node type of the underlying graph. 414 typedef typename Graph::Node GraphNode; 354 415 class NodeIt; 355 416 class EdgeIt; … … 467 528 468 529 469 /*** Iterator classes ***/ 530 531 /** 532 * \brief Iterator class to iterate on the edges of the paths 533 * 534 * \ingroup paths 535 * This class is used to iterate on the edges of the paths 536 * 537 * Of course it converts to Graph::Edge 538 * 539 * \todo Its interface differs from the standard edge iterator. 540 * Yes, it shouldn't. 541 */ 470 542 class EdgeIt { 471 543 friend class UndirPath; … … 474 546 const UndirPath *p; 475 547 public: 548 /// Default constructor 476 549 EdgeIt() {} 550 /// Invalid constructor 477 551 EdgeIt(Invalid) : idx(1), p(0) {} 552 /// Constructor with starting point 478 553 EdgeIt(const UndirPath &_p, int _idx = 0) : 479 554 idx(_idx), p(&_p) { validate(); } 480 555 556 ///Validity check 481 557 bool valid() const { return idx!=1; } 482 558 559 ///Conversion to Graph::Edge 483 560 operator GraphEdge () const { 484 561 return valid() ? p>edges[idx] : INVALID; 485 562 } 486 EdgeIt& operator++() { ++idx; validate(); return *this; } 487 563 /// Next edge 564 EdgeIt& operator++() { ++idx; validate(); return *this; } 565 566 /// Comparison operator 488 567 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 568 /// Comparison operator 489 569 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 570 /// Comparison operator 490 571 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 491 572 … … 496 577 }; 497 578 579 /** 580 * \brief Iterator class to iterate on the nodes of the paths 581 * 582 * \ingroup paths 583 * This class is used to iterate on the nodes of the paths 584 * 585 * Of course it converts to Graph::Node 586 * 587 * \todo Its interface differs from the standard node iterator. 588 * Yes, it shouldn't. 589 */ 498 590 class NodeIt { 499 591 friend class UndirPath; … … 502 594 const UndirPath *p; 503 595 public: 596 /// Default constructor 504 597 NodeIt() {} 598 /// Invalid constructor 505 599 NodeIt(Invalid) : idx(1), p(0) {} 600 /// Constructor with starting point 506 601 NodeIt(const UndirPath &_p, int _idx = 0) : 507 602 idx(_idx), p(&_p) { validate(); } 508 603 604 ///Validity check 509 605 bool valid() const { return idx!=1; } 510 606 607 ///Conversion to Graph::Node 511 608 operator const GraphNode& () const { 512 609 if(idx >= p>length()) … … 517 614 return INVALID; 518 615 } 616 /// Next node 519 617 NodeIt& operator++() { ++idx; validate(); return *this; } 520 618 619 /// Comparison operator 521 620 bool operator==(const NodeIt& e) const { return idx==e.idx; } 621 /// Comparison operator 522 622 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 523 bool operator<(const NodeIt& e) const { return idx<e.idx; } 623 /// Comparison operator 624 bool operator<(const NodeIt& e) const { return idx<e.idx; } 524 625 525 626 private: … … 532 633 * \brief Class to build paths 533 634 * 534 * \ingroup datas635 * \ingroup paths 535 636 * This class is used to fill a path with edges. 536 637 * … … 600 701 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 601 702 // Hogy kenyelmes egy ilyet hasznalni? 602 void reserve(size_t r) { 703 704 ///Reserve storage in advance for the builder 705 706 ///If you know an reasonable upper bound of the number of the edges 707 ///to add, using this function you can speed up the building. 708 void reserve(size_t r) { 603 709 front.reserve(r); 604 710 back.reserve(r); … … 636 742 637 743 638 639 640 641 642 643 644 645 646 /**********************************************************************/647 648 649 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata650 elott. Eleg bonyinak nez ki, ahogyan azokat az STLben hasznaljak. */651 652 template<typename Graph>653 class DynamicPath {654 655 public:656 typedef typename Graph::Edge GraphEdge;657 typedef typename Graph::Node GraphNode;658 class NodeIt;659 class EdgeIt;660 661 protected:662 Graph& G;663 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el664 // iranyitasat:665 GraphNode _first, _last;666 typedef std::deque<GraphEdge> Container;667 Container edges;668 669 public:670 671 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}672 673 /// Subpath defined by two nodes.674 /// Nodes may be in reversed order, then675 /// we contstruct the reversed path.676 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);677 /// Subpath defined by two edges. Contains edges in [a,b)678 /// It is an error if the two edges are not in order!679 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);680 681 size_t length() const { return edges.size(); }682 GraphNode from() const { return _first; }683 GraphNode to() const { return _last; }684 685 NodeIt& first(NodeIt &n) const { return nth(n, 0); }686 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }687 template<typename It>688 It first() const {689 It e;690 first(e);691 return e;692 }693 694 NodeIt& nth(NodeIt &, size_t) const;695 EdgeIt& nth(EdgeIt &, size_t) const;696 template<typename It>697 It nth(size_t n) const {698 It e;699 nth(e, n);700 return e;701 }702 703 bool valid(const NodeIt &n) const { return n.idx <= length(); }704 bool valid(const EdgeIt &e) const { return e.it < edges.end(); }705 706 bool isForward(const EdgeIt &e) const { return e.forw; }707 708 /// index of a node on the path. Returns length+2 for the invalid NodeIt709 int index(const NodeIt &n) const { return n.idx; }710 /// index of an edge on the path. Returns length+1 for the invalid EdgeIt711 int index(const EdgeIt &e) const { return e.it  edges.begin(); }712 713 EdgeIt& next(EdgeIt &e) const;714 NodeIt& next(NodeIt &n) const;715 template <typename It>716 It getNext(It it) const {717 It tmp(it); return next(tmp);718 }719 720 // A path is constructed using the following four functions.721 // They return false if the requested operation is inconsistent722 // with the path constructed so far.723 // If your path has only one edge you MUST set either "from" or "to"!724 // So you probably SHOULD call it in any case to be safe (and check the725 // returned value to check if your path is consistent with your idea).726 bool pushFront(const GraphEdge &e);727 bool pushBack(const GraphEdge &e);728 bool setFrom(const GraphNode &n);729 bool setTo(const GraphNode &n);730 731 // WARNING: these two functions return the head/tail of an edge with732 // respect to the direction of the path!733 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if734 // P.forward(e) is true (or the edge is a loop)!735 NodeIt head(const EdgeIt& e) const;736 NodeIt tail(const EdgeIt& e) const;737 738 // FIXME: ezeknek valami jobb nev kellene!!!739 GraphEdge graphEdge(const EdgeIt& e) const;740 GraphNode graphNode(const NodeIt& n) const;741 742 743 /*** Iterator classes ***/744 class EdgeIt {745 friend class DynamicPath;746 747 typename Container::const_iterator it;748 bool forw;749 public:750 // FIXME: jarna neki ilyen is...751 // EdgeIt(Invalid);752 753 bool forward() const { return forw; }754 755 bool operator==(const EdgeIt& e) const { return it==e.it; }756 bool operator!=(const EdgeIt& e) const { return it!=e.it; }757 bool operator<(const EdgeIt& e) const { return it<e.it; }758 };759 760 class NodeIt {761 friend class DynamicPath;762 763 size_t idx;764 bool tail; // Is this node the tail of the edge with same idx?765 766 public:767 // FIXME: jarna neki ilyen is...768 // NodeIt(Invalid);769 770 bool operator==(const NodeIt& n) const { return idx==n.idx; }771 bool operator!=(const NodeIt& n) const { return idx!=n.idx; }772 bool operator<(const NodeIt& n) const { return idx<n.idx; }773 };774 775 private:776 bool edgeIncident(const GraphEdge &e, const GraphNode &a,777 GraphNode &b);778 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);779 };780 781 template<typename Gr>782 typename DynamicPath<Gr>::EdgeIt&783 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {784 if( e.it == edges.end() )785 return e;786 787 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );788 ++e.it;789 790 // Invalid edgeit is always forward :)791 if( e.it == edges.end() ) {792 e.forw = true;793 return e;794 }795 796 e.forw = ( G.tail(*e.it) == common_node );797 return e;798 }799 800 template<typename Gr>801 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {802 if( n.idx >= length() ) {803 // FIXME: invalid804 n.idx = length()+1;805 return n;806 }807 808 809 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :810 G.tail(edges[n.idx]) );811 ++n.idx;812 if( n.idx < length() ) {813 n.tail = ( next_node == G.tail(edges[n.idx]) );814 }815 else {816 n.tail = true;817 }818 819 return n;820 }821 822 template<typename Gr>823 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,824 GraphNode &b) {825 if( G.tail(e) == a ) {826 b=G.head(e);827 return true;828 }829 if( G.head(e) == a ) {830 b=G.tail(e);831 return true;832 }833 return false;834 }835 836 template<typename Gr>837 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,838 const GraphEdge &f) {839 if( edgeIncident(f, G.tail(e), _last) ) {840 _first = G.head(e);841 return true;842 }843 if( edgeIncident(f, G.head(e), _last) ) {844 _first = G.tail(e);845 return true;846 }847 return false;848 }849 850 template<typename Gr>851 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {852 if( G.valid(_first) ) {853 if( edgeIncident(e, _first, _first) ) {854 edges.push_front(e);855 return true;856 }857 else858 return false;859 }860 else if( length() < 1  connectTwoEdges(e, edges[0]) ) {861 edges.push_front(e);862 return true;863 }864 else865 return false;866 }867 868 template<typename Gr>869 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {870 if( G.valid(_last) ) {871 if( edgeIncident(e, _last, _last) ) {872 edges.push_back(e);873 return true;874 }875 else876 return false;877 }878 else if( length() < 1  connectTwoEdges(edges[0], e) ) {879 edges.push_back(e);880 return true;881 }882 else883 return false;884 }885 886 887 template<typename Gr>888 bool DynamicPath<Gr>::setFrom(const GraphNode &n) {889 if( G.valid(_first) ) {890 return _first == n;891 }892 else {893 if( length() > 0) {894 if( edgeIncident(edges[0], n, _last) ) {895 _first = n;896 return true;897 }898 else return false;899 }900 else {901 _first = _last = n;902 return true;903 }904 }905 }906 907 template<typename Gr>908 bool DynamicPath<Gr>::setTo(const GraphNode &n) {909 if( G.valid(_last) ) {910 return _last == n;911 }912 else {913 if( length() > 0) {914 if( edgeIncident(edges[0], n, _first) ) {915 _last = n;916 return true;917 }918 else return false;919 }920 else {921 _first = _last = n;922 return true;923 }924 }925 }926 927 928 template<typename Gr>929 typename DynamicPath<Gr>::NodeIt930 DynamicPath<Gr>::tail(const EdgeIt& e) const {931 NodeIt n;932 933 if( e.it == edges.end() ) {934 // FIXME: invalid> invalid935 n.idx = length() + 1;936 n.tail = true;937 return n;938 }939 940 n.idx = e.itedges.begin();941 n.tail = e.forw;942 return n;943 }944 945 template<typename Gr>946 typename DynamicPath<Gr>::NodeIt947 DynamicPath<Gr>::head(const EdgeIt& e) const {948 if( e.it == edges.end()1 ) {949 return _last;950 }951 952 EdgeIt next_edge = e;953 next(next_edge);954 return tail(next_edge);955 }956 957 template<typename Gr>958 typename DynamicPath<Gr>::GraphEdge959 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {960 if( e.it != edges.end() ) {961 return *e.it;962 }963 else {964 return INVALID;965 }966 }967 968 template<typename Gr>969 typename DynamicPath<Gr>::GraphNode970 DynamicPath<Gr>::graphNode(const NodeIt& n) const {971 if( n.idx < length() ) {972 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);973 }974 else if( n.idx == length() ) {975 return _last;976 }977 else {978 return INVALID;979 }980 }981 982 template<typename Gr>983 typename DynamicPath<Gr>::EdgeIt&984 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {985 if( k>=length() ) {986 // FIXME: invalid EdgeIt987 e.it = edges.end();988 e.forw = true;989 return e;990 }991 992 e.it = edges.begin()+k;993 if(k==0) {994 e.forw = ( G.tail(*e.it) == _first );995 }996 else {997 e.forw = ( G.tail(*e.it) == G.tail(edges[k1]) 998 G.tail(*e.it) == G.head(edges[k1]) );999 }1000 return e;1001 }1002 1003 template<typename Gr>1004 typename DynamicPath<Gr>::NodeIt&1005 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {1006 if( k>length() ) {1007 // FIXME: invalid NodeIt1008 n.idx = length()+1;1009 n.tail = true;1010 return n;1011 }1012 if( k==length() ) {1013 n.idx = length();1014 n.tail = true;1015 return n;1016 }1017 n = tail(nth<EdgeIt>(k));1018 return n;1019 }1020 1021 // Reszut konstruktorok:1022 1023 1024 template<typename Gr>1025 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,1026 const EdgeIt &b) :1027 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!1028 {1029 if( G.valid(P._first) && a.it < P.edges.end() ) {1030 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );1031 if( b.it < P.edges.end() ) {1032 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );1033 }1034 else {1035 _last = P._last;1036 }1037 }1038 }1039 1040 template<typename Gr>1041 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,1042 const NodeIt &b) : G(P.G)1043 {1044 if( !P.valid(a)  !P.valid(b) )1045 return;1046 1047 int ai = a.idx, bi = b.idx;1048 if( bi<ai )1049 std::swap(ai,bi);1050 1051 edges.resize(biai);1052 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());1053 1054 _first = P.graphNode(a);1055 _last = P.graphNode(b);1056 }1057 1058 744 ///@} 1059 745
Note: See TracChangeset
for help on using the changeset viewer.