alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
hegyi@819: 
hegyi@819: /**
hegyi@819: @defgroup paths Path Structures
hegyi@819: @ingroup datas
alpar@921: \brief Path structures implemented in LEMON.
hegyi@819: 
alpar@921: LEMON provides flexible data structures
hegyi@819: to work with paths.
hegyi@819: 
hegyi@819: All of them have the same interface, especially they can be built or extended
hegyi@819: using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
hegyi@819: algorithm to store its result in any kind of path structure.
hegyi@819: 
klao@959: \sa lemon::concept::Path
hegyi@819: 
hegyi@819: */
hegyi@819: 
hegyi@819: ///\ingroup paths
hegyi@819: ///\file
hegyi@819: ///\brief Classes for representing paths in graphs.
alpar@1151: ///
alpar@1151: ///\todo Iterators have obsolete style
hegyi@819: 
alpar@921: #ifndef LEMON_PATH_H
alpar@921: #define LEMON_PATH_H
hegyi@819: 
hegyi@819: #include <deque>
hegyi@819: #include <vector>
hegyi@819: #include <algorithm>
hegyi@819: 
alpar@921: #include <lemon/invalid.h>
hegyi@819: 
alpar@921: namespace lemon {
hegyi@819: 
hegyi@819:   /// \addtogroup paths
hegyi@819:   /// @{
hegyi@819: 
hegyi@819: 
hegyi@819:   //! \brief A structure for representing directed paths in a graph.
hegyi@819:   //!
hegyi@819:   //! A structure for representing directed path in a graph.
hegyi@819:   //! \param Graph The graph type in which the path is.
hegyi@819:   //! \param DM DebugMode, defaults to DefaultDebugMode.
hegyi@837:   //!
hegyi@819:   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
hegyi@819:   //! and \c EdgeIt with the same usage. These types converts to the \c Node
hegyi@819:   //! and \c Edge of the original graph.
hegyi@819:   //!
hegyi@819:   //! \todo Thoroughfully check all the range and consistency tests.
hegyi@831:   template<typename Graph>
hegyi@819:   class DirPath {
hegyi@819:   public:
hegyi@819:     /// Edge type of the underlying graph.
hegyi@837:     typedef typename Graph::Edge GraphEdge;
hegyi@819:     /// Node type of the underlying graph.
hegyi@819:     typedef typename Graph::Node GraphNode;
hegyi@819:     class NodeIt;
hegyi@819:     class EdgeIt;
hegyi@819: 
hegyi@819:   protected:
hegyi@819:     const Graph *gr;
hegyi@819:     typedef std::vector<GraphEdge> Container;
hegyi@819:     Container edges;
hegyi@819: 
hegyi@819:   public:
hegyi@819: 
hegyi@819:     /// \param _G The graph in which the path is.
hegyi@819:     ///
hegyi@819:     DirPath(const Graph &_G) : gr(&_G) {}
hegyi@819: 
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two nodes.
hegyi@819:     /// \warning It is an error if the two edges are not in order!
hegyi@819:     DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
hegyi@819:       gr = P.gr;
hegyi@819:       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two edges. Contains edges in [a,b)
hegyi@819:     /// \warning It is an error if the two edges are not in order!
hegyi@819:     DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
hegyi@819:       gr = P.gr;
hegyi@819:       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// Length of the path.
alpar@1282:     int length() const { return edges.size(); }
hegyi@819:     /// Returns whether the path is empty.
hegyi@819:     bool empty() const { return edges.empty(); }
hegyi@819: 
hegyi@819:     /// Resets the path to an empty path.
hegyi@819:     void clear() { edges.clear(); }
hegyi@819: 
hegyi@819:     /// \brief Starting point of the path.
hegyi@819:     ///
hegyi@819:     /// Starting point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
alpar@986:     GraphNode source() const {
alpar@986:       return empty() ? INVALID : gr->source(edges[0]);
hegyi@819:     }
hegyi@819:     /// \brief End point of the path.
hegyi@819:     ///
hegyi@819:     /// End point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
alpar@986:     GraphNode target() const {
alpar@986:       return empty() ? INVALID : gr->target(edges[length()-1]);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Initializes node or edge iterator to point to the first
hegyi@819:     /// node or edge.
hegyi@819:     ///
hegyi@819:     /// \sa nth
hegyi@819:     template<typename It>
hegyi@819:     It& first(It &i) const { return i=It(*this); }
hegyi@819: 
hegyi@819:     /// \brief Initializes node iterator to point to the node of a given index.
hegyi@819:     NodeIt& nth(NodeIt &i, int n) const {
hegyi@819:       return i=NodeIt(*this, n);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Initializes edge iterator to point to the edge of a given index.
hegyi@819:     EdgeIt& nth(EdgeIt &i, int n) const {
hegyi@819:       return i=EdgeIt(*this, n);
hegyi@819:     }
hegyi@819: 
alpar@986:     /// \brief Returns node iterator pointing to the target node of the
hegyi@819:     /// given edge iterator.
alpar@986:     NodeIt target(const EdgeIt& e) const {
hegyi@819:       return NodeIt(*this, e.idx+1);
hegyi@819:     }
hegyi@819: 
alpar@986:     /// \brief Returns node iterator pointing to the source node of the
hegyi@819:     /// given edge iterator.
alpar@986:     NodeIt source(const EdgeIt& e) const {
hegyi@819:       return NodeIt(*this, e.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819: 
hegyi@819:     /* Iterator classes */
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Iterator class to iterate on the edges of the paths
hegyi@837:      *
hegyi@819:      * This class is used to iterate on the edges of the paths
hegyi@819:      *
hegyi@819:      * Of course it converts to Graph::Edge
hegyi@837:      *
hegyi@819:      */
hegyi@819:     class EdgeIt {
hegyi@819:       friend class DirPath;
hegyi@819: 
hegyi@819:       int idx;
hegyi@819:       const DirPath *p;
hegyi@819:     public:
hegyi@819:       /// Default constructor
hegyi@819:       EdgeIt() {}
hegyi@819:       /// Invalid constructor
hegyi@819:       EdgeIt(Invalid) : idx(-1), p(0) {}
hegyi@819:       /// Constructor with starting point
hegyi@819:       EdgeIt(const DirPath &_p, int _idx = 0) :
hegyi@819: 	idx(_idx), p(&_p) { validate(); }
hegyi@819: 
hegyi@819:       ///Validity check
hegyi@819:       bool valid() const { return idx!=-1; }
hegyi@819: 
hegyi@819:       ///Conversion to Graph::Edge
hegyi@819:       operator GraphEdge () const {
hegyi@819: 	return valid() ? p->edges[idx] : INVALID;
hegyi@819:       }
hegyi@819: 
hegyi@819:       /// Next edge
hegyi@819:       EdgeIt& operator++() { ++idx; validate(); return *this; }
hegyi@819: 
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
hegyi@819: 
hegyi@819:     private:
alpar@1282:       void validate() { if(idx >= p->length() ) idx=-1; }
hegyi@819:     };
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Iterator class to iterate on the nodes of the paths
hegyi@837:      *
hegyi@819:      * This class is used to iterate on the nodes of the paths
hegyi@819:      *
hegyi@819:      * Of course it converts to Graph::Node
hegyi@837:      *
hegyi@819:      */
hegyi@819:     class NodeIt {
hegyi@819:       friend class DirPath;
hegyi@819: 
hegyi@819:       int idx;
hegyi@819:       const DirPath *p;
hegyi@819:     public:
hegyi@819:       /// Default constructor
hegyi@819:       NodeIt() {}
hegyi@819:       /// Invalid constructor
hegyi@819:       NodeIt(Invalid) : idx(-1), p(0) {}
hegyi@819:       /// Constructor with starting point
hegyi@819:       NodeIt(const DirPath &_p, int _idx = 0) :
hegyi@819: 	idx(_idx), p(&_p) { validate(); }
hegyi@819: 
hegyi@819:       ///Validity check
hegyi@819:       bool valid() const { return idx!=-1; }
hegyi@819: 
hegyi@819:       ///Conversion to Graph::Node
hegyi@819:       operator const GraphNode& () const {
hegyi@819: 	if(idx >= p->length())
alpar@986: 	  return p->target();
hegyi@819: 	else if(idx >= 0)
alpar@986: 	  return p->gr->source(p->edges[idx]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
hegyi@819:       /// Next node
hegyi@819:       NodeIt& operator++() { ++idx; validate(); return *this; }
hegyi@819: 
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator==(const NodeIt& e) const { return idx==e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator<(const NodeIt& e) const { return idx<e.idx; }
hegyi@819: 
hegyi@819:     private:
alpar@1282:       void validate() { if(idx > p->length() ) idx=-1; }
hegyi@819:     };
hegyi@819: 
hegyi@837:     friend class Builder;
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Class to build paths
hegyi@837:      *
hegyi@819:      * This class is used to fill a path with edges.
hegyi@819:      *
hegyi@819:      * You can push new edges to the front and to the back of the path in
hegyi@819:      * arbitrary order then you should commit these changes to the graph.
hegyi@819:      *
hegyi@819:      * Fundamentally, for most "Paths" (classes fulfilling the
hegyi@819:      * PathConcept) while the builder is active (after the first modifying
hegyi@819:      * operation and until the commit()) the original Path is in a
hegyi@819:      * "transitional" state (operations on it have undefined result). But
hegyi@819:      * in the case of DirPath the original path remains unchanged until the
hegyi@819:      * commit. However we don't recomend that you use this feature.
hegyi@819:      */
hegyi@819:     class Builder {
hegyi@819:       DirPath &P;
hegyi@819:       Container front, back;
hegyi@819: 
hegyi@819:     public:
alpar@1228:       ///\param _p the path you want to fill in.
hegyi@819:       ///
alpar@1228:       Builder(DirPath &_p) : P(_p) {}
hegyi@819: 
hegyi@819:       /// Sets the starting node of the path.
hegyi@837: 
hegyi@819:       /// Sets the starting node of the path. Edge added to the path
hegyi@819:       /// afterwards have to be incident to this node.
alpar@900:       /// It should be called if and only if
alpar@900:       /// the path is empty and before any call to
hegyi@819:       /// \ref pushFront() or \ref pushBack()
hegyi@819:       void setStartNode(const GraphNode &) {}
hegyi@819: 
hegyi@819:       ///Push a new edge to the front of the path
hegyi@819: 
hegyi@819:       ///Push a new edge to the front of the path.
hegyi@819:       ///\sa setStartNode
hegyi@819:       void pushFront(const GraphEdge& e) {
hegyi@819: 	front.push_back(e);
hegyi@819:       }
hegyi@819: 
hegyi@819:       ///Push a new edge to the back of the path
hegyi@819: 
hegyi@819:       ///Push a new edge to the back of the path.
hegyi@819:       ///\sa setStartNode
hegyi@819:       void pushBack(const GraphEdge& e) {
hegyi@819: 	back.push_back(e);
hegyi@819:       }
hegyi@819: 
hegyi@819:       ///Commit the changes to the path.
hegyi@819:       void commit() {
hegyi@837: 	if( !front.empty() || !back.empty() ) {
hegyi@819: 	  Container tmp;
hegyi@819: 	  tmp.reserve(front.size()+back.size()+P.length());
hegyi@819: 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
hegyi@819: 	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
hegyi@819: 	  tmp.insert(tmp.end(), back.begin(), back.end());
hegyi@819: 	  P.edges.swap(tmp);
hegyi@819: 	  front.clear();
hegyi@819: 	  back.clear();
hegyi@819: 	}
hegyi@819:       }
hegyi@819: 
hegyi@819:       ///Reserve storage for the builder in advance.
hegyi@819: 
hegyi@837:       ///If you know a reasonable upper bound of the number of the edges
hegyi@837:       ///to add to the front, using this function you can speed up the building.
hegyi@819: 
hegyi@837:       void reserveFront(size_t r) {front.reserve(r);}
hegyi@837: 
hegyi@837:       ///Reserve storage for the builder in advance.
hegyi@837: 
hegyi@837:       ///If you know a reasonable upper bound of the number of the edges
hegyi@837:       ///to add to the back, using this function you can speed up the building.
hegyi@837: 
hegyi@837:       void reserveBack(size_t r) {back.reserve(r);}
hegyi@831: 
hegyi@819:     private:
hegyi@819:       bool empty() {
hegyi@819: 	return front.empty() && back.empty() && P.empty();
hegyi@819:       }
hegyi@819: 
alpar@986:       GraphNode source() const {
hegyi@819: 	if( ! front.empty() )
alpar@986: 	  return P.gr->source(front[front.size()-1]);
hegyi@819: 	else if( ! P.empty() )
alpar@986: 	  return P.gr->source(P.edges[0]);
hegyi@819: 	else if( ! back.empty() )
alpar@986: 	  return P.gr->source(back[0]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
alpar@986:       GraphNode target() const {
hegyi@819: 	if( ! back.empty() )
alpar@986: 	  return P.gr->target(back[back.size()-1]);
hegyi@819: 	else if( ! P.empty() )
alpar@986: 	  return P.gr->target(P.edges[P.length()-1]);
hegyi@819: 	else if( ! front.empty() )
alpar@986: 	  return P.gr->target(front[0]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
hegyi@819: 
hegyi@819:     };
hegyi@819: 
hegyi@819:   };
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819:   /**********************************************************************/
hegyi@819: 
hegyi@819: 
hegyi@819:   //! \brief A structure for representing undirected path in a graph.
hegyi@819:   //!
hegyi@819:   //! A structure for representing undirected path in a graph. Ie. this is
hegyi@819:   //! a path in a \e directed graph but the edges should not be directed
hegyi@819:   //! forward.
hegyi@819:   //!
hegyi@819:   //! \param Graph The graph type in which the path is.
hegyi@819:   //! \param DM DebugMode, defaults to DefaultDebugMode.
hegyi@837:   //!
hegyi@819:   //! In a sense, the path can be treated as a graph, for is has \c NodeIt
hegyi@819:   //! and \c EdgeIt with the same usage. These types converts to the \c Node
hegyi@819:   //! and \c Edge of the original graph.
hegyi@819:   //!
hegyi@819:   //! \todo Thoroughfully check all the range and consistency tests.
deba@1730:   /// \todo May we need just path for undirected graph instead of this.
hegyi@831:   template<typename Graph>
klao@1909:   class UPath {
hegyi@819:   public:
hegyi@819:     /// Edge type of the underlying graph.
hegyi@819:     typedef typename Graph::Edge GraphEdge;
hegyi@819:      /// Node type of the underlying graph.
hegyi@819:    typedef typename Graph::Node GraphNode;
hegyi@819:     class NodeIt;
hegyi@819:     class EdgeIt;
hegyi@819: 
hegyi@819:   protected:
hegyi@819:     const Graph *gr;
hegyi@819:     typedef std::vector<GraphEdge> Container;
hegyi@819:     Container edges;
hegyi@819: 
hegyi@819:   public:
hegyi@819: 
hegyi@819:     /// \param _G The graph in which the path is.
hegyi@819:     ///
klao@1909:     UPath(const Graph &_G) : gr(&_G) {}
hegyi@819: 
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two nodes.
hegyi@819:     /// \warning It is an error if the two edges are not in order!
klao@1909:     UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
hegyi@819:       gr = P.gr;
hegyi@819:       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Subpath constructor.
hegyi@819:     ///
hegyi@819:     /// Subpath defined by two edges. Contains edges in [a,b)
hegyi@819:     /// \warning It is an error if the two edges are not in order!
klao@1909:     UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
hegyi@819:       gr = P.gr;
hegyi@819:       edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// Length of the path.
hegyi@819:     size_t length() const { return edges.size(); }
hegyi@819:     /// Returns whether the path is empty.
hegyi@819:     bool empty() const { return edges.empty(); }
hegyi@819: 
hegyi@819:     /// Resets the path to an empty path.
hegyi@819:     void clear() { edges.clear(); }
hegyi@819: 
hegyi@819:     /// \brief Starting point of the path.
hegyi@819:     ///
hegyi@819:     /// Starting point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
alpar@986:     GraphNode source() const {
alpar@986:       return empty() ? INVALID : gr->source(edges[0]);
hegyi@819:     }
hegyi@819:     /// \brief End point of the path.
hegyi@819:     ///
hegyi@819:     /// End point of the path.
hegyi@819:     /// Returns INVALID if the path is empty.
alpar@986:     GraphNode target() const {
alpar@986:       return empty() ? INVALID : gr->target(edges[length()-1]);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Initializes node or edge iterator to point to the first
hegyi@819:     /// node or edge.
hegyi@819:     ///
hegyi@819:     /// \sa nth
hegyi@819:     template<typename It>
hegyi@819:     It& first(It &i) const { return i=It(*this); }
hegyi@819: 
hegyi@819:     /// \brief Initializes node iterator to point to the node of a given index.
hegyi@819:     NodeIt& nth(NodeIt &i, int n) const {
hegyi@819:       return i=NodeIt(*this, n);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// \brief Initializes edge iterator to point to the edge of a given index.
hegyi@819:     EdgeIt& nth(EdgeIt &i, int n) const {
hegyi@819:       return i=EdgeIt(*this, n);
hegyi@819:     }
hegyi@819: 
hegyi@819:     /// Checks validity of a node or edge iterator.
hegyi@819:     template<typename It>
hegyi@819:     static
hegyi@819:     bool valid(const It &i) { return i.valid(); }
hegyi@819: 
hegyi@819:     /// Steps the given node or edge iterator.
hegyi@819:     template<typename It>
hegyi@819:     static
hegyi@819:     It& next(It &e) {
hegyi@819:       return ++e;
hegyi@819:     }
hegyi@819: 
alpar@986:     /// \brief Returns node iterator pointing to the target node of the
hegyi@819:     /// given edge iterator.
alpar@986:     NodeIt target(const EdgeIt& e) const {
hegyi@819:       return NodeIt(*this, e.idx+1);
hegyi@819:     }
hegyi@819: 
alpar@986:     /// \brief Returns node iterator pointing to the source node of the
hegyi@819:     /// given edge iterator.
alpar@986:     NodeIt source(const EdgeIt& e) const {
hegyi@819:       return NodeIt(*this, e.idx);
hegyi@819:     }
hegyi@819: 
hegyi@819: 
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Iterator class to iterate on the edges of the paths
hegyi@837:      *
hegyi@819:      * This class is used to iterate on the edges of the paths
hegyi@819:      *
hegyi@819:      * Of course it converts to Graph::Edge
hegyi@837:      *
hegyi@819:      * \todo Its interface differs from the standard edge iterator.
hegyi@819:      * Yes, it shouldn't.
hegyi@819:      */
hegyi@819:     class EdgeIt {
klao@1909:       friend class UPath;
hegyi@819: 
hegyi@819:       int idx;
klao@1909:       const UPath *p;
hegyi@819:     public:
hegyi@819:       /// Default constructor
hegyi@819:       EdgeIt() {}
hegyi@819:       /// Invalid constructor
hegyi@819:       EdgeIt(Invalid) : idx(-1), p(0) {}
hegyi@819:       /// Constructor with starting point
klao@1909:       EdgeIt(const UPath &_p, int _idx = 0) :
hegyi@819: 	idx(_idx), p(&_p) { validate(); }
hegyi@819: 
hegyi@819:       ///Validity check
hegyi@819:       bool valid() const { return idx!=-1; }
hegyi@819: 
hegyi@819:       ///Conversion to Graph::Edge
hegyi@819:       operator GraphEdge () const {
hegyi@819: 	return valid() ? p->edges[idx] : INVALID;
hegyi@819:       }
hegyi@819:       /// Next edge
hegyi@819:      EdgeIt& operator++() { ++idx; validate(); return *this; }
hegyi@819: 
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator==(const EdgeIt& e) const { return idx==e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator<(const EdgeIt& e) const { return idx<e.idx; }
hegyi@819: 
hegyi@819:     private:
hegyi@819:       // FIXME: comparison between signed and unsigned...
hegyi@819:       // Jo ez igy? Vagy esetleg legyen a length() int?
hegyi@819:       void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
hegyi@819:     };
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Iterator class to iterate on the nodes of the paths
hegyi@837:      *
hegyi@819:      * This class is used to iterate on the nodes of the paths
hegyi@819:      *
hegyi@819:      * Of course it converts to Graph::Node
hegyi@837:      *
hegyi@819:      * \todo Its interface differs from the standard node iterator.
hegyi@819:      * Yes, it shouldn't.
hegyi@819:      */
hegyi@819:     class NodeIt {
klao@1909:       friend class UPath;
hegyi@819: 
hegyi@819:       int idx;
klao@1909:       const UPath *p;
hegyi@819:     public:
hegyi@819:       /// Default constructor
hegyi@819:       NodeIt() {}
hegyi@819:       /// Invalid constructor
hegyi@819:       NodeIt(Invalid) : idx(-1), p(0) {}
hegyi@819:       /// Constructor with starting point
klao@1909:       NodeIt(const UPath &_p, int _idx = 0) :
hegyi@819: 	idx(_idx), p(&_p) { validate(); }
hegyi@819: 
hegyi@819:       ///Validity check
hegyi@819:       bool valid() const { return idx!=-1; }
hegyi@819: 
hegyi@819:       ///Conversion to Graph::Node
hegyi@819:       operator const GraphNode& () const {
hegyi@819: 	if(idx >= p->length())
alpar@986: 	  return p->target();
hegyi@819: 	else if(idx >= 0)
alpar@986: 	  return p->gr->source(p->edges[idx]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
hegyi@819:       /// Next node
hegyi@819:       NodeIt& operator++() { ++idx; validate(); return *this; }
hegyi@819: 
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator==(const NodeIt& e) const { return idx==e.idx; }
hegyi@819:       /// Comparison operator
hegyi@819:       bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
hegyi@819:        /// Comparison operator
hegyi@819:      bool operator<(const NodeIt& e) const { return idx<e.idx; }
hegyi@819: 
hegyi@819:     private:
hegyi@819:       void validate() { if( size_t(idx) > p->length() ) idx=-1; }
hegyi@819:     };
hegyi@819: 
hegyi@837:     friend class Builder;
hegyi@819: 
hegyi@819:     /**
hegyi@819:      * \brief Class to build paths
hegyi@837:      *
hegyi@819:      * This class is used to fill a path with edges.
hegyi@819:      *
hegyi@819:      * You can push new edges to the front and to the back of the path in
hegyi@819:      * arbitrary order then you should commit these changes to the graph.
hegyi@819:      *
hegyi@819:      * Fundamentally, for most "Paths" (classes fulfilling the
hegyi@819:      * PathConcept) while the builder is active (after the first modifying
hegyi@819:      * operation and until the commit()) the original Path is in a
hegyi@819:      * "transitional" state (operations ot it have undefined result). But
klao@1909:      * in the case of UPath the original path is unchanged until the
hegyi@819:      * commit. However we don't recomend that you use this feature.
hegyi@819:      */
hegyi@819:     class Builder {
klao@1909:       UPath &P;
hegyi@819:       Container front, back;
hegyi@819: 
hegyi@819:     public:
alpar@1228:       ///\param _p the path you want to fill in.
hegyi@819:       ///
klao@1909:       Builder(UPath &_p) : P(_p) {}
hegyi@819: 
hegyi@819:       /// Sets the starting node of the path.
hegyi@837: 
hegyi@819:       /// Sets the starting node of the path. Edge added to the path
hegyi@819:       /// afterwards have to be incident to this node.
alpar@900:       /// It should be called if and only if
alpar@900:       /// the path is empty and before any call to
hegyi@819:       /// \ref pushFront() or \ref pushBack()
hegyi@819:       void setStartNode(const GraphNode &) {}
hegyi@819: 
hegyi@819:       ///Push a new edge to the front of the path
hegyi@819: 
hegyi@819:       ///Push a new edge to the front of the path.
hegyi@819:       ///\sa setStartNode
hegyi@819:       void pushFront(const GraphEdge& e) {
hegyi@819: 	front.push_back(e);
hegyi@819:       }
hegyi@819: 
hegyi@819:       ///Push a new edge to the back of the path
hegyi@819: 
hegyi@819:       ///Push a new edge to the back of the path.
hegyi@819:       ///\sa setStartNode
hegyi@819:       void pushBack(const GraphEdge& e) {
hegyi@819: 	back.push_back(e);
hegyi@819:       }
hegyi@819: 
hegyi@819:       ///Commit the changes to the path.
hegyi@819:       void commit() {
hegyi@819: 	if( !(front.empty() && back.empty()) ) {
hegyi@819: 	  Container tmp;
hegyi@819: 	  tmp.reserve(front.size()+back.size()+P.length());
hegyi@819: 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
hegyi@819: 	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
hegyi@819: 	  tmp.insert(tmp.end(), back.begin(), back.end());
hegyi@819: 	  P.edges.swap(tmp);
hegyi@819: 	  front.clear();
hegyi@819: 	  back.clear();
hegyi@819: 	}
hegyi@819:       }
hegyi@819: 
hegyi@819: 
hegyi@819:       ///Reserve storage for the builder in advance.
hegyi@819: 
hegyi@837:       ///If you know a reasonable upper bound of the number of the edges
hegyi@837:       ///to add to the front, using this function you can speed up the building.
hegyi@819: 
hegyi@837:       void reserveFront(size_t r) {front.reserve(r);}
hegyi@837: 
hegyi@837:       ///Reserve storage for the builder in advance.
hegyi@837: 
hegyi@837:       ///If you know a reasonable upper bound of the number of the edges
hegyi@837:       ///to add to the back, using this function you can speed up the building.
hegyi@837: 
hegyi@837:       void reserveBack(size_t r) {back.reserve(r);}
hegyi@831: 
hegyi@819:     private:
hegyi@819:       bool empty() {
hegyi@819: 	return front.empty() && back.empty() && P.empty();
hegyi@819:       }
hegyi@819: 
alpar@986:       GraphNode source() const {
hegyi@819: 	if( ! front.empty() )
alpar@986: 	  return P.gr->source(front[front.size()-1]);
hegyi@819: 	else if( ! P.empty() )
alpar@986: 	  return P.gr->source(P.edges[0]);
hegyi@819: 	else if( ! back.empty() )
alpar@986: 	  return P.gr->source(back[0]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
alpar@986:       GraphNode target() const {
hegyi@819: 	if( ! back.empty() )
alpar@986: 	  return P.gr->target(back[back.size()-1]);
hegyi@819: 	else if( ! P.empty() )
alpar@986: 	  return P.gr->target(P.edges[P.length()-1]);
hegyi@819: 	else if( ! front.empty() )
alpar@986: 	  return P.gr->target(front[0]);
hegyi@819: 	else
hegyi@819: 	  return INVALID;
hegyi@819:       }
hegyi@819: 
hegyi@819:     };
hegyi@819: 
hegyi@819:   };
hegyi@819: 
hegyi@819: 
hegyi@819:   ///@}
hegyi@819: 
alpar@921: } // namespace lemon
hegyi@819: 
alpar@921: #endif // LEMON_PATH_H