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
36namespace 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

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