COIN-OR::LEMON - Graph Library

source: lemon/lemon/concepts/graph_components.h @ 1156:939d747055cd

1.1
Last change on this file since 1156:939d747055cd was 1126:a30455cd0107, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge Intel C++ compatibility fixes to branch 1.1

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