COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/concept/graph_component.h @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

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