[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

graphs.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2011-2012 Stefan Schmidt and Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35
36 /**
37 * This header provides definitions of graph-related types
38 * and optionally provides a gateway to popular graph libraries
39 * (for now, BGL is supported).
40 */
41
42 #ifndef VIGRA_GRAPH_HXX
43 #define VIGRA_GRAPH_HXX
44
45 #include "metaprogramming.hxx"
46 #include "tinyvector.hxx"
47
48 #ifdef WITH_BOOST_GRAPH
49
50 # include <boost/tuple/tuple.hpp>
51 # include <boost/graph/graph_traits.hpp>
52 # include <boost/graph/properties.hpp>
53
54 namespace vigra {
55 namespace boost_graph {
56
57 // vigra::boost_graph contains algorithms that are compatible to the Boost Graph Library
58 using namespace boost;
59
60 }} // namespace vigra::boost_graph
61
62 #else // not WITH_BOOST_GRAPH
63
64 // emulate the BGL-style interface
65 namespace vigra {
66 namespace boost_graph {
67
68 struct no_property {};
69
70 // tag classes were copied from boost:
71 // directed_category tags
72 struct directed_tag { };
73 struct undirected_tag { };
74 struct bidirectional_tag : public directed_tag { };
75
76 // traversal_category tags
77 struct incidence_graph_tag { };
78 struct adjacency_graph_tag { };
79 struct bidirectional_graph_tag : public incidence_graph_tag { };
80 struct vertex_list_graph_tag { };
81 struct edge_list_graph_tag { };
82 struct adjacency_matrix_tag { };
83
84 // edge_parallel_category tags
85 struct allow_parallel_edge_tag { };
86 struct disallow_parallel_edge_tag { };
87
88 // property maps:
89 struct readable_property_map_tag { };
90 struct writable_property_map_tag { };
91 struct read_write_property_map_tag
92 : public readable_property_map_tag,
93 public writable_property_map_tag {};
94 struct lvalue_property_map_tag
95 : public read_write_property_map_tag {};
96
97 struct vertex_index_t {};
98
99 struct edge_property_tag {};
100
101 // tie() support for std::pair, similar to Boost's one:
102 // (necessary because std::pair doesn't define a suitable assignment operator)
103 template<class T1, class T2>
104 class tie_adapter
105 {
106 public:
107 tie_adapter(T1 &x, T2 &y)
108 : x_(x), y_(y)
109 {}
110
111 template<class X, class Y>
112 tie_adapter & operator=(const std::pair<X, Y> &pair)
113 {
114 x_ = pair.first;
115 y_ = pair.second;
116 return *this;
117 }
118
119 protected:
120 T1 &x_;
121 T2 &y_;
122 };
123
124 template<class T1, class T2>
125 inline
126 tie_adapter<T1, T2>
127 tie(T1& t1, T2& t2)
128 {
129 return tie_adapter<T1, T2>(t1, t2);
130 }
131
132 // graph_traits class template
133 template <typename G>
134 struct graph_traits {
135 typedef typename G::vertex_descriptor vertex_descriptor;
136 typedef typename G::edge_descriptor edge_descriptor;
137 typedef typename G::adjacency_iterator adjacency_iterator;
138 typedef typename G::out_edge_iterator out_edge_iterator;
139 typedef typename G::in_edge_iterator in_edge_iterator;
140 typedef typename G::vertex_iterator vertex_iterator;
141 typedef typename G::edge_iterator edge_iterator;
142
143 typedef typename G::directed_category directed_category;
144 typedef typename G::edge_parallel_category edge_parallel_category;
145 typedef typename G::traversal_category traversal_category;
146
147 typedef typename G::vertices_size_type vertices_size_type;
148 typedef typename G::edges_size_type edges_size_type;
149 typedef typename G::degree_size_type degree_size_type;
150
151 static inline vertex_descriptor null_vertex()
152 {
153 return vertex_descriptor(-1);
154 }
155 };
156
157 // property_traits class template
158 template <typename PropMap>
159 struct property_traits
160 {
161 typedef typename PropMap::key_type key_type;
162 typedef typename PropMap::value_type value_type;
163 typedef typename PropMap::reference reference;
164 typedef typename PropMap::category category;
165 };
166
167 }} // namespace vigra::boost_graph
168
169 #endif // WITH_BOOST_GRAPH
170
171 #ifdef WITH_LEMON
172 # include <lemon/core.h>
173 #else // not WITH_LEMON
174
175 // emulate the lemon interface
176 namespace lemon {
177
178 struct Invalid {
179 public:
180 bool operator==(Invalid) const { return true; }
181 bool operator!=(Invalid) const { return false; }
182 bool operator< (Invalid) const { return false; }
183
184 template <class T, int N>
185 operator vigra::TinyVector<T, N>() const
186 {
187 return vigra::TinyVector<T, N>(-1);
188 }
189 };
190
191 static const Invalid INVALID = Invalid();
192
193 typedef vigra::VigraTrueType True;
194 typedef vigra::VigraFalseType False;
195
196 } // namespace lemon
197
198 #endif // WITH_LEMON
199
200 namespace lemon {
201
202 template <class T>
203 inline bool operator==(T const & t, Invalid)
204 {
205 return t == T(Invalid());
206 }
207
208 template <class T>
209 inline bool operator==(Invalid, T const & t)
210 {
211 return t == T(Invalid());
212 }
213
214 template <class T>
215 inline bool operator!=(T const & t, Invalid)
216 {
217 return t != T(Invalid());
218 }
219
220 template <class T>
221 inline bool operator!=(Invalid, T const & t)
222 {
223 return t != T(Invalid());
224 }
225
226 } // namespace lemon
227
228 namespace vigra {
229
230
231 template<class GRAPH,class ITEM>
232 struct GraphItemHelper;
233
234 template<class GRAPH>
235 struct GraphItemHelper<GRAPH,typename GRAPH::Edge>{
236 typedef typename GRAPH::index_type index_type ;
237 typedef typename GRAPH::Edge Item;
238 typedef typename GRAPH::EdgeIt ItemIt;
239
240
241 static index_type maxItemId(const GRAPH & g){
242 return g.maxEdgeId();
243 }
244 static index_type itemNum(const GRAPH & g){
245 return g.edgeNum();
246 }
247 static Item itemFromId(const GRAPH & g,const index_type id){
248 return g.edgeFromId(id);
249 }
250
251 };
252
253 template<class GRAPH>
254 struct GraphItemHelper<GRAPH,typename GRAPH::Node>{
255 typedef typename GRAPH::index_type index_type ;
256 typedef typename GRAPH::Node Item;
257 typedef typename GRAPH::NodeIt ItemIt;
258
259
260 static index_type maxItemId(const GRAPH & g){
261 return g.maxNodeId();
262 }
263 static index_type itemNum(const GRAPH & g){
264 return g.nodeNum();
265 }
266 static Item itemFromId(const GRAPH & g,const index_type id){
267 return g.nodeFromId(id);
268 }
269 };
270
271
272 template<class GRAPH>
273 struct GraphItemHelper<GRAPH,typename GRAPH::Arc>{
274 typedef typename GRAPH::index_type index_type ;
275 typedef typename GRAPH::Arc Item;
276 typedef typename GRAPH::ArcIt ItemIt;
277
278
279 static index_type maxItemId(const GRAPH & g){
280 return g.maxArcId();
281 }
282 static index_type itemNum(const GRAPH & g){
283 return g.arcNum();
284 }
285 static Item itemFromId(const GRAPH & g,const index_type id){
286 return g.arcFromId(id);
287 }
288 };
289
290
291
292
293
294 namespace lemon_graph {
295
296 // vigra::lemon_graph contains algorithms that are compatible to the LEMON graph library
297 using namespace lemon;
298
299 }} // namespace vigra::lemon_graph
300
301 #endif // VIGRA_GRAPH_HXX
boost
Definition: adjacency_list_graph.hxx:1087
vigra
Definition: accessor.hxx:43
lemon
Definition: graphs.hxx:176
vigra::operator!=
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition: fftw3.hxx:841
vigra::operator==
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition: fftw3.hxx:825
vigra::TinyVector< T, N >
vigra::operator<
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition: fixedpoint.hxx:512

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.0