Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/BidirectionalGraph.html @ 29

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

updated boost from 1_33_1 to 1_34_1
File size: 4.6 KB
RevLine 
[29]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>Bidirectional</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>
20<A NAME="concept:BidirectionalGraph"></A>
21BidirectionalGraph
22</H2>
23
24<P>
25The BidirectionalGraph concept refines <a
26href="./IncidenceGraph.html">IncidenceGraph</a> and adds the
27requirement for efficient access to the in-edges of each vertex. This
28concept is separated from <a
29href="./IncidenceGraph.html">IncidenceGraph</a> because for directed
30graphs efficient access to in-edges typically requires more storage
31space, and many algorithms do not require access to in-edges.  For
32undirected graphs this is not an issue, since the <TT>in_edges()</TT>
33and <TT>out_edges()</TT> functions are the same, they both return the
34edges incident to the vertex.
35
36<H3>Refinement of</H3>
37
38<a href="./IncidenceGraph.html">IncidenceGraph</a>
39
40<h3>Notation</h3>
41
42<Table>
43<TR>
44<TD><tt>G</tt></TD>
45<TD>A type that is a model of Graph.</TD>
46</TR>
47
48<TR>
49<TD><tt>g</tt></TD>
50<TD>An object of type <tt>G</tt>.</TD>
51</TR>
52
53<TR>
54<TD><tt>v</tt></TD>
55<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
56</TR>
57
58</table>
59
60<H3>Associated Types</H3>
61
62<Table border>
63
64<tr>
65<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
66 This tag type must be convertible to <tt>bidirectional_graph_tag</tt>.
67</td>
68</tr>
69
70<TR>
71<TD><pre>boost::graph_traits&lt;G&gt;::in_edge_iterator</pre>
72An in-edge iterator for a vertex <i>v</i> provides access to the
73in-edges of <i>v</i>.  As such, the value type of an in-edge iterator
74is the edge descriptor type of its graph. An in-edge iterator must
75meet the requirements of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
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:in-edges"><TT>in_edges(v, g)</TT></a></TD>
87<TD>
88Returns an iterator-range providing access to the
89in-edges (for directed graphs) or incident edges (for
90undirected graphs) of vertex <TT>v</TT> in graph <TT>g</TT>.
91For both directed and undirected graphs, the target of
92an out-edge is required to be vertex <tt>v</tt> and the
93source is required to be a vertex that is adjacent to <tt>v</tt>.
94<br>
95Return type: <TT>std::pair&lt;in_edge_iterator, in_edge_iterator&gt;</TT>
96</TD>
97</TR>
98
99<tr>
100<TD><TT>in_degree(v, g)</TT></TD>
101<TD>
102Returns the number of in-edges (for directed graphs) or the
103number of incident edges (for undirected graphs) of vertex <TT>v</TT>
104in graph <TT>g</TT>.<br>
105Return type: <TT>degree_size_type</TT>
106</TD>
107</TR>
108
109<tr>
110<TD><TT>degree(v, g)</TT></TD>
111<TD>Returns the number of in-edges plus out-edges (for directed graphs) or the
112number of incident edges (for undirected graphs) of vertex <TT>v</TT>
113in graph <TT>g</TT>.<br>
114Return type: <TT>degree_size_type</TT>
115</TD>
116</TR>
117
118</Table>
119
120<H3>Models</H3>
121
122<ul>
123<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=bidirectionalS</tt></li>
124<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=undirectedS</tt></li>
125</ul>
126
127
128<H3>Complexity guarantees</H3>
129
130The <TT>in_edges()</TT> function is required to be constant time.  The
131<tt>in_degree()</tt> and <tt>degree()</tt> functions must be linear in
132the number of in-edges (for directed graphs) or incident edges (for
133undirected graphs).
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<PRE>
142  template &lt;class G&gt;
143  struct BidirectionalGraphConcept
144  {
145    typedef typename boost::graph_traits&lt;G&gt;::in_edge_iterator
146      in_edge_iterator;
147    void constraints() {
148      function_requires&lt; IncidenceGraphConcept&lt;G&gt; &gt;();
149      function_requires&lt; MultiPassInputIteratorConcept&lt;in_edge_iterator&gt; &gt;();
150
151      p = in_edges(v, g);
152      e = *p.first;
153      const_constraints(g);
154    }
155    void const_constraints(const G&amp; g) {
156      p = in_edges(v, g);
157      e = *p.first;
158    }
159    std::pair&lt;in_edge_iterator, in_edge_iterator&gt; p;
160    typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
161    typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
162    G g;
163  };
164</PRE>
165
166<br>
167<HR>
168<TABLE>
169<TR valign=top>
170<TD nowrap>Copyright &copy 2000-2001</TD><TD>
171<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
172</TD></TR></TABLE>
173
174</BODY>
175</HTML> 
Note: See TracBrowser for help on using the repository browser.