36 #ifndef VIGRA_MULTI_GRIDGRAPH_HXX
37 #define VIGRA_MULTI_GRIDGRAPH_HXX
39 #include "multi_iterator.hxx"
40 #include "multi_array.hxx"
43 template <
unsigned int N>
44 struct NeighborhoodTests;
70 template<
unsigned int N>
71 class GridGraphArcDescriptor
72 :
public MultiArrayShape<N+1>::type
75 typedef typename MultiArrayShape<N+1>::type base_type;
76 typedef typename base_type::value_type value_type;
77 typedef base_type edge_coord_type;
78 typedef value_type index_type;
79 typedef typename MultiArrayShape<N>::type shape_type;
80 typedef TinyVectorView<value_type, N> vertex_descriptor_view;
82 GridGraphArcDescriptor()
86 GridGraphArcDescriptor(lemon::Invalid)
91 GridGraphArcDescriptor(base_type
const & b,
bool reversed)
93 is_reversed_(reversed)
96 GridGraphArcDescriptor(shape_type
const &vertex,
97 index_type edge_index,
99 : base_type(detail::DontInit())
101 set(vertex, edge_index, reversed);
104 void set(shape_type
const &vertex, index_type edge_index,
bool reversed)
106 this->
template subarray<0,N>() = vertex;
107 (*this)[N] = edge_index;
108 is_reversed_ = reversed;
111 void increment(GridGraphArcDescriptor
const & diff,
bool opposite=
false)
113 if(diff.is_reversed_)
115 is_reversed_ = !opposite;
116 this->
template subarray<0,N>() += diff.template subarray<0,N>();
120 is_reversed_ = opposite;
122 (*this)[N] = diff[N];
125 bool isReversed()
const
130 vertex_descriptor_view vertexDescriptor()
const
132 return this->
template subarray<0,N>();
135 value_type edgeIndex()
const
149 : pow(3.0, (
int)N) - 1;
152 template <
unsigned int N, NeighborhoodType>
153 struct GridGraphMaxDegree;
155 template <
unsigned int N>
156 struct GridGraphMaxDegree<N, DirectNeighborhood>
161 template <
unsigned int N>
162 struct GridGraphMaxDegree<N, IndirectNeighborhood>
167 template <
class Shape>
174 for(
unsigned int k=0; k<shape.size(); ++k)
175 res += 2*
prod(shape - Shape::unitVector(k));
179 res =
prod(3*shape - Shape(2)) -
prod(shape);
188 template <
class Shape>
190 computeNeighborOffsets(ArrayVector<Shape>
const & neighborOffsets,
191 ArrayVector<ArrayVector<bool> >
const & neighborExists,
192 ArrayVector<ArrayVector<Shape> > & incrementOffsets,
193 ArrayVector<ArrayVector<GridGraphArcDescriptor<Shape::static_size> > > & edgeDescriptorOffsets,
194 ArrayVector<ArrayVector<MultiArrayIndex> > & indices,
195 ArrayVector<ArrayVector<MultiArrayIndex> > & backIndices,
198 typedef GridGraphArcDescriptor<Shape::static_size> EdgeDescriptor;
200 unsigned int borderTypeCount = neighborExists.size();
201 incrementOffsets.resize(borderTypeCount);
202 edgeDescriptorOffsets.resize(borderTypeCount);
203 indices.resize(borderTypeCount);
204 backIndices.resize(borderTypeCount);
206 for(
unsigned int k=0; k<borderTypeCount; ++k)
208 incrementOffsets[k].clear();
209 edgeDescriptorOffsets[k].clear();
211 backIndices[k].clear();
213 for(
unsigned int j=0; j < neighborOffsets.size(); ++j)
215 if(neighborExists[k][j])
217 if(incrementOffsets[k].size() == 0)
219 incrementOffsets[k].push_back(neighborOffsets[j]);
223 incrementOffsets[k].push_back(neighborOffsets[j] - neighborOffsets[indices[k].back()]);
226 if(directed || j < neighborOffsets.size() / 2)
228 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(Shape(), j));
230 else if(edgeDescriptorOffsets[k].size() == 0 || !edgeDescriptorOffsets[k].back().isReversed())
232 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j], neighborOffsets.size()-j-1,
true));
236 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j] - neighborOffsets[indices[k].back()],
237 neighborOffsets.size()-j-1,
true));
240 indices[k].push_back(j);
241 if(j < neighborOffsets.size() / 2)
242 backIndices[k].push_back(j);
250 template<
unsigned int N,
bool BackEdgesOnly=false>
251 class GridGraphNeighborIterator
254 typedef typename MultiArrayShape<N>::type shape_type;
255 typedef MultiCoordinateIterator<N> vertex_iterator;
256 typedef typename vertex_iterator::value_type vertex_descriptor;
257 typedef vertex_descriptor value_type;
258 typedef typename vertex_iterator::pointer pointer;
259 typedef typename vertex_iterator::const_pointer const_pointer;
260 typedef typename vertex_iterator::reference reference;
261 typedef typename vertex_iterator::const_reference const_reference;
264 typedef std::forward_iterator_tag iterator_category;
266 friend struct NeighborhoodTests<N>;
268 GridGraphNeighborIterator()
269 : neighborOffsets_(0),
274 template <
class DirectedTag>
275 GridGraphNeighborIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
276 : neighborOffsets_(0),
281 unsigned int nbtype = g.get_border_type(v);
282 neighborOffsets_ = &(*g.neighborIncrementArray())[nbtype];
283 neighborIndices_ = &(*g.neighborIndexArray(BackEdgesOnly))[nbtype];
287 template <
class DirectedTag>
288 GridGraphNeighborIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
289 : neighborOffsets_(0),
294 unsigned int nbtype = g.get_border_type(v);
295 neighborOffsets_ = &(*g.neighborIncrementArray())[nbtype];
296 neighborIndices_ = &(*g.neighborIndexArray(BackEdgesOnly))[nbtype];
304 GridGraphNeighborIterator & operator++()
311 GridGraphNeighborIterator operator++(
int)
313 GridGraphNeighborIterator ret(*
this);
318 const_reference operator*()
const
323 const_pointer operator->()
const
328 operator const_reference()
const
333 const_reference
target()
const
345 return (*neighborIndices_)[index_];
348 bool operator==(GridGraphNeighborIterator
const & other)
const
350 return index_ == other.index_;
353 bool operator!=(GridGraphNeighborIterator
const & other)
const
355 return index_ != other.index_;
368 GridGraphNeighborIterator getEndIterator()
const
370 GridGraphNeighborIterator res(*
this);
378 GridGraphNeighborIterator(ArrayVector<shape_type>
const & neighborOffsets,
379 ArrayVector<index_type>
const & neighborIndices,
380 ArrayVector<index_type>
const & backIndices,
382 : neighborOffsets_(&neighborOffsets),
383 neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
393 target_ += (*neighborOffsets_)[index_];
396 ArrayVector<shape_type>
const * neighborOffsets_;
397 ArrayVector<index_type>
const * neighborIndices_;
398 vertex_descriptor target_;
402 template<
unsigned int N,
bool BackEdgesOnly>
403 class GridGraphEdgeIterator;
405 template<
unsigned int N,
bool BackEdgesOnly=false>
406 class GridGraphOutEdgeIterator
409 typedef typename MultiArrayShape<N>::type shape_type;
411 typedef GridGraphArcDescriptor<N> arc_descriptor;
412 typedef typename MultiArrayShape<N+1>::type value_type;
413 typedef value_type
const & reference;
414 typedef value_type
const & const_reference;
415 typedef value_type
const * pointer;
416 typedef value_type
const * const_pointer;
418 typedef std::forward_iterator_tag iterator_category;
420 friend struct NeighborhoodTests<N>;
421 friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
423 GridGraphOutEdgeIterator()
424 : neighborOffsets_(0),
429 template <
class DirectedTag>
430 GridGraphOutEdgeIterator(GridGraph<N, DirectedTag>
const & g,
431 typename GridGraph<N, DirectedTag>::NodeIt
const & v,
433 : neighborOffsets_(0),
438 unsigned int nbtype = g.get_border_type(v);
439 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], *v, opposite);
442 template <
class DirectedTag>
443 GridGraphOutEdgeIterator(GridGraph<N, DirectedTag>
const & g,
444 typename GridGraph<N, DirectedTag>::Node
const & v,
446 : neighborOffsets_(0),
451 unsigned int nbtype = g.get_border_type(v);
452 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], v, opposite);
455 GridGraphOutEdgeIterator & operator++()
461 GridGraphOutEdgeIterator operator++(
int)
463 GridGraphOutEdgeIterator ret(*
this);
468 const_reference operator*()
const
470 return edge_descriptor_;
473 operator const_reference()
const
475 return edge_descriptor_;
478 const_pointer operator->()
const
480 return &edge_descriptor_;
483 index_type index()
const
488 index_type neighborIndex()
const
490 return (*neighborIndices_)[index_];
493 arc_descriptor
const & arcDescriptor()
const
495 return edge_descriptor_;
498 bool operator==(GridGraphOutEdgeIterator
const & other)
const
500 return index_ == other.index();
503 bool operator!=(GridGraphOutEdgeIterator
const & other)
const
505 return index_ != other.index();
510 return index_ < (index_type)neighborIndices_->size();
515 return index_ >= (index_type)neighborIndices_->size();
518 GridGraphOutEdgeIterator getEndIterator()
const
520 GridGraphOutEdgeIterator res(*
this);
521 res.index_ = (index_type)neighborIndices_->size();
528 GridGraphOutEdgeIterator(ArrayVector<arc_descriptor>
const & neighborOffsets,
529 ArrayVector<index_type>
const & neighborIndices,
530 ArrayVector<index_type>
const & backIndices,
531 shape_type
const &
source)
532 : neighborOffsets_(0),
537 init(&neighborOffsets, BackEdgesOnly ? &backIndices : &neighborIndices, source);
540 void init(ArrayVector<arc_descriptor>
const * neighborOffsets,
541 ArrayVector<index_type>
const * neighborIndices,
542 shape_type
const &
source,
545 neighborOffsets_ = neighborOffsets;
546 neighborIndices_ = neighborIndices;
547 edge_descriptor_ = arc_descriptor(source, 0);
549 updateEdgeDescriptor(opposite);
552 void increment(
bool opposite)
555 updateEdgeDescriptor(opposite);
558 void updateEdgeDescriptor(
bool opposite)
561 edge_descriptor_.increment((*neighborOffsets_)[index_], opposite);
564 ArrayVector<arc_descriptor>
const * neighborOffsets_;
565 ArrayVector<index_type>
const * neighborIndices_;
566 arc_descriptor edge_descriptor_;
570 template<
unsigned int N,
bool BackEdgesOnly=false>
571 class GridGraphOutArcIterator
572 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
575 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
576 typedef typename MultiArrayShape<N>::type shape_type;
578 typedef GridGraphArcDescriptor<N> value_type;
579 typedef value_type
const & reference;
580 typedef value_type
const & const_reference;
581 typedef value_type
const * pointer;
582 typedef value_type
const * const_pointer;
584 typedef std::forward_iterator_tag iterator_category;
586 friend struct NeighborhoodTests<N>;
587 friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
589 GridGraphOutArcIterator()
593 explicit GridGraphOutArcIterator(base_type
const & b)
597 template <
class DirectedTag>
598 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
602 template <
class DirectedTag>
603 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
607 GridGraphOutArcIterator & operator++()
609 base_type::operator++();
613 GridGraphOutArcIterator operator++(
int)
615 GridGraphOutArcIterator ret(*
this);
620 const_reference operator*()
const
622 return this->edge_descriptor_;
625 operator const_reference()
const
627 return this->edge_descriptor_;
630 const_pointer operator->()
const
632 return &this->edge_descriptor_;
635 GridGraphOutArcIterator getEndIterator()
const
637 return GridGraphOutArcIterator(base_type::getEndIterator());
643 GridGraphOutArcIterator(ArrayVector<value_type>
const & neighborOffsets,
644 ArrayVector<index_type>
const & neighborIndices,
645 ArrayVector<index_type>
const & backIndices,
646 shape_type
const &
source)
647 : base_type(neighborOffsets, neighborIndices, backIndices, source)
651 template<
unsigned int N,
bool BackEdgesOnly=false>
652 class GridGraphInArcIterator
653 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
656 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
657 typedef typename MultiArrayShape<N>::type shape_type;
659 typedef GridGraphArcDescriptor<N> value_type;
660 typedef value_type
const & reference;
661 typedef value_type
const & const_reference;
662 typedef value_type
const * pointer;
663 typedef value_type
const * const_pointer;
665 typedef std::forward_iterator_tag iterator_category;
667 friend struct NeighborhoodTests<N>;
669 GridGraphInArcIterator()
673 explicit GridGraphInArcIterator(base_type
const & b)
677 template <
class DirectedTag>
678 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
679 : base_type(g, v, true)
682 template <
class DirectedTag>
683 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
684 : base_type(g, v, true)
687 GridGraphInArcIterator & operator++()
689 base_type::increment(
true);
693 GridGraphInArcIterator operator++(
int)
695 GridGraphInArcIterator ret(*
this);
700 const_reference operator*()
const
702 return this->edge_descriptor_;
705 operator const_reference()
const
707 return this->edge_descriptor_;
710 const_pointer operator->()
const
712 return &this->edge_descriptor_;
715 GridGraphInArcIterator getEndIterator()
const
717 return GridGraphInArcIterator(base_type::getEndIterator());
723 template<
unsigned int N,
bool BackEdgesOnly>
724 class GridGraphEdgeIterator
727 typedef GridGraphEdgeIterator<N, BackEdgesOnly> self_type;
728 typedef MultiCoordinateIterator<N> vertex_iterator;
729 typedef typename vertex_iterator::value_type vertex_descriptor;
730 typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
731 typedef typename MultiArrayShape<N+1>::type edge_descriptor;
732 typedef edge_descriptor value_type;
733 typedef value_type
const * pointer;
734 typedef value_type
const * const_pointer;
735 typedef value_type
const & reference;
736 typedef value_type
const & const_reference;
737 typedef typename MultiArrayShape<N>::type shape_type;
740 typedef std::forward_iterator_tag iterator_category;
742 friend struct NeighborhoodTests<N>;
744 GridGraphEdgeIterator()
745 : neighborOffsets_(0),
749 template <
class DirectedTag>
750 GridGraphEdgeIterator(GridGraph<N, DirectedTag>
const & g)
751 : neighborOffsets_(g.edgeIncrementArray()),
752 neighborIndices_(g.neighborIndexArray(BackEdgesOnly)),
754 outEdgeIterator_(g, vertexIterator_)
756 if(outEdgeIterator_.atEnd())
759 if(vertexIterator_.isValid())
760 outEdgeIterator_ = out_edge_iterator(g, vertexIterator_);
764 GridGraphEdgeIterator & operator++()
767 if(outEdgeIterator_.atEnd())
770 if(vertexIterator_.isValid())
772 unsigned int borderType = vertexIterator_.borderType();
773 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
779 GridGraphEdgeIterator operator++(
int)
781 GridGraphEdgeIterator ret(*
this);
786 const_reference operator*()
const
788 return *outEdgeIterator_;
791 operator const_reference()
const
793 return *outEdgeIterator_;
796 const_pointer operator->()
const
798 return outEdgeIterator_.operator->();
801 bool operator==(GridGraphEdgeIterator
const & other)
const
803 return (vertexIterator_ == other.vertexIterator_ && outEdgeIterator_ == other.outEdgeIterator_);
806 bool operator!=(GridGraphEdgeIterator
const & other)
const
813 return vertexIterator_.isValid();
821 GridGraphEdgeIterator getEndIterator()
const
823 GridGraphEdgeIterator ret(*
this);
824 ret.vertexIterator_ = vertexIterator_.getEndIterator();
825 vertex_iterator lastVertex = ret.vertexIterator_ - 1;
826 unsigned int borderType = lastVertex.borderType();
827 ret.outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *lastVertex);
828 ret.outEdgeIterator_ = ret.outEdgeIterator_.getEndIterator();
835 GridGraphEdgeIterator(ArrayVector<ArrayVector<typename out_edge_iterator::value_type> >
const & neighborOffsets,
836 ArrayVector<ArrayVector<index_type> >
const & neighborIndices,
837 ArrayVector<ArrayVector<index_type> >
const & backIndices,
838 shape_type
const & shape)
839 : neighborOffsets_(&neighborOffsets),
840 neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
841 vertexIterator_(shape),
842 outEdgeIterator_(neighborOffsets[vertexIterator_.borderType()],
843 neighborIndices[vertexIterator_.borderType()],
844 backIndices[vertexIterator_.borderType()], shape_type())
846 if(outEdgeIterator_.atEnd())
849 if(vertexIterator_.isValid())
851 unsigned int borderType = vertexIterator_.borderType();
852 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
857 ArrayVector<ArrayVector<typename out_edge_iterator::value_type> >
const * neighborOffsets_;
858 ArrayVector<ArrayVector<index_type> >
const * neighborIndices_;
859 vertex_iterator vertexIterator_;
860 out_edge_iterator outEdgeIterator_;
863 template<
unsigned int N,
bool BackEdgesOnly>
864 class GridGraphArcIterator
865 :
public GridGraphEdgeIterator<N, BackEdgesOnly>
868 typedef GridGraphEdgeIterator<N, BackEdgesOnly> base_type;
869 typedef GridGraphArcIterator<N, BackEdgesOnly> self_type;
870 typedef MultiCoordinateIterator<N> vertex_iterator;
871 typedef typename vertex_iterator::value_type vertex_descriptor;
872 typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
873 typedef typename out_edge_iterator::value_type edge_descriptor;
874 typedef edge_descriptor value_type;
875 typedef value_type
const * pointer;
876 typedef value_type
const * const_pointer;
877 typedef value_type
const & reference;
878 typedef value_type
const & const_reference;
879 typedef typename MultiArrayShape<N>::type shape_type;
882 typedef std::forward_iterator_tag iterator_category;
884 friend struct NeighborhoodTests<N>;
886 GridGraphArcIterator()
890 explicit GridGraphArcIterator(base_type
const & b)
894 template <
class DirectedTag>
895 GridGraphArcIterator(GridGraph<N, DirectedTag>
const & g)
899 GridGraphArcIterator & operator++()
901 base_type::operator++();
905 GridGraphArcIterator operator++(
int)
907 GridGraphArcIterator ret(*
this);
912 const_reference operator*()
const
914 return *(this->outEdgeIterator_);
917 operator const_reference()
const
919 return *(this->outEdgeIterator_);
922 const_pointer operator->()
const
924 return this->outEdgeIterator_.operator->();
927 GridGraphArcIterator getEndIterator()
const
929 return GridGraphArcIterator(base_type::getEndIterator());
935 GridGraphArcIterator(ArrayVector<ArrayVector<value_type> >
const & neighborOffsets,
936 ArrayVector<ArrayVector<index_type> >
const & neighborIndices,
937 ArrayVector<ArrayVector<index_type> >
const & backIndices,
938 shape_type
const & shape)
939 : base_type(neighborOffsets, neighborIndices, backIndices, shape)
943 template<
unsigned int N>
944 inline bool operator==(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
949 template<
unsigned int N>
950 inline bool operator!=(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
955 template<
unsigned int N>
956 inline bool operator==(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
961 template<
unsigned int N>
962 inline bool operator!=(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
967 #define VIGRA_LEMON_INVALID_COMPARISON(type) \
968 template<unsigned int N, bool BackEdgesOnly> \
969 inline bool operator==(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
973 template<unsigned int N, bool BackEdgesOnly> \
974 inline bool operator!=(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
976 return i.isValid(); \
978 template<unsigned int N, bool BackEdgesOnly> \
979 inline bool operator==(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
983 template<unsigned int N, bool BackEdgesOnly> \
984 inline bool operator!=(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
986 return i.isValid(); \
989 VIGRA_LEMON_INVALID_COMPARISON(GridGraphNeighborIterator)
990 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutEdgeIterator)
991 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutArcIterator)
992 VIGRA_LEMON_INVALID_COMPARISON(GridGraphInArcIterator)
993 VIGRA_LEMON_INVALID_COMPARISON(GridGraphEdgeIterator)
994 VIGRA_LEMON_INVALID_COMPARISON(GridGraphArcIterator)
996 #undef VIGRA_LEMON_INVALID_COMPARISON
998 using boost::directed_tag;
999 using boost::undirected_tag;
1003 template <
unsigned int N,
class DirectedTag>
1004 struct GridGraphBase;
1006 template <
unsigned int N>
1007 struct GridGraphBase<N, directed_tag>
1011 :
public MultiArray<N+1, Multiband<T> >
1014 typedef MultiArray<N+1, Multiband<T> > base_type;
1015 typedef typename base_type::difference_type difference_type;
1016 typedef typename base_type::key_type key_type;
1017 typedef typename base_type::value_type value_type;
1018 typedef typename base_type::reference reference;
1019 typedef typename base_type::const_reference const_reference;
1020 typedef boost::read_write_property_map_tag category;
1022 typedef lemon::True ReferenceMapTag;
1023 typedef key_type Key;
1024 typedef value_type Value;
1025 typedef reference Reference;
1026 typedef const_reference ConstReference;
1032 explicit ArcMap(GridGraph<N, directed_tag>
const & g)
1033 : base_type(g.arc_propmap_shape())
1036 ArcMap(GridGraph<N, directed_tag>
const & g, T
const & t)
1037 : base_type(g.arc_propmap_shape(), t)
1040 explicit ArcMap(difference_type
const & shape)
1044 ArcMap(difference_type
const & shape, T
const & t)
1045 : base_type(shape, t)
1048 ArcMap & operator=(ArcMap
const & m)
1050 base_type::operator=(m);
1054 ArcMap & operator=(base_type
const & m)
1056 base_type::operator=(m);
1062 void set(Key
const & k, Value
const & v)
1069 template <
unsigned int N>
1070 struct GridGraphBase<N, undirected_tag>
1072 typedef lemon::True UndirectedTag;
1076 :
public MultiArray<N+1, Multiband<T> >
1079 typedef MultiArray<N+1, Multiband<T> > base_type;
1080 typedef GridGraphArcDescriptor<N> difference_type;
1081 typedef difference_type key_type;
1082 typedef typename base_type::value_type value_type;
1083 typedef typename base_type::reference reference;
1084 typedef typename base_type::const_reference const_reference;
1085 typedef boost::read_write_property_map_tag category;
1087 typedef lemon::True ReferenceMapTag;
1088 typedef key_type Key;
1089 typedef value_type Value;
1090 typedef reference Reference;
1091 typedef const_reference ConstReference;
1097 explicit ArcMap(GridGraph<N, undirected_tag>
const & g)
1098 : base_type(g.arc_propmap_shape()),
1102 ArcMap(GridGraph<N, undirected_tag>
const & g, T
const & t)
1103 : base_type(g.arc_propmap_shape(), t),
1107 ArcMap & operator=(ArcMap
const & m)
1109 base_type::operator=(m);
1113 ArcMap & operator=(base_type
const & m)
1115 base_type::operator=(m);
1119 reference operator[](difference_type
const & s)
1123 return base_type::operator[](graph_->directedArc(s));
1127 return base_type::operator[](s);
1131 const_reference operator[](difference_type
const & s)
const
1135 return base_type::operator[](graph_->directedArc(s));
1139 return base_type::operator[](s);
1143 void set(Key
const & k, Value
const & v)
1148 GridGraph<N, undirected_tag>
const * graph_;
1364 template<
unsigned int N,
class DirectedTag>
1366 :
public detail::GridGraphBase<N, DirectedTag>
1371 static const bool is_directed = IsSameType<DirectedTag, directed_tag>::value;
1373 typedef detail::GridGraphBase<N, DirectedTag> base_type;
1474 :
virtual public boost::bidirectional_graph_tag,
1475 virtual public boost::adjacency_graph_tag,
1476 virtual public boost::vertex_list_graph_tag,
1477 virtual public boost::edge_list_graph_tag,
1478 virtual public boost::adjacency_matrix_tag
1502 typedef GridGraphArcDescriptor<N>
Arc;
1515 typedef GridGraphArcIterator<N, false>
ArcIt;
1536 typedef GridGraphEdgeIterator<N, !is_directed>
EdgeIt;
1538 typedef lemon::True NodeNumTag;
1539 typedef lemon::True EdgeNumTag;
1540 typedef lemon::True ArcNumTag;
1541 typedef lemon::True FindEdgeTag;
1542 typedef lemon::True FindArcTag;
1560 typedef boost::read_write_property_map_tag category;
1562 typedef lemon::True ReferenceMapTag;
1563 typedef key_type Key;
1564 typedef value_type Value;
1565 typedef reference Reference;
1566 typedef const_reference ConstReference;
1598 NodeMap(difference_type
const & shape, T
const & t)
1608 NodeMap & operator=(base_type
const & m)
1622 Value
const &
operator[](Key
const & key)
const;
1627 void set(Key
const & k, Value
const & v)
1648 typedef boost::read_write_property_map_tag category;
1650 typedef lemon::True ReferenceMapTag;
1652 typedef value_type Value;
1653 typedef reference Reference;
1654 typedef const_reference ConstReference;
1686 EdgeMap(difference_type
const & shape, T
const & t)
1696 EdgeMap & operator=(base_type
const & m)
1710 Value
const &
operator[](Key
const & key)
const;
1715 void set(Key
const & k, Value
const & v)
1745 explicit ArcMap(difference_type
const & shape);
1751 ArcMap(difference_type
const & shape, T
const & t);
1759 Value
const &
operator[](Key
const & key)
const;
1763 void set(Key
const & k, Value
const & v);
1775 typedef Value value_type;
1776 typedef Value const & reference;
1777 typedef boost::readable_property_map_tag category;
1807 typedef Value value_type;
1808 typedef Value
const & reference;
1809 typedef boost::readable_property_map_tag category;
1841 typedef Value value_type;
1842 typedef Value
const & reference;
1843 typedef boost::readable_property_map_tag category;
1879 num_vertices_(
prod(shape)),
1880 num_edges_(gridGraphEdgeCount(shape, ntype,
is_directed)),
1881 neighborhoodType_(ntype)
1887 detail::makeArrayNeighborhood(neighborOffsets_, neighborExists, neighborhoodType_);
1888 detail::computeNeighborOffsets(neighborOffsets_, neighborExists, incrementalOffsets_,
1889 edgeDescriptorOffsets_, neighborIndices_, backIndices_,
is_directed);
1899 return detail::CoordinateToScanOrder<N>::exec(shape(), v);
1902 index_type
id(
NodeIt const & v)
const
1904 return v.scanOrderIndex();
1921 Node res(SkipInitialization);
1922 detail::ScanOrderToCoordinate<N>::exec(i, shape(), res);
1930 return prod(shape()) - 1;
2009 return num_vertices_;
2027 return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), e);
2030 index_type
id(
EdgeIt const & e)
const
2049 Edge res(SkipInitialization);
2050 detail::ScanOrderToCoordinate<N+1>::exec(i, edge_propmap_shape(), res);
2063 Arc a(lastNode, backIndices_[get_border_type(lastNode)].back(),
false);
2064 return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), a);
2072 return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), directedArc(a));
2075 index_type
id(
ArcIt const & a)
const
2095 detail::ScanOrderToCoordinate<N+1>::exec(i, arc_propmap_shape(), res);
2096 return undirectedArc(res);
2106 index_type n = neighborIndices_[get_border_type(lastNode)][0];
2107 Arc a(neighbor(lastNode, n), oppositeIndex(n),
false);
2108 return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), a);
2116 return !a.isReversed();
2126 return Arc(e, !forward);
2128 return Arc(
v(e), oppositeIndex(e[N]),
true);
2141 return Arc(lemon::INVALID);
2150 Node start(
u(e)), end(
v(e));
2155 return Node(lemon::INVALID);
2164 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2165 :
Arc(a, !a.isReversed());
2169 Arc directedArc(
Arc const & a)
const
2171 return a.isReversed()
2172 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2177 Arc undirectedArc(
Arc const & a)
const
2179 return a.edgeIndex() < maxUniqueDegree()
2181 :
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
true);
2188 return source(e.arcDescriptor());
2195 return source(e.arcDescriptor());
2216 return target(e.arcDescriptor());
2223 return target(e.arcDescriptor());
2244 return source_or_target(a,
true);
2251 return source_or_target(a,
false);
2259 return Node(e.template subarray<0,N>());
2267 return Node(e.template subarray<0,N>()) + neighborOffsets_[e[N]];
2344 unsigned int bt = get_border_type(v);
2420 std::pair<edge_descriptor, bool>
2421 edge(vertex_descriptor
const &
u, vertex_descriptor
const & v)
const
2423 std::pair<edge_descriptor, bool> res(lemon::INVALID,
false);
2426 end = i.getEndIterator();
2427 for (; i != end; ++i)
2431 res.first = make_edge_descriptor(u, i.neighborIndex());
2443 return this->
edge(u, v).first;
2450 return this->
edge(u, v).first;
2467 bool isDirected()
const
2484 shape_type
const & shape()
const
2492 res.template subarray<0, N>() = shape_;
2493 res[N] = maxUniqueDegree();
2500 res.template subarray<0, N>() = shape_;
2501 res[N] = maxDegree();
2505 unsigned int get_border_type(vertex_descriptor
const & v)
const
2507 return detail::BorderTypeImpl<N>::exec(v, shape_);
2510 unsigned int get_border_type(vertex_iterator
const & v)
const
2512 return v.borderType();
2515 index_type oppositeIndex(index_type neighborIndex)
const
2517 return maxDegree() - neighborIndex - 1;
2524 index_type neighborIndex)
const
2526 if(neighborIndex < maxUniqueDegree())
2529 return edge_descriptor(neighbor(v, neighborIndex), oppositeIndex(neighborIndex),
true);
2532 shape_type
const & neighborOffset(index_type neighborIndex)
const
2534 return neighborOffsets_[neighborIndex];
2537 vertex_descriptor neighbor(vertex_descriptor
const & v, index_type neighborIndex)
const
2539 return v + neighborOffsets_[neighborIndex];
2547 if ((return_source && e.isReversed()) ||
2548 (!return_source && !e.isReversed()))
2550 return neighbor(e.vertexDescriptor(), e.edgeIndex());
2554 return e.vertexDescriptor();
2558 NeighborOffsetArray
const * neighborOffsetArray()
const
2560 return &neighborOffsets_;
2563 RelativeNeighborOffsetsArray
const * neighborIncrementArray()
const
2565 return &incrementalOffsets_;
2568 RelativeEdgeOffsetsArray
const * edgeIncrementArray()
const
2570 return &edgeDescriptorOffsets_;
2573 IndexArray
const * neighborIndexArray(
bool backEdgesOnly)
const
2575 return backEdgesOnly
2577 : &neighborIndices_;
2581 NeighborOffsetArray neighborOffsets_;
2582 IndexArray neighborIndices_, backIndices_;
2583 RelativeNeighborOffsetsArray incrementalOffsets_;
2584 RelativeEdgeOffsetsArray edgeDescriptorOffsets_;
2604 template <
unsigned int N,
class T,
class Acc>
2605 struct property_traits<vigra::MultiArray<N, T, Acc> >
2608 typedef typename type::key_type key_type;
2609 typedef typename type::value_type value_type;
2610 typedef typename type::reference reference;
2611 typedef boost::read_write_property_map_tag category;
2614 template <
unsigned int N,
class T,
class Acc>
2615 struct property_traits<vigra::MultiArray<N, T, Acc> const>
2618 typedef typename type::key_type key_type;
2619 typedef typename type::value_type value_type;
2620 typedef typename type::const_reference reference;
2621 typedef boost::readable_property_map_tag category;
2624 template <
unsigned int N,
class T,
class Str
ide>
2625 struct property_traits<vigra::MultiArrayView<N, T, Stride> >
2628 typedef typename type::key_type key_type;
2629 typedef typename type::value_type value_type;
2630 typedef typename type::reference reference;
2631 typedef boost::read_write_property_map_tag category;
2634 template <
unsigned int N,
class T,
class Str
ide>
2635 struct property_traits<vigra::MultiArrayView<N, T, Stride> const>
2638 typedef typename type::key_type key_type;
2639 typedef typename type::value_type value_type;
2640 typedef typename type::const_reference reference;
2641 typedef boost::readable_property_map_tag category;
2646 template<
unsigned int N,
class DirectedTag>
2657 template<
unsigned int N,
class DirectedTag>
2668 template<
unsigned int N,
class DirectedTag>
2679 template<
unsigned int N,
class DirectedTag>
2681 std::pair<typename vigra::GridGraph<N, DirectedTag>::vertex_iterator,
2691 template<
unsigned int N,
class DirectedTag>
2702 template<
unsigned int N,
class DirectedTag>
2704 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2716 template<
unsigned int N,
class DirectedTag>
2718 std::pair<typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator,
2728 template<
unsigned int N,
class DirectedTag>
2730 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2742 template<
unsigned int N,
class DirectedTag>
2744 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator,
2756 template<
unsigned int N,
class DirectedTag>
2758 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator,
2770 template<
unsigned int N,
class DirectedTag>
2772 std::pair<typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator,
2783 template<
unsigned int N,
class DirectedTag>
2794 template<
unsigned int N,
class DirectedTag>
2805 template<
unsigned int N,
class DirectedTag>
2807 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_iterator,
2816 template<
unsigned int N,
class DirectedTag>
2831 template<
unsigned int N,
class DirectedTag>
2832 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_descriptor,
bool>
2845 template<
unsigned int N,
class T,
class Str
ide,
class U>
2856 template<
unsigned int N,
class T,
class Str
ide>
2869 template<
unsigned int N>
2872 typedef boost::readable_property_map_tag category;
2873 typedef typename graph_type::index_type value_type;
2874 typedef typename graph_type::vertex_descriptor key_type;
2875 typedef const value_type& reference;
2878 IDMapper(
const graph_type &graph)
2879 : map_helper(graph.get_vertex_iterator())
2882 typename graph_type::vertex_iterator map_helper;
2885 template<
unsigned int N>
2886 struct property_map<vigra::GridGraph<N>, boost::vertex_index_t>
2888 typedef IDMapper<N> type;
2889 typedef IDMapper<N> const_type;
2893 template<
unsigned int N>
2895 typename IDMapper<N>::value_type
2896 get(
const IDMapper<N> & mapper,
2897 const typename IDMapper<N>::key_type &k)
2899 return (mapper.map_helper + k).scanOrderIndex();
2903 template<
unsigned int N>
2904 typename boost::property_map<vigra::GridGraph<N>, boost::vertex_index_t>::type
2909 return IDMapper<N>(graph);
2913 template<
unsigned int N>
2915 get(boost::vertex_index_t,
2918 return (IDMapper<N>(graph).map_helper + v).scanOrderIndex();
2934 template <
typename GR>
2938 template<
unsigned int N,
class DirectedTag>
2939 class InDegMap<vigra::GridGraph<N, DirectedTag> >
2945 explicit InDegMap(
const Graph& graph)
2946 : Graph::InDegMap(graph)
2950 template <
typename GR>
2954 template<
unsigned int N,
class DirectedTag>
2955 class OutDegMap<vigra::GridGraph<N, DirectedTag> >
2961 explicit OutDegMap(
const Graph& graph)
2962 : Graph::OutDegMap(graph)
2970 namespace boost_graph {
2979 template<
unsigned int N,
class DirectedTag>
2983 out <<
"v" << arg.scanOrderIndex();
2987 template<
unsigned int N,
class DirectedTag>
2991 out <<
"nb" << arg.index();
void put(vigra::MultiArrayView< N, T, Stride > &pmap, typename vigra::MultiArrayView< N, T, Stride >::difference_type const &k, U const &val)
Put value val at key k in the property map pmap (API: boost).
Definition: multi_gridgraph.hxx:2847
index_type maxEdgeId() const
Get the maximum ID of any edge in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2056
NodeMap(GridGraph const &g, T const &t)
Construct property map for the given graph g (preallocates an entry with initial value t for each nod...
Definition: multi_gridgraph.hxx:1582
out_back_edge_iterator get_out_back_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of outgoing backward edges of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:2301
Node baseNode(IncBackEdgeIt const &e) const
Return the start node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2193
vertex_descriptor Node
The Node descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1494
EdgeMap(difference_type const &shape, T const &t)
Construct property map for the given shape (preallocates an entry with initial value t for each edge ...
Definition: multi_gridgraph.hxx:1686
ArcMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each arc of t...
const value_type & const_reference
Definition: multi_array.hxx:678
MultiArrayShape< N >::type shape_type
Shape type of the graph and a node property map.
Definition: multi_gridgraph.hxx:1378
Node target(Arc const &a) const
Get the end node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2249
Arc arcFromId(index_type i) const
Get an arc descriptor for the given arc ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2092
std::pair< typename vigra::GridGraph< N, DirectedTag >::in_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::in_edge_iterator > in_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the incoming edges of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2774
MultiArrayShape< N+1 >::type edge_propmap_shape_type
Shape type of an edge property map (must have one additional dimension).
Definition: multi_gridgraph.hxx:1382
Define a grid graph in arbitrary dimensions.
Definition: multi_gridgraph.hxx:1365
vigra::GridGraph< N, DirectedTag >::vertex_descriptor source(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the start vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2786
Value & operator[](Key const &key)
Read/write access to the value associated with edge descriptor key.
GridGraph Graph
The graph type of InDegMap (works for directed and undirected graphs)
Definition: multi_gridgraph.hxx:1802
adjacency_iterator neighbor_vertex_iterator
Same as adjacency_iterator (API: VIGRA).
Definition: multi_gridgraph.hxx:1415
out_edge_iterator get_out_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first outgoing edge of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2274
Value operator[](const Key &key) const
Get the out-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1853
std::pair< typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator, typename vigra::GridGraph< N, DirectedTag >::adjacency_iterator > adjacent_vertices(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the neighbor vertices of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2706
GridGraphOutEdgeIterator< N, true > IncBackEdgeIt
Iterator over only those incident edges of a node that end in a node with smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1532
MultiArrayShape< actual_dimension >::type difference_type
Definition: multi_array.hxx:690
Node runningNode(IncBackEdgeIt const &e) const
Return the end node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2221
Node baseNode(IncEdgeIt const &e) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2186
back_neighbor_vertex_iterator get_back_neighbor_vertex_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of backward neighbors of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:1996
R arg(const FFTWComplex< R > &a)
pahse
Definition: fftw3.hxx:1009
GridGraphOutArcIterator< N > out_edge_iterator
Iterator over the outgoing edges of a given vertex (API: boost::graph, use via boost::graph_traits<Gr...
Definition: multi_gridgraph.hxx:1430
in_edge_iterator get_in_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of incoming edges of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2319
degree_size_type back_degree(vertex_descriptor const &v) const
Get the number of outgoing backward edges of the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:2335
boost::no_property vertex_property_type
The graph does not define internal property maps (API: boost::graph, use via boost::graph_traits<Grap...
Definition: multi_gridgraph.hxx:1466
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:1406
GridGraphOutArcIterator< N > OutArcIt
Iterator over the outgoing edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1506
Node runningNode(IncEdgeIt const &e) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2214
Value & operator[](Key const &key)
Read/write access to the value associated with arc descriptor key.
vertex_iterator NodeIt
Iterator over all nodes of the graph (API: LEMON).
Definition: multi_gridgraph.hxx:1498
static const bool is_directed
'true' if the graph is directed (API: boost::graph)
Definition: multi_gridgraph.hxx:1371
GridGraphNeighborIterator< N, true > back_neighbor_vertex_iterator
Iterator over only those neighbor vertices of a given vertex that have smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1420
Node nodeFromId(index_type i) const
Get node descriptor for given node ID i (API: LEMON).
Definition: multi_gridgraph.hxx:1919
void set(Key const &k, Value const &v)
Set the property of edge desctiptor key to value v.
Definition: multi_gridgraph.hxx:1715
Node baseNode(OutArcIt const &a) const
Return the start node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2200
index_type maxNodeId() const
Get the maximum ID of any node in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:1928
IndexMap(const GridGraph &)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1784
GridGraphArcDescriptor< N > edge_descriptor
The edge descriptor (API: boost::graph, use via boost::graph_traits<Graph>::edge_descriptor).
Definition: multi_gridgraph.hxx:1450
vigra::GridGraph< N, DirectedTag >::edges_size_type num_edges(vigra::GridGraph< N, DirectedTag > const &g)
Return the number of edges in graph g (API: boost).
Definition: multi_gridgraph.hxx:2819
Edge findEdge(Node const &u, Node const &v, Edge const &=lemon::INVALID) const
Get a descriptor for the edge connecting vertices u and v, or lemon::INVALID if no such edge exists (...
Definition: multi_gridgraph.hxx:2441
index_type id(Arc const &a) const
Get the ID (i.e. scan-order index an an arc property map) for the given ar a (API: LEMON)...
Definition: multi_gridgraph.hxx:2070
Define several graph tags related to graph traversal (API: boost::graph, use via boost::graph_traits<...
Definition: multi_gridgraph.hxx:1473
neighbor_vertex_iterator get_neighbor_vertex_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first neighbor of the given vertex (convenience function, the boost::graph API provides the free function boost::adjacent_vertices(v, graph), LEMON uses Graph::ArcIt(g, v)).
Definition: multi_gridgraph.hxx:1969
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2357
boost::disallow_parallel_edge_tag edge_parallel_category
The graph does not allow multiple edges between the same vertices (API: boost::graph, use via boost::graph_traits<Graph>::edge_parallel_category).
Definition: multi_gridgraph.hxx:1461
Arc direct(Edge const &e, bool forward) const
Create an arc for the given edge e, oriented along the edge's natural (forward = true) or reversed (f...
Definition: multi_gridgraph.hxx:2123
Node runningNode(OutArcIt const &a) const
Return the end node of the edge the given iterator is referring to (API: LEMON).
Definition: multi_gridgraph.hxx:2228
Value operator[](const Key &key) const
Get the in-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1819
GridGraphInArcIterator< N > InArcIt
Iterator over the incoming arcs of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1519
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_descriptor, bool > edge(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &u, typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return the pair (edge_descriptor, true) when an edge between vertices u and v exists, or (lemon::INVALID, false) otherwise (API: boost).
Definition: multi_gridgraph.hxx:2833
vertices_size_type num_vertices() const
Get the number of vertices in this graph (convenience function, the boost::graph API provides the fre...
Definition: multi_gridgraph.hxx:2007
MultiArrayIndex vertices_size_type
Type to specify number of vertices (API: boost::graph, use via boost::graph_traits<Graph>::vertices_s...
Definition: multi_gridgraph.hxx:1391
Type of a property map that returns the coordinate of a given node (API: LEMON).
Definition: multi_gridgraph.hxx:1769
DirectedTag directed_category
Is the graph directed or undirected ? (API: boost::graph, use via boost::graph_traits<Graph>::directe...
Definition: multi_gridgraph.hxx:1455
void set(Key const &k, Value const &v)
Set the property of node desctiptor key to value v.
Definition: multi_gridgraph.hxx:1627
Type of an edge property map that maps edge descriptor objects onto property values of type T (API: L...
Definition: multi_gridgraph.hxx:1638
OutDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1847
std::ptrdiff_t MultiArrayIndex
Definition: multi_shape.hxx:55
std::pair< typename vigra::GridGraph< N, DirectedTag >::back_neighbor_vertex_iterator, typename vigra::GridGraph< N, DirectedTag >::back_neighbor_vertex_iterator > back_adjacent_vertices(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for only thise neighbor vertices of vertex v that have smaller ID th...
Definition: multi_gridgraph.hxx:2720
Value const & operator[](Key const &key) const
Get the grid coordinate of the node descriptor key.
Definition: multi_gridgraph.hxx:1789
index_type id(Edge const &e) const
Get the ID (i.e. scan-order index in an edge property map) for the given edges descriptor e (API: LEM...
Definition: multi_gridgraph.hxx:2025
Node v(Edge const &e) const
Get the end node of the given edge e (API: LEMON, the boost::graph API provides the free function bo...
Definition: multi_gridgraph.hxx:2265
edges_size_type arcNum() const
Get the number of arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2388
NodeMap(difference_type const &shape)
Construct property map for the given shape. (preallocates a zero-initialized entry for each node of a...
Definition: multi_gridgraph.hxx:1590
view_type::difference_type difference_type
Definition: multi_array.hxx:2405
degree_size_type degree(vertex_descriptor const &v) const
Get the total number of edges (incoming plus outgoing) of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2361
Value & operator[](Key const &key)
Read/write access to the value associated with node descriptor key.
MultiArrayIndex degree_size_type
Type to specify number of neighbors (API: boost::graph, use via boost::graph_traits<Graph>::degree_si...
Definition: multi_gridgraph.hxx:1401
NodeMap(difference_type const &shape, T const &t)
Construct property map for the given shape. (preallocates an entry with initial value t for each node...
Definition: multi_gridgraph.hxx:1598
MultiArray & operator=(const MultiArray &rhs)
Definition: multi_array.hxx:2546
edge_iterator get_edge_iterator() const
Get edge iterator pointing to the first edge of the graph (convenience function, the boost::graph AP...
Definition: multi_gridgraph.hxx:2399
Arc direct(Edge const &e, Node const &n) const
Create an arc for the given edge e oriented so that node n is the starting node of the arc (API: LEMO...
Definition: multi_gridgraph.hxx:2135
vigra::GridGraph< N, DirectedTag >::vertices_size_type num_vertices(vigra::GridGraph< N, DirectedTag > const &g)
Return the number of vertices in graph g (API: boost).
Definition: multi_gridgraph.hxx:2694
out_back_edge_iterator get_out_back_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first outgoing backward edge of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:2292
view_type::reference reference
Definition: multi_array.hxx:2393
Node baseNode(OutBackArcIt const &a) const
Return the start node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2207
GridGraphArcIterator< N, false > ArcIt
Iterator over the acrs (directed edges) of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1515
back_neighbor_vertex_iterator get_back_neighbor_vertex_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first backward neighbor of the given vertex (API: VIGRA...
Definition: multi_gridgraph.hxx:1987
Arc oppositeArc(Arc const &a) const
Create an arc referring to the same edge as the given arc a, but with reversed direction (API: LEMON)...
Definition: multi_gridgraph.hxx:2161
NumericTraits< V >::Promote prod(TinyVectorBase< V, SIZE, D1, D2 > const &l)
product of the vector's elements
Definition: tinyvector.hxx:1895
index_type maxArcId() const
Get the maximal ID af any arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2101
edges_size_type num_edges() const
Get the number of edges in this graph (convenience function, boost::graph API provides the free funct...
Definition: multi_gridgraph.hxx:2374
vertices_size_type nodeNum() const
Get the number of nodes in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2014
degree_size_type out_degree(vertex_descriptor const &v) const
Get the number of outgoing edges of the given vertex (convenience function, the boost::graph API pro...
Definition: multi_gridgraph.hxx:2328
vigra::MultiArrayView< N, T, Stride >::const_reference get(vigra::MultiArrayView< N, T, Stride > const &pmap, typename vigra::MultiArrayView< N, T, Stride >::difference_type const &k)
Read the value at key k in property map pmap (API: boost).
Definition: multi_gridgraph.hxx:2859
Type of a property map that returns the number of incoming edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1797
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition: fftw3.hxx:841
EdgeMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each edge of ...
Definition: multi_gridgraph.hxx:1663
NodeMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each node of ...
Definition: multi_gridgraph.hxx:1575
MultiArrayIndex edges_size_type
Type to specify number of edges (API: boost::graph, use via boost::graph_traits<Graph>::edges_size_ty...
Definition: multi_gridgraph.hxx:1396
GridGraph(shape_type const &shape, NeighborhoodType ntype=DirectNeighborhood)
Construct a grid graph with given shape and neighborhood type ntype.
Definition: multi_gridgraph.hxx:1877
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition: fftw3.hxx:825
neighbor_vertex_iterator get_neighbor_vertex_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of neighbors of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:1978
GridGraphInArcIterator< N > in_edge_iterator
Iterator over the incoming edges of a given vertex (API: boost::graph, use via boost::graph_traits<Gr...
Definition: multi_gridgraph.hxx:1425
GridGraphOutArcIterator< N, true > out_back_edge_iterator
Iterator over only those outgoing edges of a given vertex that go to vertices with smaller IDs (API: ...
Definition: multi_gridgraph.hxx:1435
vigra::GridGraph< N, DirectedTag >::degree_size_type degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return total number of edges (incoming and outgoing) of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2671
vigra::GridGraph< N, DirectedTag >::degree_size_type in_degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return number of incoming edges of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2660
Node u(Edge const &e) const
Get the start node of the given edge e (API: LEMON, the boost::graph API provides the free function ...
Definition: multi_gridgraph.hxx:2257
Arc findArc(Node const &u, Node const &v, Arc const &=lemon::INVALID) const
Get a descriptor for the arc connecting vertices u and v, or lemon::INVALID if no such edge exists (A...
Definition: multi_gridgraph.hxx:2448
view_type::value_type value_type
Definition: multi_array.hxx:2381
shape_type vertex_descriptor
The vertex descriptor (API: boost::graph, use via boost::graph_traits<Graph>::vertex_descriptor).
Definition: multi_gridgraph.hxx:1445
vigra::GridGraph< N, DirectedTag >::vertex_descriptor target(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the end vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2797
Class for fixed size vectors.This class contains an array of size SIZE of the specified VALUETYPE...
Definition: accessor.hxx:940
InDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1813
vigra::GridGraph< N, DirectedTag >::degree_size_type out_degree(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return number of outgoing edges of vertex v (API: boost).
Definition: multi_gridgraph.hxx:2649
degree_size_type in_degree(vertex_descriptor const &v) const
Get the number of incoming edges of the given vertex (convenience function, the boost::graph API pro...
Definition: multi_gridgraph.hxx:2352
index_type id(Node const &v) const
Get the ID (i.e. scan-order index) for node desciptor v (API: LEMON).
Definition: multi_gridgraph.hxx:1897
vertex_iterator get_vertex_end_iterator() const
Get vertex iterator pointing beyond the valid range of vertices of this graph (convenience function...
Definition: multi_gridgraph.hxx:1960
GridGraphOutArcIterator< N, true > OutBackArcIt
Iterator over only those outgoing edges of a node that end in a node with smaller ID (API: VIGRA)...
Definition: multi_gridgraph.hxx:1511
MultiArrayIndex index_type
Type of node and edge IDs.
Definition: multi_gridgraph.hxx:1386
vertex_iterator get_vertex_iterator() const
Get vertex iterator pointing to the first vertex of this graph (convenience function, the boost::graph API provides the free function boost::vertices(graph), LEMON uses Graph::NodeIt(graph)).
Definition: multi_gridgraph.hxx:1944
Edge edgeFromId(index_type i) const
Get the edge descriptor for the given edge ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2047
GridGraphArcDescriptor< N > Arc
The arc (directed edge) descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1502
bool direction(Arc const &a) const
Return true when the arc is looking on the underlying edge in its natural (i.e. forward) direction...
Definition: multi_gridgraph.hxx:2114
std::pair< typename vigra::GridGraph< N, DirectedTag >::vertex_iterator, typename vigra::GridGraph< N, DirectedTag >::vertex_iterator > vertices(vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the vertices of graph g (API: boost).
Definition: multi_gridgraph.hxx:2683
edge_iterator get_edge_end_iterator() const
Get edge iterator pointing beyond the valid range of edges of this graph (convenience function...
Definition: multi_gridgraph.hxx:2408
MultiArrayShape< N+1 >::type Edge
The edge descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1523
degree_size_type forward_degree(vertex_descriptor const &v) const
Get the number of outgoing forward edges of the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:2342
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:655
std::pair< typename vigra::GridGraph< N, DirectedTag >::out_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::out_edge_iterator > out_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the outgoing edges of vertex v in graph g (API: boost)...
Definition: multi_gridgraph.hxx:2746
in_edge_iterator get_in_edge_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first incoming edge of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2310
vertex_iterator get_vertex_iterator(vertex_descriptor const &v) const
Get vertex iterator pointing to the given vertex (API: VIGRA).
Definition: multi_gridgraph.hxx:1951
IndexMap indexMap() const
Create a property map that returns the coordinate of each node (API: LEMON GridGraph).
Definition: multi_gridgraph.hxx:2459
GridGraph Graph
The graph type of OutDegMap (works for directed and undirected graphs)
Definition: multi_gridgraph.hxx:1836
ostream & operator<<(ostream &s, const vigra::MultiArrayView< 2, T, C > &m)
Definition: matrix.hxx:2322
void set(Key const &k, Value const &v)
Set the property of arc desctiptor key to value v.
size_type size() const
Definition: array_vector.hxx:330
out_edge_iterator get_out_edge_end_iterator(vertex_descriptor const &v) const
Get an iterator pointing beyond the range of outgoing edges of the given vertex (convenience function...
Definition: multi_gridgraph.hxx:2283
Node oppositeNode(Node const &n, Edge const &e) const
Return the opposite node of the given node n along edge e (API: LEMON), or return lemon::INVALID if t...
Definition: multi_gridgraph.hxx:2148
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_iterator, typename vigra::GridGraph< N, DirectedTag >::edge_iterator > edges(vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for the edges of graph g (API: boost).
Definition: multi_gridgraph.hxx:2809
std::pair< typename vigra::GridGraph< N, DirectedTag >::out_back_edge_iterator, typename vigra::GridGraph< N, DirectedTag >::out_back_edge_iterator > out_back_edges(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Get a (begin, end) iterator pair for only those outgoing edges of vertex v whose ID is smaller than t...
Definition: multi_gridgraph.hxx:2760
Type of a property map that returns the number of outgoing edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1831
use only direct neighbors
Definition: multi_shape.hxx:253
EdgeMap(difference_type const &shape)
Construct property map for the given shape (preallocates a zero-initialized entry for each edge of a ...
Definition: multi_gridgraph.hxx:1678
GridGraphArcIterator< N,!is_directed > edge_iterator
Iterator over the edges of a graph (API: boost::graph, use via boost::graph_traits<Graph>::edge_itera...
Definition: multi_gridgraph.hxx:1440
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_shape.hxx:252
EdgeMap(GridGraph const &g, T const &t)
Construct property map for the given graph g (preallocates an entry with initial value t for each edg...
Definition: multi_gridgraph.hxx:1670
edges_size_type edgeNum() const
Get the number of edges in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2381
Type of a node property map that maps node descriptor objects onto property values of type T (API: LE...
Definition: multi_gridgraph.hxx:1550
Node source(Arc const &a) const
Get the start node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2242
GridGraphEdgeIterator< N,!is_directed > EdgeIt
Iterator over the edges of the graph (API: LEMON).
Definition: multi_gridgraph.hxx:1536
Iterate over a virtual array where each element contains its coordinate.
Definition: multi_iterator.hxx:89
GridGraphOutEdgeIterator< N > IncEdgeIt
Iterator over the incident edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1527
std::pair< edge_descriptor, bool > edge(vertex_descriptor const &u, vertex_descriptor const &v) const
Get a descriptor for the edge connecting vertices u and v, or (lemon::INVALID, false) if no such edg...
Definition: multi_gridgraph.hxx:2421
difference_type key_type
Definition: multi_array.hxx:694
view_type::const_reference const_reference
Definition: multi_array.hxx:2397
GridGraphNeighborIterator< N > adjacency_iterator
Iterator over the neighbor vertices of a given vertex (API: boost::graph, use via boost::graph_traits...
Definition: multi_gridgraph.hxx:1411
Node const & pos(Node const &v) const
Get the grid cordinate of the given node v (convenience function).
Definition: multi_gridgraph.hxx:1935
Type of an arc property map that maps arc descriptor objects onto property values of type T (API: LEM...
Definition: multi_gridgraph.hxx:1726
Node runningNode(OutBackArcIt const &a) const
Return the end node of the edge the given iterator is referring to (API: VIGRA).
Definition: multi_gridgraph.hxx:2235