383 //! and \c Edge of the original graph. |
383 //! and \c Edge of the original graph. |
384 //! |
384 //! |
385 //! \todo Thoroughfully check all the range and consistency tests. |
385 //! \todo Thoroughfully check all the range and consistency tests. |
386 /// \todo May we need just path for undirected graph instead of this. |
386 /// \todo May we need just path for undirected graph instead of this. |
387 template<typename Graph> |
387 template<typename Graph> |
388 class UndirPath { |
388 class UPath { |
389 public: |
389 public: |
390 /// Edge type of the underlying graph. |
390 /// Edge type of the underlying graph. |
391 typedef typename Graph::Edge GraphEdge; |
391 typedef typename Graph::Edge GraphEdge; |
392 /// Node type of the underlying graph. |
392 /// Node type of the underlying graph. |
393 typedef typename Graph::Node GraphNode; |
393 typedef typename Graph::Node GraphNode; |
401 |
401 |
402 public: |
402 public: |
403 |
403 |
404 /// \param _G The graph in which the path is. |
404 /// \param _G The graph in which the path is. |
405 /// |
405 /// |
406 UndirPath(const Graph &_G) : gr(&_G) {} |
406 UPath(const Graph &_G) : gr(&_G) {} |
407 |
407 |
408 /// \brief Subpath constructor. |
408 /// \brief Subpath constructor. |
409 /// |
409 /// |
410 /// Subpath defined by two nodes. |
410 /// Subpath defined by two nodes. |
411 /// \warning It is an error if the two edges are not in order! |
411 /// \warning It is an error if the two edges are not in order! |
412 UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) { |
412 UPath(const UPath &P, const NodeIt &a, const NodeIt &b) { |
413 gr = P.gr; |
413 gr = P.gr; |
414 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
414 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
415 } |
415 } |
416 |
416 |
417 /// \brief Subpath constructor. |
417 /// \brief Subpath constructor. |
418 /// |
418 /// |
419 /// Subpath defined by two edges. Contains edges in [a,b) |
419 /// Subpath defined by two edges. Contains edges in [a,b) |
420 /// \warning It is an error if the two edges are not in order! |
420 /// \warning It is an error if the two edges are not in order! |
421 UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) { |
421 UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) { |
422 gr = P.gr; |
422 gr = P.gr; |
423 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
423 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); |
424 } |
424 } |
425 |
425 |
426 /// Length of the path. |
426 /// Length of the path. |
498 * |
498 * |
499 * \todo Its interface differs from the standard edge iterator. |
499 * \todo Its interface differs from the standard edge iterator. |
500 * Yes, it shouldn't. |
500 * Yes, it shouldn't. |
501 */ |
501 */ |
502 class EdgeIt { |
502 class EdgeIt { |
503 friend class UndirPath; |
503 friend class UPath; |
504 |
504 |
505 int idx; |
505 int idx; |
506 const UndirPath *p; |
506 const UPath *p; |
507 public: |
507 public: |
508 /// Default constructor |
508 /// Default constructor |
509 EdgeIt() {} |
509 EdgeIt() {} |
510 /// Invalid constructor |
510 /// Invalid constructor |
511 EdgeIt(Invalid) : idx(-1), p(0) {} |
511 EdgeIt(Invalid) : idx(-1), p(0) {} |
512 /// Constructor with starting point |
512 /// Constructor with starting point |
513 EdgeIt(const UndirPath &_p, int _idx = 0) : |
513 EdgeIt(const UPath &_p, int _idx = 0) : |
514 idx(_idx), p(&_p) { validate(); } |
514 idx(_idx), p(&_p) { validate(); } |
515 |
515 |
516 ///Validity check |
516 ///Validity check |
517 bool valid() const { return idx!=-1; } |
517 bool valid() const { return idx!=-1; } |
518 |
518 |
545 * |
545 * |
546 * \todo Its interface differs from the standard node iterator. |
546 * \todo Its interface differs from the standard node iterator. |
547 * Yes, it shouldn't. |
547 * Yes, it shouldn't. |
548 */ |
548 */ |
549 class NodeIt { |
549 class NodeIt { |
550 friend class UndirPath; |
550 friend class UPath; |
551 |
551 |
552 int idx; |
552 int idx; |
553 const UndirPath *p; |
553 const UPath *p; |
554 public: |
554 public: |
555 /// Default constructor |
555 /// Default constructor |
556 NodeIt() {} |
556 NodeIt() {} |
557 /// Invalid constructor |
557 /// Invalid constructor |
558 NodeIt(Invalid) : idx(-1), p(0) {} |
558 NodeIt(Invalid) : idx(-1), p(0) {} |
559 /// Constructor with starting point |
559 /// Constructor with starting point |
560 NodeIt(const UndirPath &_p, int _idx = 0) : |
560 NodeIt(const UPath &_p, int _idx = 0) : |
561 idx(_idx), p(&_p) { validate(); } |
561 idx(_idx), p(&_p) { validate(); } |
562 |
562 |
563 ///Validity check |
563 ///Validity check |
564 bool valid() const { return idx!=-1; } |
564 bool valid() const { return idx!=-1; } |
565 |
565 |
598 * |
598 * |
599 * Fundamentally, for most "Paths" (classes fulfilling the |
599 * Fundamentally, for most "Paths" (classes fulfilling the |
600 * PathConcept) while the builder is active (after the first modifying |
600 * PathConcept) while the builder is active (after the first modifying |
601 * operation and until the commit()) the original Path is in a |
601 * operation and until the commit()) the original Path is in a |
602 * "transitional" state (operations ot it have undefined result). But |
602 * "transitional" state (operations ot it have undefined result). But |
603 * in the case of UndirPath the original path is unchanged until the |
603 * in the case of UPath the original path is unchanged until the |
604 * commit. However we don't recomend that you use this feature. |
604 * commit. However we don't recomend that you use this feature. |
605 */ |
605 */ |
606 class Builder { |
606 class Builder { |
607 UndirPath &P; |
607 UPath &P; |
608 Container front, back; |
608 Container front, back; |
609 |
609 |
610 public: |
610 public: |
611 ///\param _p the path you want to fill in. |
611 ///\param _p the path you want to fill in. |
612 /// |
612 /// |
613 Builder(UndirPath &_p) : P(_p) {} |
613 Builder(UPath &_p) : P(_p) {} |
614 |
614 |
615 /// Sets the starting node of the path. |
615 /// Sets the starting node of the path. |
616 |
616 |
617 /// Sets the starting node of the path. Edge added to the path |
617 /// Sets the starting node of the path. Edge added to the path |
618 /// afterwards have to be incident to this node. |
618 /// afterwards have to be incident to this node. |