COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/concept/graph_component.h @ 1627:3fd1ba6e9872

Last change on this file since 1627:3fd1ba6e9872 was 1627:3fd1ba6e9872, checked in by Balazs Dezso, 19 years ago

Some modification on the undirected graph interface.
Doc improvments

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