...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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.
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. |
boost::graph_traits<G>::traversal_category This tag type must be convertible to bidirectional_graph_tag. |
boost::graph_traits<G>::in_edge_iteratorAn 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. |
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 |
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; };
Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |