//======================================================================= | |
// Copyright 2009 Trustees of Indiana University. | |
// Authors: Michael Hansen, Andrew Lumsdaine | |
// | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
//======================================================================= | |
#ifndef BOOST_GRAPH_GRID_GRAPH_HPP | |
#define BOOST_GRAPH_GRID_GRAPH_HPP | |
#include <cmath> | |
#include <functional> | |
#include <numeric> | |
#include <boost/array.hpp> | |
#include <boost/bind.hpp> | |
#include <boost/limits.hpp> | |
#include <boost/make_shared.hpp> | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/graph/properties.hpp> | |
#include <boost/iterator/counting_iterator.hpp> | |
#include <boost/iterator/transform_iterator.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#define BOOST_GRID_GRAPH_TEMPLATE_PARAMS \ | |
std::size_t DimensionsT, typename VertexIndexT, \ | |
typename EdgeIndexT | |
#define BOOST_GRID_GRAPH_TYPE \ | |
grid_graph<DimensionsT, VertexIndexT, EdgeIndexT> | |
#define BOOST_GRID_GRAPH_TYPE_MEM typename BOOST_GRID_GRAPH_TYPE:: | |
#define BOOST_GRID_GRAPH_TYPE_TD(mem) \ | |
typedef typename BOOST_GRID_GRAPH_TYPE::mem mem | |
#define BOOST_GRID_GRAPH_TRAITS_T \ | |
typename graph_traits<BOOST_GRID_GRAPH_TYPE > | |
namespace boost { | |
// Class prototype for grid_graph | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
class grid_graph; | |
//=================== | |
// Index Property Map | |
//=================== | |
template <typename Graph, | |
typename Descriptor, | |
typename Index> | |
struct grid_graph_index_map { | |
public: | |
typedef Index value_type; | |
typedef Index reference_type; | |
typedef reference_type reference; | |
typedef Descriptor key_type; | |
typedef readable_property_map_tag category; | |
grid_graph_index_map() { } | |
grid_graph_index_map(const Graph& graph) : | |
m_graph(make_shared<Graph>(graph)) { } | |
value_type operator[](key_type key) const { | |
return (m_graph->index_of(key)); | |
} | |
protected: | |
shared_ptr<Graph> m_graph; | |
}; | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
struct property_map<BOOST_GRID_GRAPH_TYPE, vertex_index_t> { | |
typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TRAITS_T::vertex_descriptor, | |
BOOST_GRID_GRAPH_TRAITS_T::vertices_size_type> type; | |
typedef type const_type; | |
}; | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
struct property_map<BOOST_GRID_GRAPH_TYPE, edge_index_t> { | |
typedef grid_graph_index_map<BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor, | |
BOOST_GRID_GRAPH_TRAITS_T::edges_size_type> type; | |
typedef type const_type; | |
}; | |
//================= | |
// Function Objects | |
//================= | |
namespace detail { | |
// vertex_at | |
template <typename Graph> | |
struct grid_graph_vertex_at { | |
typedef typename graph_traits<Graph>::vertex_descriptor result_type; | |
grid_graph_vertex_at() : m_graph(0) {} | |
grid_graph_vertex_at(const Graph* graph) : | |
m_graph(graph) { } | |
result_type | |
operator() | |
(typename graph_traits<Graph>::vertices_size_type vertex_index) const { | |
return (vertex(vertex_index, *m_graph)); | |
} | |
private: | |
const Graph* m_graph; | |
}; | |
// out_edge_at | |
template <typename Graph> | |
struct grid_graph_out_edge_at { | |
private: | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
public: | |
typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
grid_graph_out_edge_at() : m_vertex(), m_graph(0) {} | |
grid_graph_out_edge_at(vertex_descriptor source_vertex, | |
const Graph* graph) : | |
m_vertex(source_vertex), | |
m_graph(graph) { } | |
result_type | |
operator() | |
(typename graph_traits<Graph>::degree_size_type out_edge_index) const { | |
return (out_edge_at(m_vertex, out_edge_index, *m_graph)); | |
} | |
private: | |
vertex_descriptor m_vertex; | |
const Graph* m_graph; | |
}; | |
// in_edge_at | |
template <typename Graph> | |
struct grid_graph_in_edge_at { | |
private: | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
public: | |
typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
grid_graph_in_edge_at() : m_vertex(), m_graph(0) {} | |
grid_graph_in_edge_at(vertex_descriptor target_vertex, | |
const Graph* graph) : | |
m_vertex(target_vertex), | |
m_graph(graph) { } | |
result_type | |
operator() | |
(typename graph_traits<Graph>::degree_size_type in_edge_index) const { | |
return (in_edge_at(m_vertex, in_edge_index, *m_graph)); | |
} | |
private: | |
vertex_descriptor m_vertex; | |
const Graph* m_graph; | |
}; | |
// edge_at | |
template <typename Graph> | |
struct grid_graph_edge_at { | |
typedef typename graph_traits<Graph>::edge_descriptor result_type; | |
grid_graph_edge_at() : m_graph(0) {} | |
grid_graph_edge_at(const Graph* graph) : | |
m_graph(graph) { } | |
result_type | |
operator() | |
(typename graph_traits<Graph>::edges_size_type edge_index) const { | |
return (edge_at(edge_index, *m_graph)); | |
} | |
private: | |
const Graph* m_graph; | |
}; | |
// adjacent_vertex_at | |
template <typename Graph> | |
struct grid_graph_adjacent_vertex_at { | |
public: | |
typedef typename graph_traits<Graph>::vertex_descriptor result_type; | |
grid_graph_adjacent_vertex_at(result_type source_vertex, | |
const Graph* graph) : | |
m_vertex(source_vertex), | |
m_graph(graph) { } | |
result_type | |
operator() | |
(typename graph_traits<Graph>::degree_size_type adjacent_index) const { | |
return (target(out_edge_at(m_vertex, adjacent_index, *m_graph), *m_graph)); | |
} | |
private: | |
result_type m_vertex; | |
const Graph* m_graph; | |
}; | |
} // namespace detail | |
//=========== | |
// Grid Graph | |
//=========== | |
template <std::size_t Dimensions, | |
typename VertexIndex = std::size_t, | |
typename EdgeIndex = VertexIndex> | |
class grid_graph { | |
private: | |
typedef boost::array<bool, Dimensions> WrapDimensionArray; | |
grid_graph() { }; | |
public: | |
typedef grid_graph<Dimensions, VertexIndex, EdgeIndex> type; | |
// sizes | |
typedef VertexIndex vertices_size_type; | |
typedef EdgeIndex edges_size_type; | |
typedef EdgeIndex degree_size_type; | |
// descriptors | |
typedef boost::array<VertexIndex, Dimensions> vertex_descriptor; | |
typedef std::pair<vertex_descriptor, vertex_descriptor> edge_descriptor; | |
// vertex_iterator | |
typedef counting_iterator<vertices_size_type> vertex_index_iterator; | |
typedef detail::grid_graph_vertex_at<type> vertex_function; | |
typedef transform_iterator<vertex_function, vertex_index_iterator> vertex_iterator; | |
// edge_iterator | |
typedef counting_iterator<edges_size_type> edge_index_iterator; | |
typedef detail::grid_graph_edge_at<type> edge_function; | |
typedef transform_iterator<edge_function, edge_index_iterator> edge_iterator; | |
// out_edge_iterator | |
typedef counting_iterator<degree_size_type> degree_iterator; | |
typedef detail::grid_graph_out_edge_at<type> out_edge_function; | |
typedef transform_iterator<out_edge_function, degree_iterator> out_edge_iterator; | |
// in_edge_iterator | |
typedef detail::grid_graph_in_edge_at<type> in_edge_function; | |
typedef transform_iterator<in_edge_function, degree_iterator> in_edge_iterator; | |
// adjacency_iterator | |
typedef detail::grid_graph_adjacent_vertex_at<type> adjacent_vertex_function; | |
typedef transform_iterator<adjacent_vertex_function, degree_iterator> adjacency_iterator; | |
// categories | |
typedef undirected_tag directed_category; | |
typedef disallow_parallel_edge_tag edge_parallel_category; | |
struct traversal_category : virtual public incidence_graph_tag, | |
virtual public adjacency_graph_tag, | |
virtual public vertex_list_graph_tag, | |
virtual public edge_list_graph_tag, | |
virtual public bidirectional_graph_tag, | |
virtual public adjacency_matrix_tag { }; | |
static inline vertex_descriptor null_vertex() | |
{ | |
vertex_descriptor maxed_out_vertex; | |
std::fill(maxed_out_vertex.begin(), maxed_out_vertex.end(), | |
(std::numeric_limits<vertices_size_type>::max)()); | |
return (maxed_out_vertex); | |
} | |
// Constructor that defaults to no wrapping for all dimensions. | |
grid_graph(vertex_descriptor dimension_lengths) : | |
m_dimension_lengths(dimension_lengths) { | |
std::fill(m_wrap_dimension.begin(), | |
m_wrap_dimension.end(), false); | |
precalculate(); | |
} | |
// Constructor that allows for wrapping to be specified for all | |
// dimensions at once. | |
grid_graph(vertex_descriptor dimension_lengths, | |
bool wrap_all_dimensions) : | |
m_dimension_lengths(dimension_lengths) { | |
std::fill(m_wrap_dimension.begin(), | |
m_wrap_dimension.end(), | |
wrap_all_dimensions); | |
precalculate(); | |
} | |
// Constructor that allows for individual dimension wrapping to be | |
// specified. | |
grid_graph(vertex_descriptor dimension_lengths, | |
WrapDimensionArray wrap_dimension) : | |
m_dimension_lengths(dimension_lengths), | |
m_wrap_dimension(wrap_dimension) { | |
precalculate(); | |
} | |
// Returns the number of dimensions in the graph | |
inline std::size_t dimensions() const { | |
return (Dimensions); | |
} | |
// Returns the length of dimension [dimension_index] | |
inline vertices_size_type length(std::size_t dimension) const { | |
return (m_dimension_lengths[dimension]); | |
} | |
// Returns a value indicating if dimension [dimension_index] wraps | |
inline bool wrapped(std::size_t dimension) const { | |
return (m_wrap_dimension[dimension]); | |
} | |
// Gets the vertex that is [distance] units ahead of [vertex] in | |
// dimension [dimension_index]. | |
vertex_descriptor next | |
(vertex_descriptor vertex, | |
std::size_t dimension_index, | |
vertices_size_type distance = 1) const { | |
vertices_size_type new_position = | |
vertex[dimension_index] + distance; | |
if (wrapped(dimension_index)) { | |
new_position %= length(dimension_index); | |
} | |
else { | |
// Stop at the end of this dimension if necessary. | |
new_position = | |
(std::min)(new_position, | |
length(dimension_index) - 1); | |
} | |
vertex[dimension_index] = new_position; | |
return (vertex); | |
} | |
// Gets the vertex that is [distance] units behind [vertex] in | |
// dimension [dimension_index]. | |
vertex_descriptor previous | |
(vertex_descriptor vertex, | |
std::size_t dimension_index, | |
vertices_size_type distance = 1) const { | |
// We're assuming that vertices_size_type is unsigned, so we | |
// need to be careful about the math. | |
vertex[dimension_index] = | |
(distance > vertex[dimension_index]) ? | |
(wrapped(dimension_index) ? | |
(length(dimension_index) - (distance % length(dimension_index))) : 0) : | |
vertex[dimension_index] - distance; | |
return (vertex); | |
} | |
protected: | |
// Returns the number of vertices in the graph | |
inline vertices_size_type num_vertices() const { | |
return (m_num_vertices); | |
} | |
// Returns the number of edges in the graph | |
inline edges_size_type num_edges() const { | |
return (m_num_edges); | |
} | |
// Returns the number of edges in dimension [dimension_index] | |
inline edges_size_type num_edges | |
(std::size_t dimension_index) const { | |
return (m_edge_count[dimension_index]); | |
} | |
// Returns the index of [vertex] (See also vertex_at) | |
vertices_size_type index_of(vertex_descriptor vertex) const { | |
vertices_size_type vertex_index = 0; | |
vertices_size_type index_multiplier = 1; | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
vertex_index += (vertex[dimension_index] * index_multiplier); | |
index_multiplier *= length(dimension_index); | |
} | |
return (vertex_index); | |
} | |
// Returns the vertex whose index is [vertex_index] (See also | |
// index_of(vertex_descriptor)) | |
vertex_descriptor vertex_at | |
(vertices_size_type vertex_index) const { | |
array<vertices_size_type, Dimensions> vertex; | |
vertices_size_type index_divider = 1; | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
vertex[dimension_index] = (vertex_index / index_divider) % | |
length(dimension_index); | |
index_divider *= length(dimension_index); | |
} | |
return (vertex); | |
} | |
// Returns the edge whose index is [edge_index] (See also | |
// index_of(edge_descriptor)). NOTE: The index mapping is | |
// dependent upon dimension wrapping. | |
edge_descriptor edge_at(edges_size_type edge_index) const { | |
// Edge indices are sorted into bins by dimension | |
std::size_t dimension_index = 0; | |
edges_size_type dimension_edges = num_edges(0); | |
while (edge_index >= dimension_edges) { | |
edge_index -= dimension_edges; | |
++dimension_index; | |
dimension_edges = num_edges(dimension_index); | |
} | |
vertex_descriptor vertex_source, vertex_target; | |
bool is_forward = ((edge_index / (num_edges(dimension_index) / 2)) == 0); | |
if (wrapped(dimension_index)) { | |
vertex_source = vertex_at(edge_index % num_vertices()); | |
vertex_target = is_forward ? | |
next(vertex_source, dimension_index) : | |
previous(vertex_source, dimension_index); | |
} | |
else { | |
// Dimensions can wrap arbitrarily, so an index needs to be | |
// computed in a more complex manner. This is done by | |
// grouping the edges for each dimension together into "bins" | |
// and considering [edge_index] as an offset into the bin. | |
// Each bin consists of two parts: the "forward" looking edges | |
// and the "backward" looking edges for the dimension. | |
edges_size_type vertex_offset = edge_index % num_edges(dimension_index); | |
// Consider vertex_offset an index into the graph's vertex | |
// space but with the dimension [dimension_index] reduced in | |
// size by one. | |
vertices_size_type index_divider = 1; | |
for (std::size_t dimension_index_iter = 0; | |
dimension_index_iter < Dimensions; | |
++dimension_index_iter) { | |
std::size_t dimension_length = (dimension_index_iter == dimension_index) ? | |
length(dimension_index_iter) - 1 : | |
length(dimension_index_iter); | |
vertex_source[dimension_index_iter] = (vertex_offset / index_divider) % | |
dimension_length; | |
index_divider *= dimension_length; | |
} | |
if (is_forward) { | |
vertex_target = next(vertex_source, dimension_index); | |
} | |
else { | |
// Shift forward one more unit in the dimension for backward | |
// edges since the algorithm above will leave us one behind. | |
vertex_target = vertex_source; | |
++vertex_source[dimension_index]; | |
} | |
} // if (wrapped(dimension_index)) | |
return (std::make_pair(vertex_source, vertex_target)); | |
} | |
// Returns the index for [edge] (See also edge_at) | |
edges_size_type index_of(edge_descriptor edge) const { | |
vertex_descriptor source_vertex = source(edge, *this); | |
vertex_descriptor target_vertex = target(edge, *this); | |
// Determine the dimension where the source and target vertices | |
// differ (should only be one if this is a valid edge). | |
std::size_t different_dimension_index = 0; | |
while (source_vertex[different_dimension_index] == | |
target_vertex[different_dimension_index]) { | |
++different_dimension_index; | |
} | |
edges_size_type edge_index = 0; | |
// Offset the edge index into the appropriate "bin" (see edge_at | |
// for a more in-depth description). | |
for (std::size_t dimension_index = 0; | |
dimension_index < different_dimension_index; | |
++dimension_index) { | |
edge_index += num_edges(dimension_index); | |
} | |
// Get the position of both vertices in the differing dimension. | |
vertices_size_type source_position = source_vertex[different_dimension_index]; | |
vertices_size_type target_position = target_vertex[different_dimension_index]; | |
// Determine if edge is forward or backward | |
bool is_forward = true; | |
if (wrapped(different_dimension_index)) { | |
// If the dimension is wrapped, an edge is going backward if | |
// either A: its target precedes the source in the differing | |
// dimension and the vertices are adjacent or B: its source | |
// precedes the target and they're not adjacent. | |
if (((target_position < source_position) && | |
((source_position - target_position) == 1)) || | |
((source_position < target_position) && | |
((target_position - source_position) > 1))) { | |
is_forward = false; | |
} | |
} | |
else if (target_position < source_position) { | |
is_forward = false; | |
} | |
// "Backward" edges are in the second half of the bin. | |
if (!is_forward) { | |
edge_index += (num_edges(different_dimension_index) / 2); | |
} | |
// Finally, apply the vertex offset | |
if (wrapped(different_dimension_index)) { | |
edge_index += index_of(source_vertex); | |
} | |
else { | |
vertices_size_type index_multiplier = 1; | |
if (!is_forward) { | |
--source_vertex[different_dimension_index]; | |
} | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
edge_index += (source_vertex[dimension_index] * index_multiplier); | |
index_multiplier *= (dimension_index == different_dimension_index) ? | |
length(dimension_index) - 1 : | |
length(dimension_index); | |
} | |
} | |
return (edge_index); | |
} | |
// Returns the number of out-edges for [vertex] | |
degree_size_type out_degree(vertex_descriptor vertex) const { | |
degree_size_type out_edge_count = 0; | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
// If the vertex is on the edge of this dimension, then its | |
// number of out edges is dependent upon whether the dimension | |
// wraps or not. | |
if ((vertex[dimension_index] == 0) || | |
(vertex[dimension_index] == (length(dimension_index) - 1))) { | |
out_edge_count += (wrapped(dimension_index) ? 2 : 1); | |
} | |
else { | |
// Next and previous edges, regardless or wrapping | |
out_edge_count += 2; | |
} | |
} | |
return (out_edge_count); | |
} | |
// Returns an out-edge for [vertex] by index. Indices are in the | |
// range [0, out_degree(vertex)). | |
edge_descriptor out_edge_at | |
(vertex_descriptor vertex, | |
degree_size_type out_edge_index) const { | |
edges_size_type edges_left = out_edge_index + 1; | |
std::size_t dimension_index = 0; | |
bool is_forward = false; | |
// Walks the out edges of [vertex] and accommodates for dimension | |
// wrapping. | |
while (edges_left > 0) { | |
if (!wrapped(dimension_index)) { | |
if (!is_forward && (vertex[dimension_index] == 0)) { | |
is_forward = true; | |
continue; | |
} | |
else if (is_forward && | |
(vertex[dimension_index] == (length(dimension_index) - 1))) { | |
is_forward = false; | |
++dimension_index; | |
continue; | |
} | |
} | |
--edges_left; | |
if (edges_left > 0) { | |
is_forward = !is_forward; | |
if (!is_forward) { | |
++dimension_index; | |
} | |
} | |
} | |
return (std::make_pair(vertex, is_forward ? | |
next(vertex, dimension_index) : | |
previous(vertex, dimension_index))); | |
} | |
// Returns the number of in-edges for [vertex] | |
inline degree_size_type in_degree(vertex_descriptor vertex) const { | |
return (out_degree(vertex)); | |
} | |
// Returns an in-edge for [vertex] by index. Indices are in the | |
// range [0, in_degree(vertex)). | |
edge_descriptor in_edge_at | |
(vertex_descriptor vertex, | |
edges_size_type in_edge_index) const { | |
edge_descriptor out_edge = out_edge_at(vertex, in_edge_index); | |
return (std::make_pair(target(out_edge, *this), source(out_edge, *this))); | |
} | |
// Pre-computes the number of vertices and edges | |
void precalculate() { | |
m_num_vertices = | |
std::accumulate(m_dimension_lengths.begin(), | |
m_dimension_lengths.end(), 1, | |
std::multiplies<vertices_size_type>()); | |
// Calculate number of edges in each dimension | |
m_num_edges = 0; | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
if (wrapped(dimension_index)) { | |
m_edge_count[dimension_index] = num_vertices() * 2; | |
} | |
else { | |
m_edge_count[dimension_index] = | |
(num_vertices() - (num_vertices() / length(dimension_index))) * 2; | |
} | |
m_num_edges += num_edges(dimension_index); | |
} | |
} | |
const vertex_descriptor m_dimension_lengths; | |
WrapDimensionArray m_wrap_dimension; | |
vertices_size_type m_num_vertices; | |
boost::array<edges_size_type, Dimensions> m_edge_count; | |
edges_size_type m_num_edges; | |
public: | |
//================ | |
// VertexListGraph | |
//================ | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator, | |
BOOST_GRID_GRAPH_TYPE_MEM vertex_iterator> | |
vertices(const BOOST_GRID_GRAPH_TYPE& graph) { | |
BOOST_GRID_GRAPH_TYPE_TD(vertex_iterator); | |
BOOST_GRID_GRAPH_TYPE_TD(vertex_function); | |
BOOST_GRID_GRAPH_TYPE_TD(vertex_index_iterator); | |
return (std::make_pair | |
(vertex_iterator(vertex_index_iterator(0), | |
vertex_function(&graph)), | |
vertex_iterator(vertex_index_iterator(graph.num_vertices()), | |
vertex_function(&graph)))); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type | |
num_vertices(const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.num_vertices()); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor | |
vertex(BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type vertex_index, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.vertex_at(vertex_index)); | |
} | |
//=============== | |
// IncidenceGraph | |
//=============== | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator, | |
BOOST_GRID_GRAPH_TYPE_MEM out_edge_iterator> | |
out_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); | |
BOOST_GRID_GRAPH_TYPE_TD(out_edge_function); | |
BOOST_GRID_GRAPH_TYPE_TD(out_edge_iterator); | |
return (std::make_pair | |
(out_edge_iterator(degree_iterator(0), | |
out_edge_function(vertex, &graph)), | |
out_edge_iterator(degree_iterator(graph.out_degree(vertex)), | |
out_edge_function(vertex, &graph)))); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type | |
out_degree | |
(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.out_degree(vertex)); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor | |
out_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
BOOST_GRID_GRAPH_TYPE_MEM degree_size_type out_edge_index, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.out_edge_at(vertex, out_edge_index)); | |
} | |
//=============== | |
// AdjacencyGraph | |
//=============== | |
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend typename std::pair<BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator, | |
BOOST_GRID_GRAPH_TYPE_MEM adjacency_iterator> | |
adjacent_vertices (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); | |
BOOST_GRID_GRAPH_TYPE_TD(adjacent_vertex_function); | |
BOOST_GRID_GRAPH_TYPE_TD(adjacency_iterator); | |
return (std::make_pair | |
(adjacency_iterator(degree_iterator(0), | |
adjacent_vertex_function(vertex, &graph)), | |
adjacency_iterator(degree_iterator(graph.out_degree(vertex)), | |
adjacent_vertex_function(vertex, &graph)))); | |
} | |
//============== | |
// EdgeListGraph | |
//============== | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type | |
num_edges(const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.num_edges()); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor | |
edge_at(BOOST_GRID_GRAPH_TYPE_MEM edges_size_type edge_index, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.edge_at(edge_index)); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_iterator, | |
BOOST_GRID_GRAPH_TYPE_MEM edge_iterator> | |
edges(const BOOST_GRID_GRAPH_TYPE& graph) { | |
BOOST_GRID_GRAPH_TYPE_TD(edge_index_iterator); | |
BOOST_GRID_GRAPH_TYPE_TD(edge_function); | |
BOOST_GRID_GRAPH_TYPE_TD(edge_iterator); | |
return (std::make_pair | |
(edge_iterator(edge_index_iterator(0), | |
edge_function(&graph)), | |
edge_iterator(edge_index_iterator(graph.num_edges()), | |
edge_function(&graph)))); | |
} | |
//=================== | |
// BiDirectionalGraph | |
//=================== | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline std::pair<BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator, | |
BOOST_GRID_GRAPH_TYPE_MEM in_edge_iterator> | |
in_edges(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
BOOST_GRID_GRAPH_TYPE_TD(in_edge_function); | |
BOOST_GRID_GRAPH_TYPE_TD(degree_iterator); | |
BOOST_GRID_GRAPH_TYPE_TD(in_edge_iterator); | |
return (std::make_pair | |
(in_edge_iterator(degree_iterator(0), | |
in_edge_function(vertex, &graph)), | |
in_edge_iterator(degree_iterator(graph.in_degree(vertex)), | |
in_edge_function(vertex, &graph)))); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type | |
in_degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.in_degree(vertex)); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM degree_size_type | |
degree (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.out_degree(vertex) * 2); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor | |
in_edge_at(BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex, | |
BOOST_GRID_GRAPH_TYPE_MEM degree_size_type in_edge_index, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (graph.in_edge_at(vertex, in_edge_index)); | |
} | |
//================== | |
// Adjacency Matrix | |
//================== | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool> | |
edge (BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor source_vertex, | |
BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor destination_vertex, | |
const BOOST_GRID_GRAPH_TYPE& graph) { | |
std::pair<BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, bool> edge_exists = | |
std::make_pair(std::make_pair(source_vertex, destination_vertex), false); | |
for (std::size_t dimension_index = 0; | |
dimension_index < Dimensions; | |
++dimension_index) { | |
BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type dim_difference = 0; | |
BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type | |
source_dim = source_vertex[dimension_index], | |
dest_dim = destination_vertex[dimension_index]; | |
dim_difference = (source_dim > dest_dim) ? | |
(source_dim - dest_dim) : (dest_dim - source_dim); | |
if (dim_difference > 0) { | |
// If we've already found a valid edge, this would mean that | |
// the vertices are really diagonal across dimensions and | |
// therefore not connected. | |
if (edge_exists.second) { | |
edge_exists.second = false; | |
break; | |
} | |
// If the difference is one, the vertices are right next to | |
// each other and the edge is valid. The edge is still | |
// valid, though, if the dimension wraps and the vertices | |
// are on opposite ends. | |
if ((dim_difference == 1) || | |
(graph.wrapped(dimension_index) && | |
(((source_dim == 0) && (dest_dim == (graph.length(dimension_index) - 1))) || | |
((dest_dim == 0) && (source_dim == (graph.length(dimension_index) - 1)))))) { | |
edge_exists.second = true; | |
// Stay in the loop to check for diagonal vertices. | |
} | |
else { | |
// Stop checking - the vertices are too far apart. | |
edge_exists.second = false; | |
break; | |
} | |
} | |
} // for dimension_index | |
return (edge_exists); | |
} | |
//============================= | |
// Index Property Map Functions | |
//============================= | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type | |
get(vertex_index_t, | |
const BOOST_GRID_GRAPH_TYPE& graph, | |
BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor vertex) { | |
return (graph.index_of(vertex)); | |
} | |
template<BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline BOOST_GRID_GRAPH_TYPE_MEM edges_size_type | |
get(edge_index_t, | |
const BOOST_GRID_GRAPH_TYPE& graph, | |
BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor edge) { | |
return (graph.index_of(edge)); | |
} | |
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline grid_graph_index_map< | |
BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor, | |
BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type> | |
get(vertex_index_t, const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (grid_graph_index_map< | |
BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TYPE_MEM vertex_descriptor, | |
BOOST_GRID_GRAPH_TYPE_MEM vertices_size_type>(graph)); | |
} | |
template <BOOST_GRID_GRAPH_TEMPLATE_PARAMS> | |
friend inline grid_graph_index_map< | |
BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, | |
BOOST_GRID_GRAPH_TYPE_MEM edges_size_type> | |
get(edge_index_t, const BOOST_GRID_GRAPH_TYPE& graph) { | |
return (grid_graph_index_map< | |
BOOST_GRID_GRAPH_TYPE, | |
BOOST_GRID_GRAPH_TYPE_MEM edge_descriptor, | |
BOOST_GRID_GRAPH_TYPE_MEM edges_size_type>(graph)); | |
} | |
template<typename Graph, | |
typename Descriptor, | |
typename Index> | |
friend inline Index | |
get(const grid_graph_index_map<Graph, Descriptor, Index>& index_map, | |
const typename grid_graph_index_map<Graph, Descriptor, Index>::key_type& key) | |
{ | |
return (index_map[key]); | |
} | |
template<typename Graph, | |
typename Descriptor, | |
typename Index> | |
friend struct grid_graph_index_map; | |
}; // grid_graph | |
} // namespace boost | |
#undef BOOST_GRID_GRAPH_TYPE | |
#undef BOOST_GRID_GRAPH_TYPE_TD | |
#undef BOOST_GRID_GRAPH_TYPE_MEM | |
#undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS | |
#undef BOOST_GRID_GRAPH_TRAITS_T | |
#endif // BOOST_GRAPH_GRID_GRAPH_HPP |