Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

C++ Boost

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].

Example

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 -->

Template Parameters

ParameterDescriptionDefault
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

Model of

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.

Where Defined

boost/graph/filtered_graph.hpp

Associated Types


graph_traits<filtered_graph>::vertex_descriptor

The type for the vertex descriptors associated with the filtered_graph, which is the same type as the vertex_descriptor for the original Graph.
graph_traits<filtered_graph>::edge_descriptor


The type for the edge descriptors associated with the filtered_graph, which is the same type as the edge_descriptor for the original Graph.
graph_traits<filtered_graph>::vertex_iterator


The type for the iterators returned by vertices(), which is:
filter_iterator<VertexPredicate, graph_traits<Graph>::vertex_iterator>
The iterator is a model of MultiPassInputIterator.
graph_traits<filtered_graph>::edge_iterator

The type for the iterators returned by edges(), which is:
filter_iterator<EdgePredicate, graph_traits<Graph>::edge_iterator>
The iterator is a model of MultiPassInputIterator.
graph_traits<filtered_graph>::out_edge_iterator

The type for the iterators returned by out_edges(), which is:
filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>
The iterator is a model of MultiPassInputIterator.
graph_traits<filtered_graph>::adjacency_iterator

The type for the iterators returned by adjacent_vertices(). The adjacency_iterator models the same iterator concept as out_edge_iterator.
graph_traits<filtered_graph>::directed_category


Provides information about whether the graph is directed (directed_tag) or undirected (undirected_tag).
graph_traits<filtered_graph>::edge_parallel_category


This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The two tags are allow_parallel_edge_tag and disallow_parallel_edge_tag.
graph_traits<filtered_graph>::vertices_size_type

The type used for dealing with the number of vertices in the graph.
graph_traits<filtered_graph>::edges_size_type

The type used for dealing with the number of edges in the graph.
graph_traits<filtered_graph>::degree_size_type

The type used for dealing with the number of edges incident to a vertex in the graph.
property_map<filtered_graph, Property>::type
and
property_map<filtered_graph, Property>::const_type

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.

Member Functions


filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)
Create a filtered graph based on the graph g and the edge filter ep and vertex filter vp.
filtered_graph(Graph& g, EdgePredicate ep)
Create a filtered graph based on the graph g and the edge filter ep. All vertices from the original graph are retained.
filtered_graph(const filtered_graph& x) This creates a filtered graph for the same underlying graph as x. Anotherwords, this is a shallow copy.
filtered_graph& operator=(const filtered_graph& x)
This creates a filtered graph for the same underlying graph as x. Anotherwords, this is a shallow copy.

Non-Member Functions

Structure Access


std::pair<vertex_iterator, vertex_iterator>
vertices(const filtered_graph& g)
Returns an iterator-range providing access to the vertex set of graph g.
std::pair<edge_iterator, edge_iterator>
edges(const filtered_graph& g)
Returns an iterator-range providing access to the edge set of graph g.
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 u in graph g.
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 u in graph g. If the graph is undirected, this iterator-range provides access to all edges incident on vertex u. For both directed and undirected graphs, for an out-edge e, source(e, g) == u and target(e, g) == v where v is a vertex adjacent to u.
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 v in graph g. For an in-edge e, target(e, g) == v and source(e, g) == u for some vertex u that is adjacent to v, whether the graph is directed or undirected.
vertex_descriptor
source(edge_descriptor e, const filtered_graph& g)
Returns the source vertex of edge e.
vertex_descriptor
target(edge_descriptor e, const filtered_graph& g)
Returns the target vertex of edge e.
degree_size_type
out_degree(vertex_descriptor u, const filtered_graph& g)
Returns the number of edges leaving vertex u.
degree_size_type
in_degree(vertex_descriptor u, const filtered_graph& g)
Returns the number of edges entering vertex u.

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 u to vertex v in graph g.
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 u to v. This function only works when the underlying graph supports edge_range, which requires that it sorts its out edges according to target vertex and allows parallel edges. The adjacency_list class with OutEdgeList=multisetS is an example of such a graph.

Property Map Access


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 PropertyTag. The PropertyTag must match one of the properties specified in the graph's VertexProperty template argument.
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 x, where x is either a vertex or edge descriptor.
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 x to value. x is either a vertex or edge descriptor. Value must be convertible to typename property_traits<property_map<filtered_graph, PropertyTag>::type>::value_type

See Also

property_map, graph_traits

Notes

[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)