Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
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 concepts of graph components.
22 : :
23 : : #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
24 : : #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
25 : :
26 : : #include <lemon/core.h>
27 : : #include <lemon/concepts/maps.h>
28 : :
29 : : #include <lemon/bits/alteration_notifier.h>
30 : :
31 : : namespace lemon {
32 : : namespace concepts {
33 : :
34 : : /// \brief Concept class for \c Node, \c Arc and \c Edge types.
35 : : ///
36 : : /// This class describes the concept of \c Node, \c Arc and \c Edge
37 : : /// subtypes of digraph and graph types.
38 : : ///
39 : : /// \note This class is a template class so that we can use it to
40 : : /// create graph skeleton classes. The reason for this is that \c Node
41 : : /// and \c Arc (or \c Edge) types should \e not derive from the same
42 : : /// base class. For \c Node you should instantiate it with character
43 : : /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
44 : : #ifndef DOXYGEN
45 : : template <char sel = '0'>
46 : : #endif
47 : : class GraphItem {
48 : : public:
49 : : /// \brief Default constructor.
50 : : ///
51 : : /// Default constructor.
52 : : /// \warning The default constructor is not required to set
53 : : /// the item to some well-defined value. So you should consider it
54 : : /// as uninitialized.
55 : : GraphItem() {}
56 : :
57 : : /// \brief Copy constructor.
58 : : ///
59 : : /// Copy constructor.
60 : : GraphItem(const GraphItem &) {}
61 : :
62 : : /// \brief Constructor for conversion from \c INVALID.
63 : : ///
64 : : /// Constructor for conversion from \c INVALID.
65 : : /// It initializes the item to be invalid.
66 : : /// \sa Invalid for more details.
67 : : GraphItem(Invalid) {}
68 : :
69 : : /// \brief Assignment operator.
70 : : ///
71 : : /// Assignment operator for the item.
72 : : GraphItem& operator=(const GraphItem&) { return *this; }
73 : :
74 : : /// \brief Assignment operator for INVALID.
75 : : ///
76 : : /// This operator makes the item invalid.
77 : : GraphItem& operator=(Invalid) { return *this; }
78 : :
79 : : /// \brief Equality operator.
80 : : ///
81 : : /// Equality operator.
82 : : bool operator==(const GraphItem&) const { return false; }
83 : :
84 : : /// \brief Inequality operator.
85 : : ///
86 : : /// Inequality operator.
87 : : bool operator!=(const GraphItem&) const { return false; }
88 : :
89 : : /// \brief Ordering operator.
90 : : ///
91 : : /// This operator defines an ordering of the items.
92 : : /// It makes possible to use graph item types as key types in
93 : : /// associative containers (e.g. \c std::map).
94 : : ///
95 : : /// \note This operator only has to define some strict ordering of
96 : : /// the items; this order has nothing to do with the iteration
97 : : /// ordering of the items.
98 : : bool operator<(const GraphItem&) const { return false; }
99 : :
100 : : template<typename _GraphItem>
101 : : struct Constraints {
102 : 0 : void constraints() {
103 [ # # ][ # # ]: 0 : _GraphItem i1;
[ # # ][ # # ]
[ # # ][ # # ]
104 [ # # ][ # # ]: 0 : i1=INVALID;
[ # # ][ # # ]
[ # # ][ # # ]
105 : 0 : _GraphItem i2 = i1;
106 [ # # ][ # # ]: 0 : _GraphItem i3 = INVALID;
[ # # ][ # # ]
[ # # ][ # # ]
107 : :
108 : 0 : i1 = i2 = i3;
109 : :
110 : 0 : }
111 : :
112 : : const _GraphItem &ia;
113 : : const _GraphItem &ib;
114 : : };
115 : : };
116 : :
117 : : /// \brief Base skeleton class for directed graphs.
118 : : ///
119 : : /// This class describes the base interface of directed graph types.
120 : : /// All digraph %concepts have to conform to this class.
121 : : /// It just provides types for nodes and arcs and functions
122 : : /// to get the source and the target nodes of arcs.
123 : : class BaseDigraphComponent {
124 : : public:
125 : :
126 : : typedef BaseDigraphComponent Digraph;
127 : :
128 : : /// \brief Node class of the digraph.
129 : : ///
130 : : /// This class represents the nodes of the digraph.
131 : : typedef GraphItem<'n'> Node;
132 : :
133 : : /// \brief Arc class of the digraph.
134 : : ///
135 : : /// This class represents the arcs of the digraph.
136 : : typedef GraphItem<'a'> Arc;
137 : :
138 : : /// \brief Return the source node of an arc.
139 : : ///
140 : : /// This function returns the source node of an arc.
141 : : Node source(const Arc&) const { return INVALID; }
142 : :
143 : : /// \brief Return the target node of an arc.
144 : : ///
145 : : /// This function returns the target node of an arc.
146 : : Node target(const Arc&) const { return INVALID; }
147 : :
148 : : /// \brief Return the opposite node on the given arc.
149 : : ///
150 : : /// This function returns the opposite node on the given arc.
151 : : Node oppositeNode(const Node&, const Arc&) const {
152 : : return INVALID;
153 : : }
154 : :
155 : : template <typename _Digraph>
156 : : struct Constraints {
157 : : typedef typename _Digraph::Node Node;
158 : : typedef typename _Digraph::Arc Arc;
159 : :
160 : 0 : void constraints() {
161 : 0 : checkConcept<GraphItem<'n'>, Node>();
162 : 0 : checkConcept<GraphItem<'a'>, Arc>();
163 : : {
164 [ # # ]: 0 : Node n;
165 [ # # ]: 0 : Arc e(INVALID);
166 [ # # ]: 0 : n = digraph.source(e);
167 [ # # ]: 0 : n = digraph.target(e);
168 [ # # ]: 0 : n = digraph.oppositeNode(n, e);
169 : : }
170 : 0 : }
171 : :
172 : : const _Digraph& digraph;
173 : : };
174 : : };
175 : :
176 : : /// \brief Base skeleton class for undirected graphs.
177 : : ///
178 : : /// This class describes the base interface of undirected graph types.
179 : : /// All graph %concepts have to conform to this class.
180 : : /// It extends the interface of \ref BaseDigraphComponent with an
181 : : /// \c Edge type and functions to get the end nodes of edges,
182 : : /// to convert from arcs to edges and to get both direction of edges.
183 : : class BaseGraphComponent : public BaseDigraphComponent {
184 : : public:
185 : :
186 : : typedef BaseGraphComponent Graph;
187 : :
188 : : typedef BaseDigraphComponent::Node Node;
189 : : typedef BaseDigraphComponent::Arc Arc;
190 : :
191 : : /// \brief Undirected edge class of the graph.
192 : : ///
193 : : /// This class represents the undirected edges of the graph.
194 : : /// Undirected graphs can be used as directed graphs, each edge is
195 : : /// represented by two opposite directed arcs.
196 : : class Edge : public GraphItem<'e'> {
197 : : typedef GraphItem<'e'> Parent;
198 : :
199 : : public:
200 : : /// \brief Default constructor.
201 : : ///
202 : : /// Default constructor.
203 : : /// \warning The default constructor is not required to set
204 : : /// the item to some well-defined value. So you should consider it
205 : : /// as uninitialized.
206 : : Edge() {}
207 : :
208 : : /// \brief Copy constructor.
209 : : ///
210 : : /// Copy constructor.
211 : : Edge(const Edge &) : Parent() {}
212 : :
213 : : /// \brief Constructor for conversion from \c INVALID.
214 : : ///
215 : : /// Constructor for conversion from \c INVALID.
216 : : /// It initializes the item to be invalid.
217 : : /// \sa Invalid for more details.
218 : : Edge(Invalid) {}
219 : :
220 : : /// \brief Constructor for conversion from an arc.
221 : : ///
222 : : /// Constructor for conversion from an arc.
223 : : /// Besides the core graph item functionality each arc should
224 : : /// be convertible to the represented edge.
225 : : Edge(const Arc&) {}
226 : : };
227 : :
228 : : /// \brief Return one end node of an edge.
229 : : ///
230 : : /// This function returns one end node of an edge.
231 : : Node u(const Edge&) const { return INVALID; }
232 : :
233 : : /// \brief Return the other end node of an edge.
234 : : ///
235 : : /// This function returns the other end node of an edge.
236 : : Node v(const Edge&) const { return INVALID; }
237 : :
238 : : /// \brief Return a directed arc related to an edge.
239 : : ///
240 : : /// This function returns a directed arc from its direction and the
241 : : /// represented edge.
242 : : Arc direct(const Edge&, bool) const { return INVALID; }
243 : :
244 : : /// \brief Return a directed arc related to an edge.
245 : : ///
246 : : /// This function returns a directed arc from its source node and the
247 : : /// represented edge.
248 : : Arc direct(const Edge&, const Node&) const { return INVALID; }
249 : :
250 : : /// \brief Return the direction of the arc.
251 : : ///
252 : : /// Returns the direction of the arc. Each arc represents an
253 : : /// edge with a direction. It gives back the
254 : : /// direction.
255 : : bool direction(const Arc&) const { return true; }
256 : :
257 : : /// \brief Return the opposite arc.
258 : : ///
259 : : /// This function returns the opposite arc, i.e. the arc representing
260 : : /// the same edge and has opposite direction.
261 : : Arc oppositeArc(const Arc&) const { return INVALID; }
262 : :
263 : : template <typename _Graph>
264 : : struct Constraints {
265 : : typedef typename _Graph::Node Node;
266 : : typedef typename _Graph::Arc Arc;
267 : : typedef typename _Graph::Edge Edge;
268 : :
269 : : void constraints() {
270 : : checkConcept<BaseDigraphComponent, _Graph>();
271 : : checkConcept<GraphItem<'e'>, Edge>();
272 : : {
273 : : Node n;
274 : : Edge ue(INVALID);
275 : : Arc e;
276 : : n = graph.u(ue);
277 : : n = graph.v(ue);
278 : : e = graph.direct(ue, true);
279 : : e = graph.direct(ue, false);
280 : : e = graph.direct(ue, n);
281 : : e = graph.oppositeArc(e);
282 : : ue = e;
283 : : bool d = graph.direction(e);
284 : : ignore_unused_variable_warning(d);
285 : : }
286 : : }
287 : :
288 : : const _Graph& graph;
289 : : };
290 : :
291 : : };
292 : :
293 : : /// \brief Skeleton class for \e idable directed graphs.
294 : : ///
295 : : /// This class describes the interface of \e idable directed graphs.
296 : : /// It extends \ref BaseDigraphComponent with the core ID functions.
297 : : /// The ids of the items must be unique and immutable.
298 : : /// This concept is part of the Digraph concept.
299 : : template <typename BAS = BaseDigraphComponent>
300 : : class IDableDigraphComponent : public BAS {
301 : : public:
302 : :
303 : : typedef BAS Base;
304 : : typedef typename Base::Node Node;
305 : : typedef typename Base::Arc Arc;
306 : :
307 : : /// \brief Return a unique integer id for the given node.
308 : : ///
309 : : /// This function returns a unique integer id for the given node.
310 : : int id(const Node&) const { return -1; }
311 : :
312 : : /// \brief Return the node by its unique id.
313 : : ///
314 : : /// This function returns the node by its unique id.
315 : : /// If the digraph does not contain a node with the given id,
316 : : /// then the result of the function is undefined.
317 : : Node nodeFromId(int) const { return INVALID; }
318 : :
319 : : /// \brief Return a unique integer id for the given arc.
320 : : ///
321 : : /// This function returns a unique integer id for the given arc.
322 : : int id(const Arc&) const { return -1; }
323 : :
324 : : /// \brief Return the arc by its unique id.
325 : : ///
326 : : /// This function returns the arc by its unique id.
327 : : /// If the digraph does not contain an arc with the given id,
328 : : /// then the result of the function is undefined.
329 : : Arc arcFromId(int) const { return INVALID; }
330 : :
331 : : /// \brief Return an integer greater or equal to the maximum
332 : : /// node id.
333 : : ///
334 : : /// This function returns an integer greater or equal to the
335 : : /// maximum node id.
336 : : int maxNodeId() const { return -1; }
337 : :
338 : : /// \brief Return an integer greater or equal to the maximum
339 : : /// arc id.
340 : : ///
341 : : /// This function returns an integer greater or equal to the
342 : : /// maximum arc id.
343 : : int maxArcId() const { return -1; }
344 : :
345 : : template <typename _Digraph>
346 : : struct Constraints {
347 : :
348 : 0 : void constraints() {
349 [ # # ]: 0 : checkConcept<Base, _Digraph >();
350 [ # # ]: 0 : typename _Digraph::Node node;
351 [ # # ]: 0 : node=INVALID;
352 [ # # ]: 0 : int nid = digraph.id(node);
353 [ # # ]: 0 : nid = digraph.id(node);
354 [ # # ]: 0 : node = digraph.nodeFromId(nid);
355 [ # # ]: 0 : typename _Digraph::Arc arc;
356 [ # # ]: 0 : arc=INVALID;
357 [ # # ]: 0 : int eid = digraph.id(arc);
358 [ # # ]: 0 : eid = digraph.id(arc);
359 [ # # ]: 0 : arc = digraph.arcFromId(eid);
360 : :
361 [ # # ]: 0 : nid = digraph.maxNodeId();
362 [ # # ]: 0 : ignore_unused_variable_warning(nid);
363 [ # # ]: 0 : eid = digraph.maxArcId();
364 [ # # ]: 0 : ignore_unused_variable_warning(eid);
365 : 0 : }
366 : :
367 : : const _Digraph& digraph;
368 : : };
369 : : };
370 : :
371 : : /// \brief Skeleton class for \e idable undirected graphs.
372 : : ///
373 : : /// This class describes the interface of \e idable undirected
374 : : /// graphs. It extends \ref IDableDigraphComponent with the core ID
375 : : /// functions of undirected graphs.
376 : : /// The ids of the items must be unique and immutable.
377 : : /// This concept is part of the Graph concept.
378 : : template <typename BAS = BaseGraphComponent>
379 : : class IDableGraphComponent : public IDableDigraphComponent<BAS> {
380 : : public:
381 : :
382 : : typedef BAS Base;
383 : : typedef typename Base::Edge Edge;
384 : :
385 : : using IDableDigraphComponent<Base>::id;
386 : :
387 : : /// \brief Return a unique integer id for the given edge.
388 : : ///
389 : : /// This function returns a unique integer id for the given edge.
390 : : int id(const Edge&) const { return -1; }
391 : :
392 : : /// \brief Return the edge by its unique id.
393 : : ///
394 : : /// This function returns the edge by its unique id.
395 : : /// If the graph does not contain an edge with the given id,
396 : : /// then the result of the function is undefined.
397 : : Edge edgeFromId(int) const { return INVALID; }
398 : :
399 : : /// \brief Return an integer greater or equal to the maximum
400 : : /// edge id.
401 : : ///
402 : : /// This function returns an integer greater or equal to the
403 : : /// maximum edge id.
404 : : int maxEdgeId() const { return -1; }
405 : :
406 : : template <typename _Graph>
407 : : struct Constraints {
408 : :
409 : : void constraints() {
410 : : checkConcept<IDableDigraphComponent<Base>, _Graph >();
411 : : typename _Graph::Edge edge;
412 : : int ueid = graph.id(edge);
413 : : ueid = graph.id(edge);
414 : : edge = graph.edgeFromId(ueid);
415 : : ueid = graph.maxEdgeId();
416 : : ignore_unused_variable_warning(ueid);
417 : : }
418 : :
419 : : const _Graph& graph;
420 : : };
421 : : };
422 : :
423 : : /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
424 : : ///
425 : : /// This class describes the concept of \c NodeIt, \c ArcIt and
426 : : /// \c EdgeIt subtypes of digraph and graph types.
427 : : template <typename GR, typename Item>
428 : : class GraphItemIt : public Item {
429 : : public:
430 : : /// \brief Default constructor.
431 : : ///
432 : : /// Default constructor.
433 : : /// \warning The default constructor is not required to set
434 : : /// the iterator to some well-defined value. So you should consider it
435 : : /// as uninitialized.
436 : : GraphItemIt() {}
437 : :
438 : : /// \brief Copy constructor.
439 : : ///
440 : : /// Copy constructor.
441 : : GraphItemIt(const GraphItemIt& it) : Item(it) {}
442 : :
443 : : /// \brief Constructor that sets the iterator to the first item.
444 : : ///
445 : : /// Constructor that sets the iterator to the first item.
446 : : explicit GraphItemIt(const GR&) {}
447 : :
448 : : /// \brief Constructor for conversion from \c INVALID.
449 : : ///
450 : : /// Constructor for conversion from \c INVALID.
451 : : /// It initializes the iterator to be invalid.
452 : : /// \sa Invalid for more details.
453 : : GraphItemIt(Invalid) {}
454 : :
455 : : /// \brief Assignment operator.
456 : : ///
457 : : /// Assignment operator for the iterator.
458 : : GraphItemIt& operator=(const GraphItemIt&) { return *this; }
459 : :
460 : : /// \brief Increment the iterator.
461 : : ///
462 : : /// This operator increments the iterator, i.e. assigns it to the
463 : : /// next item.
464 : : GraphItemIt& operator++() { return *this; }
465 : :
466 : : /// \brief Equality operator
467 : : ///
468 : : /// Equality operator.
469 : : /// Two iterators are equal if and only if they point to the
470 : : /// same object or both are invalid.
471 : : bool operator==(const GraphItemIt&) const { return true;}
472 : :
473 : : /// \brief Inequality operator
474 : : ///
475 : : /// Inequality operator.
476 : : /// Two iterators are equal if and only if they point to the
477 : : /// same object or both are invalid.
478 : : bool operator!=(const GraphItemIt&) const { return true;}
479 : :
480 : : template<typename _GraphItemIt>
481 : : struct Constraints {
482 : 0 : void constraints() {
483 [ # # ][ # # ]: 0 : checkConcept<GraphItem<>, _GraphItemIt>();
484 [ # # ][ # # ]: 0 : _GraphItemIt it1(g);
485 [ # # ][ # # ]: 0 : _GraphItemIt it2;
486 : :
487 [ # # ][ # # ]: 0 : it2 = ++it1;
488 [ # # ][ # # ]: 0 : ++it2 = it1;
489 [ # # ][ # # ]: 0 : ++(++it1);
[ # # ][ # # ]
490 : :
491 : 0 : Item bi = it1;
492 : 0 : bi = it2;
493 : 0 : }
494 : : const GR& g;
495 : : };
496 : : };
497 : :
498 : : /// \brief Concept class for \c InArcIt, \c OutArcIt and
499 : : /// \c IncEdgeIt types.
500 : : ///
501 : : /// This class describes the concept of \c InArcIt, \c OutArcIt
502 : : /// and \c IncEdgeIt subtypes of digraph and graph types.
503 : : ///
504 : : /// \note Since these iterator classes do not inherit from the same
505 : : /// base class, there is an additional template parameter (selector)
506 : : /// \c sel. For \c InArcIt you should instantiate it with character
507 : : /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
508 : : template <typename GR,
509 : : typename Item = typename GR::Arc,
510 : : typename Base = typename GR::Node,
511 : : char sel = '0'>
512 : : class GraphIncIt : public Item {
513 : : public:
514 : : /// \brief Default constructor.
515 : : ///
516 : : /// Default constructor.
517 : : /// \warning The default constructor is not required to set
518 : : /// the iterator to some well-defined value. So you should consider it
519 : : /// as uninitialized.
520 : : GraphIncIt() {}
521 : :
522 : : /// \brief Copy constructor.
523 : : ///
524 : : /// Copy constructor.
525 : : GraphIncIt(const GraphIncIt& it) : Item(it) {}
526 : :
527 : : /// \brief Constructor that sets the iterator to the first
528 : : /// incoming or outgoing arc.
529 : : ///
530 : : /// Constructor that sets the iterator to the first arc
531 : : /// incoming to or outgoing from the given node.
532 : : explicit GraphIncIt(const GR&, const Base&) {}
533 : :
534 : : /// \brief Constructor for conversion from \c INVALID.
535 : : ///
536 : : /// Constructor for conversion from \c INVALID.
537 : : /// It initializes the iterator to be invalid.
538 : : /// \sa Invalid for more details.
539 : : GraphIncIt(Invalid) {}
540 : :
541 : : /// \brief Assignment operator.
542 : : ///
543 : : /// Assignment operator for the iterator.
544 : : GraphIncIt& operator=(const GraphIncIt&) { return *this; }
545 : :
546 : : /// \brief Increment the iterator.
547 : : ///
548 : : /// This operator increments the iterator, i.e. assigns it to the
549 : : /// next arc incoming to or outgoing from the given node.
550 : : GraphIncIt& operator++() { return *this; }
551 : :
552 : : /// \brief Equality operator
553 : : ///
554 : : /// Equality operator.
555 : : /// Two iterators are equal if and only if they point to the
556 : : /// same object or both are invalid.
557 : : bool operator==(const GraphIncIt&) const { return true;}
558 : :
559 : : /// \brief Inequality operator
560 : : ///
561 : : /// Inequality operator.
562 : : /// Two iterators are equal if and only if they point to the
563 : : /// same object or both are invalid.
564 : : bool operator!=(const GraphIncIt&) const { return true;}
565 : :
566 : : template <typename _GraphIncIt>
567 : : struct Constraints {
568 : 0 : void constraints() {
569 [ # # ][ # # ]: 0 : checkConcept<GraphItem<sel>, _GraphIncIt>();
570 [ # # ][ # # ]: 0 : _GraphIncIt it1(graph, node);
571 [ # # ][ # # ]: 0 : _GraphIncIt it2;
572 : :
573 [ # # ][ # # ]: 0 : it2 = ++it1;
574 [ # # ][ # # ]: 0 : ++it2 = it1;
575 [ # # ][ # # ]: 0 : ++(++it1);
[ # # ][ # # ]
576 : 0 : Item e = it1;
577 : 0 : e = it2;
578 : 0 : }
579 : : const Base& node;
580 : : const GR& graph;
581 : : };
582 : : };
583 : :
584 : : /// \brief Skeleton class for iterable directed graphs.
585 : : ///
586 : : /// This class describes the interface of iterable directed
587 : : /// graphs. It extends \ref BaseDigraphComponent with the core
588 : : /// iterable interface.
589 : : /// This concept is part of the Digraph concept.
590 : : template <typename BAS = BaseDigraphComponent>
591 : : class IterableDigraphComponent : public BAS {
592 : :
593 : : public:
594 : :
595 : : typedef BAS Base;
596 : : typedef typename Base::Node Node;
597 : : typedef typename Base::Arc Arc;
598 : :
599 : : typedef IterableDigraphComponent Digraph;
600 : :
601 : : /// \name Base Iteration
602 : : ///
603 : : /// This interface provides functions for iteration on digraph items.
604 : : ///
605 : : /// @{
606 : :
607 : : /// \brief Return the first node.
608 : : ///
609 : : /// This function gives back the first node in the iteration order.
610 : : void first(Node&) const {}
611 : :
612 : : /// \brief Return the next node.
613 : : ///
614 : : /// This function gives back the next node in the iteration order.
615 : : void next(Node&) const {}
616 : :
617 : : /// \brief Return the first arc.
618 : : ///
619 : : /// This function gives back the first arc in the iteration order.
620 : : void first(Arc&) const {}
621 : :
622 : : /// \brief Return the next arc.
623 : : ///
624 : : /// This function gives back the next arc in the iteration order.
625 : : void next(Arc&) const {}
626 : :
627 : : /// \brief Return the first arc incomming to the given node.
628 : : ///
629 : : /// This function gives back the first arc incomming to the
630 : : /// given node.
631 : : void firstIn(Arc&, const Node&) const {}
632 : :
633 : : /// \brief Return the next arc incomming to the given node.
634 : : ///
635 : : /// This function gives back the next arc incomming to the
636 : : /// given node.
637 : : void nextIn(Arc&) const {}
638 : :
639 : : /// \brief Return the first arc outgoing form the given node.
640 : : ///
641 : : /// This function gives back the first arc outgoing form the
642 : : /// given node.
643 : : void firstOut(Arc&, const Node&) const {}
644 : :
645 : : /// \brief Return the next arc outgoing form the given node.
646 : : ///
647 : : /// This function gives back the next arc outgoing form the
648 : : /// given node.
649 : : void nextOut(Arc&) const {}
650 : :
651 : : /// @}
652 : :
653 : : /// \name Class Based Iteration
654 : : ///
655 : : /// This interface provides iterator classes for digraph items.
656 : : ///
657 : : /// @{
658 : :
659 : : /// \brief This iterator goes through each node.
660 : : ///
661 : : /// This iterator goes through each node.
662 : : ///
663 : : typedef GraphItemIt<Digraph, Node> NodeIt;
664 : :
665 : : /// \brief This iterator goes through each arc.
666 : : ///
667 : : /// This iterator goes through each arc.
668 : : ///
669 : : typedef GraphItemIt<Digraph, Arc> ArcIt;
670 : :
671 : : /// \brief This iterator goes trough the incoming arcs of a node.
672 : : ///
673 : : /// This iterator goes trough the \e incoming arcs of a certain node
674 : : /// of a digraph.
675 : : typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
676 : :
677 : : /// \brief This iterator goes trough the outgoing arcs of a node.
678 : : ///
679 : : /// This iterator goes trough the \e outgoing arcs of a certain node
680 : : /// of a digraph.
681 : : typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
682 : :
683 : : /// \brief The base node of the iterator.
684 : : ///
685 : : /// This function gives back the base node of the iterator.
686 : : /// It is always the target node of the pointed arc.
687 : : Node baseNode(const InArcIt&) const { return INVALID; }
688 : :
689 : : /// \brief The running node of the iterator.
690 : : ///
691 : : /// This function gives back the running node of the iterator.
692 : : /// It is always the source node of the pointed arc.
693 : : Node runningNode(const InArcIt&) const { return INVALID; }
694 : :
695 : : /// \brief The base node of the iterator.
696 : : ///
697 : : /// This function gives back the base node of the iterator.
698 : : /// It is always the source node of the pointed arc.
699 : : Node baseNode(const OutArcIt&) const { return INVALID; }
700 : :
701 : : /// \brief The running node of the iterator.
702 : : ///
703 : : /// This function gives back the running node of the iterator.
704 : : /// It is always the target node of the pointed arc.
705 : : Node runningNode(const OutArcIt&) const { return INVALID; }
706 : :
707 : : /// @}
708 : :
709 : : template <typename _Digraph>
710 : : struct Constraints {
711 : 0 : void constraints() {
712 : 0 : checkConcept<Base, _Digraph>();
713 : :
714 : : {
715 [ # # ]: 0 : typename _Digraph::Node node(INVALID);
716 [ # # ]: 0 : typename _Digraph::Arc arc(INVALID);
717 : : {
718 [ # # ]: 0 : digraph.first(node);
719 [ # # ]: 0 : digraph.next(node);
720 : : }
721 : : {
722 [ # # ]: 0 : digraph.first(arc);
723 [ # # ]: 0 : digraph.next(arc);
724 : : }
725 : : {
726 [ # # ]: 0 : digraph.firstIn(arc, node);
727 [ # # ]: 0 : digraph.nextIn(arc);
728 : : }
729 : : {
730 [ # # ]: 0 : digraph.firstOut(arc, node);
731 [ # # ]: 0 : digraph.nextOut(arc);
732 : : }
733 : : }
734 : :
735 : : {
736 [ # # ]: 0 : checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
737 : : typename _Digraph::ArcIt >();
738 [ # # ]: 0 : checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
739 : : typename _Digraph::NodeIt >();
740 [ # # ]: 0 : checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
741 : : typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
742 [ # # ]: 0 : checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
743 : : typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
744 : :
745 [ # # ]: 0 : typename _Digraph::Node n;
746 [ # # ]: 0 : const typename _Digraph::InArcIt iait(INVALID);
747 [ # # ]: 0 : const typename _Digraph::OutArcIt oait(INVALID);
748 [ # # ]: 0 : n = digraph.baseNode(iait);
749 [ # # ]: 0 : n = digraph.runningNode(iait);
750 [ # # ]: 0 : n = digraph.baseNode(oait);
751 [ # # ]: 0 : n = digraph.runningNode(oait);
752 [ # # ]: 0 : ignore_unused_variable_warning(n);
753 : : }
754 : 0 : }
755 : :
756 : : const _Digraph& digraph;
757 : : };
758 : : };
759 : :
760 : : /// \brief Skeleton class for iterable undirected graphs.
761 : : ///
762 : : /// This class describes the interface of iterable undirected
763 : : /// graphs. It extends \ref IterableDigraphComponent with the core
764 : : /// iterable interface of undirected graphs.
765 : : /// This concept is part of the Graph concept.
766 : : template <typename BAS = BaseGraphComponent>
767 : : class IterableGraphComponent : public IterableDigraphComponent<BAS> {
768 : : public:
769 : :
770 : : typedef BAS Base;
771 : : typedef typename Base::Node Node;
772 : : typedef typename Base::Arc Arc;
773 : : typedef typename Base::Edge Edge;
774 : :
775 : :
776 : : typedef IterableGraphComponent Graph;
777 : :
778 : : /// \name Base Iteration
779 : : ///
780 : : /// This interface provides functions for iteration on edges.
781 : : ///
782 : : /// @{
783 : :
784 : : using IterableDigraphComponent<Base>::first;
785 : : using IterableDigraphComponent<Base>::next;
786 : :
787 : : /// \brief Return the first edge.
788 : : ///
789 : : /// This function gives back the first edge in the iteration order.
790 : : void first(Edge&) const {}
791 : :
792 : : /// \brief Return the next edge.
793 : : ///
794 : : /// This function gives back the next edge in the iteration order.
795 : : void next(Edge&) const {}
796 : :
797 : : /// \brief Return the first edge incident to the given node.
798 : : ///
799 : : /// This function gives back the first edge incident to the given
800 : : /// node. The bool parameter gives back the direction for which the
801 : : /// source node of the directed arc representing the edge is the
802 : : /// given node.
803 : : void firstInc(Edge&, bool&, const Node&) const {}
804 : :
805 : : /// \brief Gives back the next of the edges from the
806 : : /// given node.
807 : : ///
808 : : /// This function gives back the next edge incident to the given
809 : : /// node. The bool parameter should be used as \c firstInc() use it.
810 : : void nextInc(Edge&, bool&) const {}
811 : :
812 : : using IterableDigraphComponent<Base>::baseNode;
813 : : using IterableDigraphComponent<Base>::runningNode;
814 : :
815 : : /// @}
816 : :
817 : : /// \name Class Based Iteration
818 : : ///
819 : : /// This interface provides iterator classes for edges.
820 : : ///
821 : : /// @{
822 : :
823 : : /// \brief This iterator goes through each edge.
824 : : ///
825 : : /// This iterator goes through each edge.
826 : : typedef GraphItemIt<Graph, Edge> EdgeIt;
827 : :
828 : : /// \brief This iterator goes trough the incident edges of a
829 : : /// node.
830 : : ///
831 : : /// This iterator goes trough the incident edges of a certain
832 : : /// node of a graph.
833 : : typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
834 : :
835 : : /// \brief The base node of the iterator.
836 : : ///
837 : : /// This function gives back the base node of the iterator.
838 : : Node baseNode(const IncEdgeIt&) const { return INVALID; }
839 : :
840 : : /// \brief The running node of the iterator.
841 : : ///
842 : : /// This function gives back the running node of the iterator.
843 : : Node runningNode(const IncEdgeIt&) const { return INVALID; }
844 : :
845 : : /// @}
846 : :
847 : : template <typename _Graph>
848 : : struct Constraints {
849 : : void constraints() {
850 : : checkConcept<IterableDigraphComponent<Base>, _Graph>();
851 : :
852 : : {
853 : : typename _Graph::Node node(INVALID);
854 : : typename _Graph::Edge edge(INVALID);
855 : : bool dir;
856 : : {
857 : : graph.first(edge);
858 : : graph.next(edge);
859 : : }
860 : : {
861 : : graph.firstInc(edge, dir, node);
862 : : graph.nextInc(edge, dir);
863 : : }
864 : :
865 : : }
866 : :
867 : : {
868 : : checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
869 : : typename _Graph::EdgeIt >();
870 : : checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
871 : : typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
872 : :
873 : : typename _Graph::Node n;
874 : : const typename _Graph::IncEdgeIt ieit(INVALID);
875 : : n = graph.baseNode(ieit);
876 : : n = graph.runningNode(ieit);
877 : : }
878 : : }
879 : :
880 : : const _Graph& graph;
881 : : };
882 : : };
883 : :
884 : : /// \brief Skeleton class for alterable directed graphs.
885 : : ///
886 : : /// This class describes the interface of alterable directed
887 : : /// graphs. It extends \ref BaseDigraphComponent with the alteration
888 : : /// notifier interface. It implements
889 : : /// an observer-notifier pattern for each digraph item. More
890 : : /// obsevers can be registered into the notifier and whenever an
891 : : /// alteration occured in the digraph all the observers will be
892 : : /// notified about it.
893 : : template <typename BAS = BaseDigraphComponent>
894 : : class AlterableDigraphComponent : public BAS {
895 : : public:
896 : :
897 : : typedef BAS Base;
898 : : typedef typename Base::Node Node;
899 : : typedef typename Base::Arc Arc;
900 : :
901 : :
902 : : /// Node alteration notifier class.
903 : : typedef AlterationNotifier<AlterableDigraphComponent, Node>
904 : : NodeNotifier;
905 : : /// Arc alteration notifier class.
906 : : typedef AlterationNotifier<AlterableDigraphComponent, Arc>
907 : : ArcNotifier;
908 : :
909 : : /// \brief Return the node alteration notifier.
910 : : ///
911 : : /// This function gives back the node alteration notifier.
912 : : NodeNotifier& notifier(Node) const {
913 : : return NodeNotifier();
914 : : }
915 : :
916 : : /// \brief Return the arc alteration notifier.
917 : : ///
918 : : /// This function gives back the arc alteration notifier.
919 : : ArcNotifier& notifier(Arc) const {
920 : : return ArcNotifier();
921 : : }
922 : :
923 : : template <typename _Digraph>
924 : : struct Constraints {
925 : : void constraints() {
926 : : checkConcept<Base, _Digraph>();
927 : : typename _Digraph::NodeNotifier& nn
928 : : = digraph.notifier(typename _Digraph::Node());
929 : :
930 : : typename _Digraph::ArcNotifier& en
931 : : = digraph.notifier(typename _Digraph::Arc());
932 : :
933 : : ignore_unused_variable_warning(nn);
934 : : ignore_unused_variable_warning(en);
935 : : }
936 : :
937 : : const _Digraph& digraph;
938 : : };
939 : : };
940 : :
941 : : /// \brief Skeleton class for alterable undirected graphs.
942 : : ///
943 : : /// This class describes the interface of alterable undirected
944 : : /// graphs. It extends \ref AlterableDigraphComponent with the alteration
945 : : /// notifier interface of undirected graphs. It implements
946 : : /// an observer-notifier pattern for the edges. More
947 : : /// obsevers can be registered into the notifier and whenever an
948 : : /// alteration occured in the graph all the observers will be
949 : : /// notified about it.
950 : : template <typename BAS = BaseGraphComponent>
951 : : class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
952 : : public:
953 : :
954 : : typedef BAS Base;
955 : : typedef typename Base::Edge Edge;
956 : :
957 : :
958 : : /// Edge alteration notifier class.
959 : : typedef AlterationNotifier<AlterableGraphComponent, Edge>
960 : : EdgeNotifier;
961 : :
962 : : /// \brief Return the edge alteration notifier.
963 : : ///
964 : : /// This function gives back the edge alteration notifier.
965 : : EdgeNotifier& notifier(Edge) const {
966 : : return EdgeNotifier();
967 : : }
968 : :
969 : : template <typename _Graph>
970 : : struct Constraints {
971 : : void constraints() {
972 : : checkConcept<AlterableDigraphComponent<Base>, _Graph>();
973 : : typename _Graph::EdgeNotifier& uen
974 : : = graph.notifier(typename _Graph::Edge());
975 : : ignore_unused_variable_warning(uen);
976 : : }
977 : :
978 : : const _Graph& graph;
979 : : };
980 : : };
981 : :
982 : : /// \brief Concept class for standard graph maps.
983 : : ///
984 : : /// This class describes the concept of standard graph maps, i.e.
985 : : /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
986 : : /// graph types, which can be used for associating data to graph items.
987 : : /// The standard graph maps must conform to the ReferenceMap concept.
988 : : template <typename GR, typename K, typename V>
989 : : class GraphMap : public ReferenceMap<K, V, V&, const V&> {
990 : : typedef ReferenceMap<K, V, V&, const V&> Parent;
991 : :
992 : : public:
993 : :
994 : : /// The key type of the map.
995 : : typedef K Key;
996 : : /// The value type of the map.
997 : : typedef V Value;
998 : : /// The reference type of the map.
999 : : typedef Value& Reference;
1000 : : /// The const reference type of the map.
1001 : : typedef const Value& ConstReference;
1002 : :
1003 : : // The reference map tag.
1004 : : typedef True ReferenceMapTag;
1005 : :
1006 : : /// \brief Construct a new map.
1007 : : ///
1008 : : /// Construct a new map for the graph.
1009 : : explicit GraphMap(const GR&) {}
1010 : : /// \brief Construct a new map with default value.
1011 : : ///
1012 : : /// Construct a new map for the graph and initalize the values.
1013 : : GraphMap(const GR&, const Value&) {}
1014 : :
1015 : : private:
1016 : : /// \brief Copy constructor.
1017 : : ///
1018 : : /// Copy Constructor.
1019 : : GraphMap(const GraphMap&) : Parent() {}
1020 : :
1021 : : /// \brief Assignment operator.
1022 : : ///
1023 : : /// Assignment operator. It does not mofify the underlying graph,
1024 : : /// it just iterates on the current item set and set the map
1025 : : /// with the value returned by the assigned map.
1026 : : template <typename CMap>
1027 : : GraphMap& operator=(const CMap&) {
1028 : : checkConcept<ReadMap<Key, Value>, CMap>();
1029 : : return *this;
1030 : : }
1031 : :
1032 : : public:
1033 : : template<typename _Map>
1034 : : struct Constraints {
1035 : 0 : void constraints() {
1036 [ # # ][ # # ]: 0 : checkConcept
[ # # ][ # # ]
[ # # ][ # # ]
1037 : : <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
1038 [ # # ][ # # ]: 0 : _Map m1(g);
[ # # ][ # # ]
[ # # ][ # # ]
1039 [ # # ][ # # ]: 0 : _Map m2(g,t);
[ # # ][ # # ]
[ # # ][ # # ]
1040 : :
1041 : : // Copy constructor
1042 : : // _Map m3(m);
1043 : :
1044 : : // Assignment operator
1045 : : // ReadMap<Key, Value> cmap;
1046 : : // m3 = cmap;
1047 : :
1048 [ # # ][ # # ]: 0 : ignore_unused_variable_warning(m1);
[ # # ][ # # ]
[ # # ][ # # ]
1049 [ # # ][ # # ]: 0 : ignore_unused_variable_warning(m2);
[ # # ][ # # ]
[ # # ][ # # ]
1050 : : // ignore_unused_variable_warning(m3);
1051 : 0 : }
1052 : :
1053 : : const _Map &m;
1054 : : const GR &g;
1055 : : const typename GraphMap::Value &t;
1056 : : };
1057 : :
1058 : : };
1059 : :
1060 : : /// \brief Skeleton class for mappable directed graphs.
1061 : : ///
1062 : : /// This class describes the interface of mappable directed graphs.
1063 : : /// It extends \ref BaseDigraphComponent with the standard digraph
1064 : : /// map classes, namely \c NodeMap and \c ArcMap.
1065 : : /// This concept is part of the Digraph concept.
1066 : : template <typename BAS = BaseDigraphComponent>
1067 : : class MappableDigraphComponent : public BAS {
1068 : : public:
1069 : :
1070 : : typedef BAS Base;
1071 : : typedef typename Base::Node Node;
1072 : : typedef typename Base::Arc Arc;
1073 : :
1074 : : typedef MappableDigraphComponent Digraph;
1075 : :
1076 : : /// \brief Standard graph map for the nodes.
1077 : : ///
1078 : : /// Standard graph map for the nodes.
1079 : : /// It conforms to the ReferenceMap concept.
1080 : : template <typename V>
1081 : : class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
1082 : : typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
1083 : :
1084 : : public:
1085 : : /// \brief Construct a new map.
1086 : : ///
1087 : : /// Construct a new map for the digraph.
1088 : : explicit NodeMap(const MappableDigraphComponent& digraph)
1089 : : : Parent(digraph) {}
1090 : :
1091 : : /// \brief Construct a new map with default value.
1092 : : ///
1093 : : /// Construct a new map for the digraph and initalize the values.
1094 : : NodeMap(const MappableDigraphComponent& digraph, const V& value)
1095 : : : Parent(digraph, value) {}
1096 : :
1097 : : private:
1098 : : /// \brief Copy constructor.
1099 : : ///
1100 : : /// Copy Constructor.
1101 : : NodeMap(const NodeMap& nm) : Parent(nm) {}
1102 : :
1103 : : /// \brief Assignment operator.
1104 : : ///
1105 : : /// Assignment operator.
1106 : : template <typename CMap>
1107 : : NodeMap& operator=(const CMap&) {
1108 : : checkConcept<ReadMap<Node, V>, CMap>();
1109 : : return *this;
1110 : : }
1111 : :
1112 : : };
1113 : :
1114 : : /// \brief Standard graph map for the arcs.
1115 : : ///
1116 : : /// Standard graph map for the arcs.
1117 : : /// It conforms to the ReferenceMap concept.
1118 : : template <typename V>
1119 : : class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
1120 : : typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
1121 : :
1122 : : public:
1123 : : /// \brief Construct a new map.
1124 : : ///
1125 : : /// Construct a new map for the digraph.
1126 : : explicit ArcMap(const MappableDigraphComponent& digraph)
1127 : : : Parent(digraph) {}
1128 : :
1129 : : /// \brief Construct a new map with default value.
1130 : : ///
1131 : : /// Construct a new map for the digraph and initalize the values.
1132 : : ArcMap(const MappableDigraphComponent& digraph, const V& value)
1133 : : : Parent(digraph, value) {}
1134 : :
1135 : : private:
1136 : : /// \brief Copy constructor.
1137 : : ///
1138 : : /// Copy Constructor.
1139 : : ArcMap(const ArcMap& nm) : Parent(nm) {}
1140 : :
1141 : : /// \brief Assignment operator.
1142 : : ///
1143 : : /// Assignment operator.
1144 : : template <typename CMap>
1145 : : ArcMap& operator=(const CMap&) {
1146 : : checkConcept<ReadMap<Arc, V>, CMap>();
1147 : : return *this;
1148 : : }
1149 : :
1150 : : };
1151 : :
1152 : :
1153 : : template <typename _Digraph>
1154 : : struct Constraints {
1155 : :
1156 : : struct Dummy {
1157 : : int value;
1158 : 0 : Dummy() : value(0) {}
1159 : : Dummy(int _v) : value(_v) {}
1160 : : };
1161 : :
1162 : 0 : void constraints() {
1163 : 0 : checkConcept<Base, _Digraph>();
1164 : : { // int map test
1165 : : typedef typename _Digraph::template NodeMap<int> IntNodeMap;
1166 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
1167 : : IntNodeMap >();
1168 : : } { // bool map test
1169 : : typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
1170 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
1171 : : BoolNodeMap >();
1172 : : } { // Dummy map test
1173 : : typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
1174 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
1175 : : DummyNodeMap >();
1176 : : }
1177 : :
1178 : : { // int map test
1179 : : typedef typename _Digraph::template ArcMap<int> IntArcMap;
1180 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
1181 : : IntArcMap >();
1182 : : } { // bool map test
1183 : : typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
1184 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
1185 : : BoolArcMap >();
1186 : : } { // Dummy map test
1187 : : typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
1188 : 0 : checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
1189 : : DummyArcMap >();
1190 : : }
1191 : 0 : }
1192 : :
1193 : : const _Digraph& digraph;
1194 : : };
1195 : : };
1196 : :
1197 : : /// \brief Skeleton class for mappable undirected graphs.
1198 : : ///
1199 : : /// This class describes the interface of mappable undirected graphs.
1200 : : /// It extends \ref MappableDigraphComponent with the standard graph
1201 : : /// map class for edges (\c EdgeMap).
1202 : : /// This concept is part of the Graph concept.
1203 : : template <typename BAS = BaseGraphComponent>
1204 : : class MappableGraphComponent : public MappableDigraphComponent<BAS> {
1205 : : public:
1206 : :
1207 : : typedef BAS Base;
1208 : : typedef typename Base::Edge Edge;
1209 : :
1210 : : typedef MappableGraphComponent Graph;
1211 : :
1212 : : /// \brief Standard graph map for the edges.
1213 : : ///
1214 : : /// Standard graph map for the edges.
1215 : : /// It conforms to the ReferenceMap concept.
1216 : : template <typename V>
1217 : : class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
1218 : : typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
1219 : :
1220 : : public:
1221 : : /// \brief Construct a new map.
1222 : : ///
1223 : : /// Construct a new map for the graph.
1224 : : explicit EdgeMap(const MappableGraphComponent& graph)
1225 : : : Parent(graph) {}
1226 : :
1227 : : /// \brief Construct a new map with default value.
1228 : : ///
1229 : : /// Construct a new map for the graph and initalize the values.
1230 : : EdgeMap(const MappableGraphComponent& graph, const V& value)
1231 : : : Parent(graph, value) {}
1232 : :
1233 : : private:
1234 : : /// \brief Copy constructor.
1235 : : ///
1236 : : /// Copy Constructor.
1237 : : EdgeMap(const EdgeMap& nm) : Parent(nm) {}
1238 : :
1239 : : /// \brief Assignment operator.
1240 : : ///
1241 : : /// Assignment operator.
1242 : : template <typename CMap>
1243 : : EdgeMap& operator=(const CMap&) {
1244 : : checkConcept<ReadMap<Edge, V>, CMap>();
1245 : : return *this;
1246 : : }
1247 : :
1248 : : };
1249 : :
1250 : :
1251 : : template <typename _Graph>
1252 : : struct Constraints {
1253 : :
1254 : : struct Dummy {
1255 : : int value;
1256 : : Dummy() : value(0) {}
1257 : : Dummy(int _v) : value(_v) {}
1258 : : };
1259 : :
1260 : : void constraints() {
1261 : : checkConcept<MappableDigraphComponent<Base>, _Graph>();
1262 : :
1263 : : { // int map test
1264 : : typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
1265 : : checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
1266 : : IntEdgeMap >();
1267 : : } { // bool map test
1268 : : typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
1269 : : checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
1270 : : BoolEdgeMap >();
1271 : : } { // Dummy map test
1272 : : typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
1273 : : checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
1274 : : DummyEdgeMap >();
1275 : : }
1276 : : }
1277 : :
1278 : : const _Graph& graph;
1279 : : };
1280 : : };
1281 : :
1282 : : /// \brief Skeleton class for extendable directed graphs.
1283 : : ///
1284 : : /// This class describes the interface of extendable directed graphs.
1285 : : /// It extends \ref BaseDigraphComponent with functions for adding
1286 : : /// nodes and arcs to the digraph.
1287 : : /// This concept requires \ref AlterableDigraphComponent.
1288 : : template <typename BAS = BaseDigraphComponent>
1289 : : class ExtendableDigraphComponent : public BAS {
1290 : : public:
1291 : : typedef BAS Base;
1292 : :
1293 : : typedef typename Base::Node Node;
1294 : : typedef typename Base::Arc Arc;
1295 : :
1296 : : /// \brief Add a new node to the digraph.
1297 : : ///
1298 : : /// This function adds a new node to the digraph.
1299 : : Node addNode() {
1300 : : return INVALID;
1301 : : }
1302 : :
1303 : : /// \brief Add a new arc connecting the given two nodes.
1304 : : ///
1305 : : /// This function adds a new arc connecting the given two nodes
1306 : : /// of the digraph.
1307 : : Arc addArc(const Node&, const Node&) {
1308 : : return INVALID;
1309 : : }
1310 : :
1311 : : template <typename _Digraph>
1312 : : struct Constraints {
1313 : : void constraints() {
1314 : : checkConcept<Base, _Digraph>();
1315 : : typename _Digraph::Node node_a, node_b;
1316 : : node_a = digraph.addNode();
1317 : : node_b = digraph.addNode();
1318 : : typename _Digraph::Arc arc;
1319 : : arc = digraph.addArc(node_a, node_b);
1320 : : }
1321 : :
1322 : : _Digraph& digraph;
1323 : : };
1324 : : };
1325 : :
1326 : : /// \brief Skeleton class for extendable undirected graphs.
1327 : : ///
1328 : : /// This class describes the interface of extendable undirected graphs.
1329 : : /// It extends \ref BaseGraphComponent with functions for adding
1330 : : /// nodes and edges to the graph.
1331 : : /// This concept requires \ref AlterableGraphComponent.
1332 : : template <typename BAS = BaseGraphComponent>
1333 : : class ExtendableGraphComponent : public BAS {
1334 : : public:
1335 : :
1336 : : typedef BAS Base;
1337 : : typedef typename Base::Node Node;
1338 : : typedef typename Base::Edge Edge;
1339 : :
1340 : : /// \brief Add a new node to the digraph.
1341 : : ///
1342 : : /// This function adds a new node to the digraph.
1343 : : Node addNode() {
1344 : : return INVALID;
1345 : : }
1346 : :
1347 : : /// \brief Add a new edge connecting the given two nodes.
1348 : : ///
1349 : : /// This function adds a new edge connecting the given two nodes
1350 : : /// of the graph.
1351 : : Edge addEdge(const Node&, const Node&) {
1352 : : return INVALID;
1353 : : }
1354 : :
1355 : : template <typename _Graph>
1356 : : struct Constraints {
1357 : : void constraints() {
1358 : : checkConcept<Base, _Graph>();
1359 : : typename _Graph::Node node_a, node_b;
1360 : : node_a = graph.addNode();
1361 : : node_b = graph.addNode();
1362 : : typename _Graph::Edge edge;
1363 : : edge = graph.addEdge(node_a, node_b);
1364 : : }
1365 : :
1366 : : _Graph& graph;
1367 : : };
1368 : : };
1369 : :
1370 : : /// \brief Skeleton class for erasable directed graphs.
1371 : : ///
1372 : : /// This class describes the interface of erasable directed graphs.
1373 : : /// It extends \ref BaseDigraphComponent with functions for removing
1374 : : /// nodes and arcs from the digraph.
1375 : : /// This concept requires \ref AlterableDigraphComponent.
1376 : : template <typename BAS = BaseDigraphComponent>
1377 : : class ErasableDigraphComponent : public BAS {
1378 : : public:
1379 : :
1380 : : typedef BAS Base;
1381 : : typedef typename Base::Node Node;
1382 : : typedef typename Base::Arc Arc;
1383 : :
1384 : : /// \brief Erase a node from the digraph.
1385 : : ///
1386 : : /// This function erases the given node from the digraph and all arcs
1387 : : /// connected to the node.
1388 : : void erase(const Node&) {}
1389 : :
1390 : : /// \brief Erase an arc from the digraph.
1391 : : ///
1392 : : /// This function erases the given arc from the digraph.
1393 : : void erase(const Arc&) {}
1394 : :
1395 : : template <typename _Digraph>
1396 : : struct Constraints {
1397 : : void constraints() {
1398 : : checkConcept<Base, _Digraph>();
1399 : : const typename _Digraph::Node node(INVALID);
1400 : : digraph.erase(node);
1401 : : const typename _Digraph::Arc arc(INVALID);
1402 : : digraph.erase(arc);
1403 : : }
1404 : :
1405 : : _Digraph& digraph;
1406 : : };
1407 : : };
1408 : :
1409 : : /// \brief Skeleton class for erasable undirected graphs.
1410 : : ///
1411 : : /// This class describes the interface of erasable undirected graphs.
1412 : : /// It extends \ref BaseGraphComponent with functions for removing
1413 : : /// nodes and edges from the graph.
1414 : : /// This concept requires \ref AlterableGraphComponent.
1415 : : template <typename BAS = BaseGraphComponent>
1416 : : class ErasableGraphComponent : public BAS {
1417 : : public:
1418 : :
1419 : : typedef BAS Base;
1420 : : typedef typename Base::Node Node;
1421 : : typedef typename Base::Edge Edge;
1422 : :
1423 : : /// \brief Erase a node from the graph.
1424 : : ///
1425 : : /// This function erases the given node from the graph and all edges
1426 : : /// connected to the node.
1427 : : void erase(const Node&) {}
1428 : :
1429 : : /// \brief Erase an edge from the digraph.
1430 : : ///
1431 : : /// This function erases the given edge from the digraph.
1432 : : void erase(const Edge&) {}
1433 : :
1434 : : template <typename _Graph>
1435 : : struct Constraints {
1436 : : void constraints() {
1437 : : checkConcept<Base, _Graph>();
1438 : : const typename _Graph::Node node(INVALID);
1439 : : graph.erase(node);
1440 : : const typename _Graph::Edge edge(INVALID);
1441 : : graph.erase(edge);
1442 : : }
1443 : :
1444 : : _Graph& graph;
1445 : : };
1446 : : };
1447 : :
1448 : : /// \brief Skeleton class for clearable directed graphs.
1449 : : ///
1450 : : /// This class describes the interface of clearable directed graphs.
1451 : : /// It extends \ref BaseDigraphComponent with a function for clearing
1452 : : /// the digraph.
1453 : : /// This concept requires \ref AlterableDigraphComponent.
1454 : : template <typename BAS = BaseDigraphComponent>
1455 : : class ClearableDigraphComponent : public BAS {
1456 : : public:
1457 : :
1458 : : typedef BAS Base;
1459 : :
1460 : : /// \brief Erase all nodes and arcs from the digraph.
1461 : : ///
1462 : : /// This function erases all nodes and arcs from the digraph.
1463 : : void clear() {}
1464 : :
1465 : : template <typename _Digraph>
1466 : : struct Constraints {
1467 : : void constraints() {
1468 : : checkConcept<Base, _Digraph>();
1469 : : digraph.clear();
1470 : : }
1471 : :
1472 : : _Digraph& digraph;
1473 : : };
1474 : : };
1475 : :
1476 : : /// \brief Skeleton class for clearable undirected graphs.
1477 : : ///
1478 : : /// This class describes the interface of clearable undirected graphs.
1479 : : /// It extends \ref BaseGraphComponent with a function for clearing
1480 : : /// the graph.
1481 : : /// This concept requires \ref AlterableGraphComponent.
1482 : : template <typename BAS = BaseGraphComponent>
1483 : : class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
1484 : : public:
1485 : :
1486 : : typedef BAS Base;
1487 : :
1488 : : /// \brief Erase all nodes and edges from the graph.
1489 : : ///
1490 : : /// This function erases all nodes and edges from the graph.
1491 : : void clear() {}
1492 : :
1493 : : template <typename _Graph>
1494 : : struct Constraints {
1495 : : void constraints() {
1496 : : checkConcept<Base, _Graph>();
1497 : : graph.clear();
1498 : : }
1499 : :
1500 : : _Graph& graph;
1501 : : };
1502 : : };
1503 : :
1504 : : }
1505 : :
1506 : : }
1507 : :
1508 : : #endif
|
