Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

C++ Boost


The AdjacencyMatrix concept refines Graph concept and adds the requirement for efficient access to any edge in the graph given the source and target vertices. No Boost Graph Library algorithms currently use this concept. However there are algorithms not yet implemented such as Floyd-Warshall that would require this concept.

Refinement of


Associated Types


This tag type must be convertible to adjacency_matrix_tag.

Valid Expressions

NameExpressionReturn TypeDescription
Direct Edge Access edge(u,v,g) std::pair<edge_descriptor, bool> Returns a pair consisting of a flag saying whether there exists an edge between u and v in graph g, and consisting of the edge descriptor if the edge was found.

Complexity guarantees

The edge() function must return in constant time.



Concept Checking Class

  template <class G>
  struct AdjacencyMatrix
    typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
    void constraints() {
      p = edge(u, v, g);
    typename boost::graph_traits<G>::vertex_descriptor u, v;
    std::pair<bool, edge_descriptor> p;
    G g;

Copyright © 2000-2001 Jeremy Siek, Indiana University (