COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph_component.h @ 1619:f0700b9e6418

Last change on this file since 1619:f0700b9e6418 was 1563:0853ed07a677, checked in by Balazs Dezso, 19 years ago

Fix concepts and constraints

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