1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/path.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,709 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/path.h - Part of LEMON, 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 LEMON.
1.24 +
1.25 +LEMON 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 lemon::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 LEMON_PATH_H
1.41 +#define LEMON_PATH_H
1.42 +
1.43 +#include <deque>
1.44 +#include <vector>
1.45 +#include <algorithm>
1.46 +
1.47 +#include <lemon/invalid.h>
1.48 +
1.49 +namespace lemon {
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 lemon
1.711 +
1.712 +#endif // LEMON_PATH_H