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,
394 vertex_descriptor source)
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),
448 unsigned int nbtype = g.get_border_type(v);
449 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], *v, opposite);
452 template <
class DirectedTag>
453 GridGraphOutEdgeIterator(GridGraph<N, DirectedTag>
const & g,
454 typename GridGraph<N, DirectedTag>::Node
const & v,
456 : neighborOffsets_(0),
461 unsigned int nbtype = g.get_border_type(v);
462 init(&(*g.edgeIncrementArray())[nbtype], &(*g.neighborIndexArray(BackEdgesOnly))[nbtype], v, opposite);
465 GridGraphOutEdgeIterator & operator++()
471 GridGraphOutEdgeIterator operator++(
int)
473 GridGraphOutEdgeIterator ret(*
this);
478 const_reference operator*()
const
480 return edge_descriptor_;
483 operator const_reference()
const
485 return edge_descriptor_;
488 const_pointer operator->()
const
490 return &edge_descriptor_;
493 index_type index()
const
498 index_type neighborIndex()
const
500 return (*neighborIndices_)[index_];
503 arc_descriptor
const & arcDescriptor()
const
505 return edge_descriptor_;
508 bool operator==(GridGraphOutEdgeIterator
const & other)
const
510 return index_ == other.index();
513 bool operator!=(GridGraphOutEdgeIterator
const & other)
const
515 return index_ != other.index();
520 return index_ < (index_type)neighborIndices_->size();
525 return index_ >= (index_type)neighborIndices_->size();
528 GridGraphOutEdgeIterator getEndIterator()
const
530 GridGraphOutEdgeIterator res(*
this);
531 res.index_ = (index_type)neighborIndices_->size();
538 GridGraphOutEdgeIterator(ArrayVector<arc_descriptor>
const & neighborOffsets,
539 ArrayVector<index_type>
const & neighborIndices,
540 ArrayVector<index_type>
const & backIndices,
541 shape_type
const & source)
542 : neighborOffsets_(0),
547 init(&neighborOffsets, BackEdgesOnly ? &backIndices : &neighborIndices, source);
550 void init(ArrayVector<arc_descriptor>
const * neighborOffsets,
551 ArrayVector<index_type>
const * neighborIndices,
552 shape_type
const & source,
555 neighborOffsets_ = neighborOffsets;
556 neighborIndices_ = neighborIndices;
557 edge_descriptor_ = arc_descriptor(source, 0);
559 updateEdgeDescriptor(opposite);
562 void increment(
bool opposite)
565 updateEdgeDescriptor(opposite);
568 void updateEdgeDescriptor(
bool opposite)
571 edge_descriptor_.increment((*neighborOffsets_)[index_], opposite);
574 ArrayVector<arc_descriptor>
const * neighborOffsets_;
575 ArrayVector<index_type>
const * neighborIndices_;
576 arc_descriptor edge_descriptor_;
580 template<
unsigned int N,
bool BackEdgesOnly>
581 class GridGraphOutArcIterator
582 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
585 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
586 typedef typename MultiArrayShape<N>::type shape_type;
588 typedef GridGraphArcDescriptor<N> value_type;
589 typedef value_type
const & reference;
590 typedef value_type
const & const_reference;
591 typedef value_type
const * pointer;
592 typedef value_type
const * const_pointer;
594 typedef std::forward_iterator_tag iterator_category;
596 friend struct NeighborhoodTests<N>;
597 friend class GridGraphEdgeIterator<N, BackEdgesOnly>;
599 GridGraphOutArcIterator()
603 explicit GridGraphOutArcIterator(base_type
const & b)
607 template <
class DirectedTag>
608 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
612 template <
class DirectedTag>
613 GridGraphOutArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
617 GridGraphOutArcIterator & operator++()
619 base_type::operator++();
623 GridGraphOutArcIterator operator++(
int)
625 GridGraphOutArcIterator ret(*
this);
630 const_reference operator*()
const
632 return this->edge_descriptor_;
635 operator const_reference()
const
637 return this->edge_descriptor_;
640 const_pointer operator->()
const
642 return &this->edge_descriptor_;
645 GridGraphOutArcIterator getEndIterator()
const
647 return GridGraphOutArcIterator(base_type::getEndIterator());
653 GridGraphOutArcIterator(ArrayVector<value_type>
const & neighborOffsets,
654 ArrayVector<index_type>
const & neighborIndices,
655 ArrayVector<index_type>
const & backIndices,
656 shape_type
const & source)
657 : base_type(neighborOffsets, neighborIndices, backIndices, source)
661 template<
unsigned int N,
bool BackEdgesOnly>
662 class GridGraphInArcIterator
663 :
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
666 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_type;
667 typedef typename MultiArrayShape<N>::type shape_type;
669 typedef GridGraphArcDescriptor<N> value_type;
670 typedef value_type
const & reference;
671 typedef value_type
const & const_reference;
672 typedef value_type
const * pointer;
673 typedef value_type
const * const_pointer;
675 typedef std::forward_iterator_tag iterator_category;
677 friend struct NeighborhoodTests<N>;
679 GridGraphInArcIterator()
683 explicit GridGraphInArcIterator(base_type
const & b)
687 template <
class DirectedTag>
688 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::NodeIt
const & v)
689 : base_type(g, v, true)
692 template <
class DirectedTag>
693 GridGraphInArcIterator(GridGraph<N, DirectedTag>
const & g,
typename GridGraph<N, DirectedTag>::Node
const & v)
694 : base_type(g, v, true)
697 GridGraphInArcIterator & operator++()
699 base_type::increment(
true);
703 GridGraphInArcIterator operator++(
int)
705 GridGraphInArcIterator ret(*
this);
710 const_reference operator*()
const
712 return this->edge_descriptor_;
715 operator const_reference()
const
717 return this->edge_descriptor_;
720 const_pointer operator->()
const
722 return &this->edge_descriptor_;
725 GridGraphInArcIterator getEndIterator()
const
727 return GridGraphInArcIterator(base_type::getEndIterator());
733 template<
unsigned int N,
bool BackEdgesOnly>
734 class GridGraphEdgeIterator
737 typedef GridGraphEdgeIterator<N, BackEdgesOnly> self_type;
738 typedef MultiCoordinateIterator<N> vertex_iterator;
739 typedef typename vertex_iterator::value_type vertex_descriptor;
740 typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
741 typedef typename MultiArrayShape<N+1>::type edge_descriptor;
742 typedef edge_descriptor value_type;
743 typedef value_type
const * pointer;
744 typedef value_type
const * const_pointer;
745 typedef value_type
const & reference;
746 typedef value_type
const & const_reference;
747 typedef typename MultiArrayShape<N>::type shape_type;
750 typedef std::forward_iterator_tag iterator_category;
752 friend struct NeighborhoodTests<N>;
754 GridGraphEdgeIterator()
755 : neighborOffsets_(0),
759 template <
class DirectedTag>
760 GridGraphEdgeIterator(GridGraph<N, DirectedTag>
const & g)
761 : neighborOffsets_(g.edgeIncrementArray()),
762 neighborIndices_(g.neighborIndexArray(BackEdgesOnly)),
764 outEdgeIterator_(g, vertexIterator_)
766 if(outEdgeIterator_.atEnd())
769 if(vertexIterator_.isValid())
770 outEdgeIterator_ = out_edge_iterator(g, vertexIterator_);
774 GridGraphEdgeIterator & operator++()
777 if(outEdgeIterator_.atEnd())
780 if(vertexIterator_.isValid())
782 unsigned int borderType = vertexIterator_.borderType();
783 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
789 GridGraphEdgeIterator operator++(
int)
791 GridGraphEdgeIterator ret(*
this);
796 const_reference operator*()
const
798 return *outEdgeIterator_;
801 operator const_reference()
const
803 return *outEdgeIterator_;
806 const_pointer operator->()
const
808 return outEdgeIterator_.operator->();
813 return outEdgeIterator_.neighborIndex();
817 bool operator==(GridGraphEdgeIterator
const & other)
const
819 return (vertexIterator_ == other.vertexIterator_ && outEdgeIterator_ == other.outEdgeIterator_);
822 bool operator!=(GridGraphEdgeIterator
const & other)
const
829 return vertexIterator_.isValid();
837 GridGraphEdgeIterator getEndIterator()
const
839 GridGraphEdgeIterator ret(*
this);
840 ret.vertexIterator_ = vertexIterator_.getEndIterator();
841 vertex_iterator lastVertex = ret.vertexIterator_ - 1;
842 unsigned int borderType = lastVertex.borderType();
843 ret.outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *lastVertex);
844 ret.outEdgeIterator_ = ret.outEdgeIterator_.getEndIterator();
851 GridGraphEdgeIterator(ArrayVector<ArrayVector<typename out_edge_iterator::value_type> >
const & neighborOffsets,
852 ArrayVector<ArrayVector<index_type> >
const & neighborIndices,
853 ArrayVector<ArrayVector<index_type> >
const & backIndices,
854 shape_type
const & shape)
855 : neighborOffsets_(&neighborOffsets),
856 neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
857 vertexIterator_(shape),
858 outEdgeIterator_(neighborOffsets[vertexIterator_.borderType()],
859 neighborIndices[vertexIterator_.borderType()],
860 backIndices[vertexIterator_.borderType()], shape_type())
862 if(outEdgeIterator_.atEnd())
865 if(vertexIterator_.isValid())
867 unsigned int borderType = vertexIterator_.borderType();
868 outEdgeIterator_.init(&(*neighborOffsets_)[borderType], &(*neighborIndices_)[borderType], *vertexIterator_);
873 ArrayVector<ArrayVector<typename out_edge_iterator::value_type> >
const * neighborOffsets_;
874 ArrayVector<ArrayVector<index_type> >
const * neighborIndices_;
875 vertex_iterator vertexIterator_;
876 out_edge_iterator outEdgeIterator_;
879 template<
unsigned int N,
bool BackEdgesOnly>
880 class GridGraphArcIterator
881 :
public GridGraphEdgeIterator<N, BackEdgesOnly>
884 typedef GridGraphEdgeIterator<N, BackEdgesOnly> base_type;
885 typedef GridGraphArcIterator<N, BackEdgesOnly> self_type;
886 typedef MultiCoordinateIterator<N> vertex_iterator;
887 typedef typename vertex_iterator::value_type vertex_descriptor;
888 typedef GridGraphOutArcIterator<N, BackEdgesOnly> out_edge_iterator;
889 typedef typename out_edge_iterator::value_type edge_descriptor;
890 typedef edge_descriptor value_type;
891 typedef value_type
const * pointer;
892 typedef value_type
const * const_pointer;
893 typedef value_type
const & reference;
894 typedef value_type
const & const_reference;
895 typedef typename MultiArrayShape<N>::type shape_type;
898 typedef std::forward_iterator_tag iterator_category;
900 friend struct NeighborhoodTests<N>;
902 GridGraphArcIterator()
906 explicit GridGraphArcIterator(base_type
const & b)
910 template <
class DirectedTag>
911 GridGraphArcIterator(GridGraph<N, DirectedTag>
const & g)
915 GridGraphArcIterator & operator++()
917 base_type::operator++();
921 GridGraphArcIterator operator++(
int)
923 GridGraphArcIterator ret(*
this);
928 const_reference operator*()
const
930 return *(this->outEdgeIterator_);
933 operator const_reference()
const
935 return *(this->outEdgeIterator_);
938 const_pointer operator->()
const
940 return this->outEdgeIterator_.operator->();
943 GridGraphArcIterator getEndIterator()
const
945 return GridGraphArcIterator(base_type::getEndIterator());
951 GridGraphArcIterator(ArrayVector<ArrayVector<value_type> >
const & neighborOffsets,
952 ArrayVector<ArrayVector<index_type> >
const & neighborIndices,
953 ArrayVector<ArrayVector<index_type> >
const & backIndices,
954 shape_type
const & shape)
955 : base_type(neighborOffsets, neighborIndices, backIndices, shape)
959 template<
unsigned int N>
960 inline bool operator==(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
965 template<
unsigned int N>
966 inline bool operator!=(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
971 template<
unsigned int N>
972 inline bool operator==(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
977 template<
unsigned int N>
978 inline bool operator!=(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
983 #define VIGRA_LEMON_INVALID_COMPARISON(type) \
984 template<unsigned int N, bool BackEdgesOnly> \
985 inline bool operator==(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
989 template<unsigned int N, bool BackEdgesOnly> \
990 inline bool operator!=(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
992 return i.isValid(); \
994 template<unsigned int N, bool BackEdgesOnly> \
995 inline bool operator==(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
999 template<unsigned int N, bool BackEdgesOnly> \
1000 inline bool operator!=(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
1002 return i.isValid(); \
1005 VIGRA_LEMON_INVALID_COMPARISON(GridGraphNeighborIterator)
1006 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutEdgeIterator)
1007 VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutArcIterator)
1008 VIGRA_LEMON_INVALID_COMPARISON(GridGraphInArcIterator)
1009 VIGRA_LEMON_INVALID_COMPARISON(GridGraphEdgeIterator)
1010 VIGRA_LEMON_INVALID_COMPARISON(GridGraphArcIterator)
1012 #undef VIGRA_LEMON_INVALID_COMPARISON
1014 using boost::directed_tag;
1015 using boost::undirected_tag;
1019 template <
unsigned int N,
class DirectedTag>
1020 struct GridGraphBase;
1022 template <
unsigned int N>
1023 struct GridGraphBase<N, directed_tag>
1027 :
public MultiArray<N+1, Multiband<T> >
1030 typedef MultiArray<N+1, Multiband<T> > base_type;
1031 typedef typename base_type::difference_type difference_type;
1032 typedef typename base_type::key_type key_type;
1033 typedef typename base_type::value_type value_type;
1034 typedef typename base_type::reference reference;
1035 typedef typename base_type::const_reference const_reference;
1036 typedef boost::read_write_property_map_tag category;
1038 typedef lemon::True ReferenceMapTag;
1039 typedef key_type Key;
1040 typedef value_type Value;
1041 typedef reference Reference;
1042 typedef const_reference ConstReference;
1048 explicit ArcMap(GridGraph<N, directed_tag>
const & g)
1049 : base_type(g.arc_propmap_shape())
1052 ArcMap(GridGraph<N, directed_tag>
const & g, T
const & t)
1053 : base_type(g.arc_propmap_shape(), t)
1056 explicit ArcMap(difference_type
const & shape)
1060 ArcMap(difference_type
const & shape, T
const & t)
1061 : base_type(shape, t)
1064 ArcMap & operator=(ArcMap
const & m)
1066 base_type::operator=(m);
1070 ArcMap & operator=(base_type
const & m)
1072 base_type::operator=(m);
1078 void set(Key
const & k, Value
const & v)
1085 template <
unsigned int N>
1086 struct GridGraphBase<N, undirected_tag>
1088 typedef lemon::True UndirectedTag;
1092 :
public MultiArray<N+1, Multiband<T> >
1095 typedef MultiArray<N+1, Multiband<T> > base_type;
1096 typedef GridGraphArcDescriptor<N> difference_type;
1097 typedef difference_type key_type;
1098 typedef typename base_type::value_type value_type;
1099 typedef typename base_type::reference reference;
1100 typedef typename base_type::const_reference const_reference;
1101 typedef boost::read_write_property_map_tag category;
1103 typedef lemon::True ReferenceMapTag;
1104 typedef key_type Key;
1105 typedef value_type Value;
1106 typedef reference Reference;
1107 typedef const_reference ConstReference;
1113 explicit ArcMap(GridGraph<N, undirected_tag>
const & g)
1114 : base_type(g.arc_propmap_shape()),
1118 ArcMap(GridGraph<N, undirected_tag>
const & g, T
const & t)
1119 : base_type(g.arc_propmap_shape(), t),
1123 ArcMap & operator=(ArcMap
const & m)
1125 base_type::operator=(m);
1129 ArcMap & operator=(base_type
const & m)
1131 base_type::operator=(m);
1135 reference operator[](difference_type
const & s)
1139 return base_type::operator[](graph_->directedArc(s));
1143 return base_type::operator[](s);
1147 const_reference operator[](difference_type
const & s)
const
1151 return base_type::operator[](graph_->directedArc(s));
1155 return base_type::operator[](s);
1159 void set(Key
const & k, Value
const & v)
1164 GridGraph<N, undirected_tag>
const * graph_;
1380 template<
unsigned int N,
class DirectedTag=undirected_tag>
1382 :
public detail::GridGraphBase<N, DirectedTag>
1387 static const bool is_directed = IsSameType<DirectedTag, directed_tag>::value;
1389 typedef detail::GridGraphBase<N, DirectedTag> base_type;
1494 :
virtual public boost::bidirectional_graph_tag,
1495 virtual public boost::adjacency_graph_tag,
1496 virtual public boost::vertex_list_graph_tag,
1497 virtual public boost::edge_list_graph_tag,
1498 virtual public boost::adjacency_matrix_tag
1525 typedef GridGraphArcDescriptor<N>
Arc;
1538 typedef GridGraphArcIterator<N, false>
ArcIt;
1559 typedef GridGraphEdgeIterator<N, !is_directed>
EdgeIt;
1561 typedef lemon::True NodeNumTag;
1562 typedef lemon::True EdgeNumTag;
1563 typedef lemon::True ArcNumTag;
1564 typedef lemon::True FindEdgeTag;
1565 typedef lemon::True FindArcTag;
1583 typedef boost::read_write_property_map_tag category;
1585 typedef lemon::True ReferenceMapTag;
1586 typedef key_type Key;
1587 typedef value_type Value;
1588 typedef reference Reference;
1589 typedef const_reference ConstReference;
1621 NodeMap(difference_type
const & shape, T
const & t)
1631 NodeMap & operator=(base_type
const & m)
1645 Value
const &
operator[](Key
const & key)
const;
1650 void set(Key
const & k, Value
const & v)
1671 typedef boost::read_write_property_map_tag category;
1673 typedef lemon::True ReferenceMapTag;
1675 typedef value_type Value;
1676 typedef reference Reference;
1677 typedef const_reference ConstReference;
1709 EdgeMap(difference_type
const & shape, T
const & t)
1719 EdgeMap & operator=(base_type
const & m)
1733 Value
const &
operator[](Key
const & key)
const;
1738 void set(Key
const & k, Value
const & v)
1768 explicit ArcMap(difference_type
const & shape);
1774 ArcMap(difference_type
const & shape, T
const & t);
1782 Value
const &
operator[](Key
const & key)
const;
1786 void set(Key
const & k, Value
const & v);
1798 typedef Value value_type;
1799 typedef Value const & reference;
1800 typedef boost::readable_property_map_tag category;
1830 typedef Value value_type;
1831 typedef Value
const & reference;
1832 typedef boost::readable_property_map_tag category;
1864 typedef Value value_type;
1865 typedef Value
const & reference;
1866 typedef boost::readable_property_map_tag category;
1905 num_vertices_(
prod(shape)),
1906 num_edges_(gridGraphEdgeCount(shape, ntype,
is_directed)),
1907 max_node_id_(num_vertices_ - 1),
1910 neighborhoodType_(ntype)
1914 detail::makeArrayNeighborhood(neighborOffsets_, neighborExists_, neighborhoodType_);
1915 detail::computeNeighborOffsets(neighborOffsets_, neighborExists_, incrementalOffsets_,
1916 edgeDescriptorOffsets_, neighborIndices_, backIndices_,
is_directed);
1926 return detail::CoordinateToScanOrder<N>::exec(shape(), v);
1929 index_type
id(
NodeIt const & v)
const
1931 return v.scanOrderIndex();
1951 return Node(lemon::INVALID);
1953 Node res(SkipInitialization);
1954 detail::ScanOrderToCoordinate<N>::exec(i, shape(), res);
1962 return prod(shape()) - 1;
2041 return num_vertices_;
2059 return detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), e);
2062 index_type
id(
EdgeIt const & e)
const
2085 return Edge(lemon::INVALID);
2087 Edge res(SkipInitialization);
2088 detail::ScanOrderToCoordinate<N+1>::exec(i, edge_propmap_shape(), res);
2090 unsigned int b = detail::BorderTypeImpl<N>::exec(res.template subarray<0, N>(), shape());
2091 if(neighborExists_[b][res[N]])
2094 return Edge(lemon::INVALID);
2101 if(max_edge_id_ == -2)
2102 const_cast<GridGraph *
>(
this)->computeMaxEdgeAndArcId();
2103 return max_edge_id_;
2109 void computeMaxEdgeAndArcId()
2119 index_type n = neighborIndices_[get_border_type(lastNode)][0];
2120 Arc a(neighbor(lastNode, n), oppositeIndex(n),
false);
2121 max_arc_id_ = detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), a);
2125 max_edge_id_ = max_arc_id_;
2129 Arc a(lastNode, backIndices_[get_border_type(lastNode)].back(),
false);
2130 max_edge_id_ = detail::CoordinateToScanOrder<N+1>::exec(edge_propmap_shape(), a);
2140 return detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), directedArc(a));
2143 index_type
id(
ArcIt const & a)
const
2166 return Arc(lemon::INVALID);
2169 detail::ScanOrderToCoordinate<N+1>::exec(i, arc_propmap_shape(), res);
2170 unsigned int b = detail::BorderTypeImpl<N>::exec(res.template subarray<0, N>(), shape());
2171 if(neighborExists_[b][res[N]])
2172 return undirectedArc(res);
2174 return Arc(lemon::INVALID);
2181 if(max_arc_id_ == -2)
2182 const_cast<GridGraph *
>(
this)->computeMaxEdgeAndArcId();
2191 return !a.isReversed();
2201 return Arc(e, !forward);
2203 return Arc(
v(e), oppositeIndex(e[N]),
true);
2216 return Arc(lemon::INVALID);
2225 Node start(
u(e)), end(
v(e));
2230 return Node(lemon::INVALID);
2239 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2240 :
Arc(a, !a.isReversed());
2246 Arc directedArc(
Arc const & a)
const
2248 return a.isReversed()
2249 ?
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
false)
2257 Arc undirectedArc(
Arc const & a)
const
2259 return a.edgeIndex() < maxUniqueDegree()
2261 :
Arc(neighbor(a.vertexDescriptor(), a.edgeIndex()), oppositeIndex(a.edgeIndex()),
true);
2268 return source(e.arcDescriptor());
2275 return source(e.arcDescriptor());
2296 return target(e.arcDescriptor());
2303 return target(e.arcDescriptor());
2324 return source_or_target(a,
true);
2331 return source_or_target(a,
false);
2339 return Node(e.template subarray<0,N>());
2347 return Node(e.template subarray<0,N>()) + neighborOffsets_[e[N]];
2424 unsigned int bt = get_border_type(v);
2500 std::pair<edge_descriptor, bool>
2501 edge(vertex_descriptor
const &
u, vertex_descriptor
const & v)
const
2503 std::pair<edge_descriptor, bool> res(lemon::INVALID,
false);
2506 end = i.getEndIterator();
2507 for (; i != end; ++i)
2511 res.first = make_edge_descriptor(u, i.neighborIndex());
2523 return this->
edge(u, v).first;
2530 return this->
edge(u, v).first;
2547 bool isDirected()
const
2564 shape_type
const & shape()
const
2572 res.template subarray<0, N>() = shape_;
2573 res[N] = maxUniqueDegree();
2580 res.template subarray<0, N>() = shape_;
2581 res[N] = maxDegree();
2585 unsigned int get_border_type(vertex_descriptor
const & v)
const
2587 return detail::BorderTypeImpl<N>::exec(v, shape_);
2590 unsigned int get_border_type(vertex_iterator
const & v)
const
2592 return v.borderType();
2595 index_type oppositeIndex(index_type neighborIndex)
const
2597 return maxDegree() - neighborIndex - 1;
2604 index_type neighborIndex)
const
2606 if(neighborIndex < maxUniqueDegree())
2609 return edge_descriptor(neighbor(v, neighborIndex), oppositeIndex(neighborIndex),
true);
2612 shape_type
const & neighborOffset(index_type neighborIndex)
const
2614 return neighborOffsets_[neighborIndex];
2617 vertex_descriptor neighbor(vertex_descriptor
const & v, index_type neighborIndex)
const
2619 return v + neighborOffsets_[neighborIndex];
2627 if ((return_source && e.isReversed()) ||
2628 (!return_source && !e.isReversed()))
2630 return neighbor(e.vertexDescriptor(), e.edgeIndex());
2634 return e.vertexDescriptor();
2638 NeighborOffsetArray
const * neighborOffsetArray()
const
2640 return &neighborOffsets_;
2643 RelativeNeighborOffsetsArray
const * neighborIncrementArray()
const
2645 return &incrementalOffsets_;
2648 RelativeEdgeOffsetsArray
const * edgeIncrementArray()
const
2650 return &edgeDescriptorOffsets_;
2653 IndexArray
const * neighborIndexArray(
bool backEdgesOnly)
const
2655 return backEdgesOnly
2657 : &neighborIndices_;
2661 NeighborOffsetArray neighborOffsets_;
2662 NeighborExistsArray neighborExists_;
2663 IndexArray neighborIndices_, backIndices_;
2664 RelativeNeighborOffsetsArray incrementalOffsets_;
2665 RelativeEdgeOffsetsArray edgeDescriptorOffsets_;
2667 MultiArrayIndex num_vertices_, num_edges_, max_node_id_, max_arc_id_, max_edge_id_;
2685 template <
unsigned int N,
class T,
class Acc>
2686 struct property_traits<vigra::MultiArray<N, T, Acc> >
2689 typedef typename type::key_type key_type;
2690 typedef typename type::value_type value_type;
2691 typedef typename type::reference reference;
2692 typedef boost::read_write_property_map_tag category;
2695 template <
unsigned int N,
class T,
class Acc>
2696 struct property_traits<vigra::MultiArray<N, T, Acc> const>
2699 typedef typename type::key_type key_type;
2700 typedef typename type::value_type value_type;
2701 typedef typename type::const_reference reference;
2702 typedef boost::readable_property_map_tag category;
2705 template <
unsigned int N,
class T,
class Str
ide>
2706 struct property_traits<vigra::MultiArrayView<N, T, Stride> >
2709 typedef typename type::key_type key_type;
2710 typedef typename type::value_type value_type;
2711 typedef typename type::reference reference;
2712 typedef boost::read_write_property_map_tag category;
2715 template <
unsigned int N,
class T,
class Str
ide>
2716 struct property_traits<vigra::MultiArrayView<N, T, Stride> const>
2719 typedef typename type::key_type key_type;
2720 typedef typename type::value_type value_type;
2721 typedef typename type::const_reference reference;
2722 typedef boost::readable_property_map_tag category;
2727 template<
unsigned int N,
class DirectedTag>
2738 template<
unsigned int N,
class DirectedTag>
2749 template<
unsigned int N,
class DirectedTag>
2760 template<
unsigned int N,
class DirectedTag>
2762 std::pair<typename vigra::GridGraph<N, DirectedTag>::vertex_iterator,
2772 template<
unsigned int N,
class DirectedTag>
2783 template<
unsigned int N,
class DirectedTag>
2785 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2797 template<
unsigned int N,
class DirectedTag>
2799 std::pair<typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator,
2809 template<
unsigned int N,
class DirectedTag>
2811 std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2823 template<
unsigned int N,
class DirectedTag>
2825 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator,
2837 template<
unsigned int N,
class DirectedTag>
2839 std::pair<typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator,
2851 template<
unsigned int N,
class DirectedTag>
2853 std::pair<typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator,
2864 template<
unsigned int N,
class DirectedTag>
2875 template<
unsigned int N,
class DirectedTag>
2886 template<
unsigned int N,
class DirectedTag>
2888 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_iterator,
2897 template<
unsigned int N,
class DirectedTag>
2912 template<
unsigned int N,
class DirectedTag>
2913 std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_descriptor,
bool>
2926 template<
unsigned int N,
class T,
class Str
ide,
class U>
2952 template<
unsigned int N>
2955 typedef boost::readable_property_map_tag category;
2956 typedef typename graph_type::index_type value_type;
2957 typedef typename graph_type::vertex_descriptor key_type;
2958 typedef const value_type& reference;
2961 IDMapper(
const graph_type &graph)
2962 : map_helper(graph.get_vertex_iterator())
2965 typename graph_type::vertex_iterator map_helper;
2968 template<
unsigned int N>
2969 struct property_map<vigra::GridGraph<N>, boost::vertex_index_t>
2971 typedef IDMapper<N> type;
2972 typedef IDMapper<N> const_type;
2976 template<
unsigned int N>
2978 typename IDMapper<N>::value_type
2979 get(
const IDMapper<N> & mapper,
2980 const typename IDMapper<N>::key_type &k)
2982 return (mapper.map_helper + k).scanOrderIndex();
2986 template<
unsigned int N>
2987 typename boost::property_map<vigra::GridGraph<N>, boost::vertex_index_t>::type
2992 return IDMapper<N>(graph);
2996 template<
unsigned int N>
2998 get(boost::vertex_index_t,
3001 return (IDMapper<N>(graph).map_helper + v).scanOrderIndex();
3017 template <
typename GR>
3021 template<
unsigned int N,
class DirectedTag>
3022 class InDegMap<vigra::GridGraph<N, DirectedTag> >
3028 explicit InDegMap(
const Graph& graph)
3029 : Graph::InDegMap(graph)
3033 template <
typename GR>
3037 template<
unsigned int N,
class DirectedTag>
3038 class OutDegMap<vigra::GridGraph<N, DirectedTag> >
3044 explicit OutDegMap(
const Graph& graph)
3045 : Graph::OutDegMap(graph)
3053 namespace boost_graph {
3062 template<
unsigned int N,
class DirectedTag>
3066 out <<
"v" << arg.scanOrderIndex();
3070 template<
unsigned int N,
class DirectedTag>
3074 out <<
"nb" << arg.index();