path.h by Misi, committed by Peter. There is DirPath usw. in it.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/path.h Wed Sep 08 11:49:09 2004 +0000
1.3 @@ -0,0 +1,1174 @@
1.4 +// -*- c++ -*- //
1.5 +
1.6 +/**
1.7 +@defgroup paths Path Structures
1.8 +@ingroup datas
1.9 +\brief Path structures implemented in Hugo.
1.10 +
1.11 +Hugolib 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 hugo::skeleton::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 HUGO_PATH_H
1.27 +#define HUGO_PATH_H
1.28 +
1.29 +#include <deque>
1.30 +#include <vector>
1.31 +#include <algorithm>
1.32 +
1.33 +#include <hugo/invalid.h>
1.34 +#include <hugo/error.h>
1.35 +#include <hugo/debug.h>
1.36 +
1.37 +namespace hugo {
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->tail(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->head(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 head node of the
1.160 + /// given edge iterator.
1.161 + NodeIt head(const EdgeIt& e) const {
1.162 + if( DM::range_check && !e.valid() )
1.163 + fault("DirPath::head() on invalid iterator");
1.164 + return NodeIt(*this, e.idx+1);
1.165 + }
1.166 +
1.167 + /// \brief Returns node iterator pointing to the tail node of the
1.168 + /// given edge iterator.
1.169 + NodeIt tail(const EdgeIt& e) const {
1.170 + if( DM::range_check && !e.valid() )
1.171 + fault("DirPath::tail() 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->tail(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->head(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->tail(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->tail(front[front.size()-1]);
1.369 + else if( ! P.empty() )
1.370 + return P.gr->tail(P.edges[0]);
1.371 + else if( ! back.empty() )
1.372 + return P.gr->tail(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->head(back[back.size()-1]);
1.379 + else if( ! P.empty() )
1.380 + return P.gr->head(P.edges[P.length()-1]);
1.381 + else if( ! front.empty() )
1.382 + return P.gr->head(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->tail(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->head(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 head node of the
1.523 + /// given edge iterator.
1.524 + NodeIt head(const EdgeIt& e) const {
1.525 + if( DM::range_check && !e.valid() )
1.526 + fault("UndirPath::head() on invalid iterator");
1.527 + return NodeIt(*this, e.idx+1);
1.528 + }
1.529 +
1.530 + /// \brief Returns node iterator pointing to the tail node of the
1.531 + /// given edge iterator.
1.532 + NodeIt tail(const EdgeIt& e) const {
1.533 + if( DM::range_check && !e.valid() )
1.534 + fault("UndirPath::tail() 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->tail(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->head(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->tail(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->tail(front[front.size()-1]);
1.730 + else if( ! P.empty() )
1.731 + return P.gr->tail(P.edges[0]);
1.732 + else if( ! back.empty() )
1.733 + return P.gr->tail(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->head(back[back.size()-1]);
1.740 + else if( ! P.empty() )
1.741 + return P.gr->head(P.edges[P.length()-1]);
1.742 + else if( ! front.empty() )
1.743 + return P.gr->head(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 head/tail of an edge with
1.847 + // respect to the direction of the path!
1.848 + // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
1.849 + // P.forward(e) is true (or the edge is a loop)!
1.850 + NodeIt head(const EdgeIt& e) const;
1.851 + NodeIt tail(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 tail; // Is this node the tail 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.head(*e.it) : G.tail(*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.tail(*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.tail ? G.head(edges[n.idx]) :
1.925 + G.tail(edges[n.idx]) );
1.926 + ++n.idx;
1.927 + if( n.idx < length() ) {
1.928 + n.tail = ( next_node == G.tail(edges[n.idx]) );
1.929 + }
1.930 + else {
1.931 + n.tail = 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.tail(e) == a ) {
1.941 + b=G.head(e);
1.942 + return true;
1.943 + }
1.944 + if( G.head(e) == a ) {
1.945 + b=G.tail(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.tail(e), _last) ) {
1.955 + _first = G.head(e);
1.956 + return true;
1.957 + }
1.958 + if( edgeIncident(f, G.head(e), _last) ) {
1.959 + _first = G.tail(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>::tail(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.tail = true;
1.1052 + return n;
1.1053 + }
1.1054 +
1.1055 + n.idx = e.it-edges.begin();
1.1056 + n.tail = 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>::head(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 tail(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.tail ? G.tail(edges[n.idx]) : G.head(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.tail(*e.it) == _first );
1.1110 + }
1.1111 + else {
1.1112 + e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1.1113 + G.tail(*e.it) == G.head(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.tail = true;
1.1125 + return n;
1.1126 + }
1.1127 + if( k==length() ) {
1.1128 + n.idx = length();
1.1129 + n.tail = true;
1.1130 + return n;
1.1131 + }
1.1132 + n = tail(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.tail(*a.it) : G.head(*a.it) );
1.1146 + if( b.it < P.edges.end() ) {
1.1147 + _last = ( b.forw ? G.tail(*b.it) : G.head(*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 hugo
1.1176 +
1.1177 +#endif // HUGO_PATH_H