[ceph.git] / ceph / src / boost / libs / graph / doc / filtered_graph.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>Boost Graph Library: Filtered Graph</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>


<H1><A NAME="sec:filtered-graph-class"></A>
<pre>
filtered_graph&lt;Graph, EdgePredicate, VertexPredicate&gt;
</pre>
</H1>


<P>
The <tt>filtered_graph</tt> class template is an adaptor that creates
a filtered view of a graph. The predicate function objects determine
which edges and vertices of the original graph will show up in the
filtered graph.  If the edge predicate returns <tt>true</tt> for an
edge then it shows up in the filtered graph, and if the predicate
returns <tt>false</tt> then the edge does not appear in the filtered
graph.  Likewise for vertices. The <tt>filtered_graph</tt> class does
not create a copy of the original graph, but uses a reference to the
original graph. The lifetime of the original graph must extend past
any use of the filtered graph. The filtered graph does not change the
structure of the original graph, though vertex and edge properties of
the original graph can be changed through property maps of the
filtered graph. Vertex and edge descriptors of the filtered graph are
the same as, and interchangeable with, the vertex and edge descriptors
of the original graph.

<P>The <a href="#num_vertices"><tt>num_vertices</tt></a> and <a
href="#num_edges"><tt>num_edges</tt></a> functions do not filter
before returning results, so they return the number of vertices or
edges in the underlying graph, unfiltered <a href="#2">[2]</a>.

<H3>Example</H3>

<P>
In this example we will filter a graph's edges based on edge
weight. We will keep all edges with positive edge weight.
First, we create a predicate function object.

<PRE>
template &lt;typename EdgeWeightMap&gt;
struct positive_edge_weight {
  positive_edge_weight() { }
  positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }
  template &lt;typename Edge&gt;
  bool operator()(const Edge& e) const {
    return 0 &lt; get(m_weight, e);
  }
  EdgeWeightMap m_weight;
};
</PRE>

Now we create a graph and print out the filtered graph.
<pre>
int main()
{
  using namespace boost;
  
  typedef adjacency_list&lt;vecS, vecS, directedS,
    no_property, property&lt;edge_weight_t, int&gt; &gt; Graph;
  typedef property_map&lt;Graph, edge_weight_t&gt;::type EdgeWeightMap;

  enum { A, B, C, D, E, N };
  const char* name = "ABCDE";
  Graph g(N);
  add_edge(A, B, 2, g);
  add_edge(A, C, 0, g);
  add_edge(C, D, 1, g);
  add_edge(C, E, 0, g);
  add_edge(D, B, 3, g);
  add_edge(E, C, 0, g);
  
  positive_edge_weight&lt;EdgeWeightMap&gt; filter(get(edge_weight, g));
  filtered_graph&lt;Graph, positive_edge_weight&lt;EdgeWeightMap&gt; &gt;
    fg(g, filter);

  std::cout &lt;&lt; "filtered edge set: ";
  print_edges(fg, name);

  std::cout &lt;&lt; "filtered out-edges:" &lt;&lt; std::endl;
  print_graph(fg, name);
  
  return 0;
}
</pre>
The output is:
<PRE>
filtered edge set: (A,B) (C,D) (D,B) 
filtered out-edges:
A --> B 
B --> 
C --> D 
D --> B 
E --> 
</PRE>

<P>

<H3>Template Parameters</H3>

<P>
<TABLE border>
<TR>
<th>Parameter</th><th>Description</th><th>Default</th>
</tr>

<TR><TD><TT>Graph</TT></TD>
<TD>The underlying graph type.</TD>
<TD>&nbsp;</TD>
</TR>

<TR>
<TD><TT>EdgePredicate</TT></TD> <TD>A function object that selects
which edges from the original graph will appear in the filtered
graph. The function object must model <a
href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
argument type for the function object must be the edge descriptor type
of the graph. Also, the predicate must be <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
<TD>&nbsp;</TD>
</TR>

