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: dimension_index)) { |
382 | new_position %= length(dimension: 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: 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: dimension_index) ? |
408 | (length(dimension: dimension_index) - (distance % length(dimension: 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: 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: dimension_index); |
463 | |
464 | index_divider *= length(dimension: 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: dimension_index)) { |
489 | vertex_source = vertex_at(vertex_index: edge_index % num_vertices()); |
490 | vertex_target = is_forward ? |
491 | next(vertex: vertex_source, dimension_index) : |
492 | previous(vertex: 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: dimension_index_iter) - 1 : |
516 | length(dimension: 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: 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(dimension: 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(dimension: 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: dimension_index) - 1 : |
615 | length(dimension: 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: dimension_index) - 1))) { |
636 | out_edge_count += (wrapped(dimension: 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: 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: 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, out_edge_index: 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: 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: 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 |
1016 | |