3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Bidirectional
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
20 <A NAME=
"concept:BidirectionalGraph"></A>
25 The BidirectionalGraph concept refines
<a
26 href=
"./IncidenceGraph.html">IncidenceGraph
</a> and adds the
27 requirement for efficient access to the in-edges of each vertex. This
28 concept is separated from
<a
29 href=
"./IncidenceGraph.html">IncidenceGraph
</a> because for directed
30 graphs efficient access to in-edges typically requires more storage
31 space, and many algorithms do not require access to in-edges. For
32 undirected graphs this is not an issue, since the
<TT>in_edges()
</TT>
33 and
<TT>out_edges()
</TT> functions are the same, they both return the
34 edges incident to the vertex.
36 <H3>Refinement of
</H3>
38 <a href=
"./IncidenceGraph.html">IncidenceGraph
</a>
45 <TD>A type that is a model of Graph.
</TD>
50 <TD>An object of type
<tt>G
</tt>.
</TD>
55 <TD>An object of type
<tt>boost::graph_traits
<G
>::vertex_descriptor
</tt>.
</TD>
60 <H3>Associated Types
</H3>
65 <td><tt>boost::graph_traits
<G
>::traversal_category
</tt><br><br>
66 This tag type must be convertible to
<tt>bidirectional_graph_tag
</tt>.
71 <TD><pre>boost::graph_traits
<G
>::in_edge_iterator
</pre>
72 An in-edge iterator for a vertex
<i>v
</i> provides access to the
73 in-edges of
<i>v
</i>. As such, the value type of an in-edge iterator
74 is the edge descriptor type of its graph. An in-edge iterator must
75 meet the requirements of
<a href=
"../../utility/MultiPassInputIterator.html">MultiPassInputIterator
</a>.
81 <h3>Valid Expressions
</h3>
86 <td><a name=
"sec:in-edges"><TT>in_edges(v, g)
</TT></a></TD>
88 Returns an iterator-range providing access to the
89 in-edges (for directed graphs) or incident edges (for
90 undirected graphs) of vertex
<TT>v
</TT> in graph
<TT>g
</TT>.
91 For both directed and undirected graphs, the target of
92 an out-edge is required to be vertex
<tt>v
</tt> and the
93 source is required to be a vertex that is adjacent to
<tt>v
</tt>.
95 Return type:
<TT>std::pair
<in_edge_iterator, in_edge_iterator
></TT>
100 <TD><TT>in_degree(v, g)
</TT></TD>
102 Returns the number of in-edges (for directed graphs) or the
103 number of incident edges (for undirected graphs) of vertex
<TT>v
</TT>
104 in graph
<TT>g
</TT>.
<br>
105 Return type:
<TT>degree_size_type
</TT>
110 <TD><TT>degree(v, g)
</TT></TD>
111 <TD>Returns the number of in-edges plus out-edges (for directed graphs) or the
112 number of incident edges (for undirected graphs) of vertex
<TT>v
</TT>
113 in graph
<TT>g
</TT>.
<br>
114 Return type:
<TT>degree_size_type
</TT>
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>
128 <H3>Complexity guarantees
</H3>
130 The
<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
132 the number of in-edges (for directed graphs) or incident edges (for
137 <a href=
"./graph_concepts.html">Graph concepts
</a>
139 <H3>Concept Checking Class
</H3>
142 template
<class G
>
143 struct BidirectionalGraphConcept
145 typedef typename boost::graph_traits
<G
>::in_edge_iterator
148 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept
<G
> ));
149 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept
<in_edge_iterator
> ));
155 const_constraints(g);
157 void const_constraints(const G
& g) {
163 std::pair
<in_edge_iterator, in_edge_iterator
> p;
164 typename boost::graph_traits
<G
>::vertex_descriptor v;
165 typename boost::graph_traits
<G
>::edge_descriptor e;
166 typename boost::graph_traits
<G
>::degree_size_type n;
175 <TD nowrap
>Copyright
© 2000-
2001</TD><TD>
176 <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>)