<TR>
<TD><TT>VertexPredicate</TT></TD>
<TD>A function object that selects
which vertices from the original graph will appear in the filtered
graph. The function object must model <a
href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
argument type for the function object must be the vertex descriptor type
of the graph. Also, the predicate must be <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
<TD><TT>keep_all</TT></TD>
</TR>

</TABLE>
<P>

<H3>Model of</H3>

<P>
This depends on the underlying graph type. If the underlying
<tt>Graph</tt> type models <a
href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and <a
href="./PropertyGraph.html">PropertyGraph</a> then so does the
filtered graph. If the underlying <tt>Graph</tt> type models fewer or
smaller concepts than these, then so does the filtered graph.

<P>

<H3>Where Defined</H3>

<P>
<a href="../../../boost/graph/filtered_graph.hpp"><TT>boost/graph/filtered_graph.hpp</TT></a>

<P>

<H2>Associated Types</H2>

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::vertex_descriptor</tt>
<br><br>

The type for the vertex descriptors associated with the
<TT>filtered_graph</TT>, which is the same type as the
<tt>vertex_descriptor</tt> for the original <tt>Graph</tt>.


<hr>

<tt>graph_traits&lt;filtered_graph&gt;::edge_descriptor</tt><br>
<br><br>
The type for the edge descriptors associated with the
<TT>filtered_graph</TT>, which is the same type as the
<tt>edge_descriptor</tt> for the original <tt>Graph</tt>.

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::vertex_iterator</tt><br>
<br><br>
The type for the iterators returned by <TT>vertices()</TT>,
which is:
<pre>
<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;VertexPredicate, graph_traits&lt;Graph&gt;::vertex_iterator&gt;
</pre>
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.


<hr>

<tt>graph_traits&lt;filtered_graph&gt;::edge_iterator</tt>
<br><br>
The type for the iterators returned by <TT>edges()</TT>, which is:
<pre>
<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;EdgePredicate, graph_traits&lt;Graph&gt;::edge_iterator&gt;
</pre>
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.

<hr>


<tt>graph_traits&lt;filtered_graph&gt;::out_edge_iterator</tt>
<br><br>
The type for the iterators returned by <TT>out_edges()</TT>, which is:
<pre>
<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a>&lt;EdgePredicate, graph_traits&lt;Graph&gt;::out_edge_iterator&gt;
</pre>
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.


<hr>

<tt>graph_traits&lt;filtered_graph&gt;::adjacency_iterator</tt>
<br><br>
The type for the iterators returned by <TT>adjacent_vertices()</TT>.

The <tt>adjacency_iterator</tt> models the same iterator concept as
<tt>out_edge_iterator</tt>.

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::directed_category</tt><br>
<br><br>
Provides information about whether the graph is directed
(<TT>directed_tag</TT>) or undirected (<TT>undirected_tag</TT>).

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::edge_parallel_category</tt><br>
<br><br>
This describes whether the graph class allows the insertion of
parallel edges (edges with the same source and target). The two tags
are <TT>allow_parallel_edge_tag</TT> and
<TT>disallow_parallel_edge_tag</TT>.

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::vertices_size_type</tt>
<br><br>
The type used for dealing with the number of vertices in the graph.

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::edges_size_type</tt>
<br><br>
The type used for dealing with the number of edges in the graph.

<hr>

<tt>graph_traits&lt;filtered_graph&gt;::degree_size_type</tt>
<br><br>
The type used for dealing with the number of edges incident to a vertex
in the graph.

<hr>

<tt>property_map&lt;filtered_graph, Property&gt;::type</tt><br>
and<br>
<tt>property_map&lt;filtered_graph, Property&gt;::const_type</tt>
<br><br>
The property map type for vertex or edge properties in the graph. 
The same property maps from the adapted graph are available
in the filtered graph.

<hr>

<H2>Member Functions</H2>

<hr>

