Boost C++ 库

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

C++ Boost 

adjacency_matrix<Directed, VertexProperty,
                 EdgeProperty, GraphProperty,
                 Allocator>

adjacency_matrix类使用传统的邻接矩阵存储格式实现了 BGL 图接口。对于具有 V 个顶点的图，使用 V x V 矩阵，其中每个元素 aij 是一个布尔标志，表示是否存在从顶点 i 到顶点 j 的边。图 1 显示了图的邻接矩阵表示。

图 1：有向图的邻接矩阵表示。

这种矩阵格式相对于邻接表的优势在于边插入和删除是常数时间。但也有一些缺点。首先，使用的内存量为 O(V2) 而不是 O(V + E)（其中 E 是边的数量）。其次，遍历每个顶点的所有出边（例如广度优先搜索）的操作在 O(V2) 时间内运行，而不是邻接表的 O(V + E) 时间。简而言之，对于稠密图（其中 E 接近 V2）最好使用adjacency_matrix`adjacency_matrix` 类，而对于稀疏图（其中 E 远小于 V2）最好使用 adjacency_list。adjacency_matrix`adjacency_matrix` 类扩展了传统的数据结构，允许使用 adjacency_list 支持的相同属性模板参数将对象附加到顶点和边。这些可以是 捆绑属性 或标准（向后兼容）的 内部属性。所有属性值类型必须是可复制构造、可赋值和可默认构造的。在无向图的情况下，adjacency_matrix`adjacency_matrix` 类不使用完整的 V x V 矩阵，而是使用下三角（对角线及以下），因为无向图的矩阵是对称的。这将存储减少到 (V2)/2。 图 2 显示了无向图的邻接矩阵表示。

图 2：无向图的邻接矩阵表示。

示例

创建 图 1 的图。
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";

  typedef boost::adjacency_matrix<boost::directedS> Graph;
  Graph g(N);
  add_edge(B, C, g);
  add_edge(B, F, g);
  add_edge(C, A, g);
  add_edge(C, C, g);
  add_edge(D, E, g);
  add_edge(E, D, g);
  add_edge(F, A, g);

  std::cout << "vertex set: ";
  boost::print_vertices(g, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(g, name);
  std::cout << std::endl;

  std::cout << "out-edges: " << std::endl;
  boost::print_graph(g, name);
  std::cout << std::endl;
输出为
  vertex set: A B C D E F

  edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A)

  out-edges:
  A -->
  B --> C F
  C --> A C
  D --> E
  E --> D
  F --> A
创建 图 2 的图。
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";

  typedef boost::adjacency_matrix<boost::undirectedS> UGraph;
  UGraph ug(N);
  add_edge(B, C, ug);
  add_edge(B, F, ug);
  add_edge(C, A, ug);
  add_edge(D, E, ug);
  add_edge(F, A, ug);

  std::cout << "vertex set: ";
  boost::print_vertices(ug, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(ug, name);
  std::cout << std::endl;

  std::cout << "incident edges: " << std::endl;
  boost::print_graph(ug, name);
  std::cout << std::endl;
输出为
  vertex set: A B C D E F

  edge set: (C,A) (C,B) (E,D) (F,A) (F,B)

  incident edges:
  A <--> C F
  B <--> C F
  C <--> A B
  D <--> E
  E <--> D
  F <--> A B

定义位置

boost/graph/adjacency_matrix.hpp

模板参数

参数描述默认值
Directed 用于选择图是有向还是无向的选择器。选项是directedS和undirectedS. directedS
VertexProperty 用于指定内部属性存储。 no_property
EdgeProperty 用于指定内部属性存储。 no_property
GraphProperty 用于指定图对象的属性存储。 no_property

模型

顶点和边列表图、关联图、双向图、邻接矩阵、可变属性图、可复制构造 和 可赋值。

关联类型

graph_traits<adjacency_matrix>::vertex_descriptor

与

关联的顶点描述符的类型 adjacency_matrix.
`adjacency_matrix`。（图 要求。）
graph_traits<adjacency_matrix>::edge_descriptor

与

关联的边描述符的类型 adjacency_matrix.
`adjacency_matrix`。（图 要求。）
graph_traits<adjacency_matrix>::vertex_iterator

由

返回的迭代器的类型 vertices()。顶点迭代器模型为随机访问迭代器。
（顶点列表图 要求。）
graph_traits<adjacency_matrix>::edge_iterator

由

返回的迭代器的类型 edges()返回的迭代器的类型。此迭代器模型为 多遍输入迭代器。
（边列表图 要求。）
graph_traits<adjacency_matrix>::out_edge_iterator

由

返回的迭代器的类型 out_edges()返回的迭代器的类型。此迭代器模型为 多遍输入迭代器。
返回的迭代器的类型。（关联图 要求。）
graph_traits<adjacency_matrix>::in_edge_iterator

由

返回的迭代器的类型 in_edges()返回的迭代器的类型。此迭代器模型为 多遍输入迭代器。
返回的迭代器的类型。（双向图 要求。）
graph_traits<adjacency_matrix>::adjacency_iterator

由

返回的迭代器的类型 adjacent_vertices()返回的迭代器的类型。此迭代器与出边迭代器模型的概念相同。
（邻接图 要求。）
graph_traits<adjacency_matrix>::directed_category

提供关于图是有向（directed_tag）还是无向（undirected_tag).
`adjacency_matrix`。（图 要求。）
）的信息。

