Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

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

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