COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/graph_component.h @ 1106:0a7d604a9763

Last change on this file since 1106:0a7d604a9763 was 1106:0a7d604a9763, checked in by Balazs Dezso, 15 years ago

Concept modification to resolve the item by its ID.

File size: 24.1 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      /// \brief Gives back the node by the unique id.
301      ///
302      /// Gives back the node by the unique id.
303      /// If the graph does not contain node with the given id
304      /// then the result of the function is undetermined.
305      Node fromId(int id, Node) const { return INVALID;}
306
307      /// \brief Gives back an unique integer id for the Edge.
308      ///
309      /// Gives back an unique integer id for the Edge.
310      ///
311      int id(const Edge&) const { return -1;}
312
313      /// \brief Gives back the edge by the unique id.
314      ///
315      /// Gives back the edge by the unique id.
316      /// If the graph does not contain edge with the given id
317      /// then the result of the function is undetermined.
318      Edge fromId(int id, Edge) const { return INVALID;}
319
320      template <typename _Graph>
321      struct Constraints {
322
323        void constraints() {
324          checkConcept< BaseGraphComponent, _Graph >();
325          typename _Graph::Node node;
326          int nid = graph.id(node);
327          nid = graph.id(node);
328          node = graph.fromId(nid, Node());
329          typename _Graph::Edge edge;
330          int eid = graph.id(edge);
331          eid = graph.id(edge);
332          edge = graph.fromId(eid, Edge());
333        }
334
335        const _Graph& graph;
336      };
337    };
338
339
340    /// An empty max-idable base graph class.
341 
342    /// This class provides beside the core graph features
343    /// core max id functions for the graph structure.
344    /// The most of the base graphs should be conform to this concept.
345    /// The id's are unique and immutable.
346    class MaxIDableGraphComponent : virtual public BaseGraphComponent {
347    public:
348
349      /// Gives back an integer greater or equal to the maximum Node id.
350
351      /// Gives back an integer greater or equal to the maximum Node id.
352      ///
353      int maxId(Node = INVALID) const { return -1;}
354
355      /// Gives back an integer greater or equal to the maximum Edge id.
356
357      /// Gives back an integer greater or equal to the maximum Edge id.
358      ///
359      int maxId(Edge = INVALID) const { return -1;}
360
361      template <typename _Graph>
362      struct Constraints {
363
364        void constraints() {
365          checkConcept<BaseGraphComponent, _Graph>();
366          int nid = graph.maxId(typename _Graph::Node());
367          ignore_unused_variable_warning(nid);
368          int eid = graph.maxId(typename _Graph::Edge());
369          ignore_unused_variable_warning(eid);
370        }
371     
372        const _Graph& graph;
373      };
374    };
375
376    /// An empty extendable base graph class.
377 
378    /// This class provides beside the core graph features
379    /// core graph extend interface for the graph structure.
380    /// The most of the base graphs should be conform to this concept.
381    class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
382    public:
383
384      typedef BaseGraphComponent::Node Node;
385      typedef BaseGraphComponent::Edge Edge;
386
387      /// Adds a new Node to the graph.
388
389      /// Adds a new Node to the graph.
390      ///
391      Node addNode() {
392        return INVALID;
393      }
394   
395      /// Adds a new Edge connects the two Nodes to the graph.
396
397      /// Adds a new Edge connects the two Nodes to the graph.
398      ///
399      Edge addEdge(const Node& from, const Node& to) {
400        return INVALID;
401      }
402
403      template <typename _Graph>
404      struct Constraints {
405        void constraints() {
406          checkConcept<BaseGraphComponent, _Graph >();
407          typename _Graph::Node node_a, node_b;
408          node_a = graph.addNode();
409          typename _Graph::Edge edge;
410          edge = graph.addEdge(node_a, node_b);
411        }
412
413        _Graph& graph;
414      };
415    };
416
417    /// An empty erasable base graph class.
418 
419    /// This class provides beside the core graph features
420    /// core erase functions for the graph structure.
421    /// The most of the base graphs should be conform to this concept.
422    class BaseErasableGraphComponent : virtual public BaseGraphComponent {
423    public:
424
425      typedef BaseGraphComponent::Node Node;
426      typedef BaseGraphComponent::Edge Edge;
427
428      /// Erase a Node from the graph.
429     
430      /// Erase a Node from the graph. This function should not
431      /// erase edges connecting to the Node.
432      void erase(const Node&) {}   
433
434      /// Erase an Edge from the graph.
435
436      /// Erase an Edge from the graph.
437      ///
438      void erase(const Edge&) {}
439
440      template <typename _Graph>
441      struct Constraints {
442        void constraints() {
443          checkConcept<BaseGraphComponent, _Graph>();
444          typename _Graph::Node node;
445          graph.erase(node);
446          typename _Graph::Edge edge;
447          graph.erase(edge);
448        }
449
450        _Graph& graph;
451      };
452    };
453
454    /// An empty clearable base graph class.
455 
456    /// This class provides beside the core graph features
457    /// core clear functions for the graph structure.
458    /// The most of the base graphs should be conform to this concept.
459    class ClearableGraphComponent : virtual public BaseGraphComponent {
460    public:
461
462      /// Erase all the Nodes and Edges from the graph.
463
464      /// Erase all the Nodes and Edges from the graph.
465      ///
466      void clear() {}   
467
468      template <typename _Graph>
469      struct Constraints {
470        void constraints() {
471          checkConcept<BaseGraphComponent, _Graph>();
472          graph.clear();
473        }
474
475        _Graph graph;
476      };
477    };
478
479
480    /// Skeleton class for graph NodeIt and EdgeIt
481
482    /// Skeleton class for graph NodeIt and EdgeIt.
483    ///
484    template <typename _Graph, typename _Item>
485    class GraphIterator : public _Item {
486    public:
487      /// \todo Don't we need the Item type as typedef?
488
489      /// Default constructor.
490     
491      /// @warning The default constructor sets the iterator
492      /// to an undefined value.
493      GraphIterator() {}
494      /// Copy constructor.
495     
496      /// Copy constructor.
497      ///
498      GraphIterator(GraphIterator const&) {}
499      /// Sets the iterator to the first item.
500     
501      /// Sets the iterator to the first item of \c the graph.
502      ///
503      explicit GraphIterator(const _Graph&) {}
504      /// Invalid constructor \& conversion.
505
506      /// This constructor initializes the item to be invalid.
507      /// \sa Invalid for more details.
508      GraphIterator(Invalid) {}
509      /// Assign operator for items.
510
511      /// The items are assignable.
512      ///
513      GraphIterator& operator=(GraphIterator const&) { return *this; }     
514      /// Next item.
515
516      /// Assign the iterator to the next item.
517      ///
518      GraphIterator& operator++() { return *this; }
519      //        Node operator*() const { return INVALID; }
520      /// Equality operator
521
522      /// Two iterators are equal if and only if they point to the
523      /// same object or both are invalid.
524      bool operator==(const GraphIterator&) const { return true;}
525      /// Inequality operator
526       
527      /// \sa operator==(Node n)
528      ///
529      bool operator!=(const GraphIterator&) const { return true;}
530     
531      template<typename _GraphIterator>
532      struct Constraints {
533        void constraints() {
534          //      checkConcept< Item, _GraphIterator >();
535          _GraphIterator it1(g);
536       
537          /// \todo Do we need NodeIt(Node) kind of constructor?
538          //    _GraphIterator it2(bj);
539          _GraphIterator it2;
540
541          it2 = ++it1;
542          ++it2 = it1;
543          ++(++it1);
544          /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
545          _Item bi = it1;
546          bi = it2;
547        }
548        _Graph& g;
549      };
550    };
551
552    /// Skeleton class for graph InEdgeIt and OutEdgeIt
553
554    /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
555    /// base class, the _selector is a additional template parameter. For
556    /// InEdgeIt you should instantiate it with character 'i' and for
557    /// OutEdgeIt with 'o'.
558    /// \todo Is this a good name for this concept?
559    template <typename Graph,
560              typename Edge = typename Graph::Edge,
561              char _selector = '0'>
562    class GraphIncIterator : public Edge {
563    public:
564      /// Default constructor.
565     
566      /// @warning The default constructor sets the iterator
567      /// to an undefined value.
568      GraphIncIterator() {}
569      /// Copy constructor.
570     
571      /// Copy constructor.
572      ///
573      GraphIncIterator(GraphIncIterator const&) {}
574      /// Sets the iterator to the first edge incoming into or outgoing from the node.
575     
576      /// Sets the iterator to the first edge incoming into or outgoing from the node.
577      ///
578      explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
579      /// Invalid constructor \& conversion.
580
581      /// This constructor initializes the item to be invalid.
582      /// \sa Invalid for more details.
583      GraphIncIterator(Invalid) {}
584      /// Assign operator for nodes.
585
586      /// The nodes are assignable.
587      ///
588      GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }     
589      /// Next edge.
590
591      /// Assign the iterator to the next node.
592      ///
593      GraphIncIterator& operator++() { return *this; }
594
595      //        Node operator*() const { return INVALID; }
596
597      /// Equality operator
598
599      /// Two iterators are equal if and only if they point to the
600      /// same object or both are invalid.
601      bool operator==(const GraphIncIterator&) const { return true;}
602
603      /// Inequality operator
604       
605      /// \sa operator==(Node n)
606      ///
607      bool operator!=(const GraphIncIterator&) const { return true;}
608
609      template <typename _GraphIncIterator>
610      struct Constraints {
611        typedef typename Graph::Node Node;
612        void constraints() {
613          checkConcept<GraphItem<'e'>, _GraphIncIterator>();
614          _GraphIncIterator it1(graph, node);
615          /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
616          //    _GraphIncIterator it2(edge);
617          _GraphIncIterator it2;
618
619          it2 = ++it1;
620          ++it2 = it1;
621          ++(++it1);
622          Edge e = it1;
623          e = it2;
624        }
625
626        Edge& edge;
627        Node& node;
628        Graph& graph;
629      };
630    };
631
632
633    /// An empty iterable base graph class.
634 
635    /// This class provides beside the core graph features
636    /// iterator based iterable interface for the graph structure.
637    /// This concept is part of the StaticGraphConcept.
638    class IterableGraphComponent : virtual public BaseGraphComponent {
639
640    public:
641   
642      typedef IterableGraphComponent Graph;
643
644      typedef BaseGraphComponent::Node Node;
645      typedef BaseGraphComponent::Edge Edge;
646
647      /// This iterator goes through each node.
648
649      /// This iterator goes through each node.
650      ///
651      typedef GraphIterator<Graph, Node> NodeIt;
652      /// This iterator goes through each node.
653
654      /// This iterator goes through each node.
655      ///
656      typedef GraphIterator<Graph, Edge> EdgeIt;
657      /// This iterator goes trough the incoming edges of a node.
658
659      /// This iterator goes trough the \e inccoming edges of a certain node
660      /// of a graph.
661      typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
662      /// This iterator goes trough the outgoing edges of a node.
663
664      /// This iterator goes trough the \e outgoing edges of a certain node
665      /// of a graph.
666      typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
667    };
668   
669    template <typename _Graph>
670    struct Constraints {
671      void constraints() {
672        checkConcept< BaseGraphComponent, _Graph>();
673
674        checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
675        checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
676        checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
677        checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
678      }
679    };
680
681
682    /// Class describing the concept of graph maps
683
684    /// This class describes the common interface of the graph maps
685    /// (NodeMap, EdgeMap), that is \ref maps-pages "maps" which can be used to
686    /// associate data to graph descriptors (nodes or edges).
687    template <typename Graph, typename Item, typename _Value>
688    class GraphMap : public ReadWriteMap<Item, _Value> {
689    protected:     
690      GraphMap() {}
691    public:
692      explicit GraphMap(const Graph&) {}
693      GraphMap(const Graph&, const _Value&) {}
694      GraphMap(const GraphMap&) {}
695     
696      GraphMap& operator=(const GraphMap&) { return *this;}
697
698      template<typename _Map>
699      struct Constraints {
700        void constraints() {
701          checkConcept<ReadWriteMap<Item, _Value>, _Map >();
702          // Construction with a graph parameter
703          _Map a(g);
704          // Constructor with a graph and a default value parameter
705          _Map a2(g,t);
706          // Copy constructor. Do we need it?
707          _Map b=c;
708          // Copy operator. Do we need it?
709          a=b;
710
711          ignore_unused_variable_warning(a2);
712        }
713
714        const _Map &c;
715        const Graph &g;
716        const typename GraphMap::Value &t;
717      };
718
719    };
720
721    /// An empty mappable base graph class.
722 
723    /// This class provides beside the core graph features
724    /// map interface for the graph structure.
725    /// This concept is part of the StaticGraphConcept.
726    class MappableGraphComponent : virtual public BaseGraphComponent {
727    public:
728
729      typedef MappableGraphComponent Graph;
730
731      typedef BaseGraphComponent::Node Node;
732      typedef BaseGraphComponent::Edge Edge;
733
734      /// ReadWrite map of the nodes.
735   
736      /// ReadWrite map of the nodes.
737      ///
738      template <typename _Value>
739      class NodeMap : public GraphMap<Graph, Node, _Value> {
740      private:
741        NodeMap();
742      public:
743        // \todo call the right parent class constructor
744        explicit NodeMap(const Graph&) {}
745        NodeMap(const Graph&, const _Value&) {}
746        NodeMap(const NodeMap&) {}
747
748        NodeMap& operator=(const NodeMap&) { return *this;}
749
750      };
751
752      /// ReadWrite map of the edges.
753   
754      /// ReadWrite map of the edges.
755      ///
756      template <typename _Value>
757      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
758      private:
759        EdgeMap();
760      public:
761        // \todo call the right parent class constructor
762        explicit EdgeMap(const Graph&) {}
763        EdgeMap(const Graph&, const _Value&) {}
764        EdgeMap(const EdgeMap&) {}
765
766        EdgeMap& operator=(const EdgeMap&) { return *this;}
767
768      };
769
770      template <typename _Graph>
771      struct Constraints {
772
773        struct Type {
774          int value;
775          Type() : value(0) {}
776          Type(int _v) : value(_v) {}
777        };
778
779        void constraints() {
780          checkConcept<BaseGraphComponent, _Graph>();
781          { // int map test
782            typedef typename _Graph::template NodeMap<int> IntNodeMap;
783            checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, IntNodeMap >();
784          } { // bool map test
785            typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
786            checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, BoolNodeMap >();
787          } { // Type map test
788            typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
789            checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, TypeNodeMap >();
790          }
791
792          { // int map test
793            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
794            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, IntEdgeMap >();
795          } { // bool map test
796            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
797            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, BoolEdgeMap >();
798          } { // Type map test
799            typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
800            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, TypeEdgeMap >();
801          }
802        }
803
804        _Graph& graph;
805      };
806    };
807
808
809    class ExtendableGraphComponent : virtual public BaseGraphComponent {
810    public:
811
812      typedef ExtendableGraphComponent Graph;
813
814      typedef BaseGraphComponent::Node Node;
815      typedef BaseGraphComponent::Edge Edge;
816
817      Node addNode() {
818        return INVALID;
819      }
820   
821      Edge addEdge(const Node& from, const Node& to) {
822        return INVALID;
823      }
824
825      template <typename _Graph>
826      struct Constraints {
827        void constraints() {
828          checkConcept<BaseGraphComponent, _Graph >();
829          typename _Graph::Node node_a, node_b;
830          node_a = graph.addNode();
831          typename _Graph::Edge edge;
832          edge = graph.addEdge(node_a, node_b);     
833        }
834        _Graph& graph;
835      };
836    };
837    class ErasableGraphComponent : virtual public BaseGraphComponent {
838    public:
839
840      typedef ErasableGraphComponent Graph;
841
842      typedef BaseGraphComponent::Node Node;
843      typedef BaseGraphComponent::Edge Edge;
844
845      void erase(const Node&) {}   
846      void erase(const Edge&) {}
847
848      template <typename _Graph>
849      struct Constraints {
850        void constraints() {
851          checkConcept<BaseGraphComponent, _Graph >();
852          typename _Graph::Node node;
853          graph.erase(node);
854          typename _Graph::Edge edge;
855          graph.erase(edge);     
856        }
857
858        _Graph& graph;
859      };
860    };
861
862    /// @}
863
864  }
865
866}
867
868#endif
Note: See TracBrowser for help on using the repository browser.