COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph_component.h @ 1999:2ff283124dfc

Last change on this file since 1999:2ff283124dfc was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

Clarifing alteration observing system
It is directly connected now to a container

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