COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/graph_component.h @ 1030:c8a41699e613

Last change on this file since 1030:c8a41699e613 was 1030:c8a41699e613, checked in by Mihaly Barasz, 15 years ago

Undirected graph documentation and concept refinements.

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