3 Copyright (c) Jeremy Siek 2000
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
10 <Title>AdjacencyMatrix
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
20 <H2><A NAME=
"concept:AdjacencyMatrix"></A>
25 The AdjacencyMatrix concept refines
<a href=
"./Graph.html">Graph
</a>
26 concept and adds the requirement for efficient access to any edge in
27 the graph given the source and target vertices. No Boost Graph Library
28 algorithms currently use this concept. However there are algorithms
29 not yet implemented such as Floyd-Warshall that would require this
32 <H3>Refinement of
</H3>
34 <a href=
"./Graph.html">Graph
</a>
36 <H3>Associated Types
</H3>
41 <td><tt>boost::graph_traits
<G
>::traversal_category
</tt><br><br>
42 This tag type must be convertible to
<tt>adjacency_matrix_tag
</tt>.
48 <H3>Valid Expressions
</H3>
53 <th>Name
</th><th>Expression
</th><th>Return Type
</th><th>Description
</th>
57 <td>Direct Edge Access
</td>
58 <TD><TT>edge(u,v,g)
</TT></TD>
59 <TD><TT>std::pair
<edge_descriptor, bool
></TT></TD>
61 Returns a pair consisting of a flag saying whether there exists an
62 edge between
<TT>u
</TT> and
<TT>v
</TT> in graph
<TT>g
</TT>, and
63 consisting of the edge descriptor if the edge was found.
68 <H3>Complexity guarantees
</H3>
70 The
<TT>edge()
</TT> function must return in constant time.
75 <a href=
"./adjacency_matrix.html"><tt>adjacency_matrix
</tt></a>
77 <H3>Concept Checking Class
</H3>
80 template
<class G
>
81 struct AdjacencyMatrix
83 typedef typename boost::graph_traits
<G
>::edge_descriptor edge_descriptor;
87 typename boost::graph_traits
<G
>::vertex_descriptor u, v;
88 std::pair
<bool, edge_descriptor
> p;
98 <TD nowrap
>Copyright
© 2000-
2001</TD><TD>
99 <A HREF=
"http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek
</A>, Indiana University (
<A HREF=
"mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu
</A>)