COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/graph_component.h @ 1022:567f392d1d2e

Last change on this file since 1022:567f392d1d2e was 1022:567f392d1d2e, checked in by Mihaly Barasz, 19 years ago

UndirGraph? implementation nearly complete

File size: 21.9 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/concept/graph_component.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17///\ingroup concept
18///\file
19///\brief The graph components.
20
21
22#ifndef LEMON_CONCEPT_GRAPH_COMPONENT_H
23#define LEMON_CONCEPT_GRAPH_COMPONENT_H
24
25#include <lemon/invalid.h>
26#include <lemon/concept/maps.h>
27
28namespace lemon {
29  namespace concept {
30
31
32    /****************   Graph iterator concepts   ****************/
33
34    /// Skeleton class for graph Node and Edge
35
36    /// \note Because Node and Edge are forbidden to inherit from the same
37    /// base class, this is a template. For Node you should instantiate it
38    /// with character 'n' and for Edge with 'e'.
39
40    template<char _selector>
41    class GraphItem {
42    public:
43      /// Default constructor.
44     
45      /// @warning The default constructor sets the item
46      /// to an undefined value.
47      GraphItem() {}
48      /// Copy constructor.
49     
50      /// Copy constructor.
51      ///
52      GraphItem(GraphItem const&) {}
53      /// Invalid constructor \& conversion.
54
55      /// This constructor initializes the item to be invalid.
56      /// \sa Invalid for more details.
57      GraphItem(Invalid) {}
58      /// Assign operator for nodes.
59
60      /// The nodes are assignable.
61      ///
62      GraphItem& operator=(GraphItem const&) { return *this; }
63      /// Equality operator.
64     
65      /// Two iterators are equal if and only if they represents the
66      /// same node in the graph or both are invalid.
67      bool operator==(GraphItem) const { return false; }
68      /// Inequality operator.
69       
70      /// \sa operator==(const Node& n)
71      ///
72      bool operator!=(GraphItem) const { return false; }
73
74      // Technical requirement. Do we really need this?
75      //      bool operator<(GraphItem) const { return false; }
76
77
78      template<typename _GraphItem>
79      struct Constraints {
80        void constraints() {
81          _GraphItem i1;
82          _GraphItem i2 = i1;
83          _GraphItem i3 = INVALID;
84         
85          i1 = i2 = i3;
86
87          bool b;
88          //      b = (ia == ib) && (ia != ib) && (ia < ib);
89          b = (ia == ib) && (ia != ib);
90          b = (ia == INVALID) && (ib != INVALID);
91        }
92
93        const _GraphItem &ia;
94        const _GraphItem &ib;
95      };
96    };
97
98    /// An empty base graph class.
99 
100    /// This class provides the minimal set of features needed for a graph
101    /// structure. All graph concepts have to be conform to this base
102    /// graph.
103    ///
104    /// \bug This is not true. The minimal graph concept is the
105    /// BaseIterableGraphComponent.
106
107    class BaseGraphComponent {
108    public:
109
110      typedef BaseGraphComponent Graph;
111     
112      /// Node class of the graph.
113
114      /// This class represents the Nodes of the graph.
115      ///
116      typedef GraphItem<'n'> Node;
117
118      /// Edge class of the graph.
119
120      /// This class represents the Edges of the graph.
121      ///
122      typedef GraphItem<'e'> Edge;
123
124      ///Gives back the target node of an edge.
125
126      ///Gives back the target node of an edge.
127      ///
128      Node target(const Edge&) const { return INVALID;}
129
130      ///Gives back the source node of an edge.
131
132      ///Gives back the source node of an edge.
133      ///
134      Node source(const Edge&) const { return INVALID;}
135
136
137      template <typename _Graph>
138      struct Constraints {
139        typedef typename _Graph::Node Node;
140        typedef typename _Graph::Edge Edge;
141     
142        void constraints() {
143          checkConcept<GraphItem<'n'>, Node>();
144          checkConcept<GraphItem<'e'>, Edge>();
145          {
146            Node n;
147            Edge e;
148            n = graph.source(e);
149            n = graph.target(e);
150          }     
151        }
152     
153        const _Graph& graph;
154      };
155    };
156
157    /// An empty iterable base graph class.
158 
159    /// This class provides beside the core graph features
160    /// core iterable interface for the graph structure.
161    /// Most of the base graphs should be conform to this concept.
162
163    class BaseIterableGraphComponent : virtual public BaseGraphComponent {
164    public:
165
166      typedef BaseGraphComponent::Node Node;
167      typedef BaseGraphComponent::Edge Edge;
168
169      /// Gives back the first Node in the iterating order.
170     
171      /// Gives back the first Node in the iterating order.
172      ///     
173      void first(Node&) const {}
174
175      /// Gives back the next Node in the iterating order.
176     
177      /// Gives back the next Node in the iterating order.
178      ///     
179      void next(Node&) const {}
180
181      /// Gives back the first Edge in the iterating order.
182     
183      /// Gives back the first Edge in the iterating order.
184      ///     
185      void first(Edge&) const {}
186      /// Gives back the next Edge in the iterating order.
187     
188      /// Gives back the next Edge in the iterating order.
189      ///     
190      void next(Edge&) const {}
191
192
193      /// Gives back the first of the Edges point to the given Node.
194     
195      /// Gives back the first of the Edges point to the given Node.
196      ///     
197      void firstIn(Edge&, const Node&) const {}
198
199      /// Gives back the next of the Edges points to the given Node.
200
201
202      /// Gives back the next of the Edges points to the given Node.
203      ///
204      void nextIn(Edge&) const {}
205
206      /// Gives back the first of the Edges start from the given Node.
207     
208      /// Gives back the first of the Edges start from the given Node.
209      ///     
210      void firstOut(Edge&, const Node&) const {}
211
212      /// Gives back the next of the Edges start from the given Node.
213     
214      /// Gives back the next of the Edges start from the given Node.
215      ///     
216      void nextOut(Edge&) const {}
217
218
219      template <typename _Graph>
220      struct Constraints {
221     
222        void constraints() {
223          checkConcept< BaseGraphComponent, _Graph >();
224          typename _Graph::Node node;     
225          typename _Graph::Edge edge;
226          {
227            graph.first(node);
228            graph.next(node);
229          }
230          {
231            graph.first(edge);
232            graph.next(edge);
233          }
234          {
235            graph.firstIn(edge, node);
236            graph.nextIn(edge);
237          }
238          {
239            graph.firstOut(edge, node);
240            graph.nextOut(edge);
241          }
242        }
243
244        const _Graph& graph;
245      };
246    };
247
248    /// An empty idable base graph class.
249 
250    /// This class provides beside the core graph features
251    /// core id functions for the graph structure.
252    /// The most of the base graphs should be conform to this concept.
253    /// The id's are unique and immutable.
254    class IDableGraphComponent : virtual public BaseGraphComponent {
255    public:
256
257      typedef BaseGraphComponent::Node Node;
258      typedef BaseGraphComponent::Edge Edge;
259
260      /// Gives back an unique integer id for the Node.
261
262      /// Gives back an unique integer id for the Node.
263      ///
264      int id(const Node&) const { return -1;}
265
266      /// Gives back an unique integer id for the Edge.
267
268      /// Gives back an unique integer id for the Edge.
269      ///
270      int id(const Edge&) const { return -1;}
271
272      template <typename _Graph>
273      struct Constraints {
274
275        void constraints() {
276          checkConcept< BaseGraphComponent, _Graph >();
277          typename _Graph::Node node;
278          int nid = graph.id(node);
279          nid = graph.id(node);
280          typename _Graph::Edge edge;
281          int eid = graph.id(edge);
282          eid = graph.id(edge);
283        }
284
285        const _Graph& graph;
286      };
287    };
288
289
290    /// An empty max-idable base graph class.
291 
292    /// This class provides beside the core graph features
293    /// core max id functions for the graph structure.
294    /// The most of the base graphs should be conform to this concept.
295    /// The id's are unique and immutable.
296    class MaxIDableGraphComponent : virtual public BaseGraphComponent {
297    public:
298
299      /// Gives back an integer greater or equal to the maximum Node id.
300
301      /// Gives back an integer greater or equal to the maximum Node id.
302      ///
303      int maxId(Node = INVALID) const { return -1;}
304
305      /// Gives back an integer greater or equal to the maximum Edge id.
306
307      /// Gives back an integer greater or equal to the maximum Edge id.
308      ///
309      int maxId(Edge = INVALID) const { return -1;}
310
311      template <typename _Graph>
312      struct Constraints {
313
314        void constraints() {
315          checkConcept<BaseGraphComponent, _Graph>();
316          int nid = graph.maxId(typename _Graph::Node());
317          ignore_unused_variable_warning(nid);
318          int eid = graph.maxId(typename _Graph::Edge());
319          ignore_unused_variable_warning(eid);
320        }
321     
322        const _Graph& graph;
323      };
324    };
325
326    /// An empty extendable base graph class.
327 
328    /// This class provides beside the core graph features
329    /// core graph extend interface for the graph structure.
330    /// The most of the base graphs should be conform to this concept.
331    class BaseExtendableGraphComponent : virtual public BaseGraphComponent {
332    public:
333
334      typedef BaseGraphComponent::Node Node;
335      typedef BaseGraphComponent::Edge Edge;
336
337      /// Adds a new Node to the graph.
338
339      /// Adds a new Node to the graph.
340      ///
341      Node addNode() {
342        return INVALID;
343      }
344   
345      /// Adds a new Edge connects the two Nodes to the graph.
346
347      /// Adds a new Edge connects the two Nodes to the graph.
348      ///
349      Edge addEdge(const Node& from, const Node& to) {
350        return INVALID;
351      }
352
353      template <typename _Graph>
354      struct Constraints {
355        void constraints() {
356          checkConcept<BaseGraphComponent, _Graph >();
357          typename _Graph::Node node_a, node_b;
358          node_a = graph.addNode();
359          typename _Graph::Edge edge;
360          edge = graph.addEdge(node_a, node_b);
361        }
362
363        _Graph& graph;
364      };
365    };
366
367    /// An empty erasable base graph class.
368 
369    /// This class provides beside the core graph features
370    /// core erase functions for the graph structure.
371    /// The most of the base graphs should be conform to this concept.
372    class BaseErasableGraphComponent : virtual public BaseGraphComponent {
373    public:
374
375      typedef BaseGraphComponent::Node Node;
376      typedef BaseGraphComponent::Edge Edge;
377
378      /// Erase a Node from the graph.
379     
380      /// Erase a Node from the graph. This function should not
381      /// erase edges connecting to the Node.
382      void erase(const Node&) {}   
383
384      /// Erase an Edge from the graph.
385
386      /// Erase an Edge from the graph.
387      ///
388      void erase(const Edge&) {}
389
390      template <typename _Graph>
391      struct Constraints {
392        void constraints() {
393          checkConcept<BaseGraphComponent, _Graph>();
394          typename _Graph::Node node;
395          graph.erase(node);
396          typename _Graph::Edge edge;
397          graph.erase(edge);
398        }
399
400        _Graph& graph;
401      };
402    };
403
404    /// An empty clearable base graph class.
405 
406    /// This class provides beside the core graph features
407    /// core clear functions for the graph structure.
408    /// The most of the base graphs should be conform to this concept.
409    class ClearableGraphComponent : virtual public BaseGraphComponent {
410    public:
411
412      /// Erase all the Nodes and Edges from the graph.
413
414      /// Erase all the Nodes and Edges from the graph.
415      ///
416      void clear() {}   
417
418      template <typename _Graph>
419      struct Constraints {
420        void constraints() {
421          checkConcept<BaseGraphComponent, _Graph>();
422          graph.clear();
423        }
424
425        _Graph graph;
426      };
427    };
428
429
430    /// Skeleton class for graph NodeIt and EdgeIt
431
432    /// Skeleton class for graph NodeIt and EdgeIt.
433    ///
434    template <typename _Graph, typename _Item>
435    class GraphIterator : public _Item {
436    public:
437      /// \todo Don't we need the Item type as typedef?
438
439      /// Default constructor.
440     
441      /// @warning The default constructor sets the iterator
442      /// to an undefined value.
443      GraphIterator() {}
444      /// Copy constructor.
445     
446      /// Copy constructor.
447      ///
448      GraphIterator(GraphIterator const&) {}
449      /// Sets the iterator to the first item.
450     
451      /// Sets the iterator to the first item of \c the graph.
452      ///
453      explicit GraphIterator(const _Graph&) {}
454      /// Invalid constructor \& conversion.
455
456      /// This constructor initializes the item to be invalid.
457      /// \sa Invalid for more details.
458      GraphIterator(Invalid) {}
459      /// Assign operator for items.
460
461      /// The items are assignable.
462      ///
463      GraphIterator& operator=(GraphIterator const&) { return *this; }     
464      /// Next item.
465
466      /// Assign the iterator to the next item.
467      ///
468      GraphIterator& operator++() { return *this; }
469      //        Node operator*() const { return INVALID; }
470      /// Equality operator
471
472      /// Two iterators are equal if and only if they point to the
473      /// same object or both are invalid.
474      bool operator==(const GraphIterator&) const { return true;}
475      /// Inequality operator
476       
477      /// \sa operator==(Node n)
478      ///
479      bool operator!=(const GraphIterator&) const { return true;}
480     
481      template<typename _GraphIterator>
482      struct Constraints {
483        void constraints() {
484          //      checkConcept< Item, _GraphIterator >();
485          _GraphIterator it1(g);
486       
487          /// \todo Do we need NodeIt(Node) kind of constructor?
488          //    _GraphIterator it2(bj);
489          _GraphIterator it2;
490
491          it2 = ++it1;
492          ++it2 = it1;
493          ++(++it1);
494          /// \bug This should be: is_base_and_derived<BaseItem, _GraphIterator>
495          _Item bi = it1;
496          bi = it2;
497        }
498        _Graph& g;
499      };
500    };
501
502    /// Skeleton class for graph InEdgeIt and OutEdgeIt
503
504    /// \note Because InEdgeIt and OutEdgeIt may not inherit from the same
505    /// base class, the _selector is a additional template parameter. For
506    /// InEdgeIt you should instantiate it with character 'i' and for
507    /// OutEdgeIt with 'o'.
508    /// \todo Is this a good name for this concept?
509    template <typename Graph,
510              typename Edge = typename Graph::Edge,
511              char _selector = '0'>
512    class GraphIncIterator : public Edge {
513    public:
514      /// Default constructor.
515     
516      /// @warning The default constructor sets the iterator
517      /// to an undefined value.
518      GraphIncIterator() {}
519      /// Copy constructor.
520     
521      /// Copy constructor.
522      ///
523      GraphIncIterator(GraphIncIterator const&) {}
524      /// Sets the iterator to the first edge incoming into or outgoing from the node.
525     
526      /// Sets the iterator to the first edge incoming into or outgoing from the node.
527      ///
528      explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
529      /// Invalid constructor \& conversion.
530
531      /// This constructor initializes the item to be invalid.
532      /// \sa Invalid for more details.
533      GraphIncIterator(Invalid) {}
534      /// Assign operator for nodes.
535
536      /// The nodes are assignable.
537      ///
538      GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }     
539      /// Next edge.
540
541      /// Assign the iterator to the next node.
542      ///
543      GraphIncIterator& operator++() { return *this; }
544
545      //        Node operator*() const { return INVALID; }
546
547      /// Equality operator
548
549      /// Two iterators are equal if and only if they point to the
550      /// same object or both are invalid.
551      bool operator==(const GraphIncIterator&) const { return true;}
552
553      /// Inequality operator
554       
555      /// \sa operator==(Node n)
556      ///
557      bool operator!=(const GraphIncIterator&) const { return true;}
558
559      template <typename _GraphIncIterator>
560      struct Constraints {
561        typedef typename Graph::Node Node;
562        void constraints() {
563          checkConcept<GraphItem<'e'>, _GraphIncIterator>();
564          _GraphIncIterator it1(graph, node);
565          /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
566          //    _GraphIncIterator it2(edge);
567          _GraphIncIterator it2;
568
569          it2 = ++it1;
570          ++it2 = it1;
571          ++(++it1);
572          Edge e = it1;
573          e = it2;
574        }
575
576        Edge& edge;
577        Node& node;
578        Graph& graph;
579      };
580    };
581
582
583    /// An empty iterable base graph class.
584 
585    /// This class provides beside the core graph features
586    /// iterator based iterable interface for the graph structure.
587    /// This concept is part of the StaticGraphConcept.
588    class IterableGraphComponent : virtual public BaseGraphComponent {
589
590    public:
591   
592      typedef IterableGraphComponent Graph;
593
594      typedef BaseGraphComponent::Node Node;
595      typedef BaseGraphComponent::Edge Edge;
596
597      /// This iterator goes through each node.
598
599      /// This iterator goes through each node.
600      ///
601      typedef GraphIterator<Graph, Node> NodeIt;
602      /// This iterator goes through each node.
603
604      /// This iterator goes through each node.
605      ///
606      typedef GraphIterator<Graph, Edge> EdgeIt;
607      /// This iterator goes trough the incoming edges of a node.
608
609      /// This iterator goes trough the \e inccoming edges of a certain node
610      /// of a graph.
611      typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
612      /// This iterator goes trough the outgoing edges of a node.
613
614      /// This iterator goes trough the \e outgoing edges of a certain node
615      /// of a graph.
616      typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
617    };
618   
619    template <typename _Graph>
620    struct Constraints {
621      void constraints() {
622        checkConcept< BaseGraphComponent, _Graph>();
623
624        checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
625        checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
626        checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
627        checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
628      }
629    };
630
631
632    template <typename Graph, typename Item, typename _Value>
633    class GraphMap : public ReadWriteMap<Item, _Value> {
634    protected:     
635      GraphMap() {}
636    public:
637      explicit GraphMap(const Graph&) {}
638      GraphMap(const Graph&, const _Value&) {}
639      GraphMap(const GraphMap&) {}
640     
641      GraphMap& operator=(const GraphMap&) { return *this;}
642
643      template<typename _Map>
644      struct Constraints {
645        void constraints() {
646          checkConcept<ReadWriteMap<Item, _Value>, _Map >();
647          // Construction with a graph parameter
648          _Map a(g);
649          // Constructor with a graph and a default value parameter
650          _Map a2(g,t);
651          // Copy constructor. Do we need it?
652          _Map b=c;
653          // Copy operator. Do we need it?
654          a=b;
655
656          ignore_unused_variable_warning(a2);
657        }
658
659        const _Map &c;
660        const Graph &g;
661        const typename GraphMap::Value &t;
662      };
663
664    };
665
666    /// An empty mappable base graph class.
667 
668    /// This class provides beside the core graph features
669    /// map interface for the graph structure.
670    /// This concept is part of the StaticGraphConcept.
671    class MappableGraphComponent : virtual public BaseGraphComponent {
672    public:
673
674      typedef MappableGraphComponent Graph;
675
676      typedef BaseGraphComponent::Node Node;
677      typedef BaseGraphComponent::Edge Edge;
678
679      /// ReadWrite map of the nodes.
680   
681      /// ReadWrite map of the nodes.
682      ///
683      template <typename _Value>
684      class NodeMap : public GraphMap<Graph, Node, _Value> {
685      private:
686        NodeMap();
687      public:
688        // \todo call the right parent class constructor
689        explicit NodeMap(const Graph&) {}
690        NodeMap(const Graph&, const _Value&) {}
691        NodeMap(const NodeMap&) {}
692
693        NodeMap& operator=(const NodeMap&) { return *this;}
694
695      };
696
697      /// ReadWrite map of the edges.
698   
699      /// ReadWrite map of the edges.
700      ///
701      template <typename _Value>
702      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
703      private:
704        EdgeMap();
705      public:
706        // \todo call the right parent class constructor
707        explicit EdgeMap(const Graph&) {}
708        EdgeMap(const Graph&, const _Value&) {}
709        EdgeMap(const EdgeMap&) {}
710
711        EdgeMap& operator=(const EdgeMap&) { return *this;}
712
713      };
714
715      template <typename _Graph>
716      struct Constraints {
717
718        struct Type {
719          int value;
720          Type() : value(0) {}
721          Type(int _v) : value(_v) {}
722        };
723
724        void constraints() {
725          checkConcept<BaseGraphComponent, _Graph>();
726          { // int map test
727            typedef typename _Graph::template NodeMap<int> IntNodeMap;
728            checkConcept<GraphMap<_Graph, typename _Graph::Node, int>, IntNodeMap >();
729          } { // bool map test
730            typedef typename _Graph::template NodeMap<bool> BoolNodeMap;
731            checkConcept<GraphMap<_Graph, typename _Graph::Node, bool>, BoolNodeMap >();
732          } { // Type map test
733            typedef typename _Graph::template NodeMap<Type> TypeNodeMap;
734            checkConcept<GraphMap<_Graph, typename _Graph::Node, Type>, TypeNodeMap >();
735          }
736
737          { // int map test
738            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
739            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>, IntEdgeMap >();
740          } { // bool map test
741            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
742            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>, BoolEdgeMap >();
743          } { // Type map test
744            typedef typename _Graph::template EdgeMap<Type> TypeEdgeMap;
745            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Type>, TypeEdgeMap >();
746          }
747        }
748
749        _Graph& graph;
750      };
751    };
752
753
754    class ExtendableGraphComponent : virtual public BaseGraphComponent {
755    public:
756
757      typedef ExtendableGraphComponent Graph;
758
759      typedef BaseGraphComponent::Node Node;
760      typedef BaseGraphComponent::Edge Edge;
761
762      Node addNode() {
763        return INVALID;
764      }
765   
766      Edge addEdge(const Node& from, const Node& to) {
767        return INVALID;
768      }
769
770      template <typename _Graph>
771      struct Constraints {
772        void constraints() {
773          checkConcept<BaseGraphComponent, _Graph >();
774          typename _Graph::Node node_a, node_b;
775          node_a = graph.addNode();
776          typename _Graph::Edge edge;
777          edge = graph.addEdge(node_a, node_b);     
778        }
779        _Graph& graph;
780      };
781    };
782    class ErasableGraphComponent : virtual public BaseGraphComponent {
783    public:
784
785      typedef ErasableGraphComponent Graph;
786
787      typedef BaseGraphComponent::Node Node;
788      typedef BaseGraphComponent::Edge Edge;
789
790      void erase(const Node&) {}   
791      void erase(const Edge&) {}
792
793      template <typename _Graph>
794      struct Constraints {
795        void constraints() {
796          checkConcept<BaseGraphComponent, _Graph >();
797          typename _Graph::Node node;
798          graph.erase(node);
799          typename _Graph::Edge edge;
800          graph.erase(edge);     
801        }
802
803        _Graph& graph;
804      };
805    };
806
807  }
808
809}
810
811#endif
Note: See TracBrowser for help on using the repository browser.