36 #ifndef VIGRA_MULTI_GRIDGRAPH_HXX
37 #define VIGRA_MULTI_GRIDGRAPH_HXX
39 #include "multi_fwd.hxx"
40 #include "multi_iterator.hxx"
41 #include "multi_array.hxx"
44 template <
unsigned int N>
45 struct NeighborhoodTests;
49 template<
unsigned int N,
class T,
class Str
ide>
83 template<
unsigned int N>
84 class GridGraphArcDescriptor
85 :
public MultiArrayShape<N+1>::type
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;
95 GridGraphArcDescriptor()
99 GridGraphArcDescriptor(lemon::Invalid)
104 GridGraphArcDescriptor(base_type
const & b,
bool reversed)
106 is_reversed_(reversed)
109 GridGraphArcDescriptor(shape_type
const &vertex,
110 index_type edge_index,
112 : base_type(detail::DontInit())
114 set(vertex, edge_index, reversed);
117 void set(shape_type
const &vertex, index_type edge_index,
bool reversed)
119 this->
template subarray<0,N>() = vertex;
120 (*this)[N] = edge_index;
121 is_reversed_ = reversed;
124 void increment(GridGraphArcDescriptor
const & diff,
bool opposite=
false)
126 if(diff.is_reversed_)
128 is_reversed_ = !opposite;
129 this->
template subarray<0,N>() += diff.template subarray<0,N>();
133 is_reversed_ = opposite;
135 (*this)[N] = diff[N];
138 bool isReversed()
const
143 vertex_descriptor_view vertexDescriptor()
const
145 return this->
template subarray<0,N>();
148 value_type edgeIndex()
const
162 : pow(3.0, (
int)N) - 1;
165 template <
unsigned int N, NeighborhoodType>
166 struct GridGraphMaxDegree;
168 template <
unsigned int N>
169 struct GridGraphMaxDegree<N, DirectNeighborhood>
174 template <
unsigned int N>
175 struct GridGraphMaxDegree<N, IndirectNeighborhood>
180 template <
class Shape>
187 for(
unsigned int k=0; k<shape.size(); ++k)
188 res += 2*
prod(shape - Shape::unitVector(k));
192 res =
prod(3*shape - Shape(2)) -
prod(shape);
201 template <
class Shape>
203 computeNeighborOffsets(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,
211 typedef GridGraphArcDescriptor<Shape::static_size> EdgeDescriptor;
213 unsigned int borderTypeCount = neighborExists.size();
214 incrementOffsets.resize(borderTypeCount);
215 edgeDescriptorOffsets.resize(borderTypeCount);
216 indices.resize(borderTypeCount);
217 backIndices.resize(borderTypeCount);
219 for(
unsigned int k=0; k<borderTypeCount; ++k)
221 incrementOffsets[k].clear();
222 edgeDescriptorOffsets[k].clear();
224 backIndices[k].clear();
226 for(
unsigned int j=0; j < neighborOffsets.size(); ++j)
228 if(neighborExists[k][j])
230 if(incrementOffsets[k].size() == 0)
232 incrementOffsets[k].push_back(neighborOffsets[j]);
236 incrementOffsets[k].push_back(neighborOffsets[j] - neighborOffsets[indices[k].back()]);
239 if(directed || j < neighborOffsets.size() / 2)
241 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(Shape(), j));
243 else if(edgeDescriptorOffsets[k].size() == 0 || !edgeDescriptorOffsets[k].back().isReversed())
245 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j], neighborOffsets.size()-j-1,
true));
249 edgeDescriptorOffsets[k].push_back(EdgeDescriptor(neighborOffsets[j] - neighborOffsets[indices[k].back()],
250 neighborOffsets.size()-j-1,
true));
253 indices[k].push_back(j);
254 if(j < neighborOffsets.size() / 2)
255 backIndices[k].push_back(j);
263 template<
unsigned int N,
bool BackEdgesOnly>
264 class GridGraphNeighborIterator
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;
277 typedef std::forward_iterator_tag iterator_category;
279 friend struct NeighborhoodTests<N>;
281 GridGraphNeighborIterator()
282 : neighborOffsets_(0),
287 template <
class DirectedTag>
288 GridGraphNeighborIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
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];
300 template <
class DirectedTag>
301 GridGraphNeighborIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
302 : neighborOffsets_(0),
307 unsigned int nbtype = g.get_border_type(v);
308 neighborOffsets_ = &(*g.neighborIncrementArray())[nbtype];
309 neighborIndices_ = &(*g.neighborIndexArray(BackEdgesOnly))[nbtype];
317 GridGraphNeighborIterator & operator++()
324 GridGraphNeighborIterator operator++(
int)
326 GridGraphNeighborIterator ret(*
this);
331 const_reference operator*()
const
336 const_pointer operator->()
const
341 operator const_reference()
const
346 const_reference
target()
const
358 return (*neighborIndices_)[index_];
361 bool operator==(GridGraphNeighborIterator
const & other)
const
363 return index_ == other.index_;
366 bool operator!=(GridGraphNeighborIterator
const & other)
const
368 return index_ != other.index_;
381 GridGraphNeighborIterator getEndIterator()
const
383 GridGraphNeighborIterator res(*
this);
391 GridGraphNeighborIterator(ArrayVector<shape_type>
const & neighborOffsets,
392 ArrayVector<index_type>
const & neighborIndices,
393 ArrayVector<index_type>
const & backIndices,
395 : neighborOffsets_(&neighborOffsets),
396 neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
406 target_ += (*neighborOffsets_)[index_];
409 ArrayVector<shape_type>
const * neighborOffsets_;
410 ArrayVector<index_type>
const * neighborIndices_;
411 vertex_descriptor target_;
415 template<
unsigned int N,
bool BackEdgesOnly>
416 class GridGraphOutEdgeIterator
419 typedef typename MultiArrayShape<N>::type shape_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;
428 typedef std::forward_iterator_tag iterator_category;
430 friend struct NeighborhoodTests<N>;
431 friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
433 GridGraphOutEdgeIterator()
434 : neighborOffsets_(0),
439 template <
class DirectedTag>
440 GridGraphOutEdgeIterator(GridGraph<N, DirectedTag>
const & g,
441 typename GridGraph<N, DirectedTag>::NodeIt
const & v,
443 : neighborOffsets_(0),
449 unsigned int nbtype = g.get_border_type(v);
450 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], *v, opposite);
453 index_ = (index_type)neighborIndices_->size();
457 template <
class DirectedTag>
458 GridGraphOutEdgeIterator(GridGraph<N, DirectedTag>
const & g,
459 typename GridGraph<N, DirectedTag>::Node
const & v,
461 : neighborOffsets_(0),
467 unsigned int nbtype = g.get_border_type(v);
468 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], v, opposite);
471 index_ = (index_type)neighborIndices_->size();
475 GridGraphOutEdgeIterator & operator++()
481 GridGraphOutEdgeIterator operator++(
int)
483 GridGraphOutEdgeIterator ret(*
this);
488 const_reference operator*()
const
490 return edge_descriptor_;
493 operator const_reference()
const
495 return edge_descriptor_;
498 const_pointer operator->()
const
500 return &edge_descriptor_;
503 index_type index()
const
508 index_type neighborIndex()
const
510 return (*neighborIndices_)[index_];
513 arc_descriptor
const & arcDescriptor()
const
515 return edge_descriptor_;
518 bool operator==(GridGraphOutEdgeIterator
const & other)
const
520 return index_ == other.index();
523 bool operator!=(GridGraphOutEdgeIterator
const & other)
const
525 return index_ != other.index();
530 return index_ < (index_type)neighborIndices_->size();
535 return index_ >= (index_type)neighborIndices_->size();
538 GridGraphOutEdgeIterator getEndIterator()
const
540 GridGraphOutEdgeIterator res(*
this);
541 res.index_ = (index_type)neighborIndices_->size();
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),
557 init(&neighborOffsets, BackEdgesOnly ? &backIndices : &neighborIndices, source);
560 void init(ArrayVector<arc_descriptor>
const * neighborOffsets,
561 ArrayVector<index_type>
const * neighborIndices,
562 shape_type
const &
source,
565 neighborOffsets_ = neighborOffsets;
566 neighborIndices_ = neighborIndices;
567 edge_descriptor_ = arc_descriptor(source, 0);
569 updateEdgeDescriptor(opposite);
572 void increment(
bool opposite)
575 updateEdgeDescriptor(opposite);
578 void updateEdgeDescriptor(
bool opposite)
581 edge_descriptor_.increment((*neighborOffsets_)[index_], opposite);
584 ArrayVector<arc_descriptor>
const * neighborOffsets_;
585 ArrayVector<index_type>
const * neighborIndices_;
586 arc_descriptor edge_descriptor_;
590 template<
unsigned int N,
bool BackEdgesOnly>
591 class GridGraphOutArcIterator
592 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
595 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
596 typedef typename MultiArrayShape<N>::type shape_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;
604 typedef std::forward_iterator_tag iterator_category;
606 friend struct NeighborhoodTests<N>;
607 friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
609 GridGraphOutArcIterator()
613 explicit GridGraphOutArcIterator(base_type
const & b)
617 template <
class DirectedTag>
618 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
622 template <
class DirectedTag>
623 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
627 GridGraphOutArcIterator & operator++()
629 base_type::operator++();
633 GridGraphOutArcIterator operator++(
int)
635 GridGraphOutArcIterator ret(*
this);
640 const_reference operator*()
const
642 return this->edge_descriptor_;
645 operator const_reference()
const
647 return this->edge_descriptor_;
650 const_pointer operator->()
const
652 return &this->edge_descriptor_;
655 GridGraphOutArcIterator getEndIterator()
const
657 return GridGraphOutArcIterator(base_type::getEndIterator());
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)
671 template<
unsigned int N,
bool BackEdgesOnly>
672 class GridGraphInArcIterator
673 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
676 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
677 typedef typename MultiArrayShape<N>::type shape_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;
685 typedef std::forward_iterator_tag iterator_category;
687 friend struct NeighborhoodTests<N>;
689 GridGraphInArcIterator()
693 explicit GridGraphInArcIterator(base_type
const & b)
697 template <
class DirectedTag>
698 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
699 : base_type(g, v, true)
702 template <
class DirectedTag>
703 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
704 : base_type(g, v, true)
707 GridGraphInArcIterator & operator++()
709 base_type::increment(
true);
713 GridGraphInArcIterator operator++(
int)
715 GridGraphInArcIterator ret(*
this);
720 const_reference operator*()
const
722 return this->edge_descriptor_;
725 operator const_reference()
const
727 return this->edge_descriptor_;
730 const_pointer operator->()
const
732 return &this->edge_descriptor_;
735 GridGraphInArcIterator getEndIterator()
const
737 return GridGraphInArcIterator(base_type::getEndIterator());
743 template<
unsigned int N,
bool BackEdgesOnly>
744 class GridGraphEdgeIterator
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;
760 typedef std::forward_iterator_tag iterator_category;
762 friend struct NeighborhoodTests<N>;
764 GridGraphEdgeIterator()
765 : neighborOffsets_(0),
769 template <
class DirectedTag>
770 GridGraphEdgeIterator(GridGraph<N, DirectedTag>
const & g)
771 : neighborOffsets_(g.edgeIncrementArray()),
772 neighborIndices_(g.neighborIndexArray(BackEdgesOnly)),
774 outEdgeIterator_(g, vertexIterator_)
776 if(outEdgeIterator_.atEnd())
779 if(vertexIterator_.isValid())
780 outEdgeIterator_ = out_edge_iterator(g, vertexIterator_);
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_)
793 if(vertexIterator_.isValid()){
799 if(edge[N] >= 0 && edge[N] < g.maxUniqueDegree( ) &&
800 (*( g.neighborExistsArray()))[vertexIterator_.borderType()][edge[N]] ){
801 while(*outEdgeIterator_!=edge){
806 vertexIterator_ = vertexIterator_.getEndIterator();
820 GridGraphEdgeIterator & operator++()
823 if(outEdgeIterator_.atEnd())
826 if(vertexIterator_.isValid())
828 unsigned int borderType = vertexIterator_.borderType();
829 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
835 GridGraphEdgeIterator operator++(
int)
837 GridGraphEdgeIterator ret(*
this);
842 const_reference operator*()
const
844 return *outEdgeIterator_;
847 operator const_reference()
const
849 return *outEdgeIterator_;
852 const_pointer operator->()
const
854 return outEdgeIterator_.operator->();
859 return outEdgeIterator_.neighborIndex();
863 bool operator==(GridGraphEdgeIterator
const & other)
const
865 return (vertexIterator_ == other.vertexIterator_ && outEdgeIterator_ == other.outEdgeIterator_);
868 bool operator!=(GridGraphEdgeIterator
const & other)
const
875 return vertexIterator_.isValid();
883 GridGraphEdgeIterator getEndIterator()
const
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();
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())
908 if(outEdgeIterator_.atEnd())
911 if(vertexIterator_.isValid())
913 unsigned int borderType = vertexIterator_.borderType();
914 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
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_;
925 template<
unsigned int N,
bool BackEdgesOnly>
926 class GridGraphArcIterator
927 :
public GridGraphEdgeIterator<N, BackEdgesOnly>
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;
944 typedef std::forward_iterator_tag iterator_category;
946 friend struct NeighborhoodTests<N>;
948 GridGraphArcIterator()
952 explicit GridGraphArcIterator(base_type
const & b)
956 template <
class DirectedTag>
957 GridGraphArcIterator(GridGraph<N, DirectedTag>
const & g)
961 GridGraphArcIterator & operator++()
963 base_type::operator++();
967 GridGraphArcIterator operator++(
int)
969 GridGraphArcIterator ret(*
this);
974 const_reference operator*()
const
976 return *(this->outEdgeIterator_);
979 operator const_reference()
const
981 return *(this->outEdgeIterator_);
984 const_pointer operator->()
const
986 return this->outEdgeIterator_.operator->();
989 GridGraphArcIterator getEndIterator()
const
991 return GridGraphArcIterator(base_type::getEndIterator());
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)
1005 template<
unsigned int N>
1006 inline bool operator==(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
1011 template<
unsigned int N>
1012 inline bool operator!=(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
1017 template<
unsigned int N>
1018 inline bool operator==(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
1023 template<
unsigned int N>
1024 inline bool operator!=(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
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) \
1035 template<unsigned int N, bool BackEdgesOnly> \
1036 inline bool operator!=(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
1038 return i.isValid(); \
1040 template<unsigned int N, bool BackEdgesOnly> \
1041 inline bool operator==(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
1045 template<unsigned int N, bool BackEdgesOnly> \
1046 inline bool operator!=(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
1048 return i.isValid(); \
1051 VIGRA_LEMON_INVALID_COMPARISON(GridGraphNeighborIterator)
1052 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutEdgeIterator)
1053 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutArcIterator)
1054 VIGRA_LEMON_INVALID_COMPARISON(GridGraphInArcIterator)
1055 VIGRA_LEMON_INVALID_COMPARISON(GridGraphEdgeIterator)
1056 VIGRA_LEMON_INVALID_COMPARISON(GridGraphArcIterator)
1058 #undef VIGRA_LEMON_INVALID_COMPARISON
1060 using boost_graph::directed_tag;
1061 using boost_graph::undirected_tag;
1065 template <
unsigned int N,
class DirectedTag>
1066 struct GridGraphBase;
1068 template <
unsigned int N>
1069 struct GridGraphBase<N, directed_tag>
1073 :
public MultiArray<N+1, Multiband<T> >
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;
1084 typedef lemon::True ReferenceMapTag;
1085 typedef key_type Key;
1086 typedef value_type Value;
1087 typedef reference Reference;
1088 typedef const_reference ConstReference;
1094 explicit ArcMap(GridGraph<N, directed_tag>
const & g)
1095 : base_type(g.arc_propmap_shape())
1098 ArcMap(GridGraph<N, directed_tag>
const & g, T
const & t)
1099 : base_type(g.arc_propmap_shape(), t)
1102 explicit ArcMap(difference_type
const & shape)
1106 ArcMap(difference_type
const & shape, T
const & t)
1107 : base_type(shape, t)
1110 ArcMap & operator=(ArcMap
const & m)
1112 base_type::operator=(m);
1116 ArcMap & operator=(base_type
const & m)
1118 base_type::operator=(m);
1124 void set(Key
const & k, Value
const & v)
1131 template <
unsigned int N>
1132 struct GridGraphBase<N, undirected_tag>
1134 typedef lemon::True UndirectedTag;
1138 :
public MultiArray<N+1, Multiband<T> >
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;
1149 typedef lemon::True ReferenceMapTag;
1150 typedef key_type Key;
1151 typedef value_type Value;
1152 typedef reference Reference;
1153 typedef const_reference ConstReference;
1159 explicit ArcMap(GridGraph<N, undirected_tag>
const & g)
1160 : base_type(g.arc_propmap_shape()),
1164 ArcMap(GridGraph<N, undirected_tag>
const & g, T
const & t)
1165 : base_type(g.arc_propmap_shape(), t),
1169 ArcMap & operator=(ArcMap
const & m)
1171 base_type::operator=(m);
1175 ArcMap & operator=(base_type
const & m)
1177 base_type::operator=(m);
1181 reference operator[](difference_type
const & s)
1185 return base_type::operator[](graph_->directedArc(s));
1189 return base_type::operator[](s);
1193 const_reference operator[](difference_type
const & s)
const
1197 return base_type::operator[](graph_->directedArc(s));
1201 return base_type::operator[](s);
1205 void set(Key
const & k, Value
const & v)
1210 GridGraph<N, undirected_tag>
const * graph_;
1426 template<
unsigned int N,
class DirectedTag=undirected_tag>
1428 :
public detail::GridGraphBase<N, DirectedTag>
1433 static const bool is_directed = IsSameType<DirectedTag, directed_tag>::value;
1435 typedef detail::GridGraphBase<N, DirectedTag> base_type;
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
1571 typedef GridGraphArcDescriptor<N>
Arc;
1584 typedef GridGraphArcIterator<N, false>
ArcIt;
1605 typedef GridGraphEdgeIterator<N, !is_directed>
EdgeIt;
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;
1629 typedef boost_graph::read_write_property_map_tag category;
1631 typedef lemon::True ReferenceMapTag;
1632 typedef key_type Key;
1633 typedef value_type Value;
1634 typedef reference Reference;
1635 typedef const_reference ConstReference;
1667 NodeMap(difference_type
const & shape, T
const & t)
1677 NodeMap & operator=(base_type
const & m)
1691 Value
const &
operator[](Key
const & key)
const;
1696 void set(Key
const & k, Value
const & v)
1717 typedef boost_graph::read_write_property_map_tag category;
1719 typedef lemon::True ReferenceMapTag;
1721 typedef value_type Value;
1722 typedef reference Reference;
1723 typedef const_reference ConstReference;
1755 EdgeMap(difference_type
const & shape, T
const & t)
1765 EdgeMap & operator=(base_type
const & m)
1779 Value
const &
operator[](Key
const & key)
const;
1784 void set(Key
const & k, Value
const & v)
1814 explicit ArcMap(difference_type
const & shape);
1820 ArcMap(difference_type
const & shape, T
const & t);
1828 Value
const &
operator[](Key
const & key)
const;
1832 void set(Key
const & k, Value
const & v);
1844 typedef Value value_type;
1845 typedef Value const & reference;
1846 typedef boost_graph::readable_property_map_tag category;
1876 typedef Value value_type;
1877 typedef Value
const & reference;
1878 typedef boost_graph::readable_property_map_tag category;
1910 typedef Value value_type;
1911 typedef Value
const & reference;
1912 typedef boost_graph::readable_property_map_tag category;
1950 num_vertices_(
prod(shape)),
1951 num_edges_(gridGraphEdgeCount(shape, ntype,
is_directed)),
1952 max_node_id_(num_vertices_ - 1),
1955 neighborhoodType_(ntype)
1959 detail::makeArrayNeighborhood(neighborOffsets_, neighborExists_, neighborhoodType_);
1960 detail::computeNeighborOffsets(neighborOffsets_, neighborExists_, incrementalOffsets_,
1961 edgeDescriptorOffsets_, neighborIndices_, backIndices_,
is_directed);
1971 return detail::CoordinateToScanOrder<N>::exec(shape(), v);
1974 index_type
id(
NodeIt const & v)
const
1976 return v.scanOrderIndex();
1996 return Node(lemon::INVALID);
1998 Node res(SkipInitialization);
1999 detail::ScanOrderToCoordinate<N>::exec(i, shape(), res);
2007 return prod(shape()) - 1;
2086 return num_vertices_;
2104 return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), e);
2107 index_type
id(
EdgeIt const & e)
const
2130 return Edge(lemon::INVALID);
2132 Edge res(SkipInitialization);
2133 detail::ScanOrderToCoordinate<N+1>::exec(i, edge_propmap_shape(), res);
2135 unsigned int b = detail::BorderTypeImpl<N>::exec(res.template subarray<0, N>(), shape());
2136 if(neighborExists_[b][res[N]])
2139 return Edge(lemon::INVALID);
2146 if(max_edge_id_ == -2)
2147 const_cast<GridGraph *
>(
this)->computeMaxEdgeAndArcId();
2148 return max_edge_id_;
2154 void computeMaxEdgeAndArcId()
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);
2170 max_edge_id_ = max_arc_id_;
2174 Arc a(lastNode, backIndices_[get_border_type(lastNode)].back(),
false);
2175 max_edge_id_ = detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), a);
2185 return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), directedArc(a));
2188 index_type
id(
ArcIt const & a)
const
2211 return Arc(lemon::INVALID);
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);
2219 return Arc(lemon::INVALID);
2226 if(max_arc_id_ == -2)
2227 const_cast<GridGraph *
>(
this)->computeMaxEdgeAndArcId();
2236 return !a.isReversed();
2246 return Arc(e, !forward);
2248 return Arc(
v(e), oppositeIndex(e[N]),
true);
2261 return Arc(lemon::INVALID);
2270 Node start(
u(e)), end(
v(e));
2275 return Node(lemon::INVALID);
2284 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2285 :
Arc(a, !a.isReversed());
2291 Arc directedArc(
Arc const & a)
const
2293 return a.isReversed()
2294 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2302 Arc undirectedArc(
Arc const & a)
const
2304 return a.edgeIndex() < maxUniqueDegree()
2306 :
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
true);
2313 return source(e.arcDescriptor());
2320 return source(e.arcDescriptor());
2341 return target(e.arcDescriptor());
2348 return target(e.arcDescriptor());
2369 return source_or_target(a,
true);
2376 return source_or_target(a,
false);
2384 return Node(e.template subarray<0,N>());
2392 return Node(e.template subarray<0,N>()) + neighborOffsets_[e[N]];
2469 unsigned int bt = get_border_type(v);
2545 std::pair<edge_descriptor, bool>
2546 edge(vertex_descriptor
const &
u, vertex_descriptor
const & v)
const
2548 std::pair<edge_descriptor, bool> res(lemon::INVALID,
false);
2551 end = i.getEndIterator();
2552 for (; i != end; ++i)
2556 res.first = make_edge_descriptor(u, i.neighborIndex());
2568 return this->
edge(u, v).first;
2575 return this->
edge(u, v).first;
2592 bool isDirected()
const
2609 shape_type
const & shape()
const
2617 res.template subarray<0, N>() = shape_;
2618 res[N] = maxUniqueDegree();
2625 res.template subarray<0, N>() = shape_;
2626 res[N] = maxDegree();
2630 unsigned int get_border_type(vertex_descriptor
const & v)
const
2632 return detail::BorderTypeImpl<N>::exec(v, shape_);
2635 unsigned int get_border_type(vertex_iterator
const & v)
const
2637 return v.borderType();
2640 index_type oppositeIndex(index_type neighborIndex)
const
2642 return maxDegree() - neighborIndex - 1;
2649 index_type neighborIndex)
const
2651 if(neighborIndex < maxUniqueDegree())
2654 return edge_descriptor(neighbor(v, neighborIndex), oppositeIndex(neighborIndex),
true);
2657 shape_type
const & neighborOffset(index_type neighborIndex)
const
2659 return neighborOffsets_[neighborIndex];
2662 vertex_descriptor neighbor(vertex_descriptor
const & v, index_type neighborIndex)
const
2664 return v + neighborOffsets_[neighborIndex];
2672 if ((return_source && e.isReversed()) ||
2673 (!return_source && !e.isReversed()))
2675 return neighbor(e.vertexDescriptor(), e.edgeIndex());
2679 return e.vertexDescriptor();
2683 NeighborOffsetArray
const * neighborOffsetArray()
const
2685 return &neighborOffsets_;
2688 RelativeNeighborOffsetsArray
const * neighborIncrementArray()
const
2690 return &incrementalOffsets_;
2693 RelativeEdgeOffsetsArray
const * edgeIncrementArray()
const
2695 return &edgeDescriptorOffsets_;
2698 IndexArray
const * neighborIndexArray(
bool backEdgesOnly)
const
2700 return backEdgesOnly
2702 : &neighborIndices_;
2705 NeighborExistsArray
const * neighborExistsArray()
const
2707 return &neighborExists_;
2711 NeighborOffsetArray neighborOffsets_;
2712 NeighborExistsArray neighborExists_;
2713 IndexArray neighborIndices_, backIndices_;
2714 RelativeNeighborOffsetsArray incrementalOffsets_;
2715 RelativeEdgeOffsetsArray edgeDescriptorOffsets_;
2717 MultiArrayIndex num_vertices_, num_edges_, max_node_id_, max_arc_id_, max_edge_id_;
2721 template<
unsigned int N,
class DirectedTag>
2724 isInside(GridGraph<N, DirectedTag>
const & g,
2725 typename GridGraph<N, DirectedTag>::vertex_descriptor
const & v)
2732 #ifdef WITH_BOOST_GRAPH
2740 namespace boost_graph {
2746 template <
unsigned int N,
class T,
class Acc>
2747 struct property_traits<vigra::MultiArray<N, T, Acc> >
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;
2756 template <
unsigned int N,
class T,
class Acc>
2757 struct property_traits<vigra::MultiArray<N, T, Acc> const>
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;
2766 template <
unsigned int N,
class T,
class Str
ide>
2767 struct property_traits<vigra::MultiArrayView<N, T, Stride> >
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;
2776 template <
unsigned int N,
class T,
class Str
ide>
2777 struct property_traits<vigra::MultiArrayView<N, T, Stride> const>
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;
2786 #ifdef WITH_BOOST_GRAPH
2791 namespace boost_graph {
2803 template<
unsigned int N,
class DirectedTag>
2814 template<
unsigned int N,
class DirectedTag>
2825 template<
unsigned int N,
class DirectedTag>
2836 template<
unsigned int N,
class DirectedTag>
2838 std::pair<typename vigra::GridGraph<N, DirectedTag>::vertex_iterator,
2848 template<
unsigned int N,
class DirectedTag>
2859 template<
unsigned int N,
class DirectedTag>
2861 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2873 template<
unsigned int N,
class DirectedTag>
2875 std::pair<typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator,
2885 template<
unsigned int N,
class DirectedTag>
2887 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2899 template<
unsigned int N,
class DirectedTag>
2901 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator,
2913 template<
unsigned int N,
class DirectedTag>
2915 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator,
2927 template<
unsigned int N,
class DirectedTag>
2929 std::pair<typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator,
2940 template<
unsigned int N,
class DirectedTag>
2951 template<
unsigned int N,
class DirectedTag>
2962 template<
unsigned int N,
class DirectedTag>
2964 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_iterator,
2973 template<
unsigned int N,
class DirectedTag>
2988 template<
unsigned int N,
class DirectedTag>
2989 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_descriptor,
bool>
3002 template<
unsigned int N,
class T,
class Str
ide,
class U>
3029 template <
typename GR>
3033 template<
unsigned int N,
class DirectedTag>
3034 class InDegMap<vigra::GridGraph<N, DirectedTag> >
3040 explicit InDegMap(
const Graph& graph)
3041 : Graph::InDegMap(graph)
3045 template <
typename GR>
3049 template<
unsigned int N,
class DirectedTag>
3050 class OutDegMap<vigra::GridGraph<N, DirectedTag> >
3056 explicit OutDegMap(
const Graph& graph)
3057 : Graph::OutDegMap(graph)
3066 template<
unsigned int N,
class DirectedTag>
3067 ostream& operator<<(ostream& out,
3070 out <<
"v" << arg.scanOrderIndex();
3074 template<
unsigned int N,
class DirectedTag>
3075 ostream& operator<<(ostream& out,
3078 out <<
"nb" << arg.index();
3084 #ifdef WITH_BOOST_GRAPH
index_type maxEdgeId() const
Get the maximum ID of any edge in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2144
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
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
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
vertex_descriptor Node
The Node descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1563
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
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:727
MultiArrayShape< N >::type shape_type
Shape type of the graph and a node property map.
Definition: multi_gridgraph.hxx:1444
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:2828
Node target(Arc const &a) const
Get the end node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2374
Arc arcFromId(index_type i) const
Get an arc descriptor for the given arc ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2208
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:2863
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< 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:2976
Define a grid graph in arbitrary dimensions.
Definition: multi_fwd.hxx:217
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:1871
adjacency_iterator neighbor_vertex_iterator
Same as adjacency_iterator (API: VIGRA).
Definition: multi_gridgraph.hxx:1481
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
Value operator[](const Key &key) const
Get the out-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1922
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
MultiArrayShape< actual_dimension >::type difference_type
Definition: multi_array.hxx:739
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:2917
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
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
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< 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:2954
R arg(const FFTWComplex< R > &a)
phase
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:1496
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:2806
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
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
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
GridGraphOutArcIterator< N > OutArcIt
Iterator over the outgoing edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1575
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
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:1567
static const bool is_directed
'true' if the graph is directed (API: boost::graph)
Definition: multi_gridgraph.hxx:1433
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
Node nodeFromId(index_type i) const
Get node descriptor for given node ID i (API: LEMON).
Definition: multi_gridgraph.hxx:1993
void set(Key const &k, Value const &v)
Set the property of edge desctiptor key to value v.
Definition: multi_gridgraph.hxx:1784
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
index_type maxNodeId() const
Get the maximum ID of any node in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2005
IndexMap(const GridGraph &)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1853
GridGraphArcDescriptor< N > edge_descriptor
The edge descriptor (API: boost::graph, use via boost::graph_traits<Graph>::edge_descriptor).
Definition: multi_gridgraph.hxx:1516
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
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
Define several graph tags related to graph traversal (API: boost::graph, use via boost::graph_traits<...
Definition: multi_gridgraph.hxx:1539
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:2046
boost_graph::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:1527
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2474
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
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
Value operator[](const Key &key) const
Get the in-degree of the node descriptor key.
Definition: multi_gridgraph.hxx:1888
GridGraphInArcIterator< N > InArcIt
Iterator over the incoming arcs of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1588
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< 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:2817
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
Type of a property map that returns the coordinate of a given node (API: LEMON).
Definition: multi_gridgraph.hxx:1838
DirectedTag directed_category
Is the graph directed or undirected ? (API: boost::graph, use via boost::graph_traits<Graph>::directe...
Definition: multi_gridgraph.hxx:1521
void set(Key const &k, Value const &v)
Set the property of node desctiptor key to value v.
Definition: multi_gridgraph.hxx:1696
Type of an edge property map that maps edge descriptor objects onto property values of type T (API: L...
Definition: multi_gridgraph.hxx:1707
OutDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1916
std::ptrdiff_t MultiArrayIndex
Definition: multi_fwd.hxx:60
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:2903
Value const & operator[](Key const &key) const
Get the grid coordinate of the node descriptor key.
Definition: multi_gridgraph.hxx:1858
bool allLess(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-than
Definition: tinyvector.hxx:1375
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
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
edges_size_type arcNum() const
Get the number of arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2513
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
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:2877
view_type::difference_type difference_type
Definition: multi_array.hxx:2522
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
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:1467
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
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:3004
MultiArray & operator=(const MultiArray &rhs)
Definition: multi_array.hxx:2669
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:2931
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
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
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
view_type::reference reference
Definition: multi_array.hxx:2510
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
GridGraphArcIterator< N, false > ArcIt
Iterator over the acrs (directed edges) of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1584
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
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
NumericTraits< V >::Promote prod(TinyVectorBase< V, SIZE, D1, D2 > const &l)
product of the vector's elements
Definition: tinyvector.hxx:2097
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:2851
index_type maxArcId() const
Get the maximal ID af any arc in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2224
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
vertices_size_type nodeNum() const
Get the number of nodes in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2091
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
Type of a property map that returns the number of incoming edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1866
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:1732
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
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
GridGraph(shape_type const &shape, NeighborhoodType ntype=DirectNeighborhood)
Construct a grid graph with given shape and neighborhood type ntype.
Definition: multi_gridgraph.hxx:1948
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:2840
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:2055
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< 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:2943
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:2966
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
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
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
view_type::value_type value_type
Definition: multi_array.hxx:2498
shape_type vertex_descriptor
The vertex descriptor (API: boost::graph, use via boost::graph_traits<Graph>::vertex_descriptor).
Definition: multi_gridgraph.hxx:1511
bool allGreaterEqual(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise greater-equal
Definition: tinyvector.hxx:1411
Class for fixed size vectors.This class contains an array of size SIZE of the specified VALUETYPE...
Definition: accessor.hxx:940
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
InDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition: multi_gridgraph.hxx:1882
std::pair< typename vigra::GridGraph< N, DirectedTag >::edge_descriptor, bool > edge(typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &u, typename vigra::GridGraph< N, DirectedTag >::vertex_descriptor const &v, vigra::GridGraph< N, DirectedTag > const &g)
Return the pair (edge_descriptor, true) when an edge between vertices u and v exists, or (lemon::INVALID, false) otherwise (API: boost).
Definition: multi_gridgraph.hxx:2990
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
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
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
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
MultiArrayIndex index_type
Type of node and edge IDs.
Definition: multi_gridgraph.hxx:1452
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:2021
Edge edgeFromId(index_type i) const
Get the edge descriptor for the given edge ID i (API: LEMON).
Definition: multi_gridgraph.hxx:2127
GridGraphArcDescriptor< N > Arc
The arc (directed edge) descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1571
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
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
MultiArrayShape< N+1 >::type Edge
The edge descriptor (API: LEMON).
Definition: multi_gridgraph.hxx:1592
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
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:704
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
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
IndexMap indexMap() const
Create a property map that returns the coordinate of each node (API: LEMON GridGraph).
Definition: multi_gridgraph.hxx:2584
GridGraph Graph
The graph type of OutDegMap (works for directed and undirected graphs)
Definition: multi_gridgraph.hxx:1905
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:358
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
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
Type of a property map that returns the number of outgoing edges of a given node (API: LEMON...
Definition: multi_gridgraph.hxx:1900
use only direct neighbors
Definition: multi_fwd.hxx:187
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
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
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_fwd.hxx:186
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
edges_size_type edgeNum() const
Get the number of edges in this graph (API: LEMON).
Definition: multi_gridgraph.hxx:2506
Type of a node property map that maps node descriptor objects onto property values of type T (API: LE...
Definition: multi_gridgraph.hxx:1619
Node source(Arc const &a) const
Get the start node of the given arc a (API: LEMON).
Definition: multi_gridgraph.hxx:2367
GridGraphEdgeIterator< N,!is_directed > EdgeIt
Iterator over the edges of the graph (API: LEMON).
Definition: multi_gridgraph.hxx:1605
Iterate over a virtual array where each element contains its coordinate.
Definition: multi_fwd.hxx:157
GridGraphOutEdgeIterator< N > IncEdgeIt
Iterator over the incident edges of a node (API: LEMON).
Definition: multi_gridgraph.hxx:1596
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
difference_type key_type
Definition: multi_array.hxx:743
view_type::const_reference const_reference
Definition: multi_array.hxx:2514
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
Node const & pos(Node const &v) const
Get the grid cordinate of the given node v (convenience function).
Definition: multi_gridgraph.hxx:2012
Type of an arc property map that maps arc descriptor objects onto property values of type T (API: LEM...
Definition: multi_gridgraph.hxx:1795
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
static const unsigned int dimension
Dimension of the grid.
Definition: multi_gridgraph.hxx:1440