klao@959: /* -*- C++ -*-
klao@959: * src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
klao@959: *
alpar@1164: * Copyright (C) 2005 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.
alpar@1151: ///
alpar@1151: ///\todo Iterators have obsolete style
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.
alpar@986: GraphNode/*It*/ target() 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.
alpar@986: GraphNode/*It*/ source() 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:
alpar@986: /// \brief The target of an edge.
klao@959: ///
alpar@986: /// Returns node iterator pointing to the target node of the
klao@959: /// given edge iterator.
alpar@986: NodeIt target(const EdgeIt& e) const {return INVALID;}
klao@959:
alpar@986: /// \brief The source of an edge.
klao@959: ///
alpar@986: /// Returns node iterator pointing to the source node of the
klao@959: /// given edge iterator.
alpar@986: NodeIt source(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: * 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: * 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: * 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