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