COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/concepts/graph_components.h @ 666:1993af615e68

Last change on this file since 666:1993af615e68 was 666:1993af615e68, checked in by Alpar Juttner <alpar@…>, 16 years ago

Resolve GCC-4.4 warnings & fix ambiguous op=() in graph_components.h

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