EdgeListGraph
The EdgeListGraph concept refines the Graph
concept, and adds the requirement for efficient access to all the
edges in the graph.
Refinement of
Graph
Notation
G |
A type that is a model of EdgeListGraph. |
g |
An object of type G. |
e |
An object of type boost::graph_traits<G>::edge_descriptor. |
Associated Types
boost::graph_traits<G>::traversal_category
This tag type must be convertible to edge_list_graph_tag.
|
boost::graph_traits<G>::edge_iterator
An edge iterator (obtained via edges(g)) provides access to
all of the edges in a graph. An edge iterator type must meet the
requirements of MultiPassInputIterator. The
value type of the edge iterator must be the same as the edge
descriptor of the graph.
|
boost::graph_traits<G>::edges_size_type
The unsigned integer type used to represent the number of edges in the
graph.
|
Valid Expressions
edges(g) |
Returns an iterator-range providing access to all
the edges in the graph g.
Return type: std::pair<edge_iterator, edge_iterator>
|
num_edges(g) |
Returns the number of edges in the graph g.
Return type: edges_size_type
|
source(e, g) |
Returns the vertex descriptor for u of the edge (u,v)
represented by e.
Return type: vertex_descriptor
|
target(e, g) |
Returns the vertex descriptor for
v of the edge (u,v) represented by e.
Return type: vertex_descriptor
|
Models
Complexity guarantees
The edges(), source(), and target() functions
must all return in constant time.
See Also
Graph concepts
Concept Checking Class
template <class G>
struct EdgeListGraphConcept
{
typedef typename boost::graph_traits<G>::edge_iterator
edge_iterator;
void constraints() {
function_requires< GraphConcept<G> >();
function_requires< MultiPassInputIteratorConcept<edge_iterator> >();
p = edges(g);
E = num_edges(g);
e = *p.first;
u = source(e, g);
v = target(e, g);
const_constraints(g);
}
void const_constraints(const G& g) {
p = edges(g);
E = num_edges(g);
e = *p.first;
u = source(e, g);
v = target(e, g);
}
std::pair<edge_iterator,edge_iterator> p;
typename boost::graph_traits<G>::vertex_descriptor u, v;
typename boost::graph_traits<G>::edge_descriptor e;
typename boost::graph_traits<G>::edges_size_type E;
G g;
};
|