Changeset 493:bbd1db03f0fe in lemon-0.x for src/work/klao/path.h
- Timestamp:
- 04/30/04 03:59:15 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@651
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/klao/path.h
r450 r493 1 1 // -*- c++ -*- // 2 2 3 /// ingroup datas3 ///\ingroup datas 4 4 ///\file 5 ///\brief Class for representing paths in graphs.5 ///\brief Classes for representing paths in graphs. 6 6 7 7 #ifndef HUGO_PATH_H … … 13 13 14 14 #include <invalid.h> 15 #include <error.h> 16 #include <debug.h> 15 17 16 18 namespace hugo { … … 19 21 /// @{ 20 22 21 ///A container for directed paths 22 23 ///\param Graph The graph type in which the path is. 24 /// 25 ///In a sense, the path can be treated as a graph, for is has \c NodeIt 26 ///and \c EdgeIt with the same usage. These types converts to the \c Node 27 ///and \c Edge of the original graph. 28 ///\todo How to clear a path? 29 ///\todo Clarify the consistency checks to do. 30 template<typename Graph> 23 24 //! \brief A structure for representing directed path in a graph. 25 //! 26 //! \param Graph The graph type in which the path is. 27 //! \param DM DebugMode, defaults to DefaultDebugMode. 28 //! 29 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 30 //! and \c EdgeIt with the same usage. These types converts to the \c Node 31 //! and \c Edge of the original graph. 32 //! 33 //! \todo Thoroughfully check all the range and consistency tests. 34 template<typename Graph, typename DM = DefaultDebugMode> 31 35 class DirPath { 32 36 public: … … 43 47 public: 44 48 45 /// Constructor46 47 49 /// \param _G The graph in which the path is. 48 50 /// 49 51 DirPath(const Graph &_G) : gr(&_G) {} 50 52 53 /// \brief Subpath constructor. 54 /// 51 55 /// Subpath defined by two nodes. 52 56 /// \warning It is an error if the two edges are not in order! 57 /// \todo Implement! 53 58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); 59 /// \brief Subpath constructor. 60 /// 54 61 /// Subpath defined by two edges. Contains edges in [a,b) 55 62 /// \warning It is an error if the two edges are not in order! 63 /// \todo Implement! 56 64 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); 57 65 66 /// Length of the path. 58 67 size_t length() const { return edges.size(); } 68 /// Returns whether the path is empty. 59 69 bool empty() const { return edges.empty(); } 70 71 /// Resets the path to an empty path. 72 void clear() { edges.clear(); } 73 74 /// \brief Starting point of the path. 75 /// 76 /// Starting point of the path. 77 /// Returns INVALID if the path is empty. 60 78 GraphNode from() const { 61 79 return empty() ? INVALID : gr->tail(edges[0]); 62 80 } 81 /// \brief End point of the path. 82 /// 83 /// End point of the path. 84 /// Returns INVALID if the path is empty. 63 85 GraphNode to() const { 64 86 return empty() ? INVALID : gr->head(edges[length()-1]); 65 87 } 66 88 89 /// \brief Initializes node or edge iterator to point to the first 90 /// node or edge. 91 /// 92 /// \sa nth 67 93 template<typename It> 68 94 It& first(It &i) const { return i=It(*this); } 69 95 96 /// \brief Initializes node or edge iterator to point to the node or edge 97 /// of a given index. 70 98 template<typename It> 71 It& nth(It &i, int n) const { return i=It(*this, n); } 72 99 It& nth(It &i, int n) const { 100 // FIXME: this test should be different for NodeIt and EdgeIt: 101 if( DM::range_check && (n<0 || n>int(length())) ) 102 fault("DirPath::nth: index out of range"); 103 return i=It(*this, n); 104 } 105 106 /// Checks validity of a node or edge iterator. 73 107 template<typename It> 74 108 bool valid(const It &i) const { return i.valid(); } 75 109 110 /// Steps the given node or edge iterator. 76 111 template<typename It> 77 It& next(It &e) const { return ++e; } 78 79 /// \todo ! 80 NodeIt head(const EdgeIt& e) const; 81 NodeIt tail(const EdgeIt& e) const; 112 It& next(It &e) const { 113 if( DM::range_check && !e.valid() ) 114 fault("DirPath::next() on invalid iterator"); 115 return ++e; 116 } 117 118 /// \brief Returns node iterator pointing to the head node of the 119 /// given edge iterator. 120 NodeIt head(const EdgeIt& e) const { 121 return NodeIt(*this, e.idx+1); 122 } 123 124 /// \brief Returns node iterator pointing to the tail node of the 125 /// given edge iterator. 126 NodeIt tail(const EdgeIt& e) const { 127 return NodeIt(*this, e.idx); 128 } 82 129 83 130 … … 144 191 friend class Builder; 145 192 146 ///Class to build paths 147 148 ///\ingroup datas 149 ///This class is used to build new paths. 150 ///You can push new edges to the front and to the back of the path in 151 ///arbitrary order the you can commit these changes to the graph. 152 ///\todo We must clarify when the path will be in "transitional" state. 193 /** 194 * \brief Class to build paths 195 * 196 * \ingroup datas 197 * This class is used to fill a path with edges. 198 * 199 * You can push new edges to the front and to the back of the path in 200 * arbitrary order the you can commit these changes to the graph. 201 * 202 * Fundamentally, for most "Paths" (classes fulfilling the 203 * PathConcept) while the builder is active (after the first modifying 204 * operation and until the commit()) the original Path is in a 205 * "transitional" state (operations ot it have undefined result). But 206 * in the case of DirPath the original path is unchanged until the 207 * commit. However we don't recomend that you use this feature. 208 */ 153 209 class Builder { 154 210 DirPath &P; 155 Container d;211 Container front, back; 156 212 157 213 public: 158 ///Constructor 159 160 ///\param _P the path you want to build. 214 ///\param _P the path you want to fill in. 161 215 /// 162 216 Builder(DirPath &_P) : P(_P) {} 163 217 164 ///Set the first node of the path.218 ///Sets the first node of the path. 165 219 166 ///Set the first node of the path. 167 ///If the path is empty, this must be call before any call of 168 ///\ref pushFront() or \ref pushBack() 169 void setFirst(const GraphNode &) { } 220 ///Sets the first node of the path. If the path is empty, this 221 ///function or setTo() have to be called before any call to \ref 222 ///pushFront() or \ref pushBack() 223 void setFrom(const GraphNode &) {} 224 225 ///Sets the last node of the path. 226 227 ///Sets the last node of the path. If the path is empty, this 228 ///function or setFrom() have to be called before any call of \ref 229 ///pushFront() or \ref pushBack() 230 void setTo(const GraphNode &) {} 170 231 171 232 ///Push a new edge to the front of the path 172 233 173 234 ///Push a new edge to the front of the path. 174 ///\sa setFirst() 175 bool pushFront(const GraphEdge& e) { 176 if( empty() || P.gr->head(e)==from() ) { 177 d.push_back(e); 178 return true; 235 ///\sa setTo 236 void pushFront(const GraphEdge& e) { 237 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) { 238 fault("DirPath::Builder::pushFront: nonincident edge"); 179 239 } 180 return false; 181 } 240 front.push_back(e); 241 } 242 182 243 ///Push a new edge to the back of the path 183 244 184 245 ///Push a new edge to the back of the path. 185 ///\sa setFirst() 186 bool pushBack(const GraphEdge& e) { 187 if( empty() || P.gr->tail(e)==to() ) { 188 P.edges.push_back(e); 189 return true; 246 ///\sa setFrom 247 void pushBack(const GraphEdge& e) { 248 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) { 249 fault("DirPath::Builder::pushBack: nonincident edge"); 190 250 } 191 return false;251 back.push_back(e); 192 252 } 193 253 194 254 ///Commit the changes to the path. 195 255 void commit() { 196 if( !d.empty() ) { 197 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); 198 d.clear(); 256 if( !(front.empty() && back.empty()) ) { 257 Container tmp; 258 tmp.reserve(front.size()+back.size()+P.length()); 259 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 260 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); 261 tmp.insert(tmp.end(), back.begin(), back.end()); 262 P.edges.swap(tmp); 263 front.clear(); 264 back.clear(); 199 265 } 200 266 } 201 267 202 ///Desctuctor 203 204 ///The desctuctor. 205 ///It commit also commit the changes. 206 ///\todo Is this what we want? 207 ~Builder() { commit(); } 268 // ///Desctuctor 269 270 // ///The desctuctor. 271 // ///It commit also commit the changes. 272 // ///\todo Is this what we want? 273 // Nope. Let's use commit() explicitly. 274 // ~Builder() { commit(); } 208 275 209 276 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 210 277 // Hogy kenyelmes egy ilyet hasznalni? 211 278 void reserve(size_t r) { 212 d.reserve(r);213 P.edges.reserve(P.length()+r);279 front.reserve(r); 280 back.reserve(r); 214 281 } 215 282 216 283 private: 217 bool empty() { return d.empty() && P.empty(); } 284 bool empty() { 285 return front.empty() && back.empty() && P.empty(); 286 } 218 287 219 288 GraphNode from() const { 220 if( ! d.empty() )221 return P.gr->tail( d[d.size()-1]);289 if( ! front.empty() ) 290 return P.gr->tail(front[front.size()-1]); 222 291 else if( ! P.empty() ) 223 292 return P.gr->tail(P.edges[0]); 293 else if( ! back.empty() ) 294 return P.gr->tail(back[0]); 224 295 else 225 296 return INVALID; 226 297 } 227 298 GraphNode to() const { 228 if( ! P.empty() ) 299 if( ! back.empty() ) 300 return P.gr->head(back[back.size()-1]); 301 else if( ! P.empty() ) 229 302 return P.gr->head(P.edges[P.length()-1]); 230 else if( ! d.empty() )231 return P.gr->head( d[0]);303 else if( ! front.empty() ) 304 return P.gr->head(front[0]); 232 305 else 233 306 return INVALID;
Note: See TracChangeset
for help on using the changeset viewer.