1.1 --- a/lemon/concept/path.h Tue Oct 17 10:42:19 2006 +0000
1.2 +++ b/lemon/concept/path.h Tue Oct 17 10:50:57 2006 +0000
1.3 @@ -37,21 +37,22 @@
1.4 //! \brief A skeleton structure for representing directed paths in a graph.
1.5 //!
1.6 //! A skeleton structure for representing directed paths in a graph.
1.7 - //! \param GR The graph type in which the path is.
1.8 + //! \param _Graph The graph type in which the path is.
1.9 //!
1.10 //! In a sense, the path can be treated as a graph, for it has \c NodeIt
1.11 //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.12 //! and \c Edge of the original graph.
1.13 - template<typename GR>
1.14 + template<typename _Graph>
1.15 class Path {
1.16 public:
1.17
1.18 /// Type of the underlying graph.
1.19 - typedef /*typename*/ GR Graph;
1.20 + typedef _Graph Graph;
1.21 /// Edge type of the underlying graph.
1.22 - typedef typename Graph::Edge GraphEdge;
1.23 + typedef typename Graph::Edge Edge;
1.24 /// Node type of the underlying graph.
1.25 - typedef typename Graph::Node GraphNode;
1.26 + typedef typename Graph::Node Node;
1.27 +
1.28 class NodeIt;
1.29 class EdgeIt;
1.30
1.31 @@ -61,8 +62,9 @@
1.32 ignore_unused_variable_warning(_g);
1.33 }
1.34
1.35 - /// Length of the path.
1.36 + /// Length of the path ie. the number of edges in the path.
1.37 int length() const {return 0;}
1.38 +
1.39 /// Returns whether the path is empty.
1.40 bool empty() const { return true;}
1.41
1.42 @@ -73,19 +75,12 @@
1.43 ///
1.44 /// Starting point of the path.
1.45 /// Returns INVALID if the path is empty.
1.46 - GraphNode/*It*/ target() const {return INVALID;}
1.47 + Node target() const {return INVALID;}
1.48 /// \brief End point of the path.
1.49 ///
1.50 /// End point of the path.
1.51 /// Returns INVALID if the path is empty.
1.52 - GraphNode/*It*/ source() const {return INVALID;}
1.53 -
1.54 - /// \brief First NodeIt/EdgeIt.
1.55 - ///
1.56 - /// Initializes node or edge iterator to point to the first
1.57 - /// node or edge.
1.58 - template<typename It>
1.59 - It& first(It &i) const { return i=It(*this); }
1.60 + Node source() const {return INVALID;}
1.61
1.62 /// \brief The target of an edge.
1.63 ///
1.64 @@ -99,49 +94,11 @@
1.65 /// given edge iterator.
1.66 NodeIt source(const EdgeIt&) const {return INVALID;}
1.67
1.68 -
1.69 - /* Iterator classes */
1.70 -
1.71 - /**
1.72 - * \brief Iterator class to iterate on the edges of the paths
1.73 - *
1.74 - * This class is used to iterate on the edges of the paths
1.75 - *
1.76 - * Of course it converts to Graph::Edge
1.77 - *
1.78 - */
1.79 - class EdgeIt {
1.80 - public:
1.81 - /// Default constructor
1.82 - EdgeIt() {}
1.83 - /// Invalid constructor
1.84 - EdgeIt(Invalid) {}
1.85 - /// Constructor with starting point
1.86 - EdgeIt(const Path &) {}
1.87 -
1.88 - operator GraphEdge () const {}
1.89 -
1.90 - /// Next edge
1.91 - EdgeIt& operator++() {return *this;}
1.92 -
1.93 - /// Comparison operator
1.94 - bool operator==(const EdgeIt&) const {return true;}
1.95 - /// Comparison operator
1.96 - bool operator!=(const EdgeIt&) const {return true;}
1.97 -// /// Comparison operator
1.98 -// /// \todo It is not clear what is the "natural" ordering.
1.99 -// bool operator<(const EdgeIt& e) const {}
1.100 -
1.101 - };
1.102 -
1.103 - /**
1.104 - * \brief Iterator class to iterate on the nodes of the paths
1.105 - *
1.106 - * This class is used to iterate on the nodes of the paths
1.107 - *
1.108 - * Of course it converts to Graph::Node.
1.109 - *
1.110 - */
1.111 + /// \brief Iterator class to iterate on the nodes of the paths
1.112 + ///
1.113 + /// This class is used to iterate on the nodes of the paths
1.114 + ///
1.115 + /// Of course it converts to Graph::Node.
1.116 class NodeIt {
1.117 public:
1.118 /// Default constructor
1.119 @@ -152,7 +109,7 @@
1.120 NodeIt(const Path &) {}
1.121
1.122 ///Conversion to Graph::Node
1.123 - operator const GraphNode& () const {}
1.124 + operator Node() const { return INVALID; }
1.125 /// Next node
1.126 NodeIt& operator++() {return *this;}
1.127
1.128 @@ -160,36 +117,63 @@
1.129 bool operator==(const NodeIt&) const {return true;}
1.130 /// Comparison operator
1.131 bool operator!=(const NodeIt&) const {return true;}
1.132 -// /// Comparison operator
1.133 -// /// \todo It is not clear what is the "natural" ordering.
1.134 -// bool operator<(const NodeIt& e) const {}
1.135 + /// Comparison operator
1.136 + bool operator<(const NodeIt&) const {return false;}
1.137
1.138 };
1.139
1.140 + /// \brief Iterator class to iterate on the edges of the paths
1.141 + ///
1.142 + /// This class is used to iterate on the edges of the paths
1.143 + ///
1.144 + /// Of course it converts to Graph::Edge
1.145 + class EdgeIt {
1.146 + public:
1.147 + /// Default constructor
1.148 + EdgeIt() {}
1.149 + /// Invalid constructor
1.150 + EdgeIt(Invalid) {}
1.151 + /// Constructor with starting point
1.152 + EdgeIt(const Path &) {}
1.153 +
1.154 + operator Edge() const { return INVALID; }
1.155 +
1.156 + /// Next edge
1.157 + EdgeIt& operator++() {return *this;}
1.158 +
1.159 + /// Comparison operator
1.160 + bool operator==(const EdgeIt&) const {return true;}
1.161 + /// Comparison operator
1.162 + bool operator!=(const EdgeIt&) const {return true;}
1.163 + /// Comparison operator
1.164 + bool operator<(const EdgeIt&) const {return false;}
1.165 +
1.166 + };
1.167 +
1.168 +
1.169 friend class Builder;
1.170
1.171 - /**
1.172 - * \brief Class to build paths
1.173 - *
1.174 - * This class is used to fill a path with edges.
1.175 - *
1.176 - * You can push new edges to the front and to the back of the path in
1.177 - * arbitrary order then you should commit these changes to the graph.
1.178 - *
1.179 - * While the builder is active (after the first modifying
1.180 - * operation and until the call of \ref commit()) the
1.181 - * underlining Path is in a "transitional" state (operations on
1.182 - * it have undefined result).
1.183 - */
1.184 + /// \brief Class to build paths
1.185 + ///
1.186 + /// This class is used to fill a path with edges.
1.187 + ///
1.188 + /// You can push new edges to the front and to the back of the path in
1.189 + /// arbitrary order then you should commit these changes to the graph.
1.190 + ///
1.191 + /// While the builder is active (after the first modifying
1.192 + /// operation and until the call of \ref commit()) the
1.193 + /// underlining Path is in a "transitional" state (operations on
1.194 + /// it have undefined result).
1.195 class Builder {
1.196 public:
1.197
1.198 - Path &P;
1.199 + /// Constructor
1.200
1.201 - ///\param _p the path you want to fill in.
1.202 + /// Constructor
1.203 + /// \param _path the path you want to fill in.
1.204 ///
1.205
1.206 - Builder(Path &_p) : P(_p) {}
1.207 + Builder(Path &_path) { ignore_unused_variable_warning(_path); }
1.208
1.209 /// Sets the starting node of the path.
1.210
1.211 @@ -199,23 +183,26 @@
1.212 /// (And you \em must \em not use it later).
1.213 /// \sa pushFront()
1.214 /// \sa pushBack()
1.215 - void setStartNode(const GraphNode &) {}
1.216 + void setStartNode(const Node &) {}
1.217
1.218 ///Push a new edge to the front of the path
1.219
1.220 ///Push a new edge to the front of the path.
1.221 ///If the path is empty, you \em must call \ref setStartNode() before
1.222 ///the first use of \ref pushFront().
1.223 - void pushFront(const GraphEdge&) {}
1.224 + void pushFront(const Edge&) {}
1.225
1.226 ///Push a new edge to the back of the path
1.227
1.228 ///Push a new edge to the back of the path.
1.229 ///If the path is empty, you \em must call \ref setStartNode() before
1.230 ///the first use of \ref pushBack().
1.231 - void pushBack(const GraphEdge&) {}
1.232 + void pushBack(const Edge&) {}
1.233
1.234 ///Commit the changes to the path.
1.235 +
1.236 + ///Commit the changes to the path.
1.237 + ///
1.238 void commit() {}
1.239
1.240 ///Reserve (front) storage for the builder in advance.
1.241 @@ -231,6 +218,72 @@
1.242 ///using this function you may speed up the building.
1.243 void reserveBack(size_t) {}
1.244 };
1.245 +
1.246 + template <typename _Path>
1.247 + struct Constraints {
1.248 + void constraints() {
1.249 + typedef typename _Path::Node Node;
1.250 + typedef typename _Path::NodeIt NodeIt;
1.251 + typedef typename Graph::Node GraphNode;
1.252 +
1.253 + typedef typename _Path::Edge Edge;
1.254 + typedef typename _Path::EdgeIt EdgeIt;
1.255 + typedef typename Graph::Edge GraphEdge;
1.256 +
1.257 + typedef typename _Path::Builder Builder;
1.258 +
1.259 + path = _Path(graph);
1.260 +
1.261 + bool b = cpath.empty();
1.262 + int l = cpath.length();
1.263 +
1.264 + Node gn;
1.265 + Edge ge;
1.266 + gn = cpath.source();
1.267 + gn = cpath.target();
1.268 +
1.269 + NodeIt nit;
1.270 + EdgeIt eit(INVALID);
1.271 + nit = path.source(eit);
1.272 + nit = path.target(eit);
1.273 +
1.274 + nit = NodeIt();
1.275 + nit = NodeIt(cpath);
1.276 + nit = INVALID;
1.277 + gn = nit;
1.278 + ++nit;
1.279 + b = nit == nit;
1.280 + b = nit != nit;
1.281 + b = nit < nit;
1.282 +
1.283 + eit = EdgeIt();
1.284 + eit = EdgeIt(cpath);
1.285 + eit = INVALID;
1.286 + ge = eit;
1.287 + ++eit;
1.288 + b = eit == eit;
1.289 + b = eit != eit;
1.290 + b = eit < eit;
1.291 +
1.292 + size_t st = 0;
1.293 +
1.294 + Builder builder(path);
1.295 + builder.setStartNode(gn);
1.296 + builder.pushFront(ge);
1.297 + builder.pushBack(ge);
1.298 + builder.commit();
1.299 + builder.reserveFront(st);
1.300 + builder.reserveBack(st);
1.301 +
1.302 + ignore_unused_variable_warning(l);
1.303 + ignore_unused_variable_warning(b);
1.304 + }
1.305 +
1.306 + const Graph& graph;
1.307 + const _Path& cpath;
1.308 + _Path& path;
1.309 + };
1.310 +
1.311 };
1.312
1.313 ///@}