# IncidenceGraph

The IncidenceGraph concept provides an interface for efficient access to the out-edges of each vertex in the graph.

### Refinement of

Graph

### Notation

`G` | A type that is a model of IncidenceGraph.
`g` | An object of type `G`.
`e` | An object of type `boost::graph_traits<G>::edge_descriptor`.
`u, v` | Are objects of type `boost::graph_traits<G>::vertex_descriptor`.

### Associated Types

`boost::graph_traits<G>::traversal_category` This tag type must be convertible to `incidence_graph_tag`.
    boost::graph_traits<G>::out_edge_iterator
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 MultiPassInputIterator.
    boost::graph_traits<G>::degree_size_type
The unsigned intergral type used for representing the number out-edges or incident edges of a vertex.

### Valid Expressions

`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`
`out_edges(u, g)` | Returns an iterator-range providing access to the out-edges (for directed graphs) or incident edges (for undirected graphs) of vertex `u` in graph `g`. The source vertex of an edge obtained via an out edge iterator is guaranteed (for both directed and undirected graphs) to be the vertex `u` used in the call to `out_edges(u, g)` and the target vertex must the a vertex adjacent to `u`.[1]
Return type: `std::pair<out_edge_iterator, out_edge_iterator>`
`out_degree(u, g)` | Returns the number of out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex `u` in graph `g`. Return type: `degree_size_type`

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

### See Also

Graph concepts

### 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() {
          function_requires< GraphConcept<G> >();
          function_requires< 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;
      };

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)