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

graph_maps.hxx
1/************************************************************************/
2/* */
3/* Copyright 2014 by Ullrich Koethe and Thorsten Beier */
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#ifndef VIGRA_GRAPH_MAPS
38#define VIGRA_GRAPH_MAPS
39
40/*vigra*/
41#include "multi_array.hxx"
42#include "graph_generalization.hxx"
43#include "graphs.hxx"
44
45
46 namespace vigra{
47
48// base class for basic implementation
49// of a class for node,edge and arc maps.
50 template<class T,class KEY,class REF,class CREF>
51 class DenseReferenceMap
52: public MultiArray<1,T>
53{
54 public:
55 typedef KEY Key;
56 typedef T Value;
57 typedef REF Reference;
58 typedef CREF ConstReference;
59
60 typedef Key key_type;
61 typedef Value value_type;
62 typedef Reference reference;
63 typedef ConstReference const_reference;
64 typedef boost_graph::read_write_property_map_tag category;
65
66
67 typedef typename MultiArray<1,T>::difference_type Shape1Type;
68
69 DenseReferenceMap()
70 : MultiArray<1,T>(){
71 }
72 DenseReferenceMap(const size_t maxKey)
73 : MultiArray<1,T>(Shape1Type(maxKey+1)){
74 }
75 DenseReferenceMap(const size_t maxKey,ConstReference value)
76 : MultiArray<1,T>(Shape1Type(maxKey+1),value){
77 }
78
79
80
81
82 ConstReference operator[](const KEY & key)const{
83 //return this->operator[](key.id());
84 return MultiArray<1,T>::operator()(key.id());
85 }
86 Reference operator[](const KEY & key){
87 return MultiArray<1,T>::operator()(key.id());
88 }
89
90 size_t size()const{
91 return this->shape(0);
92 }
93 protected:
94 void assign(const size_t maxKey){
95 this->reshape(Shape1Type(maxKey+1));
96 }
97 private:
98 // NONE
99};
100
101
102// basic implementation
103// of a class for node,edge and arc maps.
104 template<class GRAPH,class ITEM,class T,class REF,class CREF>
105 class DenseGraphItemReferenceMap
106: public DenseReferenceMap<T,ITEM,REF,CREF>
107{
108 typedef GRAPH Graph;
109 typedef ITEM Item;
110 typedef DenseReferenceMap<T,ITEM,REF,CREF> DenseReferenceMapType;
111 typedef GraphItemHelper<Graph,ITEM> ItemHelper;
112 typedef typename ItemHelper::ItemIt ItemIt;
113
114 public:
115 DenseGraphItemReferenceMap()
116 : DenseReferenceMapType(){
117
118 }
119 DenseGraphItemReferenceMap(const Graph & g)
120 : DenseReferenceMapType(ItemHelper::itemNum(g)==0 ? 0: ItemHelper::maxItemId(g) ){
121
122 }
123 DenseGraphItemReferenceMap(const Graph & g,typename DenseReferenceMapType::ConstReference)
124 : DenseReferenceMapType(ItemHelper::itemNum(g)==0 ? 0: ItemHelper::maxItemId(g)){
125
126 }
127 void assign(const Graph & g){
128 DenseReferenceMapType::assign(ItemHelper::itemNum(g)==0 ? 0: ItemHelper::maxItemId(g));
129 }
130};
131
132// basic class for node-maps
133 template<class GRAPH,class T,class REF= T & ,class CREF = const T & >
134 class DenseNodeReferenceMap
135: public DenseGraphItemReferenceMap<GRAPH,typename GRAPH::Node,T,REF,CREF>
136{
137 typedef typename GRAPH::Node Node;
138 typedef DenseGraphItemReferenceMap<GRAPH,Node,T,REF,CREF> DenseGraphItemReferenceMapType;
139 public:
140 DenseNodeReferenceMap()
141 : DenseGraphItemReferenceMapType(){
142 }
143 DenseNodeReferenceMap(const GRAPH & g)
144 : DenseGraphItemReferenceMapType(g){
145 }
146 DenseNodeReferenceMap(const GRAPH & g,typename DenseGraphItemReferenceMapType::ConstReference value)
147 : DenseGraphItemReferenceMapType(g,value){
148 }
149};
150
151// basic class for edge-maps
152 template<class GRAPH,class T,class REF= T & ,class CREF = const T & >
153 class DenseEdgeReferenceMap
154: public DenseGraphItemReferenceMap<GRAPH,typename GRAPH::Edge,T,REF,CREF>
155{
156 typedef typename GRAPH::Edge Edge;
157 typedef DenseGraphItemReferenceMap<GRAPH,Edge,T,REF,CREF> DenseGraphItemReferenceMapType;
158 public:
159 DenseEdgeReferenceMap()
160 : DenseGraphItemReferenceMapType(){
161 }
162 DenseEdgeReferenceMap(const GRAPH & g)
163 : DenseGraphItemReferenceMapType(g){
164 }
165 DenseEdgeReferenceMap(const GRAPH & g,typename DenseGraphItemReferenceMapType::ConstReference value)
166 : DenseGraphItemReferenceMapType(g,value){
167 }
168};
169
170// basic class for arc-maps
171 template<class GRAPH,class T,class REF= T & ,class CREF = const T & >
172 class DenseArcReferenceMap
173: public DenseGraphItemReferenceMap<GRAPH,typename GRAPH::Arc,T,REF,CREF>
174{
175 typedef typename GRAPH::Arc Arc;
176 typedef DenseGraphItemReferenceMap<GRAPH,Arc,T,REF,CREF> DenseGraphItemReferenceMapType;
177 public:
178 DenseArcReferenceMap()
179 : DenseGraphItemReferenceMapType(){
180 }
181 DenseArcReferenceMap(const GRAPH & g)
182 : DenseGraphItemReferenceMapType(g){
183 }
184 DenseArcReferenceMap(const GRAPH & g,typename DenseGraphItemReferenceMapType::ConstReference value)
185 : DenseGraphItemReferenceMapType(g,value){
186 }
187};
188
189// implicit edge map:
190// the values of a node map are converted
191// to an edge map.
192// FUNCTOR is used to convert the two
193// node map values corresponding to an edge to
194// an edge map value
195 template<class G,class NODE_MAP,class FUNCTOR,class RESULT>
196 class OnTheFlyEdgeMap{
197
198 public:
199 typedef G Graph;
200 typedef typename Graph::Node Node;
201 typedef NODE_MAP NodeMap;
202 typedef typename Graph::Edge Key;
203 typedef RESULT Value;
204 typedef RESULT ConstReference;
205
206 typedef Key key_type;
207 typedef Value value_type;
208 typedef ConstReference const_reference;
209
210 typedef boost_graph::readable_property_map_tag category;
211
212 OnTheFlyEdgeMap(const Graph & graph,const NodeMap & nodeMap,FUNCTOR & f)
213 : graph_(graph),
214 nodeMap_(nodeMap),
215 f_(f){
216 }
217
218 ConstReference operator[](const Key & key){
219 const Node u(graph_.u(key));
220 const Node v(graph_.v(key));
221 return f_(nodeMap_[u],nodeMap_[v]);
222 }
223
224 ConstReference operator[](const Key & key)const{
225 const Node u(graph_.u(key));
226 const Node v(graph_.v(key));
227 return f_(nodeMap_[u],nodeMap_[v]);
228 }
229 private:
230
231 const Graph & graph_;
232 const NodeMap & nodeMap_;
233 FUNCTOR & f_;
234};
235
236
237// node map that returns zero (specifically, <tt>RESULT()</tt>) for all keys
238 template<class G, class RESULT>
239 class ZeroNodeMap
240{
241 public:
242 typedef G Graph;
243 typedef typename Graph::Node Key;
244 typedef RESULT Value;
245 typedef RESULT ConstReference;
246
247 typedef Key key_type;
248 typedef Value value_type;
249 typedef ConstReference const_reference;
250 typedef boost_graph::readable_property_map_tag category;
251
252 ZeroNodeMap()
253 {}
254
255 value_type operator[](const Key &) const
256 {
257 return value_type();
258 }
259};
260
261
262
263 template<class T_OUT>
264 struct MeanFunctor{
265 template<class T>
266 T_OUT operator()(const T & a, const T & b)const{
267 return static_cast<T_OUT>(a+b)/static_cast<T_OUT>(2.0);
268 }
269
270};
271
272
273// implicit edge map:
274// the values of a node map are converted
275// to an edge map.
276// FUNCTOR is used to convert the two
277// node map values corresponding to an edge to
278// an edge map value
279 template<class G,class NODE_MAP,class FUNCTOR,class RESULT>
280 class OnTheFlyEdgeMap2{
281
282 public:
283 typedef G Graph;
284 typedef typename Graph::Node Node;
285 typedef NODE_MAP NodeMap;
286 typedef typename Graph::Edge Key;
287 typedef RESULT Value;
288 typedef RESULT ConstReference;
289
290 typedef Key key_type;
291 typedef Value value_type;
292 typedef ConstReference const_reference;
293
294 typedef boost_graph::readable_property_map_tag category;
295
296 OnTheFlyEdgeMap2(const Graph & graph,const NodeMap & nodeMap,FUNCTOR f)
297 : graph_(graph),
298 nodeMap_(nodeMap),
299 f_(f){
300 }
301
302 ConstReference operator[](const Key & key){
303 const Node u(graph_.u(key));
304 const Node v(graph_.v(key));
305 return f_(nodeMap_[u],nodeMap_[v]);
306 }
307
308 ConstReference operator[](const Key & key)const{
309 const Node u(graph_.u(key));
310 const Node v(graph_.v(key));
311 return f_(nodeMap_[u],nodeMap_[v]);
312 }
313 private:
314
315 const Graph & graph_;
316 const NodeMap nodeMap_;
317 FUNCTOR f_;
318};
319
320
321// convert 2 edge maps with a functor into a single edge map
322 template<class G,class EDGE_MAP_A,class EDGE_MAP_B,class FUNCTOR,class RESULT>
323 class BinaryOpEdgeMap{
324 public:
325 typedef G Graph;
326 typedef typename Graph::Edge Key;
327 typedef RESULT Value;
328 typedef RESULT ConstReference;
329
330 typedef Key key_type;
331 typedef Value value_type;
332 typedef ConstReference const_reference;
333
334 typedef boost_graph::readable_property_map_tag category;
335
336 BinaryOpEdgeMap(const Graph & graph,const EDGE_MAP_A & edgeMapA,const EDGE_MAP_B & edgeMapB,FUNCTOR & f)
337 : graph_(graph),
338 edgeMapA_(edgeMapA),
339 edgeMapB_(edgeMapB),
340 f_(f){
341 }
342 ConstReference operator[](const Key & key){
343 return f_(edgeMapA_[key],edgeMapB_[key]);
344 }
345 ConstReference operator[](const Key & key)const{
346 return f_(edgeMapA_[key],edgeMapB_[key]);
347 }
348 private:
349
350 const Graph & graph_;
351 const EDGE_MAP_A & edgeMapA_;
352 const EDGE_MAP_B & edgeMapB_;
353 FUNCTOR & f_;
354};
355
356
357
358// encapsulate a MultiArrayView indexed by node/edge ID
359 template<class T,class GRAPH, class KEY>
360 struct ArrayMap{
361
362 typedef MultiArrayView<1, T> View;
363 typedef KEY Key;
364 typedef typename View::value_type Value;
365 typedef typename View::const_reference ConstReference;
366 typedef typename View::reference Reference;
367
368 ArrayMap(const GRAPH & graph)
369 : graph_(graph),
370 view_(){
371 }
372
373 ArrayMap(const GRAPH & graph, const View & view)
374 : graph_(graph),
375 view_(view){
376 }
377
378 void setArray(const MultiArrayView<1, T> & view){
379 view_ = view;
380 }
381
382 Reference operator[](const Key & key){
383 return view_(graph_.id(key));
384 }
385
386 ConstReference operator[](const Key & key)const{
387 return view_(graph_.id(key));
388 }
389 const GRAPH & graph_;
390 MultiArrayView<1, T> view_;
391
392};
393
394
395
396
397} // end namespace vigra
398
399#endif // VIGRA_GRAPH_MAPS
vigra::MultiArrayView< 1, T >::value_type
T value_type
Definition multi_array.hxx:719
vigra::MultiArrayView< N, vigra::detail::ResolveMultiband< T >::type, vigra::detail::ResolveMultiband< T >::Stride >::shape
const difference_type & shape() const
Definition multi_array.hxx:1650
vigra::MultiArrayView< N, vigra::detail::ResolveMultiband< T >::type, vigra::detail::ResolveMultiband< T >::Stride >::operator()
reference operator()(difference_type_1 x)
Definition multi_array.hxx:1123
vigra::MultiArrayView< 1, T >::reference
value_type & reference
Definition multi_array.hxx:723
vigra::MultiArrayView< N, vigra::detail::ResolveMultiband< T >::type, vigra::detail::ResolveMultiband< T >::Stride >::size
difference_type_1 size() const
Definition multi_array.hxx:1643
vigra::MultiArrayView< 1, T >::const_reference
const value_type & const_reference
Definition multi_array.hxx:727
vigra::MultiArray
Main MultiArray class containing the memory management.
Definition multi_array.hxx:2483
vigra::MultiArray< 1, T >::reshape
void reshape(const difference_type &shape)
Definition multi_array.hxx:2867
vigra::MultiArray< 1, T >::MultiArray
MultiArray()
Definition multi_array.hxx:2594
vigra

© 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.12.4