Filtered Graph

A view of a graph that hides vertices and/or edges based on predicate functions.

Defined in: <boost/graph/filtered_graph.hpp>
Models: same concepts as the underlying graph (VertexListGraph, EdgeListGraph, IncidenceGraph, BidirectionalGraph, PropertyGraph, etc.)

num_vertices() and num_edges() return counts from the underlying graph, not the filtered view. This means std::distance(vertices(fg).first, vertices(fg).second) != num_vertices(fg). This is by design: computing filtered counts would be O(V) instead of O(1), and the vertex/edge indices would no longer fall in the range [0, num_vertices(g)) which many algorithms assume. Some algorithms (e.g. vf2_sub_graph_iso) have been specifically patched to use std::distance instead of num_vertices.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <functional>
#include <iostream>

struct Road {
    int weight;
};

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS, no_property, Road>;
    using Edge = graph_traits<Graph>::edge_descriptor;

    Graph g(4);
    add_edge(0, 1, Road{5}, g);
    add_edge(0, 2, Road{0}, g);
    add_edge(1, 3, Road{3}, g);
    add_edge(2, 3, Road{0}, g);

    // Keep only edges with positive weight
    auto filter = [&g](Edge e) { return g[e].weight > 0; };
    filtered_graph<Graph, std::function<bool(Edge)>> fg(g, filter);

    std::cout << "Original: " << num_edges(g) << " edges\n";
    for (auto ei = edges(g).first; ei != edges(g).second; ++ei) {
        std::cout << "  " << source(*ei, g) << " -> " << target(*ei, g)
                  << " (weight=" << g[*ei].weight << ")\n";
    }

    std::cout << "Filtered (weight > 0):\n";
    for (auto ei = edges(fg).first; ei != edges(fg).second; ++ei) {
        std::cout << "  " << source(*ei, fg) << " -> " << target(*ei, fg)
                  << " (weight=" << fg[*ei].weight << ")\n";
    }
}
Original: 4 edges
  0 -> 1 (weight=5)
  0 -> 2 (weight=0)
  1 -> 3 (weight=3)
  2 -> 3 (weight=0)
Filtered (weight > 0):
  0 -> 1 (weight=5)
  1 -> 3 (weight=3)

Synopsis

template <typename Graph,
          typename EdgePredicate,
          typename VertexPredicate = keep_all>
class filtered_graph;

The filtered_graph does not copy the original graph. It holds a reference to it. The lifetime of the original graph must extend past any use of the filtered graph.

Vertex and edge descriptors of the filtered graph are the same as, and interchangeable with, the descriptors of the original graph. Property maps from the original graph are available through the filtered graph.

Template Parameters

Parameter Description Default

Graph

The underlying graph type.

EdgePredicate

Function object selecting which edges appear. Must model Predicate (argument type: edge descriptor). Must be Default Constructible.

VertexPredicate

Function object selecting which vertices appear. Must model Predicate (argument type: vertex descriptor). Must be Default Constructible.

keep_all
Predicates must be Default Constructible because they are stored by-value in filter iterators, and the C++ Standard requires iterators to be Default Constructible.

Member Functions

Constructors

filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp);

Create a filtered view of g with both edge and vertex filters.

filtered_graph(Graph& g, EdgePredicate ep);

Create a filtered view of g with an edge filter only. All vertices are retained.

Non-Member Functions

Structure Access

std::pair<vertex_iterator, vertex_iterator>
vertices(const filtered_graph& g);

Returns an iterator-range for the filtered vertex set.

std::pair<edge_iterator, edge_iterator>
edges(const filtered_graph& g);

Returns an iterator-range for the filtered edge set.

std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor u, const filtered_graph& g);

Returns an iterator-range for the filtered out-edges of vertex u.

std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const filtered_graph& g);

Returns an iterator-range for the filtered in-edges of vertex v. Requires the underlying graph to model BidirectionalGraph.

std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u, const filtered_graph& g);

Returns an iterator-range for the vertices adjacent to u through filtered edges.

vertex_descriptor source(edge_descriptor e, const filtered_graph& g);
vertex_descriptor target(edge_descriptor e, const filtered_graph& g);

Returns the source/target vertex of edge e.

degree_size_type out_degree(vertex_descriptor u, const filtered_graph& g);
degree_size_type in_degree(vertex_descriptor u, const filtered_graph& g);

Returns the filtered out-degree/in-degree of vertex u.

vertices_size_type num_vertices(const filtered_graph& g);
edges_size_type num_edges(const filtered_graph& g);

Returns the number of vertices/edges in the underlying graph (not the filtered count).

std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v, const filtered_graph& g);

Returns the edge connecting u to v, if it exists and passes the filter.

std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const filtered_graph& g);

Returns all parallel edges from u to v. Only works when the underlying graph sorts out-edges by target (e.g. adjacency_list with OutEdgeList=multisetS).

Property Map Access

template <typename PropertyTag>
property_map<filtered_graph, PropertyTag>::type
get(PropertyTag, filtered_graph& g);

template <typename PropertyTag>
property_map<filtered_graph, PropertyTag>::const_type
get(PropertyTag, const filtered_graph& g);

Returns the property map for the given tag. The same property maps from the underlying graph are accessible through the filtered graph.

template <typename PropertyTag, typename X>
auto get(PropertyTag, const filtered_graph& g, X x);

Returns the property value for vertex or edge x.

template <typename PropertyTag, typename X, typename Value>
void put(PropertyTag, const filtered_graph& g, X x, const Value& value);

Sets the property value for vertex or edge x. This modifies the property in the underlying graph.

Associated Types

Type Description

vertex_descriptor

Same as the underlying graph.

edge_descriptor

Same as the underlying graph.

vertex_iterator

filter_iterator<VertexPredicate, graph_traits<Graph>::vertex_iterator>

edge_iterator

filter_iterator<EdgePredicate, graph_traits<Graph>::edge_iterator>

out_edge_iterator

filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>

adjacency_iterator

Models the same iterator concept as out_edge_iterator.

directed_category

directed_tag or undirected_tag (from underlying graph).

edge_parallel_category

allow_parallel_edge_tag or disallow_parallel_edge_tag (from underlying graph).

vertices_size_type, edges_size_type, degree_size_type

Size types from the underlying graph.

Helper Predicates

The header provides several ready-made predicates:

Predicate Description

keep_all

Keeps all elements (the default vertex predicate).

is_residual_edge<ResCapMap>

Keeps edges with positive residual capacity. Useful for max-flow.

is_in_subset<Set>

Keeps vertices that are in the given set.

is_not_in_subset<Set>

Keeps vertices that are not in the given set.
Edit this Page