1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/path.h Thu Mar 20 12:12:24 2008 +0000
1.3 @@ -0,0 +1,1079 @@
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/error.h>
1.34 +#include <lemon/bits/invalid.h>
1.35 +#include <lemon/concepts/path.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 of the path and the source node of
1.51 + /// a zero length path is undefined.
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 erase is done in O(1) (amortized) time. The
1.56 + /// implementation uses two vectors for storing the front and back
1.57 + /// insertions.
1.58 + template <typename _Digraph>
1.59 + class Path {
1.60 + public:
1.61 +
1.62 + typedef _Digraph Digraph;
1.63 + typedef typename Digraph::Arc Arc;
1.64 +
1.65 + /// \brief Default constructor
1.66 + ///
1.67 + /// Default constructor
1.68 + Path() {}
1.69 +
1.70 + /// \brief Template copy constructor
1.71 + ///
1.72 + /// This constuctor initializes the path from any other path type.
1.73 + /// It simply makes a copy of the given path.
1.74 + template <typename CPath>
1.75 + Path(const CPath& cpath) {
1.76 + copyPath(*this, cpath);
1.77 + }
1.78 +
1.79 + /// \brief Template copy assignment
1.80 + ///
1.81 + /// This operator makes a copy of a path of any other type.
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 iterator 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 Return whether the path is empty.
1.136 + bool empty() const { return head.empty() && tail.empty(); }
1.137 +
1.138 + /// \brief Reset the path to an empty one.
1.139 + void clear() { head.clear(); tail.clear(); }
1.140 +
1.141 + /// \brief 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 Initialize 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 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 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 + typedef True BuildTag;
1.206 +
1.207 + template <typename CPath>
1.208 + void build(const CPath& path) {
1.209 + int len = path.length();
1.210 + tail.reserve(len);
1.211 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.212 + tail.push_back(it);
1.213 + }
1.214 + }
1.215 +
1.216 + template <typename CPath>
1.217 + void buildRev(const CPath& path) {
1.218 + int len = path.length();
1.219 + head.reserve(len);
1.220 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.221 + head.push_back(it);
1.222 + }
1.223 + }
1.224 +
1.225 + protected:
1.226 + typedef std::vector<Arc> Container;
1.227 + Container head, tail;
1.228 +
1.229 + };
1.230 +
1.231 + /// \brief A structure for representing directed paths in a digraph.
1.232 + ///
1.233 + /// A structure for representing directed path in a digraph.
1.234 + /// \param Digraph The digraph type in which the path is.
1.235 + ///
1.236 + /// In a sense, the path can be treated as a list of arcs. The
1.237 + /// lemon path type stores just this list. As a consequence it
1.238 + /// cannot enumerate the nodes in the path and the zero length paths
1.239 + /// cannot store the source.
1.240 + ///
1.241 + /// This implementation is a just back insertable and erasable path
1.242 + /// type. It can be indexed in O(1) time. The back insertion and
1.243 + /// erasure is amortized O(1) time. This implementation is faster
1.244 + /// then the \c Path type because it use just one vector for the
1.245 + /// arcs.
1.246 + template <typename _Digraph>
1.247 + class SimplePath {
1.248 + public:
1.249 +
1.250 + typedef _Digraph Digraph;
1.251 + typedef typename Digraph::Arc Arc;
1.252 +
1.253 + /// \brief Default constructor
1.254 + ///
1.255 + /// Default constructor
1.256 + SimplePath() {}
1.257 +
1.258 + /// \brief Template copy constructor
1.259 + ///
1.260 + /// This path can be initialized with any other path type. It just
1.261 + /// makes a copy of the given path.
1.262 + template <typename CPath>
1.263 + SimplePath(const CPath& cpath) {
1.264 + copyPath(*this, cpath);
1.265 + }
1.266 +
1.267 + /// \brief Template copy assignment
1.268 + ///
1.269 + /// This path can be initialized with any other path type. It just
1.270 + /// makes a copy of the given path.
1.271 + template <typename CPath>
1.272 + SimplePath& operator=(const CPath& cpath) {
1.273 + copyPath(*this, cpath);
1.274 + return *this;
1.275 + }
1.276 +
1.277 + /// \brief Iterator class to iterate on the arcs of the paths
1.278 + ///
1.279 + /// This class is used to iterate on the arcs of the paths
1.280 + ///
1.281 + /// Of course it converts to Digraph::Arc
1.282 + class ArcIt {
1.283 + friend class SimplePath;
1.284 + public:
1.285 + /// Default constructor
1.286 + ArcIt() {}
1.287 + /// Invalid constructor
1.288 + ArcIt(Invalid) : path(0), idx(-1) {}
1.289 + /// \brief Initializate the constructor to the first arc of path
1.290 + ArcIt(const SimplePath &_path)
1.291 + : path(&_path), idx(_path.empty() ? -1 : 0) {}
1.292 +
1.293 + private:
1.294 +
1.295 + /// Constructor with starting point
1.296 + ArcIt(const SimplePath &_path, int _idx)
1.297 + : idx(_idx), path(&_path) {}
1.298 +
1.299 + public:
1.300 +
1.301 + ///Conversion to Digraph::Arc
1.302 + operator const Arc&() const {
1.303 + return path->nth(idx);
1.304 + }
1.305 +
1.306 + /// Next arc
1.307 + ArcIt& operator++() {
1.308 + ++idx;
1.309 + if (idx >= path->length()) idx = -1;
1.310 + return *this;
1.311 + }
1.312 +
1.313 + /// Comparison operator
1.314 + bool operator==(const ArcIt& e) const { return idx==e.idx; }
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 +
1.320 + private:
1.321 + const SimplePath *path;
1.322 + int idx;
1.323 + };
1.324 +
1.325 + /// \brief Length of the path.
1.326 + int length() const { return data.size(); }
1.327 + /// \brief Return true if the path is empty.
1.328 + bool empty() const { return data.empty(); }
1.329 +
1.330 + /// \brief Reset the path to an empty one.
1.331 + void clear() { data.clear(); }
1.332 +
1.333 + /// \brief The nth arc.
1.334 + ///
1.335 + /// \pre n is in the [0..length() - 1] range
1.336 + const Arc& nth(int n) const {
1.337 + return data[n];
1.338 + }
1.339 +
1.340 + /// \brief Initializes arc iterator to point to the nth arc.
1.341 + ArcIt nthIt(int n) const {
1.342 + return ArcIt(*this, n);
1.343 + }
1.344 +
1.345 + /// \brief The first arc of the path.
1.346 + const Arc& front() const {
1.347 + return data.front();
1.348 + }
1.349 +
1.350 + /// \brief The last arc of the path.
1.351 + const Arc& back() const {
1.352 + return data.back();
1.353 + }
1.354 +
1.355 + /// \brief Add a new arc behind the current path.
1.356 + void addBack(const Arc& arc) {
1.357 + data.push_back(arc);
1.358 + }
1.359 +
1.360 + /// \brief Erase the last arc of the path
1.361 + void eraseBack() {
1.362 + data.pop_back();
1.363 + }
1.364 +
1.365 + typedef True BuildTag;
1.366 +
1.367 + template <typename CPath>
1.368 + void build(const CPath& path) {
1.369 + int len = path.length();
1.370 + data.resize(len);
1.371 + int index = 0;
1.372 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.373 + data[index] = it;;
1.374 + ++index;
1.375 + }
1.376 + }
1.377 +
1.378 + template <typename CPath>
1.379 + void buildRev(const CPath& path) {
1.380 + int len = path.length();
1.381 + data.resize(len);
1.382 + int index = len;
1.383 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.384 + --index;
1.385 + data[index] = it;;
1.386 + }
1.387 + }
1.388 +
1.389 + protected:
1.390 + typedef std::vector<Arc> Container;
1.391 + Container data;
1.392 +
1.393 + };
1.394 +
1.395 + /// \brief A structure for representing directed paths in a digraph.
1.396 + ///
1.397 + /// A structure for representing directed path in a digraph.
1.398 + /// \param Digraph The digraph type in which the path is.
1.399 + ///
1.400 + /// In a sense, the path can be treated as a list of arcs. The
1.401 + /// lemon path type stores just this list. As a consequence it
1.402 + /// cannot enumerate the nodes in the path and the zero length paths
1.403 + /// cannot store the source.
1.404 + ///
1.405 + /// This implementation is a back and front insertable and erasable
1.406 + /// path type. It can be indexed in O(k) time, where k is the rank
1.407 + /// of the arc in the path. The length can be computed in O(n)
1.408 + /// time. The front and back insertion and erasure is O(1) time
1.409 + /// and it can be splited and spliced in O(1) time.
1.410 + template <typename _Digraph>
1.411 + class ListPath {
1.412 + public:
1.413 +
1.414 + typedef _Digraph Digraph;
1.415 + typedef typename Digraph::Arc Arc;
1.416 +
1.417 + protected:
1.418 +
1.419 + // the std::list<> is incompatible
1.420 + // hard to create invalid iterator
1.421 + struct Node {
1.422 + Arc arc;
1.423 + Node *next, *prev;
1.424 + };
1.425 +
1.426 + Node *first, *last;
1.427 +
1.428 + std::allocator<Node> alloc;
1.429 +
1.430 + public:
1.431 +
1.432 + /// \brief Default constructor
1.433 + ///
1.434 + /// Default constructor
1.435 + ListPath() : first(0), last(0) {}
1.436 +
1.437 + /// \brief Template copy constructor
1.438 + ///
1.439 + /// This path can be initialized with any other path type. It just
1.440 + /// makes a copy of the given path.
1.441 + template <typename CPath>
1.442 + ListPath(const CPath& cpath) : first(0), last(0) {
1.443 + copyPath(*this, cpath);
1.444 + }
1.445 +
1.446 + /// \brief Destructor of the path
1.447 + ///
1.448 + /// Destructor of the path
1.449 + ~ListPath() {
1.450 + clear();
1.451 + }
1.452 +
1.453 + /// \brief Template copy assignment
1.454 + ///
1.455 + /// This path can be initialized with any other path type. It just
1.456 + /// makes a copy of the given path.
1.457 + template <typename CPath>
1.458 + ListPath& operator=(const CPath& cpath) {
1.459 + copyPath(*this, cpath);
1.460 + return *this;
1.461 + }
1.462 +
1.463 + /// \brief Iterator class to iterate on the arcs of the paths
1.464 + ///
1.465 + /// This class is used to iterate on the arcs of the paths
1.466 + ///
1.467 + /// Of course it converts to Digraph::Arc
1.468 + class ArcIt {
1.469 + friend class ListPath;
1.470 + public:
1.471 + /// Default constructor
1.472 + ArcIt() {}
1.473 + /// Invalid constructor
1.474 + ArcIt(Invalid) : path(0), node(0) {}
1.475 + /// \brief Initializate the constructor to the first arc of path
1.476 + ArcIt(const ListPath &_path)
1.477 + : path(&_path), node(_path.first) {}
1.478 +
1.479 + protected:
1.480 +
1.481 + ArcIt(const ListPath &_path, Node *_node)
1.482 + : path(&_path), node(_node) {}
1.483 +
1.484 +
1.485 + public:
1.486 +
1.487 + ///Conversion to Digraph::Arc
1.488 + operator const Arc&() const {
1.489 + return node->arc;
1.490 + }
1.491 +
1.492 + /// Next arc
1.493 + ArcIt& operator++() {
1.494 + node = node->next;
1.495 + return *this;
1.496 + }
1.497 +
1.498 + /// Comparison operator
1.499 + bool operator==(const ArcIt& e) const { return node==e.node; }
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 +
1.505 + private:
1.506 + const ListPath *path;
1.507 + Node *node;
1.508 + };
1.509 +
1.510 + /// \brief The nth arc.
1.511 + ///
1.512 + /// This function looks for the nth arc in O(n) time.
1.513 + /// \pre n is in the [0..length() - 1] range
1.514 + const Arc& nth(int n) const {
1.515 + Node *node = first;
1.516 + for (int i = 0; i < n; ++i) {
1.517 + node = node->next;
1.518 + }
1.519 + return node->arc;
1.520 + }
1.521 +
1.522 + /// \brief Initializes arc iterator to point to the nth arc.
1.523 + ArcIt nthIt(int n) const {
1.524 + Node *node = first;
1.525 + for (int i = 0; i < n; ++i) {
1.526 + node = node->next;
1.527 + }
1.528 + return ArcIt(*this, node);
1.529 + }
1.530 +
1.531 + /// \brief Length of the path.
1.532 + int length() const {
1.533 + int len = 0;
1.534 + Node *node = first;
1.535 + while (node != 0) {
1.536 + node = node->next;
1.537 + ++len;
1.538 + }
1.539 + return len;
1.540 + }
1.541 +
1.542 + /// \brief Return true if the path is empty.
1.543 + bool empty() const { return first == 0; }
1.544 +
1.545 + /// \brief Reset the path to an empty one.
1.546 + void clear() {
1.547 + while (first != 0) {
1.548 + last = first->next;
1.549 + alloc.destroy(first);
1.550 + alloc.deallocate(first, 1);
1.551 + first = last;
1.552 + }
1.553 + }
1.554 +
1.555 + /// \brief The first arc of the path
1.556 + const Arc& front() const {
1.557 + return first->arc;
1.558 + }
1.559 +
1.560 + /// \brief Add a new arc before the current path
1.561 + void addFront(const Arc& arc) {
1.562 + Node *node = alloc.allocate(1);
1.563 + alloc.construct(node, Node());
1.564 + node->prev = 0;
1.565 + node->next = first;
1.566 + node->arc = arc;
1.567 + if (first) {
1.568 + first->prev = node;
1.569 + first = node;
1.570 + } else {
1.571 + first = last = node;
1.572 + }
1.573 + }
1.574 +
1.575 + /// \brief Erase the first arc of the path
1.576 + void eraseFront() {
1.577 + Node *node = first;
1.578 + first = first->next;
1.579 + if (first) {
1.580 + first->prev = 0;
1.581 + } else {
1.582 + last = 0;
1.583 + }
1.584 + alloc.destroy(node);
1.585 + alloc.deallocate(node, 1);
1.586 + }
1.587 +
1.588 + /// \brief The last arc of the path.
1.589 + const Arc& back() const {
1.590 + return last->arc;
1.591 + }
1.592 +
1.593 + /// \brief Add a new arc behind the current path.
1.594 + void addBack(const Arc& arc) {
1.595 + Node *node = alloc.allocate(1);
1.596 + alloc.construct(node, Node());
1.597 + node->next = 0;
1.598 + node->prev = last;
1.599 + node->arc = arc;
1.600 + if (last) {
1.601 + last->next = node;
1.602 + last = node;
1.603 + } else {
1.604 + last = first = node;
1.605 + }
1.606 + }
1.607 +
1.608 + /// \brief Erase the last arc of the path
1.609 + void eraseBack() {
1.610 + Node *node = last;
1.611 + last = last->prev;
1.612 + if (last) {
1.613 + last->next = 0;
1.614 + } else {
1.615 + first = 0;
1.616 + }
1.617 + alloc.destroy(node);
1.618 + alloc.deallocate(node, 1);
1.619 + }
1.620 +
1.621 + /// \brief Splice a path to the back of the current path.
1.622 + ///
1.623 + /// It splices \c tpath to the back of the current path and \c
1.624 + /// tpath becomes empty. The time complexity of this function is
1.625 + /// O(1).
1.626 + void spliceBack(ListPath& tpath) {
1.627 + if (first) {
1.628 + if (tpath.first) {
1.629 + last->next = tpath.first;
1.630 + tpath.first->prev = last;
1.631 + last = tpath.last;
1.632 + }
1.633 + } else {
1.634 + first = tpath.first;
1.635 + last = tpath.last;
1.636 + }
1.637 + tpath.first = tpath.last = 0;
1.638 + }
1.639 +
1.640 + /// \brief Splice a path to the front of the current path.
1.641 + ///
1.642 + /// It splices \c tpath before the current path and \c tpath
1.643 + /// becomes empty. The time complexity of this function
1.644 + /// is O(1).
1.645 + void spliceFront(ListPath& tpath) {
1.646 + if (first) {
1.647 + if (tpath.first) {
1.648 + first->prev = tpath.last;
1.649 + tpath.last->next = first;
1.650 + first = tpath.first;
1.651 + }
1.652 + } else {
1.653 + first = tpath.first;
1.654 + last = tpath.last;
1.655 + }
1.656 + tpath.first = tpath.last = 0;
1.657 + }
1.658 +
1.659 + /// \brief Splice a path into the current path.
1.660 + ///
1.661 + /// It splices the \c tpath into the current path before the
1.662 + /// position of \c it iterator and \c tpath becomes empty. The
1.663 + /// time complexity of this function is O(1). If the \c it is
1.664 + /// \c INVALID then it will splice behind the current path.
1.665 + void splice(ArcIt it, ListPath& tpath) {
1.666 + if (it.node) {
1.667 + if (tpath.first) {
1.668 + tpath.first->prev = it.node->prev;
1.669 + if (it.node->prev) {
1.670 + it.node->prev->next = tpath.first;
1.671 + } else {
1.672 + first = tpath.first;
1.673 + }
1.674 + it.node->prev = tpath.last;
1.675 + tpath.last->next = it.node;
1.676 + }
1.677 + } else {
1.678 + if (first) {
1.679 + if (tpath.first) {
1.680 + last->next = tpath.first;
1.681 + tpath.first->prev = last;
1.682 + last = tpath.last;
1.683 + }
1.684 + } else {
1.685 + first = tpath.first;
1.686 + last = tpath.last;
1.687 + }
1.688 + }
1.689 + tpath.first = tpath.last = 0;
1.690 + }
1.691 +
1.692 + /// \brief Split the current path.
1.693 + ///
1.694 + /// It splits the current path into two parts. The part before
1.695 + /// the iterator \c it will remain in the current path and the part
1.696 + /// starting with
1.697 + /// \c it will put into \c tpath. If \c tpath have arcs
1.698 + /// before the operation they are removed first. The time
1.699 + /// complexity of this function is O(1) plus the the time of emtying
1.700 + /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
1.701 + void split(ArcIt it, ListPath& tpath) {
1.702 + tpath.clear();
1.703 + if (it.node) {
1.704 + tpath.first = it.node;
1.705 + tpath.last = last;
1.706 + if (it.node->prev) {
1.707 + last = it.node->prev;
1.708 + last->next = 0;
1.709 + } else {
1.710 + first = last = 0;
1.711 + }
1.712 + it.node->prev = 0;
1.713 + }
1.714 + }
1.715 +
1.716 +
1.717 + typedef True BuildTag;
1.718 +
1.719 + template <typename CPath>
1.720 + void build(const CPath& path) {
1.721 + for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
1.722 + addBack(it);
1.723 + }
1.724 + }
1.725 +
1.726 + template <typename CPath>
1.727 + void buildRev(const CPath& path) {
1.728 + for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
1.729 + addFront(it);
1.730 + }
1.731 + }
1.732 +
1.733 + };
1.734 +
1.735 + /// \brief A structure for representing directed paths in a digraph.
1.736 + ///
1.737 + /// A structure for representing directed path in a digraph.
1.738 + /// \param Digraph The digraph type in which the path is.
1.739 + ///
1.740 + /// In a sense, the path can be treated as a list of arcs. The
1.741 + /// lemon path type stores just this list. As a consequence it
1.742 + /// cannot enumerate the nodes in the path and the source node of
1.743 + /// a zero length path is undefined.
1.744 + ///
1.745 + /// This implementation is completly static, i.e. it can be copy constucted
1.746 + /// or copy assigned from another path, but otherwise it cannot be
1.747 + /// modified.
1.748 + ///
1.749 + /// Being the the most memory efficient path type in LEMON,
1.750 + /// it is intented to be
1.751 + /// used when you want to store a large number of paths.
1.752 + template <typename _Digraph>
1.753 + class StaticPath {
1.754 + public:
1.755 +
1.756 + typedef _Digraph Digraph;
1.757 + typedef typename Digraph::Arc Arc;
1.758 +
1.759 + /// \brief Default constructor
1.760 + ///
1.761 + /// Default constructor
1.762 + StaticPath() : len(0), arcs(0) {}
1.763 +
1.764 + /// \brief Template copy constructor
1.765 + ///
1.766 + /// This path can be initialized from any other path type.
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 made equal to any other path type. It simply
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 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 The arc iterator pointing to the nth arc.
1.845 + ArcIt nthIt(int n) const {
1.846 + return ArcIt(*this, n);
1.847 + }
1.848 +
1.849 + /// \brief The length of the path.
1.850 + int length() const { return len; }
1.851 +
1.852 + /// \brief Return true when the path is empty.
1.853 + int empty() const { return len == 0; }
1.854 +
1.855 + /// \break Erase all arcs 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 The first arc of the path.
1.863 + const Arc& front() const {
1.864 + return arcs[0];
1.865 + }
1.866 +
1.867 + /// \brief 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 + // Additional utilities
1.904 + ///////////////////////////////////////////////////////////////////////
1.905 +
1.906 + namespace _path_bits {
1.907 +
1.908 + template <typename Path, typename Enable = void>
1.909 + struct RevTagIndicator {
1.910 + static const bool value = false;
1.911 + };
1.912 +
1.913 + template <typename Digraph>
1.914 + struct RevTagIndicator<
1.915 + Digraph,
1.916 + typename enable_if<typename Digraph::RevTag, void>::type
1.917 + > {
1.918 + static const bool value = true;
1.919 + };
1.920 +
1.921 + template <typename Target, typename Source,
1.922 + typename BuildEnable = void, typename RevEnable = void>
1.923 + struct PathCopySelector {
1.924 + static void copy(Target& target, const Source& source) {
1.925 + target.clear();
1.926 + for (typename Source::ArcIt it(source); it != INVALID; ++it) {
1.927 + target.addBack(it);
1.928 + }
1.929 + }
1.930 + };
1.931 +
1.932 + template <typename Target, typename Source, typename BuildEnable>
1.933 + struct PathCopySelector<
1.934 + Target, Source, BuildEnable,
1.935 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.936 + static void copy(Target& target, const Source& source) {
1.937 + target.clear();
1.938 + for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
1.939 + target.addFront(it);
1.940 + }
1.941 + }
1.942 + };
1.943 +
1.944 + template <typename Target, typename Source, typename RevEnable>
1.945 + struct PathCopySelector<
1.946 + Target, Source,
1.947 + typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
1.948 + static void copy(Target& target, const Source& source) {
1.949 + target.clear();
1.950 + target.build(source);
1.951 + }
1.952 + };
1.953 +
1.954 + template <typename Target, typename Source>
1.955 + struct PathCopySelector<
1.956 + Target, Source,
1.957 + typename enable_if<typename Target::BuildTag, void>::type,
1.958 + typename enable_if<typename Source::RevPathTag, void>::type> {
1.959 + static void copy(Target& target, const Source& source) {
1.960 + target.clear();
1.961 + target.buildRev(source);
1.962 + }
1.963 + };
1.964 +
1.965 + }
1.966 +
1.967 +
1.968 + /// \brief Make a copy of a path.
1.969 + ///
1.970 + /// This function makes a copy of a path.
1.971 + template <typename Target, typename Source>
1.972 + void copyPath(Target& target, const Source& source) {
1.973 + checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
1.974 + _path_bits::PathCopySelector<Target, Source>::copy(target, source);
1.975 + }
1.976 +
1.977 + /// \brief Check the consistency of a path.
1.978 + ///
1.979 + /// This function checks that the target of each arc is the same
1.980 + /// as the source of the next one.
1.981 + ///
1.982 + template <typename Digraph, typename Path>
1.983 + bool checkPath(const Digraph& digraph, const Path& path) {
1.984 + typename Path::ArcIt it(path);
1.985 + if (it == INVALID) return true;
1.986 + typename Digraph::Node node = digraph.target(it);
1.987 + ++it;
1.988 + while (it != INVALID) {
1.989 + if (digraph.source(it) != node) return false;
1.990 + node = digraph.target(it);
1.991 + ++it;
1.992 + }
1.993 + return true;
1.994 + }
1.995 +
1.996 + /// \brief The source of a path
1.997 + ///
1.998 + /// This function returns the source of the given path.
1.999 + template <typename Digraph, typename Path>
1.1000 + typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
1.1001 + return digraph.source(path.front());
1.1002 + }
1.1003 +
1.1004 + /// \brief The target of a path
1.1005 + ///
1.1006 + /// This function returns the target of the given path.
1.1007 + template <typename Digraph, typename Path>
1.1008 + typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
1.1009 + return digraph.target(path.back());
1.1010 + }
1.1011 +
1.1012 + /// \brief Class which helps to iterate through the nodes of a path
1.1013 + ///
1.1014 + /// In a sense, the path can be treated as a list of arcs. The
1.1015 + /// lemon path type stores only this list. As a consequence, it
1.1016 + /// cannot enumerate the nodes in the path and the zero length paths
1.1017 + /// cannot have a source node.
1.1018 + ///
1.1019 + /// This class implements the node iterator of a path structure. To
1.1020 + /// provide this feature, the underlying digraph should be passed to
1.1021 + /// the constructor of the iterator.
1.1022 + template <typename Path>
1.1023 + class PathNodeIt {
1.1024 + private:
1.1025 + const typename Path::Digraph *_digraph;
1.1026 + typename Path::ArcIt _it;
1.1027 + typename Path::Digraph::Node _nd;
1.1028 +
1.1029 + public:
1.1030 +
1.1031 + typedef typename Path::Digraph Digraph;
1.1032 + typedef typename Digraph::Node Node;
1.1033 +
1.1034 + /// Default constructor
1.1035 + PathNodeIt() {}
1.1036 + /// Invalid constructor
1.1037 + PathNodeIt(Invalid)
1.1038 + : _digraph(0), _it(INVALID), _nd(INVALID) {}
1.1039 + /// Constructor
1.1040 + PathNodeIt(const Digraph& digraph, const Path& path)
1.1041 + : _digraph(&digraph), _it(path) {
1.1042 + _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
1.1043 + }
1.1044 + /// Constructor
1.1045 + PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
1.1046 + : _digraph(&digraph), _it(path), _nd(src) {}
1.1047 +
1.1048 + ///Conversion to Digraph::Node
1.1049 + operator Node() const {
1.1050 + return _nd;
1.1051 + }
1.1052 +
1.1053 + /// Next node
1.1054 + PathNodeIt& operator++() {
1.1055 + if (_it == INVALID) _nd = INVALID;
1.1056 + else {
1.1057 + _nd = _digraph->target(_it);
1.1058 + ++_it;
1.1059 + }
1.1060 + return *this;
1.1061 + }
1.1062 +
1.1063 + /// Comparison operator
1.1064 + bool operator==(const PathNodeIt& n) const {
1.1065 + return _it == n._it && _nd == n._nd;
1.1066 + }
1.1067 + /// Comparison operator
1.1068 + bool operator!=(const PathNodeIt& n) const {
1.1069 + return _it != n._it || _nd != n._nd;
1.1070 + }
1.1071 + /// Comparison operator
1.1072 + bool operator<(const PathNodeIt& n) const {
1.1073 + return (_it < n._it && _nd != INVALID);
1.1074 + }
1.1075 +
1.1076 + };
1.1077 +
1.1078 + ///@}
1.1079 +
1.1080 +} // namespace lemon
1.1081 +
1.1082 +#endif // LEMON_PATH_H