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