Boost C++ 库

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

VertexListGraph

VertexListGraph 概念细化了 Graph 概念，并增加了对图中所有顶点进行高效遍历的要求。

细化自

关联类型

boost::graph_traits<G>::traversal_category

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

boost::graph_traits<G>::vertex_iterator

顶点迭代器（通过vertices(g)获取）提供对图中所有顶点的访问。顶点迭代器类型必须满足 MultiPassInputIterator 的要求。顶点迭代器的值类型必须是图的顶点描述符。

boost::graph_traits<G>::vertices_size_type

用于表示图中顶点数量的无符号整数类型。

有效表达式

名称	表达式	返回类型	描述
图的顶点集合	`vertices(g)`	`std::pair<vertex_iterator, vertex_iterator>`	返回一个迭代器范围，提供对图中所有顶点的访问`g`.
图中顶点的数量	`num_vertices(g)`	`vertices_size_type`	返回图中顶点的数量`g`.

复杂度保证

vertices()函数必须在常数时间内返回。

参见

图概念

设计原理

此概念设计中的一个问题是是否包含来自 IncidenceGraph 和 AdjacencyGraph 概念的细化。遍历图的顶点的能力与遍历出边是正交的，因此创建一个仅包含顶点遍历的 VertexListGraph 概念是有意义的。然而，这样的概念将不再真正是一个图，而只是一个集合，而 STL 已经有处理此类事物的概念。但是，许多 BGL 算法需要遍历图的顶点和出边，因此为了方便起见，需要一个将这些要求组合在一起的概念，因此就有了 VertexListGraph 概念。

概念检查类

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

      p = vertices(g);
      V = num_vertices(g);
      v = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = vertices(g);
      V = num_vertices(g);
      v = *p.first;
    }
    std::pair<vertex_iterator, vertex_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor v;
    typename boost::graph_traits<G>::vertices_size_type V;
    G g;
  };

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