Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/EdgeListGraph.html @ 47

Last change on this file since 47 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 4.1 KB
Line 
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>EdgeListGraph</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:EdgeListGraph"></A>
20EdgeListGraph
21</H2>
22
23The EdgeListGraph concept refines the <a href="./Graph.html">Graph</a>
24concept, and adds the requirement for efficient access to all the
25edges in the graph.
26
27
28<H3>Refinement of</H3>
29
30<a href="./Graph.html">Graph</a>
31
32
33<h3>Notation</h3>
34
35<Table>
36<TR>
37<TD><tt>G</tt></TD>
38<TD>A type that is a model of EdgeListGraph.</TD>
39</TR>
40
41<TR>
42<TD><tt>g</tt></TD>
43<TD>An object of type <tt>G</tt>.</TD>
44</TR>
45
46<TR>
47<TD><tt>e</tt></TD>
48<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
49</TR>
50
51</table>
52
53<H3>Associated Types</H3>
54
55<table border>
56
57<tr>
58<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
59 This tag type must be convertible to <tt>edge_list_graph_tag</tt>.
60</td>
61</tr>
62
63<tr>
64<td><pre>boost::graph_traits&lt;G&gt;::edge_iterator</pre>
65An edge iterator (obtained via <TT>edges(g)</TT>) provides access to
66all of the edges in a graph. An edge iterator type must meet the
67requirements of <a
68href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.  The
69value type of the edge iterator must be the same as the edge
70descriptor of the graph.
71
72<tr>
73<td><pre>boost::graph_traits&lt;G&gt;::edges_size_type</pre>
74The unsigned integer type used to represent the number of edges in the
75graph.
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:edges"><TT>edges(g)</TT></a></TD>
87<TD>Returns an iterator-range providing access to all
88     the edges in the graph <TT>g</TT>.<br>
89Return type: <TT>std::pair&lt;edge_iterator, edge_iterator&gt;</TT>
90</td>
91</TR>
92
93<tr>
94<TD><TT>num_edges(g)</TT></TD>
95<TD>Returns the number of edges in the graph <TT>g</TT>.<br>
96Return type: <TT>edges_size_type</TT>
97</td>
98</TR>
99
100<tr>
101<TD><TT>source(e, g)</TT></TD>
102<TD>
103Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i>
104represented by <TT>e</TT>.<br>
105Return type: <TT>vertex_descriptor</TT>
106</td>
107</tr>
108
109<tr>
110<TD><TT>target(e, g)</TT></TD>
111<TD>
112Returns the vertex descriptor for
113<i>v</i> of the edge <i>(u,v)</i> represented by  <TT>e</TT>.<br>
114Return type: <TT>vertex_descriptor</TT>
115</TD>
116</TR>
117
118</TABLE>
119
120
121<H3>Models</H3>
122
123<UL>
124<LI><a href="./adjacency_list.html"><TT>adjacency_list</TT></a></LI>
125<LI><a href="./edge_list.html"><TT>edge_list</TT></a></LI>
126</UL>
127
128
129<H3>Complexity guarantees</H3>
130
131The <TT>edges()</TT>, <TT>source()</TT>, and <TT>target()</TT> functions
132must all return in constant time.
133
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<P>
142<PRE>
143  template &lt;class G&gt;
144  struct EdgeListGraphConcept
145  {
146    typedef typename boost::graph_traits&lt;G&gt;::edge_iterator
147      edge_iterator;
148    void constraints() {
149      function_requires&lt; GraphConcept&lt;G&gt; &gt;();
150      function_requires&lt; MultiPassInputIteratorConcept&lt;edge_iterator&gt; &gt;();
151
152      p = edges(g);
153      E = num_edges(g);
154      e = *p.first;
155      u = source(e, g);
156      v = target(e, g);
157      const_constraints(g);
158    }
159    void const_constraints(const G&amp; g) {
160      p = edges(g);
161      E = num_edges(g);
162      e = *p.first;
163      u = source(e, g);
164      v = target(e, g);
165    }
166    std::pair&lt;edge_iterator,edge_iterator&gt; p;
167    typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
168    typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
169    typename boost::graph_traits&lt;G&gt;::edges_size_type E;
170    G g;
171  };
172</PRE>
173
174
175<br>
176<HR>
177<TABLE>
178<TR valign=top>
179<TD nowrap>Copyright &copy 2000-2001</TD><TD>
180<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
181</TD></TR></TABLE>
182
183</BODY>
184</HTML> 
Note: See TracBrowser for help on using the repository browser.