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 ///@}
2.1 --- a/lemon/path.h Tue Oct 17 10:42:19 2006 +0000
2.2 +++ b/lemon/path.h Tue Oct 17 10:50:57 2006 +0000
2.3 @@ -21,15 +21,14 @@
2.4 ///\file
2.5 ///\brief Classes for representing paths in graphs.
2.6 ///
2.7 -///\todo Iterators have obsolete style
2.8
2.9 #ifndef LEMON_PATH_H
2.10 #define LEMON_PATH_H
2.11
2.12 -#include <deque>
2.13 #include <vector>
2.14 #include <algorithm>
2.15
2.16 +#include <lemon/error.h>
2.17 #include <lemon/bits/invalid.h>
2.18
2.19 namespace lemon {
2.20 @@ -42,7 +41,6 @@
2.21 //!
2.22 //! A structure for representing directed path in a graph.
2.23 //! \param Graph The graph type in which the path is.
2.24 - //! \param DM DebugMode, defaults to DefaultDebugMode.
2.25 //!
2.26 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
2.27 //! and \c EdgeIt with the same usage. These types converts to the \c Node
2.28 @@ -50,640 +48,383 @@
2.29 //!
2.30 //! \todo Thoroughfully check all the range and consistency tests.
2.31 template<typename Graph>
2.32 - class DirPath {
2.33 + class Path {
2.34 public:
2.35 /// Edge type of the underlying graph.
2.36 - typedef typename Graph::Edge GraphEdge;
2.37 + typedef typename Graph::Edge Edge;
2.38 /// Node type of the underlying graph.
2.39 - typedef typename Graph::Node GraphNode;
2.40 + typedef typename Graph::Node Node;
2.41 +
2.42 class NodeIt;
2.43 class EdgeIt;
2.44
2.45 - protected:
2.46 - const Graph *gr;
2.47 - typedef std::vector<GraphEdge> Container;
2.48 - Container edges;
2.49 + struct PathError : public LogicError {
2.50 + virtual const char* what() const throw() {
2.51 + return "lemon::PathError";
2.52 + }
2.53 + };
2.54
2.55 public:
2.56
2.57 + /// \brief Constructor
2.58 + ///
2.59 + /// Constructor
2.60 /// \param _G The graph in which the path is.
2.61 - ///
2.62 - DirPath(const Graph &_G) : gr(&_G) {}
2.63 -
2.64 + Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
2.65 +
2.66 /// \brief Subpath constructor.
2.67 ///
2.68 /// Subpath defined by two nodes.
2.69 /// \warning It is an error if the two edges are not in order!
2.70 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
2.71 - gr = P.gr;
2.72 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.73 + Path(const Path &other, const NodeIt &a, const NodeIt &b) {
2.74 + graph = other.graph;
2.75 + start = a;
2.76 + edges.insert(edges.end(),
2.77 + other.edges.begin() + a.id, other.edges.begin() + b.id);
2.78 }
2.79
2.80 /// \brief Subpath constructor.
2.81 ///
2.82 /// Subpath defined by two edges. Contains edges in [a,b)
2.83 /// \warning It is an error if the two edges are not in order!
2.84 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
2.85 - gr = P.gr;
2.86 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.87 + Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
2.88 + graph = other.graph;
2.89 + start = graph->source(a);
2.90 + edges.insert(edges.end(),
2.91 + other.edges.begin() + a.id, other.edges.begin() + b.id);
2.92 }
2.93
2.94 - /// Length of the path.
2.95 + /// \brief Length of the path.
2.96 + ///
2.97 + /// The number of the edges in the path. It can be zero if the
2.98 + /// path has only one node or it is empty.
2.99 int length() const { return edges.size(); }
2.100 - /// Returns whether the path is empty.
2.101 - bool empty() const { return edges.empty(); }
2.102
2.103 + /// \brief Returns whether the path is empty.
2.104 + ///
2.105 + /// Returns true when the path does not contain neither edge nor
2.106 + /// node.
2.107 + bool empty() const { return start == INVALID; }
2.108 +
2.109 + /// \brief Resets the path to an empty path.
2.110 + ///
2.111 /// Resets the path to an empty path.
2.112 - void clear() { edges.clear(); }
2.113 + void clear() { edges.clear(); start = INVALID; }
2.114
2.115 /// \brief Starting point of the path.
2.116 ///
2.117 /// Starting point of the path.
2.118 /// Returns INVALID if the path is empty.
2.119 - GraphNode source() const {
2.120 - return empty() ? INVALID : gr->source(edges[0]);
2.121 + Node source() const {
2.122 + return start;
2.123 }
2.124 /// \brief End point of the path.
2.125 ///
2.126 /// End point of the path.
2.127 /// Returns INVALID if the path is empty.
2.128 - GraphNode target() const {
2.129 - return empty() ? INVALID : gr->target(edges[length()-1]);
2.130 + Node target() const {
2.131 + return length() == 0 ? start : graph->target(edges[length()-1]);
2.132 }
2.133
2.134 - /// \brief Initializes node or edge iterator to point to the first
2.135 - /// node or edge.
2.136 + /// \brief Gives back a node iterator to point to the node of a
2.137 + /// given index.
2.138 ///
2.139 - /// \sa nth
2.140 - template<typename It>
2.141 - It& first(It &i) const { return i=It(*this); }
2.142 -
2.143 - /// \brief Initializes node iterator to point to the node of a given index.
2.144 - NodeIt& nth(NodeIt &i, int n) const {
2.145 - return i=NodeIt(*this, n);
2.146 + /// Gives back a node iterator to point to the node of a given
2.147 + /// index.
2.148 + /// \pre n should less or equal to \c length()
2.149 + NodeIt nthNode(int n) const {
2.150 + return NodeIt(*this, n);
2.151 }
2.152
2.153 - /// \brief Initializes edge iterator to point to the edge of a given index.
2.154 - EdgeIt& nth(EdgeIt &i, int n) const {
2.155 - return i=EdgeIt(*this, n);
2.156 + /// \brief Gives back an edge iterator to point to the edge of a
2.157 + /// given index.
2.158 + ///
2.159 + /// Gives back an edge iterator to point to the node of a given
2.160 + /// index.
2.161 + /// \pre n should less than \c length()
2.162 + EdgeIt nthEdge(int n) const {
2.163 + return EdgeIt(*this, n);
2.164 + }
2.165 +
2.166 + /// \brief Returns node iterator pointing to the source node of the
2.167 + /// given edge iterator.
2.168 + ///
2.169 + /// Returns node iterator pointing to the source node of the given
2.170 + /// edge iterator.
2.171 + NodeIt source(const EdgeIt& e) const {
2.172 + return NodeIt(*this, e.id);
2.173 }
2.174
2.175 /// \brief Returns node iterator pointing to the target node of the
2.176 /// given edge iterator.
2.177 + ///
2.178 + /// Returns node iterator pointing to the target node of the given
2.179 + /// edge iterator.
2.180 NodeIt target(const EdgeIt& e) const {
2.181 - return NodeIt(*this, e.idx+1);
2.182 + return NodeIt(*this, e.id + 1);
2.183 }
2.184
2.185 - /// \brief Returns node iterator pointing to the source node of the
2.186 - /// given edge iterator.
2.187 - NodeIt source(const EdgeIt& e) const {
2.188 - return NodeIt(*this, e.idx);
2.189 - }
2.190
2.191 + /// \brief Iterator class to iterate on the nodes of the paths
2.192 + ///
2.193 + /// This class is used to iterate on the nodes of the paths
2.194 + ///
2.195 + /// Of course it converts to Graph::Node
2.196 + class NodeIt {
2.197 + friend class Path;
2.198 + public:
2.199
2.200 - /* Iterator classes */
2.201 + /// \brief Default constructor
2.202 + ///
2.203 + /// Default constructor
2.204 + NodeIt() {}
2.205
2.206 - /**
2.207 - * \brief Iterator class to iterate on the edges of the paths
2.208 - *
2.209 - * This class is used to iterate on the edges of the paths
2.210 - *
2.211 - * Of course it converts to Graph::Edge
2.212 - *
2.213 - */
2.214 + /// \brief Invalid constructor
2.215 + ///
2.216 + /// Invalid constructor
2.217 + NodeIt(Invalid) : id(-1), path(0) {}
2.218 +
2.219 + /// \brief Constructor with starting point
2.220 + ///
2.221 + /// Constructor with starting point
2.222 + NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
2.223 + if (id > path->length()) id = -1;
2.224 + }
2.225 +
2.226 + /// \brief Conversion to Graph::Node
2.227 + ///
2.228 + /// Conversion to Graph::Node
2.229 + operator Node() const {
2.230 + if (id > 0) {
2.231 + return path->graph->target(path->edges[id - 1]);
2.232 + } else if (id == 0) {
2.233 + return path->start;
2.234 + } else {
2.235 + return INVALID;
2.236 + }
2.237 + }
2.238 +
2.239 + /// \brief Steps to the next node
2.240 + ///
2.241 + /// Steps to the next node
2.242 + NodeIt& operator++() {
2.243 + ++id;
2.244 + if (id > path->length()) id = -1;
2.245 + return *this;
2.246 + }
2.247 +
2.248 + /// \brief Comparison operator
2.249 + ///
2.250 + /// Comparison operator
2.251 + bool operator==(const NodeIt& n) const { return id == n.id; }
2.252 +
2.253 + /// \brief Comparison operator
2.254 + ///
2.255 + /// Comparison operator
2.256 + bool operator!=(const NodeIt& n) const { return id != n.id; }
2.257 +
2.258 + /// \brief Comparison operator
2.259 + ///
2.260 + /// Comparison operator
2.261 + bool operator<(const NodeIt& n) const { return id < n.id; }
2.262 +
2.263 + private:
2.264 + int id;
2.265 + const Path *path;
2.266 + };
2.267 +
2.268 + /// \brief Iterator class to iterate on the edges of the paths
2.269 + ///
2.270 + /// This class is used to iterate on the edges of the paths
2.271 + /// Of course it converts to Graph::Edge
2.272 class EdgeIt {
2.273 - friend class DirPath;
2.274 + friend class Path;
2.275 + public:
2.276
2.277 - int idx;
2.278 - const DirPath *p;
2.279 - public:
2.280 + /// \brief Default constructor
2.281 + ///
2.282 /// Default constructor
2.283 EdgeIt() {}
2.284 +
2.285 + /// \brief Invalid constructor
2.286 + ///
2.287 /// Invalid constructor
2.288 - EdgeIt(Invalid) : idx(-1), p(0) {}
2.289 + EdgeIt(Invalid) : id(-1), path(0) {}
2.290 +
2.291 + /// \brief Constructor with starting point
2.292 + ///
2.293 /// Constructor with starting point
2.294 - EdgeIt(const DirPath &_p, int _idx = 0) :
2.295 - idx(_idx), p(&_p) { validate(); }
2.296 -
2.297 - ///Validity check
2.298 - bool valid() const { return idx!=-1; }
2.299 -
2.300 - ///Conversion to Graph::Edge
2.301 - operator GraphEdge () const {
2.302 - return valid() ? p->edges[idx] : INVALID;
2.303 + EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
2.304 + if (id >= path->length()) id = -1;
2.305 }
2.306
2.307 - /// Next edge
2.308 - EdgeIt& operator++() { ++idx; validate(); return *this; }
2.309 + /// \brief Conversion to Graph::Edge
2.310 + ///
2.311 + /// Conversion to Graph::Edge
2.312 + operator Edge() const {
2.313 + return id != -1 ? path->edges[id] : INVALID;
2.314 + }
2.315
2.316 + /// \brief Steps to the next edge
2.317 + ///
2.318 + /// Steps to the next edge
2.319 + EdgeIt& operator++() {
2.320 + ++id;
2.321 + if (id >= path->length()) id = -1;
2.322 + return *this;
2.323 + }
2.324 +
2.325 + /// \brief Comparison operator
2.326 + ///
2.327 /// Comparison operator
2.328 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.329 + bool operator==(const EdgeIt& e) const { return id == e.id; }
2.330 +
2.331 + /// \brief Comparison operator
2.332 + ///
2.333 /// Comparison operator
2.334 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.335 + bool operator!=(const EdgeIt& e) const { return id != e.id; }
2.336 +
2.337 + /// \brief Comparison operator
2.338 + ///
2.339 /// Comparison operator
2.340 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.341 + bool operator<(const EdgeIt& e) const { return id < e.id; }
2.342
2.343 private:
2.344 - void validate() { if(idx >= p->length() ) idx=-1; }
2.345 +
2.346 + int id;
2.347 + const Path *path;
2.348 };
2.349
2.350 - /**
2.351 - * \brief Iterator class to iterate on the nodes of the paths
2.352 - *
2.353 - * This class is used to iterate on the nodes of the paths
2.354 - *
2.355 - * Of course it converts to Graph::Node
2.356 - *
2.357 - */
2.358 - class NodeIt {
2.359 - friend class DirPath;
2.360 + protected:
2.361
2.362 - int idx;
2.363 - const DirPath *p;
2.364 - public:
2.365 - /// Default constructor
2.366 - NodeIt() {}
2.367 - /// Invalid constructor
2.368 - NodeIt(Invalid) : idx(-1), p(0) {}
2.369 - /// Constructor with starting point
2.370 - NodeIt(const DirPath &_p, int _idx = 0) :
2.371 - idx(_idx), p(&_p) { validate(); }
2.372 + const Graph *graph;
2.373
2.374 - ///Validity check
2.375 - bool valid() const { return idx!=-1; }
2.376 + typedef std::vector<Edge> Container;
2.377 + Container edges;
2.378 + Node start;
2.379
2.380 - ///Conversion to Graph::Node
2.381 - operator GraphNode () const {
2.382 - if(idx >= p->length())
2.383 - return p->target();
2.384 - else if(idx >= 0)
2.385 - return p->gr->source(p->edges[idx]);
2.386 - else
2.387 - return INVALID;
2.388 - }
2.389 - /// Next node
2.390 - NodeIt& operator++() { ++idx; validate(); return *this; }
2.391 -
2.392 - /// Comparison operator
2.393 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.394 - /// Comparison operator
2.395 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.396 - /// Comparison operator
2.397 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.398 -
2.399 - private:
2.400 - void validate() { if(idx > p->length() ) idx=-1; }
2.401 - };
2.402 + public:
2.403
2.404 friend class Builder;
2.405
2.406 - /**
2.407 - * \brief Class to build paths
2.408 - *
2.409 - * This class is used to fill a path with edges.
2.410 - *
2.411 - * You can push new edges to the front and to the back of the path in
2.412 - * arbitrary order then you should commit these changes to the graph.
2.413 - *
2.414 - * Fundamentally, for most "Paths" (classes fulfilling the
2.415 - * PathConcept) while the builder is active (after the first modifying
2.416 - * operation and until the commit()) the original Path is in a
2.417 - * "transitional" state (operations on it have undefined result). But
2.418 - * in the case of DirPath the original path remains unchanged until the
2.419 - * commit. However we don't recomend that you use this feature.
2.420 - */
2.421 + /// \brief Class to build paths
2.422 + ///
2.423 + /// This class is used to fill a path with edges.
2.424 + ///
2.425 + /// You can push new edges to the front and to the back of the
2.426 + /// path in arbitrary order then you should commit these changes
2.427 + /// to the graph.
2.428 + ///
2.429 + /// Fundamentally, for most "Paths" (classes fulfilling the
2.430 + /// PathConcept) while the builder is active (after the first
2.431 + /// modifying operation and until the commit()) the original Path
2.432 + /// is in a "transitional" state (operations on it have undefined
2.433 + /// result). But in the case of Path the original path remains
2.434 + /// unchanged until the commit. However we don't recomend that you
2.435 + /// use this feature.
2.436 class Builder {
2.437 - DirPath &P;
2.438 - Container front, back;
2.439 + public:
2.440 + /// \brief Constructor
2.441 + ///
2.442 + /// Constructor
2.443 + /// \param _path the path you want to fill in.
2.444 + Builder(Path &_path) : path(_path), start(INVALID) {}
2.445
2.446 - public:
2.447 - ///\param _p the path you want to fill in.
2.448 + /// \brief Destructor
2.449 ///
2.450 - Builder(DirPath &_p) : P(_p) {}
2.451 + /// Destructor
2.452 + ~Builder() {
2.453 + LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
2.454 + PathError());
2.455 + }
2.456
2.457 - /// Sets the starting node of the path.
2.458 + /// \brief Sets the starting node of the path.
2.459 + ///
2.460 + /// Sets the starting node of the path. Edge added to the path
2.461 + /// afterwards have to be incident to this node. It should be
2.462 + /// called if and only if the path is empty and before any call
2.463 + /// to \ref pushFront() or \ref pushBack()
2.464 + void setStartNode(const Node &_start) {
2.465 + LEMON_ASSERT(path.empty() && start == INVALID, PathError());
2.466 + start = _start;
2.467 + }
2.468
2.469 - /// Sets the starting node of the path. Edge added to the path
2.470 - /// afterwards have to be incident to this node.
2.471 - /// It should be called if and only if
2.472 - /// the path is empty and before any call to
2.473 - /// \ref pushFront() or \ref pushBack()
2.474 - void setStartNode(const GraphNode &) {}
2.475 -
2.476 - ///Push a new edge to the front of the path
2.477 -
2.478 - ///Push a new edge to the front of the path.
2.479 - ///\sa setStartNode
2.480 - void pushFront(const GraphEdge& e) {
2.481 + /// \brief Push a new edge to the front of the path
2.482 + ///
2.483 + /// Push a new edge to the front of the path.
2.484 + /// \sa setStartNode
2.485 + void pushFront(const Edge& e) {
2.486 + LEMON_ASSERT(front.empty() ||
2.487 + (path.graph->source(front.back()) ==
2.488 + path.graph->target(e)), PathError());
2.489 + LEMON_ASSERT(path.empty() ||
2.490 + (path.source() == path.graph->target(e)), PathError());
2.491 + LEMON_ASSERT(!path.empty() || !front.empty() ||
2.492 + (start == path.graph->target(e)), PathError());
2.493 front.push_back(e);
2.494 }
2.495
2.496 - ///Push a new edge to the back of the path
2.497 -
2.498 - ///Push a new edge to the back of the path.
2.499 - ///\sa setStartNode
2.500 - void pushBack(const GraphEdge& e) {
2.501 + /// \brief Push a new edge to the back of the path
2.502 + ///
2.503 + /// Push a new edge to the back of the path.
2.504 + /// \sa setStartNode
2.505 + void pushBack(const Edge& e) {
2.506 + LEMON_ASSERT(back.empty() ||
2.507 + (path.graph->target(back.back()) ==
2.508 + path.graph->source(e)), PathError());
2.509 + LEMON_ASSERT(path.empty() ||
2.510 + (path.target() == path.graph->source(e)), PathError());
2.511 + LEMON_ASSERT(!path.empty() || !back.empty() ||
2.512 + (start == path.graph->source(e)), PathError());
2.513 back.push_back(e);
2.514 }
2.515
2.516 - ///Commit the changes to the path.
2.517 + /// \brief Commit the changes to the path.
2.518 + ///
2.519 + /// Commit the changes to the path.
2.520 void commit() {
2.521 - if( !front.empty() || !back.empty() ) {
2.522 + if( !front.empty() || !back.empty() || start != INVALID) {
2.523 Container tmp;
2.524 - tmp.reserve(front.size()+back.size()+P.length());
2.525 + tmp.reserve(front.size() + back.size() + path.length());
2.526 tmp.insert(tmp.end(), front.rbegin(), front.rend());
2.527 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
2.528 + tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
2.529 tmp.insert(tmp.end(), back.begin(), back.end());
2.530 - P.edges.swap(tmp);
2.531 + path.edges.swap(tmp);
2.532 + if (!front.empty()) {
2.533 + path.start = path.graph->source(front.back());
2.534 + } else {
2.535 + path.start = start;
2.536 + }
2.537 + start = INVALID;
2.538 front.clear();
2.539 back.clear();
2.540 }
2.541 }
2.542
2.543 - ///Reserve storage for the builder in advance.
2.544 -
2.545 - ///If you know a reasonable upper bound of the number of the edges
2.546 - ///to add to the front, using this function you can speed up the building.
2.547 -
2.548 + /// \brief Reserve storage for the builder in advance.
2.549 + ///
2.550 + /// If you know a reasonable upper bound of the number of the
2.551 + /// edges to add to the front, using this function you can speed
2.552 + /// up the building.
2.553 void reserveFront(size_t r) {front.reserve(r);}
2.554
2.555 - ///Reserve storage for the builder in advance.
2.556 -
2.557 - ///If you know a reasonable upper bound of the number of the edges
2.558 - ///to add to the back, using this function you can speed up the building.
2.559 -
2.560 + /// \brief Reserve storage for the builder in advance.
2.561 + ///
2.562 + /// If you know a reasonable upper bound of the number of the
2.563 + /// edges to add to the back, using this function you can speed
2.564 + /// up the building.
2.565 void reserveBack(size_t r) {back.reserve(r);}
2.566
2.567 private:
2.568 - bool empty() {
2.569 - return front.empty() && back.empty() && P.empty();
2.570 - }
2.571
2.572 - GraphNode source() const {
2.573 - if( ! front.empty() )
2.574 - return P.gr->source(front[front.size()-1]);
2.575 - else if( ! P.empty() )
2.576 - return P.gr->source(P.edges[0]);
2.577 - else if( ! back.empty() )
2.578 - return P.gr->source(back[0]);
2.579 - else
2.580 - return INVALID;
2.581 - }
2.582 - GraphNode target() const {
2.583 - if( ! back.empty() )
2.584 - return P.gr->target(back[back.size()-1]);
2.585 - else if( ! P.empty() )
2.586 - return P.gr->target(P.edges[P.length()-1]);
2.587 - else if( ! front.empty() )
2.588 - return P.gr->target(front[0]);
2.589 - else
2.590 - return INVALID;
2.591 - }
2.592 + Path &path;
2.593 + Container front, back;
2.594 + Node start;
2.595
2.596 };
2.597
2.598 };
2.599
2.600 -
2.601 -
2.602 -
2.603 -
2.604 -
2.605 -
2.606 -
2.607 -
2.608 -
2.609 - /**********************************************************************/
2.610 -
2.611 -
2.612 - //! \brief A structure for representing undirected path in a graph.
2.613 - //!
2.614 - //! A structure for representing undirected path in a graph. Ie. this is
2.615 - //! a path in a \e directed graph but the edges should not be directed
2.616 - //! forward.
2.617 - //!
2.618 - //! \param Graph The graph type in which the path is.
2.619 - //! \param DM DebugMode, defaults to DefaultDebugMode.
2.620 - //!
2.621 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
2.622 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
2.623 - //! and \c Edge of the original graph.
2.624 - //!
2.625 - //! \todo Thoroughfully check all the range and consistency tests.
2.626 - /// \todo May we need just path for undirected graph instead of this.
2.627 - template<typename Graph>
2.628 - class UPath {
2.629 - public:
2.630 - /// Edge type of the underlying graph.
2.631 - typedef typename Graph::Edge GraphEdge;
2.632 - /// Node type of the underlying graph.
2.633 - typedef typename Graph::Node GraphNode;
2.634 - class NodeIt;
2.635 - class EdgeIt;
2.636 -
2.637 - protected:
2.638 - const Graph *gr;
2.639 - typedef std::vector<GraphEdge> Container;
2.640 - Container edges;
2.641 -
2.642 - public:
2.643 -
2.644 - /// \param _G The graph in which the path is.
2.645 - ///
2.646 - UPath(const Graph &_G) : gr(&_G) {}
2.647 -
2.648 - /// \brief Subpath constructor.
2.649 - ///
2.650 - /// Subpath defined by two nodes.
2.651 - /// \warning It is an error if the two edges are not in order!
2.652 - UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
2.653 - gr = P.gr;
2.654 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.655 - }
2.656 -
2.657 - /// \brief Subpath constructor.
2.658 - ///
2.659 - /// Subpath defined by two edges. Contains edges in [a,b)
2.660 - /// \warning It is an error if the two edges are not in order!
2.661 - UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
2.662 - gr = P.gr;
2.663 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.664 - }
2.665 -
2.666 - /// Length of the path.
2.667 - size_t length() const { return edges.size(); }
2.668 - /// Returns whether the path is empty.
2.669 - bool empty() const { return edges.empty(); }
2.670 -
2.671 - /// Resets the path to an empty path.
2.672 - void clear() { edges.clear(); }
2.673 -
2.674 - /// \brief Starting point of the path.
2.675 - ///
2.676 - /// Starting point of the path.
2.677 - /// Returns INVALID if the path is empty.
2.678 - GraphNode source() const {
2.679 - return empty() ? INVALID : gr->source(edges[0]);
2.680 - }
2.681 - /// \brief End point of the path.
2.682 - ///
2.683 - /// End point of the path.
2.684 - /// Returns INVALID if the path is empty.
2.685 - GraphNode target() const {
2.686 - return empty() ? INVALID : gr->target(edges[length()-1]);
2.687 - }
2.688 -
2.689 - /// \brief Initializes node or edge iterator to point to the first
2.690 - /// node or edge.
2.691 - ///
2.692 - /// \sa nth
2.693 - template<typename It>
2.694 - It& first(It &i) const { return i=It(*this); }
2.695 -
2.696 - /// \brief Initializes node iterator to point to the node of a given index.
2.697 - NodeIt& nth(NodeIt &i, int n) const {
2.698 - return i=NodeIt(*this, n);
2.699 - }
2.700 -
2.701 - /// \brief Initializes edge iterator to point to the edge of a given index.
2.702 - EdgeIt& nth(EdgeIt &i, int n) const {
2.703 - return i=EdgeIt(*this, n);
2.704 - }
2.705 -
2.706 - /// Checks validity of a node or edge iterator.
2.707 - template<typename It>
2.708 - static
2.709 - bool valid(const It &i) { return i.valid(); }
2.710 -
2.711 - /// Steps the given node or edge iterator.
2.712 - template<typename It>
2.713 - static
2.714 - It& next(It &e) {
2.715 - return ++e;
2.716 - }
2.717 -
2.718 - /// \brief Returns node iterator pointing to the target node of the
2.719 - /// given edge iterator.
2.720 - NodeIt target(const EdgeIt& e) const {
2.721 - return NodeIt(*this, e.idx+1);
2.722 - }
2.723 -
2.724 - /// \brief Returns node iterator pointing to the source node of the
2.725 - /// given edge iterator.
2.726 - NodeIt source(const EdgeIt& e) const {
2.727 - return NodeIt(*this, e.idx);
2.728 - }
2.729 -
2.730 -
2.731 -
2.732 - /**
2.733 - * \brief Iterator class to iterate on the edges of the paths
2.734 - *
2.735 - * This class is used to iterate on the edges of the paths
2.736 - *
2.737 - * Of course it converts to Graph::Edge
2.738 - *
2.739 - * \todo Its interface differs from the standard edge iterator.
2.740 - * Yes, it shouldn't.
2.741 - */
2.742 - class EdgeIt {
2.743 - friend class UPath;
2.744 -
2.745 - int idx;
2.746 - const UPath *p;
2.747 - public:
2.748 - /// Default constructor
2.749 - EdgeIt() {}
2.750 - /// Invalid constructor
2.751 - EdgeIt(Invalid) : idx(-1), p(0) {}
2.752 - /// Constructor with starting point
2.753 - EdgeIt(const UPath &_p, int _idx = 0) :
2.754 - idx(_idx), p(&_p) { validate(); }
2.755 -
2.756 - ///Validity check
2.757 - bool valid() const { return idx!=-1; }
2.758 -
2.759 - ///Conversion to Graph::Edge
2.760 - operator GraphEdge () const {
2.761 - return valid() ? p->edges[idx] : INVALID;
2.762 - }
2.763 - /// Next edge
2.764 - EdgeIt& operator++() { ++idx; validate(); return *this; }
2.765 -
2.766 - /// Comparison operator
2.767 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.768 - /// Comparison operator
2.769 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.770 - /// Comparison operator
2.771 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.772 -
2.773 - private:
2.774 - // FIXME: comparison between signed and unsigned...
2.775 - // Jo ez igy? Vagy esetleg legyen a length() int?
2.776 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.777 - };
2.778 -
2.779 - /**
2.780 - * \brief Iterator class to iterate on the nodes of the paths
2.781 - *
2.782 - * This class is used to iterate on the nodes of the paths
2.783 - *
2.784 - * Of course it converts to Graph::Node
2.785 - *
2.786 - * \todo Its interface differs from the standard node iterator.
2.787 - * Yes, it shouldn't.
2.788 - */
2.789 - class NodeIt {
2.790 - friend class UPath;
2.791 -
2.792 - int idx;
2.793 - const UPath *p;
2.794 - public:
2.795 - /// Default constructor
2.796 - NodeIt() {}
2.797 - /// Invalid constructor
2.798 - NodeIt(Invalid) : idx(-1), p(0) {}
2.799 - /// Constructor with starting point
2.800 - NodeIt(const UPath &_p, int _idx = 0) :
2.801 - idx(_idx), p(&_p) { validate(); }
2.802 -
2.803 - ///Validity check
2.804 - bool valid() const { return idx!=-1; }
2.805 -
2.806 - ///Conversion to Graph::Node
2.807 - operator const GraphNode& () const {
2.808 - if(idx >= p->length())
2.809 - return p->target();
2.810 - else if(idx >= 0)
2.811 - return p->gr->source(p->edges[idx]);
2.812 - else
2.813 - return INVALID;
2.814 - }
2.815 - /// Next node
2.816 - NodeIt& operator++() { ++idx; validate(); return *this; }
2.817 -
2.818 - /// Comparison operator
2.819 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.820 - /// Comparison operator
2.821 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.822 - /// Comparison operator
2.823 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.824 -
2.825 - private:
2.826 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
2.827 - };
2.828 -
2.829 - friend class Builder;
2.830 -
2.831 - /**
2.832 - * \brief Class to build paths
2.833 - *
2.834 - * This class is used to fill a path with edges.
2.835 - *
2.836 - * You can push new edges to the front and to the back of the path in
2.837 - * arbitrary order then you should commit these changes to the graph.
2.838 - *
2.839 - * Fundamentally, for most "Paths" (classes fulfilling the
2.840 - * PathConcept) while the builder is active (after the first modifying
2.841 - * operation and until the commit()) the original Path is in a
2.842 - * "transitional" state (operations ot it have undefined result). But
2.843 - * in the case of UPath the original path is unchanged until the
2.844 - * commit. However we don't recomend that you use this feature.
2.845 - */
2.846 - class Builder {
2.847 - UPath &P;
2.848 - Container front, back;
2.849 -
2.850 - public:
2.851 - ///\param _p the path you want to fill in.
2.852 - ///
2.853 - Builder(UPath &_p) : P(_p) {}
2.854 -
2.855 - /// Sets the starting node of the path.
2.856 -
2.857 - /// Sets the starting node of the path. Edge added to the path
2.858 - /// afterwards have to be incident to this node.
2.859 - /// It should be called if and only if
2.860 - /// the path is empty and before any call to
2.861 - /// \ref pushFront() or \ref pushBack()
2.862 - void setStartNode(const GraphNode &) {}
2.863 -
2.864 - ///Push a new edge to the front of the path
2.865 -
2.866 - ///Push a new edge to the front of the path.
2.867 - ///\sa setStartNode
2.868 - void pushFront(const GraphEdge& e) {
2.869 - front.push_back(e);
2.870 - }
2.871 -
2.872 - ///Push a new edge to the back of the path
2.873 -
2.874 - ///Push a new edge to the back of the path.
2.875 - ///\sa setStartNode
2.876 - void pushBack(const GraphEdge& e) {
2.877 - back.push_back(e);
2.878 - }
2.879 -
2.880 - ///Commit the changes to the path.
2.881 - void commit() {
2.882 - if( !(front.empty() && back.empty()) ) {
2.883 - Container tmp;
2.884 - tmp.reserve(front.size()+back.size()+P.length());
2.885 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
2.886 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
2.887 - tmp.insert(tmp.end(), back.begin(), back.end());
2.888 - P.edges.swap(tmp);
2.889 - front.clear();
2.890 - back.clear();
2.891 - }
2.892 - }
2.893 -
2.894 -
2.895 - ///Reserve storage for the builder in advance.
2.896 -
2.897 - ///If you know a reasonable upper bound of the number of the edges
2.898 - ///to add to the front, using this function you can speed up the building.
2.899 -
2.900 - void reserveFront(size_t r) {front.reserve(r);}
2.901 -
2.902 - ///Reserve storage for the builder in advance.
2.903 -
2.904 - ///If you know a reasonable upper bound of the number of the edges
2.905 - ///to add to the back, using this function you can speed up the building.
2.906 -
2.907 - void reserveBack(size_t r) {back.reserve(r);}
2.908 -
2.909 - private:
2.910 - bool empty() {
2.911 - return front.empty() && back.empty() && P.empty();
2.912 - }
2.913 -
2.914 - GraphNode source() const {
2.915 - if( ! front.empty() )
2.916 - return P.gr->source(front[front.size()-1]);
2.917 - else if( ! P.empty() )
2.918 - return P.gr->source(P.edges[0]);
2.919 - else if( ! back.empty() )
2.920 - return P.gr->source(back[0]);
2.921 - else
2.922 - return INVALID;
2.923 - }
2.924 - GraphNode target() const {
2.925 - if( ! back.empty() )
2.926 - return P.gr->target(back[back.size()-1]);
2.927 - else if( ! P.empty() )
2.928 - return P.gr->target(P.edges[P.length()-1]);
2.929 - else if( ! front.empty() )
2.930 - return P.gr->target(front[0]);
2.931 - else
2.932 - return INVALID;
2.933 - }
2.934 -
2.935 - };
2.936 -
2.937 - };
2.938 -
2.939 -
2.940 ///@}
2.941
2.942 } // namespace lemon
3.1 --- a/test/bfs_test.cc Tue Oct 17 10:42:19 2006 +0000
3.2 +++ b/test/bfs_test.cc Tue Oct 17 10:50:57 2006 +0000
3.3 @@ -59,7 +59,7 @@
3.4 // pn = bfs_test.predNodeMap();
3.5 b = bfs_test.reached(n);
3.6
3.7 - DirPath<Graph> pp(G);
3.8 + Path<Graph> pp(G);
3.9 bfs_test.getPath(pp,n);
3.10 }
3.11
3.12 @@ -109,7 +109,7 @@
3.13
3.14 check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
3.15
3.16 - DirPath<Graph> p(G);
3.17 + Path<Graph> p(G);
3.18 check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
3.19 check(p.length()==3,"getPath() found a wrong path.");
3.20
4.1 --- a/test/dfs_test.cc Tue Oct 17 10:42:19 2006 +0000
4.2 +++ b/test/dfs_test.cc Tue Oct 17 10:50:57 2006 +0000
4.3 @@ -59,7 +59,7 @@
4.4 // pn = dfs_test.predNodeMap();
4.5 b = dfs_test.reached(n);
4.6
4.7 - DirPath<Graph> pp(G);
4.8 + Path<Graph> pp(G);
4.9 dfs_test.getPath(pp,n);
4.10 }
4.11
4.12 @@ -108,7 +108,7 @@
4.13 Dfs<Graph> dfs_test(G);
4.14 dfs_test.run(s);
4.15
4.16 - DirPath<Graph> p(G);
4.17 + Path<Graph> p(G);
4.18 check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
4.19 check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
4.20
5.1 --- a/test/dijkstra_test.cc Tue Oct 17 10:42:19 2006 +0000
5.2 +++ b/test/dijkstra_test.cc Tue Oct 17 10:50:57 2006 +0000
5.3 @@ -63,7 +63,7 @@
5.4 // pn = dijkstra_test.predNodeMap();
5.5 b = dijkstra_test.reached(n);
5.6
5.7 - DirPath<Graph> pp(G);
5.8 + Path<Graph> pp(G);
5.9 dijkstra_test.getPath(pp,n);
5.10 }
5.11
5.12 @@ -120,7 +120,7 @@
5.13 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
5.14
5.15
5.16 - DirPath<Graph> p(G);
5.17 + Path<Graph> p(G);
5.18 check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
5.19 check(p.length()==4,"getPath() found a wrong path.");
5.20
6.1 --- a/test/path_test.cc Tue Oct 17 10:42:19 2006 +0000
6.2 +++ b/test/path_test.cc Tue Oct 17 10:50:57 2006 +0000
6.3 @@ -18,81 +18,91 @@
6.4
6.5 #include <string>
6.6 #include <iostream>
6.7 +
6.8 #include <lemon/concept/path.h>
6.9 +#include <lemon/concept/graph.h>
6.10 +
6.11 #include <lemon/path.h>
6.12 #include <lemon/list_graph.h>
6.13
6.14 +#include "test_tools.h"
6.15 +
6.16 using namespace std;
6.17 using namespace lemon;
6.18 -using namespace lemon::concept;
6.19
6.20 -template<class Path> void checkCompilePath(Path &P)
6.21 -{
6.22 - typedef typename Path::EdgeIt EdgeIt;
6.23 - typedef typename Path::NodeIt NodeIt;
6.24 - typedef typename Path::GraphNode GraphNode;
6.25 - typedef typename Path::GraphEdge GraphEdge;
6.26 - //typedef typename Path::Builder Builder;
6.27 - //??? ha csinalok ilyet es siman Builderrel peldanyositok, akkor warningol. Talan friend miatt? De ki az?
6.28 -
6.29 - EdgeIt ei;
6.30 - NodeIt ni;
6.31 - GraphNode gn;
6.32 - GraphEdge ge;
6.33 -
6.34 - size_t st;
6.35 - bool b;
6.36 -
6.37 - //Path(const Graph &_G) {} //the constructor has been already called
6.38 -
6.39 - st=P.length(); //size_t length() const {return 0;}
6.40 - b=P.empty(); //bool empty() const {}
6.41 - P.clear(); //void clear() {}
6.42 -
6.43 - gn=P.target(); //GraphNode/*It*/ target() const {return INVALID;}
6.44 - gn=P.source(); //GraphNode/*It*/ source() const {return INVALID;}
6.45 -
6.46 - ei=P.first(ei); //It& first(It &i) const { return i=It(*this); }
6.47 -
6.48 - ni=P.target(ei); //NodeIt target(const EdgeIt& e) const {}
6.49 - ni=P.source(ei); //NodeIt source(const EdgeIt& e) const {}
6.50 -
6.51 -
6.52 - ListGraph lg;
6.53 - Path p(lg);
6.54 -
6.55 - EdgeIt i; //EdgeIt() {}
6.56 - EdgeIt j(INVALID); //EdgeIt(Invalid) {}
6.57 - EdgeIt k(p); //EdgeIt(const Path &_p) {}
6.58 -
6.59 - i=++j; //EdgeIt& operator++() {}
6.60 - ++k;
6.61 - b=(i==j); //bool operator==(const EdgeIt& e) const {return true;}
6.62 - b=(i!=j); //bool operator!=(const EdgeIt& e) const {return true;}
6.63 -
6.64 -
6.65 - NodeIt l; //NodeIt() {}
6.66 - NodeIt m(INVALID); //NodeIt(Invalid) {}
6.67 - NodeIt n(p); //NodeIt(const Path &_p) {}
6.68 -
6.69 - l=++m; //NodeIt& operator++() {}
6.70 - b=(m==n); //bool operator==(const NodeIt& e) const {}
6.71 - b=(m!=n); //bool operator!=(const NodeIt& e) const {}
6.72 -
6.73 - typename Path::Builder builder(p); //Builder(Path &_P) : P(_P) {}
6.74 - builder.setStartNode(gn); //void setStartNode(const GraphNode &) {}
6.75 - builder.pushFront(ge); //void pushFront(const GraphEdge& e) {}
6.76 - builder.pushBack(ge); //void pushBack(const GraphEdge& e) {}
6.77 - builder.commit(); //void commit() {}
6.78 - builder.reserveFront(st); //void reserveFront(size_t r) {}
6.79 - builder.reserveBack(st); //void reserveBack(size_t r) {}
6.80 -
6.81 +void check_concepts() {
6.82 + checkConcept<concept::Path<concept::Graph>,
6.83 + concept::Path<concept::Graph> >();
6.84 + checkConcept<concept::Path<concept::Graph>,
6.85 + Path<concept::Graph> >();
6.86 + checkConcept<concept::Path<ListGraph>, Path<ListGraph> >();
6.87 }
6.88
6.89 -template void checkCompilePath< concept::Path<ListGraph> >(concept::Path<ListGraph> &);
6.90 -template void checkCompilePath< DirPath<ListGraph> >(DirPath<ListGraph> &);
6.91 -template void checkCompilePath< UPath<ListGraph> >(UPath<ListGraph> &);
6.92 +int main() {
6.93 + check_concepts();
6.94 +
6.95 + ListGraph g;
6.96 +
6.97 + ListGraph::Node n1 = g.addNode();
6.98 + ListGraph::Node n2 = g.addNode();
6.99 + ListGraph::Node n3 = g.addNode();
6.100 + ListGraph::Node n4 = g.addNode();
6.101 + ListGraph::Node n5 = g.addNode();
6.102 +
6.103 + ListGraph::Edge e1 = g.addEdge(n1, n2);
6.104 + ListGraph::Edge e2 = g.addEdge(n2, n3);
6.105 + ListGraph::Edge e3 = g.addEdge(n3, n4);
6.106 + ListGraph::Edge e4 = g.addEdge(n4, n5);
6.107 + ListGraph::Edge e5 = g.addEdge(n5, n1);
6.108
6.109 -int main()
6.110 -{
6.111 + {
6.112 + Path<ListGraph> p(g);
6.113 +
6.114 + check(p.empty(), "Wrong Path");
6.115 + check(p.length() == 0, "Wrong Path");
6.116 +
6.117 + {
6.118 + Path<ListGraph>::Builder b(p);
6.119 + b.setStartNode(n3);
6.120 + b.commit();
6.121 + }
6.122 +
6.123 + check(!p.empty(), "Wrong Path");
6.124 + check(p.length() == 0, "Wrong Path");
6.125 + check(p.source() == n3, "Wrong Path");
6.126 + check(p.target() == n3, "Wrong Path");
6.127 +
6.128 + {
6.129 + Path<ListGraph>::Builder b(p);
6.130 + b.pushBack(e3);
6.131 + b.pushBack(e4);
6.132 + b.pushFront(e2);
6.133 + b.commit();
6.134 + }
6.135 +
6.136 + check(!p.empty(), "Wrong Path");
6.137 + check(p.length() == 3, "Wrong Path");
6.138 + check(p.source() == n2, "Wrong Path");
6.139 + check(p.target() == n5, "Wrong Path");
6.140 +
6.141 + {
6.142 + Path<ListGraph>::NodeIt it(p);
6.143 + check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
6.144 + check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
6.145 + check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
6.146 + check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
6.147 + check((ListGraph::Node)it == INVALID, "Wrong Path");
6.148 + }
6.149 +
6.150 + {
6.151 + Path<ListGraph>::EdgeIt it(p);
6.152 + check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
6.153 + check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
6.154 + check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
6.155 + check((ListGraph::Edge)it == INVALID, "Wrong Path");
6.156 + }
6.157 +
6.158 + }
6.159 +
6.160 + return 0;
6.161 }