1.1 --- a/src/work/alpar/path.h Tue Jun 15 06:30:03 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,748 +0,0 @@
1.4 -// -*- c++ -*- //
1.5 -
1.6 -/**
1.7 -@defgroup paths Path Structures
1.8 -@ingroup datas
1.9 -\brief Path structures implemented in Hugo.
1.10 -
1.11 -Hugolib provides flexible data structures
1.12 -to work with paths.
1.13 -
1.14 -All of them have the same interface, especially they can be built or extended
1.15 -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
1.16 -algorithm to store its result in any kind of path structure.
1.17 -
1.18 -*/
1.19 -
1.20 -///\ingroup paths
1.21 -///\file
1.22 -///\brief Classes for representing paths in graphs.
1.23 -
1.24 -#ifndef HUGO_PATH_H
1.25 -#define HUGO_PATH_H
1.26 -
1.27 -#include <deque>
1.28 -#include <vector>
1.29 -#include <algorithm>
1.30 -
1.31 -#include <hugo/invalid.h>
1.32 -#include <hugo/error.h>
1.33 -#include <debug.h>
1.34 -
1.35 -namespace hugo {
1.36 -
1.37 - /// \addtogroup paths
1.38 - /// @{
1.39 -
1.40 -
1.41 - //! \brief A structure for representing directed path in a graph.
1.42 - //!
1.43 - //! A structure for representing directed path in a graph.
1.44 - //! \param Graph The graph type in which the path is.
1.45 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.46 - //!
1.47 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.48 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.49 - //! and \c Edge of the original graph.
1.50 - //!
1.51 - //! \todo Thoroughfully check all the range and consistency tests.
1.52 - template<typename Graph, typename DM = DefaultDebugMode>
1.53 - class DirPath {
1.54 - public:
1.55 - /// Edge type of the underlying graph.
1.56 - typedef typename Graph::Edge GraphEdge;
1.57 - /// Node type of the underlying graph.
1.58 - typedef typename Graph::Node GraphNode;
1.59 - class NodeIt;
1.60 - class EdgeIt;
1.61 -
1.62 - protected:
1.63 - const Graph *gr;
1.64 - typedef std::vector<GraphEdge> Container;
1.65 - Container edges;
1.66 -
1.67 - public:
1.68 -
1.69 - /// \param _G The graph in which the path is.
1.70 - ///
1.71 - DirPath(const Graph &_G) : gr(&_G) {}
1.72 -
1.73 - /// \brief Subpath constructor.
1.74 - ///
1.75 - /// Subpath defined by two nodes.
1.76 - /// \warning It is an error if the two edges are not in order!
1.77 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.78 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.79 - // FIXME: this check should be more elaborate...
1.80 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.81 - }
1.82 - gr = P.gr;
1.83 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.84 - }
1.85 -
1.86 - /// \brief Subpath constructor.
1.87 - ///
1.88 - /// Subpath defined by two edges. Contains edges in [a,b)
1.89 - /// \warning It is an error if the two edges are not in order!
1.90 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.91 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.92 - // FIXME: this check should be more elaborate...
1.93 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.94 - }
1.95 - gr = P.gr;
1.96 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.97 - }
1.98 -
1.99 - /// Length of the path.
1.100 - size_t length() const { return edges.size(); }
1.101 - /// Returns whether the path is empty.
1.102 - bool empty() const { return edges.empty(); }
1.103 -
1.104 - /// Resets the path to an empty path.
1.105 - void clear() { edges.clear(); }
1.106 -
1.107 - /// \brief Starting point of the path.
1.108 - ///
1.109 - /// Starting point of the path.
1.110 - /// Returns INVALID if the path is empty.
1.111 - GraphNode from() const {
1.112 - return empty() ? INVALID : gr->tail(edges[0]);
1.113 - }
1.114 - /// \brief End point of the path.
1.115 - ///
1.116 - /// End point of the path.
1.117 - /// Returns INVALID if the path is empty.
1.118 - GraphNode to() const {
1.119 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.120 - }
1.121 -
1.122 - /// \brief Initializes node or edge iterator to point to the first
1.123 - /// node or edge.
1.124 - ///
1.125 - /// \sa nth
1.126 - template<typename It>
1.127 - It& first(It &i) const { return i=It(*this); }
1.128 -
1.129 - /// \brief Initializes node iterator to point to the node of a given index.
1.130 - NodeIt& nth(NodeIt &i, int n) const {
1.131 - if( DM::range_check && (n<0 || n>int(length())) )
1.132 - fault("DirPath::nth: index out of range");
1.133 - return i=NodeIt(*this, n);
1.134 - }
1.135 -
1.136 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.137 - EdgeIt& nth(EdgeIt &i, int n) const {
1.138 - if( DM::range_check && (n<0 || n>=int(length())) )
1.139 - fault("DirPath::nth: index out of range");
1.140 - return i=EdgeIt(*this, n);
1.141 - }
1.142 -
1.143 - /// Checks validity of a node or edge iterator.
1.144 - template<typename It>
1.145 - static
1.146 - bool valid(const It &i) { return i.valid(); }
1.147 -
1.148 - /// Steps the given node or edge iterator.
1.149 - template<typename It>
1.150 - static
1.151 - It& next(It &e) {
1.152 - if( DM::range_check && !e.valid() )
1.153 - fault("DirPath::next() on invalid iterator");
1.154 - return ++e;
1.155 - }
1.156 -
1.157 - /// \brief Returns node iterator pointing to the head node of the
1.158 - /// given edge iterator.
1.159 - NodeIt head(const EdgeIt& e) const {
1.160 - if( DM::range_check && !e.valid() )
1.161 - fault("DirPath::head() on invalid iterator");
1.162 - return NodeIt(*this, e.idx+1);
1.163 - }
1.164 -
1.165 - /// \brief Returns node iterator pointing to the tail node of the
1.166 - /// given edge iterator.
1.167 - NodeIt tail(const EdgeIt& e) const {
1.168 - if( DM::range_check && !e.valid() )
1.169 - fault("DirPath::tail() on invalid iterator");
1.170 - return NodeIt(*this, e.idx);
1.171 - }
1.172 -
1.173 -
1.174 - /* Iterator classes */
1.175 -
1.176 - /**
1.177 - * \brief Iterator class to iterate on the edges of the paths
1.178 - *
1.179 - * \ingroup paths
1.180 - * This class is used to iterate on the edges of the paths
1.181 - *
1.182 - * Of course it converts to Graph::Edge
1.183 - *
1.184 - * \todo Its interface differs from the standard edge iterator.
1.185 - * Yes, it shouldn't.
1.186 - */
1.187 - class EdgeIt {
1.188 - friend class DirPath;
1.189 -
1.190 - int idx;
1.191 - const DirPath *p;
1.192 - public:
1.193 - /// Default constructor
1.194 - EdgeIt() {}
1.195 - /// Invalid constructor
1.196 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.197 - /// Constructor with starting point
1.198 - EdgeIt(const DirPath &_p, int _idx = 0) :
1.199 - idx(_idx), p(&_p) { validate(); }
1.200 -
1.201 - ///Validity check
1.202 - bool valid() const { return idx!=-1; }
1.203 -
1.204 - ///Conversion to Graph::Edge
1.205 - operator GraphEdge () const {
1.206 - return valid() ? p->edges[idx] : INVALID;
1.207 - }
1.208 -
1.209 - /// Next edge
1.210 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.211 -
1.212 - /// Comparison operator
1.213 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.214 - /// Comparison operator
1.215 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.216 - /// Comparison operator
1.217 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.218 -
1.219 - private:
1.220 - // FIXME: comparison between signed and unsigned...
1.221 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.222 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.223 - };
1.224 -
1.225 - /**
1.226 - * \brief Iterator class to iterate on the nodes of the paths
1.227 - *
1.228 - * \ingroup paths
1.229 - * This class is used to iterate on the nodes of the paths
1.230 - *
1.231 - * Of course it converts to Graph::Node
1.232 - *
1.233 - * \todo Its interface differs from the standard node iterator.
1.234 - * Yes, it shouldn't.
1.235 - */
1.236 - class NodeIt {
1.237 - friend class DirPath;
1.238 -
1.239 - int idx;
1.240 - const DirPath *p;
1.241 - public:
1.242 - /// Default constructor
1.243 - NodeIt() {}
1.244 - /// Invalid constructor
1.245 - NodeIt(Invalid) : idx(-1), p(0) {}
1.246 - /// Constructor with starting point
1.247 - NodeIt(const DirPath &_p, int _idx = 0) :
1.248 - idx(_idx), p(&_p) { validate(); }
1.249 -
1.250 - ///Validity check
1.251 - bool valid() const { return idx!=-1; }
1.252 -
1.253 - ///Conversion to Graph::Node
1.254 - operator const GraphNode& () const {
1.255 - if(idx >= p->length())
1.256 - return p->to();
1.257 - else if(idx >= 0)
1.258 - return p->gr->tail(p->edges[idx]);
1.259 - else
1.260 - return INVALID;
1.261 - }
1.262 - /// Next node
1.263 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.264 -
1.265 - /// Comparison operator
1.266 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.267 - /// Comparison operator
1.268 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.269 - /// Comparison operator
1.270 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.271 -
1.272 - private:
1.273 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.274 - };
1.275 -
1.276 - friend class Builder;
1.277 -
1.278 - /**
1.279 - * \brief Class to build paths
1.280 - *
1.281 - * \ingroup paths
1.282 - * This class is used to fill a path with edges.
1.283 - *
1.284 - * You can push new edges to the front and to the back of the path in
1.285 - * arbitrary order then you should commit these changes to the graph.
1.286 - *
1.287 - * Fundamentally, for most "Paths" (classes fulfilling the
1.288 - * PathConcept) while the builder is active (after the first modifying
1.289 - * operation and until the commit()) the original Path is in a
1.290 - * "transitional" state (operations on it have undefined result). But
1.291 - * in the case of DirPath the original path remains unchanged until the
1.292 - * commit. However we don't recomend that you use this feature.
1.293 - */
1.294 - class Builder {
1.295 - DirPath &P;
1.296 - Container front, back;
1.297 -
1.298 - public:
1.299 - ///\param _P the path you want to fill in.
1.300 - ///
1.301 - Builder(DirPath &_P) : P(_P) {}
1.302 -
1.303 - /// Sets the starting node of the path.
1.304 -
1.305 - /// Sets the starting node of the path. Edge added to the path
1.306 - /// afterwards have to be incident to this node.
1.307 - /// It should be called iff the path is empty and before any call to
1.308 - /// \ref pushFront() or \ref pushBack()
1.309 - void setStart(const GraphNode &) {}
1.310 -
1.311 - ///Push a new edge to the front of the path
1.312 -
1.313 - ///Push a new edge to the front of the path.
1.314 - ///\sa setStart
1.315 - void pushFront(const GraphEdge& e) {
1.316 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.317 - fault("DirPath::Builder::pushFront: nonincident edge");
1.318 - }
1.319 - front.push_back(e);
1.320 - }
1.321 -
1.322 - ///Push a new edge to the back of the path
1.323 -
1.324 - ///Push a new edge to the back of the path.
1.325 - ///\sa setStart
1.326 - void pushBack(const GraphEdge& e) {
1.327 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.328 - fault("DirPath::Builder::pushBack: nonincident edge");
1.329 - }
1.330 - back.push_back(e);
1.331 - }
1.332 -
1.333 - ///Commit the changes to the path.
1.334 - void commit() {
1.335 - if( !(front.empty() && back.empty()) ) {
1.336 - Container tmp;
1.337 - tmp.reserve(front.size()+back.size()+P.length());
1.338 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.339 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.340 - tmp.insert(tmp.end(), back.begin(), back.end());
1.341 - P.edges.swap(tmp);
1.342 - front.clear();
1.343 - back.clear();
1.344 - }
1.345 - }
1.346 -
1.347 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.348 - // Hogy kenyelmes egy ilyet hasznalni?
1.349 -
1.350 - ///Reserve storage in advance for the builder
1.351 -
1.352 - ///If you know an reasonable upper bound of the number of the edges
1.353 - ///to add, using this function you can speed up the building.
1.354 - void reserve(size_t r) {
1.355 - front.reserve(r);
1.356 - back.reserve(r);
1.357 - }
1.358 -
1.359 - private:
1.360 - bool empty() {
1.361 - return front.empty() && back.empty() && P.empty();
1.362 - }
1.363 -
1.364 - GraphNode from() const {
1.365 - if( ! front.empty() )
1.366 - return P.gr->tail(front[front.size()-1]);
1.367 - else if( ! P.empty() )
1.368 - return P.gr->tail(P.edges[0]);
1.369 - else if( ! back.empty() )
1.370 - return P.gr->tail(back[0]);
1.371 - else
1.372 - return INVALID;
1.373 - }
1.374 - GraphNode to() const {
1.375 - if( ! back.empty() )
1.376 - return P.gr->head(back[back.size()-1]);
1.377 - else if( ! P.empty() )
1.378 - return P.gr->head(P.edges[P.length()-1]);
1.379 - else if( ! front.empty() )
1.380 - return P.gr->head(front[0]);
1.381 - else
1.382 - return INVALID;
1.383 - }
1.384 -
1.385 - };
1.386 -
1.387 - };
1.388 -
1.389 -
1.390 -
1.391 -
1.392 -
1.393 -
1.394 - /**********************************************************************/
1.395 -
1.396 -
1.397 - //! \brief A structure for representing undirected path in a graph.
1.398 - //!
1.399 - //! A structure for representing undirected path in a graph. Ie. this is
1.400 - //! a path in a \e directed graph but the edges should not be directed
1.401 - //! forward.
1.402 - //!
1.403 - //! \param Graph The graph type in which the path is.
1.404 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.405 - //!
1.406 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.407 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.408 - //! and \c Edge of the original graph.
1.409 - //!
1.410 - //! \todo Thoroughfully check all the range and consistency tests.
1.411 - template<typename Graph, typename DM = DefaultDebugMode>
1.412 - class UndirPath {
1.413 - public:
1.414 - /// Edge type of the underlying graph.
1.415 - typedef typename Graph::Edge GraphEdge;
1.416 - /// Node type of the underlying graph.
1.417 - typedef typename Graph::Node GraphNode;
1.418 - class NodeIt;
1.419 - class EdgeIt;
1.420 -
1.421 - protected:
1.422 - const Graph *gr;
1.423 - typedef std::vector<GraphEdge> Container;
1.424 - Container edges;
1.425 -
1.426 - public:
1.427 -
1.428 - /// \param _G The graph in which the path is.
1.429 - ///
1.430 - UndirPath(const Graph &_G) : gr(&_G) {}
1.431 -
1.432 - /// \brief Subpath constructor.
1.433 - ///
1.434 - /// Subpath defined by two nodes.
1.435 - /// \warning It is an error if the two edges are not in order!
1.436 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.437 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.438 - // FIXME: this check should be more elaborate...
1.439 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.440 - }
1.441 - gr = P.gr;
1.442 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.443 - }
1.444 -
1.445 - /// \brief Subpath constructor.
1.446 - ///
1.447 - /// Subpath defined by two edges. Contains edges in [a,b)
1.448 - /// \warning It is an error if the two edges are not in order!
1.449 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.450 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.451 - // FIXME: this check should be more elaborate...
1.452 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.453 - }
1.454 - gr = P.gr;
1.455 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.456 - }
1.457 -
1.458 - /// Length of the path.
1.459 - size_t length() const { return edges.size(); }
1.460 - /// Returns whether the path is empty.
1.461 - bool empty() const { return edges.empty(); }
1.462 -
1.463 - /// Resets the path to an empty path.
1.464 - void clear() { edges.clear(); }
1.465 -
1.466 - /// \brief Starting point of the path.
1.467 - ///
1.468 - /// Starting point of the path.
1.469 - /// Returns INVALID if the path is empty.
1.470 - GraphNode from() const {
1.471 - return empty() ? INVALID : gr->tail(edges[0]);
1.472 - }
1.473 - /// \brief End point of the path.
1.474 - ///
1.475 - /// End point of the path.
1.476 - /// Returns INVALID if the path is empty.
1.477 - GraphNode to() const {
1.478 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.479 - }
1.480 -
1.481 - /// \brief Initializes node or edge iterator to point to the first
1.482 - /// node or edge.
1.483 - ///
1.484 - /// \sa nth
1.485 - template<typename It>
1.486 - It& first(It &i) const { return i=It(*this); }
1.487 -
1.488 - /// \brief Initializes node iterator to point to the node of a given index.
1.489 - NodeIt& nth(NodeIt &i, int n) const {
1.490 - if( DM::range_check && (n<0 || n>int(length())) )
1.491 - fault("UndirPath::nth: index out of range");
1.492 - return i=NodeIt(*this, n);
1.493 - }
1.494 -
1.495 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.496 - EdgeIt& nth(EdgeIt &i, int n) const {
1.497 - if( DM::range_check && (n<0 || n>=int(length())) )
1.498 - fault("UndirPath::nth: index out of range");
1.499 - return i=EdgeIt(*this, n);
1.500 - }
1.501 -
1.502 - /// Checks validity of a node or edge iterator.
1.503 - template<typename It>
1.504 - static
1.505 - bool valid(const It &i) { return i.valid(); }
1.506 -
1.507 - /// Steps the given node or edge iterator.
1.508 - template<typename It>
1.509 - static
1.510 - It& next(It &e) {
1.511 - if( DM::range_check && !e.valid() )
1.512 - fault("UndirPath::next() on invalid iterator");
1.513 - return ++e;
1.514 - }
1.515 -
1.516 - /// \brief Returns node iterator pointing to the head node of the
1.517 - /// given edge iterator.
1.518 - NodeIt head(const EdgeIt& e) const {
1.519 - if( DM::range_check && !e.valid() )
1.520 - fault("UndirPath::head() on invalid iterator");
1.521 - return NodeIt(*this, e.idx+1);
1.522 - }
1.523 -
1.524 - /// \brief Returns node iterator pointing to the tail node of the
1.525 - /// given edge iterator.
1.526 - NodeIt tail(const EdgeIt& e) const {
1.527 - if( DM::range_check && !e.valid() )
1.528 - fault("UndirPath::tail() on invalid iterator");
1.529 - return NodeIt(*this, e.idx);
1.530 - }
1.531 -
1.532 -
1.533 -
1.534 - /**
1.535 - * \brief Iterator class to iterate on the edges of the paths
1.536 - *
1.537 - * \ingroup paths
1.538 - * This class is used to iterate on the edges of the paths
1.539 - *
1.540 - * Of course it converts to Graph::Edge
1.541 - *
1.542 - * \todo Its interface differs from the standard edge iterator.
1.543 - * Yes, it shouldn't.
1.544 - */
1.545 - class EdgeIt {
1.546 - friend class UndirPath;
1.547 -
1.548 - int idx;
1.549 - const UndirPath *p;
1.550 - public:
1.551 - /// Default constructor
1.552 - EdgeIt() {}
1.553 - /// Invalid constructor
1.554 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.555 - /// Constructor with starting point
1.556 - EdgeIt(const UndirPath &_p, int _idx = 0) :
1.557 - idx(_idx), p(&_p) { validate(); }
1.558 -
1.559 - ///Validity check
1.560 - bool valid() const { return idx!=-1; }
1.561 -
1.562 - ///Conversion to Graph::Edge
1.563 - operator GraphEdge () const {
1.564 - return valid() ? p->edges[idx] : INVALID;
1.565 - }
1.566 - /// Next edge
1.567 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.568 -
1.569 - /// Comparison operator
1.570 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.571 - /// Comparison operator
1.572 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.573 - /// Comparison operator
1.574 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.575 -
1.576 - private:
1.577 - // FIXME: comparison between signed and unsigned...
1.578 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.579 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.580 - };
1.581 -
1.582 - /**
1.583 - * \brief Iterator class to iterate on the nodes of the paths
1.584 - *
1.585 - * \ingroup paths
1.586 - * This class is used to iterate on the nodes of the paths
1.587 - *
1.588 - * Of course it converts to Graph::Node
1.589 - *
1.590 - * \todo Its interface differs from the standard node iterator.
1.591 - * Yes, it shouldn't.
1.592 - */
1.593 - class NodeIt {
1.594 - friend class UndirPath;
1.595 -
1.596 - int idx;
1.597 - const UndirPath *p;
1.598 - public:
1.599 - /// Default constructor
1.600 - NodeIt() {}
1.601 - /// Invalid constructor
1.602 - NodeIt(Invalid) : idx(-1), p(0) {}
1.603 - /// Constructor with starting point
1.604 - NodeIt(const UndirPath &_p, int _idx = 0) :
1.605 - idx(_idx), p(&_p) { validate(); }
1.606 -
1.607 - ///Validity check
1.608 - bool valid() const { return idx!=-1; }
1.609 -
1.610 - ///Conversion to Graph::Node
1.611 - operator const GraphNode& () const {
1.612 - if(idx >= p->length())
1.613 - return p->to();
1.614 - else if(idx >= 0)
1.615 - return p->gr->tail(p->edges[idx]);
1.616 - else
1.617 - return INVALID;
1.618 - }
1.619 - /// Next node
1.620 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.621 -
1.622 - /// Comparison operator
1.623 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.624 - /// Comparison operator
1.625 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.626 - /// Comparison operator
1.627 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.628 -
1.629 - private:
1.630 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.631 - };
1.632 -
1.633 - friend class Builder;
1.634 -
1.635 - /**
1.636 - * \brief Class to build paths
1.637 - *
1.638 - * \ingroup paths
1.639 - * This class is used to fill a path with edges.
1.640 - *
1.641 - * You can push new edges to the front and to the back of the path in
1.642 - * arbitrary order then you should commit these changes to the graph.
1.643 - *
1.644 - * Fundamentally, for most "Paths" (classes fulfilling the
1.645 - * PathConcept) while the builder is active (after the first modifying
1.646 - * operation and until the commit()) the original Path is in a
1.647 - * "transitional" state (operations ot it have undefined result). But
1.648 - * in the case of UndirPath the original path is unchanged until the
1.649 - * commit. However we don't recomend that you use this feature.
1.650 - */
1.651 - class Builder {
1.652 - UndirPath &P;
1.653 - Container front, back;
1.654 -
1.655 - public:
1.656 - ///\param _P the path you want to fill in.
1.657 - ///
1.658 - Builder(UndirPath &_P) : P(_P) {}
1.659 -
1.660 - /// Sets the starting node of the path.
1.661 -
1.662 - /// Sets the starting node of the path. Edge added to the path
1.663 - /// afterwards have to be incident to this node.
1.664 - /// It should be called iff the path is empty and before any call to
1.665 - /// \ref pushFront() or \ref pushBack()
1.666 - void setStart(const GraphNode &) {}
1.667 -
1.668 - ///Push a new edge to the front of the path
1.669 -
1.670 - ///Push a new edge to the front of the path.
1.671 - ///\sa setStart
1.672 - void pushFront(const GraphEdge& e) {
1.673 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.674 - fault("UndirPath::Builder::pushFront: nonincident edge");
1.675 - }
1.676 - front.push_back(e);
1.677 - }
1.678 -
1.679 - ///Push a new edge to the back of the path
1.680 -
1.681 - ///Push a new edge to the back of the path.
1.682 - ///\sa setStart
1.683 - void pushBack(const GraphEdge& e) {
1.684 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.685 - fault("UndirPath::Builder::pushBack: nonincident edge");
1.686 - }
1.687 - back.push_back(e);
1.688 - }
1.689 -
1.690 - ///Commit the changes to the path.
1.691 - void commit() {
1.692 - if( !(front.empty() && back.empty()) ) {
1.693 - Container tmp;
1.694 - tmp.reserve(front.size()+back.size()+P.length());
1.695 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.696 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.697 - tmp.insert(tmp.end(), back.begin(), back.end());
1.698 - P.edges.swap(tmp);
1.699 - front.clear();
1.700 - back.clear();
1.701 - }
1.702 - }
1.703 -
1.704 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.705 - // Hogy kenyelmes egy ilyet hasznalni?
1.706 -
1.707 - ///Reserve storage in advance for the builder
1.708 -
1.709 - ///If you know an reasonable upper bound of the number of the edges
1.710 - ///to add, using this function you can speed up the building.
1.711 - void reserve(size_t r) {
1.712 - front.reserve(r);
1.713 - back.reserve(r);
1.714 - }
1.715 -
1.716 - private:
1.717 - bool empty() {
1.718 - return front.empty() && back.empty() && P.empty();
1.719 - }
1.720 -
1.721 - GraphNode from() const {
1.722 - if( ! front.empty() )
1.723 - return P.gr->tail(front[front.size()-1]);
1.724 - else if( ! P.empty() )
1.725 - return P.gr->tail(P.edges[0]);
1.726 - else if( ! back.empty() )
1.727 - return P.gr->tail(back[0]);
1.728 - else
1.729 - return INVALID;
1.730 - }
1.731 - GraphNode to() const {
1.732 - if( ! back.empty() )
1.733 - return P.gr->head(back[back.size()-1]);
1.734 - else if( ! P.empty() )
1.735 - return P.gr->head(P.edges[P.length()-1]);
1.736 - else if( ! front.empty() )
1.737 - return P.gr->head(front[0]);
1.738 - else
1.739 - return INVALID;
1.740 - }
1.741 -
1.742 - };
1.743 -
1.744 - };
1.745 -
1.746 -
1.747 - ///@}
1.748 -
1.749 -} // namespace hugo
1.750 -
1.751 -#endif // HUGO_PATH_H
2.1 --- a/src/work/klao/path.h Tue Jun 15 06:30:03 2004 +0000
2.2 +++ b/src/work/klao/path.h Wed Jun 16 09:44:30 2004 +0000
2.3 @@ -1,6 +1,20 @@
2.4 // -*- c++ -*- //
2.5
2.6 -///\ingroup datas
2.7 +/**
2.8 +@defgroup paths Path Structures
2.9 +@ingroup datas
2.10 +\brief Path structures implemented in Hugo.
2.11 +
2.12 +Hugolib provides flexible data structures
2.13 +to work with paths.
2.14 +
2.15 +All of them have the same interface, especially they can be built or extended
2.16 +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
2.17 +algorithm to store its result in any kind of path structure.
2.18 +
2.19 +*/
2.20 +
2.21 +///\ingroup paths
2.22 ///\file
2.23 ///\brief Classes for representing paths in graphs.
2.24
2.25 @@ -17,7 +31,7 @@
2.26
2.27 namespace hugo {
2.28
2.29 - /// \addtogroup datas
2.30 + /// \addtogroup paths
2.31 /// @{
2.32
2.33
2.34 @@ -35,7 +49,9 @@
2.35 template<typename Graph, typename DM = DefaultDebugMode>
2.36 class DirPath {
2.37 public:
2.38 - typedef typename Graph::Edge GraphEdge;
2.39 + /// Edge type of the underlying graph.
2.40 + typedef typename Graph::Edge GraphEdge;
2.41 + /// Node type of the underlying graph.
2.42 typedef typename Graph::Node GraphNode;
2.43 class NodeIt;
2.44 class EdgeIt;
2.45 @@ -152,27 +168,49 @@
2.46 }
2.47
2.48
2.49 - /*** Iterator classes ***/
2.50 + /* Iterator classes */
2.51 +
2.52 + /**
2.53 + * \brief Iterator class to iterate on the edges of the paths
2.54 + *
2.55 + * \ingroup paths
2.56 + * This class is used to iterate on the edges of the paths
2.57 + *
2.58 + * Of course it converts to Graph::Edge
2.59 + *
2.60 + * \todo Its interface differs from the standard edge iterator.
2.61 + * Yes, it shouldn't.
2.62 + */
2.63 class EdgeIt {
2.64 friend class DirPath;
2.65
2.66 int idx;
2.67 const DirPath *p;
2.68 public:
2.69 + /// Default constructor
2.70 EdgeIt() {}
2.71 + /// Invalid constructor
2.72 EdgeIt(Invalid) : idx(-1), p(0) {}
2.73 + /// Constructor with starting point
2.74 EdgeIt(const DirPath &_p, int _idx = 0) :
2.75 idx(_idx), p(&_p) { validate(); }
2.76
2.77 + ///Validity check
2.78 bool valid() const { return idx!=-1; }
2.79
2.80 + ///Conversion to Graph::Edge
2.81 operator GraphEdge () const {
2.82 return valid() ? p->edges[idx] : INVALID;
2.83 }
2.84 +
2.85 + /// Next edge
2.86 EdgeIt& operator++() { ++idx; validate(); return *this; }
2.87
2.88 + /// Comparison operator
2.89 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.90 + /// Comparison operator
2.91 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.92 + /// Comparison operator
2.93 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.94
2.95 private:
2.96 @@ -181,19 +219,35 @@
2.97 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.98 };
2.99
2.100 + /**
2.101 + * \brief Iterator class to iterate on the nodes of the paths
2.102 + *
2.103 + * \ingroup paths
2.104 + * This class is used to iterate on the nodes of the paths
2.105 + *
2.106 + * Of course it converts to Graph::Node
2.107 + *
2.108 + * \todo Its interface differs from the standard node iterator.
2.109 + * Yes, it shouldn't.
2.110 + */
2.111 class NodeIt {
2.112 friend class DirPath;
2.113
2.114 int idx;
2.115 const DirPath *p;
2.116 public:
2.117 + /// Default constructor
2.118 NodeIt() {}
2.119 + /// Invalid constructor
2.120 NodeIt(Invalid) : idx(-1), p(0) {}
2.121 + /// Constructor with starting point
2.122 NodeIt(const DirPath &_p, int _idx = 0) :
2.123 idx(_idx), p(&_p) { validate(); }
2.124
2.125 + ///Validity check
2.126 bool valid() const { return idx!=-1; }
2.127
2.128 + ///Conversion to Graph::Node
2.129 operator const GraphNode& () const {
2.130 if(idx >= p->length())
2.131 return p->to();
2.132 @@ -202,10 +256,14 @@
2.133 else
2.134 return INVALID;
2.135 }
2.136 + /// Next node
2.137 NodeIt& operator++() { ++idx; validate(); return *this; }
2.138
2.139 + /// Comparison operator
2.140 bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.141 + /// Comparison operator
2.142 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.143 + /// Comparison operator
2.144 bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.145
2.146 private:
2.147 @@ -217,7 +275,7 @@
2.148 /**
2.149 * \brief Class to build paths
2.150 *
2.151 - * \ingroup datas
2.152 + * \ingroup paths
2.153 * This class is used to fill a path with edges.
2.154 *
2.155 * You can push new edges to the front and to the back of the path in
2.156 @@ -285,6 +343,11 @@
2.157
2.158 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.159 // Hogy kenyelmes egy ilyet hasznalni?
2.160 +
2.161 + ///Reserve storage in advance for the builder
2.162 +
2.163 + ///If you know an reasonable upper bound of the number of the edges
2.164 + ///to add, using this function you can speed up the building.
2.165 void reserve(size_t r) {
2.166 front.reserve(r);
2.167 back.reserve(r);
2.168 @@ -349,8 +412,10 @@
2.169 template<typename Graph, typename DM = DefaultDebugMode>
2.170 class UndirPath {
2.171 public:
2.172 + /// Edge type of the underlying graph.
2.173 typedef typename Graph::Edge GraphEdge;
2.174 - typedef typename Graph::Node GraphNode;
2.175 + /// Node type of the underlying graph.
2.176 + typedef typename Graph::Node GraphNode;
2.177 class NodeIt;
2.178 class EdgeIt;
2.179
2.180 @@ -466,27 +531,47 @@
2.181 }
2.182
2.183
2.184 - /*** Iterator classes ***/
2.185 +
2.186 + /**
2.187 + * \brief Iterator class to iterate on the edges of the paths
2.188 + *
2.189 + * \ingroup paths
2.190 + * This class is used to iterate on the edges of the paths
2.191 + *
2.192 + * Of course it converts to Graph::Edge
2.193 + *
2.194 + * \todo Its interface differs from the standard edge iterator.
2.195 + * Yes, it shouldn't.
2.196 + */
2.197 class EdgeIt {
2.198 friend class UndirPath;
2.199
2.200 int idx;
2.201 const UndirPath *p;
2.202 public:
2.203 + /// Default constructor
2.204 EdgeIt() {}
2.205 + /// Invalid constructor
2.206 EdgeIt(Invalid) : idx(-1), p(0) {}
2.207 + /// Constructor with starting point
2.208 EdgeIt(const UndirPath &_p, int _idx = 0) :
2.209 idx(_idx), p(&_p) { validate(); }
2.210
2.211 + ///Validity check
2.212 bool valid() const { return idx!=-1; }
2.213
2.214 + ///Conversion to Graph::Edge
2.215 operator GraphEdge () const {
2.216 return valid() ? p->edges[idx] : INVALID;
2.217 }
2.218 - EdgeIt& operator++() { ++idx; validate(); return *this; }
2.219 + /// Next edge
2.220 + EdgeIt& operator++() { ++idx; validate(); return *this; }
2.221
2.222 + /// Comparison operator
2.223 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.224 + /// Comparison operator
2.225 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.226 + /// Comparison operator
2.227 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.228
2.229 private:
2.230 @@ -495,19 +580,35 @@
2.231 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.232 };
2.233
2.234 + /**
2.235 + * \brief Iterator class to iterate on the nodes of the paths
2.236 + *
2.237 + * \ingroup paths
2.238 + * This class is used to iterate on the nodes of the paths
2.239 + *
2.240 + * Of course it converts to Graph::Node
2.241 + *
2.242 + * \todo Its interface differs from the standard node iterator.
2.243 + * Yes, it shouldn't.
2.244 + */
2.245 class NodeIt {
2.246 friend class UndirPath;
2.247
2.248 int idx;
2.249 const UndirPath *p;
2.250 public:
2.251 + /// Default constructor
2.252 NodeIt() {}
2.253 + /// Invalid constructor
2.254 NodeIt(Invalid) : idx(-1), p(0) {}
2.255 + /// Constructor with starting point
2.256 NodeIt(const UndirPath &_p, int _idx = 0) :
2.257 idx(_idx), p(&_p) { validate(); }
2.258
2.259 + ///Validity check
2.260 bool valid() const { return idx!=-1; }
2.261
2.262 + ///Conversion to Graph::Node
2.263 operator const GraphNode& () const {
2.264 if(idx >= p->length())
2.265 return p->to();
2.266 @@ -516,11 +617,15 @@
2.267 else
2.268 return INVALID;
2.269 }
2.270 + /// Next node
2.271 NodeIt& operator++() { ++idx; validate(); return *this; }
2.272
2.273 + /// Comparison operator
2.274 bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.275 + /// Comparison operator
2.276 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.277 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.278 + /// Comparison operator
2.279 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.280
2.281 private:
2.282 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
2.283 @@ -531,7 +636,7 @@
2.284 /**
2.285 * \brief Class to build paths
2.286 *
2.287 - * \ingroup datas
2.288 + * \ingroup paths
2.289 * This class is used to fill a path with edges.
2.290 *
2.291 * You can push new edges to the front and to the back of the path in
2.292 @@ -599,7 +704,12 @@
2.293
2.294 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.295 // Hogy kenyelmes egy ilyet hasznalni?
2.296 - void reserve(size_t r) {
2.297 +
2.298 + ///Reserve storage in advance for the builder
2.299 +
2.300 + ///If you know an reasonable upper bound of the number of the edges
2.301 + ///to add, using this function you can speed up the building.
2.302 + void reserve(size_t r) {
2.303 front.reserve(r);
2.304 back.reserve(r);
2.305 }