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

graph_generalization.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_GENERALIZATION_HXX
43 #define VIGRA_GRAPH_GENERALIZATION_HXX
44 
45 
46 #include "graphs.hxx"
47 #include "multi_gridgraph.hxx"
48 namespace 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
vigra::MultiArray::difference_type
view_type::difference_type difference_type
Definition: multi_array.hxx:2522
vigra::boost_graph::edge
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_descriptor, bool > edge(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &u, typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return the pair (edge_descriptor, true) when an edge between vertices u and v exists, or (lemon::INVALID, false) otherwise (API: boost).
Definition: multi_gridgraph.hxx:2990

© 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.1 (Fri May 19 2017)