Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/IncidenceGraph.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 18 years ago

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