ceph/src/boost/libs/graph/doc/Graph.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>Graph</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 <H2><A NAME="concept:Graph"></A>
  19 Graph
  20 </H2>
  21
  22 <P>
  23 The Graph concept contains a few requirements that are common to all
  24 the graph concepts. These include some associated types for
  25 <tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, etc. One should
  26 note that a model of Graph is <B>not</B> required to be a model of <a
  27 href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>,
  28 so algorithms should pass graph objects by reference.
  29
  30 <P>
  31
  32 <h3>Notation</h3>
  33
  34 <Table>
  35 <TR>
  36 <TD><tt>G</tt></TD>
  37 <TD>A type that is a model of Graph.</TD>
  38 </TR>
  39
  40 <TR>
  41 <TD><tt>g</tt></TD>
  42 <TD>An object of type <tt>G</tt>.</TD>
  43 </TR>
  44 </table>
  45
  46 <H3>Associated Types</H3>
  47
  48 <table border>
  49 <tr>
  50 <td><pre>boost::graph_traits&lt;G&gt;::vertex_descriptor</pre>
  51 A vertex descriptor corresponds to a unique vertex in an abstract
  52 graph instance. A vertex descriptor must be
  53 <a
  54 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a>,
  55 <a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
  56 <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
  57 </td>
  58 </tr>
  59
  60 <tr>
  61 <td><pre>boost::graph_traits&lt;G&gt;::edge_descriptor</pre>
  62 An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a
  63 graph.  An edge descriptor must be <a
  64 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</I>,
  65 <a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
  66 <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
  67 </td>
  68 </tr>
  69
  70 <tr>
  71 <td><pre>boost::graph_traits&lt;G&gt;::directed_category</pre>
  72 This type shall be convertible to <TT>directed_tag</TT> or <TT>undirected_tag</TT>.
  73 </td>
  74 </tr>
  75
  76 <tr>
  77 <td><pre>boost::graph_traits&lt;G&gt;::edge_parallel_category</pre>
  78 This describes whether the graph class allows the insertion of
  79 parallel edges (edges with the same source and target). The two tags
  80 are <TT>allow_parallel_edge_tag</TT> and <TT>disallow_parallel_edge_tag</TT>.
  81 </td>
  82 </tr>
  83
  84 <tr>
  85 <td><pre>boost::graph_traits&lt;G&gt;::traversal_category</pre>
  86 This describes the ways in which the vertices and edges of the
  87 graph can be visited. The choices are <TT>incidence_graph_tag</TT>,
  88 <TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>,
  89 <TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and
  90 <TT>adjacency_matrix_tag</TT>.
  91 </td>
  92 </tr>
  93
  94 </table>
  95
  96 <H3>Valid Expressions</H3>
  97
  98 <table border>
  99
 100 <tr>
 101 <td><pre>boost::graph_traits&lt;G&gt;::null_vertex()</pre></td></TD>
 102 <td>
 103 Returns a special <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt> object which does not refer to
 104 any vertex of graph object which type is <tt>G</tt>.
 105 <td>
 106 </tr>
 107 </table>
 108
 109
 110
 111 <H3>Concept Checking Class</H3>
 112
 113 <PRE>
 114   template &lt;class G&gt;
 115   struct GraphConcept
 116   {
 117     typedef typename boost::graph_traits&lt;G&gt;::vertex_descriptor vertex_descriptor;
 118     typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
 119     typedef typename boost::graph_traits&lt;G&gt;::directed_category directed_category;
 120     typedef typename boost::graph_traits&lt;G&gt;::edge_parallel_category edge_parallel_category;
 121     typedef typename boost::graph_traits&lt;G&gt;::traversal_category traversal_category;
 122
 123     void constraints() {
 124       BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept&lt;vertex_descriptor&gt; ));
 125       BOOST_CONCEPT_ASSERT(( EqualityComparableConcept&lt;vertex_descriptor&gt; ));
 126       BOOST_CONCEPT_ASSERT(( AssignableConcept&lt;vertex_descriptor&gt; ));
 127       BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept&lt;edge_descriptor&gt; ));
 128       BOOST_CONCEPT_ASSERT(( EqualityComparableConcept&lt;edge_descriptor&gt; ));
 129       BOOST_CONCEPT_ASSERT(( AssignableConcept&lt;edge_descriptor&gt; ));
 130     }
 131     G g;
 132   };
 133 </PRE>
 134
 135 <H3>See Also</H3>
 136
 137 <a href="./graph_concepts.html">Graph concepts</a>
 138
 139 <br>
 140 <HR>
 141 <TABLE>
 142 <TR valign=top>
 143 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 144 <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>)
 145 </TD></TR></TABLE>
 146
 147 </BODY>
 148 </HTML>