1.1 --- a/lemon/path.h Tue Oct 17 10:42:19 2006 +0000
1.2 +++ b/lemon/path.h Tue Oct 17 10:50:57 2006 +0000
1.3 @@ -21,15 +21,14 @@
1.4 ///\file
1.5 ///\brief Classes for representing paths in graphs.
1.6 ///
1.7 -///\todo Iterators have obsolete style
1.8
1.9 #ifndef LEMON_PATH_H
1.10 #define LEMON_PATH_H
1.11
1.12 -#include <deque>
1.13 #include <vector>
1.14 #include <algorithm>
1.15
1.16 +#include <lemon/error.h>
1.17 #include <lemon/bits/invalid.h>
1.18
1.19 namespace lemon {
1.20 @@ -42,7 +41,6 @@
1.21 //!
1.22 //! A structure for representing directed path in a graph.
1.23 //! \param Graph The graph type in which the path is.
1.24 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.25 //!
1.26 //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.27 //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.28 @@ -50,640 +48,383 @@
1.29 //!
1.30 //! \todo Thoroughfully check all the range and consistency tests.
1.31 template<typename Graph>
1.32 - class DirPath {
1.33 + class Path {
1.34 public:
1.35 /// Edge type of the underlying graph.
1.36 - typedef typename Graph::Edge GraphEdge;
1.37 + typedef typename Graph::Edge Edge;
1.38 /// Node type of the underlying graph.
1.39 - typedef typename Graph::Node GraphNode;
1.40 + typedef typename Graph::Node Node;
1.41 +
1.42 class NodeIt;
1.43 class EdgeIt;
1.44
1.45 - protected:
1.46 - const Graph *gr;
1.47 - typedef std::vector<GraphEdge> Container;
1.48 - Container edges;
1.49 + struct PathError : public LogicError {
1.50 + virtual const char* what() const throw() {
1.51 + return "lemon::PathError";
1.52 + }
1.53 + };
1.54
1.55 public:
1.56
1.57 + /// \brief Constructor
1.58 + ///
1.59 + /// Constructor
1.60 /// \param _G The graph in which the path is.
1.61 - ///
1.62 - DirPath(const Graph &_G) : gr(&_G) {}
1.63 -
1.64 + Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
1.65 +
1.66 /// \brief Subpath constructor.
1.67 ///
1.68 /// Subpath defined by two nodes.
1.69 /// \warning It is an error if the two edges are not in order!
1.70 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.71 - gr = P.gr;
1.72 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.73 + Path(const Path &other, const NodeIt &a, const NodeIt &b) {
1.74 + graph = other.graph;
1.75 + start = a;
1.76 + edges.insert(edges.end(),
1.77 + other.edges.begin() + a.id, other.edges.begin() + b.id);
1.78 }
1.79
1.80 /// \brief Subpath constructor.
1.81 ///
1.82 /// Subpath defined by two edges. Contains edges in [a,b)
1.83 /// \warning It is an error if the two edges are not in order!
1.84 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.85 - gr = P.gr;
1.86 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.87 + Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
1.88 + graph = other.graph;
1.89 + start = graph->source(a);
1.90 + edges.insert(edges.end(),
1.91 + other.edges.begin() + a.id, other.edges.begin() + b.id);
1.92 }
1.93
1.94 - /// Length of the path.
1.95 + /// \brief Length of the path.
1.96 + ///
1.97 + /// The number of the edges in the path. It can be zero if the
1.98 + /// path has only one node or it is empty.
1.99 int length() const { return edges.size(); }
1.100 - /// Returns whether the path is empty.
1.101 - bool empty() const { return edges.empty(); }
1.102
1.103 + /// \brief Returns whether the path is empty.
1.104 + ///
1.105 + /// Returns true when the path does not contain neither edge nor
1.106 + /// node.
1.107 + bool empty() const { return start == INVALID; }
1.108 +
1.109 + /// \brief Resets the path to an empty path.
1.110 + ///
1.111 /// Resets the path to an empty path.
1.112 - void clear() { edges.clear(); }
1.113 + void clear() { edges.clear(); start = INVALID; }
1.114
1.115 /// \brief Starting point of the path.
1.116 ///
1.117 /// Starting point of the path.
1.118 /// Returns INVALID if the path is empty.
1.119 - GraphNode source() const {
1.120 - return empty() ? INVALID : gr->source(edges[0]);
1.121 + Node source() const {
1.122 + return start;
1.123 }
1.124 /// \brief End point of the path.
1.125 ///
1.126 /// End point of the path.
1.127 /// Returns INVALID if the path is empty.
1.128 - GraphNode target() const {
1.129 - return empty() ? INVALID : gr->target(edges[length()-1]);
1.130 + Node target() const {
1.131 + return length() == 0 ? start : graph->target(edges[length()-1]);
1.132 }
1.133
1.134 - /// \brief Initializes node or edge iterator to point to the first
1.135 - /// node or edge.
1.136 + /// \brief Gives back a node iterator to point to the node of a
1.137 + /// given index.
1.138 ///
1.139 - /// \sa nth
1.140 - template<typename It>
1.141 - It& first(It &i) const { return i=It(*this); }
1.142 -
1.143 - /// \brief Initializes node iterator to point to the node of a given index.
1.144 - NodeIt& nth(NodeIt &i, int n) const {
1.145 - return i=NodeIt(*this, n);
1.146 + /// Gives back a node iterator to point to the node of a given
1.147 + /// index.
1.148 + /// \pre n should less or equal to \c length()
1.149 + NodeIt nthNode(int n) const {
1.150 + return NodeIt(*this, n);
1.151 }
1.152
1.153 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.154 - EdgeIt& nth(EdgeIt &i, int n) const {
1.155 - return i=EdgeIt(*this, n);
1.156 + /// \brief Gives back an edge iterator to point to the edge of a
1.157 + /// given index.
1.158 + ///
1.159 + /// Gives back an edge iterator to point to the node of a given
1.160 + /// index.
1.161 + /// \pre n should less than \c length()
1.162 + EdgeIt nthEdge(int n) const {
1.163 + return EdgeIt(*this, n);
1.164 + }
1.165 +
1.166 + /// \brief Returns node iterator pointing to the source node of the
1.167 + /// given edge iterator.
1.168 + ///
1.169 + /// Returns node iterator pointing to the source node of the given
1.170 + /// edge iterator.
1.171 + NodeIt source(const EdgeIt& e) const {
1.172 + return NodeIt(*this, e.id);
1.173 }
1.174
1.175 /// \brief Returns node iterator pointing to the target node of the
1.176 /// given edge iterator.
1.177 + ///
1.178 + /// Returns node iterator pointing to the target node of the given
1.179 + /// edge iterator.
1.180 NodeIt target(const EdgeIt& e) const {
1.181 - return NodeIt(*this, e.idx+1);
1.182 + return NodeIt(*this, e.id + 1);
1.183 }
1.184
1.185 - /// \brief Returns node iterator pointing to the source node of the
1.186 - /// given edge iterator.
1.187 - NodeIt source(const EdgeIt& e) const {
1.188 - return NodeIt(*this, e.idx);
1.189 - }
1.190
1.191 + /// \brief Iterator class to iterate on the nodes of the paths
1.192 + ///
1.193 + /// This class is used to iterate on the nodes of the paths
1.194 + ///
1.195 + /// Of course it converts to Graph::Node
1.196 + class NodeIt {
1.197 + friend class Path;
1.198 + public:
1.199
1.200 - /* Iterator classes */
1.201 + /// \brief Default constructor
1.202 + ///
1.203 + /// Default constructor
1.204 + NodeIt() {}
1.205
1.206 - /**
1.207 - * \brief Iterator class to iterate on the edges of the paths
1.208 - *
1.209 - * This class is used to iterate on the edges of the paths
1.210 - *
1.211 - * Of course it converts to Graph::Edge
1.212 - *
1.213 - */
1.214 + /// \brief Invalid constructor
1.215 + ///
1.216 + /// Invalid constructor
1.217 + NodeIt(Invalid) : id(-1), path(0) {}
1.218 +
1.219 + /// \brief Constructor with starting point
1.220 + ///
1.221 + /// Constructor with starting point
1.222 + NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
1.223 + if (id > path->length()) id = -1;
1.224 + }
1.225 +
1.226 + /// \brief Conversion to Graph::Node
1.227 + ///
1.228 + /// Conversion to Graph::Node
1.229 + operator Node() const {
1.230 + if (id > 0) {
1.231 + return path->graph->target(path->edges[id - 1]);
1.232 + } else if (id == 0) {
1.233 + return path->start;
1.234 + } else {
1.235 + return INVALID;
1.236 + }
1.237 + }
1.238 +
1.239 + /// \brief Steps to the next node
1.240 + ///
1.241 + /// Steps to the next node
1.242 + NodeIt& operator++() {
1.243 + ++id;
1.244 + if (id > path->length()) id = -1;
1.245 + return *this;
1.246 + }
1.247 +
1.248 + /// \brief Comparison operator
1.249 + ///
1.250 + /// Comparison operator
1.251 + bool operator==(const NodeIt& n) const { return id == n.id; }
1.252 +
1.253 + /// \brief Comparison operator
1.254 + ///
1.255 + /// Comparison operator
1.256 + bool operator!=(const NodeIt& n) const { return id != n.id; }
1.257 +
1.258 + /// \brief Comparison operator
1.259 + ///
1.260 + /// Comparison operator
1.261 + bool operator<(const NodeIt& n) const { return id < n.id; }
1.262 +
1.263 + private:
1.264 + int id;
1.265 + const Path *path;
1.266 + };
1.267 +
1.268 + /// \brief Iterator class to iterate on the edges of the paths
1.269 + ///
1.270 + /// This class is used to iterate on the edges of the paths
1.271 + /// Of course it converts to Graph::Edge
1.272 class EdgeIt {
1.273 - friend class DirPath;
1.274 + friend class Path;
1.275 + public:
1.276
1.277 - int idx;
1.278 - const DirPath *p;
1.279 - public:
1.280 + /// \brief Default constructor
1.281 + ///
1.282 /// Default constructor
1.283 EdgeIt() {}
1.284 +
1.285 + /// \brief Invalid constructor
1.286 + ///
1.287 /// Invalid constructor
1.288 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.289 + EdgeIt(Invalid) : id(-1), path(0) {}
1.290 +
1.291 + /// \brief Constructor with starting point
1.292 + ///
1.293 /// Constructor with starting point
1.294 - EdgeIt(const DirPath &_p, int _idx = 0) :
1.295 - idx(_idx), p(&_p) { validate(); }
1.296 -
1.297 - ///Validity check
1.298 - bool valid() const { return idx!=-1; }
1.299 -
1.300 - ///Conversion to Graph::Edge
1.301 - operator GraphEdge () const {
1.302 - return valid() ? p->edges[idx] : INVALID;
1.303 + EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
1.304 + if (id >= path->length()) id = -1;
1.305 }
1.306
1.307 - /// Next edge
1.308 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.309 + /// \brief Conversion to Graph::Edge
1.310 + ///
1.311 + /// Conversion to Graph::Edge
1.312 + operator Edge() const {
1.313 + return id != -1 ? path->edges[id] : INVALID;
1.314 + }
1.315
1.316 + /// \brief Steps to the next edge
1.317 + ///
1.318 + /// Steps to the next edge
1.319 + EdgeIt& operator++() {
1.320 + ++id;
1.321 + if (id >= path->length()) id = -1;
1.322 + return *this;
1.323 + }
1.324 +
1.325 + /// \brief Comparison operator
1.326 + ///
1.327 /// Comparison operator
1.328 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.329 + bool operator==(const EdgeIt& e) const { return id == e.id; }
1.330 +
1.331 + /// \brief Comparison operator
1.332 + ///
1.333 /// Comparison operator
1.334 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.335 + bool operator!=(const EdgeIt& e) const { return id != e.id; }
1.336 +
1.337 + /// \brief Comparison operator
1.338 + ///
1.339 /// Comparison operator
1.340 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.341 + bool operator<(const EdgeIt& e) const { return id < e.id; }
1.342
1.343 private:
1.344 - void validate() { if(idx >= p->length() ) idx=-1; }
1.345 +
1.346 + int id;
1.347 + const Path *path;
1.348 };
1.349
1.350 - /**
1.351 - * \brief Iterator class to iterate on the nodes of the paths
1.352 - *
1.353 - * This class is used to iterate on the nodes of the paths
1.354 - *
1.355 - * Of course it converts to Graph::Node
1.356 - *
1.357 - */
1.358 - class NodeIt {
1.359 - friend class DirPath;
1.360 + protected:
1.361
1.362 - int idx;
1.363 - const DirPath *p;
1.364 - public:
1.365 - /// Default constructor
1.366 - NodeIt() {}
1.367 - /// Invalid constructor
1.368 - NodeIt(Invalid) : idx(-1), p(0) {}
1.369 - /// Constructor with starting point
1.370 - NodeIt(const DirPath &_p, int _idx = 0) :
1.371 - idx(_idx), p(&_p) { validate(); }
1.372 + const Graph *graph;
1.373
1.374 - ///Validity check
1.375 - bool valid() const { return idx!=-1; }
1.376 + typedef std::vector<Edge> Container;
1.377 + Container edges;
1.378 + Node start;
1.379
1.380 - ///Conversion to Graph::Node
1.381 - operator GraphNode () const {
1.382 - if(idx >= p->length())
1.383 - return p->target();
1.384 - else if(idx >= 0)
1.385 - return p->gr->source(p->edges[idx]);
1.386 - else
1.387 - return INVALID;
1.388 - }
1.389 - /// Next node
1.390 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.391 -
1.392 - /// Comparison operator
1.393 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.394 - /// Comparison operator
1.395 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.396 - /// Comparison operator
1.397 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.398 -
1.399 - private:
1.400 - void validate() { if(idx > p->length() ) idx=-1; }
1.401 - };
1.402 + public:
1.403
1.404 friend class Builder;
1.405
1.406 - /**
1.407 - * \brief Class to build paths
1.408 - *
1.409 - * This class is used to fill a path with edges.
1.410 - *
1.411 - * You can push new edges to the front and to the back of the path in
1.412 - * arbitrary order then you should commit these changes to the graph.
1.413 - *
1.414 - * Fundamentally, for most "Paths" (classes fulfilling the
1.415 - * PathConcept) while the builder is active (after the first modifying
1.416 - * operation and until the commit()) the original Path is in a
1.417 - * "transitional" state (operations on it have undefined result). But
1.418 - * in the case of DirPath the original path remains unchanged until the
1.419 - * commit. However we don't recomend that you use this feature.
1.420 - */
1.421 + /// \brief Class to build paths
1.422 + ///
1.423 + /// This class is used to fill a path with edges.
1.424 + ///
1.425 + /// You can push new edges to the front and to the back of the
1.426 + /// path in arbitrary order then you should commit these changes
1.427 + /// to the graph.
1.428 + ///
1.429 + /// Fundamentally, for most "Paths" (classes fulfilling the
1.430 + /// PathConcept) while the builder is active (after the first
1.431 + /// modifying operation and until the commit()) the original Path
1.432 + /// is in a "transitional" state (operations on it have undefined
1.433 + /// result). But in the case of Path the original path remains
1.434 + /// unchanged until the commit. However we don't recomend that you
1.435 + /// use this feature.
1.436 class Builder {
1.437 - DirPath &P;
1.438 - Container front, back;
1.439 + public:
1.440 + /// \brief Constructor
1.441 + ///
1.442 + /// Constructor
1.443 + /// \param _path the path you want to fill in.
1.444 + Builder(Path &_path) : path(_path), start(INVALID) {}
1.445
1.446 - public:
1.447 - ///\param _p the path you want to fill in.
1.448 + /// \brief Destructor
1.449 ///
1.450 - Builder(DirPath &_p) : P(_p) {}
1.451 + /// Destructor
1.452 + ~Builder() {
1.453 + LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
1.454 + PathError());
1.455 + }
1.456
1.457 - /// Sets the starting node of the path.
1.458 + /// \brief Sets the starting node of the path.
1.459 + ///
1.460 + /// Sets the starting node of the path. Edge added to the path
1.461 + /// afterwards have to be incident to this node. It should be
1.462 + /// called if and only if the path is empty and before any call
1.463 + /// to \ref pushFront() or \ref pushBack()
1.464 + void setStartNode(const Node &_start) {
1.465 + LEMON_ASSERT(path.empty() && start == INVALID, PathError());
1.466 + start = _start;
1.467 + }
1.468
1.469 - /// Sets the starting node of the path. Edge added to the path
1.470 - /// afterwards have to be incident to this node.
1.471 - /// It should be called if and only if
1.472 - /// the path is empty and before any call to
1.473 - /// \ref pushFront() or \ref pushBack()
1.474 - void setStartNode(const GraphNode &) {}
1.475 -
1.476 - ///Push a new edge to the front of the path
1.477 -
1.478 - ///Push a new edge to the front of the path.
1.479 - ///\sa setStartNode
1.480 - void pushFront(const GraphEdge& e) {
1.481 + /// \brief Push a new edge to the front of the path
1.482 + ///
1.483 + /// Push a new edge to the front of the path.
1.484 + /// \sa setStartNode
1.485 + void pushFront(const Edge& e) {
1.486 + LEMON_ASSERT(front.empty() ||
1.487 + (path.graph->source(front.back()) ==
1.488 + path.graph->target(e)), PathError());
1.489 + LEMON_ASSERT(path.empty() ||
1.490 + (path.source() == path.graph->target(e)), PathError());
1.491 + LEMON_ASSERT(!path.empty() || !front.empty() ||
1.492 + (start == path.graph->target(e)), PathError());
1.493 front.push_back(e);
1.494 }
1.495
1.496 - ///Push a new edge to the back of the path
1.497 -
1.498 - ///Push a new edge to the back of the path.
1.499 - ///\sa setStartNode
1.500 - void pushBack(const GraphEdge& e) {
1.501 + /// \brief Push a new edge to the back of the path
1.502 + ///
1.503 + /// Push a new edge to the back of the path.
1.504 + /// \sa setStartNode
1.505 + void pushBack(const Edge& e) {
1.506 + LEMON_ASSERT(back.empty() ||
1.507 + (path.graph->target(back.back()) ==
1.508 + path.graph->source(e)), PathError());
1.509 + LEMON_ASSERT(path.empty() ||
1.510 + (path.target() == path.graph->source(e)), PathError());
1.511 + LEMON_ASSERT(!path.empty() || !back.empty() ||
1.512 + (start == path.graph->source(e)), PathError());
1.513 back.push_back(e);
1.514 }
1.515
1.516 - ///Commit the changes to the path.
1.517 + /// \brief Commit the changes to the path.
1.518 + ///
1.519 + /// Commit the changes to the path.
1.520 void commit() {
1.521 - if( !front.empty() || !back.empty() ) {
1.522 + if( !front.empty() || !back.empty() || start != INVALID) {
1.523 Container tmp;
1.524 - tmp.reserve(front.size()+back.size()+P.length());
1.525 + tmp.reserve(front.size() + back.size() + path.length());
1.526 tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.527 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.528 + tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
1.529 tmp.insert(tmp.end(), back.begin(), back.end());
1.530 - P.edges.swap(tmp);
1.531 + path.edges.swap(tmp);
1.532 + if (!front.empty()) {
1.533 + path.start = path.graph->source(front.back());
1.534 + } else {
1.535 + path.start = start;
1.536 + }
1.537 + start = INVALID;
1.538 front.clear();
1.539 back.clear();
1.540 }
1.541 }
1.542
1.543 - ///Reserve storage for the builder in advance.
1.544 -
1.545 - ///If you know a reasonable upper bound of the number of the edges
1.546 - ///to add to the front, using this function you can speed up the building.
1.547 -
1.548 + /// \brief Reserve storage for the builder in advance.
1.549 + ///
1.550 + /// If you know a reasonable upper bound of the number of the
1.551 + /// edges to add to the front, using this function you can speed
1.552 + /// up the building.
1.553 void reserveFront(size_t r) {front.reserve(r);}
1.554
1.555 - ///Reserve storage for the builder in advance.
1.556 -
1.557 - ///If you know a reasonable upper bound of the number of the edges
1.558 - ///to add to the back, using this function you can speed up the building.
1.559 -
1.560 + /// \brief Reserve storage for the builder in advance.
1.561 + ///
1.562 + /// If you know a reasonable upper bound of the number of the
1.563 + /// edges to add to the back, using this function you can speed
1.564 + /// up the building.
1.565 void reserveBack(size_t r) {back.reserve(r);}
1.566
1.567 private:
1.568 - bool empty() {
1.569 - return front.empty() && back.empty() && P.empty();
1.570 - }
1.571
1.572 - GraphNode source() const {
1.573 - if( ! front.empty() )
1.574 - return P.gr->source(front[front.size()-1]);
1.575 - else if( ! P.empty() )
1.576 - return P.gr->source(P.edges[0]);
1.577 - else if( ! back.empty() )
1.578 - return P.gr->source(back[0]);
1.579 - else
1.580 - return INVALID;
1.581 - }
1.582 - GraphNode target() const {
1.583 - if( ! back.empty() )
1.584 - return P.gr->target(back[back.size()-1]);
1.585 - else if( ! P.empty() )
1.586 - return P.gr->target(P.edges[P.length()-1]);
1.587 - else if( ! front.empty() )
1.588 - return P.gr->target(front[0]);
1.589 - else
1.590 - return INVALID;
1.591 - }
1.592 + Path &path;
1.593 + Container front, back;
1.594 + Node start;
1.595
1.596 };
1.597
1.598 };
1.599
1.600 -
1.601 -
1.602 -
1.603 -
1.604 -
1.605 -
1.606 -
1.607 -
1.608 -
1.609 - /**********************************************************************/
1.610 -
1.611 -
1.612 - //! \brief A structure for representing undirected path in a graph.
1.613 - //!
1.614 - //! A structure for representing undirected path in a graph. Ie. this is
1.615 - //! a path in a \e directed graph but the edges should not be directed
1.616 - //! forward.
1.617 - //!
1.618 - //! \param Graph The graph type in which the path is.
1.619 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.620 - //!
1.621 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.622 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.623 - //! and \c Edge of the original graph.
1.624 - //!
1.625 - //! \todo Thoroughfully check all the range and consistency tests.
1.626 - /// \todo May we need just path for undirected graph instead of this.
1.627 - template<typename Graph>
1.628 - class UPath {
1.629 - public:
1.630 - /// Edge type of the underlying graph.
1.631 - typedef typename Graph::Edge GraphEdge;
1.632 - /// Node type of the underlying graph.
1.633 - typedef typename Graph::Node GraphNode;
1.634 - class NodeIt;
1.635 - class EdgeIt;
1.636 -
1.637 - protected:
1.638 - const Graph *gr;
1.639 - typedef std::vector<GraphEdge> Container;
1.640 - Container edges;
1.641 -
1.642 - public:
1.643 -
1.644 - /// \param _G The graph in which the path is.
1.645 - ///
1.646 - UPath(const Graph &_G) : gr(&_G) {}
1.647 -
1.648 - /// \brief Subpath constructor.
1.649 - ///
1.650 - /// Subpath defined by two nodes.
1.651 - /// \warning It is an error if the two edges are not in order!
1.652 - UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
1.653 - gr = P.gr;
1.654 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.655 - }
1.656 -
1.657 - /// \brief Subpath constructor.
1.658 - ///
1.659 - /// Subpath defined by two edges. Contains edges in [a,b)
1.660 - /// \warning It is an error if the two edges are not in order!
1.661 - UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
1.662 - gr = P.gr;
1.663 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.664 - }
1.665 -
1.666 - /// Length of the path.
1.667 - size_t length() const { return edges.size(); }
1.668 - /// Returns whether the path is empty.
1.669 - bool empty() const { return edges.empty(); }
1.670 -
1.671 - /// Resets the path to an empty path.
1.672 - void clear() { edges.clear(); }
1.673 -
1.674 - /// \brief Starting point of the path.
1.675 - ///
1.676 - /// Starting point of the path.
1.677 - /// Returns INVALID if the path is empty.
1.678 - GraphNode source() const {
1.679 - return empty() ? INVALID : gr->source(edges[0]);
1.680 - }
1.681 - /// \brief End point of the path.
1.682 - ///
1.683 - /// End point of the path.
1.684 - /// Returns INVALID if the path is empty.
1.685 - GraphNode target() const {
1.686 - return empty() ? INVALID : gr->target(edges[length()-1]);
1.687 - }
1.688 -
1.689 - /// \brief Initializes node or edge iterator to point to the first
1.690 - /// node or edge.
1.691 - ///
1.692 - /// \sa nth
1.693 - template<typename It>
1.694 - It& first(It &i) const { return i=It(*this); }
1.695 -
1.696 - /// \brief Initializes node iterator to point to the node of a given index.
1.697 - NodeIt& nth(NodeIt &i, int n) const {
1.698 - return i=NodeIt(*this, n);
1.699 - }
1.700 -
1.701 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.702 - EdgeIt& nth(EdgeIt &i, int n) const {
1.703 - return i=EdgeIt(*this, n);
1.704 - }
1.705 -
1.706 - /// Checks validity of a node or edge iterator.
1.707 - template<typename It>
1.708 - static
1.709 - bool valid(const It &i) { return i.valid(); }
1.710 -
1.711 - /// Steps the given node or edge iterator.
1.712 - template<typename It>
1.713 - static
1.714 - It& next(It &e) {
1.715 - return ++e;
1.716 - }
1.717 -
1.718 - /// \brief Returns node iterator pointing to the target node of the
1.719 - /// given edge iterator.
1.720 - NodeIt target(const EdgeIt& e) const {
1.721 - return NodeIt(*this, e.idx+1);
1.722 - }
1.723 -
1.724 - /// \brief Returns node iterator pointing to the source node of the
1.725 - /// given edge iterator.
1.726 - NodeIt source(const EdgeIt& e) const {
1.727 - return NodeIt(*this, e.idx);
1.728 - }
1.729 -
1.730 -
1.731 -
1.732 - /**
1.733 - * \brief Iterator class to iterate on the edges of the paths
1.734 - *
1.735 - * This class is used to iterate on the edges of the paths
1.736 - *
1.737 - * Of course it converts to Graph::Edge
1.738 - *
1.739 - * \todo Its interface differs from the standard edge iterator.
1.740 - * Yes, it shouldn't.
1.741 - */
1.742 - class EdgeIt {
1.743 - friend class UPath;
1.744 -
1.745 - int idx;
1.746 - const UPath *p;
1.747 - public:
1.748 - /// Default constructor
1.749 - EdgeIt() {}
1.750 - /// Invalid constructor
1.751 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.752 - /// Constructor with starting point
1.753 - EdgeIt(const UPath &_p, int _idx = 0) :
1.754 - idx(_idx), p(&_p) { validate(); }
1.755 -
1.756 - ///Validity check
1.757 - bool valid() const { return idx!=-1; }
1.758 -
1.759 - ///Conversion to Graph::Edge
1.760 - operator GraphEdge () const {
1.761 - return valid() ? p->edges[idx] : INVALID;
1.762 - }
1.763 - /// Next edge
1.764 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.765 -
1.766 - /// Comparison operator
1.767 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.768 - /// Comparison operator
1.769 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.770 - /// Comparison operator
1.771 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.772 -
1.773 - private:
1.774 - // FIXME: comparison between signed and unsigned...
1.775 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.776 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.777 - };
1.778 -
1.779 - /**
1.780 - * \brief Iterator class to iterate on the nodes of the paths
1.781 - *
1.782 - * This class is used to iterate on the nodes of the paths
1.783 - *
1.784 - * Of course it converts to Graph::Node
1.785 - *
1.786 - * \todo Its interface differs from the standard node iterator.
1.787 - * Yes, it shouldn't.
1.788 - */
1.789 - class NodeIt {
1.790 - friend class UPath;
1.791 -
1.792 - int idx;
1.793 - const UPath *p;
1.794 - public:
1.795 - /// Default constructor
1.796 - NodeIt() {}
1.797 - /// Invalid constructor
1.798 - NodeIt(Invalid) : idx(-1), p(0) {}
1.799 - /// Constructor with starting point
1.800 - NodeIt(const UPath &_p, int _idx = 0) :
1.801 - idx(_idx), p(&_p) { validate(); }
1.802 -
1.803 - ///Validity check
1.804 - bool valid() const { return idx!=-1; }
1.805 -
1.806 - ///Conversion to Graph::Node
1.807 - operator const GraphNode& () const {
1.808 - if(idx >= p->length())
1.809 - return p->target();
1.810 - else if(idx >= 0)
1.811 - return p->gr->source(p->edges[idx]);
1.812 - else
1.813 - return INVALID;
1.814 - }
1.815 - /// Next node
1.816 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.817 -
1.818 - /// Comparison operator
1.819 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.820 - /// Comparison operator
1.821 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.822 - /// Comparison operator
1.823 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.824 -
1.825 - private:
1.826 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.827 - };
1.828 -
1.829 - friend class Builder;
1.830 -
1.831 - /**
1.832 - * \brief Class to build paths
1.833 - *
1.834 - * This class is used to fill a path with edges.
1.835 - *
1.836 - * You can push new edges to the front and to the back of the path in
1.837 - * arbitrary order then you should commit these changes to the graph.
1.838 - *
1.839 - * Fundamentally, for most "Paths" (classes fulfilling the
1.840 - * PathConcept) while the builder is active (after the first modifying
1.841 - * operation and until the commit()) the original Path is in a
1.842 - * "transitional" state (operations ot it have undefined result). But
1.843 - * in the case of UPath the original path is unchanged until the
1.844 - * commit. However we don't recomend that you use this feature.
1.845 - */
1.846 - class Builder {
1.847 - UPath &P;
1.848 - Container front, back;
1.849 -
1.850 - public:
1.851 - ///\param _p the path you want to fill in.
1.852 - ///
1.853 - Builder(UPath &_p) : P(_p) {}
1.854 -
1.855 - /// Sets the starting node of the path.
1.856 -
1.857 - /// Sets the starting node of the path. Edge added to the path
1.858 - /// afterwards have to be incident to this node.
1.859 - /// It should be called if and only if
1.860 - /// the path is empty and before any call to
1.861 - /// \ref pushFront() or \ref pushBack()
1.862 - void setStartNode(const GraphNode &) {}
1.863 -
1.864 - ///Push a new edge to the front of the path
1.865 -
1.866 - ///Push a new edge to the front of the path.
1.867 - ///\sa setStartNode
1.868 - void pushFront(const GraphEdge& e) {
1.869 - front.push_back(e);
1.870 - }
1.871 -
1.872 - ///Push a new edge to the back of the path
1.873 -
1.874 - ///Push a new edge to the back of the path.
1.875 - ///\sa setStartNode
1.876 - void pushBack(const GraphEdge& e) {
1.877 - back.push_back(e);
1.878 - }
1.879 -
1.880 - ///Commit the changes to the path.
1.881 - void commit() {
1.882 - if( !(front.empty() && back.empty()) ) {
1.883 - Container tmp;
1.884 - tmp.reserve(front.size()+back.size()+P.length());
1.885 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.886 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.887 - tmp.insert(tmp.end(), back.begin(), back.end());
1.888 - P.edges.swap(tmp);
1.889 - front.clear();
1.890 - back.clear();
1.891 - }
1.892 - }
1.893 -
1.894 -
1.895 - ///Reserve storage for the builder in advance.
1.896 -
1.897 - ///If you know a reasonable upper bound of the number of the edges
1.898 - ///to add to the front, using this function you can speed up the building.
1.899 -
1.900 - void reserveFront(size_t r) {front.reserve(r);}
1.901 -
1.902 - ///Reserve storage for the builder in advance.
1.903 -
1.904 - ///If you know a reasonable upper bound of the number of the edges
1.905 - ///to add to the back, using this function you can speed up the building.
1.906 -
1.907 - void reserveBack(size_t r) {back.reserve(r);}
1.908 -
1.909 - private:
1.910 - bool empty() {
1.911 - return front.empty() && back.empty() && P.empty();
1.912 - }
1.913 -
1.914 - GraphNode source() const {
1.915 - if( ! front.empty() )
1.916 - return P.gr->source(front[front.size()-1]);
1.917 - else if( ! P.empty() )
1.918 - return P.gr->source(P.edges[0]);
1.919 - else if( ! back.empty() )
1.920 - return P.gr->source(back[0]);
1.921 - else
1.922 - return INVALID;
1.923 - }
1.924 - GraphNode target() const {
1.925 - if( ! back.empty() )
1.926 - return P.gr->target(back[back.size()-1]);
1.927 - else if( ! P.empty() )
1.928 - return P.gr->target(P.edges[P.length()-1]);
1.929 - else if( ! front.empty() )
1.930 - return P.gr->target(front[0]);
1.931 - else
1.932 - return INVALID;
1.933 - }
1.934 -
1.935 - };
1.936 -
1.937 - };
1.938 -
1.939 -
1.940 ///@}
1.941
1.942 } // namespace lemon