1.1 --- a/src/work/alpar/path.h Tue Jun 15 06:30:03 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,748 +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 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 - //! \brief A structure for representing undirected path in a graph.
1.398 - //!
1.399 - //! A structure for representing undirected path in a graph. Ie. this is
1.400 - //! a path in a \e directed graph but the edges should not be directed
1.401 - //! forward.
1.402 - //!
1.403 - //! \param Graph The graph type in which the path is.
1.404 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.405 - //!
1.406 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.407 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.408 - //! and \c Edge of the original graph.
1.409 - //!
1.410 - //! \todo Thoroughfully check all the range and consistency tests.
1.411 - template<typename Graph, typename DM = DefaultDebugMode>
1.412 - class UndirPath {
1.413 - public:
1.414 - /// Edge type of the underlying graph.
1.415 - typedef typename Graph::Edge GraphEdge;
1.416 - /// Node type of the underlying graph.
1.417 - typedef typename Graph::Node GraphNode;
1.418 - class NodeIt;
1.419 - class EdgeIt;
1.420 -
1.421 - protected:
1.422 - const Graph *gr;
1.423 - typedef std::vector<GraphEdge> Container;
1.424 - Container edges;
1.425 -
1.426 - public:
1.427 -
1.428 - /// \param _G The graph in which the path is.
1.429 - ///
1.430 - UndirPath(const Graph &_G) : gr(&_G) {}
1.431 -
1.432 - /// \brief Subpath constructor.
1.433 - ///
1.434 - /// Subpath defined by two nodes.
1.435 - /// \warning It is an error if the two edges are not in order!
1.436 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.437 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.438 - // FIXME: this check should be more elaborate...
1.439 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.440 - }
1.441 - gr = P.gr;
1.442 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.443 - }
1.444 -
1.445 - /// \brief Subpath constructor.
1.446 - ///
1.447 - /// Subpath defined by two edges. Contains edges in [a,b)
1.448 - /// \warning It is an error if the two edges are not in order!
1.449 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.450 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.451 - // FIXME: this check should be more elaborate...
1.452 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.453 - }
1.454 - gr = P.gr;
1.455 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.456 - }
1.457 -
1.458 - /// Length of the path.
1.459 - size_t length() const { return edges.size(); }
1.460 - /// Returns whether the path is empty.
1.461 - bool empty() const { return edges.empty(); }
1.462 -
1.463 - /// Resets the path to an empty path.
1.464 - void clear() { edges.clear(); }
1.465 -
1.466 - /// \brief Starting point of the path.
1.467 - ///
1.468 - /// Starting point of the path.
1.469 - /// Returns INVALID if the path is empty.
1.470 - GraphNode from() const {
1.471 - return empty() ? INVALID : gr->tail(edges[0]);
1.472 - }
1.473 - /// \brief End point of the path.
1.474 - ///
1.475 - /// End point of the path.
1.476 - /// Returns INVALID if the path is empty.
1.477 - GraphNode to() const {
1.478 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.479 - }
1.480 -
1.481 - /// \brief Initializes node or edge iterator to point to the first
1.482 - /// node or edge.
1.483 - ///
1.484 - /// \sa nth
1.485 - template<typename It>
1.486 - It& first(It &i) const { return i=It(*this); }
1.487 -
1.488 - /// \brief Initializes node iterator to point to the node of a given index.
1.489 - NodeIt& nth(NodeIt &i, int n) const {
1.490 - if( DM::range_check && (n<0 || n>int(length())) )
1.491 - fault("UndirPath::nth: index out of range");
1.492 - return i=NodeIt(*this, n);
1.493 - }
1.494 -
1.495 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.496 - EdgeIt& nth(EdgeIt &i, int n) const {
1.497 - if( DM::range_check && (n<0 || n>=int(length())) )
1.498 - fault("UndirPath::nth: index out of range");
1.499 - return i=EdgeIt(*this, n);
1.500 - }
1.501 -
1.502 - /// Checks validity of a node or edge iterator.
1.503 - template<typename It>
1.504 - static
1.505 - bool valid(const It &i) { return i.valid(); }
1.506 -
1.507 - /// Steps the given node or edge iterator.
1.508 - template<typename It>
1.509 - static
1.510 - It& next(It &e) {
1.511 - if( DM::range_check && !e.valid() )
1.512 - fault("UndirPath::next() on invalid iterator");
1.513 - return ++e;
1.514 - }
1.515 -
1.516 - /// \brief Returns node iterator pointing to the head node of the
1.517 - /// given edge iterator.
1.518 - NodeIt head(const EdgeIt& e) const {
1.519 - if( DM::range_check && !e.valid() )
1.520 - fault("UndirPath::head() on invalid iterator");
1.521 - return NodeIt(*this, e.idx+1);
1.522 - }
1.523 -
1.524 - /// \brief Returns node iterator pointing to the tail node of the
1.525 - /// given edge iterator.
1.526 - NodeIt tail(const EdgeIt& e) const {
1.527 - if( DM::range_check && !e.valid() )
1.528 - fault("UndirPath::tail() on invalid iterator");
1.529 - return NodeIt(*this, e.idx);
1.530 - }
1.531 -
1.532 -
1.533 -
1.534 - /**
1.535 - * \brief Iterator class to iterate on the edges of the paths
1.536 - *
1.537 - * \ingroup paths
1.538 - * This class is used to iterate on the edges of the paths
1.539 - *
1.540 - * Of course it converts to Graph::Edge
1.541 - *
1.542 - * \todo Its interface differs from the standard edge iterator.
1.543 - * Yes, it shouldn't.
1.544 - */
1.545 - class EdgeIt {
1.546 - friend class UndirPath;
1.547 -
1.548 - int idx;
1.549 - const UndirPath *p;
1.550 - public:
1.551 - /// Default constructor
1.552 - EdgeIt() {}
1.553 - /// Invalid constructor
1.554 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.555 - /// Constructor with starting point
1.556 - EdgeIt(const UndirPath &_p, int _idx = 0) :
1.557 - idx(_idx), p(&_p) { validate(); }
1.558 -
1.559 - ///Validity check
1.560 - bool valid() const { return idx!=-1; }
1.561 -
1.562 - ///Conversion to Graph::Edge
1.563 - operator GraphEdge () const {
1.564 - return valid() ? p->edges[idx] : INVALID;
1.565 - }
1.566 - /// Next edge
1.567 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.568 -
1.569 - /// Comparison operator
1.570 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.571 - /// Comparison operator
1.572 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.573 - /// Comparison operator
1.574 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.575 -
1.576 - private:
1.577 - // FIXME: comparison between signed and unsigned...
1.578 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.579 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.580 - };
1.581 -
1.582 - /**
1.583 - * \brief Iterator class to iterate on the nodes of the paths
1.584 - *
1.585 - * \ingroup paths
1.586 - * This class is used to iterate on the nodes of the paths
1.587 - *
1.588 - * Of course it converts to Graph::Node
1.589 - *
1.590 - * \todo Its interface differs from the standard node iterator.
1.591 - * Yes, it shouldn't.
1.592 - */
1.593 - class NodeIt {
1.594 - friend class UndirPath;
1.595 -
1.596 - int idx;
1.597 - const UndirPath *p;
1.598 - public:
1.599 - /// Default constructor
1.600 - NodeIt() {}
1.601 - /// Invalid constructor
1.602 - NodeIt(Invalid) : idx(-1), p(0) {}
1.603 - /// Constructor with starting point
1.604 - NodeIt(const UndirPath &_p, int _idx = 0) :
1.605 - idx(_idx), p(&_p) { validate(); }
1.606 -
1.607 - ///Validity check
1.608 - bool valid() const { return idx!=-1; }
1.609 -
1.610 - ///Conversion to Graph::Node
1.611 - operator const GraphNode& () const {
1.612 - if(idx >= p->length())
1.613 - return p->to();
1.614 - else if(idx >= 0)
1.615 - return p->gr->tail(p->edges[idx]);
1.616 - else
1.617 - return INVALID;
1.618 - }
1.619 - /// Next node
1.620 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.621 -
1.622 - /// Comparison operator
1.623 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.624 - /// Comparison operator
1.625 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.626 - /// Comparison operator
1.627 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.628 -
1.629 - private:
1.630 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.631 - };
1.632 -
1.633 - friend class Builder;
1.634 -
1.635 - /**
1.636 - * \brief Class to build paths
1.637 - *
1.638 - * \ingroup paths
1.639 - * This class is used to fill a path with edges.
1.640 - *
1.641 - * You can push new edges to the front and to the back of the path in
1.642 - * arbitrary order then you should commit these changes to the graph.
1.643 - *
1.644 - * Fundamentally, for most "Paths" (classes fulfilling the
1.645 - * PathConcept) while the builder is active (after the first modifying
1.646 - * operation and until the commit()) the original Path is in a
1.647 - * "transitional" state (operations ot it have undefined result). But
1.648 - * in the case of UndirPath the original path is unchanged until the
1.649 - * commit. However we don't recomend that you use this feature.
1.650 - */
1.651 - class Builder {
1.652 - UndirPath &P;
1.653 - Container front, back;
1.654 -
1.655 - public:
1.656 - ///\param _P the path you want to fill in.
1.657 - ///
1.658 - Builder(UndirPath &_P) : P(_P) {}
1.659 -
1.660 - /// Sets the starting node of the path.
1.661 -
1.662 - /// Sets the starting node of the path. Edge added to the path
1.663 - /// afterwards have to be incident to this node.
1.664 - /// It should be called iff the path is empty and before any call to
1.665 - /// \ref pushFront() or \ref pushBack()
1.666 - void setStart(const GraphNode &) {}
1.667 -
1.668 - ///Push a new edge to the front of the path
1.669 -
1.670 - ///Push a new edge to the front of the path.
1.671 - ///\sa setStart
1.672 - void pushFront(const GraphEdge& e) {
1.673 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.674 - fault("UndirPath::Builder::pushFront: nonincident edge");
1.675 - }
1.676 - front.push_back(e);
1.677 - }
1.678 -
1.679 - ///Push a new edge to the back of the path
1.680 -
1.681 - ///Push a new edge to the back of the path.
1.682 - ///\sa setStart
1.683 - void pushBack(const GraphEdge& e) {
1.684 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.685 - fault("UndirPath::Builder::pushBack: nonincident edge");
1.686 - }
1.687 - back.push_back(e);
1.688 - }
1.689 -
1.690 - ///Commit the changes to the path.
1.691 - void commit() {
1.692 - if( !(front.empty() && back.empty()) ) {
1.693 - Container tmp;
1.694 - tmp.reserve(front.size()+back.size()+P.length());
1.695 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.696 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.697 - tmp.insert(tmp.end(), back.begin(), back.end());
1.698 - P.edges.swap(tmp);
1.699 - front.clear();
1.700 - back.clear();
1.701 - }
1.702 - }
1.703 -
1.704 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.705 - // Hogy kenyelmes egy ilyet hasznalni?
1.706 -
1.707 - ///Reserve storage in advance for the builder
1.708 -
1.709 - ///If you know an reasonable upper bound of the number of the edges
1.710 - ///to add, using this function you can speed up the building.
1.711 - void reserve(size_t r) {
1.712 - front.reserve(r);
1.713 - back.reserve(r);
1.714 - }
1.715 -
1.716 - private:
1.717 - bool empty() {
1.718 - return front.empty() && back.empty() && P.empty();
1.719 - }
1.720 -
1.721 - GraphNode from() const {
1.722 - if( ! front.empty() )
1.723 - return P.gr->tail(front[front.size()-1]);
1.724 - else if( ! P.empty() )
1.725 - return P.gr->tail(P.edges[0]);
1.726 - else if( ! back.empty() )
1.727 - return P.gr->tail(back[0]);
1.728 - else
1.729 - return INVALID;
1.730 - }
1.731 - GraphNode to() const {
1.732 - if( ! back.empty() )
1.733 - return P.gr->head(back[back.size()-1]);
1.734 - else if( ! P.empty() )
1.735 - return P.gr->head(P.edges[P.length()-1]);
1.736 - else if( ! front.empty() )
1.737 - return P.gr->head(front[0]);
1.738 - else
1.739 - return INVALID;
1.740 - }
1.741 -
1.742 - };
1.743 -
1.744 - };
1.745 -
1.746 -
1.747 - ///@}
1.748 -
1.749 -} // namespace hugo
1.750 -
1.751 -#endif // HUGO_PATH_H