26 #define LEMON_PATH_H |
26 #define LEMON_PATH_H |
27 |
27 |
28 #include <vector> |
28 #include <vector> |
29 #include <algorithm> |
29 #include <algorithm> |
30 |
30 |
|
31 #include <lemon/path_utils.h> |
31 #include <lemon/error.h> |
32 #include <lemon/error.h> |
32 #include <lemon/bits/invalid.h> |
33 #include <lemon/bits/invalid.h> |
33 |
34 |
34 namespace lemon { |
35 namespace lemon { |
35 |
36 |
36 /// \addtogroup paths |
37 /// \addtogroup paths |
37 /// @{ |
38 /// @{ |
38 |
39 |
39 |
40 |
40 //! \brief A structure for representing directed paths in a graph. |
41 /// \brief A structure for representing directed paths in a graph. |
41 //! |
42 /// |
42 //! A structure for representing directed path in a graph. |
43 /// A structure for representing directed path in a graph. |
43 //! \param Graph The graph type in which the path is. |
44 /// \param Graph The graph type in which the path is. |
44 //! |
45 /// |
45 //! In a sense, the path can be treated as a graph, for is has \c NodeIt |
46 /// In a sense, the path can be treated as a list of edges. The |
46 //! and \c EdgeIt with the same usage. These types converts to the \c Node |
47 /// lemon path type stores just this list. As a consequence it |
47 //! and \c Edge of the original graph. |
48 /// cannot enumerate the nodes in the path and the zero length paths |
48 //! |
49 /// cannot store the source. |
49 //! \todo Thoroughfully check all the range and consistency tests. |
50 /// |
50 template<typename Graph> |
51 /// This implementation is a back and front insertable and erasable |
|
52 /// path type. It can be indexed in O(1) time. The front and back |
|
53 /// insertion and erasure is amortized O(1) time. The |
|
54 /// impelementation is based on two opposite organized vectors. |
|
55 template <typename _Graph> |
51 class Path { |
56 class Path { |
52 public: |
57 public: |
53 /// Edge type of the underlying graph. |
58 |
|
59 typedef _Graph Graph; |
54 typedef typename Graph::Edge Edge; |
60 typedef typename Graph::Edge Edge; |
55 /// Node type of the underlying graph. |
61 |
56 typedef typename Graph::Node Node; |
62 /// \brief Default constructor |
57 |
63 /// |
58 class NodeIt; |
64 /// Default constructor |
59 class EdgeIt; |
65 Path() {} |
60 |
66 |
61 struct PathError : public LogicError { |
67 /// \brief Template copy constructor |
62 virtual const char* what() const throw() { |
68 /// |
63 return "lemon::PathError"; |
69 /// This path can be initialized with any other path type. It just |
64 } |
70 /// makes a copy of the given path. |
65 }; |
71 template <typename CPath> |
66 |
72 Path(const CPath& cpath) { |
67 public: |
73 copyPath(*this, cpath); |
68 |
74 } |
69 /// \brief Constructor |
75 |
70 /// |
76 /// \brief Template copy assignment |
71 /// Constructor |
77 /// |
72 /// \param _G The graph in which the path is. |
78 /// This path can be initialized with any other path type. It just |
73 Path(const Graph &_graph) : graph(&_graph), start(INVALID) {} |
79 /// makes a copy of the given path. |
74 |
80 template <typename CPath> |
75 /// \brief Subpath constructor. |
81 Path& operator=(const CPath& cpath) { |
76 /// |
82 copyPath(*this, cpath); |
77 /// Subpath defined by two nodes. |
83 return *this; |
78 /// \warning It is an error if the two edges are not in order! |
84 } |
79 Path(const Path &other, const NodeIt &a, const NodeIt &b) { |
85 |
80 graph = other.graph; |
86 /// \brief Lemon style iterator for path edges |
81 start = a; |
87 /// |
82 edges.insert(edges.end(), |
88 /// This class is used to iterate on the edges of the paths. |
83 other.edges.begin() + a.id, other.edges.begin() + b.id); |
|
84 } |
|
85 |
|
86 /// \brief Subpath constructor. |
|
87 /// |
|
88 /// Subpath defined by two edges. Contains edges in [a,b) |
|
89 /// \warning It is an error if the two edges are not in order! |
|
90 Path(const Path &other, const EdgeIt &a, const EdgeIt &b) { |
|
91 graph = other.graph; |
|
92 start = graph->source(a); |
|
93 edges.insert(edges.end(), |
|
94 other.edges.begin() + a.id, other.edges.begin() + b.id); |
|
95 } |
|
96 |
|
97 /// \brief Length of the path. |
|
98 /// |
|
99 /// The number of the edges in the path. It can be zero if the |
|
100 /// path has only one node or it is empty. |
|
101 int length() const { return edges.size(); } |
|
102 |
|
103 /// \brief Returns whether the path is empty. |
|
104 /// |
|
105 /// Returns true when the path does not contain neither edge nor |
|
106 /// node. |
|
107 bool empty() const { return start == INVALID; } |
|
108 |
|
109 /// \brief Resets the path to an empty path. |
|
110 /// |
|
111 /// Resets the path to an empty path. |
|
112 void clear() { edges.clear(); start = INVALID; } |
|
113 |
|
114 /// \brief Starting point of the path. |
|
115 /// |
|
116 /// Starting point of the path. |
|
117 /// Returns INVALID if the path is empty. |
|
118 Node source() const { |
|
119 return start; |
|
120 } |
|
121 /// \brief End point of the path. |
|
122 /// |
|
123 /// End point of the path. |
|
124 /// Returns INVALID if the path is empty. |
|
125 Node target() const { |
|
126 return length() == 0 ? start : graph->target(edges[length()-1]); |
|
127 } |
|
128 |
|
129 /// \brief Gives back a node iterator to point to the node of a |
|
130 /// given index. |
|
131 /// |
|
132 /// Gives back a node iterator to point to the node of a given |
|
133 /// index. |
|
134 /// \pre n should less or equal to \c length() |
|
135 NodeIt nthNode(int n) const { |
|
136 return NodeIt(*this, n); |
|
137 } |
|
138 |
|
139 /// \brief Gives back an edge iterator to point to the edge of a |
|
140 /// given index. |
|
141 /// |
|
142 /// Gives back an edge iterator to point to the node of a given |
|
143 /// index. |
|
144 /// \pre n should less than \c length() |
|
145 EdgeIt nthEdge(int n) const { |
|
146 return EdgeIt(*this, n); |
|
147 } |
|
148 |
|
149 /// \brief Returns node iterator pointing to the source node of the |
|
150 /// given edge iterator. |
|
151 /// |
|
152 /// Returns node iterator pointing to the source node of the given |
|
153 /// edge iterator. |
|
154 NodeIt source(const EdgeIt& e) const { |
|
155 return NodeIt(*this, e.id); |
|
156 } |
|
157 |
|
158 /// \brief Returns node iterator pointing to the target node of the |
|
159 /// given edge iterator. |
|
160 /// |
|
161 /// Returns node iterator pointing to the target node of the given |
|
162 /// edge iterator. |
|
163 NodeIt target(const EdgeIt& e) const { |
|
164 return NodeIt(*this, e.id + 1); |
|
165 } |
|
166 |
|
167 |
|
168 /// \brief Iterator class to iterate on the nodes of the paths |
|
169 /// |
|
170 /// This class is used to iterate on the nodes of the paths |
|
171 /// |
|
172 /// Of course it converts to Graph::Node |
|
173 class NodeIt { |
|
174 friend class Path; |
|
175 public: |
|
176 |
|
177 /// \brief Default constructor |
|
178 /// |
|
179 /// Default constructor |
|
180 NodeIt() {} |
|
181 |
|
182 /// \brief Invalid constructor |
|
183 /// |
|
184 /// Invalid constructor |
|
185 NodeIt(Invalid) : id(-1), path(0) {} |
|
186 |
|
187 /// \brief Constructor with starting point |
|
188 /// |
|
189 /// Constructor with starting point |
|
190 NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { |
|
191 if (id > path->length()) id = -1; |
|
192 } |
|
193 |
|
194 /// \brief Conversion to Graph::Node |
|
195 /// |
|
196 /// Conversion to Graph::Node |
|
197 operator Node() const { |
|
198 if (id > 0) { |
|
199 return path->graph->target(path->edges[id - 1]); |
|
200 } else if (id == 0) { |
|
201 return path->start; |
|
202 } else { |
|
203 return INVALID; |
|
204 } |
|
205 } |
|
206 |
|
207 /// \brief Steps to the next node |
|
208 /// |
|
209 /// Steps to the next node |
|
210 NodeIt& operator++() { |
|
211 ++id; |
|
212 if (id > path->length()) id = -1; |
|
213 return *this; |
|
214 } |
|
215 |
|
216 /// \brief Comparison operator |
|
217 /// |
|
218 /// Comparison operator |
|
219 bool operator==(const NodeIt& n) const { return id == n.id; } |
|
220 |
|
221 /// \brief Comparison operator |
|
222 /// |
|
223 /// Comparison operator |
|
224 bool operator!=(const NodeIt& n) const { return id != n.id; } |
|
225 |
|
226 /// \brief Comparison operator |
|
227 /// |
|
228 /// Comparison operator |
|
229 bool operator<(const NodeIt& n) const { return id < n.id; } |
|
230 |
|
231 private: |
|
232 int id; |
|
233 const Path *path; |
|
234 }; |
|
235 |
|
236 /// \brief Iterator class to iterate on the edges of the paths |
|
237 /// |
|
238 /// This class is used to iterate on the edges of the paths |
|
239 /// Of course it converts to Graph::Edge |
|
240 class EdgeIt { |
89 class EdgeIt { |
241 friend class Path; |
90 friend class Path; |
242 public: |
91 public: |
243 |
|
244 /// \brief Default constructor |
92 /// \brief Default constructor |
245 /// |
93 EdgeIt() {} |
|
94 /// \brief Invalid constructor |
|
95 EdgeIt(Invalid) : path(0), idx(-1) {} |
|
96 /// \brief Initializate the constructor to the first edge of path |
|
97 EdgeIt(const Path &_path) |
|
98 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
|
99 |
|
100 private: |
|
101 |
|
102 EdgeIt(const Path &_path, int _idx) |
|
103 : idx(_idx), path(&_path) {} |
|
104 |
|
105 public: |
|
106 |
|
107 /// \brief Conversion to Edge |
|
108 operator const Edge&() const { |
|
109 return path->nth(idx); |
|
110 } |
|
111 |
|
112 /// \brief Next edge |
|
113 EdgeIt& operator++() { |
|
114 ++idx; |
|
115 if (idx >= path->length()) idx = -1; |
|
116 return *this; |
|
117 } |
|
118 |
|
119 /// \brief Comparison operator |
|
120 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
|
121 /// \brief Comparison operator |
|
122 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
|
123 /// \brief Comparison operator |
|
124 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
|
125 |
|
126 private: |
|
127 const Path *path; |
|
128 int idx; |
|
129 }; |
|
130 |
|
131 /// \brief Length of the path. |
|
132 int length() const { return head.size() + tail.size(); } |
|
133 /// \brief Returns whether the path is empty. |
|
134 bool empty() const { return head.empty() && tail.empty(); } |
|
135 |
|
136 /// \brief Resets the path to an empty path. |
|
137 void clear() { head.clear(); tail.clear(); } |
|
138 |
|
139 /// \brief Gives back the nth edge. |
|
140 /// |
|
141 /// \pre n is in the [0..length() - 1] range |
|
142 const Edge& nth(int n) const { |
|
143 return n < (int)head.size() ? *(head.rbegin() + n) : |
|
144 *(tail.begin() + (n - head.size())); |
|
145 } |
|
146 |
|
147 /// \brief Initializes edge iterator to point to the nth edge |
|
148 /// |
|
149 /// \pre n is in the [0..length() - 1] range |
|
150 EdgeIt nthIt(int n) const { |
|
151 return EdgeIt(*this, n); |
|
152 } |
|
153 |
|
154 /// \brief Gives back the first edge of the path |
|
155 const Edge& front() const { |
|
156 return head.empty() ? tail.front() : head.back(); |
|
157 } |
|
158 |
|
159 /// \brief Add a new edge before the current path |
|
160 void addFront(const Edge& edge) { |
|
161 head.push_back(edge); |
|
162 } |
|
163 |
|
164 /// \brief Erase the first edge of the path |
|
165 void eraseFront() { |
|
166 if (!head.empty()) { |
|
167 head.pop_back(); |
|
168 } else { |
|
169 head.clear(); |
|
170 int halfsize = tail.size() / 2; |
|
171 head.resize(halfsize); |
|
172 std::copy(tail.begin() + 1, tail.begin() + halfsize + 1, |
|
173 head.rbegin()); |
|
174 std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin()); |
|
175 tail.resize(tail.size() - halfsize - 1); |
|
176 } |
|
177 } |
|
178 |
|
179 /// \brief Gives back the last edge of the path |
|
180 const Edge& back() const { |
|
181 return tail.empty() ? head.front() : tail.back(); |
|
182 } |
|
183 |
|
184 /// \brief Add a new edge behind the current path |
|
185 void addBack(const Edge& edge) { |
|
186 tail.push_back(edge); |
|
187 } |
|
188 |
|
189 /// \brief Erase the last edge of the path |
|
190 void eraseBack() { |
|
191 if (!tail.empty()) { |
|
192 tail.pop_back(); |
|
193 } else { |
|
194 int halfsize = head.size() / 2; |
|
195 tail.resize(halfsize); |
|
196 std::copy(head.begin() + 1, head.begin() + halfsize + 1, |
|
197 tail.rbegin()); |
|
198 std::copy(head.begin() + halfsize + 1, head.end(), head.begin()); |
|
199 head.resize(head.size() - halfsize - 1); |
|
200 } |
|
201 } |
|
202 |
|
203 |
|
204 |
|
205 typedef True BuildTag; |
|
206 |
|
207 template <typename CPath> |
|
208 void build(const CPath& path) { |
|
209 int len = path.length(); |
|
210 tail.reserve(len); |
|
211 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) { |
|
212 tail.push_back(it); |
|
213 } |
|
214 } |
|
215 |
|
216 template <typename CPath> |
|
217 void buildRev(const CPath& path) { |
|
218 int len = path.length(); |
|
219 head.reserve(len); |
|
220 for (typename CPath::RevIt it(path); it != INVALID; ++it) { |
|
221 head.push_back(it); |
|
222 } |
|
223 } |
|
224 |
|
225 protected: |
|
226 typedef std::vector<Edge> Container; |
|
227 Container head, tail; |
|
228 |
|
229 }; |
|
230 |
|
231 /// \brief A structure for representing directed paths in a graph. |
|
232 /// |
|
233 /// A structure for representing directed path in a graph. |
|
234 /// \param Graph The graph type in which the path is. |
|
235 /// |
|
236 /// In a sense, the path can be treated as a list of edges. The |
|
237 /// lemon path type stores just this list. As a consequence it |
|
238 /// cannot enumerate the nodes in the path and the zero length paths |
|
239 /// cannot store the source. |
|
240 /// |
|
241 /// This implementation is a just back insertable and erasable path |
|
242 /// type. It can be indexed in O(1) time. The back insertion and |
|
243 /// erasure is amortized O(1) time. This implementation is faster |
|
244 /// then the \c Path type because it use just one vector for the |
|
245 /// edges. |
|
246 template <typename _Graph> |
|
247 class SimplePath { |
|
248 public: |
|
249 |
|
250 typedef _Graph Graph; |
|
251 typedef typename Graph::Edge Edge; |
|
252 |
|
253 /// \brief Default constructor |
|
254 /// |
|
255 /// Default constructor |
|
256 SimplePath() {} |
|
257 |
|
258 /// \brief Template copy constructor |
|
259 /// |
|
260 /// This path can be initialized with any other path type. It just |
|
261 /// makes a copy of the given path. |
|
262 template <typename CPath> |
|
263 SimplePath(const CPath& cpath) { |
|
264 copyPath(*this, cpath); |
|
265 } |
|
266 |
|
267 /// \brief Template copy assignment |
|
268 /// |
|
269 /// This path can be initialized with any other path type. It just |
|
270 /// makes a copy of the given path. |
|
271 template <typename CPath> |
|
272 SimplePath& operator=(const CPath& cpath) { |
|
273 copyPath(*this, cpath); |
|
274 return *this; |
|
275 } |
|
276 |
|
277 /// \brief Iterator class to iterate on the edges of the paths |
|
278 /// |
|
279 /// This class is used to iterate on the edges of the paths |
|
280 /// |
|
281 /// Of course it converts to Graph::Edge |
|
282 class EdgeIt { |
|
283 friend class SimplePath; |
|
284 public: |
246 /// Default constructor |
285 /// Default constructor |
247 EdgeIt() {} |
286 EdgeIt() {} |
248 |
|
249 /// \brief Invalid constructor |
|
250 /// |
|
251 /// Invalid constructor |
287 /// Invalid constructor |
252 EdgeIt(Invalid) : id(-1), path(0) {} |
288 EdgeIt(Invalid) : path(0), idx(-1) {} |
253 |
289 /// \brief Initializate the constructor to the first edge of path |
254 /// \brief Constructor with starting point |
290 EdgeIt(const SimplePath &_path) |
255 /// |
291 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
|
292 |
|
293 private: |
|
294 |
256 /// Constructor with starting point |
295 /// Constructor with starting point |
257 EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { |
296 EdgeIt(const SimplePath &_path, int _idx) |
258 if (id >= path->length()) id = -1; |
297 : idx(_idx), path(&_path) {} |
259 } |
298 |
260 |
299 public: |
261 /// \brief Conversion to Graph::Edge |
300 |
262 /// |
301 ///Conversion to Graph::Edge |
263 /// Conversion to Graph::Edge |
302 operator const Edge&() const { |
264 operator Edge() const { |
303 return path->nth(idx); |
265 return id != -1 ? path->edges[id] : INVALID; |
304 } |
266 } |
305 |
267 |
306 /// Next edge |
268 /// \brief Steps to the next edge |
|
269 /// |
|
270 /// Steps to the next edge |
|
271 EdgeIt& operator++() { |
307 EdgeIt& operator++() { |
272 ++id; |
308 ++idx; |
273 if (id >= path->length()) id = -1; |
309 if (idx >= path->length()) idx = -1; |
274 return *this; |
310 return *this; |
275 } |
311 } |
276 |
312 |
277 /// \brief Comparison operator |
|
278 /// |
|
279 /// Comparison operator |
313 /// Comparison operator |
280 bool operator==(const EdgeIt& e) const { return id == e.id; } |
314 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
281 |
|
282 /// \brief Comparison operator |
|
283 /// |
|
284 /// Comparison operator |
315 /// Comparison operator |
285 bool operator!=(const EdgeIt& e) const { return id != e.id; } |
316 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
286 |
|
287 /// \brief Comparison operator |
|
288 /// |
|
289 /// Comparison operator |
317 /// Comparison operator |
290 bool operator<(const EdgeIt& e) const { return id < e.id; } |
318 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
291 |
319 |
292 private: |
320 private: |
293 |
321 const SimplePath *path; |
294 int id; |
322 int idx; |
295 const Path *path; |
|
296 }; |
323 }; |
297 |
324 |
|
325 /// \brief Length of the path. |
|
326 int length() const { return data.size(); } |
|
327 /// \brief Returns whether the path is empty. |
|
328 bool empty() const { return data.empty(); } |
|
329 |
|
330 /// \brief Resets the path to an empty path. |
|
331 void clear() { data.clear(); } |
|
332 |
|
333 /// \brief Gives back the nth edge. |
|
334 /// |
|
335 /// \pre n is in the [0..length() - 1] range |
|
336 const Edge& nth(int n) const { |
|
337 return data[n]; |
|
338 } |
|
339 |
|
340 /// \brief Initializes edge iterator to point to the nth edge. |
|
341 EdgeIt nthIt(int n) const { |
|
342 return EdgeIt(*this, n); |
|
343 } |
|
344 |
|
345 /// \brief Gives back the last edge of the path. |
|
346 const Edge& back() const { |
|
347 return data.back(); |
|
348 } |
|
349 |
|
350 /// \brief Add a new edge behind the current path. |
|
351 void addBack(const Edge& edge) { |
|
352 data.push_back(edge); |
|
353 } |
|
354 |
|
355 /// \brief Erase the last edge of the path |
|
356 void eraseBack() { |
|
357 data.pop_back(); |
|
358 } |
|
359 |
|
360 typedef True BuildTag; |
|
361 |
|
362 template <typename CPath> |
|
363 void build(const CPath& path) { |
|
364 int len = path.length(); |
|
365 data.resize(len); |
|
366 int index = 0; |
|
367 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) { |
|
368 data[index] = it;; |
|
369 ++index; |
|
370 } |
|
371 } |
|
372 |
|
373 template <typename CPath> |
|
374 void buildRev(const CPath& path) { |
|
375 int len = path.length(); |
|
376 data.resize(len); |
|
377 int index = len; |
|
378 for (typename CPath::RevIt it(path); it != INVALID; ++it) { |
|
379 --index; |
|
380 data[index] = it;; |
|
381 } |
|
382 } |
|
383 |
298 protected: |
384 protected: |
299 |
|
300 const Graph *graph; |
|
301 |
|
302 typedef std::vector<Edge> Container; |
385 typedef std::vector<Edge> Container; |
303 Container edges; |
386 Container data; |
304 Node start; |
387 |
305 |
388 }; |
|
389 |
|
390 /// \brief A structure for representing directed paths in a graph. |
|
391 /// |
|
392 /// A structure for representing directed path in a graph. |
|
393 /// \param Graph The graph type in which the path is. |
|
394 /// |
|
395 /// In a sense, the path can be treated as a list of edges. The |
|
396 /// lemon path type stores just this list. As a consequence it |
|
397 /// cannot enumerate the nodes in the path and the zero length paths |
|
398 /// cannot store the source. |
|
399 /// |
|
400 /// This implementation is a back and front insertable and erasable |
|
401 /// path type. It can be indexed in O(k) time, where k is the rank |
|
402 /// of the edge in the path. The length can be computed in O(n) |
|
403 /// time. The front and back insertion and erasure is O(1) time |
|
404 /// and it can be splited and spliced in O(1) time. |
|
405 template <typename _Graph> |
|
406 class ListPath { |
306 public: |
407 public: |
307 |
408 |
308 friend class Builder; |
409 typedef _Graph Graph; |
309 |
410 typedef typename Graph::Edge Edge; |
310 /// \brief Class to build paths |
411 |
311 /// |
412 protected: |
312 /// This class is used to fill a path with edges. |
413 |
313 /// |
414 // the std::list<> is incompatible |
314 /// You can push new edges to the front and to the back of the |
415 // hard to create invalid iterator |
315 /// path in arbitrary order then you should commit these changes |
416 struct Node { |
316 /// to the graph. |
417 Edge edge; |
317 /// |
418 Node *next, *prev; |
318 /// Fundamentally, for most "Paths" (classes fulfilling the |
419 }; |
319 /// PathConcept) while the builder is active (after the first |
420 |
320 /// modifying operation and until the commit()) the original Path |
421 Node *first, *last; |
321 /// is in a "transitional" state (operations on it have undefined |
422 |
322 /// result). But in the case of Path the original path remains |
423 std::allocator<Node> alloc; |
323 /// unchanged until the commit. However we don't recomend that you |
424 |
324 /// use this feature. |
425 public: |
325 class Builder { |
426 |
|
427 /// \brief Default constructor |
|
428 /// |
|
429 /// Default constructor |
|
430 ListPath() : first(0), last(0) {} |
|
431 |
|
432 /// \brief Template copy constructor |
|
433 /// |
|
434 /// This path can be initialized with any other path type. It just |
|
435 /// makes a copy of the given path. |
|
436 template <typename CPath> |
|
437 ListPath(const CPath& cpath) : first(0), last(0) { |
|
438 copyPath(*this, cpath); |
|
439 } |
|
440 |
|
441 /// \brief Destructor of the path |
|
442 /// |
|
443 /// Destructor of the path |
|
444 ~ListPath() { |
|
445 clear(); |
|
446 } |
|
447 |
|
448 /// \brief Template copy assignment |
|
449 /// |
|
450 /// This path can be initialized with any other path type. It just |
|
451 /// makes a copy of the given path. |
|
452 template <typename CPath> |
|
453 ListPath& operator=(const CPath& cpath) { |
|
454 copyPath(*this, cpath); |
|
455 return *this; |
|
456 } |
|
457 |
|
458 /// \brief Iterator class to iterate on the edges of the paths |
|
459 /// |
|
460 /// This class is used to iterate on the edges of the paths |
|
461 /// |
|
462 /// Of course it converts to Graph::Edge |
|
463 class EdgeIt { |
|
464 friend class ListPath; |
326 public: |
465 public: |
327 /// \brief Constructor |
466 /// Default constructor |
328 /// |
467 EdgeIt() {} |
329 /// Constructor |
468 /// Invalid constructor |
330 /// \param _path the path you want to fill in. |
469 EdgeIt(Invalid) : path(0), node(0) {} |
331 Builder(Path &_path) : path(_path), start(INVALID) {} |
470 /// \brief Initializate the constructor to the first edge of path |
332 |
471 EdgeIt(const ListPath &_path) |
333 /// \brief Destructor |
472 : path(&_path), node(_path.first) {} |
334 /// |
473 |
335 /// Destructor |
474 protected: |
336 ~Builder() { |
475 |
337 LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, |
476 EdgeIt(const ListPath &_path, Node *_node) |
338 PathError()); |
477 : path(&_path), node(_node) {} |
339 } |
478 |
340 |
479 |
341 /// \brief Sets the starting node of the path. |
480 public: |
342 /// |
481 |
343 /// Sets the starting node of the path. Edge added to the path |
482 ///Conversion to Graph::Edge |
344 /// afterwards have to be incident to this node. It should be |
483 operator const Edge&() const { |
345 /// called if and only if the path is empty and before any call |
484 return node->edge; |
346 /// to \ref pushFront() or \ref pushBack() |
485 } |
347 void setStartNode(const Node &_start) { |
486 |
348 LEMON_ASSERT(path.empty() && start == INVALID, PathError()); |
487 /// Next edge |
349 start = _start; |
488 EdgeIt& operator++() { |
350 } |
489 node = node->next; |
351 |
490 return *this; |
352 /// \brief Push a new edge to the front of the path |
491 } |
353 /// |
492 |
354 /// Push a new edge to the front of the path. |
493 /// Comparison operator |
355 /// \sa setStartNode |
494 bool operator==(const EdgeIt& e) const { return node==e.node; } |
356 void pushFront(const Edge& e) { |
495 /// Comparison operator |
357 LEMON_ASSERT(front.empty() || |
496 bool operator!=(const EdgeIt& e) const { return node!=e.node; } |
358 (path.graph->source(front.back()) == |
497 /// Comparison operator |
359 path.graph->target(e)), PathError()); |
498 bool operator<(const EdgeIt& e) const { return node<e.node; } |
360 LEMON_ASSERT(path.empty() || |
499 |
361 (path.source() == path.graph->target(e)), PathError()); |
500 private: |
362 LEMON_ASSERT(!path.empty() || !front.empty() || |
501 const ListPath *path; |
363 (start == path.graph->target(e)), PathError()); |
502 Node *node; |
364 front.push_back(e); |
503 }; |
365 } |
504 |
366 |
505 /// \brief Gives back the nth edge. |
367 /// \brief Push a new edge to the back of the path |
506 /// |
368 /// |
507 /// Gives back the nth edge in O(n) time. |
369 /// Push a new edge to the back of the path. |
508 /// \pre n is in the [0..length() - 1] range |
370 /// \sa setStartNode |
509 const Edge& nth(int n) const { |
371 void pushBack(const Edge& e) { |
510 Node *node = first; |
372 LEMON_ASSERT(back.empty() || |
511 for (int i = 0; i < n; ++i) { |
373 (path.graph->target(back.back()) == |
512 node = node->next; |
374 path.graph->source(e)), PathError()); |
513 } |
375 LEMON_ASSERT(path.empty() || |
514 return node->edge; |
376 (path.target() == path.graph->source(e)), PathError()); |
515 } |
377 LEMON_ASSERT(!path.empty() || !back.empty() || |
516 |
378 (start == path.graph->source(e)), PathError()); |
517 /// \brief Initializes edge iterator to point to the nth edge. |
379 back.push_back(e); |
518 EdgeIt nthIt(int n) const { |
380 } |
519 Node *node = first; |
381 |
520 for (int i = 0; i < n; ++i) { |
382 /// \brief Commit the changes to the path. |
521 node = node->next; |
383 /// |
522 } |
384 /// Commit the changes to the path. |
523 return EdgeIt(*this, node); |
385 void commit() { |
524 } |
386 if( !front.empty() || !back.empty() || start != INVALID) { |
525 |
387 Container tmp; |
526 /// \brief Length of the path. |
388 tmp.reserve(front.size() + back.size() + path.length()); |
527 int length() const { |
389 tmp.insert(tmp.end(), front.rbegin(), front.rend()); |
528 int len = 0; |
390 tmp.insert(tmp.end(), path.edges.begin(), path.edges.end()); |
529 Node *node = first; |
391 tmp.insert(tmp.end(), back.begin(), back.end()); |
530 while (node != 0) { |
392 path.edges.swap(tmp); |
531 node = node->next; |
393 if (!front.empty()) { |
532 ++len; |
394 path.start = path.graph->source(front.back()); |
533 } |
|
534 return len; |
|
535 } |
|
536 |
|
537 /// \brief Returns whether the path is empty. |
|
538 bool empty() const { return first == 0; } |
|
539 |
|
540 /// \brief Resets the path to an empty path. |
|
541 void clear() { |
|
542 while (first != 0) { |
|
543 last = first->next; |
|
544 alloc.destroy(first); |
|
545 alloc.deallocate(first, 1); |
|
546 first = last; |
|
547 } |
|
548 } |
|
549 |
|
550 /// \brief Gives back the first edge of the path |
|
551 const Edge& front() const { |
|
552 return first->edge; |
|
553 } |
|
554 |
|
555 /// \brief Add a new edge before the current path |
|
556 void addFront(const Edge& edge) { |
|
557 Node *node = alloc.allocate(1); |
|
558 alloc.construct(node, Node()); |
|
559 node->prev = 0; |
|
560 node->next = first; |
|
561 node->edge = edge; |
|
562 if (first) { |
|
563 first->prev = node; |
|
564 first = node; |
|
565 } else { |
|
566 first = last = node; |
|
567 } |
|
568 } |
|
569 |
|
570 /// \brief Erase the first edge of the path |
|
571 void eraseFront() { |
|
572 Node *node = first; |
|
573 first = first->next; |
|
574 if (first) { |
|
575 first->prev = 0; |
|
576 } else { |
|
577 last = 0; |
|
578 } |
|
579 alloc.destroy(node); |
|
580 alloc.deallocate(node, 1); |
|
581 } |
|
582 |
|
583 /// \brief Gives back the last edge of the path. |
|
584 const Edge& back() const { |
|
585 return last->edge; |
|
586 } |
|
587 |
|
588 /// \brief Add a new edge behind the current path. |
|
589 void addBack(const Edge& edge) { |
|
590 Node *node = alloc.allocate(1); |
|
591 alloc.construct(node, Node()); |
|
592 node->next = 0; |
|
593 node->prev = last; |
|
594 node->edge = edge; |
|
595 if (last) { |
|
596 last->next = node; |
|
597 last = node; |
|
598 } else { |
|
599 last = first = node; |
|
600 } |
|
601 } |
|
602 |
|
603 /// \brief Erase the last edge of the path |
|
604 void eraseBack() { |
|
605 Node *node = last; |
|
606 last = last->prev; |
|
607 if (last) { |
|
608 last->next = 0; |
|
609 } else { |
|
610 first = 0; |
|
611 } |
|
612 alloc.destroy(node); |
|
613 alloc.deallocate(node, 1); |
|
614 } |
|
615 |
|
616 /// \brief Splicing the given path to the current path. |
|
617 /// |
|
618 /// It splices the \c tpath to the back of the current path and \c |
|
619 /// tpath becomes empty. The time complexity of this function is |
|
620 /// O(1). |
|
621 void spliceBack(ListPath& tpath) { |
|
622 if (first) { |
|
623 if (tpath.first) { |
|
624 last->next = tpath.first; |
|
625 tpath.first->prev = last; |
|
626 last = tpath.last; |
|
627 } |
|
628 } else { |
|
629 first = tpath.first; |
|
630 last = tpath.last; |
|
631 } |
|
632 tpath.first = tpath.last = 0; |
|
633 } |
|
634 |
|
635 /// \brief Splicing the given path to the current path. |
|
636 /// |
|
637 /// It splices the \c tpath before the current path and \c tpath |
|
638 /// becomes empty. The time complexity of this function |
|
639 /// is O(1). |
|
640 void spliceFront(ListPath& tpath) { |
|
641 if (first) { |
|
642 if (tpath.first) { |
|
643 first->prev = tpath.last; |
|
644 tpath.last->next = first; |
|
645 first = tpath.first; |
|
646 } |
|
647 } else { |
|
648 first = tpath.first; |
|
649 last = tpath.last; |
|
650 } |
|
651 tpath.first = tpath.last = 0; |
|
652 } |
|
653 |
|
654 /// \brief Splicing the given path into the current path. |
|
655 /// |
|
656 /// It splices the \c tpath into the current path before the |
|
657 /// position of \c it iterator and \c tpath becomes empty. The |
|
658 /// time complexity of this function is O(1). If the \c it is \c |
|
659 /// INVALID then it will splice behind the current path. |
|
660 void splice(EdgeIt it, ListPath& tpath) { |
|
661 if (it.node) { |
|
662 if (tpath.first) { |
|
663 tpath.first->prev = it.node->prev; |
|
664 if (it.node->prev) { |
|
665 it.node->prev->next = tpath.first; |
395 } else { |
666 } else { |
396 path.start = start; |
667 first = tpath.first; |
397 } |
668 } |
398 start = INVALID; |
669 it.node->prev = tpath.last; |
399 front.clear(); |
670 tpath.last->next = it.node; |
400 back.clear(); |
671 } |
401 } |
672 } else { |
402 } |
673 if (first) { |
403 |
674 if (tpath.first) { |
404 /// \brief Reserve storage for the builder in advance. |
675 last->next = tpath.first; |
405 /// |
676 tpath.first->prev = last; |
406 /// If you know a reasonable upper bound of the number of the |
677 last = tpath.last; |
407 /// edges to add to the front, using this function you can speed |
678 } |
408 /// up the building. |
679 } else { |
409 void reserveFront(size_t r) {front.reserve(r);} |
680 first = tpath.first; |
410 |
681 last = tpath.last; |
411 /// \brief Reserve storage for the builder in advance. |
682 } |
412 /// |
683 } |
413 /// If you know a reasonable upper bound of the number of the |
684 tpath.first = tpath.last = 0; |
414 /// edges to add to the back, using this function you can speed |
685 } |
415 /// up the building. |
686 |
416 void reserveBack(size_t r) {back.reserve(r);} |
687 /// \brief Spliting the current path. |
|
688 /// |
|
689 /// It splits the current path into two parts. The part before \c |
|
690 /// it iterator will remain in the current path and the part from |
|
691 /// the it will put into the \c tpath. If the \c tpath had edges |
|
692 /// before the operation they will be removed first. The time |
|
693 /// complexity of this function is O(1) plus the clearing of \c |
|
694 /// tpath. If the \c it is \c INVALID then it just clears \c |
|
695 /// tpath. |
|
696 void split(EdgeIt it, ListPath& tpath) { |
|
697 tpath.clear(); |
|
698 if (it.node) { |
|
699 tpath.first = it.node; |
|
700 tpath.last = last; |
|
701 if (it.node->prev) { |
|
702 last = it.node->prev; |
|
703 last->next = 0; |
|
704 } else { |
|
705 first = last = 0; |
|
706 } |
|
707 it.node->prev = 0; |
|
708 } |
|
709 } |
|
710 |
|
711 |
|
712 typedef True BuildTag; |
|
713 |
|
714 template <typename CPath> |
|
715 void build(const CPath& path) { |
|
716 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) { |
|
717 addBack(it); |
|
718 } |
|
719 } |
|
720 |
|
721 template <typename CPath> |
|
722 void buildRev(const CPath& path) { |
|
723 for (typename CPath::RevIt it(path); it != INVALID; ++it) { |
|
724 addFront(it); |
|
725 } |
|
726 } |
|
727 |
|
728 }; |
|
729 |
|
730 /// \brief A structure for representing directed paths in a graph. |
|
731 /// |
|
732 /// A structure for representing directed path in a graph. |
|
733 /// \param Graph The graph type in which the path is. |
|
734 /// |
|
735 /// In a sense, the path can be treated as a list of edges. The |
|
736 /// lemon path type stores just this list. As a consequence it |
|
737 /// cannot enumerate the nodes in the path and the zero length paths |
|
738 /// cannot store the source. |
|
739 /// |
|
740 /// This implementation is completly static, so it cannot be |
|
741 /// modified exclude the assign an other path. It is intented to be |
|
742 /// used when you want to store a large amount paths because it is |
|
743 /// the most memory efficient path type in the lemon. |
|
744 template <typename _Graph> |
|
745 class StaticPath { |
|
746 public: |
|
747 |
|
748 typedef _Graph Graph; |
|
749 typedef typename Graph::Edge Edge; |
|
750 |
|
751 /// \brief Default constructor |
|
752 /// |
|
753 /// Default constructor |
|
754 StaticPath() : len(0), edges(0) {} |
|
755 |
|
756 /// \brief Template copy constructor |
|
757 /// |
|
758 /// This path can be initialized with any other path type. It just |
|
759 /// makes a copy of the given path. |
|
760 template <typename CPath> |
|
761 StaticPath(const CPath& cpath) : edges(0) { |
|
762 copyPath(*this, cpath); |
|
763 } |
|
764 |
|
765 /// \brief Destructor of the path |
|
766 /// |
|
767 /// Destructor of the path |
|
768 ~StaticPath() { |
|
769 if (edges) delete[] edges; |
|
770 } |
|
771 |
|
772 /// \brief Template copy assignment |
|
773 /// |
|
774 /// This path can be initialized with any other path type. It just |
|
775 /// makes a copy of the given path. |
|
776 template <typename CPath> |
|
777 StaticPath& operator=(const CPath& cpath) { |
|
778 copyPath(*this, cpath); |
|
779 return *this; |
|
780 } |
|
781 |
|
782 /// \brief Iterator class to iterate on the edges of the paths |
|
783 /// |
|
784 /// This class is used to iterate on the edges of the paths |
|
785 /// |
|
786 /// Of course it converts to Graph::Edge |
|
787 class EdgeIt { |
|
788 friend class StaticPath; |
|
789 public: |
|
790 /// Default constructor |
|
791 EdgeIt() {} |
|
792 /// Invalid constructor |
|
793 EdgeIt(Invalid) : path(0), idx(-1) {} |
|
794 /// Initializate the constructor to the first edge of path |
|
795 EdgeIt(const StaticPath &_path) |
|
796 : path(&_path), idx(_path.empty() ? -1 : 0) {} |
417 |
797 |
418 private: |
798 private: |
419 |
799 |
420 Path &path; |
800 /// Constructor with starting point |
421 Container front, back; |
801 EdgeIt(const StaticPath &_path, int _idx) |
422 Node start; |
802 : idx(_idx), path(&_path) {} |
423 |
803 |
|
804 public: |
|
805 |
|
806 ///Conversion to Graph::Edge |
|
807 operator const Edge&() const { |
|
808 return path->nth(idx); |
|
809 } |
|
810 |
|
811 /// Next edge |
|
812 EdgeIt& operator++() { |
|
813 ++idx; |
|
814 if (idx >= path->length()) idx = -1; |
|
815 return *this; |
|
816 } |
|
817 |
|
818 /// Comparison operator |
|
819 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
|
820 /// Comparison operator |
|
821 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
|
822 /// Comparison operator |
|
823 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
|
824 |
|
825 private: |
|
826 const StaticPath *path; |
|
827 int idx; |
424 }; |
828 }; |
425 |
829 |
|
830 /// \brief Gives back the nth edge. |
|
831 /// |
|
832 /// \pre n is in the [0..length() - 1] range |
|
833 const Edge& nth(int n) const { |
|
834 return edges[n]; |
|
835 } |
|
836 |
|
837 /// \brief Initializes edge iterator to point to the nth edge. |
|
838 EdgeIt nthIt(int n) const { |
|
839 return EdgeIt(*this, n); |
|
840 } |
|
841 |
|
842 /// \brief Gives back the length of the path. |
|
843 int length() const { return len; } |
|
844 |
|
845 /// \brief Returns true when the path is empty. |
|
846 int empty() const { return len == 0; } |
|
847 |
|
848 /// \break Erase all edge in the graph. |
|
849 void clear() { |
|
850 len = 0; |
|
851 if (edges) delete[] edges; |
|
852 edges = 0; |
|
853 } |
|
854 |
|
855 /// \brief Gives back the first edge of the path. |
|
856 const Edge& front() const { |
|
857 return edges[0]; |
|
858 } |
|
859 |
|
860 /// \brief Gives back the last edge of the path. |
|
861 const Edge& back() const { |
|
862 return edges[len - 1]; |
|
863 } |
|
864 |
|
865 |
|
866 typedef True BuildTag; |
|
867 |
|
868 template <typename CPath> |
|
869 void build(const CPath& path) { |
|
870 len = path.length(); |
|
871 edges = new Edge[len]; |
|
872 int index = 0; |
|
873 for (typename CPath::EdgeIt it(path); it != INVALID; ++it) { |
|
874 edges[index] = it; |
|
875 ++index; |
|
876 } |
|
877 } |
|
878 |
|
879 template <typename CPath> |
|
880 void buildRev(const CPath& path) { |
|
881 len = path.length(); |
|
882 edges = new Edge[len]; |
|
883 int index = len; |
|
884 for (typename CPath::RevIt it(path); it != INVALID; ++it) { |
|
885 --index; |
|
886 edges[index] = it; |
|
887 } |
|
888 } |
|
889 |
|
890 private: |
|
891 int len; |
|
892 Edge* edges; |
426 }; |
893 }; |
427 |
894 |
428 ///@} |
895 ///@} |
429 |
896 |
430 } // namespace lemon |
897 } // namespace lemon |