# HG changeset patch
# User alpar
# Date 1087379070 0
# Node ID fc8a3393e0d91c18cff8a56b6e3e0e916392d79e
# Parent c7e37b0660333e268d669830a274dca9cd0a96c2
src/work/alpar/path.h (docs) is merged into src/work/klao/path.h
(and removed)
diff -r c7e37b066033 -r fc8a3393e0d9 src/work/alpar/path.h
--- a/src/work/alpar/path.h Tue Jun 15 06:30:03 2004 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,748 +0,0 @@
-// -*- c++ -*- //
-
-/**
-@defgroup paths Path Structures
-@ingroup datas
-\brief Path structures implemented in Hugo.
-
-Hugolib provides flexible data structures
-to work with paths.
-
-All of them have the same interface, especially they can be built or extended
-using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
-algorithm to store its result in any kind of path structure.
-
-*/
-
-///\ingroup paths
-///\file
-///\brief Classes for representing paths in graphs.
-
-#ifndef HUGO_PATH_H
-#define HUGO_PATH_H
-
-#include <deque>
-#include <vector>
-#include <algorithm>
-
-#include <hugo/invalid.h>
-#include <hugo/error.h>
-#include <debug.h>
-
-namespace hugo {
-
- /// \addtogroup paths
- /// @{
-
-
- //! \brief A structure for representing directed path in a graph.
- //!
- //! A structure for representing directed path in a graph.
- //! \param Graph The graph type in which the path is.
- //! \param DM DebugMode, defaults to DefaultDebugMode.
- //!
- //! In a sense, the path can be treated as a graph, for is has \c NodeIt
- //! and \c EdgeIt with the same usage. These types converts to the \c Node
- //! and \c Edge of the original graph.
- //!
- //! \todo Thoroughfully check all the range and consistency tests.
- template<typename Graph, typename DM = DefaultDebugMode>
- class DirPath {
- public:
- /// Edge type of the underlying graph.
- typedef typename Graph::Edge GraphEdge;
- /// Node type of the underlying graph.
- typedef typename Graph::Node GraphNode;
- class NodeIt;
- class EdgeIt;
-
- protected:
- const Graph *gr;
- typedef std::vector<GraphEdge> Container;
- Container edges;
-
- public:
-
- /// \param _G The graph in which the path is.
- ///
- DirPath(const Graph &_G) : gr(&_G) {}
-
- /// \brief Subpath constructor.
- ///
- /// Subpath defined by two nodes.
- /// \warning It is an error if the two edges are not in order!
- DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
- if( DM::range_check && (!a.valid() || !b.valid) ) {
- // FIXME: this check should be more elaborate...
- fault("DirPath, subpath ctor: invalid bounding nodes");
- }
- gr = P.gr;
- edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
- }
-
- /// \brief Subpath constructor.
- ///
- /// Subpath defined by two edges. Contains edges in [a,b)
- /// \warning It is an error if the two edges are not in order!
- DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
- if( DM::range_check && (!a.valid() || !b.valid) ) {
- // FIXME: this check should be more elaborate...
- fault("DirPath, subpath ctor: invalid bounding nodes");
- }
- gr = P.gr;
- edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
- }
-
- /// Length of the path.
- size_t length() const { return edges.size(); }
- /// Returns whether the path is empty.
- bool empty() const { return edges.empty(); }
-
- /// Resets the path to an empty path.
- void clear() { edges.clear(); }
-
- /// \brief Starting point of the path.
- ///
- /// Starting point of the path.
- /// Returns INVALID if the path is empty.
- GraphNode from() const {
- return empty() ? INVALID : gr->tail(edges[0]);
- }
- /// \brief End point of the path.
- ///
- /// End point of the path.
- /// Returns INVALID if the path is empty.
- GraphNode to() const {
- return empty() ? INVALID : gr->head(edges[length()-1]);
- }
-
- /// \brief Initializes node or edge iterator to point to the first
- /// node or edge.
- ///
- /// \sa nth
- template<typename It>
- It& first(It &i) const { return i=It(*this); }
-
- /// \brief Initializes node iterator to point to the node of a given index.
- NodeIt& nth(NodeIt &i, int n) const {
- if( DM::range_check && (n<0 || n>int(length())) )
- fault("DirPath::nth: index out of range");
- return i=NodeIt(*this, n);
- }
-
- /// \brief Initializes edge iterator to point to the edge of a given index.
- EdgeIt& nth(EdgeIt &i, int n) const {
- if( DM::range_check && (n<0 || n>=int(length())) )
- fault("DirPath::nth: index out of range");
- return i=EdgeIt(*this, n);
- }
-
- /// Checks validity of a node or edge iterator.
- template<typename It>
- static
- bool valid(const It &i) { return i.valid(); }
-
- /// Steps the given node or edge iterator.
- template<typename It>
- static
- It& next(It &e) {
- if( DM::range_check && !e.valid() )
- fault("DirPath::next() on invalid iterator");
- return ++e;
- }
-
- /// \brief Returns node iterator pointing to the head node of the
- /// given edge iterator.
- NodeIt head(const EdgeIt& e) const {
- if( DM::range_check && !e.valid() )
- fault("DirPath::head() on invalid iterator");
- return NodeIt(*this, e.idx+1);
- }
-
- /// \brief Returns node iterator pointing to the tail node of the
- /// given edge iterator.
- NodeIt tail(const EdgeIt& e) const {
- if( DM::range_check && !e.valid() )
- fault("DirPath::tail() on invalid iterator");
- return NodeIt(*this, e.idx);
- }
-
-
- /* Iterator classes */
-
- /**
- * \brief Iterator class to iterate on the edges of the paths
- *
- * \ingroup paths
- * This class is used to iterate on the edges of the paths
- *
- * Of course it converts to Graph::Edge
- *
- * \todo Its interface differs from the standard edge iterator.
- * Yes, it shouldn't.
- */
- class EdgeIt {
- friend class DirPath;
-
- int idx;
- const DirPath *p;
- public:
- /// Default constructor
- EdgeIt() {}
- /// Invalid constructor
- EdgeIt(Invalid) : idx(-1), p(0) {}
- /// Constructor with starting point
- EdgeIt(const DirPath &_p, int _idx = 0) :
- idx(_idx), p(&_p) { validate(); }
-
- ///Validity check
- bool valid() const { return idx!=-1; }
-
- ///Conversion to Graph::Edge
- operator GraphEdge () const {
- return valid() ? p->edges[idx] : INVALID;
- }
-
- /// Next edge
- EdgeIt& operator++() { ++idx; validate(); return *this; }
-
- /// Comparison operator
- bool operator==(const EdgeIt& e) const { return idx==e.idx; }
- /// Comparison operator
- bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
- /// Comparison operator
- bool operator<(const EdgeIt& e) const { return idx<e.idx; }
-
- private:
- // FIXME: comparison between signed and unsigned...
- // Jo ez igy? Vagy esetleg legyen a length() int?
- void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
- };
-
- /**
- * \brief Iterator class to iterate on the nodes of the paths
- *
- * \ingroup paths
- * This class is used to iterate on the nodes of the paths
- *
- * Of course it converts to Graph::Node
- *
- * \todo Its interface differs from the standard node iterator.
- * Yes, it shouldn't.
- */
- class NodeIt {
- friend class DirPath;
-
- int idx;
- const DirPath *p;
- public:
- /// Default constructor
- NodeIt() {}
- /// Invalid constructor
- NodeIt(Invalid) : idx(-1), p(0) {}
- /// Constructor with starting point
- NodeIt(const DirPath &_p, int _idx = 0) :
- idx(_idx), p(&_p) { validate(); }
-
- ///Validity check
- bool valid() const { return idx!=-1; }
-
- ///Conversion to Graph::Node
- operator const GraphNode& () const {
- if(idx >= p->length())
- return p->to();
- else if(idx >= 0)
- return p->gr->tail(p->edges[idx]);
- else
- return INVALID;
- }
- /// Next node
- NodeIt& operator++() { ++idx; validate(); return *this; }
-
- /// Comparison operator
- bool operator==(const NodeIt& e) const { return idx==e.idx; }
- /// Comparison operator
- bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
- /// Comparison operator
- bool operator<(const NodeIt& e) const { return idx<e.idx; }
-
- private:
- void validate() { if( size_t(idx) > p->length() ) idx=-1; }
- };
-
- friend class Builder;
-
- /**
- * \brief Class to build paths
- *
- * \ingroup paths
- * This class is used to fill a path with edges.
- *
- * You can push new edges to the front and to the back of the path in
- * arbitrary order then you should commit these changes to the graph.
- *
- * Fundamentally, for most "Paths" (classes fulfilling the
- * PathConcept) while the builder is active (after the first modifying
- * operation and until the commit()) the original Path is in a
- * "transitional" state (operations on it have undefined result). But
- * in the case of DirPath the original path remains unchanged until the
- * commit. However we don't recomend that you use this feature.
- */
- class Builder {
- DirPath &P;
- Container front, back;
-
- public:
- ///\param _P the path you want to fill in.
- ///
- Builder(DirPath &_P) : P(_P) {}
-
- /// Sets the starting node of the path.
-
- /// Sets the starting node of the path. Edge added to the path
- /// afterwards have to be incident to this node.
- /// It should be called iff the path is empty and before any call to
- /// \ref pushFront() or \ref pushBack()
- void setStart(const GraphNode &) {}
-
- ///Push a new edge to the front of the path
-
- ///Push a new edge to the front of the path.
- ///\sa setStart
- void pushFront(const GraphEdge& e) {
- if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
- fault("DirPath::Builder::pushFront: nonincident edge");
- }
- front.push_back(e);
- }
-
- ///Push a new edge to the back of the path
-
- ///Push a new edge to the back of the path.
- ///\sa setStart
- void pushBack(const GraphEdge& e) {
- if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
- fault("DirPath::Builder::pushBack: nonincident edge");
- }
- back.push_back(e);
- }
-
- ///Commit the changes to the path.
- void commit() {
- if( !(front.empty() && back.empty()) ) {
- Container tmp;
- tmp.reserve(front.size()+back.size()+P.length());
- tmp.insert(tmp.end(), front.rbegin(), front.rend());
- tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
- tmp.insert(tmp.end(), back.begin(), back.end());
- P.edges.swap(tmp);
- front.clear();
- back.clear();
- }
- }
-
- // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
- // Hogy kenyelmes egy ilyet hasznalni?
-
- ///Reserve storage in advance for the builder
-
- ///If you know an reasonable upper bound of the number of the edges
- ///to add, using this function you can speed up the building.
- void reserve(size_t r) {
- front.reserve(r);
- back.reserve(r);
- }
-
- private:
- bool empty() {
- return front.empty() && back.empty() && P.empty();
- }
-
- GraphNode from() const {
- if( ! front.empty() )
- return P.gr->tail(front[front.size()-1]);
- else if( ! P.empty() )
- return P.gr->tail(P.edges[0]);
- else if( ! back.empty() )
- return P.gr->tail(back[0]);
- else
- return INVALID;
- }
- GraphNode to() const {
- if( ! back.empty() )
- return P.gr->head(back[back.size()-1]);
- else if( ! P.empty() )
- return P.gr->head(P.edges[P.length()-1]);
- else if( ! front.empty() )
- return P.gr->head(front[0]);
- else
- return INVALID;
- }
-
- };
-
- };
-
-
-
-
-
-
- /**********************************************************************/
-
-
- //! \brief A structure for representing undirected path in a graph.
- //!
- //! A structure for representing undirected path in a graph. Ie. this is
- //! a path in a \e directed graph but the edges should not be directed
- //! forward.
- //!
- //! \param Graph The graph type in which the path is.
- //! \param DM DebugMode, defaults to DefaultDebugMode.
- //!
- //! In a sense, the path can be treated as a graph, for is has \c NodeIt
- //! and \c EdgeIt with the same usage. These types converts to the \c Node
- //! and \c Edge of the original graph.
- //!
- //! \todo Thoroughfully check all the range and consistency tests.
- template<typename Graph, typename DM = DefaultDebugMode>
- class UndirPath {
- public:
- /// Edge type of the underlying graph.
- typedef typename Graph::Edge GraphEdge;
- /// Node type of the underlying graph.
- typedef typename Graph::Node GraphNode;
- class NodeIt;
- class EdgeIt;
-
- protected:
- const Graph *gr;
- typedef std::vector<GraphEdge> Container;
- Container edges;
-
- public:
-
- /// \param _G The graph in which the path is.
- ///
- UndirPath(const Graph &_G) : gr(&_G) {}
-
- /// \brief Subpath constructor.
- ///
- /// Subpath defined by two nodes.
- /// \warning It is an error if the two edges are not in order!
- UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
- if( DM::range_check && (!a.valid() || !b.valid) ) {
- // FIXME: this check should be more elaborate...
- fault("UndirPath, subpath ctor: invalid bounding nodes");
- }
- gr = P.gr;
- edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
- }
-
- /// \brief Subpath constructor.
- ///
- /// Subpath defined by two edges. Contains edges in [a,b)
- /// \warning It is an error if the two edges are not in order!
- UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
- if( DM::range_check && (!a.valid() || !b.valid) ) {
- // FIXME: this check should be more elaborate...
- fault("UndirPath, subpath ctor: invalid bounding nodes");
- }
- gr = P.gr;
- edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
- }
-
- /// Length of the path.
- size_t length() const { return edges.size(); }
- /// Returns whether the path is empty.
- bool empty() const { return edges.empty(); }
-
- /// Resets the path to an empty path.
- void clear() { edges.clear(); }
-
- /// \brief Starting point of the path.
- ///
- /// Starting point of the path.
- /// Returns INVALID if the path is empty.
- GraphNode from() const {
- return empty() ? INVALID : gr->tail(edges[0]);
- }
- /// \brief End point of the path.
- ///
- /// End point of the path.
- /// Returns INVALID if the path is empty.
- GraphNode to() const {
- return empty() ? INVALID : gr->head(edges[length()-1]);
- }
-
- /// \brief Initializes node or edge iterator to point to the first
- /// node or edge.
- ///
- /// \sa nth
- template<typename It>
- It& first(It &i) const { return i=It(*this); }
-
- /// \brief Initializes node iterator to point to the node of a given index.
- NodeIt& nth(NodeIt &i, int n) const {
- if( DM::range_check && (n<0 || n>int(length())) )
- fault("UndirPath::nth: index out of range");
- return i=NodeIt(*this, n);
- }
-
- /// \brief Initializes edge iterator to point to the edge of a given index.
- EdgeIt& nth(EdgeIt &i, int n) const {
- if( DM::range_check && (n<0 || n>=int(length())) )
- fault("UndirPath::nth: index out of range");
- return i=EdgeIt(*this, n);
- }
-
- /// Checks validity of a node or edge iterator.
- template<typename It>
- static
- bool valid(const It &i) { return i.valid(); }
-
- /// Steps the given node or edge iterator.
- template<typename It>
- static
- It& next(It &e) {
- if( DM::range_check && !e.valid() )
- fault("UndirPath::next() on invalid iterator");
- return ++e;
- }
-
- /// \brief Returns node iterator pointing to the head node of the
- /// given edge iterator.
- NodeIt head(const EdgeIt& e) const {
- if( DM::range_check && !e.valid() )
- fault("UndirPath::head() on invalid iterator");
- return NodeIt(*this, e.idx+1);
- }
-
- /// \brief Returns node iterator pointing to the tail node of the
- /// given edge iterator.
- NodeIt tail(const EdgeIt& e) const {
- if( DM::range_check && !e.valid() )
- fault("UndirPath::tail() on invalid iterator");
- return NodeIt(*this, e.idx);
- }
-
-
-
- /**
- * \brief Iterator class to iterate on the edges of the paths
- *
- * \ingroup paths
- * This class is used to iterate on the edges of the paths
- *
- * Of course it converts to Graph::Edge
- *
- * \todo Its interface differs from the standard edge iterator.
- * Yes, it shouldn't.
- */
- class EdgeIt {
- friend class UndirPath;
-
- int idx;
- const UndirPath *p;
- public:
- /// Default constructor
- EdgeIt() {}
- /// Invalid constructor
- EdgeIt(Invalid) : idx(-1), p(0) {}
- /// Constructor with starting point
- EdgeIt(const UndirPath &_p, int _idx = 0) :
- idx(_idx), p(&_p) { validate(); }
-
- ///Validity check
- bool valid() const { return idx!=-1; }
-
- ///Conversion to Graph::Edge
- operator GraphEdge () const {
- return valid() ? p->edges[idx] : INVALID;
- }
- /// Next edge
- EdgeIt& operator++() { ++idx; validate(); return *this; }
-
- /// Comparison operator
- bool operator==(const EdgeIt& e) const { return idx==e.idx; }
- /// Comparison operator
- bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
- /// Comparison operator
- bool operator<(const EdgeIt& e) const { return idx<e.idx; }
-
- private:
- // FIXME: comparison between signed and unsigned...
- // Jo ez igy? Vagy esetleg legyen a length() int?
- void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
- };
-
- /**
- * \brief Iterator class to iterate on the nodes of the paths
- *
- * \ingroup paths
- * This class is used to iterate on the nodes of the paths
- *
- * Of course it converts to Graph::Node
- *
- * \todo Its interface differs from the standard node iterator.
- * Yes, it shouldn't.
- */
- class NodeIt {
- friend class UndirPath;
-
- int idx;
- const UndirPath *p;
- public:
- /// Default constructor
- NodeIt() {}
- /// Invalid constructor
- NodeIt(Invalid) : idx(-1), p(0) {}
- /// Constructor with starting point
- NodeIt(const UndirPath &_p, int _idx = 0) :
- idx(_idx), p(&_p) { validate(); }
-
- ///Validity check
- bool valid() const { return idx!=-1; }
-
- ///Conversion to Graph::Node
- operator const GraphNode& () const {
- if(idx >= p->length())
- return p->to();
- else if(idx >= 0)
- return p->gr->tail(p->edges[idx]);
- else
- return INVALID;
- }
- /// Next node
- NodeIt& operator++() { ++idx; validate(); return *this; }
-
- /// Comparison operator
- bool operator==(const NodeIt& e) const { return idx==e.idx; }
- /// Comparison operator
- bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
- /// Comparison operator
- bool operator<(const NodeIt& e) const { return idx<e.idx; }
-
- private:
- void validate() { if( size_t(idx) > p->length() ) idx=-1; }
- };
-
- friend class Builder;
-
- /**
- * \brief Class to build paths
- *
- * \ingroup paths
- * This class is used to fill a path with edges.
- *
- * You can push new edges to the front and to the back of the path in
- * arbitrary order then you should commit these changes to the graph.
- *
- * Fundamentally, for most "Paths" (classes fulfilling the
- * PathConcept) while the builder is active (after the first modifying
- * operation and until the commit()) the original Path is in a
- * "transitional" state (operations ot it have undefined result). But
- * in the case of UndirPath the original path is unchanged until the
- * commit. However we don't recomend that you use this feature.
- */
- class Builder {
- UndirPath &P;
- Container front, back;
-
- public:
- ///\param _P the path you want to fill in.
- ///
- Builder(UndirPath &_P) : P(_P) {}
-
- /// Sets the starting node of the path.
-
- /// Sets the starting node of the path. Edge added to the path
- /// afterwards have to be incident to this node.
- /// It should be called iff the path is empty and before any call to
- /// \ref pushFront() or \ref pushBack()
- void setStart(const GraphNode &) {}
-
- ///Push a new edge to the front of the path
-
- ///Push a new edge to the front of the path.
- ///\sa setStart
- void pushFront(const GraphEdge& e) {
- if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
- fault("UndirPath::Builder::pushFront: nonincident edge");
- }
- front.push_back(e);
- }
-
- ///Push a new edge to the back of the path
-
- ///Push a new edge to the back of the path.
- ///\sa setStart
- void pushBack(const GraphEdge& e) {
- if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
- fault("UndirPath::Builder::pushBack: nonincident edge");
- }
- back.push_back(e);
- }
-
- ///Commit the changes to the path.
- void commit() {
- if( !(front.empty() && back.empty()) ) {
- Container tmp;
- tmp.reserve(front.size()+back.size()+P.length());
- tmp.insert(tmp.end(), front.rbegin(), front.rend());
- tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
- tmp.insert(tmp.end(), back.begin(), back.end());
- P.edges.swap(tmp);
- front.clear();
- back.clear();
- }
- }
-
- // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
- // Hogy kenyelmes egy ilyet hasznalni?
-
- ///Reserve storage in advance for the builder
-
- ///If you know an reasonable upper bound of the number of the edges
- ///to add, using this function you can speed up the building.
- void reserve(size_t r) {
- front.reserve(r);
- back.reserve(r);
- }
-
- private:
- bool empty() {
- return front.empty() && back.empty() && P.empty();
- }
-
- GraphNode from() const {
- if( ! front.empty() )
- return P.gr->tail(front[front.size()-1]);
- else if( ! P.empty() )
- return P.gr->tail(P.edges[0]);
- else if( ! back.empty() )
- return P.gr->tail(back[0]);
- else
- return INVALID;
- }
- GraphNode to() const {
- if( ! back.empty() )
- return P.gr->head(back[back.size()-1]);
- else if( ! P.empty() )
- return P.gr->head(P.edges[P.length()-1]);
- else if( ! front.empty() )
- return P.gr->head(front[0]);
- else
- return INVALID;
- }
-
- };
-
- };
-
-
- ///@}
-
-} // namespace hugo
-
-#endif // HUGO_PATH_H
diff -r c7e37b066033 -r fc8a3393e0d9 src/work/klao/path.h
--- a/src/work/klao/path.h Tue Jun 15 06:30:03 2004 +0000
+++ b/src/work/klao/path.h Wed Jun 16 09:44:30 2004 +0000
@@ -1,6 +1,20 @@
// -*- c++ -*- //
-///\ingroup datas
+/**
+@defgroup paths Path Structures
+@ingroup datas
+\brief Path structures implemented in Hugo.
+
+Hugolib provides flexible data structures
+to work with paths.
+
+All of them have the same interface, especially they can be built or extended
+using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
+algorithm to store its result in any kind of path structure.
+
+*/
+
+///\ingroup paths
///\file
///\brief Classes for representing paths in graphs.
@@ -17,7 +31,7 @@
namespace hugo {
- /// \addtogroup datas
+ /// \addtogroup paths
/// @{
@@ -35,7 +49,9 @@
template<typename Graph, typename DM = DefaultDebugMode>
class DirPath {
public:
- typedef typename Graph::Edge GraphEdge;
+ /// Edge type of the underlying graph.
+ typedef typename Graph::Edge GraphEdge;
+ /// Node type of the underlying graph.
typedef typename Graph::Node GraphNode;
class NodeIt;
class EdgeIt;
@@ -152,27 +168,49 @@
}
- /*** Iterator classes ***/
+ /* Iterator classes */
+
+ /**
+ * \brief Iterator class to iterate on the edges of the paths
+ *
+ * \ingroup paths
+ * This class is used to iterate on the edges of the paths
+ *
+ * Of course it converts to Graph::Edge
+ *
+ * \todo Its interface differs from the standard edge iterator.
+ * Yes, it shouldn't.
+ */
class EdgeIt {
friend class DirPath;
int idx;
const DirPath *p;
public:
+ /// Default constructor
EdgeIt() {}
+ /// Invalid constructor
EdgeIt(Invalid) : idx(-1), p(0) {}
+ /// Constructor with starting point
EdgeIt(const DirPath &_p, int _idx = 0) :
idx(_idx), p(&_p) { validate(); }
+ ///Validity check
bool valid() const { return idx!=-1; }
+ ///Conversion to Graph::Edge
operator GraphEdge () const {
return valid() ? p->edges[idx] : INVALID;
}
+
+ /// Next edge
EdgeIt& operator++() { ++idx; validate(); return *this; }
+ /// Comparison operator
bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+ /// Comparison operator
bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+ /// Comparison operator
bool operator<(const EdgeIt& e) const { return idx<e.idx; }
private:
@@ -181,19 +219,35 @@
void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
};
+ /**
+ * \brief Iterator class to iterate on the nodes of the paths
+ *
+ * \ingroup paths
+ * This class is used to iterate on the nodes of the paths
+ *
+ * Of course it converts to Graph::Node
+ *
+ * \todo Its interface differs from the standard node iterator.
+ * Yes, it shouldn't.
+ */
class NodeIt {
friend class DirPath;
int idx;
const DirPath *p;
public:
+ /// Default constructor
NodeIt() {}
+ /// Invalid constructor
NodeIt(Invalid) : idx(-1), p(0) {}
+ /// Constructor with starting point
NodeIt(const DirPath &_p, int _idx = 0) :
idx(_idx), p(&_p) { validate(); }
+ ///Validity check
bool valid() const { return idx!=-1; }
+ ///Conversion to Graph::Node
operator const GraphNode& () const {
if(idx >= p->length())
return p->to();
@@ -202,10 +256,14 @@
else
return INVALID;
}
+ /// Next node
NodeIt& operator++() { ++idx; validate(); return *this; }
+ /// Comparison operator
bool operator==(const NodeIt& e) const { return idx==e.idx; }
+ /// Comparison operator
bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
+ /// Comparison operator
bool operator<(const NodeIt& e) const { return idx<e.idx; }
private:
@@ -217,7 +275,7 @@
/**
* \brief Class to build paths
*
- * \ingroup datas
+ * \ingroup paths
* This class is used to fill a path with edges.
*
* You can push new edges to the front and to the back of the path in
@@ -285,6 +343,11 @@
// FIXME: Hmm, pontosan hogy is kene ezt csinalni?
// Hogy kenyelmes egy ilyet hasznalni?
+
+ ///Reserve storage in advance for the builder
+
+ ///If you know an reasonable upper bound of the number of the edges
+ ///to add, using this function you can speed up the building.
void reserve(size_t r) {
front.reserve(r);
back.reserve(r);
@@ -349,8 +412,10 @@
template<typename Graph, typename DM = DefaultDebugMode>
class UndirPath {
public:
+ /// Edge type of the underlying graph.
typedef typename Graph::Edge GraphEdge;
- typedef typename Graph::Node GraphNode;
+ /// Node type of the underlying graph.
+ typedef typename Graph::Node GraphNode;
class NodeIt;
class EdgeIt;
@@ -466,27 +531,47 @@
}
- /*** Iterator classes ***/
+
+ /**
+ * \brief Iterator class to iterate on the edges of the paths
+ *
+ * \ingroup paths
+ * This class is used to iterate on the edges of the paths
+ *
+ * Of course it converts to Graph::Edge
+ *
+ * \todo Its interface differs from the standard edge iterator.
+ * Yes, it shouldn't.
+ */
class EdgeIt {
friend class UndirPath;
int idx;
const UndirPath *p;
public:
+ /// Default constructor
EdgeIt() {}
+ /// Invalid constructor
EdgeIt(Invalid) : idx(-1), p(0) {}
+ /// Constructor with starting point
EdgeIt(const UndirPath &_p, int _idx = 0) :
idx(_idx), p(&_p) { validate(); }
+ ///Validity check
bool valid() const { return idx!=-1; }
+ ///Conversion to Graph::Edge
operator GraphEdge () const {
return valid() ? p->edges[idx] : INVALID;
}
- EdgeIt& operator++() { ++idx; validate(); return *this; }
+ /// Next edge
+ EdgeIt& operator++() { ++idx; validate(); return *this; }
+ /// Comparison operator
bool operator==(const EdgeIt& e) const { return idx==e.idx; }
+ /// Comparison operator
bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
+ /// Comparison operator
bool operator<(const EdgeIt& e) const { return idx<e.idx; }
private:
@@ -495,19 +580,35 @@
void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
};
+ /**
+ * \brief Iterator class to iterate on the nodes of the paths
+ *
+ * \ingroup paths
+ * This class is used to iterate on the nodes of the paths
+ *
+ * Of course it converts to Graph::Node
+ *
+ * \todo Its interface differs from the standard node iterator.
+ * Yes, it shouldn't.
+ */
class NodeIt {
friend class UndirPath;
int idx;
const UndirPath *p;
public:
+ /// Default constructor
NodeIt() {}
+ /// Invalid constructor
NodeIt(Invalid) : idx(-1), p(0) {}
+ /// Constructor with starting point
NodeIt(const UndirPath &_p, int _idx = 0) :
idx(_idx), p(&_p) { validate(); }
+ ///Validity check
bool valid() const { return idx!=-1; }
+ ///Conversion to Graph::Node
operator const GraphNode& () const {
if(idx >= p->length())
return p->to();
@@ -516,11 +617,15 @@
else
return INVALID;
}
+ /// Next node
NodeIt& operator++() { ++idx; validate(); return *this; }
+ /// Comparison operator
bool operator==(const NodeIt& e) const { return idx==e.idx; }
+ /// Comparison operator
bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
- bool operator<(const NodeIt& e) const { return idx<e.idx; }
+ /// Comparison operator
+ bool operator<(const NodeIt& e) const { return idx<e.idx; }
private:
void validate() { if( size_t(idx) > p->length() ) idx=-1; }
@@ -531,7 +636,7 @@
/**
* \brief Class to build paths
*
- * \ingroup datas
+ * \ingroup paths
* This class is used to fill a path with edges.
*
* You can push new edges to the front and to the back of the path in
@@ -599,7 +704,12 @@
// FIXME: Hmm, pontosan hogy is kene ezt csinalni?
// Hogy kenyelmes egy ilyet hasznalni?
- void reserve(size_t r) {
+
+ ///Reserve storage in advance for the builder
+
+ ///If you know an reasonable upper bound of the number of the edges
+ ///to add, using this function you can speed up the building.
+ void reserve(size_t r) {
front.reserve(r);
back.reserve(r);
}