Version_1_18_3/boost/libs/graph/docs/EdgeListGraph.html

   1 <HTML>
   2 <!--
   3   -- Copyright (c) Jeremy Siek 2000
   4   --
   5   -- Permission to use, copy, modify, distribute and sell this software
   6   -- and its documentation for any purpose is hereby granted without fee,
   7   -- provided that the above copyright notice appears in all copies and
   8   -- that both that copyright notice and this permission notice appear
   9   -- in supporting documentation.  Silicon Graphics makes no
  10   -- representations about the suitability of this software for any
  11   -- purpose.  It is provided "as is" without express or implied warranty.
  12   -->
  13 <Head>
  14 <Title>EdgeListGraph</Title>
  15 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  16         ALINK="#ff0000">
  17 <IMG SRC="../../../c++boost.gif"
  18      ALT="C++ Boost" width="277" height="86">
  19
  20 <BR Clear>
  21
  22
  23 <H2><A NAME="concept:EdgeListGraph"></A>
  24 EdgeListGraph
  25 </H2>
  26
  27 The EdgeListGraph concept refines the <a href="./Graph.html">Graph</a>
  28 concept, and adds the requirement for efficient access to all the
  29 edges in the graph.
  30
  31
  32 <H3>Refinement of</H3>
  33
  34 <a href="./Graph.html">Graph</a>
  35
  36
  37 <h3>Notation</h3>
  38
  39 <Table>
  40 <TR>
  41 <TD><tt>G</tt></TD>
  42 <TD>A type that is a model of EdgeListGraph.</TD>
  43 </TR>
  44
  45 <TR>
  46 <TD><tt>g</tt></TD>
  47 <TD>An object of type <tt>G</tt>.</TD>
  48 </TR>
  49
  50 <TR>
  51 <TD><tt>e</tt></TD>
  52 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  53 </TR>
  54
  55 </table>
  56
  57 <H3>Associated Types</H3>
  58
  59 <table border>
  60
  61 <tr>
  62 <td><pre>boost::graph_traits&lt;G&gt;::edge_iterator</pre>
  63 An edge iterator (obtained via <TT>edges(g)</TT>) provides access to
  64 all of the edges in a graph. An edge iterator type must meet the
  65 requirements of <a
  66 href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.  The
  67 value type of the edge iterator must be the same as the edge
  68 descriptor of the graph.
  69
  70 <tr>
  71 <td><pre>boost::graph_traits&lt;G&gt;::edges_size_type</pre>
  72 The unsigned integer type used to represent the number of edges in the
  73 graph.
  74 </td>
  75 </tr>
  76
  77 </table>
  78
  79 <h3>Valid Expressions</h3>
  80
  81 <table border>
  82
  83 <tr>
  84 <TD><a name="sec:edges"><TT>edges(g)</TT></a></TD>
  85 <TD>Returns an iterator-range providing access to all
  86      the edges in the graph <TT>g</TT>.<br>
  87 Return type: <TT>std::pair&lt;edge_iterator, edge_iterator&gt;</TT>
  88 </td>
  89 </TR>
  90
  91 <tr>
  92 <TD><TT>num_edges(g)</TT></TD>
  93 <TD>Returns the number of edges in the graph <TT>g</TT>.<br>
  94 Return type: <TT>edges_size_type</TT>
  95 </td>
  96 </TR>
  97
  98 <tr>
  99 <TD><TT>source(e, g)</TT></TD>
 100 <TD>
 101 Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i>
 102 represented by <TT>e</TT>.<br>
 103 Return type: <TT>vertex_descriptor</TT>
 104 </td>
 105 </tr>
 106
 107 <tr>
 108 <TD><TT>target(e, g)</TT></TD>
 109 <TD>
 110 Returns the vertex descriptor for
 111 <i>v</i> of the edge <i>(u,v)</i> represented by  <TT>e</TT>.<br>
 112 Return type: <TT>vertex_descriptor</TT>
 113 </TD>
 114 </TR>
 115
 116 </TABLE>
 117
 118
 119 <H3>Models</H3>
 120
 121 <UL>
 122 <LI><a href="./adjacency_list.html"><TT>adjacency_list</TT></a></LI>
 123 <LI><a href="./edge_list.html"><TT>edge_list</TT></a></LI>
 124 </UL>
 125
 126
 127 <H3>Complexity guarantees</H3>
 128
 129 The <TT>edges()</TT>, <TT>source()</TT>, and <TT>target()</TT> functions
 130 must all return in constant time.
 131
 132
 133 <H3>See Also</H3>
 134
 135 <a href="./graph_concepts.html">Graph concepts</a>
 136
 137 <H3>Concept Checking Class</H3>
 138
 139 <P>
 140 <PRE>
 141   template &lt;class G&gt;
 142   struct EdgeListGraph_concept
 143   {
 144     typedef typename boost::graph_traits&lt;G&gt;::edge_iterator
 145       edge_iterator;
 146     void constraints() {
 147       REQUIRE(G, Graph);
 148       REQUIRE(edge_iterator, MultiPassInputIterator);
 149
 150       p = edges(g);
 151       E = num_edges(g);
 152       e = *p.first;
 153       u = source(e, g);
 154       v = target(e, g);
 155       const_constraints(g);
 156     }
 157     void const_constraints(const G&amp; g) {
 158       p = edges(g);
 159       E = num_edges(g);
 160       e = *p.first;
 161       u = source(e, g);
 162       v = target(e, g);
 163     }
 164     std::pair&lt;edge_iterator,edge_iterator&gt; p;
 165     typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
 166     typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
 167     typename boost::graph_traits&lt;G&gt;::edges_size_type E;
 168     G g;
 169   };
 170 </PRE>
 171
 172
 173 <br>
 174 <HR>
 175 <TABLE>
 176 <TR valign=top>
 177 <TD nowrap>Copyright &copy 2000</TD><TD>
 178 <A HREF=http://www.boost.org/people/jeremy_siek.htm>Jeremy Siek</A>, Univ.of Notre Dame (<A HREF="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</A>)
 179 </TD></TR></TABLE>
 180
 181 </BODY>
 182 </HTML>