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