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.
Notation
G |
A type that is a model of Graph. |
|---|---|
|
An object of type |
|
An object of type
|
Associated Types
|
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 |
Valid Expressions
|
Returns an iterator-range
providing access to the in-edges (for directed graphs) or incident edges
(for undirected graphs) of vertex |
|
Returns the number of in-edges (for directed
graphs) or the number of incident edges (for undirected graphs) of
vertex |
|
Returns the number of in-edges plus out-edges (for
directed graphs) or the number of incident edges (for undirected graphs)
of vertex |
Models
-
adjacency_listwithDirected=bidirectionalS -
adjacency_listwithDirected=undirectedS
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).
Concept Checking Class
template <class G>
struct BidirectionalGraphConcept
{
typedef typename boost::graph_traits<G>::in_edge_iterator
in_edge_iterator;
void constraints() {
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> ));
p = in_edges(v, g);
n = in_degree(v, g);
n = degree(v, g);
e = *p.first;
const_constraints(g);
}
void const_constraints(const G& g) {
p = in_edges(v, g);
n = in_degree(v, g);
n = degree(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;
typename boost::graph_traits<G>::degree_size_type n;
G g;
};