16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 ///\ingroup graph_concepts |
19 ///\ingroup graph_concepts |
20 ///\file |
20 ///\file |
21 ///\brief The concept of Undirected Graphs. |
21 ///\brief The concept of undirected graphs. |
22 |
22 |
23 #ifndef LEMON_CONCEPTS_GRAPH_H |
23 #ifndef LEMON_CONCEPTS_GRAPH_H |
24 #define LEMON_CONCEPTS_GRAPH_H |
24 #define LEMON_CONCEPTS_GRAPH_H |
25 |
25 |
26 #include <lemon/concepts/graph_components.h> |
26 #include <lemon/concepts/graph_components.h> |
|
27 #include <lemon/concepts/maps.h> |
|
28 #include <lemon/concept_check.h> |
27 #include <lemon/core.h> |
29 #include <lemon/core.h> |
28 |
30 |
29 namespace lemon { |
31 namespace lemon { |
30 namespace concepts { |
32 namespace concepts { |
31 |
33 |
32 /// \ingroup graph_concepts |
34 /// \ingroup graph_concepts |
33 /// |
35 /// |
34 /// \brief Class describing the concept of Undirected Graphs. |
36 /// \brief Class describing the concept of undirected graphs. |
35 /// |
37 /// |
36 /// This class describes the common interface of all Undirected |
38 /// This class describes the common interface of all undirected |
37 /// Graphs. |
39 /// graphs. |
38 /// |
40 /// |
39 /// As all concept describing classes it provides only interface |
41 /// Like all concept classes, it only provides an interface |
40 /// without any sensible implementation. So any algorithm for |
42 /// without any sensible implementation. So any general algorithm for |
41 /// undirected graph should compile with this class, but it will not |
43 /// undirected graphs should compile with this class, but it will not |
42 /// run properly, of course. |
44 /// run properly, of course. |
|
45 /// An actual graph implementation like \ref ListGraph or |
|
46 /// \ref SmartGraph may have additional functionality. |
43 /// |
47 /// |
44 /// The LEMON undirected graphs also fulfill the concept of |
48 /// The undirected graphs also fulfill the concept of \ref Digraph |
45 /// directed graphs (\ref lemon::concepts::Digraph "Digraph |
49 /// "directed graphs", since each edge can also be regarded as two |
46 /// Concept"). Each edges can be seen as two opposite |
50 /// oppositely directed arcs. |
47 /// directed arc and consequently the undirected graph can be |
51 /// Undirected graphs provide an Edge type for the undirected edges and |
48 /// seen as the direceted graph of these directed arcs. The |
52 /// an Arc type for the directed arcs. The Arc type is convertible to |
49 /// Graph has the Edge inner class for the edges and |
53 /// Edge or inherited from it, i.e. the corresponding edge can be |
50 /// the Arc type for the directed arcs. The Arc type is |
54 /// obtained from an arc. |
51 /// convertible to Edge or inherited from it so from a directed |
55 /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt |
52 /// arc we can get the represented edge. |
56 /// and ArcMap classes can be used for the arcs (just like in digraphs). |
|
57 /// Both InArcIt and OutArcIt iterates on the same edges but with |
|
58 /// opposite direction. IncEdgeIt also iterates on the same edges |
|
59 /// as OutArcIt and InArcIt, but it is not convertible to Arc, |
|
60 /// only to Edge. |
53 /// |
61 /// |
54 /// In the sense of the LEMON each edge has a default |
62 /// In LEMON, each undirected edge has an inherent orientation. |
55 /// direction (it should be in every computer implementation, |
63 /// Thus it can defined if an arc is forward or backward oriented in |
56 /// because the order of edge's nodes defines an |
64 /// an undirected graph with respect to this default oriantation of |
57 /// orientation). With the default orientation we can define that |
65 /// the represented edge. |
58 /// the directed arc is forward or backward directed. With the \c |
66 /// With the direction() and direct() functions the direction |
59 /// direction() and \c direct() function we can get the direction |
67 /// of an arc can be obtained and set, respectively. |
60 /// of the directed arc and we can direct an edge. |
|
61 /// |
68 /// |
62 /// The EdgeIt is an iterator for the edges. We can use |
69 /// Only nodes and edges can be added to or removed from an undirected |
63 /// the EdgeMap to map values for the edges. The InArcIt and |
70 /// graph and the corresponding arcs are added or removed automatically. |
64 /// OutArcIt iterates on the same edges but with opposite |
71 /// |
65 /// direction. The IncEdgeIt iterates also on the same edges |
72 /// \sa Digraph |
66 /// as the OutArcIt and InArcIt but it is not convertible to Arc just |
|
67 /// to Edge. |
|
68 class Graph { |
73 class Graph { |
|
74 private: |
|
75 /// Graphs are \e not copy constructible. Use DigraphCopy instead. |
|
76 Graph(const Graph&) {} |
|
77 /// \brief Assignment of a graph to another one is \e not allowed. |
|
78 /// Use DigraphCopy instead. |
|
79 void operator=(const Graph&) {} |
|
80 |
69 public: |
81 public: |
70 /// \brief The undirected graph should be tagged by the |
82 /// Default constructor. |
71 /// UndirectedTag. |
83 Graph() {} |
72 /// |
84 |
73 /// The undirected graph should be tagged by the UndirectedTag. This |
85 /// \brief Undirected graphs should be tagged with \c UndirectedTag. |
74 /// tag helps the enable_if technics to make compile time |
86 /// |
|
87 /// Undirected graphs should be tagged with \c UndirectedTag. |
|
88 /// |
|
89 /// This tag helps the \c enable_if technics to make compile time |
75 /// specializations for undirected graphs. |
90 /// specializations for undirected graphs. |
76 typedef True UndirectedTag; |
91 typedef True UndirectedTag; |
77 |
92 |
78 /// \brief The base type of node iterators, |
93 /// The node type of the graph |
79 /// or in other words, the trivial node iterator. |
94 |
80 /// |
95 /// This class identifies a node of the graph. It also serves |
81 /// This is the base type of each node iterator, |
96 /// as a base class of the node iterators, |
82 /// thus each kind of node iterator converts to this. |
97 /// thus they convert to this type. |
83 /// More precisely each kind of node iterator should be inherited |
|
84 /// from the trivial node iterator. |
|
85 class Node { |
98 class Node { |
86 public: |
99 public: |
87 /// Default constructor |
100 /// Default constructor |
88 |
101 |
89 /// @warning The default constructor sets the iterator |
102 /// Default constructor. |
90 /// to an undefined value. |
103 /// \warning It sets the object to an undefined value. |
91 Node() { } |
104 Node() { } |
92 /// Copy constructor. |
105 /// Copy constructor. |
93 |
106 |
94 /// Copy constructor. |
107 /// Copy constructor. |
95 /// |
108 /// |
96 Node(const Node&) { } |
109 Node(const Node&) { } |
97 |
110 |
98 /// Invalid constructor \& conversion. |
111 /// %Invalid constructor \& conversion. |
99 |
112 |
100 /// This constructor initializes the iterator to be invalid. |
113 /// Initializes the object to be invalid. |
101 /// \sa Invalid for more details. |
114 /// \sa Invalid for more details. |
102 Node(Invalid) { } |
115 Node(Invalid) { } |
103 /// Equality operator |
116 /// Equality operator |
104 |
117 |
|
118 /// Equality operator. |
|
119 /// |
105 /// Two iterators are equal if and only if they point to the |
120 /// Two iterators are equal if and only if they point to the |
106 /// same object or both are invalid. |
121 /// same object or both are \c INVALID. |
107 bool operator==(Node) const { return true; } |
122 bool operator==(Node) const { return true; } |
108 |
123 |
109 /// Inequality operator |
124 /// Inequality operator |
110 |
125 |
111 /// \sa operator==(Node n) |
126 /// Inequality operator. |
112 /// |
|
113 bool operator!=(Node) const { return true; } |
127 bool operator!=(Node) const { return true; } |
114 |
128 |
115 /// Artificial ordering operator. |
129 /// Artificial ordering operator. |
116 |
130 |
117 /// To allow the use of graph descriptors as key type in std::map or |
131 /// Artificial ordering operator. |
118 /// similar associative container we require this. |
132 /// |
119 /// |
133 /// \note This operator only has to define some strict ordering of |
120 /// \note This operator only have to define some strict ordering of |
|
121 /// the items; this order has nothing to do with the iteration |
134 /// the items; this order has nothing to do with the iteration |
122 /// ordering of the items. |
135 /// ordering of the items. |
123 bool operator<(Node) const { return false; } |
136 bool operator<(Node) const { return false; } |
124 |
137 |
125 }; |
138 }; |
126 |
139 |
127 /// This iterator goes through each node. |
140 /// Iterator class for the nodes. |
128 |
141 |
129 /// This iterator goes through each node. |
142 /// This iterator goes through each node of the graph. |
130 /// Its usage is quite simple, for example you can count the number |
143 /// Its usage is quite simple, for example you can count the number |
131 /// of nodes in graph \c g of type \c Graph like this: |
144 /// of nodes in a graph \c g of type \c %Graph like this: |
132 ///\code |
145 ///\code |
133 /// int count=0; |
146 /// int count=0; |
134 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
147 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
135 ///\endcode |
148 ///\endcode |
136 class NodeIt : public Node { |
149 class NodeIt : public Node { |
137 public: |
150 public: |
138 /// Default constructor |
151 /// Default constructor |
139 |
152 |
140 /// @warning The default constructor sets the iterator |
153 /// Default constructor. |
141 /// to an undefined value. |
154 /// \warning It sets the iterator to an undefined value. |
142 NodeIt() { } |
155 NodeIt() { } |
143 /// Copy constructor. |
156 /// Copy constructor. |
144 |
157 |
145 /// Copy constructor. |
158 /// Copy constructor. |
146 /// |
159 /// |
147 NodeIt(const NodeIt& n) : Node(n) { } |
160 NodeIt(const NodeIt& n) : Node(n) { } |
148 /// Invalid constructor \& conversion. |
161 /// %Invalid constructor \& conversion. |
149 |
162 |
150 /// Initialize the iterator to be invalid. |
163 /// Initializes the iterator to be invalid. |
151 /// \sa Invalid for more details. |
164 /// \sa Invalid for more details. |
152 NodeIt(Invalid) { } |
165 NodeIt(Invalid) { } |
153 /// Sets the iterator to the first node. |
166 /// Sets the iterator to the first node. |
154 |
167 |
155 /// Sets the iterator to the first node of \c g. |
168 /// Sets the iterator to the first node of the given digraph. |
156 /// |
169 /// |
157 NodeIt(const Graph&) { } |
170 explicit NodeIt(const Graph&) { } |
158 /// Node -> NodeIt conversion. |
171 /// Sets the iterator to the given node. |
159 |
172 |
160 /// Sets the iterator to the node of \c the graph pointed by |
173 /// Sets the iterator to the given node of the given digraph. |
161 /// the trivial iterator. |
174 /// |
162 /// This feature necessitates that each time we |
|
163 /// iterate the arc-set, the iteration order is the same. |
|
164 NodeIt(const Graph&, const Node&) { } |
175 NodeIt(const Graph&, const Node&) { } |
165 /// Next node. |
176 /// Next node. |
166 |
177 |
167 /// Assign the iterator to the next node. |
178 /// Assign the iterator to the next node. |
168 /// |
179 /// |
169 NodeIt& operator++() { return *this; } |
180 NodeIt& operator++() { return *this; } |
170 }; |
181 }; |
171 |
182 |
172 |
183 |
173 /// The base type of the edge iterators. |
184 /// The edge type of the graph |
174 |
185 |
175 /// The base type of the edge iterators. |
186 /// This class identifies an edge of the graph. It also serves |
176 /// |
187 /// as a base class of the edge iterators, |
|
188 /// thus they will convert to this type. |
177 class Edge { |
189 class Edge { |
178 public: |
190 public: |
179 /// Default constructor |
191 /// Default constructor |
180 |
192 |
181 /// @warning The default constructor sets the iterator |
193 /// Default constructor. |
182 /// to an undefined value. |
194 /// \warning It sets the object to an undefined value. |
183 Edge() { } |
195 Edge() { } |
184 /// Copy constructor. |
196 /// Copy constructor. |
185 |
197 |
186 /// Copy constructor. |
198 /// Copy constructor. |
187 /// |
199 /// |
188 Edge(const Edge&) { } |
200 Edge(const Edge&) { } |
189 /// Initialize the iterator to be invalid. |
201 /// %Invalid constructor \& conversion. |
190 |
202 |
191 /// Initialize the iterator to be invalid. |
203 /// Initializes the object to be invalid. |
192 /// |
204 /// \sa Invalid for more details. |
193 Edge(Invalid) { } |
205 Edge(Invalid) { } |
194 /// Equality operator |
206 /// Equality operator |
195 |
207 |
|
208 /// Equality operator. |
|
209 /// |
196 /// Two iterators are equal if and only if they point to the |
210 /// Two iterators are equal if and only if they point to the |
197 /// same object or both are invalid. |
211 /// same object or both are \c INVALID. |
198 bool operator==(Edge) const { return true; } |
212 bool operator==(Edge) const { return true; } |
199 /// Inequality operator |
213 /// Inequality operator |
200 |
214 |
201 /// \sa operator==(Edge n) |
215 /// Inequality operator. |
202 /// |
|
203 bool operator!=(Edge) const { return true; } |
216 bool operator!=(Edge) const { return true; } |
204 |
217 |
205 /// Artificial ordering operator. |
218 /// Artificial ordering operator. |
206 |
219 |
207 /// To allow the use of graph descriptors as key type in std::map or |
220 /// Artificial ordering operator. |
208 /// similar associative container we require this. |
221 /// |
209 /// |
222 /// \note This operator only has to define some strict ordering of |
210 /// \note This operator only have to define some strict ordering of |
223 /// the edges; this order has nothing to do with the iteration |
211 /// the items; this order has nothing to do with the iteration |
224 /// ordering of the edges. |
212 /// ordering of the items. |
|
213 bool operator<(Edge) const { return false; } |
225 bool operator<(Edge) const { return false; } |
214 }; |
226 }; |
215 |
227 |
216 /// This iterator goes through each edge. |
228 /// Iterator class for the edges. |
217 |
229 |
218 /// This iterator goes through each edge of a graph. |
230 /// This iterator goes through each edge of the graph. |
219 /// Its usage is quite simple, for example you can count the number |
231 /// Its usage is quite simple, for example you can count the number |
220 /// of edges in a graph \c g of type \c Graph as follows: |
232 /// of edges in a graph \c g of type \c %Graph as follows: |
221 ///\code |
233 ///\code |
222 /// int count=0; |
234 /// int count=0; |
223 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
235 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
224 ///\endcode |
236 ///\endcode |
225 class EdgeIt : public Edge { |
237 class EdgeIt : public Edge { |
226 public: |
238 public: |
227 /// Default constructor |
239 /// Default constructor |
228 |
240 |
229 /// @warning The default constructor sets the iterator |
241 /// Default constructor. |
230 /// to an undefined value. |
242 /// \warning It sets the iterator to an undefined value. |
231 EdgeIt() { } |
243 EdgeIt() { } |
232 /// Copy constructor. |
244 /// Copy constructor. |
233 |
245 |
234 /// Copy constructor. |
246 /// Copy constructor. |
235 /// |
247 /// |
236 EdgeIt(const EdgeIt& e) : Edge(e) { } |
248 EdgeIt(const EdgeIt& e) : Edge(e) { } |
237 /// Initialize the iterator to be invalid. |
249 /// %Invalid constructor \& conversion. |
238 |
250 |
239 /// Initialize the iterator to be invalid. |
251 /// Initializes the iterator to be invalid. |
240 /// |
252 /// \sa Invalid for more details. |
241 EdgeIt(Invalid) { } |
253 EdgeIt(Invalid) { } |
242 /// This constructor sets the iterator to the first edge. |
254 /// Sets the iterator to the first edge. |
243 |
255 |
244 /// This constructor sets the iterator to the first edge. |
256 /// Sets the iterator to the first edge of the given graph. |
245 EdgeIt(const Graph&) { } |
257 /// |
246 /// Edge -> EdgeIt conversion |
258 explicit EdgeIt(const Graph&) { } |
247 |
259 /// Sets the iterator to the given edge. |
248 /// Sets the iterator to the value of the trivial iterator. |
260 |
249 /// This feature necessitates that each time we |
261 /// Sets the iterator to the given edge of the given graph. |
250 /// iterate the edge-set, the iteration order is the |
262 /// |
251 /// same. |
|
252 EdgeIt(const Graph&, const Edge&) { } |
263 EdgeIt(const Graph&, const Edge&) { } |
253 /// Next edge |
264 /// Next edge |
254 |
265 |
255 /// Assign the iterator to the next edge. |
266 /// Assign the iterator to the next edge. |
|
267 /// |
256 EdgeIt& operator++() { return *this; } |
268 EdgeIt& operator++() { return *this; } |
257 }; |
269 }; |
258 |
270 |
259 /// \brief This iterator goes trough the incident undirected |
271 /// Iterator class for the incident edges of a node. |
260 /// arcs of a node. |
272 |
261 /// |
273 /// This iterator goes trough the incident undirected edges |
262 /// This iterator goes trough the incident edges |
274 /// of a certain node of a graph. |
263 /// of a certain node of a graph. You should assume that the |
|
264 /// loop arcs will be iterated twice. |
|
265 /// |
|
266 /// Its usage is quite simple, for example you can compute the |
275 /// Its usage is quite simple, for example you can compute the |
267 /// degree (i.e. count the number of incident arcs of a node \c n |
276 /// degree (i.e. the number of incident edges) of a node \c n |
268 /// in graph \c g of type \c Graph as follows. |
277 /// in a graph \c g of type \c %Graph as follows. |
269 /// |
278 /// |
270 ///\code |
279 ///\code |
271 /// int count=0; |
280 /// int count=0; |
272 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
281 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
273 ///\endcode |
282 ///\endcode |
|
283 /// |
|
284 /// \warning Loop edges will be iterated twice. |
274 class IncEdgeIt : public Edge { |
285 class IncEdgeIt : public Edge { |
275 public: |
286 public: |
276 /// Default constructor |
287 /// Default constructor |
277 |
288 |
278 /// @warning The default constructor sets the iterator |
289 /// Default constructor. |
279 /// to an undefined value. |
290 /// \warning It sets the iterator to an undefined value. |
280 IncEdgeIt() { } |
291 IncEdgeIt() { } |
281 /// Copy constructor. |
292 /// Copy constructor. |
282 |
293 |
283 /// Copy constructor. |
294 /// Copy constructor. |
284 /// |
295 /// |
285 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } |
296 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } |
286 /// Initialize the iterator to be invalid. |
297 /// %Invalid constructor \& conversion. |
287 |
298 |
288 /// Initialize the iterator to be invalid. |
299 /// Initializes the iterator to be invalid. |
289 /// |
300 /// \sa Invalid for more details. |
290 IncEdgeIt(Invalid) { } |
301 IncEdgeIt(Invalid) { } |
291 /// This constructor sets the iterator to first incident arc. |
302 /// Sets the iterator to the first incident edge. |
292 |
303 |
293 /// This constructor set the iterator to the first incident arc of |
304 /// Sets the iterator to the first incident edge of the given node. |
294 /// the node. |
305 /// |
295 IncEdgeIt(const Graph&, const Node&) { } |
306 IncEdgeIt(const Graph&, const Node&) { } |
296 /// Edge -> IncEdgeIt conversion |
307 /// Sets the iterator to the given edge. |
297 |
308 |
298 /// Sets the iterator to the value of the trivial iterator \c e. |
309 /// Sets the iterator to the given edge of the given graph. |
299 /// This feature necessitates that each time we |
310 /// |
300 /// iterate the arc-set, the iteration order is the same. |
|
301 IncEdgeIt(const Graph&, const Edge&) { } |
311 IncEdgeIt(const Graph&, const Edge&) { } |
302 /// Next incident arc |
312 /// Next incident edge |
303 |
313 |
304 /// Assign the iterator to the next incident arc |
314 /// Assign the iterator to the next incident edge |
305 /// of the corresponding node. |
315 /// of the corresponding node. |
306 IncEdgeIt& operator++() { return *this; } |
316 IncEdgeIt& operator++() { return *this; } |
307 }; |
317 }; |
308 |
318 |
309 /// The directed arc type. |
319 /// The arc type of the graph |
310 |
320 |
311 /// The directed arc type. It can be converted to the |
321 /// This class identifies a directed arc of the graph. It also serves |
312 /// edge or it should be inherited from the undirected |
322 /// as a base class of the arc iterators, |
313 /// edge. |
323 /// thus they will convert to this type. |
314 class Arc { |
324 class Arc { |
315 public: |
325 public: |
316 /// Default constructor |
326 /// Default constructor |
317 |
327 |
318 /// @warning The default constructor sets the iterator |
328 /// Default constructor. |
319 /// to an undefined value. |
329 /// \warning It sets the object to an undefined value. |
320 Arc() { } |
330 Arc() { } |
321 /// Copy constructor. |
331 /// Copy constructor. |
322 |
332 |
323 /// Copy constructor. |
333 /// Copy constructor. |
324 /// |
334 /// |
325 Arc(const Arc&) { } |
335 Arc(const Arc&) { } |
326 /// Initialize the iterator to be invalid. |
336 /// %Invalid constructor \& conversion. |
327 |
337 |
328 /// Initialize the iterator to be invalid. |
338 /// Initializes the object to be invalid. |
329 /// |
339 /// \sa Invalid for more details. |
330 Arc(Invalid) { } |
340 Arc(Invalid) { } |
331 /// Equality operator |
341 /// Equality operator |
332 |
342 |
|
343 /// Equality operator. |
|
344 /// |
333 /// Two iterators are equal if and only if they point to the |
345 /// Two iterators are equal if and only if they point to the |
334 /// same object or both are invalid. |
346 /// same object or both are \c INVALID. |
335 bool operator==(Arc) const { return true; } |
347 bool operator==(Arc) const { return true; } |
336 /// Inequality operator |
348 /// Inequality operator |
337 |
349 |
338 /// \sa operator==(Arc n) |
350 /// Inequality operator. |
339 /// |
|
340 bool operator!=(Arc) const { return true; } |
351 bool operator!=(Arc) const { return true; } |
341 |
352 |
342 /// Artificial ordering operator. |
353 /// Artificial ordering operator. |
343 |
354 |
344 /// To allow the use of graph descriptors as key type in std::map or |
355 /// Artificial ordering operator. |
345 /// similar associative container we require this. |
356 /// |
346 /// |
357 /// \note This operator only has to define some strict ordering of |
347 /// \note This operator only have to define some strict ordering of |
358 /// the arcs; this order has nothing to do with the iteration |
348 /// the items; this order has nothing to do with the iteration |
359 /// ordering of the arcs. |
349 /// ordering of the items. |
|
350 bool operator<(Arc) const { return false; } |
360 bool operator<(Arc) const { return false; } |
351 |
361 |
352 /// Converison to Edge |
362 /// Converison to \c Edge |
|
363 |
|
364 /// Converison to \c Edge. |
|
365 /// |
353 operator Edge() const { return Edge(); } |
366 operator Edge() const { return Edge(); } |
354 }; |
367 }; |
355 /// This iterator goes through each directed arc. |
368 |
356 |
369 /// Iterator class for the arcs. |
357 /// This iterator goes through each arc of a graph. |
370 |
|
371 /// This iterator goes through each directed arc of the graph. |
358 /// Its usage is quite simple, for example you can count the number |
372 /// Its usage is quite simple, for example you can count the number |
359 /// of arcs in a graph \c g of type \c Graph as follows: |
373 /// of arcs in a graph \c g of type \c %Graph as follows: |
360 ///\code |
374 ///\code |
361 /// int count=0; |
375 /// int count=0; |
362 /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; |
376 /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; |
363 ///\endcode |
377 ///\endcode |
364 class ArcIt : public Arc { |
378 class ArcIt : public Arc { |
365 public: |
379 public: |
366 /// Default constructor |
380 /// Default constructor |
367 |
381 |
368 /// @warning The default constructor sets the iterator |
382 /// Default constructor. |
369 /// to an undefined value. |
383 /// \warning It sets the iterator to an undefined value. |
370 ArcIt() { } |
384 ArcIt() { } |
371 /// Copy constructor. |
385 /// Copy constructor. |
372 |
386 |
373 /// Copy constructor. |
387 /// Copy constructor. |
374 /// |
388 /// |
375 ArcIt(const ArcIt& e) : Arc(e) { } |
389 ArcIt(const ArcIt& e) : Arc(e) { } |
376 /// Initialize the iterator to be invalid. |
390 /// %Invalid constructor \& conversion. |
377 |
391 |
378 /// Initialize the iterator to be invalid. |
392 /// Initializes the iterator to be invalid. |
379 /// |
393 /// \sa Invalid for more details. |
380 ArcIt(Invalid) { } |
394 ArcIt(Invalid) { } |
381 /// This constructor sets the iterator to the first arc. |
395 /// Sets the iterator to the first arc. |
382 |
396 |
383 /// This constructor sets the iterator to the first arc of \c g. |
397 /// Sets the iterator to the first arc of the given graph. |
384 ///@param g the graph |
398 /// |
385 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } |
399 explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } |
386 /// Arc -> ArcIt conversion |
400 /// Sets the iterator to the given arc. |
387 |
401 |
388 /// Sets the iterator to the value of the trivial iterator \c e. |
402 /// Sets the iterator to the given arc of the given graph. |
389 /// This feature necessitates that each time we |
403 /// |
390 /// iterate the arc-set, the iteration order is the same. |
|
391 ArcIt(const Graph&, const Arc&) { } |
404 ArcIt(const Graph&, const Arc&) { } |
392 ///Next arc |
405 /// Next arc |
393 |
406 |
394 /// Assign the iterator to the next arc. |
407 /// Assign the iterator to the next arc. |
|
408 /// |
395 ArcIt& operator++() { return *this; } |
409 ArcIt& operator++() { return *this; } |
396 }; |
410 }; |
397 |
411 |
398 /// This iterator goes trough the outgoing directed arcs of a node. |
412 /// Iterator class for the outgoing arcs of a node. |
399 |
413 |
400 /// This iterator goes trough the \e outgoing arcs of a certain node |
414 /// This iterator goes trough the \e outgoing directed arcs of a |
401 /// of a graph. |
415 /// certain node of a graph. |
402 /// Its usage is quite simple, for example you can count the number |
416 /// Its usage is quite simple, for example you can count the number |
403 /// of outgoing arcs of a node \c n |
417 /// of outgoing arcs of a node \c n |
404 /// in graph \c g of type \c Graph as follows. |
418 /// in a graph \c g of type \c %Graph as follows. |
405 ///\code |
419 ///\code |
406 /// int count=0; |
420 /// int count=0; |
407 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; |
421 /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; |
408 ///\endcode |
422 ///\endcode |
409 |
|
410 class OutArcIt : public Arc { |
423 class OutArcIt : public Arc { |
411 public: |
424 public: |
412 /// Default constructor |
425 /// Default constructor |
413 |
426 |
414 /// @warning The default constructor sets the iterator |
427 /// Default constructor. |
415 /// to an undefined value. |
428 /// \warning It sets the iterator to an undefined value. |
416 OutArcIt() { } |
429 OutArcIt() { } |
417 /// Copy constructor. |
430 /// Copy constructor. |
418 |
431 |
419 /// Copy constructor. |
432 /// Copy constructor. |
420 /// |
433 /// |
421 OutArcIt(const OutArcIt& e) : Arc(e) { } |
434 OutArcIt(const OutArcIt& e) : Arc(e) { } |
422 /// Initialize the iterator to be invalid. |
435 /// %Invalid constructor \& conversion. |
423 |
436 |
424 /// Initialize the iterator to be invalid. |
437 /// Initializes the iterator to be invalid. |
425 /// |
438 /// \sa Invalid for more details. |
426 OutArcIt(Invalid) { } |
439 OutArcIt(Invalid) { } |
427 /// This constructor sets the iterator to the first outgoing arc. |
440 /// Sets the iterator to the first outgoing arc. |
428 |
441 |
429 /// This constructor sets the iterator to the first outgoing arc of |
442 /// Sets the iterator to the first outgoing arc of the given node. |
430 /// the node. |
443 /// |
431 ///@param n the node |
|
432 ///@param g the graph |
|
433 OutArcIt(const Graph& n, const Node& g) { |
444 OutArcIt(const Graph& n, const Node& g) { |
434 ignore_unused_variable_warning(n); |
445 ignore_unused_variable_warning(n); |
435 ignore_unused_variable_warning(g); |
446 ignore_unused_variable_warning(g); |
436 } |
447 } |
437 /// Arc -> OutArcIt conversion |
448 /// Sets the iterator to the given arc. |
438 |
449 |
439 /// Sets the iterator to the value of the trivial iterator. |
450 /// Sets the iterator to the given arc of the given graph. |
440 /// This feature necessitates that each time we |
451 /// |
441 /// iterate the arc-set, the iteration order is the same. |
|
442 OutArcIt(const Graph&, const Arc&) { } |
452 OutArcIt(const Graph&, const Arc&) { } |
443 ///Next outgoing arc |
453 /// Next outgoing arc |
444 |
454 |
445 /// Assign the iterator to the next |
455 /// Assign the iterator to the next |
446 /// outgoing arc of the corresponding node. |
456 /// outgoing arc of the corresponding node. |
447 OutArcIt& operator++() { return *this; } |
457 OutArcIt& operator++() { return *this; } |
448 }; |
458 }; |
449 |
459 |
450 /// This iterator goes trough the incoming directed arcs of a node. |
460 /// Iterator class for the incoming arcs of a node. |
451 |
461 |
452 /// This iterator goes trough the \e incoming arcs of a certain node |
462 /// This iterator goes trough the \e incoming directed arcs of a |
453 /// of a graph. |
463 /// certain node of a graph. |
454 /// Its usage is quite simple, for example you can count the number |
464 /// Its usage is quite simple, for example you can count the number |
455 /// of outgoing arcs of a node \c n |
465 /// of incoming arcs of a node \c n |
456 /// in graph \c g of type \c Graph as follows. |
466 /// in a graph \c g of type \c %Graph as follows. |
457 ///\code |
467 ///\code |
458 /// int count=0; |
468 /// int count=0; |
459 /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; |
469 /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; |
460 ///\endcode |
470 ///\endcode |
461 |
|
462 class InArcIt : public Arc { |
471 class InArcIt : public Arc { |
463 public: |
472 public: |
464 /// Default constructor |
473 /// Default constructor |
465 |
474 |
466 /// @warning The default constructor sets the iterator |
475 /// Default constructor. |
467 /// to an undefined value. |
476 /// \warning It sets the iterator to an undefined value. |
468 InArcIt() { } |
477 InArcIt() { } |
469 /// Copy constructor. |
478 /// Copy constructor. |
470 |
479 |
471 /// Copy constructor. |
480 /// Copy constructor. |
472 /// |
481 /// |
473 InArcIt(const InArcIt& e) : Arc(e) { } |
482 InArcIt(const InArcIt& e) : Arc(e) { } |
474 /// Initialize the iterator to be invalid. |
483 /// %Invalid constructor \& conversion. |
475 |
484 |
476 /// Initialize the iterator to be invalid. |
485 /// Initializes the iterator to be invalid. |
477 /// |
486 /// \sa Invalid for more details. |
478 InArcIt(Invalid) { } |
487 InArcIt(Invalid) { } |
479 /// This constructor sets the iterator to first incoming arc. |
488 /// Sets the iterator to the first incoming arc. |
480 |
489 |
481 /// This constructor set the iterator to the first incoming arc of |
490 /// Sets the iterator to the first incoming arc of the given node. |
482 /// the node. |
491 /// |
483 ///@param n the node |
|
484 ///@param g the graph |
|
485 InArcIt(const Graph& g, const Node& n) { |
492 InArcIt(const Graph& g, const Node& n) { |
486 ignore_unused_variable_warning(n); |
493 ignore_unused_variable_warning(n); |
487 ignore_unused_variable_warning(g); |
494 ignore_unused_variable_warning(g); |
488 } |
495 } |
489 /// Arc -> InArcIt conversion |
496 /// Sets the iterator to the given arc. |
490 |
497 |
491 /// Sets the iterator to the value of the trivial iterator \c e. |
498 /// Sets the iterator to the given arc of the given graph. |
492 /// This feature necessitates that each time we |
499 /// |
493 /// iterate the arc-set, the iteration order is the same. |
|
494 InArcIt(const Graph&, const Arc&) { } |
500 InArcIt(const Graph&, const Arc&) { } |
495 /// Next incoming arc |
501 /// Next incoming arc |
496 |
502 |
497 /// Assign the iterator to the next inarc of the corresponding node. |
503 /// Assign the iterator to the next |
498 /// |
504 /// incoming arc of the corresponding node. |
499 InArcIt& operator++() { return *this; } |
505 InArcIt& operator++() { return *this; } |
500 }; |
506 }; |
501 |
507 |
502 /// \brief Reference map of the nodes to type \c T. |
508 /// \brief Standard graph map type for the nodes. |
503 /// |
509 /// |
504 /// Reference map of the nodes to type \c T. |
510 /// Standard graph map type for the nodes. |
|
511 /// It conforms to the ReferenceMap concept. |
505 template<class T> |
512 template<class T> |
506 class NodeMap : public ReferenceMap<Node, T, T&, const T&> |
513 class NodeMap : public ReferenceMap<Node, T, T&, const T&> |
507 { |
514 { |
508 public: |
515 public: |
509 |
516 |
510 ///\e |
517 /// Constructor |
511 NodeMap(const Graph&) { } |
518 explicit NodeMap(const Graph&) { } |
512 ///\e |
519 /// Constructor with given initial value |
513 NodeMap(const Graph&, T) { } |
520 NodeMap(const Graph&, T) { } |
514 |
521 |
515 private: |
522 private: |
516 ///Copy constructor |
523 ///Copy constructor |
517 NodeMap(const NodeMap& nm) : |
524 NodeMap(const NodeMap& nm) : |
570 checkConcept<ReadMap<Edge, T>, CMap>(); |
581 checkConcept<ReadMap<Edge, T>, CMap>(); |
571 return *this; |
582 return *this; |
572 } |
583 } |
573 }; |
584 }; |
574 |
585 |
575 /// \brief Direct the given edge. |
586 /// \brief The first node of the edge. |
576 /// |
587 /// |
577 /// Direct the given edge. The returned arc source |
588 /// Returns the first node of the given edge. |
578 /// will be the given node. |
589 /// |
579 Arc direct(const Edge&, const Node&) const { |
590 /// Edges don't have source and target nodes, however methods |
580 return INVALID; |
591 /// u() and v() are used to query the two end-nodes of an edge. |
581 } |
592 /// The orientation of an edge that arises this way is called |
582 |
593 /// the inherent direction, it is used to define the default |
583 /// \brief Direct the given edge. |
594 /// direction for the corresponding arcs. |
584 /// |
|
585 /// Direct the given edge. The returned arc |
|
586 /// represents the given edge and the direction comes |
|
587 /// from the bool parameter. The source of the edge and |
|
588 /// the directed arc is the same when the given bool is true. |
|
589 Arc direct(const Edge&, bool) const { |
|
590 return INVALID; |
|
591 } |
|
592 |
|
593 /// \brief Returns true if the arc has default orientation. |
|
594 /// |
|
595 /// Returns whether the given directed arc is same orientation as |
|
596 /// the corresponding edge's default orientation. |
|
597 bool direction(Arc) const { return true; } |
|
598 |
|
599 /// \brief Returns the opposite directed arc. |
|
600 /// |
|
601 /// Returns the opposite directed arc. |
|
602 Arc oppositeArc(Arc) const { return INVALID; } |
|
603 |
|
604 /// \brief Opposite node on an arc |
|
605 /// |
|
606 /// \return The opposite of the given node on the given edge. |
|
607 Node oppositeNode(Node, Edge) const { return INVALID; } |
|
608 |
|
609 /// \brief First node of the edge. |
|
610 /// |
|
611 /// \return The first node of the given edge. |
|
612 /// |
|
613 /// Naturally edges don't have direction and thus |
|
614 /// don't have source and target node. However we use \c u() and \c v() |
|
615 /// methods to query the two nodes of the arc. The direction of the |
|
616 /// arc which arises this way is called the inherent direction of the |
|
617 /// edge, and is used to define the "default" direction |
|
618 /// of the directed versions of the arcs. |
|
619 /// \sa v() |
595 /// \sa v() |
620 /// \sa direction() |
596 /// \sa direction() |
621 Node u(Edge) const { return INVALID; } |
597 Node u(Edge) const { return INVALID; } |
622 |
598 |
623 /// \brief Second node of the edge. |
599 /// \brief The second node of the edge. |
624 /// |
600 /// |
625 /// \return The second node of the given edge. |
601 /// Returns the second node of the given edge. |
626 /// |
602 /// |
627 /// Naturally edges don't have direction and thus |
603 /// Edges don't have source and target nodes, however methods |
628 /// don't have source and target node. However we use \c u() and \c v() |
604 /// u() and v() are used to query the two end-nodes of an edge. |
629 /// methods to query the two nodes of the arc. The direction of the |
605 /// The orientation of an edge that arises this way is called |
630 /// arc which arises this way is called the inherent direction of the |
606 /// the inherent direction, it is used to define the default |
631 /// edge, and is used to define the "default" direction |
607 /// direction for the corresponding arcs. |
632 /// of the directed versions of the arcs. |
|
633 /// \sa u() |
608 /// \sa u() |
634 /// \sa direction() |
609 /// \sa direction() |
635 Node v(Edge) const { return INVALID; } |
610 Node v(Edge) const { return INVALID; } |
636 |
611 |
637 /// \brief Source node of the directed arc. |
612 /// \brief The source node of the arc. |
|
613 /// |
|
614 /// Returns the source node of the given arc. |
638 Node source(Arc) const { return INVALID; } |
615 Node source(Arc) const { return INVALID; } |
639 |
616 |
640 /// \brief Target node of the directed arc. |
617 /// \brief The target node of the arc. |
|
618 /// |
|
619 /// Returns the target node of the given arc. |
641 Node target(Arc) const { return INVALID; } |
620 Node target(Arc) const { return INVALID; } |
642 |
621 |
643 /// \brief Returns the id of the node. |
622 /// \brief The ID of the node. |
|
623 /// |
|
624 /// Returns the ID of the given node. |
644 int id(Node) const { return -1; } |
625 int id(Node) const { return -1; } |
645 |
626 |
646 /// \brief Returns the id of the edge. |
627 /// \brief The ID of the edge. |
|
628 /// |
|
629 /// Returns the ID of the given edge. |
647 int id(Edge) const { return -1; } |
630 int id(Edge) const { return -1; } |
648 |
631 |
649 /// \brief Returns the id of the arc. |
632 /// \brief The ID of the arc. |
|
633 /// |
|
634 /// Returns the ID of the given arc. |
650 int id(Arc) const { return -1; } |
635 int id(Arc) const { return -1; } |
651 |
636 |
652 /// \brief Returns the node with the given id. |
637 /// \brief The node with the given ID. |
653 /// |
638 /// |
654 /// \pre The argument should be a valid node id in the graph. |
639 /// Returns the node with the given ID. |
|
640 /// \pre The argument should be a valid node ID in the graph. |
655 Node nodeFromId(int) const { return INVALID; } |
641 Node nodeFromId(int) const { return INVALID; } |
656 |
642 |
657 /// \brief Returns the edge with the given id. |
643 /// \brief The edge with the given ID. |
658 /// |
644 /// |
659 /// \pre The argument should be a valid edge id in the graph. |
645 /// Returns the edge with the given ID. |
|
646 /// \pre The argument should be a valid edge ID in the graph. |
660 Edge edgeFromId(int) const { return INVALID; } |
647 Edge edgeFromId(int) const { return INVALID; } |
661 |
648 |
662 /// \brief Returns the arc with the given id. |
649 /// \brief The arc with the given ID. |
663 /// |
650 /// |
664 /// \pre The argument should be a valid arc id in the graph. |
651 /// Returns the arc with the given ID. |
|
652 /// \pre The argument should be a valid arc ID in the graph. |
665 Arc arcFromId(int) const { return INVALID; } |
653 Arc arcFromId(int) const { return INVALID; } |
666 |
654 |
667 /// \brief Returns an upper bound on the node IDs. |
655 /// \brief An upper bound on the node IDs. |
|
656 /// |
|
657 /// Returns an upper bound on the node IDs. |
668 int maxNodeId() const { return -1; } |
658 int maxNodeId() const { return -1; } |
669 |
659 |
670 /// \brief Returns an upper bound on the edge IDs. |
660 /// \brief An upper bound on the edge IDs. |
|
661 /// |
|
662 /// Returns an upper bound on the edge IDs. |
671 int maxEdgeId() const { return -1; } |
663 int maxEdgeId() const { return -1; } |
672 |
664 |
673 /// \brief Returns an upper bound on the arc IDs. |
665 /// \brief An upper bound on the arc IDs. |
|
666 /// |
|
667 /// Returns an upper bound on the arc IDs. |
674 int maxArcId() const { return -1; } |
668 int maxArcId() const { return -1; } |
|
669 |
|
670 /// \brief The direction of the arc. |
|
671 /// |
|
672 /// Returns \c true if the direction of the given arc is the same as |
|
673 /// the inherent orientation of the represented edge. |
|
674 bool direction(Arc) const { return true; } |
|
675 |
|
676 /// \brief Direct the edge. |
|
677 /// |
|
678 /// Direct the given edge. The returned arc |
|
679 /// represents the given edge and its direction comes |
|
680 /// from the bool parameter. If it is \c true, then the direction |
|
681 /// of the arc is the same as the inherent orientation of the edge. |
|
682 Arc direct(Edge, bool) const { |
|
683 return INVALID; |
|
684 } |
|
685 |
|
686 /// \brief Direct the edge. |
|
687 /// |
|
688 /// Direct the given edge. The returned arc represents the given |
|
689 /// edge and its source node is the given node. |
|
690 Arc direct(Edge, Node) const { |
|
691 return INVALID; |
|
692 } |
|
693 |
|
694 /// \brief The oppositely directed arc. |
|
695 /// |
|
696 /// Returns the oppositely directed arc representing the same edge. |
|
697 Arc oppositeArc(Arc) const { return INVALID; } |
|
698 |
|
699 /// \brief The opposite node on the edge. |
|
700 /// |
|
701 /// Returns the opposite node on the given edge. |
|
702 Node oppositeNode(Node, Edge) const { return INVALID; } |
675 |
703 |
676 void first(Node&) const {} |
704 void first(Node&) const {} |
677 void next(Node&) const {} |
705 void next(Node&) const {} |
678 |
706 |
679 void first(Edge&) const {} |
707 void first(Edge&) const {} |