author | marci |
Tue, 21 Sep 2004 21:10:26 +0000 | |
changeset 893 | 89d5c283a485 |
parent 823 | afba7fbbb239 |
child 906 | 17f31d280385 |
permissions | -rw-r--r-- |
alpar@797 | 1 |
// -*- c++ -*- // |
alpar@797 | 2 |
|
alpar@807 | 3 |
///\ingroup skeletons |
alpar@797 | 4 |
///\file |
alpar@797 | 5 |
///\brief Classes for representing paths in graphs. |
alpar@797 | 6 |
|
hegyi@831 | 7 |
#ifndef HUGO_SKELETON_PATH_H |
hegyi@831 | 8 |
#define HUGO_SKELETON_PATH_H |
alpar@797 | 9 |
|
alpar@797 | 10 |
#include <hugo/invalid.h> |
alpar@797 | 11 |
|
alpar@797 | 12 |
namespace hugo { |
alpar@803 | 13 |
namespace skeleton { |
alpar@803 | 14 |
/// \addtogroup skeletons |
alpar@803 | 15 |
/// @{ |
hegyi@831 | 16 |
|
hegyi@831 | 17 |
|
alpar@806 | 18 |
//! \brief A skeletom structure for representing directed paths in a graph. |
alpar@803 | 19 |
//! |
alpar@806 | 20 |
//! A skeleton structure for representing directed paths in a graph. |
alpar@803 | 21 |
//! \param GR The graph type in which the path is. |
hegyi@831 | 22 |
//! |
alpar@803 | 23 |
//! In a sense, the path can be treated as a graph, for is has \c NodeIt |
alpar@803 | 24 |
//! and \c EdgeIt with the same usage. These types converts to the \c Node |
alpar@803 | 25 |
//! and \c Edge of the original graph. |
alpar@803 | 26 |
template<typename GR> |
alpar@803 | 27 |
class Path { |
alpar@803 | 28 |
public: |
hegyi@831 | 29 |
|
alpar@803 | 30 |
/// Type of the underlying graph. |
hegyi@818 | 31 |
typedef /*typename*/ GR Graph; |
alpar@803 | 32 |
/// Edge type of the underlying graph. |
hegyi@831 | 33 |
typedef typename Graph::Edge GraphEdge; |
alpar@803 | 34 |
/// Node type of the underlying graph. |
hegyi@818 | 35 |
typedef typename Graph::Node GraphNode; |
alpar@803 | 36 |
class NodeIt; |
alpar@803 | 37 |
class EdgeIt; |
hegyi@831 | 38 |
|
alpar@803 | 39 |
/// \param _G The graph in which the path is. |
alpar@803 | 40 |
/// |
alpar@803 | 41 |
Path(const Graph &_G) {} |
hegyi@831 | 42 |
|
alpar@803 | 43 |
/// Length of the path. |
hegyi@818 | 44 |
size_t length() const {return 0;} |
alpar@803 | 45 |
/// Returns whether the path is empty. |
hegyi@831 | 46 |
bool empty() const { return true;} |
hegyi@831 | 47 |
|
alpar@803 | 48 |
/// Resets the path to an empty path. |
alpar@803 | 49 |
void clear() {} |
alpar@797 | 50 |
|
alpar@803 | 51 |
/// \brief Starting point of the path. |
alpar@803 | 52 |
/// |
alpar@803 | 53 |
/// Starting point of the path. |
alpar@803 | 54 |
/// Returns INVALID if the path is empty. |
hegyi@818 | 55 |
GraphNode/*It*/ head() const {return INVALID;} |
alpar@803 | 56 |
/// \brief End point of the path. |
alpar@803 | 57 |
/// |
alpar@803 | 58 |
/// End point of the path. |
alpar@803 | 59 |
/// Returns INVALID if the path is empty. |
hegyi@818 | 60 |
GraphNode/*It*/ tail() const {return INVALID;} |
alpar@797 | 61 |
|
alpar@803 | 62 |
/// \brief First NodeIt/EdgeIt. |
alpar@803 | 63 |
/// |
alpar@803 | 64 |
/// Initializes node or edge iterator to point to the first |
alpar@803 | 65 |
/// node or edge. |
alpar@803 | 66 |
template<typename It> |
alpar@803 | 67 |
It& first(It &i) const { return i=It(*this); } |
alpar@797 | 68 |
|
alpar@803 | 69 |
/// \brief The head of an edge. |
alpar@803 | 70 |
/// |
alpar@803 | 71 |
/// Returns node iterator pointing to the head node of the |
alpar@803 | 72 |
/// given edge iterator. |
hegyi@831 | 73 |
NodeIt head(const EdgeIt& e) const {return INVALID;} |
alpar@797 | 74 |
|
alpar@803 | 75 |
/// \brief The tail of an edge. |
alpar@803 | 76 |
/// |
alpar@803 | 77 |
/// Returns node iterator pointing to the tail node of the |
alpar@803 | 78 |
/// given edge iterator. |
hegyi@831 | 79 |
NodeIt tail(const EdgeIt& e) const {return INVALID;} |
alpar@797 | 80 |
|
alpar@797 | 81 |
|
alpar@803 | 82 |
/* Iterator classes */ |
alpar@797 | 83 |
|
alpar@803 | 84 |
/** |
alpar@803 | 85 |
* \brief Iterator class to iterate on the edges of the paths |
hegyi@831 | 86 |
* |
alpar@803 | 87 |
* \ingroup skeletons |
alpar@803 | 88 |
* This class is used to iterate on the edges of the paths |
alpar@803 | 89 |
* |
alpar@803 | 90 |
* Of course it converts to Graph::Edge |
hegyi@831 | 91 |
* |
alpar@803 | 92 |
*/ |
alpar@803 | 93 |
class EdgeIt { |
alpar@803 | 94 |
public: |
alpar@803 | 95 |
/// Default constructor |
alpar@803 | 96 |
EdgeIt() {} |
alpar@803 | 97 |
/// Invalid constructor |
alpar@803 | 98 |
EdgeIt(Invalid) {} |
alpar@803 | 99 |
/// Constructor with starting point |
alpar@803 | 100 |
EdgeIt(const Path &_p) {} |
alpar@797 | 101 |
|
alpar@803 | 102 |
operator GraphEdge () const {} |
alpar@797 | 103 |
|
alpar@803 | 104 |
/// Next edge |
hegyi@831 | 105 |
EdgeIt& operator++() {return *this;} |
alpar@797 | 106 |
|
alpar@803 | 107 |
/// Comparison operator |
hegyi@823 | 108 |
bool operator==(const EdgeIt& e) const {return true;} |
alpar@803 | 109 |
/// Comparison operator |
hegyi@823 | 110 |
bool operator!=(const EdgeIt& e) const {return true;} |
alpar@803 | 111 |
// /// Comparison operator |
alpar@803 | 112 |
// /// \todo It is not clear what is the "natural" ordering. |
alpar@803 | 113 |
// bool operator<(const EdgeIt& e) const {} |
alpar@797 | 114 |
|
alpar@803 | 115 |
}; |
alpar@797 | 116 |
|
alpar@803 | 117 |
/** |
alpar@803 | 118 |
* \brief Iterator class to iterate on the nodes of the paths |
hegyi@831 | 119 |
* |
alpar@803 | 120 |
* \ingroup skeletons |
alpar@803 | 121 |
* This class is used to iterate on the nodes of the paths |
alpar@803 | 122 |
* |
alpar@803 | 123 |
* Of course it converts to Graph::Node. |
hegyi@831 | 124 |
* |
alpar@803 | 125 |
*/ |
alpar@803 | 126 |
class NodeIt { |
alpar@803 | 127 |
public: |
alpar@803 | 128 |
/// Default constructor |
alpar@803 | 129 |
NodeIt() {} |
alpar@803 | 130 |
/// Invalid constructor |
alpar@803 | 131 |
NodeIt(Invalid) {} |
alpar@803 | 132 |
/// Constructor with starting point |
alpar@803 | 133 |
NodeIt(const Path &_p) {} |
alpar@797 | 134 |
|
alpar@803 | 135 |
///Conversion to Graph::Node |
alpar@803 | 136 |
operator const GraphNode& () const {} |
alpar@803 | 137 |
/// Next node |
hegyi@831 | 138 |
NodeIt& operator++() {return *this;} |
alpar@797 | 139 |
|
alpar@803 | 140 |
/// Comparison operator |
hegyi@831 | 141 |
bool operator==(const NodeIt& e) const {return true;} |
alpar@803 | 142 |
/// Comparison operator |
hegyi@831 | 143 |
bool operator!=(const NodeIt& e) const {return true;} |
alpar@803 | 144 |
// /// Comparison operator |
alpar@803 | 145 |
// /// \todo It is not clear what is the "natural" ordering. |
alpar@803 | 146 |
// bool operator<(const NodeIt& e) const {} |
alpar@797 | 147 |
|
alpar@803 | 148 |
}; |
alpar@797 | 149 |
|
hegyi@831 | 150 |
friend class Builder; |
alpar@797 | 151 |
|
alpar@803 | 152 |
/** |
alpar@803 | 153 |
* \brief Class to build paths |
hegyi@831 | 154 |
* |
alpar@803 | 155 |
* \ingroup skeletons |
alpar@803 | 156 |
* This class is used to fill a path with edges. |
alpar@803 | 157 |
* |
alpar@803 | 158 |
* You can push new edges to the front and to the back of the path in |
alpar@803 | 159 |
* arbitrary order then you should commit these changes to the graph. |
alpar@803 | 160 |
* |
alpar@803 | 161 |
* While the builder is active (after the first modifying |
alpar@803 | 162 |
* operation and until the call of \ref commit()) |
alpar@803 | 163 |
* the underlining Path is in a |
alpar@803 | 164 |
* "transitional" state (operations on it have undefined result). |
alpar@803 | 165 |
*/ |
alpar@803 | 166 |
class Builder { |
alpar@803 | 167 |
public: |
hegyi@818 | 168 |
|
hegyi@818 | 169 |
Path &P; |
hegyi@818 | 170 |
|
alpar@803 | 171 |
///\param _P the path you want to fill in. |
alpar@803 | 172 |
/// |
alpar@803 | 173 |
Builder(Path &_P) : P(_P) {} |
alpar@797 | 174 |
|
alpar@803 | 175 |
/// Sets the starting node of the path. |
hegyi@831 | 176 |
|
alpar@803 | 177 |
/// Sets the starting node of the path. Edge added to the path |
alpar@803 | 178 |
/// afterwards have to be incident to this node. |
alpar@803 | 179 |
/// You \em must start building an empry path with this functions. |
alpar@803 | 180 |
/// (And you \em must \em not use it later). |
alpar@803 | 181 |
/// \sa pushFront() |
alpar@803 | 182 |
/// \sa pushBack() |
alpar@803 | 183 |
void setStartNode(const GraphNode &) {} |
alpar@797 | 184 |
|
alpar@803 | 185 |
///Push a new edge to the front of the path |
alpar@797 | 186 |
|
alpar@803 | 187 |
///Push a new edge to the front of the path. |
alpar@803 | 188 |
///If the path is empty, you \em must call \ref setStartNode() before |
alpar@803 | 189 |
///the first use of \ref pushFront(). |
alpar@803 | 190 |
void pushFront(const GraphEdge& e) {} |
alpar@797 | 191 |
|
alpar@803 | 192 |
///Push a new edge to the back of the path |
alpar@797 | 193 |
|
alpar@803 | 194 |
///Push a new edge to the back of the path. |
alpar@803 | 195 |
///If the path is empty, you \em must call \ref setStartNode() before |
alpar@803 | 196 |
///the first use of \ref pushBack(). |
alpar@803 | 197 |
void pushBack(const GraphEdge& e) {} |
alpar@797 | 198 |
|
alpar@803 | 199 |
///Commit the changes to the path. |
alpar@803 | 200 |
void commit() {} |
alpar@797 | 201 |
|
alpar@803 | 202 |
///Reserve (front) storage for the builder in advance. |
alpar@797 | 203 |
|
alpar@803 | 204 |
///If you know an reasonable upper bound of the number of the edges |
alpar@803 | 205 |
///to add to the front of the path, |
alpar@803 | 206 |
///using this function you may speed up the building. |
alpar@803 | 207 |
void reserveFront(size_t r) {} |
alpar@803 | 208 |
///Reserve (back) storage for the builder in advance. |
alpar@797 | 209 |
|
alpar@803 | 210 |
///If you know an reasonable upper bound of the number of the edges |
alpar@803 | 211 |
///to add to the back of the path, |
alpar@803 | 212 |
///using this function you may speed up the building. |
alpar@803 | 213 |
void reserveBack(size_t r) {} |
alpar@803 | 214 |
}; |
alpar@797 | 215 |
}; |
alpar@797 | 216 |
|
alpar@803 | 217 |
///@} |
alpar@797 | 218 |
} |
hegyi@831 | 219 |
|
alpar@797 | 220 |
} // namespace hugo |
alpar@797 | 221 |
|
hegyi@831 | 222 |
#endif // HUGO_SKELETON_PATH_H |