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"
44template <
unsigned int N>
45struct NeighborhoodTests;
49template<
unsigned int N,
class T,
class Str
ide>
51typename vigra::MultiArrayView<N, T, Stride>::const_reference
52get(vigra::MultiArrayView<N, T, Stride>
const & pmap,
53 typename vigra::MultiArrayView<N, T, Stride>::difference_type
const & k)
83template<
unsigned int N>
84class GridGraphArcDescriptor
89 typedef typename base_type::value_type value_type;
90 typedef base_type edge_coord_type;
91 typedef value_type index_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)
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;
133 is_reversed_ = opposite;
135 (*this)[N] = diff[N];
138 bool isReversed()
const
143 vertex_descriptor_view vertexDescriptor()
const
148 value_type edgeIndex()
const
162 : pow(3.0, (
int)N) - 1;
165template <
unsigned int N, NeighborhoodType>
166struct GridGraphMaxDegree;
168template <
unsigned int N>
169struct GridGraphMaxDegree<N, DirectNeighborhood>
174template <
unsigned int N>
175struct GridGraphMaxDegree<N, IndirectNeighborhood>
180template <
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);
201template <
class Shape>
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);
263template<
unsigned int N,
bool BackEdgesOnly>
264class GridGraphNeighborIterator
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;
279 friend struct NeighborhoodTests<N>;
281 GridGraphNeighborIterator()
282 : neighborOffsets_(0),
287 template <
class DirectedTag>
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>
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);
394 vertex_descriptor source)
395 : neighborOffsets_(&neighborOffsets),
396 neighborIndices_(BackEdgesOnly ? &backIndices : &neighborIndices),
406 target_ += (*neighborOffsets_)[index_];
411 vertex_descriptor target_;
415template<
unsigned int N,
bool BackEdgesOnly>
416class GridGraphOutEdgeIterator
421 typedef GridGraphArcDescriptor<N> arc_descriptor;
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,
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,
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_;
590template<
unsigned int N,
bool BackEdgesOnly>
591class GridGraphOutArcIterator
592:
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
595 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_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>
622 template <
class DirectedTag>
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)
671template<
unsigned int N,
bool BackEdgesOnly>
672class GridGraphInArcIterator
673:
public GridGraphOutEdgeIterator<N, BackEdgesOnly>
676 typedef GridGraphOutEdgeIterator<N, BackEdgesOnly> base_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>
699 : base_type(g, v, true)
702 template <
class DirectedTag>
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());
743template<
unsigned int N,
bool BackEdgesOnly>
744class 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;
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;
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>
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();
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_;
925template<
unsigned int N,
bool BackEdgesOnly>
926class 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)
1005template<
unsigned int N>
1006inline bool operator==(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
1011template<
unsigned int N>
1012inline bool operator!=(MultiCoordinateIterator<N>
const & i, lemon::Invalid)
1017template<
unsigned int N>
1018inline bool operator==(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
1023template<
unsigned int N>
1024inline bool operator!=(lemon::Invalid, MultiCoordinateIterator<N>
const & i)
1029#define VIGRA_LEMON_INVALID_COMPARISON(type) \
1030template<unsigned int N, bool BackEdgesOnly> \
1031inline bool operator==(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
1035template<unsigned int N, bool BackEdgesOnly> \
1036inline bool operator!=(type<N, BackEdgesOnly> const & i, lemon::Invalid) \
1038 return i.isValid(); \
1040template<unsigned int N, bool BackEdgesOnly> \
1041inline bool operator==(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
1045template<unsigned int N, bool BackEdgesOnly> \
1046inline bool operator!=(lemon::Invalid, type<N, BackEdgesOnly> const & i) \
1048 return i.isValid(); \
1051VIGRA_LEMON_INVALID_COMPARISON(GridGraphNeighborIterator)
1052VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutEdgeIterator)
1053VIGRA_LEMON_INVALID_COMPARISON(GridGraphOutArcIterator)
1054VIGRA_LEMON_INVALID_COMPARISON(GridGraphInArcIterator)
1055VIGRA_LEMON_INVALID_COMPARISON(GridGraphEdgeIterator)
1056VIGRA_LEMON_INVALID_COMPARISON(GridGraphArcIterator)
1058#undef VIGRA_LEMON_INVALID_COMPARISON
1060using boost_graph::directed_tag;
1061using boost_graph::undirected_tag;
1065template <
unsigned int N,
class DirectedTag>
1066struct GridGraphBase;
1068template <
unsigned int N>
1069struct 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)
1131template <
unsigned int N>
1132struct 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_;
1426template<
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;
1436 typedef GridGraph<N, DirectedTag> self_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
1559 typedef self_type Graph;
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;
1645 : base_type(g.shape())
1652 : base_type(g.shape(), t)
1667 NodeMap(difference_type
const & shape, T
const & t)
1668 : base_type(shape, t)
1673 base_type::operator=(m);
1677 NodeMap & operator=(base_type
const & m)
1679 base_type::operator=(m);
1696 void set(Key
const & k, Value
const &
v)
1717 typedef boost_graph::read_write_property_map_tag category;
1719 typedef lemon::True ReferenceMapTag;
1720 typedef key_type Key;
1721 typedef value_type Value;
1722 typedef reference Reference;
1723 typedef const_reference ConstReference;
1733 : base_type(g.edge_propmap_shape())
1740 : base_type(g.edge_propmap_shape(), t)
1755 EdgeMap(difference_type
const & shape, T
const & t)
1756 : base_type(shape, t)
1761 base_type::operator=(m);
1765 EdgeMap & operator=(base_type
const & m)
1767 base_type::operator=(m);
1784 void set(Key
const & k, Value
const &
v)
1832 void set(Key
const & k, Value
const &
v);
1843 typedef Key key_type;
1844 typedef Value value_type;
1845 typedef Value
const & reference;
1846 typedef boost_graph::readable_property_map_tag category;
1872 typedef GridGraph Digraph;
1875 typedef Key key_type;
1876 typedef Value value_type;
1877 typedef Value
const & reference;
1878 typedef boost_graph::readable_property_map_tag category;
1890 return graph_.in_degree(key);
1895 GridGraph
const & graph_;
1906 typedef GridGraph Digraph;
1909 typedef Key key_type;
1910 typedef Value value_type;
1911 typedef Value
const & reference;
1912 typedef boost_graph::readable_property_map_tag category;
1924 return graph_.out_degree(key);
1928 GridGraph
const & graph_;
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();
1979 index_type id(neighbor_vertex_iterator
const & v)
const
1984 index_type id(back_neighbor_vertex_iterator
const & v)
const
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
2112 index_type id(IncEdgeIt
const & e)
const
2117 index_type id(IncBackEdgeIt
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()
2163 Node lastNode = shape() - shape_type(1);
2164 index_type n = neighborIndices_[get_border_type(lastNode)][0];
2165 Arc a(neighbor(lastNode, n), oppositeIndex(n),
false);
2166 max_arc_id_ = detail::CoordinateToScanOrder<N+1>::exec(arc_propmap_shape(), a);
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
2193 index_type id(OutArcIt
const & a)
const
2198 index_type id(OutBackArcIt
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);
2470 return (
degree_size_type)(neighborIndices_[bt].size() - backIndices_[bt].size());
2545 std::pair<edge_descriptor, bool>
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
2597 degree_size_type maxDegree()
const
2599 return (degree_size_type)neighborOffsets_.size();
2602 degree_size_type maxUniqueDegree()
const
2609 shape_type
const & shape()
const
2614 edge_propmap_shape_type edge_propmap_shape()
const
2616 edge_propmap_shape_type res(SkipInitialization);
2617 res.template subarray<0, N>() = shape_;
2618 res[N] = maxUniqueDegree();
2622 edge_propmap_shape_type arc_propmap_shape()
const
2624 edge_propmap_shape_type res(SkipInitialization);
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;
2648 edge_descriptor make_edge_descriptor(vertex_descriptor
const & v,
2649 index_type neighborIndex)
const
2651 if(neighborIndex < maxUniqueDegree())
2652 return edge_descriptor(v, neighborIndex,
false);
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];
2668 source_or_target(edge_descriptor
const & e,
bool return_source)
const
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_;
2721template<
unsigned int N,
class DirectedTag>
2724isInside(GridGraph<N, DirectedTag>
const & g,
2725 typename GridGraph<N, DirectedTag>::vertex_descriptor
const & v)
2732#ifdef WITH_BOOST_GRAPH
2740namespace boost_graph {
2746template <
unsigned int N,
class T,
class Acc>
2747struct property_traits<vigra::MultiArray<N, T, Acc> >
2749 typedef vigra::MultiArray<N, T, Acc> type;
2750 typedef typename type::key_type key_type;
2751 typedef typename type::value_type value_type;
2752 typedef typename type::reference reference;
2753 typedef read_write_property_map_tag category;
2756template <
unsigned int N,
class T,
class Acc>
2757struct property_traits<vigra::MultiArray<N, T, Acc> const>
2759 typedef vigra::MultiArray<N, T, Acc>
const type;
2760 typedef typename type::key_type key_type;
2761 typedef typename type::value_type value_type;
2762 typedef typename type::const_reference reference;
2763 typedef readable_property_map_tag category;
2766template <
unsigned int N,
class T,
class Str
ide>
2767struct property_traits<vigra::MultiArrayView<N, T, Stride> >
2769 typedef vigra::MultiArrayView<N, T, Stride> type;
2770 typedef typename type::key_type key_type;
2771 typedef typename type::value_type value_type;
2772 typedef typename type::reference reference;
2773 typedef read_write_property_map_tag category;
2776template <
unsigned int N,
class T,
class Str
ide>
2777struct property_traits<vigra::MultiArrayView<N, T, Stride> const>
2779 typedef vigra::MultiArrayView<N, T, Stride>
const type;
2780 typedef typename type::key_type key_type;
2781 typedef typename type::value_type value_type;
2782 typedef typename type::const_reference reference;
2783 typedef readable_property_map_tag category;
2786#ifdef WITH_BOOST_GRAPH
2791namespace boost_graph {
2803template<
unsigned int N,
class DirectedTag>
2805typename vigra::GridGraph<N, DirectedTag>::degree_size_type
2806out_degree(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2807 vigra::GridGraph<N, DirectedTag>
const & g)
2814template<
unsigned int N,
class DirectedTag>
2816typename vigra::GridGraph<N, DirectedTag>::degree_size_type
2817in_degree(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2818 vigra::GridGraph<N, DirectedTag>
const & g)
2825template<
unsigned int N,
class DirectedTag>
2827typename vigra::GridGraph<N, DirectedTag>::degree_size_type
2828degree(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2829 vigra::GridGraph<N, DirectedTag>
const & g)
2836template<
unsigned int N,
class DirectedTag>
2838std::pair<typename vigra::GridGraph<N, DirectedTag>::vertex_iterator,
2839 typename vigra::GridGraph<N, DirectedTag>::vertex_iterator>
2840vertices(vigra::GridGraph<N, DirectedTag>
const & g)
2848template<
unsigned int N,
class DirectedTag>
2850typename vigra::GridGraph<N, DirectedTag>::vertices_size_type
2851num_vertices(vigra::GridGraph<N, DirectedTag>
const & g)
2859template<
unsigned int N,
class DirectedTag>
2861std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2862 typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator>
2863adjacent_vertices(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2864 vigra::GridGraph<N, DirectedTag>
const & g)
2873template<
unsigned int N,
class DirectedTag>
2875std::pair<typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator,
2876 typename vigra::GridGraph<N, DirectedTag>::back_neighbor_vertex_iterator>
2877back_adjacent_vertices(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2878 vigra::GridGraph<N, DirectedTag>
const & g)
2885template<
unsigned int N,
class DirectedTag>
2887std::pair<typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator,
2888 typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator>
2889adjacent_vertices_at_iterator(
typename vigra::GridGraph<N, DirectedTag>::vertex_iterator
const & v,
2890 vigra::GridGraph<N, DirectedTag>
const & g)
2899template<
unsigned int N,
class DirectedTag>
2901std::pair<typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator,
2902 typename vigra::GridGraph<N, DirectedTag>::out_edge_iterator>
2903out_edges(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2904 vigra::GridGraph<N, DirectedTag>
const & g)
2913template<
unsigned int N,
class DirectedTag>
2915std::pair<typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator,
2916 typename vigra::GridGraph<N, DirectedTag>::out_back_edge_iterator>
2917out_back_edges(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2918 vigra::GridGraph<N, DirectedTag>
const & g)
2927template<
unsigned int N,
class DirectedTag>
2929std::pair<typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator,
2930 typename vigra::GridGraph<N, DirectedTag>::in_edge_iterator>
2931in_edges(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2932 vigra::GridGraph<N, DirectedTag>
const & g)
2940template<
unsigned int N,
class DirectedTag>
2942typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
2943source(
typename vigra::GridGraph<N, DirectedTag>::edge_descriptor
const & e,
2944 vigra::GridGraph<N, DirectedTag>
const & g)
2951template<
unsigned int N,
class DirectedTag>
2953typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
2954target(
typename vigra::GridGraph<N, DirectedTag>::edge_descriptor
const & e,
2955 vigra::GridGraph<N, DirectedTag>
const & g)
2962template<
unsigned int N,
class DirectedTag>
2964std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_iterator,
2965 typename vigra::GridGraph<N, DirectedTag>::edge_iterator>
2966edges(vigra::GridGraph<N, DirectedTag>
const & g)
2973template<
unsigned int N,
class DirectedTag>
2975typename vigra::GridGraph<N, DirectedTag>::edges_size_type
2976num_edges(vigra::GridGraph<N, DirectedTag>
const & g)
2988template<
unsigned int N,
class DirectedTag>
2989std::pair<typename vigra::GridGraph<N, DirectedTag>::edge_descriptor,
bool>
2990edge(
typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & u,
2991 typename vigra::GridGraph<N, DirectedTag>::vertex_descriptor
const & v,
2992 vigra::GridGraph<N, DirectedTag>
const & g)
3002template<
unsigned int N,
class T,
class Str
ide,
class U>
3004void put(vigra::MultiArrayView<N, T, Stride> & pmap,
3005 typename vigra::MultiArrayView<N, T, Stride>::difference_type
const & k,
3029template <
typename GR>
3033template<
unsigned int N,
class DirectedTag>
3034class InDegMap<vigra::GridGraph<N, DirectedTag> >
3035:
public vigra::GridGraph<N, DirectedTag>::InDegMap
3038 typedef vigra::GridGraph<N, DirectedTag> Graph;
3040 explicit InDegMap(
const Graph& graph)
3041 : Graph::InDegMap(graph)
3045template <
typename GR>
3049template<
unsigned int N,
class DirectedTag>
3050class OutDegMap<vigra::GridGraph<N, DirectedTag> >
3051:
public vigra::GridGraph<N, DirectedTag>::OutDegMap
3054 typedef vigra::GridGraph<N, DirectedTag> Graph;
3056 explicit OutDegMap(
const Graph& graph)
3057 : Graph::OutDegMap(graph)
3066template<
unsigned int N,
class DirectedTag>
3067ostream& operator<<(ostream& out,
3068 typename vigra::GridGraph<N, DirectedTag>::vertex_iterator
const & arg)
3070 out <<
"v" <<
arg.scanOrderIndex();
3074template<
unsigned int N,
class DirectedTag>
3075ostream& operator<<(ostream& out,
3076 typename vigra::GridGraph<N, DirectedTag>::adjacency_iterator
const & arg)
3078 out <<
"nb" <<
arg.index();
3084#ifdef WITH_BOOST_GRAPH
3086 using vigra::boost_graph::out_edges;
3087 using vigra::boost_graph::out_degree;
3088 using vigra::boost_graph::source;
3089 using vigra::boost_graph::target;
3090 using vigra::boost_graph::in_edges;
3091 using vigra::boost_graph::in_degree;
3092 using vigra::boost_graph::adjacent_vertices;
3093 using vigra::boost_graph::vertices;
3094 using vigra::boost_graph::edges;
3095 using vigra::boost_graph::edge;
3096 using vigra::boost_graph::num_vertices;
3097 using vigra::boost_graph::num_edges;
Definition array_vector.hxx:514
ArcMap(difference_type const &shape)
Construct property map for the given shape (preallocates a zero-initialized entry for each arc of a g...
ArcMap(GridGraph const &g)
Construct property map for the given graph g (preallocates a zero-initialized entry for each arc of t...
ArcMap(difference_type const &shape, T const &t)
Construct property map for the given shape (preallocates an entry with initial value t for each arc o...
Value & operator[](Key const &key)
Read/write access to the value associated with arc descriptor key.
void set(Key const &k, Value const &v)
Set the property of arc desctiptor key to value v.
ArcMap(GridGraph const &g, T const &t)
Construct property map for the given graph g (preallocates an entry with initial value t for each arc...
Value const & operator[](Key const &key) const
Read-only access to the value associated with arc descriptor key.
Type of an edge property map that maps edge descriptor objects onto property values of type T (API: L...
Definition multi_gridgraph.hxx:1709
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
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
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
Value & operator[](Key const &key)
Read/write access to the value associated with edge descriptor key.
void set(Key const &k, Value const &v)
Set the property of edge desctiptor key to value v.
Definition multi_gridgraph.hxx:1784
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
Value const & operator[](Key const &key) const
Read-only 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
Value operator[](const Key &key) const
Get the in-degree of the node descriptor key.
Definition multi_gridgraph.hxx:1888
InDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition multi_gridgraph.hxx:1882
IndexMap(const GridGraph &)
Construct property map for the given graph.
Definition multi_gridgraph.hxx:1853
Value const & operator[](Key const &key) const
Get the grid coordinate of the node descriptor key.
Definition multi_gridgraph.hxx:1858
Type of a node property map that maps node descriptor objects onto property values of type T (API: LE...
Definition multi_gridgraph.hxx:1621
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
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
Value & operator[](Key const &key)
Read/write access to the value associated with node descriptor key.
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
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
void set(Key const &k, Value const &v)
Set the property of node desctiptor key to value v.
Definition multi_gridgraph.hxx:1696
Value const & operator[](Key const &key) const
Read-only access to the value associated with node descriptor key.
OutDegMap(const GridGraph &graph)
Construct property map for the given graph.
Definition multi_gridgraph.hxx:1916
GridGraph Graph
The graph type of OutDegMap (works for directed and undirected graphs)
Definition multi_gridgraph.hxx:1905
Value operator[](const Key &key) const
Get the out-degree of the node descriptor key.
Definition multi_gridgraph.hxx:1922
Define a grid graph in arbitrary dimensions.
Definition multi_gridgraph.hxx:1429
adjacency_iterator neighbor_vertex_iterator
Definition multi_gridgraph.hxx:1481
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
Node const & pos(Node const &v) const
Get the grid cordinate of the given node v (convenience function).
Definition multi_gridgraph.hxx:2012
GridGraphArcDescriptor< N > Arc
Definition multi_gridgraph.hxx:1571
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
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
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
GridGraphOutArcIterator< N, true > OutBackArcIt
Definition multi_gridgraph.hxx:1580
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
boost_graph::no_property vertex_property_type
Definition multi_gridgraph.hxx:1532
MultiArrayShape< N >::type shape_type
Definition multi_gridgraph.hxx:1444
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
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
GridGraphOutArcIterator< N > OutArcIt
Definition multi_gridgraph.hxx:1575
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
GridGraphArcIterator< N, !is_directed > edge_iterator
Definition multi_gridgraph.hxx:1506
GridGraphEdgeIterator< N, !is_directed > EdgeIt
Definition multi_gridgraph.hxx:1605
static const bool is_directed
Definition multi_gridgraph.hxx:1433
Edge edgeFromId(index_type i) const
Get the edge descriptor for the given edge ID i (API: LEMON).
Definition multi_gridgraph.hxx:2127
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
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
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
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
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
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(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 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
MultiArrayShape< N+1 >::type edge_propmap_shape_type
Definition multi_gridgraph.hxx:1448
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
GridGraphOutArcIterator< N, true > out_back_edge_iterator
Definition multi_gridgraph.hxx:1501
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
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
Arc arcFromId(index_type i) const
Get an arc descriptor for the given arc ID i (API: LEMON).
Definition multi_gridgraph.hxx:2208
Node target(Arc const &a) const
Definition multi_gridgraph.hxx:2374
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
GridGraphArcIterator< N, false > ArcIt
Definition multi_gridgraph.hxx:1584
GridGraphNeighborIterator< N, true > back_neighbor_vertex_iterator
Definition multi_gridgraph.hxx:1486
GridGraphArcDescriptor< N > edge_descriptor
Definition multi_gridgraph.hxx:1516
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
shape_type vertex_descriptor
Definition multi_gridgraph.hxx:1511
GridGraph(shape_type const &shape, NeighborhoodType ntype=DirectNeighborhood)
Construct a grid graph with given shape and neighborhood type ntype.
Definition multi_gridgraph.hxx:1948
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
vertex_descriptor Node
The Node descriptor (API: LEMON).
Definition multi_gridgraph.hxx:1563
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
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
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
index_type maxArcId() const
Definition multi_gridgraph.hxx:2224
static const unsigned int dimension
Definition multi_gridgraph.hxx:1440
MultiArrayShape< N+1 >::type Edge
The edge descriptor (API: LEMON).
Definition multi_gridgraph.hxx:1592
MultiArrayIndex vertices_size_type
Definition multi_gridgraph.hxx:1457
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
IndexMap indexMap() const
Create a property map that returns the coordinate of each node (API: LEMON GridGraph).
Definition multi_gridgraph.hxx:2584
edges_size_type arcNum() const
Get the number of arc in this graph (API: LEMON).
Definition multi_gridgraph.hxx:2513
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
edges_size_type edgeNum() const
Get the number of edges in this graph (API: LEMON).
Definition multi_gridgraph.hxx:2506
DIRECTED_TAG directed_category
Definition multi_gridgraph.hxx:1521
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
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
MultiArrayIndex degree_size_type
Definition multi_gridgraph.hxx:1467
GridGraphInArcIterator< N > InArcIt
Definition multi_gridgraph.hxx:1588
Node u(Edge const &e) const
Definition multi_gridgraph.hxx:2382
Node source(Arc const &a) const
Definition multi_gridgraph.hxx:2367
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
vertex_iterator get_vertex_iterator() const
Get vertex iterator pointing to the first vertex of this graph (convenience function,...
Definition multi_gridgraph.hxx:2021
vertices_size_type nodeNum() const
Get the number of nodes in this graph (API: LEMON).
Definition multi_gridgraph.hxx:2091
index_type maxNodeId() const
Definition multi_gridgraph.hxx:2005
GridGraphOutArcIterator< N > out_edge_iterator
Definition multi_gridgraph.hxx:1496
boost_graph::disallow_parallel_edge_tag edge_parallel_category
Definition multi_gridgraph.hxx:1527
MultiCoordinateIterator< N > vertex_iterator
Definition multi_gridgraph.hxx:1472
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
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
vertex_iterator NodeIt
Iterator over all nodes of the graph (API: LEMON).
Definition multi_gridgraph.hxx:1567
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
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
MultiArrayIndex edges_size_type
Definition multi_gridgraph.hxx:1462
neighbor_vertex_iterator get_neighbor_vertex_iterator(vertex_descriptor const &v) const
Get an iterator pointing to the first neighbor of the given vertex (convenience function,...
Definition multi_gridgraph.hxx:2046
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
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
GridGraphInArcIterator< N > in_edge_iterator
Definition multi_gridgraph.hxx:1491
GridGraphOutEdgeIterator< N > IncEdgeIt
Definition multi_gridgraph.hxx:1596
Node nodeFromId(index_type i) const
Get node descriptor for given node ID i (API: LEMON).
Definition multi_gridgraph.hxx:1993
GridGraphOutEdgeIterator< N, true > IncBackEdgeIt
Definition multi_gridgraph.hxx:1601
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
MultiArrayIndex index_type
Definition multi_gridgraph.hxx:1452
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
GridGraphNeighborIterator< N > adjacency_iterator
Definition multi_gridgraph.hxx:1477
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
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
index_type maxEdgeId() const
Definition multi_gridgraph.hxx:2144
Definition multi_shape.hxx:267
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
difference_type key_type
Definition multi_array.hxx:743
view_type::const_reference const_reference
Definition multi_array.hxx:2516
MultiArray()
Definition multi_array.hxx:2590
view_type::difference_type difference_type
Definition multi_array.hxx:2524
view_type::reference reference
Definition multi_array.hxx:2512
view_type::value_type value_type
Definition multi_array.hxx:2500
Iterate over a virtual array where each element contains its coordinate.
Definition multi_iterator.hxx:89
TinyVectorView< VALUETYPE, TO-FROM > subarray() const
Definition tinyvector.hxx:887
bool allGreaterEqual(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise greater-equal
Definition tinyvector.hxx:1411
R arg(const FFTWComplex< R > &a)
phase
Definition fftw3.hxx:1009
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition multi_fwd.hxx:186
@ DirectNeighborhood
use only direct neighbors
Definition multi_fwd.hxx:187
NumericTraits< V >::Promote prod(TinyVectorBase< V, SIZE, D1, D2 > const &l)
product of the vector's elements
Definition tinyvector.hxx:2097
bool allLess(TinyVectorBase< V1, SIZE, D1, D2 > const &l, TinyVectorBase< V2, SIZE, D3, D4 > const &r)
pointwise less-than
Definition tinyvector.hxx:1375
std::ptrdiff_t MultiArrayIndex
Definition multi_fwd.hxx:60
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition fftw3.hxx:825
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition fftw3.hxx:841
Define several graph tags related to graph traversal (API: boost::graph, use via boost::graph_traits<...
Definition multi_gridgraph.hxx:1545