1.1 --- a/src/work/peter/path/path.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1174 +0,0 @@
1.4 -// -*- c++ -*- //
1.5 -
1.6 -/**
1.7 -@defgroup paths Path Structures
1.8 -@ingroup datas
1.9 -\brief Path structures implemented in LEMON.
1.10 -
1.11 -LEMON provides flexible data structures
1.12 -to work with paths.
1.13 -
1.14 -All of them have the same interface, especially they can be built or extended
1.15 -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
1.16 -algorithm to store its result in any kind of path structure.
1.17 -
1.18 -\sa lemon::concept::Path
1.19 -
1.20 -*/
1.21 -
1.22 -///\ingroup paths
1.23 -///\file
1.24 -///\brief Classes for representing paths in graphs.
1.25 -
1.26 -#ifndef LEMON_PATH_H
1.27 -#define LEMON_PATH_H
1.28 -
1.29 -#include <deque>
1.30 -#include <vector>
1.31 -#include <algorithm>
1.32 -
1.33 -#include <lemon/invalid.h>
1.34 -#include <lemon/error.h>
1.35 -#include <debug.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 graph.
1.44 - //!
1.45 - //! A structure for representing directed path in a graph.
1.46 - //! \param Graph The graph type in which the path is.
1.47 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.48 - //!
1.49 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.50 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.51 - //! and \c Edge of the original graph.
1.52 - //!
1.53 - //! \todo Thoroughfully check all the range and consistency tests.
1.54 - template<typename Graph, typename DM = DefaultDebugMode>
1.55 - class DirPath {
1.56 - public:
1.57 - /// Edge type of the underlying graph.
1.58 - typedef typename Graph::Edge GraphEdge;
1.59 - /// Node type of the underlying graph.
1.60 - typedef typename Graph::Node GraphNode;
1.61 - class NodeIt;
1.62 - class EdgeIt;
1.63 -
1.64 - protected:
1.65 - const Graph *gr;
1.66 - typedef std::vector<GraphEdge> Container;
1.67 - Container edges;
1.68 -
1.69 - public:
1.70 -
1.71 - /// \param _G The graph in which the path is.
1.72 - ///
1.73 - DirPath(const Graph &_G) : gr(&_G) {}
1.74 -
1.75 - /// \brief Subpath constructor.
1.76 - ///
1.77 - /// Subpath defined by two nodes.
1.78 - /// \warning It is an error if the two edges are not in order!
1.79 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.80 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.81 - // FIXME: this check should be more elaborate...
1.82 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.83 - }
1.84 - gr = P.gr;
1.85 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.86 - }
1.87 -
1.88 - /// \brief Subpath constructor.
1.89 - ///
1.90 - /// Subpath defined by two edges. Contains edges in [a,b)
1.91 - /// \warning It is an error if the two edges are not in order!
1.92 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.93 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.94 - // FIXME: this check should be more elaborate...
1.95 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.96 - }
1.97 - gr = P.gr;
1.98 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.99 - }
1.100 -
1.101 - /// Length of the path.
1.102 - size_t length() const { return edges.size(); }
1.103 - /// Returns whether the path is empty.
1.104 - bool empty() const { return edges.empty(); }
1.105 -
1.106 - /// Resets the path to an empty path.
1.107 - void clear() { edges.clear(); }
1.108 -
1.109 - /// \brief Starting point of the path.
1.110 - ///
1.111 - /// Starting point of the path.
1.112 - /// Returns INVALID if the path is empty.
1.113 - GraphNode from() const {
1.114 - return empty() ? INVALID : gr->source(edges[0]);
1.115 - }
1.116 - /// \brief End point of the path.
1.117 - ///
1.118 - /// End point of the path.
1.119 - /// Returns INVALID if the path is empty.
1.120 - GraphNode to() const {
1.121 - return empty() ? INVALID : gr->target(edges[length()-1]);
1.122 - }
1.123 -
1.124 - /// \brief Initializes node or edge iterator to point to the first
1.125 - /// node or edge.
1.126 - ///
1.127 - /// \sa nth
1.128 - template<typename It>
1.129 - It& first(It &i) const { return i=It(*this); }
1.130 -
1.131 - /// \brief Initializes node iterator to point to the node of a given index.
1.132 - NodeIt& nth(NodeIt &i, int n) const {
1.133 - if( DM::range_check && (n<0 || n>int(length())) )
1.134 - fault("DirPath::nth: index out of range");
1.135 - return i=NodeIt(*this, n);
1.136 - }
1.137 -
1.138 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.139 - EdgeIt& nth(EdgeIt &i, int n) const {
1.140 - if( DM::range_check && (n<0 || n>=int(length())) )
1.141 - fault("DirPath::nth: index out of range");
1.142 - return i=EdgeIt(*this, n);
1.143 - }
1.144 -
1.145 - /// Checks validity of a node or edge iterator.
1.146 - template<typename It>
1.147 - static
1.148 - bool valid(const It &i) { return i.valid(); }
1.149 -
1.150 - /// Steps the given node or edge iterator.
1.151 - template<typename It>
1.152 - static
1.153 - It& next(It &e) {
1.154 - if( DM::range_check && !e.valid() )
1.155 - fault("DirPath::next() on invalid iterator");
1.156 - return ++e;
1.157 - }
1.158 -
1.159 - /// \brief Returns node iterator pointing to the target node of the
1.160 - /// given edge iterator.
1.161 - NodeIt target(const EdgeIt& e) const {
1.162 - if( DM::range_check && !e.valid() )
1.163 - fault("DirPath::target() on invalid iterator");
1.164 - return NodeIt(*this, e.idx+1);
1.165 - }
1.166 -
1.167 - /// \brief Returns node iterator pointing to the source node of the
1.168 - /// given edge iterator.
1.169 - NodeIt source(const EdgeIt& e) const {
1.170 - if( DM::range_check && !e.valid() )
1.171 - fault("DirPath::source() on invalid iterator");
1.172 - return NodeIt(*this, e.idx);
1.173 - }
1.174 -
1.175 -
1.176 - /* Iterator classes */
1.177 -
1.178 - /**
1.179 - * \brief Iterator class to iterate on the edges of the paths
1.180 - *
1.181 - * \ingroup paths
1.182 - * This class is used to iterate on the edges of the paths
1.183 - *
1.184 - * Of course it converts to Graph::Edge
1.185 - *
1.186 - * \todo Its interface differs from the standard edge iterator.
1.187 - * Yes, it shouldn't.
1.188 - */
1.189 - class EdgeIt {
1.190 - friend class DirPath;
1.191 -
1.192 - int idx;
1.193 - const DirPath *p;
1.194 - public:
1.195 - /// Default constructor
1.196 - EdgeIt() {}
1.197 - /// Invalid constructor
1.198 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.199 - /// Constructor with starting point
1.200 - EdgeIt(const DirPath &_p, int _idx = 0) :
1.201 - idx(_idx), p(&_p) { validate(); }
1.202 -
1.203 - ///Validity check
1.204 - bool valid() const { return idx!=-1; }
1.205 -
1.206 - ///Conversion to Graph::Edge
1.207 - operator GraphEdge () const {
1.208 - return valid() ? p->edges[idx] : INVALID;
1.209 - }
1.210 -
1.211 - /// Next edge
1.212 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.213 -
1.214 - /// Comparison operator
1.215 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.216 - /// Comparison operator
1.217 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.218 - /// Comparison operator
1.219 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.220 -
1.221 - private:
1.222 - // FIXME: comparison between signed and unsigned...
1.223 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.224 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.225 - };
1.226 -
1.227 - /**
1.228 - * \brief Iterator class to iterate on the nodes of the paths
1.229 - *
1.230 - * \ingroup paths
1.231 - * This class is used to iterate on the nodes of the paths
1.232 - *
1.233 - * Of course it converts to Graph::Node
1.234 - *
1.235 - * \todo Its interface differs from the standard node iterator.
1.236 - * Yes, it shouldn't.
1.237 - */
1.238 - class NodeIt {
1.239 - friend class DirPath;
1.240 -
1.241 - int idx;
1.242 - const DirPath *p;
1.243 - public:
1.244 - /// Default constructor
1.245 - NodeIt() {}
1.246 - /// Invalid constructor
1.247 - NodeIt(Invalid) : idx(-1), p(0) {}
1.248 - /// Constructor with starting point
1.249 - NodeIt(const DirPath &_p, int _idx = 0) :
1.250 - idx(_idx), p(&_p) { validate(); }
1.251 -
1.252 - ///Validity check
1.253 - bool valid() const { return idx!=-1; }
1.254 -
1.255 - ///Conversion to Graph::Node
1.256 - operator const GraphNode& () const {
1.257 - if(idx >= p->length())
1.258 - return p->to();
1.259 - else if(idx >= 0)
1.260 - return p->gr->source(p->edges[idx]);
1.261 - else
1.262 - return INVALID;
1.263 - }
1.264 - /// Next node
1.265 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.266 -
1.267 - /// Comparison operator
1.268 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.269 - /// Comparison operator
1.270 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.271 - /// Comparison operator
1.272 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.273 -
1.274 - private:
1.275 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.276 - };
1.277 -
1.278 - friend class Builder;
1.279 -
1.280 - /**
1.281 - * \brief Class to build paths
1.282 - *
1.283 - * \ingroup paths
1.284 - * This class is used to fill a path with edges.
1.285 - *
1.286 - * You can push new edges to the front and to the back of the path in
1.287 - * arbitrary order then you should commit these changes to the graph.
1.288 - *
1.289 - * Fundamentally, for most "Paths" (classes fulfilling the
1.290 - * PathConcept) while the builder is active (after the first modifying
1.291 - * operation and until the commit()) the original Path is in a
1.292 - * "transitional" state (operations on it have undefined result). But
1.293 - * in the case of DirPath the original path remains unchanged until the
1.294 - * commit. However we don't recomend that you use this feature.
1.295 - */
1.296 - class Builder {
1.297 - DirPath &P;
1.298 - Container front, back;
1.299 -
1.300 - public:
1.301 - ///\param _P the path you want to fill in.
1.302 - ///
1.303 - Builder(DirPath &_P) : P(_P) {}
1.304 -
1.305 - /// Sets the starting node of the path.
1.306 -
1.307 - /// Sets the starting node of the path. Edge added to the path
1.308 - /// afterwards have to be incident to this node.
1.309 - /// It should be called iff the path is empty and before any call to
1.310 - /// \ref pushFront() or \ref pushBack()
1.311 - void setStartNode(const GraphNode &) {}
1.312 -
1.313 - ///Push a new edge to the front of the path
1.314 -
1.315 - ///Push a new edge to the front of the path.
1.316 - ///\sa setStartNode
1.317 - void pushFront(const GraphEdge& e) {
1.318 - if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) {
1.319 - fault("DirPath::Builder::pushFront: nonincident edge");
1.320 - }
1.321 - front.push_back(e);
1.322 - }
1.323 -
1.324 - ///Push a new edge to the back of the path
1.325 -
1.326 - ///Push a new edge to the back of the path.
1.327 - ///\sa setStartNode
1.328 - void pushBack(const GraphEdge& e) {
1.329 - if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) {
1.330 - fault("DirPath::Builder::pushBack: nonincident edge");
1.331 - }
1.332 - back.push_back(e);
1.333 - }
1.334 -
1.335 - ///Commit the changes to the path.
1.336 - void commit() {
1.337 - if( !(front.empty() && back.empty()) ) {
1.338 - Container tmp;
1.339 - tmp.reserve(front.size()+back.size()+P.length());
1.340 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.341 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.342 - tmp.insert(tmp.end(), back.begin(), back.end());
1.343 - P.edges.swap(tmp);
1.344 - front.clear();
1.345 - back.clear();
1.346 - }
1.347 - }
1.348 -
1.349 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.350 - // Hogy kenyelmes egy ilyet hasznalni?
1.351 -
1.352 - ///Reserve storage for the builder in advance.
1.353 -
1.354 - ///If you know an reasonable upper bound of the number of the edges
1.355 - ///to add, using this function you can speed up the building.
1.356 - void reserve(size_t r) {
1.357 - front.reserve(r);
1.358 - back.reserve(r);
1.359 - }
1.360 -
1.361 - private:
1.362 - bool empty() {
1.363 - return front.empty() && back.empty() && P.empty();
1.364 - }
1.365 -
1.366 - GraphNode from() const {
1.367 - if( ! front.empty() )
1.368 - return P.gr->source(front[front.size()-1]);
1.369 - else if( ! P.empty() )
1.370 - return P.gr->source(P.edges[0]);
1.371 - else if( ! back.empty() )
1.372 - return P.gr->source(back[0]);
1.373 - else
1.374 - return INVALID;
1.375 - }
1.376 - GraphNode to() const {
1.377 - if( ! back.empty() )
1.378 - return P.gr->target(back[back.size()-1]);
1.379 - else if( ! P.empty() )
1.380 - return P.gr->target(P.edges[P.length()-1]);
1.381 - else if( ! front.empty() )
1.382 - return P.gr->target(front[0]);
1.383 - else
1.384 - return INVALID;
1.385 - }
1.386 -
1.387 - };
1.388 -
1.389 - };
1.390 -
1.391 -
1.392 -
1.393 -
1.394 -
1.395 -
1.396 -
1.397 -
1.398 -
1.399 -
1.400 - /**********************************************************************/
1.401 -
1.402 -
1.403 - //! \brief A structure for representing undirected path in a graph.
1.404 - //!
1.405 - //! A structure for representing undirected path in a graph. Ie. this is
1.406 - //! a path in a \e directed graph but the edges should not be directed
1.407 - //! forward.
1.408 - //!
1.409 - //! \param Graph The graph type in which the path is.
1.410 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.411 - //!
1.412 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.413 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.414 - //! and \c Edge of the original graph.
1.415 - //!
1.416 - //! \todo Thoroughfully check all the range and consistency tests.
1.417 - template<typename Graph, typename DM = DefaultDebugMode>
1.418 - class UndirPath {
1.419 - public:
1.420 - /// Edge type of the underlying graph.
1.421 - typedef typename Graph::Edge GraphEdge;
1.422 - /// Node type of the underlying graph.
1.423 - typedef typename Graph::Node GraphNode;
1.424 - class NodeIt;
1.425 - class EdgeIt;
1.426 -
1.427 - protected:
1.428 - const Graph *gr;
1.429 - typedef std::vector<GraphEdge> Container;
1.430 - Container edges;
1.431 -
1.432 - public:
1.433 -
1.434 - /// \param _G The graph in which the path is.
1.435 - ///
1.436 - UndirPath(const Graph &_G) : gr(&_G) {}
1.437 -
1.438 - /// \brief Subpath constructor.
1.439 - ///
1.440 - /// Subpath defined by two nodes.
1.441 - /// \warning It is an error if the two edges are not in order!
1.442 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.443 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.444 - // FIXME: this check should be more elaborate...
1.445 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.446 - }
1.447 - gr = P.gr;
1.448 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.449 - }
1.450 -
1.451 - /// \brief Subpath constructor.
1.452 - ///
1.453 - /// Subpath defined by two edges. Contains edges in [a,b)
1.454 - /// \warning It is an error if the two edges are not in order!
1.455 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.456 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.457 - // FIXME: this check should be more elaborate...
1.458 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.459 - }
1.460 - gr = P.gr;
1.461 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.462 - }
1.463 -
1.464 - /// Length of the path.
1.465 - size_t length() const { return edges.size(); }
1.466 - /// Returns whether the path is empty.
1.467 - bool empty() const { return edges.empty(); }
1.468 -
1.469 - /// Resets the path to an empty path.
1.470 - void clear() { edges.clear(); }
1.471 -
1.472 - /// \brief Starting point of the path.
1.473 - ///
1.474 - /// Starting point of the path.
1.475 - /// Returns INVALID if the path is empty.
1.476 - GraphNode from() const {
1.477 - return empty() ? INVALID : gr->source(edges[0]);
1.478 - }
1.479 - /// \brief End point of the path.
1.480 - ///
1.481 - /// End point of the path.
1.482 - /// Returns INVALID if the path is empty.
1.483 - GraphNode to() const {
1.484 - return empty() ? INVALID : gr->target(edges[length()-1]);
1.485 - }
1.486 -
1.487 - /// \brief Initializes node or edge iterator to point to the first
1.488 - /// node or edge.
1.489 - ///
1.490 - /// \sa nth
1.491 - template<typename It>
1.492 - It& first(It &i) const { return i=It(*this); }
1.493 -
1.494 - /// \brief Initializes node iterator to point to the node of a given index.
1.495 - NodeIt& nth(NodeIt &i, int n) const {
1.496 - if( DM::range_check && (n<0 || n>int(length())) )
1.497 - fault("UndirPath::nth: index out of range");
1.498 - return i=NodeIt(*this, n);
1.499 - }
1.500 -
1.501 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.502 - EdgeIt& nth(EdgeIt &i, int n) const {
1.503 - if( DM::range_check && (n<0 || n>=int(length())) )
1.504 - fault("UndirPath::nth: index out of range");
1.505 - return i=EdgeIt(*this, n);
1.506 - }
1.507 -
1.508 - /// Checks validity of a node or edge iterator.
1.509 - template<typename It>
1.510 - static
1.511 - bool valid(const It &i) { return i.valid(); }
1.512 -
1.513 - /// Steps the given node or edge iterator.
1.514 - template<typename It>
1.515 - static
1.516 - It& next(It &e) {
1.517 - if( DM::range_check && !e.valid() )
1.518 - fault("UndirPath::next() on invalid iterator");
1.519 - return ++e;
1.520 - }
1.521 -
1.522 - /// \brief Returns node iterator pointing to the target node of the
1.523 - /// given edge iterator.
1.524 - NodeIt target(const EdgeIt& e) const {
1.525 - if( DM::range_check && !e.valid() )
1.526 - fault("UndirPath::target() on invalid iterator");
1.527 - return NodeIt(*this, e.idx+1);
1.528 - }
1.529 -
1.530 - /// \brief Returns node iterator pointing to the source node of the
1.531 - /// given edge iterator.
1.532 - NodeIt source(const EdgeIt& e) const {
1.533 - if( DM::range_check && !e.valid() )
1.534 - fault("UndirPath::source() on invalid iterator");
1.535 - return NodeIt(*this, e.idx);
1.536 - }
1.537 -
1.538 -
1.539 -
1.540 - /**
1.541 - * \brief Iterator class to iterate on the edges of the paths
1.542 - *
1.543 - * \ingroup paths
1.544 - * This class is used to iterate on the edges of the paths
1.545 - *
1.546 - * Of course it converts to Graph::Edge
1.547 - *
1.548 - * \todo Its interface differs from the standard edge iterator.
1.549 - * Yes, it shouldn't.
1.550 - */
1.551 - class EdgeIt {
1.552 - friend class UndirPath;
1.553 -
1.554 - int idx;
1.555 - const UndirPath *p;
1.556 - public:
1.557 - /// Default constructor
1.558 - EdgeIt() {}
1.559 - /// Invalid constructor
1.560 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.561 - /// Constructor with starting point
1.562 - EdgeIt(const UndirPath &_p, int _idx = 0) :
1.563 - idx(_idx), p(&_p) { validate(); }
1.564 -
1.565 - ///Validity check
1.566 - bool valid() const { return idx!=-1; }
1.567 -
1.568 - ///Conversion to Graph::Edge
1.569 - operator GraphEdge () const {
1.570 - return valid() ? p->edges[idx] : INVALID;
1.571 - }
1.572 - /// Next edge
1.573 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.574 -
1.575 - /// Comparison operator
1.576 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.577 - /// Comparison operator
1.578 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.579 - /// Comparison operator
1.580 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.581 -
1.582 - private:
1.583 - // FIXME: comparison between signed and unsigned...
1.584 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.585 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.586 - };
1.587 -
1.588 - /**
1.589 - * \brief Iterator class to iterate on the nodes of the paths
1.590 - *
1.591 - * \ingroup paths
1.592 - * This class is used to iterate on the nodes of the paths
1.593 - *
1.594 - * Of course it converts to Graph::Node
1.595 - *
1.596 - * \todo Its interface differs from the standard node iterator.
1.597 - * Yes, it shouldn't.
1.598 - */
1.599 - class NodeIt {
1.600 - friend class UndirPath;
1.601 -
1.602 - int idx;
1.603 - const UndirPath *p;
1.604 - public:
1.605 - /// Default constructor
1.606 - NodeIt() {}
1.607 - /// Invalid constructor
1.608 - NodeIt(Invalid) : idx(-1), p(0) {}
1.609 - /// Constructor with starting point
1.610 - NodeIt(const UndirPath &_p, int _idx = 0) :
1.611 - idx(_idx), p(&_p) { validate(); }
1.612 -
1.613 - ///Validity check
1.614 - bool valid() const { return idx!=-1; }
1.615 -
1.616 - ///Conversion to Graph::Node
1.617 - operator const GraphNode& () const {
1.618 - if(idx >= p->length())
1.619 - return p->to();
1.620 - else if(idx >= 0)
1.621 - return p->gr->source(p->edges[idx]);
1.622 - else
1.623 - return INVALID;
1.624 - }
1.625 - /// Next node
1.626 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.627 -
1.628 - /// Comparison operator
1.629 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.630 - /// Comparison operator
1.631 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.632 - /// Comparison operator
1.633 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.634 -
1.635 - private:
1.636 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.637 - };
1.638 -
1.639 - friend class Builder;
1.640 -
1.641 - /**
1.642 - * \brief Class to build paths
1.643 - *
1.644 - * \ingroup paths
1.645 - * This class is used to fill a path with edges.
1.646 - *
1.647 - * You can push new edges to the front and to the back of the path in
1.648 - * arbitrary order then you should commit these changes to the graph.
1.649 - *
1.650 - * Fundamentally, for most "Paths" (classes fulfilling the
1.651 - * PathConcept) while the builder is active (after the first modifying
1.652 - * operation and until the commit()) the original Path is in a
1.653 - * "transitional" state (operations ot it have undefined result). But
1.654 - * in the case of UndirPath the original path is unchanged until the
1.655 - * commit. However we don't recomend that you use this feature.
1.656 - */
1.657 - class Builder {
1.658 - UndirPath &P;
1.659 - Container front, back;
1.660 -
1.661 - public:
1.662 - ///\param _P the path you want to fill in.
1.663 - ///
1.664 - Builder(UndirPath &_P) : P(_P) {}
1.665 -
1.666 - /// Sets the starting node of the path.
1.667 -
1.668 - /// Sets the starting node of the path. Edge added to the path
1.669 - /// afterwards have to be incident to this node.
1.670 - /// It should be called iff the path is empty and before any call to
1.671 - /// \ref pushFront() or \ref pushBack()
1.672 - void setStartNode(const GraphNode &) {}
1.673 -
1.674 - ///Push a new edge to the front of the path
1.675 -
1.676 - ///Push a new edge to the front of the path.
1.677 - ///\sa setStartNode
1.678 - void pushFront(const GraphEdge& e) {
1.679 - if( DM::consistensy_check && !empty() && P.gr->target(e)!=from() ) {
1.680 - fault("UndirPath::Builder::pushFront: nonincident edge");
1.681 - }
1.682 - front.push_back(e);
1.683 - }
1.684 -
1.685 - ///Push a new edge to the back of the path
1.686 -
1.687 - ///Push a new edge to the back of the path.
1.688 - ///\sa setStartNode
1.689 - void pushBack(const GraphEdge& e) {
1.690 - if( DM::consistensy_check && !empty() && P.gr->source(e)!=to() ) {
1.691 - fault("UndirPath::Builder::pushBack: nonincident edge");
1.692 - }
1.693 - back.push_back(e);
1.694 - }
1.695 -
1.696 - ///Commit the changes to the path.
1.697 - void commit() {
1.698 - if( !(front.empty() && back.empty()) ) {
1.699 - Container tmp;
1.700 - tmp.reserve(front.size()+back.size()+P.length());
1.701 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.702 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.703 - tmp.insert(tmp.end(), back.begin(), back.end());
1.704 - P.edges.swap(tmp);
1.705 - front.clear();
1.706 - back.clear();
1.707 - }
1.708 - }
1.709 -
1.710 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.711 - // Hogy kenyelmes egy ilyet hasznalni?
1.712 -
1.713 - ///Reserve storage for the builder in advance.
1.714 -
1.715 - ///If you know an reasonable upper bound of the number of the edges
1.716 - ///to add, using this function you can speed up the building.
1.717 - void reserve(size_t r) {
1.718 - front.reserve(r);
1.719 - back.reserve(r);
1.720 - }
1.721 -
1.722 - private:
1.723 - bool empty() {
1.724 - return front.empty() && back.empty() && P.empty();
1.725 - }
1.726 -
1.727 - GraphNode from() const {
1.728 - if( ! front.empty() )
1.729 - return P.gr->source(front[front.size()-1]);
1.730 - else if( ! P.empty() )
1.731 - return P.gr->source(P.edges[0]);
1.732 - else if( ! back.empty() )
1.733 - return P.gr->source(back[0]);
1.734 - else
1.735 - return INVALID;
1.736 - }
1.737 - GraphNode to() const {
1.738 - if( ! back.empty() )
1.739 - return P.gr->target(back[back.size()-1]);
1.740 - else if( ! P.empty() )
1.741 - return P.gr->target(P.edges[P.length()-1]);
1.742 - else if( ! front.empty() )
1.743 - return P.gr->target(front[0]);
1.744 - else
1.745 - return INVALID;
1.746 - }
1.747 -
1.748 - };
1.749 -
1.750 - };
1.751 -
1.752 -
1.753 -
1.754 -
1.755 -
1.756 -
1.757 -
1.758 -
1.759 -
1.760 -
1.761 - /**********************************************************************/
1.762 -
1.763 -
1.764 - /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
1.765 - elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
1.766 -
1.767 - template<typename Graph>
1.768 - class DynamicPath {
1.769 -
1.770 - public:
1.771 - typedef typename Graph::Edge GraphEdge;
1.772 - typedef typename Graph::Node GraphNode;
1.773 - class NodeIt;
1.774 - class EdgeIt;
1.775 -
1.776 - protected:
1.777 - Graph& G;
1.778 - // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
1.779 - // iranyitasat:
1.780 - GraphNode _first, _last;
1.781 - typedef std::deque<GraphEdge> Container;
1.782 - Container edges;
1.783 -
1.784 - public:
1.785 -
1.786 - DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
1.787 -
1.788 - /// Subpath defined by two nodes.
1.789 - /// Nodes may be in reversed order, then
1.790 - /// we contstruct the reversed path.
1.791 - DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
1.792 - /// Subpath defined by two edges. Contains edges in [a,b)
1.793 - /// It is an error if the two edges are not in order!
1.794 - DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
1.795 -
1.796 - size_t length() const { return edges.size(); }
1.797 - GraphNode from() const { return _first; }
1.798 - GraphNode to() const { return _last; }
1.799 -
1.800 - NodeIt& first(NodeIt &n) const { return nth(n, 0); }
1.801 - EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
1.802 - template<typename It>
1.803 - It first() const {
1.804 - It e;
1.805 - first(e);
1.806 - return e;
1.807 - }
1.808 -
1.809 - NodeIt& nth(NodeIt &, size_t) const;
1.810 - EdgeIt& nth(EdgeIt &, size_t) const;
1.811 - template<typename It>
1.812 - It nth(size_t n) const {
1.813 - It e;
1.814 - nth(e, n);
1.815 - return e;
1.816 - }
1.817 -
1.818 - bool valid(const NodeIt &n) const { return n.idx <= length(); }
1.819 - bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
1.820 -
1.821 - bool isForward(const EdgeIt &e) const { return e.forw; }
1.822 -
1.823 - /// index of a node on the path. Returns length+2 for the invalid NodeIt
1.824 - int index(const NodeIt &n) const { return n.idx; }
1.825 - /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
1.826 - int index(const EdgeIt &e) const { return e.it - edges.begin(); }
1.827 -
1.828 - EdgeIt& next(EdgeIt &e) const;
1.829 - NodeIt& next(NodeIt &n) const;
1.830 - template <typename It>
1.831 - It getNext(It it) const {
1.832 - It tmp(it); return next(tmp);
1.833 - }
1.834 -
1.835 - // A path is constructed using the following four functions.
1.836 - // They return false if the requested operation is inconsistent
1.837 - // with the path constructed so far.
1.838 - // If your path has only one edge you MUST set either "from" or "to"!
1.839 - // So you probably SHOULD call it in any case to be safe (and check the
1.840 - // returned value to check if your path is consistent with your idea).
1.841 - bool pushFront(const GraphEdge &e);
1.842 - bool pushBack(const GraphEdge &e);
1.843 - bool setFrom(const GraphNode &n);
1.844 - bool setTo(const GraphNode &n);
1.845 -
1.846 - // WARNING: these two functions return the target/source of an edge with
1.847 - // respect to the direction of the path!
1.848 - // So G.target(P.graphEdge(e)) == P.graphNode(P.target(e)) holds only if
1.849 - // P.forward(e) is true (or the edge is a loop)!
1.850 - NodeIt target(const EdgeIt& e) const;
1.851 - NodeIt source(const EdgeIt& e) const;
1.852 -
1.853 - // FIXME: ezeknek valami jobb nev kellene!!!
1.854 - GraphEdge graphEdge(const EdgeIt& e) const;
1.855 - GraphNode graphNode(const NodeIt& n) const;
1.856 -
1.857 -
1.858 - /*** Iterator classes ***/
1.859 - class EdgeIt {
1.860 - friend class DynamicPath;
1.861 -
1.862 - typename Container::const_iterator it;
1.863 - bool forw;
1.864 - public:
1.865 - // FIXME: jarna neki ilyen is...
1.866 - // EdgeIt(Invalid);
1.867 -
1.868 - bool forward() const { return forw; }
1.869 -
1.870 - bool operator==(const EdgeIt& e) const { return it==e.it; }
1.871 - bool operator!=(const EdgeIt& e) const { return it!=e.it; }
1.872 - bool operator<(const EdgeIt& e) const { return it<e.it; }
1.873 - };
1.874 -
1.875 - class NodeIt {
1.876 - friend class DynamicPath;
1.877 -
1.878 - size_t idx;
1.879 - bool source; // Is this node the source of the edge with same idx?
1.880 -
1.881 - public:
1.882 - // FIXME: jarna neki ilyen is...
1.883 - // NodeIt(Invalid);
1.884 -
1.885 - bool operator==(const NodeIt& n) const { return idx==n.idx; }
1.886 - bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
1.887 - bool operator<(const NodeIt& n) const { return idx<n.idx; }
1.888 - };
1.889 -
1.890 - private:
1.891 - bool edgeIncident(const GraphEdge &e, const GraphNode &a,
1.892 - GraphNode &b);
1.893 - bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
1.894 - };
1.895 -
1.896 - template<typename Gr>
1.897 - typename DynamicPath<Gr>::EdgeIt&
1.898 - DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
1.899 - if( e.it == edges.end() )
1.900 - return e;
1.901 -
1.902 - GraphNode common_node = ( e.forw ? G.target(*e.it) : G.source(*e.it) );
1.903 - ++e.it;
1.904 -
1.905 - // Invalid edgeit is always forward :)
1.906 - if( e.it == edges.end() ) {
1.907 - e.forw = true;
1.908 - return e;
1.909 - }
1.910 -
1.911 - e.forw = ( G.source(*e.it) == common_node );
1.912 - return e;
1.913 - }
1.914 -
1.915 - template<typename Gr>
1.916 - typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
1.917 - if( n.idx >= length() ) {
1.918 - // FIXME: invalid
1.919 - n.idx = length()+1;
1.920 - return n;
1.921 - }
1.922 -
1.923 -
1.924 - GraphNode next_node = ( n.source ? G.target(edges[n.idx]) :
1.925 - G.source(edges[n.idx]) );
1.926 - ++n.idx;
1.927 - if( n.idx < length() ) {
1.928 - n.source = ( next_node == G.source(edges[n.idx]) );
1.929 - }
1.930 - else {
1.931 - n.source = true;
1.932 - }
1.933 -
1.934 - return n;
1.935 - }
1.936 -
1.937 - template<typename Gr>
1.938 - bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
1.939 - GraphNode &b) {
1.940 - if( G.source(e) == a ) {
1.941 - b=G.target(e);
1.942 - return true;
1.943 - }
1.944 - if( G.target(e) == a ) {
1.945 - b=G.source(e);
1.946 - return true;
1.947 - }
1.948 - return false;
1.949 - }
1.950 -
1.951 - template<typename Gr>
1.952 - bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
1.953 - const GraphEdge &f) {
1.954 - if( edgeIncident(f, G.source(e), _last) ) {
1.955 - _first = G.target(e);
1.956 - return true;
1.957 - }
1.958 - if( edgeIncident(f, G.target(e), _last) ) {
1.959 - _first = G.source(e);
1.960 - return true;
1.961 - }
1.962 - return false;
1.963 - }
1.964 -
1.965 - template<typename Gr>
1.966 - bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
1.967 - if( G.valid(_first) ) {
1.968 - if( edgeIncident(e, _first, _first) ) {
1.969 - edges.push_front(e);
1.970 - return true;
1.971 - }
1.972 - else
1.973 - return false;
1.974 - }
1.975 - else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
1.976 - edges.push_front(e);
1.977 - return true;
1.978 - }
1.979 - else
1.980 - return false;
1.981 - }
1.982 -
1.983 - template<typename Gr>
1.984 - bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
1.985 - if( G.valid(_last) ) {
1.986 - if( edgeIncident(e, _last, _last) ) {
1.987 - edges.push_back(e);
1.988 - return true;
1.989 - }
1.990 - else
1.991 - return false;
1.992 - }
1.993 - else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
1.994 - edges.push_back(e);
1.995 - return true;
1.996 - }
1.997 - else
1.998 - return false;
1.999 - }
1.1000 -
1.1001 -
1.1002 - template<typename Gr>
1.1003 - bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1.1004 - if( G.valid(_first) ) {
1.1005 - return _first == n;
1.1006 - }
1.1007 - else {
1.1008 - if( length() > 0) {
1.1009 - if( edgeIncident(edges[0], n, _last) ) {
1.1010 - _first = n;
1.1011 - return true;
1.1012 - }
1.1013 - else return false;
1.1014 - }
1.1015 - else {
1.1016 - _first = _last = n;
1.1017 - return true;
1.1018 - }
1.1019 - }
1.1020 - }
1.1021 -
1.1022 - template<typename Gr>
1.1023 - bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1.1024 - if( G.valid(_last) ) {
1.1025 - return _last == n;
1.1026 - }
1.1027 - else {
1.1028 - if( length() > 0) {
1.1029 - if( edgeIncident(edges[0], n, _first) ) {
1.1030 - _last = n;
1.1031 - return true;
1.1032 - }
1.1033 - else return false;
1.1034 - }
1.1035 - else {
1.1036 - _first = _last = n;
1.1037 - return true;
1.1038 - }
1.1039 - }
1.1040 - }
1.1041 -
1.1042 -
1.1043 - template<typename Gr>
1.1044 - typename DynamicPath<Gr>::NodeIt
1.1045 - DynamicPath<Gr>::source(const EdgeIt& e) const {
1.1046 - NodeIt n;
1.1047 -
1.1048 - if( e.it == edges.end() ) {
1.1049 - // FIXME: invalid-> invalid
1.1050 - n.idx = length() + 1;
1.1051 - n.source = true;
1.1052 - return n;
1.1053 - }
1.1054 -
1.1055 - n.idx = e.it-edges.begin();
1.1056 - n.source = e.forw;
1.1057 - return n;
1.1058 - }
1.1059 -
1.1060 - template<typename Gr>
1.1061 - typename DynamicPath<Gr>::NodeIt
1.1062 - DynamicPath<Gr>::target(const EdgeIt& e) const {
1.1063 - if( e.it == edges.end()-1 ) {
1.1064 - return _last;
1.1065 - }
1.1066 -
1.1067 - EdgeIt next_edge = e;
1.1068 - next(next_edge);
1.1069 - return source(next_edge);
1.1070 - }
1.1071 -
1.1072 - template<typename Gr>
1.1073 - typename DynamicPath<Gr>::GraphEdge
1.1074 - DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1.1075 - if( e.it != edges.end() ) {
1.1076 - return *e.it;
1.1077 - }
1.1078 - else {
1.1079 - return INVALID;
1.1080 - }
1.1081 - }
1.1082 -
1.1083 - template<typename Gr>
1.1084 - typename DynamicPath<Gr>::GraphNode
1.1085 - DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1.1086 - if( n.idx < length() ) {
1.1087 - return n.source ? G.source(edges[n.idx]) : G.target(edges[n.idx]);
1.1088 - }
1.1089 - else if( n.idx == length() ) {
1.1090 - return _last;
1.1091 - }
1.1092 - else {
1.1093 - return INVALID;
1.1094 - }
1.1095 - }
1.1096 -
1.1097 - template<typename Gr>
1.1098 - typename DynamicPath<Gr>::EdgeIt&
1.1099 - DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1.1100 - if( k>=length() ) {
1.1101 - // FIXME: invalid EdgeIt
1.1102 - e.it = edges.end();
1.1103 - e.forw = true;
1.1104 - return e;
1.1105 - }
1.1106 -
1.1107 - e.it = edges.begin()+k;
1.1108 - if(k==0) {
1.1109 - e.forw = ( G.source(*e.it) == _first );
1.1110 - }
1.1111 - else {
1.1112 - e.forw = ( G.source(*e.it) == G.source(edges[k-1]) ||
1.1113 - G.source(*e.it) == G.target(edges[k-1]) );
1.1114 - }
1.1115 - return e;
1.1116 - }
1.1117 -
1.1118 - template<typename Gr>
1.1119 - typename DynamicPath<Gr>::NodeIt&
1.1120 - DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1.1121 - if( k>length() ) {
1.1122 - // FIXME: invalid NodeIt
1.1123 - n.idx = length()+1;
1.1124 - n.source = true;
1.1125 - return n;
1.1126 - }
1.1127 - if( k==length() ) {
1.1128 - n.idx = length();
1.1129 - n.source = true;
1.1130 - return n;
1.1131 - }
1.1132 - n = source(nth<EdgeIt>(k));
1.1133 - return n;
1.1134 - }
1.1135 -
1.1136 - // Reszut konstruktorok:
1.1137 -
1.1138 -
1.1139 - template<typename Gr>
1.1140 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1.1141 - const EdgeIt &b) :
1.1142 - G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1.1143 - {
1.1144 - if( G.valid(P._first) && a.it < P.edges.end() ) {
1.1145 - _first = ( a.forw ? G.source(*a.it) : G.target(*a.it) );
1.1146 - if( b.it < P.edges.end() ) {
1.1147 - _last = ( b.forw ? G.source(*b.it) : G.target(*b.it) );
1.1148 - }
1.1149 - else {
1.1150 - _last = P._last;
1.1151 - }
1.1152 - }
1.1153 - }
1.1154 -
1.1155 - template<typename Gr>
1.1156 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1.1157 - const NodeIt &b) : G(P.G)
1.1158 - {
1.1159 - if( !P.valid(a) || !P.valid(b) )
1.1160 - return;
1.1161 -
1.1162 - int ai = a.idx, bi = b.idx;
1.1163 - if( bi<ai )
1.1164 - std::swap(ai,bi);
1.1165 -
1.1166 - edges.resize(bi-ai);
1.1167 - copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1.1168 -
1.1169 - _first = P.graphNode(a);
1.1170 - _last = P.graphNode(b);
1.1171 - }
1.1172 -
1.1173 - ///@}
1.1174 -
1.1175 -} // namespace lemon
1.1176 -
1.1177 -#endif // LEMON_PATH_H