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, the graph's edges is filtered based on edge weight. Keep all edges with positive edge weight. First, 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 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
filtered_graph(Graph& g, EdgePredicate ep, VertexPredicate vp)
filtered_graph(Graph& g, EdgePredicate ep)
filtered_graph& operator=(const filtered_graph& x)
std::pair<vertex_iterator, vertex_iterator>
vertices(const filtered_graph& g)
std::pair<edge_iterator, edge_iterator>
edges(const filtered_graph& g)
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u, const filtered_graph& g)
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor u, const filtered_graph& g)
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const filtered_graph& g)
vertex_descriptor
source(edge_descriptor e, const filtered_graph& g)
vertex_descriptor
target(edge_descriptor e, const filtered_graph& g)
degree_size_type
out_degree(vertex_descriptor u, const filtered_graph& g)
degree_size_type
in_degree(vertex_descriptor u, const filtered_graph& g)
vertices_size_type
num_vertices(const filtered_graph& g)
edges_size_type
num_edges(const filtered_graph& g)
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
const filtered_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)
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)
PropertyTag, class X>
typename property_traits<property_map<filtered_graph, PropertyTag>::const_type>::value_type
get(PropertyTag, const filtered_graph& g, X x)
PropertyTag, class X, class Value>
void
put(PropertyTag, const filtered_graph& g, X x, const Value& value)
[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.
| Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.eduu) |