1 /* -*- C++ -*- |
|
2 * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, 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 graph_concepts |
|
18 ///\file |
|
19 ///\brief The graph components. |
|
20 |
|
21 |
|
22 #ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H |
|
23 #define LEMON_CONCEPT_GRAPH_COMPONENT_H |
|
24 |
|
25 #include <lemon/invalid.h> |
|
26 #include <lemon/concept/maps.h> |
|
27 |
|
28 #include <lemon/bits/alteration_notifier.h> |
|
29 |
|
30 namespace lemon { |
|
31 namespace concept { |
|
32 |
|
33 /// \addtogroup graph_concepts |
|
34 /// @{ |
|
35 |
|
36 /**************** Graph iterator concepts ****************/ |
|
37 |
|
38 /// Skeleton class for graph Node and Edge types |
|
39 |
|
40 /// This class describes the interface of Node and Edge (and UndirEdge |
|
41 /// in undirected graphs) subtypes of graph types. |
|
42 /// |
|
43 /// \note This class is a template class so that we can use it to |
|
44 /// create graph skeleton classes. The reason for this is than Node |
|
45 /// and Edge types should \em not derive from the same base class. |
|
46 /// For Node you should instantiate it with character 'n' and for Edge |
|
47 /// with 'e'. |
|
48 |
|
49 #ifndef DOXYGEN |
|
50 template <char _selector = '0'> |
|
51 #endif |
|
52 class GraphItem { |
|
53 public: |
|
54 /// Default constructor. |
|
55 |
|
56 /// \warning The default constructor is not required to set |
|
57 /// the item to some well-defined value. So you should consider it |
|
58 /// as uninitialized. |
|
59 GraphItem() {} |
|
60 /// Copy constructor. |
|
61 |
|
62 /// Copy constructor. |
|
63 /// |
|
64 GraphItem(GraphItem const&) {} |
|
65 /// Invalid constructor \& conversion. |
|
66 |
|
67 /// This constructor initializes the item to be invalid. |
|
68 /// \sa Invalid for more details. |
|
69 GraphItem(Invalid) {} |
|
70 /// Assign operator for nodes. |
|
71 |
|
72 /// The nodes are assignable. |
|
73 /// |
|
74 GraphItem& operator=(GraphItem const&) { return *this; } |
|
75 /// Equality operator. |
|
76 |
|
77 /// Two iterators are equal if and only if they represents the |
|
78 /// same node in the graph or both are invalid. |
|
79 bool operator==(GraphItem) const { return false; } |
|
80 /// Inequality operator. |
|
81 |
|
82 /// \sa operator==(const Node& n) |
|
83 /// |
|
84 bool operator!=(GraphItem) const { return false; } |
|
85 |
|
86 /// Artificial ordering operator. |
|
87 |
|
88 /// To allow the use of graph descriptors as key type in std::map or |
|
89 /// similar associative container we require this. |
|
90 /// |
|
91 /// \note This operator only have to define some strict ordering of |
|
92 /// the items; this order has nothing to do with the iteration |
|
93 /// ordering of the items. |
|
94 /// |
|
95 /// \bug This is a technical requirement. Do we really need this? |
|
96 bool operator<(GraphItem) const { return false; } |
|
97 |
|
98 template<typename _GraphItem> |
|
99 struct Constraints { |
|
100 void constraints() { |
|
101 _GraphItem i1; |
|
102 _GraphItem i2 = i1; |
|
103 _GraphItem i3 = INVALID; |
|
104 |
|
105 i1 = i2 = i3; |
|
106 |
|
107 bool b; |
|
108 // b = (ia == ib) && (ia != ib) && (ia < ib); |
|
109 b = (ia == ib) && (ia != ib); |
|
110 b = (ia == INVALID) && (ib != INVALID); |
|
111 // b = (ia < ib); |
|
112 } |
|
113 |
|
114 const _GraphItem &ia; |
|
115 const _GraphItem &ib; |
|
116 }; |
|
117 }; |
|
118 |
|
119 /// A type describing the concept of graph node |
|
120 |
|
121 /// This is an instantiation of \ref GraphItem which can be used as a |
|
122 /// Node subtype in graph skeleton definitions |
|
123 typedef GraphItem<'n'> GraphNode; |
|
124 |
|
125 /// A type describing the concept of graph edge |
|
126 |
|
127 /// This is an instantiation of \ref GraphItem which can be used as a |
|
128 /// Edge subtype in graph skeleton definitions |
|
129 typedef GraphItem<'e'> GraphEdge; |
|
130 |
|
131 |
|
132 /**************** Basic features of graphs ****************/ |
|
133 |
|
134 /// An empty base graph class. |
|
135 |
|
136 /// This class provides the minimal set of features needed for a graph |
|
137 /// structure. All graph concepts have to be conform to this base |
|
138 /// graph. |
|
139 /// |
|
140 /// \bug This is not true. The minimal graph concept is the |
|
141 /// BaseIterableGraphComponent. |
|
142 |
|
143 class BaseGraphComponent { |
|
144 public: |
|
145 |
|
146 typedef BaseGraphComponent Graph; |
|
147 |
|
148 /// Node class of the graph. |
|
149 |
|
150 /// This class represents the Nodes of the graph. |
|
151 /// |
|
152 typedef GraphItem<'n'> Node; |
|
153 |
|
154 /// Edge class of the graph. |
|
155 |
|
156 /// This class represents the Edges of the graph. |
|
157 /// |
|
158 typedef GraphItem<'e'> Edge; |
|
159 |
|
160 ///Gives back the target node of an edge. |
|
161 |
|
162 ///Gives back the target node of an edge. |
|
163 /// |
|
164 Node target(const Edge&) const { return INVALID;} |
|
165 |
|
166 ///Gives back the source node of an edge. |
|
167 |
|
168 ///Gives back the source node of an edge. |
|
169 /// |
|
170 Node source(const Edge&) const { return INVALID;} |
|
171 |
|
172 |
|
173 template <typename _Graph> |
|
174 struct Constraints { |
|
175 typedef typename _Graph::Node Node; |
|
176 typedef typename _Graph::Edge Edge; |
|
177 |
|
178 void constraints() { |
|
179 checkConcept<GraphItem<'n'>, Node>(); |
|
180 checkConcept<GraphItem<'e'>, Edge>(); |
|
181 { |
|
182 Node n; |
|
183 Edge e; |
|
184 n = graph.source(e); |
|
185 n = graph.target(e); |
|
186 } |
|
187 } |
|
188 |
|
189 const _Graph& graph; |
|
190 }; |
|
191 }; |
|
192 |
|
193 /// An empty iterable base graph class. |
|
194 |
|
195 /// This class provides beside the core graph features |
|
196 /// core iterable interface for the graph structure. |
|
197 /// Most of the base graphs should be conform to this concept. |
|
198 |
|
199 class BaseIterableGraphComponent : virtual public BaseGraphComponent { |
|
200 public: |
|
201 |
|
202 typedef BaseGraphComponent::Node Node; |
|
203 typedef BaseGraphComponent::Edge Edge; |
|
204 |
|
205 /// Gives back the first Node in the iterating order. |
|
206 |
|
207 /// Gives back the first Node in the iterating order. |
|
208 /// |
|
209 void first(Node&) const {} |
|
210 |
|
211 /// Gives back the next Node in the iterating order. |
|
212 |
|
213 /// Gives back the next Node in the iterating order. |
|
214 /// |
|
215 void next(Node&) const {} |
|
216 |
|
217 /// Gives back the first Edge in the iterating order. |
|
218 |
|
219 /// Gives back the first Edge in the iterating order. |
|
220 /// |
|
221 void first(Edge&) const {} |
|
222 /// Gives back the next Edge in the iterating order. |
|
223 |
|
224 /// Gives back the next Edge in the iterating order. |
|
225 /// |
|
226 void next(Edge&) const {} |
|
227 |
|
228 |
|
229 /// Gives back the first of the Edges point to the given Node. |
|
230 |
|
231 /// Gives back the first of the Edges point to the given Node. |
|
232 /// |
|
233 void firstIn(Edge&, const Node&) const {} |
|
234 |
|
235 /// Gives back the next of the Edges points to the given Node. |
|
236 |
|
237 |
|
238 /// Gives back the next of the Edges points to the given Node. |
|
239 /// |
|
240 void nextIn(Edge&) const {} |
|
241 |
|
242 /// Gives back the first of the Edges start from the given Node. |
|
243 |
|
244 /// Gives back the first of the Edges start from the given Node. |
|
245 /// |
|
246 void firstOut(Edge&, const Node&) const {} |
|
247 |
|
248 /// Gives back the next of the Edges start from the given Node. |
|
249 |
|
250 /// Gives back the next of the Edges start from the given Node. |
|
251 /// |
|
252 void nextOut(Edge&) const {} |
|
253 |
|
254 |
|
255 template <typename _Graph> |
|
256 struct Constraints { |
|
257 |
|
258 void constraints() { |
|
259 checkConcept< BaseGraphComponent, _Graph >(); |
|
260 typename _Graph::Node node; |
|
261 typename _Graph::Edge edge; |
|
262 { |
|
263 graph.first(node); |
|
264 graph.next(node); |
|
265 } |
|
266 { |
|
267 graph.first(edge); |
|
268 graph.next(edge); |
|
269 } |
|
270 { |
|
271 graph.firstIn(edge, node); |
|
272 graph.nextIn(edge); |
|
273 } |
|
274 { |
|
275 graph.firstOut(edge, node); |
|
276 graph.nextOut(edge); |
|
277 } |
|
278 } |
|
279 |
|
280 const _Graph& graph; |
|
281 }; |
|
282 }; |
|
283 |
|
284 /// An empty idable base graph class. |
|
285 |
|
286 /// This class provides beside the core graph features |
|
287 /// core id functions for the graph structure. |
|
288 /// The most of the base graphs should be conform to this concept. |
|
289 /// The id's are unique and immutable. |
|
290 class IDableGraphComponent : virtual public BaseGraphComponent { |
|
291 public: |
|
292 |
|
293 typedef BaseGraphComponent::Node Node; |
|
294 typedef BaseGraphComponent::Edge Edge; |
|
295 |
|
296 /// Gives back an unique integer id for the Node. |
|
297 |
|
298 /// Gives back an unique integer id for the Node. |
|
299 /// |
|
300 int id(const Node&) const { return -1;} |
|
301 |
|
302 /// \brief Gives back the node by the unique id. |
|
303 /// |
|
304 /// Gives back the node by the unique id. |
|
305 /// If the graph does not contain node with the given id |
|
306 /// then the result of the function is undetermined. |
|
307 Node fromId(int , Node) const { return INVALID;} |
|
308 |
|
309 /// \brief Gives back an unique integer id for the Edge. |
|
310 /// |
|
311 /// Gives back an unique integer id for the Edge. |
|
312 /// |
|
313 int id(const Edge&) const { return -1;} |
|
314 |
|
315 /// \brief Gives back the edge by the unique id. |
|
316 /// |
|
317 /// Gives back the edge by the unique id. |
|
318 /// If the graph does not contain edge with the given id |
|
319 /// then the result of the function is undetermined. |
|
320 Edge fromId(int, Edge) const { return INVALID;} |
|
321 |
|
322 template <typename _Graph> |
|
323 struct Constraints { |
|
324 |
|
325 void constraints() { |
|
326 checkConcept< BaseGraphComponent, _Graph >(); |
|
327 typename _Graph::Node node; |
|
328 int nid = graph.id(node); |
|
329 nid = graph.id(node); |
|
330 node = graph.fromId(nid, Node()); |
|
331 typename _Graph::Edge edge; |
|
332 int eid = graph.id(edge); |
|
333 eid = graph.id(edge); |
|
334 edge = graph.fromId(eid, Edge()); |
|
335 } |
|
336 |
|
337 const _Graph& graph; |
|
338 }; |
|
339 }; |
|
340 |
|
341 |
|
342 /// An empty max-idable base graph class. |
|
343 |
|
344 /// This class provides beside the core graph features |
|
345 /// core max id functions for the graph structure. |
|
346 /// The most of the base graphs should be conform to this concept. |
|
347 /// The id's are unique and immutable. |
|
348 class MaxIDableGraphComponent : virtual public BaseGraphComponent { |
|
349 public: |
|
350 |
|
351 /// Gives back an integer greater or equal to the maximum Node id. |
|
352 |
|
353 /// Gives back an integer greater or equal to the maximum Node id. |
|
354 /// |
|
355 int maxId(Node = INVALID) const { return -1;} |
|
356 |
|
357 /// Gives back an integer greater or equal to the maximum Edge id. |
|
358 |
|
359 /// Gives back an integer greater or equal to the maximum Edge id. |
|
360 /// |
|
361 int maxId(Edge = INVALID) const { return -1;} |
|
362 |
|
363 template <typename _Graph> |
|
364 struct Constraints { |
|
365 |
|
366 void constraints() { |
|
367 checkConcept<BaseGraphComponent, _Graph>(); |
|
368 int nid = graph.maxId(typename _Graph::Node()); |
|
369 ignore_unused_variable_warning(nid); |
|
370 int eid = graph.maxId(typename _Graph::Edge()); |
|
371 ignore_unused_variable_warning(eid); |
|
372 } |
|
373 |
|
374 const _Graph& graph; |
|
375 }; |
|
376 }; |
|
377 |
|
378 /// An empty extendable base graph class. |
|
379 |
|
380 /// This class provides beside the core graph features |
|
381 /// core graph extend interface for the graph structure. |
|
382 /// The most of the base graphs should be conform to this concept. |
|
383 class BaseExtendableGraphComponent : virtual public BaseGraphComponent { |
|
384 public: |
|
385 |
|
386 typedef BaseGraphComponent::Node Node; |
|
387 typedef BaseGraphComponent::Edge Edge; |
|
388 |
|
389 /// Adds a new Node to the graph. |
|
390 |
|
391 /// Adds a new Node to the graph. |
|
392 /// |
|
393 Node addNode() { |
|
394 return INVALID; |
|
395 } |
|
396 |
|
397 /// Adds a new Edge connects the two Nodes to the graph. |
|
398 |
|
399 /// Adds a new Edge connects the two Nodes to the graph. |
|
400 /// |
|
401 Edge addEdge(const Node&, const Node&) { |
|
402 return INVALID; |
|
403 } |
|
404 |
|
405 template <typename _Graph> |
|
406 struct Constraints { |
|
407 void constraints() { |
|
408 checkConcept<BaseGraphComponent, _Graph >(); |
|
409 typename _Graph::Node node_a, node_b; |
|
410 node_a = graph.addNode(); |
|
411 typename _Graph::Edge edge; |
|
412 edge = graph.addEdge(node_a, node_b); |
|
413 } |
|
414 |
|
415 _Graph& graph; |
|
416 }; |
|
417 }; |
|
418 |
|
419 /// An empty erasable base graph class. |
|
420 |
|
421 /// This class provides beside the core graph features |
|
422 /// core erase functions for the graph structure. |
|
423 /// The most of the base graphs should be conform to this concept. |
|
424 class BaseErasableGraphComponent : virtual public BaseGraphComponent { |
|
425 public: |
|
426 |
|
427 typedef BaseGraphComponent::Node Node; |
|
428 typedef BaseGraphComponent::Edge Edge; |
|
429 |
|
430 /// Erase a Node from the graph. |
|
431 |
|
432 /// Erase a Node from the graph. This function should not |
|
433 /// erase edges connecting to the Node. |
|
434 void erase(const Node&) {} |
|
435 |
|
436 /// Erase an Edge from the graph. |
|
437 |
|
438 /// Erase an Edge from the graph. |
|
439 /// |
|
440 void erase(const Edge&) {} |
|
441 |
|
442 template <typename _Graph> |
|
443 struct Constraints { |
|
444 void constraints() { |
|
445 checkConcept<BaseGraphComponent, _Graph>(); |
|
446 typename _Graph::Node node; |
|
447 graph.erase(node); |
|
448 typename _Graph::Edge edge; |
|
449 graph.erase(edge); |
|
450 } |
|
451 |
|
452 _Graph& graph; |
|
453 }; |
|
454 }; |
|
455 |
|
456 /// An empty clearable base graph class. |
|
457 |
|
458 /// This class provides beside the core graph features |
|
459 /// core clear functions for the graph structure. |
|
460 /// The most of the base graphs should be conform to this concept. |
|
461 class ClearableGraphComponent : virtual public BaseGraphComponent { |
|
462 public: |
|
463 |
|
464 /// Erase all the Nodes and Edges from the graph. |
|
465 |
|
466 /// Erase all the Nodes and Edges from the graph. |
|
467 /// |
|
468 void clear() {} |
|
469 |
|
470 template <typename _Graph> |
|
471 struct Constraints { |
|
472 void constraints() { |
|
473 checkConcept<BaseGraphComponent, _Graph>(); |
|
474 graph.clear(); |
|
475 } |
|
476 |
|
477 _Graph graph; |
|
478 }; |
|
479 }; |
|
480 |
|
481 |
|
482 /// Skeleton class for graph NodeIt and EdgeIt |
|
483 |
|
484 /// Skeleton class for graph NodeIt and EdgeIt. |
|
485 /// |
|
486 template <typename _Graph, typename _Item> |
|
487 class GraphIterator : public _Item { |
|
488 public: |
|
489 /// \todo Don't we need the Item type as typedef? |
|
490 |
|
491 /// Default constructor. |
|
492 |
|
493 /// @warning The default constructor sets the iterator |
|
494 /// to an undefined value. |
|
495 GraphIterator() {} |
|
496 /// Copy constructor. |
|
497 |
|
498 /// Copy constructor. |
|
499 /// |
|
500 GraphIterator(GraphIterator const&) {} |
|
501 /// Sets the iterator to the first item. |
|
502 |
|
503 /// Sets the iterator to the first item of \c the graph. |
|
504 /// |
|
505 explicit GraphIterator(const _Graph&) {} |
|
506 /// Invalid constructor \& conversion. |
|
507 |
|
508 /// This constructor initializes the item to be invalid. |
|
509 /// \sa Invalid for more details. |
|
510 GraphIterator(Invalid) {} |
|
511 /// Assign operator for items. |
|
512 |
|
513 /// The items are assignable. |
|
514 /// |
|
515 GraphIterator& operator=(GraphIterator const&) { return *this; } |
|
516 /// Next item. |
|
517 |
|
518 /// Assign the iterator to the next item. |
|
519 /// |
|
520 GraphIterator& operator++() { return *this; } |
|
521 // Node operator*() const { return INVALID; } |
|
522 /// Equality operator |
|
523 |
|
524 /// Two iterators are equal if and only if they point to the |
|
525 /// same object or both are invalid. |
|
526 bool operator==(const GraphIterator&) const { return true;} |
|
527 /// Inequality operator |
|
528 |
|
529 /// \sa operator==(Node n) |
|
530 /// |
|
531 bool operator!=(const GraphIterator&) const { return true;} |
|
532 |
|
533 template<typename _GraphIterator> |
|
534 struct Constraints { |
|
535 void constraints() { |
|
536 // checkConcept< Item, _GraphIterator >(); |
|
537 _GraphIterator it1(g); |
|
538 |
|
539 /// \todo Do we need NodeIt(Node) kind of constructor? |
|
540 // _GraphIterator it2(bj); |
|
541 _GraphIterator it2; |
|
542 |
|
543 it2 = ++it1; |
|
544 ++it2 = it1; |
|
545 ++(++it1); |
|
546 /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator> |
|
547 _Item bi = it1; |
|
548 bi = it2; |
|
549 } |
|
550 _Graph& g; |
|
551 }; |
|
552 }; |
|
553 |
|
554 /// Skeleton class for graph InEdgeIt and OutEdgeIt |
|
555 |
|
556 /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same |
|
557 /// base class, the _selector is a additional template parameter. For |
|
558 /// InEdgeIt you should instantiate it with character 'i' and for |
|
559 /// OutEdgeIt with 'o'. |
|
560 /// \todo Is this a good name for this concept? |
|
561 template <typename Graph, |
|
562 typename Edge = typename Graph::Edge, |
|
563 char _selector = '0'> |
|
564 class GraphIncIterator : public Edge { |
|
565 public: |
|
566 /// Default constructor. |
|
567 |
|
568 /// @warning The default constructor sets the iterator |
|
569 /// to an undefined value. |
|
570 GraphIncIterator() {} |
|
571 /// Copy constructor. |
|
572 |
|
573 /// Copy constructor. |
|
574 /// |
|
575 GraphIncIterator(GraphIncIterator const& gi) :Edge(gi) {} |
|
576 /// Sets the iterator to the first edge incoming into or outgoing |
|
577 /// from the node. |
|
578 |
|
579 /// Sets the iterator to the first edge incoming into or outgoing |
|
580 /// from the node. |
|
581 /// |
|
582 explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {} |
|
583 /// Invalid constructor \& conversion. |
|
584 |
|
585 /// This constructor initializes the item to be invalid. |
|
586 /// \sa Invalid for more details. |
|
587 GraphIncIterator(Invalid) {} |
|
588 /// Assign operator for nodes. |
|
589 |
|
590 /// The nodes are assignable. |
|
591 /// |
|
592 GraphIncIterator& operator=(GraphIncIterator const&) { return *this; } |
|
593 /// Next edge. |
|
594 |
|
595 /// Assign the iterator to the next node. |
|
596 /// |
|
597 GraphIncIterator& operator++() { return *this; } |
|
598 |
|
599 // Node operator*() const { return INVALID; } |
|
600 |
|
601 /// Equality operator |
|
602 |
|
603 /// Two iterators are equal if and only if they point to the |
|
604 /// same object or both are invalid. |
|
605 bool operator==(const GraphIncIterator&) const { return true;} |
|
606 |
|
607 /// Inequality operator |
|
608 |
|
609 /// \sa operator==(Node n) |
|
610 /// |
|
611 bool operator!=(const GraphIncIterator&) const { return true;} |
|
612 |
|
613 template <typename _GraphIncIterator> |
|
614 struct Constraints { |
|
615 typedef typename Graph::Node Node; |
|
616 void constraints() { |
|
617 checkConcept<GraphItem<'e'>, _GraphIncIterator>(); |
|
618 _GraphIncIterator it1(graph, node); |
|
619 /// \todo Do we need OutEdgeIt(Edge) kind of constructor? |
|
620 // _GraphIncIterator it2(edge); |
|
621 _GraphIncIterator it2; |
|
622 |
|
623 it2 = ++it1; |
|
624 ++it2 = it1; |
|
625 ++(++it1); |
|
626 Edge e = it1; |
|
627 e = it2; |
|
628 |
|
629 const_constraits(); |
|
630 } |
|
631 |
|
632 void const_constraits() { |
|
633 Node n = graph.baseNode(it); |
|
634 n = graph.runningNode(it); |
|
635 } |
|
636 |
|
637 Edge edge; |
|
638 Node node; |
|
639 Graph graph; |
|
640 _GraphIncIterator it; |
|
641 }; |
|
642 }; |
|
643 |
|
644 |
|
645 /// An empty iterable base graph class. |
|
646 |
|
647 /// This class provides beside the core graph features |
|
648 /// iterator based iterable interface for the graph structure. |
|
649 /// This concept is part of the StaticGraphConcept. |
|
650 class IterableGraphComponent : virtual public BaseGraphComponent { |
|
651 |
|
652 public: |
|
653 |
|
654 typedef IterableGraphComponent Graph; |
|
655 |
|
656 typedef BaseGraphComponent::Node Node; |
|
657 typedef BaseGraphComponent::Edge Edge; |
|
658 |
|
659 /// This iterator goes through each node. |
|
660 |
|
661 /// This iterator goes through each node. |
|
662 /// |
|
663 typedef GraphIterator<Graph, Node> NodeIt; |
|
664 /// This iterator goes through each node. |
|
665 |
|
666 /// This iterator goes through each node. |
|
667 /// |
|
668 typedef GraphIterator<Graph, Edge> EdgeIt; |
|
669 /// This iterator goes trough the incoming edges of a node. |
|
670 |
|
671 /// This iterator goes trough the \e inccoming edges of a certain node |
|
672 /// of a graph. |
|
673 typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt; |
|
674 /// This iterator goes trough the outgoing edges of a node. |
|
675 |
|
676 /// This iterator goes trough the \e outgoing edges of a certain node |
|
677 /// of a graph. |
|
678 typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt; |
|
679 }; |
|
680 |
|
681 template <typename _Graph> |
|
682 struct Constraints { |
|
683 void constraints() { |
|
684 checkConcept< BaseGraphComponent, _Graph>(); |
|
685 |
|
686 checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, |
|
687 typename _Graph::EdgeIt >(); |
|
688 checkConcept<GraphIterator<_Graph, typename _Graph::Node>, |
|
689 typename _Graph::NodeIt >(); |
|
690 checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >(); |
|
691 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >(); |
|
692 } |
|
693 }; |
|
694 |
|
695 /// An empty alteration notifier base graph class. |
|
696 |
|
697 /// This class provides beside the core graph features |
|
698 /// alteration notifier interface for the graph structure. |
|
699 /// This is an observer-notifier pattern. More Obsevers can |
|
700 /// be registered into the notifier and whenever an alteration |
|
701 /// occured in the graph all the observers will notified about it. |
|
702 class AlterableGraphComponent : virtual public BaseGraphComponent { |
|
703 public: |
|
704 |
|
705 /// The edge observer registry. |
|
706 typedef AlterationNotifier<Edge> EdgeNotifier; |
|
707 /// The node observer registry. |
|
708 typedef AlterationNotifier<Node> NodeNotifier; |
|
709 |
|
710 /// \brief Gives back the edge alteration notifier. |
|
711 /// |
|
712 /// Gives back the edge alteration notifier. |
|
713 EdgeNotifier getNotifier(Edge) const { |
|
714 return EdgeNotifier(); |
|
715 } |
|
716 |
|
717 /// \brief Gives back the node alteration notifier. |
|
718 /// |
|
719 /// Gives back the node alteration notifier. |
|
720 NodeNotifier getNotifier(Node) const { |
|
721 return NodeNotifier(); |
|
722 } |
|
723 |
|
724 }; |
|
725 |
|
726 |
|
727 /// Class describing the concept of graph maps |
|
728 |
|
729 /// This class describes the common interface of the graph maps |
|
730 /// (NodeMap, EdgeMap), that is \ref maps-pages "maps" which can be used to |
|
731 /// associate data to graph descriptors (nodes or edges). |
|
732 template <typename Graph, typename Item, typename _Value> |
|
733 class GraphMap : public ReadWriteMap<Item, _Value> { |
|
734 protected: |
|
735 GraphMap() {} |
|
736 public: |
|
737 /// \brief Construct a new map. |
|
738 /// |
|
739 /// Construct a new map for the graph. |
|
740 explicit GraphMap(const Graph&) {} |
|
741 /// \brief Construct a new map with default value. |
|
742 /// |
|
743 /// Construct a new map for the graph and initalise the values. |
|
744 GraphMap(const Graph&, const _Value&) {} |
|
745 /// \brief Copy constructor. |
|
746 /// |
|
747 /// Copy Constructor. |
|
748 GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {} |
|
749 |
|
750 /// \brief Assign operator. |
|
751 /// |
|
752 /// Assign operator. |
|
753 GraphMap& operator=(const GraphMap&) { return *this;} |
|
754 |
|
755 template<typename _Map> |
|
756 struct Constraints { |
|
757 void constraints() { |
|
758 checkConcept<ReadWriteMap<Item, _Value>, _Map >(); |
|
759 // Construction with a graph parameter |
|
760 _Map a(g); |
|
761 // Constructor with a graph and a default value parameter |
|
762 _Map a2(g,t); |
|
763 // Copy constructor. Do we need it? |
|
764 _Map b=c; |
|
765 // Copy operator. Do we need it? |
|
766 a=b; |
|
767 |
|
768 ignore_unused_variable_warning(a2); |
|
769 } |
|
770 |
|
771 const _Map &c; |
|
772 const Graph &g; |
|
773 const typename GraphMap::Value &t; |
|
774 }; |
|
775 |
|
776 }; |
|
777 |
|
778 /// An empty mappable base graph class. |
|
779 |
|
780 /// This class provides beside the core graph features |
|
781 /// map interface for the graph structure. |
|
782 /// This concept is part of the StaticGraphConcept. |
|
783 class MappableGraphComponent : virtual public BaseGraphComponent { |
|
784 public: |
|
785 |
|
786 typedef MappableGraphComponent Graph; |
|
787 |
|
788 typedef BaseGraphComponent::Node Node; |
|
789 typedef BaseGraphComponent::Edge Edge; |
|
790 |
|
791 /// ReadWrite map of the nodes. |
|
792 |
|
793 /// ReadWrite map of the nodes. |
|
794 /// |
|
795 template <typename _Value> |
|
796 class NodeMap : public GraphMap<Graph, Node, _Value> { |
|
797 private: |
|
798 NodeMap(); |
|
799 public: |
|
800 /// \brief Construct a new map. |
|
801 /// |
|
802 /// Construct a new map for the graph. |
|
803 /// \todo call the right parent class constructor |
|
804 explicit NodeMap(const Graph&) {} |
|
805 /// \brief Construct a new map with default value. |
|
806 /// |
|
807 /// Construct a new map for the graph and initalise the values. |
|
808 NodeMap(const Graph&, const _Value&) {} |
|
809 /// \brief Copy constructor. |
|
810 /// |
|
811 /// Copy Constructor. |
|
812 NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {} |
|
813 |
|
814 /// \brief Assign operator. |
|
815 /// |
|
816 /// Assign operator. |
|
817 NodeMap& operator=(const NodeMap&) { return *this;} |
|
818 |
|
819 }; |
|
820 |
|
821 /// ReadWrite map of the edges. |
|
822 |
|
823 /// ReadWrite map of the edges. |
|
824 /// |
|
825 template <typename _Value> |
|
826 class EdgeMap : public GraphMap<Graph, Edge, _Value> { |
|
827 private: |
|
828 EdgeMap(); |
|
829 public: |
|
830 /// \brief Construct a new map. |
|
831 /// |
|
832 /// Construct a new map for the graph. |
|
833 /// \todo call the right parent class constructor |
|
834 explicit EdgeMap(const Graph&) {} |
|
835 /// \brief Construct a new map with default value. |
|
836 /// |
|
837 /// Construct a new map for the graph and initalise the values. |
|
838 EdgeMap(const Graph&, const _Value&) {} |
|
839 /// \brief Copy constructor. |
|
840 /// |
|
841 /// Copy Constructor. |
|
842 EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {} |
|
843 |
|
844 /// \brief Assign operator. |
|
845 /// |
|
846 /// Assign operator. |
|
847 EdgeMap& operator=(const EdgeMap&) { return *this;} |
|
848 |
|
849 }; |
|
850 |
|
851 template <typename _Graph> |
|
852 struct Constraints { |
|
853 |
|
854 struct Type { |
|
855 int value; |
|
856 Type() : value(0) {} |
|
857 Type(int _v) : value(_v) {} |
|
858 }; |
|
859 |
|
860 void constraints() { |
|
861 checkConcept<BaseGraphComponent, _Graph>(); |
|
862 { // int map test |
|
863 typedef typename _Graph::template NodeMap<int> IntNodeMap; |
|
864 checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, |
|
865 IntNodeMap >(); |
|
866 } { // bool map test |
|
867 typedef typename _Graph::template NodeMap<bool> BoolNodeMap; |
|
868 checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, |
|
869 BoolNodeMap >(); |
|
870 } { // Type map test |
|
871 typedef typename _Graph::template NodeMap<Type> TypeNodeMap; |
|
872 checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, |
|
873 TypeNodeMap >(); |
|
874 } |
|
875 |
|
876 { // int map test |
|
877 typedef typename _Graph::template EdgeMap<int> IntEdgeMap; |
|
878 checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, |
|
879 IntEdgeMap >(); |
|
880 } { // bool map test |
|
881 typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap; |
|
882 checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, |
|
883 BoolEdgeMap >(); |
|
884 } { // Type map test |
|
885 typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap; |
|
886 checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, |
|
887 TypeEdgeMap >(); |
|
888 } |
|
889 } |
|
890 |
|
891 _Graph& graph; |
|
892 }; |
|
893 }; |
|
894 |
|
895 /// \brief An empty extendable extended graph class. |
|
896 /// |
|
897 /// This class provides beside the core graph features |
|
898 /// item addition interface for the graph structure. |
|
899 /// The difference between this class and the |
|
900 /// \c BaseExtendableGraphComponent is that it should |
|
901 /// notify the item alteration observers. |
|
902 class ExtendableGraphComponent : virtual public BaseGraphComponent { |
|
903 public: |
|
904 |
|
905 typedef ExtendableGraphComponent Graph; |
|
906 |
|
907 typedef BaseGraphComponent::Node Node; |
|
908 typedef BaseGraphComponent::Edge Edge; |
|
909 |
|
910 /// \brief Add a node to the graph. |
|
911 /// |
|
912 /// Add a node to the graph and notify the observers. |
|
913 Node addNode() { |
|
914 return INVALID; |
|
915 } |
|
916 |
|
917 /// \brief Add an edge to the graph. |
|
918 /// |
|
919 /// Add an edge to the graph and notify the observers. |
|
920 Edge addEdge(const Node&, const Node&) { |
|
921 return INVALID; |
|
922 } |
|
923 |
|
924 template <typename _Graph> |
|
925 struct Constraints { |
|
926 void constraints() { |
|
927 checkConcept<BaseGraphComponent, _Graph >(); |
|
928 typename _Graph::Node node_a, node_b; |
|
929 node_a = graph.addNode(); |
|
930 typename _Graph::Edge edge; |
|
931 edge = graph.addEdge(node_a, node_b); |
|
932 } |
|
933 _Graph& graph; |
|
934 }; |
|
935 }; |
|
936 |
|
937 /// \brief An empty erasable extended graph class. |
|
938 /// |
|
939 /// This class provides beside the core graph features |
|
940 /// item erase interface for the graph structure. |
|
941 /// The difference between this class and the |
|
942 /// \c BaseErasableGraphComponent is that it should |
|
943 /// notify the item alteration observers. |
|
944 class ErasableGraphComponent : virtual public BaseGraphComponent { |
|
945 public: |
|
946 |
|
947 typedef ErasableGraphComponent Graph; |
|
948 |
|
949 typedef BaseGraphComponent::Node Node; |
|
950 typedef BaseGraphComponent::Edge Edge; |
|
951 |
|
952 /// \brief Erase the Node and notify the node alteration observers. |
|
953 /// |
|
954 /// Erase the Node and notify the node alteration observers. |
|
955 void erase(const Node&) {} |
|
956 |
|
957 /// \brief Erase the Edge and notify the edge alteration observers. |
|
958 /// |
|
959 /// Erase the Edge and notify the edge alteration observers. |
|
960 void erase(const Edge&) {} |
|
961 |
|
962 template <typename _Graph> |
|
963 struct Constraints { |
|
964 void constraints() { |
|
965 checkConcept<BaseGraphComponent, _Graph >(); |
|
966 typename _Graph::Node node; |
|
967 graph.erase(node); |
|
968 typename _Graph::Edge edge; |
|
969 graph.erase(edge); |
|
970 } |
|
971 |
|
972 _Graph& graph; |
|
973 }; |
|
974 }; |
|
975 |
|
976 /// @} |
|
977 |
|
978 } |
|
979 |
|
980 } |
|
981 |
|
982 #endif |
|