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

multi_gridgraph.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2011-2012 by 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 #ifndef VIGRA_MULTI_GRIDGRAPH_HXX
37 #define VIGRA_MULTI_GRIDGRAPH_HXX
38 
39 #include "multi_iterator.hxx"
40 #include "multi_array.hxx"
41 #include "graphs.hxx"
42 
43 template <unsigned int N>
44 struct NeighborhoodTests;
45 
46 namespace vigra {
47 
48 /** \addtogroup GraphDataStructures Graph Data Structures
49 
50  A GridGraph class implementing the APIs of the <a href="http://www.boost.org/doc/libs/release/libs/graph/">boost::graph</a> and
51  <a href="http://lemon.cs.elte.hu/">LEMON</a> libraries. See also
52  the \ref BoostGraphExtensions.
53 */
54 //@{
55 
56 /*
57 undirected edge_descriptor derived from TinyVector,
58 including flag for original edge orientation,
59 as necessary for source(), target() functions;
60 This edge_descriptor allows to directly (without adapter object)
61 index a MultiArrayView with one dimension more than the gridgraph,
62 the last coordinate indexing the edge number
63 (missing edges at the border are just ignored)
64 
65 The gridgraph class is able to convert/construct these edge_descriptors
66 and to reconstruct the corresponding source/target nodes.
67 
68 FIXME: store edge index in (*this)[0] ??
69 */
70 template<unsigned int N>
71 class GridGraphArcDescriptor
72  : public MultiArrayShape<N+1>::type
73 {
74  public:
75  typedef typename MultiArrayShape<N+1>::type base_type;
76  typedef typename base_type::value_type value_type;
77  typedef base_type edge_coord_type;
78  typedef value_type index_type;
79  typedef typename MultiArrayShape<N>::type shape_type;
80  typedef TinyVectorView<value_type, N> vertex_descriptor_view;
81 
82  GridGraphArcDescriptor()
83  : is_reversed_(false)
84  {}
85 
86  GridGraphArcDescriptor(lemon::Invalid)
87  : base_type(-1),
88  is_reversed_(false)
89  {}
90 
91  GridGraphArcDescriptor(base_type const & b, bool reversed)
92  : base_type(b),
93  is_reversed_(reversed)
94  {}
95 
96  GridGraphArcDescriptor(shape_type const &vertex,
97  index_type edge_index,
98  bool reversed=false)
99  : base_type(detail::DontInit())
100  {
101  set(vertex, edge_index, reversed);
102  }
103 
104  void set(shape_type const &vertex, index_type edge_index, bool reversed)
105  {
106  this->template subarray<0,N>() = vertex;
107  (*this)[N] = edge_index;
108  is_reversed_ = reversed;
109  }
110 
111  void increment(GridGraphArcDescriptor const & diff, bool opposite=false)
112  {
113  if(diff.is_reversed_)
114  {
115  is_reversed_ = !opposite;
116  this->template subarray<0,N>() += diff.template subarray<0,N>();
117  }
118  else
119  {
120  is_reversed_ = opposite;
121  }
122  (*this)[N] = diff[N];
123  }
124 
125  bool isReversed() const
126  {
127  return is_reversed_;
128  }
129 
130  vertex_descriptor_view vertexDescriptor() const
131  {
132  return this->template subarray<0,N>();
133  }
134 
135  value_type edgeIndex() const
136  {
137  return (*this)[N];
138  }
139 
140  protected:
141  bool is_reversed_;
142 };
143 
144 inline MultiArrayIndex
145 gridGraphMaxDegree(unsigned int N, NeighborhoodType t)
146 {
147  return t == DirectNeighborhood
148  ? 2*N
149  : pow(3.0, (int)N) - 1;
150 }
151 
152 template <unsigned int N, NeighborhoodType>
153 struct GridGraphMaxDegree;
154 
155 template <unsigned int N>
156 struct GridGraphMaxDegree<N, DirectNeighborhood>
157 {
158  static const MultiArrayIndex value = 2*N;
159 };
160 
161 template <unsigned int N>
162 struct GridGraphMaxDegree<N, IndirectNeighborhood>
163 {
164  static const MultiArrayIndex value = MetaPow<3, N>::value - 1;
165 };
166 
167 template <class Shape>
169 gridGraphEdgeCount(Shape const & shape, NeighborhoodType t, bool directed)
170 {
171  int res = 0;
172  if(t == DirectNeighborhood)
173  {
174  for(unsigned int k=0; k<shape.size(); ++k)
175  res += 2*prod(shape - Shape::unitVector(k));
176  }
177  else
178  {
179  res = prod(3*shape - Shape(2)) - prod(shape);
180  }
181  return directed
182  ? res
183  : res / 2;
184 }
185 
186 namespace detail {
187 
188 template <class Shape>
189 void
190 computeNeighborOffsets(ArrayVector<Shape> const & neighborOffsets,
191  ArrayVector<ArrayVector<bool> > const & neighborExists,
192  ArrayVector<ArrayVector<Shape> > & incrementOffsets,
193  ArrayVector<ArrayVector<GridGraphArcDescriptor<Shape::static_size> > > & edgeDescriptorOffsets,
194  ArrayVector<ArrayVector<MultiArrayIndex> > & indices,
195  ArrayVector<ArrayVector<MultiArrayIndex> > & backIndices,
196  bool directed)
197 {
198  typedef GridGraphArcDescriptor<Shape::static_size> EdgeDescriptor;
199 
200  unsigned int borderTypeCount = neighborExists.size();
201  incrementOffsets.resize(borderTypeCount);
202  edgeDescriptorOffsets.resize(borderTypeCount);
203  indices.resize(borderTypeCount);
204  backIndices.resize(borderTypeCount);
205 
206  for(unsigned int k=0; k<borderTypeCount; ++k)
207  {
208  incrementOffsets[k].clear();
209  edgeDescriptorOffsets[k].clear();
210  indices[k].clear();
211  backIndices[k].clear();
212 
213  for(unsigned int j=0; j < neighborOffsets.size(); ++j)
214  {
215  if(neighborExists[k][j])
216  {
217  if(incrementOffsets[k].size() == 0)
218  {
219  incrementOffsets[k].push_back(neighborOffsets[j]);
220  }
221  else
222  {
223  incrementOffsets[k].push_back(neighborOffsets[j] - neighborOffsets[indices[k].back()]);
224  }
225 
226  if(directed || j < neighborOffsets.size() / 2) // directed or backward edge
227  {
228  edgeDescriptorOffsets[k].push_back(EdgeDescriptor(Shape(), j));
229  }
230  else if(edgeDescriptorOffsets[k].size() == 0 || !edgeDescriptorOffsets[k].back().isReversed()) // the first forward edge
231  {
232  edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j], neighborOffsets.size()-j-1, true));
233  }
234  else // second or higher forward edge
235  {
236  edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j] - neighborOffsets[indices[k].back()],
237  neighborOffsets.size()-j-1, true));
238  }
239 
240  indices[k].push_back(j);
241  if(j < neighborOffsets.size() / 2)
242  backIndices[k].push_back(j);
243  }
244  }
245  }
246 }
247 
248 } // namespace detail
249 
250 template<unsigned int N, bool BackEdgesOnly=false>
251 class GridGraphNeighborIterator
252 {
253 public:
254  typedef typename MultiArrayShape<N>::type shape_type;
255  typedef MultiCoordinateIterator<N> vertex_iterator;
256  typedef typename vertex_iterator::value_type vertex_descriptor;
257  typedef vertex_descriptor value_type;
258  typedef typename vertex_iterator::pointer pointer;
259  typedef typename vertex_iterator::const_pointer const_pointer;
260  typedef typename vertex_iterator::reference reference;
261  typedef typename vertex_iterator::const_reference const_reference;
262  typedef MultiArrayIndex difference_type;
263  typedef MultiArrayIndex index_type;
264  typedef std::forward_iterator_tag iterator_category;
265 
266  friend struct NeighborhoodTests<N>;
267 
268  GridGraphNeighborIterator()
269  : neighborOffsets_(0),
270  neighborIndices_(0),
271  index_(0)
272  {}
273 
274  template <class DirectedTag>
275  GridGraphNeighborIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::Node const & v)
276  : neighborOffsets_(0),
277  neighborIndices_(0),
278  target_(v),
279  index_(0)
280  {
281  unsigned int nbtype = g.get_border_type(v);
282  neighborOffsets_ = &(*g.neighborIncrementArray())[nbtype];
283  neighborIndices_ = &(*g.neighborIndexArray(BackEdgesOnly))[nbtype];
284  updateTarget();
285  }
286 
287  template <class DirectedTag>
288  GridGraphNeighborIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::NodeIt const & v)
289  : neighborOffsets_(0),
290  neighborIndices_(0),
291  target_(v),
292  index_(0)
293  {
294  unsigned int nbtype = g.get_border_type(v);
295  neighborOffsets_ = &(*g.neighborIncrementArray())[nbtype];
296  neighborIndices_ = &(*g.neighborIndexArray(BackEdgesOnly))[nbtype];
297  updateTarget();
298  }
299 
300  // TODO: implement a "goto-neighbor" operation
301  // yielding a vertex_iterator! -> useful for
302  // watershed algo.
303 
304  GridGraphNeighborIterator & operator++()
305  {
306  ++index_;
307  updateTarget();
308  return *this;
309  }
310 
311  GridGraphNeighborIterator operator++(int)
312  {
313  GridGraphNeighborIterator ret(*this);
314  ++*this;
315  return ret;
316  }
317 
318  const_reference operator*() const
319  {
320  return target_;
321  }
322 
323  const_pointer operator->() const
324  {
325  return &target_;
326  }
327 
328  operator const_reference() const
329  {
330  return target_;
331  }
332 
333  const_reference target() const
334  {
335  return target_;
336  }
337 
338  MultiArrayIndex index() const
339  {
340  return index_;
341  }
342 
343  MultiArrayIndex neighborIndex() const
344  {
345  return (*neighborIndices_)[index_];
346  }
347 
348  bool operator==(GridGraphNeighborIterator const & other) const
349  {
350  return index_ == other.index_;
351  }
352 
353  bool operator!=(GridGraphNeighborIterator const & other) const
354  {
355  return index_ != other.index_;
356  }
357 
358  bool isValid() const
359  {
360  return index_ < (MultiArrayIndex)neighborIndices_->size();
361  }
362 
363  bool atEnd() const
364  {
365  return index_ >= (MultiArrayIndex)neighborIndices_->size();
366  }
367 
368  GridGraphNeighborIterator getEndIterator() const
369  {
370  GridGraphNeighborIterator res(*this);
371  res.index_ = (MultiArrayIndex)neighborIndices_->size();
372  return res;
373  }
374 
375  protected:
376 
377  // for testing only
378  GridGraphNeighborIterator(ArrayVector<shape_type> const & neighborOffsets,
379  ArrayVector<index_type> const & neighborIndices,
380  ArrayVector<index_type> const & backIndices,
381  vertex_descriptor source)
382  : neighborOffsets_(&neighborOffsets),
383  neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
384  target_(source),
385  index_(0)
386  {
387  updateTarget();
388  }
389 
390  void updateTarget()
391  {
392  if(isValid())
393  target_ += (*neighborOffsets_)[index_];
394  }
395 
396  ArrayVector<shape_type> const * neighborOffsets_;
397  ArrayVector<index_type> const * neighborIndices_;
398  vertex_descriptor target_;
399  MultiArrayIndex index_;
400 };
401 
402 template<unsigned int N, bool BackEdgesOnly>
403 class GridGraphEdgeIterator;
404 
405 template<unsigned int N, bool BackEdgesOnly=false>
406 class GridGraphOutEdgeIterator
407 {
408  public:
409  typedef typename MultiArrayShape<N>::type shape_type;
410  typedef MultiArrayIndex index_type;
411  typedef GridGraphArcDescriptor<N> arc_descriptor;
412  typedef typename MultiArrayShape<N+1>::type value_type;
413  typedef value_type const & reference;
414  typedef value_type const & const_reference;
415  typedef value_type const * pointer;
416  typedef value_type const * const_pointer;
417  typedef MultiArrayIndex difference_type;
418  typedef std::forward_iterator_tag iterator_category;
419 
420  friend struct NeighborhoodTests<N>;
421  friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
422 
423  GridGraphOutEdgeIterator()
424  : neighborOffsets_(0),
425  neighborIndices_(0),
426  index_(0)
427  {}
428 
429  template <class DirectedTag>
430  GridGraphOutEdgeIterator(GridGraph<N, DirectedTag> const & g,
431  typename GridGraph<N, DirectedTag>::NodeIt const & v,
432  bool opposite=false)
433  : neighborOffsets_(0),
434  neighborIndices_(0),
435  edge_descriptor_(),
436  index_(0)
437  {
438  unsigned int nbtype = g.get_border_type(v);
439  init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], *v, opposite);
440  }
441 
442  template <class DirectedTag>
443  GridGraphOutEdgeIterator(GridGraph<N, DirectedTag> const & g,
444  typename GridGraph<N, DirectedTag>::Node const & v,
445  bool opposite=false)
446  : neighborOffsets_(0),
447  neighborIndices_(0),
448  edge_descriptor_(),
449  index_(0)
450  {
451  unsigned int nbtype = g.get_border_type(v);
452  init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], v, opposite);
453  }
454 
455  GridGraphOutEdgeIterator & operator++()
456  {
457  increment(false);
458  return *this;
459  }
460 
461  GridGraphOutEdgeIterator operator++(int)
462  {
463  GridGraphOutEdgeIterator ret(*this);
464  ++*this;
465  return ret;
466  }
467 
468  const_reference operator*() const
469  {
470  return edge_descriptor_;
471  }
472 
473  operator const_reference() const
474  {
475  return edge_descriptor_;
476  }
477 
478  const_pointer operator->() const
479  {
480  return &edge_descriptor_;
481  }
482 
483  index_type index() const
484  {
485  return index_;
486  }
487 
488  index_type neighborIndex() const
489  {
490  return (*neighborIndices_)[index_];
491  }
492 
493  arc_descriptor const & arcDescriptor() const
494  {
495  return edge_descriptor_;
496  }
497 
498  bool operator==(GridGraphOutEdgeIterator const & other) const
499  {
500  return index_ == other.index();
501  }
502 
503  bool operator!=(GridGraphOutEdgeIterator const & other) const
504  {
505  return index_ != other.index();
506  }
507 
508  bool isValid() const
509  {
510  return index_ < (index_type)neighborIndices_->size();
511  }
512 
513  bool atEnd() const
514  {
515  return index_ >= (index_type)neighborIndices_->size();
516  }
517 
518  GridGraphOutEdgeIterator getEndIterator() const
519  {
520  GridGraphOutEdgeIterator res(*this);
521  res.index_ = (index_type)neighborIndices_->size();
522  return res;
523  }
524 
525  protected:
526 
527  // for testing only
528  GridGraphOutEdgeIterator(ArrayVector<arc_descriptor> const & neighborOffsets,
529  ArrayVector<index_type> const & neighborIndices,
530  ArrayVector<index_type> const & backIndices,
531  shape_type const & source)
532  : neighborOffsets_(0),
533  neighborIndices_(0),
534  edge_descriptor_(),
535  index_(0)
536  {
537  init(&neighborOffsets, BackEdgesOnly ? &backIndices : &neighborIndices, source);
538  }
539 
540  void init(ArrayVector<arc_descriptor> const * neighborOffsets,
541  ArrayVector<index_type> const * neighborIndices,
542  shape_type const & source,
543  bool opposite=false)
544  {
545  neighborOffsets_ = neighborOffsets;
546  neighborIndices_ = neighborIndices;
547  edge_descriptor_ = arc_descriptor(source, 0);
548  index_ = 0;
549  updateEdgeDescriptor(opposite);
550  }
551 
552  void increment(bool opposite)
553  {
554  ++index_;
555  updateEdgeDescriptor(opposite);
556  }
557 
558  void updateEdgeDescriptor(bool opposite)
559  {
560  if(isValid())
561  edge_descriptor_.increment((*neighborOffsets_)[index_], opposite);
562  }
563 
564  ArrayVector<arc_descriptor> const * neighborOffsets_;
565  ArrayVector<index_type> const * neighborIndices_;
566  arc_descriptor edge_descriptor_;
567  index_type index_;
568 };
569 
570 template<unsigned int N, bool BackEdgesOnly=false>
571 class GridGraphOutArcIterator
572 : public GridGraphOutEdgeIterator<N, BackEdgesOnly>
573 {
574  public:
575  typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
576  typedef typename MultiArrayShape<N>::type shape_type;
577  typedef MultiArrayIndex index_type;
578  typedef GridGraphArcDescriptor<N> value_type;
579  typedef value_type const & reference;
580  typedef value_type const & const_reference;
581  typedef value_type const * pointer;
582  typedef value_type const * const_pointer;
583  typedef MultiArrayIndex difference_type;
584  typedef std::forward_iterator_tag iterator_category;
585 
586  friend struct NeighborhoodTests<N>;
587  friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
588 
589  GridGraphOutArcIterator()
590  : base_type()
591  {}
592 
593  explicit GridGraphOutArcIterator(base_type const & b)
594  : base_type(b)
595  {}
596 
597  template <class DirectedTag>
598  GridGraphOutArcIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::NodeIt const & v)
599  : base_type(g, v)
600  {}
601 
602  template <class DirectedTag>
603  GridGraphOutArcIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::Node const & v)
604  : base_type(g, v)
605  {}
606 
607  GridGraphOutArcIterator & operator++()
608  {
609  base_type::operator++();
610  return *this;
611  }
612 
613  GridGraphOutArcIterator operator++(int)
614  {
615  GridGraphOutArcIterator ret(*this);
616  ++*this;
617  return ret;
618  }
619 
620  const_reference operator*() const
621  {
622  return this->edge_descriptor_;
623  }
624 
625  operator const_reference() const
626  {
627  return this->edge_descriptor_;
628  }
629 
630  const_pointer operator->() const
631  {
632  return &this->edge_descriptor_;
633  }
634 
635  GridGraphOutArcIterator getEndIterator() const
636  {
637  return GridGraphOutArcIterator(base_type::getEndIterator());
638  }
639 
640  protected:
641 
642  // for testing only
643  GridGraphOutArcIterator(ArrayVector<value_type> const & neighborOffsets,
644  ArrayVector<index_type> const & neighborIndices,
645  ArrayVector<index_type> const & backIndices,
646  shape_type const & source)
647  : base_type(neighborOffsets, neighborIndices, backIndices, source)
648  {}
649 };
650 
651 template<unsigned int N, bool BackEdgesOnly=false>
652 class GridGraphInArcIterator
653 : public GridGraphOutEdgeIterator<N, BackEdgesOnly>
654 {
655  public:
656  typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
657  typedef typename MultiArrayShape<N>::type shape_type;
658  typedef MultiArrayIndex index_type;
659  typedef GridGraphArcDescriptor<N> value_type;
660  typedef value_type const & reference;
661  typedef value_type const & const_reference;
662  typedef value_type const * pointer;
663  typedef value_type const * const_pointer;
664  typedef MultiArrayIndex difference_type;
665  typedef std::forward_iterator_tag iterator_category;
666 
667  friend struct NeighborhoodTests<N>;
668 
669  GridGraphInArcIterator()
670  : base_type()
671  {}
672 
673  explicit GridGraphInArcIterator(base_type const & b)
674  : base_type(b)
675  {}
676 
677  template <class DirectedTag>
678  GridGraphInArcIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::NodeIt const & v)
679  : base_type(g, v, true)
680  {}
681 
682  template <class DirectedTag>
683  GridGraphInArcIterator(GridGraph<N, DirectedTag> const & g, typename GridGraph<N, DirectedTag>::Node const & v)
684  : base_type(g, v, true)
685  {}
686 
687  GridGraphInArcIterator & operator++()
688  {
689  base_type::increment(true);
690  return *this;
691  }
692 
693  GridGraphInArcIterator operator++(int)
694  {
695  GridGraphInArcIterator ret(*this);
696  ++*this;
697  return ret;
698  }
699 
700  const_reference operator*() const
701  {
702  return this->edge_descriptor_;
703  }
704 
705  operator const_reference() const
706  {
707  return this->edge_descriptor_;
708  }
709 
710  const_pointer operator->() const
711  {
712  return &this->edge_descriptor_;
713  }
714 
715  GridGraphInArcIterator getEndIterator() const
716  {
717  return GridGraphInArcIterator(base_type::getEndIterator());
718  }
719 };
720 
721  // Edge iterator for directed and undirected graphs.
722  // Composed of a vertex_iterator and an out_edge_iterator.
723 template<unsigned int N, bool BackEdgesOnly>
724 class GridGraphEdgeIterator
725 {
726 public:
727  typedef GridGraphEdgeIterator<N, BackEdgesOnly> self_type;
728  typedef MultiCoordinateIterator<N> vertex_iterator;
729  typedef typename vertex_iterator::value_type vertex_descriptor;
730  typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
731  typedef typename MultiArrayShape<N+1>::type edge_descriptor;
732  typedef edge_descriptor value_type;
733  typedef value_type const * pointer;
734  typedef value_type const * const_pointer;
735  typedef value_type const & reference;
736  typedef value_type const & const_reference;
737  typedef typename MultiArrayShape<N>::type shape_type;
738  typedef MultiArrayIndex difference_type;
739  typedef MultiArrayIndex index_type;
740  typedef std::forward_iterator_tag iterator_category;
741 
742  friend struct NeighborhoodTests<N>;
743 
744  GridGraphEdgeIterator()
745  : neighborOffsets_(0),
746  neighborIndices_(0)
747  {}
748 
749  template <class DirectedTag>
750  GridGraphEdgeIterator(GridGraph<N, DirectedTag> const & g)
751  : neighborOffsets_(g.edgeIncrementArray()),
752  neighborIndices_(g.neighborIndexArray(BackEdgesOnly)),
753  vertexIterator_(g),
754  outEdgeIterator_(g, vertexIterator_)
755  {
756  if(outEdgeIterator_.atEnd()) // in a undirected graph, the first point stores no edges
757  {
758  ++vertexIterator_;
759  if(vertexIterator_.isValid())
760  outEdgeIterator_ = out_edge_iterator(g, vertexIterator_);
761  }
762  }
763 
764  GridGraphEdgeIterator & operator++()
765  {
766  ++outEdgeIterator_;
767  if(outEdgeIterator_.atEnd())
768  {
769  ++vertexIterator_;
770  if(vertexIterator_.isValid())
771  {
772  unsigned int borderType = vertexIterator_.borderType();
773  outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
774  }
775  }
776  return *this;
777  }
778 
779  GridGraphEdgeIterator operator++(int)
780  {
781  GridGraphEdgeIterator ret(*this);
782  ++*this;
783  return ret;
784  }
785 
786  const_reference operator*() const
787  {
788  return *outEdgeIterator_;
789  }
790 
791  operator const_reference() const
792  {
793  return *outEdgeIterator_;
794  }
795 
796  const_pointer operator->() const
797  {
798  return outEdgeIterator_.operator->();
799  }
800 
801  bool operator==(GridGraphEdgeIterator const & other) const
802  {
803  return (vertexIterator_ == other.vertexIterator_ && outEdgeIterator_ == other.outEdgeIterator_);
804  }
805 
806  bool operator!=(GridGraphEdgeIterator const & other) const
807  {
808  return !operator==(other);
809  }
810 
811  bool isValid() const
812  {
813  return vertexIterator_.isValid();
814  }
815 
816  bool atEnd() const
817  {
818  return !isValid();
819  }
820 
821  GridGraphEdgeIterator getEndIterator() const
822  {
823  GridGraphEdgeIterator ret(*this);
824  ret.vertexIterator_ = vertexIterator_.getEndIterator();
825  vertex_iterator lastVertex = ret.vertexIterator_ - 1;
826  unsigned int borderType = lastVertex.borderType();
827  ret.outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *lastVertex);
828  ret.outEdgeIterator_ = ret.outEdgeIterator_.getEndIterator();
829  return ret;
830  }
831 
832  protected:
833 
834  // for testing only
835  GridGraphEdgeIterator(ArrayVector<ArrayVector<typename out_edge_iterator::value_type> > const & neighborOffsets,
836  ArrayVector<ArrayVector<index_type> > const & neighborIndices,
837  ArrayVector<ArrayVector<index_type> > const & backIndices,
838  shape_type const & shape)
839  : neighborOffsets_(&neighborOffsets),
840  neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
841  vertexIterator_(shape),
842  outEdgeIterator_(neighborOffsets[vertexIterator_.borderType()],
843  neighborIndices[vertexIterator_.borderType()],
844  backIndices[vertexIterator_.borderType()], shape_type())
845  {
846  if(outEdgeIterator_.atEnd()) // in a undirected graph, the first point stores no edges
847  {
848  ++vertexIterator_;
849  if(vertexIterator_.isValid())
850  {
851  unsigned int borderType = vertexIterator_.borderType();
852  outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
853  }
854  }
855  }
856 
857  ArrayVector<ArrayVector<typename out_edge_iterator::value_type> > const * neighborOffsets_;
858  ArrayVector<ArrayVector<index_type> > const * neighborIndices_;
859  vertex_iterator vertexIterator_;
860  out_edge_iterator outEdgeIterator_;
861 };
862 
863 template<unsigned int N, bool BackEdgesOnly>
864 class GridGraphArcIterator
865 : public GridGraphEdgeIterator<N, BackEdgesOnly>
866 {
867 public:
868  typedef GridGraphEdgeIterator<N, BackEdgesOnly> base_type;
869  typedef GridGraphArcIterator<N, BackEdgesOnly> self_type;
870  typedef MultiCoordinateIterator<N> vertex_iterator;
871  typedef typename vertex_iterator::value_type vertex_descriptor;
872  typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
873  typedef typename out_edge_iterator::value_type edge_descriptor;
874  typedef edge_descriptor value_type;
875  typedef value_type const * pointer;
876  typedef value_type const * const_pointer;
877  typedef value_type const & reference;
878  typedef value_type const & const_reference;
879  typedef typename MultiArrayShape<N>::type shape_type;
880  typedef MultiArrayIndex difference_type;
881  typedef MultiArrayIndex index_type;
882  typedef std::forward_iterator_tag iterator_category;
883 
884  friend struct NeighborhoodTests<N>;
885 
886  GridGraphArcIterator()
887  : base_type()
888  {}
889 
890  explicit GridGraphArcIterator(base_type const & b)
891  : base_type(b)
892  {}
893 
894  template <class DirectedTag>
895  GridGraphArcIterator(GridGraph<N, DirectedTag> const & g)
896  : base_type(g)
897  {}
898 
899  GridGraphArcIterator & operator++()
900  {
901  base_type::operator++();
902  return *this;
903  }
904 
905  GridGraphArcIterator operator++(int)
906  {
907  GridGraphArcIterator ret(*this);
908  ++*this;
909  return ret;
910  }
911 
912  const_reference operator*() const
913  {
914  return *(this->outEdgeIterator_);
915  }
916 
917  operator const_reference() const
918  {
919  return *(this->outEdgeIterator_);
920  }
921 
922  const_pointer operator->() const
923  {
924  return this->outEdgeIterator_.operator->();
925  }
926 
927  GridGraphArcIterator getEndIterator() const
928  {
929  return GridGraphArcIterator(base_type::getEndIterator());
930  }
931 
932  protected:
933 
934  // for testing only
935  GridGraphArcIterator(ArrayVector<ArrayVector<value_type> > const & neighborOffsets,
936  ArrayVector<ArrayVector<index_type> > const & neighborIndices,
937  ArrayVector<ArrayVector<index_type> > const & backIndices,
938  shape_type const & shape)
939  : base_type(neighborOffsets, neighborIndices, backIndices, shape)
940  {}
941 };
942 
943 template<unsigned int N>
944 inline bool operator==(MultiCoordinateIterator<N> const & i, lemon::Invalid)
945 {
946  return i.atEnd();
947 }
948 
949 template<unsigned int N>
950 inline bool operator!=(MultiCoordinateIterator<N> const & i, lemon::Invalid)
951 {
952  return i.isValid();
953 }
954 
955 template<unsigned int N>
956 inline bool operator==(lemon::Invalid, MultiCoordinateIterator<N> const & i)
957 {
958  return i.atEnd();
959 }
960 
961 template<unsigned int N>
962 inline bool operator!=(lemon::Invalid, MultiCoordinateIterator<N> const & i)
963 {
964  return i.isValid();
965 }
966 
967 #define VIGRA_LEMON_INVALID_COMPARISON(type) \
968 template<unsigned int N, bool BackEdgesOnly> \
969 inline bool operator==(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
970 { \
971  return i.atEnd(); \
972 } \
973 template<unsigned int N, bool BackEdgesOnly> \
974 inline bool operator!=(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
975 { \
976  return i.isValid(); \
977 } \
978 template<unsigned int N, bool BackEdgesOnly> \
979 inline bool operator==(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
980 { \
981  return i.atEnd(); \
982 } \
983 template<unsigned int N, bool BackEdgesOnly> \
984 inline bool operator!=(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
985 { \
986  return i.isValid(); \
987 }
988 
989 VIGRA_LEMON_INVALID_COMPARISON(GridGraphNeighborIterator)
990 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutEdgeIterator)
991 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutArcIterator)
992 VIGRA_LEMON_INVALID_COMPARISON(GridGraphInArcIterator)
993 VIGRA_LEMON_INVALID_COMPARISON(GridGraphEdgeIterator)
994 VIGRA_LEMON_INVALID_COMPARISON(GridGraphArcIterator)
995 
996 #undef VIGRA_LEMON_INVALID_COMPARISON
997 
998 using boost::directed_tag;
999 using boost::undirected_tag;
1000 
1001 namespace detail {
1002 
1003 template <unsigned int N, class DirectedTag>
1004 struct GridGraphBase;
1005 
1006 template <unsigned int N>
1007 struct GridGraphBase<N, directed_tag>
1008 {
1009  template <class T>
1010  class ArcMap
1011  : public MultiArray<N+1, Multiband<T> >
1012  {
1013  public:
1014  typedef MultiArray<N+1, Multiband<T> > base_type;
1015  typedef typename base_type::difference_type difference_type;
1016  typedef typename base_type::key_type key_type;
1017  typedef typename base_type::value_type value_type;
1018  typedef typename base_type::reference reference;
1019  typedef typename base_type::const_reference const_reference;
1020  typedef boost::read_write_property_map_tag category;
1021 
1022  typedef lemon::True ReferenceMapTag;
1023  typedef key_type Key;
1024  typedef value_type Value;
1025  typedef reference Reference;
1026  typedef const_reference ConstReference;
1027 
1028  ArcMap()
1029  : base_type()
1030  {}
1031 
1032  explicit ArcMap(GridGraph<N, directed_tag> const & g)
1033  : base_type(g.arc_propmap_shape())
1034  {}
1035 
1036  ArcMap(GridGraph<N, directed_tag> const & g, T const & t)
1037  : base_type(g.arc_propmap_shape(), t)
1038  {}
1039 
1040  explicit ArcMap(difference_type const & shape)
1041  : base_type(shape)
1042  {}
1043 
1044  ArcMap(difference_type const & shape, T const & t)
1045  : base_type(shape, t)
1046  {}
1047 
1048  ArcMap & operator=(ArcMap const & m)
1049  {
1050  base_type::operator=(m);
1051  return *this;
1052  }
1053 
1054  ArcMap & operator=(base_type const & m)
1055  {
1056  base_type::operator=(m);
1057  return *this;
1058  }
1059 
1060  // appropriate operator[] are inherited
1061 
1062  void set(Key const & k, Value const & v)
1063  {
1064  (*this)[k] = v;
1065  }
1066  };
1067 };
1068 
1069 template <unsigned int N>
1070 struct GridGraphBase<N, undirected_tag>
1071 {
1072  typedef lemon::True UndirectedTag;
1073 
1074  template <class T>
1075  class ArcMap
1076  : public MultiArray<N+1, Multiband<T> >
1077  {
1078  public:
1079  typedef MultiArray<N+1, Multiband<T> > base_type;
1080  typedef GridGraphArcDescriptor<N> difference_type;
1081  typedef difference_type key_type;
1082  typedef typename base_type::value_type value_type;
1083  typedef typename base_type::reference reference;
1084  typedef typename base_type::const_reference const_reference;
1085  typedef boost::read_write_property_map_tag category;
1086 
1087  typedef lemon::True ReferenceMapTag;
1088  typedef key_type Key;
1089  typedef value_type Value;
1090  typedef reference Reference;
1091  typedef const_reference ConstReference;
1092 
1093  ArcMap()
1094  : base_type()
1095  {}
1096 
1097  explicit ArcMap(GridGraph<N, undirected_tag> const & g)
1098  : base_type(g.arc_propmap_shape()),
1099  graph_(&g)
1100  {}
1101 
1102  ArcMap(GridGraph<N, undirected_tag> const & g, T const & t)
1103  : base_type(g.arc_propmap_shape(), t),
1104  graph_(&g)
1105  {}
1106 
1107  ArcMap & operator=(ArcMap const & m)
1108  {
1109  base_type::operator=(m);
1110  return *this;
1111  }
1112 
1113  ArcMap & operator=(base_type const & m)
1114  {
1115  base_type::operator=(m);
1116  return *this;
1117  }
1118 
1119  reference operator[](difference_type const & s)
1120  {
1121  if(s.isReversed())
1122  {
1123  return base_type::operator[](graph_->directedArc(s));
1124  }
1125  else
1126  {
1127  return base_type::operator[](s);
1128  }
1129  }
1130 
1131  const_reference operator[](difference_type const & s) const
1132  {
1133  if(s.isReversed())
1134  {
1135  return base_type::operator[](graph_->directedArc(s));
1136  }
1137  else
1138  {
1139  return base_type::operator[](s);
1140  }
1141  }
1142 
1143  void set(Key const & k, Value const & v)
1144  {
1145  (*this)[k] = v;
1146  }
1147 
1148  GridGraph<N, undirected_tag> const * graph_;
1149  };
1150 };
1151 
1152 } // namespace detail
1153 
1154 /********************************************************/
1155 /* */
1156 /* GridGraph */
1157 /* */
1158 /********************************************************/
1159 
1160 /** \brief Define a grid graph in arbitrary dimensions.
1161 
1162  A GridGraph connects each pixel to its direct or indirect neighbors.
1163  Direct neighbors are the adjacent point along the coordinate axes,
1164  whereas indirect neighbors include the diagonally adjacent points. Thus,
1165  direct neighbors correspond to the 4-neighborhood in 2D and the
1166  6-neighborhood in 3D, whereas indirect neighbors correspond to the
1167  8-neighborhood and 26-neighborhood respectively. The GridGraph class
1168  extends this scheme to arbitrary dimensions. While the dimension must be
1169  defined at compile time via the template parameter <tt>N</tt>, the
1170  desired neighborhood can be chosen at runtime in the GridGraph's
1171  constructor. The shape of the grid is also specified at runtime in terms
1172  of a suitable shape object.
1173 
1174  Another choice to be made at compile time is whether the graph should be directed
1175  or undirected. This is defined via the <tt>DirectedTag</tt> template parameter
1176  which can take the values <tt>directed_tag</tt> or <tt>undirected_tag</tt>.
1177 
1178  The main difficulty in a grid graph is to skip the missing neighbors
1179  of the pixels near the grid's border. For example, the upper left pixel in a
1180  2D grid has only two direct neighbors instead of the usual four. The GridGraph
1181  class uses a precomputed set of internal look-up tables to efficiently determine the
1182  appropriate number and location of the existing neighbors. A key design decision
1183  to make this fast was to give up the requirement that edge IDs are contiguous
1184  integers (as in LEMON's implementation of a 2D grid graph, which became very
1185  complicated and slow by enforcing this requirement). Instead, edges are numbered
1186  as if all nodes (including nodes at the grid's border) had the same degree.
1187  Since edges crossing the border are not actually present in the graph, these IDs
1188  are missing, leading to gaps in the sequence of IDs.
1189 
1190  For the sake of compatibility, the GridGraph class implements two
1191  popular graph APIs: the one defined by the <a href="http://www.boost.org/doc/libs/release/libs/graph/">boost::graph</a> library and
1192  the one defined by the <a href="http://lemon.cs.elte.hu/">LEMON</a> library.
1193  Their basic principles are very similar: The graph's nodes, edges and adjacency
1194  structure are accessed via a set of iterators, whereas additional properties
1195  (like node and edge weights) are provided via <i>property maps</i> that are
1196  indexed with suitable node or edge descriptor objects returned by the iterators.
1197 
1198  Specifically, GridGraph implements the requirements of the following <a href="http://www.boost.org/doc/libs/release/libs/graph/doc/graph_concepts.html">concepts of the
1199  boost::graph API</a>: <b>Graph, IncidenceGraph, BidirectionalGraph, AdjacencyGraph,
1200  VertexListGraph, EdgeListGraph,</b> and <b>AdjacencyMatrix</b>. Likewise, it supports
1201  the concepts <b>Graph</b> and <b>Digraph</b> of the LEMON API. The property maps
1202  associated with a GridGraph support the boost concepts ReadablePropertyMap,
1203  WritablePropertyMap, ReadWritePropertyMap, and LvaluePropertyMap as well as the
1204  LEMON concepts ReadMap, WriteMap, ReadWriteMap, and ReferenceMap.
1205 
1206  VIGRA's GridGraph class is designed such that multi-dimensional coordinates
1207  (i.e. <tt>TinyVector<MultiArrayIndex></tt>) serve as descriptor objects, which means
1208  that normal <tt>MultiArray</tt>s or <tt>MultiArrayView</tt>s can serve as property
1209  maps in most situations. Thus, node properties like a foreground probability for
1210  foreground/background segmentation can simply be stored as normal images.
1211 
1212  Since the boost::graph and LEMON APIs differ in how they call corresponding
1213  functionality (e.g., they use the terms <tt>vertex</tt> and <tt>node</tt> respectively
1214  in an exactly synonymous way), most GridGraph helper classes and functions are exposed
1215  under two different names. To implement your own algorithms, you can choose the API
1216  you like most. VIGRA adopts the convention that algorithms using the boost::graph
1217  API go into the namespace <tt>vigra::boost_graph</tt>, while those using the
1218  LEMON API are placed into the namespace <tt>vigra::lemon_graph</tt>. This helps
1219  to avoid name clashes when the two APIs happen to use the same name for different
1220  things. The documentation of the GridGraph members specifies which API the respective
1221  function or class belongs to. Please consult the documentation of these
1222  libraries for tutorial introductions and full reference of the respective APIs.
1223 
1224  VIGRA adds an important new concept of its own: the back neighborhood
1225  and associated adjacency and edge iterators. The back neighborhood of a given vertex
1226  with ID <tt>i</tt> is the set of all neighbor vertices whose ID is smaller than <tt>i</tt>.
1227  This concept is useful if you work on the grid graph's vertices in scan order
1228  and want to access just those neighbors that have already been processed. Connected
1229  components labeling is a typical example of an algorithm that can take advantage of this
1230  possibility. In principle, a back neighborhood iterator could be implemented as
1231  a filter iterator that simply skips all neighbors with inappropriate IDs. However,
1232  in case of grid graphs it is more efficient to provide a special iterator for this purpose.
1233 
1234  <b>Usage:</b>
1235 
1236  <b>\#include</b> <vigra/multi_gridgraph.hxx> <br/>
1237  Namespace: vigra
1238 
1239  At present, the GridGraph class is mainly used internally to implement image
1240  analysis functions for arbitrary dimensional arrays (e.g. detection of local
1241  extrema, connected components labeling, watersheds, SLIC superpixels). For example,
1242  a dimension-independent algorithm to detect local maxima using the LEMON API
1243  might look like this:
1244 
1245  \code
1246  namespace vigra { namespace lemon_graph {
1247 
1248  template <class Graph, class InputMap, class OutputMap>
1249  void
1250  localMaxima(Graph const & g,
1251  InputMap const & src,
1252  OutputMap & local_maxima,
1253  typename OutputMap::value_type marker)
1254  {
1255  // define abreviations for the required iterators
1256  typedef typename Graph::NodeIt graph_scanner;
1257  typedef typename Graph::OutArcIt neighbor_iterator;
1258 
1259  // iterate over all nodes (i.e. pixels)
1260  for (graph_scanner node(g); node != INVALID; ++node)
1261  {
1262  // remember the value of the current node
1263  typename InputMap::value_type current = src[*node];
1264 
1265  // iterate over all neighbors of the current node
1266  bool is_local_maximum = true;
1267  for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
1268  {
1269  // if a neighbor has larger value, the center node is not a local maximum
1270  if (current < src[g.target(*arc)])
1271  is_local_maximum = false;
1272  }
1273 
1274  // mark the node when it is a local maximum
1275  if (is_local_maximum)
1276  local_maxima[*node] = marker;
1277  }
1278  }
1279 
1280  }} // namespace vigra::lemon_graph
1281  \endcode
1282 
1283  It should be noted that this algorithm will work for any LEMON-compatible graph class,
1284  not just our GridGraph. When implemented in terms of the boost::graph API, the same algorithm
1285  looks like this:
1286 
1287  \code
1288  namespace vigra { namespace boost_graph {
1289 
1290  template <class Graph, class InputMap, class OutputMap>
1291  void
1292  localMaxima(Graph const & g,
1293  InputMap const & src,
1294  OutputMap & local_maxima,
1295  typename property_traits<OutputMap>::value_type marker)
1296  {
1297  // define abreviations and variables for the required iterators
1298  typedef typename graph_traits<Graph>::vertex_iterator graph_scanner;
1299  typedef typename graph_traits<Graph>::adjacency_iterator neighbor_iterator;
1300 
1301  graph_scanner node, node_end;
1302  neighbor_iterator arc, arc_end;
1303 
1304  // iterate over all nodes (i.e. pixels)
1305  tie(node, node_end) = vertices(g);
1306  for (; node != node_end; ++node)
1307  {
1308  // remember the value of the current node
1309  typename property_traits<InputMap>::value_type current = get(src, *node);
1310 
1311  // iterate over all neighbors of the current node
1312  bool is_local_maximum = true;
1313  tie(arc, arc_end) = adjacent_vertices(*node, g);
1314  for (;arc != arc_end; ++arc)
1315  {
1316  // if a neighbor has larger value, the center node is not a local maximum
1317  if (current < get(src, *arc))
1318  is_local_maximum = false;
1319  }
1320 
1321  // mark the node when it is a local maximum
1322  if (is_local_maximum)
1323  put(local_maxima, *node, marker);
1324  }
1325  }
1326 
1327  }} // namespace vigra::boost_graph
1328  \endcode
1329 
1330  It can be seen that the differences between the APIs are mainly syntactic
1331  (especially note that boost::graph users traits classes and free functions,
1332  whereas LEMON uses nested typedefs and member functions). Either of these
1333  algorithms can now serve as the backend of a local maxima detector
1334  for <tt>MultiArrayViews</tt>:
1335 
1336  \code
1337  namespace vigra {
1338 
1339  template <unsigned int N, class T1,
1340  class T2>
1341  void
1342  localMaxima(MultiArrayView<N, T1> const & src,
1343  MultiArrayView<N, T2> local_maxima,
1344  T2 marker,
1345  NeighborhoodType neighborhood = IndirectNeighborhood)
1346  {
1347  vigra_precondition(src.shape() == local_maxima.shape(),
1348  "localMinMax(): shape mismatch between input and output.");
1349 
1350  // create a grid graph with appropriate shape and desired neighborhood
1351  GridGraph<N, undirected_tag> graph(src.shape(), neighborhood);
1352 
1353  // forward the call to the graph-based algorithm, using
1354  // the given MultiArrayViews as property maps
1355  lemon_graph::localMaxima(graph, src, local_maxima, marker);
1356  }
1357 
1358  } // namespace vigra
1359  \endcode
1360 
1361  A slightly enhanced version of this code is actually used to implement this
1362  functionality in VIGRA.
1363 */
1364 template<unsigned int N, class DirectedTag>
1366 : public detail::GridGraphBase<N, DirectedTag>
1367 {
1368 public:
1369  /** \brief 'true' if the graph is directed (API: boost::graph)
1370  */
1371  static const bool is_directed = IsSameType<DirectedTag, directed_tag>::value;
1372 
1373  typedef detail::GridGraphBase<N, DirectedTag> base_type;
1374  typedef GridGraph<N, DirectedTag> self_type;
1375 
1376  /** \brief Shape type of the graph and a node property map.
1377  */
1379 
1380  /** \brief Shape type of an edge property map (must have one additional dimension).
1381  */
1383 
1384  /** \brief Type of node and edge IDs.
1385  */
1387 
1388  /** \brief Type to specify number of vertices (API: boost::graph,
1389  use via <tt>boost::graph_traits<Graph>::vertices_size_type</tt>).
1390  */
1392 
1393  /** \brief Type to specify number of edges (API: boost::graph,
1394  use via <tt>boost::graph_traits<Graph>::edges_size_type</tt>).
1395  */
1397 
1398  /** \brief Type to specify number of neighbors (API: boost::graph,
1399  use via <tt>boost::graph_traits<Graph>::degree_size_type</tt>).
1400  */
1402 
1403  /** \brief Iterator over the vertices of the graph (API: boost::graph,
1404  use via <tt>boost::graph_traits<Graph>::vertex_iterator</tt>).
1405  */
1407 
1408  /** \brief Iterator over the neighbor vertices of a given vertex (API: boost::graph,
1409  use via <tt>boost::graph_traits<Graph>::adjacency_iterator</tt>).
1410  */
1411  typedef GridGraphNeighborIterator<N> adjacency_iterator;
1412 
1413  /** \brief Same as adjacency_iterator (API: VIGRA).
1414  */
1415  typedef adjacency_iterator neighbor_vertex_iterator;
1416 
1417  /** \brief Iterator over only those neighbor vertices of a given vertex
1418  that have smaller ID (API: VIGRA).
1419  */
1420  typedef GridGraphNeighborIterator<N, true> back_neighbor_vertex_iterator;
1421 
1422  /** \brief Iterator over the incoming edges of a given vertex (API: boost::graph,
1423  use via <tt>boost::graph_traits<Graph>::in_edge_iterator</tt>).
1424  */
1425  typedef GridGraphInArcIterator<N> in_edge_iterator;
1426 
1427  /** \brief Iterator over the outgoing edges of a given vertex (API: boost::graph,
1428  use via <tt>boost::graph_traits<Graph>::out_edge_iterator</tt>).
1429  */
1430  typedef GridGraphOutArcIterator<N> out_edge_iterator;
1431 
1432  /** \brief Iterator over only those outgoing edges of a given vertex
1433  that go to vertices with smaller IDs (API: VIGRA).
1434  */
1435  typedef GridGraphOutArcIterator<N, true> out_back_edge_iterator;
1436 
1437  /** \brief Iterator over the edges of a graph (API: boost::graph,
1438  use via <tt>boost::graph_traits<Graph>::edge_iterator</tt>).
1439  */
1440  typedef GridGraphArcIterator<N, !is_directed> edge_iterator;
1441 
1442  /** \brief The vertex descriptor (API: boost::graph,
1443  use via <tt>boost::graph_traits<Graph>::vertex_descriptor</tt>).
1444  */
1445  typedef shape_type vertex_descriptor;
1446 
1447  /** \brief The edge descriptor (API: boost::graph,
1448  use via <tt>boost::graph_traits<Graph>::edge_descriptor</tt>).
1449  */
1450  typedef GridGraphArcDescriptor<N> edge_descriptor;
1451 
1452  /** \brief Is the graph directed or undirected ? (API: boost::graph,
1453  use via <tt>boost::graph_traits<Graph>::directed_category</tt>).
1454  */
1455  typedef DirectedTag directed_category;
1456 
1457  /** \brief The graph does not allow multiple edges between the same vertices
1458  (API: boost::graph, use via
1459  <tt>boost::graph_traits<Graph>::edge_parallel_category</tt>).
1460  */
1461  typedef boost::disallow_parallel_edge_tag edge_parallel_category;
1462 
1463  /** \brief The graph does not define internal property maps (API: boost::graph,
1464  use via <tt>boost::graph_traits<Graph>::vertex_property_type</tt>).
1465  */
1466  typedef boost::no_property vertex_property_type; // we only support "external properties".
1467  // FIXME: Maybe support the vertex -> coordinate map (identity) as the only internal property map
1468  // and additionally the vertex_descriptor -> ID map (vertex_index = SOI).
1469 
1470  /** \brief Define several graph tags related to graph traversal (API: boost::graph,
1471  use via <tt>boost::graph_traits<Graph>::traversal_category</tt>).
1472  */
1474  : virtual public boost::bidirectional_graph_tag,
1475  virtual public boost::adjacency_graph_tag,
1476  virtual public boost::vertex_list_graph_tag,
1477  virtual public boost::edge_list_graph_tag,
1478  virtual public boost::adjacency_matrix_tag
1479  {};
1480 
1481  // internal types
1486 
1487  ////////////////////////////////////////////////////////////////////
1488 
1489  // LEMON interface
1490  typedef self_type Graph;
1491 
1492  /** \brief The Node descriptor (API: LEMON).
1493  */
1494  typedef vertex_descriptor Node;
1495 
1496  /** \brief Iterator over all nodes of the graph (API: LEMON).
1497  */
1498  typedef vertex_iterator NodeIt;
1499 
1500  /** \brief The arc (directed edge) descriptor (API: LEMON).
1501  */
1502  typedef GridGraphArcDescriptor<N> Arc;
1503 
1504  /** \brief Iterator over the outgoing edges of a node (API: LEMON).
1505  */
1506  typedef GridGraphOutArcIterator<N> OutArcIt;
1507 
1508  /** \brief Iterator over only those outgoing edges of a node
1509  that end in a node with smaller ID (API: VIGRA).
1510  */
1511  typedef GridGraphOutArcIterator<N, true> OutBackArcIt;
1512 
1513  /** \brief Iterator over the acrs (directed edges) of a node (API: LEMON).
1514  */
1515  typedef GridGraphArcIterator<N, false> ArcIt;
1516 
1517  /** \brief Iterator over the incoming arcs of a node (API: LEMON).
1518  */
1519  typedef GridGraphInArcIterator<N> InArcIt;
1520 
1521  /** \brief The edge descriptor (API: LEMON).
1522  */
1524 
1525  /** \brief Iterator over the incident edges of a node (API: LEMON).
1526  */
1527  typedef GridGraphOutEdgeIterator<N> IncEdgeIt;
1528 
1529  /** \brief Iterator over only those incident edges of a node that
1530  end in a node with smaller ID (API: VIGRA).
1531  */
1532  typedef GridGraphOutEdgeIterator<N, true> IncBackEdgeIt;
1533 
1534  /** \brief Iterator over the edges of the graph (API: LEMON).
1535  */
1536  typedef GridGraphEdgeIterator<N, !is_directed> EdgeIt;
1537 
1538  typedef lemon::True NodeNumTag;
1539  typedef lemon::True EdgeNumTag;
1540  typedef lemon::True ArcNumTag;
1541  typedef lemon::True FindEdgeTag;
1542  typedef lemon::True FindArcTag;
1543 
1544  ////////////////////////////////////////////////////////////////////
1545 
1546  /** \brief Type of a node property map that maps node descriptor objects
1547  onto property values of type <tt>T</tt> (API: LEMON).
1548  */
1549  template <class T>
1550  class NodeMap
1551  : public MultiArray<N, T>
1552  {
1553  public:
1554  typedef MultiArray<N, T> base_type;
1555  typedef typename base_type::difference_type difference_type;
1556  typedef typename base_type::key_type key_type;
1557  typedef typename base_type::value_type value_type;
1558  typedef typename base_type::reference reference;
1559  typedef typename base_type::const_reference const_reference;
1560  typedef boost::read_write_property_map_tag category;
1561 
1562  typedef lemon::True ReferenceMapTag;
1563  typedef key_type Key;
1564  typedef value_type Value;
1565  typedef reference Reference;
1566  typedef const_reference ConstReference;
1567 
1568  NodeMap()
1569  : base_type()
1570  {}
1571 
1572  /** \brief Construct property map for the given graph \a g
1573  (preallocates a zero-initialized entry for each node of the graph).
1574  */
1575  explicit NodeMap(GridGraph const & g)
1576  : base_type(g.shape())
1577  {}
1578 
1579  /** \brief Construct property map for the given graph \a g
1580  (preallocates an entry with initial value \a t for each node of the graph).
1581  */
1582  NodeMap(GridGraph const & g, T const & t)
1583  : base_type(g.shape(), t)
1584  {}
1585 
1586  /** \brief Construct property map for the given \a shape.
1587  (preallocates a zero-initialized entry for each node of a grid
1588  graph with this shape).
1589  */
1590  explicit NodeMap(difference_type const & shape)
1591  : base_type(shape)
1592  {}
1593 
1594  /** \brief Construct property map for the given \a shape.
1595  (preallocates an entry with initial value \a t for each node of a grid
1596  graph with this shape).
1597  */
1598  NodeMap(difference_type const & shape, T const & t)
1599  : base_type(shape, t)
1600  {}
1601 
1602  NodeMap & operator=(NodeMap const & m)
1603  {
1605  return *this;
1606  }
1607 
1608  NodeMap & operator=(base_type const & m)
1609  {
1611  return *this;
1612  }
1613 
1614  // appropriate operator[] are inherited
1615 #ifdef DOXYGEN
1616  /** \brief Read/write access to the value associated with node descriptor \a key.
1617  */
1618  Value & operator[](Key const & key);
1619 
1620  /** \brief Read-only access to the value associated with node descriptor \a key.
1621  */
1622  Value const & operator[](Key const & key) const;
1623 #endif // DOXYGEN
1624 
1625  /** \brief Set the property of node desctiptor \a key to value \a v.
1626  */
1627  void set(Key const & k, Value const & v)
1628  {
1629  (*this)[k] = v;
1630  }
1631  };
1632 
1633 
1634  /** \brief Type of an edge property map that maps edge descriptor objects
1635  onto property values of type <tt>T</tt> (API: LEMON).
1636  */
1637  template <class T>
1638  class EdgeMap
1639  : public MultiArray<N+1, Multiband<T> >
1640  {
1641  public:
1642  typedef MultiArray<N+1, Multiband<T> > base_type;
1643  typedef typename base_type::difference_type difference_type;
1644  typedef typename base_type::key_type key_type;
1645  typedef typename base_type::value_type value_type;
1646  typedef typename base_type::reference reference;
1647  typedef typename base_type::const_reference const_reference;
1648  typedef boost::read_write_property_map_tag category;
1649 
1650  typedef lemon::True ReferenceMapTag;
1651  typedef key_type Key;
1652  typedef value_type Value;
1653  typedef reference Reference;
1654  typedef const_reference ConstReference;
1655 
1656  EdgeMap()
1657  : base_type()
1658  {}
1659 
1660  /** \brief Construct property map for the given graph \a g
1661  (preallocates a zero-initialized entry for each edge of the graph).
1662  */
1663  explicit EdgeMap(GridGraph const & g)
1664  : base_type(g.edge_propmap_shape())
1665  {}
1666 
1667  /** \brief Construct property map for the given graph \a g
1668  (preallocates an entry with initial value \a t for each edge of the graph).
1669  */
1670  EdgeMap(GridGraph const & g, T const & t)
1671  : base_type(g.edge_propmap_shape(), t)
1672  {}
1673 
1674  /** \brief Construct property map for the given \a shape
1675  (preallocates a zero-initialized entry for each edge of
1676  a grid graph with this shape).
1677  */
1678  explicit EdgeMap(difference_type const & shape)
1679  : base_type(shape)
1680  {}
1681 
1682  /** \brief Construct property map for the given \a shape
1683  (preallocates an entry with initial value \a t for each edge
1684  of a grid graph with this shape).
1685  */
1686  EdgeMap(difference_type const & shape, T const & t)
1687  : base_type(shape, t)
1688  {}
1689 
1690  EdgeMap & operator=(EdgeMap const & m)
1691  {
1693  return *this;
1694  }
1695 
1696  EdgeMap & operator=(base_type const & m)
1697  {
1699  return *this;
1700  }
1701 
1702  // appropriate operator[] are inherited
1703 #ifdef DOXYGEN
1704  /** \brief Read/write access to the value associated with edge descriptor \a key.
1705  */
1706  Value & operator[](Key const & key);
1707 
1708  /** \brief Read-only access to the value associated with edge descriptor \a key.
1709  */
1710  Value const & operator[](Key const & key) const;
1711 #endif // DOXYGEN
1712 
1713  /** \brief Set the property of edge desctiptor \a key to value \a v.
1714  */
1715  void set(Key const & k, Value const & v)
1716  {
1717  (*this)[k] = v;
1718  }
1719  };
1720 
1721 #ifdef DOXYGEN
1722  /** \brief Type of an arc property map that maps arc descriptor objects
1723  onto property values of type <tt>T</tt> (API: LEMON).
1724  */
1725  template <class T>
1726  class ArcMap
1727  : public MultiArray<N+1, Multiband<T> >
1728  {
1729  public:
1730 
1731  /** \brief Construct property map for the given graph \a g
1732  (preallocates a zero-initialized entry for each arc of the graph).
1733  */
1734  explicit ArcMap(GridGraph const & g);
1735 
1736  /** \brief Construct property map for the given graph \a g
1737  (preallocates an entry with initial value \a t for each arc of the graph).
1738  */
1739  ArcMap(GridGraph const & g, T const & t);
1740 
1741  /** \brief Construct property map for the given \a shape
1742  (preallocates a zero-initialized entry for each arc of
1743  a grid graph with this shape).
1744  */
1745  explicit ArcMap(difference_type const & shape);
1746 
1747  /** \brief Construct property map for the given \a shape
1748  (preallocates an entry with initial value \a t for each arc of
1749  a grid graph with this shape).
1750  */
1751  ArcMap(difference_type const & shape, T const & t);
1752 
1753  /** \brief Read/write access to the value associated with arc descriptor \a key.
1754  */
1755  Value & operator[](Key const & key);
1756 
1757  /** \brief Read-only access to the value associated with arc descriptor \a key.
1758  */
1759  Value const & operator[](Key const & key) const;
1760 
1761  /** \brief Set the property of arc desctiptor \a key to value \a v.
1762  */
1763  void set(Key const & k, Value const & v);
1764  };
1765 #endif // DOXYGEN
1766 
1767  /** \brief Type of a property map that returns the coordinate of a given node (API: LEMON).
1768  */
1769  class IndexMap
1770  {
1771  public:
1772  typedef Node Key;
1773  typedef Node Value;
1774  typedef Key key_type;
1775  typedef Value value_type;
1776  typedef Value const & reference;
1777  typedef boost::readable_property_map_tag category;
1778 
1779  IndexMap()
1780  {}
1781 
1782  /** \brief Construct property map for the given graph.
1783  */
1784  explicit IndexMap(const GridGraph&)
1785  {}
1786 
1787  /** \brief Get the grid coordinate of the node descriptor \a key.
1788  */
1789  Value const & operator[](Key const & key) const
1790  {
1791  return key;
1792  }
1793  };
1794 
1795  /** \brief Type of a property map that returns the number of incoming edges of a given node (API: LEMON, use via <tt>lemon::InDegMap<Graph></tt>).
1796  */
1797  class InDegMap
1798  {
1799  public:
1800 
1801  /// The graph type of InDegMap (works for directed and undirected graphs)
1802  typedef GridGraph Graph;
1803  typedef GridGraph Digraph;
1804  typedef Node Key;
1805  typedef degree_size_type Value;
1806  typedef Key key_type;
1807  typedef Value value_type;
1808  typedef Value const & reference;
1809  typedef boost::readable_property_map_tag category;
1810 
1811  /** \brief Construct property map for the given graph.
1812  */
1813  explicit InDegMap(const GridGraph& graph)
1814  : graph_(graph)
1815  {}
1816 
1817  /** \brief Get the in-degree of the node descriptor \a key.
1818  */
1819  Value operator[](const Key& key) const
1820  {
1821  return graph_.in_degree(key);
1822  }
1823 
1824  protected:
1825 
1826  GridGraph const & graph_;
1827  };
1828 
1829  /** \brief Type of a property map that returns the number of outgoing edges of a given node (API: LEMON, use via <tt>lemon::OutDegMap<Graph></tt>).
1830  */
1832  {
1833  public:
1834 
1835  /// The graph type of OutDegMap (works for directed and undirected graphs)
1836  typedef GridGraph Graph;
1837  typedef GridGraph Digraph;
1838  typedef Node Key;
1839  typedef degree_size_type Value;
1840  typedef Key key_type;
1841  typedef Value value_type;
1842  typedef Value const & reference;
1843  typedef boost::readable_property_map_tag category;
1844 
1845  /** \brief Construct property map for the given graph.
1846  */
1847  explicit OutDegMap(const GridGraph& graph)
1848  : graph_(graph)
1849  {}
1850 
1851  /** \brief Get the out-degree of the node descriptor \a key.
1852  */
1853  Value operator[](const Key& key) const
1854  {
1855  return graph_.out_degree(key);
1856  }
1857 
1858  protected:
1859 
1860  GridGraph const & graph_;
1861  };
1862 
1863  ////////////////////////////////////////////////////////////////////
1864 
1865  // dummy default constructor to satisfy adjacency_graph concept
1866  GridGraph()
1867  {}
1868 
1869  /** \brief Construct a grid graph with given \a shape and neighborhood type \a ntype.
1870 
1871  The shape must have type <tt>MultiArrayShape<N>::type</tt> with the appropriate
1872  dimension <tt>N</tt>. The neighborhood type can take the values
1873  <tt>DirectNeighborhood</tt> to use only the axis-aligned edges (2N-neighborhood)
1874  and <tt>IndirectNeighborhood</tt> to use all diagonal edges as well
1875  ((3<sup>N</sup>-1)-neighborhood).
1876  */
1877  GridGraph(shape_type const &shape, NeighborhoodType ntype = DirectNeighborhood)
1878  : shape_(shape),
1879  num_vertices_(prod(shape)),
1880  num_edges_(gridGraphEdgeCount(shape, ntype, is_directed)),
1881  neighborhoodType_(ntype)
1882  {
1883  ArrayVector<ArrayVector<bool> > neighborExists;
1884 
1885  // populate the neighborhood tables:
1886  // FIXME: this might be static (but make sure that it works with multi-threading)
1887  detail::makeArrayNeighborhood(neighborOffsets_, neighborExists, neighborhoodType_);
1888  detail::computeNeighborOffsets(neighborOffsets_, neighborExists, incrementalOffsets_,
1889  edgeDescriptorOffsets_, neighborIndices_, backIndices_, is_directed);
1890 
1891  // compute the neighbor offsets per neighborhood type
1892  // detail::makeArraySubNeighborhood(neighborhood[0], neighborExists, shape_type(1), neighborhoodIndices);
1893  }
1894 
1895  /** \brief Get the ID (i.e. scan-order index) for node desciptor \a v (API: LEMON).
1896  */
1897  index_type id(Node const & v) const
1898  {
1899  return detail::CoordinateToScanOrder<N>::exec(shape(), v);
1900  }
1901 
1902  index_type id(NodeIt const & v) const
1903  {
1904  return v.scanOrderIndex();
1905  }
1906 
1907  index_type id(neighbor_vertex_iterator const & v) const
1908  {
1909  return id(*v);
1910  }
1911 
1912  index_type id(back_neighbor_vertex_iterator const & v) const
1913  {
1914  return id(*v);
1915  }
1916 
1917  /** \brief Get node descriptor for given node ID \a i (API: LEMON).
1918  */
1919  Node nodeFromId(index_type i) const
1920  {
1921  Node res(SkipInitialization);
1922  detail::ScanOrderToCoordinate<N>::exec(i, shape(), res);
1923  return res;
1924  }
1925 
1926  /** \brief Get the maximum ID of any node in this graph (API: LEMON).
1927  */
1928  index_type maxNodeId() const
1929  {
1930  return prod(shape()) - 1;
1931  }
1932 
1933  /** \brief Get the grid cordinate of the given node \a v (convenience function).
1934  */
1935  Node const & pos(Node const & v) const
1936  {
1937  return v;
1938  }
1939 
1940  /** \brief Get vertex iterator pointing to the first vertex of this graph (convenience function,<br/>
1941  the boost::graph API provides the free function <tt>boost::vertices(graph)</tt>,<br/>
1942  LEMON uses <tt>Graph::NodeIt(graph)</tt>).
1943  */
1944  vertex_iterator get_vertex_iterator() const
1945  {
1946  return vertex_iterator(shape_);
1947  }
1948 
1949  /** \brief Get vertex iterator pointing to the given vertex (API: VIGRA).
1950  */
1951  vertex_iterator get_vertex_iterator(vertex_descriptor const & v) const
1952  {
1953  return vertex_iterator(shape_) + v;
1954  }
1955 
1956  /** \brief Get vertex iterator pointing beyond the valid range of vertices of this graph (convenience function,<br/>
1957  the boost::graph API provides the free function <tt>boost::vertices(graph)</tt>,<br/>
1958  LEMON uses the special value <tt>lemon::INVALID</tt> instead).
1959  */
1960  vertex_iterator get_vertex_end_iterator() const
1961  {
1962  return get_vertex_iterator().getEndIterator();
1963  }
1964 
1965  /** \brief Get an iterator pointing to the first neighbor of the given vertex (convenience function,<br/>
1966  the boost::graph API provides the free function <tt>boost::adjacent_vertices(v, graph)</tt>,<br/>
1967  LEMON uses <tt>Graph::ArcIt(g, v)</tt>).
1968  */
1969  neighbor_vertex_iterator get_neighbor_vertex_iterator(vertex_descriptor const & v) const
1970  {
1971  return neighbor_vertex_iterator(*this, v);
1972  }
1973 
1974  /** \brief Get an iterator pointing beyond the range of neighbors of the given vertex (convenience function,<br/>
1975  the boost::graph API provides the free function <tt>boost::adjacent_vertices(v, graph)</tt>,<br/>
1976  LEMON uses the speical value <tt>lemon::INVALID</tt> instead).
1977  */
1978  neighbor_vertex_iterator get_neighbor_vertex_end_iterator(vertex_descriptor const & v) const
1979  {
1980  return get_neighbor_vertex_iterator(v).getEndIterator();
1981  }
1982 
1983  /** \brief Get an iterator pointing to the first backward neighbor of the given vertex (API: VIGRA,<br/>
1984  in analogy to the boost::graph API, we also provide a free function <tt>boost::back_adjacent_vertices(v, g)</tt>,<br/>
1985  and the LEMON analogue is <tt>Graph::OutBackArcIt(graph, v)</tt>).
1986  */
1987  back_neighbor_vertex_iterator get_back_neighbor_vertex_iterator(vertex_descriptor const & v) const
1988  {
1989  return back_neighbor_vertex_iterator(*this, v);
1990  }
1991 
1992  /** \brief Get an iterator pointing beyond the range of backward neighbors of the given vertex (API: VIGRA,<br/>
1993  in analogy to the boost::graph API, we also provide a free function <tt>boost::back_adjacent_vertices(v, g)</tt>,<br/>
1994  and LEMON just uses <tt>lemon::INVALID</tt> instead).
1995  */
1996  back_neighbor_vertex_iterator get_back_neighbor_vertex_end_iterator(vertex_descriptor const & v) const
1997  {
1998  return get_back_neighbor_vertex_iterator(v).getEndIterator();
1999  }
2000 
2001  // --------------------------------------------------
2002  // support for VertexListGraph:
2003 
2004  /** \brief Get the number of vertices in this graph (convenience function,
2005  the boost::graph API provides the free function <tt>boost::num_vertices(graph)</tt>).
2006  */
2007  vertices_size_type num_vertices() const
2008  {
2009  return num_vertices_;
2010  }
2011 
2012  /** \brief Get the number of nodes in this graph (API: LEMON).
2013  */
2014  vertices_size_type nodeNum() const
2015  {
2016  return num_vertices();
2017  }
2018 
2019  // --------------------------------------------------
2020  // support for IncidenceGraph:
2021 
2022  /** \brief Get the ID (i.e. scan-order index in an edge property map) for the
2023  given edges descriptor \a e (API: LEMON).
2024  */
2025  index_type id(Edge const & e) const
2026  {
2027  return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), e);
2028  }
2029 
2030  index_type id(EdgeIt const & e) const
2031  {
2032  return id(*e);
2033  }
2034 
2035  index_type id(IncEdgeIt const & e) const
2036  {
2037  return id(*e);
2038  }
2039 
2040  index_type id(IncBackEdgeIt const & e) const
2041  {
2042  return id(*e);
2043  }
2044 
2045  /** \brief Get the edge descriptor for the given edge ID \a i (API: LEMON).
2046  */
2047  Edge edgeFromId(index_type i) const
2048  {
2049  Edge res(SkipInitialization);
2050  detail::ScanOrderToCoordinate<N+1>::exec(i, edge_propmap_shape(), res);
2051  return res;
2052  }
2053 
2054  /** \brief Get the maximum ID of any edge in this graph (API: LEMON).
2055  */
2056  index_type maxEdgeId() const
2057  {
2058  if(is_directed)
2059  return maxArcId();
2060  if(edgeNum() == 0)
2061  return -1;
2062  Node lastNode = shape() - shape_type(1);
2063  Arc a(lastNode, backIndices_[get_border_type(lastNode)].back(), false);
2064  return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), a);
2065  }
2066 
2067  /** \brief Get the ID (i.e. scan-order index an an arc property map) for
2068  the given ar \a a (API: LEMON).
2069  */
2070  index_type id(Arc const & a) const
2071  {
2072  return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), directedArc(a));
2073  }
2074 
2075  index_type id(ArcIt const & a) const
2076  {
2077  return id(*a);
2078  }
2079 
2080  index_type id(OutArcIt const & a) const
2081  {
2082  return id(*a);
2083  }
2084 
2085  index_type id(OutBackArcIt const & a) const
2086  {
2087  return id(*a);
2088  }
2089 
2090  /** \brief Get an arc descriptor for the given arc ID \a i (API: LEMON).
2091  */
2092  Arc arcFromId(index_type i) const
2093  {
2094  Arc res;
2095  detail::ScanOrderToCoordinate<N+1>::exec(i, arc_propmap_shape(), res);
2096  return undirectedArc(res);
2097  }
2098 
2099  /** \brief Get the maximal ID af any arc in this graph (API: LEMON).
2100  */
2101  index_type maxArcId() const
2102  {
2103  if(edgeNum() == 0)
2104  return -1;
2105  Node lastNode = shape() - shape_type(1);
2106  index_type n = neighborIndices_[get_border_type(lastNode)][0];
2107  Arc a(neighbor(lastNode, n), oppositeIndex(n), false);
2108  return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), a);
2109  }
2110 
2111  /** \brief Return <tt>true</tt> when the arc is looking on the underlying
2112  edge in its natural (i.e. forward) direction, <tt>false</tt> otherwise (API: LEMON).
2113  */
2114  bool direction(Arc const & a) const
2115  {
2116  return !a.isReversed();
2117  }
2118 
2119  /** \brief Create an arc for the given edge \a e, oriented along the
2120  edge's natural (<tt>forward = true</tt>) or reversed
2121  (<tt>forward = false</tt>) direction (API: LEMON).
2122  */
2123  Arc direct(Edge const & e, bool forward) const
2124  {
2125  if(!is_directed || forward)
2126  return Arc(e, !forward);
2127  else
2128  return Arc(v(e), oppositeIndex(e[N]), true);
2129  }
2130 
2131  /** \brief Create an arc for the given edge \a e oriented
2132  so that node \a n is the starting node of the arc (API: LEMON), or
2133  return <tt>lemon::INVALID</tt> if the edge is not incident to this node.
2134  */
2135  Arc direct(Edge const & e, Node const & n) const
2136  {
2137  if(u(e) == n)
2138  return direct(e, true);
2139  if(v(e) == n)
2140  return direct(e, false);
2141  return Arc(lemon::INVALID);
2142  }
2143 
2144  /** \brief Return the opposite node of the given node \a n
2145  along edge \a e (API: LEMON), or return <tt>lemon::INVALID</tt>
2146  if the edge is not incident to this node.
2147  */
2148  Node oppositeNode(Node const & n, Edge const & e) const
2149  {
2150  Node start(u(e)), end(v(e));
2151  if(n == start)
2152  return end;
2153  if(n == end)
2154  return start;
2155  return Node(lemon::INVALID);
2156  }
2157 
2158  /** \brief Create an arc referring to the same edge as the given
2159  arc \a a, but with reversed direction (API: LEMON).
2160  */
2161  Arc oppositeArc(Arc const & a) const
2162  {
2163  return is_directed
2164  ? Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()), false)
2165  : Arc(a, !a.isReversed());
2166  }
2167 
2168  // internal function
2169  Arc directedArc(Arc const & a) const
2170  {
2171  return a.isReversed()
2172  ? Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()), false)
2173  : a;
2174  }
2175 
2176  // internal function
2177  Arc undirectedArc(Arc const & a) const
2178  {
2179  return a.edgeIndex() < maxUniqueDegree()
2180  ? a
2181  : Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()), true);
2182  }
2183 
2184  /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
2185  */
2186  Node baseNode(IncEdgeIt const & e) const
2187  {
2188  return source(e.arcDescriptor());
2189  }
2190 
2191  /** \brief Return the start node of the edge the given iterator is referring to (API: VIGRA).
2192  */
2193  Node baseNode(IncBackEdgeIt const & e) const
2194  {
2195  return source(e.arcDescriptor());
2196  }
2197 
2198  /** \brief Return the start node of the edge the given iterator is referring to (API: LEMON).
2199  */
2200  Node baseNode(OutArcIt const & a) const
2201  {
2202  return source(*a);
2203  }
2204 
2205  /** \brief Return the start node of the edge the given iterator is referring to (API: VIGRA).
2206  */
2207  Node baseNode(OutBackArcIt const & a) const
2208  {
2209  return source(*a);
2210  }
2211 
2212  /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
2213  */
2214  Node runningNode(IncEdgeIt const & e) const
2215  {
2216  return target(e.arcDescriptor());
2217  }
2218 
2219  /** \brief Return the end node of the edge the given iterator is referring to (API: VIGRA).
2220  */
2221  Node runningNode(IncBackEdgeIt const & e) const
2222  {
2223  return target(e.arcDescriptor());
2224  }
2225 
2226  /** \brief Return the end node of the edge the given iterator is referring to (API: LEMON).
2227  */
2228  Node runningNode(OutArcIt const & a) const
2229  {
2230  return target(*a);
2231  }
2232 
2233  /** \brief Return the end node of the edge the given iterator is referring to (API: VIGRA).
2234  */
2235  Node runningNode(OutBackArcIt const & a) const
2236  {
2237  return target(*a);
2238  }
2239 
2240  /** \brief Get the start node of the given arc \a a (API: LEMON).
2241  */
2242  Node source(Arc const & a) const
2243  {
2244  return source_or_target(a, true);
2245  }
2246 
2247  /** \brief Get the end node of the given arc \a a (API: LEMON).
2248  */
2249  Node target(Arc const & a) const
2250  {
2251  return source_or_target(a, false);
2252  }
2253 
2254  /** \brief Get the start node of the given edge \a e (API: LEMON,<br/>
2255  the boost::graph API provides the free function <tt>boost::source(e, graph)</tt>).
2256  */
2257  Node u(Edge const & e) const
2258  {
2259  return Node(e.template subarray<0,N>());
2260  }
2261 
2262  /** \brief Get the end node of the given edge \a e (API: LEMON,<br/>
2263  the boost::graph API provides the free function <tt>boost::target(e, graph)</tt>).
2264  */
2265  Node v(Edge const & e) const
2266  {
2267  return Node(e.template subarray<0,N>()) + neighborOffsets_[e[N]];
2268  }
2269 
2270  /** \brief Get an iterator pointing to the first outgoing edge of the given vertex (convenience function,<br/>
2271  the boost::graph API provides the free function <tt>boost::out_edges(v, graph)</tt>,<br/>
2272  LEMON uses <tt>Graph::OutArcIt(g, v)</tt>).
2273  */
2274  out_edge_iterator get_out_edge_iterator(vertex_descriptor const & v) const
2275  {
2276  return out_edge_iterator(*this, v);
2277  }
2278 
2279  /** \brief Get an iterator pointing beyond the range of outgoing edges of the given vertex (convenience function,<br/>
2280  the boost::graph API provides the free function <tt>boost::out_edges(v, graph)</tt>,<br/>
2281  LEMON uses the special value <tt>lemon::INVALID</tt> instead).
2282  */
2283  out_edge_iterator get_out_edge_end_iterator(vertex_descriptor const & v) const
2284  {
2285  return get_out_edge_iterator(v).getEndIterator();
2286  }
2287 
2288  /** \brief Get an iterator pointing to the first outgoing backward edge of the given vertex (API: VIGRA,<br/>
2289  in analogy to the boost::graph API, we also provide a free function <tt>boost::out_back_edges(v, g)</tt>,<br/>
2290  and the LEMON analogue is <tt>Graph::IncBackEdgeIt(graph, v)</tt>).
2291  */
2292  out_back_edge_iterator get_out_back_edge_iterator(vertex_descriptor const & v) const
2293  {
2294  return out_back_edge_iterator(*this, v);
2295  }
2296 
2297  /** \brief Get an iterator pointing beyond the range of outgoing backward edges of the given vertex (API: VIGRA,<br/>
2298  in analogy to the boost::graph API, we also provide a free function <tt>boost::out_back_edges(v, g)</tt>,<br/>
2299  and LEMON uses the special value <tt>lemon::INVALID</tt> instead).
2300  */
2301  out_back_edge_iterator get_out_back_edge_end_iterator(vertex_descriptor const & v) const
2302  {
2303  return get_out_back_edge_iterator(v).getEndIterator();
2304  }
2305 
2306  /** \brief Get an iterator pointing to the first incoming edge of the given vertex (convenience function,<br/>
2307  the boost::graph API provides the free function <tt>boost::in_edges(v, graph)</tt>,<br/>
2308  LEMON uses <tt>Graph::InArcIt(g, v)</tt>).
2309  */
2310  in_edge_iterator get_in_edge_iterator(vertex_descriptor const & v) const
2311  {
2312  return in_edge_iterator(*this, v);
2313  }
2314 
2315  /** \brief Get an iterator pointing beyond the range of incoming edges of the given vertex (convenience function,<br/>
2316  the boost::graph API provides the free function <tt>boost::in_edges(v, graph)</tt>,<br/>
2317  LEMON uses the special value <tt>lemon::INVALID</tt> instead).
2318  */
2319  in_edge_iterator get_in_edge_end_iterator(vertex_descriptor const & v) const
2320  {
2321  return get_in_edge_iterator(v).getEndIterator();
2322  }
2323 
2324  /** \brief Get the number of outgoing edges of the given vertex (convenience function,<br/>
2325  the boost::graph API provides the free function <tt>boost::out_degree(v, graph)</tt>,<br/>
2326  LEMON uses a special property map <tt>lemon::OutDegMap<Graph></tt>).
2327  */
2328  degree_size_type out_degree(vertex_descriptor const & v) const
2329  {
2330  return (degree_size_type)neighborIndices_[get_border_type(v)].size();
2331  }
2332 
2333  /** \brief Get the number of outgoing backward edges of the given vertex (API: VIGRA).
2334  */
2335  degree_size_type back_degree(vertex_descriptor const & v) const
2336  {
2337  return (degree_size_type)backIndices_[get_border_type(v)].size();
2338  }
2339 
2340  /** \brief Get the number of outgoing forward edges of the given vertex (API: VIGRA).
2341  */
2342  degree_size_type forward_degree(vertex_descriptor const & v) const
2343  {
2344  unsigned int bt = get_border_type(v);
2345  return (degree_size_type)(neighborIndices_[bt].size() - backIndices_[bt].size());
2346  }
2347 
2348  /** \brief Get the number of incoming edges of the given vertex (convenience function,<br/>
2349  the boost::graph API provides the free function <tt>boost::in_degree(v, graph)</tt>,<br/>
2350  LEMON uses a special property map <tt>lemon::InDegMap<Graph></tt>).
2351  */
2352  degree_size_type in_degree(vertex_descriptor const & v) const
2353  {
2354  return out_degree(v);
2355  }
2356 
2357  /** \brief Get the total number of edges (incoming plus outgoing) of the given vertex (convenience function,<br/>
2358  the boost::graph API provides the free function <tt>boost::degree(v, graph)</tt>,<br/>
2359  LEMON has no analogue).
2360  */
2361  degree_size_type degree(vertex_descriptor const & v) const
2362  {
2363  return is_directed
2364  ? 2*out_degree(v)
2365  : out_degree(v);
2366  }
2367 
2368  // --------------------------------------------------
2369  // support for EdgeListGraph:
2370 
2371  /** \brief Get the number of edges in this graph (convenience function,
2372  boost::graph API provides the free function <tt>boost::num_edges(graph)</tt>).
2373  */
2374  edges_size_type num_edges() const
2375  {
2376  return num_edges_;
2377  }
2378 
2379  /** \brief Get the number of edges in this graph (API: LEMON).
2380  */
2381  edges_size_type edgeNum() const
2382  {
2383  return num_edges();
2384  }
2385 
2386  /** \brief Get the number of arc in this graph (API: LEMON).
2387  */
2388  edges_size_type arcNum() const
2389  {
2390  return is_directed
2391  ? num_edges()
2392  : 2*num_edges();
2393  }
2394 
2395  /** \brief Get edge iterator pointing to the first edge of the graph (convenience function,<br/>
2396  the boost::graph API provides the free function <tt>boost::edges(graph)</tt>,<br/>
2397  LEMON uses <tt>Graph::EdgeIt(graph)</tt>).
2398  */
2399  edge_iterator get_edge_iterator() const
2400  {
2401  return edge_iterator(*this);
2402  }
2403 
2404  /** \brief Get edge iterator pointing beyond the valid range of edges of this graph (convenience function,<br/>
2405  the boost::graph API provides the free function <tt>boost::vertices(graph)</tt>,<br/>
2406  LEMON uses the special value <tt>lemon::INVALID</tt> instead).
2407  */
2408  edge_iterator get_edge_end_iterator() const
2409  {
2410  return get_edge_iterator().getEndIterator();
2411  }
2412 
2413  // --------------------------------------------------
2414  // support for AdjacencyMatrix concept:
2415 
2416  /** \brief Get a descriptor for the edge connecting vertices \a u and \a v,<br/>
2417  or <tt>(lemon::INVALID, false)</tt> if no such edge exists (convenience function,<br/>
2418  the boost::graph API provides the free function <tt>boost::edge(u, v, graph)</tt>).
2419  */
2420  std::pair<edge_descriptor, bool>
2421  edge(vertex_descriptor const & u, vertex_descriptor const & v) const
2422  {
2423  std::pair<edge_descriptor, bool> res(lemon::INVALID, false);
2424 
2425  neighbor_vertex_iterator i = get_neighbor_vertex_iterator(u),
2426  end = i.getEndIterator();
2427  for (; i != end; ++i)
2428  {
2429  if (*i == v)
2430  {
2431  res.first = make_edge_descriptor(u, i.neighborIndex());
2432  res.second = true;
2433  break;
2434  }
2435  }
2436  return res;
2437  }
2438 
2439  /** \brief Get a descriptor for the edge connecting vertices \a u and \a v,<br/>or <tt>lemon::INVALID</tt> if no such edge exists (API: LEMON).
2440  */
2441  Edge findEdge(Node const & u, Node const & v, Edge const & = lemon::INVALID) const
2442  {
2443  return this->edge(u, v).first;
2444  }
2445 
2446  /** \brief Get a descriptor for the arc connecting vertices \a u and \a v,<br/>or <tt>lemon::INVALID</tt> if no such edge exists (API: LEMON).
2447  */
2448  Arc findArc(Node const & u, Node const & v, Arc const & = lemon::INVALID) const
2449  {
2450  return this->edge(u, v).first;
2451  // std::pair<edge_descriptor, bool> res(edge(u, v));
2452  // return res.second
2453  // ? res.first
2454  // : Arc(lemon::INVALID);
2455  }
2456 
2457  /** \brief Create a property map that returns the coordinate of each node (API: LEMON GridGraph).
2458  */
2460  {
2461  return IndexMap();
2462  }
2463 
2464  // --------------------------------------------------
2465  // other helper functions:
2466 
2467  bool isDirected() const
2468  {
2469  return is_directed;
2470  }
2471 
2472  degree_size_type maxDegree() const
2473  {
2474  return (degree_size_type)neighborOffsets_.size();
2475  }
2476 
2477  degree_size_type maxUniqueDegree() const
2478  {
2479  return is_directed
2480  ? maxDegree()
2481  : maxDegree() / 2;
2482  }
2483 
2484  shape_type const & shape() const
2485  {
2486  return shape_;
2487  }
2488 
2489  edge_propmap_shape_type edge_propmap_shape() const
2490  {
2491  edge_propmap_shape_type res(SkipInitialization);
2492  res.template subarray<0, N>() = shape_;
2493  res[N] = maxUniqueDegree();
2494  return res;
2495  }
2496 
2497  edge_propmap_shape_type arc_propmap_shape() const
2498  {
2499  edge_propmap_shape_type res(SkipInitialization);
2500  res.template subarray<0, N>() = shape_;
2501  res[N] = maxDegree();
2502  return res;
2503  }
2504 
2505  unsigned int get_border_type(vertex_descriptor const & v) const
2506  {
2507  return detail::BorderTypeImpl<N>::exec(v, shape_);
2508  }
2509 
2510  unsigned int get_border_type(vertex_iterator const & v) const
2511  {
2512  return v.borderType();
2513  }
2514 
2515  index_type oppositeIndex(index_type neighborIndex) const
2516  {
2517  return maxDegree() - neighborIndex - 1;
2518  }
2519 
2520  /* the given neighborIndex must be valid for the given vertex,
2521  otherwise this function will crash
2522  */
2523  edge_descriptor make_edge_descriptor(vertex_descriptor const & v,
2524  index_type neighborIndex) const
2525  {
2526  if(neighborIndex < maxUniqueDegree())
2527  return edge_descriptor(v, neighborIndex, false);
2528  else
2529  return edge_descriptor(neighbor(v, neighborIndex), oppositeIndex(neighborIndex), true);
2530  }
2531 
2532  shape_type const & neighborOffset(index_type neighborIndex) const
2533  {
2534  return neighborOffsets_[neighborIndex];
2535  }
2536 
2537  vertex_descriptor neighbor(vertex_descriptor const & v, index_type neighborIndex) const
2538  {
2539  return v + neighborOffsets_[neighborIndex];
2540  }
2541 
2542  vertex_descriptor
2543  source_or_target(edge_descriptor const & e, bool return_source) const
2544  {
2545  // source is always the attached node (first coords) unless the
2546  // edge has been reversed.
2547  if ((return_source && e.isReversed()) ||
2548  (!return_source && !e.isReversed()))
2549  {
2550  return neighbor(e.vertexDescriptor(), e.edgeIndex());
2551  }
2552  else
2553  {
2554  return e.vertexDescriptor();
2555  }
2556  }
2557 
2558  NeighborOffsetArray const * neighborOffsetArray() const
2559  {
2560  return &neighborOffsets_;
2561  }
2562 
2563  RelativeNeighborOffsetsArray const * neighborIncrementArray() const
2564  {
2565  return &incrementalOffsets_;
2566  }
2567 
2568  RelativeEdgeOffsetsArray const * edgeIncrementArray() const
2569  {
2570  return &edgeDescriptorOffsets_;
2571  }
2572 
2573  IndexArray const * neighborIndexArray(bool backEdgesOnly) const
2574  {
2575  return backEdgesOnly
2576  ? &backIndices_
2577  : &neighborIndices_;
2578  }
2579 
2580  protected:
2581  NeighborOffsetArray neighborOffsets_;
2582  IndexArray neighborIndices_, backIndices_;
2583  RelativeNeighborOffsetsArray incrementalOffsets_;
2584  RelativeEdgeOffsetsArray edgeDescriptorOffsets_;
2585  shape_type shape_;
2586  MultiArrayIndex num_vertices_, num_edges_;
2587  NeighborhoodType neighborhoodType_;
2588 };
2589 
2590 //@}
2591 
2592 } // namespace vigra
2593 
2594 namespace boost {
2595 
2596 /** \addtogroup BoostGraphExtensions GridGraph additions to namespace <tt>boost</tt>
2597 
2598  provides the required functionality to make \ref vigra::GridGraph compatible to the boost::graph library.
2599 */
2600 //@{
2601 
2602 
2603 
2604 template <unsigned int N, class T, class Acc>
2605 struct property_traits<vigra::MultiArray<N, T, Acc> >
2606 {
2607  typedef vigra::MultiArray<N, T, Acc> type;
2608  typedef typename type::key_type key_type;
2609  typedef typename type::value_type value_type;
2610  typedef typename type::reference reference;
2611  typedef boost::read_write_property_map_tag category;
2612 };
2613 
2614 template <unsigned int N, class T, class Acc>
2615 struct property_traits<vigra::MultiArray<N, T, Acc> const>
2616 {
2617  typedef vigra::MultiArray<N, T, Acc> const type;
2618  typedef typename type::key_type key_type;
2619  typedef typename type::value_type value_type;
2620  typedef typename type::const_reference reference;
2621  typedef boost::readable_property_map_tag category;
2622 };
2623 
2624 template <unsigned int N, class T, class Stride>
2625 struct property_traits<vigra::MultiArrayView<N, T, Stride> >
2626 {
2628  typedef typename type::key_type key_type;
2629  typedef typename type::value_type value_type;
2630  typedef typename type::reference reference;
2631  typedef boost::read_write_property_map_tag category;
2632 };
2633 
2634 template <unsigned int N, class T, class Stride>
2635 struct property_traits<vigra::MultiArrayView<N, T, Stride> const>
2636 {
2637  typedef vigra::MultiArrayView<N, T, Stride> const type;
2638  typedef typename type::key_type key_type;
2639  typedef typename type::value_type value_type;
2640  typedef typename type::const_reference reference;
2641  typedef boost::readable_property_map_tag category;
2642 };
2643 
2644  /** \brief Return number of outgoing edges of vertex \a v (API: boost).
2645  */
2646 template<unsigned int N, class DirectedTag>
2647 inline
2651 {
2652  return g.out_degree(v);
2653 }
2654 
2655  /** \brief Return number of incoming edges of vertex \a v (API: boost).
2656  */
2657 template<unsigned int N, class DirectedTag>
2658 inline
2662 {
2663  return g.in_degree(v);
2664 }
2665 
2666  /** \brief Return total number of edges (incoming and outgoing) of vertex \a v (API: boost).
2667  */
2668 template<unsigned int N, class DirectedTag>
2669 inline
2673 {
2674  return g.degree(v);
2675 }
2676 
2677  /** \brief Get a (begin, end) iterator pair for the vertices of graph \a g (API: boost).
2678  */
2679 template<unsigned int N, class DirectedTag>
2680 inline
2681 std::pair<typename vigra::GridGraph<N, DirectedTag>::vertex_iterator,
2684 {
2685  return std::make_pair(g.get_vertex_iterator(),
2687 }
2688 
2689  /** \brief Return the number of vertices in graph \a g (API: boost).
2690  */
2691 template<unsigned int N, class DirectedTag>
2692 inline
2695 {
2696  return g.num_vertices();
2697 }
2698 
2699  /** \brief Get a (begin, end) iterator pair for the neighbor vertices of
2700  vertex \a v in graph \a g (API: boost).
2701  */
2702 template<unsigned int N, class DirectedTag>
2703 inline
2704 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2708 {
2709  return std::make_pair(g.get_neighbor_vertex_iterator(v),
2711 }
2712 
2713  /** \brief Get a (begin, end) iterator pair for only thise neighbor vertices of
2714  vertex \a v that have smaller ID than \a v (API: VIGRA).
2715  */
2716 template<unsigned int N, class DirectedTag>
2717 inline
2718 std::pair<typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator,
2722 {
2723  return std::make_pair(g.get_back_neighbor_vertex_iterator(v),
2725 }
2726 
2727 // adjacent_vertices variant in vigra namespace: allows to call adjacent_vertices with vertex_iterator argument
2728 template<unsigned int N, class DirectedTag>
2729 inline
2730 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2732 adjacent_vertices_at_iterator(typename vigra::GridGraph<N, DirectedTag>::vertex_iterator const & v,
2734 {
2735  return std::make_pair(g.get_neighbor_vertex_iterator(v),
2737 }
2738 
2739  /** \brief Get a (begin, end) iterator pair for the outgoing edges of
2740  vertex \a v in graph \a g (API: boost).
2741  */
2742 template<unsigned int N, class DirectedTag>
2743 inline
2744 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator,
2748 {
2749  return std::make_pair(g.get_out_edge_iterator(v),
2751 }
2752 
2753  /** \brief Get a (begin, end) iterator pair for only those outgoing edges of
2754  vertex \a v whose ID is smaller than that of \a v (API: VIGRA).
2755  */
2756 template<unsigned int N, class DirectedTag>
2757 inline
2758 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator,
2762 {
2763  return std::make_pair(g.get_out_back_edge_iterator(v),
2765 }
2766 
2767  /** \brief Get a (begin, end) iterator pair for the incoming edges of
2768  vertex \a v in graph \a g (API: boost).
2769  */
2770 template<unsigned int N, class DirectedTag>
2771 inline
2772 std::pair<typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator,
2776 {
2777  return std::make_pair(g.get_in_edge_iterator(v),
2778  g.get_in_edge_end_iterator(v));
2779 }
2780 
2781  /** \brief Get a vertex descriptor for the start vertex of edge \a e in graph \a g (API: boost).
2782  */
2783 template<unsigned int N, class DirectedTag>
2784 inline
2788 {
2789  return g.source(e);
2790 }
2791 
2792  /** \brief Get a vertex descriptor for the end vertex of edge \a e in graph \a g (API: boost).
2793  */
2794 template<unsigned int N, class DirectedTag>
2795 inline
2799 {
2800  return g.target(e);
2801 }
2802 
2803  /** \brief Get a (begin, end) iterator pair for the edges of graph \a g (API: boost).
2804  */
2805 template<unsigned int N, class DirectedTag>
2806 inline
2807 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_iterator,
2810 {
2811  return std::make_pair(g.get_edge_iterator(), g.get_edge_end_iterator());
2812 }
2813 
2814  /** \brief Return the number of edges in graph \a g (API: boost).
2815  */
2816 template<unsigned int N, class DirectedTag>
2817 inline
2820 {
2821  return g.num_edges();
2822 }
2823 
2824 // --------------------------------------------------
2825 // support for AdjacencyMatrix concept:
2826 
2827 // FIXME: test this
2828  /** \brief Return the pair (edge_descriptor, true) when an edge between vertices
2829  \a u and \a v exists, or (lemon::INVALID, false) otherwise (API: boost).
2830  */
2831 template<unsigned int N, class DirectedTag>
2832 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_descriptor, bool>
2836 {
2837  return g.edge(u,v);
2838 }
2839 
2840 // provide get / put for MultiArrayViews, indexed by the
2841 // above-defined vertex_descriptor and edge_descriptor (in our case, a coordinate tuple):
2842 // FIXME: place this into multi_array.hxx ?
2843  /** \brief Put value \a val at key \a k in the property map \a pmap (API: boost).
2844  */
2845 template<unsigned int N, class T, class Stride, class U>
2846 inline
2849  U const & val)
2850 {
2851  pmap[k] = val;
2852 }
2853 
2854  /** \brief Read the value at key \a k in property map \a pmap (API: boost).
2855  */
2856 template<unsigned int N, class T, class Stride>
2857 inline
2861 {
2862  return pmap[k];
2863 }
2864 
2865 #if 0
2866 
2867 // property map support for mapping coordinates to scan-order indices:
2868 
2869 template<unsigned int N>
2870 struct IDMapper {
2871  typedef typename vigra::GridGraph<N> graph_type;
2872  typedef boost::readable_property_map_tag category;
2873  typedef typename graph_type::index_type value_type;
2874  typedef typename graph_type::vertex_descriptor key_type;
2875  typedef const value_type& reference;
2876 
2877 
2878  IDMapper(const graph_type &graph)
2879  : map_helper(graph.get_vertex_iterator())
2880  {}
2881 
2882  typename graph_type::vertex_iterator map_helper;
2883 };
2884 
2885 template<unsigned int N>
2886 struct property_map<vigra::GridGraph<N>, boost::vertex_index_t>
2887 {
2888  typedef IDMapper<N> type;
2889  typedef IDMapper<N> const_type;
2890 };
2891 
2892 
2893 template<unsigned int N>
2894 inline
2895 typename IDMapper<N>::value_type
2896 get(const IDMapper<N> & mapper,
2897  const typename IDMapper<N>::key_type &k)
2898 {
2899  return (mapper.map_helper + k).scanOrderIndex();
2900 }
2901 
2902 
2903 template<unsigned int N>
2904 typename boost::property_map<vigra::GridGraph<N>, boost::vertex_index_t>::type
2905 //typename IDMapper<N>
2906 get(boost::vertex_index_t, const vigra::GridGraph<N> &graph) {
2907  // return a lightweight wrapper for the CoupledIterator, which easily allows the conversion of
2908  // coordinates via its += operator followed by index().
2909  return IDMapper<N>(graph);
2910 }
2911 
2912 // CHECK if required: also provide the direct (three-parameter) version for index lookup
2913 template<unsigned int N>
2915 get(boost::vertex_index_t,
2916  const vigra::GridGraph<N> &graph,
2917  const typename vigra::GridGraph<N>::vertex_descriptor &v) {
2918  return (IDMapper<N>(graph).map_helper + v).scanOrderIndex();
2919 }
2920 
2921 
2922 // TODO:
2923 // eventually provide an edge_index property map as well?
2924 // (edge_descriptor -> linear contiguous edge index)
2925 
2926 #endif
2927 
2928 //@}
2929 
2930 } // namespace boost
2931 
2932 namespace lemon {
2933 
2934 template <typename GR>
2935 class InDegMap;
2936 
2937  // LEMON-compatible property map for the in-degree of the nodes
2938 template<unsigned int N, class DirectedTag>
2939 class InDegMap<vigra::GridGraph<N, DirectedTag> >
2940 : public vigra::GridGraph<N, DirectedTag>::InDegMap
2941 {
2942  public:
2943  typedef vigra::GridGraph<N, DirectedTag> Graph;
2944 
2945  explicit InDegMap(const Graph& graph)
2946  : Graph::InDegMap(graph)
2947  {}
2948 };
2949 
2950 template <typename GR>
2951 class OutDegMap;
2952 
2953  // LEMON-compatible property map for the out-degree of the nodes
2954 template<unsigned int N, class DirectedTag>
2955 class OutDegMap<vigra::GridGraph<N, DirectedTag> >
2956 : public vigra::GridGraph<N, DirectedTag>::OutDegMap
2957 {
2958  public:
2959  typedef vigra::GridGraph<N, DirectedTag> Graph;
2960 
2961  explicit OutDegMap(const Graph& graph)
2962  : Graph::OutDegMap(graph)
2963  {}
2964 };
2965 
2966 
2967 } // namespace lemon
2968 
2969 namespace vigra {
2970 namespace boost_graph {
2971 
2972 using boost::get;
2973 
2974 }} // namespace vigra::boost_graph
2975 
2976 
2977 namespace std {
2978 
2979 template<unsigned int N, class DirectedTag>
2980 ostream& operator<<(ostream& out,
2982 {
2983  out << "v" << arg.scanOrderIndex();
2984  return out;
2985 }
2986 
2987 template<unsigned int N, class DirectedTag>
2988 ostream& operator<<(ostream& out,
2990 {
2991  out << "nb" << arg.index();
2992  return out;
2993 }
2994 
2995 } // namespace std
2996 
2997 
2998 
2999 #endif /* VIGRA_MULTI_GRIDGRAPH_HXX */
3000 
3001 
3002 
void put(vigra::MultiArrayView< N, T, Stride > &pmap, typename vigra::MultiArrayView< N, T, Stride >::difference_type const &k, U const &val)
Put value val at key k in the property map pmap (API: boost).
Definition: multi_gridgraph.hxx:2847
index_type maxEdgeId() const
Get the maximum ID of any edge in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2056
NodeMap(GridGraph const &g, T const &t)
Construct property map for the given graph g (preallocates an entry with initial value t for each nod...
Definition: multi_gridgraph.hxx:1582
out_back_edge_iterator get_out_back_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of outgoing backward edges of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:2301
Node baseNode(IncBackEdgeIt const &e) const
Return the start node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2193
vertex_descriptor Node
The Node descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1494
EdgeMap(difference_type const &shape, T const &t)
Construct property map for the given shape (preallocates an entry with initial value t for each edge ...
Definition: multi_gridgraph.hxx:1686
ArcMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each arc of t...
const value_type & const_reference
Definition: multi_array.hxx:678
MultiArrayShape< N >::type shape_type
Shape type of the graph and a node property map.
Definition: multi_gridgraph.hxx:1378
Node target(Arc const &a) const
Get the end node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2249
Arc arcFromId(index_type i) const
Get an arc descriptor for the given arc ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2092
std::pair< typename vigra::GridGraph< N, DirectedTag >::in_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::in_edge_iterator > in_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the incoming edges of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2774
MultiArrayShape< N+1 >::type edge_propmap_shape_type
Shape type of an edge property map (must have one additional dimension).
Definition: multi_gridgraph.hxx:1382
Define a grid graph in arbitrary dimensions.
Definition: multi_gridgraph.hxx:1365
vigra::GridGraph< N, DirectedTag >::vertex_descriptor source(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the start vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2786
Value & operator[](Key const &key)
Read/write access to the value associated with edge descriptor key.
GridGraph Graph
The graph type of InDegMap (works for directed and undirected graphs)
Definition: multi_gridgraph.hxx:1802
adjacency_iterator neighbor_vertex_iterator
Same as adjacency_iterator (API: VIGRA).
Definition: multi_gridgraph.hxx:1415
out_edge_iterator get_out_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first outgoing edge of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2274
Value operator[](const Key &key) const
Get the out-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1853
std::pair< typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator, typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator > adjacent_vertices(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the neighbor vertices of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2706
GridGraphOutEdgeIterator< N, true > IncBackEdgeIt
Iterator over only those incident edges of a node that end in a node with smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1532
Definition: graphs.hxx:57
MultiArrayShape< actual_dimension >::type difference_type
Definition: multi_array.hxx:690
Node runningNode(IncBackEdgeIt const &e) const
Return the end node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2221
Node baseNode(IncEdgeIt const &e) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2186
back_neighbor_vertex_iterator get_back_neighbor_vertex_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of backward neighbors of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:1996
R arg(const FFTWComplex< R > &a)
pahse
Definition: fftw3.hxx:1009
GridGraphOutArcIterator< N > out_edge_iterator
Iterator over the outgoing edges of a given vertex (API: boost::graph, use via boost::graph_traits
Definition: multi_gridgraph.hxx:1430
in_edge_iterator get_in_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of incoming edges of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2319
degree_size_type back_degree(vertex_descriptor const &v) const
Get the number of outgoing backward edges of the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:2335
boost::no_property vertex_property_type
The graph does not define internal property maps (API: boost::graph, use via boost::graph_traits
Definition: multi_gridgraph.hxx:1466
MultiCoordinateIterator< N > vertex_iterator
Iterator over the vertices of the graph (API: boost::graph, use via boost::graph_traits::verte...
Definition: multi_gridgraph.hxx:1406
GridGraphOutArcIterator< N > OutArcIt
Iterator over the outgoing edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1506
Node runningNode(IncEdgeIt const &e) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2214
Value & operator[](Key const &key)
Read/write access to the value associated with arc descriptor key.
vertex_iterator NodeIt
Iterator over all nodes of the graph (API: LEMON).
Definition: multi_gridgraph.hxx:1498
static const bool is_directed
'true' if the graph is directed (API: boost::graph)
Definition: multi_gridgraph.hxx:1371
GridGraphNeighborIterator< N, true > back_neighbor_vertex_iterator
Iterator over only those neighbor vertices of a given vertex that have smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1420
Node nodeFromId(index_type i) const
Get node descriptor for given node ID i (API: LEMON).
Definition: multi_gridgraph.hxx:1919
void set(Key const &k, Value const &v)
Set the property of edge desctiptor key to value v.
Definition: multi_gridgraph.hxx:1715
Node baseNode(OutArcIt const &a) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2200
index_type maxNodeId() const
Get the maximum ID of any node in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:1928
IndexMap(const GridGraph &)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1784
GridGraphArcDescriptor< N > edge_descriptor
The edge descriptor (API: boost::graph, use via boost::graph_traits::edge_descriptor).
Definition: multi_gridgraph.hxx:1450
vigra::GridGraph< N, DirectedTag >::edges_size_type num_edges(vigra::GridGraph< N, DirectedTag > const &g)
Return the number of edges in graph g (API: boost).
Definition: multi_gridgraph.hxx:2819
Definition: array_vector.hxx:903
Edge findEdge(Node const &u, Node const &v, Edge const &=lemon::INVALID) const
Get a descriptor for the edge connecting vertices u and v, or lemon::INVALID if no such edge exists (...
Definition: multi_gridgraph.hxx:2441
index_type id(Arc const &a) const
Get the ID (i.e. scan-order index an an arc property map) for the given ar a (API: LEMON)...
Definition: multi_gridgraph.hxx:2070
Define several graph tags related to graph traversal (API: boost::graph, use via boost::graph_traits<...
Definition: multi_gridgraph.hxx:1473
neighbor_vertex_iterator get_neighbor_vertex_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first neighbor of the given vertex (convenience function, the boost::graph API provides the free function boost::adjacent_vertices(v, graph), LEMON uses Graph::ArcIt(g, v)).
Definition: multi_gridgraph.hxx:1969
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2357
boost::disallow_parallel_edge_tag edge_parallel_category
The graph does not allow multiple edges between the same vertices (API: boost::graph, use via boost::graph_traits::edge_parallel_category).
Definition: multi_gridgraph.hxx:1461
Arc direct(Edge const &e, bool forward) const
Create an arc for the given edge e, oriented along the edge's natural (forward = true) or reversed (f...
Definition: multi_gridgraph.hxx:2123
Node runningNode(OutArcIt const &a) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2228
Value operator[](const Key &key) const
Get the in-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1819
GridGraphInArcIterator< N > InArcIt
Iterator over the incoming arcs of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1519
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:2833
vertices_size_type num_vertices() const
Get the number of vertices in this graph (convenience function, the boost::graph API provides the fre...
Definition: multi_gridgraph.hxx:2007
MultiArrayIndex vertices_size_type
Type to specify number of vertices (API: boost::graph, use via boost::graph_traits::vertices_s...
Definition: multi_gridgraph.hxx:1391
Type of a property map that returns the coordinate of a given node (API: LEMON).
Definition: multi_gridgraph.hxx:1769
DirectedTag directed_category
Is the graph directed or undirected ? (API: boost::graph, use via boost::graph_traits::directe...
Definition: multi_gridgraph.hxx:1455
void set(Key const &k, Value const &v)
Set the property of node desctiptor key to value v.
Definition: multi_gridgraph.hxx:1627
Type of an edge property map that maps edge descriptor objects onto property values of type T (API: L...
Definition: multi_gridgraph.hxx:1638
OutDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1847
std::ptrdiff_t MultiArrayIndex
Definition: multi_shape.hxx:55
std::pair< typename vigra::GridGraph< N, DirectedTag >::back_neighbor_vertex_iterator, typename vigra::GridGraph< N, DirectedTag >::back_neighbor_vertex_iterator > back_adjacent_vertices(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for only thise neighbor vertices of vertex v that have smaller ID th...
Definition: multi_gridgraph.hxx:2720
Value const & operator[](Key const &key) const
Get the grid coordinate of the node descriptor key.
Definition: multi_gridgraph.hxx:1789
index_type id(Edge const &e) const
Get the ID (i.e. scan-order index in an edge property map) for the given edges descriptor e (API: LEM...
Definition: multi_gridgraph.hxx:2025
Definition: accessor.hxx:43
Node v(Edge const &e) const
Get the end node of the given edge e (API: LEMON, the boost::graph API provides the free function bo...
Definition: multi_gridgraph.hxx:2265
edges_size_type arcNum() const
Get the number of arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2388
NodeMap(difference_type const &shape)
Construct property map for the given shape. (preallocates a zero-initialized entry for each node of a...
Definition: multi_gridgraph.hxx:1590
view_type::difference_type difference_type
Definition: multi_array.hxx:2405
degree_size_type degree(vertex_descriptor const &v) const
Get the total number of edges (incoming plus outgoing) of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2361
Value & operator[](Key const &key)
Read/write access to the value associated with node descriptor key.
MultiArrayIndex degree_size_type
Type to specify number of neighbors (API: boost::graph, use via boost::graph_traits::degree_si...
Definition: multi_gridgraph.hxx:1401
NodeMap(difference_type const &shape, T const &t)
Construct property map for the given shape. (preallocates an entry with initial value t for each node...
Definition: multi_gridgraph.hxx:1598
Definition: graphs.hxx:226
MultiArray & operator=(const MultiArray &rhs)
Definition: multi_array.hxx:2546
edge_iterator get_edge_iterator() const
Get edge iterator pointing to the first edge of the graph (convenience function, the boost::graph AP...
Definition: multi_gridgraph.hxx:2399
Arc direct(Edge const &e, Node const &n) const
Create an arc for the given edge e oriented so that node n is the starting node of the arc (API: LEMO...
Definition: multi_gridgraph.hxx:2135
vigra::GridGraph< N, DirectedTag >::vertices_size_type num_vertices(vigra::GridGraph< N, DirectedTag > const &g)
Return the number of vertices in graph g (API: boost).
Definition: multi_gridgraph.hxx:2694
out_back_edge_iterator get_out_back_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first outgoing backward edge of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:2292
view_type::reference reference
Definition: multi_array.hxx:2393
Node baseNode(OutBackArcIt const &a) const
Return the start node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2207
GridGraphArcIterator< N, false > ArcIt
Iterator over the acrs (directed edges) of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1515
back_neighbor_vertex_iterator get_back_neighbor_vertex_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first backward neighbor of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:1987
Arc oppositeArc(Arc const &a) const
Create an arc referring to the same edge as the given arc a, but with reversed direction (API: LEMON)...
Definition: multi_gridgraph.hxx:2161
NumericTraits< V >::Promote prod(TinyVectorBase< V, SIZE, D1, D2 > const &l)
product of the vector's elements
Definition: tinyvector.hxx:1895
index_type maxArcId() const
Get the maximal ID af any arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2101
edges_size_type num_edges() const
Get the number of edges in this graph (convenience function, boost::graph API provides the free funct...
Definition: multi_gridgraph.hxx:2374
vertices_size_type nodeNum() const
Get the number of nodes in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2014
degree_size_type out_degree(vertex_descriptor const &v) const
Get the number of outgoing edges of the given vertex (convenience function, the boost::graph API pro...
Definition: multi_gridgraph.hxx:2328
vigra::MultiArrayView< N, T, Stride >::const_reference get(vigra::MultiArrayView< N, T, Stride > const &pmap, typename vigra::MultiArrayView< N, T, Stride >::difference_type const &k)
Read the value at key k in property map pmap (API: boost).
Definition: multi_gridgraph.hxx:2859
Type of a property map that returns the number of incoming edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1797
EdgeMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each edge of ...
Definition: multi_gridgraph.hxx:1663
NodeMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each node of ...
Definition: multi_gridgraph.hxx:1575
MultiArrayIndex edges_size_type
Type to specify number of edges (API: boost::graph, use via boost::graph_traits::edges_size_ty...
Definition: multi_gridgraph.hxx:1396
GridGraph(shape_type const &shape, NeighborhoodType ntype=DirectNeighborhood)
Construct a grid graph with given shape and neighborhood type ntype.
Definition: multi_gridgraph.hxx:1877
neighbor_vertex_iterator get_neighbor_vertex_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of neighbors of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:1978
GridGraphInArcIterator< N > in_edge_iterator
Iterator over the incoming edges of a given vertex (API: boost::graph, use via boost::graph_traits
Definition: multi_gridgraph.hxx:1425
GridGraphOutArcIterator< N, true > out_back_edge_iterator
Iterator over only those outgoing edges of a given vertex that go to vertices with smaller IDs (API: ...
Definition: multi_gridgraph.hxx:1435
vigra::GridGraph< N, DirectedTag >::degree_size_type degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return total number of edges (incoming and outgoing) of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2671
vigra::GridGraph< N, DirectedTag >::degree_size_type in_degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return number of incoming edges of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2660
Node u(Edge const &e) const
Get the start node of the given edge e (API: LEMON, the boost::graph API provides the free function ...
Definition: multi_gridgraph.hxx:2257
Arc findArc(Node const &u, Node const &v, Arc const &=lemon::INVALID) const
Get a descriptor for the arc connecting vertices u and v, or lemon::INVALID if no such edge exists (A...
Definition: multi_gridgraph.hxx:2448
view_type::value_type value_type
Definition: multi_array.hxx:2381
shape_type vertex_descriptor
The vertex descriptor (API: boost::graph, use via boost::graph_traits::vertex_descriptor).
Definition: multi_gridgraph.hxx:1445
vigra::GridGraph< N, DirectedTag >::vertex_descriptor target(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the end vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2797
Class for fixed size vectors.This class contains an array of size SIZE of the specified VALUETYPE...
Definition: accessor.hxx:940
InDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1813
vigra::GridGraph< N, DirectedTag >::degree_size_type out_degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return number of outgoing edges of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2649
degree_size_type in_degree(vertex_descriptor const &v) const
Get the number of incoming edges of the given vertex (convenience function, the boost::graph API pro...
Definition: multi_gridgraph.hxx:2352
index_type id(Node const &v) const
Get the ID (i.e. scan-order index) for node desciptor v (API: LEMON).
Definition: multi_gridgraph.hxx:1897
vertex_iterator get_vertex_end_iterator() const
Get vertex iterator pointing beyond the valid range of vertices of this graph (convenience function...
Definition: multi_gridgraph.hxx:1960
GridGraphOutArcIterator< N, true > OutBackArcIt
Iterator over only those outgoing edges of a node that end in a node with smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1511
MultiArrayIndex index_type
Type of node and edge IDs.
Definition: multi_gridgraph.hxx:1386
vertex_iterator get_vertex_iterator() const
Get vertex iterator pointing to the first vertex of this graph (convenience function, the boost::graph API provides the free function boost::vertices(graph), LEMON uses Graph::NodeIt(graph)).
Definition: multi_gridgraph.hxx:1944
Edge edgeFromId(index_type i) const
Get the edge descriptor for the given edge ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2047
GridGraphArcDescriptor< N > Arc
The arc (directed edge) descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1502
bool direction(Arc const &a) const
Return true when the arc is looking on the underlying edge in its natural (i.e. forward) direction...
Definition: multi_gridgraph.hxx:2114
std::pair< typename vigra::GridGraph< N, DirectedTag >::vertex_iterator, typename vigra::GridGraph< N, DirectedTag >::vertex_iterator > vertices(vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the vertices of graph g (API: boost).
Definition: multi_gridgraph.hxx:2683
edge_iterator get_edge_end_iterator() const
Get edge iterator pointing beyond the valid range of edges of this graph (convenience function...
Definition: multi_gridgraph.hxx:2408
MultiArrayShape< N+1 >::type Edge
The edge descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1523
degree_size_type forward_degree(vertex_descriptor const &v) const
Get the number of outgoing forward edges of the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:2342
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:655
std::pair< typename vigra::GridGraph< N, DirectedTag >::out_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::out_edge_iterator > out_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the outgoing edges of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2746
in_edge_iterator get_in_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first incoming edge of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2310
vertex_iterator get_vertex_iterator(vertex_descriptor const &v) const
Get vertex iterator pointing to the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:1951
IndexMap indexMap() const
Create a property map that returns the coordinate of each node (API: LEMON GridGraph).
Definition: multi_gridgraph.hxx:2459
GridGraph Graph
The graph type of OutDegMap (works for directed and undirected graphs)
Definition: multi_gridgraph.hxx:1836
ostream & operator<<(ostream &s, const vigra::MultiArrayView< 2, T, C > &m)
Definition: matrix.hxx:2322
void set(Key const &k, Value const &v)
Set the property of arc desctiptor key to value v.
size_type size() const
Definition: array_vector.hxx:330
out_edge_iterator get_out_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of outgoing edges of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2283
Node oppositeNode(Node const &n, Edge const &e) const
Return the opposite node of the given node n along edge e (API: LEMON), or return lemon::INVALID if t...
Definition: multi_gridgraph.hxx:2148
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_iterator, typename vigra::GridGraph< N, DirectedTag >::edge_iterator > edges(vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the edges of graph g (API: boost).
Definition: multi_gridgraph.hxx:2809
std::pair< typename vigra::GridGraph< N, DirectedTag >::out_back_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::out_back_edge_iterator > out_back_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for only those outgoing edges of vertex v whose ID is smaller than t...
Definition: multi_gridgraph.hxx:2760
Type of a property map that returns the number of outgoing edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1831
use only direct neighbors
Definition: multi_shape.hxx:253
EdgeMap(difference_type const &shape)
Construct property map for the given shape (preallocates a zero-initialized entry for each edge of a ...
Definition: multi_gridgraph.hxx:1678
GridGraphArcIterator< N,!is_directed > edge_iterator
Iterator over the edges of a graph (API: boost::graph, use via boost::graph_traits::edge_itera...
Definition: multi_gridgraph.hxx:1440
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_shape.hxx:252
EdgeMap(GridGraph const &g, T const &t)
Construct property map for the given graph g (preallocates an entry with initial value t for each edg...
Definition: multi_gridgraph.hxx:1670
edges_size_type edgeNum() const
Get the number of edges in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2381
Type of a node property map that maps node descriptor objects onto property values of type T (API: LE...
Definition: multi_gridgraph.hxx:1550
Node source(Arc const &a) const
Get the start node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2242
GridGraphEdgeIterator< N,!is_directed > EdgeIt
Iterator over the edges of the graph (API: LEMON).
Definition: multi_gridgraph.hxx:1536
Iterate over a virtual array where each element contains its coordinate.
Definition: multi_iterator.hxx:89
GridGraphOutEdgeIterator< N > IncEdgeIt
Iterator over the incident edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1527
std::pair< edge_descriptor, bool > edge(vertex_descriptor const &u, vertex_descriptor const &v) const
Get a descriptor for the edge connecting vertices u and v, or (lemon::INVALID, false) if no such edg...
Definition: multi_gridgraph.hxx:2421
view_type::const_reference const_reference
Definition: multi_array.hxx:2397
GridGraphNeighborIterator< N > adjacency_iterator
Iterator over the neighbor vertices of a given vertex (API: boost::graph, use via boost::graph_traits...
Definition: multi_gridgraph.hxx:1411
Node const & pos(Node const &v) const
Get the grid cordinate of the given node v (convenience function).
Definition: multi_gridgraph.hxx:1935
Type of an arc property map that maps arc descriptor objects onto property values of type T (API: LEM...
Definition: multi_gridgraph.hxx:1726
Node runningNode(OutBackArcIt const &a) const
Return the end node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2235

© 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