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

graphs.hxx VIGRA

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 #else // not WITH_BOOST_GRAPH
55 
56 // emulate the BGL-style interface
57 namespace boost {
58 
59 struct no_property {};
60 
61 // tag classes were copied from boost:
62 // directed_category tags
63 struct directed_tag { };
64 struct undirected_tag { };
65 struct bidirectional_tag : public directed_tag { };
66 
67 // traversal_category tags
68 struct incidence_graph_tag { };
69 struct adjacency_graph_tag { };
70 struct bidirectional_graph_tag : public incidence_graph_tag { };
71 struct vertex_list_graph_tag { };
72 struct edge_list_graph_tag { };
73 struct adjacency_matrix_tag { };
74 
75 // edge_parallel_category tags
76 struct allow_parallel_edge_tag { };
77 struct disallow_parallel_edge_tag { };
78 
79 // property maps:
80 struct readable_property_map_tag { };
81 struct writable_property_map_tag { };
82 struct read_write_property_map_tag
83  : public readable_property_map_tag,
84  public writable_property_map_tag {};
85 struct lvalue_property_map_tag
86  : public read_write_property_map_tag {};
87 
88 struct vertex_index_t {};
89 
90 struct edge_property_tag {};
91 
92 #ifndef BOOST_TUPLE_HPP
93 
94 // tie() support for std::pair, similar to Boost's one:
95 // (necessary because std::pair doesn't define a suitable assignment operator)
96 template<class T1, class T2>
97 class tie_adapter
98 {
99  public:
100  tie_adapter(T1 &x, T2 &y)
101  : x_(x), y_(y)
102  {}
103 
104  template<class X, class Y>
105  tie_adapter & operator=(const std::pair<X, Y> &pair)
106  {
107  x_ = pair.first;
108  y_ = pair.second;
109  return *this;
110  }
111 
112  protected:
113  T1 &x_;
114  T2 &y_;
115 };
116 
117 template<class T1, class T2>
118 inline
119 tie_adapter<T1, T2>
120 tie(T1& t1, T2& t2)
121 {
122  return tie_adapter<T1, T2>(t1, t2);
123 }
124 #endif
125 
126 // graph_traits class template
127 template <typename G>
128 struct graph_traits {
129  typedef typename G::vertex_descriptor vertex_descriptor;
130  typedef typename G::edge_descriptor edge_descriptor;
131  typedef typename G::adjacency_iterator adjacency_iterator;
132  typedef typename G::out_edge_iterator out_edge_iterator;
133  typedef typename G::in_edge_iterator in_edge_iterator;
134  typedef typename G::vertex_iterator vertex_iterator;
135  typedef typename G::edge_iterator edge_iterator;
136 
137  typedef typename G::directed_category directed_category;
138  typedef typename G::edge_parallel_category edge_parallel_category;
139  typedef typename G::traversal_category traversal_category;
140 
141  typedef typename G::vertices_size_type vertices_size_type;
142  typedef typename G::edges_size_type edges_size_type;
143  typedef typename G::degree_size_type degree_size_type;
144 
145  static inline vertex_descriptor null_vertex()
146  {
147  return vertex_descriptor(-1);
148  }
149 };
150 
151 // property_traits class template
152 template <typename PropMap>
153 struct property_traits
154 {
155  typedef typename PropMap::key_type key_type;
156  typedef typename PropMap::value_type value_type;
157  typedef typename PropMap::reference reference;
158  typedef typename PropMap::category category;
159 };
160 
161 } // namespace boost
162 
163 #endif // WITH_BOOST_GRAPH
164 
165 namespace vigra {
166 namespace boost_graph {
167 
168 // vigra::boost_graph contains algorithms that are compatible to the Boost Graph Library
169 using namespace boost;
170 
171 }} // namespace vigra::boost_graph
172 
173 
174 
175 
176 #if 0
177 namespace vigragraph {
178 
179 // custom get_helper for read-only property maps (by-value)
180 
181 template <class ValueType, class ReadablePropertyMap>
182 struct get_helper { };
183 
184 template <class PropertyMap, class ValueType, class K>
185 inline ValueType
186 get(const get_helper<ValueType, PropertyMap>& pa, const K& k)
187 {
188  const ValueType v = static_cast<const PropertyMap&>(pa)[k];
189  return v;
190 }
191 
192 
193 // ! A fallback template for adjacent_vertices() called with
194 // a vertex_iterator
195 // (which may be specialized to be implemented more efficiently;
196 // the reason is that the iterator may have more information than
197 // the plain vertex_descriptor, e.g. it knows the neighborhood
198 // already which otherwise needs to be reconstructed.)
199 template<class GRAPH>
200 inline
201 std::pair<typename graph_traits<GRAPH>::adjacency_iterator,
202  typename graph_traits<GRAPH>::adjacency_iterator >
203 adjacent_vertices_at_iterator(typename graph_traits<GRAPH>::vertex_iterator const &v,
204  GRAPH const &g)
205 {
206  // the default implementation just derefences the iterator
207  // to yield a vertex_descriptor and forwards the call
208  std::cout << "FB" << std::endl;
209  return adjacent_vertices(*v, g);
210 }
211 
212 } // namespace vigragraph
213 #endif
214 
215 #ifdef WITH_LEMON
216 # include <lemon/core.h>
217 #else // not WITH_LEMON
218 
219 // emulate the lemon interface
220 namespace lemon {
221 
222 struct Invalid {
223  public:
224  bool operator==(Invalid) const { return true; }
225  bool operator!=(Invalid) const { return false; }
226  bool operator< (Invalid) const { return false; }
227 
228  template <class T, int N>
229  operator vigra::TinyVector<T, N>() const
230  {
231  return vigra::TinyVector<T, N>(-1);
232  }
233 };
234 
235 static const Invalid INVALID = Invalid();
236 
237 typedef vigra::VigraTrueType True;
238 typedef vigra::VigraFalseType False;
239 
240 } // namespace lemon
241 
242 #endif // WITH_LEMON
243 
244 namespace lemon {
245 
246 template <class T>
247 inline bool operator==(T const & t, Invalid)
248 {
249  return t == T(Invalid());
250 }
251 
252 template <class T>
253 inline bool operator==(Invalid, T const & t)
254 {
255  return t == T(Invalid());
256 }
257 
258 template <class T>
259 inline bool operator!=(T const & t, Invalid)
260 {
261  return t != T(Invalid());
262 }
263 
264 template <class T>
265 inline bool operator!=(Invalid, T const & t)
266 {
267  return t != T(Invalid());
268 }
269 
270 } // namespace lemon
271 
272 namespace vigra {
273 
274 
275 template<class GRAPH,class ITEM>
276 struct GraphItemHelper;
277 
278 template<class GRAPH>
279 struct GraphItemHelper<GRAPH,typename GRAPH::Edge>{
280  typedef typename GRAPH::index_type index_type ;
281  typedef typename GRAPH::Edge Item;
282  typedef typename GRAPH::EdgeIt ItemIt;
283 
284 
285  static index_type maxItemId(const GRAPH & g){
286  return g.maxEdgeId();
287  }
288  static index_type itemNum(const GRAPH & g){
289  return g.edgeNum();
290  }
291  static Item itemFromId(const GRAPH & g,const index_type id){
292  return g.edgeFromId(id);
293  }
294 
295 };
296 
297 template<class GRAPH>
298 struct GraphItemHelper<GRAPH,typename GRAPH::Node>{
299  typedef typename GRAPH::index_type index_type ;
300  typedef typename GRAPH::Node Item;
301  typedef typename GRAPH::NodeIt ItemIt;
302 
303 
304  static index_type maxItemId(const GRAPH & g){
305  return g.maxNodeId();
306  }
307  static index_type itemNum(const GRAPH & g){
308  return g.nodeNum();
309  }
310  static Item itemFromId(const GRAPH & g,const index_type id){
311  return g.nodeFromId(id);
312  }
313 };
314 
315 
316 template<class GRAPH>
317 struct GraphItemHelper<GRAPH,typename GRAPH::Arc>{
318  typedef typename GRAPH::index_type index_type ;
319  typedef typename GRAPH::Arc Item;
320  typedef typename GRAPH::ArcIt ItemIt;
321 
322 
323  static index_type maxItemId(const GRAPH & g){
324  return g.maxArcId();
325  }
326  static index_type itemNum(const GRAPH & g){
327  return g.arcNum();
328  }
329  static Item itemFromId(const GRAPH & g,const index_type id){
330  return g.arcFromId(id);
331  }
332 };
333 
334 
335 
336 
337 
338 namespace lemon_graph {
339 
340 // vigra::lemon_graph contains algorithms that are compatible to the LEMON graph library
341 using namespace lemon;
342 
343 }} // namespace vigra::lemon_graph
344 
345 #endif // VIGRA_GRAPH_HXX

© 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.10.0 (Thu Jan 8 2015)