COIN-OR::LEMON - Graph Library

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

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

UndirGraph? implementation nearly complete

File size: 4.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * src/lemon/concept/undir_graph_component.h - Part of LEMON, a generic
4 * C++ optimization library
5 *
6 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi
7 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
8 * EGRES).
9 *
10 * Permission to use, modify and distribute this software is granted
11 * provided that this copyright notice appears in all copies. For
12 * precise terms see the accompanying LICENSE file.
13 *
14 * This software is provided "AS IS" with no warranty of any kind,
15 * express or implied, and with no claim as to its suitability for any
16 * purpose.
17 *
18 */
19
20///\ingroup concept
21///\file
22///\brief Undirected graphs and components of.
23
24
25#ifndef LEMON_CONCEPT_UNDIR_GRAPH_H
26#define LEMON_CONCEPT_UNDIR_GRAPH_H
27
28#include <lemon/concept/graph_component.h>
29
30namespace lemon {
31  namespace concept {
32
33    /// \todo to be done
34
35    struct BaseIterableUndirGraphConcept {
36
37      template <typename Graph>
38      struct Constraints {
39
40        typedef typename Graph::UndirEdge UndirEdge;
41        typedef typename Graph::Edge Edge;
42        typedef typename Graph::Node Node;
43
44        void constraints() {
45          checkConcept<BaseIterableGraphComponent, Graph>();
46          checkConcept<GraphItem<'u'>, UndirEdge >();
47
48          /// \bug this should be base_and_derived:
49          UndirEdge ue = e;
50          ue = e;
51
52          Node n;
53          n = graph.target(ue);
54          n = graph.source(ue);
55
56          graph.first(ue);
57          graph.next(ue);
58        }
59        const Graph &graph;
60        Edge e;
61      };
62
63    };
64
65
66    struct IterableUndirGraphConcept {
67
68      template <typename Graph>
69      struct Constraints {
70        void constraints() {
71          /// \todo we don't need the iterable component to be base iterable
72          /// Don't we really???
73          //checkConcept< BaseIterableUndirGraphConcept, Graph > ();
74
75          checkConcept<IterableGraphComponent, Graph> ();
76
77          typedef typename Graph::UndirEdge UndirEdge;
78          typedef typename Graph::UndirEdgeIt UndirEdgeIt;
79          typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
80
81          checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
82          checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
83        }
84      };
85
86    };
87
88    struct MappableUndirGraphConcept {
89
90      template <typename Graph>
91      struct Constraints {
92
93        struct Dummy {
94          int value;
95          Dummy() : value(0) {}
96          Dummy(int _v) : value(_v) {}
97        };
98
99        void constraints() {
100          checkConcept<MappableGraphComponent, Graph>();
101
102          typedef typename Graph::template UndirEdgeMap<int> IntMap;
103          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,
104            IntMap >();
105
106          typedef typename Graph::template UndirEdgeMap<bool> BoolMap;
107          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,
108            BoolMap >();
109
110          typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;
111          checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,
112            DummyMap >();
113        }
114      };
115
116    };
117
118    struct ExtendableUndirGraphConcept {
119
120      template <typename Graph>
121      struct Constraints {
122        void constraints() {
123          node_a = graph.addNode();
124          uedge = graph.addEdge(node_a, node_b);
125        }
126        typename Graph::Node node_a, node_b;
127        typename Graph::UndirEdge uedge;
128        Graph graph;
129      };
130
131    };
132
133    struct ErasableUndirGraphConcept {
134
135      template <typename Graph>
136      struct Constraints {
137        void constraints() {
138          graph.erase(n);
139          graph.erase(e);
140        }
141        Graph graph;
142        typename Graph::Node n;
143        typename Graph::UndirEdge e;
144      };
145
146    };
147
148    class UndirGraph {
149    public:
150
151      template <typename Graph>
152      struct Constraints {
153        void constraints() {
154          checkConcept<BaseIterableUndirGraphConcept, Graph>();
155          checkConcept<IterableUndirGraphConcept, Graph>();
156          checkConcept<MappableUndirGraphConcept, Graph>();
157        }
158      };
159
160    };
161
162    class ExtendableUndirGraph : public UndirGraph {
163    public:
164
165      template <typename Graph>
166      struct Constraints {
167        void constraints() {
168          checkConcept<BaseIterableUndirGraphConcept, Graph>();
169          checkConcept<IterableUndirGraphConcept, Graph>();
170          checkConcept<MappableUndirGraphConcept, Graph>();
171
172          checkConcept<UndirGraph, Graph>();
173          checkConcept<ExtendableUndirGraphConcept, Graph>();
174          checkConcept<ClearableGraphComponent, Graph>();
175        }
176      };
177
178    };
179
180    class ErasableUndirGraph : public ExtendableUndirGraph {
181    public:
182
183      template <typename Graph>
184      struct Constraints {
185        void constraints() {
186          checkConcept<ExtendableUndirGraph, Graph>();
187          checkConcept<ErasableUndirGraphConcept, Graph>();
188        }
189      };
190
191    };
192
193  }
194
195}
196
197#endif
Note: See TracBrowser for help on using the repository browser.