Boost C++ 库

...世界上最受推崇和专业设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 编码标准

双向图 (BidirectionalGraph)

双向图概念细化了 IncidenceGraph，并增加了对每个顶点的入边进行高效访问的要求。此概念与 IncidenceGraph 分离，是因为对于有向图，对入边的高效访问通常需要更多的存储空间，并且许多算法不需要访问入边。对于无向图，这不是问题，因为in_edges()和out_edges()函数是相同的，它们都返回与顶点关联的边。

细化自

IncidenceGraph

符号

`G`	作为图模型的类型。
`g`	类型为`G`.
`v`	类型为`boost::graph_traits<G>::vertex_descriptor`.

关联类型

boost::graph_traits<G>::traversal_category

此标签类型必须可转换为bidirectional_graph_tag.

boost::graph_traits<G>::in_edge_iterator

顶点 v 的入边迭代器提供对 v 的入边的访问。因此，入边迭代器的值类型是其图的边描述符类型。入边迭代器必须满足 MultiPassInputIterator 的要求。

有效表达式

`in_edges(v, g)`	返回一个迭代器范围，提供对顶点入边（对于有向图）或关联边（对于无向图）的访问`v`在图 g 中`g`。对于有向图和无向图，出边的目标都必须是顶点`v`，源必须是与之相邻的顶点`v`. 返回类型`std::pair<in_edge_iterator, in_edge_iterator>`
`in_degree(v, g)`	返回顶点入边的数量（对于有向图）或关联边的数量（对于无向图）`v`在图 g 中`g`. 返回类型`degree_size_type`
`degree(v, g)`	返回顶点入边加出边的数量（对于有向图）或关联边的数量（对于无向图）`v`在图 g 中`g`. 返回类型`degree_size_type`

模型

adjacency_list 与Directed=bidirectionalS
adjacency_list 与Directed=undirectedS

复杂度保证

Thein_edges()函数需要为常数时间。in_degree()和degree()函数必须与入边数量（对于有向图）或关联边数量（对于无向图）成线性关系。

参见

图概念

概念检查类

  template <class G>
  struct BidirectionalGraphConcept
  {
    typedef typename boost::graph_traits<G>::in_edge_iterator
      in_edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> ));

      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = in_edges(v, g);
      n = in_degree(v, g);
      n = degree(v, g);
      e = *p.first;
    }
    std::pair<in_edge_iterator, in_edge_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor v;
    typename boost::graph_traits<G>::edge_descriptor e;
    typename boost::graph_traits<G>::degree_size_type n;
    G g;
  };

Jeremy Siek, 印第安纳大学 (jsiek@osl.iu.edu)