hegyi@819
|
1 |
// -*- c++ -*- //
|
hegyi@819
|
2 |
|
hegyi@819
|
3 |
/**
|
hegyi@819
|
4 |
@defgroup paths Path Structures
|
hegyi@819
|
5 |
@ingroup datas
|
hegyi@819
|
6 |
\brief Path structures implemented in Hugo.
|
hegyi@819
|
7 |
|
hegyi@819
|
8 |
Hugolib provides flexible data structures
|
hegyi@819
|
9 |
to work with paths.
|
hegyi@819
|
10 |
|
hegyi@819
|
11 |
All of them have the same interface, especially they can be built or extended
|
hegyi@819
|
12 |
using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
|
hegyi@819
|
13 |
algorithm to store its result in any kind of path structure.
|
hegyi@819
|
14 |
|
hegyi@819
|
15 |
\sa hugo::skeleton::Path
|
hegyi@819
|
16 |
|
hegyi@819
|
17 |
*/
|
hegyi@819
|
18 |
|
hegyi@819
|
19 |
///\ingroup paths
|
hegyi@819
|
20 |
///\file
|
hegyi@819
|
21 |
///\brief Classes for representing paths in graphs.
|
hegyi@819
|
22 |
|
hegyi@819
|
23 |
#ifndef HUGO_PATH_H
|
hegyi@819
|
24 |
#define HUGO_PATH_H
|
hegyi@819
|
25 |
|
hegyi@819
|
26 |
#include <deque>
|
hegyi@819
|
27 |
#include <vector>
|
hegyi@819
|
28 |
#include <algorithm>
|
hegyi@819
|
29 |
|
hegyi@819
|
30 |
#include <hugo/invalid.h>
|
hegyi@819
|
31 |
|
hegyi@819
|
32 |
namespace hugo {
|
hegyi@819
|
33 |
|
hegyi@819
|
34 |
/// \addtogroup paths
|
hegyi@819
|
35 |
/// @{
|
hegyi@819
|
36 |
|
hegyi@819
|
37 |
|
hegyi@819
|
38 |
//! \brief A structure for representing directed paths in a graph.
|
hegyi@819
|
39 |
//!
|
hegyi@819
|
40 |
//! A structure for representing directed path in a graph.
|
hegyi@819
|
41 |
//! \param Graph The graph type in which the path is.
|
hegyi@819
|
42 |
//! \param DM DebugMode, defaults to DefaultDebugMode.
|
hegyi@819
|
43 |
//!
|
hegyi@819
|
44 |
//! In a sense, the path can be treated as a graph, for is has \c NodeIt
|
hegyi@819
|
45 |
//! and \c EdgeIt with the same usage. These types converts to the \c Node
|
hegyi@819
|
46 |
//! and \c Edge of the original graph.
|
hegyi@819
|
47 |
//!
|
hegyi@819
|
48 |
//! \todo Thoroughfully check all the range and consistency tests.
|
hegyi@831
|
49 |
template<typename Graph>
|
hegyi@819
|
50 |
class DirPath {
|
hegyi@819
|
51 |
public:
|
hegyi@819
|
52 |
/// Edge type of the underlying graph.
|
hegyi@819
|
53 |
typedef typename Graph::Edge GraphEdge;
|
hegyi@819
|
54 |
/// Node type of the underlying graph.
|
hegyi@819
|
55 |
typedef typename Graph::Node GraphNode;
|
hegyi@819
|
56 |
class NodeIt;
|
hegyi@819
|
57 |
class EdgeIt;
|
hegyi@819
|
58 |
|
hegyi@819
|
59 |
protected:
|
hegyi@819
|
60 |
const Graph *gr;
|
hegyi@819
|
61 |
typedef std::vector<GraphEdge> Container;
|
hegyi@819
|
62 |
Container edges;
|
hegyi@819
|
63 |
|
hegyi@819
|
64 |
public:
|
hegyi@819
|
65 |
|
hegyi@819
|
66 |
/// \param _G The graph in which the path is.
|
hegyi@819
|
67 |
///
|
hegyi@819
|
68 |
DirPath(const Graph &_G) : gr(&_G) {}
|
hegyi@819
|
69 |
|
hegyi@819
|
70 |
/// \brief Subpath constructor.
|
hegyi@819
|
71 |
///
|
hegyi@819
|
72 |
/// Subpath defined by two nodes.
|
hegyi@819
|
73 |
/// \warning It is an error if the two edges are not in order!
|
hegyi@819
|
74 |
DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
|
hegyi@819
|
75 |
gr = P.gr;
|
hegyi@819
|
76 |
edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
|
hegyi@819
|
77 |
}
|
hegyi@819
|
78 |
|
hegyi@819
|
79 |
/// \brief Subpath constructor.
|
hegyi@819
|
80 |
///
|
hegyi@819
|
81 |
/// Subpath defined by two edges. Contains edges in [a,b)
|
hegyi@819
|
82 |
/// \warning It is an error if the two edges are not in order!
|
hegyi@819
|
83 |
DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
|
hegyi@819
|
84 |
gr = P.gr;
|
hegyi@819
|
85 |
edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
|
hegyi@819
|
86 |
}
|
hegyi@819
|
87 |
|
hegyi@819
|
88 |
/// Length of the path.
|
hegyi@819
|
89 |
size_t length() const { return edges.size(); }
|
hegyi@819
|
90 |
/// Returns whether the path is empty.
|
hegyi@819
|
91 |
bool empty() const { return edges.empty(); }
|
hegyi@819
|
92 |
|
hegyi@819
|
93 |
/// Resets the path to an empty path.
|
hegyi@819
|
94 |
void clear() { edges.clear(); }
|
hegyi@819
|
95 |
|
hegyi@819
|
96 |
/// \brief Starting point of the path.
|
hegyi@819
|
97 |
///
|
hegyi@819
|
98 |
/// Starting point of the path.
|
hegyi@819
|
99 |
/// Returns INVALID if the path is empty.
|
hegyi@831
|
100 |
GraphNode tail() const {
|
hegyi@819
|
101 |
return empty() ? INVALID : gr->tail(edges[0]);
|
hegyi@819
|
102 |
}
|
hegyi@819
|
103 |
/// \brief End point of the path.
|
hegyi@819
|
104 |
///
|
hegyi@819
|
105 |
/// End point of the path.
|
hegyi@819
|
106 |
/// Returns INVALID if the path is empty.
|
hegyi@831
|
107 |
GraphNode head() const {
|
hegyi@819
|
108 |
return empty() ? INVALID : gr->head(edges[length()-1]);
|
hegyi@819
|
109 |
}
|
hegyi@819
|
110 |
|
hegyi@819
|
111 |
/// \brief Initializes node or edge iterator to point to the first
|
hegyi@819
|
112 |
/// node or edge.
|
hegyi@819
|
113 |
///
|
hegyi@819
|
114 |
/// \sa nth
|
hegyi@819
|
115 |
template<typename It>
|
hegyi@819
|
116 |
It& first(It &i) const { return i=It(*this); }
|
hegyi@819
|
117 |
|
hegyi@819
|
118 |
/// \brief Initializes node iterator to point to the node of a given index.
|
hegyi@819
|
119 |
NodeIt& nth(NodeIt &i, int n) const {
|
hegyi@819
|
120 |
return i=NodeIt(*this, n);
|
hegyi@819
|
121 |
}
|
hegyi@819
|
122 |
|
hegyi@819
|
123 |
/// \brief Initializes edge iterator to point to the edge of a given index.
|
hegyi@819
|
124 |
EdgeIt& nth(EdgeIt &i, int n) const {
|
hegyi@819
|
125 |
return i=EdgeIt(*this, n);
|
hegyi@819
|
126 |
}
|
hegyi@819
|
127 |
|
hegyi@819
|
128 |
/// Checks validity of a node or edge iterator.
|
hegyi@819
|
129 |
template<typename It>
|
hegyi@819
|
130 |
static
|
hegyi@819
|
131 |
bool valid(const It &i) { return i.valid(); }
|
hegyi@819
|
132 |
|
hegyi@819
|
133 |
/// Steps the given node or edge iterator.
|
hegyi@819
|
134 |
template<typename It>
|
hegyi@819
|
135 |
static
|
hegyi@819
|
136 |
It& next(It &e) {
|
hegyi@819
|
137 |
return ++e;
|
hegyi@819
|
138 |
}
|
hegyi@819
|
139 |
|
hegyi@819
|
140 |
/// \brief Returns node iterator pointing to the head node of the
|
hegyi@819
|
141 |
/// given edge iterator.
|
hegyi@819
|
142 |
NodeIt head(const EdgeIt& e) const {
|
hegyi@819
|
143 |
return NodeIt(*this, e.idx+1);
|
hegyi@819
|
144 |
}
|
hegyi@819
|
145 |
|
hegyi@819
|
146 |
/// \brief Returns node iterator pointing to the tail node of the
|
hegyi@819
|
147 |
/// given edge iterator.
|
hegyi@819
|
148 |
NodeIt tail(const EdgeIt& e) const {
|
hegyi@819
|
149 |
return NodeIt(*this, e.idx);
|
hegyi@819
|
150 |
}
|
hegyi@819
|
151 |
|
hegyi@819
|
152 |
|
hegyi@819
|
153 |
/* Iterator classes */
|
hegyi@819
|
154 |
|
hegyi@819
|
155 |
/**
|
hegyi@819
|
156 |
* \brief Iterator class to iterate on the edges of the paths
|
hegyi@819
|
157 |
*
|
hegyi@819
|
158 |
* \ingroup paths
|
hegyi@819
|
159 |
* This class is used to iterate on the edges of the paths
|
hegyi@819
|
160 |
*
|
hegyi@819
|
161 |
* Of course it converts to Graph::Edge
|
hegyi@819
|
162 |
*
|
hegyi@819
|
163 |
* \todo Its interface differs from the standard edge iterator.
|
hegyi@819
|
164 |
* Yes, it shouldn't.
|
hegyi@819
|
165 |
*/
|
hegyi@819
|
166 |
class EdgeIt {
|
hegyi@819
|
167 |
friend class DirPath;
|
hegyi@819
|
168 |
|
hegyi@819
|
169 |
int idx;
|
hegyi@819
|
170 |
const DirPath *p;
|
hegyi@819
|
171 |
public:
|
hegyi@819
|
172 |
/// Default constructor
|
hegyi@819
|
173 |
EdgeIt() {}
|
hegyi@819
|
174 |
/// Invalid constructor
|
hegyi@819
|
175 |
EdgeIt(Invalid) : idx(-1), p(0) {}
|
hegyi@819
|
176 |
/// Constructor with starting point
|
hegyi@819
|
177 |
EdgeIt(const DirPath &_p, int _idx = 0) :
|
hegyi@819
|
178 |
idx(_idx), p(&_p) { validate(); }
|
hegyi@819
|
179 |
|
hegyi@819
|
180 |
///Validity check
|
hegyi@819
|
181 |
bool valid() const { return idx!=-1; }
|
hegyi@819
|
182 |
|
hegyi@819
|
183 |
///Conversion to Graph::Edge
|
hegyi@819
|
184 |
operator GraphEdge () const {
|
hegyi@819
|
185 |
return valid() ? p->edges[idx] : INVALID;
|
hegyi@819
|
186 |
}
|
hegyi@819
|
187 |
|
hegyi@819
|
188 |
/// Next edge
|
hegyi@819
|
189 |
EdgeIt& operator++() { ++idx; validate(); return *this; }
|
hegyi@819
|
190 |
|
hegyi@819
|
191 |
/// Comparison operator
|
hegyi@819
|
192 |
bool operator==(const EdgeIt& e) const { return idx==e.idx; }
|
hegyi@819
|
193 |
/// Comparison operator
|
hegyi@819
|
194 |
bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
|
hegyi@819
|
195 |
/// Comparison operator
|
hegyi@819
|
196 |
bool operator<(const EdgeIt& e) const { return idx<e.idx; }
|
hegyi@819
|
197 |
|
hegyi@819
|
198 |
private:
|
hegyi@819
|
199 |
// FIXME: comparison between signed and unsigned...
|
hegyi@819
|
200 |
// Jo ez igy? Vagy esetleg legyen a length() int?
|
hegyi@819
|
201 |
void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
|
hegyi@819
|
202 |
};
|
hegyi@819
|
203 |
|
hegyi@819
|
204 |
/**
|
hegyi@819
|
205 |
* \brief Iterator class to iterate on the nodes of the paths
|
hegyi@819
|
206 |
*
|
hegyi@819
|
207 |
* \ingroup paths
|
hegyi@819
|
208 |
* This class is used to iterate on the nodes of the paths
|
hegyi@819
|
209 |
*
|
hegyi@819
|
210 |
* Of course it converts to Graph::Node
|
hegyi@819
|
211 |
*
|
hegyi@819
|
212 |
* \todo Its interface differs from the standard node iterator.
|
hegyi@819
|
213 |
* Yes, it shouldn't.
|
hegyi@819
|
214 |
*/
|
hegyi@819
|
215 |
class NodeIt {
|
hegyi@819
|
216 |
friend class DirPath;
|
hegyi@819
|
217 |
|
hegyi@819
|
218 |
int idx;
|
hegyi@819
|
219 |
const DirPath *p;
|
hegyi@819
|
220 |
public:
|
hegyi@819
|
221 |
/// Default constructor
|
hegyi@819
|
222 |
NodeIt() {}
|
hegyi@819
|
223 |
/// Invalid constructor
|
hegyi@819
|
224 |
NodeIt(Invalid) : idx(-1), p(0) {}
|
hegyi@819
|
225 |
/// Constructor with starting point
|
hegyi@819
|
226 |
NodeIt(const DirPath &_p, int _idx = 0) :
|
hegyi@819
|
227 |
idx(_idx), p(&_p) { validate(); }
|
hegyi@819
|
228 |
|
hegyi@819
|
229 |
///Validity check
|
hegyi@819
|
230 |
bool valid() const { return idx!=-1; }
|
hegyi@819
|
231 |
|
hegyi@819
|
232 |
///Conversion to Graph::Node
|
hegyi@819
|
233 |
operator const GraphNode& () const {
|
hegyi@819
|
234 |
if(idx >= p->length())
|
hegyi@831
|
235 |
return p->head();
|
hegyi@819
|
236 |
else if(idx >= 0)
|
hegyi@819
|
237 |
return p->gr->tail(p->edges[idx]);
|
hegyi@819
|
238 |
else
|
hegyi@819
|
239 |
return INVALID;
|
hegyi@819
|
240 |
}
|
hegyi@819
|
241 |
/// Next node
|
hegyi@819
|
242 |
NodeIt& operator++() { ++idx; validate(); return *this; }
|
hegyi@819
|
243 |
|
hegyi@819
|
244 |
/// Comparison operator
|
hegyi@819
|
245 |
bool operator==(const NodeIt& e) const { return idx==e.idx; }
|
hegyi@819
|
246 |
/// Comparison operator
|
hegyi@819
|
247 |
bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
|
hegyi@819
|
248 |
/// Comparison operator
|
hegyi@819
|
249 |
bool operator<(const NodeIt& e) const { return idx<e.idx; }
|
hegyi@819
|
250 |
|
hegyi@819
|
251 |
private:
|
hegyi@819
|
252 |
void validate() { if( size_t(idx) > p->length() ) idx=-1; }
|
hegyi@819
|
253 |
};
|
hegyi@819
|
254 |
|
hegyi@819
|
255 |
friend class Builder;
|
hegyi@819
|
256 |
|
hegyi@819
|
257 |
/**
|
hegyi@819
|
258 |
* \brief Class to build paths
|
hegyi@819
|
259 |
*
|
hegyi@819
|
260 |
* \ingroup paths
|
hegyi@819
|
261 |
* This class is used to fill a path with edges.
|
hegyi@819
|
262 |
*
|
hegyi@819
|
263 |
* You can push new edges to the front and to the back of the path in
|
hegyi@819
|
264 |
* arbitrary order then you should commit these changes to the graph.
|
hegyi@819
|
265 |
*
|
hegyi@819
|
266 |
* Fundamentally, for most "Paths" (classes fulfilling the
|
hegyi@819
|
267 |
* PathConcept) while the builder is active (after the first modifying
|
hegyi@819
|
268 |
* operation and until the commit()) the original Path is in a
|
hegyi@819
|
269 |
* "transitional" state (operations on it have undefined result). But
|
hegyi@819
|
270 |
* in the case of DirPath the original path remains unchanged until the
|
hegyi@819
|
271 |
* commit. However we don't recomend that you use this feature.
|
hegyi@819
|
272 |
*/
|
hegyi@819
|
273 |
class Builder {
|
hegyi@819
|
274 |
DirPath &P;
|
hegyi@819
|
275 |
Container front, back;
|
hegyi@819
|
276 |
|
hegyi@819
|
277 |
public:
|
hegyi@819
|
278 |
///\param _P the path you want to fill in.
|
hegyi@819
|
279 |
///
|
hegyi@819
|
280 |
Builder(DirPath &_P) : P(_P) {}
|
hegyi@819
|
281 |
|
hegyi@819
|
282 |
/// Sets the starting node of the path.
|
hegyi@819
|
283 |
|
hegyi@819
|
284 |
/// Sets the starting node of the path. Edge added to the path
|
hegyi@819
|
285 |
/// afterwards have to be incident to this node.
|
hegyi@819
|
286 |
/// It should be called iff the path is empty and before any call to
|
hegyi@819
|
287 |
/// \ref pushFront() or \ref pushBack()
|
hegyi@819
|
288 |
void setStartNode(const GraphNode &) {}
|
hegyi@819
|
289 |
|
hegyi@819
|
290 |
///Push a new edge to the front of the path
|
hegyi@819
|
291 |
|
hegyi@819
|
292 |
///Push a new edge to the front of the path.
|
hegyi@819
|
293 |
///\sa setStartNode
|
hegyi@819
|
294 |
void pushFront(const GraphEdge& e) {
|
hegyi@819
|
295 |
front.push_back(e);
|
hegyi@819
|
296 |
}
|
hegyi@819
|
297 |
|
hegyi@819
|
298 |
///Push a new edge to the back of the path
|
hegyi@819
|
299 |
|
hegyi@819
|
300 |
///Push a new edge to the back of the path.
|
hegyi@819
|
301 |
///\sa setStartNode
|
hegyi@819
|
302 |
void pushBack(const GraphEdge& e) {
|
hegyi@819
|
303 |
back.push_back(e);
|
hegyi@819
|
304 |
}
|
hegyi@819
|
305 |
|
hegyi@819
|
306 |
///Commit the changes to the path.
|
hegyi@819
|
307 |
void commit() {
|
hegyi@819
|
308 |
if( !(front.empty() && back.empty()) ) {
|
hegyi@819
|
309 |
Container tmp;
|
hegyi@819
|
310 |
tmp.reserve(front.size()+back.size()+P.length());
|
hegyi@819
|
311 |
tmp.insert(tmp.end(), front.rbegin(), front.rend());
|
hegyi@819
|
312 |
tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
|
hegyi@819
|
313 |
tmp.insert(tmp.end(), back.begin(), back.end());
|
hegyi@819
|
314 |
P.edges.swap(tmp);
|
hegyi@819
|
315 |
front.clear();
|
hegyi@819
|
316 |
back.clear();
|
hegyi@819
|
317 |
}
|
hegyi@819
|
318 |
}
|
hegyi@819
|
319 |
|
hegyi@819
|
320 |
// FIXME: Hmm, pontosan hogy is kene ezt csinalni?
|
hegyi@819
|
321 |
// Hogy kenyelmes egy ilyet hasznalni?
|
hegyi@819
|
322 |
|
hegyi@819
|
323 |
///Reserve storage for the builder in advance.
|
hegyi@819
|
324 |
|
hegyi@819
|
325 |
///If you know an reasonable upper bound of the number of the edges
|
hegyi@819
|
326 |
///to add, using this function you can speed up the building.
|
hegyi@819
|
327 |
void reserve(size_t r) {
|
hegyi@819
|
328 |
front.reserve(r);
|
hegyi@819
|
329 |
back.reserve(r);
|
hegyi@819
|
330 |
}
|
hegyi@819
|
331 |
|
hegyi@831
|
332 |
void reserveFront(size_t r) {}
|
hegyi@831
|
333 |
void reserveBack(size_t r) {}
|
hegyi@831
|
334 |
|
hegyi@819
|
335 |
private:
|
hegyi@819
|
336 |
bool empty() {
|
hegyi@819
|
337 |
return front.empty() && back.empty() && P.empty();
|
hegyi@819
|
338 |
}
|
hegyi@819
|
339 |
|
hegyi@831
|
340 |
GraphNode tail() const {
|
hegyi@819
|
341 |
if( ! front.empty() )
|
hegyi@819
|
342 |
return P.gr->tail(front[front.size()-1]);
|
hegyi@819
|
343 |
else if( ! P.empty() )
|
hegyi@819
|
344 |
return P.gr->tail(P.edges[0]);
|
hegyi@819
|
345 |
else if( ! back.empty() )
|
hegyi@819
|
346 |
return P.gr->tail(back[0]);
|
hegyi@819
|
347 |
else
|
hegyi@819
|
348 |
return INVALID;
|
hegyi@819
|
349 |
}
|
hegyi@831
|
350 |
GraphNode head() const {
|
hegyi@819
|
351 |
if( ! back.empty() )
|
hegyi@819
|
352 |
return P.gr->head(back[back.size()-1]);
|
hegyi@819
|
353 |
else if( ! P.empty() )
|
hegyi@819
|
354 |
return P.gr->head(P.edges[P.length()-1]);
|
hegyi@819
|
355 |
else if( ! front.empty() )
|
hegyi@819
|
356 |
return P.gr->head(front[0]);
|
hegyi@819
|
357 |
else
|
hegyi@819
|
358 |
return INVALID;
|
hegyi@819
|
359 |
}
|
hegyi@819
|
360 |
|
hegyi@819
|
361 |
};
|
hegyi@819
|
362 |
|
hegyi@819
|
363 |
};
|
hegyi@819
|
364 |
|
hegyi@819
|
365 |
|
hegyi@819
|
366 |
|
hegyi@819
|
367 |
|
hegyi@819
|
368 |
|
hegyi@819
|
369 |
|
hegyi@819
|
370 |
|
hegyi@819
|
371 |
|
hegyi@819
|
372 |
|
hegyi@819
|
373 |
|
hegyi@819
|
374 |
/**********************************************************************/
|
hegyi@819
|
375 |
|
hegyi@819
|
376 |
|
hegyi@819
|
377 |
//! \brief A structure for representing undirected path in a graph.
|
hegyi@819
|
378 |
//!
|
hegyi@819
|
379 |
//! A structure for representing undirected path in a graph. Ie. this is
|
hegyi@819
|
380 |
//! a path in a \e directed graph but the edges should not be directed
|
hegyi@819
|
381 |
//! forward.
|
hegyi@819
|
382 |
//!
|
hegyi@819
|
383 |
//! \param Graph The graph type in which the path is.
|
hegyi@819
|
384 |
//! \param DM DebugMode, defaults to DefaultDebugMode.
|
hegyi@819
|
385 |
//!
|
hegyi@819
|
386 |
//! In a sense, the path can be treated as a graph, for is has \c NodeIt
|
hegyi@819
|
387 |
//! and \c EdgeIt with the same usage. These types converts to the \c Node
|
hegyi@819
|
388 |
//! and \c Edge of the original graph.
|
hegyi@819
|
389 |
//!
|
hegyi@819
|
390 |
//! \todo Thoroughfully check all the range and consistency tests.
|
hegyi@831
|
391 |
template<typename Graph>
|
hegyi@819
|
392 |
class UndirPath {
|
hegyi@819
|
393 |
public:
|
hegyi@819
|
394 |
/// Edge type of the underlying graph.
|
hegyi@819
|
395 |
typedef typename Graph::Edge GraphEdge;
|
hegyi@819
|
396 |
/// Node type of the underlying graph.
|
hegyi@819
|
397 |
typedef typename Graph::Node GraphNode;
|
hegyi@819
|
398 |
class NodeIt;
|
hegyi@819
|
399 |
class EdgeIt;
|
hegyi@819
|
400 |
|
hegyi@819
|
401 |
protected:
|
hegyi@819
|
402 |
const Graph *gr;
|
hegyi@819
|
403 |
typedef std::vector<GraphEdge> Container;
|
hegyi@819
|
404 |
Container edges;
|
hegyi@819
|
405 |
|
hegyi@819
|
406 |
public:
|
hegyi@819
|
407 |
|
hegyi@819
|
408 |
/// \param _G The graph in which the path is.
|
hegyi@819
|
409 |
///
|
hegyi@819
|
410 |
UndirPath(const Graph &_G) : gr(&_G) {}
|
hegyi@819
|
411 |
|
hegyi@819
|
412 |
/// \brief Subpath constructor.
|
hegyi@819
|
413 |
///
|
hegyi@819
|
414 |
/// Subpath defined by two nodes.
|
hegyi@819
|
415 |
/// \warning It is an error if the two edges are not in order!
|
hegyi@819
|
416 |
UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
|
hegyi@819
|
417 |
gr = P.gr;
|
hegyi@819
|
418 |
edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
|
hegyi@819
|
419 |
}
|
hegyi@819
|
420 |
|
hegyi@819
|
421 |
/// \brief Subpath constructor.
|
hegyi@819
|
422 |
///
|
hegyi@819
|
423 |
/// Subpath defined by two edges. Contains edges in [a,b)
|
hegyi@819
|
424 |
/// \warning It is an error if the two edges are not in order!
|
hegyi@819
|
425 |
UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
|
hegyi@819
|
426 |
gr = P.gr;
|
hegyi@819
|
427 |
edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
|
hegyi@819
|
428 |
}
|
hegyi@819
|
429 |
|
hegyi@819
|
430 |
/// Length of the path.
|
hegyi@819
|
431 |
size_t length() const { return edges.size(); }
|
hegyi@819
|
432 |
/// Returns whether the path is empty.
|
hegyi@819
|
433 |
bool empty() const { return edges.empty(); }
|
hegyi@819
|
434 |
|
hegyi@819
|
435 |
/// Resets the path to an empty path.
|
hegyi@819
|
436 |
void clear() { edges.clear(); }
|
hegyi@819
|
437 |
|
hegyi@819
|
438 |
/// \brief Starting point of the path.
|
hegyi@819
|
439 |
///
|
hegyi@819
|
440 |
/// Starting point of the path.
|
hegyi@819
|
441 |
/// Returns INVALID if the path is empty.
|
hegyi@831
|
442 |
GraphNode tail() const {
|
hegyi@819
|
443 |
return empty() ? INVALID : gr->tail(edges[0]);
|
hegyi@819
|
444 |
}
|
hegyi@819
|
445 |
/// \brief End point of the path.
|
hegyi@819
|
446 |
///
|
hegyi@819
|
447 |
/// End point of the path.
|
hegyi@819
|
448 |
/// Returns INVALID if the path is empty.
|
hegyi@831
|
449 |
GraphNode head() const {
|
hegyi@819
|
450 |
return empty() ? INVALID : gr->head(edges[length()-1]);
|
hegyi@819
|
451 |
}
|
hegyi@819
|
452 |
|
hegyi@819
|
453 |
/// \brief Initializes node or edge iterator to point to the first
|
hegyi@819
|
454 |
/// node or edge.
|
hegyi@819
|
455 |
///
|
hegyi@819
|
456 |
/// \sa nth
|
hegyi@819
|
457 |
template<typename It>
|
hegyi@819
|
458 |
It& first(It &i) const { return i=It(*this); }
|
hegyi@819
|
459 |
|
hegyi@819
|
460 |
/// \brief Initializes node iterator to point to the node of a given index.
|
hegyi@819
|
461 |
NodeIt& nth(NodeIt &i, int n) const {
|
hegyi@819
|
462 |
return i=NodeIt(*this, n);
|
hegyi@819
|
463 |
}
|
hegyi@819
|
464 |
|
hegyi@819
|
465 |
/// \brief Initializes edge iterator to point to the edge of a given index.
|
hegyi@819
|
466 |
EdgeIt& nth(EdgeIt &i, int n) const {
|
hegyi@819
|
467 |
return i=EdgeIt(*this, n);
|
hegyi@819
|
468 |
}
|
hegyi@819
|
469 |
|
hegyi@819
|
470 |
/// Checks validity of a node or edge iterator.
|
hegyi@819
|
471 |
template<typename It>
|
hegyi@819
|
472 |
static
|
hegyi@819
|
473 |
bool valid(const It &i) { return i.valid(); }
|
hegyi@819
|
474 |
|
hegyi@819
|
475 |
/// Steps the given node or edge iterator.
|
hegyi@819
|
476 |
template<typename It>
|
hegyi@819
|
477 |
static
|
hegyi@819
|
478 |
It& next(It &e) {
|
hegyi@819
|
479 |
return ++e;
|
hegyi@819
|
480 |
}
|
hegyi@819
|
481 |
|
hegyi@819
|
482 |
/// \brief Returns node iterator pointing to the head node of the
|
hegyi@819
|
483 |
/// given edge iterator.
|
hegyi@819
|
484 |
NodeIt head(const EdgeIt& e) const {
|
hegyi@819
|
485 |
return NodeIt(*this, e.idx+1);
|
hegyi@819
|
486 |
}
|
hegyi@819
|
487 |
|
hegyi@819
|
488 |
/// \brief Returns node iterator pointing to the tail node of the
|
hegyi@819
|
489 |
/// given edge iterator.
|
hegyi@819
|
490 |
NodeIt tail(const EdgeIt& e) const {
|
hegyi@819
|
491 |
return NodeIt(*this, e.idx);
|
hegyi@819
|
492 |
}
|
hegyi@819
|
493 |
|
hegyi@819
|
494 |
|
hegyi@819
|
495 |
|
hegyi@819
|
496 |
/**
|
hegyi@819
|
497 |
* \brief Iterator class to iterate on the edges of the paths
|
hegyi@819
|
498 |
*
|
hegyi@819
|
499 |
* \ingroup paths
|
hegyi@819
|
500 |
* This class is used to iterate on the edges of the paths
|
hegyi@819
|
501 |
*
|
hegyi@819
|
502 |
* Of course it converts to Graph::Edge
|
hegyi@819
|
503 |
*
|
hegyi@819
|
504 |
* \todo Its interface differs from the standard edge iterator.
|
hegyi@819
|
505 |
* Yes, it shouldn't.
|
hegyi@819
|
506 |
*/
|
hegyi@819
|
507 |
class EdgeIt {
|
hegyi@819
|
508 |
friend class UndirPath;
|
hegyi@819
|
509 |
|
hegyi@819
|
510 |
int idx;
|
hegyi@819
|
511 |
const UndirPath *p;
|
hegyi@819
|
512 |
public:
|
hegyi@819
|
513 |
/// Default constructor
|
hegyi@819
|
514 |
EdgeIt() {}
|
hegyi@819
|
515 |
/// Invalid constructor
|
hegyi@819
|
516 |
EdgeIt(Invalid) : idx(-1), p(0) {}
|
hegyi@819
|
517 |
/// Constructor with starting point
|
hegyi@819
|
518 |
EdgeIt(const UndirPath &_p, int _idx = 0) :
|
hegyi@819
|
519 |
idx(_idx), p(&_p) { validate(); }
|
hegyi@819
|
520 |
|
hegyi@819
|
521 |
///Validity check
|
hegyi@819
|
522 |
bool valid() const { return idx!=-1; }
|
hegyi@819
|
523 |
|
hegyi@819
|
524 |
///Conversion to Graph::Edge
|
hegyi@819
|
525 |
operator GraphEdge () const {
|
hegyi@819
|
526 |
return valid() ? p->edges[idx] : INVALID;
|
hegyi@819
|
527 |
}
|
hegyi@819
|
528 |
/// Next edge
|
hegyi@819
|
529 |
EdgeIt& operator++() { ++idx; validate(); return *this; }
|
hegyi@819
|
530 |
|
hegyi@819
|
531 |
/// Comparison operator
|
hegyi@819
|
532 |
bool operator==(const EdgeIt& e) const { return idx==e.idx; }
|
hegyi@819
|
533 |
/// Comparison operator
|
hegyi@819
|
534 |
bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
|
hegyi@819
|
535 |
/// Comparison operator
|
hegyi@819
|
536 |
bool operator<(const EdgeIt& e) const { return idx<e.idx; }
|
hegyi@819
|
537 |
|
hegyi@819
|
538 |
private:
|
hegyi@819
|
539 |
// FIXME: comparison between signed and unsigned...
|
hegyi@819
|
540 |
// Jo ez igy? Vagy esetleg legyen a length() int?
|
hegyi@819
|
541 |
void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
|
hegyi@819
|
542 |
};
|
hegyi@819
|
543 |
|
hegyi@819
|
544 |
/**
|
hegyi@819
|
545 |
* \brief Iterator class to iterate on the nodes of the paths
|
hegyi@819
|
546 |
*
|
hegyi@819
|
547 |
* \ingroup paths
|
hegyi@819
|
548 |
* This class is used to iterate on the nodes of the paths
|
hegyi@819
|
549 |
*
|
hegyi@819
|
550 |
* Of course it converts to Graph::Node
|
hegyi@819
|
551 |
*
|
hegyi@819
|
552 |
* \todo Its interface differs from the standard node iterator.
|
hegyi@819
|
553 |
* Yes, it shouldn't.
|
hegyi@819
|
554 |
*/
|
hegyi@819
|
555 |
class NodeIt {
|
hegyi@819
|
556 |
friend class UndirPath;
|
hegyi@819
|
557 |
|
hegyi@819
|
558 |
int idx;
|
hegyi@819
|
559 |
const UndirPath *p;
|
hegyi@819
|
560 |
public:
|
hegyi@819
|
561 |
/// Default constructor
|
hegyi@819
|
562 |
NodeIt() {}
|
hegyi@819
|
563 |
/// Invalid constructor
|
hegyi@819
|
564 |
NodeIt(Invalid) : idx(-1), p(0) {}
|
hegyi@819
|
565 |
/// Constructor with starting point
|
hegyi@819
|
566 |
NodeIt(const UndirPath &_p, int _idx = 0) :
|
hegyi@819
|
567 |
idx(_idx), p(&_p) { validate(); }
|
hegyi@819
|
568 |
|
hegyi@819
|
569 |
///Validity check
|
hegyi@819
|
570 |
bool valid() const { return idx!=-1; }
|
hegyi@819
|
571 |
|
hegyi@819
|
572 |
///Conversion to Graph::Node
|
hegyi@819
|
573 |
operator const GraphNode& () const {
|
hegyi@819
|
574 |
if(idx >= p->length())
|
hegyi@831
|
575 |
return p->head();
|
hegyi@819
|
576 |
else if(idx >= 0)
|
hegyi@819
|
577 |
return p->gr->tail(p->edges[idx]);
|
hegyi@819
|
578 |
else
|
hegyi@819
|
579 |
return INVALID;
|
hegyi@819
|
580 |
}
|
hegyi@819
|
581 |
/// Next node
|
hegyi@819
|
582 |
NodeIt& operator++() { ++idx; validate(); return *this; }
|
hegyi@819
|
583 |
|
hegyi@819
|
584 |
/// Comparison operator
|
hegyi@819
|
585 |
bool operator==(const NodeIt& e) const { return idx==e.idx; }
|
hegyi@819
|
586 |
/// Comparison operator
|
hegyi@819
|
587 |
bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
|
hegyi@819
|
588 |
/// Comparison operator
|
hegyi@819
|
589 |
bool operator<(const NodeIt& e) const { return idx<e.idx; }
|
hegyi@819
|
590 |
|
hegyi@819
|
591 |
private:
|
hegyi@819
|
592 |
void validate() { if( size_t(idx) > p->length() ) idx=-1; }
|
hegyi@819
|
593 |
};
|
hegyi@819
|
594 |
|
hegyi@819
|
595 |
friend class Builder;
|
hegyi@819
|
596 |
|
hegyi@819
|
597 |
/**
|
hegyi@819
|
598 |
* \brief Class to build paths
|
hegyi@819
|
599 |
*
|
hegyi@819
|
600 |
* \ingroup paths
|
hegyi@819
|
601 |
* This class is used to fill a path with edges.
|
hegyi@819
|
602 |
*
|
hegyi@819
|
603 |
* You can push new edges to the front and to the back of the path in
|
hegyi@819
|
604 |
* arbitrary order then you should commit these changes to the graph.
|
hegyi@819
|
605 |
*
|
hegyi@819
|
606 |
* Fundamentally, for most "Paths" (classes fulfilling the
|
hegyi@819
|
607 |
* PathConcept) while the builder is active (after the first modifying
|
hegyi@819
|
608 |
* operation and until the commit()) the original Path is in a
|
hegyi@819
|
609 |
* "transitional" state (operations ot it have undefined result). But
|
hegyi@819
|
610 |
* in the case of UndirPath the original path is unchanged until the
|
hegyi@819
|
611 |
* commit. However we don't recomend that you use this feature.
|
hegyi@819
|
612 |
*/
|
hegyi@819
|
613 |
class Builder {
|
hegyi@819
|
614 |
UndirPath &P;
|
hegyi@819
|
615 |
Container front, back;
|
hegyi@819
|
616 |
|
hegyi@819
|
617 |
public:
|
hegyi@819
|
618 |
///\param _P the path you want to fill in.
|
hegyi@819
|
619 |
///
|
hegyi@819
|
620 |
Builder(UndirPath &_P) : P(_P) {}
|
hegyi@819
|
621 |
|
hegyi@819
|
622 |
/// Sets the starting node of the path.
|
hegyi@819
|
623 |
|
hegyi@819
|
624 |
/// Sets the starting node of the path. Edge added to the path
|
hegyi@819
|
625 |
/// afterwards have to be incident to this node.
|
hegyi@819
|
626 |
/// It should be called iff the path is empty and before any call to
|
hegyi@819
|
627 |
/// \ref pushFront() or \ref pushBack()
|
hegyi@819
|
628 |
void setStartNode(const GraphNode &) {}
|
hegyi@819
|
629 |
|
hegyi@819
|
630 |
///Push a new edge to the front of the path
|
hegyi@819
|
631 |
|
hegyi@819
|
632 |
///Push a new edge to the front of the path.
|
hegyi@819
|
633 |
///\sa setStartNode
|
hegyi@819
|
634 |
void pushFront(const GraphEdge& e) {
|
hegyi@819
|
635 |
front.push_back(e);
|
hegyi@819
|
636 |
}
|
hegyi@819
|
637 |
|
hegyi@819
|
638 |
///Push a new edge to the back of the path
|
hegyi@819
|
639 |
|
hegyi@819
|
640 |
///Push a new edge to the back of the path.
|
hegyi@819
|
641 |
///\sa setStartNode
|
hegyi@819
|
642 |
void pushBack(const GraphEdge& e) {
|
hegyi@831
|
643 |
if( !empty() && P.gr->tail(e)!=head() ) {
|
hegyi@819
|
644 |
fault("UndirPath::Builder::pushBack: nonincident edge");
|
hegyi@819
|
645 |
}
|
hegyi@819
|
646 |
back.push_back(e);
|
hegyi@819
|
647 |
}
|
hegyi@819
|
648 |
|
hegyi@819
|
649 |
///Commit the changes to the path.
|
hegyi@819
|
650 |
void commit() {
|
hegyi@819
|
651 |
if( !(front.empty() && back.empty()) ) {
|
hegyi@819
|
652 |
Container tmp;
|
hegyi@819
|
653 |
tmp.reserve(front.size()+back.size()+P.length());
|
hegyi@819
|
654 |
tmp.insert(tmp.end(), front.rbegin(), front.rend());
|
hegyi@819
|
655 |
tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
|
hegyi@819
|
656 |
tmp.insert(tmp.end(), back.begin(), back.end());
|
hegyi@819
|
657 |
P.edges.swap(tmp);
|
hegyi@819
|
658 |
front.clear();
|
hegyi@819
|
659 |
back.clear();
|
hegyi@819
|
660 |
}
|
hegyi@819
|
661 |
}
|
hegyi@819
|
662 |
|
hegyi@819
|
663 |
// FIXME: Hmm, pontosan hogy is kene ezt csinalni?
|
hegyi@819
|
664 |
// Hogy kenyelmes egy ilyet hasznalni?
|
hegyi@819
|
665 |
|
hegyi@819
|
666 |
///Reserve storage for the builder in advance.
|
hegyi@819
|
667 |
|
hegyi@819
|
668 |
///If you know an reasonable upper bound of the number of the edges
|
hegyi@819
|
669 |
///to add, using this function you can speed up the building.
|
hegyi@819
|
670 |
void reserve(size_t r) {
|
hegyi@819
|
671 |
front.reserve(r);
|
hegyi@819
|
672 |
back.reserve(r);
|
hegyi@819
|
673 |
}
|
hegyi@819
|
674 |
|
hegyi@831
|
675 |
void reserveFront(size_t r) {}
|
hegyi@831
|
676 |
void reserveBack(size_t r) {}
|
hegyi@831
|
677 |
|
hegyi@819
|
678 |
private:
|
hegyi@819
|
679 |
bool empty() {
|
hegyi@819
|
680 |
return front.empty() && back.empty() && P.empty();
|
hegyi@819
|
681 |
}
|
hegyi@819
|
682 |
|
hegyi@831
|
683 |
GraphNode tail() const {
|
hegyi@819
|
684 |
if( ! front.empty() )
|
hegyi@819
|
685 |
return P.gr->tail(front[front.size()-1]);
|
hegyi@819
|
686 |
else if( ! P.empty() )
|
hegyi@819
|
687 |
return P.gr->tail(P.edges[0]);
|
hegyi@819
|
688 |
else if( ! back.empty() )
|
hegyi@819
|
689 |
return P.gr->tail(back[0]);
|
hegyi@819
|
690 |
else
|
hegyi@819
|
691 |
return INVALID;
|
hegyi@819
|
692 |
}
|
hegyi@831
|
693 |
GraphNode head() const {
|
hegyi@819
|
694 |
if( ! back.empty() )
|
hegyi@819
|
695 |
return P.gr->head(back[back.size()-1]);
|
hegyi@819
|
696 |
else if( ! P.empty() )
|
hegyi@819
|
697 |
return P.gr->head(P.edges[P.length()-1]);
|
hegyi@819
|
698 |
else if( ! front.empty() )
|
hegyi@819
|
699 |
return P.gr->head(front[0]);
|
hegyi@819
|
700 |
else
|
hegyi@819
|
701 |
return INVALID;
|
hegyi@819
|
702 |
}
|
hegyi@819
|
703 |
|
hegyi@819
|
704 |
};
|
hegyi@819
|
705 |
|
hegyi@819
|
706 |
};
|
hegyi@819
|
707 |
|
hegyi@819
|
708 |
|
hegyi@819
|
709 |
|
hegyi@819
|
710 |
|
hegyi@819
|
711 |
|
hegyi@819
|
712 |
|
hegyi@819
|
713 |
|
hegyi@819
|
714 |
|
hegyi@819
|
715 |
|
hegyi@819
|
716 |
|
hegyi@819
|
717 |
/**********************************************************************/
|
hegyi@819
|
718 |
|
hegyi@819
|
719 |
|
hegyi@819
|
720 |
/* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
|
hegyi@819
|
721 |
elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
|
hegyi@819
|
722 |
|
hegyi@819
|
723 |
template<typename Graph>
|
hegyi@819
|
724 |
class DynamicPath {
|
hegyi@819
|
725 |
|
hegyi@819
|
726 |
public:
|
hegyi@819
|
727 |
typedef typename Graph::Edge GraphEdge;
|
hegyi@819
|
728 |
typedef typename Graph::Node GraphNode;
|
hegyi@819
|
729 |
class NodeIt;
|
hegyi@819
|
730 |
class EdgeIt;
|
hegyi@819
|
731 |
|
hegyi@819
|
732 |
protected:
|
hegyi@819
|
733 |
Graph& G;
|
hegyi@819
|
734 |
// FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
|
hegyi@819
|
735 |
// iranyitasat:
|
hegyi@819
|
736 |
GraphNode _first, _last;
|
hegyi@819
|
737 |
typedef std::deque<GraphEdge> Container;
|
hegyi@819
|
738 |
Container edges;
|
hegyi@819
|
739 |
|
hegyi@819
|
740 |
public:
|
hegyi@819
|
741 |
|
hegyi@819
|
742 |
DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
|
hegyi@819
|
743 |
|
hegyi@819
|
744 |
/// Subpath defined by two nodes.
|
hegyi@819
|
745 |
/// Nodes may be in reversed order, then
|
hegyi@819
|
746 |
/// we contstruct the reversed path.
|
hegyi@819
|
747 |
DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
|
hegyi@819
|
748 |
/// Subpath defined by two edges. Contains edges in [a,b)
|
hegyi@819
|
749 |
/// It is an error if the two edges are not in order!
|
hegyi@819
|
750 |
DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
|
hegyi@819
|
751 |
|
hegyi@819
|
752 |
size_t length() const { return edges.size(); }
|
hegyi@831
|
753 |
GraphNode tail() const { return _first; }
|
hegyi@831
|
754 |
GraphNode head() const { return _last; }
|
hegyi@819
|
755 |
|
hegyi@819
|
756 |
NodeIt& first(NodeIt &n) const { return nth(n, 0); }
|
hegyi@819
|
757 |
EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
|
hegyi@819
|
758 |
template<typename It>
|
hegyi@819
|
759 |
It first() const {
|
hegyi@819
|
760 |
It e;
|
hegyi@819
|
761 |
first(e);
|
hegyi@819
|
762 |
return e;
|
hegyi@819
|
763 |
}
|
hegyi@819
|
764 |
|
hegyi@819
|
765 |
NodeIt& nth(NodeIt &, size_t) const;
|
hegyi@819
|
766 |
EdgeIt& nth(EdgeIt &, size_t) const;
|
hegyi@819
|
767 |
template<typename It>
|
hegyi@819
|
768 |
It nth(size_t n) const {
|
hegyi@819
|
769 |
It e;
|
hegyi@819
|
770 |
nth(e, n);
|
hegyi@819
|
771 |
return e;
|
hegyi@819
|
772 |
}
|
hegyi@819
|
773 |
|
hegyi@819
|
774 |
bool valid(const NodeIt &n) const { return n.idx <= length(); }
|
hegyi@819
|
775 |
bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
|
hegyi@819
|
776 |
|
hegyi@819
|
777 |
bool isForward(const EdgeIt &e) const { return e.forw; }
|
hegyi@819
|
778 |
|
hegyi@819
|
779 |
/// index of a node on the path. Returns length+2 for the invalid NodeIt
|
hegyi@819
|
780 |
int index(const NodeIt &n) const { return n.idx; }
|
hegyi@819
|
781 |
/// index of an edge on the path. Returns length+1 for the invalid EdgeIt
|
hegyi@819
|
782 |
int index(const EdgeIt &e) const { return e.it - edges.begin(); }
|
hegyi@819
|
783 |
|
hegyi@819
|
784 |
EdgeIt& next(EdgeIt &e) const;
|
hegyi@819
|
785 |
NodeIt& next(NodeIt &n) const;
|
hegyi@819
|
786 |
template <typename It>
|
hegyi@819
|
787 |
It getNext(It it) const {
|
hegyi@819
|
788 |
It tmp(it); return next(tmp);
|
hegyi@819
|
789 |
}
|
hegyi@819
|
790 |
|
hegyi@819
|
791 |
// A path is constructed using the following four functions.
|
hegyi@819
|
792 |
// They return false if the requested operation is inconsistent
|
hegyi@819
|
793 |
// with the path constructed so far.
|
hegyi@819
|
794 |
// If your path has only one edge you MUST set either "from" or "to"!
|
hegyi@819
|
795 |
// So you probably SHOULD call it in any case to be safe (and check the
|
hegyi@819
|
796 |
// returned value to check if your path is consistent with your idea).
|
hegyi@819
|
797 |
bool pushFront(const GraphEdge &e);
|
hegyi@819
|
798 |
bool pushBack(const GraphEdge &e);
|
hegyi@819
|
799 |
bool setFrom(const GraphNode &n);
|
hegyi@819
|
800 |
bool setTo(const GraphNode &n);
|
hegyi@819
|
801 |
|
hegyi@819
|
802 |
// WARNING: these two functions return the head/tail of an edge with
|
hegyi@819
|
803 |
// respect to the direction of the path!
|
hegyi@819
|
804 |
// So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
|
hegyi@819
|
805 |
// P.forward(e) is true (or the edge is a loop)!
|
hegyi@819
|
806 |
NodeIt head(const EdgeIt& e) const;
|
hegyi@819
|
807 |
NodeIt tail(const EdgeIt& e) const;
|
hegyi@819
|
808 |
|
hegyi@819
|
809 |
// FIXME: ezeknek valami jobb nev kellene!!!
|
hegyi@819
|
810 |
GraphEdge graphEdge(const EdgeIt& e) const;
|
hegyi@819
|
811 |
GraphNode graphNode(const NodeIt& n) const;
|
hegyi@819
|
812 |
|
hegyi@819
|
813 |
|
hegyi@819
|
814 |
/*** Iterator classes ***/
|
hegyi@819
|
815 |
class EdgeIt {
|
hegyi@819
|
816 |
friend class DynamicPath;
|
hegyi@819
|
817 |
|
hegyi@819
|
818 |
typename Container::const_iterator it;
|
hegyi@819
|
819 |
bool forw;
|
hegyi@819
|
820 |
public:
|
hegyi@819
|
821 |
// FIXME: jarna neki ilyen is...
|
hegyi@819
|
822 |
// EdgeIt(Invalid);
|
hegyi@819
|
823 |
|
hegyi@819
|
824 |
bool forward() const { return forw; }
|
hegyi@819
|
825 |
|
hegyi@819
|
826 |
bool operator==(const EdgeIt& e) const { return it==e.it; }
|
hegyi@819
|
827 |
bool operator!=(const EdgeIt& e) const { return it!=e.it; }
|
hegyi@819
|
828 |
bool operator<(const EdgeIt& e) const { return it<e.it; }
|
hegyi@819
|
829 |
};
|
hegyi@819
|
830 |
|
hegyi@819
|
831 |
class NodeIt {
|
hegyi@819
|
832 |
friend class DynamicPath;
|
hegyi@819
|
833 |
|
hegyi@819
|
834 |
size_t idx;
|
hegyi@819
|
835 |
bool tail; // Is this node the tail of the edge with same idx?
|
hegyi@819
|
836 |
|
hegyi@819
|
837 |
public:
|
hegyi@819
|
838 |
// FIXME: jarna neki ilyen is...
|
hegyi@819
|
839 |
// NodeIt(Invalid);
|
hegyi@819
|
840 |
|
hegyi@819
|
841 |
bool operator==(const NodeIt& n) const { return idx==n.idx; }
|
hegyi@819
|
842 |
bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
|
hegyi@819
|
843 |
bool operator<(const NodeIt& n) const { return idx<n.idx; }
|
hegyi@819
|
844 |
};
|
hegyi@819
|
845 |
|
hegyi@819
|
846 |
private:
|
hegyi@819
|
847 |
bool edgeIncident(const GraphEdge &e, const GraphNode &a,
|
hegyi@819
|
848 |
GraphNode &b);
|
hegyi@819
|
849 |
bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
|
hegyi@819
|
850 |
};
|
hegyi@819
|
851 |
|
hegyi@819
|
852 |
template<typename Gr>
|
hegyi@819
|
853 |
typename DynamicPath<Gr>::EdgeIt&
|
hegyi@819
|
854 |
DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
|
hegyi@819
|
855 |
if( e.it == edges.end() )
|
hegyi@819
|
856 |
return e;
|
hegyi@819
|
857 |
|
hegyi@819
|
858 |
GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
|
hegyi@819
|
859 |
++e.it;
|
hegyi@819
|
860 |
|
hegyi@819
|
861 |
// Invalid edgeit is always forward :)
|
hegyi@819
|
862 |
if( e.it == edges.end() ) {
|
hegyi@819
|
863 |
e.forw = true;
|
hegyi@819
|
864 |
return e;
|
hegyi@819
|
865 |
}
|
hegyi@819
|
866 |
|
hegyi@819
|
867 |
e.forw = ( G.tail(*e.it) == common_node );
|
hegyi@819
|
868 |
return e;
|
hegyi@819
|
869 |
}
|
hegyi@819
|
870 |
|
hegyi@819
|
871 |
template<typename Gr>
|
hegyi@819
|
872 |
typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
|
hegyi@819
|
873 |
if( n.idx >= length() ) {
|
hegyi@819
|
874 |
// FIXME: invalid
|
hegyi@819
|
875 |
n.idx = length()+1;
|
hegyi@819
|
876 |
return n;
|
hegyi@819
|
877 |
}
|
hegyi@819
|
878 |
|
hegyi@819
|
879 |
|
hegyi@819
|
880 |
GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
|
hegyi@819
|
881 |
G.tail(edges[n.idx]) );
|
hegyi@819
|
882 |
++n.idx;
|
hegyi@819
|
883 |
if( n.idx < length() ) {
|
hegyi@819
|
884 |
n.tail = ( next_node == G.tail(edges[n.idx]) );
|
hegyi@819
|
885 |
}
|
hegyi@819
|
886 |
else {
|
hegyi@819
|
887 |
n.tail = true;
|
hegyi@819
|
888 |
}
|
hegyi@819
|
889 |
|
hegyi@819
|
890 |
return n;
|
hegyi@819
|
891 |
}
|
hegyi@819
|
892 |
|
hegyi@819
|
893 |
template<typename Gr>
|
hegyi@819
|
894 |
bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
|
hegyi@819
|
895 |
GraphNode &b) {
|
hegyi@819
|
896 |
if( G.tail(e) == a ) {
|
hegyi@819
|
897 |
b=G.head(e);
|
hegyi@819
|
898 |
return true;
|
hegyi@819
|
899 |
}
|
hegyi@819
|
900 |
if( G.head(e) == a ) {
|
hegyi@819
|
901 |
b=G.tail(e);
|
hegyi@819
|
902 |
return true;
|
hegyi@819
|
903 |
}
|
hegyi@819
|
904 |
return false;
|
hegyi@819
|
905 |
}
|
hegyi@819
|
906 |
|
hegyi@819
|
907 |
template<typename Gr>
|
hegyi@819
|
908 |
bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
|
hegyi@819
|
909 |
const GraphEdge &f) {
|
hegyi@819
|
910 |
if( edgeIncident(f, G.tail(e), _last) ) {
|
hegyi@819
|
911 |
_first = G.head(e);
|
hegyi@819
|
912 |
return true;
|
hegyi@819
|
913 |
}
|
hegyi@819
|
914 |
if( edgeIncident(f, G.head(e), _last) ) {
|
hegyi@819
|
915 |
_first = G.tail(e);
|
hegyi@819
|
916 |
return true;
|
hegyi@819
|
917 |
}
|
hegyi@819
|
918 |
return false;
|
hegyi@819
|
919 |
}
|
hegyi@819
|
920 |
|
hegyi@819
|
921 |
template<typename Gr>
|
hegyi@819
|
922 |
bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
|
hegyi@819
|
923 |
if( G.valid(_first) ) {
|
hegyi@819
|
924 |
if( edgeIncident(e, _first, _first) ) {
|
hegyi@819
|
925 |
edges.push_front(e);
|
hegyi@819
|
926 |
return true;
|
hegyi@819
|
927 |
}
|
hegyi@819
|
928 |
else
|
hegyi@819
|
929 |
return false;
|
hegyi@819
|
930 |
}
|
hegyi@819
|
931 |
else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
|
hegyi@819
|
932 |
edges.push_front(e);
|
hegyi@819
|
933 |
return true;
|
hegyi@819
|
934 |
}
|
hegyi@819
|
935 |
else
|
hegyi@819
|
936 |
return false;
|
hegyi@819
|
937 |
}
|
hegyi@819
|
938 |
|
hegyi@819
|
939 |
template<typename Gr>
|
hegyi@819
|
940 |
bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
|
hegyi@819
|
941 |
if( G.valid(_last) ) {
|
hegyi@819
|
942 |
if( edgeIncident(e, _last, _last) ) {
|
hegyi@819
|
943 |
edges.push_back(e);
|
hegyi@819
|
944 |
return true;
|
hegyi@819
|
945 |
}
|
hegyi@819
|
946 |
else
|
hegyi@819
|
947 |
return false;
|
hegyi@819
|
948 |
}
|
hegyi@819
|
949 |
else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
|
hegyi@819
|
950 |
edges.push_back(e);
|
hegyi@819
|
951 |
return true;
|
hegyi@819
|
952 |
}
|
hegyi@819
|
953 |
else
|
hegyi@819
|
954 |
return false;
|
hegyi@819
|
955 |
}
|
hegyi@819
|
956 |
|
hegyi@819
|
957 |
|
hegyi@819
|
958 |
template<typename Gr>
|
hegyi@819
|
959 |
bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
|
hegyi@819
|
960 |
if( G.valid(_first) ) {
|
hegyi@819
|
961 |
return _first == n;
|
hegyi@819
|
962 |
}
|
hegyi@819
|
963 |
else {
|
hegyi@819
|
964 |
if( length() > 0) {
|
hegyi@819
|
965 |
if( edgeIncident(edges[0], n, _last) ) {
|
hegyi@819
|
966 |
_first = n;
|
hegyi@819
|
967 |
return true;
|
hegyi@819
|
968 |
}
|
hegyi@819
|
969 |
else return false;
|
hegyi@819
|
970 |
}
|
hegyi@819
|
971 |
else {
|
hegyi@819
|
972 |
_first = _last = n;
|
hegyi@819
|
973 |
return true;
|
hegyi@819
|
974 |
}
|
hegyi@819
|
975 |
}
|
hegyi@819
|
976 |
}
|
hegyi@819
|
977 |
|
hegyi@819
|
978 |
template<typename Gr>
|
hegyi@819
|
979 |
bool DynamicPath<Gr>::setTo(const GraphNode &n) {
|
hegyi@819
|
980 |
if( G.valid(_last) ) {
|
hegyi@819
|
981 |
return _last == n;
|
hegyi@819
|
982 |
}
|
hegyi@819
|
983 |
else {
|
hegyi@819
|
984 |
if( length() > 0) {
|
hegyi@819
|
985 |
if( edgeIncident(edges[0], n, _first) ) {
|
hegyi@819
|
986 |
_last = n;
|
hegyi@819
|
987 |
return true;
|
hegyi@819
|
988 |
}
|
hegyi@819
|
989 |
else return false;
|
hegyi@819
|
990 |
}
|
hegyi@819
|
991 |
else {
|
hegyi@819
|
992 |
_first = _last = n;
|
hegyi@819
|
993 |
return true;
|
hegyi@819
|
994 |
}
|
hegyi@819
|
995 |
}
|
hegyi@819
|
996 |
}
|
hegyi@819
|
997 |
|
hegyi@819
|
998 |
|
hegyi@819
|
999 |
template<typename Gr>
|
hegyi@819
|
1000 |
typename DynamicPath<Gr>::NodeIt
|
hegyi@819
|
1001 |
DynamicPath<Gr>::tail(const EdgeIt& e) const {
|
hegyi@819
|
1002 |
NodeIt n;
|
hegyi@819
|
1003 |
|
hegyi@819
|
1004 |
if( e.it == edges.end() ) {
|
hegyi@819
|
1005 |
// FIXME: invalid-> invalid
|
hegyi@819
|
1006 |
n.idx = length() + 1;
|
hegyi@819
|
1007 |
n.tail = true;
|
hegyi@819
|
1008 |
return n;
|
hegyi@819
|
1009 |
}
|
hegyi@819
|
1010 |
|
hegyi@819
|
1011 |
n.idx = e.it-edges.begin();
|
hegyi@819
|
1012 |
n.tail = e.forw;
|
hegyi@819
|
1013 |
return n;
|
hegyi@819
|
1014 |
}
|
hegyi@819
|
1015 |
|
hegyi@819
|
1016 |
template<typename Gr>
|
hegyi@819
|
1017 |
typename DynamicPath<Gr>::NodeIt
|
hegyi@819
|
1018 |
DynamicPath<Gr>::head(const EdgeIt& e) const {
|
hegyi@819
|
1019 |
if( e.it == edges.end()-1 ) {
|
hegyi@819
|
1020 |
return _last;
|
hegyi@819
|
1021 |
}
|
hegyi@819
|
1022 |
|
hegyi@819
|
1023 |
EdgeIt next_edge = e;
|
hegyi@819
|
1024 |
next(next_edge);
|
hegyi@819
|
1025 |
return tail(next_edge);
|
hegyi@819
|
1026 |
}
|
hegyi@819
|
1027 |
|
hegyi@819
|
1028 |
template<typename Gr>
|
hegyi@819
|
1029 |
typename DynamicPath<Gr>::GraphEdge
|
hegyi@819
|
1030 |
DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
|
hegyi@819
|
1031 |
if( e.it != edges.end() ) {
|
hegyi@819
|
1032 |
return *e.it;
|
hegyi@819
|
1033 |
}
|
hegyi@819
|
1034 |
else {
|
hegyi@819
|
1035 |
return INVALID;
|
hegyi@819
|
1036 |
}
|
hegyi@819
|
1037 |
}
|
hegyi@819
|
1038 |
|
hegyi@819
|
1039 |
template<typename Gr>
|
hegyi@819
|
1040 |
typename DynamicPath<Gr>::GraphNode
|
hegyi@819
|
1041 |
DynamicPath<Gr>::graphNode(const NodeIt& n) const {
|
hegyi@819
|
1042 |
if( n.idx < length() ) {
|
hegyi@819
|
1043 |
return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
|
hegyi@819
|
1044 |
}
|
hegyi@819
|
1045 |
else if( n.idx == length() ) {
|
hegyi@819
|
1046 |
return _last;
|
hegyi@819
|
1047 |
}
|
hegyi@819
|
1048 |
else {
|
hegyi@819
|
1049 |
return INVALID;
|
hegyi@819
|
1050 |
}
|
hegyi@819
|
1051 |
}
|
hegyi@819
|
1052 |
|
hegyi@819
|
1053 |
template<typename Gr>
|
hegyi@819
|
1054 |
typename DynamicPath<Gr>::EdgeIt&
|
hegyi@819
|
1055 |
DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
|
hegyi@819
|
1056 |
if( k>=length() ) {
|
hegyi@819
|
1057 |
// FIXME: invalid EdgeIt
|
hegyi@819
|
1058 |
e.it = edges.end();
|
hegyi@819
|
1059 |
e.forw = true;
|
hegyi@819
|
1060 |
return e;
|
hegyi@819
|
1061 |
}
|
hegyi@819
|
1062 |
|
hegyi@819
|
1063 |
e.it = edges.begin()+k;
|
hegyi@819
|
1064 |
if(k==0) {
|
hegyi@819
|
1065 |
e.forw = ( G.tail(*e.it) == _first );
|
hegyi@819
|
1066 |
}
|
hegyi@819
|
1067 |
else {
|
hegyi@819
|
1068 |
e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
|
hegyi@819
|
1069 |
G.tail(*e.it) == G.head(edges[k-1]) );
|
hegyi@819
|
1070 |
}
|
hegyi@819
|
1071 |
return e;
|
hegyi@819
|
1072 |
}
|
hegyi@819
|
1073 |
|
hegyi@819
|
1074 |
template<typename Gr>
|
hegyi@819
|
1075 |
typename DynamicPath<Gr>::NodeIt&
|
hegyi@819
|
1076 |
DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
|
hegyi@819
|
1077 |
if( k>length() ) {
|
hegyi@819
|
1078 |
// FIXME: invalid NodeIt
|
hegyi@819
|
1079 |
n.idx = length()+1;
|
hegyi@819
|
1080 |
n.tail = true;
|
hegyi@819
|
1081 |
return n;
|
hegyi@819
|
1082 |
}
|
hegyi@819
|
1083 |
if( k==length() ) {
|
hegyi@819
|
1084 |
n.idx = length();
|
hegyi@819
|
1085 |
n.tail = true;
|
hegyi@819
|
1086 |
return n;
|
hegyi@819
|
1087 |
}
|
hegyi@819
|
1088 |
n = tail(nth<EdgeIt>(k));
|
hegyi@819
|
1089 |
return n;
|
hegyi@819
|
1090 |
}
|
hegyi@819
|
1091 |
|
hegyi@819
|
1092 |
// Reszut konstruktorok:
|
hegyi@819
|
1093 |
|
hegyi@819
|
1094 |
|
hegyi@819
|
1095 |
template<typename Gr>
|
hegyi@819
|
1096 |
DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
|
hegyi@819
|
1097 |
const EdgeIt &b) :
|
hegyi@819
|
1098 |
G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
|
hegyi@819
|
1099 |
{
|
hegyi@819
|
1100 |
if( G.valid(P._first) && a.it < P.edges.end() ) {
|
hegyi@819
|
1101 |
_first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
|
hegyi@819
|
1102 |
if( b.it < P.edges.end() ) {
|
hegyi@819
|
1103 |
_last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
|
hegyi@819
|
1104 |
}
|
hegyi@819
|
1105 |
else {
|
hegyi@819
|
1106 |
_last = P._last;
|
hegyi@819
|
1107 |
}
|
hegyi@819
|
1108 |
}
|
hegyi@819
|
1109 |
}
|
hegyi@819
|
1110 |
|
hegyi@819
|
1111 |
template<typename Gr>
|
hegyi@819
|
1112 |
DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
|
hegyi@819
|
1113 |
const NodeIt &b) : G(P.G)
|
hegyi@819
|
1114 |
{
|
hegyi@819
|
1115 |
if( !P.valid(a) || !P.valid(b) )
|
hegyi@819
|
1116 |
return;
|
hegyi@819
|
1117 |
|
hegyi@819
|
1118 |
int ai = a.idx, bi = b.idx;
|
hegyi@819
|
1119 |
if( bi<ai )
|
hegyi@819
|
1120 |
std::swap(ai,bi);
|
hegyi@819
|
1121 |
|
hegyi@819
|
1122 |
edges.resize(bi-ai);
|
hegyi@819
|
1123 |
copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
|
hegyi@819
|
1124 |
|
hegyi@819
|
1125 |
_first = P.graphNode(a);
|
hegyi@819
|
1126 |
_last = P.graphNode(b);
|
hegyi@819
|
1127 |
}
|
hegyi@819
|
1128 |
|
hegyi@819
|
1129 |
///@}
|
hegyi@819
|
1130 |
|
hegyi@819
|
1131 |
} // namespace hugo
|
hegyi@819
|
1132 |
|
hegyi@819
|
1133 |
#endif // HUGO_PATH_H
|