boost/graph/vertex_and_edge_range.hpp

0001 // Copyright 2004 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009
0010 #ifndef BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
0011 #define BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP
0012
0013 #include <boost/graph/graph_traits.hpp>
0014 #include <iterator>
0015
0016 namespace boost
0017 {
0018
0019 namespace graph
0020 {
0021     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0022     class vertex_and_edge_range
0023     {
0024         typedef graph_traits< Graph > traits_type;
0025
0026     public:
0027         typedef typename traits_type::directed_category directed_category;
0028         typedef
0029             typename traits_type::edge_parallel_category edge_parallel_category;
0030         struct traversal_category : public virtual vertex_list_graph_tag,
0031                                     public virtual edge_list_graph_tag
0032         {
0033         };
0034
0035         typedef std::size_t vertices_size_type;
0036         typedef VertexIterator vertex_iterator;
0037         typedef typename std::iterator_traits< VertexIterator >::value_type
0038             vertex_descriptor;
0039
0040         typedef EdgeIterator edge_iterator;
0041         typedef typename std::iterator_traits< EdgeIterator >::value_type
0042             edge_descriptor;
0043
0044         typedef std::size_t edges_size_type;
0045
0046         typedef void adjacency_iterator;
0047         typedef void out_edge_iterator;
0048         typedef void in_edge_iterator;
0049         typedef void degree_size_type;
0050
0051         static vertex_descriptor null_vertex()
0052         {
0053             return traits_type::null_vertex();
0054         }
0055
0056         vertex_and_edge_range(const Graph& g, VertexIterator first_v,
0057             VertexIterator last_v, vertices_size_type n, EdgeIterator first_e,
0058             EdgeIterator last_e, edges_size_type m)
0059         : g(&g)
0060         , first_vertex(first_v)
0061         , last_vertex(last_v)
0062         , m_num_vertices(n)
0063         , first_edge(first_e)
0064         , last_edge(last_e)
0065         , m_num_edges(m)
0066         {
0067         }
0068
0069         vertex_and_edge_range(const Graph& g, VertexIterator first_v,
0070             VertexIterator last_v, EdgeIterator first_e, EdgeIterator last_e)
0071         : g(&g)
0072         , first_vertex(first_v)
0073         , last_vertex(last_v)
0074         , first_edge(first_e)
0075         , last_edge(last_e)
0076         {
0077             m_num_vertices = std::distance(first_v, last_v);
0078             m_num_edges = std::distance(first_e, last_e);
0079         }
0080
0081         const Graph* g;
0082         vertex_iterator first_vertex;
0083         vertex_iterator last_vertex;
0084         vertices_size_type m_num_vertices;
0085         edge_iterator first_edge;
0086         edge_iterator last_edge;
0087         edges_size_type m_num_edges;
0088     };
0089
0090     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0091     inline std::pair< VertexIterator, VertexIterator > vertices(
0092         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0093     {
0094         return std::make_pair(g.first_vertex, g.last_vertex);
0095     }
0096
0097     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0098     inline typename vertex_and_edge_range< Graph, VertexIterator,
0099         EdgeIterator >::vertices_size_type
0100     num_vertices(
0101         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0102     {
0103         return g.m_num_vertices;
0104     }
0105
0106     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0107     inline std::pair< EdgeIterator, EdgeIterator > edges(
0108         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0109     {
0110         return std::make_pair(g.first_edge, g.last_edge);
0111     }
0112
0113     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0114     inline typename vertex_and_edge_range< Graph, VertexIterator,
0115         EdgeIterator >::edges_size_type
0116     num_edges(
0117         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0118     {
0119         return g.m_num_edges;
0120     }
0121
0122     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0123     inline typename vertex_and_edge_range< Graph, VertexIterator,
0124         EdgeIterator >::vertex_descriptor
0125     source(typename vertex_and_edge_range< Graph, VertexIterator,
0126                EdgeIterator >::edge_descriptor e,
0127         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0128     {
0129         return source(e, *g.g);
0130     }
0131
0132     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0133     inline typename vertex_and_edge_range< Graph, VertexIterator,
0134         EdgeIterator >::vertex_descriptor
0135     target(typename vertex_and_edge_range< Graph, VertexIterator,
0136                EdgeIterator >::edge_descriptor e,
0137         const vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >& g)
0138     {
0139         return target(e, *g.g);
0140     }
0141
0142     template < typename Graph, typename VertexIterator, typename EdgeIterator >
0143     inline vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >
0144     make_vertex_and_edge_range(const Graph& g, VertexIterator first_v,
0145         VertexIterator last_v, EdgeIterator first_e, EdgeIterator last_e)
0146     {
0147         typedef vertex_and_edge_range< Graph, VertexIterator, EdgeIterator >
0148             result_type;
0149         return result_type(g, first_v, last_v, first_e, last_e);
0150     }
0151
0152 } // end namespace graph
0153
0154 using graph::make_vertex_and_edge_range;
0155 using graph::vertex_and_edge_range;
0156
0157 } // end namespace boost
0158 #endif // BOOST_GRAPH_VERTEX_AND_EDGE_RANGE_HPP