filtered_graph<Graph, EdgePredicate, VertexPredicate>

这个filtered_graph类模板是一个适配器，用于创建图的过滤视图。谓词函数对象决定了原始图的哪些边和顶点将显示在过滤图中。如果边谓词返回true对于一条边，则它会显示在过滤图中；如果谓词返回false则该边不会出现在过滤图中。顶点也是如此。这个filtered_graph类不会创建原始图的副本，而是使用对原始图的引用。原始图的生命周期必须超过对过滤图的任何使用。过滤图不会更改原始图的结构，但原始图的顶点和边属性可以通过过滤图的属性映射来更改。过滤图的顶点和边描述符与原始图的顶点和边描述符相同且可互换。

num_vertices 和 num_edges 函数在返回结果之前不进行过滤，因此它们返回底层图中未过滤的顶点或边的数量 [2]。

示例

在这个示例中，我们将基于边权重过滤图的边。我们将保留所有具有正边权重的边。首先，我们创建一个谓词函数对象。

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

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

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

模板参数

参数	描述	默认值
图	底层图类型。
边谓词	一个函数对象，用于选择原始图中哪些边将出现在过滤图中。该函数对象必须符合 Predicate 模型。函数对象的参数类型必须是图的边描述符类型。此外，该谓词必须是 Default Constructible 模型 [1]。
顶点谓词	一个函数对象，用于选择原始图中哪些顶点将出现在过滤图中。该函数对象必须符合 Predicate 模型。函数对象的参数类型必须是图的顶点描述符类型。此外，该谓词必须是 Default Constructible 模型 [1]。	keep_all

模型

这取决于底层图类型。如果底层图类型符合 VertexAndEdgeListGraph 和 PropertyGraph 模型，则过滤图也符合。如果底层图类型符合比这些更少或更小的概念，则过滤图也符合。

定义位置

boost/graph/filtered_graph.hpp

关联类型

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

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

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

成员函数

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)

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)

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

参见

注释

[1] 在以下项中要求 Default Constructible 的原因是边谓词和顶点谓词类型的原因是，这些谓词在过滤器迭代器适配器中按值存储（出于性能原因），并且 C++ 标准要求迭代器是默认可构造的。

[2] 如果返回应用过滤器后剩余的顶点（或边）的数量会更好，但这有两个问题。第一个是计算时间会更长，第二个是它会与底层的顶点/边索引映射产生不良的交互。索引映射将不再落入以下范围[0,num_vertices(g))（分别是[0, num_edges(g))），这在许多算法中是假设的。