1.1 --- a/src/lemon/path.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,703 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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