## 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

- `adjacency_list`
- `edge_list`

### 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;
      };

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)