ceph/src/boost/libs/graph/doc/BidirectionalGraph.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>Bidirectional</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 <H2>
  20 <A NAME="concept:BidirectionalGraph"></A>
  21 BidirectionalGraph
  22 </H2>
  23
  24 <P>
  25 The BidirectionalGraph concept refines <a
  26 href="./IncidenceGraph.html">IncidenceGraph</a> and adds the
  27 requirement for efficient access to the in-edges of each vertex. This
  28 concept is separated from <a
  29 href="./IncidenceGraph.html">IncidenceGraph</a> because for directed
  30 graphs efficient access to in-edges typically requires more storage
  31 space, and many algorithms do not require access to in-edges.  For
  32 undirected graphs this is not an issue, since the <TT>in_edges()</TT>
  33 and <TT>out_edges()</TT> functions are the same, they both return the
  34 edges incident to the vertex.
  35
  36 <H3>Refinement of</H3>
  37
  38 <a href="./IncidenceGraph.html">IncidenceGraph</a>
  39
  40 <h3>Notation</h3>
  41
  42 <Table>
  43 <TR>
  44 <TD><tt>G</tt></TD>
  45 <TD>A type that is a model of Graph.</TD>
  46 </TR>
  47
  48 <TR>
  49 <TD><tt>g</tt></TD>
  50 <TD>An object of type <tt>G</tt>.</TD>
  51 </TR>
  52
  53 <TR>
  54 <TD><tt>v</tt></TD>
  55 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  56 </TR>
  57
  58 </table>
  59
  60 <H3>Associated Types</H3>
  61
  62 <Table border>
  63
  64 <tr>
  65 <td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
  66  This tag type must be convertible to <tt>bidirectional_graph_tag</tt>.
  67 </td>
  68 </tr>
  69
  70 <TR>
  71 <TD><pre>boost::graph_traits&lt;G&gt;::in_edge_iterator</pre>
  72 An in-edge iterator for a vertex <i>v</i> provides access to the
  73 in-edges of <i>v</i>.  As such, the value type of an in-edge iterator
  74 is the edge descriptor type of its graph. An in-edge iterator must
  75 meet the requirements of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
  76 </TD>
  77 </TR>
  78
  79 </Table>
  80
  81 <h3>Valid Expressions</h3>
  82
  83 <Table border>
  84
  85 <tr>
  86 <td><a name="sec:in-edges"><TT>in_edges(v, g)</TT></a></TD>
  87 <TD>
  88 Returns an iterator-range providing access to the
  89 in-edges (for directed graphs) or incident edges (for
  90 undirected graphs) of vertex <TT>v</TT> in graph <TT>g</TT>.
  91 For both directed and undirected graphs, the target of
  92 an out-edge is required to be vertex <tt>v</tt> and the
  93 source is required to be a vertex that is adjacent to <tt>v</tt>.
  94 <br>
  95 Return type: <TT>std::pair&lt;in_edge_iterator, in_edge_iterator&gt;</TT>
  96 </TD>
  97 </TR>
  98
  99 <tr>
 100 <TD><TT>in_degree(v, g)</TT></TD>
 101 <TD>
 102 Returns the number of in-edges (for directed graphs) or the
 103 number of incident edges (for undirected graphs) of vertex <TT>v</TT>
 104 in graph <TT>g</TT>.<br>
 105 Return type: <TT>degree_size_type</TT>
 106 </TD>
 107 </TR>
 108
 109 <tr>
 110 <TD><TT>degree(v, g)</TT></TD>
 111 <TD>Returns the number of in-edges plus out-edges (for directed graphs) or the
 112 number of incident edges (for undirected graphs) of vertex <TT>v</TT>
 113 in graph <TT>g</TT>.<br>
 114 Return type: <TT>degree_size_type</TT>
 115 </TD>
 116 </TR>
 117
 118 </Table>
 119
 120 <H3>Models</H3>
 121
 122 <ul>
 123 <li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=bidirectionalS</tt></li>
 124 <li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=undirectedS</tt></li>
 125 </ul>
 126
 127
 128 <H3>Complexity guarantees</H3>
 129
 130 The <TT>in_edges()</TT> function is required to be constant time.  The
 131 <tt>in_degree()</tt> and <tt>degree()</tt> functions must be linear in
 132 the number of in-edges (for directed graphs) or incident edges (for
 133 undirected graphs).
 134
 135 <H3>See Also</H3>
 136
 137 <a href="./graph_concepts.html">Graph concepts</a>
 138
 139 <H3>Concept Checking Class</H3>
 140
 141 <PRE>
 142   template &lt;class G&gt;
 143   struct BidirectionalGraphConcept
 144   {
 145     typedef typename boost::graph_traits&lt;G&gt;::in_edge_iterator
 146       in_edge_iterator;
 147     void constraints() {
 148       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept&lt;G&gt; ));
 149       BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;in_edge_iterator&gt; ));
 150
 151       p = in_edges(v, g);
 152       n = in_degree(v, g);
 153       n = degree(v, g);
 154       e = *p.first;
 155       const_constraints(g);
 156     }
 157     void const_constraints(const G&amp; g) {
 158       p = in_edges(v, g);
 159       n = in_degree(v, g);
 160       n = degree(v, g);
 161       e = *p.first;
 162     }
 163     std::pair&lt;in_edge_iterator, in_edge_iterator&gt; p;
 164     typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
 165     typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
 166     typename boost::graph_traits&lt;G&gt;::degree_size_type n;
 167     G g;
 168   };
 169 </PRE>
 170
 171 <br>
 172 <HR>
 173 <TABLE>
 174 <TR valign=top>
 175 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 176 <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>)
 177 </TD></TR></TABLE>
 178
 179 </BODY>
 180 </HTML>