COIN-OR::LEMON - Graph Library

Changeset 837:2d50d1f045c5 in lemon-0.x


Ignore:
Timestamp:
09/13/04 17:30:01 (15 years ago)
Author:
Hegyi Péter
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1136
Message:

Reserve is resolved.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/path.h

    r835 r837  
    4141  //! \param Graph The graph type in which the path is.
    4242  //! \param DM DebugMode, defaults to DefaultDebugMode.
    43   //! 
     43  //!
    4444  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    4545  //! and \c EdgeIt with the same usage. These types converts to the \c Node
     
    5151  public:
    5252    /// Edge type of the underlying graph.
    53     typedef typename Graph::Edge GraphEdge; 
     53    typedef typename Graph::Edge GraphEdge;
    5454    /// Node type of the underlying graph.
    5555    typedef typename Graph::Node GraphNode;
     
    155155    /**
    156156     * \brief Iterator class to iterate on the edges of the paths
    157      * 
     157     *
    158158     * \ingroup paths
    159159     * This class is used to iterate on the edges of the paths
    160160     *
    161161     * Of course it converts to Graph::Edge
    162      * 
     162     *
    163163     * \todo Its interface differs from the standard edge iterator.
    164164     * Yes, it shouldn't.
     
    204204    /**
    205205     * \brief Iterator class to iterate on the nodes of the paths
    206      * 
     206     *
    207207     * \ingroup paths
    208208     * This class is used to iterate on the nodes of the paths
    209209     *
    210210     * Of course it converts to Graph::Node
    211      * 
     211     *
    212212     * \todo Its interface differs from the standard node iterator.
    213213     * Yes, it shouldn't.
     
    253253    };
    254254
    255     friend class Builder;   
     255    friend class Builder;
    256256
    257257    /**
    258258     * \brief Class to build paths
    259      * 
     259     *
    260260     * \ingroup paths
    261261     * This class is used to fill a path with edges.
     
    281281
    282282      /// Sets the starting node of the path.
    283      
     283
    284284      /// Sets the starting node of the path. Edge added to the path
    285285      /// afterwards have to be incident to this node.
     
    306306      ///Commit the changes to the path.
    307307      void commit() {
    308         if( !(front.empty() && back.empty()) ) {
     308        if( !front.empty() || !back.empty() ) {
    309309          Container tmp;
    310310          tmp.reserve(front.size()+back.size()+P.length());
     
    318318      }
    319319
    320       // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
    321       // Hogy kenyelmes egy ilyet hasznalni?
    322  
    323320      ///Reserve storage for the builder in advance.
    324321
    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);}
    334333
    335334    private:
     
    383382  //! \param Graph The graph type in which the path is.
    384383  //! \param DM DebugMode, defaults to DefaultDebugMode.
    385   //! 
     384  //!
    386385  //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    387386  //! and \c EdgeIt with the same usage. These types converts to the \c Node
     
    496495    /**
    497496     * \brief Iterator class to iterate on the edges of the paths
    498      * 
     497     *
    499498     * \ingroup paths
    500499     * This class is used to iterate on the edges of the paths
    501500     *
    502501     * Of course it converts to Graph::Edge
    503      * 
     502     *
    504503     * \todo Its interface differs from the standard edge iterator.
    505504     * Yes, it shouldn't.
     
    544543    /**
    545544     * \brief Iterator class to iterate on the nodes of the paths
    546      * 
     545     *
    547546     * \ingroup paths
    548547     * This class is used to iterate on the nodes of the paths
    549548     *
    550549     * Of course it converts to Graph::Node
    551      * 
     550     *
    552551     * \todo Its interface differs from the standard node iterator.
    553552     * Yes, it shouldn't.
     
    593592    };
    594593
    595     friend class Builder;   
     594    friend class Builder;
    596595
    597596    /**
    598597     * \brief Class to build paths
    599      * 
     598     *
    600599     * \ingroup paths
    601600     * This class is used to fill a path with edges.
     
    621620
    622621      /// Sets the starting node of the path.
    623      
     622
    624623      /// Sets the starting node of the path. Edge added to the path
    625624      /// afterwards have to be incident to this node.
     
    658657      }
    659658
    660       // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
    661       // Hogy kenyelmes egy ilyet hasznalni?
    662659
    663660      ///Reserve storage for the builder in advance.
    664661
    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);}
    674673
    675674    private:
     
    704703
    705704
    706 
    707 
    708 
    709 
    710 
    711 
    712 
    713 
    714   /**********************************************************************/
    715 
    716 
    717   /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
    718      elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben 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 el
    732     // 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, then
    743     /// 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 NodeIt
    777     int index(const NodeIt &n) const { return n.idx; }
    778     /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
    779     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 inconsistent
    790     // 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 the
    793     // 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 with
    800     // respect to the direction of the path!
    801     // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
    802     // 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: invalid
    872       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         else
    926           return false;
    927     }
    928     else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
    929       edges.push_front(e);
    930       return true;
    931     }
    932     else
    933       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         else
    944           return false;
    945     }
    946     else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
    947       edges.push_back(e);
    948       return true;
    949     }
    950     else
    951       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>::NodeIt
    998   DynamicPath<Gr>::tail(const EdgeIt& e) const {
    999     NodeIt n;
    1000 
    1001     if( e.it == edges.end() ) {
    1002       // FIXME: invalid-> invalid
    1003       n.idx = length() + 1;
    1004       n.tail = true;
    1005       return n;
    1006     }
    1007 
    1008     n.idx = e.it-edges.begin();
    1009     n.tail = e.forw;
    1010     return n;
    1011   }
    1012 
    1013   template<typename Gr>
    1014   typename DynamicPath<Gr>::NodeIt
    1015   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>::GraphEdge
    1027   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>::GraphNode
    1038   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 EdgeIt
    1055       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[k-1]) ||
    1066                  G.tail(*e.it) == G.head(edges[k-1]) );
    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 NodeIt
    1076       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(bi-ai);
    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 
    1126705  ///@}
    1127706
Note: See TracChangeset for help on using the changeset viewer.