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