Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/IncidenceGraph.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: 5.5 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>IncidenceGraph</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<H1><A NAME="concept:IncidenceGraph"></A>
19IncidenceGraph
20</H1>
21
22The IncidenceGraph concept provides an interface for
23efficient access to the out-edges of each vertex in the graph.
24
25
26<H3>Refinement of</H3>
27
28<a href="./Graph.html">Graph</a>
29
30<h3>Notation</h3>
31
32<Table>
33<TR>
34<TD><tt>G</tt></TD>
35<TD>A type that is a model of IncidenceGraph.</TD>
36</TR>
37
38<TR>
39<TD><tt>g</tt></TD>
40<TD>An object of type <tt>G</tt>.</TD>
41</TR>
42
43<TR>
44<TD><tt>e</tt></TD>
45<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
46</TR>
47
48<TR>
49<TD><tt>u, v</tt></TD>
50<TD>Are objects of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
51</TR>
52
53</table>
54
55<H3>Associated Types</H3>
56
57<Table border>
58
59<tr>
60<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
61 This tag type must be convertible to <tt>incidence_graph_tag</tt>.
62</td>
63</tr>
64
65
66<TR>
67<TD>
68<pre>boost::graph_traits&lt;G&gt;::out_edge_iterator</pre>
69An out-edge iterator for a vertex <i>v</i> provides access to the
70out-edges of the vertex.  As such, the value type of an out-edge
71iterator is the edge descriptor type of its graph. An out-edge
72iterator must meet the requirements of <a
73href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
74</TD>
75</TR>
76
77<TR>
78<TD><pre>boost::graph_traits&lt;G&gt;::degree_size_type</pre>
79The unsigned intergral type used for representing the number
80out-edges or incident edges of a vertex.
81</TD>
82</TR>
83
84</table>
85
86<h3>Valid Expressions</h3>
87
88<Table border>
89
90<tr>
91<td><a name="sec:source"><TT>source(e,&nbsp;g)</TT></a></TD>
92<TD>Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br>
93Return type: <TT>vertex_descriptor</TT>
94</TD>
95</TR>
96
97
98<tr>
99<td><a name="sec:target"><TT>target(e,&nbsp;g)</TT></a></TD>
100<TD>Returns the vertex descriptor for <i>v</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br>
101Return type: <TT>vertex_descriptor</TT>
102</td></tr>
103
104<tr>
105<td><a name="sec:out-edges"><TT>out_edges(u,&nbsp;g)</TT></a></TD>
106<TD>Returns an iterator-range providing access to the out-edges (for
107directed graphs) or incident edges (for undirected graphs) of vertex
108<TT>u</TT> in graph <TT>g</TT>.  The source vertex of an edge obtained
109via an out edge iterator is guaranteed (for both directed and
110undirected graphs) to be the vertex <tt>u</tt> used in the call to
111<tt>out_edges(u, g)</tt> and the target vertex must the a vertex
112adjacent to <tt>u</tt>.<a href="#1">[1]</a>
113<br>
114Return type: <TT>std::pair&lt;out_edge_iterator, out_edge_iterator&gt;</TT>
115</TD>
116</tr>
117
118<tr>
119<TD><TT>out_degree(u,&nbsp;g)</TT></TD>
120<TD>Returns the number of out-edges (for directed graphs) or the
121number of incident edges (for undirected graphs) of vertex <TT>u</TT>
122in graph <TT>g</TT>.<br>
123Return type: <TT>degree_size_type</TT>
124</TD>
125</TR>
126
127</TABLE>
128
129<P>
130
131<H3>Complexity guarantees</H3>
132
133<P>
134The <TT>source()</TT>, <TT>target()</TT>, and <TT>out_edges()</TT>
135functions must all be constant time. The <tt>out_degree()</tt>
136function must be linear in the number of out-edges.
137
138<P>
139
140<H3>See Also</H3>
141
142<a href="./graph_concepts.html">Graph concepts</a>
143
144<H3>Notes</H3>
145
146<a name="1">[1]</a> For undirected graphs, the edge <tt>(u,v)</tt> is
147the same as edge <tt>(v,u)</tt>, so without some extra guarantee an
148implementation would be free use any ordering for the pair of vertices
149in an out-edge. For example, if you call <tt>out_edges(u, g)</tt>, and
150<tt>v</tt> is one of the vertices adjacent to <tt>u</tt>, then the
151implementation would be free to return <tt>(v,u)</tt> as an out-edge
152which would be non-intuitive and cause trouble for algorithms.
153Therefore, the extra requirement is added that the out-edge connecting
154<tt>u</tt> and <tt>v</tt> must be given as <tt>(u,v)</tt> and not
155<tt>(v,u)</tt>.
156
157<H3>Concept Checking Class</H3>
158
159<PRE>
160  template &lt;class G&gt;
161  struct IncidenceGraphConcept
162  {
163    typedef typename boost::graph_traits&lt;G&gt;::out_edge_iterator out_edge_iterator;
164    void constraints() {
165      function_requires&lt; GraphConcept&lt;G&gt; &gt;();
166      function_requires&lt; MultiPassInputIteratorConcept&lt;out_edge_iterator&gt; &gt;();
167
168      p = out_edges(u, g);
169      e = *p.first;
170      u = source(e, g);
171      v = target(e, g);
172    }
173    void const_constraints(const G&amp; g) {
174      p = out_edges(u, g);
175      e = *p.first;
176      u = source(e, g);
177      v = target(e, g);
178    }
179    std::pair&lt;out_edge_iterator, out_edge_iterator&gt; p;
180    typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
181    typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
182    G g;
183  };
184</PRE>
185
186
187<br>
188<HR>
189<TABLE>
190<TR valign=top>
191<TD nowrap>Copyright &copy 2000-2001</TD><TD>
192<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
193Indiana University (<A
194HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
195<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
196<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
197Indiana University (<A
198HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
199</TD></TR></TABLE>
200
201</BODY>
202</HTML> 
Note: See TracBrowser for help on using the repository browser.