1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/path.h Thu Jan 24 11:31:19 2008 +0000
1.3 @@ -0,0 +1,903 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup paths
1.23 +///\file
1.24 +///\brief Classes for representing paths in digraphs.
1.25 +///
1.26 +
1.27 +#ifndef LEMON_PATH_H
1.28 +#define LEMON_PATH_H
1.29 +
1.30 +#include <vector>
1.31 +#include <algorithm>
1.32 +
1.33 +#include <lemon/path_utils.h>
1.34 +#include <lemon/error.h>
1.35 +#include <lemon/bits/invalid.h>
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 + /// \addtogroup paths
1.40 + /// @{
1.41 +
1.42 +
1.43 + /// \brief A structure for representing directed paths in a digraph.
1.44 + ///
1.45 + /// A structure for representing directed path in a digraph.
1.46 + /// \param Digraph The digraph type in which the path is.
1.47 + ///
1.48 + /// In a sense, the path can be treated as a list of arcs. The
1.49 + /// lemon path type stores just this list. As a consequence it
1.50 + /// cannot enumerate the nodes in the path and the zero length paths
1.51 + /// cannot store the source.
1.52 + ///
1.53 + /// This implementation is a back and front insertable and erasable
1.54 + /// path type. It can be indexed in O(1) time. The front and back
1.55 + /// insertion and erasure is amortized O(1) time. The
1.56 + /// impelementation is based on two opposite organized vectors.
1.57 + template <typename _Digraph>
1.58 + class Path {
1.59 + public:
1.60 +
1.61 + typedef _Digraph Digraph;
1.62 + typedef typename Digraph::Arc Arc;
1.63 +
1.64 + /// \brief Default constructor
1.65 + ///
1.66 + /// Default constructor
1.67 + Path() {}
1.68 +
1.69 + /// \brief Template copy constructor
1.70 + ///
1.71 + /// This path can be initialized with any other path type. It just
1.72 + /// makes a copy of the given path.
1.73 + template <typename CPath>
1.74 + Path(const CPath& cpath) {
1.75 + copyPath(*this, cpath);
1.76 + }
1.77 +
1.78 + /// \brief Template copy assignment
1.79 + ///
1.80 + /// This path can be initialized with any other path type. It just
1.81 + /// makes a copy of the given path.
1.82 + template <typename CPath>
1.83 + Path& operator=(const CPath& cpath) {
1.84 + copyPath(*this, cpath);
1.85 + return *this;
1.86 + }
1.87 +
1.88 + /// \brief Lemon style iterator for path arcs
1.89 + ///
1.90 + /// This class is used to iterate on the arcs of the paths.
1.91 + class ArcIt {
1.92 + friend class Path;
1.93 + public:
1.94 + /// \brief Default constructor
1.95 + ArcIt() {}
1.96 + /// \brief Invalid constructor
1.97 + ArcIt(Invalid) : path(0), idx(-1) {}
1.98 + /// \brief Initializate the constructor to the first arc of path
1.99 + ArcIt(const Path &_path)
1.100 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.101 +
1.102 + private:
1.103 +
1.104 + ArcIt(const Path &_path, int _idx)
1.105 + : path(&_path), idx(_idx) {}
1.106 +
1.107 + public:
1.108 +
1.109 + /// \brief Conversion to Arc
1.110 + operator const Arc&() const {
1.111 + return path->nth(idx);
1.112 + }
1.113 +
1.114 + /// \brief Next arc
1.115 + ArcIt& operator++() {
1.116 + ++idx;
1.117 + if (idx >= path->length()) idx = -1;
1.118 + return *this;
1.119 + }
1.120 +
1.121 + /// \brief Comparison operator
1.122 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
1.123 + /// \brief Comparison operator
1.124 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
1.125 + /// \brief Comparison operator
1.126 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
1.127 +
1.128 + private:
1.129 + const Path *path;
1.130 + int idx;
1.131 + };
1.132 +
1.133 + /// \brief Length of the path.
1.134 + int length() const { return head.size() + tail.size(); }
1.135 + /// \brief Returns whether the path is empty.
1.136 + bool empty() const { return head.empty() && tail.empty(); }
1.137 +
1.138 + /// \brief Resets the path to an empty path.
1.139 + void clear() { head.clear(); tail.clear(); }
1.140 +
1.141 + /// \brief Gives back the nth arc.
1.142 + ///
1.143 + /// \pre n is in the [0..length() - 1] range
1.144 + const Arc& nth(int n) const {
1.145 + return n < int(head.size()) ? *(head.rbegin() + n) :
1.146 + *(tail.begin() + (n - head.size()));
1.147 + }
1.148 +
1.149 + /// \brief Initializes arc iterator to point to the nth arc
1.150 + ///
1.151 + /// \pre n is in the [0..length() - 1] range
1.152 + ArcIt nthIt(int n) const {
1.153 + return ArcIt(*this, n);
1.154 + }
1.155 +
1.156 + /// \brief Gives back the first arc of the path
1.157 + const Arc& front() const {
1.158 + return head.empty() ? tail.front() : head.back();
1.159 + }
1.160 +
1.161 + /// \brief Add a new arc before the current path
1.162 + void addFront(const Arc& arc) {
1.163 + head.push_back(arc);
1.164 + }
1.165 +
1.166 + /// \brief Erase the first arc of the path
1.167 + void eraseFront() {
1.168 + if (!head.empty()) {
1.169 + head.pop_back();
1.170 + } else {
1.171 + head.clear();
1.172 + int halfsize = tail.size() / 2;
1.173 + head.resize(halfsize);
1.174 + std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
1.175 + head.rbegin());
1.176 + std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
1.177 + tail.resize(tail.size() - halfsize - 1);
1.178 + }
1.179 + }
1.180 +
1.181 + /// \brief Gives back the last arc of the path
1.182 + const Arc& back() const {
1.183 + return tail.empty() ? head.front() : tail.back();
1.184 + }
1.185 +
1.186 + /// \brief Add a new arc behind the current path
1.187 + void addBack(const Arc& arc) {
1.188 + tail.push_back(arc);
1.189 + }
1.190 +
1.191 + /// \brief Erase the last arc of the path
1.192 + void eraseBack() {
1.193 + if (!tail.empty()) {
1.194 + tail.pop_back();
1.195 + } else {
1.196 + int halfsize = head.size() / 2;
1.197 + tail.resize(halfsize);
1.198 + std::copy(head.begin() + 1, head.begin() + halfsize + 1,
1.199 + tail.rbegin());
1.200 + std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
1.201 + head.resize(head.size() - halfsize - 1);
1.202 + }
1.203 + }
1.204 +
1.205 +
1.206 +
1.207 + typedef True BuildTag;
1.208 +
1.209 + template <typename CPath>
1.210 + void build(const CPath& path) {
1.211 + int len = path.length();
1.212 + tail.reserve(len);
1.213 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.214 + tail.push_back(it);
1.215 + }
1.216 + }
1.217 +
1.218 + template <typename CPath>
1.219 + void buildRev(const CPath& path) {
1.220 + int len = path.length();
1.221 + head.reserve(len);
1.222 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.223 + head.push_back(it);
1.224 + }
1.225 + }
1.226 +
1.227 + protected:
1.228 + typedef std::vector<Arc> Container;
1.229 + Container head, tail;
1.230 +
1.231 + };
1.232 +
1.233 + /// \brief A structure for representing directed paths in a digraph.
1.234 + ///
1.235 + /// A structure for representing directed path in a digraph.
1.236 + /// \param Digraph The digraph type in which the path is.
1.237 + ///
1.238 + /// In a sense, the path can be treated as a list of arcs. The
1.239 + /// lemon path type stores just this list. As a consequence it
1.240 + /// cannot enumerate the nodes in the path and the zero length paths
1.241 + /// cannot store the source.
1.242 + ///
1.243 + /// This implementation is a just back insertable and erasable path
1.244 + /// type. It can be indexed in O(1) time. The back insertion and
1.245 + /// erasure is amortized O(1) time. This implementation is faster
1.246 + /// then the \c Path type because it use just one vector for the
1.247 + /// arcs.
1.248 + template <typename _Digraph>
1.249 + class SimplePath {
1.250 + public:
1.251 +
1.252 + typedef _Digraph Digraph;
1.253 + typedef typename Digraph::Arc Arc;
1.254 +
1.255 + /// \brief Default constructor
1.256 + ///
1.257 + /// Default constructor
1.258 + SimplePath() {}
1.259 +
1.260 + /// \brief Template copy constructor
1.261 + ///
1.262 + /// This path can be initialized with any other path type. It just
1.263 + /// makes a copy of the given path.
1.264 + template <typename CPath>
1.265 + SimplePath(const CPath& cpath) {
1.266 + copyPath(*this, cpath);
1.267 + }
1.268 +
1.269 + /// \brief Template copy assignment
1.270 + ///
1.271 + /// This path can be initialized with any other path type. It just
1.272 + /// makes a copy of the given path.
1.273 + template <typename CPath>
1.274 + SimplePath& operator=(const CPath& cpath) {
1.275 + copyPath(*this, cpath);
1.276 + return *this;
1.277 + }
1.278 +
1.279 + /// \brief Iterator class to iterate on the arcs of the paths
1.280 + ///
1.281 + /// This class is used to iterate on the arcs of the paths
1.282 + ///
1.283 + /// Of course it converts to Digraph::Arc
1.284 + class ArcIt {
1.285 + friend class SimplePath;
1.286 + public:
1.287 + /// Default constructor
1.288 + ArcIt() {}
1.289 + /// Invalid constructor
1.290 + ArcIt(Invalid) : path(0), idx(-1) {}
1.291 + /// \brief Initializate the constructor to the first arc of path
1.292 + ArcIt(const SimplePath &_path)
1.293 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.294 +
1.295 + private:
1.296 +
1.297 + /// Constructor with starting point
1.298 + ArcIt(const SimplePath &_path, int _idx)
1.299 + : idx(_idx), path(&_path) {}
1.300 +
1.301 + public:
1.302 +
1.303 + ///Conversion to Digraph::Arc
1.304 + operator const Arc&() const {
1.305 + return path->nth(idx);
1.306 + }
1.307 +
1.308 + /// Next arc
1.309 + ArcIt& operator++() {
1.310 + ++idx;
1.311 + if (idx >= path->length()) idx = -1;
1.312 + return *this;
1.313 + }
1.314 +
1.315 + /// Comparison operator
1.316 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
1.317 + /// Comparison operator
1.318 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
1.319 + /// Comparison operator
1.320 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
1.321 +
1.322 + private:
1.323 + const SimplePath *path;
1.324 + int idx;
1.325 + };
1.326 +
1.327 + /// \brief Length of the path.
1.328 + int length() const { return data.size(); }
1.329 + /// \brief Returns whether the path is empty.
1.330 + bool empty() const { return data.empty(); }
1.331 +
1.332 + /// \brief Resets the path to an empty path.
1.333 + void clear() { data.clear(); }
1.334 +
1.335 + /// \brief Gives back the nth arc.
1.336 + ///
1.337 + /// \pre n is in the [0..length() - 1] range
1.338 + const Arc& nth(int n) const {
1.339 + return data[n];
1.340 + }
1.341 +
1.342 + /// \brief Initializes arc iterator to point to the nth arc.
1.343 + ArcIt nthIt(int n) const {
1.344 + return ArcIt(*this, n);
1.345 + }
1.346 +
1.347 + /// \brief Gives back the first arc of the path.
1.348 + const Arc& front() const {
1.349 + return data.front();
1.350 + }
1.351 +
1.352 + /// \brief Gives back the last arc of the path.
1.353 + const Arc& back() const {
1.354 + return data.back();
1.355 + }
1.356 +
1.357 + /// \brief Add a new arc behind the current path.
1.358 + void addBack(const Arc& arc) {
1.359 + data.push_back(arc);
1.360 + }
1.361 +
1.362 + /// \brief Erase the last arc of the path
1.363 + void eraseBack() {
1.364 + data.pop_back();
1.365 + }
1.366 +
1.367 + typedef True BuildTag;
1.368 +
1.369 + template <typename CPath>
1.370 + void build(const CPath& path) {
1.371 + int len = path.length();
1.372 + data.resize(len);
1.373 + int index = 0;
1.374 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.375 + data[index] = it;;
1.376 + ++index;
1.377 + }
1.378 + }
1.379 +
1.380 + template <typename CPath>
1.381 + void buildRev(const CPath& path) {
1.382 + int len = path.length();
1.383 + data.resize(len);
1.384 + int index = len;
1.385 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.386 + --index;
1.387 + data[index] = it;;
1.388 + }
1.389 + }
1.390 +
1.391 + protected:
1.392 + typedef std::vector<Arc> Container;
1.393 + Container data;
1.394 +
1.395 + };
1.396 +
1.397 + /// \brief A structure for representing directed paths in a digraph.
1.398 + ///
1.399 + /// A structure for representing directed path in a digraph.
1.400 + /// \param Digraph The digraph type in which the path is.
1.401 + ///
1.402 + /// In a sense, the path can be treated as a list of arcs. The
1.403 + /// lemon path type stores just this list. As a consequence it
1.404 + /// cannot enumerate the nodes in the path and the zero length paths
1.405 + /// cannot store the source.
1.406 + ///
1.407 + /// This implementation is a back and front insertable and erasable
1.408 + /// path type. It can be indexed in O(k) time, where k is the rank
1.409 + /// of the arc in the path. The length can be computed in O(n)
1.410 + /// time. The front and back insertion and erasure is O(1) time
1.411 + /// and it can be splited and spliced in O(1) time.
1.412 + template <typename _Digraph>
1.413 + class ListPath {
1.414 + public:
1.415 +
1.416 + typedef _Digraph Digraph;
1.417 + typedef typename Digraph::Arc Arc;
1.418 +
1.419 + protected:
1.420 +
1.421 + // the std::list<> is incompatible
1.422 + // hard to create invalid iterator
1.423 + struct Node {
1.424 + Arc arc;
1.425 + Node *next, *prev;
1.426 + };
1.427 +
1.428 + Node *first, *last;
1.429 +
1.430 + std::allocator<Node> alloc;
1.431 +
1.432 + public:
1.433 +
1.434 + /// \brief Default constructor
1.435 + ///
1.436 + /// Default constructor
1.437 + ListPath() : first(0), last(0) {}
1.438 +
1.439 + /// \brief Template copy constructor
1.440 + ///
1.441 + /// This path can be initialized with any other path type. It just
1.442 + /// makes a copy of the given path.
1.443 + template <typename CPath>
1.444 + ListPath(const CPath& cpath) : first(0), last(0) {
1.445 + copyPath(*this, cpath);
1.446 + }
1.447 +
1.448 + /// \brief Destructor of the path
1.449 + ///
1.450 + /// Destructor of the path
1.451 + ~ListPath() {
1.452 + clear();
1.453 + }
1.454 +
1.455 + /// \brief Template copy assignment
1.456 + ///
1.457 + /// This path can be initialized with any other path type. It just
1.458 + /// makes a copy of the given path.
1.459 + template <typename CPath>
1.460 + ListPath& operator=(const CPath& cpath) {
1.461 + copyPath(*this, cpath);
1.462 + return *this;
1.463 + }
1.464 +
1.465 + /// \brief Iterator class to iterate on the arcs of the paths
1.466 + ///
1.467 + /// This class is used to iterate on the arcs of the paths
1.468 + ///
1.469 + /// Of course it converts to Digraph::Arc
1.470 + class ArcIt {
1.471 + friend class ListPath;
1.472 + public:
1.473 + /// Default constructor
1.474 + ArcIt() {}
1.475 + /// Invalid constructor
1.476 + ArcIt(Invalid) : path(0), node(0) {}
1.477 + /// \brief Initializate the constructor to the first arc of path
1.478 + ArcIt(const ListPath &_path)
1.479 + : path(&_path), node(_path.first) {}
1.480 +
1.481 + protected:
1.482 +
1.483 + ArcIt(const ListPath &_path, Node *_node)
1.484 + : path(&_path), node(_node) {}
1.485 +
1.486 +
1.487 + public:
1.488 +
1.489 + ///Conversion to Digraph::Arc
1.490 + operator const Arc&() const {
1.491 + return node->arc;
1.492 + }
1.493 +
1.494 + /// Next arc
1.495 + ArcIt& operator++() {
1.496 + node = node->next;
1.497 + return *this;
1.498 + }
1.499 +
1.500 + /// Comparison operator
1.501 + bool operator==(const ArcIt& e) const { return node==e.node; }
1.502 + /// Comparison operator
1.503 + bool operator!=(const ArcIt& e) const { return node!=e.node; }
1.504 + /// Comparison operator
1.505 + bool operator<(const ArcIt& e) const { return node<e.node; }
1.506 +
1.507 + private:
1.508 + const ListPath *path;
1.509 + Node *node;
1.510 + };
1.511 +
1.512 + /// \brief Gives back the nth arc.
1.513 + ///
1.514 + /// Gives back the nth arc in O(n) time.
1.515 + /// \pre n is in the [0..length() - 1] range
1.516 + const Arc& nth(int n) const {
1.517 + Node *node = first;
1.518 + for (int i = 0; i < n; ++i) {
1.519 + node = node->next;
1.520 + }
1.521 + return node->arc;
1.522 + }
1.523 +
1.524 + /// \brief Initializes arc iterator to point to the nth arc.
1.525 + ArcIt nthIt(int n) const {
1.526 + Node *node = first;
1.527 + for (int i = 0; i < n; ++i) {
1.528 + node = node->next;
1.529 + }
1.530 + return ArcIt(*this, node);
1.531 + }
1.532 +
1.533 + /// \brief Length of the path.
1.534 + int length() const {
1.535 + int len = 0;
1.536 + Node *node = first;
1.537 + while (node != 0) {
1.538 + node = node->next;
1.539 + ++len;
1.540 + }
1.541 + return len;
1.542 + }
1.543 +
1.544 + /// \brief Returns whether the path is empty.
1.545 + bool empty() const { return first == 0; }
1.546 +
1.547 + /// \brief Resets the path to an empty path.
1.548 + void clear() {
1.549 + while (first != 0) {
1.550 + last = first->next;
1.551 + alloc.destroy(first);
1.552 + alloc.deallocate(first, 1);
1.553 + first = last;
1.554 + }
1.555 + }
1.556 +
1.557 + /// \brief Gives back the first arc of the path
1.558 + const Arc& front() const {
1.559 + return first->arc;
1.560 + }
1.561 +
1.562 + /// \brief Add a new arc before the current path
1.563 + void addFront(const Arc& arc) {
1.564 + Node *node = alloc.allocate(1);
1.565 + alloc.construct(node, Node());
1.566 + node->prev = 0;
1.567 + node->next = first;
1.568 + node->arc = arc;
1.569 + if (first) {
1.570 + first->prev = node;
1.571 + first = node;
1.572 + } else {
1.573 + first = last = node;
1.574 + }
1.575 + }
1.576 +
1.577 + /// \brief Erase the first arc of the path
1.578 + void eraseFront() {
1.579 + Node *node = first;
1.580 + first = first->next;
1.581 + if (first) {
1.582 + first->prev = 0;
1.583 + } else {
1.584 + last = 0;
1.585 + }
1.586 + alloc.destroy(node);
1.587 + alloc.deallocate(node, 1);
1.588 + }
1.589 +
1.590 + /// \brief Gives back the last arc of the path.
1.591 + const Arc& back() const {
1.592 + return last->arc;
1.593 + }
1.594 +
1.595 + /// \brief Add a new arc behind the current path.
1.596 + void addBack(const Arc& arc) {
1.597 + Node *node = alloc.allocate(1);
1.598 + alloc.construct(node, Node());
1.599 + node->next = 0;
1.600 + node->prev = last;
1.601 + node->arc = arc;
1.602 + if (last) {
1.603 + last->next = node;
1.604 + last = node;
1.605 + } else {
1.606 + last = first = node;
1.607 + }
1.608 + }
1.609 +
1.610 + /// \brief Erase the last arc of the path
1.611 + void eraseBack() {
1.612 + Node *node = last;
1.613 + last = last->prev;
1.614 + if (last) {
1.615 + last->next = 0;
1.616 + } else {
1.617 + first = 0;
1.618 + }
1.619 + alloc.destroy(node);
1.620 + alloc.deallocate(node, 1);
1.621 + }
1.622 +
1.623 + /// \brief Splicing the given path to the current path.
1.624 + ///
1.625 + /// It splices the \c tpath to the back of the current path and \c
1.626 + /// tpath becomes empty. The time complexity of this function is
1.627 + /// O(1).
1.628 + void spliceBack(ListPath& tpath) {
1.629 + if (first) {
1.630 + if (tpath.first) {
1.631 + last->next = tpath.first;
1.632 + tpath.first->prev = last;
1.633 + last = tpath.last;
1.634 + }
1.635 + } else {
1.636 + first = tpath.first;
1.637 + last = tpath.last;
1.638 + }
1.639 + tpath.first = tpath.last = 0;
1.640 + }
1.641 +
1.642 + /// \brief Splicing the given path to the current path.
1.643 + ///
1.644 + /// It splices the \c tpath before the current path and \c tpath
1.645 + /// becomes empty. The time complexity of this function
1.646 + /// is O(1).
1.647 + void spliceFront(ListPath& tpath) {
1.648 + if (first) {
1.649 + if (tpath.first) {
1.650 + first->prev = tpath.last;
1.651 + tpath.last->next = first;
1.652 + first = tpath.first;
1.653 + }
1.654 + } else {
1.655 + first = tpath.first;
1.656 + last = tpath.last;
1.657 + }
1.658 + tpath.first = tpath.last = 0;
1.659 + }
1.660 +
1.661 + /// \brief Splicing the given path into the current path.
1.662 + ///
1.663 + /// It splices the \c tpath into the current path before the
1.664 + /// position of \c it iterator and \c tpath becomes empty. The
1.665 + /// time complexity of this function is O(1). If the \c it is \c
1.666 + /// INVALID then it will splice behind the current path.
1.667 + void splice(ArcIt it, ListPath& tpath) {
1.668 + if (it.node) {
1.669 + if (tpath.first) {
1.670 + tpath.first->prev = it.node->prev;
1.671 + if (it.node->prev) {
1.672 + it.node->prev->next = tpath.first;
1.673 + } else {
1.674 + first = tpath.first;
1.675 + }
1.676 + it.node->prev = tpath.last;
1.677 + tpath.last->next = it.node;
1.678 + }
1.679 + } else {
1.680 + if (first) {
1.681 + if (tpath.first) {
1.682 + last->next = tpath.first;
1.683 + tpath.first->prev = last;
1.684 + last = tpath.last;
1.685 + }
1.686 + } else {
1.687 + first = tpath.first;
1.688 + last = tpath.last;
1.689 + }
1.690 + }
1.691 + tpath.first = tpath.last = 0;
1.692 + }
1.693 +
1.694 + /// \brief Spliting the current path.
1.695 + ///
1.696 + /// It splits the current path into two parts. The part before \c
1.697 + /// it iterator will remain in the current path and the part from
1.698 + /// the it will put into the \c tpath. If the \c tpath had arcs
1.699 + /// before the operation they will be removed first. The time
1.700 + /// complexity of this function is O(1) plus the clearing of \c
1.701 + /// tpath. If the \c it is \c INVALID then it just clears \c
1.702 + /// tpath.
1.703 + void split(ArcIt it, ListPath& tpath) {
1.704 + tpath.clear();
1.705 + if (it.node) {
1.706 + tpath.first = it.node;
1.707 + tpath.last = last;
1.708 + if (it.node->prev) {
1.709 + last = it.node->prev;
1.710 + last->next = 0;
1.711 + } else {
1.712 + first = last = 0;
1.713 + }
1.714 + it.node->prev = 0;
1.715 + }
1.716 + }
1.717 +
1.718 +
1.719 + typedef True BuildTag;
1.720 +
1.721 + template <typename CPath>
1.722 + void build(const CPath& path) {
1.723 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.724 + addBack(it);
1.725 + }
1.726 + }
1.727 +
1.728 + template <typename CPath>
1.729 + void buildRev(const CPath& path) {
1.730 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.731 + addFront(it);
1.732 + }
1.733 + }
1.734 +
1.735 + };
1.736 +
1.737 + /// \brief A structure for representing directed paths in a digraph.
1.738 + ///
1.739 + /// A structure for representing directed path in a digraph.
1.740 + /// \param Digraph The digraph type in which the path is.
1.741 + ///
1.742 + /// In a sense, the path can be treated as a list of arcs. The
1.743 + /// lemon path type stores just this list. As a consequence it
1.744 + /// cannot enumerate the nodes in the path and the zero length paths
1.745 + /// cannot store the source.
1.746 + ///
1.747 + /// This implementation is completly static, so it cannot be
1.748 + /// modified exclude the assign an other path. It is intented to be
1.749 + /// used when you want to store a large number of paths because it is
1.750 + /// the most memory efficient path type in the lemon.
1.751 + template <typename _Digraph>
1.752 + class StaticPath {
1.753 + public:
1.754 +
1.755 + typedef _Digraph Digraph;
1.756 + typedef typename Digraph::Arc Arc;
1.757 +
1.758 + /// \brief Default constructor
1.759 + ///
1.760 + /// Default constructor
1.761 + StaticPath() : len(0), arcs(0) {}
1.762 +
1.763 + /// \brief Template copy constructor
1.764 + ///
1.765 + /// This path can be initialized with any other path type. It just
1.766 + /// makes a copy of the given path.
1.767 + template <typename CPath>
1.768 + StaticPath(const CPath& cpath) : arcs(0) {
1.769 + copyPath(*this, cpath);
1.770 + }
1.771 +
1.772 + /// \brief Destructor of the path
1.773 + ///
1.774 + /// Destructor of the path
1.775 + ~StaticPath() {
1.776 + if (arcs) delete[] arcs;
1.777 + }
1.778 +
1.779 + /// \brief Template copy assignment
1.780 + ///
1.781 + /// This path can be initialized with any other path type. It just
1.782 + /// makes a copy of the given path.
1.783 + template <typename CPath>
1.784 + StaticPath& operator=(const CPath& cpath) {
1.785 + copyPath(*this, cpath);
1.786 + return *this;
1.787 + }
1.788 +
1.789 + /// \brief Iterator class to iterate on the arcs of the paths
1.790 + ///
1.791 + /// This class is used to iterate on the arcs of the paths
1.792 + ///
1.793 + /// Of course it converts to Digraph::Arc
1.794 + class ArcIt {
1.795 + friend class StaticPath;
1.796 + public:
1.797 + /// Default constructor
1.798 + ArcIt() {}
1.799 + /// Invalid constructor
1.800 + ArcIt(Invalid) : path(0), idx(-1) {}
1.801 + /// Initializate the constructor to the first arc of path
1.802 + ArcIt(const StaticPath &_path)
1.803 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.804 +
1.805 + private:
1.806 +
1.807 + /// Constructor with starting point
1.808 + ArcIt(const StaticPath &_path, int _idx)
1.809 + : idx(_idx), path(&_path) {}
1.810 +
1.811 + public:
1.812 +
1.813 + ///Conversion to Digraph::Arc
1.814 + operator const Arc&() const {
1.815 + return path->nth(idx);
1.816 + }
1.817 +
1.818 + /// Next arc
1.819 + ArcIt& operator++() {
1.820 + ++idx;
1.821 + if (idx >= path->length()) idx = -1;
1.822 + return *this;
1.823 + }
1.824 +
1.825 + /// Comparison operator
1.826 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
1.827 + /// Comparison operator
1.828 + bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
1.829 + /// Comparison operator
1.830 + bool operator<(const ArcIt& e) const { return idx<e.idx; }
1.831 +
1.832 + private:
1.833 + const StaticPath *path;
1.834 + int idx;
1.835 + };
1.836 +
1.837 + /// \brief Gives back the nth arc.
1.838 + ///
1.839 + /// \pre n is in the [0..length() - 1] range
1.840 + const Arc& nth(int n) const {
1.841 + return arcs[n];
1.842 + }
1.843 +
1.844 + /// \brief Initializes arc iterator to point to the nth arc.
1.845 + ArcIt nthIt(int n) const {
1.846 + return ArcIt(*this, n);
1.847 + }
1.848 +
1.849 + /// \brief Gives back the length of the path.
1.850 + int length() const { return len; }
1.851 +
1.852 + /// \brief Returns true when the path is empty.
1.853 + int empty() const { return len == 0; }
1.854 +
1.855 + /// \break Erase all arc in the digraph.
1.856 + void clear() {
1.857 + len = 0;
1.858 + if (arcs) delete[] arcs;
1.859 + arcs = 0;
1.860 + }
1.861 +
1.862 + /// \brief Gives back the first arc of the path.
1.863 + const Arc& front() const {
1.864 + return arcs[0];
1.865 + }
1.866 +
1.867 + /// \brief Gives back the last arc of the path.
1.868 + const Arc& back() const {
1.869 + return arcs[len - 1];
1.870 + }
1.871 +
1.872 +
1.873 + typedef True BuildTag;
1.874 +
1.875 + template <typename CPath>
1.876 + void build(const CPath& path) {
1.877 + len = path.length();
1.878 + arcs = new Arc[len];
1.879 + int index = 0;
1.880 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.881 + arcs[index] = it;
1.882 + ++index;
1.883 + }
1.884 + }
1.885 +
1.886 + template <typename CPath>
1.887 + void buildRev(const CPath& path) {
1.888 + len = path.length();
1.889 + arcs = new Arc[len];
1.890 + int index = len;
1.891 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.892 + --index;
1.893 + arcs[index] = it;
1.894 + }
1.895 + }
1.896 +
1.897 + private:
1.898 + int len;
1.899 + Arc* arcs;
1.900 + };
1.901 +
1.902 + ///@}
1.903 +
1.904 +} // namespace lemon
1.905 +
1.906 +#endif // LEMON_PATH_H