ceph/src/boost/libs/graph/doc/VertexListGraph.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>VertexListGraph</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><A NAME="concept:VertexListGraph">
  20 VertexListGraph
  21 </H2>
  22
  23 The <I>VertexListGraph</I> concept refines the <a
  24 href="./Graph.html">Graph</a> concept, and adds the requirement for
  25 efficient traversal of all the vertices in the graph.
  26
  27 <H3>Refinement of</H3>
  28
  29 <a href="./Graph.html">Graph</a>
  30
  31 <H3>Associated Types</H3>
  32
  33 <Table border>
  34
  35 <tr>
  36 <td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
  37  This tag type must be convertible to <tt>vertex_list_graph_tag</tt>.
  38 </td>
  39 </tr>
  40
  41 <TR>
  42 <TD><tt>boost::graph_traits&lt;G&gt;::vertex_iterator</tt><br><br>
  43 A vertex iterator (obtained via <TT>vertices(g)</TT>) provides access
  44 to all of the vertices in a graph.  A vertex iterator type must meet
  45 the requirements of <a
  46 href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. The
  47 value type of the vertex iterator must be the vertex descriptor of the
  48 graph.
  49 </TD>
  50 </TR>
  51
  52 <tr>
  53 <td><tt>boost::graph_traits&lt;G&gt;::vertices_size_type</tt><br><br>
  54 The unsigned integer type used to represent the number of vertices
  55 in the graph.
  56 </td>
  57 </tr>
  58
  59 </table>
  60
  61 <h3>Valid Expressions</h3>
  62
  63 <table border>
  64
  65 <tr>
  66 <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
  67 </tr>
  68
  69 <tr>
  70 <td>Vertex Set of the Graph</td>
  71 <td><a name="sec:vertices"><TT>vertices(g)</TT></a></TD>
  72 <TD><TT>std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;</TT></TD>
  73 <TD>
  74 Returns an iterator-range providing access to all the vertices in the
  75 graph<TT>g</TT>.
  76 </TD>
  77 </TR>
  78
  79 <tr>
  80 <td>Number of Vertices in the Graph </td>
  81 <td><TT>num_vertices(g)</TT></TD>
  82 <TD><TT>vertices_size_type</TT></TD>
  83 <TD>Returns the number of vertices in the graph <TT>g</TT>.</TD>
  84 </TR>
  85
  86 </TABLE>
  87
  88
  89 <H3>Complexity guarantees</H3>
  90
  91 <P>
  92 The <TT>vertices()</TT> function must return in constant time.
  93
  94 <H3>See Also</H3>
  95
  96 <a href="./graph_concepts.html">Graph concepts</a>
  97
  98
  99 <H3>Design Rationale</H3>
 100
 101 One issue in the design of this concept is whether to include the
 102 refinement from the <a href="./IncidenceGraph.html">IncidenceGraph</a>
 103 and <a href="./AdjacencyGraph.html">AdjacencyGraph</a> concepts.  The
 104 ability to traverse the vertices of a graph is orthogonal to
 105 traversing out-edges, so it would make sense to have a VertexListGraph
 106 concept that only includes vertex traversal. However, such a concept
 107 would no longer really be a graph, but would just be a set, and the
 108 STL already has concepts for dealing with such things. However, there
 109 are many BGL algorithms that need to traverse the vertices and
 110 out-edges of a graph, so for convenience a concept is needed that
 111 groups these requirements together, hence the VertexListGraph concept.
 112
 113
 114 <H3>Concept Checking Class</H3>
 115
 116 <P>
 117 <PRE>
 118   template &lt;class G&gt;
 119   struct VertexListGraphConcept
 120   {
 121     typedef typename boost::graph_traits&lt;G&gt;::vertex_iterator
 122       vertex_iterator;
 123     void constraints() {
 124       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept&lt;G&gt; ));
 125       BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept&lt;G&gt; ));
 126       BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;vertex_iterator&gt; ));
 127
 128       p = vertices(g);
 129       V = num_vertices(g);
 130       v = *p.first;
 131       const_constraints(g);
 132     }
 133     void const_constraints(const G&amp; g) {
 134       p = vertices(g);
 135       V = num_vertices(g);
 136       v = *p.first;
 137     }
 138     std::pair&lt;vertex_iterator, vertex_iterator&gt; p;
 139     typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
 140     typename boost::graph_traits&lt;G&gt;::vertices_size_type V;
 141     G g;
 142   };
 143 </PRE>
 144
 145 <br>
 146 <HR>
 147 <TABLE>
 148 <TR valign=top>
 149 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 150 <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>)
 151 </TD></TR></TABLE>
 152
 153 </BODY>
 154 </HTML>