EIC code displayed by LXR master/​include/​boost/​graph/​grid_graph.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:37:29

 //=======================================================================
 // 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/limits.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_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(&graph) {}
 
     value_type operator[](key_type key) const
     {
         return (m_graph->index_of(key));
     }
 
     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]);
     }
 
 protected:
     const 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;
 };
 
 //==========================
 // Reverse Edge Property Map
 //==========================
 
 template < typename Descriptor > struct grid_graph_reverse_edge_map
 {
 public:
     typedef Descriptor value_type;
     typedef Descriptor reference_type;
     typedef reference_type reference;
     typedef Descriptor key_type;
     typedef readable_property_map_tag category;
 
     grid_graph_reverse_edge_map() {}
 
     value_type operator[](const key_type& key) const
     {
         return (value_type(key.second, key.first));
     }
 
     friend inline Descriptor get(
         const grid_graph_reverse_edge_map< Descriptor >& rev_map,
         const typename grid_graph_reverse_edge_map< Descriptor >::key_type& key)
     {
         return (rev_map[key]);
     }
 };
 
 template < BOOST_GRID_GRAPH_TEMPLATE_PARAMS >
 struct property_map< BOOST_GRID_GRAPH_TYPE, edge_reverse_t >
 {
     typedef grid_graph_reverse_edge_map<
         BOOST_GRID_GRAPH_TRAITS_T::edge_descriptor >
         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 directed_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, vertices_size_type(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
     {
 
         boost::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);
 
         BOOST_ASSERT(source_vertex != target_vertex);
 
         // 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(), vertices_size_type(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
     //================
 
     friend inline std::pair< typename type::vertex_iterator,
         typename type::vertex_iterator >
     vertices(const type& graph)
     {
         typedef typename type::vertex_iterator vertex_iterator;
         typedef typename type::vertex_function vertex_function;
         typedef typename type::vertex_index_iterator 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))));
     }
 
     friend inline typename type::vertices_size_type num_vertices(
         const type& graph)
     {
         return (graph.num_vertices());
     }
 
     friend inline typename type::vertex_descriptor vertex(
         typename type::vertices_size_type vertex_index, const type& graph)
     {
 
         return (graph.vertex_at(vertex_index));
     }
 
     //===============
     // IncidenceGraph
     //===============
 
     friend inline std::pair< typename type::out_edge_iterator,
         typename type::out_edge_iterator >
     out_edges(typename type::vertex_descriptor vertex, const type& graph)
     {
         typedef typename type::degree_iterator degree_iterator;
         typedef typename type::out_edge_function out_edge_function;
         typedef typename type::out_edge_iterator 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))));
     }
 
     friend inline typename type::degree_size_type out_degree(
         typename type::vertex_descriptor vertex, const type& graph)
     {
         return (graph.out_degree(vertex));
     }
 
     friend inline typename type::edge_descriptor out_edge_at(
         typename type::vertex_descriptor vertex,
         typename type::degree_size_type out_edge_index, const type& graph)
     {
         return (graph.out_edge_at(vertex, out_edge_index));
     }
 
     //===============
     // AdjacencyGraph
     //===============
 
     friend typename std::pair< typename type::adjacency_iterator,
         typename type::adjacency_iterator >
     adjacent_vertices(
         typename type::vertex_descriptor vertex, const type& graph)
     {
         typedef typename type::degree_iterator degree_iterator;
         typedef
             typename type::adjacent_vertex_function adjacent_vertex_function;
         typedef typename type::adjacency_iterator 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
     //==============
 
     friend inline typename type::edges_size_type num_edges(const type& graph)
     {
         return (graph.num_edges());
     }
 
     friend inline typename type::edge_descriptor edge_at(
         typename type::edges_size_type edge_index, const type& graph)
     {
         return (graph.edge_at(edge_index));
     }
 
     friend inline std::pair< typename type::edge_iterator,
         typename type::edge_iterator >
     edges(const type& graph)
     {
         typedef typename type::edge_index_iterator edge_index_iterator;
         typedef typename type::edge_function edge_function;
         typedef typename type::edge_iterator 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
     //===================
 
     friend inline std::pair< typename type::in_edge_iterator,
         typename type::in_edge_iterator >
     in_edges(typename type::vertex_descriptor vertex, const type& graph)
     {
         typedef typename type::in_edge_function in_edge_function;
         typedef typename type::degree_iterator degree_iterator;
         typedef typename type::in_edge_iterator 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))));
     }
 
     friend inline typename type::degree_size_type in_degree(
         typename type::vertex_descriptor vertex, const type& graph)
     {
         return (graph.in_degree(vertex));
     }
 
     friend inline typename type::degree_size_type degree(
         typename type::vertex_descriptor vertex, const type& graph)
     {
         return (graph.out_degree(vertex) * 2);
     }
 
     friend inline typename type::edge_descriptor in_edge_at(
         typename type::vertex_descriptor vertex,
         typename type::degree_size_type in_edge_index, const type& graph)
     {
         return (graph.in_edge_at(vertex, in_edge_index));
     }
 
     //==================
     // Adjacency Matrix
     //==================
 
     friend std::pair< typename type::edge_descriptor, bool > edge(
         typename type::vertex_descriptor source_vertex,
         typename type::vertex_descriptor destination_vertex, const type& graph)
     {
 
         std::pair< typename type::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)
         {
 
             typename type::vertices_size_type dim_difference = 0;
             typename type::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
     //=============================
 
     friend inline typename type::vertices_size_type get(vertex_index_t,
         const type& graph, typename type::vertex_descriptor vertex)
     {
         return (graph.index_of(vertex));
     }
 
     friend inline typename type::edges_size_type get(
         edge_index_t, const type& graph, typename type::edge_descriptor edge)
     {
         return (graph.index_of(edge));
     }
 
     friend inline grid_graph_index_map< type, typename type::vertex_descriptor,
         typename type::vertices_size_type >
     get(vertex_index_t, const type& graph)
     {
         return (grid_graph_index_map< type, typename type::vertex_descriptor,
             typename type::vertices_size_type >(graph));
     }
 
     friend inline grid_graph_index_map< type, typename type::edge_descriptor,
         typename type::edges_size_type >
     get(edge_index_t, const type& graph)
     {
         return (grid_graph_index_map< type, typename type::edge_descriptor,
             typename type::edges_size_type >(graph));
     }
 
     friend inline grid_graph_reverse_edge_map< typename type::edge_descriptor >
     get(edge_reverse_t, const type& graph)
     {
         return (
             grid_graph_reverse_edge_map< typename type::edge_descriptor >());
     }
 
     template < typename Graph, typename Descriptor, typename Index >
     friend struct grid_graph_index_map;
 
     template < typename Descriptor > friend struct grid_graph_reverse_edge_map;
 
 }; // grid_graph
 
 } // namespace boost
 
 #undef BOOST_GRID_GRAPH_TYPE
 #undef BOOST_GRID_GRAPH_TEMPLATE_PARAMS
 #undef BOOST_GRID_GRAPH_TRAITS_T
 
 #endif // BOOST_GRAPH_GRID_GRAPH_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team