1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/peter/path/comments Tue Sep 07 13:55:35 2004 +0000
1.3 @@ -0,0 +1,11 @@
1.4 +path_test
1.5 + 124. sorban ki van szedve a "e<<", mert nem foditotta a cucli
1.6 + 9. sorba kell a skeleton namespace, ha a skeletonnal akarjuk forditani, kulonben nem
1.7 + 154. sor: a skeletonban nincsen nth. whattodo?
1.8 +
1.9 +path_skeleton
1.10 + 31. sorabol ki van szedve egy typename!!
1.11 + 169. sorba beraktam egy Path ojjektumot, mert ott azt valakinek parameterkent kell kapnia
1.12 + masik lehetoseg lett volna, hogy kiszedem ott azt abbol a fuggveny fej utani torzs elotti reszbol
1.13 + 56. es 61. sorban a head es a tail eljarasok gondolom a from es a to eredeti eljarast kivanjak helyettesiteni
1.14 + de azok Node-ot adtak vissza, nem pedig iteratort, ezert azt atirtam.
1.15 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/peter/path/debug.h Tue Sep 07 13:55:35 2004 +0000
2.3 @@ -0,0 +1,56 @@
2.4 +// -*- C++ -*- //
2.5 +
2.6 +#ifndef HUGO_DEBUG_H
2.7 +#define HUGO_DEBUG_H
2.8 +
2.9 +//! \file
2.10 +//! \brief Basic definitions for debug control.
2.11 +
2.12 +namespace hugo {
2.13 +
2.14 + //! Debug mode for testing/debugging
2.15 +
2.16 + //! Use this debug mode if you want exhaustive range and consistency checks.
2.17 + //! It also produces verbose debug messages.
2.18 + struct DebugOn {
2.19 + //! Example: check whether the edges added to a path are adjacent
2.20 + static const bool consistensy_check = true;
2.21 +
2.22 + static const bool range_check = true;
2.23 +
2.24 + //! Examples: initialize maps with some value;
2.25 + //! after deleting an item from UnionFindEnum set its value in the
2.26 + //! corresponding map to NULL...
2.27 + static const bool ensure_safe_state = true;
2.28 +
2.29 + static const int verbose = 5;
2.30 + };
2.31 +
2.32 + //! Debug mode for turning off debug aids.
2.33 +
2.34 + //! This debud mode switches off all range and consistency checks,
2.35 + //! as well as the debug messages.
2.36 + //!
2.37 + struct DebugOff {
2.38 + static const bool consistensy_check = false;
2.39 + static const bool range_check = false;
2.40 + static const bool ensure_safe_state = false;
2.41 + static const int verbose = 0;
2.42 + };
2.43 +
2.44 +#ifdef DEBUG
2.45 + //! The default debug mode.
2.46 +
2.47 + //! The default debug mode.
2.48 + //!
2.49 + typedef DebugOn DefaultDebugMode;
2.50 +#else
2.51 + //! The default debug mode.
2.52 +
2.53 + //! The default debug mode.
2.54 + //!
2.55 + typedef DebugOff DefaultDebugMode;
2.56 +#endif
2.57 +
2.58 +}
2.59 +#endif // HUGO_DEBUG_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/peter/path/path.h Tue Sep 07 13:55:35 2004 +0000
3.3 @@ -0,0 +1,1174 @@
3.4 +// -*- c++ -*- //
3.5 +
3.6 +/**
3.7 +@defgroup paths Path Structures
3.8 +@ingroup datas
3.9 +\brief Path structures implemented in Hugo.
3.10 +
3.11 +Hugolib provides flexible data structures
3.12 +to work with paths.
3.13 +
3.14 +All of them have the same interface, especially they can be built or extended
3.15 +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
3.16 +algorithm to store its result in any kind of path structure.
3.17 +
3.18 +\sa hugo::skeleton::Path
3.19 +
3.20 +*/
3.21 +
3.22 +///\ingroup paths
3.23 +///\file
3.24 +///\brief Classes for representing paths in graphs.
3.25 +
3.26 +#ifndef HUGO_PATH_H
3.27 +#define HUGO_PATH_H
3.28 +
3.29 +#include <deque>
3.30 +#include <vector>
3.31 +#include <algorithm>
3.32 +
3.33 +#include <hugo/invalid.h>
3.34 +#include <hugo/error.h>
3.35 +#include <debug.h>
3.36 +
3.37 +namespace hugo {
3.38 +
3.39 + /// \addtogroup paths
3.40 + /// @{
3.41 +
3.42 +
3.43 + //! \brief A structure for representing directed paths in a graph.
3.44 + //!
3.45 + //! A structure for representing directed path in a graph.
3.46 + //! \param Graph The graph type in which the path is.
3.47 + //! \param DM DebugMode, defaults to DefaultDebugMode.
3.48 + //!
3.49 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
3.50 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
3.51 + //! and \c Edge of the original graph.
3.52 + //!
3.53 + //! \todo Thoroughfully check all the range and consistency tests.
3.54 + template<typename Graph, typename DM = DefaultDebugMode>
3.55 + class DirPath {
3.56 + public:
3.57 + /// Edge type of the underlying graph.
3.58 + typedef typename Graph::Edge GraphEdge;
3.59 + /// Node type of the underlying graph.
3.60 + typedef typename Graph::Node GraphNode;
3.61 + class NodeIt;
3.62 + class EdgeIt;
3.63 +
3.64 + protected:
3.65 + const Graph *gr;
3.66 + typedef std::vector<GraphEdge> Container;
3.67 + Container edges;
3.68 +
3.69 + public:
3.70 +
3.71 + /// \param _G The graph in which the path is.
3.72 + ///
3.73 + DirPath(const Graph &_G) : gr(&_G) {}
3.74 +
3.75 + /// \brief Subpath constructor.
3.76 + ///
3.77 + /// Subpath defined by two nodes.
3.78 + /// \warning It is an error if the two edges are not in order!
3.79 + DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
3.80 + if( DM::range_check && (!a.valid() || !b.valid) ) {
3.81 + // FIXME: this check should be more elaborate...
3.82 + fault("DirPath, subpath ctor: invalid bounding nodes");
3.83 + }
3.84 + gr = P.gr;
3.85 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
3.86 + }
3.87 +
3.88 + /// \brief Subpath constructor.
3.89 + ///
3.90 + /// Subpath defined by two edges. Contains edges in [a,b)
3.91 + /// \warning It is an error if the two edges are not in order!
3.92 + DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
3.93 + if( DM::range_check && (!a.valid() || !b.valid) ) {
3.94 + // FIXME: this check should be more elaborate...
3.95 + fault("DirPath, subpath ctor: invalid bounding nodes");
3.96 + }
3.97 + gr = P.gr;
3.98 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
3.99 + }
3.100 +
3.101 + /// Length of the path.
3.102 + size_t length() const { return edges.size(); }
3.103 + /// Returns whether the path is empty.
3.104 + bool empty() const { return edges.empty(); }
3.105 +
3.106 + /// Resets the path to an empty path.
3.107 + void clear() { edges.clear(); }
3.108 +
3.109 + /// \brief Starting point of the path.
3.110 + ///
3.111 + /// Starting point of the path.
3.112 + /// Returns INVALID if the path is empty.
3.113 + GraphNode from() const {
3.114 + return empty() ? INVALID : gr->tail(edges[0]);
3.115 + }
3.116 + /// \brief End point of the path.
3.117 + ///
3.118 + /// End point of the path.
3.119 + /// Returns INVALID if the path is empty.
3.120 + GraphNode to() const {
3.121 + return empty() ? INVALID : gr->head(edges[length()-1]);
3.122 + }
3.123 +
3.124 + /// \brief Initializes node or edge iterator to point to the first
3.125 + /// node or edge.
3.126 + ///
3.127 + /// \sa nth
3.128 + template<typename It>
3.129 + It& first(It &i) const { return i=It(*this); }
3.130 +
3.131 + /// \brief Initializes node iterator to point to the node of a given index.
3.132 + NodeIt& nth(NodeIt &i, int n) const {
3.133 + if( DM::range_check && (n<0 || n>int(length())) )
3.134 + fault("DirPath::nth: index out of range");
3.135 + return i=NodeIt(*this, n);
3.136 + }
3.137 +
3.138 + /// \brief Initializes edge iterator to point to the edge of a given index.
3.139 + EdgeIt& nth(EdgeIt &i, int n) const {
3.140 + if( DM::range_check && (n<0 || n>=int(length())) )
3.141 + fault("DirPath::nth: index out of range");
3.142 + return i=EdgeIt(*this, n);
3.143 + }
3.144 +
3.145 + /// Checks validity of a node or edge iterator.
3.146 + template<typename It>
3.147 + static
3.148 + bool valid(const It &i) { return i.valid(); }
3.149 +
3.150 + /// Steps the given node or edge iterator.
3.151 + template<typename It>
3.152 + static
3.153 + It& next(It &e) {
3.154 + if( DM::range_check && !e.valid() )
3.155 + fault("DirPath::next() on invalid iterator");
3.156 + return ++e;
3.157 + }
3.158 +
3.159 + /// \brief Returns node iterator pointing to the head node of the
3.160 + /// given edge iterator.
3.161 + NodeIt head(const EdgeIt& e) const {
3.162 + if( DM::range_check && !e.valid() )
3.163 + fault("DirPath::head() on invalid iterator");
3.164 + return NodeIt(*this, e.idx+1);
3.165 + }
3.166 +
3.167 + /// \brief Returns node iterator pointing to the tail node of the
3.168 + /// given edge iterator.
3.169 + NodeIt tail(const EdgeIt& e) const {
3.170 + if( DM::range_check && !e.valid() )
3.171 + fault("DirPath::tail() on invalid iterator");
3.172 + return NodeIt(*this, e.idx);
3.173 + }
3.174 +
3.175 +
3.176 + /* Iterator classes */
3.177 +
3.178 + /**
3.179 + * \brief Iterator class to iterate on the edges of the paths
3.180 + *
3.181 + * \ingroup paths
3.182 + * This class is used to iterate on the edges of the paths
3.183 + *
3.184 + * Of course it converts to Graph::Edge
3.185 + *
3.186 + * \todo Its interface differs from the standard edge iterator.
3.187 + * Yes, it shouldn't.
3.188 + */
3.189 + class EdgeIt {
3.190 + friend class DirPath;
3.191 +
3.192 + int idx;
3.193 + const DirPath *p;
3.194 + public:
3.195 + /// Default constructor
3.196 + EdgeIt() {}
3.197 + /// Invalid constructor
3.198 + EdgeIt(Invalid) : idx(-1), p(0) {}
3.199 + /// Constructor with starting point
3.200 + EdgeIt(const DirPath &_p, int _idx = 0) :
3.201 + idx(_idx), p(&_p) { validate(); }
3.202 +
3.203 + ///Validity check
3.204 + bool valid() const { return idx!=-1; }
3.205 +
3.206 + ///Conversion to Graph::Edge
3.207 + operator GraphEdge () const {
3.208 + return valid() ? p->edges[idx] : INVALID;
3.209 + }
3.210 +
3.211 + /// Next edge
3.212 + EdgeIt& operator++() { ++idx; validate(); return *this; }
3.213 +
3.214 + /// Comparison operator
3.215 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
3.216 + /// Comparison operator
3.217 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
3.218 + /// Comparison operator
3.219 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
3.220 +
3.221 + private:
3.222 + // FIXME: comparison between signed and unsigned...
3.223 + // Jo ez igy? Vagy esetleg legyen a length() int?
3.224 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
3.225 + };
3.226 +
3.227 + /**
3.228 + * \brief Iterator class to iterate on the nodes of the paths
3.229 + *
3.230 + * \ingroup paths
3.231 + * This class is used to iterate on the nodes of the paths
3.232 + *
3.233 + * Of course it converts to Graph::Node
3.234 + *
3.235 + * \todo Its interface differs from the standard node iterator.
3.236 + * Yes, it shouldn't.
3.237 + */
3.238 + class NodeIt {
3.239 + friend class DirPath;
3.240 +
3.241 + int idx;
3.242 + const DirPath *p;
3.243 + public:
3.244 + /// Default constructor
3.245 + NodeIt() {}
3.246 + /// Invalid constructor
3.247 + NodeIt(Invalid) : idx(-1), p(0) {}
3.248 + /// Constructor with starting point
3.249 + NodeIt(const DirPath &_p, int _idx = 0) :
3.250 + idx(_idx), p(&_p) { validate(); }
3.251 +
3.252 + ///Validity check
3.253 + bool valid() const { return idx!=-1; }
3.254 +
3.255 + ///Conversion to Graph::Node
3.256 + operator const GraphNode& () const {
3.257 + if(idx >= p->length())
3.258 + return p->to();
3.259 + else if(idx >= 0)
3.260 + return p->gr->tail(p->edges[idx]);
3.261 + else
3.262 + return INVALID;
3.263 + }
3.264 + /// Next node
3.265 + NodeIt& operator++() { ++idx; validate(); return *this; }
3.266 +
3.267 + /// Comparison operator
3.268 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
3.269 + /// Comparison operator
3.270 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
3.271 + /// Comparison operator
3.272 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
3.273 +
3.274 + private:
3.275 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
3.276 + };
3.277 +
3.278 + friend class Builder;
3.279 +
3.280 + /**
3.281 + * \brief Class to build paths
3.282 + *
3.283 + * \ingroup paths
3.284 + * This class is used to fill a path with edges.
3.285 + *
3.286 + * You can push new edges to the front and to the back of the path in
3.287 + * arbitrary order then you should commit these changes to the graph.
3.288 + *
3.289 + * Fundamentally, for most "Paths" (classes fulfilling the
3.290 + * PathConcept) while the builder is active (after the first modifying
3.291 + * operation and until the commit()) the original Path is in a
3.292 + * "transitional" state (operations on it have undefined result). But
3.293 + * in the case of DirPath the original path remains unchanged until the
3.294 + * commit. However we don't recomend that you use this feature.
3.295 + */
3.296 + class Builder {
3.297 + DirPath &P;
3.298 + Container front, back;
3.299 +
3.300 + public:
3.301 + ///\param _P the path you want to fill in.
3.302 + ///
3.303 + Builder(DirPath &_P) : P(_P) {}
3.304 +
3.305 + /// Sets the starting node of the path.
3.306 +
3.307 + /// Sets the starting node of the path. Edge added to the path
3.308 + /// afterwards have to be incident to this node.
3.309 + /// It should be called iff the path is empty and before any call to
3.310 + /// \ref pushFront() or \ref pushBack()
3.311 + void setStartNode(const GraphNode &) {}
3.312 +
3.313 + ///Push a new edge to the front of the path
3.314 +
3.315 + ///Push a new edge to the front of the path.
3.316 + ///\sa setStartNode
3.317 + void pushFront(const GraphEdge& e) {
3.318 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
3.319 + fault("DirPath::Builder::pushFront: nonincident edge");
3.320 + }
3.321 + front.push_back(e);
3.322 + }
3.323 +
3.324 + ///Push a new edge to the back of the path
3.325 +
3.326 + ///Push a new edge to the back of the path.
3.327 + ///\sa setStartNode
3.328 + void pushBack(const GraphEdge& e) {
3.329 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
3.330 + fault("DirPath::Builder::pushBack: nonincident edge");
3.331 + }
3.332 + back.push_back(e);
3.333 + }
3.334 +
3.335 + ///Commit the changes to the path.
3.336 + void commit() {
3.337 + if( !(front.empty() && back.empty()) ) {
3.338 + Container tmp;
3.339 + tmp.reserve(front.size()+back.size()+P.length());
3.340 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
3.341 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
3.342 + tmp.insert(tmp.end(), back.begin(), back.end());
3.343 + P.edges.swap(tmp);
3.344 + front.clear();
3.345 + back.clear();
3.346 + }
3.347 + }
3.348 +
3.349 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
3.350 + // Hogy kenyelmes egy ilyet hasznalni?
3.351 +
3.352 + ///Reserve storage for the builder in advance.
3.353 +
3.354 + ///If you know an reasonable upper bound of the number of the edges
3.355 + ///to add, using this function you can speed up the building.
3.356 + void reserve(size_t r) {
3.357 + front.reserve(r);
3.358 + back.reserve(r);
3.359 + }
3.360 +
3.361 + private:
3.362 + bool empty() {
3.363 + return front.empty() && back.empty() && P.empty();
3.364 + }
3.365 +
3.366 + GraphNode from() const {
3.367 + if( ! front.empty() )
3.368 + return P.gr->tail(front[front.size()-1]);
3.369 + else if( ! P.empty() )
3.370 + return P.gr->tail(P.edges[0]);
3.371 + else if( ! back.empty() )
3.372 + return P.gr->tail(back[0]);
3.373 + else
3.374 + return INVALID;
3.375 + }
3.376 + GraphNode to() const {
3.377 + if( ! back.empty() )
3.378 + return P.gr->head(back[back.size()-1]);
3.379 + else if( ! P.empty() )
3.380 + return P.gr->head(P.edges[P.length()-1]);
3.381 + else if( ! front.empty() )
3.382 + return P.gr->head(front[0]);
3.383 + else
3.384 + return INVALID;
3.385 + }
3.386 +
3.387 + };
3.388 +
3.389 + };
3.390 +
3.391 +
3.392 +
3.393 +
3.394 +
3.395 +
3.396 +
3.397 +
3.398 +
3.399 +
3.400 + /**********************************************************************/
3.401 +
3.402 +
3.403 + //! \brief A structure for representing undirected path in a graph.
3.404 + //!
3.405 + //! A structure for representing undirected path in a graph. Ie. this is
3.406 + //! a path in a \e directed graph but the edges should not be directed
3.407 + //! forward.
3.408 + //!
3.409 + //! \param Graph The graph type in which the path is.
3.410 + //! \param DM DebugMode, defaults to DefaultDebugMode.
3.411 + //!
3.412 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
3.413 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
3.414 + //! and \c Edge of the original graph.
3.415 + //!
3.416 + //! \todo Thoroughfully check all the range and consistency tests.
3.417 + template<typename Graph, typename DM = DefaultDebugMode>
3.418 + class UndirPath {
3.419 + public:
3.420 + /// Edge type of the underlying graph.
3.421 + typedef typename Graph::Edge GraphEdge;
3.422 + /// Node type of the underlying graph.
3.423 + typedef typename Graph::Node GraphNode;
3.424 + class NodeIt;
3.425 + class EdgeIt;
3.426 +
3.427 + protected:
3.428 + const Graph *gr;
3.429 + typedef std::vector<GraphEdge> Container;
3.430 + Container edges;
3.431 +
3.432 + public:
3.433 +
3.434 + /// \param _G The graph in which the path is.
3.435 + ///
3.436 + UndirPath(const Graph &_G) : gr(&_G) {}
3.437 +
3.438 + /// \brief Subpath constructor.
3.439 + ///
3.440 + /// Subpath defined by two nodes.
3.441 + /// \warning It is an error if the two edges are not in order!
3.442 + UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
3.443 + if( DM::range_check && (!a.valid() || !b.valid) ) {
3.444 + // FIXME: this check should be more elaborate...
3.445 + fault("UndirPath, subpath ctor: invalid bounding nodes");
3.446 + }
3.447 + gr = P.gr;
3.448 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
3.449 + }
3.450 +
3.451 + /// \brief Subpath constructor.
3.452 + ///
3.453 + /// Subpath defined by two edges. Contains edges in [a,b)
3.454 + /// \warning It is an error if the two edges are not in order!
3.455 + UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
3.456 + if( DM::range_check && (!a.valid() || !b.valid) ) {
3.457 + // FIXME: this check should be more elaborate...
3.458 + fault("UndirPath, subpath ctor: invalid bounding nodes");
3.459 + }
3.460 + gr = P.gr;
3.461 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
3.462 + }
3.463 +
3.464 + /// Length of the path.
3.465 + size_t length() const { return edges.size(); }
3.466 + /// Returns whether the path is empty.
3.467 + bool empty() const { return edges.empty(); }
3.468 +
3.469 + /// Resets the path to an empty path.
3.470 + void clear() { edges.clear(); }
3.471 +
3.472 + /// \brief Starting point of the path.
3.473 + ///
3.474 + /// Starting point of the path.
3.475 + /// Returns INVALID if the path is empty.
3.476 + GraphNode from() const {
3.477 + return empty() ? INVALID : gr->tail(edges[0]);
3.478 + }
3.479 + /// \brief End point of the path.
3.480 + ///
3.481 + /// End point of the path.
3.482 + /// Returns INVALID if the path is empty.
3.483 + GraphNode to() const {
3.484 + return empty() ? INVALID : gr->head(edges[length()-1]);
3.485 + }
3.486 +
3.487 + /// \brief Initializes node or edge iterator to point to the first
3.488 + /// node or edge.
3.489 + ///
3.490 + /// \sa nth
3.491 + template<typename It>
3.492 + It& first(It &i) const { return i=It(*this); }
3.493 +
3.494 + /// \brief Initializes node iterator to point to the node of a given index.
3.495 + NodeIt& nth(NodeIt &i, int n) const {
3.496 + if( DM::range_check && (n<0 || n>int(length())) )
3.497 + fault("UndirPath::nth: index out of range");
3.498 + return i=NodeIt(*this, n);
3.499 + }
3.500 +
3.501 + /// \brief Initializes edge iterator to point to the edge of a given index.
3.502 + EdgeIt& nth(EdgeIt &i, int n) const {
3.503 + if( DM::range_check && (n<0 || n>=int(length())) )
3.504 + fault("UndirPath::nth: index out of range");
3.505 + return i=EdgeIt(*this, n);
3.506 + }
3.507 +
3.508 + /// Checks validity of a node or edge iterator.
3.509 + template<typename It>
3.510 + static
3.511 + bool valid(const It &i) { return i.valid(); }
3.512 +
3.513 + /// Steps the given node or edge iterator.
3.514 + template<typename It>
3.515 + static
3.516 + It& next(It &e) {
3.517 + if( DM::range_check && !e.valid() )
3.518 + fault("UndirPath::next() on invalid iterator");
3.519 + return ++e;
3.520 + }
3.521 +
3.522 + /// \brief Returns node iterator pointing to the head node of the
3.523 + /// given edge iterator.
3.524 + NodeIt head(const EdgeIt& e) const {
3.525 + if( DM::range_check && !e.valid() )
3.526 + fault("UndirPath::head() on invalid iterator");
3.527 + return NodeIt(*this, e.idx+1);
3.528 + }
3.529 +
3.530 + /// \brief Returns node iterator pointing to the tail node of the
3.531 + /// given edge iterator.
3.532 + NodeIt tail(const EdgeIt& e) const {
3.533 + if( DM::range_check && !e.valid() )
3.534 + fault("UndirPath::tail() on invalid iterator");
3.535 + return NodeIt(*this, e.idx);
3.536 + }
3.537 +
3.538 +
3.539 +
3.540 + /**
3.541 + * \brief Iterator class to iterate on the edges of the paths
3.542 + *
3.543 + * \ingroup paths
3.544 + * This class is used to iterate on the edges of the paths
3.545 + *
3.546 + * Of course it converts to Graph::Edge
3.547 + *
3.548 + * \todo Its interface differs from the standard edge iterator.
3.549 + * Yes, it shouldn't.
3.550 + */
3.551 + class EdgeIt {
3.552 + friend class UndirPath;
3.553 +
3.554 + int idx;
3.555 + const UndirPath *p;
3.556 + public:
3.557 + /// Default constructor
3.558 + EdgeIt() {}
3.559 + /// Invalid constructor
3.560 + EdgeIt(Invalid) : idx(-1), p(0) {}
3.561 + /// Constructor with starting point
3.562 + EdgeIt(const UndirPath &_p, int _idx = 0) :
3.563 + idx(_idx), p(&_p) { validate(); }
3.564 +
3.565 + ///Validity check
3.566 + bool valid() const { return idx!=-1; }
3.567 +
3.568 + ///Conversion to Graph::Edge
3.569 + operator GraphEdge () const {
3.570 + return valid() ? p->edges[idx] : INVALID;
3.571 + }
3.572 + /// Next edge
3.573 + EdgeIt& operator++() { ++idx; validate(); return *this; }
3.574 +
3.575 + /// Comparison operator
3.576 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
3.577 + /// Comparison operator
3.578 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
3.579 + /// Comparison operator
3.580 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
3.581 +
3.582 + private:
3.583 + // FIXME: comparison between signed and unsigned...
3.584 + // Jo ez igy? Vagy esetleg legyen a length() int?
3.585 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
3.586 + };
3.587 +
3.588 + /**
3.589 + * \brief Iterator class to iterate on the nodes of the paths
3.590 + *
3.591 + * \ingroup paths
3.592 + * This class is used to iterate on the nodes of the paths
3.593 + *
3.594 + * Of course it converts to Graph::Node
3.595 + *
3.596 + * \todo Its interface differs from the standard node iterator.
3.597 + * Yes, it shouldn't.
3.598 + */
3.599 + class NodeIt {
3.600 + friend class UndirPath;
3.601 +
3.602 + int idx;
3.603 + const UndirPath *p;
3.604 + public:
3.605 + /// Default constructor
3.606 + NodeIt() {}
3.607 + /// Invalid constructor
3.608 + NodeIt(Invalid) : idx(-1), p(0) {}
3.609 + /// Constructor with starting point
3.610 + NodeIt(const UndirPath &_p, int _idx = 0) :
3.611 + idx(_idx), p(&_p) { validate(); }
3.612 +
3.613 + ///Validity check
3.614 + bool valid() const { return idx!=-1; }
3.615 +
3.616 + ///Conversion to Graph::Node
3.617 + operator const GraphNode& () const {
3.618 + if(idx >= p->length())
3.619 + return p->to();
3.620 + else if(idx >= 0)
3.621 + return p->gr->tail(p->edges[idx]);
3.622 + else
3.623 + return INVALID;
3.624 + }
3.625 + /// Next node
3.626 + NodeIt& operator++() { ++idx; validate(); return *this; }
3.627 +
3.628 + /// Comparison operator
3.629 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
3.630 + /// Comparison operator
3.631 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
3.632 + /// Comparison operator
3.633 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
3.634 +
3.635 + private:
3.636 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
3.637 + };
3.638 +
3.639 + friend class Builder;
3.640 +
3.641 + /**
3.642 + * \brief Class to build paths
3.643 + *
3.644 + * \ingroup paths
3.645 + * This class is used to fill a path with edges.
3.646 + *
3.647 + * You can push new edges to the front and to the back of the path in
3.648 + * arbitrary order then you should commit these changes to the graph.
3.649 + *
3.650 + * Fundamentally, for most "Paths" (classes fulfilling the
3.651 + * PathConcept) while the builder is active (after the first modifying
3.652 + * operation and until the commit()) the original Path is in a
3.653 + * "transitional" state (operations ot it have undefined result). But
3.654 + * in the case of UndirPath the original path is unchanged until the
3.655 + * commit. However we don't recomend that you use this feature.
3.656 + */
3.657 + class Builder {
3.658 + UndirPath &P;
3.659 + Container front, back;
3.660 +
3.661 + public:
3.662 + ///\param _P the path you want to fill in.
3.663 + ///
3.664 + Builder(UndirPath &_P) : P(_P) {}
3.665 +
3.666 + /// Sets the starting node of the path.
3.667 +
3.668 + /// Sets the starting node of the path. Edge added to the path
3.669 + /// afterwards have to be incident to this node.
3.670 + /// It should be called iff the path is empty and before any call to
3.671 + /// \ref pushFront() or \ref pushBack()
3.672 + void setStartNode(const GraphNode &) {}
3.673 +
3.674 + ///Push a new edge to the front of the path
3.675 +
3.676 + ///Push a new edge to the front of the path.
3.677 + ///\sa setStartNode
3.678 + void pushFront(const GraphEdge& e) {
3.679 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
3.680 + fault("UndirPath::Builder::pushFront: nonincident edge");
3.681 + }
3.682 + front.push_back(e);
3.683 + }
3.684 +
3.685 + ///Push a new edge to the back of the path
3.686 +
3.687 + ///Push a new edge to the back of the path.
3.688 + ///\sa setStartNode
3.689 + void pushBack(const GraphEdge& e) {
3.690 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
3.691 + fault("UndirPath::Builder::pushBack: nonincident edge");
3.692 + }
3.693 + back.push_back(e);
3.694 + }
3.695 +
3.696 + ///Commit the changes to the path.
3.697 + void commit() {
3.698 + if( !(front.empty() && back.empty()) ) {
3.699 + Container tmp;
3.700 + tmp.reserve(front.size()+back.size()+P.length());
3.701 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
3.702 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
3.703 + tmp.insert(tmp.end(), back.begin(), back.end());
3.704 + P.edges.swap(tmp);
3.705 + front.clear();
3.706 + back.clear();
3.707 + }
3.708 + }
3.709 +
3.710 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
3.711 + // Hogy kenyelmes egy ilyet hasznalni?
3.712 +
3.713 + ///Reserve storage for the builder in advance.
3.714 +
3.715 + ///If you know an reasonable upper bound of the number of the edges
3.716 + ///to add, using this function you can speed up the building.
3.717 + void reserve(size_t r) {
3.718 + front.reserve(r);
3.719 + back.reserve(r);
3.720 + }
3.721 +
3.722 + private:
3.723 + bool empty() {
3.724 + return front.empty() && back.empty() && P.empty();
3.725 + }
3.726 +
3.727 + GraphNode from() const {
3.728 + if( ! front.empty() )
3.729 + return P.gr->tail(front[front.size()-1]);
3.730 + else if( ! P.empty() )
3.731 + return P.gr->tail(P.edges[0]);
3.732 + else if( ! back.empty() )
3.733 + return P.gr->tail(back[0]);
3.734 + else
3.735 + return INVALID;
3.736 + }
3.737 + GraphNode to() const {
3.738 + if( ! back.empty() )
3.739 + return P.gr->head(back[back.size()-1]);
3.740 + else if( ! P.empty() )
3.741 + return P.gr->head(P.edges[P.length()-1]);
3.742 + else if( ! front.empty() )
3.743 + return P.gr->head(front[0]);
3.744 + else
3.745 + return INVALID;
3.746 + }
3.747 +
3.748 + };
3.749 +
3.750 + };
3.751 +
3.752 +
3.753 +
3.754 +
3.755 +
3.756 +
3.757 +
3.758 +
3.759 +
3.760 +
3.761 + /**********************************************************************/
3.762 +
3.763 +
3.764 + /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
3.765 + elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
3.766 +
3.767 + template<typename Graph>
3.768 + class DynamicPath {
3.769 +
3.770 + public:
3.771 + typedef typename Graph::Edge GraphEdge;
3.772 + typedef typename Graph::Node GraphNode;
3.773 + class NodeIt;
3.774 + class EdgeIt;
3.775 +
3.776 + protected:
3.777 + Graph& G;
3.778 + // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
3.779 + // iranyitasat:
3.780 + GraphNode _first, _last;
3.781 + typedef std::deque<GraphEdge> Container;
3.782 + Container edges;
3.783 +
3.784 + public:
3.785 +
3.786 + DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
3.787 +
3.788 + /// Subpath defined by two nodes.
3.789 + /// Nodes may be in reversed order, then
3.790 + /// we contstruct the reversed path.
3.791 + DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
3.792 + /// Subpath defined by two edges. Contains edges in [a,b)
3.793 + /// It is an error if the two edges are not in order!
3.794 + DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
3.795 +
3.796 + size_t length() const { return edges.size(); }
3.797 + GraphNode from() const { return _first; }
3.798 + GraphNode to() const { return _last; }
3.799 +
3.800 + NodeIt& first(NodeIt &n) const { return nth(n, 0); }
3.801 + EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
3.802 + template<typename It>
3.803 + It first() const {
3.804 + It e;
3.805 + first(e);
3.806 + return e;
3.807 + }
3.808 +
3.809 + NodeIt& nth(NodeIt &, size_t) const;
3.810 + EdgeIt& nth(EdgeIt &, size_t) const;
3.811 + template<typename It>
3.812 + It nth(size_t n) const {
3.813 + It e;
3.814 + nth(e, n);
3.815 + return e;
3.816 + }
3.817 +
3.818 + bool valid(const NodeIt &n) const { return n.idx <= length(); }
3.819 + bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
3.820 +
3.821 + bool isForward(const EdgeIt &e) const { return e.forw; }
3.822 +
3.823 + /// index of a node on the path. Returns length+2 for the invalid NodeIt
3.824 + int index(const NodeIt &n) const { return n.idx; }
3.825 + /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
3.826 + int index(const EdgeIt &e) const { return e.it - edges.begin(); }
3.827 +
3.828 + EdgeIt& next(EdgeIt &e) const;
3.829 + NodeIt& next(NodeIt &n) const;
3.830 + template <typename It>
3.831 + It getNext(It it) const {
3.832 + It tmp(it); return next(tmp);
3.833 + }
3.834 +
3.835 + // A path is constructed using the following four functions.
3.836 + // They return false if the requested operation is inconsistent
3.837 + // with the path constructed so far.
3.838 + // If your path has only one edge you MUST set either "from" or "to"!
3.839 + // So you probably SHOULD call it in any case to be safe (and check the
3.840 + // returned value to check if your path is consistent with your idea).
3.841 + bool pushFront(const GraphEdge &e);
3.842 + bool pushBack(const GraphEdge &e);
3.843 + bool setFrom(const GraphNode &n);
3.844 + bool setTo(const GraphNode &n);
3.845 +
3.846 + // WARNING: these two functions return the head/tail of an edge with
3.847 + // respect to the direction of the path!
3.848 + // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
3.849 + // P.forward(e) is true (or the edge is a loop)!
3.850 + NodeIt head(const EdgeIt& e) const;
3.851 + NodeIt tail(const EdgeIt& e) const;
3.852 +
3.853 + // FIXME: ezeknek valami jobb nev kellene!!!
3.854 + GraphEdge graphEdge(const EdgeIt& e) const;
3.855 + GraphNode graphNode(const NodeIt& n) const;
3.856 +
3.857 +
3.858 + /*** Iterator classes ***/
3.859 + class EdgeIt {
3.860 + friend class DynamicPath;
3.861 +
3.862 + typename Container::const_iterator it;
3.863 + bool forw;
3.864 + public:
3.865 + // FIXME: jarna neki ilyen is...
3.866 + // EdgeIt(Invalid);
3.867 +
3.868 + bool forward() const { return forw; }
3.869 +
3.870 + bool operator==(const EdgeIt& e) const { return it==e.it; }
3.871 + bool operator!=(const EdgeIt& e) const { return it!=e.it; }
3.872 + bool operator<(const EdgeIt& e) const { return it<e.it; }
3.873 + };
3.874 +
3.875 + class NodeIt {
3.876 + friend class DynamicPath;
3.877 +
3.878 + size_t idx;
3.879 + bool tail; // Is this node the tail of the edge with same idx?
3.880 +
3.881 + public:
3.882 + // FIXME: jarna neki ilyen is...
3.883 + // NodeIt(Invalid);
3.884 +
3.885 + bool operator==(const NodeIt& n) const { return idx==n.idx; }
3.886 + bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
3.887 + bool operator<(const NodeIt& n) const { return idx<n.idx; }
3.888 + };
3.889 +
3.890 + private:
3.891 + bool edgeIncident(const GraphEdge &e, const GraphNode &a,
3.892 + GraphNode &b);
3.893 + bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
3.894 + };
3.895 +
3.896 + template<typename Gr>
3.897 + typename DynamicPath<Gr>::EdgeIt&
3.898 + DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
3.899 + if( e.it == edges.end() )
3.900 + return e;
3.901 +
3.902 + GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
3.903 + ++e.it;
3.904 +
3.905 + // Invalid edgeit is always forward :)
3.906 + if( e.it == edges.end() ) {
3.907 + e.forw = true;
3.908 + return e;
3.909 + }
3.910 +
3.911 + e.forw = ( G.tail(*e.it) == common_node );
3.912 + return e;
3.913 + }
3.914 +
3.915 + template<typename Gr>
3.916 + typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
3.917 + if( n.idx >= length() ) {
3.918 + // FIXME: invalid
3.919 + n.idx = length()+1;
3.920 + return n;
3.921 + }
3.922 +
3.923 +
3.924 + GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
3.925 + G.tail(edges[n.idx]) );
3.926 + ++n.idx;
3.927 + if( n.idx < length() ) {
3.928 + n.tail = ( next_node == G.tail(edges[n.idx]) );
3.929 + }
3.930 + else {
3.931 + n.tail = true;
3.932 + }
3.933 +
3.934 + return n;
3.935 + }
3.936 +
3.937 + template<typename Gr>
3.938 + bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
3.939 + GraphNode &b) {
3.940 + if( G.tail(e) == a ) {
3.941 + b=G.head(e);
3.942 + return true;
3.943 + }
3.944 + if( G.head(e) == a ) {
3.945 + b=G.tail(e);
3.946 + return true;
3.947 + }
3.948 + return false;
3.949 + }
3.950 +
3.951 + template<typename Gr>
3.952 + bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
3.953 + const GraphEdge &f) {
3.954 + if( edgeIncident(f, G.tail(e), _last) ) {
3.955 + _first = G.head(e);
3.956 + return true;
3.957 + }
3.958 + if( edgeIncident(f, G.head(e), _last) ) {
3.959 + _first = G.tail(e);
3.960 + return true;
3.961 + }
3.962 + return false;
3.963 + }
3.964 +
3.965 + template<typename Gr>
3.966 + bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
3.967 + if( G.valid(_first) ) {
3.968 + if( edgeIncident(e, _first, _first) ) {
3.969 + edges.push_front(e);
3.970 + return true;
3.971 + }
3.972 + else
3.973 + return false;
3.974 + }
3.975 + else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
3.976 + edges.push_front(e);
3.977 + return true;
3.978 + }
3.979 + else
3.980 + return false;
3.981 + }
3.982 +
3.983 + template<typename Gr>
3.984 + bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
3.985 + if( G.valid(_last) ) {
3.986 + if( edgeIncident(e, _last, _last) ) {
3.987 + edges.push_back(e);
3.988 + return true;
3.989 + }
3.990 + else
3.991 + return false;
3.992 + }
3.993 + else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
3.994 + edges.push_back(e);
3.995 + return true;
3.996 + }
3.997 + else
3.998 + return false;
3.999 + }
3.1000 +
3.1001 +
3.1002 + template<typename Gr>
3.1003 + bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
3.1004 + if( G.valid(_first) ) {
3.1005 + return _first == n;
3.1006 + }
3.1007 + else {
3.1008 + if( length() > 0) {
3.1009 + if( edgeIncident(edges[0], n, _last) ) {
3.1010 + _first = n;
3.1011 + return true;
3.1012 + }
3.1013 + else return false;
3.1014 + }
3.1015 + else {
3.1016 + _first = _last = n;
3.1017 + return true;
3.1018 + }
3.1019 + }
3.1020 + }
3.1021 +
3.1022 + template<typename Gr>
3.1023 + bool DynamicPath<Gr>::setTo(const GraphNode &n) {
3.1024 + if( G.valid(_last) ) {
3.1025 + return _last == n;
3.1026 + }
3.1027 + else {
3.1028 + if( length() > 0) {
3.1029 + if( edgeIncident(edges[0], n, _first) ) {
3.1030 + _last = n;
3.1031 + return true;
3.1032 + }
3.1033 + else return false;
3.1034 + }
3.1035 + else {
3.1036 + _first = _last = n;
3.1037 + return true;
3.1038 + }
3.1039 + }
3.1040 + }
3.1041 +
3.1042 +
3.1043 + template<typename Gr>
3.1044 + typename DynamicPath<Gr>::NodeIt
3.1045 + DynamicPath<Gr>::tail(const EdgeIt& e) const {
3.1046 + NodeIt n;
3.1047 +
3.1048 + if( e.it == edges.end() ) {
3.1049 + // FIXME: invalid-> invalid
3.1050 + n.idx = length() + 1;
3.1051 + n.tail = true;
3.1052 + return n;
3.1053 + }
3.1054 +
3.1055 + n.idx = e.it-edges.begin();
3.1056 + n.tail = e.forw;
3.1057 + return n;
3.1058 + }
3.1059 +
3.1060 + template<typename Gr>
3.1061 + typename DynamicPath<Gr>::NodeIt
3.1062 + DynamicPath<Gr>::head(const EdgeIt& e) const {
3.1063 + if( e.it == edges.end()-1 ) {
3.1064 + return _last;
3.1065 + }
3.1066 +
3.1067 + EdgeIt next_edge = e;
3.1068 + next(next_edge);
3.1069 + return tail(next_edge);
3.1070 + }
3.1071 +
3.1072 + template<typename Gr>
3.1073 + typename DynamicPath<Gr>::GraphEdge
3.1074 + DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
3.1075 + if( e.it != edges.end() ) {
3.1076 + return *e.it;
3.1077 + }
3.1078 + else {
3.1079 + return INVALID;
3.1080 + }
3.1081 + }
3.1082 +
3.1083 + template<typename Gr>
3.1084 + typename DynamicPath<Gr>::GraphNode
3.1085 + DynamicPath<Gr>::graphNode(const NodeIt& n) const {
3.1086 + if( n.idx < length() ) {
3.1087 + return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
3.1088 + }
3.1089 + else if( n.idx == length() ) {
3.1090 + return _last;
3.1091 + }
3.1092 + else {
3.1093 + return INVALID;
3.1094 + }
3.1095 + }
3.1096 +
3.1097 + template<typename Gr>
3.1098 + typename DynamicPath<Gr>::EdgeIt&
3.1099 + DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
3.1100 + if( k>=length() ) {
3.1101 + // FIXME: invalid EdgeIt
3.1102 + e.it = edges.end();
3.1103 + e.forw = true;
3.1104 + return e;
3.1105 + }
3.1106 +
3.1107 + e.it = edges.begin()+k;
3.1108 + if(k==0) {
3.1109 + e.forw = ( G.tail(*e.it) == _first );
3.1110 + }
3.1111 + else {
3.1112 + e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
3.1113 + G.tail(*e.it) == G.head(edges[k-1]) );
3.1114 + }
3.1115 + return e;
3.1116 + }
3.1117 +
3.1118 + template<typename Gr>
3.1119 + typename DynamicPath<Gr>::NodeIt&
3.1120 + DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
3.1121 + if( k>length() ) {
3.1122 + // FIXME: invalid NodeIt
3.1123 + n.idx = length()+1;
3.1124 + n.tail = true;
3.1125 + return n;
3.1126 + }
3.1127 + if( k==length() ) {
3.1128 + n.idx = length();
3.1129 + n.tail = true;
3.1130 + return n;
3.1131 + }
3.1132 + n = tail(nth<EdgeIt>(k));
3.1133 + return n;
3.1134 + }
3.1135 +
3.1136 + // Reszut konstruktorok:
3.1137 +
3.1138 +
3.1139 + template<typename Gr>
3.1140 + DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
3.1141 + const EdgeIt &b) :
3.1142 + G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
3.1143 + {
3.1144 + if( G.valid(P._first) && a.it < P.edges.end() ) {
3.1145 + _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
3.1146 + if( b.it < P.edges.end() ) {
3.1147 + _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
3.1148 + }
3.1149 + else {
3.1150 + _last = P._last;
3.1151 + }
3.1152 + }
3.1153 + }
3.1154 +
3.1155 + template<typename Gr>
3.1156 + DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
3.1157 + const NodeIt &b) : G(P.G)
3.1158 + {
3.1159 + if( !P.valid(a) || !P.valid(b) )
3.1160 + return;
3.1161 +
3.1162 + int ai = a.idx, bi = b.idx;
3.1163 + if( bi<ai )
3.1164 + std::swap(ai,bi);
3.1165 +
3.1166 + edges.resize(bi-ai);
3.1167 + copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
3.1168 +
3.1169 + _first = P.graphNode(a);
3.1170 + _last = P.graphNode(b);
3.1171 + }
3.1172 +
3.1173 + ///@}
3.1174 +
3.1175 +} // namespace hugo
3.1176 +
3.1177 +#endif // HUGO_PATH_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/peter/path/path_skeleton.h Tue Sep 07 13:55:35 2004 +0000
4.3 @@ -0,0 +1,223 @@
4.4 +#define SKELETON
4.5 +// -*- c++ -*- //
4.6 +
4.7 +///\ingroup skeletons
4.8 +///\file
4.9 +///\brief Classes for representing paths in graphs.
4.10 +
4.11 +#ifndef HUGO_PATH_H
4.12 +#define HUGO_PATH_H
4.13 +
4.14 +#include <hugo/invalid.h>
4.15 +
4.16 +namespace hugo {
4.17 + namespace skeleton {
4.18 + /// \addtogroup skeletons
4.19 + /// @{
4.20 +
4.21 +
4.22 + //! \brief A skeletom structure for representing directed paths in a graph.
4.23 + //!
4.24 + //! A skeleton structure for representing directed paths in a graph.
4.25 + //! \param GR The graph type in which the path is.
4.26 + //!
4.27 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
4.28 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
4.29 + //! and \c Edge of the original graph.
4.30 + template<typename GR>
4.31 + class Path {
4.32 + public:
4.33 +
4.34 + /// Type of the underlying graph.
4.35 + typedef /*typename*/ GR Graph;
4.36 + /// Edge type of the underlying graph.
4.37 + typedef typename Graph::Edge GraphEdge;
4.38 + /// Node type of the underlying graph.
4.39 + typedef typename Graph::Node GraphNode;
4.40 + class NodeIt;
4.41 + class EdgeIt;
4.42 +
4.43 + /// \param _G The graph in which the path is.
4.44 + ///
4.45 + Path(const Graph &_G) {}
4.46 +
4.47 + /// Length of the path.
4.48 + size_t length() const {}
4.49 + /// Returns whether the path is empty.
4.50 + bool empty() const {}
4.51 +
4.52 + /// Resets the path to an empty path.
4.53 + void clear() {}
4.54 +
4.55 + /// \brief Starting point of the path.
4.56 + ///
4.57 + /// Starting point of the path.
4.58 + /// Returns INVALID if the path is empty.
4.59 + GraphNode head() const {}
4.60 + /// \brief End point of the path.
4.61 + ///
4.62 + /// End point of the path.
4.63 + /// Returns INVALID if the path is empty.
4.64 + GraphNode tail() const {}
4.65 +
4.66 + /// \brief First NodeIt/EdgeIt.
4.67 + ///
4.68 + /// Initializes node or edge iterator to point to the first
4.69 + /// node or edge.
4.70 + template<typename It>
4.71 + It& first(It &i) const { return i=It(*this); }
4.72 +
4.73 + /// \brief The head of an edge.
4.74 + ///
4.75 + /// Returns node iterator pointing to the head node of the
4.76 + /// given edge iterator.
4.77 + NodeIt head(const EdgeIt& e) const {}
4.78 +
4.79 + /// \brief The tail of an edge.
4.80 + ///
4.81 + /// Returns node iterator pointing to the tail node of the
4.82 + /// given edge iterator.
4.83 + NodeIt tail(const EdgeIt& e) const {}
4.84 +
4.85 +
4.86 + /* Iterator classes */
4.87 +
4.88 + /**
4.89 + * \brief Iterator class to iterate on the edges of the paths
4.90 + *
4.91 + * \ingroup skeletons
4.92 + * This class is used to iterate on the edges of the paths
4.93 + *
4.94 + * Of course it converts to Graph::Edge
4.95 + *
4.96 + */
4.97 + class EdgeIt {
4.98 + public:
4.99 + /// Default constructor
4.100 + EdgeIt() {}
4.101 + /// Invalid constructor
4.102 + EdgeIt(Invalid) {}
4.103 + /// Constructor with starting point
4.104 + EdgeIt(const Path &_p) {}
4.105 +
4.106 + operator GraphEdge () const {}
4.107 +
4.108 + /// Next edge
4.109 + EdgeIt& operator++() {}
4.110 +
4.111 + /// Comparison operator
4.112 + bool operator==(const EdgeIt& e) const {}
4.113 + /// Comparison operator
4.114 + bool operator!=(const EdgeIt& e) const {}
4.115 +// /// Comparison operator
4.116 +// /// \todo It is not clear what is the "natural" ordering.
4.117 +// bool operator<(const EdgeIt& e) const {}
4.118 +
4.119 + };
4.120 +
4.121 + /**
4.122 + * \brief Iterator class to iterate on the nodes of the paths
4.123 + *
4.124 + * \ingroup skeletons
4.125 + * This class is used to iterate on the nodes of the paths
4.126 + *
4.127 + * Of course it converts to Graph::Node.
4.128 + *
4.129 + */
4.130 + class NodeIt {
4.131 + public:
4.132 + /// Default constructor
4.133 + NodeIt() {}
4.134 + /// Invalid constructor
4.135 + NodeIt(Invalid) {}
4.136 + /// Constructor with starting point
4.137 + NodeIt(const Path &_p) {}
4.138 +
4.139 + ///Conversion to Graph::Node
4.140 + operator const GraphNode& () const {}
4.141 + /// Next node
4.142 + NodeIt& operator++() {}
4.143 +
4.144 + /// Comparison operator
4.145 + bool operator==(const NodeIt& e) const {}
4.146 + /// Comparison operator
4.147 + bool operator!=(const NodeIt& e) const {}
4.148 +// /// Comparison operator
4.149 +// /// \todo It is not clear what is the "natural" ordering.
4.150 +// bool operator<(const NodeIt& e) const {}
4.151 +
4.152 + };
4.153 +
4.154 + friend class Builder;
4.155 +
4.156 + /**
4.157 + * \brief Class to build paths
4.158 + *
4.159 + * \ingroup skeletons
4.160 + * This class is used to fill a path with edges.
4.161 + *
4.162 + * You can push new edges to the front and to the back of the path in
4.163 + * arbitrary order then you should commit these changes to the graph.
4.164 + *
4.165 + * While the builder is active (after the first modifying
4.166 + * operation and until the call of \ref commit())
4.167 + * the underlining Path is in a
4.168 + * "transitional" state (operations on it have undefined result).
4.169 + */
4.170 + class Builder {
4.171 + public:
4.172 +
4.173 + Path &P;
4.174 +
4.175 + ///\param _P the path you want to fill in.
4.176 + ///
4.177 + Builder(Path &_P) : P(_P) {}
4.178 +
4.179 + /// Sets the starting node of the path.
4.180 +
4.181 + /// Sets the starting node of the path. Edge added to the path
4.182 + /// afterwards have to be incident to this node.
4.183 + /// You \em must start building an empry path with this functions.
4.184 + /// (And you \em must \em not use it later).
4.185 + /// \sa pushFront()
4.186 + /// \sa pushBack()
4.187 + void setStartNode(const GraphNode &) {}
4.188 +
4.189 + ///Push a new edge to the front of the path
4.190 +
4.191 + ///Push a new edge to the front of the path.
4.192 + ///If the path is empty, you \em must call \ref setStartNode() before
4.193 + ///the first use of \ref pushFront().
4.194 + void pushFront(const GraphEdge& e) {}
4.195 +
4.196 + ///Push a new edge to the back of the path
4.197 +
4.198 + ///Push a new edge to the back of the path.
4.199 + ///If the path is empty, you \em must call \ref setStartNode() before
4.200 + ///the first use of \ref pushBack().
4.201 + void pushBack(const GraphEdge& e) {}
4.202 +
4.203 + ///Commit the changes to the path.
4.204 + void commit() {}
4.205 +
4.206 + ///Reserve (front) storage for the builder in advance.
4.207 +
4.208 + ///If you know an reasonable upper bound of the number of the edges
4.209 + ///to add to the front of the path,
4.210 + ///using this function you may speed up the building.
4.211 + void reserveFront(size_t r) {}
4.212 + ///Reserve (back) storage for the builder in advance.
4.213 +
4.214 + ///If you know an reasonable upper bound of the number of the edges
4.215 + ///to add to the back of the path,
4.216 + ///using this function you may speed up the building.
4.217 + void reserveBack(size_t r) {}
4.218 + };
4.219 + };
4.220 +
4.221 + ///@}
4.222 + }
4.223 +
4.224 +} // namespace hugo
4.225 +
4.226 +#endif // HUGO_PATH_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/peter/path/path_test.cc Tue Sep 07 13:55:35 2004 +0000
5.3 @@ -0,0 +1,182 @@
5.4 +#include <string>
5.5 +#include <iostream>
5.6 +//#include <path.h>
5.7 +#include <path_skeleton.h>
5.8 +#include <list_graph.h>
5.9 +
5.10 +using namespace std;
5.11 +using namespace hugo;
5.12 +using namespace skeleton;
5.13 +
5.14 +bool passed = true;
5.15 +
5.16 +void check(bool rc) {
5.17 + passed = passed && rc;
5.18 + if(!rc) {
5.19 + cout << "Test failed!" << endl;
5.20 + }
5.21 +}
5.22 +
5.23 +#ifdef DEBUG
5.24 +const bool debug = true;
5.25 +#else
5.26 +const bool debug = false;
5.27 +#endif
5.28 +
5.29 +
5.30 +int main() {
5.31 +
5.32 + try {
5.33 +
5.34 + typedef ListGraph::Node Node;
5.35 + typedef ListGraph::Edge Edge;
5.36 +
5.37 + ListGraph G;
5.38 +
5.39 + Node s=G.addNode();
5.40 + Node v1=G.addNode();
5.41 + Node v2=G.addNode();
5.42 + Node v3=G.addNode();
5.43 + Node v4=G.addNode();
5.44 + Node t=G.addNode();
5.45 +
5.46 + Edge e1 = G.addEdge(s, v1);
5.47 + Edge e2 = G.addEdge(s, v2);
5.48 + Edge e3 = G.addEdge(v1, v2);
5.49 + Edge e4 = G.addEdge(v2, v1);
5.50 + Edge e5 = G.addEdge(v1, v3);
5.51 + Edge e6 = G.addEdge(v3, v2);
5.52 + Edge e7 = G.addEdge(v2, v4);
5.53 + Edge e8 = G.addEdge(v4, v3);
5.54 + Edge e9 = G.addEdge(v3, t);
5.55 + Edge e10 = G.addEdge(v4, t);
5.56 +
5.57 + bool rc;
5.58 +
5.59 + {
5.60 + cout << "\n\n\nDirPath tesztelese...\n";
5.61 +
5.62 +
5.63 + cout << "Ures path letrehozasa" << endl;
5.64 + //typedef DirPath<ListGraph> DPath;
5.65 + typedef Path <ListGraph> DPath;
5.66 + DPath P(G);
5.67 +
5.68 + cout << "P.length() == " << P.length() << endl;
5.69 + check(P.length() == 0);
5.70 +
5.71 +#ifdef SKELETON
5.72 + cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
5.73 + check(! (P.tail()!=INVALID));
5.74 +#else
5.75 + cout << "P.tail() valid? " << (P.from()!=INVALID) << endl;
5.76 + check(! (P.to()!=INVALID));
5.77 +#endif
5.78 + {
5.79 + cout << "Builder objektum letrehozasa" << endl;
5.80 + DPath::Builder B(P);
5.81 +
5.82 + cout << "Hozzaadunk az elejehez ket elet..." << endl;
5.83 + B.pushFront(e6);
5.84 + B.pushFront(e5);
5.85 + cout << "P.length() == " << P.length() << endl;
5.86 + check(P.length() == 0);
5.87 +
5.88 + cout << "Commitolunk..." << endl;
5.89 + B.commit();
5.90 +
5.91 + cout << "P.length() == " << P.length() << endl;
5.92 + check(P.length() == 2);
5.93 +
5.94 +#ifdef SKELETON
5.95 + cout << "P.tail() valid? " << (P.tail()!=INVALID) << endl;
5.96 + check(P.tail()!=INVALID);
5.97 + cout << "P.tail()==v1 ? " << (P.tail()==v1) << endl;
5.98 + check(P.tail() == v1);
5.99 +#else
5.100 + cout << "P.tail() valid? " << (P.from()!=INVALID) << endl;
5.101 + check(P.from()!=INVALID);
5.102 + cout << "P.tail()==v1 ? " << (P.from()==v1) << endl;
5.103 + check(P.from() == v1);
5.104 +#endif
5.105 +
5.106 + // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
5.107 + // de legalabb valami:
5.108 +#ifdef DEBUG
5.109 + cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl;
5.110 + rc = false;
5.111 + try {
5.112 + B.pushFront(e3);
5.113 + }
5.114 + catch(const Exception &e) {
5.115 + cout << "E: " << e.what() << endl;
5.116 + rc = true;
5.117 + }
5.118 + check(rc);
5.119 +#endif
5.120 +
5.121 + cout << "Hozzaadunk a vegehez ket elet..." << endl;
5.122 + B.pushBack(e7);
5.123 + B.pushBack(e8);
5.124 + cout << "P.length() == " << P.length() << endl;
5.125 + check(P.length() == 2);
5.126 +
5.127 + cout << "Es commitolunk...\n";
5.128 + B.commit();
5.129 + }
5.130 + cout << "P.length() == " << P.length() << endl;
5.131 + check(P.length() == 4);
5.132 +
5.133 +#ifdef SKELETON
5.134 + cout << "P.head()==v3 ? " << (P.head()==v3) << endl;
5.135 + check(P.head() == v3);
5.136 +#else
5.137 + cout << "P.head()==v3 ? " << (P.to()==v3) << endl;
5.138 + check(P.to() == v3);
5.139 +#endif
5.140 +
5.141 + cout << "Vegigiteralunk az eleken." << endl;
5.142 + typedef DPath::NodeIt NodeIt;
5.143 + typedef DPath::EdgeIt EdgeIt;
5.144 + EdgeIt e;
5.145 + int i=1;
5.146 + for(P.first(e); e!=INVALID; ++e, ++i) {
5.147 + cout << i << ". el: " <</* e << */endl;
5.148 + }
5.149 +
5.150 +
5.151 + // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
5.152 + // de legalabb valami:
5.153 +
5.154 +#ifdef DEBUG
5.155 + rc = false;
5.156 + try {
5.157 + cout << "Setting an edgeiter to a nonexistant edge." << endl;
5.158 + //P.nth(e,134);
5.159 + rc = !debug;
5.160 + }
5.161 + catch(const Exception &e) {
5.162 + cout << "E: " << e.what() << endl;
5.163 + rc = debug;
5.164 + }
5.165 + check(rc);
5.166 +#endif
5.167 + }
5.168 +
5.169 + }
5.170 + catch(const std::exception &e) {
5.171 + cout << "Uncaught exception: " << e.what() << endl;
5.172 + return 1;
5.173 + }
5.174 + catch(...) {
5.175 + cout << "Something horrible happened: an exception which isn't "
5.176 + << "std::exception" << endl;
5.177 + return 2;
5.178 + }
5.179 +
5.180 +
5.181 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
5.182 + << endl;
5.183 +
5.184 + return passed ? 0 : 1;
5.185 +}