1.1 --- a/src/work/peter/path/path_skeleton.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,223 +0,0 @@
1.4 -#define SKELETON
1.5 -// -*- c++ -*- //
1.6 -
1.7 -///\ingroup concept
1.8 -///\file
1.9 -///\brief Classes for representing paths in graphs.
1.10 -
1.11 -#ifndef LEMON_PATH_H
1.12 -#define LEMON_PATH_H
1.13 -
1.14 -#include <lemon/invalid.h>
1.15 -
1.16 -namespace lemon {
1.17 - namespace concept {
1.18 - /// \addtogroup concept
1.19 - /// @{
1.20 -
1.21 -
1.22 - //! \brief A skeleton structure for representing directed paths in a graph.
1.23 - //!
1.24 - //! A skeleton structure for representing directed paths in a graph.
1.25 - //! \param GR The graph type in which the path is.
1.26 - //!
1.27 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.28 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.29 - //! and \c Edge of the original graph.
1.30 - template<typename GR>
1.31 - class Path {
1.32 - public:
1.33 -
1.34 - /// Type of the underlying graph.
1.35 - typedef /*typename*/ GR Graph;
1.36 - /// Edge type of the underlying graph.
1.37 - typedef typename Graph::Edge GraphEdge;
1.38 - /// Node type of the underlying graph.
1.39 - typedef typename Graph::Node GraphNode;
1.40 - class NodeIt;
1.41 - class EdgeIt;
1.42 -
1.43 - /// \param _G The graph in which the path is.
1.44 - ///
1.45 - Path(const Graph &_G) {}
1.46 -
1.47 - /// Length of the path.
1.48 - size_t length() const {}
1.49 - /// Returns whether the path is empty.
1.50 - bool empty() const {}
1.51 -
1.52 - /// Resets the path to an empty path.
1.53 - void clear() {}
1.54 -
1.55 - /// \brief Starting point of the path.
1.56 - ///
1.57 - /// Starting point of the path.
1.58 - /// Returns INVALID if the path is empty.
1.59 - GraphNode target() const {}
1.60 - /// \brief End point of the path.
1.61 - ///
1.62 - /// End point of the path.
1.63 - /// Returns INVALID if the path is empty.
1.64 - GraphNode source() const {}
1.65 -
1.66 - /// \brief First NodeIt/EdgeIt.
1.67 - ///
1.68 - /// Initializes node or edge iterator to point to the first
1.69 - /// node or edge.
1.70 - template<typename It>
1.71 - It& first(It &i) const { return i=It(*this); }
1.72 -
1.73 - /// \brief The target of an edge.
1.74 - ///
1.75 - /// Returns node iterator pointing to the target node of the
1.76 - /// given edge iterator.
1.77 - NodeIt target(const EdgeIt& e) const {}
1.78 -
1.79 - /// \brief The source of an edge.
1.80 - ///
1.81 - /// Returns node iterator pointing to the source node of the
1.82 - /// given edge iterator.
1.83 - NodeIt source(const EdgeIt& e) const {}
1.84 -
1.85 -
1.86 - /* Iterator classes */
1.87 -
1.88 - /**
1.89 - * \brief Iterator class to iterate on the edges of the paths
1.90 - *
1.91 - * \ingroup concept
1.92 - * This class is used to iterate on the edges of the paths
1.93 - *
1.94 - * Of course it converts to Graph::Edge
1.95 - *
1.96 - */
1.97 - class EdgeIt {
1.98 - public:
1.99 - /// Default constructor
1.100 - EdgeIt() {}
1.101 - /// Invalid constructor
1.102 - EdgeIt(Invalid) {}
1.103 - /// Constructor with starting point
1.104 - EdgeIt(const Path &_p) {}
1.105 -
1.106 - operator GraphEdge () const {}
1.107 -
1.108 - /// Next edge
1.109 - EdgeIt& operator++() {}
1.110 -
1.111 - /// Comparison operator
1.112 - bool operator==(const EdgeIt& e) const {}
1.113 - /// Comparison operator
1.114 - bool operator!=(const EdgeIt& e) const {}
1.115 -// /// Comparison operator
1.116 -// /// \todo It is not clear what is the "natural" ordering.
1.117 -// bool operator<(const EdgeIt& e) const {}
1.118 -
1.119 - };
1.120 -
1.121 - /**
1.122 - * \brief Iterator class to iterate on the nodes of the paths
1.123 - *
1.124 - * \ingroup concept
1.125 - * This class is used to iterate on the nodes of the paths
1.126 - *
1.127 - * Of course it converts to Graph::Node.
1.128 - *
1.129 - */
1.130 - class NodeIt {
1.131 - public:
1.132 - /// Default constructor
1.133 - NodeIt() {}
1.134 - /// Invalid constructor
1.135 - NodeIt(Invalid) {}
1.136 - /// Constructor with starting point
1.137 - NodeIt(const Path &_p) {}
1.138 -
1.139 - ///Conversion to Graph::Node
1.140 - operator const GraphNode& () const {}
1.141 - /// Next node
1.142 - NodeIt& operator++() {}
1.143 -
1.144 - /// Comparison operator
1.145 - bool operator==(const NodeIt& e) const {}
1.146 - /// Comparison operator
1.147 - bool operator!=(const NodeIt& e) const {}
1.148 -// /// Comparison operator
1.149 -// /// \todo It is not clear what is the "natural" ordering.
1.150 -// bool operator<(const NodeIt& e) const {}
1.151 -
1.152 - };
1.153 -
1.154 - friend class Builder;
1.155 -
1.156 - /**
1.157 - * \brief Class to build paths
1.158 - *
1.159 - * \ingroup concept
1.160 - * This class is used to fill a path with edges.
1.161 - *
1.162 - * You can push new edges to the front and to the back of the path in
1.163 - * arbitrary order then you should commit these changes to the graph.
1.164 - *
1.165 - * While the builder is active (after the first modifying
1.166 - * operation and until the call of \ref commit())
1.167 - * the underlining Path is in a
1.168 - * "transitional" state (operations on it have undefined result).
1.169 - */
1.170 - class Builder {
1.171 - public:
1.172 -
1.173 - Path &P;
1.174 -
1.175 - ///\param _P the path you want to fill in.
1.176 - ///
1.177 - Builder(Path &_P) : P(_P) {}
1.178 -
1.179 - /// Sets the starting node of the path.
1.180 -
1.181 - /// Sets the starting node of the path. Edge added to the path
1.182 - /// afterwards have to be incident to this node.
1.183 - /// You \em must start building an empry path with this functions.
1.184 - /// (And you \em must \em not use it later).
1.185 - /// \sa pushFront()
1.186 - /// \sa pushBack()
1.187 - void setStartNode(const GraphNode &) {}
1.188 -
1.189 - ///Push a new edge to the front of the path
1.190 -
1.191 - ///Push a new edge to the front of the path.
1.192 - ///If the path is empty, you \em must call \ref setStartNode() before
1.193 - ///the first use of \ref pushFront().
1.194 - void pushFront(const GraphEdge& e) {}
1.195 -
1.196 - ///Push a new edge to the back of the path
1.197 -
1.198 - ///Push a new edge to the back of the path.
1.199 - ///If the path is empty, you \em must call \ref setStartNode() before
1.200 - ///the first use of \ref pushBack().
1.201 - void pushBack(const GraphEdge& e) {}
1.202 -
1.203 - ///Commit the changes to the path.
1.204 - void commit() {}
1.205 -
1.206 - ///Reserve (front) storage for the builder in advance.
1.207 -
1.208 - ///If you know an reasonable upper bound of the number of the edges
1.209 - ///to add to the front of the path,
1.210 - ///using this function you may speed up the building.
1.211 - void reserveFront(size_t r) {}
1.212 - ///Reserve (back) storage for the builder in advance.
1.213 -
1.214 - ///If you know an reasonable upper bound of the number of the edges
1.215 - ///to add to the back of the path,
1.216 - ///using this function you may speed up the building.
1.217 - void reserveBack(size_t r) {}
1.218 - };
1.219 - };
1.220 -
1.221 - ///@}
1.222 - }
1.223 -
1.224 -} // namespace lemon
1.225 -
1.226 -#endif // LEMON_PATH_H