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

graph_generalization.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_GENERALIZATION_HXX
43#define VIGRA_GRAPH_GENERALIZATION_HXX
44
45
46#include "graphs.hxx"
47#include "multi_gridgraph.hxx"
48namespace vigra{
49
50
51
52 template<class MAP>
53 struct GraphMapTypeTraits{
54 typedef typename MAP::value_type Value;
55 typedef typename MAP::reference Reference;
56 typedef typename MAP::const_reference ConstReference;
57 };
58
59 // generalizes the iterator begin end accessed
60 // since grid graph has no constructor
61 // for INVALID
62 template<class GRAPH>
63 struct GraphIteratorAccessor{
64 typedef GRAPH Graph;
65 typedef typename Graph::Node Node;
66 typedef typename Graph::NodeIt NodeIt;
67 typedef typename Graph::EdgeIt EdgeIt;
68 typedef typename Graph::ArcIt ArcIt;
69 typedef typename Graph::OutArcIt OutArcIt;
70 typedef typename Graph::IncEdgeIt IncEdgeIt;
71
72 static NodeIt nodesBegin(const Graph & g){ return NodeIt(g);}
73 static EdgeIt edgesBegin(const Graph & g){ return EdgeIt(g);}
74 static ArcIt arcsBegin( const Graph & g){ return ArcIt( g);}
75 static OutArcIt outArcBegin(const Graph & g,const Node & node){
76 return OutArcIt(g,node);
77 }
78 static IncEdgeIt incEdgeBegin(const Graph & g,const Node & node){
79 return IncEdgeIt(g,node);
80 }
81
82
83 static NodeIt nodesEnd(const Graph &){ return NodeIt(lemon::INVALID);}
84 static EdgeIt edgesEnd(const Graph &){ return EdgeIt(lemon::INVALID);}
85 static ArcIt arcsEnd( const Graph &){ return ArcIt( lemon::INVALID);}
86 static OutArcIt outArcEnd(const Graph &,const Node &){
87 return OutArcIt(lemon::INVALID);
88 }
89 static IncEdgeIt incEdgeEnd(const Graph &,const Node &){
90 return IncEdgeIt(lemon::INVALID);
91 }
92 };
93
94 // generalizes the iterator begin end accessed
95 // since grid graph has no constructor
96 // for INVALID
97 template<unsigned int DIM,class DIRECTED_TAG>
98 struct GraphIteratorAccessor<GridGraph<DIM,DIRECTED_TAG> >{
99 typedef GridGraph<DIM,DIRECTED_TAG> Graph;
100 typedef typename Graph::Node Node;
101 typedef typename Graph::NodeIt NodeIt;
102 typedef typename Graph::EdgeIt EdgeIt;
103 typedef typename Graph::ArcIt ArcIt;
104 typedef typename Graph::OutArcIt OutArcIt;
105 typedef typename Graph::IncEdgeIt IncEdgeIt;
106
107 static NodeIt nodesBegin(const Graph & g){ return NodeIt(g);}
108 static EdgeIt edgesBegin(const Graph & g){ return g.get_edge_iterator();}
109 static ArcIt arcsBegin( const Graph & g){ return ArcIt( g);}
110 static OutArcIt outArcBegin(const Graph & g,const Node & node){
111 return g.get_out_edge_iterator(node);
112 }
113 static IncEdgeIt incEdgeBegin(const Graph & g,const Node & node){
114 return IncEdgeIt(g,node);
115 }
116
117 static NodeIt nodesEnd(const Graph & g){ return g.get_vertex_end_iterator();}
118 static EdgeIt edgesEnd(const Graph & g){ return g.get_edge_end_iterator();}
119 static ArcIt arcsEnd( const Graph & g){ return g.get_arc_end_iterator(); }
120 static OutArcIt outArcEnd(const Graph & g,const Node & node){
121 return g.get_out_edge_end_iterator(node);
122 }
123 static IncEdgeIt incEdgeEnd(const Graph &,const Node &){
124 return IncEdgeIt(lemon::INVALID);
125 }
126 };
127
128
129 // shape of graphs node,edge,arc-maps
130 template<class GRAPH>
131 class IntrinsicGraphShape{
132 private:
133 typedef GRAPH Graph;
134 typedef typename vigra::MultiArray<1,int>::difference_type DiffType1d;
135 typedef typename Graph::index_type index_type;
136 public:
137 typedef typename Graph::Node Node ;
138 typedef typename Graph::Edge Edge ;
139 typedef typename Graph::Arc Arc ;
140
141 typedef DiffType1d IntrinsicNodeMapShape;
142 typedef DiffType1d IntrinsicEdgeMapShape;
143 typedef DiffType1d IntrinsicArcMapShape;
144
145 static IntrinsicNodeMapShape intrinsicNodeMapShape(const Graph & g){
146 return IntrinsicNodeMapShape(g.maxNodeId()+1);
147 }
148 static IntrinsicEdgeMapShape intrinsicEdgeMapShape(const Graph & g){
149 return IntrinsicEdgeMapShape(g.maxEdgeId()+1);
150 }
151 static IntrinsicArcMapShape intrinsicArcMapShape(const Graph & g){
152 return IntrinsicArcMapShape(g.maxArcId()+1);
153 }
154
155
156 static const unsigned int IntrinsicNodeMapDimension=1;
157 static const unsigned int IntrinsicEdgeMapDimension=1;
158 static const unsigned int IntrinsicArcMapDimension=1;
159 };
160 // shape of graphs node,edge,arc-maps
161 template<unsigned int DIM,class DIRECTED_TAG>
162 class IntrinsicGraphShape<GridGraph<DIM,DIRECTED_TAG> >{
163 private:
164 typedef GridGraph<DIM,DIRECTED_TAG> Graph;
165 typedef typename Graph::index_type index_type;
166 public:
167 typedef typename Graph::Node Node ;
168 typedef typename Graph::Edge Edge ;
169 typedef typename Graph::Arc Arc ;
170
171 typedef typename Graph::shape_type IntrinsicNodeMapShape;
172 typedef typename Graph::edge_propmap_shape_type IntrinsicEdgeMapShape;
173 typedef typename Graph::edge_propmap_shape_type IntrinsicArcMapShape;
174
175 static IntrinsicNodeMapShape intrinsicNodeMapShape(const Graph & g){
176 return g.shape();
177 }
178 static IntrinsicEdgeMapShape intrinsicEdgeMapShape(const Graph & g){
179 return g.edge_propmap_shape();
180 }
181 static IntrinsicArcMapShape intrinsicArcMapShape(const Graph & g){
182 return g.arc_propmap_shape();
183 }
184 static const unsigned int IntrinsicNodeMapDimension=DIM;
185 static const unsigned int IntrinsicEdgeMapDimension=DIM+1;
186 static const unsigned int IntrinsicArcMapDimension=DIM+1;
187 };
188
189 // convert a descriptor to an multi_array index w.r.t.
190 // an node/edge/arc map
191 template<class GRAPH>
192 class GraphDescriptorToMultiArrayIndex{
193 private:
194 typedef GRAPH Graph;
195 typedef typename Graph::index_type index_type;
196 public:
197 typedef typename Graph::Node Node ;
198 typedef typename Graph::Edge Edge ;
199 typedef typename Graph::Arc Arc ;
200
201 typedef typename IntrinsicGraphShape<Graph>::IntrinsicNodeMapShape IntrinsicNodeMapShape;
202 typedef typename IntrinsicGraphShape<Graph>::IntrinsicEdgeMapShape IntrinsicEdgeMapShape;
203 typedef typename IntrinsicGraphShape<Graph>::IntrinsicArcMapShape IntrinsicArcMapShape;
204
205 static IntrinsicNodeMapShape intrinsicNodeCoordinate(const Graph & g,const Node & node){
206 return IntrinsicNodeMapShape(g.id(node));
207 }
208 static IntrinsicEdgeMapShape intrinsicEdgeCoordinate(const Graph & g,const Edge & edge){
209 return IntrinsicEdgeMapShape(g.id(edge));
210 }
211 static IntrinsicArcMapShape intrinsicArcCoordinate(const Graph & g,const Arc & arc){
212 return IntrinsicArcMapShape(g.id(arc));
213 }
214
215 };
216
217 // convert a descriptor to an multi_array index w.r.t.
218 // an node/edge/arc map
219 template<unsigned int DIM,class DIRECTED_TAG>
220 class GraphDescriptorToMultiArrayIndex<GridGraph<DIM,DIRECTED_TAG> >{
221 private:
222 typedef GridGraph<DIM,DIRECTED_TAG> Graph;
223 typedef typename Graph::index_type index_type;
224 public:
225 typedef typename Graph::Node Node ;
226 typedef typename Graph::Edge Edge ;
227 typedef typename Graph::Arc Arc ;
228
229 typedef typename IntrinsicGraphShape<Graph>::IntrinsicNodeMapShape IntrinsicNodeMapShape;
230 typedef typename IntrinsicGraphShape<Graph>::IntrinsicEdgeMapShape IntrinsicEdgeMapShape;
231 typedef typename IntrinsicGraphShape<Graph>::IntrinsicArcMapShape IntrinsicArcMapShape;
232
233
234 static Node intrinsicNodeCoordinate(const Graph &,const Node & node){
235 return node;
236 }
237 static Edge intrinsicEdgeCoordinate(const Graph &,const Edge & edge){
238 return edge;
239 }
240 static Arc intrinsicArcCoordinate (const Graph &,const Arc & arc){
241 return arc;
242 }
243
244 };
245
246
247
248
249
250} // namespace vigra
251
252#endif // VIGRA_GRAPH_GENERALIZATION_HXX
Define a grid graph in arbitrary dimensions.
Definition multi_gridgraph.hxx:1429
view_type::difference_type difference_type
Definition multi_array.hxx:2524

© 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.1 (Thu Feb 27 2025)