1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 4 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) 8 --> 9<Head> 10<Title>AdjacencyMatrix</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18 19 20<H2><A NAME="concept:AdjacencyMatrix"></A> 21AdjacencyMatrix 22</H2> 23 24<P> 25The AdjacencyMatrix concept refines <a href="./Graph.html">Graph</a> 26concept and adds the requirement for efficient access to any edge in 27the graph given the source and target vertices. No Boost Graph Library 28algorithms currently use this concept. However there are algorithms 29not yet implemented such as Floyd-Warshall that would require this 30concept. 31 32<H3>Refinement of</H3> 33 34<a href="./Graph.html">Graph</a> 35 36<H3>Associated Types</H3> 37 38<Table border> 39 40<tr> 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>. 43</td> 44</tr> 45 46</table> 47 48<H3>Valid Expressions</H3> 49 50<table border> 51 52<tr> 53<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th> 54</tr> 55 56<tr> 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> 60<TD> 61Returns a pair consisting of a flag saying whether there exists an 62edge between <TT>u</TT> and <TT>v</TT> in graph <TT>g</TT>, and 63consisting of the edge descriptor if the edge was found. 64</TD> 65</TR> 66</TABLE> 67 68<H3>Complexity guarantees</H3> 69 70The <TT>edge()</TT> function must return in constant time. 71 72 73<H3>Models</H3> 74 75<a href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a> 76 77<H3>Concept Checking Class</H3> 78 79<PRE> 80 template <class G> 81 struct AdjacencyMatrix 82 { 83 typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; 84 void constraints() { 85 p = edge(u, v, g); 86 } 87 typename boost::graph_traits<G>::vertex_descriptor u, v; 88 std::pair<bool, edge_descriptor> p; 89 G g; 90 }; 91</PRE> 92 93 94<br> 95<HR> 96<TABLE> 97<TR valign=top> 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>) 100</TD></TR></TABLE> 101 102</BODY> 103</HTML> 104
