|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 ///\ingroup graph_concepts |
|
20 ///\file |
|
21 ///\brief The concept of the undirected graphs. |
|
22 |
|
23 |
|
24 #ifndef LEMON_CONCEPT_UGRAPH_H |
|
25 #define LEMON_CONCEPT_UGRAPH_H |
|
26 |
|
27 #include <lemon/concepts/graph_components.h> |
|
28 #include <lemon/concepts/graph.h> |
|
29 #include <lemon/bits/utility.h> |
|
30 |
|
31 namespace lemon { |
|
32 namespace concepts { |
|
33 |
|
34 /// \addtogroup graph_concepts |
|
35 /// @{ |
|
36 |
|
37 |
|
38 /// \brief Class describing the concept of Undirected Graphs. |
|
39 /// |
|
40 /// This class describes the common interface of all Undirected |
|
41 /// Graphs. |
|
42 /// |
|
43 /// As all concept describing classes it provides only interface |
|
44 /// without any sensible implementation. So any algorithm for |
|
45 /// undirected graph should compile with this class, but it will not |
|
46 /// run properly, of course. |
|
47 /// |
|
48 /// The LEMON undirected graphs also fulfill the concept of |
|
49 /// directed graphs (\ref lemon::concepts::Graph "Graph |
|
50 /// Concept"). Each undirected edges can be seen as two opposite |
|
51 /// directed edge and consequently the undirected graph can be |
|
52 /// seen as the direceted graph of these directed edges. The |
|
53 /// UGraph has the UEdge inner class for the undirected edges and |
|
54 /// the Edge type for the directed edges. The Edge type is |
|
55 /// convertible to UEdge or inherited from it so from a directed |
|
56 /// edge we can get the represented undirected edge. |
|
57 /// |
|
58 /// In the sense of the LEMON each undirected edge has a default |
|
59 /// direction (it should be in every computer implementation, |
|
60 /// because the order of undirected edge's nodes defines an |
|
61 /// orientation). With the default orientation we can define that |
|
62 /// the directed edge is forward or backward directed. With the \c |
|
63 /// direction() and \c direct() function we can get the direction |
|
64 /// of the directed edge and we can direct an undirected edge. |
|
65 /// |
|
66 /// The UEdgeIt is an iterator for the undirected edges. We can use |
|
67 /// the UEdgeMap to map values for the undirected edges. The InEdgeIt and |
|
68 /// OutEdgeIt iterates on the same undirected edges but with opposite |
|
69 /// direction. The IncEdgeIt iterates also on the same undirected edges |
|
70 /// as the OutEdgeIt and InEdgeIt but it is not convertible to Edge just |
|
71 /// to UEdge. |
|
72 class UGraph { |
|
73 public: |
|
74 /// \brief The undirected graph should be tagged by the |
|
75 /// UndirectedTag. |
|
76 /// |
|
77 /// The undirected graph should be tagged by the UndirectedTag. This |
|
78 /// tag helps the enable_if technics to make compile time |
|
79 /// specializations for undirected graphs. |
|
80 typedef True UndirectedTag; |
|
81 |
|
82 /// \brief The base type of node iterators, |
|
83 /// or in other words, the trivial node iterator. |
|
84 /// |
|
85 /// This is the base type of each node iterator, |
|
86 /// thus each kind of node iterator converts to this. |
|
87 /// More precisely each kind of node iterator should be inherited |
|
88 /// from the trivial node iterator. |
|
89 class Node { |
|
90 public: |
|
91 /// Default constructor |
|
92 |
|
93 /// @warning The default constructor sets the iterator |
|
94 /// to an undefined value. |
|
95 Node() { } |
|
96 /// Copy constructor. |
|
97 |
|
98 /// Copy constructor. |
|
99 /// |
|
100 Node(const Node&) { } |
|
101 |
|
102 /// Invalid constructor \& conversion. |
|
103 |
|
104 /// This constructor initializes the iterator to be invalid. |
|
105 /// \sa Invalid for more details. |
|
106 Node(Invalid) { } |
|
107 /// Equality operator |
|
108 |
|
109 /// Two iterators are equal if and only if they point to the |
|
110 /// same object or both are invalid. |
|
111 bool operator==(Node) const { return true; } |
|
112 |
|
113 /// Inequality operator |
|
114 |
|
115 /// \sa operator==(Node n) |
|
116 /// |
|
117 bool operator!=(Node) const { return true; } |
|
118 |
|
119 /// Artificial ordering operator. |
|
120 |
|
121 /// To allow the use of graph descriptors as key type in std::map or |
|
122 /// similar associative container we require this. |
|
123 /// |
|
124 /// \note This operator only have to define some strict ordering of |
|
125 /// the items; this order has nothing to do with the iteration |
|
126 /// ordering of the items. |
|
127 bool operator<(Node) const { return false; } |
|
128 |
|
129 }; |
|
130 |
|
131 /// This iterator goes through each node. |
|
132 |
|
133 /// This iterator goes through each node. |
|
134 /// Its usage is quite simple, for example you can count the number |
|
135 /// of nodes in graph \c g of type \c Graph like this: |
|
136 ///\code |
|
137 /// int count=0; |
|
138 /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; |
|
139 ///\endcode |
|
140 class NodeIt : public Node { |
|
141 public: |
|
142 /// Default constructor |
|
143 |
|
144 /// @warning The default constructor sets the iterator |
|
145 /// to an undefined value. |
|
146 NodeIt() { } |
|
147 /// Copy constructor. |
|
148 |
|
149 /// Copy constructor. |
|
150 /// |
|
151 NodeIt(const NodeIt& n) : Node(n) { } |
|
152 /// Invalid constructor \& conversion. |
|
153 |
|
154 /// Initialize the iterator to be invalid. |
|
155 /// \sa Invalid for more details. |
|
156 NodeIt(Invalid) { } |
|
157 /// Sets the iterator to the first node. |
|
158 |
|
159 /// Sets the iterator to the first node of \c g. |
|
160 /// |
|
161 NodeIt(const UGraph&) { } |
|
162 /// Node -> NodeIt conversion. |
|
163 |
|
164 /// Sets the iterator to the node of \c the graph pointed by |
|
165 /// the trivial iterator. |
|
166 /// This feature necessitates that each time we |
|
167 /// iterate the edge-set, the iteration order is the same. |
|
168 NodeIt(const UGraph&, const Node&) { } |
|
169 /// Next node. |
|
170 |
|
171 /// Assign the iterator to the next node. |
|
172 /// |
|
173 NodeIt& operator++() { return *this; } |
|
174 }; |
|
175 |
|
176 |
|
177 /// The base type of the undirected edge iterators. |
|
178 |
|
179 /// The base type of the undirected edge iterators. |
|
180 /// |
|
181 class UEdge { |
|
182 public: |
|
183 /// Default constructor |
|
184 |
|
185 /// @warning The default constructor sets the iterator |
|
186 /// to an undefined value. |
|
187 UEdge() { } |
|
188 /// Copy constructor. |
|
189 |
|
190 /// Copy constructor. |
|
191 /// |
|
192 UEdge(const UEdge&) { } |
|
193 /// Initialize the iterator to be invalid. |
|
194 |
|
195 /// Initialize the iterator to be invalid. |
|
196 /// |
|
197 UEdge(Invalid) { } |
|
198 /// Equality operator |
|
199 |
|
200 /// Two iterators are equal if and only if they point to the |
|
201 /// same object or both are invalid. |
|
202 bool operator==(UEdge) const { return true; } |
|
203 /// Inequality operator |
|
204 |
|
205 /// \sa operator==(UEdge n) |
|
206 /// |
|
207 bool operator!=(UEdge) const { return true; } |
|
208 |
|
209 /// Artificial ordering operator. |
|
210 |
|
211 /// To allow the use of graph descriptors as key type in std::map or |
|
212 /// similar associative container we require this. |
|
213 /// |
|
214 /// \note This operator only have to define some strict ordering of |
|
215 /// the items; this order has nothing to do with the iteration |
|
216 /// ordering of the items. |
|
217 bool operator<(UEdge) const { return false; } |
|
218 }; |
|
219 |
|
220 /// This iterator goes through each undirected edge. |
|
221 |
|
222 /// This iterator goes through each undirected edge of a graph. |
|
223 /// Its usage is quite simple, for example you can count the number |
|
224 /// of undirected edges in a graph \c g of type \c Graph as follows: |
|
225 ///\code |
|
226 /// int count=0; |
|
227 /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count; |
|
228 ///\endcode |
|
229 class UEdgeIt : public UEdge { |
|
230 public: |
|
231 /// Default constructor |
|
232 |
|
233 /// @warning The default constructor sets the iterator |
|
234 /// to an undefined value. |
|
235 UEdgeIt() { } |
|
236 /// Copy constructor. |
|
237 |
|
238 /// Copy constructor. |
|
239 /// |
|
240 UEdgeIt(const UEdgeIt& e) : UEdge(e) { } |
|
241 /// Initialize the iterator to be invalid. |
|
242 |
|
243 /// Initialize the iterator to be invalid. |
|
244 /// |
|
245 UEdgeIt(Invalid) { } |
|
246 /// This constructor sets the iterator to the first undirected edge. |
|
247 |
|
248 /// This constructor sets the iterator to the first undirected edge. |
|
249 UEdgeIt(const UGraph&) { } |
|
250 /// UEdge -> UEdgeIt conversion |
|
251 |
|
252 /// Sets the iterator to the value of the trivial iterator. |
|
253 /// This feature necessitates that each time we |
|
254 /// iterate the undirected edge-set, the iteration order is the |
|
255 /// same. |
|
256 UEdgeIt(const UGraph&, const UEdge&) { } |
|
257 /// Next undirected edge |
|
258 |
|
259 /// Assign the iterator to the next undirected edge. |
|
260 UEdgeIt& operator++() { return *this; } |
|
261 }; |
|
262 |
|
263 /// \brief This iterator goes trough the incident undirected |
|
264 /// edges of a node. |
|
265 /// |
|
266 /// This iterator goes trough the incident undirected edges |
|
267 /// of a certain node of a graph. You should assume that the |
|
268 /// loop edges will be iterated twice. |
|
269 /// |
|
270 /// Its usage is quite simple, for example you can compute the |
|
271 /// degree (i.e. count the number of incident edges of a node \c n |
|
272 /// in graph \c g of type \c Graph as follows. |
|
273 /// |
|
274 ///\code |
|
275 /// int count=0; |
|
276 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
277 ///\endcode |
|
278 class IncEdgeIt : public UEdge { |
|
279 public: |
|
280 /// Default constructor |
|
281 |
|
282 /// @warning The default constructor sets the iterator |
|
283 /// to an undefined value. |
|
284 IncEdgeIt() { } |
|
285 /// Copy constructor. |
|
286 |
|
287 /// Copy constructor. |
|
288 /// |
|
289 IncEdgeIt(const IncEdgeIt& e) : UEdge(e) { } |
|
290 /// Initialize the iterator to be invalid. |
|
291 |
|
292 /// Initialize the iterator to be invalid. |
|
293 /// |
|
294 IncEdgeIt(Invalid) { } |
|
295 /// This constructor sets the iterator to first incident edge. |
|
296 |
|
297 /// This constructor set the iterator to the first incident edge of |
|
298 /// the node. |
|
299 IncEdgeIt(const UGraph&, const Node&) { } |
|
300 /// UEdge -> IncEdgeIt conversion |
|
301 |
|
302 /// Sets the iterator to the value of the trivial iterator \c e. |
|
303 /// This feature necessitates that each time we |
|
304 /// iterate the edge-set, the iteration order is the same. |
|
305 IncEdgeIt(const UGraph&, const UEdge&) { } |
|
306 /// Next incident edge |
|
307 |
|
308 /// Assign the iterator to the next incident edge |
|
309 /// of the corresponding node. |
|
310 IncEdgeIt& operator++() { return *this; } |
|
311 }; |
|
312 |
|
313 /// The directed edge type. |
|
314 |
|
315 /// The directed edge type. It can be converted to the |
|
316 /// undirected edge or it should be inherited from the undirected |
|
317 /// edge. |
|
318 class Edge : public UEdge { |
|
319 public: |
|
320 /// Default constructor |
|
321 |
|
322 /// @warning The default constructor sets the iterator |
|
323 /// to an undefined value. |
|
324 Edge() { } |
|
325 /// Copy constructor. |
|
326 |
|
327 /// Copy constructor. |
|
328 /// |
|
329 Edge(const Edge& e) : UEdge(e) { } |
|
330 /// Initialize the iterator to be invalid. |
|
331 |
|
332 /// Initialize the iterator to be invalid. |
|
333 /// |
|
334 Edge(Invalid) { } |
|
335 /// Equality operator |
|
336 |
|
337 /// Two iterators are equal if and only if they point to the |
|
338 /// same object or both are invalid. |
|
339 bool operator==(Edge) const { return true; } |
|
340 /// Inequality operator |
|
341 |
|
342 /// \sa operator==(Edge n) |
|
343 /// |
|
344 bool operator!=(Edge) const { return true; } |
|
345 |
|
346 /// Artificial ordering operator. |
|
347 |
|
348 /// To allow the use of graph descriptors as key type in std::map or |
|
349 /// similar associative container we require this. |
|
350 /// |
|
351 /// \note This operator only have to define some strict ordering of |
|
352 /// the items; this order has nothing to do with the iteration |
|
353 /// ordering of the items. |
|
354 bool operator<(Edge) const { return false; } |
|
355 |
|
356 }; |
|
357 /// This iterator goes through each directed edge. |
|
358 |
|
359 /// This iterator goes through each edge of a graph. |
|
360 /// Its usage is quite simple, for example you can count the number |
|
361 /// of edges in a graph \c g of type \c Graph as follows: |
|
362 ///\code |
|
363 /// int count=0; |
|
364 /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; |
|
365 ///\endcode |
|
366 class EdgeIt : public Edge { |
|
367 public: |
|
368 /// Default constructor |
|
369 |
|
370 /// @warning The default constructor sets the iterator |
|
371 /// to an undefined value. |
|
372 EdgeIt() { } |
|
373 /// Copy constructor. |
|
374 |
|
375 /// Copy constructor. |
|
376 /// |
|
377 EdgeIt(const EdgeIt& e) : Edge(e) { } |
|
378 /// Initialize the iterator to be invalid. |
|
379 |
|
380 /// Initialize the iterator to be invalid. |
|
381 /// |
|
382 EdgeIt(Invalid) { } |
|
383 /// This constructor sets the iterator to the first edge. |
|
384 |
|
385 /// This constructor sets the iterator to the first edge of \c g. |
|
386 ///@param g the graph |
|
387 EdgeIt(const UGraph &g) { ignore_unused_variable_warning(g); } |
|
388 /// Edge -> EdgeIt conversion |
|
389 |
|
390 /// Sets the iterator to the value of the trivial iterator \c e. |
|
391 /// This feature necessitates that each time we |
|
392 /// iterate the edge-set, the iteration order is the same. |
|
393 EdgeIt(const UGraph&, const Edge&) { } |
|
394 ///Next edge |
|
395 |
|
396 /// Assign the iterator to the next edge. |
|
397 EdgeIt& operator++() { return *this; } |
|
398 }; |
|
399 |
|
400 /// This iterator goes trough the outgoing directed edges of a node. |
|
401 |
|
402 /// This iterator goes trough the \e outgoing edges of a certain node |
|
403 /// of a graph. |
|
404 /// Its usage is quite simple, for example you can count the number |
|
405 /// of outgoing edges of a node \c n |
|
406 /// in graph \c g of type \c Graph as follows. |
|
407 ///\code |
|
408 /// int count=0; |
|
409 /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
410 ///\endcode |
|
411 |
|
412 class OutEdgeIt : public Edge { |
|
413 public: |
|
414 /// Default constructor |
|
415 |
|
416 /// @warning The default constructor sets the iterator |
|
417 /// to an undefined value. |
|
418 OutEdgeIt() { } |
|
419 /// Copy constructor. |
|
420 |
|
421 /// Copy constructor. |
|
422 /// |
|
423 OutEdgeIt(const OutEdgeIt& e) : Edge(e) { } |
|
424 /// Initialize the iterator to be invalid. |
|
425 |
|
426 /// Initialize the iterator to be invalid. |
|
427 /// |
|
428 OutEdgeIt(Invalid) { } |
|
429 /// This constructor sets the iterator to the first outgoing edge. |
|
430 |
|
431 /// This constructor sets the iterator to the first outgoing edge of |
|
432 /// the node. |
|
433 ///@param n the node |
|
434 ///@param g the graph |
|
435 OutEdgeIt(const UGraph& n, const Node& g) { |
|
436 ignore_unused_variable_warning(n); |
|
437 ignore_unused_variable_warning(g); |
|
438 } |
|
439 /// Edge -> OutEdgeIt conversion |
|
440 |
|
441 /// Sets the iterator to the value of the trivial iterator. |
|
442 /// This feature necessitates that each time we |
|
443 /// iterate the edge-set, the iteration order is the same. |
|
444 OutEdgeIt(const UGraph&, const Edge&) { } |
|
445 ///Next outgoing edge |
|
446 |
|
447 /// Assign the iterator to the next |
|
448 /// outgoing edge of the corresponding node. |
|
449 OutEdgeIt& operator++() { return *this; } |
|
450 }; |
|
451 |
|
452 /// This iterator goes trough the incoming directed edges of a node. |
|
453 |
|
454 /// This iterator goes trough the \e incoming edges of a certain node |
|
455 /// of a graph. |
|
456 /// Its usage is quite simple, for example you can count the number |
|
457 /// of outgoing edges of a node \c n |
|
458 /// in graph \c g of type \c Graph as follows. |
|
459 ///\code |
|
460 /// int count=0; |
|
461 /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; |
|
462 ///\endcode |
|
463 |
|
464 class InEdgeIt : public Edge { |
|
465 public: |
|
466 /// Default constructor |
|
467 |
|
468 /// @warning The default constructor sets the iterator |
|
469 /// to an undefined value. |
|
470 InEdgeIt() { } |
|
471 /// Copy constructor. |
|
472 |
|
473 /// Copy constructor. |
|
474 /// |
|
475 InEdgeIt(const InEdgeIt& e) : Edge(e) { } |
|
476 /// Initialize the iterator to be invalid. |
|
477 |
|
478 /// Initialize the iterator to be invalid. |
|
479 /// |
|
480 InEdgeIt(Invalid) { } |
|
481 /// This constructor sets the iterator to first incoming edge. |
|
482 |
|
483 /// This constructor set the iterator to the first incoming edge of |
|
484 /// the node. |
|
485 ///@param n the node |
|
486 ///@param g the graph |
|
487 InEdgeIt(const UGraph& g, const Node& n) { |
|
488 ignore_unused_variable_warning(n); |
|
489 ignore_unused_variable_warning(g); |
|
490 } |
|
491 /// Edge -> InEdgeIt conversion |
|
492 |
|
493 /// Sets the iterator to the value of the trivial iterator \c e. |
|
494 /// This feature necessitates that each time we |
|
495 /// iterate the edge-set, the iteration order is the same. |
|
496 InEdgeIt(const UGraph&, const Edge&) { } |
|
497 /// Next incoming edge |
|
498 |
|
499 /// Assign the iterator to the next inedge of the corresponding node. |
|
500 /// |
|
501 InEdgeIt& operator++() { return *this; } |
|
502 }; |
|
503 |
|
504 /// \brief Read write map of the nodes to type \c T. |
|
505 /// |
|
506 /// ReadWrite map of the nodes to type \c T. |
|
507 /// \sa Reference |
|
508 /// \warning Making maps that can handle bool type (NodeMap<bool>) |
|
509 /// needs some extra attention! |
|
510 template<class T> |
|
511 class NodeMap : public ReadWriteMap< Node, T > |
|
512 { |
|
513 public: |
|
514 |
|
515 ///\e |
|
516 NodeMap(const UGraph&) { } |
|
517 ///\e |
|
518 NodeMap(const UGraph&, T) { } |
|
519 |
|
520 ///Copy constructor |
|
521 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } |
|
522 ///Assignment operator |
|
523 template <typename CMap> |
|
524 NodeMap& operator=(const CMap&) { |
|
525 checkConcept<ReadMap<Node, T>, CMap>(); |
|
526 return *this; |
|
527 } |
|
528 }; |
|
529 |
|
530 /// \brief Read write map of the directed edges to type \c T. |
|
531 /// |
|
532 /// Reference map of the directed edges to type \c T. |
|
533 /// \sa Reference |
|
534 /// \warning Making maps that can handle bool type (EdgeMap<bool>) |
|
535 /// needs some extra attention! |
|
536 template<class T> |
|
537 class EdgeMap : public ReadWriteMap<Edge,T> |
|
538 { |
|
539 public: |
|
540 |
|
541 ///\e |
|
542 EdgeMap(const UGraph&) { } |
|
543 ///\e |
|
544 EdgeMap(const UGraph&, T) { } |
|
545 ///Copy constructor |
|
546 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { } |
|
547 ///Assignment operator |
|
548 template <typename CMap> |
|
549 EdgeMap& operator=(const CMap&) { |
|
550 checkConcept<ReadMap<Edge, T>, CMap>(); |
|
551 return *this; |
|
552 } |
|
553 }; |
|
554 |
|
555 /// Read write map of the undirected edges to type \c T. |
|
556 |
|
557 /// Reference map of the edges to type \c T. |
|
558 /// \sa Reference |
|
559 /// \warning Making maps that can handle bool type (UEdgeMap<bool>) |
|
560 /// needs some extra attention! |
|
561 template<class T> |
|
562 class UEdgeMap : public ReadWriteMap<UEdge,T> |
|
563 { |
|
564 public: |
|
565 |
|
566 ///\e |
|
567 UEdgeMap(const UGraph&) { } |
|
568 ///\e |
|
569 UEdgeMap(const UGraph&, T) { } |
|
570 ///Copy constructor |
|
571 UEdgeMap(const UEdgeMap& em) : ReadWriteMap<UEdge,T>(em) {} |
|
572 ///Assignment operator |
|
573 template <typename CMap> |
|
574 UEdgeMap& operator=(const CMap&) { |
|
575 checkConcept<ReadMap<UEdge, T>, CMap>(); |
|
576 return *this; |
|
577 } |
|
578 }; |
|
579 |
|
580 /// \brief Direct the given undirected edge. |
|
581 /// |
|
582 /// Direct the given undirected edge. The returned edge source |
|
583 /// will be the given node. |
|
584 Edge direct(const UEdge&, const Node&) const { |
|
585 return INVALID; |
|
586 } |
|
587 |
|
588 /// \brief Direct the given undirected edge. |
|
589 /// |
|
590 /// Direct the given undirected edge. The returned edge |
|
591 /// represents the given undireted edge and the direction comes |
|
592 /// from the given bool. The source of the undirected edge and |
|
593 /// the directed edge is the same when the given bool is true. |
|
594 Edge direct(const UEdge&, bool) const { |
|
595 return INVALID; |
|
596 } |
|
597 |
|
598 /// \brief Returns true if the edge has default orientation. |
|
599 /// |
|
600 /// Returns whether the given directed edge is same orientation as |
|
601 /// the corresponding undirected edge's default orientation. |
|
602 bool direction(Edge) const { return true; } |
|
603 |
|
604 /// \brief Returns the opposite directed edge. |
|
605 /// |
|
606 /// Returns the opposite directed edge. |
|
607 Edge oppositeEdge(Edge) const { return INVALID; } |
|
608 |
|
609 /// \brief Opposite node on an edge |
|
610 /// |
|
611 /// \return the opposite of the given Node on the given UEdge |
|
612 Node oppositeNode(Node, UEdge) const { return INVALID; } |
|
613 |
|
614 /// \brief First node of the undirected edge. |
|
615 /// |
|
616 /// \return the first node of the given UEdge. |
|
617 /// |
|
618 /// Naturally undirected edges don't have direction and thus |
|
619 /// don't have source and target node. But we use these two methods |
|
620 /// to query the two nodes of the edge. The direction of the edge |
|
621 /// which arises this way is called the inherent direction of the |
|
622 /// undirected edge, and is used to define the "default" direction |
|
623 /// of the directed versions of the edges. |
|
624 /// \sa direction |
|
625 Node source(UEdge) const { return INVALID; } |
|
626 |
|
627 /// \brief Second node of the undirected edge. |
|
628 Node target(UEdge) const { return INVALID; } |
|
629 |
|
630 /// \brief Source node of the directed edge. |
|
631 Node source(Edge) const { return INVALID; } |
|
632 |
|
633 /// \brief Target node of the directed edge. |
|
634 Node target(Edge) const { return INVALID; } |
|
635 |
|
636 void first(Node&) const {} |
|
637 void next(Node&) const {} |
|
638 |
|
639 void first(UEdge&) const {} |
|
640 void next(UEdge&) const {} |
|
641 |
|
642 void first(Edge&) const {} |
|
643 void next(Edge&) const {} |
|
644 |
|
645 void firstOut(Edge&, Node) const {} |
|
646 void nextOut(Edge&) const {} |
|
647 |
|
648 void firstIn(Edge&, Node) const {} |
|
649 void nextIn(Edge&) const {} |
|
650 |
|
651 |
|
652 void firstInc(UEdge &, bool &, const Node &) const {} |
|
653 void nextInc(UEdge &, bool &) const {} |
|
654 |
|
655 /// \brief Base node of the iterator |
|
656 /// |
|
657 /// Returns the base node (the source in this case) of the iterator |
|
658 Node baseNode(OutEdgeIt e) const { |
|
659 return source(e); |
|
660 } |
|
661 /// \brief Running node of the iterator |
|
662 /// |
|
663 /// Returns the running node (the target in this case) of the |
|
664 /// iterator |
|
665 Node runningNode(OutEdgeIt e) const { |
|
666 return target(e); |
|
667 } |
|
668 |
|
669 /// \brief Base node of the iterator |
|
670 /// |
|
671 /// Returns the base node (the target in this case) of the iterator |
|
672 Node baseNode(InEdgeIt e) const { |
|
673 return target(e); |
|
674 } |
|
675 /// \brief Running node of the iterator |
|
676 /// |
|
677 /// Returns the running node (the source in this case) of the |
|
678 /// iterator |
|
679 Node runningNode(InEdgeIt e) const { |
|
680 return source(e); |
|
681 } |
|
682 |
|
683 /// \brief Base node of the iterator |
|
684 /// |
|
685 /// Returns the base node of the iterator |
|
686 Node baseNode(IncEdgeIt) const { |
|
687 return INVALID; |
|
688 } |
|
689 |
|
690 /// \brief Running node of the iterator |
|
691 /// |
|
692 /// Returns the running node of the iterator |
|
693 Node runningNode(IncEdgeIt) const { |
|
694 return INVALID; |
|
695 } |
|
696 |
|
697 template <typename Graph> |
|
698 struct Constraints { |
|
699 void constraints() { |
|
700 checkConcept<IterableUGraphComponent<>, Graph>(); |
|
701 checkConcept<MappableUGraphComponent<>, Graph>(); |
|
702 } |
|
703 }; |
|
704 |
|
705 }; |
|
706 |
|
707 /// @} |
|
708 |
|
709 } |
|
710 |
|
711 } |
|
712 |
|
713 #endif |