Changeset 803:c3d832275e69 in lemon0.x for src/hugo/skeletons/path.h
 Timestamp:
 09/05/04 22:13:48 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1097
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/skeletons/path.h
r797 r803 31 31 32 32 namespace hugo { 33 34 /// \addtogroup paths 35 /// @{ 36 37 38 //! \brief A structure for representing directed path in a graph. 39 //! 40 //! A structure for representing directed path in a graph. 41 //! \param Graph The graph type in which the path is. 42 //! \param DM DebugMode, defaults to DefaultDebugMode. 43 //! 44 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 45 //! and \c EdgeIt with the same usage. These types converts to the \c Node 46 //! and \c Edge of the original graph. 47 //! 48 //! \todo Thoroughfully check all the range and consistency tests. 49 template<typename Graph, typename DM = DefaultDebugMode> 50 class DirPath { 51 public: 52 /// Edge type of the underlying graph. 53 typedef typename Graph::Edge GraphEdge; 54 /// Node type of the underlying graph. 55 typedef typename Graph::Node GraphNode; 56 class NodeIt; 57 class EdgeIt; 58 59 protected: 60 const Graph *gr; 61 typedef std::vector<GraphEdge> Container; 62 Container edges; 63 64 public: 65 66 /// \param _G The graph in which the path is. 67 /// 68 DirPath(const Graph &_G) : gr(&_G) {} 69 70 /// \brief Subpath constructor. 71 /// 72 /// Subpath defined by two nodes. 73 /// \warning It is an error if the two edges are not in order! 74 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { 75 if( DM::range_check && (!a.valid()  !b.valid) ) { 76 // FIXME: this check should be more elaborate... 77 fault("DirPath, subpath ctor: invalid bounding nodes"); 78 } 79 gr = P.gr; 80 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 81 } 82 83 /// \brief Subpath constructor. 84 /// 85 /// Subpath defined by two edges. Contains edges in [a,b) 86 /// \warning It is an error if the two edges are not in order! 87 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { 88 if( DM::range_check && (!a.valid()  !b.valid) ) { 89 // FIXME: this check should be more elaborate... 90 fault("DirPath, subpath ctor: invalid bounding nodes"); 91 } 92 gr = P.gr; 93 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 94 } 95 96 /// Length of the path. 97 size_t length() const { return edges.size(); } 98 /// Returns whether the path is empty. 99 bool empty() const { return edges.empty(); } 100 101 /// Resets the path to an empty path. 102 void clear() { edges.clear(); } 103 104 /// \brief Starting point of the path. 105 /// 106 /// Starting point of the path. 107 /// Returns INVALID if the path is empty. 108 GraphNode from() const { 109 return empty() ? INVALID : gr>tail(edges[0]); 110 } 111 /// \brief End point of the path. 112 /// 113 /// End point of the path. 114 /// Returns INVALID if the path is empty. 115 GraphNode to() const { 116 return empty() ? INVALID : gr>head(edges[length()1]); 117 } 118 119 /// \brief Initializes node or edge iterator to point to the first 120 /// node or edge. 121 /// 122 /// \sa nth 123 template<typename It> 124 It& first(It &i) const { return i=It(*this); } 125 126 /// \brief Initializes node iterator to point to the node of a given index. 127 NodeIt& nth(NodeIt &i, int n) const { 128 if( DM::range_check && (n<0  n>int(length())) ) 129 fault("DirPath::nth: index out of range"); 130 return i=NodeIt(*this, n); 131 } 132 133 /// \brief Initializes edge iterator to point to the edge of a given index. 134 EdgeIt& nth(EdgeIt &i, int n) const { 135 if( DM::range_check && (n<0  n>=int(length())) ) 136 fault("DirPath::nth: index out of range"); 137 return i=EdgeIt(*this, n); 138 } 139 140 /// Checks validity of a node or edge iterator. 141 template<typename It> 142 static 143 bool valid(const It &i) { return i.valid(); } 144 145 /// Steps the given node or edge iterator. 146 template<typename It> 147 static 148 It& next(It &e) { 149 if( DM::range_check && !e.valid() ) 150 fault("DirPath::next() on invalid iterator"); 151 return ++e; 152 } 153 154 /// \brief Returns node iterator pointing to the head node of the 155 /// given edge iterator. 156 NodeIt head(const EdgeIt& e) const { 157 if( DM::range_check && !e.valid() ) 158 fault("DirPath::head() on invalid iterator"); 159 return NodeIt(*this, e.idx+1); 160 } 161 162 /// \brief Returns node iterator pointing to the tail node of the 163 /// given edge iterator. 164 NodeIt tail(const EdgeIt& e) const { 165 if( DM::range_check && !e.valid() ) 166 fault("DirPath::tail() on invalid iterator"); 167 return NodeIt(*this, e.idx); 168 } 169 170 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 */ 184 class EdgeIt { 185 friend class DirPath; 186 187 int idx; 188 const DirPath *p; 33 namespace skeleton { 34 /// \addtogroup skeletons 35 /// @{ 36 37 38 //! \brief A structure for representing directed path in a graph. 39 //! 40 //! A structure for representing directed path in a graph. 41 //! \param GR The graph type in which the path is. 42 //! 43 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 44 //! and \c EdgeIt with the same usage. These types converts to the \c Node 45 //! and \c Edge of the original graph. 46 template<typename GR> 47 class Path { 189 48 public: 190 /// Default constructor 191 EdgeIt() {} 192 /// Invalid constructor 193 EdgeIt(Invalid) : idx(1), p(0) {} 194 /// Constructor with starting point 195 EdgeIt(const DirPath &_p, int _idx = 0) : 196 idx(_idx), p(&_p) { validate(); } 197 198 ///Validity check 199 bool valid() const { return idx!=1; } 200 201 ///Conversion to Graph::Edge 202 operator GraphEdge () const { 203 return valid() ? p>edges[idx] : INVALID; 204 } 205 206 /// Next edge 207 EdgeIt& operator++() { ++idx; validate(); return *this; } 208 209 /// Comparison operator 210 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 211 /// Comparison operator 212 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 213 /// Comparison operator 214 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 215 216 private: 217 // FIXME: comparison between signed and unsigned... 218 // Jo ez igy? Vagy esetleg legyen a length() int? 219 void validate() { if( size_t(idx) >= p>length() ) idx=1; } 49 50 /// Type of the underlying graph. 51 typedef typename GR Graph; 52 /// Edge type of the underlying graph. 53 typedef typename Graph::Edge GraphEdge; 54 /// Node type of the underlying graph. 55 typedef typename Graph::Node GraphNode; 56 class NodeIt; 57 class EdgeIt; 58 59 /// \param _G The graph in which the path is. 60 /// 61 Path(const Graph &_G) {} 62 63 /// Length of the path. 64 size_t length() const {} 65 /// Returns whether the path is empty. 66 bool empty() const {} 67 68 /// Resets the path to an empty path. 69 void clear() {} 70 71 /// \brief Starting point of the path. 72 /// 73 /// Starting point of the path. 74 /// Returns INVALID if the path is empty. 75 NodeIt head() const {} 76 /// \brief End point of the path. 77 /// 78 /// End point of the path. 79 /// Returns INVALID if the path is empty. 80 NodeIt tail() const {} 81 82 /// \brief First NodeIt/EdgeIt. 83 /// 84 /// Initializes node or edge iterator to point to the first 85 /// node or edge. 86 template<typename It> 87 It& first(It &i) const { return i=It(*this); } 88 89 /// \brief The head of an edge. 90 /// 91 /// Returns node iterator pointing to the head node of the 92 /// given edge iterator. 93 NodeIt head(const EdgeIt& e) const {} 94 95 /// \brief The tail of an edge. 96 /// 97 /// Returns node iterator pointing to the tail node of the 98 /// given edge iterator. 99 NodeIt tail(const EdgeIt& e) const {} 100 101 102 /* Iterator classes */ 103 104 /** 105 * \brief Iterator class to iterate on the edges of the paths 106 * 107 * \ingroup skeletons 108 * This class is used to iterate on the edges of the paths 109 * 110 * Of course it converts to Graph::Edge 111 * 112 */ 113 class EdgeIt { 114 public: 115 /// Default constructor 116 EdgeIt() {} 117 /// Invalid constructor 118 EdgeIt(Invalid) {} 119 /// Constructor with starting point 120 EdgeIt(const Path &_p) {} 121 122 operator GraphEdge () const {} 123 124 /// Next edge 125 EdgeIt& operator++() {} 126 127 /// Comparison operator 128 bool operator==(const EdgeIt& e) const {} 129 /// Comparison operator 130 bool operator!=(const EdgeIt& e) const {} 131 // /// Comparison operator 132 // /// \todo It is not clear what is the "natural" ordering. 133 // bool operator<(const EdgeIt& e) const {} 134 135 }; 136 137 /** 138 * \brief Iterator class to iterate on the nodes of the paths 139 * 140 * \ingroup skeletons 141 * This class is used to iterate on the nodes of the paths 142 * 143 * Of course it converts to Graph::Node. 144 * 145 */ 146 class NodeIt { 147 public: 148 /// Default constructor 149 NodeIt() {} 150 /// Invalid constructor 151 NodeIt(Invalid) {} 152 /// Constructor with starting point 153 NodeIt(const Path &_p) {} 154 155 ///Conversion to Graph::Node 156 operator const GraphNode& () const {} 157 /// Next node 158 NodeIt& operator++() {} 159 160 /// Comparison operator 161 bool operator==(const NodeIt& e) const {} 162 /// Comparison operator 163 bool operator!=(const NodeIt& e) const {} 164 // /// Comparison operator 165 // /// \todo It is not clear what is the "natural" ordering. 166 // bool operator<(const NodeIt& e) const {} 167 168 }; 169 170 friend class Builder; 171 172 /** 173 * \brief Class to build paths 174 * 175 * \ingroup skeletons 176 * This class is used to fill a path with edges. 177 * 178 * You can push new edges to the front and to the back of the path in 179 * arbitrary order then you should commit these changes to the graph. 180 * 181 * While the builder is active (after the first modifying 182 * operation and until the call of \ref commit()) 183 * the underlining Path is in a 184 * "transitional" state (operations on it have undefined result). 185 */ 186 class Builder { 187 public: 188 ///\param _P the path you want to fill in. 189 /// 190 Builder(Path &_P) : P(_P) {} 191 192 /// Sets the starting node of the path. 193 194 /// Sets the starting node of the path. Edge added to the path 195 /// afterwards have to be incident to this node. 196 /// You \em must start building an empry path with this functions. 197 /// (And you \em must \em not use it later). 198 /// \sa pushFront() 199 /// \sa pushBack() 200 void setStartNode(const GraphNode &) {} 201 202 ///Push a new edge to the front of the path 203 204 ///Push a new edge to the front of the path. 205 ///If the path is empty, you \em must call \ref setStartNode() before 206 ///the first use of \ref pushFront(). 207 void pushFront(const GraphEdge& e) {} 208 209 ///Push a new edge to the back of the path 210 211 ///Push a new edge to the back of the path. 212 ///If the path is empty, you \em must call \ref setStartNode() before 213 ///the first use of \ref pushBack(). 214 void pushBack(const GraphEdge& e) {} 215 216 ///Commit the changes to the path. 217 void commit() {} 218 219 ///Reserve (front) storage for the builder in advance. 220 221 ///If you know an reasonable upper bound of the number of the edges 222 ///to add to the front of the path, 223 ///using this function you may speed up the building. 224 void reserveFront(size_t r) {} 225 ///Reserve (back) storage for the builder in advance. 226 227 ///If you know an reasonable upper bound of the number of the edges 228 ///to add to the back of the path, 229 ///using this function you may speed up the building. 230 void reserveBack(size_t r) {} 231 }; 220 232 }; 221 233 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 */ 233 class NodeIt { 234 friend class DirPath; 235 236 int idx; 237 const DirPath *p; 238 public: 239 /// Default constructor 240 NodeIt() {} 241 /// Invalid constructor 242 NodeIt(Invalid) : idx(1), p(0) {} 243 /// Constructor with starting point 244 NodeIt(const DirPath &_p, int _idx = 0) : 245 idx(_idx), p(&_p) { validate(); } 246 247 ///Validity check 248 bool valid() const { return idx!=1; } 249 250 ///Conversion to Graph::Node 251 operator const GraphNode& () const { 252 if(idx >= p>length()) 253 return p>to(); 254 else if(idx >= 0) 255 return p>gr>tail(p>edges[idx]); 256 else 257 return INVALID; 258 } 259 /// Next node 260 NodeIt& operator++() { ++idx; validate(); return *this; } 261 262 /// Comparison operator 263 bool operator==(const NodeIt& e) const { return idx==e.idx; } 264 /// Comparison operator 265 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 266 /// Comparison operator 267 bool operator<(const NodeIt& e) const { return idx<e.idx; } 268 269 private: 270 void validate() { if( size_t(idx) > p>length() ) idx=1; } 271 }; 272 273 friend class Builder; 274 275 /** 276 * \brief Class to build paths 277 * 278 * \ingroup paths 279 * This class is used to fill a path with edges. 280 * 281 * You can push new edges to the front and to the back of the path in 282 * arbitrary order then you should commit these changes to the graph. 283 * 284 * Fundamentally, for most "Paths" (classes fulfilling the 285 * PathConcept) while the builder is active (after the first modifying 286 * operation and until the commit()) the original Path is in a 287 * "transitional" state (operations on it have undefined result). But 288 * in the case of DirPath the original path remains unchanged until the 289 * commit. However we don't recomend that you use this feature. 290 */ 291 class Builder { 292 DirPath &P; 293 Container front, back; 294 295 public: 296 ///\param _P the path you want to fill in. 297 /// 298 Builder(DirPath &_P) : P(_P) {} 299 300 /// Sets the starting node of the path. 301 302 /// Sets the starting node of the path. Edge added to the path 303 /// afterwards have to be incident to this node. 304 /// It should be called iff the path is empty and before any call to 305 /// \ref pushFront() or \ref pushBack() 306 void setStart(const GraphNode &) {} 307 308 ///Push a new edge to the front of the path 309 310 ///Push a new edge to the front of the path. 311 ///\sa setStart 312 void pushFront(const GraphEdge& e) { 313 if( DM::consistensy_check && !empty() && P.gr>head(e)!=from() ) { 314 fault("DirPath::Builder::pushFront: nonincident edge"); 315 } 316 front.push_back(e); 317 } 318 319 ///Push a new edge to the back of the path 320 321 ///Push a new edge to the back of the path. 322 ///\sa setStart 323 void pushBack(const GraphEdge& e) { 324 if( DM::consistensy_check && !empty() && P.gr>tail(e)!=to() ) { 325 fault("DirPath::Builder::pushBack: nonincident edge"); 326 } 327 back.push_back(e); 328 } 329 330 ///Commit the changes to the path. 331 void commit() { 332 if( !(front.empty() && back.empty()) ) { 333 Container tmp; 334 tmp.reserve(front.size()+back.size()+P.length()); 335 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 336 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); 337 tmp.insert(tmp.end(), back.begin(), back.end()); 338 P.edges.swap(tmp); 339 front.clear(); 340 back.clear(); 341 } 342 } 343 344 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 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. 351 void reserve(size_t r) { 352 front.reserve(r); 353 back.reserve(r); 354 } 355 356 private: 357 bool empty() { 358 return front.empty() && back.empty() && P.empty(); 359 } 360 361 GraphNode from() const { 362 if( ! front.empty() ) 363 return P.gr>tail(front[front.size()1]); 364 else if( ! P.empty() ) 365 return P.gr>tail(P.edges[0]); 366 else if( ! back.empty() ) 367 return P.gr>tail(back[0]); 368 else 369 return INVALID; 370 } 371 GraphNode to() const { 372 if( ! back.empty() ) 373 return P.gr>head(back[back.size()1]); 374 else if( ! P.empty() ) 375 return P.gr>head(P.edges[P.length()1]); 376 else if( ! front.empty() ) 377 return P.gr>head(front[0]); 378 else 379 return INVALID; 380 } 381 382 }; 383 384 }; 385 386 387 388 389 390 391 392 393 394 395 /**********************************************************************/ 396 397 398 //! \brief A structure for representing undirected path in a graph. 399 //! 400 //! A structure for representing undirected path in a graph. Ie. this is 401 //! a path in a \e directed graph but the edges should not be directed 402 //! forward. 403 //! 404 //! \param Graph The graph type in which the path is. 405 //! \param DM DebugMode, defaults to DefaultDebugMode. 406 //! 407 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 408 //! and \c EdgeIt with the same usage. These types converts to the \c Node 409 //! and \c Edge of the original graph. 410 //! 411 //! \todo Thoroughfully check all the range and consistency tests. 412 template<typename Graph, typename DM = DefaultDebugMode> 413 class UndirPath { 414 public: 415 /// Edge type of the underlying graph. 416 typedef typename Graph::Edge GraphEdge; 417 /// Node type of the underlying graph. 418 typedef typename Graph::Node GraphNode; 419 class NodeIt; 420 class EdgeIt; 421 422 protected: 423 const Graph *gr; 424 typedef std::vector<GraphEdge> Container; 425 Container edges; 426 427 public: 428 429 /// \param _G The graph in which the path is. 430 /// 431 UndirPath(const Graph &_G) : gr(&_G) {} 432 433 /// \brief Subpath constructor. 434 /// 435 /// Subpath defined by two nodes. 436 /// \warning It is an error if the two edges are not in order! 437 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) { 438 if( DM::range_check && (!a.valid()  !b.valid) ) { 439 // FIXME: this check should be more elaborate... 440 fault("UndirPath, subpath ctor: invalid bounding nodes"); 441 } 442 gr = P.gr; 443 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 444 } 445 446 /// \brief Subpath constructor. 447 /// 448 /// Subpath defined by two edges. Contains edges in [a,b) 449 /// \warning It is an error if the two edges are not in order! 450 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) { 451 if( DM::range_check && (!a.valid()  !b.valid) ) { 452 // FIXME: this check should be more elaborate... 453 fault("UndirPath, subpath ctor: invalid bounding nodes"); 454 } 455 gr = P.gr; 456 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 457 } 458 459 /// Length of the path. 460 size_t length() const { return edges.size(); } 461 /// Returns whether the path is empty. 462 bool empty() const { return edges.empty(); } 463 464 /// Resets the path to an empty path. 465 void clear() { edges.clear(); } 466 467 /// \brief Starting point of the path. 468 /// 469 /// Starting point of the path. 470 /// Returns INVALID if the path is empty. 471 GraphNode from() const { 472 return empty() ? INVALID : gr>tail(edges[0]); 473 } 474 /// \brief End point of the path. 475 /// 476 /// End point of the path. 477 /// Returns INVALID if the path is empty. 478 GraphNode to() const { 479 return empty() ? INVALID : gr>head(edges[length()1]); 480 } 481 482 /// \brief Initializes node or edge iterator to point to the first 483 /// node or edge. 484 /// 485 /// \sa nth 486 template<typename It> 487 It& first(It &i) const { return i=It(*this); } 488 489 /// \brief Initializes node iterator to point to the node of a given index. 490 NodeIt& nth(NodeIt &i, int n) const { 491 if( DM::range_check && (n<0  n>int(length())) ) 492 fault("UndirPath::nth: index out of range"); 493 return i=NodeIt(*this, n); 494 } 495 496 /// \brief Initializes edge iterator to point to the edge of a given index. 497 EdgeIt& nth(EdgeIt &i, int n) const { 498 if( DM::range_check && (n<0  n>=int(length())) ) 499 fault("UndirPath::nth: index out of range"); 500 return i=EdgeIt(*this, n); 501 } 502 503 /// Checks validity of a node or edge iterator. 504 template<typename It> 505 static 506 bool valid(const It &i) { return i.valid(); } 507 508 /// Steps the given node or edge iterator. 509 template<typename It> 510 static 511 It& next(It &e) { 512 if( DM::range_check && !e.valid() ) 513 fault("UndirPath::next() on invalid iterator"); 514 return ++e; 515 } 516 517 /// \brief Returns node iterator pointing to the head node of the 518 /// given edge iterator. 519 NodeIt head(const EdgeIt& e) const { 520 if( DM::range_check && !e.valid() ) 521 fault("UndirPath::head() on invalid iterator"); 522 return NodeIt(*this, e.idx+1); 523 } 524 525 /// \brief Returns node iterator pointing to the tail node of the 526 /// given edge iterator. 527 NodeIt tail(const EdgeIt& e) const { 528 if( DM::range_check && !e.valid() ) 529 fault("UndirPath::tail() on invalid iterator"); 530 return NodeIt(*this, e.idx); 531 } 532 533 534 535 /** 536 * \brief Iterator class to iterate on the edges of the paths 537 * 538 * \ingroup paths 539 * This class is used to iterate on the edges of the paths 540 * 541 * Of course it converts to Graph::Edge 542 * 543 * \todo Its interface differs from the standard edge iterator. 544 * Yes, it shouldn't. 545 */ 546 class EdgeIt { 547 friend class UndirPath; 548 549 int idx; 550 const UndirPath *p; 551 public: 552 /// Default constructor 553 EdgeIt() {} 554 /// Invalid constructor 555 EdgeIt(Invalid) : idx(1), p(0) {} 556 /// Constructor with starting point 557 EdgeIt(const UndirPath &_p, int _idx = 0) : 558 idx(_idx), p(&_p) { validate(); } 559 560 ///Validity check 561 bool valid() const { return idx!=1; } 562 563 ///Conversion to Graph::Edge 564 operator GraphEdge () const { 565 return valid() ? p>edges[idx] : INVALID; 566 } 567 /// Next edge 568 EdgeIt& operator++() { ++idx; validate(); return *this; } 569 570 /// Comparison operator 571 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 572 /// Comparison operator 573 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 574 /// Comparison operator 575 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 576 577 private: 578 // FIXME: comparison between signed and unsigned... 579 // Jo ez igy? Vagy esetleg legyen a length() int? 580 void validate() { if( size_t(idx) >= p>length() ) idx=1; } 581 }; 582 583 /** 584 * \brief Iterator class to iterate on the nodes of the paths 585 * 586 * \ingroup paths 587 * This class is used to iterate on the nodes of the paths 588 * 589 * Of course it converts to Graph::Node 590 * 591 * \todo Its interface differs from the standard node iterator. 592 * Yes, it shouldn't. 593 */ 594 class NodeIt { 595 friend class UndirPath; 596 597 int idx; 598 const UndirPath *p; 599 public: 600 /// Default constructor 601 NodeIt() {} 602 /// Invalid constructor 603 NodeIt(Invalid) : idx(1), p(0) {} 604 /// Constructor with starting point 605 NodeIt(const UndirPath &_p, int _idx = 0) : 606 idx(_idx), p(&_p) { validate(); } 607 608 ///Validity check 609 bool valid() const { return idx!=1; } 610 611 ///Conversion to Graph::Node 612 operator const GraphNode& () const { 613 if(idx >= p>length()) 614 return p>to(); 615 else if(idx >= 0) 616 return p>gr>tail(p>edges[idx]); 617 else 618 return INVALID; 619 } 620 /// Next node 621 NodeIt& operator++() { ++idx; validate(); return *this; } 622 623 /// Comparison operator 624 bool operator==(const NodeIt& e) const { return idx==e.idx; } 625 /// Comparison operator 626 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 627 /// Comparison operator 628 bool operator<(const NodeIt& e) const { return idx<e.idx; } 629 630 private: 631 void validate() { if( size_t(idx) > p>length() ) idx=1; } 632 }; 633 634 friend class Builder; 635 636 /** 637 * \brief Class to build paths 638 * 639 * \ingroup paths 640 * This class is used to fill a path with edges. 641 * 642 * You can push new edges to the front and to the back of the path in 643 * arbitrary order then you should commit these changes to the graph. 644 * 645 * Fundamentally, for most "Paths" (classes fulfilling the 646 * PathConcept) while the builder is active (after the first modifying 647 * operation and until the commit()) the original Path is in a 648 * "transitional" state (operations ot it have undefined result). But 649 * in the case of UndirPath the original path is unchanged until the 650 * commit. However we don't recomend that you use this feature. 651 */ 652 class Builder { 653 UndirPath &P; 654 Container front, back; 655 656 public: 657 ///\param _P the path you want to fill in. 658 /// 659 Builder(UndirPath &_P) : P(_P) {} 660 661 /// Sets the starting node of the path. 662 663 /// Sets the starting node of the path. Edge added to the path 664 /// afterwards have to be incident to this node. 665 /// It should be called iff the path is empty and before any call to 666 /// \ref pushFront() or \ref pushBack() 667 void setStart(const GraphNode &) {} 668 669 ///Push a new edge to the front of the path 670 671 ///Push a new edge to the front of the path. 672 ///\sa setStart 673 void pushFront(const GraphEdge& e) { 674 if( DM::consistensy_check && !empty() && P.gr>head(e)!=from() ) { 675 fault("UndirPath::Builder::pushFront: nonincident edge"); 676 } 677 front.push_back(e); 678 } 679 680 ///Push a new edge to the back of the path 681 682 ///Push a new edge to the back of the path. 683 ///\sa setStart 684 void pushBack(const GraphEdge& e) { 685 if( DM::consistensy_check && !empty() && P.gr>tail(e)!=to() ) { 686 fault("UndirPath::Builder::pushBack: nonincident edge"); 687 } 688 back.push_back(e); 689 } 690 691 ///Commit the changes to the path. 692 void commit() { 693 if( !(front.empty() && back.empty()) ) { 694 Container tmp; 695 tmp.reserve(front.size()+back.size()+P.length()); 696 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 697 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); 698 tmp.insert(tmp.end(), back.begin(), back.end()); 699 P.edges.swap(tmp); 700 front.clear(); 701 back.clear(); 702 } 703 } 704 705 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 706 // Hogy kenyelmes egy ilyet hasznalni? 707 708 ///Reserve storage in advance for the builder 709 710 ///If you know an reasonable upper bound of the number of the edges 711 ///to add, using this function you can speed up the building. 712 void reserve(size_t r) { 713 front.reserve(r); 714 back.reserve(r); 715 } 716 717 private: 718 bool empty() { 719 return front.empty() && back.empty() && P.empty(); 720 } 721 722 GraphNode from() const { 723 if( ! front.empty() ) 724 return P.gr>tail(front[front.size()1]); 725 else if( ! P.empty() ) 726 return P.gr>tail(P.edges[0]); 727 else if( ! back.empty() ) 728 return P.gr>tail(back[0]); 729 else 730 return INVALID; 731 } 732 GraphNode to() const { 733 if( ! back.empty() ) 734 return P.gr>head(back[back.size()1]); 735 else if( ! P.empty() ) 736 return P.gr>head(P.edges[P.length()1]); 737 else if( ! front.empty() ) 738 return P.gr>head(front[0]); 739 else 740 return INVALID; 741 } 742 743 }; 744 745 }; 746 747 748 749 750 751 752 753 754 755 756 /**********************************************************************/ 757 758 759 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata 760 elott. Eleg bonyinak nez ki, ahogyan azokat az STLben hasznaljak. */ 761 762 template<typename Graph> 763 class DynamicPath { 764 765 public: 766 typedef typename Graph::Edge GraphEdge; 767 typedef typename Graph::Node GraphNode; 768 class NodeIt; 769 class EdgeIt; 770 771 protected: 772 Graph& G; 773 // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el 774 // iranyitasat: 775 GraphNode _first, _last; 776 typedef std::deque<GraphEdge> Container; 777 Container edges; 778 779 public: 780 781 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {} 782 783 /// Subpath defined by two nodes. 784 /// Nodes may be in reversed order, then 785 /// we contstruct the reversed path. 786 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b); 787 /// Subpath defined by two edges. Contains edges in [a,b) 788 /// It is an error if the two edges are not in order! 789 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b); 790 791 size_t length() const { return edges.size(); } 792 GraphNode from() const { return _first; } 793 GraphNode to() const { return _last; } 794 795 NodeIt& first(NodeIt &n) const { return nth(n, 0); } 796 EdgeIt& first(EdgeIt &e) const { return nth(e, 0); } 797 template<typename It> 798 It first() const { 799 It e; 800 first(e); 801 return e; 802 } 803 804 NodeIt& nth(NodeIt &, size_t) const; 805 EdgeIt& nth(EdgeIt &, size_t) const; 806 template<typename It> 807 It nth(size_t n) const { 808 It e; 809 nth(e, n); 810 return e; 811 } 812 813 bool valid(const NodeIt &n) const { return n.idx <= length(); } 814 bool valid(const EdgeIt &e) const { return e.it < edges.end(); } 815 816 bool isForward(const EdgeIt &e) const { return e.forw; } 817 818 /// index of a node on the path. Returns length+2 for the invalid NodeIt 819 int index(const NodeIt &n) const { return n.idx; } 820 /// index of an edge on the path. Returns length+1 for the invalid EdgeIt 821 int index(const EdgeIt &e) const { return e.it  edges.begin(); } 822 823 EdgeIt& next(EdgeIt &e) const; 824 NodeIt& next(NodeIt &n) const; 825 template <typename It> 826 It getNext(It it) const { 827 It tmp(it); return next(tmp); 828 } 829 830 // A path is constructed using the following four functions. 831 // They return false if the requested operation is inconsistent 832 // with the path constructed so far. 833 // If your path has only one edge you MUST set either "from" or "to"! 834 // So you probably SHOULD call it in any case to be safe (and check the 835 // returned value to check if your path is consistent with your idea). 836 bool pushFront(const GraphEdge &e); 837 bool pushBack(const GraphEdge &e); 838 bool setFrom(const GraphNode &n); 839 bool setTo(const GraphNode &n); 840 841 // WARNING: these two functions return the head/tail of an edge with 842 // respect to the direction of the path! 843 // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if 844 // P.forward(e) is true (or the edge is a loop)! 845 NodeIt head(const EdgeIt& e) const; 846 NodeIt tail(const EdgeIt& e) const; 847 848 // FIXME: ezeknek valami jobb nev kellene!!! 849 GraphEdge graphEdge(const EdgeIt& e) const; 850 GraphNode graphNode(const NodeIt& n) const; 851 852 853 /*** Iterator classes ***/ 854 class EdgeIt { 855 friend class DynamicPath; 856 857 typename Container::const_iterator it; 858 bool forw; 859 public: 860 // FIXME: jarna neki ilyen is... 861 // EdgeIt(Invalid); 862 863 bool forward() const { return forw; } 864 865 bool operator==(const EdgeIt& e) const { return it==e.it; } 866 bool operator!=(const EdgeIt& e) const { return it!=e.it; } 867 bool operator<(const EdgeIt& e) const { return it<e.it; } 868 }; 869 870 class NodeIt { 871 friend class DynamicPath; 872 873 size_t idx; 874 bool tail; // Is this node the tail of the edge with same idx? 875 876 public: 877 // FIXME: jarna neki ilyen is... 878 // NodeIt(Invalid); 879 880 bool operator==(const NodeIt& n) const { return idx==n.idx; } 881 bool operator!=(const NodeIt& n) const { return idx!=n.idx; } 882 bool operator<(const NodeIt& n) const { return idx<n.idx; } 883 }; 884 885 private: 886 bool edgeIncident(const GraphEdge &e, const GraphNode &a, 887 GraphNode &b); 888 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f); 889 }; 890 891 template<typename Gr> 892 typename DynamicPath<Gr>::EdgeIt& 893 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const { 894 if( e.it == edges.end() ) 895 return e; 896 897 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) ); 898 ++e.it; 899 900 // Invalid edgeit is always forward :) 901 if( e.it == edges.end() ) { 902 e.forw = true; 903 return e; 904 } 905 906 e.forw = ( G.tail(*e.it) == common_node ); 907 return e; 908 } 909 910 template<typename Gr> 911 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const { 912 if( n.idx >= length() ) { 913 // FIXME: invalid 914 n.idx = length()+1; 915 return n; 916 } 917 918 919 GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) : 920 G.tail(edges[n.idx]) ); 921 ++n.idx; 922 if( n.idx < length() ) { 923 n.tail = ( next_node == G.tail(edges[n.idx]) ); 924 } 925 else { 926 n.tail = true; 927 } 928 929 return n; 930 } 931 932 template<typename Gr> 933 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a, 934 GraphNode &b) { 935 if( G.tail(e) == a ) { 936 b=G.head(e); 937 return true; 938 } 939 if( G.head(e) == a ) { 940 b=G.tail(e); 941 return true; 942 } 943 return false; 944 } 945 946 template<typename Gr> 947 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e, 948 const GraphEdge &f) { 949 if( edgeIncident(f, G.tail(e), _last) ) { 950 _first = G.head(e); 951 return true; 952 } 953 if( edgeIncident(f, G.head(e), _last) ) { 954 _first = G.tail(e); 955 return true; 956 } 957 return false; 958 } 959 960 template<typename Gr> 961 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) { 962 if( G.valid(_first) ) { 963 if( edgeIncident(e, _first, _first) ) { 964 edges.push_front(e); 965 return true; 966 } 967 else 968 return false; 969 } 970 else if( length() < 1  connectTwoEdges(e, edges[0]) ) { 971 edges.push_front(e); 972 return true; 973 } 974 else 975 return false; 976 } 977 978 template<typename Gr> 979 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) { 980 if( G.valid(_last) ) { 981 if( edgeIncident(e, _last, _last) ) { 982 edges.push_back(e); 983 return true; 984 } 985 else 986 return false; 987 } 988 else if( length() < 1  connectTwoEdges(edges[0], e) ) { 989 edges.push_back(e); 990 return true; 991 } 992 else 993 return false; 994 } 995 996 997 template<typename Gr> 998 bool DynamicPath<Gr>::setFrom(const GraphNode &n) { 999 if( G.valid(_first) ) { 1000 return _first == n; 1001 } 1002 else { 1003 if( length() > 0) { 1004 if( edgeIncident(edges[0], n, _last) ) { 1005 _first = n; 1006 return true; 1007 } 1008 else return false; 1009 } 1010 else { 1011 _first = _last = n; 1012 return true; 1013 } 1014 } 1015 } 1016 1017 template<typename Gr> 1018 bool DynamicPath<Gr>::setTo(const GraphNode &n) { 1019 if( G.valid(_last) ) { 1020 return _last == n; 1021 } 1022 else { 1023 if( length() > 0) { 1024 if( edgeIncident(edges[0], n, _first) ) { 1025 _last = n; 1026 return true; 1027 } 1028 else return false; 1029 } 1030 else { 1031 _first = _last = n; 1032 return true; 1033 } 1034 } 1035 } 1036 1037 1038 template<typename Gr> 1039 typename DynamicPath<Gr>::NodeIt 1040 DynamicPath<Gr>::tail(const EdgeIt& e) const { 1041 NodeIt n; 1042 1043 if( e.it == edges.end() ) { 1044 // FIXME: invalid> invalid 1045 n.idx = length() + 1; 1046 n.tail = true; 1047 return n; 1048 } 1049 1050 n.idx = e.itedges.begin(); 1051 n.tail = e.forw; 1052 return n; 1053 } 1054 1055 template<typename Gr> 1056 typename DynamicPath<Gr>::NodeIt 1057 DynamicPath<Gr>::head(const EdgeIt& e) const { 1058 if( e.it == edges.end()1 ) { 1059 return _last; 1060 } 1061 1062 EdgeIt next_edge = e; 1063 next(next_edge); 1064 return tail(next_edge); 1065 } 1066 1067 template<typename Gr> 1068 typename DynamicPath<Gr>::GraphEdge 1069 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const { 1070 if( e.it != edges.end() ) { 1071 return *e.it; 1072 } 1073 else { 1074 return INVALID; 1075 } 234 ///@} 1076 235 } 1077 236 1078 template<typename Gr>1079 typename DynamicPath<Gr>::GraphNode1080 DynamicPath<Gr>::graphNode(const NodeIt& n) const {1081 if( n.idx < length() ) {1082 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);1083 }1084 else if( n.idx == length() ) {1085 return _last;1086 }1087 else {1088 return INVALID;1089 }1090 }1091 1092 template<typename Gr>1093 typename DynamicPath<Gr>::EdgeIt&1094 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {1095 if( k>=length() ) {1096 // FIXME: invalid EdgeIt1097 e.it = edges.end();1098 e.forw = true;1099 return e;1100 }1101 1102 e.it = edges.begin()+k;1103 if(k==0) {1104 e.forw = ( G.tail(*e.it) == _first );1105 }1106 else {1107 e.forw = ( G.tail(*e.it) == G.tail(edges[k1]) 1108 G.tail(*e.it) == G.head(edges[k1]) );1109 }1110 return e;1111 }1112 1113 template<typename Gr>1114 typename DynamicPath<Gr>::NodeIt&1115 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {1116 if( k>length() ) {1117 // FIXME: invalid NodeIt1118 n.idx = length()+1;1119 n.tail = true;1120 return n;1121 }1122 if( k==length() ) {1123 n.idx = length();1124 n.tail = true;1125 return n;1126 }1127 n = tail(nth<EdgeIt>(k));1128 return n;1129 }1130 1131 // Reszut konstruktorok:1132 1133 1134 template<typename Gr>1135 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,1136 const EdgeIt &b) :1137 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!1138 {1139 if( G.valid(P._first) && a.it < P.edges.end() ) {1140 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );1141 if( b.it < P.edges.end() ) {1142 _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );1143 }1144 else {1145 _last = P._last;1146 }1147 }1148 }1149 1150 template<typename Gr>1151 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,1152 const NodeIt &b) : G(P.G)1153 {1154 if( !P.valid(a)  !P.valid(b) )1155 return;1156 1157 int ai = a.idx, bi = b.idx;1158 if( bi<ai )1159 std::swap(ai,bi);1160 1161 edges.resize(biai);1162 copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());1163 1164 _first = P.graphNode(a);1165 _last = P.graphNode(b);1166 }1167 1168 ///@}1169 1170 237 } // namespace hugo 1171 238
Note: See TracChangeset
for help on using the changeset viewer.