Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
undirected_boost.h
Go to the documentation of this file.
1#ifndef UG_GRAPH_UNDIRECTED_BOOST_H
2#define UG_GRAPH_UNDIRECTED_BOOST_H
3
4#include "undirected.h"
5//#include "trace.h"
6#include <boost/iterator/counting_iterator.hpp>
7
8namespace boost{
9
10#if 0
11template<class T>
12class UM_adjacency_iterator : public iterator_facade<
13 UM_adjacency_iterator<T>,
14 typename ug::SparseMatrix<T>::const_row_iterator,
15 std::input_iterator_tag,
16 size_t, // <= reference
17 std::intmax_t // difference_type
18 >{ //
19 typedef ug::SparseMatrix<T> M;
20 typedef typename M::const_row_iterator iter_t;
21
22public:
23 typedef iter_t* value_type;
24 typedef intmax_t difference_type;
25 typedef size_t reference;
26
27public:
28 UM_adjacency_iterator() : _base(nullptr), _end(nullptr){}
29 UM_adjacency_iterator(UM_adjacency_iterator&& p) = delete;
30 UM_adjacency_iterator(UM_adjacency_iterator const& p)
31 : _base(p._base?(new iter_t(*p._base)) : nullptr)
32 , _end(p._end?(new iter_t(*p._end)) : nullptr){
33 }
34 UM_adjacency_iterator(value_type p, value_type e){
35 assert(p);
36 _base = new iter_t(*p);
37 _end = new iter_t(*e);
38 skip_zeroes();
39 }
40 ~UM_adjacency_iterator(){
41 delete _base;
42 delete _end;
43 _base = nullptr;
44 _end = nullptr;
45 }
46 T const& value() const {
47 assert(_base);
48 return _base->value();
49 }
50 int row() const {
51 assert(_base);
52 return _base->row();
53 }
54 size_t idx() const { untested();
55 assert(_base);
56 return _base->idx();
57 }
58 reference dereference() const {
59 assert(_base);
60 return _base->index(); // row?
61 }
62 bool operator==(const UM_adjacency_iterator& other) const {
63 assert(_base);
64 assert(other._base);
65 return *_base == *other._base;
66 }
67 bool operator!=(const UM_adjacency_iterator& other) const {
68 assert(_base);
69 assert(other._base);
70 return *_base != *other._base;
71 }
72 UM_adjacency_iterator operator=(const UM_adjacency_iterator& other) {
73 if(other._base){
74 _base = new iter_t(*other._base);
75 }else{ untested();
76 _base = nullptr;
77 }
78 if(other._end){
79 _end = new iter_t(*other._end);
80 }else{ untested();
81 _end = nullptr;
82 }
83 return *this;
84 }
85
86private:
87 // could use boost::filter_iterator, but does not work yet.
88 void skip_zeroes(){
89 while((*_base) != (*_end)){
90 if(iszero(_base->value())){
91 ++(*_base);
92 }else{
93 break;
94 }
95 }
96 }
97 bool equal(UM_adjacency_iterator const& other) const { untested();
98 assert(_base);
99 assert(other._base);
100 return *_base == *other._base;
101 }
102 void increment() {
103 assert(_base);
104 assert(_end);
105 ++(*_base);
106 skip_zeroes();
107 }
108 void decrement() { untested();
109 // incomplete(); // don't use. too complicated.
110 assert(_base);
111 --(*_base);
112 }
113
114private:
115 value_type _base;
116 value_type _end;
117 friend class iterator_core_access;
118}; // UM_adjacency_iterator
119#else
120template<class T>
121class UM_out_edge_iterator : public iterator_facade<
122 UM_out_edge_iterator<T>,
123 typename ug::UndirectedMatrix<T>::adjacency_iterator,
124 // bidirectional_traversal_tag, // breaks InputIterator (why?)
125 std::input_iterator_tag,
126 typename ug::UndirectedMatrix<T>::edge, // <= reference
127 std::intmax_t // difference_type
128 >{ //
129private: // types
130 typedef iterator_facade<
133 // bidirectional_traversal_tag, // breaks InputIterator (why?)
134 std::input_iterator_tag,
135 typename ug::UndirectedMatrix<T>::edge, // <= reference
136 std::intmax_t // difference_type
138public: // types
141 typedef intmax_t difference_type;
144
145public: // construct
147 }
149 : base_class(), _v(v), _base(w) {
150 }
152 : base_class(p), _v(p._v), _base(p._base){
153 }
158 _v = p._v;
159 _base = p._base;
160 return *this;
161 }
163#if 0
164public: // op
165 UM_out_edge_iterator operator+(int a) const{ untested();
166 UM_out_edge_iterator ret(*this);
167 ret.base.first += a;
168 return ret;
169 }
170 UM_out_edge_iterator operator-(int a) const{ untested();
171 UM_out_edge_iterator ret(*this);
172 ret.base.first -= a;
173 return ret;
174 }
175 difference_type operator-(UM_out_edge_iterator const& other) const{ untested();
176 UM_out_edge_iterator ret(*this);
177 return ret.base.first - other.base.first;
178 }
179#endif
180private:
182 return edge_type(_v, *_base);
183 }
184 bool equal(UM_out_edge_iterator const& other) const { untested();
185 assert(_base.first == other._base.first);
186 return _base.second == other._base.second;
187 }
188 void increment() { untested();
189 ++_base;
190 }
191 void decrement() { untested();
192 --_base;
193 }
194 // bool operator==(const UM_out_edge_iterator& other) const
195 // { incomplete();
196 // return false;
197 // }
198public:
200 ++_base;
201 return *this;
202 }
204 UM_out_edge_iterator copy(*this);
205 ++*this;
206 return copy;
207 }
208 bool operator==(const UM_out_edge_iterator& other) const {
209 return _base == other._base;
210 }
211 bool operator!=(const UM_out_edge_iterator& other) const {
212 return _base != other._base;
213 }
214
215private:
216 int _v;
219}; // UM_out_edge_iterator
220#endif
221
222template <class T> struct graph_traits<ug::UndirectedMatrix<T>>{
224 typedef int vertex_descriptor;
225 typedef typename G::edge edge_descriptor;
226 typedef undirected_tag directed_category;
227 typedef disallow_parallel_edge_tag edge_parallel_category;
229 typedef counting_iterator<size_t> vertex_iterator;
231 typedef typename G::adjacency_iterator adjacency_iterator;
232 typedef int degree_size_type;
234};
235
236template<class T>
237std::pair<counting_iterator<size_t>, counting_iterator<size_t> > vertices(
239{
240 counting_iterator<size_t> b(0);
241 counting_iterator<size_t> e(M.num_rows());
242
243 return std::make_pair(b,e);
244}
245
246template<class T>
247int degree(int v, ug::UndirectedMatrix<T> const& M)
248{
249 return M.degree(v);
250}
251
252template<class T>
254{
255 return degree(v, M);
256}
257
258template<class T>
260{
261 return degree(v, M);
262}
263
264template<class T>
265std::pair<UM_out_edge_iterator<T>, UM_out_edge_iterator<T> >
267{
269 typedef UM_out_edge_iterator<T> ei;
270
271 ai b(M.begin_row(v));
272 ai e(M.end_row(v));
273
274 return std::make_pair(ei(v, b), ei(v, e));
275}
276
277template<class T>
278std::pair<typename ug::UndirectedMatrix<T>::adjacency_iterator,
281{
283
284 ei b(M.begin_row(v));
285 ei e(M.end_row(v));
286
287 return std::make_pair(b, e);
288}
289
290template<class T>
291int source(typename T::edge const& e, T const&)
292{
293 return e.first;
294}
295
296template<class T>
297int target(typename T::edge const& e, T const&)
298{
299 return e.second;
300}
301
302template<class T>
303struct property_map<ug::UndirectedMatrix<T>, vertex_index_t>{
306};
307
308template<class T>
309inline typename property_map<ug::UndirectedMatrix<T>, vertex_index_t>::const_type
310get(vertex_index_t, ug::UndirectedMatrix<T> const& m)
311{
313}
314
315template<class T>
317{
318 return M.num_rows();
319}
320
321template <class T>
322class degree_property_map< ug::UndirectedMatrix<T> >
323: public put_get_helper< typename graph_traits< ug::UndirectedMatrix<T> >::degree_size_type,
324 degree_property_map< ug::UndirectedMatrix<T> > >
325{
326public:
328 typedef typename graph_traits< Graph >::vertex_descriptor key_type;
329 typedef typename graph_traits< Graph >::degree_size_type value_type;
331 typedef readable_property_map_tag category;
332 degree_property_map(const Graph& g) : m_g(g) {}
333 value_type operator[](const key_type& v) const { return degree(v, m_g); }
334
335private:
336 Graph const& m_g;
337};
338
339template<class T>
340degree_property_map< ug::UndirectedMatrix<T> >
342{
343 return degree_property_map< ug::UndirectedMatrix<T> >(g);
344}
345
346} // boost
347
348namespace ug{
349
350// adl hack/workaround?
351// (required by adjacency list concept
352using boost::vertices;
354// required by vertexListGraph concept
356using boost::out_edges; // used in IndicenceGraph concept
357using boost::out_degree; // used in IndicenceGraph concept
358
359} // ug
360#endif
parameterString p
Definition undirected_boost.h:128
ug::UndirectedMatrix< T >::edge reference
Definition undirected_boost.h:142
void increment()
Definition undirected_boost.h:188
friend class iterator_core_access
Definition undirected_boost.h:218
iterator_facade< UM_out_edge_iterator< T >, typename ug::UndirectedMatrix< T >::adjacency_iterator, std::input_iterator_tag, typename ug::UndirectedMatrix< T >::edge, std::intmax_t > base_class
Definition undirected_boost.h:137
~UM_out_edge_iterator()
Definition undirected_boost.h:155
UM_out_edge_iterator(UM_out_edge_iterator const &p)
Definition undirected_boost.h:151
int _v
Definition undirected_boost.h:216
UM_out_edge_iterator()
Definition undirected_boost.h:146
UM_out_edge_iterator operator++(int)
Definition undirected_boost.h:203
reference dereference() const
Definition undirected_boost.h:181
bool equal(UM_out_edge_iterator const &other) const
Definition undirected_boost.h:184
UM_out_edge_iterator(UM_out_edge_iterator &&p)=delete
intmax_t difference_type
Definition undirected_boost.h:141
UM_out_edge_iterator & operator=(UM_out_edge_iterator const &p)
Definition undirected_boost.h:157
ug::SparseMatrix< T > M
Definition undirected_boost.h:139
UM_out_edge_iterator & operator++()
Definition undirected_boost.h:199
ug::UndirectedMatrix< T >::edge edge_type
Definition undirected_boost.h:143
void decrement()
Definition undirected_boost.h:191
UM_out_edge_iterator(int v, value_type w)
Definition undirected_boost.h:148
value_type _base
Definition undirected_boost.h:217
bool operator!=(const UM_out_edge_iterator &other) const
Definition undirected_boost.h:211
ug::UndirectedMatrix< T >::adjacency_iterator value_type
Definition undirected_boost.h:140
UM_out_edge_iterator & operator=(UM_out_edge_iterator &&p)=delete
bool operator==(const UM_out_edge_iterator &other) const
Definition undirected_boost.h:208
graph_traits< Graph >::vertex_descriptor key_type
Definition undirected_boost.h:328
readable_property_map_tag category
Definition undirected_boost.h:331
degree_property_map(const Graph &g)
Definition undirected_boost.h:332
Graph const & m_g
Definition undirected_boost.h:336
graph_traits< Graph >::degree_size_type value_type
Definition undirected_boost.h:329
ug::UndirectedMatrix< T > Graph
Definition undirected_boost.h:327
value_type operator[](const key_type &v) const
Definition undirected_boost.h:333
value_type reference
Definition undirected_boost.h:330
Definition sparsematrix_boost.h:350
sparse matrix for big, variable sparse matrices.
Definition sparsematrix.h:99
Definition undirected.h:57
Definition undirected.h:50
int num_rows() const
Definition undirected.h:96
int degree(int v) const
Definition undirected.h:110
boost::geometry::concatenate_iterator< boost::SM_adjacency_iterator< value_type >, G_adj_it, int, int > adjacency_iterator
Definition undirected.h:73
adjacency_iterator begin_row(int row) const
Definition undirected.h:128
adjacency_iterator end_row(int row) const
Definition undirected.h:134
bool operator==(const MathVector< N, T > &v, const MathVector< N, T > &w)
Definition math_vector.h:523
bool operator!=(const MathVector< N, T > &v, const MathVector< N, T > &w)
Definition math_vector.h:552
#define untested()
Definition lua_table_handle.cpp:15
Definition boost_serialization_routines.h:49
std::pair< typename graph_traits< T >::adjacency_iterator, typename graph_traits< T >::adjacency_iterator > adjacent_vertices(size_t v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:108
std::pair< SM_out_edge_iterator< typename T::value_type >, SM_out_edge_iterator< typename T::value_type > > out_edges(size_t v, ug::BidirectionalMatrix< T > const &g)
Definition bidirectional_boost.h:136
int out_degree(int v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:76
int degree(int v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:88
int in_degree(int v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:82
std::pair< counting_iterator< size_t >, counting_iterator< size_t > > vertices(ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:60
int num_vertices(ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:70
SM_edge_weight_map< typename T::value_type, ug::BidirectionalMatrix< T > > get(edge_weight_t, ug::BidirectionalMatrix< T > const &g)
Definition bidirectional_boost.h:157
size_t target(SM_edge< typename T::value_type > const &e, ug::BidirectionalMatrix< T > const &m)
Definition bidirectional_boost.h:100
size_t source(SM_edge< typename T::value_type > const &e, ug::BidirectionalMatrix< T > const &)
Definition bidirectional_boost.h:94
degree_property_map< ug::UndirectedMatrix< T > > make_degree_map(const ug::UndirectedMatrix< T > &g)
Definition undirected_boost.h:341
the ug namespace
bool iszero(__T __val)
Definition sparsematrix_impl.h:53
T value_type
Definition sparsematrix_interface.h:2
Definition sparsematrix_boost.h:309
disallow_parallel_edge_tag edge_parallel_category
Definition undirected_boost.h:227
undirected_tag directed_category
Definition undirected_boost.h:226
G::adjacency_iterator adjacency_iterator
Definition undirected_boost.h:231
ug::UndirectedMatrix< T > G
Definition undirected_boost.h:223
int vertex_descriptor
Definition undirected_boost.h:224
int degree_size_type
Definition undirected_boost.h:232
counting_iterator< size_t > vertex_iterator
Definition undirected_boost.h:229
int vertices_size_type
Definition undirected_boost.h:233
G::edge edge_descriptor
Definition undirected_boost.h:225
SM_traversal_tag traversal_category
Definition undirected_boost.h:228
UM_out_edge_iterator< T > out_edge_iterator
Definition undirected_boost.h:230
sparse_matrix_index_map< T > type
Definition undirected_boost.h:304
function ProblemDisc new(problemDesc, dom)