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