<pre>
filtered_graph(Graph&amp;&nbsp;g, EdgePredicate&nbsp;ep, VertexPredicate&nbsp;vp)
</pre>
Create a filtered graph based on the graph <i>g</i> and the
edge filter <i>ep</i> and vertex filter <i>vp</i>.

<hr>

<pre>
filtered_graph(Graph&amp;&nbsp;g, EdgePredicate&nbsp;ep)
</pre>
Create a filtered graph based on the graph <i>g</i> and the
edge filter <i>ep</i>. All vertices from the original graph
are retained.

<hr>

filtered_graph(const&nbsp;filtered_graph&amp;&nbsp;x)
</pre>
This creates a filtered graph for the same underlying graph
as <i>x</i>. Anotherwords, this is a shallow copy.

<hr>

<pre>
filtered_graph&amp; operator=(const&nbsp;filtered_graph&amp;&nbsp;x)
</pre>
This creates a filtered graph for the same underlying graph
as <i>x</i>. Anotherwords, this is a shallow copy.

<hr>

<P>

<H2>Non-Member Functions</H2>

<h4>Structure Access</h4>

<hr>

<pre>
std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
vertices(const filtered_graph&amp; g)
</pre>
Returns an iterator-range providing access to the vertex set of graph
<tt>g</tt>.

<hr>

<pre>
std::pair&lt;edge_iterator,&nbsp;edge_iterator&gt;
edges(const filtered_graph&amp; g)
</pre>
Returns an iterator-range providing access to the edge set of graph
<tt>g</tt>.

<hr>

