graph_traits<Graph>
The graph equivalent of std::iterator_traits. Pulls the associated types
(descriptors, iterators, categories, sizes) out of a graph type, and
provides the portable null_vertex() sentinel and directed/undirected
queries.
Defined in: <boost/graph/graph_traits.hpp>
When to use it
Always reach for graph_traits<Graph> when Graph is a template
parameter. When Graph is a concrete type you can use the nested typedef
(Graph::vertex_descriptor) directly, but going through the traits
indirection keeps your code compatible with third-party graph types that
specialize graph_traits externally.
Do not subclass a BGL graph type. graph_traits is specialized
for specific types; a derived class will not inherit the specialization.
|
Example — plain usage
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <iostream>
using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;
using Traits = graph_traits<Graph>;
int main() {
Graph g(3);
add_edge(0, 1, g);
add_edge(1, 2, g);
// Descriptors and sizes come out of graph_traits
Traits::vertex_descriptor s = vertex(0, g);
Traits::vertices_size_type n = num_vertices(g);
std::cout << "num_vertices = " << n << '\n';
std::cout << "source vertex = " << s << '\n';
std::cout << "is_directed = " << std::boolalpha << is_directed(g) << '\n';
// The null vertex sentinel — portable across selectors
Traits::vertex_descriptor nv = Traits::null_vertex();
std::cout << "null_vertex = " << nv << '\n';
}num_vertices = 3
source vertex = 0
is_directed = true
null_vertex = 18446744073709551615The null_vertex value above is std::numeric_limits<std::size_t>::max()
because this graph uses vecS vertex storage. For listS it is a
null pointer; never compare descriptors to 0, -1, or any other
literal — always use graph_traits<Graph>::null_vertex().
Example — generic template function
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <iostream>
// Generic function: Graph is a template parameter, so every nested type
// must be disambiguated with `typename graph_traits<Graph>::...`.
template <typename Graph>
typename boost::graph_traits<Graph>::degree_size_type
sum_out_degrees(const Graph& g) {
using Traits = boost::graph_traits<Graph>;
typename Traits::degree_size_type total = 0;
for (auto v : boost::make_iterator_range(vertices(g))) {
total += out_degree(v, g);
}
return total;
}
int main() {
using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;
Graph g(3);
add_edge(0, 1, g);
add_edge(1, 2, g);
add_edge(0, 2, g);
std::cout << "sum of out-degrees = " << sum_out_degrees(g) << '\n';
}sum of out-degrees = 3Inside a function template, every nested name through graph_traits must
be disambiguated with typename because the compiler does not yet know
that graph_traits<Graph>::degree_size_type names a type.
Synopsis
namespace boost {
template <typename Graph>
struct graph_traits {
typedef /* from Graph */ vertex_descriptor;
typedef /* from Graph */ edge_descriptor;
typedef /* from Graph */ adjacency_iterator;
typedef /* from Graph */ out_edge_iterator;
typedef /* from Graph */ in_edge_iterator;
typedef /* from Graph */ vertex_iterator;
typedef /* from Graph */ edge_iterator;
typedef /* from Graph */ directed_category;
typedef /* from Graph */ edge_parallel_category;
typedef /* from Graph */ traversal_category;
typedef /* from Graph */ vertices_size_type;
typedef /* from Graph */ edges_size_type;
typedef /* from Graph */ degree_size_type;
static vertex_descriptor null_vertex();
};
// Free functions / type traits:
template <typename Graph> bool is_directed (const Graph& g);
template <typename Graph> bool is_undirected(const Graph& g);
template <typename Graph> struct is_directed_graph; // inherits mpl::bool_
template <typename Graph> struct is_undirected_graph; // inherits mpl::bool_
} // namespace boostMembers
| Member | Description |
|---|---|
|
Handle type for vertices. Concrete type depends on the graph storage selector (see the overview table). |
|
Handle type for edges. Contains source/target endpoint information. |
|
Iterator over vertices adjacent to a given vertex. Dereferences to a
|
|
Iterator over the out-edges of a vertex. Dereferences to |
|
Iterator over the in-edges of a vertex (requires Bidirectional Graph). |
|
Iterator over the whole vertex set. |
|
Iterator over the whole edge set. |
|
|
|
|
|
Tag composed (via inheritance) of
|
|
Unsigned integer types for vertex count, edge count, and per-vertex degree. |
|
Portable sentinel meaning "no vertex". Use it instead of integer literals when clearing predecessor maps or testing for "unset". |