[ceph.git] / ceph / src / boost / libs / graph / doc / BidirectionalGraph.html

<HTML>
<!--
     Copyright (c) Jeremy Siek 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>Bidirectional</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>


<H2>
<A NAME="concept:BidirectionalGraph"></A>
BidirectionalGraph
</H2>

<P>
The BidirectionalGraph concept refines <a
href="./IncidenceGraph.html">IncidenceGraph</a> and adds the
requirement for efficient access to the in-edges of each vertex. This
concept is separated from <a
href="./IncidenceGraph.html">IncidenceGraph</a> because for directed
graphs efficient access to in-edges typically requires more storage
space, and many algorithms do not require access to in-edges.  For
undirected graphs this is not an issue, since the <TT>in_edges()</TT>
and <TT>out_edges()</TT> functions are the same, they both return the
edges incident to the vertex.

<H3>Refinement of</H3>

<a href="./IncidenceGraph.html">IncidenceGraph</a>

<h3>Notation</h3>

<Table>
<TR>
<TD><tt>G</tt></TD>
<TD>A type that is a model of Graph.</TD>
</TR>

<TR>
<TD><tt>g</tt></TD>
<TD>An object of type <tt>G</tt>.</TD>
</TR>

<TR>
<TD><tt>v</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
</TR>

</table>

<H3>Associated Types</H3>

<Table border>

<tr>
<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
 This tag type must be convertible to <tt>bidirectional_graph_tag</tt>.
</td>
</tr>

<TR>
<TD><pre>boost::graph_traits&lt;G&gt;::in_edge_iterator</pre>
An in-edge iterator for a vertex <i>v</i> provides access to the
in-edges of <i>v</i>.  As such, the value type of an in-edge iterator
is the edge descriptor type of its graph. An in-edge iterator must
meet the requirements of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
</TD>
</TR>

</Table>

<h3>Valid Expressions</h3>

<Table border>

<tr>
<td><a name="sec:in-edges"><TT>in_edges(v, g)</TT></a></TD>
<TD>
Returns an iterator-range providing access to the
in-edges (for directed graphs) or incident edges (for
undirected graphs) of vertex <TT>v</TT> in graph <TT>g</TT>.
For both directed and undirected graphs, the target of
an out-edge is required to be vertex <tt>v</tt> and the
source is required to be a vertex that is adjacent to <tt>v</tt>.
<br>
Return type: <TT>std::pair&lt;in_edge_iterator, in_edge_iterator&gt;</TT>
</TD>
</TR>

<tr>
<TD><TT>in_degree(v, g)</TT></TD>
<TD>
Returns the number of in-edges (for directed graphs) or the
number of incident edges (for undirected graphs) of vertex <TT>v</TT>
in graph <TT>g</TT>.<br>
Return type: <TT>degree_size_type</TT>
</TD>
</TR>

<tr>
<TD><TT>degree(v, g)</TT></TD>
<TD>Returns the number of in-edges plus out-edges (for directed graphs) or the
number of incident edges (for undirected graphs) of vertex <TT>v</TT>
in graph <TT>g</TT>.<br>
Return type: <TT>degree_size_type</TT>
</TD>
</TR>

</Table>

<H3>Models</H3>

<ul>
<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=bidirectionalS</tt></li>
<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=undirectedS</tt></li>
</ul>


<H3>Complexity guarantees</H3>

The <TT>in_edges()</TT> function is required to be constant time.  The
<tt>in_degree()</tt> and <tt>degree()</tt> functions must be linear in
the number of in-edges (for directed graphs) or incident edges (for
undirected graphs).

<H3>See Also</H3>

<a href="./graph_concepts.html">Graph concepts</a>

<H3>Concept Checking Class</H3>

<PRE>
  template &lt;class G&gt;
  struct BidirectionalGraphConcept
  {
    typedef typename boost::graph_traits&lt;G&gt;::in_edge_iterator
      in_edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept&lt;G&gt; ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;in_edge_iterator&gt; ));

      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G&amp; g) {
      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
    }
    std::pair&lt;in_edge_iterator, in_edge_iterator&gt; p;
    typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
    typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
    typename boost::graph_traits&lt;G&gt;::degree_size_type n;
    G g;
  };
</PRE>

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 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>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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>
	21	BidirectionalGraph
	22	</H2>
	23
	24	<P>
	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.
	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<G>::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<G>::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<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>.
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>
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>.
94	<br>
95	Return type: <TT>std::pair<in_edge_iterator, in_edge_iterator></TT>
96	</TD>
97	</TR>
98
99	<tr>
100	<TD><TT>in_degree(v, g)</TT></TD>
101	<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>
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
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>
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
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
133	undirected 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 <class G>
143	struct BidirectionalGraphConcept
144	{
145	typedef typename boost::graph_traits<G>::in_edge_iterator
146	in_edge_iterator;
147	void constraints() {
148	BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
149	BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> ));
150
151	p = in_edges(v, g);
152	n = in_degree(v, g);
153	n = degree(v, g);
154	e = *p.first;
155	const_constraints(g);
156	}
157	void const_constraints(const G& g) {
158	p = in_edges(v, g);
159	n = in_degree(v, g);
160	n = degree(v, g);
161	e = *p.first;
162	}
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;
167	G g;
168	};
169	</PRE>
170
171	<br>
172	<HR>
173	<TABLE>
174	<TR valign=top>
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>)
177	</TD></TR></TABLE>
178
179	</BODY>
180	</HTML>