1.1 --- a/lemon/path.h Fri Jan 05 10:59:18 2007 +0000
1.2 +++ b/lemon/path.h Mon Jan 08 10:39:59 2007 +0000
1.3 @@ -28,6 +28,7 @@
1.4 #include <vector>
1.5 #include <algorithm>
1.6
1.7 +#include <lemon/path_utils.h>
1.8 #include <lemon/error.h>
1.9 #include <lemon/bits/invalid.h>
1.10
1.11 @@ -37,392 +38,858 @@
1.12 /// @{
1.13
1.14
1.15 - //! \brief A structure for representing directed paths in a graph.
1.16 - //!
1.17 - //! A structure for representing directed path in a graph.
1.18 - //! \param Graph The graph type in which the path is.
1.19 - //!
1.20 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.21 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.22 - //! and \c Edge of the original graph.
1.23 - //!
1.24 - //! \todo Thoroughfully check all the range and consistency tests.
1.25 - template<typename Graph>
1.26 + /// \brief A structure for representing directed paths in a graph.
1.27 + ///
1.28 + /// A structure for representing directed path in a graph.
1.29 + /// \param Graph The graph type in which the path is.
1.30 + ///
1.31 + /// In a sense, the path can be treated as a list of edges. The
1.32 + /// lemon path type stores just this list. As a consequence it
1.33 + /// cannot enumerate the nodes in the path and the zero length paths
1.34 + /// cannot store the source.
1.35 + ///
1.36 + /// This implementation is a back and front insertable and erasable
1.37 + /// path type. It can be indexed in O(1) time. The front and back
1.38 + /// insertion and erasure is amortized O(1) time. The
1.39 + /// impelementation is based on two opposite organized vectors.
1.40 + template <typename _Graph>
1.41 class Path {
1.42 public:
1.43 - /// Edge type of the underlying graph.
1.44 +
1.45 + typedef _Graph Graph;
1.46 typedef typename Graph::Edge Edge;
1.47 - /// Node type of the underlying graph.
1.48 - typedef typename Graph::Node Node;
1.49
1.50 - class NodeIt;
1.51 - class EdgeIt;
1.52 + /// \brief Default constructor
1.53 + ///
1.54 + /// Default constructor
1.55 + Path() {}
1.56
1.57 - struct PathError : public LogicError {
1.58 - virtual const char* what() const throw() {
1.59 - return "lemon::PathError";
1.60 - }
1.61 - };
1.62 -
1.63 - public:
1.64 -
1.65 - /// \brief Constructor
1.66 + /// \brief Template copy constructor
1.67 ///
1.68 - /// Constructor
1.69 - /// \param _G The graph in which the path is.
1.70 - Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}
1.71 -
1.72 - /// \brief Subpath constructor.
1.73 - ///
1.74 - /// Subpath defined by two nodes.
1.75 - /// \warning It is an error if the two edges are not in order!
1.76 - Path(const Path &other, const NodeIt &a, const NodeIt &b) {
1.77 - graph = other.graph;
1.78 - start = a;
1.79 - edges.insert(edges.end(),
1.80 - other.edges.begin() + a.id, other.edges.begin() + b.id);
1.81 + /// This path can be initialized with any other path type. It just
1.82 + /// makes a copy of the given path.
1.83 + template <typename CPath>
1.84 + Path(const CPath& cpath) {
1.85 + copyPath(*this, cpath);
1.86 }
1.87
1.88 - /// \brief Subpath constructor.
1.89 + /// \brief Template copy assignment
1.90 ///
1.91 - /// Subpath defined by two edges. Contains edges in [a,b)
1.92 - /// \warning It is an error if the two edges are not in order!
1.93 - Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {
1.94 - graph = other.graph;
1.95 - start = graph->source(a);
1.96 - edges.insert(edges.end(),
1.97 - other.edges.begin() + a.id, other.edges.begin() + b.id);
1.98 + /// This path can be initialized with any other path type. It just
1.99 + /// makes a copy of the given path.
1.100 + template <typename CPath>
1.101 + Path& operator=(const CPath& cpath) {
1.102 + copyPath(*this, cpath);
1.103 + return *this;
1.104 }
1.105
1.106 - /// \brief Length of the path.
1.107 + /// \brief Lemon style iterator for path edges
1.108 ///
1.109 - /// The number of the edges in the path. It can be zero if the
1.110 - /// path has only one node or it is empty.
1.111 - int length() const { return edges.size(); }
1.112 -
1.113 - /// \brief Returns whether the path is empty.
1.114 - ///
1.115 - /// Returns true when the path does not contain neither edge nor
1.116 - /// node.
1.117 - bool empty() const { return start == INVALID; }
1.118 -
1.119 - /// \brief Resets the path to an empty path.
1.120 - ///
1.121 - /// Resets the path to an empty path.
1.122 - void clear() { edges.clear(); start = INVALID; }
1.123 -
1.124 - /// \brief Starting point of the path.
1.125 - ///
1.126 - /// Starting point of the path.
1.127 - /// Returns INVALID if the path is empty.
1.128 - Node source() const {
1.129 - return start;
1.130 - }
1.131 - /// \brief End point of the path.
1.132 - ///
1.133 - /// End point of the path.
1.134 - /// Returns INVALID if the path is empty.
1.135 - Node target() const {
1.136 - return length() == 0 ? start : graph->target(edges[length()-1]);
1.137 - }
1.138 -
1.139 - /// \brief Gives back a node iterator to point to the node of a
1.140 - /// given index.
1.141 - ///
1.142 - /// Gives back a node iterator to point to the node of a given
1.143 - /// index.
1.144 - /// \pre n should less or equal to \c length()
1.145 - NodeIt nthNode(int n) const {
1.146 - return NodeIt(*this, n);
1.147 - }
1.148 -
1.149 - /// \brief Gives back an edge iterator to point to the edge of a
1.150 - /// given index.
1.151 - ///
1.152 - /// Gives back an edge iterator to point to the node of a given
1.153 - /// index.
1.154 - /// \pre n should less than \c length()
1.155 - EdgeIt nthEdge(int n) const {
1.156 - return EdgeIt(*this, n);
1.157 - }
1.158 -
1.159 - /// \brief Returns node iterator pointing to the source node of the
1.160 - /// given edge iterator.
1.161 - ///
1.162 - /// Returns node iterator pointing to the source node of the given
1.163 - /// edge iterator.
1.164 - NodeIt source(const EdgeIt& e) const {
1.165 - return NodeIt(*this, e.id);
1.166 - }
1.167 -
1.168 - /// \brief Returns node iterator pointing to the target node of the
1.169 - /// given edge iterator.
1.170 - ///
1.171 - /// Returns node iterator pointing to the target node of the given
1.172 - /// edge iterator.
1.173 - NodeIt target(const EdgeIt& e) const {
1.174 - return NodeIt(*this, e.id + 1);
1.175 - }
1.176 -
1.177 -
1.178 - /// \brief Iterator class to iterate on the nodes of the paths
1.179 - ///
1.180 - /// This class is used to iterate on the nodes of the paths
1.181 - ///
1.182 - /// Of course it converts to Graph::Node
1.183 - class NodeIt {
1.184 + /// This class is used to iterate on the edges of the paths.
1.185 + class EdgeIt {
1.186 friend class Path;
1.187 public:
1.188 + /// \brief Default constructor
1.189 + EdgeIt() {}
1.190 + /// \brief Invalid constructor
1.191 + EdgeIt(Invalid) : path(0), idx(-1) {}
1.192 + /// \brief Initializate the constructor to the first edge of path
1.193 + EdgeIt(const Path &_path)
1.194 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.195
1.196 - /// \brief Default constructor
1.197 - ///
1.198 - /// Default constructor
1.199 - NodeIt() {}
1.200 + private:
1.201
1.202 - /// \brief Invalid constructor
1.203 - ///
1.204 - /// Invalid constructor
1.205 - NodeIt(Invalid) : id(-1), path(0) {}
1.206 + EdgeIt(const Path &_path, int _idx)
1.207 + : idx(_idx), path(&_path) {}
1.208
1.209 - /// \brief Constructor with starting point
1.210 - ///
1.211 - /// Constructor with starting point
1.212 - NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
1.213 - if (id > path->length()) id = -1;
1.214 + public:
1.215 +
1.216 + /// \brief Conversion to Edge
1.217 + operator const Edge&() const {
1.218 + return path->nth(idx);
1.219 }
1.220
1.221 - /// \brief Conversion to Graph::Node
1.222 - ///
1.223 - /// Conversion to Graph::Node
1.224 - operator Node() const {
1.225 - if (id > 0) {
1.226 - return path->graph->target(path->edges[id - 1]);
1.227 - } else if (id == 0) {
1.228 - return path->start;
1.229 - } else {
1.230 - return INVALID;
1.231 - }
1.232 - }
1.233 -
1.234 - /// \brief Steps to the next node
1.235 - ///
1.236 - /// Steps to the next node
1.237 - NodeIt& operator++() {
1.238 - ++id;
1.239 - if (id > path->length()) id = -1;
1.240 + /// \brief Next edge
1.241 + EdgeIt& operator++() {
1.242 + ++idx;
1.243 + if (idx >= path->length()) idx = -1;
1.244 return *this;
1.245 }
1.246
1.247 /// \brief Comparison operator
1.248 - ///
1.249 - /// Comparison operator
1.250 - bool operator==(const NodeIt& n) const { return id == n.id; }
1.251 -
1.252 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
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 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.259 /// \brief Comparison operator
1.260 - ///
1.261 - /// Comparison operator
1.262 - bool operator<(const NodeIt& n) const { return id < n.id; }
1.263 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.264
1.265 private:
1.266 - int id;
1.267 const Path *path;
1.268 + int idx;
1.269 };
1.270
1.271 + /// \brief Length of the path.
1.272 + int length() const { return head.size() + tail.size(); }
1.273 + /// \brief Returns whether the path is empty.
1.274 + bool empty() const { return head.empty() && tail.empty(); }
1.275 +
1.276 + /// \brief Resets the path to an empty path.
1.277 + void clear() { head.clear(); tail.clear(); }
1.278 +
1.279 + /// \brief Gives back the nth edge.
1.280 + ///
1.281 + /// \pre n is in the [0..length() - 1] range
1.282 + const Edge& nth(int n) const {
1.283 + return n < (int)head.size() ? *(head.rbegin() + n) :
1.284 + *(tail.begin() + (n - head.size()));
1.285 + }
1.286 +
1.287 + /// \brief Initializes edge iterator to point to the nth edge
1.288 + ///
1.289 + /// \pre n is in the [0..length() - 1] range
1.290 + EdgeIt nthIt(int n) const {
1.291 + return EdgeIt(*this, n);
1.292 + }
1.293 +
1.294 + /// \brief Gives back the first edge of the path
1.295 + const Edge& front() const {
1.296 + return head.empty() ? tail.front() : head.back();
1.297 + }
1.298 +
1.299 + /// \brief Add a new edge before the current path
1.300 + void addFront(const Edge& edge) {
1.301 + head.push_back(edge);
1.302 + }
1.303 +
1.304 + /// \brief Erase the first edge of the path
1.305 + void eraseFront() {
1.306 + if (!head.empty()) {
1.307 + head.pop_back();
1.308 + } else {
1.309 + head.clear();
1.310 + int halfsize = tail.size() / 2;
1.311 + head.resize(halfsize);
1.312 + std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
1.313 + head.rbegin());
1.314 + std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
1.315 + tail.resize(tail.size() - halfsize - 1);
1.316 + }
1.317 + }
1.318 +
1.319 + /// \brief Gives back the last edge of the path
1.320 + const Edge& back() const {
1.321 + return tail.empty() ? head.front() : tail.back();
1.322 + }
1.323 +
1.324 + /// \brief Add a new edge behind the current path
1.325 + void addBack(const Edge& edge) {
1.326 + tail.push_back(edge);
1.327 + }
1.328 +
1.329 + /// \brief Erase the last edge of the path
1.330 + void eraseBack() {
1.331 + if (!tail.empty()) {
1.332 + tail.pop_back();
1.333 + } else {
1.334 + int halfsize = head.size() / 2;
1.335 + tail.resize(halfsize);
1.336 + std::copy(head.begin() + 1, head.begin() + halfsize + 1,
1.337 + tail.rbegin());
1.338 + std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
1.339 + head.resize(head.size() - halfsize - 1);
1.340 + }
1.341 + }
1.342 +
1.343 +
1.344 +
1.345 + typedef True BuildTag;
1.346 +
1.347 + template <typename CPath>
1.348 + void build(const CPath& path) {
1.349 + int len = path.length();
1.350 + tail.reserve(len);
1.351 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
1.352 + tail.push_back(it);
1.353 + }
1.354 + }
1.355 +
1.356 + template <typename CPath>
1.357 + void buildRev(const CPath& path) {
1.358 + int len = path.length();
1.359 + head.reserve(len);
1.360 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
1.361 + head.push_back(it);
1.362 + }
1.363 + }
1.364 +
1.365 + protected:
1.366 + typedef std::vector<Edge> Container;
1.367 + Container head, tail;
1.368 +
1.369 + };
1.370 +
1.371 + /// \brief A structure for representing directed paths in a graph.
1.372 + ///
1.373 + /// A structure for representing directed path in a graph.
1.374 + /// \param Graph The graph type in which the path is.
1.375 + ///
1.376 + /// In a sense, the path can be treated as a list of edges. The
1.377 + /// lemon path type stores just this list. As a consequence it
1.378 + /// cannot enumerate the nodes in the path and the zero length paths
1.379 + /// cannot store the source.
1.380 + ///
1.381 + /// This implementation is a just back insertable and erasable path
1.382 + /// type. It can be indexed in O(1) time. The back insertion and
1.383 + /// erasure is amortized O(1) time. This implementation is faster
1.384 + /// then the \c Path type because it use just one vector for the
1.385 + /// edges.
1.386 + template <typename _Graph>
1.387 + class SimplePath {
1.388 + public:
1.389 +
1.390 + typedef _Graph Graph;
1.391 + typedef typename Graph::Edge Edge;
1.392 +
1.393 + /// \brief Default constructor
1.394 + ///
1.395 + /// Default constructor
1.396 + SimplePath() {}
1.397 +
1.398 + /// \brief Template copy constructor
1.399 + ///
1.400 + /// This path can be initialized with any other path type. It just
1.401 + /// makes a copy of the given path.
1.402 + template <typename CPath>
1.403 + SimplePath(const CPath& cpath) {
1.404 + copyPath(*this, cpath);
1.405 + }
1.406 +
1.407 + /// \brief Template copy assignment
1.408 + ///
1.409 + /// This path can be initialized with any other path type. It just
1.410 + /// makes a copy of the given path.
1.411 + template <typename CPath>
1.412 + SimplePath& operator=(const CPath& cpath) {
1.413 + copyPath(*this, cpath);
1.414 + return *this;
1.415 + }
1.416 +
1.417 /// \brief Iterator class to iterate on the edges of the paths
1.418 ///
1.419 /// This class is used to iterate on the edges of the paths
1.420 + ///
1.421 /// Of course it converts to Graph::Edge
1.422 class EdgeIt {
1.423 - friend class Path;
1.424 + friend class SimplePath;
1.425 + public:
1.426 + /// Default constructor
1.427 + EdgeIt() {}
1.428 + /// Invalid constructor
1.429 + EdgeIt(Invalid) : path(0), idx(-1) {}
1.430 + /// \brief Initializate the constructor to the first edge of path
1.431 + EdgeIt(const SimplePath &_path)
1.432 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.433 +
1.434 + private:
1.435 +
1.436 + /// Constructor with starting point
1.437 + EdgeIt(const SimplePath &_path, int _idx)
1.438 + : idx(_idx), path(&_path) {}
1.439 +
1.440 public:
1.441
1.442 - /// \brief Default constructor
1.443 - ///
1.444 - /// Default constructor
1.445 - EdgeIt() {}
1.446 -
1.447 - /// \brief Invalid constructor
1.448 - ///
1.449 - /// Invalid constructor
1.450 - EdgeIt(Invalid) : id(-1), path(0) {}
1.451 -
1.452 - /// \brief Constructor with starting point
1.453 - ///
1.454 - /// Constructor with starting point
1.455 - EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) {
1.456 - if (id >= path->length()) id = -1;
1.457 + ///Conversion to Graph::Edge
1.458 + operator const Edge&() const {
1.459 + return path->nth(idx);
1.460 }
1.461
1.462 - /// \brief Conversion to Graph::Edge
1.463 - ///
1.464 - /// Conversion to Graph::Edge
1.465 - operator Edge() const {
1.466 - return id != -1 ? path->edges[id] : INVALID;
1.467 - }
1.468 -
1.469 - /// \brief Steps to the next edge
1.470 - ///
1.471 - /// Steps to the next edge
1.472 + /// Next edge
1.473 EdgeIt& operator++() {
1.474 - ++id;
1.475 - if (id >= path->length()) id = -1;
1.476 + ++idx;
1.477 + if (idx >= path->length()) idx = -1;
1.478 return *this;
1.479 }
1.480
1.481 - /// \brief Comparison operator
1.482 - ///
1.483 /// Comparison operator
1.484 - bool operator==(const EdgeIt& e) const { return id == e.id; }
1.485 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.486 + /// Comparison operator
1.487 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.488 + /// Comparison operator
1.489 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.490
1.491 - /// \brief Comparison operator
1.492 - ///
1.493 + private:
1.494 + const SimplePath *path;
1.495 + int idx;
1.496 + };
1.497 +
1.498 + /// \brief Length of the path.
1.499 + int length() const { return data.size(); }
1.500 + /// \brief Returns whether the path is empty.
1.501 + bool empty() const { return data.empty(); }
1.502 +
1.503 + /// \brief Resets the path to an empty path.
1.504 + void clear() { data.clear(); }
1.505 +
1.506 + /// \brief Gives back the nth edge.
1.507 + ///
1.508 + /// \pre n is in the [0..length() - 1] range
1.509 + const Edge& nth(int n) const {
1.510 + return data[n];
1.511 + }
1.512 +
1.513 + /// \brief Initializes edge iterator to point to the nth edge.
1.514 + EdgeIt nthIt(int n) const {
1.515 + return EdgeIt(*this, n);
1.516 + }
1.517 +
1.518 + /// \brief Gives back the last edge of the path.
1.519 + const Edge& back() const {
1.520 + return data.back();
1.521 + }
1.522 +
1.523 + /// \brief Add a new edge behind the current path.
1.524 + void addBack(const Edge& edge) {
1.525 + data.push_back(edge);
1.526 + }
1.527 +
1.528 + /// \brief Erase the last edge of the path
1.529 + void eraseBack() {
1.530 + data.pop_back();
1.531 + }
1.532 +
1.533 + typedef True BuildTag;
1.534 +
1.535 + template <typename CPath>
1.536 + void build(const CPath& path) {
1.537 + int len = path.length();
1.538 + data.resize(len);
1.539 + int index = 0;
1.540 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
1.541 + data[index] = it;;
1.542 + ++index;
1.543 + }
1.544 + }
1.545 +
1.546 + template <typename CPath>
1.547 + void buildRev(const CPath& path) {
1.548 + int len = path.length();
1.549 + data.resize(len);
1.550 + int index = len;
1.551 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
1.552 + --index;
1.553 + data[index] = it;;
1.554 + }
1.555 + }
1.556 +
1.557 + protected:
1.558 + typedef std::vector<Edge> Container;
1.559 + Container data;
1.560 +
1.561 + };
1.562 +
1.563 + /// \brief A structure for representing directed paths in a graph.
1.564 + ///
1.565 + /// A structure for representing directed path in a graph.
1.566 + /// \param Graph The graph type in which the path is.
1.567 + ///
1.568 + /// In a sense, the path can be treated as a list of edges. The
1.569 + /// lemon path type stores just this list. As a consequence it
1.570 + /// cannot enumerate the nodes in the path and the zero length paths
1.571 + /// cannot store the source.
1.572 + ///
1.573 + /// This implementation is a back and front insertable and erasable
1.574 + /// path type. It can be indexed in O(k) time, where k is the rank
1.575 + /// of the edge in the path. The length can be computed in O(n)
1.576 + /// time. The front and back insertion and erasure is O(1) time
1.577 + /// and it can be splited and spliced in O(1) time.
1.578 + template <typename _Graph>
1.579 + class ListPath {
1.580 + public:
1.581 +
1.582 + typedef _Graph Graph;
1.583 + typedef typename Graph::Edge Edge;
1.584 +
1.585 + protected:
1.586 +
1.587 + // the std::list<> is incompatible
1.588 + // hard to create invalid iterator
1.589 + struct Node {
1.590 + Edge edge;
1.591 + Node *next, *prev;
1.592 + };
1.593 +
1.594 + Node *first, *last;
1.595 +
1.596 + std::allocator<Node> alloc;
1.597 +
1.598 + public:
1.599 +
1.600 + /// \brief Default constructor
1.601 + ///
1.602 + /// Default constructor
1.603 + ListPath() : first(0), last(0) {}
1.604 +
1.605 + /// \brief Template copy constructor
1.606 + ///
1.607 + /// This path can be initialized with any other path type. It just
1.608 + /// makes a copy of the given path.
1.609 + template <typename CPath>
1.610 + ListPath(const CPath& cpath) : first(0), last(0) {
1.611 + copyPath(*this, cpath);
1.612 + }
1.613 +
1.614 + /// \brief Destructor of the path
1.615 + ///
1.616 + /// Destructor of the path
1.617 + ~ListPath() {
1.618 + clear();
1.619 + }
1.620 +
1.621 + /// \brief Template copy assignment
1.622 + ///
1.623 + /// This path can be initialized with any other path type. It just
1.624 + /// makes a copy of the given path.
1.625 + template <typename CPath>
1.626 + ListPath& operator=(const CPath& cpath) {
1.627 + copyPath(*this, cpath);
1.628 + return *this;
1.629 + }
1.630 +
1.631 + /// \brief Iterator class to iterate on the edges of the paths
1.632 + ///
1.633 + /// This class is used to iterate on the edges of the paths
1.634 + ///
1.635 + /// Of course it converts to Graph::Edge
1.636 + class EdgeIt {
1.637 + friend class ListPath;
1.638 + public:
1.639 + /// Default constructor
1.640 + EdgeIt() {}
1.641 + /// Invalid constructor
1.642 + EdgeIt(Invalid) : path(0), node(0) {}
1.643 + /// \brief Initializate the constructor to the first edge of path
1.644 + EdgeIt(const ListPath &_path)
1.645 + : path(&_path), node(_path.first) {}
1.646 +
1.647 + protected:
1.648 +
1.649 + EdgeIt(const ListPath &_path, Node *_node)
1.650 + : path(&_path), node(_node) {}
1.651 +
1.652 +
1.653 + public:
1.654 +
1.655 + ///Conversion to Graph::Edge
1.656 + operator const Edge&() const {
1.657 + return node->edge;
1.658 + }
1.659 +
1.660 + /// Next edge
1.661 + EdgeIt& operator++() {
1.662 + node = node->next;
1.663 + return *this;
1.664 + }
1.665 +
1.666 /// Comparison operator
1.667 - bool operator!=(const EdgeIt& e) const { return id != e.id; }
1.668 + bool operator==(const EdgeIt& e) const { return node==e.node; }
1.669 + /// Comparison operator
1.670 + bool operator!=(const EdgeIt& e) const { return node!=e.node; }
1.671 + /// Comparison operator
1.672 + bool operator<(const EdgeIt& e) const { return node<e.node; }
1.673
1.674 - /// \brief Comparison operator
1.675 - ///
1.676 - /// Comparison operator
1.677 - bool operator<(const EdgeIt& e) const { return id < e.id; }
1.678 + private:
1.679 + const ListPath *path;
1.680 + Node *node;
1.681 + };
1.682 +
1.683 + /// \brief Gives back the nth edge.
1.684 + ///
1.685 + /// Gives back the nth edge in O(n) time.
1.686 + /// \pre n is in the [0..length() - 1] range
1.687 + const Edge& nth(int n) const {
1.688 + Node *node = first;
1.689 + for (int i = 0; i < n; ++i) {
1.690 + node = node->next;
1.691 + }
1.692 + return node->edge;
1.693 + }
1.694 +
1.695 + /// \brief Initializes edge iterator to point to the nth edge.
1.696 + EdgeIt nthIt(int n) const {
1.697 + Node *node = first;
1.698 + for (int i = 0; i < n; ++i) {
1.699 + node = node->next;
1.700 + }
1.701 + return EdgeIt(*this, node);
1.702 + }
1.703 +
1.704 + /// \brief Length of the path.
1.705 + int length() const {
1.706 + int len = 0;
1.707 + Node *node = first;
1.708 + while (node != 0) {
1.709 + node = node->next;
1.710 + ++len;
1.711 + }
1.712 + return len;
1.713 + }
1.714 +
1.715 + /// \brief Returns whether the path is empty.
1.716 + bool empty() const { return first == 0; }
1.717 +
1.718 + /// \brief Resets the path to an empty path.
1.719 + void clear() {
1.720 + while (first != 0) {
1.721 + last = first->next;
1.722 + alloc.destroy(first);
1.723 + alloc.deallocate(first, 1);
1.724 + first = last;
1.725 + }
1.726 + }
1.727 +
1.728 + /// \brief Gives back the first edge of the path
1.729 + const Edge& front() const {
1.730 + return first->edge;
1.731 + }
1.732 +
1.733 + /// \brief Add a new edge before the current path
1.734 + void addFront(const Edge& edge) {
1.735 + Node *node = alloc.allocate(1);
1.736 + alloc.construct(node, Node());
1.737 + node->prev = 0;
1.738 + node->next = first;
1.739 + node->edge = edge;
1.740 + if (first) {
1.741 + first->prev = node;
1.742 + first = node;
1.743 + } else {
1.744 + first = last = node;
1.745 + }
1.746 + }
1.747 +
1.748 + /// \brief Erase the first edge of the path
1.749 + void eraseFront() {
1.750 + Node *node = first;
1.751 + first = first->next;
1.752 + if (first) {
1.753 + first->prev = 0;
1.754 + } else {
1.755 + last = 0;
1.756 + }
1.757 + alloc.destroy(node);
1.758 + alloc.deallocate(node, 1);
1.759 + }
1.760 +
1.761 + /// \brief Gives back the last edge of the path.
1.762 + const Edge& back() const {
1.763 + return last->edge;
1.764 + }
1.765 +
1.766 + /// \brief Add a new edge behind the current path.
1.767 + void addBack(const Edge& edge) {
1.768 + Node *node = alloc.allocate(1);
1.769 + alloc.construct(node, Node());
1.770 + node->next = 0;
1.771 + node->prev = last;
1.772 + node->edge = edge;
1.773 + if (last) {
1.774 + last->next = node;
1.775 + last = node;
1.776 + } else {
1.777 + last = first = node;
1.778 + }
1.779 + }
1.780 +
1.781 + /// \brief Erase the last edge of the path
1.782 + void eraseBack() {
1.783 + Node *node = last;
1.784 + last = last->prev;
1.785 + if (last) {
1.786 + last->next = 0;
1.787 + } else {
1.788 + first = 0;
1.789 + }
1.790 + alloc.destroy(node);
1.791 + alloc.deallocate(node, 1);
1.792 + }
1.793 +
1.794 + /// \brief Splicing the given path to the current path.
1.795 + ///
1.796 + /// It splices the \c tpath to the back of the current path and \c
1.797 + /// tpath becomes empty. The time complexity of this function is
1.798 + /// O(1).
1.799 + void spliceBack(ListPath& tpath) {
1.800 + if (first) {
1.801 + if (tpath.first) {
1.802 + last->next = tpath.first;
1.803 + tpath.first->prev = last;
1.804 + last = tpath.last;
1.805 + }
1.806 + } else {
1.807 + first = tpath.first;
1.808 + last = tpath.last;
1.809 + }
1.810 + tpath.first = tpath.last = 0;
1.811 + }
1.812 +
1.813 + /// \brief Splicing the given path to the current path.
1.814 + ///
1.815 + /// It splices the \c tpath before the current path and \c tpath
1.816 + /// becomes empty. The time complexity of this function
1.817 + /// is O(1).
1.818 + void spliceFront(ListPath& tpath) {
1.819 + if (first) {
1.820 + if (tpath.first) {
1.821 + first->prev = tpath.last;
1.822 + tpath.last->next = first;
1.823 + first = tpath.first;
1.824 + }
1.825 + } else {
1.826 + first = tpath.first;
1.827 + last = tpath.last;
1.828 + }
1.829 + tpath.first = tpath.last = 0;
1.830 + }
1.831 +
1.832 + /// \brief Splicing the given path into the current path.
1.833 + ///
1.834 + /// It splices the \c tpath into the current path before the
1.835 + /// position of \c it iterator and \c tpath becomes empty. The
1.836 + /// time complexity of this function is O(1). If the \c it is \c
1.837 + /// INVALID then it will splice behind the current path.
1.838 + void splice(EdgeIt it, ListPath& tpath) {
1.839 + if (it.node) {
1.840 + if (tpath.first) {
1.841 + tpath.first->prev = it.node->prev;
1.842 + if (it.node->prev) {
1.843 + it.node->prev->next = tpath.first;
1.844 + } else {
1.845 + first = tpath.first;
1.846 + }
1.847 + it.node->prev = tpath.last;
1.848 + tpath.last->next = it.node;
1.849 + }
1.850 + } else {
1.851 + if (first) {
1.852 + if (tpath.first) {
1.853 + last->next = tpath.first;
1.854 + tpath.first->prev = last;
1.855 + last = tpath.last;
1.856 + }
1.857 + } else {
1.858 + first = tpath.first;
1.859 + last = tpath.last;
1.860 + }
1.861 + }
1.862 + tpath.first = tpath.last = 0;
1.863 + }
1.864 +
1.865 + /// \brief Spliting the current path.
1.866 + ///
1.867 + /// It splits the current path into two parts. The part before \c
1.868 + /// it iterator will remain in the current path and the part from
1.869 + /// the it will put into the \c tpath. If the \c tpath had edges
1.870 + /// before the operation they will be removed first. The time
1.871 + /// complexity of this function is O(1) plus the clearing of \c
1.872 + /// tpath. If the \c it is \c INVALID then it just clears \c
1.873 + /// tpath.
1.874 + void split(EdgeIt it, ListPath& tpath) {
1.875 + tpath.clear();
1.876 + if (it.node) {
1.877 + tpath.first = it.node;
1.878 + tpath.last = last;
1.879 + if (it.node->prev) {
1.880 + last = it.node->prev;
1.881 + last->next = 0;
1.882 + } else {
1.883 + first = last = 0;
1.884 + }
1.885 + it.node->prev = 0;
1.886 + }
1.887 + }
1.888 +
1.889 +
1.890 + typedef True BuildTag;
1.891 +
1.892 + template <typename CPath>
1.893 + void build(const CPath& path) {
1.894 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
1.895 + addBack(it);
1.896 + }
1.897 + }
1.898 +
1.899 + template <typename CPath>
1.900 + void buildRev(const CPath& path) {
1.901 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
1.902 + addFront(it);
1.903 + }
1.904 + }
1.905 +
1.906 + };
1.907 +
1.908 + /// \brief A structure for representing directed paths in a graph.
1.909 + ///
1.910 + /// A structure for representing directed path in a graph.
1.911 + /// \param Graph The graph type in which the path is.
1.912 + ///
1.913 + /// In a sense, the path can be treated as a list of edges. The
1.914 + /// lemon path type stores just this list. As a consequence it
1.915 + /// cannot enumerate the nodes in the path and the zero length paths
1.916 + /// cannot store the source.
1.917 + ///
1.918 + /// This implementation is completly static, so it cannot be
1.919 + /// modified exclude the assign an other path. It is intented to be
1.920 + /// used when you want to store a large amount paths because it is
1.921 + /// the most memory efficient path type in the lemon.
1.922 + template <typename _Graph>
1.923 + class StaticPath {
1.924 + public:
1.925 +
1.926 + typedef _Graph Graph;
1.927 + typedef typename Graph::Edge Edge;
1.928 +
1.929 + /// \brief Default constructor
1.930 + ///
1.931 + /// Default constructor
1.932 + StaticPath() : len(0), edges(0) {}
1.933 +
1.934 + /// \brief Template copy constructor
1.935 + ///
1.936 + /// This path can be initialized with any other path type. It just
1.937 + /// makes a copy of the given path.
1.938 + template <typename CPath>
1.939 + StaticPath(const CPath& cpath) : edges(0) {
1.940 + copyPath(*this, cpath);
1.941 + }
1.942 +
1.943 + /// \brief Destructor of the path
1.944 + ///
1.945 + /// Destructor of the path
1.946 + ~StaticPath() {
1.947 + if (edges) delete[] edges;
1.948 + }
1.949 +
1.950 + /// \brief Template copy assignment
1.951 + ///
1.952 + /// This path can be initialized with any other path type. It just
1.953 + /// makes a copy of the given path.
1.954 + template <typename CPath>
1.955 + StaticPath& operator=(const CPath& cpath) {
1.956 + copyPath(*this, cpath);
1.957 + return *this;
1.958 + }
1.959 +
1.960 + /// \brief Iterator class to iterate on the edges of the paths
1.961 + ///
1.962 + /// This class is used to iterate on the edges of the paths
1.963 + ///
1.964 + /// Of course it converts to Graph::Edge
1.965 + class EdgeIt {
1.966 + friend class StaticPath;
1.967 + public:
1.968 + /// Default constructor
1.969 + EdgeIt() {}
1.970 + /// Invalid constructor
1.971 + EdgeIt(Invalid) : path(0), idx(-1) {}
1.972 + /// Initializate the constructor to the first edge of path
1.973 + EdgeIt(const StaticPath &_path)
1.974 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.975
1.976 private:
1.977
1.978 - int id;
1.979 - const Path *path;
1.980 + /// Constructor with starting point
1.981 + EdgeIt(const StaticPath &_path, int _idx)
1.982 + : idx(_idx), path(&_path) {}
1.983 +
1.984 + public:
1.985 +
1.986 + ///Conversion to Graph::Edge
1.987 + operator const Edge&() const {
1.988 + return path->nth(idx);
1.989 + }
1.990 +
1.991 + /// Next edge
1.992 + EdgeIt& operator++() {
1.993 + ++idx;
1.994 + if (idx >= path->length()) idx = -1;
1.995 + return *this;
1.996 + }
1.997 +
1.998 + /// Comparison operator
1.999 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.1000 + /// Comparison operator
1.1001 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.1002 + /// Comparison operator
1.1003 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.1004 +
1.1005 + private:
1.1006 + const StaticPath *path;
1.1007 + int idx;
1.1008 };
1.1009
1.1010 - protected:
1.1011 + /// \brief Gives back the nth edge.
1.1012 + ///
1.1013 + /// \pre n is in the [0..length() - 1] range
1.1014 + const Edge& nth(int n) const {
1.1015 + return edges[n];
1.1016 + }
1.1017
1.1018 - const Graph *graph;
1.1019 + /// \brief Initializes edge iterator to point to the nth edge.
1.1020 + EdgeIt nthIt(int n) const {
1.1021 + return EdgeIt(*this, n);
1.1022 + }
1.1023
1.1024 - typedef std::vector<Edge> Container;
1.1025 - Container edges;
1.1026 - Node start;
1.1027 + /// \brief Gives back the length of the path.
1.1028 + int length() const { return len; }
1.1029
1.1030 - public:
1.1031 + /// \brief Returns true when the path is empty.
1.1032 + int empty() const { return len == 0; }
1.1033
1.1034 - friend class Builder;
1.1035 + /// \break Erase all edge in the graph.
1.1036 + void clear() {
1.1037 + len = 0;
1.1038 + if (edges) delete[] edges;
1.1039 + edges = 0;
1.1040 + }
1.1041
1.1042 - /// \brief Class to build paths
1.1043 - ///
1.1044 - /// This class is used to fill a path with edges.
1.1045 - ///
1.1046 - /// You can push new edges to the front and to the back of the
1.1047 - /// path in arbitrary order then you should commit these changes
1.1048 - /// to the graph.
1.1049 - ///
1.1050 - /// Fundamentally, for most "Paths" (classes fulfilling the
1.1051 - /// PathConcept) while the builder is active (after the first
1.1052 - /// modifying operation and until the commit()) the original Path
1.1053 - /// is in a "transitional" state (operations on it have undefined
1.1054 - /// result). But in the case of Path the original path remains
1.1055 - /// unchanged until the commit. However we don't recomend that you
1.1056 - /// use this feature.
1.1057 - class Builder {
1.1058 - public:
1.1059 - /// \brief Constructor
1.1060 - ///
1.1061 - /// Constructor
1.1062 - /// \param _path the path you want to fill in.
1.1063 - Builder(Path &_path) : path(_path), start(INVALID) {}
1.1064 + /// \brief Gives back the first edge of the path.
1.1065 + const Edge& front() const {
1.1066 + return edges[0];
1.1067 + }
1.1068
1.1069 - /// \brief Destructor
1.1070 - ///
1.1071 - /// Destructor
1.1072 - ~Builder() {
1.1073 - LEMON_ASSERT(front.empty() && back.empty() && start == INVALID,
1.1074 - PathError());
1.1075 + /// \brief Gives back the last edge of the path.
1.1076 + const Edge& back() const {
1.1077 + return edges[len - 1];
1.1078 + }
1.1079 +
1.1080 +
1.1081 + typedef True BuildTag;
1.1082 +
1.1083 + template <typename CPath>
1.1084 + void build(const CPath& path) {
1.1085 + len = path.length();
1.1086 + edges = new Edge[len];
1.1087 + int index = 0;
1.1088 + for (typename CPath::EdgeIt it(path); it != INVALID; ++it) {
1.1089 + edges[index] = it;
1.1090 + ++index;
1.1091 }
1.1092 + }
1.1093
1.1094 - /// \brief Sets the starting node of the path.
1.1095 - ///
1.1096 - /// Sets the starting node of the path. Edge added to the path
1.1097 - /// afterwards have to be incident to this node. It should be
1.1098 - /// called if and only if the path is empty and before any call
1.1099 - /// to \ref pushFront() or \ref pushBack()
1.1100 - void setStartNode(const Node &_start) {
1.1101 - LEMON_ASSERT(path.empty() && start == INVALID, PathError());
1.1102 - start = _start;
1.1103 + template <typename CPath>
1.1104 + void buildRev(const CPath& path) {
1.1105 + len = path.length();
1.1106 + edges = new Edge[len];
1.1107 + int index = len;
1.1108 + for (typename CPath::RevIt it(path); it != INVALID; ++it) {
1.1109 + --index;
1.1110 + edges[index] = it;
1.1111 }
1.1112 + }
1.1113
1.1114 - /// \brief Push a new edge to the front of the path
1.1115 - ///
1.1116 - /// Push a new edge to the front of the path.
1.1117 - /// \sa setStartNode
1.1118 - void pushFront(const Edge& e) {
1.1119 - LEMON_ASSERT(front.empty() ||
1.1120 - (path.graph->source(front.back()) ==
1.1121 - path.graph->target(e)), PathError());
1.1122 - LEMON_ASSERT(path.empty() ||
1.1123 - (path.source() == path.graph->target(e)), PathError());
1.1124 - LEMON_ASSERT(!path.empty() || !front.empty() ||
1.1125 - (start == path.graph->target(e)), PathError());
1.1126 - front.push_back(e);
1.1127 - }
1.1128 -
1.1129 - /// \brief Push a new edge to the back of the path
1.1130 - ///
1.1131 - /// Push a new edge to the back of the path.
1.1132 - /// \sa setStartNode
1.1133 - void pushBack(const Edge& e) {
1.1134 - LEMON_ASSERT(back.empty() ||
1.1135 - (path.graph->target(back.back()) ==
1.1136 - path.graph->source(e)), PathError());
1.1137 - LEMON_ASSERT(path.empty() ||
1.1138 - (path.target() == path.graph->source(e)), PathError());
1.1139 - LEMON_ASSERT(!path.empty() || !back.empty() ||
1.1140 - (start == path.graph->source(e)), PathError());
1.1141 - back.push_back(e);
1.1142 - }
1.1143 -
1.1144 - /// \brief Commit the changes to the path.
1.1145 - ///
1.1146 - /// Commit the changes to the path.
1.1147 - void commit() {
1.1148 - if( !front.empty() || !back.empty() || start != INVALID) {
1.1149 - Container tmp;
1.1150 - tmp.reserve(front.size() + back.size() + path.length());
1.1151 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.1152 - tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());
1.1153 - tmp.insert(tmp.end(), back.begin(), back.end());
1.1154 - path.edges.swap(tmp);
1.1155 - if (!front.empty()) {
1.1156 - path.start = path.graph->source(front.back());
1.1157 - } else {
1.1158 - path.start = start;
1.1159 - }
1.1160 - start = INVALID;
1.1161 - front.clear();
1.1162 - back.clear();
1.1163 - }
1.1164 - }
1.1165 -
1.1166 - /// \brief Reserve storage for the builder in advance.
1.1167 - ///
1.1168 - /// If you know a reasonable upper bound of the number of the
1.1169 - /// edges to add to the front, using this function you can speed
1.1170 - /// up the building.
1.1171 - void reserveFront(size_t r) {front.reserve(r);}
1.1172 -
1.1173 - /// \brief Reserve storage for the builder in advance.
1.1174 - ///
1.1175 - /// If you know a reasonable upper bound of the number of the
1.1176 - /// edges to add to the back, using this function you can speed
1.1177 - /// up the building.
1.1178 - void reserveBack(size_t r) {back.reserve(r);}
1.1179 -
1.1180 - private:
1.1181 -
1.1182 - Path &path;
1.1183 - Container front, back;
1.1184 - Node start;
1.1185 -
1.1186 - };
1.1187 -
1.1188 + private:
1.1189 + int len;
1.1190 + Edge* edges;
1.1191 };
1.1192
1.1193 ///@}