/* -*- C++ -*- * lemon/concept/path.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ ///\ingroup concept ///\file ///\brief Classes for representing paths in graphs. /// ///\todo Iterators have obsolete style #ifndef LEMON_CONCEPT_PATH_H #define LEMON_CONCEPT_PATH_H #include namespace lemon { namespace concept { /// \addtogroup concept /// @{ //! \brief A skeleton structure for representing directed paths in a graph. //! //! A skeleton structure for representing directed paths in a graph. //! \param GR The graph type in which the path is. //! //! In a sense, the path can be treated as a graph, for it has \c NodeIt //! and \c EdgeIt with the same usage. These types converts to the \c Node //! and \c Edge of the original graph. template class Path { public: /// Type of the underlying graph. typedef /*typename*/ GR Graph; /// 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; /// \param _g The graph in which the path is. /// Path(const Graph &_g) {} /// Length of the path. int length() const {return 0;} /// Returns whether the path is empty. bool empty() const { return true;} /// Resets the path to an empty path. void clear() {} /// \brief Starting point of the path. /// /// Starting point of the path. /// Returns INVALID if the path is empty. GraphNode/*It*/ target() const {return INVALID;} /// \brief End point of the path. /// /// End point of the path. /// Returns INVALID if the path is empty. GraphNode/*It*/ source() const {return INVALID;} /// \brief First NodeIt/EdgeIt. /// /// Initializes node or edge iterator to point to the first /// node or edge. template It& first(It &i) const { return i=It(*this); } /// \brief The target of an edge. /// /// Returns node iterator pointing to the target node of the /// given edge iterator. NodeIt target(const EdgeIt&) const {return INVALID;} /// \brief The source of an edge. /// /// Returns node iterator pointing to the source node of the /// given edge iterator. NodeIt source(const EdgeIt&) const {return INVALID;} /* Iterator classes */ /** * \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 { public: /// Default constructor EdgeIt() {} /// Invalid constructor EdgeIt(Invalid) {} /// Constructor with starting point EdgeIt(const Path &) {} operator GraphEdge () const {} /// Next edge EdgeIt& operator++() {return *this;} /// Comparison operator bool operator==(const EdgeIt&) const {return true;} /// Comparison operator bool operator!=(const EdgeIt&) const {return true;} // /// Comparison operator // /// \todo It is not clear what is the "natural" ordering. // bool operator<(const EdgeIt& e) const {} }; /** * \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 { public: /// Default constructor NodeIt() {} /// Invalid constructor NodeIt(Invalid) {} /// Constructor with starting point NodeIt(const Path &) {} ///Conversion to Graph::Node operator const GraphNode& () const {} /// Next node NodeIt& operator++() {return *this;} /// Comparison operator bool operator==(const NodeIt&) const {return true;} /// Comparison operator bool operator!=(const NodeIt&) const {return true;} // /// Comparison operator // /// \todo It is not clear what is the "natural" ordering. // bool operator<(const NodeIt& e) const {} }; 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. * * While the builder is active (after the first modifying * operation and until the call of \ref commit()) the * underlining Path is in a "transitional" state (operations on * it have undefined result). */ class Builder { public: Path &P; ///\param _p the path you want to fill in. /// Builder(Path &_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. /// You \em must start building an empty path with these functions. /// (And you \em must \em not use it later). /// \sa pushFront() /// \sa 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. ///If the path is empty, you \em must call \ref setStartNode() before ///the first use of \ref pushFront(). void pushFront(const GraphEdge&) {} ///Push a new edge to the back of the path ///Push a new edge to the back of the path. ///If the path is empty, you \em must call \ref setStartNode() before ///the first use of \ref pushBack(). void pushBack(const GraphEdge&) {} ///Commit the changes to the path. void commit() {} ///Reserve (front) storage for the builder in advance. ///If you know a reasonable upper bound on the number of the edges ///to add to the front of the path, ///using this function you may speed up the building. void reserveFront(size_t) {} ///Reserve (back) storage for the builder in advance. ///If you know a reasonable upper bound on the number of the edges ///to add to the back of the path, ///using this function you may speed up the building. void reserveBack(size_t) {} }; }; ///@} } } // namespace lemon #endif // LEMON_CONCEPT_PATH_H