...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

filtered_graph<Graph, EdgePredicate, VertexPredicate>

The `filtered_graph` 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 `true` for an
edge then it shows up in the filtered graph, and if the predicate
returns `false` then the edge does not appear in the filtered
graph. Likewise for vertices. The `filtered_graph` 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.

The `num_vertices` and `num_edges` functions do not filter
before returning results, so they return the number of vertices or
edges in the underlying graph, unfiltered [2].

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.

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; };Now we create a graph and print out the filtered graph.

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; }The output is:

filtered edge set: (A,B) (C,D) (D,B) filtered out-edges: A --> B B --> C --> D D --> B E -->

Parameter | Description | Default |
---|---|---|

Graph |
The underlying graph type. | |

EdgePredicate | A function object that selects which edges from the original graph will appear in the filtered graph. The function object must model Predicate. The argument type for the function object must be the edge descriptor type of the graph. Also, the predicate must be Default Constructible [1]. | |

VertexPredicate |
A function object that selects which vertices from the original graph will appear in the filtered graph. The function object must model Predicate. The argument type for the function object must be the vertex descriptor type of the graph. Also, the predicate must be Default Constructible [1]. | keep_all |

This depends on the underlying graph type. If the underlying
`Graph` type models VertexAndEdgeListGraph and PropertyGraph then so does the
filtered graph. If the underlying `Graph` type models fewer or
smaller concepts than these, then so does the filtered graph.

`boost/graph/filtered_graph.hpp`

The type for the vertex descriptors associated with the

The type for the edge descriptors associated with the

The type for the iterators returned by

filter_iterator<VertexPredicate, graph_traits<Graph>::vertex_iterator>The iterator is a model of MultiPassInputIterator.

The type for the iterators returned by

filter_iterator<EdgePredicate, graph_traits<Graph>::edge_iterator>The iterator is a model of MultiPassInputIterator.

The type for the iterators returned by

filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>The iterator is a model of MultiPassInputIterator.

The type for the iterators returned by

Provides information about whether the graph is directed (

This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The two tags are

The type used for dealing with the number of vertices in the graph.

The type used for dealing with the number of edges in the graph.

The type used for dealing with the number of edges incident to a vertex in the graph.

and

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.

filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)Create a filtered graph based on the graph

filtered_graph(Graph& g, EdgePredicate ep)Create a filtered graph based on the graph

filtered_graph(const filtered_graph& x) This creates a filtered graph for the same underlying graph as

filtered_graph& operator=(const filtered_graph& x)This creates a filtered graph for the same underlying graph as

std::pair<vertex_iterator, vertex_iterator> vertices(const filtered_graph& g)Returns an iterator-range providing access to the vertex set of graph

std::pair<edge_iterator, edge_iterator> edges(const filtered_graph& g)Returns an iterator-range providing access to the edge set of graph

std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor u, const filtered_graph& g)Returns an iterator-range providing access to the vertices adjacent to vertex

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u, const filtered_graph& g)Returns an iterator-range providing access to the out-edges of vertex

std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const filtered_graph& g)Returns an iterator-range providing access to the in-edges of vertex

vertex_descriptor source(edge_descriptor e, const filtered_graph& g)Returns the source vertex of edge

vertex_descriptor target(edge_descriptor e, const filtered_graph& g)Returns the target vertex of edge

degree_size_type out_degree(vertex_descriptor u, const filtered_graph& g)Returns the number of edges leaving vertex

degree_size_type in_degree(vertex_descriptor u, const filtered_graph& g)Returns the number of edges entering vertex

vertices_size_type num_vertices(const filtered_graph& g)Returns the number of vertices in the underlying graph [2].

edges_size_type num_edges(const filtered_graph& g)Returns the number of edges in the underlying graph [2].

std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const filtered_graph& g)Returns the edge connecting vertex

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)Returns a pair of out-edge iterators that give the range for all the parallel edges from

template <class PropertyTag> property_map<filtered_graph, PropertyTag>::type get(PropertyTag, filtered_graph& g) template <class PropertyTag> property_map<filtered_graph, Tag>::const_type get(PropertyTag, const filtered_graph& g)Returns the property map object for the vertex property specified by

template <class PropertyTag, class X> typename property_traits<property_map<filtered_graph, PropertyTag>::const_type>::value_type get(PropertyTag, const filtered_graph& g, X x)This returns the property value for

template <class PropertyTag, class X, class Value> void put(PropertyTag, const filtered_graph& g, X x, const Value& value)This sets the property value for

[1] The reason for requiring Default
Constructible in the `EdgePredicate` and
`VertexPredicate` 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.

[2] 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 `[0,num_vertices(g))` (resp. `[0,
num_edges(g))`) which is assumed in many of the algorithms.

Copyright © 2000-2001 |
Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |