1 // Copyright 2004, 2005 The Trustees of Indiana University.
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 // Authors: Nick Edmonds
9 #ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
10 #define BOOST_GRAPH_MESH_GENERATOR_HPP
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/type_traits/is_base_and_derived.hpp>
17 #include <boost/type_traits/is_same.hpp>
21 template<typename Graph
>
24 typedef typename graph_traits
<Graph
>::directed_category directed_category
;
25 typedef typename graph_traits
<Graph
>::vertices_size_type
30 is_undirected
= (is_base_and_derived
<undirected_tag
,
31 directed_category
>::value
32 || is_same
<undirected_tag
, directed_category
>::value
));
35 typedef std::input_iterator_tag iterator_category
;
36 typedef std::pair
<vertices_size_type
, vertices_size_type
> value_type
;
37 typedef const value_type
& reference
;
38 typedef const value_type
* pointer
;
39 typedef void difference_type
;
42 : x(0), y(0), done(true) { }
44 // Vertices are numbered in row-major order
46 mesh_iterator(vertices_size_type x
, vertices_size_type y
,
48 : x(x
), y(y
), n(x
*y
), source(0), target(1), current(0,1),
49 toroidal(toroidal
), done(false)
50 { assert(x
> 1 && y
> 1); }
52 reference
operator*() const { return current
; }
53 pointer
operator->() const { return ¤t
; }
55 mesh_iterator
& operator++()
59 if (target
== source
+ 1)
60 if (source
< x
* (y
- 1))
64 target
= (source
% x
) < x
- 1 ? source
+ 1 : source
+ x
;
68 else if (target
== source
+ x
) {
70 target
= (source
% x
) < x
- 1 ? source
+ 1 : source
+ x
;
73 if (target
== source
+ 1 || target
== source
- (source
% x
))
74 target
= (source
+ x
) % n
;
75 else if (target
== (source
+ x
) % n
) {
80 target
= (source
% x
) < (x
- 1) ? source
+ 1 : source
- (source
% x
);
86 if (target
== source
- x
)
87 target
= source
% x
> 0 ? source
- 1 : source
+ 1;
88 else if (target
== source
- 1)
89 if ((source
% x
) < (x
- 1))
91 else if (source
< x
* (y
- 1))
96 else if (target
== source
+ 1)
97 if (source
< x
* (y
- 1))
103 else if (target
== source
+ x
) {
105 target
= (source
>= x
) ? source
- x
: source
- 1;
108 if (source
== n
- 1 && target
== (source
+ x
) % n
)
110 else if (target
== source
- 1 || target
== source
+ x
- 1)
111 target
= (source
+ x
) % n
;
112 else if (target
== source
+ 1 || target
== source
- (source
% x
))
113 target
= (source
- x
+ n
) % n
;
114 else if (target
== (source
- x
+ n
) % n
)
115 target
= (source
% x
> 0) ? source
- 1 : source
+ x
- 1;
116 else if (target
== (source
+ x
) % n
) {
118 target
= (source
% x
) < (x
- 1) ? source
+ 1 : source
- (source
% x
);
123 current
.first
= source
;
124 current
.second
= target
;
129 mesh_iterator
operator++(int)
131 mesh_iterator
temp(*this);
136 bool operator==(const mesh_iterator
& other
) const
138 return done
== other
.done
;
141 bool operator!=(const mesh_iterator
& other
) const
142 { return !(*this == other
); }
146 vertices_size_type x
,y
;
147 vertices_size_type n
;
148 vertices_size_type source
;
149 vertices_size_type target
;
156 } // end namespace boost
158 #endif // BOOST_GRAPH_MESH_GENERATOR_HPP