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