mirror of
https://github.com/boostorg/graph.git
synced 2026-01-19 04:12:11 +00:00
536 lines
15 KiB
HTML
536 lines
15 KiB
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<Graph, EdgePredicate, VertexPredicate>
|
|
</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 <typename EdgeWeightMap>
|
|
struct positive_edge_weight {
|
|
positive_edge_weight() { }
|
|
positive_edge_weight(EdgeWeightMap weight) : m_weight(weight) { }
|
|
template <typename Edge>
|
|
bool operator()(const Edge& e) const {
|
|
return 0 < 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<vecS, vecS, directedS,
|
|
no_property, property<edge_weight_t, int> > Graph;
|
|
typedef property_map<Graph, edge_weight_t>::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<EdgeWeightMap> filter(get(edge_weight, g));
|
|
filtered_graph<Graph, positive_edge_weight<EdgeWeightMap> >
|
|
fg(g, filter);
|
|
|
|
std::cout << "filtered edge set: ";
|
|
print_edges(fg, name);
|
|
|
|
std::cout << "filtered out-edges:" << 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> </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.boost.org/sgi/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.boost.org/sgi/stl/DefaultConstructible.html">Default Constructible</a> <a href="#1">[1]</a>.</TD>
|
|
<TD> </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.boost.org/sgi/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.boost.org/sgi/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<filtered_graph>::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<filtered_graph>::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<filtered_graph>::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><VertexPredicate, graph_traits<Graph>::vertex_iterator>
|
|
</pre>
|
|
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
|
|
|
|
|
|
<hr>
|
|
|
|
<tt>graph_traits<filtered_graph>::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><EdgePredicate, graph_traits<Graph>::edge_iterator>
|
|
</pre>
|
|
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
|
|
|
|
<hr>
|
|
|
|
|
|
<tt>graph_traits<filtered_graph>::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><EdgePredicate, graph_traits<Graph>::out_edge_iterator>
|
|
</pre>
|
|
The iterator is a model of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
|
|
|
|
|
|
<hr>
|
|
|
|
<tt>graph_traits<filtered_graph>::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<filtered_graph>::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<filtered_graph>::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<filtered_graph>::vertices_size_type</tt>
|
|
<br><br>
|
|
The type used for dealing with the number of vertices in the graph.
|
|
|
|
<hr>
|
|
|
|
<tt>graph_traits<filtered_graph>::edges_size_type</tt>
|
|
<br><br>
|
|
The type used for dealing with the number of edges in the graph.
|
|
|
|
<hr>
|
|
|
|
<tt>graph_traits<filtered_graph>::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<filtered_graph, Property>::type</tt><br>
|
|
and<br>
|
|
<tt>property_map<filtered_graph, Property>::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& g, EdgePredicate ep, VertexPredicate 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& g, EdgePredicate 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 filtered_graph& 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& operator=(const filtered_graph& 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<vertex_iterator, vertex_iterator>
|
|
vertices(const filtered_graph& g)
|
|
</pre>
|
|
Returns an iterator-range providing access to the vertex set of graph
|
|
<tt>g</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
std::pair<edge_iterator, edge_iterator>
|
|
edges(const filtered_graph& g)
|
|
</pre>
|
|
Returns an iterator-range providing access to the edge set of graph
|
|
<tt>g</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
std::pair<adjacency_iterator, adjacency_iterator>
|
|
adjacent_vertices(vertex_descriptor u, const filtered_graph& 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<out_edge_iterator, out_edge_iterator>
|
|
out_edges(vertex_descriptor u, const filtered_graph& 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<in_edge_iterator, in_edge_iterator>
|
|
in_edges(vertex_descriptor v, const filtered_graph& 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 e, const filtered_graph& g)
|
|
</pre>
|
|
Returns the source vertex of edge <tt>e</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
vertex_descriptor
|
|
target(edge_descriptor e, const filtered_graph& g)
|
|
</pre>
|
|
Returns the target vertex of edge <tt>e</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
degree_size_type
|
|
out_degree(vertex_descriptor u, const filtered_graph& g)
|
|
</pre>
|
|
Returns the number of edges leaving vertex <tt>u</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
degree_size_type
|
|
in_degree(vertex_descriptor u, const filtered_graph& 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& 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& g)
|
|
</pre>
|
|
Returns the number of edges in the underlying graph <a href="#2">[2]</a>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
std::pair<edge_descriptor, bool>
|
|
edge(vertex_descriptor u, vertex_descriptor v,
|
|
const filtered_graph& g)
|
|
</pre>
|
|
Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in
|
|
graph <tt>g</tt>.
|
|
|
|
<hr>
|
|
|
|
<pre>
|
|
template <typename G, typename EP, typename VP>
|
|
std::pair<out_edge_iterator, out_edge_iterator>
|
|
edge_range(vertex_descriptor u, vertex_descriptor v,
|
|
const filtered_graph& 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 <class <a href="./PropertyTag.html">PropertyTag</a>>
|
|
property_map<filtered_graph, PropertyTag>::type
|
|
get(PropertyTag, filtered_graph& g)
|
|
|
|
template <class <a href="./PropertyTag.html">PropertyTag</a>>
|
|
property_map<filtered_graph, Tag>::const_type
|
|
get(PropertyTag, const filtered_graph& 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 <class <a href="./PropertyTag.html">PropertyTag</a>, class X>
|
|
typename property_traits<property_map<filtered_graph, PropertyTag>::const_type>::value_type
|
|
get(PropertyTag, const filtered_graph& 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 <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
|
|
void
|
|
put(PropertyTag, const filtered_graph& 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<property_map<filtered_graph, PropertyTag>::type>::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.boost.org/sgi/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 © 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|