| <HTML> |
| <!-- |
| Copyright (c) Jeremy Siek 2000 |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| <Head> |
| <Title>AdjacencyMatrix</Title> |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| |
| |
| |
| <H2><A NAME="concept:AdjacencyMatrix"></A> |
| AdjacencyMatrix |
| </H2> |
| |
| <P> |
| The AdjacencyMatrix concept refines <a href="./Graph.html">Graph</a> |
| 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. |
| |
| <H3>Refinement of</H3> |
| |
| <a href="./Graph.html">Graph</a> |
| |
| <H3>Associated Types</H3> |
| |
| <Table border> |
| |
| <tr> |
| <td><tt>boost::graph_traits<G>::traversal_category</tt><br><br> |
| This tag type must be convertible to <tt>adjacency_matrix_tag</tt>. |
| </td> |
| </tr> |
| |
| </table> |
| |
| <H3>Valid Expressions</H3> |
| |
| <table border> |
| |
| <tr> |
| <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th> |
| </tr> |
| |
| <tr> |
| <td>Direct Edge Access</td> |
| <TD><TT>edge(u,v,g)</TT></TD> |
| <TD><TT>std::pair<edge_descriptor, bool></TT></TD> |
| <TD> |
| Returns a pair consisting of a flag saying whether there exists an |
| edge between <TT>u</TT> and <TT>v</TT> in graph <TT>g</TT>, and |
| consisting of the edge descriptor if the edge was found. |
| </TD> |
| </TR> |
| </TABLE> |
| |
| <H3>Complexity guarantees</H3> |
| |
| The <TT>edge()</TT> function must return in constant time. |
| |
| |
| <H3>Models</H3> |
| |
| <a href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a> |
| |
| <H3>Concept Checking Class</H3> |
| |
| <PRE> |
| 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; |
| }; |
| </PRE> |
| |
| |
| <br> |
| <HR> |
| <TABLE> |
| <TR valign=top> |
| <TD nowrap>Copyright © 2000-2001</TD><TD> |
| <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>) |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |
