Changeset 619:e09818232531 in lemon0.x for src/work/klao/path.h
 Timestamp:
 05/12/04 00:50:09 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@804
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/klao/path.h
r607 r619 24 24 //! \brief A structure for representing directed path in a graph. 25 25 //! 26 //! A structure for representing directed path in a graph. 26 27 //! \param Graph The graph type in which the path is. 27 28 //! \param DM DebugMode, defaults to DefaultDebugMode. … … 55 56 /// Subpath defined by two nodes. 56 57 /// \warning It is an error if the two edges are not in order! 57 /// \todo Implement! 58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); 58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { 59 if( DM::range_check && (!a.valid()  !b.valid) ) { 60 // FIXME: this check should be more elaborate... 61 fault("DirPath, subpath ctor: invalid bounding nodes"); 62 } 63 gr = P.gr; 64 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 65 } 66 59 67 /// \brief Subpath constructor. 60 68 /// 61 69 /// Subpath defined by two edges. Contains edges in [a,b) 62 70 /// \warning It is an error if the two edges are not in order! 63 /// \todo Implement! 64 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); 71 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { 72 if( DM::range_check && (!a.valid()  !b.valid) ) { 73 // FIXME: this check should be more elaborate... 74 fault("DirPath, subpath ctor: invalid bounding nodes"); 75 } 76 gr = P.gr; 77 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 78 } 65 79 66 80 /// Length of the path. … … 94 108 It& first(It &i) const { return i=It(*this); } 95 109 96 /// \brief Initializes node or edge iterator to point to the node or edge 97 /// of a given index. 98 template<typename It> 99 It& nth(It &i, int n) const { 100 // FIXME: this test should be different for NodeIt and EdgeIt: 110 /// \brief Initializes node iterator to point to the node of a given index. 111 NodeIt& nth(NodeIt &i, int n) const { 101 112 if( DM::range_check && (n<0  n>int(length())) ) 102 113 fault("DirPath::nth: index out of range"); 103 return i=It(*this, n); 114 return i=NodeIt(*this, n); 115 } 116 117 /// \brief Initializes edge iterator to point to the edge of a given index. 118 EdgeIt& nth(EdgeIt &i, int n) const { 119 if( DM::range_check && (n<0  n>=int(length())) ) 120 fault("DirPath::nth: index out of range"); 121 return i=EdgeIt(*this, n); 104 122 } 105 123 106 124 /// Checks validity of a node or edge iterator. 107 125 template<typename It> 108 bool valid(const It &i) const { return i.valid(); } 126 static 127 bool valid(const It &i) { return i.valid(); } 109 128 110 129 /// Steps the given node or edge iterator. 111 130 template<typename It> 112 It& next(It &e) const { 131 static 132 It& next(It &e) { 113 133 if( DM::range_check && !e.valid() ) 114 134 fault("DirPath::next() on invalid iterator"); … … 119 139 /// given edge iterator. 120 140 NodeIt head(const EdgeIt& e) const { 141 if( DM::range_check && !e.valid() ) 142 fault("DirPath::head() on invalid iterator"); 121 143 return NodeIt(*this, e.idx+1); 122 144 } … … 125 147 /// given edge iterator. 126 148 NodeIt tail(const EdgeIt& e) const { 149 if( DM::range_check && !e.valid() ) 150 fault("DirPath::tail() on invalid iterator"); 127 151 return NodeIt(*this, e.idx); 128 152 } … … 171 195 bool valid() const { return idx!=1; } 172 196 173 operator const Graph Edge& () const {197 operator const GraphNode& () const { 174 198 if(idx >= p>length()) 175 199 return p>to(); … … 198 222 * 199 223 * You can push new edges to the front and to the back of the path in 200 * arbitrary order the you cancommit these changes to the graph.224 * arbitrary order then you should commit these changes to the graph. 201 225 * 202 226 * Fundamentally, for most "Paths" (classes fulfilling the … … 216 240 Builder(DirPath &_P) : P(_P) {} 217 241 218 /// Sets the firstnode of the path.242 /// Sets the starting node of the path. 219 243 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 &) {} 231 244 /// Sets the starting node of the path. Edge added to the path 245 /// afterwards have to be incident to this node. 246 /// It should be called iff the path is empty and before any call to 247 /// \ref pushFront() or \ref pushBack() 248 void setStart(const GraphNode &) {} 249 232 250 ///Push a new edge to the front of the path 233 251 234 252 ///Push a new edge to the front of the path. 235 ///\sa set To253 ///\sa setStart 236 254 void pushFront(const GraphEdge& e) { 237 255 if( DM::consistensy_check && !empty() && P.gr>head(e)!=from() ) { … … 244 262 245 263 ///Push a new edge to the back of the path. 246 ///\sa set From264 ///\sa setStart 247 265 void pushBack(const GraphEdge& e) { 248 266 if( DM::consistensy_check && !empty() && P.gr>tail(e)!=to() ) { … … 266 284 } 267 285 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(); } 286 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 287 // Hogy kenyelmes egy ilyet hasznalni? 288 void reserve(size_t r) { 289 front.reserve(r); 290 back.reserve(r); 291 } 292 293 private: 294 bool empty() { 295 return front.empty() && back.empty() && P.empty(); 296 } 297 298 GraphNode from() const { 299 if( ! front.empty() ) 300 return P.gr>tail(front[front.size()1]); 301 else if( ! P.empty() ) 302 return P.gr>tail(P.edges[0]); 303 else if( ! back.empty() ) 304 return P.gr>tail(back[0]); 305 else 306 return INVALID; 307 } 308 GraphNode to() const { 309 if( ! back.empty() ) 310 return P.gr>head(back[back.size()1]); 311 else if( ! P.empty() ) 312 return P.gr>head(P.edges[P.length()1]); 313 else if( ! front.empty() ) 314 return P.gr>head(front[0]); 315 else 316 return INVALID; 317 } 318 319 }; 320 321 }; 322 323 324 325 326 327 328 329 330 331 332 /**********************************************************************/ 333 334 335 //! \brief A structure for representing undirected path in a graph. 336 //! 337 //! A structure for representing undirected path in a graph. Ie. this is 338 //! a path in a \e directed graph but the edges should not be directed 339 //! forward. 340 //! 341 //! \param Graph The graph type in which the path is. 342 //! \param DM DebugMode, defaults to DefaultDebugMode. 343 //! 344 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 345 //! and \c EdgeIt with the same usage. These types converts to the \c Node 346 //! and \c Edge of the original graph. 347 //! 348 //! \todo Thoroughfully check all the range and consistency tests. 349 template<typename Graph, typename DM = DefaultDebugMode> 350 class UndirPath { 351 public: 352 typedef typename Graph::Edge GraphEdge; 353 typedef typename Graph::Node GraphNode; 354 class NodeIt; 355 class EdgeIt; 356 357 protected: 358 const Graph *gr; 359 typedef std::vector<GraphEdge> Container; 360 Container edges; 361 362 public: 363 364 /// \param _G The graph in which the path is. 365 /// 366 UndirPath(const Graph &_G) : gr(&_G) {} 367 368 /// \brief Subpath constructor. 369 /// 370 /// Subpath defined by two nodes. 371 /// \warning It is an error if the two edges are not in order! 372 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) { 373 if( DM::range_check && (!a.valid()  !b.valid) ) { 374 // FIXME: this check should be more elaborate... 375 fault("UndirPath, subpath ctor: invalid bounding nodes"); 376 } 377 gr = P.gr; 378 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 379 } 380 381 /// \brief Subpath constructor. 382 /// 383 /// Subpath defined by two edges. Contains edges in [a,b) 384 /// \warning It is an error if the two edges are not in order! 385 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) { 386 if( DM::range_check && (!a.valid()  !b.valid) ) { 387 // FIXME: this check should be more elaborate... 388 fault("UndirPath, subpath ctor: invalid bounding nodes"); 389 } 390 gr = P.gr; 391 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 392 } 393 394 /// Length of the path. 395 size_t length() const { return edges.size(); } 396 /// Returns whether the path is empty. 397 bool empty() const { return edges.empty(); } 398 399 /// Resets the path to an empty path. 400 void clear() { edges.clear(); } 401 402 /// \brief Starting point of the path. 403 /// 404 /// Starting point of the path. 405 /// Returns INVALID if the path is empty. 406 GraphNode from() const { 407 return empty() ? INVALID : gr>tail(edges[0]); 408 } 409 /// \brief End point of the path. 410 /// 411 /// End point of the path. 412 /// Returns INVALID if the path is empty. 413 GraphNode to() const { 414 return empty() ? INVALID : gr>head(edges[length()1]); 415 } 416 417 /// \brief Initializes node or edge iterator to point to the first 418 /// node or edge. 419 /// 420 /// \sa nth 421 template<typename It> 422 It& first(It &i) const { return i=It(*this); } 423 424 /// \brief Initializes node iterator to point to the node of a given index. 425 NodeIt& nth(NodeIt &i, int n) const { 426 if( DM::range_check && (n<0  n>int(length())) ) 427 fault("UndirPath::nth: index out of range"); 428 return i=NodeIt(*this, n); 429 } 430 431 /// \brief Initializes edge iterator to point to the edge of a given index. 432 EdgeIt& nth(EdgeIt &i, int n) const { 433 if( DM::range_check && (n<0  n>=int(length())) ) 434 fault("UndirPath::nth: index out of range"); 435 return i=EdgeIt(*this, n); 436 } 437 438 /// Checks validity of a node or edge iterator. 439 template<typename It> 440 static 441 bool valid(const It &i) { return i.valid(); } 442 443 /// Steps the given node or edge iterator. 444 template<typename It> 445 static 446 It& next(It &e) { 447 if( DM::range_check && !e.valid() ) 448 fault("UndirPath::next() on invalid iterator"); 449 return ++e; 450 } 451 452 /// \brief Returns node iterator pointing to the head node of the 453 /// given edge iterator. 454 NodeIt head(const EdgeIt& e) const { 455 if( DM::range_check && !e.valid() ) 456 fault("UndirPath::head() on invalid iterator"); 457 return NodeIt(*this, e.idx+1); 458 } 459 460 /// \brief Returns node iterator pointing to the tail node of the 461 /// given edge iterator. 462 NodeIt tail(const EdgeIt& e) const { 463 if( DM::range_check && !e.valid() ) 464 fault("UndirPath::tail() on invalid iterator"); 465 return NodeIt(*this, e.idx); 466 } 467 468 469 /*** Iterator classes ***/ 470 class EdgeIt { 471 friend class UndirPath; 472 473 int idx; 474 const UndirPath *p; 475 public: 476 EdgeIt() {} 477 EdgeIt(Invalid) : idx(1), p(0) {} 478 EdgeIt(const UndirPath &_p, int _idx = 0) : 479 idx(_idx), p(&_p) { validate(); } 480 481 bool valid() const { return idx!=1; } 482 483 operator GraphEdge () const { 484 return valid() ? p>edges[idx] : INVALID; 485 } 486 EdgeIt& operator++() { ++idx; validate(); return *this; } 487 488 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 489 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 490 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 491 492 private: 493 // FIXME: comparison between signed and unsigned... 494 // Jo ez igy? Vagy esetleg legyen a length() int? 495 void validate() { if( size_t(idx) >= p>length() ) idx=1; } 496 }; 497 498 class NodeIt { 499 friend class UndirPath; 500 501 int idx; 502 const UndirPath *p; 503 public: 504 NodeIt() {} 505 NodeIt(Invalid) : idx(1), p(0) {} 506 NodeIt(const UndirPath &_p, int _idx = 0) : 507 idx(_idx), p(&_p) { validate(); } 508 509 bool valid() const { return idx!=1; } 510 511 operator const GraphNode& () const { 512 if(idx >= p>length()) 513 return p>to(); 514 else if(idx >= 0) 515 return p>gr>tail(p>edges[idx]); 516 else 517 return INVALID; 518 } 519 NodeIt& operator++() { ++idx; validate(); return *this; } 520 521 bool operator==(const NodeIt& e) const { return idx==e.idx; } 522 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 523 bool operator<(const NodeIt& e) const { return idx<e.idx; } 524 525 private: 526 void validate() { if( size_t(idx) > p>length() ) idx=1; } 527 }; 528 529 friend class Builder; 530 531 /** 532 * \brief Class to build paths 533 * 534 * \ingroup datas 535 * This class is used to fill a path with edges. 536 * 537 * You can push new edges to the front and to the back of the path in 538 * arbitrary order then you should commit these changes to the graph. 539 * 540 * Fundamentally, for most "Paths" (classes fulfilling the 541 * PathConcept) while the builder is active (after the first modifying 542 * operation and until the commit()) the original Path is in a 543 * "transitional" state (operations ot it have undefined result). But 544 * in the case of UndirPath the original path is unchanged until the 545 * commit. However we don't recomend that you use this feature. 546 */ 547 class Builder { 548 UndirPath &P; 549 Container front, back; 550 551 public: 552 ///\param _P the path you want to fill in. 553 /// 554 Builder(UndirPath &_P) : P(_P) {} 555 556 /// Sets the starting node of the path. 557 558 /// Sets the starting node of the path. Edge added to the path 559 /// afterwards have to be incident to this node. 560 /// It should be called iff the path is empty and before any call to 561 /// \ref pushFront() or \ref pushBack() 562 void setStart(const GraphNode &) {} 563 564 ///Push a new edge to the front of the path 565 566 ///Push a new edge to the front of the path. 567 ///\sa setStart 568 void pushFront(const GraphEdge& e) { 569 if( DM::consistensy_check && !empty() && P.gr>head(e)!=from() ) { 570 fault("UndirPath::Builder::pushFront: nonincident edge"); 571 } 572 front.push_back(e); 573 } 574 575 ///Push a new edge to the back of the path 576 577 ///Push a new edge to the back of the path. 578 ///\sa setStart 579 void pushBack(const GraphEdge& e) { 580 if( DM::consistensy_check && !empty() && P.gr>tail(e)!=to() ) { 581 fault("UndirPath::Builder::pushBack: nonincident edge"); 582 } 583 back.push_back(e); 584 } 585 586 ///Commit the changes to the path. 587 void commit() { 588 if( !(front.empty() && back.empty()) ) { 589 Container tmp; 590 tmp.reserve(front.size()+back.size()+P.length()); 591 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 592 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); 593 tmp.insert(tmp.end(), back.begin(), back.end()); 594 P.edges.swap(tmp); 595 front.clear(); 596 back.clear(); 597 } 598 } 275 599 276 600 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
Note: See TracChangeset
for help on using the changeset viewer.