alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/path.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, 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. hegyi@819: alpar@921: #ifndef LEMON_PATH_H alpar@921: #define LEMON_PATH_H hegyi@819: hegyi@819: #include hegyi@819: #include hegyi@819: #include hegyi@819: alpar@921: #include 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 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 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. 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. hegyi@831: GraphNode tail() const { hegyi@819: return empty() ? INVALID : gr->tail(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. hegyi@831: GraphNode head() const { hegyi@819: return empty() ? INVALID : gr->head(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 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: /// \brief Returns node iterator pointing to the head node of the hegyi@819: /// given edge iterator. hegyi@819: NodeIt head(const EdgeIt& e) const { hegyi@819: return NodeIt(*this, e.idx+1); hegyi@819: } hegyi@819: hegyi@819: /// \brief Returns node iterator pointing to the tail node of the hegyi@819: /// given edge iterator. hegyi@819: NodeIt tail(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: * \ingroup paths 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= 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: * \ingroup paths 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()) hegyi@831: return p->head(); hegyi@819: else if(idx >= 0) hegyi@819: return p->gr->tail(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 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: * \ingroup paths 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: hegyi@819: ///\param _P the path you want to fill in. hegyi@819: /// hegyi@819: 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: hegyi@831: GraphNode tail() const { hegyi@819: if( ! front.empty() ) hegyi@819: return P.gr->tail(front[front.size()-1]); hegyi@819: else if( ! P.empty() ) hegyi@819: return P.gr->tail(P.edges[0]); hegyi@819: else if( ! back.empty() ) hegyi@819: return P.gr->tail(back[0]); hegyi@819: else hegyi@819: return INVALID; hegyi@819: } hegyi@831: GraphNode head() const { hegyi@819: if( ! back.empty() ) hegyi@819: return P.gr->head(back[back.size()-1]); hegyi@819: else if( ! P.empty() ) hegyi@819: return P.gr->head(P.edges[P.length()-1]); hegyi@819: else if( ! front.empty() ) hegyi@819: return P.gr->head(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. hegyi@831: template hegyi@819: class UndirPath { 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 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: UndirPath(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: UndirPath(const UndirPath &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: UndirPath(const UndirPath &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. hegyi@831: GraphNode tail() const { hegyi@819: return empty() ? INVALID : gr->tail(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. hegyi@831: GraphNode head() const { hegyi@819: return empty() ? INVALID : gr->head(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 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 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 hegyi@819: static hegyi@819: It& next(It &e) { hegyi@819: return ++e; hegyi@819: } hegyi@819: hegyi@819: /// \brief Returns node iterator pointing to the head node of the hegyi@819: /// given edge iterator. hegyi@819: NodeIt head(const EdgeIt& e) const { hegyi@819: return NodeIt(*this, e.idx+1); hegyi@819: } hegyi@819: hegyi@819: /// \brief Returns node iterator pointing to the tail node of the hegyi@819: /// given edge iterator. hegyi@819: NodeIt tail(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: * \ingroup paths 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 { hegyi@819: friend class UndirPath; hegyi@819: hegyi@819: int idx; hegyi@819: const UndirPath *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 UndirPath &_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= 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: * \ingroup paths 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 { hegyi@819: friend class UndirPath; hegyi@819: hegyi@819: int idx; hegyi@819: const UndirPath *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 UndirPath &_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()) hegyi@831: return p->head(); hegyi@819: else if(idx >= 0) hegyi@819: return p->gr->tail(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 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: * \ingroup paths 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 hegyi@819: * in the case of UndirPath 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 { hegyi@819: UndirPath &P; hegyi@819: Container front, back; hegyi@819: hegyi@819: public: hegyi@819: ///\param _P the path you want to fill in. hegyi@819: /// hegyi@819: Builder(UndirPath &_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: hegyi@831: GraphNode tail() const { hegyi@819: if( ! front.empty() ) hegyi@819: return P.gr->tail(front[front.size()-1]); hegyi@819: else if( ! P.empty() ) hegyi@819: return P.gr->tail(P.edges[0]); hegyi@819: else if( ! back.empty() ) hegyi@819: return P.gr->tail(back[0]); hegyi@819: else hegyi@819: return INVALID; hegyi@819: } hegyi@831: GraphNode head() const { hegyi@819: if( ! back.empty() ) hegyi@819: return P.gr->head(back[back.size()-1]); hegyi@819: else if( ! P.empty() ) hegyi@819: return P.gr->head(P.edges[P.length()-1]); hegyi@819: else if( ! front.empty() ) hegyi@819: return P.gr->head(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