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

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

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.12.1