<pre>
std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
adjacent_vertices(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns an iterator-range providing access to the vertices adjacent to
vertex <tt>u</tt> in graph <tt>g</tt>.

<hr>


<pre>
std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
out_edges(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns an iterator-range providing access to the out-edges of vertex
<tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
iterator-range provides access to all edges incident on vertex
<tt>u</tt>. For both directed and undirected graphs, for an out-edge
<tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.

<hr>

<pre>
std::pair&lt;in_edge_iterator,&nbsp;in_edge_iterator&gt;
in_edges(vertex_descriptor&nbsp;v, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns an iterator-range providing access to the in-edges of vertex
<tt>v</tt> in graph <tt>g</tt>.  For an in-edge <tt>e</tt>,
<tt>target(e, g) == v</tt> and <tt>source(e, g) == u</tt> for some
vertex <tt>u</tt> that is adjacent to <tt>v</tt>, whether the graph is
directed or undirected.

<hr>

<pre>
vertex_descriptor
source(edge_descriptor&nbsp;e, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns the source vertex of edge <tt>e</tt>.

<hr>

<pre>
vertex_descriptor
target(edge_descriptor&nbsp;e, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns the target vertex of edge <tt>e</tt>.

<hr>

<pre>
degree_size_type
out_degree(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns the number of edges leaving vertex <tt>u</tt>.

<hr>

<pre>
degree_size_type
in_degree(vertex_descriptor&nbsp;u, const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns the number of edges entering vertex <tt>u</tt>. 

<hr>

<pre><a name="num_vertices"></a>
vertices_size_type
num_vertices(const filtered_graph&amp; g)
</pre>
Returns the number of vertices in the underlying graph <a href="#2">[2]</a>. 

<hr>

<pre><a name="num_edges"></a>
edges_size_type
num_edges(const filtered_graph&amp; g)
</pre>
Returns the number of edges in the underlying graph <a href="#2">[2]</a>.

<hr>

<pre>
std::pair&lt;edge_descriptor, bool&gt;
edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
     const&nbsp;filtered_graph&amp;&nbsp;g)
</pre>
Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in
graph <tt>g</tt>.

<hr>

<pre>
template &lt;typename G, typename EP, typename VP&gt;
std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
edge_range(vertex_descriptor u, vertex_descriptor v,
	   const filtered_graph&amp; g)
</pre>
Returns a pair of out-edge iterators that give the range for all the
parallel edges from <tt>u</tt> to <tt>v</tt>. This function only works
when the underlying graph supports <tt>edge_range</tt>, which requires
that it sorts its out edges according to target vertex and allows
parallel edges. The <tt>adjacency_list</tt> class with
<tt>OutEdgeList=multisetS</tt> is an example of such a graph.


<hr>

<h4>Property Map Access</h4>

<hr>

<pre>
template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
property_map&lt;filtered_graph, PropertyTag&gt;::type
get(PropertyTag, filtered_graph&amp; g)

template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
property_map&lt;filtered_graph, Tag&gt;::const_type
get(PropertyTag, const filtered_graph&amp; g)
</pre>
Returns the property map object for the vertex property specified by
<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
properties specified in the graph's <TT>VertexProperty</TT> template
argument.

<hr>

<pre>
template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X&gt;
typename property_traits&lt;property_map&lt;filtered_graph, PropertyTag&gt;::const_type&gt::value_type
get(PropertyTag, const filtered_graph&amp; g, X x)
</pre>
This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
a vertex or edge descriptor.
<hr>

<pre>
template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value&gt;
void
put(PropertyTag, const filtered_graph&amp; g, X x, const Value& value)
</pre>
This sets the property value for <tt>x</tt> to
<tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
<tt>Value</tt> must be convertible to
<tt>typename property_traits&lt;property_map&lt;filtered_graph, PropertyTag&gt;::type&gt::value_type</tt>

<hr>

<h3>See Also</h3>

<a href="./property_map.html"><tt>property_map</tt></a>,
<a href="./graph_traits.html"><tt>graph_traits</tt></a>

<h3>Notes</h3>

<p>
<a name="1">[1]</a> The reason for requiring <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
Constructible</a> in the <tt>EdgePredicate</tt> and
<tt>VertexPredicate</tt> types is that these predicates are stored
by-value (for performance reasons) in the filter iterator adaptor, and
iterators are required to be Default Constructible by the C++
Standard.

<p> <a name="2">[2]</a> It would be nicer to return the number of
vertices (or edges) remaining after the filter has been applied, but
this has two problems. The first is that it would take longer to
calculate, and the second is that it would interact badly with the
underlying vertex/edge index mappings. The index mapping would no
longer fall in the range <tt>[0,num_vertices(g))</tt> (resp. <tt>[0,
num_edges(g))</tt>) which is assumed in many of the algorithms. 


<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>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@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>Boost Graph Library: Filtered Graph</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
	20	<H1><A NAME="sec:filtered-graph-class"></A>
	21	<pre>
	22	filtered_graph<Graph, EdgePredicate, VertexPredicate>
	23	</pre>
	24	</H1>
	25
	26
	27	<P>
	28	The <tt>filtered_graph</tt> class template is an adaptor that creates
	29	a filtered view of a graph. The predicate function objects determine
	30	which edges and vertices of the original graph will show up in the
	31	filtered graph. If the edge predicate returns <tt>true</tt> for an
	32	edge then it shows up in the filtered graph, and if the predicate
	33	returns <tt>false</tt> then the edge does not appear in the filtered
	34	graph. Likewise for vertices. The <tt>filtered_graph</tt> class does
	35	not create a copy of the original graph, but uses a reference to the
	36	original graph. The lifetime of the original graph must extend past
	37	any use of the filtered graph. The filtered graph does not change the
	38	structure of the original graph, though vertex and edge properties of
	39	the original graph can be changed through property maps of the
	40	filtered graph. Vertex and edge descriptors of the filtered graph are
	41	the same as, and interchangeable with, the vertex and edge descriptors
	42	of the original graph.
	43
	44	<P>The <a href="#num_vertices"><tt>num_vertices</tt></a> and <a
	45	href="#num_edges"><tt>num_edges</tt></a> functions do not filter
	46	before returning results, so they return the number of vertices or
	47	edges in the underlying graph, unfiltered <a href="#2">[2]</a>.
	48
	49	<H3>Example</H3>
	50
	51	<P>
	52	In this example we will filter a graph's edges based on edge
	53	weight. We will keep all edges with positive edge weight.
	54	First, we create a predicate function object.
	55
	56	<PRE>
	57	template <typename EdgeWeightMap>
	58	struct positive_edge_weight {
	59	positive_edge_weight() { }
	60	positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }
	61	template <typename Edge>
	62	bool operator()(const Edge& e) const {
	63	return 0 < get(m_weight, e);
	64	}
65	EdgeWeightMap m_weight;
66	};
67	</PRE>
68
69	Now we create a graph and print out the filtered graph.
70	<pre>
71	int main()
72	{
73	using namespace boost;
74
75	typedef adjacency_list<vecS, vecS, directedS,
76	no_property, property<edge_weight_t, int> > Graph;
77	typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap;
78
79	enum { A, B, C, D, E, N };
80	const char* name = "ABCDE";
81	Graph g(N);
82	add_edge(A, B, 2, g);
83	add_edge(A, C, 0, g);
84	add_edge(C, D, 1, g);
85	add_edge(C, E, 0, g);
86	add_edge(D, B, 3, g);
87	add_edge(E, C, 0, g);
88
89	positive_edge_weight<EdgeWeightMap> filter(get(edge_weight, g));
90	filtered_graph<Graph, positive_edge_weight<EdgeWeightMap> >
91	fg(g, filter);
92
93	std::cout << "filtered edge set: ";
94	print_edges(fg, name);
95
96	std::cout << "filtered out-edges:" << std::endl;
97	print_graph(fg, name);
98
99	return 0;
100	}
101	</pre>
102	The output is:
103	<PRE>
104	filtered edge set: (A,B) (C,D) (D,B)
105	filtered out-edges:
106	A --> B
107	B -->
108	C --> D
109	D --> B
110	E -->
111	</PRE>
112
113	<P>
114
115	<H3>Template Parameters</H3>
116
117	<P>
118	<TABLE border>
119	<TR>
120	<th>Parameter</th><th>Description</th><th>Default</th>
121	</tr>
122
123	<TR><TD><TT>Graph</TT></TD>
124	<TD>The underlying graph type.</TD>
125	<TD> </TD>
126	</TR>
127
128	<TR>
129	<TD><TT>EdgePredicate</TT></TD> <TD>A function object that selects
130	which edges from the original graph will appear in the filtered
131	graph. The function object must model <a
132	href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
133	argument type for the function object must be the edge descriptor type
134	of the graph. Also, the predicate must be <a
135	href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
136	<TD> </TD>
137	</TR>
138
139	<TR>
140	<TD><TT>VertexPredicate</TT></TD>
141	<TD>A function object that selects
142	which vertices from the original graph will appear in the filtered
143	graph. The function object must model <a
144	href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>. The
145	argument type for the function object must be the vertex descriptor type
146	of the graph. Also, the predicate must be <a
147	href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
148	<TD><TT>keep_all</TT></TD>
149	</TR>
150
151	</TABLE>
152	<P>
153
154	<H3>Model of</H3>
155
156	<P>
157	This depends on the underlying graph type. If the underlying
158	<tt>Graph</tt> type models <a
159	href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and <a
160	href="./PropertyGraph.html">PropertyGraph</a> then so does the
161	filtered graph. If the underlying <tt>Graph</tt> type models fewer or
162	smaller concepts than these, then so does the filtered graph.
163
164	<P>
165
166	<H3>Where Defined</H3>
167
168	<P>
169	<a href="../../../boost/graph/filtered_graph.hpp"><TT>boost/graph/filtered_graph.hpp</TT></a>
170
171	<P>
172
173	<H2>Associated Types</H2>
174
175	<hr>
176
177	<tt>graph_traits<filtered_graph>::vertex_descriptor</tt>
178	<br><br>
179
180	The type for the vertex descriptors associated with the
181	<TT>filtered_graph</TT>, which is the same type as the
182	<tt>vertex_descriptor</tt> for the original <tt>Graph</tt>.
183
184
185	<hr>
186
187	<tt>graph_traits<filtered_graph>::edge_descriptor</tt><br>
188	<br><br>
189	The type for the edge descriptors associated with the
190	<TT>filtered_graph</TT>, which is the same type as the
191	<tt>edge_descriptor</tt> for the original <tt>Graph</tt>.
192
193	<hr>
194
195	<tt>graph_traits<filtered_graph>::vertex_iterator</tt><br>
196	<br><br>
197	The type for the iterators returned by <TT>vertices()</TT>,
198	which is:
199	<pre>
200	<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><VertexPredicate, graph_traits<Graph>::vertex_iterator>
201	</pre>
202	The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
203
204
205	<hr>
206
207	<tt>graph_traits<filtered_graph>::edge_iterator</tt>
208	<br><br>
209	The type for the iterators returned by <TT>edges()</TT>, which is:
210	<pre>
211	<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><EdgePredicate, graph_traits<Graph>::edge_iterator>
212	</pre>
213	The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
214
215	<hr>
216
217
218	<tt>graph_traits<filtered_graph>::out_edge_iterator</tt>
219	<br><br>
220	The type for the iterators returned by <TT>out_edges()</TT>, which is:
221	<pre>
222	<a href="../../iterator/doc/filter_iterator.html">filter_iterator</a><EdgePredicate, graph_traits<Graph>::out_edge_iterator>
223	</pre>
224	The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
225
226
227	<hr>
228
229	<tt>graph_traits<filtered_graph>::adjacency_iterator</tt>
230	<br><br>
231	The type for the iterators returned by <TT>adjacent_vertices()</TT>.
232
233	The <tt>adjacency_iterator</tt> models the same iterator concept as
234	<tt>out_edge_iterator</tt>.
235
236	<hr>
237
238	<tt>graph_traits<filtered_graph>::directed_category</tt><br>
239	<br><br>
240	Provides information about whether the graph is directed
241	(<TT>directed_tag</TT>) or undirected (<TT>undirected_tag</TT>).
242
243	<hr>
244
245	<tt>graph_traits<filtered_graph>::edge_parallel_category</tt><br>
246	<br><br>
247	This describes whether the graph class allows the insertion of
248	parallel edges (edges with the same source and target). The two tags
249	are <TT>allow_parallel_edge_tag</TT> and
250	<TT>disallow_parallel_edge_tag</TT>.
251
252	<hr>
253
254	<tt>graph_traits<filtered_graph>::vertices_size_type</tt>
255	<br><br>
256	The type used for dealing with the number of vertices in the graph.
257
258	<hr>
259
260	<tt>graph_traits<filtered_graph>::edges_size_type</tt>
261	<br><br>
262	The type used for dealing with the number of edges in the graph.
263
264	<hr>
265
266	<tt>graph_traits<filtered_graph>::degree_size_type</tt>
267	<br><br>
268	The type used for dealing with the number of edges incident to a vertex
269	in the graph.
270
271	<hr>
272
273	<tt>property_map<filtered_graph, Property>::type</tt><br>
274	and<br>
275	<tt>property_map<filtered_graph, Property>::const_type</tt>
276	<br><br>
277	The property map type for vertex or edge properties in the graph.
278	The same property maps from the adapted graph are available
279	in the filtered graph.
280
281	<hr>
282
283	<H2>Member Functions</H2>
284
285	<hr>
286
287	<pre>
288	filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)
289	</pre>
290	Create a filtered graph based on the graph <i>g</i> and the
291	edge filter <i>ep</i> and vertex filter <i>vp</i>.
292
293	<hr>
294
295	<pre>
296	filtered_graph(Graph& g, EdgePredicate ep)
297	</pre>
298	Create a filtered graph based on the graph <i>g</i> and the
299	edge filter <i>ep</i>. All vertices from the original graph
300	are retained.
301
302	<hr>
303
304	filtered_graph(const filtered_graph& x)
305	</pre>
306	This creates a filtered graph for the same underlying graph
307	as <i>x</i>. Anotherwords, this is a shallow copy.
308
309	<hr>
310
311	<pre>
312	filtered_graph& operator=(const filtered_graph& x)
313	</pre>
314	This creates a filtered graph for the same underlying graph
315	as <i>x</i>. Anotherwords, this is a shallow copy.
316
317	<hr>
318
319	<P>
320
321	<H2>Non-Member Functions</H2>
322
323	<h4>Structure Access</h4>
324
325	<hr>
326
327	<pre>
328	std::pair<vertex_iterator, vertex_iterator>
329	vertices(const filtered_graph& g)
330	</pre>
331	Returns an iterator-range providing access to the vertex set of graph
332	<tt>g</tt>.
333
334	<hr>
335
336	<pre>
337	std::pair<edge_iterator, edge_iterator>
338	edges(const filtered_graph& g)
339	</pre>
340	Returns an iterator-range providing access to the edge set of graph
341	<tt>g</tt>.
342
343	<hr>
344
345	<pre>
346	std::pair<adjacency_iterator, adjacency_iterator>
347	adjacent_vertices(vertex_descriptor u, const filtered_graph& g)
348	</pre>
349	Returns an iterator-range providing access to the vertices adjacent to
350	vertex <tt>u</tt> in graph <tt>g</tt>.
351
352	<hr>
353
354
355	<pre>
356	std::pair<out_edge_iterator, out_edge_iterator>
357	out_edges(vertex_descriptor u, const filtered_graph& g)
358	</pre>
359	Returns an iterator-range providing access to the out-edges of vertex
360	<tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
361	iterator-range provides access to all edges incident on vertex
362	<tt>u</tt>. For both directed and undirected graphs, for an out-edge
363	<tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
364	where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.
365
366	<hr>
367
368	<pre>
369	std::pair<in_edge_iterator, in_edge_iterator>
370	in_edges(vertex_descriptor v, const filtered_graph& g)
371	</pre>
372	Returns an iterator-range providing access to the in-edges of vertex
373	<tt>v</tt> in graph <tt>g</tt>. For an in-edge <tt>e</tt>,
374	<tt>target(e, g) == v</tt> and <tt>source(e, g) == u</tt> for some
375	vertex <tt>u</tt> that is adjacent to <tt>v</tt>, whether the graph is
376	directed or undirected.
377
378	<hr>
379
380	<pre>
381	vertex_descriptor
382	source(edge_descriptor e, const filtered_graph& g)
383	</pre>
384	Returns the source vertex of edge <tt>e</tt>.
385
386	<hr>
387
388	<pre>
389	vertex_descriptor
390	target(edge_descriptor e, const filtered_graph& g)
391	</pre>
392	Returns the target vertex of edge <tt>e</tt>.
393
394	<hr>
395
396	<pre>
397	degree_size_type
398	out_degree(vertex_descriptor u, const filtered_graph& g)
399	</pre>
400	Returns the number of edges leaving vertex <tt>u</tt>.
401
402	<hr>
403
404	<pre>
405	degree_size_type
406	in_degree(vertex_descriptor u, const filtered_graph& g)
407	</pre>
408	Returns the number of edges entering vertex <tt>u</tt>.
409
410	<hr>
411
412	<pre><a name="num_vertices"></a>
413	vertices_size_type
414	num_vertices(const filtered_graph& g)
415	</pre>
416	Returns the number of vertices in the underlying graph <a href="#2">[2]</a>.
417
418	<hr>
419
420	<pre><a name="num_edges"></a>
421	edges_size_type
422	num_edges(const filtered_graph& g)
423	</pre>
424	Returns the number of edges in the underlying graph <a href="#2">[2]</a>.
425
426	<hr>
427
428	<pre>
429	std::pair<edge_descriptor, bool>
430	edge(vertex_descriptor u, vertex_descriptor v,
431	const filtered_graph& g)
432	</pre>
433	Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in
434	graph <tt>g</tt>.
435
436	<hr>
437
438	<pre>
439	template <typename G, typename EP, typename VP>
440	std::pair<out_edge_iterator, out_edge_iterator>
441	edge_range(vertex_descriptor u, vertex_descriptor v,
442	const filtered_graph& g)
443	</pre>
444	Returns a pair of out-edge iterators that give the range for all the
445	parallel edges from <tt>u</tt> to <tt>v</tt>. This function only works
446	when the underlying graph supports <tt>edge_range</tt>, which requires
447	that it sorts its out edges according to target vertex and allows
448	parallel edges. The <tt>adjacency_list</tt> class with
449	<tt>OutEdgeList=multisetS</tt> is an example of such a graph.
450
451
452	<hr>
453
454	<h4>Property Map Access</h4>
455
456	<hr>
457
458	<pre>
459	template <class <a href="./PropertyTag.html">PropertyTag</a>>
460	property_map<filtered_graph, PropertyTag>::type
461	get(PropertyTag, filtered_graph& g)
462
463	template <class <a href="./PropertyTag.html">PropertyTag</a>>
464	property_map<filtered_graph, Tag>::const_type
465	get(PropertyTag, const filtered_graph& g)
466	</pre>
467	Returns the property map object for the vertex property specified by
468	<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
469	properties specified in the graph's <TT>VertexProperty</TT> template
470	argument.
471
472	<hr>
473
474	<pre>
475	template <class <a href="./PropertyTag.html">PropertyTag</a>, class X>
476	typename property_traits<property_map<filtered_graph, PropertyTag>::const_type&gt::value_type
477	get(PropertyTag, const filtered_graph& g, X x)
478	</pre>
479	This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
480	a vertex or edge descriptor.
481	<hr>
482
483	<pre>
484	template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
485	void
486	put(PropertyTag, const filtered_graph& g, X x, const Value& value)
487	</pre>
488	This sets the property value for <tt>x</tt> to
489	<tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
490	<tt>Value</tt> must be convertible to
491	<tt>typename property_traits<property_map<filtered_graph, PropertyTag>::type&gt::value_type</tt>
492
493	<hr>
494
495	<h3>See Also</h3>
496
497	<a href="./property_map.html"><tt>property_map</tt></a>,
498	<a href="./graph_traits.html"><tt>graph_traits</tt></a>
499
500	<h3>Notes</h3>
501
502	<p>
503	<a name="1">[1]</a> The reason for requiring <a
504	href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
505	Constructible</a> in the <tt>EdgePredicate</tt> and
506	<tt>VertexPredicate</tt> types is that these predicates are stored
507	by-value (for performance reasons) in the filter iterator adaptor, and
508	iterators are required to be Default Constructible by the C++
509	Standard.
510
511	<p> <a name="2">[2]</a> It would be nicer to return the number of
512	vertices (or edges) remaining after the filter has been applied, but
513	this has two problems. The first is that it would take longer to
514	calculate, and the second is that it would interact badly with the
515	underlying vertex/edge index mappings. The index mapping would no
516	longer fall in the range <tt>[0,num_vertices(g))</tt> (resp. <tt>[0,
517	num_edges(g))</tt>) which is assumed in many of the algorithms.
518
519
520	<br>
521	<HR>
522	<TABLE>
523	<TR valign=top>
524	<TD nowrap>Copyright © 2000-2001</TD><TD>
525	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
526	Indiana University (<A
527	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
528	<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
529	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
530	Indiana University (<A
531	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
532	</TD></TR></TABLE>
533
534	</BODY>
535	</HTML>