graph_traits<adjacency_matrix>::edge_parallel_category邻接矩阵不允许插入平行边，因此此类型始终为.
`adjacency_matrix`。（图 要求。）
disallow_parallel_edge_tag

graph_traits<adjacency_matrix>::vertices_size_type
（顶点列表图 要求。）
用于处理图中顶点数量的类型。

graph_traits<adjacency_matrix>::edges_size_type
（边列表图 要求。）
用于处理图中边数量的类型。

graph_traits<adjacency_matrix>::degree_size_type
返回的迭代器的类型。（关联图 要求。）
用于处理顶点出边数量的类型。
property_map<adjacency_matrix, PropertyTag>::type

property_map<adjacency_matrix, PropertyTag>::const_type图中顶点或边属性的映射类型。具体的属性由PropertyTagVertexProperty模板参数指定，并且必须与

中指定的属性之一匹配 EdgeProperty`VertexProperty` 或 `EdgeProperty`
参数。（属性图 要求。）

成员函数

adjacency_matrix(vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建具有n个顶点和零条边的图对象。
（可变图 要求。）
template <typename EdgeIterator>
adjacency_matrix(EdgeIterator first,
                 EdgeIterator last,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建具有n创建具有n个顶点的图，其边在范围[first, last)给出的边列表中指定。`EdgeIterator` 的 `value_type` 必须是 `std::pair`，其中 pair 中的类型是整数类型。整数将对应于顶点，并且它们必须全部落在.
[0, n)
template <typename EdgeIterator, typename EdgePropertyIterator>
adjacency_matrix(EdgeIterator first, EdgeIterator last,
                 EdgePropertyIterator ep_iter,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建具有n的范围内。（迭代器可构造图 要求。）n个顶点的图，其边在范围[first, last)给出的边列表中指定。`EdgeIterator` 的 `value_type` 必须是 `std::pair`，其中 pair 中的类型是整数类型。整数将对应于顶点，并且它们必须全部落在创建具有n个顶点的图，其边在范围

`[first, last)` 给出的边列表中指定。`ep_iter` 的 `value_type应该是EdgeProperty.

非成员函数

std::pair<vertex_iterator, vertex_iterator>
vertices(const adjacency_matrix& g)
返回一个迭代器范围，提供对图g.
（顶点列表图 要求。）
std::pair<edge_iterator, edge_iterator>
edges(const adjacency_matrix& g);
gg.
（边列表图 要求。）
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor v, const adjacency_matrix& g)
的边集的访问。v相邻的顶点的访问。g.
（邻接图 要求。）
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor v, const adjacency_matrix& g)
返回一个迭代器范围，提供对顶点v相邻的顶点的访问。guv.
返回的迭代器的类型。（关联图 要求。）
vertex_descriptor
source(edge_descriptor e, const adjacency_matrix& g)
关联的所有边的访问。返回边.
返回的迭代器的类型。（关联图 要求。）
vertex_descriptor
target(edge_descriptor e, const adjacency_matrix& g)
e返回边.
返回的迭代器的类型。（关联图 要求。）
degree_size_type
out_degree(vertex_descriptor u, const adjacency_matrix& g)
返回离开顶点u.
返回的迭代器的类型。（关联图 要求。）
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const adjacency_matrix& g)
返回一个迭代器范围，提供对顶点v相邻的顶点的访问。guv.
返回的迭代器的类型。（双向图 要求。）
degree_size_type
in_degree(vertex_descriptor u, const adjacency_matrix& g)
返回进入顶点u.
返回的迭代器的类型。（双向图 要求。）
vertices_size_type num_vertices(const adjacency_matrix& g)
返回图中的顶点数。g.
（顶点列表图 要求。）
edges_size_type num_edges(const adjacency_matrix& g)
返回图中的边数。g.
（边列表图 要求。）
vertex_descriptor vertex(vertices_size_type n, const adjacency_matrix& g)
返回图的顶点列表中的第 n 个顶点。
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
     const adjacency_matrix& g)
返回连接顶点uuv相邻的顶点的访问。g.
的边。（邻接矩阵 要求。）
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         adjacency_matrix& g)
将边(u,v)添加到图中，并返回新边的边描述符。如果边已在图中，则不会添加重复边，并且bool标志将为false。此操作不会使图的任何迭代器或描述符失效。
（可变图 要求。）
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         const EdgeProperty& p,
         adjacency_matrix& g)
将边(u,v)将边添加到图中，并将p附加为边内部属性存储的值。另请参阅前面的add_edge()
void remove_edge(vertex_descriptor u, vertex_descriptor v,
                 adjacency_matrix& g)
从图中移除边(u,v)。
（可变图 要求。）
void remove_edge(edge_descriptor e, adjacency_matrix& g)
从图中移除边返回边从图中移除边。这等效于调用.
（可变图 要求。）
void clear_vertex(vertex_descriptor u, adjacency_matrix& g)
移除所有与顶点u相连的边。顶点仍然出现在图的顶点集中。
（可变图 要求。）
template <typename Property>
property_map<adjacency_matrix, Property>::type
get(Property, adjacency_matrix& g)

template <typename Property>
property_map<adjacency_matrix, Property>::const_type
get(Property, const adjacency_matrix& g)
返回由Property创建具有Property指定的顶点属性的属性映射对象。`VertexPropertyVertexProperty` 模板参数中指定的属性之一匹配。
参数。（属性图 要求。）
template <typename Property, typename X>
typename property_traits<
  typename property_map<adjacency_matrix, Property>::const_type
>::value_type
get(Property, const adjacency_matrix& g, X x)
这将返回x` 是顶点或边描述符。`的属性值，它是顶点或边描述符。
参数。（属性图 要求。）
template <typename Property, typename X, typename Value>
void
put(Property, const adjacency_matrix& g, X x, const Value& value)
这会将x` 是顶点或边描述符。`的属性值设置为value. x` 是顶点或边描述符。`。`Value必须可转换为 `typename property_traits<property_map<adjacency_matrix, Property>::type>::value_type`。.
参数。（属性图 要求。）
template <typename GraphProperty, typename GraphProperty>
typename property_value<GraphProperty, GraphProperty>::type&
get_property(adjacency_matrix& g, GraphProperty)
返回附加到图对象GraphProperty的由g创建具有指定的属性。`property_traits` 类在boost/pending/property.hpp. 
template <typename GraphProperty, typename GraphProperty>
const typename property_value<GraphProperty, GraphProperty>::type&
get_property(const adjacency_matrix& g, GraphProperty)
返回附加到图对象GraphProperty的由g创建具有指定的属性。`property_traits` 类在boost/pending/property.hpp.