1.1 --- a/src/hugo/path.h Wed Sep 29 14:12:26 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,709 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/hugo/path.h - Part of HUGOlib, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -/**
1.21 -@defgroup paths Path Structures
1.22 -@ingroup datas
1.23 -\brief Path structures implemented in Hugo.
1.24 -
1.25 -Hugolib provides flexible data structures
1.26 -to work with paths.
1.27 -
1.28 -All of them have the same interface, especially they can be built or extended
1.29 -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
1.30 -algorithm to store its result in any kind of path structure.
1.31 -
1.32 -\sa hugo::skeleton::Path
1.33 -
1.34 -*/
1.35 -
1.36 -///\ingroup paths
1.37 -///\file
1.38 -///\brief Classes for representing paths in graphs.
1.39 -
1.40 -#ifndef HUGO_PATH_H
1.41 -#define HUGO_PATH_H
1.42 -
1.43 -#include <deque>
1.44 -#include <vector>
1.45 -#include <algorithm>
1.46 -
1.47 -#include <hugo/invalid.h>
1.48 -
1.49 -namespace hugo {
1.50 -
1.51 - /// \addtogroup paths
1.52 - /// @{
1.53 -
1.54 -
1.55 - //! \brief A structure for representing directed paths in a graph.
1.56 - //!
1.57 - //! A structure for representing directed path in a graph.
1.58 - //! \param Graph The graph type in which the path is.
1.59 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.60 - //!
1.61 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.62 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.63 - //! and \c Edge of the original graph.
1.64 - //!
1.65 - //! \todo Thoroughfully check all the range and consistency tests.
1.66 - template<typename Graph>
1.67 - class DirPath {
1.68 - public:
1.69 - /// Edge type of the underlying graph.
1.70 - typedef typename Graph::Edge GraphEdge;
1.71 - /// Node type of the underlying graph.
1.72 - typedef typename Graph::Node GraphNode;
1.73 - class NodeIt;
1.74 - class EdgeIt;
1.75 -
1.76 - protected:
1.77 - const Graph *gr;
1.78 - typedef std::vector<GraphEdge> Container;
1.79 - Container edges;
1.80 -
1.81 - public:
1.82 -
1.83 - /// \param _G The graph in which the path is.
1.84 - ///
1.85 - DirPath(const Graph &_G) : gr(&_G) {}
1.86 -
1.87 - /// \brief Subpath constructor.
1.88 - ///
1.89 - /// Subpath defined by two nodes.
1.90 - /// \warning It is an error if the two edges are not in order!
1.91 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.92 - gr = P.gr;
1.93 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.94 - }
1.95 -
1.96 - /// \brief Subpath constructor.
1.97 - ///
1.98 - /// Subpath defined by two edges. Contains edges in [a,b)
1.99 - /// \warning It is an error if the two edges are not in order!
1.100 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.101 - gr = P.gr;
1.102 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.103 - }
1.104 -
1.105 - /// Length of the path.
1.106 - size_t length() const { return edges.size(); }
1.107 - /// Returns whether the path is empty.
1.108 - bool empty() const { return edges.empty(); }
1.109 -
1.110 - /// Resets the path to an empty path.
1.111 - void clear() { edges.clear(); }
1.112 -
1.113 - /// \brief Starting point of the path.
1.114 - ///
1.115 - /// Starting point of the path.
1.116 - /// Returns INVALID if the path is empty.
1.117 - GraphNode tail() const {
1.118 - return empty() ? INVALID : gr->tail(edges[0]);
1.119 - }
1.120 - /// \brief End point of the path.
1.121 - ///
1.122 - /// End point of the path.
1.123 - /// Returns INVALID if the path is empty.
1.124 - GraphNode head() const {
1.125 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.126 - }
1.127 -
1.128 - /// \brief Initializes node or edge iterator to point to the first
1.129 - /// node or edge.
1.130 - ///
1.131 - /// \sa nth
1.132 - template<typename It>
1.133 - It& first(It &i) const { return i=It(*this); }
1.134 -
1.135 - /// \brief Initializes node iterator to point to the node of a given index.
1.136 - NodeIt& nth(NodeIt &i, int n) const {
1.137 - return i=NodeIt(*this, n);
1.138 - }
1.139 -
1.140 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.141 - EdgeIt& nth(EdgeIt &i, int n) const {
1.142 - return i=EdgeIt(*this, n);
1.143 - }
1.144 -
1.145 - /// \brief Returns node iterator pointing to the head node of the
1.146 - /// given edge iterator.
1.147 - NodeIt head(const EdgeIt& e) const {
1.148 - return NodeIt(*this, e.idx+1);
1.149 - }
1.150 -
1.151 - /// \brief Returns node iterator pointing to the tail node of the
1.152 - /// given edge iterator.
1.153 - NodeIt tail(const EdgeIt& e) const {
1.154 - return NodeIt(*this, e.idx);
1.155 - }
1.156 -
1.157 -
1.158 - /* Iterator classes */
1.159 -
1.160 - /**
1.161 - * \brief Iterator class to iterate on the edges of the paths
1.162 - *
1.163 - * \ingroup paths
1.164 - * This class is used to iterate on the edges of the paths
1.165 - *
1.166 - * Of course it converts to Graph::Edge
1.167 - *
1.168 - */
1.169 - class EdgeIt {
1.170 - friend class DirPath;
1.171 -
1.172 - int idx;
1.173 - const DirPath *p;
1.174 - public:
1.175 - /// Default constructor
1.176 - EdgeIt() {}
1.177 - /// Invalid constructor
1.178 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.179 - /// Constructor with starting point
1.180 - EdgeIt(const DirPath &_p, int _idx = 0) :
1.181 - idx(_idx), p(&_p) { validate(); }
1.182 -
1.183 - ///Validity check
1.184 - bool valid() const { return idx!=-1; }
1.185 -
1.186 - ///Conversion to Graph::Edge
1.187 - operator GraphEdge () const {
1.188 - return valid() ? p->edges[idx] : INVALID;
1.189 - }
1.190 -
1.191 - /// Next edge
1.192 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.193 -
1.194 - /// Comparison operator
1.195 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.196 - /// Comparison operator
1.197 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.198 - /// Comparison operator
1.199 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.200 -
1.201 - private:
1.202 - // FIXME: comparison between signed and unsigned...
1.203 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.204 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.205 - };
1.206 -
1.207 - /**
1.208 - * \brief Iterator class to iterate on the nodes of the paths
1.209 - *
1.210 - * \ingroup paths
1.211 - * This class is used to iterate on the nodes of the paths
1.212 - *
1.213 - * Of course it converts to Graph::Node
1.214 - *
1.215 - */
1.216 - class NodeIt {
1.217 - friend class DirPath;
1.218 -
1.219 - int idx;
1.220 - const DirPath *p;
1.221 - public:
1.222 - /// Default constructor
1.223 - NodeIt() {}
1.224 - /// Invalid constructor
1.225 - NodeIt(Invalid) : idx(-1), p(0) {}
1.226 - /// Constructor with starting point
1.227 - NodeIt(const DirPath &_p, int _idx = 0) :
1.228 - idx(_idx), p(&_p) { validate(); }
1.229 -
1.230 - ///Validity check
1.231 - bool valid() const { return idx!=-1; }
1.232 -
1.233 - ///Conversion to Graph::Node
1.234 - operator const GraphNode& () const {
1.235 - if(idx >= p->length())
1.236 - return p->head();
1.237 - else if(idx >= 0)
1.238 - return p->gr->tail(p->edges[idx]);
1.239 - else
1.240 - return INVALID;
1.241 - }
1.242 - /// Next node
1.243 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.244 -
1.245 - /// Comparison operator
1.246 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.247 - /// Comparison operator
1.248 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.249 - /// Comparison operator
1.250 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.251 -
1.252 - private:
1.253 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.254 - };
1.255 -
1.256 - friend class Builder;
1.257 -
1.258 - /**
1.259 - * \brief Class to build paths
1.260 - *
1.261 - * \ingroup paths
1.262 - * This class is used to fill a path with edges.
1.263 - *
1.264 - * You can push new edges to the front and to the back of the path in
1.265 - * arbitrary order then you should commit these changes to the graph.
1.266 - *
1.267 - * Fundamentally, for most "Paths" (classes fulfilling the
1.268 - * PathConcept) while the builder is active (after the first modifying
1.269 - * operation and until the commit()) the original Path is in a
1.270 - * "transitional" state (operations on it have undefined result). But
1.271 - * in the case of DirPath the original path remains unchanged until the
1.272 - * commit. However we don't recomend that you use this feature.
1.273 - */
1.274 - class Builder {
1.275 - DirPath &P;
1.276 - Container front, back;
1.277 -
1.278 - public:
1.279 - ///\param _P the path you want to fill in.
1.280 - ///
1.281 - Builder(DirPath &_P) : P(_P) {}
1.282 -
1.283 - /// Sets the starting node of the path.
1.284 -
1.285 - /// Sets the starting node of the path. Edge added to the path
1.286 - /// afterwards have to be incident to this node.
1.287 - /// It should be called if and only if
1.288 - /// the path is empty and before any call to
1.289 - /// \ref pushFront() or \ref pushBack()
1.290 - void setStartNode(const GraphNode &) {}
1.291 -
1.292 - ///Push a new edge to the front of the path
1.293 -
1.294 - ///Push a new edge to the front of the path.
1.295 - ///\sa setStartNode
1.296 - void pushFront(const GraphEdge& e) {
1.297 - front.push_back(e);
1.298 - }
1.299 -
1.300 - ///Push a new edge to the back of the path
1.301 -
1.302 - ///Push a new edge to the back of the path.
1.303 - ///\sa setStartNode
1.304 - void pushBack(const GraphEdge& e) {
1.305 - back.push_back(e);
1.306 - }
1.307 -
1.308 - ///Commit the changes to the path.
1.309 - void commit() {
1.310 - if( !front.empty() || !back.empty() ) {
1.311 - Container tmp;
1.312 - tmp.reserve(front.size()+back.size()+P.length());
1.313 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.314 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.315 - tmp.insert(tmp.end(), back.begin(), back.end());
1.316 - P.edges.swap(tmp);
1.317 - front.clear();
1.318 - back.clear();
1.319 - }
1.320 - }
1.321 -
1.322 - ///Reserve storage for the builder in advance.
1.323 -
1.324 - ///If you know a reasonable upper bound of the number of the edges
1.325 - ///to add to the front, using this function you can speed up the building.
1.326 -
1.327 - void reserveFront(size_t r) {front.reserve(r);}
1.328 -
1.329 - ///Reserve storage for the builder in advance.
1.330 -
1.331 - ///If you know a reasonable upper bound of the number of the edges
1.332 - ///to add to the back, using this function you can speed up the building.
1.333 -
1.334 - void reserveBack(size_t r) {back.reserve(r);}
1.335 -
1.336 - private:
1.337 - bool empty() {
1.338 - return front.empty() && back.empty() && P.empty();
1.339 - }
1.340 -
1.341 - GraphNode tail() const {
1.342 - if( ! front.empty() )
1.343 - return P.gr->tail(front[front.size()-1]);
1.344 - else if( ! P.empty() )
1.345 - return P.gr->tail(P.edges[0]);
1.346 - else if( ! back.empty() )
1.347 - return P.gr->tail(back[0]);
1.348 - else
1.349 - return INVALID;
1.350 - }
1.351 - GraphNode head() const {
1.352 - if( ! back.empty() )
1.353 - return P.gr->head(back[back.size()-1]);
1.354 - else if( ! P.empty() )
1.355 - return P.gr->head(P.edges[P.length()-1]);
1.356 - else if( ! front.empty() )
1.357 - return P.gr->head(front[0]);
1.358 - else
1.359 - return INVALID;
1.360 - }
1.361 -
1.362 - };
1.363 -
1.364 - };
1.365 -
1.366 -
1.367 -
1.368 -
1.369 -
1.370 -
1.371 -
1.372 -
1.373 -
1.374 -
1.375 - /**********************************************************************/
1.376 -
1.377 -
1.378 - //! \brief A structure for representing undirected path in a graph.
1.379 - //!
1.380 - //! A structure for representing undirected path in a graph. Ie. this is
1.381 - //! a path in a \e directed graph but the edges should not be directed
1.382 - //! forward.
1.383 - //!
1.384 - //! \param Graph The graph type in which the path is.
1.385 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.386 - //!
1.387 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.388 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.389 - //! and \c Edge of the original graph.
1.390 - //!
1.391 - //! \todo Thoroughfully check all the range and consistency tests.
1.392 - template<typename Graph>
1.393 - class UndirPath {
1.394 - public:
1.395 - /// Edge type of the underlying graph.
1.396 - typedef typename Graph::Edge GraphEdge;
1.397 - /// Node type of the underlying graph.
1.398 - typedef typename Graph::Node GraphNode;
1.399 - class NodeIt;
1.400 - class EdgeIt;
1.401 -
1.402 - protected:
1.403 - const Graph *gr;
1.404 - typedef std::vector<GraphEdge> Container;
1.405 - Container edges;
1.406 -
1.407 - public:
1.408 -
1.409 - /// \param _G The graph in which the path is.
1.410 - ///
1.411 - UndirPath(const Graph &_G) : gr(&_G) {}
1.412 -
1.413 - /// \brief Subpath constructor.
1.414 - ///
1.415 - /// Subpath defined by two nodes.
1.416 - /// \warning It is an error if the two edges are not in order!
1.417 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.418 - gr = P.gr;
1.419 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.420 - }
1.421 -
1.422 - /// \brief Subpath constructor.
1.423 - ///
1.424 - /// Subpath defined by two edges. Contains edges in [a,b)
1.425 - /// \warning It is an error if the two edges are not in order!
1.426 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.427 - gr = P.gr;
1.428 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.429 - }
1.430 -
1.431 - /// Length of the path.
1.432 - size_t length() const { return edges.size(); }
1.433 - /// Returns whether the path is empty.
1.434 - bool empty() const { return edges.empty(); }
1.435 -
1.436 - /// Resets the path to an empty path.
1.437 - void clear() { edges.clear(); }
1.438 -
1.439 - /// \brief Starting point of the path.
1.440 - ///
1.441 - /// Starting point of the path.
1.442 - /// Returns INVALID if the path is empty.
1.443 - GraphNode tail() const {
1.444 - return empty() ? INVALID : gr->tail(edges[0]);
1.445 - }
1.446 - /// \brief End point of the path.
1.447 - ///
1.448 - /// End point of the path.
1.449 - /// Returns INVALID if the path is empty.
1.450 - GraphNode head() const {
1.451 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.452 - }
1.453 -
1.454 - /// \brief Initializes node or edge iterator to point to the first
1.455 - /// node or edge.
1.456 - ///
1.457 - /// \sa nth
1.458 - template<typename It>
1.459 - It& first(It &i) const { return i=It(*this); }
1.460 -
1.461 - /// \brief Initializes node iterator to point to the node of a given index.
1.462 - NodeIt& nth(NodeIt &i, int n) const {
1.463 - return i=NodeIt(*this, n);
1.464 - }
1.465 -
1.466 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.467 - EdgeIt& nth(EdgeIt &i, int n) const {
1.468 - return i=EdgeIt(*this, n);
1.469 - }
1.470 -
1.471 - /// Checks validity of a node or edge iterator.
1.472 - template<typename It>
1.473 - static
1.474 - bool valid(const It &i) { return i.valid(); }
1.475 -
1.476 - /// Steps the given node or edge iterator.
1.477 - template<typename It>
1.478 - static
1.479 - It& next(It &e) {
1.480 - return ++e;
1.481 - }
1.482 -
1.483 - /// \brief Returns node iterator pointing to the head node of the
1.484 - /// given edge iterator.
1.485 - NodeIt head(const EdgeIt& e) const {
1.486 - return NodeIt(*this, e.idx+1);
1.487 - }
1.488 -
1.489 - /// \brief Returns node iterator pointing to the tail node of the
1.490 - /// given edge iterator.
1.491 - NodeIt tail(const EdgeIt& e) const {
1.492 - return NodeIt(*this, e.idx);
1.493 - }
1.494 -
1.495 -
1.496 -
1.497 - /**
1.498 - * \brief Iterator class to iterate on the edges of the paths
1.499 - *
1.500 - * \ingroup paths
1.501 - * This class is used to iterate on the edges of the paths
1.502 - *
1.503 - * Of course it converts to Graph::Edge
1.504 - *
1.505 - * \todo Its interface differs from the standard edge iterator.
1.506 - * Yes, it shouldn't.
1.507 - */
1.508 - class EdgeIt {
1.509 - friend class UndirPath;
1.510 -
1.511 - int idx;
1.512 - const UndirPath *p;
1.513 - public:
1.514 - /// Default constructor
1.515 - EdgeIt() {}
1.516 - /// Invalid constructor
1.517 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.518 - /// Constructor with starting point
1.519 - EdgeIt(const UndirPath &_p, int _idx = 0) :
1.520 - idx(_idx), p(&_p) { validate(); }
1.521 -
1.522 - ///Validity check
1.523 - bool valid() const { return idx!=-1; }
1.524 -
1.525 - ///Conversion to Graph::Edge
1.526 - operator GraphEdge () const {
1.527 - return valid() ? p->edges[idx] : INVALID;
1.528 - }
1.529 - /// Next edge
1.530 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.531 -
1.532 - /// Comparison operator
1.533 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.534 - /// Comparison operator
1.535 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.536 - /// Comparison operator
1.537 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.538 -
1.539 - private:
1.540 - // FIXME: comparison between signed and unsigned...
1.541 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.542 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.543 - };
1.544 -
1.545 - /**
1.546 - * \brief Iterator class to iterate on the nodes of the paths
1.547 - *
1.548 - * \ingroup paths
1.549 - * This class is used to iterate on the nodes of the paths
1.550 - *
1.551 - * Of course it converts to Graph::Node
1.552 - *
1.553 - * \todo Its interface differs from the standard node iterator.
1.554 - * Yes, it shouldn't.
1.555 - */
1.556 - class NodeIt {
1.557 - friend class UndirPath;
1.558 -
1.559 - int idx;
1.560 - const UndirPath *p;
1.561 - public:
1.562 - /// Default constructor
1.563 - NodeIt() {}
1.564 - /// Invalid constructor
1.565 - NodeIt(Invalid) : idx(-1), p(0) {}
1.566 - /// Constructor with starting point
1.567 - NodeIt(const UndirPath &_p, int _idx = 0) :
1.568 - idx(_idx), p(&_p) { validate(); }
1.569 -
1.570 - ///Validity check
1.571 - bool valid() const { return idx!=-1; }
1.572 -
1.573 - ///Conversion to Graph::Node
1.574 - operator const GraphNode& () const {
1.575 - if(idx >= p->length())
1.576 - return p->head();
1.577 - else if(idx >= 0)
1.578 - return p->gr->tail(p->edges[idx]);
1.579 - else
1.580 - return INVALID;
1.581 - }
1.582 - /// Next node
1.583 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.584 -
1.585 - /// Comparison operator
1.586 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.587 - /// Comparison operator
1.588 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.589 - /// Comparison operator
1.590 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.591 -
1.592 - private:
1.593 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.594 - };
1.595 -
1.596 - friend class Builder;
1.597 -
1.598 - /**
1.599 - * \brief Class to build paths
1.600 - *
1.601 - * \ingroup paths
1.602 - * This class is used to fill a path with edges.
1.603 - *
1.604 - * You can push new edges to the front and to the back of the path in
1.605 - * arbitrary order then you should commit these changes to the graph.
1.606 - *
1.607 - * Fundamentally, for most "Paths" (classes fulfilling the
1.608 - * PathConcept) while the builder is active (after the first modifying
1.609 - * operation and until the commit()) the original Path is in a
1.610 - * "transitional" state (operations ot it have undefined result). But
1.611 - * in the case of UndirPath the original path is unchanged until the
1.612 - * commit. However we don't recomend that you use this feature.
1.613 - */
1.614 - class Builder {
1.615 - UndirPath &P;
1.616 - Container front, back;
1.617 -
1.618 - public:
1.619 - ///\param _P the path you want to fill in.
1.620 - ///
1.621 - Builder(UndirPath &_P) : P(_P) {}
1.622 -
1.623 - /// Sets the starting node of the path.
1.624 -
1.625 - /// Sets the starting node of the path. Edge added to the path
1.626 - /// afterwards have to be incident to this node.
1.627 - /// It should be called if and only if
1.628 - /// the path is empty and before any call to
1.629 - /// \ref pushFront() or \ref pushBack()
1.630 - void setStartNode(const GraphNode &) {}
1.631 -
1.632 - ///Push a new edge to the front of the path
1.633 -
1.634 - ///Push a new edge to the front of the path.
1.635 - ///\sa setStartNode
1.636 - void pushFront(const GraphEdge& e) {
1.637 - front.push_back(e);
1.638 - }
1.639 -
1.640 - ///Push a new edge to the back of the path
1.641 -
1.642 - ///Push a new edge to the back of the path.
1.643 - ///\sa setStartNode
1.644 - void pushBack(const GraphEdge& e) {
1.645 - back.push_back(e);
1.646 - }
1.647 -
1.648 - ///Commit the changes to the path.
1.649 - void commit() {
1.650 - if( !(front.empty() && back.empty()) ) {
1.651 - Container tmp;
1.652 - tmp.reserve(front.size()+back.size()+P.length());
1.653 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.654 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.655 - tmp.insert(tmp.end(), back.begin(), back.end());
1.656 - P.edges.swap(tmp);
1.657 - front.clear();
1.658 - back.clear();
1.659 - }
1.660 - }
1.661 -
1.662 -
1.663 - ///Reserve storage for the builder in advance.
1.664 -
1.665 - ///If you know a reasonable upper bound of the number of the edges
1.666 - ///to add to the front, using this function you can speed up the building.
1.667 -
1.668 - void reserveFront(size_t r) {front.reserve(r);}
1.669 -
1.670 - ///Reserve storage for the builder in advance.
1.671 -
1.672 - ///If you know a reasonable upper bound of the number of the edges
1.673 - ///to add to the back, using this function you can speed up the building.
1.674 -
1.675 - void reserveBack(size_t r) {back.reserve(r);}
1.676 -
1.677 - private:
1.678 - bool empty() {
1.679 - return front.empty() && back.empty() && P.empty();
1.680 - }
1.681 -
1.682 - GraphNode tail() const {
1.683 - if( ! front.empty() )
1.684 - return P.gr->tail(front[front.size()-1]);
1.685 - else if( ! P.empty() )
1.686 - return P.gr->tail(P.edges[0]);
1.687 - else if( ! back.empty() )
1.688 - return P.gr->tail(back[0]);
1.689 - else
1.690 - return INVALID;
1.691 - }
1.692 - GraphNode head() const {
1.693 - if( ! back.empty() )
1.694 - return P.gr->head(back[back.size()-1]);
1.695 - else if( ! P.empty() )
1.696 - return P.gr->head(P.edges[P.length()-1]);
1.697 - else if( ! front.empty() )
1.698 - return P.gr->head(front[0]);
1.699 - else
1.700 - return INVALID;
1.701 - }
1.702 -
1.703 - };
1.704 -
1.705 - };
1.706 -
1.707 -
1.708 - ///@}
1.709 -
1.710 -} // namespace hugo
1.711 -
1.712 -#endif // HUGO_PATH_H