]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2009 Trustees of Indiana University. | |
3 | // Authors: Michael Hansen, Andrew Lumsdaine | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. (See | |
6 | // accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | //======================================================================= | |
9 | ||
10 | #ifndef BOOST_GRAPH_GRID_GRAPH_HPP | |
11 | #define BOOST_GRAPH_GRID_GRAPH_HPP | |
12 | ||
13 | #include <cmath> | |
14 | #include <functional> | |
15 | #include <numeric> | |
16 | ||
17 | #include <boost/array.hpp> | |
18 | #include <boost/bind.hpp> | |
19 | #include <boost/limits.hpp> | |
20 | #include <boost/graph/graph_traits.hpp> | |
21 | #include <boost/graph/properties.hpp> | |
22 | #include <boost/iterator/counting_iterator.hpp> | |
23 | #include <boost/iterator/transform_iterator.hpp> | |
24 | #include <boost/property_map/property_map.hpp> | |
25 | ||
26 | #define BOOST_GRID_GRAPH_TEMPLATE_PARAMS \ | |
27 | std::size_t DimensionsT, typename VertexIndexT, \ | |
28 | typename EdgeIndexT | |
29 | ||
30 | #define BOOST_GRID_GRAPH_TYPE \ | |
31 | grid_graph<DimensionsT, VertexIndexT, EdgeIndexT> | |
32 | ||
33 | #define BOOST_GRID_GRAPH_TRAITS_T \ | |
34 | typename graph_traits<BOOST_GRID_GRAPH_TYPE > | |
35 | ||
36 | namespace boost { | |
37 | ||
38 | // Class prototype for grid_graph | |
39 | template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
40 | class grid_graph; | |
41 | ||
42 | //=================== | |
43 | // Index Property Map | |
44 | //=================== | |
45 | ||
46 | template <typename Graph, | |
47 | typename Descriptor, | |
48 | typename Index> | |
49 | struct grid_graph_index_map { | |
50 | public: | |
51 | typedef Index value_type; | |
52 | typedef Index reference_type; | |
53 | typedef reference_type reference; | |
54 | typedef Descriptor key_type; | |
55 | typedef readable_property_map_tag category; | |
56 | ||
57 | grid_graph_index_map() { } | |
58 | ||
59 | grid_graph_index_map(const Graph& graph) : | |
60 | m_graph(&graph) { } | |
61 | ||
62 | value_type operator[](key_type key) const { | |
63 | return (m_graph->index_of(key)); | |
64 | } | |
65 | ||
66 | friend inline Index | |
67 | get(const grid_graph_index_map<Graph, Descriptor, Index>& index_map, | |
68 | const typename grid_graph_index_map<Graph, Descriptor, Index>::key_type& key) | |
69 | { | |
70 | return (index_map[key]); | |
71 | } | |
72 | ||
73 | protected: | |
74 | const Graph* m_graph; | |
75 | }; | |
76 | ||
77 | template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
78 | struct property_map<BOOST_GRID_GRAPH_TYPE, vertex_index_t> { | |
79 | typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, | |
80 | BOOST_GRID_GRAPH_TRAITS_T::vertex_descriptor, | |
81 | BOOST_GRID_GRAPH_TRAITS_T::vertices_size_type> type; | |
82 | typedef type const_type; | |
83 | }; | |
84 | ||
85 | template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
86 | struct property_map<BOOST_GRID_GRAPH_TYPE, edge_index_t> { | |
87 | typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, | |
88 | BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor, | |
89 | BOOST_GRID_GRAPH_TRAITS_T::edges_size_type> type; | |
90 | typedef type const_type; | |
91 | }; | |
92 | ||
93 | //========================== | |
94 | // Reverse Edge Property Map | |
95 | //========================== | |
96 | ||
97 | template <typename Descriptor> | |
98 | struct grid_graph_reverse_edge_map { | |
99 | public: | |
100 | typedef Descriptor value_type; | |
101 | typedef Descriptor reference_type; | |
102 | typedef reference_type reference; | |
103 | typedef Descriptor key_type; | |
104 | typedef readable_property_map_tag category; | |
105 | ||
106 | grid_graph_reverse_edge_map() { } | |
107 | ||
108 | value_type operator[](const key_type& key) const { | |
109 | return (value_type(key.second, key.first)); | |
110 | } | |
111 | ||
112 | friend inline Descriptor | |
113 | get(const grid_graph_reverse_edge_map<Descriptor>& rev_map, | |
114 | const typename grid_graph_reverse_edge_map<Descriptor>::key_type& key) | |
115 | { | |
116 | return (rev_map[key]); | |
117 | } | |
118 | }; | |
119 | ||
120 | template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
121 | struct property_map<BOOST_GRID_GRAPH_TYPE, edge_reverse_t> { | |
122 | typedef grid_graph_reverse_edge_map<BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor> type; | |
123 | typedef type const_type; | |
124 | }; | |
125 | ||
126 | //================= | |
127 | // Function Objects | |
128 | //================= | |
129 | ||
130 | namespace detail { | |
131 | ||
132 | // vertex_at | |
133 | template <typename Graph> | |
134 | struct grid_graph_vertex_at { | |
135 | ||
136 | typedef typename graph_traits<Graph>::vertex_descriptor result_type; | |
137 | ||
138 | grid_graph_vertex_at() : m_graph(0) {} | |
139 | ||
140 | grid_graph_vertex_at(const Graph* graph) : | |
141 | m_graph(graph) { } | |
142 | ||
143 | result_type | |
144 | operator() | |
145 | (typename graph_traits<Graph>::vertices_size_type vertex_index) const { | |
146 | return (vertex(vertex_index, *m_graph)); | |
147 | } | |
148 | ||
149 | private: | |
150 | const Graph* m_graph; | |
151 | }; | |
152 | ||
153 | // out_edge_at | |
154 | template <typename Graph> | |
155 | struct grid_graph_out_edge_at { | |
156 | ||
157 | private: | |
158 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
159 | ||
160 | public: | |
161 | typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
162 | ||
163 | grid_graph_out_edge_at() : m_vertex(), m_graph(0) {} | |
164 | ||
165 | grid_graph_out_edge_at(vertex_descriptor source_vertex, | |
166 | const Graph* graph) : | |
167 | m_vertex(source_vertex), | |
168 | m_graph(graph) { } | |
169 | ||
170 | result_type | |
171 | operator() | |
172 | (typename graph_traits<Graph>::degree_size_type out_edge_index) const { | |
173 | return (out_edge_at(m_vertex, out_edge_index, *m_graph)); | |
174 | } | |
175 | ||
176 | private: | |
177 | vertex_descriptor m_vertex; | |
178 | const Graph* m_graph; | |
179 | }; | |
180 | ||
181 | // in_edge_at | |
182 | template <typename Graph> | |
183 | struct grid_graph_in_edge_at { | |
184 | ||
185 | private: | |
186 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
187 | ||
188 | public: | |
189 | typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
190 | ||
191 | grid_graph_in_edge_at() : m_vertex(), m_graph(0) {} | |
192 | ||
193 | grid_graph_in_edge_at(vertex_descriptor target_vertex, | |
194 | const Graph* graph) : | |
195 | m_vertex(target_vertex), | |
196 | m_graph(graph) { } | |
197 | ||
198 | result_type | |
199 | operator() | |
200 | (typename graph_traits<Graph>::degree_size_type in_edge_index) const { | |
201 | return (in_edge_at(m_vertex, in_edge_index, *m_graph)); | |
202 | } | |
203 | ||
204 | private: | |
205 | vertex_descriptor m_vertex; | |
206 | const Graph* m_graph; | |
207 | }; | |
208 | ||
209 | // edge_at | |
210 | template <typename Graph> | |
211 | struct grid_graph_edge_at { | |
212 | ||
213 | typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
214 | ||
215 | grid_graph_edge_at() : m_graph(0) {} | |
216 | ||
217 | grid_graph_edge_at(const Graph* graph) : | |
218 | m_graph(graph) { } | |
219 | ||
220 | result_type | |
221 | operator() | |
222 | (typename graph_traits<Graph>::edges_size_type edge_index) const { | |
223 | return (edge_at(edge_index, *m_graph)); | |
224 | } | |
225 | ||
226 | private: | |
227 | const Graph* m_graph; | |
228 | }; | |
229 | ||
230 | // adjacent_vertex_at | |
231 | template <typename Graph> | |
232 | struct grid_graph_adjacent_vertex_at { | |
233 | ||
234 | public: | |
235 | typedef typename graph_traits<Graph>::vertex_descriptor result_type; | |
236 | ||
237 | grid_graph_adjacent_vertex_at(result_type source_vertex, | |
238 | const Graph* graph) : | |
239 | m_vertex(source_vertex), | |
240 | m_graph(graph) { } | |
241 | ||
242 | result_type | |
243 | operator() | |
244 | (typename graph_traits<Graph>::degree_size_type adjacent_index) const { | |
245 | return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph)); | |
246 | } | |
247 | ||
248 | private: | |
249 | result_type m_vertex; | |
250 | const Graph* m_graph; | |
251 | }; | |
252 | ||
253 | } // namespace detail | |
254 | ||
255 | //=========== | |
256 | // Grid Graph | |
257 | //=========== | |
258 | ||
259 | template <std::size_t Dimensions, | |
260 | typename VertexIndex = std::size_t, | |
261 | typename EdgeIndex = VertexIndex> | |
262 | class grid_graph { | |
263 | ||
264 | private: | |
265 | typedef boost::array<bool, Dimensions> WrapDimensionArray; | |
266 | grid_graph() { }; | |
267 | ||
268 | public: | |
269 | ||
270 | typedef grid_graph<Dimensions, VertexIndex, EdgeIndex> type; | |
271 | ||
272 | // sizes | |
273 | typedef VertexIndex vertices_size_type; | |
274 | typedef EdgeIndex edges_size_type; | |
275 | typedef EdgeIndex degree_size_type; | |
276 | ||
277 | // descriptors | |
278 | typedef boost::array<VertexIndex, Dimensions> vertex_descriptor; | |
279 | typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; | |
280 | ||
281 | // vertex_iterator | |
282 | typedef counting_iterator<vertices_size_type> vertex_index_iterator; | |
283 | typedef detail::grid_graph_vertex_at<type> vertex_function; | |
284 | typedef transform_iterator<vertex_function, vertex_index_iterator> vertex_iterator; | |
285 | ||
286 | // edge_iterator | |
287 | typedef counting_iterator<edges_size_type> edge_index_iterator; | |
288 | typedef detail::grid_graph_edge_at<type> edge_function; | |
289 | typedef transform_iterator<edge_function, edge_index_iterator> edge_iterator; | |
290 | ||
291 | // out_edge_iterator | |
292 | typedef counting_iterator<degree_size_type> degree_iterator; | |
293 | typedef detail::grid_graph_out_edge_at<type> out_edge_function; | |
294 | typedef transform_iterator<out_edge_function, degree_iterator> out_edge_iterator; | |
295 | ||
296 | // in_edge_iterator | |
297 | typedef detail::grid_graph_in_edge_at<type> in_edge_function; | |
298 | typedef transform_iterator<in_edge_function, degree_iterator> in_edge_iterator; | |
299 | ||
300 | // adjacency_iterator | |
301 | typedef detail::grid_graph_adjacent_vertex_at<type> adjacent_vertex_function; | |
302 | typedef transform_iterator<adjacent_vertex_function, degree_iterator> adjacency_iterator; | |
303 | ||
304 | // categories | |
305 | typedef directed_tag directed_category; | |
306 | typedef disallow_parallel_edge_tag edge_parallel_category; | |
307 | struct traversal_category : virtual public incidence_graph_tag, | |
308 | virtual public adjacency_graph_tag, | |
309 | virtual public vertex_list_graph_tag, | |
310 | virtual public edge_list_graph_tag, | |
311 | virtual public bidirectional_graph_tag, | |
312 | virtual public adjacency_matrix_tag { }; | |
313 | ||
314 | static inline vertex_descriptor null_vertex() | |
315 | { | |
316 | vertex_descriptor maxed_out_vertex; | |
317 | std::fill(maxed_out_vertex.begin(), maxed_out_vertex.end(), | |
318 | (std::numeric_limits<vertices_size_type>::max)()); | |
319 | ||
320 | return (maxed_out_vertex); | |
321 | } | |
322 | ||
323 | // Constructor that defaults to no wrapping for all dimensions. | |
324 | grid_graph(vertex_descriptor dimension_lengths) : | |
325 | m_dimension_lengths(dimension_lengths) { | |
326 | ||
327 | std::fill(m_wrap_dimension.begin(), | |
328 | m_wrap_dimension.end(), false); | |
329 | ||
330 | precalculate(); | |
331 | } | |
332 | ||
333 | // Constructor that allows for wrapping to be specified for all | |
334 | // dimensions at once. | |
335 | grid_graph(vertex_descriptor dimension_lengths, | |
336 | bool wrap_all_dimensions) : | |
337 | m_dimension_lengths(dimension_lengths) { | |
338 | ||
339 | std::fill(m_wrap_dimension.begin(), | |
340 | m_wrap_dimension.end(), | |
341 | wrap_all_dimensions); | |
342 | ||
343 | precalculate(); | |
344 | } | |
345 | ||
346 | // Constructor that allows for individual dimension wrapping to be | |
347 | // specified. | |
348 | grid_graph(vertex_descriptor dimension_lengths, | |
349 | WrapDimensionArray wrap_dimension) : | |
350 | m_dimension_lengths(dimension_lengths), | |
351 | m_wrap_dimension(wrap_dimension) { | |
352 | ||
353 | precalculate(); | |
354 | } | |
355 | ||
356 | // Returns the number of dimensions in the graph | |
357 | inline std::size_t dimensions() const { | |
358 | return (Dimensions); | |
359 | } | |
360 | ||
361 | // Returns the length of dimension [dimension_index] | |
362 | inline vertices_size_type length(std::size_t dimension) const { | |
363 | return (m_dimension_lengths[dimension]); | |
364 | } | |
365 | ||
366 | // Returns a value indicating if dimension [dimension_index] wraps | |
367 | inline bool wrapped(std::size_t dimension) const { | |
368 | return (m_wrap_dimension[dimension]); | |
369 | } | |
370 | ||
371 | // Gets the vertex that is [distance] units ahead of [vertex] in | |
372 | // dimension [dimension_index]. | |
373 | vertex_descriptor next | |
374 | (vertex_descriptor vertex, | |
375 | std::size_t dimension_index, | |
376 | vertices_size_type distance = 1) const { | |
377 | ||
378 | vertices_size_type new_position = | |
379 | vertex[dimension_index] + distance; | |
380 | ||
381 | if (wrapped(dimension_index)) { | |
382 | new_position %= length(dimension_index); | |
383 | } | |
384 | else { | |
385 | // Stop at the end of this dimension if necessary. | |
386 | new_position = | |
387 | (std::min)(new_position, | |
388 | vertices_size_type(length(dimension_index) - 1)); | |
389 | } | |
390 | ||
391 | vertex[dimension_index] = new_position; | |
392 | ||
393 | return (vertex); | |
394 | } | |
395 | ||
396 | // Gets the vertex that is [distance] units behind [vertex] in | |
397 | // dimension [dimension_index]. | |
398 | vertex_descriptor previous | |
399 | (vertex_descriptor vertex, | |
400 | std::size_t dimension_index, | |
401 | vertices_size_type distance = 1) const { | |
402 | ||
403 | // We're assuming that vertices_size_type is unsigned, so we | |
404 | // need to be careful about the math. | |
405 | vertex[dimension_index] = | |
406 | (distance > vertex[dimension_index]) ? | |
407 | (wrapped(dimension_index) ? | |
408 | (length(dimension_index) - (distance % length(dimension_index))) : 0) : | |
409 | vertex[dimension_index] - distance; | |
410 | ||
411 | return (vertex); | |
412 | } | |
413 | ||
414 | protected: | |
415 | ||
416 | // Returns the number of vertices in the graph | |
417 | inline vertices_size_type num_vertices() const { | |
418 | return (m_num_vertices); | |
419 | } | |
420 | ||
421 | // Returns the number of edges in the graph | |
422 | inline edges_size_type num_edges() const { | |
423 | return (m_num_edges); | |
424 | } | |
425 | ||
426 | // Returns the number of edges in dimension [dimension_index] | |
427 | inline edges_size_type num_edges | |
428 | (std::size_t dimension_index) const { | |
429 | return (m_edge_count[dimension_index]); | |
430 | } | |
431 | ||
432 | // Returns the index of [vertex] (See also vertex_at) | |
433 | vertices_size_type index_of(vertex_descriptor vertex) const { | |
434 | ||
435 | vertices_size_type vertex_index = 0; | |
436 | vertices_size_type index_multiplier = 1; | |
437 | ||
438 | for (std::size_t dimension_index = 0; | |
439 | dimension_index < Dimensions; | |
440 | ++dimension_index) { | |
441 | ||
442 | vertex_index += (vertex[dimension_index] * index_multiplier); | |
443 | index_multiplier *= length(dimension_index); | |
444 | } | |
445 | ||
446 | return (vertex_index); | |
447 | } | |
448 | ||
449 | // Returns the vertex whose index is [vertex_index] (See also | |
450 | // index_of(vertex_descriptor)) | |
451 | vertex_descriptor vertex_at | |
452 | (vertices_size_type vertex_index) const { | |
453 | ||
454 | boost::array<vertices_size_type, Dimensions> vertex; | |
455 | vertices_size_type index_divider = 1; | |
456 | ||
457 | for (std::size_t dimension_index = 0; | |
458 | dimension_index < Dimensions; | |
459 | ++dimension_index) { | |
460 | ||
461 | vertex[dimension_index] = (vertex_index / index_divider) % | |
462 | length(dimension_index); | |
463 | ||
464 | index_divider *= length(dimension_index); | |
465 | } | |
466 | ||
467 | return (vertex); | |
468 | } | |
469 | ||
470 | // Returns the edge whose index is [edge_index] (See also | |
471 | // index_of(edge_descriptor)). NOTE: The index mapping is | |
472 | // dependent upon dimension wrapping. | |
473 | edge_descriptor edge_at(edges_size_type edge_index) const { | |
474 | ||
475 | // Edge indices are sorted into bins by dimension | |
476 | std::size_t dimension_index = 0; | |
477 | edges_size_type dimension_edges = num_edges(0); | |
478 | ||
479 | while (edge_index >= dimension_edges) { | |
480 | edge_index -= dimension_edges; | |
481 | ++dimension_index; | |
482 | dimension_edges = num_edges(dimension_index); | |
483 | } | |
484 | ||
485 | vertex_descriptor vertex_source, vertex_target; | |
486 | bool is_forward = ((edge_index / (num_edges(dimension_index) / 2)) == 0); | |
487 | ||
488 | if (wrapped(dimension_index)) { | |
489 | vertex_source = vertex_at(edge_index % num_vertices()); | |
490 | vertex_target = is_forward ? | |
491 | next(vertex_source, dimension_index) : | |
492 | previous(vertex_source, dimension_index); | |
493 | } | |
494 | else { | |
495 | ||
496 | // Dimensions can wrap arbitrarily, so an index needs to be | |
497 | // computed in a more complex manner. This is done by | |
498 | // grouping the edges for each dimension together into "bins" | |
499 | // and considering [edge_index] as an offset into the bin. | |
500 | // Each bin consists of two parts: the "forward" looking edges | |
501 | // and the "backward" looking edges for the dimension. | |
502 | ||
503 | edges_size_type vertex_offset = edge_index % num_edges(dimension_index); | |
504 | ||
505 | // Consider vertex_offset an index into the graph's vertex | |
506 | // space but with the dimension [dimension_index] reduced in | |
507 | // size by one. | |
508 | vertices_size_type index_divider = 1; | |
509 | ||
510 | for (std::size_t dimension_index_iter = 0; | |
511 | dimension_index_iter < Dimensions; | |
512 | ++dimension_index_iter) { | |
513 | ||
514 | std::size_t dimension_length = (dimension_index_iter == dimension_index) ? | |
515 | length(dimension_index_iter) - 1 : | |
516 | length(dimension_index_iter); | |
517 | ||
518 | vertex_source[dimension_index_iter] = (vertex_offset / index_divider) % | |
519 | dimension_length; | |
520 | ||
521 | index_divider *= dimension_length; | |
522 | } | |
523 | ||
524 | if (is_forward) { | |
525 | vertex_target = next(vertex_source, dimension_index); | |
526 | } | |
527 | else { | |
528 | // Shift forward one more unit in the dimension for backward | |
529 | // edges since the algorithm above will leave us one behind. | |
530 | vertex_target = vertex_source; | |
531 | ++vertex_source[dimension_index]; | |
532 | } | |
533 | ||
534 | } // if (wrapped(dimension_index)) | |
535 | ||
536 | return (std::make_pair(vertex_source, vertex_target)); | |
537 | } | |
538 | ||
539 | // Returns the index for [edge] (See also edge_at) | |
540 | edges_size_type index_of(edge_descriptor edge) const { | |
541 | vertex_descriptor source_vertex = source(edge, *this); | |
542 | vertex_descriptor target_vertex = target(edge, *this); | |
543 | ||
544 | BOOST_ASSERT (source_vertex != target_vertex); | |
545 | ||
546 | // Determine the dimension where the source and target vertices | |
547 | // differ (should only be one if this is a valid edge). | |
548 | std::size_t different_dimension_index = 0; | |
549 | ||
550 | while (source_vertex[different_dimension_index] == | |
551 | target_vertex[different_dimension_index]) { | |
552 | ||
553 | ++different_dimension_index; | |
554 | } | |
555 | ||
556 | edges_size_type edge_index = 0; | |
557 | ||
558 | // Offset the edge index into the appropriate "bin" (see edge_at | |
559 | // for a more in-depth description). | |
560 | for (std::size_t dimension_index = 0; | |
561 | dimension_index < different_dimension_index; | |
562 | ++dimension_index) { | |
563 | ||
564 | edge_index += num_edges(dimension_index); | |
565 | } | |
566 | ||
567 | // Get the position of both vertices in the differing dimension. | |
568 | vertices_size_type source_position = source_vertex[different_dimension_index]; | |
569 | vertices_size_type target_position = target_vertex[different_dimension_index]; | |
570 | ||
571 | // Determine if edge is forward or backward | |
572 | bool is_forward = true; | |
573 | ||
574 | if (wrapped(different_dimension_index)) { | |
575 | ||
576 | // If the dimension is wrapped, an edge is going backward if | |
577 | // either A: its target precedes the source in the differing | |
578 | // dimension and the vertices are adjacent or B: its source | |
579 | // precedes the target and they're not adjacent. | |
580 | if (((target_position < source_position) && | |
581 | ((source_position - target_position) == 1)) || | |
582 | ((source_position < target_position) && | |
583 | ((target_position - source_position) > 1))) { | |
584 | ||
585 | is_forward = false; | |
586 | } | |
587 | } | |
588 | else if (target_position < source_position) { | |
589 | is_forward = false; | |
590 | } | |
591 | ||
592 | // "Backward" edges are in the second half of the bin. | |
593 | if (!is_forward) { | |
594 | edge_index += (num_edges(different_dimension_index) / 2); | |
595 | } | |
596 | ||
597 | // Finally, apply the vertex offset | |
598 | if (wrapped(different_dimension_index)) { | |
599 | edge_index += index_of(source_vertex); | |
600 | } | |
601 | else { | |
602 | vertices_size_type index_multiplier = 1; | |
603 | ||
604 | if (!is_forward) { | |
605 | --source_vertex[different_dimension_index]; | |
606 | } | |
607 | ||
608 | for (std::size_t dimension_index = 0; | |
609 | dimension_index < Dimensions; | |
610 | ++dimension_index) { | |
611 | ||
612 | edge_index += (source_vertex[dimension_index] * index_multiplier); | |
613 | index_multiplier *= (dimension_index == different_dimension_index) ? | |
614 | length(dimension_index) - 1 : | |
615 | length(dimension_index); | |
616 | } | |
617 | } | |
618 | ||
619 | return (edge_index); | |
620 | } | |
621 | ||
622 | // Returns the number of out-edges for [vertex] | |
623 | degree_size_type out_degree(vertex_descriptor vertex) const { | |
624 | ||
625 | degree_size_type out_edge_count = 0; | |
626 | ||
627 | for (std::size_t dimension_index = 0; | |
628 | dimension_index < Dimensions; | |
629 | ++dimension_index) { | |
630 | ||
631 | // If the vertex is on the edge of this dimension, then its | |
632 | // number of out edges is dependent upon whether the dimension | |
633 | // wraps or not. | |
634 | if ((vertex[dimension_index] == 0) || | |
635 | (vertex[dimension_index] == (length(dimension_index) - 1))) { | |
636 | out_edge_count += (wrapped(dimension_index) ? 2 : 1); | |
637 | } | |
638 | else { | |
639 | // Next and previous edges, regardless or wrapping | |
640 | out_edge_count += 2; | |
641 | } | |
642 | } | |
643 | ||
644 | return (out_edge_count); | |
645 | } | |
646 | ||
647 | // Returns an out-edge for [vertex] by index. Indices are in the | |
648 | // range [0, out_degree(vertex)). | |
649 | edge_descriptor out_edge_at | |
650 | (vertex_descriptor vertex, | |
651 | degree_size_type out_edge_index) const { | |
652 | ||
653 | edges_size_type edges_left = out_edge_index + 1; | |
654 | std::size_t dimension_index = 0; | |
655 | bool is_forward = false; | |
656 | ||
657 | // Walks the out edges of [vertex] and accommodates for dimension | |
658 | // wrapping. | |
659 | while (edges_left > 0) { | |
660 | ||
661 | if (!wrapped(dimension_index)) { | |
662 | if (!is_forward && (vertex[dimension_index] == 0)) { | |
663 | is_forward = true; | |
664 | continue; | |
665 | } | |
666 | else if (is_forward && | |
667 | (vertex[dimension_index] == (length(dimension_index) - 1))) { | |
668 | is_forward = false; | |
669 | ++dimension_index; | |
670 | continue; | |
671 | } | |
672 | } | |
673 | ||
674 | --edges_left; | |
675 | ||
676 | if (edges_left > 0) { | |
677 | is_forward = !is_forward; | |
678 | ||
679 | if (!is_forward) { | |
680 | ++dimension_index; | |
681 | } | |
682 | } | |
683 | } | |
684 | ||
685 | return (std::make_pair(vertex, is_forward ? | |
686 | next(vertex, dimension_index) : | |
687 | previous(vertex, dimension_index))); | |
688 | } | |
689 | ||
690 | // Returns the number of in-edges for [vertex] | |
691 | inline degree_size_type in_degree(vertex_descriptor vertex) const { | |
692 | return (out_degree(vertex)); | |
693 | } | |
694 | ||
695 | // Returns an in-edge for [vertex] by index. Indices are in the | |
696 | // range [0, in_degree(vertex)). | |
697 | edge_descriptor in_edge_at | |
698 | (vertex_descriptor vertex, | |
699 | edges_size_type in_edge_index) const { | |
700 | ||
701 | edge_descriptor out_edge = out_edge_at(vertex, in_edge_index); | |
702 | return (std::make_pair(target(out_edge, *this), source(out_edge, *this))); | |
703 | ||
704 | } | |
705 | ||
706 | // Pre-computes the number of vertices and edges | |
707 | void precalculate() { | |
708 | m_num_vertices = | |
709 | std::accumulate(m_dimension_lengths.begin(), | |
710 | m_dimension_lengths.end(), | |
711 | vertices_size_type(1), | |
712 | std::multiplies<vertices_size_type>()); | |
713 | ||
714 | // Calculate number of edges in each dimension | |
715 | m_num_edges = 0; | |
716 | ||
717 | for (std::size_t dimension_index = 0; | |
718 | dimension_index < Dimensions; | |
719 | ++dimension_index) { | |
720 | ||
721 | if (wrapped(dimension_index)) { | |
722 | m_edge_count[dimension_index] = num_vertices() * 2; | |
723 | } | |
724 | else { | |
725 | m_edge_count[dimension_index] = | |
726 | (num_vertices() - (num_vertices() / length(dimension_index))) * 2; | |
727 | } | |
728 | ||
729 | m_num_edges += num_edges(dimension_index); | |
730 | } | |
731 | } | |
732 | ||
733 | const vertex_descriptor m_dimension_lengths; | |
734 | WrapDimensionArray m_wrap_dimension; | |
735 | vertices_size_type m_num_vertices; | |
736 | ||
737 | boost::array<edges_size_type, Dimensions> m_edge_count; | |
738 | edges_size_type m_num_edges; | |
739 | ||
740 | public: | |
741 | ||
742 | //================ | |
743 | // VertexListGraph | |
744 | //================ | |
745 | ||
746 | friend inline std::pair<typename type::vertex_iterator, | |
747 | typename type::vertex_iterator> | |
748 | vertices(const type& graph) { | |
749 | typedef typename type::vertex_iterator vertex_iterator; | |
750 | typedef typename type::vertex_function vertex_function; | |
751 | typedef typename type::vertex_index_iterator vertex_index_iterator; | |
752 | ||
753 | return (std::make_pair | |
754 | (vertex_iterator(vertex_index_iterator(0), | |
755 | vertex_function(&graph)), | |
756 | vertex_iterator(vertex_index_iterator(graph.num_vertices()), | |
757 | vertex_function(&graph)))); | |
758 | } | |
759 | ||
760 | friend inline typename type::vertices_size_type | |
761 | num_vertices(const type& graph) { | |
762 | return (graph.num_vertices()); | |
763 | } | |
764 | ||
765 | friend inline typename type::vertex_descriptor | |
766 | vertex(typename type::vertices_size_type vertex_index, | |
767 | const type& graph) { | |
768 | ||
769 | return (graph.vertex_at(vertex_index)); | |
770 | } | |
771 | ||
772 | //=============== | |
773 | // IncidenceGraph | |
774 | //=============== | |
775 | ||
776 | friend inline std::pair<typename type::out_edge_iterator, | |
777 | typename type::out_edge_iterator> | |
778 | out_edges(typename type::vertex_descriptor vertex, | |
779 | const type& graph) { | |
780 | typedef typename type::degree_iterator degree_iterator; | |
781 | typedef typename type::out_edge_function out_edge_function; | |
782 | typedef typename type::out_edge_iterator out_edge_iterator; | |
783 | ||
784 | return (std::make_pair | |
785 | (out_edge_iterator(degree_iterator(0), | |
786 | out_edge_function(vertex, &graph)), | |
787 | out_edge_iterator(degree_iterator(graph.out_degree(vertex)), | |
788 | out_edge_function(vertex, &graph)))); | |
789 | } | |
790 | ||
791 | friend inline typename type::degree_size_type | |
792 | out_degree | |
793 | (typename type::vertex_descriptor vertex, | |
794 | const type& graph) { | |
795 | return (graph.out_degree(vertex)); | |
796 | } | |
797 | ||
798 | friend inline typename type::edge_descriptor | |
799 | out_edge_at(typename type::vertex_descriptor vertex, | |
800 | typename type::degree_size_type out_edge_index, | |
801 | const type& graph) { | |
802 | return (graph.out_edge_at(vertex, out_edge_index)); | |
803 | } | |
804 | ||
805 | //=============== | |
806 | // AdjacencyGraph | |
807 | //=============== | |
808 | ||
809 | friend typename std::pair<typename type::adjacency_iterator, | |
810 | typename type::adjacency_iterator> | |
811 | adjacent_vertices (typename type::vertex_descriptor vertex, | |
812 | const type& graph) { | |
813 | typedef typename type::degree_iterator degree_iterator; | |
814 | typedef typename type::adjacent_vertex_function adjacent_vertex_function; | |
815 | typedef typename type::adjacency_iterator adjacency_iterator; | |
816 | ||
817 | return (std::make_pair | |
818 | (adjacency_iterator(degree_iterator(0), | |
819 | adjacent_vertex_function(vertex, &graph)), | |
820 | adjacency_iterator(degree_iterator(graph.out_degree(vertex)), | |
821 | adjacent_vertex_function(vertex, &graph)))); | |
822 | } | |
823 | ||
824 | //============== | |
825 | // EdgeListGraph | |
826 | //============== | |
827 | ||
828 | friend inline typename type::edges_size_type | |
829 | num_edges(const type& graph) { | |
830 | return (graph.num_edges()); | |
831 | } | |
832 | ||
833 | friend inline typename type::edge_descriptor | |
834 | edge_at(typename type::edges_size_type edge_index, | |
835 | const type& graph) { | |
836 | return (graph.edge_at(edge_index)); | |
837 | } | |
838 | ||
839 | friend inline std::pair<typename type::edge_iterator, | |
840 | typename type::edge_iterator> | |
841 | edges(const type& graph) { | |
842 | typedef typename type::edge_index_iterator edge_index_iterator; | |
843 | typedef typename type::edge_function edge_function; | |
844 | typedef typename type::edge_iterator edge_iterator; | |
845 | ||
846 | return (std::make_pair | |
847 | (edge_iterator(edge_index_iterator(0), | |
848 | edge_function(&graph)), | |
849 | edge_iterator(edge_index_iterator(graph.num_edges()), | |
850 | edge_function(&graph)))); | |
851 | } | |
852 | ||
853 | //=================== | |
854 | // BiDirectionalGraph | |
855 | //=================== | |
856 | ||
857 | friend inline std::pair<typename type::in_edge_iterator, | |
858 | typename type::in_edge_iterator> | |
859 | in_edges(typename type::vertex_descriptor vertex, | |
860 | const type& graph) { | |
861 | typedef typename type::in_edge_function in_edge_function; | |
862 | typedef typename type::degree_iterator degree_iterator; | |
863 | typedef typename type::in_edge_iterator in_edge_iterator; | |
864 | ||
865 | return (std::make_pair | |
866 | (in_edge_iterator(degree_iterator(0), | |
867 | in_edge_function(vertex, &graph)), | |
868 | in_edge_iterator(degree_iterator(graph.in_degree(vertex)), | |
869 | in_edge_function(vertex, &graph)))); | |
870 | } | |
871 | ||
872 | friend inline typename type::degree_size_type | |
873 | in_degree (typename type::vertex_descriptor vertex, | |
874 | const type& graph) { | |
875 | return (graph.in_degree(vertex)); | |
876 | } | |
877 | ||
878 | friend inline typename type::degree_size_type | |
879 | degree (typename type::vertex_descriptor vertex, | |
880 | const type& graph) { | |
881 | return (graph.out_degree(vertex) * 2); | |
882 | } | |
883 | ||
884 | friend inline typename type::edge_descriptor | |
885 | in_edge_at(typename type::vertex_descriptor vertex, | |
886 | typename type::degree_size_type in_edge_index, | |
887 | const type& graph) { | |
888 | return (graph.in_edge_at(vertex, in_edge_index)); | |
889 | } | |
890 | ||
891 | ||
892 | //================== | |
893 | // Adjacency Matrix | |
894 | //================== | |
895 | ||
896 | friend std::pair<typename type::edge_descriptor, bool> | |
897 | edge (typename type::vertex_descriptor source_vertex, | |
898 | typename type::vertex_descriptor destination_vertex, | |
899 | const type& graph) { | |
900 | ||
901 | std::pair<typename type::edge_descriptor, bool> edge_exists = | |
902 | std::make_pair(std::make_pair(source_vertex, destination_vertex), false); | |
903 | ||
904 | for (std::size_t dimension_index = 0; | |
905 | dimension_index < Dimensions; | |
906 | ++dimension_index) { | |
907 | ||
908 | typename type::vertices_size_type dim_difference = 0; | |
909 | typename type::vertices_size_type | |
910 | source_dim = source_vertex[dimension_index], | |
911 | dest_dim = destination_vertex[dimension_index]; | |
912 | ||
913 | dim_difference = (source_dim > dest_dim) ? | |
914 | (source_dim - dest_dim) : (dest_dim - source_dim); | |
915 | ||
916 | if (dim_difference > 0) { | |
917 | ||
918 | // If we've already found a valid edge, this would mean that | |
919 | // the vertices are really diagonal across dimensions and | |
920 | // therefore not connected. | |
921 | if (edge_exists.second) { | |
922 | edge_exists.second = false; | |
923 | break; | |
924 | } | |
925 | ||
926 | // If the difference is one, the vertices are right next to | |
927 | // each other and the edge is valid. The edge is still | |
928 | // valid, though, if the dimension wraps and the vertices | |
929 | // are on opposite ends. | |
930 | if ((dim_difference == 1) || | |
931 | (graph.wrapped(dimension_index) && | |
932 | (((source_dim == 0) && (dest_dim == (graph.length(dimension_index) - 1))) || | |
933 | ((dest_dim == 0) && (source_dim == (graph.length(dimension_index) - 1)))))) { | |
934 | ||
935 | edge_exists.second = true; | |
936 | // Stay in the loop to check for diagonal vertices. | |
937 | } | |
938 | else { | |
939 | ||
940 | // Stop checking - the vertices are too far apart. | |
941 | edge_exists.second = false; | |
942 | break; | |
943 | } | |
944 | } | |
945 | ||
946 | } // for dimension_index | |
947 | ||
948 | return (edge_exists); | |
949 | } | |
950 | ||
951 | ||
952 | //============================= | |
953 | // Index Property Map Functions | |
954 | //============================= | |
955 | ||
956 | friend inline typename type::vertices_size_type | |
957 | get(vertex_index_t, | |
958 | const type& graph, | |
959 | typename type::vertex_descriptor vertex) { | |
960 | return (graph.index_of(vertex)); | |
961 | } | |
962 | ||
963 | friend inline typename type::edges_size_type | |
964 | get(edge_index_t, | |
965 | const type& graph, | |
966 | typename type::edge_descriptor edge) { | |
967 | return (graph.index_of(edge)); | |
968 | } | |
969 | ||
970 | friend inline grid_graph_index_map< | |
971 | type, | |
972 | typename type::vertex_descriptor, | |
973 | typename type::vertices_size_type> | |
974 | get(vertex_index_t, const type& graph) { | |
975 | return (grid_graph_index_map< | |
976 | type, | |
977 | typename type::vertex_descriptor, | |
978 | typename type::vertices_size_type>(graph)); | |
979 | } | |
980 | ||
981 | friend inline grid_graph_index_map< | |
982 | type, | |
983 | typename type::edge_descriptor, | |
984 | typename type::edges_size_type> | |
985 | get(edge_index_t, const type& graph) { | |
986 | return (grid_graph_index_map< | |
987 | type, | |
988 | typename type::edge_descriptor, | |
989 | typename type::edges_size_type>(graph)); | |
990 | } | |
991 | ||
992 | friend inline grid_graph_reverse_edge_map< | |
993 | typename type::edge_descriptor> | |
994 | get(edge_reverse_t, const type& graph) { | |
995 | return (grid_graph_reverse_edge_map< | |
996 | typename type::edge_descriptor>()); | |
997 | } | |
998 | ||
999 | template<typename Graph, | |
1000 | typename Descriptor, | |
1001 | typename Index> | |
1002 | friend struct grid_graph_index_map; | |
1003 | ||
1004 | template<typename Descriptor> | |
1005 | friend struct grid_graph_reverse_edge_map; | |
1006 | ||
1007 | }; // grid_graph | |
1008 | ||
1009 | } // namespace boost | |
1010 | ||
1011 | #undef BOOST_GRID_GRAPH_TYPE | |
1012 | #undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS | |
1013 | #undef BOOST_GRID_GRAPH_TRAITS_T | |
1014 | ||
1015 | #endif // BOOST_GRAPH_GRID_GRAPH_HPP |