hegyi@815
|
1 |
#define SKELETON
|
hegyi@815
|
2 |
// -*- c++ -*- //
|
hegyi@815
|
3 |
|
hegyi@815
|
4 |
///\ingroup skeletons
|
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 {
|
hegyi@815
|
14 |
namespace skeleton {
|
hegyi@815
|
15 |
/// \addtogroup skeletons
|
hegyi@815
|
16 |
/// @{
|
hegyi@815
|
17 |
|
hegyi@815
|
18 |
|
hegyi@815
|
19 |
//! \brief A skeletom 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.
|
hegyi@815
|
56 |
GraphNode head() 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.
|
hegyi@815
|
61 |
GraphNode tail() 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 |
|
hegyi@815
|
70 |
/// \brief The head of an edge.
|
hegyi@815
|
71 |
///
|
hegyi@815
|
72 |
/// Returns node iterator pointing to the head node of the
|
hegyi@815
|
73 |
/// given edge iterator.
|
hegyi@815
|
74 |
NodeIt head(const EdgeIt& e) const {}
|
hegyi@815
|
75 |
|
hegyi@815
|
76 |
/// \brief The tail of an edge.
|
hegyi@815
|
77 |
///
|
hegyi@815
|
78 |
/// Returns node iterator pointing to the tail node of the
|
hegyi@815
|
79 |
/// given edge iterator.
|
hegyi@815
|
80 |
NodeIt tail(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 |
*
|
hegyi@815
|
88 |
* \ingroup skeletons
|
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 |
*
|
hegyi@815
|
121 |
* \ingroup skeletons
|
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 |
*
|
hegyi@815
|
156 |
* \ingroup skeletons
|
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
|