ceph/src/boost/libs/graph/doc/AdjacencyGraph.html

   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>AdjacencyGraph</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:AdjacencyGraph"></A>
  21 AdjacencyGraph
  22 </H2>
  23
  24 The AdjacencyGraph concept provides and interface for efficient access
  25 of the adjacent vertices to a vertex in a graph. This is quite similar
  26 to the <a href="./IncidenceGraph.html">IncidenceGraph</a> concept (the
  27 target of an out-edge is an adjacent vertex). Both concepts are
  28 provided because in some contexts there is only concern for the
  29 vertices, whereas in other contexts the edges are also important.
  30
  31 <H3>Refinement of</H3>
  32
  33 <a href="Graph.html">Graph</a>
  34
  35 <h3>Notation</h3>
  36
  37 <Table>
  38 <TR>
  39 <TD><tt>G</tt></TD>
  40 <TD>A type that is a model of Graph.</TD>
  41 </TR>
  42
  43 <TR>
  44 <TD><tt>g</tt></TD>
  45 <TD>An object of type <tt>G</tt>.</TD>
  46 </TR>
  47
  48 <TR>
  49 <TD><tt>v</tt></TD>
  50 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  51 </TR>
  52
  53 </table>
  54
  55
  56 <H3>Associated Types</H3>
  57
  58 <Table border>
  59
  60 <tr>
  61 <td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
  62  This tag type must be convertible to <tt>adjacency_graph_tag</tt>.
  63 </td>
  64 </tr>
  65
  66 <TR>
  67 <TD><pre>boost::graph_traits&lt;G&gt;::adjacency_iterator</pre>
  68 An adjacency iterator for a vertex <i>v</i> provides access to the
  69 vertices adjacent to <i>v</i>.  As such, the value type of an
  70 adjacency iterator is the vertex descriptor type of its graph. An
  71 adjacency iterator must meet the requirements of <a
  72 href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
  73 </TD>
  74 </TR>
  75
  76 </table>
  77
  78 <h3>Valid Expressions</h3>
  79
  80
  81 <table border>
  82
  83 <tr>
  84 <td><a name="sec:adjacent-vertices"><TT>adjacent_vertices(v,&nbsp;g)</TT></a></TD>
  85 <TD>
  86 Returns an iterator-range providing access to the vertices adjacent to
  87 vertex <TT>v</TT> in graph <TT>g</TT>.<a
  88 href="#1">[1]</a>
  89
  90 <br> Return type:
  91 <TT>std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;</TT>
  92 </TD>
  93 </TR>
  94
  95 </table>
  96
  97 <H3>Complexity guarantees</H3>
  98
  99 The <TT>adjacent_vertices()</TT> function must return in constant time.
 100
 101 <H3>See Also</H3>
 102
 103 <a href="./graph_concepts.html">Graph concepts</a>,
 104 <a href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a>
 105
 106 <H3>Concept Checking Class</H3>
 107
 108 <PRE>
 109   template &lt;class G&gt;
 110   struct AdjacencyGraphConcept
 111   {
 112     typedef typename boost::graph_traits&lt;G&gt;::adjacency_iterator
 113       adjacency_iterator;
 114     void constraints() {
 115       BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;adjacency_iterator&gt; ));
 116
 117       p = adjacent_vertices(v, g);
 118       v = *p.first;
 119       const_constraints(g);
 120     }
 121     void const_constraints(const G&amp; g) {
 122       p = adjacent_vertices(v, g);
 123     }
 124     std::pair&lt;adjacency_iterator,adjacency_iterator&gt; p;
 125     typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
 126     G g;
 127   };
 128 </PRE>
 129
 130 <h3>Design Rationale</h3>
 131
 132 The AdjacencyGraph concept is somewhat frivolous since <a
 133 href="./IncidenceGraph.html">IncidenceGraph</a> really covers the same
 134 functionality (and more).  The AdjacencyGraph concept exists because
 135 there are situations when <tt>adjacent_vertices()</tt> is more
 136 convenient to use than <tt>out_edges()</tt>. If you are constructing a
 137 graph class and do not want to put in the extra work of creating an
 138 adjacency iterator, have no fear. There is an adaptor class named <a
 139 href="./adjacency_iterator.html"> <tt>adjacency_iterator</tt></a> that
 140 you can use to create an adjacency iterator out of an out-edge
 141 iterator.
 142
 143 <h3>Notes</h3>
 144
 145 <a name="1">[1]</a>  The case of a
 146 <I>multigraph</I> (where multiple edges can connect the same two
 147 vertices) brings up an issue as to whether the iterators returned by
 148 the <TT>adjacent_vertices()</TT> function access a range that
 149 includes each adjacent vertex once, or whether it should match the
 150 behavior of the <TT>out_edges()</TT> function, and access a
 151 range that may include an adjacent vertex more than once. For now the
 152 behavior is defined to match that of <TT>out_edges()</TT>,
 153 though this decision may need to be reviewed in light of more
 154 experience with graph algorithm implementations.
 155
 156
 157
 158 <br>
 159 <HR>
 160 <TABLE>
 161 <TR valign=top>
 162 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 163 <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>)
 164 </TD></TR></TABLE>
 165
 166 </BODY>
 167 </HTML>