diff -r 9c472eee236f -r 269a0dcee70b lemon/path.h --- a/lemon/path.h Tue Oct 17 10:42:19 2006 +0000 +++ b/lemon/path.h Tue Oct 17 10:50:57 2006 +0000 @@ -21,15 +21,14 @@ ///\file ///\brief Classes for representing paths in graphs. /// -///\todo Iterators have obsolete style #ifndef LEMON_PATH_H #define LEMON_PATH_H -#include #include #include +#include #include namespace lemon { @@ -42,7 +41,6 @@ //! //! A structure for representing directed path in a graph. //! \param Graph The graph type in which the path is. - //! \param DM DebugMode, defaults to DefaultDebugMode. //! //! In a sense, the path can be treated as a graph, for is has \c NodeIt //! and \c EdgeIt with the same usage. These types converts to the \c Node @@ -50,640 +48,383 @@ //! //! \todo Thoroughfully check all the range and consistency tests. template - class DirPath { + class Path { public: /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; + typedef typename Graph::Edge Edge; /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; + typedef typename Graph::Node Node; + class NodeIt; class EdgeIt; - protected: - const Graph *gr; - typedef std::vector Container; - Container edges; + struct PathError : public LogicError { + virtual const char* what() const throw() { + return "lemon::PathError"; + } + }; public: + /// \brief Constructor + /// + /// Constructor /// \param _G The graph in which the path is. - /// - DirPath(const Graph &_G) : gr(&_G) {} - + Path(const Graph &_graph) : graph(&_graph), start(INVALID) {} + /// \brief Subpath constructor. /// /// Subpath defined by two nodes. /// \warning It is an error if the two edges are not in order! - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); + Path(const Path &other, const NodeIt &a, const NodeIt &b) { + graph = other.graph; + start = a; + edges.insert(edges.end(), + other.edges.begin() + a.id, other.edges.begin() + b.id); } /// \brief Subpath constructor. /// /// Subpath defined by two edges. Contains edges in [a,b) /// \warning It is an error if the two edges are not in order! - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); + Path(const Path &other, const EdgeIt &a, const EdgeIt &b) { + graph = other.graph; + start = graph->source(a); + edges.insert(edges.end(), + other.edges.begin() + a.id, other.edges.begin() + b.id); } - /// Length of the path. + /// \brief Length of the path. + /// + /// The number of the edges in the path. It can be zero if the + /// path has only one node or it is empty. int length() const { return edges.size(); } - /// Returns whether the path is empty. - bool empty() const { return edges.empty(); } + /// \brief Returns whether the path is empty. + /// + /// Returns true when the path does not contain neither edge nor + /// node. + bool empty() const { return start == INVALID; } + + /// \brief Resets the path to an empty path. + /// /// Resets the path to an empty path. - void clear() { edges.clear(); } + void clear() { edges.clear(); start = INVALID; } /// \brief Starting point of the path. /// /// Starting point of the path. /// Returns INVALID if the path is empty. - GraphNode source() const { - return empty() ? INVALID : gr->source(edges[0]); + Node source() const { + return start; } /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. - GraphNode target() const { - return empty() ? INVALID : gr->target(edges[length()-1]); + Node target() const { + return length() == 0 ? start : graph->target(edges[length()-1]); } - /// \brief Initializes node or edge iterator to point to the first - /// node or edge. + /// \brief Gives back a node iterator to point to the node of a + /// given index. /// - /// \sa nth - template - It& first(It &i) const { return i=It(*this); } - - /// \brief Initializes node iterator to point to the node of a given index. - NodeIt& nth(NodeIt &i, int n) const { - return i=NodeIt(*this, n); + /// Gives back a node iterator to point to the node of a given + /// index. + /// \pre n should less or equal to \c length() + NodeIt nthNode(int n) const { + return NodeIt(*this, n); } - /// \brief Initializes edge iterator to point to the edge of a given index. - EdgeIt& nth(EdgeIt &i, int n) const { - return i=EdgeIt(*this, n); + /// \brief Gives back an edge iterator to point to the edge of a + /// given index. + /// + /// Gives back an edge iterator to point to the node of a given + /// index. + /// \pre n should less than \c length() + EdgeIt nthEdge(int n) const { + return EdgeIt(*this, n); + } + + /// \brief Returns node iterator pointing to the source node of the + /// given edge iterator. + /// + /// Returns node iterator pointing to the source node of the given + /// edge iterator. + NodeIt source(const EdgeIt& e) const { + return NodeIt(*this, e.id); } /// \brief Returns node iterator pointing to the target node of the /// given edge iterator. + /// + /// Returns node iterator pointing to the target node of the given + /// edge iterator. NodeIt target(const EdgeIt& e) const { - return NodeIt(*this, e.idx+1); + return NodeIt(*this, e.id + 1); } - /// \brief Returns node iterator pointing to the source node of the - /// given edge iterator. - NodeIt source(const EdgeIt& e) const { - return NodeIt(*this, e.idx); - } + /// \brief Iterator class to iterate on the nodes of the paths + /// + /// This class is used to iterate on the nodes of the paths + /// + /// Of course it converts to Graph::Node + class NodeIt { + friend class Path; + public: - /* Iterator classes */ + /// \brief Default constructor + /// + /// Default constructor + NodeIt() {} - /** - * \brief Iterator class to iterate on the edges of the paths - * - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - */ + /// \brief Invalid constructor + /// + /// Invalid constructor + NodeIt(Invalid) : id(-1), path(0) {} + + /// \brief Constructor with starting point + /// + /// Constructor with starting point + NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { + if (id > path->length()) id = -1; + } + + /// \brief Conversion to Graph::Node + /// + /// Conversion to Graph::Node + operator Node() const { + if (id > 0) { + return path->graph->target(path->edges[id - 1]); + } else if (id == 0) { + return path->start; + } else { + return INVALID; + } + } + + /// \brief Steps to the next node + /// + /// Steps to the next node + NodeIt& operator++() { + ++id; + if (id > path->length()) id = -1; + return *this; + } + + /// \brief Comparison operator + /// + /// Comparison operator + bool operator==(const NodeIt& n) const { return id == n.id; } + + /// \brief Comparison operator + /// + /// Comparison operator + bool operator!=(const NodeIt& n) const { return id != n.id; } + + /// \brief Comparison operator + /// + /// Comparison operator + bool operator<(const NodeIt& n) const { return id < n.id; } + + private: + int id; + const Path *path; + }; + + /// \brief Iterator class to iterate on the edges of the paths + /// + /// This class is used to iterate on the edges of the paths + /// Of course it converts to Graph::Edge class EdgeIt { - friend class DirPath; + friend class Path; + public: - int idx; - const DirPath *p; - public: + /// \brief Default constructor + /// /// Default constructor EdgeIt() {} + + /// \brief Invalid constructor + /// /// Invalid constructor - EdgeIt(Invalid) : idx(-1), p(0) {} + EdgeIt(Invalid) : id(-1), path(0) {} + + /// \brief Constructor with starting point + /// /// Constructor with starting point - EdgeIt(const DirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Edge - operator GraphEdge () const { - return valid() ? p->edges[idx] : INVALID; + EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { + if (id >= path->length()) id = -1; } - /// Next edge - EdgeIt& operator++() { ++idx; validate(); return *this; } + /// \brief Conversion to Graph::Edge + /// + /// Conversion to Graph::Edge + operator Edge() const { + return id != -1 ? path->edges[id] : INVALID; + } + /// \brief Steps to the next edge + /// + /// Steps to the next edge + EdgeIt& operator++() { + ++id; + if (id >= path->length()) id = -1; + return *this; + } + + /// \brief Comparison operator + /// /// Comparison operator - bool operator==(const EdgeIt& e) const { return idx==e.idx; } + bool operator==(const EdgeIt& e) const { return id == e.id; } + + /// \brief Comparison operator + /// /// Comparison operator - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } + bool operator!=(const EdgeIt& e) const { return id != e.id; } + + /// \brief Comparison operator + /// /// Comparison operator - bool operator<(const EdgeIt& e) const { return idx= p->length() ) idx=-1; } + + int id; + const Path *path; }; - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node - * - */ - class NodeIt { - friend class DirPath; + protected: - int idx; - const DirPath *p; - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - NodeIt(const DirPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } + const Graph *graph; - ///Validity check - bool valid() const { return idx!=-1; } + typedef std::vector Container; + Container edges; + Node start; - ///Conversion to Graph::Node - operator GraphNode () const { - if(idx >= p->length()) - return p->target(); - else if(idx >= 0) - return p->gr->source(p->edges[idx]); - else - return INVALID; - } - /// Next node - NodeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const NodeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const NodeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const NodeIt& e) const { return idx p->length() ) idx=-1; } - }; + public: friend class Builder; - /** - * \brief Class to build paths - * - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * Fundamentally, for most "Paths" (classes fulfilling the - * PathConcept) while the builder is active (after the first modifying - * operation and until the commit()) the original Path is in a - * "transitional" state (operations on it have undefined result). But - * in the case of DirPath the original path remains unchanged until the - * commit. However we don't recomend that you use this feature. - */ + /// \brief Class to build paths + /// + /// This class is used to fill a path with edges. + /// + /// You can push new edges to the front and to the back of the + /// path in arbitrary order then you should commit these changes + /// to the graph. + /// + /// Fundamentally, for most "Paths" (classes fulfilling the + /// PathConcept) while the builder is active (after the first + /// modifying operation and until the commit()) the original Path + /// is in a "transitional" state (operations on it have undefined + /// result). But in the case of Path the original path remains + /// unchanged until the commit. However we don't recomend that you + /// use this feature. class Builder { - DirPath &P; - Container front, back; + public: + /// \brief Constructor + /// + /// Constructor + /// \param _path the path you want to fill in. + Builder(Path &_path) : path(_path), start(INVALID) {} - public: - ///\param _p the path you want to fill in. + /// \brief Destructor /// - Builder(DirPath &_p) : P(_p) {} + /// Destructor + ~Builder() { + LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, + PathError()); + } - /// Sets the starting node of the path. + /// \brief Sets the starting node of the path. + /// + /// Sets the starting node of the path. Edge added to the path + /// afterwards have to be incident to this node. It should be + /// called if and only if the path is empty and before any call + /// to \ref pushFront() or \ref pushBack() + void setStartNode(const Node &_start) { + LEMON_ASSERT(path.empty() && start == INVALID, PathError()); + start = _start; + } - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// It should be called if and only if - /// the path is empty and before any call to - /// \ref pushFront() or \ref pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///\sa setStartNode - void pushFront(const GraphEdge& e) { + /// \brief Push a new edge to the front of the path + /// + /// Push a new edge to the front of the path. + /// \sa setStartNode + void pushFront(const Edge& e) { + LEMON_ASSERT(front.empty() || + (path.graph->source(front.back()) == + path.graph->target(e)), PathError()); + LEMON_ASSERT(path.empty() || + (path.source() == path.graph->target(e)), PathError()); + LEMON_ASSERT(!path.empty() || !front.empty() || + (start == path.graph->target(e)), PathError()); front.push_back(e); } - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///\sa setStartNode - void pushBack(const GraphEdge& e) { + /// \brief Push a new edge to the back of the path + /// + /// Push a new edge to the back of the path. + /// \sa setStartNode + void pushBack(const Edge& e) { + LEMON_ASSERT(back.empty() || + (path.graph->target(back.back()) == + path.graph->source(e)), PathError()); + LEMON_ASSERT(path.empty() || + (path.target() == path.graph->source(e)), PathError()); + LEMON_ASSERT(!path.empty() || !back.empty() || + (start == path.graph->source(e)), PathError()); back.push_back(e); } - ///Commit the changes to the path. + /// \brief Commit the changes to the path. + /// + /// Commit the changes to the path. void commit() { - if( !front.empty() || !back.empty() ) { + if( !front.empty() || !back.empty() || start != INVALID) { Container tmp; - tmp.reserve(front.size()+back.size()+P.length()); + tmp.reserve(front.size() + back.size() + path.length()); tmp.insert(tmp.end(), front.rbegin(), front.rend()); - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); + tmp.insert(tmp.end(), path.edges.begin(), path.edges.end()); tmp.insert(tmp.end(), back.begin(), back.end()); - P.edges.swap(tmp); + path.edges.swap(tmp); + if (!front.empty()) { + path.start = path.graph->source(front.back()); + } else { + path.start = start; + } + start = INVALID; front.clear(); back.clear(); } } - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the front, using this function you can speed up the building. - + /// \brief Reserve storage for the builder in advance. + /// + /// If you know a reasonable upper bound of the number of the + /// edges to add to the front, using this function you can speed + /// up the building. void reserveFront(size_t r) {front.reserve(r);} - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the back, using this function you can speed up the building. - + /// \brief Reserve storage for the builder in advance. + /// + /// If you know a reasonable upper bound of the number of the + /// edges to add to the back, using this function you can speed + /// up the building. void reserveBack(size_t r) {back.reserve(r);} private: - bool empty() { - return front.empty() && back.empty() && P.empty(); - } - GraphNode source() const { - if( ! front.empty() ) - return P.gr->source(front[front.size()-1]); - else if( ! P.empty() ) - return P.gr->source(P.edges[0]); - else if( ! back.empty() ) - return P.gr->source(back[0]); - else - return INVALID; - } - GraphNode target() const { - if( ! back.empty() ) - return P.gr->target(back[back.size()-1]); - else if( ! P.empty() ) - return P.gr->target(P.edges[P.length()-1]); - else if( ! front.empty() ) - return P.gr->target(front[0]); - else - return INVALID; - } + Path &path; + Container front, back; + Node start; }; }; - - - - - - - - - - /**********************************************************************/ - - - //! \brief A structure for representing undirected path in a graph. - //! - //! A structure for representing undirected path in a graph. Ie. this is - //! a path in a \e directed graph but the edges should not be directed - //! forward. - //! - //! \param Graph The graph type in which the path is. - //! \param DM DebugMode, defaults to DefaultDebugMode. - //! - //! In a sense, the path can be treated as a graph, for is has \c NodeIt - //! and \c EdgeIt with the same usage. These types converts to the \c Node - //! and \c Edge of the original graph. - //! - //! \todo Thoroughfully check all the range and consistency tests. - /// \todo May we need just path for undirected graph instead of this. - template - class UPath { - public: - /// Edge type of the underlying graph. - typedef typename Graph::Edge GraphEdge; - /// Node type of the underlying graph. - typedef typename Graph::Node GraphNode; - class NodeIt; - class EdgeIt; - - protected: - const Graph *gr; - typedef std::vector Container; - Container edges; - - public: - - /// \param _G The graph in which the path is. - /// - UPath(const Graph &_G) : gr(&_G) {} - - /// \brief Subpath constructor. - /// - /// Subpath defined by two nodes. - /// \warning It is an error if the two edges are not in order! - UPath(const UPath &P, const NodeIt &a, const NodeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// \brief Subpath constructor. - /// - /// Subpath defined by two edges. Contains edges in [a,b) - /// \warning It is an error if the two edges are not in order! - UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) { - gr = P.gr; - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); - } - - /// Length of the path. - size_t length() const { return edges.size(); } - /// Returns whether the path is empty. - bool empty() const { return edges.empty(); } - - /// Resets the path to an empty path. - void clear() { edges.clear(); } - - /// \brief Starting point of the path. - /// - /// Starting point of the path. - /// Returns INVALID if the path is empty. - GraphNode source() const { - return empty() ? INVALID : gr->source(edges[0]); - } - /// \brief End point of the path. - /// - /// End point of the path. - /// Returns INVALID if the path is empty. - GraphNode target() const { - return empty() ? INVALID : gr->target(edges[length()-1]); - } - - /// \brief Initializes node or edge iterator to point to the first - /// node or edge. - /// - /// \sa nth - template - It& first(It &i) const { return i=It(*this); } - - /// \brief Initializes node iterator to point to the node of a given index. - NodeIt& nth(NodeIt &i, int n) const { - return i=NodeIt(*this, n); - } - - /// \brief Initializes edge iterator to point to the edge of a given index. - EdgeIt& nth(EdgeIt &i, int n) const { - return i=EdgeIt(*this, n); - } - - /// Checks validity of a node or edge iterator. - template - static - bool valid(const It &i) { return i.valid(); } - - /// Steps the given node or edge iterator. - template - static - It& next(It &e) { - return ++e; - } - - /// \brief Returns node iterator pointing to the target node of the - /// given edge iterator. - NodeIt target(const EdgeIt& e) const { - return NodeIt(*this, e.idx+1); - } - - /// \brief Returns node iterator pointing to the source node of the - /// given edge iterator. - NodeIt source(const EdgeIt& e) const { - return NodeIt(*this, e.idx); - } - - - - /** - * \brief Iterator class to iterate on the edges of the paths - * - * This class is used to iterate on the edges of the paths - * - * Of course it converts to Graph::Edge - * - * \todo Its interface differs from the standard edge iterator. - * Yes, it shouldn't. - */ - class EdgeIt { - friend class UPath; - - int idx; - const UPath *p; - public: - /// Default constructor - EdgeIt() {} - /// Invalid constructor - EdgeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - EdgeIt(const UPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Edge - operator GraphEdge () const { - return valid() ? p->edges[idx] : INVALID; - } - /// Next edge - EdgeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const EdgeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const EdgeIt& e) const { return idx= p->length() ) idx=-1; } - }; - - /** - * \brief Iterator class to iterate on the nodes of the paths - * - * This class is used to iterate on the nodes of the paths - * - * Of course it converts to Graph::Node - * - * \todo Its interface differs from the standard node iterator. - * Yes, it shouldn't. - */ - class NodeIt { - friend class UPath; - - int idx; - const UPath *p; - public: - /// Default constructor - NodeIt() {} - /// Invalid constructor - NodeIt(Invalid) : idx(-1), p(0) {} - /// Constructor with starting point - NodeIt(const UPath &_p, int _idx = 0) : - idx(_idx), p(&_p) { validate(); } - - ///Validity check - bool valid() const { return idx!=-1; } - - ///Conversion to Graph::Node - operator const GraphNode& () const { - if(idx >= p->length()) - return p->target(); - else if(idx >= 0) - return p->gr->source(p->edges[idx]); - else - return INVALID; - } - /// Next node - NodeIt& operator++() { ++idx; validate(); return *this; } - - /// Comparison operator - bool operator==(const NodeIt& e) const { return idx==e.idx; } - /// Comparison operator - bool operator!=(const NodeIt& e) const { return idx!=e.idx; } - /// Comparison operator - bool operator<(const NodeIt& e) const { return idx p->length() ) idx=-1; } - }; - - friend class Builder; - - /** - * \brief Class to build paths - * - * This class is used to fill a path with edges. - * - * You can push new edges to the front and to the back of the path in - * arbitrary order then you should commit these changes to the graph. - * - * Fundamentally, for most "Paths" (classes fulfilling the - * PathConcept) while the builder is active (after the first modifying - * operation and until the commit()) the original Path is in a - * "transitional" state (operations ot it have undefined result). But - * in the case of UPath the original path is unchanged until the - * commit. However we don't recomend that you use this feature. - */ - class Builder { - UPath &P; - Container front, back; - - public: - ///\param _p the path you want to fill in. - /// - Builder(UPath &_p) : P(_p) {} - - /// Sets the starting node of the path. - - /// Sets the starting node of the path. Edge added to the path - /// afterwards have to be incident to this node. - /// It should be called if and only if - /// the path is empty and before any call to - /// \ref pushFront() or \ref pushBack() - void setStartNode(const GraphNode &) {} - - ///Push a new edge to the front of the path - - ///Push a new edge to the front of the path. - ///\sa setStartNode - void pushFront(const GraphEdge& e) { - front.push_back(e); - } - - ///Push a new edge to the back of the path - - ///Push a new edge to the back of the path. - ///\sa setStartNode - void pushBack(const GraphEdge& e) { - back.push_back(e); - } - - ///Commit the changes to the path. - void commit() { - if( !(front.empty() && back.empty()) ) { - Container tmp; - tmp.reserve(front.size()+back.size()+P.length()); - tmp.insert(tmp.end(), front.rbegin(), front.rend()); - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); - tmp.insert(tmp.end(), back.begin(), back.end()); - P.edges.swap(tmp); - front.clear(); - back.clear(); - } - } - - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the front, using this function you can speed up the building. - - void reserveFront(size_t r) {front.reserve(r);} - - ///Reserve storage for the builder in advance. - - ///If you know a reasonable upper bound of the number of the edges - ///to add to the back, using this function you can speed up the building. - - void reserveBack(size_t r) {back.reserve(r);} - - private: - bool empty() { - return front.empty() && back.empty() && P.empty(); - } - - GraphNode source() const { - if( ! front.empty() ) - return P.gr->source(front[front.size()-1]); - else if( ! P.empty() ) - return P.gr->source(P.edges[0]); - else if( ! back.empty() ) - return P.gr->source(back[0]); - else - return INVALID; - } - GraphNode target() const { - if( ! back.empty() ) - return P.gr->target(back[back.size()-1]); - else if( ! P.empty() ) - return P.gr->target(P.edges[P.length()-1]); - else if( ! front.empty() ) - return P.gr->target(front[0]); - else - return INVALID; - } - - }; - - }; - - ///@} } // namespace lemon