BidirectionalGraph
The BidirectionalGraph concept refines IncidenceGraph and adds the
requirement for efficient access to the in-edges of each vertex. This
concept is separated from IncidenceGraph because for directed
graphs efficient access to in-edges typically requires more storage
space, and many algorithms do not require access to in-edges. For
undirected graphs this is not an issue, since the in_edges()
and out_edges() functions are the same, they both return the
edges incident to the vertex.
Refinement of
IncidenceGraph
Notation
G |
A type that is a model of Graph. |
g |
An object of type G. |
v |
An object of type boost::graph_traits<G>::vertex_descriptor. |
Associated Types
boost::graph_traits<G>::traversal_category
This tag type must be convertible to bidirectional_graph_tag.
|
boost::graph_traits<G>::in_edge_iterator
An in-edge iterator for a vertex v provides access to the
in-edges of v. As such, the value type of an in-edge iterator
is the edge descriptor type of its graph. An in-edge iterator must
meet the requirements of MultiPassInputIterator.
|
Valid Expressions
in_edges(v, g) |
Returns an iterator-range providing access to the
in-edges (for directed graphs) or incident edges (for
undirected graphs) of vertex v in graph g.
For both directed and undirected graphs, the target of
an out-edge is required to be vertex v and the
source is required to be a vertex that is adjacent to v.
Return type: std::pair<in_edge_iterator, in_edge_iterator>
|
in_degree(v, g) |
Returns the number of in-edges (for directed graphs) or the
number of incident edges (for undirected graphs) of vertex v
in graph g.
Return type: degree_size_type
|
degree(v, g) |
Returns the number of in-edges plus out-edges (for directed graphs) or the
number of incident edges (for undirected graphs) of vertex v
in graph g.
Return type: degree_size_type
|
Models
Complexity guarantees
The in_edges() function is required to be constant time. The
in_degree() and degree() functions must be linear in
the number of in-edges (for directed graphs) or incident edges (for
undirected graphs).
See Also
Graph concepts
Concept Checking Class
template <class G>
struct BidirectionalGraphConcept
{
typedef typename boost::graph_traits<G>::in_edge_iterator
in_edge_iterator;
void constraints() {
function_requires< IncidenceGraphConcept<G> >();
function_requires< MultiPassInputIteratorConcept<in_edge_iterator> >();
p = in_edges(v, g);
e = *p.first;
const_constraints(g);
}
void const_constraints(const G& g) {
p = in_edges(v, g);
e = *p.first;
}
std::pair<in_edge_iterator, in_edge_iterator> p;
typename boost::graph_traits<G>::vertex_descriptor v;
typename boost::graph_traits<G>::edge_descriptor e;
G g;
};
|