- Clarified Path skeleton.
- setStart() changed to setStartNode()
1.1 --- a/src/hugo/skeletons/path.h Sun Sep 05 20:11:47 2004 +0000
1.2 +++ b/src/hugo/skeletons/path.h Sun Sep 05 20:13:48 2004 +0000
1.3 @@ -30,1143 +30,210 @@
1.4 #include <debug.h>
1.5
1.6 namespace hugo {
1.7 + namespace skeleton {
1.8 + /// \addtogroup skeletons
1.9 + /// @{
1.10 +
1.11 +
1.12 + //! \brief A structure for representing directed path in a graph.
1.13 + //!
1.14 + //! A structure for representing directed path in a graph.
1.15 + //! \param GR The graph type in which the path is.
1.16 + //!
1.17 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.18 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.19 + //! and \c Edge of the original graph.
1.20 + template<typename GR>
1.21 + class Path {
1.22 + public:
1.23 +
1.24 + /// Type of the underlying graph.
1.25 + typedef typename GR Graph;
1.26 + /// Edge type of the underlying graph.
1.27 + typedef typename Graph::Edge GraphEdge;
1.28 + /// Node type of the underlying graph.
1.29 + typedef typename Graph::Node GraphNode;
1.30 + class NodeIt;
1.31 + class EdgeIt;
1.32 +
1.33 + /// \param _G The graph in which the path is.
1.34 + ///
1.35 + Path(const Graph &_G) {}
1.36 +
1.37 + /// Length of the path.
1.38 + size_t length() const {}
1.39 + /// Returns whether the path is empty.
1.40 + bool empty() const {}
1.41 +
1.42 + /// Resets the path to an empty path.
1.43 + void clear() {}
1.44
1.45 - /// \addtogroup paths
1.46 - /// @{
1.47 + /// \brief Starting point of the path.
1.48 + ///
1.49 + /// Starting point of the path.
1.50 + /// Returns INVALID if the path is empty.
1.51 + NodeIt head() const {}
1.52 + /// \brief End point of the path.
1.53 + ///
1.54 + /// End point of the path.
1.55 + /// Returns INVALID if the path is empty.
1.56 + NodeIt tail() const {}
1.57
1.58 + /// \brief First NodeIt/EdgeIt.
1.59 + ///
1.60 + /// Initializes node or edge iterator to point to the first
1.61 + /// node or edge.
1.62 + template<typename It>
1.63 + It& first(It &i) const { return i=It(*this); }
1.64
1.65 - //! \brief A structure for representing directed path in a graph.
1.66 - //!
1.67 - //! A structure for representing directed path in a graph.
1.68 - //! \param Graph The graph type in which the path is.
1.69 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.70 - //!
1.71 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.72 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.73 - //! and \c Edge of the original graph.
1.74 - //!
1.75 - //! \todo Thoroughfully check all the range and consistency tests.
1.76 - template<typename Graph, typename DM = DefaultDebugMode>
1.77 - class DirPath {
1.78 - public:
1.79 - /// Edge type of the underlying graph.
1.80 - typedef typename Graph::Edge GraphEdge;
1.81 - /// Node type of the underlying graph.
1.82 - typedef typename Graph::Node GraphNode;
1.83 - class NodeIt;
1.84 - class EdgeIt;
1.85 + /// \brief The head of an edge.
1.86 + ///
1.87 + /// Returns node iterator pointing to the head node of the
1.88 + /// given edge iterator.
1.89 + NodeIt head(const EdgeIt& e) const {}
1.90
1.91 - protected:
1.92 - const Graph *gr;
1.93 - typedef std::vector<GraphEdge> Container;
1.94 - Container edges;
1.95 + /// \brief The tail of an edge.
1.96 + ///
1.97 + /// Returns node iterator pointing to the tail node of the
1.98 + /// given edge iterator.
1.99 + NodeIt tail(const EdgeIt& e) const {}
1.100
1.101 - public:
1.102
1.103 - /// \param _G The graph in which the path is.
1.104 - ///
1.105 - DirPath(const Graph &_G) : gr(&_G) {}
1.106 + /* Iterator classes */
1.107
1.108 - /// \brief Subpath constructor.
1.109 - ///
1.110 - /// Subpath defined by two nodes.
1.111 - /// \warning It is an error if the two edges are not in order!
1.112 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
1.113 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.114 - // FIXME: this check should be more elaborate...
1.115 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.116 - }
1.117 - gr = P.gr;
1.118 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.119 - }
1.120 + /**
1.121 + * \brief Iterator class to iterate on the edges of the paths
1.122 + *
1.123 + * \ingroup skeletons
1.124 + * This class is used to iterate on the edges of the paths
1.125 + *
1.126 + * Of course it converts to Graph::Edge
1.127 + *
1.128 + */
1.129 + class EdgeIt {
1.130 + public:
1.131 + /// Default constructor
1.132 + EdgeIt() {}
1.133 + /// Invalid constructor
1.134 + EdgeIt(Invalid) {}
1.135 + /// Constructor with starting point
1.136 + EdgeIt(const Path &_p) {}
1.137
1.138 - /// \brief Subpath constructor.
1.139 - ///
1.140 - /// Subpath defined by two edges. Contains edges in [a,b)
1.141 - /// \warning It is an error if the two edges are not in order!
1.142 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.143 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.144 - // FIXME: this check should be more elaborate...
1.145 - fault("DirPath, subpath ctor: invalid bounding nodes");
1.146 - }
1.147 - gr = P.gr;
1.148 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.149 - }
1.150 + operator GraphEdge () const {}
1.151
1.152 - /// Length of the path.
1.153 - size_t length() const { return edges.size(); }
1.154 - /// Returns whether the path is empty.
1.155 - bool empty() const { return edges.empty(); }
1.156 + /// Next edge
1.157 + EdgeIt& operator++() {}
1.158
1.159 - /// Resets the path to an empty path.
1.160 - void clear() { edges.clear(); }
1.161 + /// Comparison operator
1.162 + bool operator==(const EdgeIt& e) const {}
1.163 + /// Comparison operator
1.164 + bool operator!=(const EdgeIt& e) const {}
1.165 +// /// Comparison operator
1.166 +// /// \todo It is not clear what is the "natural" ordering.
1.167 +// bool operator<(const EdgeIt& e) const {}
1.168
1.169 - /// \brief Starting point of the path.
1.170 - ///
1.171 - /// Starting point of the path.
1.172 - /// Returns INVALID if the path is empty.
1.173 - GraphNode from() const {
1.174 - return empty() ? INVALID : gr->tail(edges[0]);
1.175 - }
1.176 - /// \brief End point of the path.
1.177 - ///
1.178 - /// End point of the path.
1.179 - /// Returns INVALID if the path is empty.
1.180 - GraphNode to() const {
1.181 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.182 - }
1.183 + };
1.184
1.185 - /// \brief Initializes node or edge iterator to point to the first
1.186 - /// node or edge.
1.187 - ///
1.188 - /// \sa nth
1.189 - template<typename It>
1.190 - It& first(It &i) const { return i=It(*this); }
1.191 + /**
1.192 + * \brief Iterator class to iterate on the nodes of the paths
1.193 + *
1.194 + * \ingroup skeletons
1.195 + * This class is used to iterate on the nodes of the paths
1.196 + *
1.197 + * Of course it converts to Graph::Node.
1.198 + *
1.199 + */
1.200 + class NodeIt {
1.201 + public:
1.202 + /// Default constructor
1.203 + NodeIt() {}
1.204 + /// Invalid constructor
1.205 + NodeIt(Invalid) {}
1.206 + /// Constructor with starting point
1.207 + NodeIt(const Path &_p) {}
1.208
1.209 - /// \brief Initializes node iterator to point to the node of a given index.
1.210 - NodeIt& nth(NodeIt &i, int n) const {
1.211 - if( DM::range_check && (n<0 || n>int(length())) )
1.212 - fault("DirPath::nth: index out of range");
1.213 - return i=NodeIt(*this, n);
1.214 - }
1.215 + ///Conversion to Graph::Node
1.216 + operator const GraphNode& () const {}
1.217 + /// Next node
1.218 + NodeIt& operator++() {}
1.219
1.220 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.221 - EdgeIt& nth(EdgeIt &i, int n) const {
1.222 - if( DM::range_check && (n<0 || n>=int(length())) )
1.223 - fault("DirPath::nth: index out of range");
1.224 - return i=EdgeIt(*this, n);
1.225 - }
1.226 + /// Comparison operator
1.227 + bool operator==(const NodeIt& e) const {}
1.228 + /// Comparison operator
1.229 + bool operator!=(const NodeIt& e) const {}
1.230 +// /// Comparison operator
1.231 +// /// \todo It is not clear what is the "natural" ordering.
1.232 +// bool operator<(const NodeIt& e) const {}
1.233
1.234 - /// Checks validity of a node or edge iterator.
1.235 - template<typename It>
1.236 - static
1.237 - bool valid(const It &i) { return i.valid(); }
1.238 + };
1.239
1.240 - /// Steps the given node or edge iterator.
1.241 - template<typename It>
1.242 - static
1.243 - It& next(It &e) {
1.244 - if( DM::range_check && !e.valid() )
1.245 - fault("DirPath::next() on invalid iterator");
1.246 - return ++e;
1.247 - }
1.248 + friend class Builder;
1.249
1.250 - /// \brief Returns node iterator pointing to the head node of the
1.251 - /// given edge iterator.
1.252 - NodeIt head(const EdgeIt& e) const {
1.253 - if( DM::range_check && !e.valid() )
1.254 - fault("DirPath::head() on invalid iterator");
1.255 - return NodeIt(*this, e.idx+1);
1.256 - }
1.257 + /**
1.258 + * \brief Class to build paths
1.259 + *
1.260 + * \ingroup skeletons
1.261 + * This class is used to fill a path with edges.
1.262 + *
1.263 + * You can push new edges to the front and to the back of the path in
1.264 + * arbitrary order then you should commit these changes to the graph.
1.265 + *
1.266 + * While the builder is active (after the first modifying
1.267 + * operation and until the call of \ref commit())
1.268 + * the underlining Path is in a
1.269 + * "transitional" state (operations on it have undefined result).
1.270 + */
1.271 + class Builder {
1.272 + public:
1.273 + ///\param _P the path you want to fill in.
1.274 + ///
1.275 + Builder(Path &_P) : P(_P) {}
1.276
1.277 - /// \brief Returns node iterator pointing to the tail node of the
1.278 - /// given edge iterator.
1.279 - NodeIt tail(const EdgeIt& e) const {
1.280 - if( DM::range_check && !e.valid() )
1.281 - fault("DirPath::tail() on invalid iterator");
1.282 - return NodeIt(*this, e.idx);
1.283 - }
1.284 + /// Sets the starting node of the path.
1.285 +
1.286 + /// Sets the starting node of the path. Edge added to the path
1.287 + /// afterwards have to be incident to this node.
1.288 + /// You \em must start building an empry path with this functions.
1.289 + /// (And you \em must \em not use it later).
1.290 + /// \sa pushFront()
1.291 + /// \sa pushBack()
1.292 + void setStartNode(const GraphNode &) {}
1.293
1.294 + ///Push a new edge to the front of the path
1.295
1.296 - /* Iterator classes */
1.297 + ///Push a new edge to the front of the path.
1.298 + ///If the path is empty, you \em must call \ref setStartNode() before
1.299 + ///the first use of \ref pushFront().
1.300 + void pushFront(const GraphEdge& e) {}
1.301
1.302 - /**
1.303 - * \brief Iterator class to iterate on the edges of the paths
1.304 - *
1.305 - * \ingroup paths
1.306 - * This class is used to iterate on the edges of the paths
1.307 - *
1.308 - * Of course it converts to Graph::Edge
1.309 - *
1.310 - * \todo Its interface differs from the standard edge iterator.
1.311 - * Yes, it shouldn't.
1.312 - */
1.313 - class EdgeIt {
1.314 - friend class DirPath;
1.315 + ///Push a new edge to the back of the path
1.316
1.317 - int idx;
1.318 - const DirPath *p;
1.319 - public:
1.320 - /// Default constructor
1.321 - EdgeIt() {}
1.322 - /// Invalid constructor
1.323 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.324 - /// Constructor with starting point
1.325 - EdgeIt(const DirPath &_p, int _idx = 0) :
1.326 - idx(_idx), p(&_p) { validate(); }
1.327 + ///Push a new edge to the back of the path.
1.328 + ///If the path is empty, you \em must call \ref setStartNode() before
1.329 + ///the first use of \ref pushBack().
1.330 + void pushBack(const GraphEdge& e) {}
1.331
1.332 - ///Validity check
1.333 - bool valid() const { return idx!=-1; }
1.334 + ///Commit the changes to the path.
1.335 + void commit() {}
1.336
1.337 - ///Conversion to Graph::Edge
1.338 - operator GraphEdge () const {
1.339 - return valid() ? p->edges[idx] : INVALID;
1.340 - }
1.341 + ///Reserve (front) storage for the builder in advance.
1.342
1.343 - /// Next edge
1.344 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.345 + ///If you know an reasonable upper bound of the number of the edges
1.346 + ///to add to the front of the path,
1.347 + ///using this function you may speed up the building.
1.348 + void reserveFront(size_t r) {}
1.349 + ///Reserve (back) storage for the builder in advance.
1.350
1.351 - /// Comparison operator
1.352 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.353 - /// Comparison operator
1.354 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.355 - /// Comparison operator
1.356 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.357 -
1.358 - private:
1.359 - // FIXME: comparison between signed and unsigned...
1.360 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.361 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.362 + ///If you know an reasonable upper bound of the number of the edges
1.363 + ///to add to the back of the path,
1.364 + ///using this function you may speed up the building.
1.365 + void reserveBack(size_t r) {}
1.366 + };
1.367 };
1.368
1.369 - /**
1.370 - * \brief Iterator class to iterate on the nodes of the paths
1.371 - *
1.372 - * \ingroup paths
1.373 - * This class is used to iterate on the nodes of the paths
1.374 - *
1.375 - * Of course it converts to Graph::Node
1.376 - *
1.377 - * \todo Its interface differs from the standard node iterator.
1.378 - * Yes, it shouldn't.
1.379 - */
1.380 - class NodeIt {
1.381 - friend class DirPath;
1.382 -
1.383 - int idx;
1.384 - const DirPath *p;
1.385 - public:
1.386 - /// Default constructor
1.387 - NodeIt() {}
1.388 - /// Invalid constructor
1.389 - NodeIt(Invalid) : idx(-1), p(0) {}
1.390 - /// Constructor with starting point
1.391 - NodeIt(const DirPath &_p, int _idx = 0) :
1.392 - idx(_idx), p(&_p) { validate(); }
1.393 -
1.394 - ///Validity check
1.395 - bool valid() const { return idx!=-1; }
1.396 -
1.397 - ///Conversion to Graph::Node
1.398 - operator const GraphNode& () const {
1.399 - if(idx >= p->length())
1.400 - return p->to();
1.401 - else if(idx >= 0)
1.402 - return p->gr->tail(p->edges[idx]);
1.403 - else
1.404 - return INVALID;
1.405 - }
1.406 - /// Next node
1.407 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.408 -
1.409 - /// Comparison operator
1.410 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.411 - /// Comparison operator
1.412 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.413 - /// Comparison operator
1.414 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.415 -
1.416 - private:
1.417 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.418 - };
1.419 -
1.420 - friend class Builder;
1.421 -
1.422 - /**
1.423 - * \brief Class to build paths
1.424 - *
1.425 - * \ingroup paths
1.426 - * This class is used to fill a path with edges.
1.427 - *
1.428 - * You can push new edges to the front and to the back of the path in
1.429 - * arbitrary order then you should commit these changes to the graph.
1.430 - *
1.431 - * Fundamentally, for most "Paths" (classes fulfilling the
1.432 - * PathConcept) while the builder is active (after the first modifying
1.433 - * operation and until the commit()) the original Path is in a
1.434 - * "transitional" state (operations on it have undefined result). But
1.435 - * in the case of DirPath the original path remains unchanged until the
1.436 - * commit. However we don't recomend that you use this feature.
1.437 - */
1.438 - class Builder {
1.439 - DirPath &P;
1.440 - Container front, back;
1.441 -
1.442 - public:
1.443 - ///\param _P the path you want to fill in.
1.444 - ///
1.445 - Builder(DirPath &_P) : P(_P) {}
1.446 -
1.447 - /// Sets the starting node of the path.
1.448 -
1.449 - /// Sets the starting node of the path. Edge added to the path
1.450 - /// afterwards have to be incident to this node.
1.451 - /// It should be called iff the path is empty and before any call to
1.452 - /// \ref pushFront() or \ref pushBack()
1.453 - void setStart(const GraphNode &) {}
1.454 -
1.455 - ///Push a new edge to the front of the path
1.456 -
1.457 - ///Push a new edge to the front of the path.
1.458 - ///\sa setStart
1.459 - void pushFront(const GraphEdge& e) {
1.460 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.461 - fault("DirPath::Builder::pushFront: nonincident edge");
1.462 - }
1.463 - front.push_back(e);
1.464 - }
1.465 -
1.466 - ///Push a new edge to the back of the path
1.467 -
1.468 - ///Push a new edge to the back of the path.
1.469 - ///\sa setStart
1.470 - void pushBack(const GraphEdge& e) {
1.471 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.472 - fault("DirPath::Builder::pushBack: nonincident edge");
1.473 - }
1.474 - back.push_back(e);
1.475 - }
1.476 -
1.477 - ///Commit the changes to the path.
1.478 - void commit() {
1.479 - if( !(front.empty() && back.empty()) ) {
1.480 - Container tmp;
1.481 - tmp.reserve(front.size()+back.size()+P.length());
1.482 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.483 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.484 - tmp.insert(tmp.end(), back.begin(), back.end());
1.485 - P.edges.swap(tmp);
1.486 - front.clear();
1.487 - back.clear();
1.488 - }
1.489 - }
1.490 -
1.491 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.492 - // Hogy kenyelmes egy ilyet hasznalni?
1.493 -
1.494 - ///Reserve storage in advance for the builder
1.495 -
1.496 - ///If you know an reasonable upper bound of the number of the edges
1.497 - ///to add, using this function you can speed up the building.
1.498 - void reserve(size_t r) {
1.499 - front.reserve(r);
1.500 - back.reserve(r);
1.501 - }
1.502 -
1.503 - private:
1.504 - bool empty() {
1.505 - return front.empty() && back.empty() && P.empty();
1.506 - }
1.507 -
1.508 - GraphNode from() const {
1.509 - if( ! front.empty() )
1.510 - return P.gr->tail(front[front.size()-1]);
1.511 - else if( ! P.empty() )
1.512 - return P.gr->tail(P.edges[0]);
1.513 - else if( ! back.empty() )
1.514 - return P.gr->tail(back[0]);
1.515 - else
1.516 - return INVALID;
1.517 - }
1.518 - GraphNode to() const {
1.519 - if( ! back.empty() )
1.520 - return P.gr->head(back[back.size()-1]);
1.521 - else if( ! P.empty() )
1.522 - return P.gr->head(P.edges[P.length()-1]);
1.523 - else if( ! front.empty() )
1.524 - return P.gr->head(front[0]);
1.525 - else
1.526 - return INVALID;
1.527 - }
1.528 -
1.529 - };
1.530 -
1.531 - };
1.532 -
1.533 -
1.534 -
1.535 -
1.536 -
1.537 -
1.538 -
1.539 -
1.540 -
1.541 -
1.542 - /**********************************************************************/
1.543 -
1.544 -
1.545 - //! \brief A structure for representing undirected path in a graph.
1.546 - //!
1.547 - //! A structure for representing undirected path in a graph. Ie. this is
1.548 - //! a path in a \e directed graph but the edges should not be directed
1.549 - //! forward.
1.550 - //!
1.551 - //! \param Graph The graph type in which the path is.
1.552 - //! \param DM DebugMode, defaults to DefaultDebugMode.
1.553 - //!
1.554 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
1.555 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
1.556 - //! and \c Edge of the original graph.
1.557 - //!
1.558 - //! \todo Thoroughfully check all the range and consistency tests.
1.559 - template<typename Graph, typename DM = DefaultDebugMode>
1.560 - class UndirPath {
1.561 - public:
1.562 - /// Edge type of the underlying graph.
1.563 - typedef typename Graph::Edge GraphEdge;
1.564 - /// Node type of the underlying graph.
1.565 - typedef typename Graph::Node GraphNode;
1.566 - class NodeIt;
1.567 - class EdgeIt;
1.568 -
1.569 - protected:
1.570 - const Graph *gr;
1.571 - typedef std::vector<GraphEdge> Container;
1.572 - Container edges;
1.573 -
1.574 - public:
1.575 -
1.576 - /// \param _G The graph in which the path is.
1.577 - ///
1.578 - UndirPath(const Graph &_G) : gr(&_G) {}
1.579 -
1.580 - /// \brief Subpath constructor.
1.581 - ///
1.582 - /// Subpath defined by two nodes.
1.583 - /// \warning It is an error if the two edges are not in order!
1.584 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
1.585 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.586 - // FIXME: this check should be more elaborate...
1.587 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.588 - }
1.589 - gr = P.gr;
1.590 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.591 - }
1.592 -
1.593 - /// \brief Subpath constructor.
1.594 - ///
1.595 - /// Subpath defined by two edges. Contains edges in [a,b)
1.596 - /// \warning It is an error if the two edges are not in order!
1.597 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
1.598 - if( DM::range_check && (!a.valid() || !b.valid) ) {
1.599 - // FIXME: this check should be more elaborate...
1.600 - fault("UndirPath, subpath ctor: invalid bounding nodes");
1.601 - }
1.602 - gr = P.gr;
1.603 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
1.604 - }
1.605 -
1.606 - /// Length of the path.
1.607 - size_t length() const { return edges.size(); }
1.608 - /// Returns whether the path is empty.
1.609 - bool empty() const { return edges.empty(); }
1.610 -
1.611 - /// Resets the path to an empty path.
1.612 - void clear() { edges.clear(); }
1.613 -
1.614 - /// \brief Starting point of the path.
1.615 - ///
1.616 - /// Starting point of the path.
1.617 - /// Returns INVALID if the path is empty.
1.618 - GraphNode from() const {
1.619 - return empty() ? INVALID : gr->tail(edges[0]);
1.620 - }
1.621 - /// \brief End point of the path.
1.622 - ///
1.623 - /// End point of the path.
1.624 - /// Returns INVALID if the path is empty.
1.625 - GraphNode to() const {
1.626 - return empty() ? INVALID : gr->head(edges[length()-1]);
1.627 - }
1.628 -
1.629 - /// \brief Initializes node or edge iterator to point to the first
1.630 - /// node or edge.
1.631 - ///
1.632 - /// \sa nth
1.633 - template<typename It>
1.634 - It& first(It &i) const { return i=It(*this); }
1.635 -
1.636 - /// \brief Initializes node iterator to point to the node of a given index.
1.637 - NodeIt& nth(NodeIt &i, int n) const {
1.638 - if( DM::range_check && (n<0 || n>int(length())) )
1.639 - fault("UndirPath::nth: index out of range");
1.640 - return i=NodeIt(*this, n);
1.641 - }
1.642 -
1.643 - /// \brief Initializes edge iterator to point to the edge of a given index.
1.644 - EdgeIt& nth(EdgeIt &i, int n) const {
1.645 - if( DM::range_check && (n<0 || n>=int(length())) )
1.646 - fault("UndirPath::nth: index out of range");
1.647 - return i=EdgeIt(*this, n);
1.648 - }
1.649 -
1.650 - /// Checks validity of a node or edge iterator.
1.651 - template<typename It>
1.652 - static
1.653 - bool valid(const It &i) { return i.valid(); }
1.654 -
1.655 - /// Steps the given node or edge iterator.
1.656 - template<typename It>
1.657 - static
1.658 - It& next(It &e) {
1.659 - if( DM::range_check && !e.valid() )
1.660 - fault("UndirPath::next() on invalid iterator");
1.661 - return ++e;
1.662 - }
1.663 -
1.664 - /// \brief Returns node iterator pointing to the head node of the
1.665 - /// given edge iterator.
1.666 - NodeIt head(const EdgeIt& e) const {
1.667 - if( DM::range_check && !e.valid() )
1.668 - fault("UndirPath::head() on invalid iterator");
1.669 - return NodeIt(*this, e.idx+1);
1.670 - }
1.671 -
1.672 - /// \brief Returns node iterator pointing to the tail node of the
1.673 - /// given edge iterator.
1.674 - NodeIt tail(const EdgeIt& e) const {
1.675 - if( DM::range_check && !e.valid() )
1.676 - fault("UndirPath::tail() on invalid iterator");
1.677 - return NodeIt(*this, e.idx);
1.678 - }
1.679 -
1.680 -
1.681 -
1.682 - /**
1.683 - * \brief Iterator class to iterate on the edges of the paths
1.684 - *
1.685 - * \ingroup paths
1.686 - * This class is used to iterate on the edges of the paths
1.687 - *
1.688 - * Of course it converts to Graph::Edge
1.689 - *
1.690 - * \todo Its interface differs from the standard edge iterator.
1.691 - * Yes, it shouldn't.
1.692 - */
1.693 - class EdgeIt {
1.694 - friend class UndirPath;
1.695 -
1.696 - int idx;
1.697 - const UndirPath *p;
1.698 - public:
1.699 - /// Default constructor
1.700 - EdgeIt() {}
1.701 - /// Invalid constructor
1.702 - EdgeIt(Invalid) : idx(-1), p(0) {}
1.703 - /// Constructor with starting point
1.704 - EdgeIt(const UndirPath &_p, int _idx = 0) :
1.705 - idx(_idx), p(&_p) { validate(); }
1.706 -
1.707 - ///Validity check
1.708 - bool valid() const { return idx!=-1; }
1.709 -
1.710 - ///Conversion to Graph::Edge
1.711 - operator GraphEdge () const {
1.712 - return valid() ? p->edges[idx] : INVALID;
1.713 - }
1.714 - /// Next edge
1.715 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.716 -
1.717 - /// Comparison operator
1.718 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.719 - /// Comparison operator
1.720 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.721 - /// Comparison operator
1.722 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.723 -
1.724 - private:
1.725 - // FIXME: comparison between signed and unsigned...
1.726 - // Jo ez igy? Vagy esetleg legyen a length() int?
1.727 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.728 - };
1.729 -
1.730 - /**
1.731 - * \brief Iterator class to iterate on the nodes of the paths
1.732 - *
1.733 - * \ingroup paths
1.734 - * This class is used to iterate on the nodes of the paths
1.735 - *
1.736 - * Of course it converts to Graph::Node
1.737 - *
1.738 - * \todo Its interface differs from the standard node iterator.
1.739 - * Yes, it shouldn't.
1.740 - */
1.741 - class NodeIt {
1.742 - friend class UndirPath;
1.743 -
1.744 - int idx;
1.745 - const UndirPath *p;
1.746 - public:
1.747 - /// Default constructor
1.748 - NodeIt() {}
1.749 - /// Invalid constructor
1.750 - NodeIt(Invalid) : idx(-1), p(0) {}
1.751 - /// Constructor with starting point
1.752 - NodeIt(const UndirPath &_p, int _idx = 0) :
1.753 - idx(_idx), p(&_p) { validate(); }
1.754 -
1.755 - ///Validity check
1.756 - bool valid() const { return idx!=-1; }
1.757 -
1.758 - ///Conversion to Graph::Node
1.759 - operator const GraphNode& () const {
1.760 - if(idx >= p->length())
1.761 - return p->to();
1.762 - else if(idx >= 0)
1.763 - return p->gr->tail(p->edges[idx]);
1.764 - else
1.765 - return INVALID;
1.766 - }
1.767 - /// Next node
1.768 - NodeIt& operator++() { ++idx; validate(); return *this; }
1.769 -
1.770 - /// Comparison operator
1.771 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.772 - /// Comparison operator
1.773 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.774 - /// Comparison operator
1.775 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.776 -
1.777 - private:
1.778 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.779 - };
1.780 -
1.781 - friend class Builder;
1.782 -
1.783 - /**
1.784 - * \brief Class to build paths
1.785 - *
1.786 - * \ingroup paths
1.787 - * This class is used to fill a path with edges.
1.788 - *
1.789 - * You can push new edges to the front and to the back of the path in
1.790 - * arbitrary order then you should commit these changes to the graph.
1.791 - *
1.792 - * Fundamentally, for most "Paths" (classes fulfilling the
1.793 - * PathConcept) while the builder is active (after the first modifying
1.794 - * operation and until the commit()) the original Path is in a
1.795 - * "transitional" state (operations ot it have undefined result). But
1.796 - * in the case of UndirPath the original path is unchanged until the
1.797 - * commit. However we don't recomend that you use this feature.
1.798 - */
1.799 - class Builder {
1.800 - UndirPath &P;
1.801 - Container front, back;
1.802 -
1.803 - public:
1.804 - ///\param _P the path you want to fill in.
1.805 - ///
1.806 - Builder(UndirPath &_P) : P(_P) {}
1.807 -
1.808 - /// Sets the starting node of the path.
1.809 -
1.810 - /// Sets the starting node of the path. Edge added to the path
1.811 - /// afterwards have to be incident to this node.
1.812 - /// It should be called iff the path is empty and before any call to
1.813 - /// \ref pushFront() or \ref pushBack()
1.814 - void setStart(const GraphNode &) {}
1.815 -
1.816 - ///Push a new edge to the front of the path
1.817 -
1.818 - ///Push a new edge to the front of the path.
1.819 - ///\sa setStart
1.820 - void pushFront(const GraphEdge& e) {
1.821 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
1.822 - fault("UndirPath::Builder::pushFront: nonincident edge");
1.823 - }
1.824 - front.push_back(e);
1.825 - }
1.826 -
1.827 - ///Push a new edge to the back of the path
1.828 -
1.829 - ///Push a new edge to the back of the path.
1.830 - ///\sa setStart
1.831 - void pushBack(const GraphEdge& e) {
1.832 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
1.833 - fault("UndirPath::Builder::pushBack: nonincident edge");
1.834 - }
1.835 - back.push_back(e);
1.836 - }
1.837 -
1.838 - ///Commit the changes to the path.
1.839 - void commit() {
1.840 - if( !(front.empty() && back.empty()) ) {
1.841 - Container tmp;
1.842 - tmp.reserve(front.size()+back.size()+P.length());
1.843 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
1.844 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
1.845 - tmp.insert(tmp.end(), back.begin(), back.end());
1.846 - P.edges.swap(tmp);
1.847 - front.clear();
1.848 - back.clear();
1.849 - }
1.850 - }
1.851 -
1.852 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.853 - // Hogy kenyelmes egy ilyet hasznalni?
1.854 -
1.855 - ///Reserve storage in advance for the builder
1.856 -
1.857 - ///If you know an reasonable upper bound of the number of the edges
1.858 - ///to add, using this function you can speed up the building.
1.859 - void reserve(size_t r) {
1.860 - front.reserve(r);
1.861 - back.reserve(r);
1.862 - }
1.863 -
1.864 - private:
1.865 - bool empty() {
1.866 - return front.empty() && back.empty() && P.empty();
1.867 - }
1.868 -
1.869 - GraphNode from() const {
1.870 - if( ! front.empty() )
1.871 - return P.gr->tail(front[front.size()-1]);
1.872 - else if( ! P.empty() )
1.873 - return P.gr->tail(P.edges[0]);
1.874 - else if( ! back.empty() )
1.875 - return P.gr->tail(back[0]);
1.876 - else
1.877 - return INVALID;
1.878 - }
1.879 - GraphNode to() const {
1.880 - if( ! back.empty() )
1.881 - return P.gr->head(back[back.size()-1]);
1.882 - else if( ! P.empty() )
1.883 - return P.gr->head(P.edges[P.length()-1]);
1.884 - else if( ! front.empty() )
1.885 - return P.gr->head(front[0]);
1.886 - else
1.887 - return INVALID;
1.888 - }
1.889 -
1.890 - };
1.891 -
1.892 - };
1.893 -
1.894 -
1.895 -
1.896 -
1.897 -
1.898 -
1.899 -
1.900 -
1.901 -
1.902 -
1.903 - /**********************************************************************/
1.904 -
1.905 -
1.906 - /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
1.907 - elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
1.908 -
1.909 - template<typename Graph>
1.910 - class DynamicPath {
1.911 -
1.912 - public:
1.913 - typedef typename Graph::Edge GraphEdge;
1.914 - typedef typename Graph::Node GraphNode;
1.915 - class NodeIt;
1.916 - class EdgeIt;
1.917 -
1.918 - protected:
1.919 - Graph& G;
1.920 - // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
1.921 - // iranyitasat:
1.922 - GraphNode _first, _last;
1.923 - typedef std::deque<GraphEdge> Container;
1.924 - Container edges;
1.925 -
1.926 - public:
1.927 -
1.928 - DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
1.929 -
1.930 - /// Subpath defined by two nodes.
1.931 - /// Nodes may be in reversed order, then
1.932 - /// we contstruct the reversed path.
1.933 - DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
1.934 - /// Subpath defined by two edges. Contains edges in [a,b)
1.935 - /// It is an error if the two edges are not in order!
1.936 - DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
1.937 -
1.938 - size_t length() const { return edges.size(); }
1.939 - GraphNode from() const { return _first; }
1.940 - GraphNode to() const { return _last; }
1.941 -
1.942 - NodeIt& first(NodeIt &n) const { return nth(n, 0); }
1.943 - EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
1.944 - template<typename It>
1.945 - It first() const {
1.946 - It e;
1.947 - first(e);
1.948 - return e;
1.949 - }
1.950 -
1.951 - NodeIt& nth(NodeIt &, size_t) const;
1.952 - EdgeIt& nth(EdgeIt &, size_t) const;
1.953 - template<typename It>
1.954 - It nth(size_t n) const {
1.955 - It e;
1.956 - nth(e, n);
1.957 - return e;
1.958 - }
1.959 -
1.960 - bool valid(const NodeIt &n) const { return n.idx <= length(); }
1.961 - bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
1.962 -
1.963 - bool isForward(const EdgeIt &e) const { return e.forw; }
1.964 -
1.965 - /// index of a node on the path. Returns length+2 for the invalid NodeIt
1.966 - int index(const NodeIt &n) const { return n.idx; }
1.967 - /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
1.968 - int index(const EdgeIt &e) const { return e.it - edges.begin(); }
1.969 -
1.970 - EdgeIt& next(EdgeIt &e) const;
1.971 - NodeIt& next(NodeIt &n) const;
1.972 - template <typename It>
1.973 - It getNext(It it) const {
1.974 - It tmp(it); return next(tmp);
1.975 - }
1.976 -
1.977 - // A path is constructed using the following four functions.
1.978 - // They return false if the requested operation is inconsistent
1.979 - // with the path constructed so far.
1.980 - // If your path has only one edge you MUST set either "from" or "to"!
1.981 - // So you probably SHOULD call it in any case to be safe (and check the
1.982 - // returned value to check if your path is consistent with your idea).
1.983 - bool pushFront(const GraphEdge &e);
1.984 - bool pushBack(const GraphEdge &e);
1.985 - bool setFrom(const GraphNode &n);
1.986 - bool setTo(const GraphNode &n);
1.987 -
1.988 - // WARNING: these two functions return the head/tail of an edge with
1.989 - // respect to the direction of the path!
1.990 - // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
1.991 - // P.forward(e) is true (or the edge is a loop)!
1.992 - NodeIt head(const EdgeIt& e) const;
1.993 - NodeIt tail(const EdgeIt& e) const;
1.994 -
1.995 - // FIXME: ezeknek valami jobb nev kellene!!!
1.996 - GraphEdge graphEdge(const EdgeIt& e) const;
1.997 - GraphNode graphNode(const NodeIt& n) const;
1.998 -
1.999 -
1.1000 - /*** Iterator classes ***/
1.1001 - class EdgeIt {
1.1002 - friend class DynamicPath;
1.1003 -
1.1004 - typename Container::const_iterator it;
1.1005 - bool forw;
1.1006 - public:
1.1007 - // FIXME: jarna neki ilyen is...
1.1008 - // EdgeIt(Invalid);
1.1009 -
1.1010 - bool forward() const { return forw; }
1.1011 -
1.1012 - bool operator==(const EdgeIt& e) const { return it==e.it; }
1.1013 - bool operator!=(const EdgeIt& e) const { return it!=e.it; }
1.1014 - bool operator<(const EdgeIt& e) const { return it<e.it; }
1.1015 - };
1.1016 -
1.1017 - class NodeIt {
1.1018 - friend class DynamicPath;
1.1019 -
1.1020 - size_t idx;
1.1021 - bool tail; // Is this node the tail of the edge with same idx?
1.1022 -
1.1023 - public:
1.1024 - // FIXME: jarna neki ilyen is...
1.1025 - // NodeIt(Invalid);
1.1026 -
1.1027 - bool operator==(const NodeIt& n) const { return idx==n.idx; }
1.1028 - bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
1.1029 - bool operator<(const NodeIt& n) const { return idx<n.idx; }
1.1030 - };
1.1031 -
1.1032 - private:
1.1033 - bool edgeIncident(const GraphEdge &e, const GraphNode &a,
1.1034 - GraphNode &b);
1.1035 - bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
1.1036 - };
1.1037 -
1.1038 - template<typename Gr>
1.1039 - typename DynamicPath<Gr>::EdgeIt&
1.1040 - DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
1.1041 - if( e.it == edges.end() )
1.1042 - return e;
1.1043 -
1.1044 - GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
1.1045 - ++e.it;
1.1046 -
1.1047 - // Invalid edgeit is always forward :)
1.1048 - if( e.it == edges.end() ) {
1.1049 - e.forw = true;
1.1050 - return e;
1.1051 - }
1.1052 -
1.1053 - e.forw = ( G.tail(*e.it) == common_node );
1.1054 - return e;
1.1055 - }
1.1056 -
1.1057 - template<typename Gr>
1.1058 - typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
1.1059 - if( n.idx >= length() ) {
1.1060 - // FIXME: invalid
1.1061 - n.idx = length()+1;
1.1062 - return n;
1.1063 - }
1.1064 -
1.1065 -
1.1066 - GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
1.1067 - G.tail(edges[n.idx]) );
1.1068 - ++n.idx;
1.1069 - if( n.idx < length() ) {
1.1070 - n.tail = ( next_node == G.tail(edges[n.idx]) );
1.1071 - }
1.1072 - else {
1.1073 - n.tail = true;
1.1074 - }
1.1075 -
1.1076 - return n;
1.1077 - }
1.1078 -
1.1079 - template<typename Gr>
1.1080 - bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
1.1081 - GraphNode &b) {
1.1082 - if( G.tail(e) == a ) {
1.1083 - b=G.head(e);
1.1084 - return true;
1.1085 - }
1.1086 - if( G.head(e) == a ) {
1.1087 - b=G.tail(e);
1.1088 - return true;
1.1089 - }
1.1090 - return false;
1.1091 - }
1.1092 -
1.1093 - template<typename Gr>
1.1094 - bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
1.1095 - const GraphEdge &f) {
1.1096 - if( edgeIncident(f, G.tail(e), _last) ) {
1.1097 - _first = G.head(e);
1.1098 - return true;
1.1099 - }
1.1100 - if( edgeIncident(f, G.head(e), _last) ) {
1.1101 - _first = G.tail(e);
1.1102 - return true;
1.1103 - }
1.1104 - return false;
1.1105 - }
1.1106 -
1.1107 - template<typename Gr>
1.1108 - bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
1.1109 - if( G.valid(_first) ) {
1.1110 - if( edgeIncident(e, _first, _first) ) {
1.1111 - edges.push_front(e);
1.1112 - return true;
1.1113 - }
1.1114 - else
1.1115 - return false;
1.1116 - }
1.1117 - else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
1.1118 - edges.push_front(e);
1.1119 - return true;
1.1120 - }
1.1121 - else
1.1122 - return false;
1.1123 - }
1.1124 -
1.1125 - template<typename Gr>
1.1126 - bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
1.1127 - if( G.valid(_last) ) {
1.1128 - if( edgeIncident(e, _last, _last) ) {
1.1129 - edges.push_back(e);
1.1130 - return true;
1.1131 - }
1.1132 - else
1.1133 - return false;
1.1134 - }
1.1135 - else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
1.1136 - edges.push_back(e);
1.1137 - return true;
1.1138 - }
1.1139 - else
1.1140 - return false;
1.1141 - }
1.1142 -
1.1143 -
1.1144 - template<typename Gr>
1.1145 - bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
1.1146 - if( G.valid(_first) ) {
1.1147 - return _first == n;
1.1148 - }
1.1149 - else {
1.1150 - if( length() > 0) {
1.1151 - if( edgeIncident(edges[0], n, _last) ) {
1.1152 - _first = n;
1.1153 - return true;
1.1154 - }
1.1155 - else return false;
1.1156 - }
1.1157 - else {
1.1158 - _first = _last = n;
1.1159 - return true;
1.1160 - }
1.1161 - }
1.1162 - }
1.1163 -
1.1164 - template<typename Gr>
1.1165 - bool DynamicPath<Gr>::setTo(const GraphNode &n) {
1.1166 - if( G.valid(_last) ) {
1.1167 - return _last == n;
1.1168 - }
1.1169 - else {
1.1170 - if( length() > 0) {
1.1171 - if( edgeIncident(edges[0], n, _first) ) {
1.1172 - _last = n;
1.1173 - return true;
1.1174 - }
1.1175 - else return false;
1.1176 - }
1.1177 - else {
1.1178 - _first = _last = n;
1.1179 - return true;
1.1180 - }
1.1181 - }
1.1182 - }
1.1183 -
1.1184 -
1.1185 - template<typename Gr>
1.1186 - typename DynamicPath<Gr>::NodeIt
1.1187 - DynamicPath<Gr>::tail(const EdgeIt& e) const {
1.1188 - NodeIt n;
1.1189 -
1.1190 - if( e.it == edges.end() ) {
1.1191 - // FIXME: invalid-> invalid
1.1192 - n.idx = length() + 1;
1.1193 - n.tail = true;
1.1194 - return n;
1.1195 - }
1.1196 -
1.1197 - n.idx = e.it-edges.begin();
1.1198 - n.tail = e.forw;
1.1199 - return n;
1.1200 - }
1.1201 -
1.1202 - template<typename Gr>
1.1203 - typename DynamicPath<Gr>::NodeIt
1.1204 - DynamicPath<Gr>::head(const EdgeIt& e) const {
1.1205 - if( e.it == edges.end()-1 ) {
1.1206 - return _last;
1.1207 - }
1.1208 -
1.1209 - EdgeIt next_edge = e;
1.1210 - next(next_edge);
1.1211 - return tail(next_edge);
1.1212 - }
1.1213 -
1.1214 - template<typename Gr>
1.1215 - typename DynamicPath<Gr>::GraphEdge
1.1216 - DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
1.1217 - if( e.it != edges.end() ) {
1.1218 - return *e.it;
1.1219 - }
1.1220 - else {
1.1221 - return INVALID;
1.1222 - }
1.1223 + ///@}
1.1224 }
1.1225
1.1226 - template<typename Gr>
1.1227 - typename DynamicPath<Gr>::GraphNode
1.1228 - DynamicPath<Gr>::graphNode(const NodeIt& n) const {
1.1229 - if( n.idx < length() ) {
1.1230 - return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
1.1231 - }
1.1232 - else if( n.idx == length() ) {
1.1233 - return _last;
1.1234 - }
1.1235 - else {
1.1236 - return INVALID;
1.1237 - }
1.1238 - }
1.1239 -
1.1240 - template<typename Gr>
1.1241 - typename DynamicPath<Gr>::EdgeIt&
1.1242 - DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
1.1243 - if( k>=length() ) {
1.1244 - // FIXME: invalid EdgeIt
1.1245 - e.it = edges.end();
1.1246 - e.forw = true;
1.1247 - return e;
1.1248 - }
1.1249 -
1.1250 - e.it = edges.begin()+k;
1.1251 - if(k==0) {
1.1252 - e.forw = ( G.tail(*e.it) == _first );
1.1253 - }
1.1254 - else {
1.1255 - e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
1.1256 - G.tail(*e.it) == G.head(edges[k-1]) );
1.1257 - }
1.1258 - return e;
1.1259 - }
1.1260 -
1.1261 - template<typename Gr>
1.1262 - typename DynamicPath<Gr>::NodeIt&
1.1263 - DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
1.1264 - if( k>length() ) {
1.1265 - // FIXME: invalid NodeIt
1.1266 - n.idx = length()+1;
1.1267 - n.tail = true;
1.1268 - return n;
1.1269 - }
1.1270 - if( k==length() ) {
1.1271 - n.idx = length();
1.1272 - n.tail = true;
1.1273 - return n;
1.1274 - }
1.1275 - n = tail(nth<EdgeIt>(k));
1.1276 - return n;
1.1277 - }
1.1278 -
1.1279 - // Reszut konstruktorok:
1.1280 -
1.1281 -
1.1282 - template<typename Gr>
1.1283 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
1.1284 - const EdgeIt &b) :
1.1285 - G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
1.1286 - {
1.1287 - if( G.valid(P._first) && a.it < P.edges.end() ) {
1.1288 - _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
1.1289 - if( b.it < P.edges.end() ) {
1.1290 - _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
1.1291 - }
1.1292 - else {
1.1293 - _last = P._last;
1.1294 - }
1.1295 - }
1.1296 - }
1.1297 -
1.1298 - template<typename Gr>
1.1299 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
1.1300 - const NodeIt &b) : G(P.G)
1.1301 - {
1.1302 - if( !P.valid(a) || !P.valid(b) )
1.1303 - return;
1.1304 -
1.1305 - int ai = a.idx, bi = b.idx;
1.1306 - if( bi<ai )
1.1307 - std::swap(ai,bi);
1.1308 -
1.1309 - edges.resize(bi-ai);
1.1310 - copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
1.1311 -
1.1312 - _first = P.graphNode(a);
1.1313 - _last = P.graphNode(b);
1.1314 - }
1.1315 -
1.1316 - ///@}
1.1317 -
1.1318 } // namespace hugo
1.1319
1.1320 #endif // HUGO_PATH_H
2.1 --- a/src/work/klao/path.h Sun Sep 05 20:11:47 2004 +0000
2.2 +++ b/src/work/klao/path.h Sun Sep 05 20:13:48 2004 +0000
2.3 @@ -303,12 +303,12 @@
2.4 /// afterwards have to be incident to this node.
2.5 /// It should be called iff the path is empty and before any call to
2.6 /// \ref pushFront() or \ref pushBack()
2.7 - void setStart(const GraphNode &) {}
2.8 + void setStartNode(const GraphNode &) {}
2.9
2.10 ///Push a new edge to the front of the path
2.11
2.12 ///Push a new edge to the front of the path.
2.13 - ///\sa setStart
2.14 + ///\sa setStartNode
2.15 void pushFront(const GraphEdge& e) {
2.16 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.17 fault("DirPath::Builder::pushFront: nonincident edge");
2.18 @@ -319,7 +319,7 @@
2.19 ///Push a new edge to the back of the path
2.20
2.21 ///Push a new edge to the back of the path.
2.22 - ///\sa setStart
2.23 + ///\sa setStartNode
2.24 void pushBack(const GraphEdge& e) {
2.25 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.26 fault("DirPath::Builder::pushBack: nonincident edge");
2.27 @@ -344,7 +344,7 @@
2.28 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.29 // Hogy kenyelmes egy ilyet hasznalni?
2.30
2.31 - ///Reserve storage in advance for the builder
2.32 + ///Reserve storage for the builder in advance.
2.33
2.34 ///If you know an reasonable upper bound of the number of the edges
2.35 ///to add, using this function you can speed up the building.
2.36 @@ -664,12 +664,12 @@
2.37 /// afterwards have to be incident to this node.
2.38 /// It should be called iff the path is empty and before any call to
2.39 /// \ref pushFront() or \ref pushBack()
2.40 - void setStart(const GraphNode &) {}
2.41 + void setStartNode(const GraphNode &) {}
2.42
2.43 ///Push a new edge to the front of the path
2.44
2.45 ///Push a new edge to the front of the path.
2.46 - ///\sa setStart
2.47 + ///\sa setStartNode
2.48 void pushFront(const GraphEdge& e) {
2.49 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.50 fault("UndirPath::Builder::pushFront: nonincident edge");
2.51 @@ -680,7 +680,7 @@
2.52 ///Push a new edge to the back of the path
2.53
2.54 ///Push a new edge to the back of the path.
2.55 - ///\sa setStart
2.56 + ///\sa setStartNode
2.57 void pushBack(const GraphEdge& e) {
2.58 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.59 fault("UndirPath::Builder::pushBack: nonincident edge");
2.60 @@ -705,7 +705,7 @@
2.61 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.62 // Hogy kenyelmes egy ilyet hasznalni?
2.63
2.64 - ///Reserve storage in advance for the builder
2.65 + ///Reserve storage for the builder in advance.
2.66
2.67 ///If you know an reasonable upper bound of the number of the edges
2.68 ///to add, using this function you can speed up the building.