IncidenceGraph
The IncidenceGraph concept provides an interface for efficient access to the out-edges of each vertex in the graph.
Notation
G |
A type that is a model of IncidenceGraph. |
|---|---|
|
An object of type |
|
An object of type
|
|
Are objects of type
|
Associated Types
|
An out-edge iterator for a vertex v provides access to the out-edges
of the vertex. As such, the value type of an out-edge iterator is the
edge descriptor type of its graph. An out-edge iterator must meet the
requirements of |
The unsigned integral type used for representing the number out-edges or incident edges of a vertex. |
Valid Expressions
|
Returns the vertex descriptor for u of
the edge (u,v) represented by |
|
Returns the vertex descriptor for v of
the edge (u,v) represented by |
|
Returns an iterator-range
providing access to the out-edges (for directed graphs) or incident
edges (for undirected graphs) of vertex |
|
Returns the number of out-edges (for directed
graphs) or the number of incident edges (for undirected graphs) of
vertex |
Complexity guarantees
The source(), target(), and out_edges() functions must all be
constant time. The out_degree() function must be linear in the
number of out-edges.
Notes
[1] For undirected graphs, the edge (u,v) is the same as
edge (v,u), so without some extra guarantee an implementation would be
free use any ordering for the pair of vertices in an out-edge. For
example, if you call out_edges(u, g), and v is one of the
vertices adjacent to u, then the implementation would be free to
return (v,u) as an out-edge which would be non-intuitive and cause
trouble for algorithms. Therefore, the extra requirement is added that
the out-edge connecting u and v must be given as (u,v) and not
(v,u).
Concept Checking Class
template <class G>
struct IncidenceGraphConcept
{
typedef typename boost::graph_traits<G>::out_edge_iterator out_edge_iterator;
void constraints() {
BOOST_CONCEPT_ASSERT(( GraphConcept<G> ));
BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<out_edge_iterator> ));
p = out_edges(u, g);
e = *p.first;
u = source(e, g);
v = target(e, g);
}
void const_constraints(const G& g) {
p = out_edges(u, g);
e = *p.first;
u = source(e, g);
v = target(e, g);
}
std::pair<out_edge_iterator, out_edge_iterator> p;
typename boost::graph_traits<G>::vertex_descriptor u, v;
typename boost::graph_traits<G>::edge_descriptor e;
G g;
};