COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/skeletons/graph_component.h @ 950:d74557d1f100

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