COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph_component.h @ 1493:94535d1833b5

Last change on this file since 1493:94535d1833b5 was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

File size: 27.7 KB
Line 
1/* -*- C++ -*-
2 * lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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
28#include <lemon/bits/alteration_notifier.h>
29
30namespace lemon {
31  namespace concept {
32
33    /// \addtogroup graph_concepts
34    /// @{
35
36    /****************   Graph iterator concepts   ****************/
37
38    /// Skeleton class for graph Node and Edge types
39
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'.
48
49#ifndef DOXYGEN
50    template <char _selector = '0'>
51#endif
52    class GraphItem {
53    public:
54      /// Default constructor.
55     
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.
59      GraphItem() {}
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.
69      GraphItem(Invalid) {}
70      /// Assign operator for nodes.
71
72      /// The nodes are assignable.
73      ///
74      GraphItem& operator=(GraphItem const&) { return *this; }
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.
79      bool operator==(GraphItem) const { return false; }
80      /// Inequality operator.
81       
82      /// \sa operator==(const Node& n)
83      ///
84      bool operator!=(GraphItem) const { return false; }
85
86      /// Artificial ordering operator.
87
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; }
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);
111          //      b = (ia < ib);
112        }
113
114        const _GraphItem &ia;
115        const _GraphItem &ib;
116      };
117    };
118
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
134    /// An empty base graph class.
135 
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.
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      ///
152      typedef GraphItem<'n'> Node;
153
154      /// Edge class of the graph.
155
156      /// This class represents the Edges of the graph.
157      ///
158      typedef GraphItem<'e'> Edge;
159
160      ///Gives back the target node of an edge.
161
162      ///Gives back the target node of an edge.
163      ///
164      Node target(const Edge&) const { return INVALID;}
165
166      ///Gives back the source node of an edge.
167
168      ///Gives back the source node of an edge.
169      ///
170      Node source(const Edge&) const { return INVALID;}
171
172
173      template <typename _Graph>
174      struct Constraints {
175        typedef typename _Graph::Node Node;
176        typedef typename _Graph::Edge Edge;
177     
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        }
188     
189        const _Graph& graph;
190      };
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
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        }
279
280        const _Graph& graph;
281      };
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
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.
307      Node fromId(int , Node) const { return INVALID;}
308
309      /// \brief Gives back an unique integer id for the Edge.
310      ///
311      /// Gives back an unique integer id for the Edge.
312      ///
313      int id(const Edge&) const { return -1;}
314
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.
320      Edge fromId(int, Edge) const { return INVALID;}
321
322      template <typename _Graph>
323      struct Constraints {
324
325        void constraints() {
326          checkConcept< BaseGraphComponent, _Graph >();
327          typename _Graph::Node node;
328          int nid = graph.id(node);
329          nid = graph.id(node);
330          node = graph.fromId(nid, Node());
331          typename _Graph::Edge edge;
332          int eid = graph.id(edge);
333          eid = graph.id(edge);
334          edge = graph.fromId(eid, Edge());
335        }
336
337        const _Graph& graph;
338      };
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      ///
355      int maxId(Node = INVALID) const { return -1;}
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      ///
361      int maxId(Edge = INVALID) const { return -1;}
362
363      template <typename _Graph>
364      struct Constraints {
365
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      };
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      ///
401      Edge addEdge(const Node&, const Node&) {
402        return INVALID;
403      }
404
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();
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   
681    template <typename _Graph>
682    struct Constraints {
683      void constraints() {
684        checkConcept< BaseGraphComponent, _Graph>();
685
686        checkConcept<GraphIterator<_Graph, typename _Graph::Edge>,
687          typename _Graph::EdgeIt >();
688        checkConcept<GraphIterator<_Graph, typename _Graph::Node>,
689          typename _Graph::NodeIt >();
690        checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
691        checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
692      }
693    };
694
695    /// An empty alteration notifier base graph class.
696 
697    /// This class provides beside the core graph features
698    /// alteration notifier interface for the graph structure.
699    /// This is an observer-notifier pattern. More Obsevers can
700    /// be registered into the notifier and whenever an alteration
701    /// occured in the graph all the observers will notified about it.
702    class AlterableGraphComponent : virtual public BaseGraphComponent {
703    public:
704
705      /// The edge observer registry.
706      typedef AlterationNotifier<Edge> EdgeNotifier;
707      /// The node observer registry.
708      typedef AlterationNotifier<Node> NodeNotifier;
709     
710      /// \brief Gives back the edge alteration notifier.
711      ///
712      /// Gives back the edge alteration notifier.
713      EdgeNotifier getNotifier(Edge) const {
714        return EdgeNotifier();
715      }
716     
717      /// \brief Gives back the node alteration notifier.
718      ///
719      /// Gives back the node alteration notifier.
720      NodeNotifier getNotifier(Node) const {
721        return NodeNotifier();
722      }
723     
724    };
725
726
727    /// Class describing the concept of graph maps
728
729    /// This class describes the common interface of the graph maps
730    /// (NodeMap, EdgeMap), that is \ref maps-pages "maps" which can be used to
731    /// associate data to graph descriptors (nodes or edges).
732    template <typename Graph, typename Item, typename _Value>
733    class GraphMap : public ReadWriteMap<Item, _Value> {
734    protected:     
735      GraphMap() {}
736    public:
737      /// \brief Construct a new map.
738      ///
739      /// Construct a new map for the graph.
740      explicit GraphMap(const Graph&) {}
741      /// \brief Construct a new map with default value.
742      ///
743      /// Construct a new map for the graph and initalise the values.
744      GraphMap(const Graph&, const _Value&) {}
745      /// \brief Copy constructor.
746      ///
747      /// Copy Constructor.
748      GraphMap(const GraphMap& gm) :ReadWriteMap<Item, _Value>(gm) {}
749     
750      /// \brief Assign operator.
751      ///
752      /// Assign operator.
753      GraphMap& operator=(const GraphMap&) { return *this;}
754
755      template<typename _Map>
756      struct Constraints {
757        void constraints() {
758          checkConcept<ReadWriteMap<Item, _Value>, _Map >();
759          // Construction with a graph parameter
760          _Map a(g);
761          // Constructor with a graph and a default value parameter
762          _Map a2(g,t);
763          // Copy constructor. Do we need it?
764          _Map b=c;
765          // Copy operator. Do we need it?
766          a=b;
767
768          ignore_unused_variable_warning(a2);
769        }
770
771        const _Map &c;
772        const Graph &g;
773        const typename GraphMap::Value &t;
774      };
775
776    };
777
778    /// An empty mappable base graph class.
779 
780    /// This class provides beside the core graph features
781    /// map interface for the graph structure.
782    /// This concept is part of the StaticGraphConcept.
783    class MappableGraphComponent : virtual public BaseGraphComponent {
784    public:
785
786      typedef MappableGraphComponent Graph;
787
788      typedef BaseGraphComponent::Node Node;
789      typedef BaseGraphComponent::Edge Edge;
790
791      /// ReadWrite map of the nodes.
792   
793      /// ReadWrite map of the nodes.
794      ///
795      template <typename _Value>
796      class NodeMap : public GraphMap<Graph, Node, _Value> {
797      private:
798        NodeMap();
799      public:
800        /// \brief Construct a new map.
801        ///
802        /// Construct a new map for the graph.
803        /// \todo call the right parent class constructor
804        explicit NodeMap(const Graph&) {}
805        /// \brief Construct a new map with default value.
806        ///
807        /// Construct a new map for the graph and initalise the values.
808        NodeMap(const Graph&, const _Value&) {}
809        /// \brief Copy constructor.
810        ///
811        /// Copy Constructor.
812        NodeMap(const NodeMap& nm) : GraphMap<Graph, Node, _Value>(nm) {}
813
814        /// \brief Assign operator.
815        ///
816        /// Assign operator.
817        NodeMap& operator=(const NodeMap&) { return *this;}
818
819      };
820
821      /// ReadWrite map of the edges.
822   
823      /// ReadWrite map of the edges.
824      ///
825      template <typename _Value>
826      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
827      private:
828        EdgeMap();
829      public:
830        /// \brief Construct a new map.
831        ///
832        /// Construct a new map for the graph.
833        /// \todo call the right parent class constructor
834        explicit EdgeMap(const Graph&) {}
835        /// \brief Construct a new map with default value.
836        ///
837        /// Construct a new map for the graph and initalise the values.
838        EdgeMap(const Graph&, const _Value&) {}
839        /// \brief Copy constructor.
840        ///
841        /// Copy Constructor.
842        EdgeMap(const EdgeMap& em) :GraphMap<Graph, Edge, _Value>(em) {}
843
844        /// \brief Assign operator.
845        ///
846        /// Assign operator.
847        EdgeMap& operator=(const EdgeMap&) { return *this;}
848
849      };
850
851      template <typename _Graph>
852      struct Constraints {
853
854        struct Type {
855          int value;
856          Type() : value(0) {}
857          Type(int _v) : value(_v) {}
858        };
859
860        void constraints() {
861          checkConcept<BaseGraphComponent, _Graph>();
862          { // int map test
863            typedef typename _Graph::template NodeMap<int> IntNodeMap;
864            checkConcept<GraphMap<_Graph, typename _Graph::Node, int>,
865              IntNodeMap >();
866          } { // bool map test
867            typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
868            checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>,
869              BoolNodeMap >();
870          } { // Type map test
871            typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
872            checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>,
873              TypeNodeMap >();
874          }
875
876          { // int map test
877            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
878            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
879              IntEdgeMap >();
880          } { // bool map test
881            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
882            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
883              BoolEdgeMap >();
884          } { // Type map test
885            typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
886            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>,
887              TypeEdgeMap >();
888          }
889        }
890
891        _Graph& graph;
892      };
893    };
894
895    /// \brief An empty extendable extended graph class.
896    ///
897    /// This class provides beside the core graph features
898    /// item addition interface for the graph structure.
899    /// The difference between this class and the
900    /// \c BaseExtendableGraphComponent is that it should
901    /// notify the item alteration observers.
902    class ExtendableGraphComponent : virtual public BaseGraphComponent {
903    public:
904
905      typedef ExtendableGraphComponent Graph;
906
907      typedef BaseGraphComponent::Node Node;
908      typedef BaseGraphComponent::Edge Edge;
909
910      /// \brief Add a node to the graph.
911      ///
912      /// Add a node to the graph and notify the observers.
913      Node addNode() {
914        return INVALID;
915      }
916   
917      /// \brief Add an edge to the graph.
918      ///
919      /// Add an edge to the graph and notify the observers.
920      Edge addEdge(const Node&, const Node&) {
921        return INVALID;
922      }
923
924      template <typename _Graph>
925      struct Constraints {
926        void constraints() {
927          checkConcept<BaseGraphComponent, _Graph >();
928          typename _Graph::Node node_a, node_b;
929          node_a = graph.addNode();
930          typename _Graph::Edge edge;
931          edge = graph.addEdge(node_a, node_b);     
932        }
933        _Graph& graph;
934      };
935    };
936
937    /// \brief An empty erasable extended graph class.
938    ///
939    /// This class provides beside the core graph features
940    /// item erase interface for the graph structure.
941    /// The difference between this class and the
942    /// \c BaseErasableGraphComponent is that it should
943    /// notify the item alteration observers.
944    class ErasableGraphComponent : virtual public BaseGraphComponent {
945    public:
946
947      typedef ErasableGraphComponent Graph;
948
949      typedef BaseGraphComponent::Node Node;
950      typedef BaseGraphComponent::Edge Edge;
951
952      /// \brief Erase the Node and notify the node alteration observers.
953      ///
954      ///  Erase the Node and notify the node alteration observers.
955      void erase(const Node&) {}   
956
957      /// \brief Erase the Edge and notify the edge alteration observers.
958      ///
959      ///  Erase the Edge and notify the edge alteration observers.
960      void erase(const Edge&) {}
961
962      template <typename _Graph>
963      struct Constraints {
964        void constraints() {
965          checkConcept<BaseGraphComponent, _Graph >();
966          typename _Graph::Node node;
967          graph.erase(node);
968          typename _Graph::Edge edge;
969          graph.erase(edge);     
970        }
971
972        _Graph& graph;
973      };
974    };
975
976    /// @}
977
978  }
979
980}
981
982#endif
Note: See TracBrowser for help on using the repository browser.