1// Copyright 2004, 2005 The Trustees of Indiana University.
2
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)
6
7// Authors: Nick Edmonds
8// Andrew Lumsdaine
9#ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
10#define BOOST_GRAPH_MESH_GENERATOR_HPP
11
12#include <iterator>
13#include <utility>
14#include <boost/assert.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>
18
19namespace boost {
20
21 template<typename Graph>
22 class mesh_iterator
23 {
24 typedef typename graph_traits<Graph>::directed_category directed_category;
25 typedef typename graph_traits<Graph>::vertices_size_type
26 vertices_size_type;
27
28 BOOST_STATIC_CONSTANT
29 (bool,
30 is_undirected = (is_base_and_derived<undirected_tag,
31 directed_category>::value
32 || is_same<undirected_tag, directed_category>::value));
33
34 public:
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;
40
41 mesh_iterator()
42 : x(0), y(0), done(true) { }
43
44 // Vertices are numbered in row-major order
45 // Assumes directed
46 mesh_iterator(vertices_size_type x, vertices_size_type y,
47 bool toroidal = true)
48 : x(x), y(y), n(x*y), source(0), target(1), current(0,1),
49 toroidal(toroidal), done(false)
50 { BOOST_ASSERT(x > 1 && y > 1); }
51
52 reference operator*() const { return current; }
53 pointer operator->() const { return &current; }
54
55 mesh_iterator& operator++()
56 {
57 if (is_undirected) {
58 if (!toroidal) {
59 if (target == source + 1)
60 if (source < x * (y - 1))
61 target = source + x;
62 else {
63 source++;
64 target = (source % x) < x - 1 ? source + 1 : source + x;
65 if (target > n)
66 done = true;
67 }
68 else if (target == source + x) {
69 source++;
70 target = (source % x) < x - 1 ? source + 1 : source + x;
71 }
72 } else {
73 if (target == source + 1 || target == source - (source % x))
74 target = (source + x) % n;
75 else if (target == (source + x) % n) {
76 if (source == n - 1)
77 done = true;
78 else {
79 source++;
80 target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
81 }
82 }
83 }
84 } else { // Directed
85 if ( !toroidal ) {
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))
90 target = source + 1;
91 else if (source < x * (y - 1))
92 target = source + x;
93 else {
94 done = true;
95 }
96 else if (target == source + 1)
97 if (source < x * (y - 1))
98 target = source + x;
99 else {
100 source++;
101 target = source - x;
102 }
103 else if (target == source + x) {
104 source++;
105 target = (source >= x) ? source - x : source - 1;
106 }
107 } else {
108 if (source == n - 1 && target == (source + x) % n)
109 done = true;
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) {
117 source++;
118 target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
119 }
120 }
121 }
122
123 current.first = source;
124 current.second = target;
125
126 return *this;
127 }
128
129 mesh_iterator operator++(int)
130 {
131 mesh_iterator temp(*this);
132 ++(*this);
133 return temp;
134 }
135
136 bool operator==(const mesh_iterator& other) const
137 {
138 return done == other.done;
139 }
140
141 bool operator!=(const mesh_iterator& other) const
142 { return !(*this == other); }
143
144 private:
145
146 vertices_size_type x,y;
147 vertices_size_type n;
148 vertices_size_type source;
149 vertices_size_type target;
150 value_type current;
151 bool toroidal;
152 bool done;
153 };
154
155
156} // end namespace boost
157
158#endif // BOOST_GRAPH_MESH_GENERATOR_HPP
159

source code of boost/boost/graph/mesh_graph_generator.hpp