Boost C++ 库

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

C++ Boost 

adjacency_list<OutEdgeList, VertexList, Directed,
               VertexProperties, EdgeProperties,
               GraphProperties, EdgeList>

Theadjacency_list类实现了一个通用的邻接表图结构。模板参数提供了许多配置选项，以便您可以选择最适合您需求的类版本。 邻接表 基本上是一个二维结构，其中第一维的每个元素代表一个顶点，每个顶点包含一个一维结构，即其边列表。 图 1 显示了一个有向图的邻接表表示。

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

TheVertexList模板参数adjacency_list类控制用于表示外部二维容器的容器类型。OutEdgeList模板参数控制用于表示边列表的容器类型。OutEdgeList和VertexList的选择将决定图结构的空间复杂度，并决定各种图操作的时间复杂度。 可能的选择和权衡在 选择 Edgelist 和 VertexList 章节中讨论。

TheDirected模板参数控制图是有向的、无向的，还是有向的且可以访问入边和出边（我们称之为双向）。 双向图比有向图占用两倍的空间（每个边），因为每个边都会出现在出边列表和入边列表中。 图 2 显示了一个无向图的邻接表表示。

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

关于如何使用adjacency_list类 的教程在 使用 adjacency_list 章节中。

示例

examples/family_tree.cpp 中的示例展示了如何使用图来表示家谱树。

模板参数

参数描述默认值
OutEdgeList 用于表示每个顶点的边列表的容器选择器。 vecS
VertexList 用于表示图的顶点列表的容器选择器。 vecS
Directed 用于选择图是有向、无向还是有向且具有双向边访问（访问出边和入边）的选择器。 选项有directedS, undirectedS，和bidirectionalS. directedS
VertexProperties 用于指定内部属性存储。 no_property
EdgeProperties 用于指定内部属性存储。 no_property
GraphProperties 用于指定图对象的属性存储。 no_property
EdgeList 用于表示图的边列表的容器选择器。 listS

模型

VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, 和 Serializable。

定义位置

boost/graph/adjacency_list.hpp

此外，序列化功能在 boost/graph/adj_list_serialize.hpp 中。

顶点和边属性

可以使用属性将颜色、距离、权重和用户定义的属性等属性附加到图的顶点和边。 属性值可以通过图提供的属性映射进行读取和写入。 属性映射通过get(property, g)函数 获取。 如何使用属性在 内部属性 章节中描述。 属性映射是实现 属性映射概念 中定义的接口的对象，也可以是 捆绑属性，后者具有更简洁的语法。 所有属性值的类型必须是 Copy Constructible、Assignable 和 Default Constructible。 从adjacency_list类 获取的属性映射是 Lvalue 属性映射 概念的模型。 如果adjacency_list是 const，则属性映射是常量，否则属性映射是可变的。

如果VertexList图的vecS是 ，则图具有通过vertex_index_t属性的属性映射访问的内置顶点索引。 索引落在[0, num_vertices(g))范围内 并且是连续的。 当删除顶点时，索引会进行调整，以便它们保留这些属性。 当使用这些索引访问外部属性存储时，必须小心。 顶点索引的属性映射是 Readable 属性映射 的模型。

迭代器和描述符的稳定性/失效

更改图的结构（通过添加或删除边）时，必须小心。 根据adjacency_list和 操作的类型，指向图中的某些迭代器或描述符对象可能会失效。 例如，以下代码将导致未定义的（错误）行为
  typedef adjacency_list<listS, vecS> Graph; // VertexList=vecS
  Graph G(N);
  // Fill in the graph...

  // Attempt to remove all the vertices. Wrong!
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    remove_vertex(*vi, G);

  // Remove all the vertices. This is still wrong!
  graph_traits<Graph>::vertex_iterator vi, vi_end, next;
  boost::tie(vi, vi_end) = vertices(G);
  for (next = vi; vi != vi_end; vi = next) {
    ++next;
    remove_vertex(*vi, G);
  }
原因是我们在调用remove_vertex()，当与adjacency_list一起使用时，其中VertexList=vecS，会使图的所有迭代器和描述符（例如vi和vi_end）失效，从而在循环的后续迭代中引起问题。

如果我们使用不同类型的adjacency_list，其中VertexList=listS，则迭代器不会因调用remove_vertex而失效，除非迭代器指向实际删除的顶点。 以下代码演示了这一点。

  typedef adjacency_list<listS, listS> Graph; // VertexList=listS
  Graph G(N);
  // Fill in the graph...

  // Attempt to remove all the vertices. Wrong!
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
    remove_vertex(*vi, G);

  // Remove all the vertices. This is OK.
  graph_traits<Graph>::vertex_iterator vi, vi_end, next;
  boost::tie(vi, vi_end) = vertices(G);
  for (next = vi; vi != vi_end; vi = next) {
    ++next;
    remove_vertex(*vi, G);
  }

稳定性问题也影响顶点和边描述符。 例如，假设您使用顶点描述符向量来跟踪最短路径树中顶点的父节点（或前任节点）（请参阅 examples/dijkstra-example.cpp）。 您通过调用dijkstra_shortest_paths()创建父向量，然后从图中删除一个顶点。 随后您尝试使用父向量，但由于所有顶点描述符都已失效，因此结果不正确。

  std::vector<Vertex> parent(num_vertices(G));
  std::vector<Vertex> distance(num_vertices(G));

  dijkstra_shortest_paths(G, s, distance_map(&distance[0]).
    predecessor_map(&parent[0]));

  remove_vertex(s, G); // Bad idea! Invalidates vertex descriptors in parent vector.

  // The following will produce incorrect results
  for(boost::tie(vi, vend) = vertices(G); vi != vend; ++vi)
    std::cout << p[*vi] << " is the parent of " << *vi << std::endl;

请注意，在本讨论中，迭代器和描述符失效与 未直接受 操作影响的迭代器和描述符的失效有关。 例如，执行remove_edge(u, v, g)将始终使 (u,v) 的任何边描述符或指向 (u,v) 的边迭代器失效，无论adjacency_list是哪种类型。 在本关于迭代器和描述符失效的讨论中，我们只关注remove_edge(u, v, g)对指向其他边（而不是 (u,v)）的边描述符和迭代器的影响。

一般来说，如果您希望您的顶点和边描述符是稳定的（永不失效），则对于listS或setS的模板参数使用VertexList和OutEdgeList。 如果您不太关心描述符和迭代器的稳定性，而更关心内存消耗和图遍历速度，请使用adjacency_list和/或vecS的模板参数使用VertexList模板参数。OutEdgeList下表总结了哪些操作会导致描述符和迭代器失效。 在表中，

EL是的缩写，OutEdgeList和VL表示VertexList。 Adj Iter 类别包括out_edge_iterator, in_edge_iterator，和adjacency_iterator类型。 有关描述符和迭代器失效的更详细描述，请参阅每个操作的文档。

表： 描述符和迭代器失效摘要。
函数 顶点描述符 边描述符 顶点迭代器 边迭代器 邻接迭代器
add_edge() OK OK OK EL=vecS &&
Directed=directedS		 EL=vecS
remove_edge()
remove_edge_if()
remove_out_edge_if()
remove_in_edge_if()
clear_vertex() 		OK OK OK EL=vecS &&
Directed=directedS		 EL=vecS
add_vertex() OK OK OK VL=vecS &&
Directed=directedS		 VL=vecS &&
Directed=directedS
remove_vertex() VL=vecS VL=vecS VL=vecS VL=vecS VL=vecS

关联类型

graph_traits<adjacency_list>::vertex_descriptor
和
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::vertex_descriptor

与adjacency_list.
graph_traits<adjacency_list>::edge_descriptor
和
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_descriptor

与adjacency_list.
graph_traits<adjacency_list>::vertex_iterator

由vertices()返回的迭代器的类型。 当VertexList=vecS时，vertex_iterator是 RandomAccessIterator 的模型。 否则，vertex_iterator是 BidirectionalIterator 的模型。
graph_traits<adjacency_list>::edge_iterator

由edges()。edge_iterator是 BidirectionalIterator 的模型。
graph_traits<adjacency_list>::out_edge_iterator

由out_edges()返回的迭代器的类型。 当OutEdgeList=vecS时，out_edge_iterator是 RandomAccessIterator 的模型。 当OutEdgeList=slistS时，out_edge_iterator是 ForwardIterator 的模型。 否则，out_edge_iterator是 BidirectionalIterator 的模型。
graph_traits<adjacency_list>::adjacency_iterator

由adjacent_vertices()。adjacency_iterator与 相同的迭代器概念out_edge_iterator.
adjacency_list::inv_adjacency_iterator

由inv_adjacent_vertices()。inv_adjacency_iterator与 相同的迭代器概念out_edge_iterator.
graph_traits<adjacency_list>::directed_category
和
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::directed_category

提供有关图是有向的 (directed_tag) 还是无向的 (undirected_tag).
graph_traits<adjacency_list>::edge_parallel_category
和
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_parallel_category

这描述了图类是否允许插入平行边（具有相同源和目标的边）。 这两个标签是allow_parallel_edge_tag和disallow_parallel_edge_tag。setS和hash_setS变体不允许平行边，而其他变体允许平行边。
graph_traits<adjacency_list>::vertices_size_type
和
adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::vertices_size_type


用于处理图中顶点数量的类型。
graph_traits<adjacency_list>::edges_size_type
和
adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::edges_size_type


用于处理图中边数量的类型。
graph_traits<adjacency_list>::degree_size_type

用于处理图中与顶点关联的边数的类型。
property_map<adjacency_list, Property>::type
和
property_map<adjacency_list, Property>::const_type

图中顶点或边属性的属性映射类型。 具体属性由Property模板参数指定，并且必须与VertexProperties或EdgeProperties图的
graph_property<adjacency_list, Property>::type

由Property标记指定的图属性的属性值类型。
adjacency_list::out_edge_list_selector

类型OutEdgeListS.
adjacency_list::vertex_list_selector

类型VertexListS.
adjacency_list::directed_selector

类型DirectedS.
adjacency_list::edge_list_selector

类型EdgeListS.

成员函数

adjacency_list(const GraphProperty& p = GraphProperty())
默认构造函数。 创建一个顶点和边数为零的空图对象。
adjacency_list(const adjacency_list& x)
复制构造函数。 创建一个新图，它是图x的副本，包括边、顶点和属性。
adjacency_list& operator=(const adjacency_list& x)
赋值运算符。 使此图成为图x的副本，包括边、顶点和属性。
adjacency_list(vertices_size_type n,
               const GraphProperty& p = GraphProperty())
创建一个具有n个顶点和零条边的图对象。
template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, edges_size_type m = 0, const GraphProperty& p = GraphProperty())
创建一个具有 n 个顶点和边，边由范围 [first, last) 中给出的边列表指定。 EdgeIterator 必须是 InputIterator 的模型。 的值类型EdgeIterator必须是std::pair，其中对中的类型是整数类型。 整数将对应于顶点，并且它们都必须落在[0, n). 
template <class EdgeIterator, class EdgePropertyIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               EdgePropertyIterator ep_iter,
               vertices_size_type n,
               edges_size_type m = 0,
               const GraphProperty& p = GraphProperty())
创建一个具有n个顶点和边，边由范围[first, last)。EdgeIterator和EdgePropertyIterator中给出的边列表指定。 InputIterator 的模型。 的值类型EdgeIterator必须是std::pair，其中对中的类型是整数类型。 整数将对应于顶点，并且它们都必须落在[0, n)。value_type的ep_iter应为EdgeProperties. 
void clear()
从图中删除所有边和顶点。
void swap(adjacency_list& x)
将此图的顶点、边和属性与图的顶点、边和属性交换x.

非成员函数

结构访问

std::pair<vertex_iterator, vertex_iterator>
vertices(const adjacency_list& g)
返回一个迭代器范围，提供对图g. 
std::pair<edge_iterator, edge_iterator>
edges(const adjacency_list& g)
的顶点集的访问。 返回一个迭代器范围，提供对图的边集的访问g. 
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u, const adjacency_list& g)
返回一个迭代器范围，提供对与顶点u在图g中相邻的顶点的访问。 例如，如果u -> v是图中的一条边，则v将在此迭代器范围内。
std::pair<inv_adjacency_iterator, inv_adjacency_iterator>
inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& g)
返回一个迭代器范围，提供对图g中与u相邻的顶点的访问。 （inv是指逆向）。 例如，如果v -> u是图中的一条边，则v将在此迭代器范围内。 此函数仅适用于双向和无向adjacency_list的。
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor u, const adjacency_list& g)
返回一个迭代器范围，提供对顶点u在图g的出边的访问。 如果图是无向的，则此迭代器范围提供对顶点u上所有关联边的访问。 对于有向图和无向图，对于出边e, source(e, g) == u和target(e, g) == v一起使用时，其中v是与u. 
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const adjacency_list& g)
相邻的顶点。 返回一个迭代器范围，提供对顶点v在图g的入边的访问。 仅当bidirectionalS为Directed模板参数指定 时，此操作才可用。 对于入边e, target(e, g) == v和source(e, g) == u对于某个与u相邻的顶点v，无论图是有向还是无向。
vertex_descriptor
source(edge_descriptor e, const adjacency_list& g)
返回边e. 
vertex_descriptor
target(edge_descriptor e, const adjacency_list& g)
的源顶点。 返回边e. 
degree_size_type
out_degree(vertex_descriptor u, const adjacency_list& g)
的目标顶点。 返回离开顶点u. 
degree_size_type
in_degree(vertex_descriptor u, const adjacency_list& g)
的边数。 返回进入顶点u的入边的访问。 仅当bidirectionalS为Directed的边数。 模板参数。
vertices_size_type
num_vertices(const adjacency_list& g)
返回图中顶点的数量g. 
edges_size_type
num_edges(const adjacency_list& g)
返回图中边的数量g. 
vertex_descriptor
vertex(vertices_size_type n, const adjacency_list& g)
返回图中顶点列表中的第 n 个顶点。
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
     const adjacency_list& g)
如果从顶点u到顶点v的边存在，则返回一个包含一个此类边和true的对。 如果u和v和之间没有边，则返回一个带有任意边描述符和. 
std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const adjacency_list& g)
falseu的对。 返回一对出边迭代器，它们给出了从v到OutEdgeList的模板参数使用adjacency_list的所有平行边的范围。 仅当是根据目标顶点对出边进行排序并允许平行边的容器时，此函数才有效。multisetS

选择器选择这样的容器。

std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         adjacency_list& g)
结构修改将边 (u,v) 添加到图中，并返回新边的边描述符。 对于不允许平行边的图，如果边已在图中，则不会添加重复项，并且bool之间没有边，则返回一个带有任意边描述符和标志将为之间没有边，则返回一个带有任意边描述符和。 当标志为

时，返回的边描述符指向已存在的边。 新边在出边列表中的位置通常是未指定的，尽管可以通过选择OutEdgeList来完成出边列表的排序。 如果VertexList选择器是vecS，并且如果任一顶点描述符u或v（它们是整数）的值大于图中当前的顶点数，则图会扩大，以便顶点数为std::max(u,v) + 1.

如果OutEdgeList选择器是vecS然后此操作将使顶点 u 的任何out_edge_iterator失效。 如果OutEdgeList是用户定义的容器，当push(container, x)调用时，它也会使其迭代器失效（请参阅 自定义邻接表存储 章节）。 如果图也是双向的，则 v 的任何in_edge_iterator也将失效。 如果图是无向的，则 v 的任何out_edge_iterator也将失效。 如果图是有向的，则add_edge()也将使任何edge_iterator. 

std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         const EdgeProperties& p,
         adjacency_list& g)
失效。 将边 (u,v) 添加到图中，并将p作为边内部属性存储的值附加。 另请参阅前面的add_edge()非成员函数以了解更多详细信息。
void remove_edge(vertex_descriptor u, vertex_descriptor v,
                 adjacency_list& g)
从图中删除边 (u,v)。

此操作会导致指向边 (u,v) 的任何未完成的边描述符或迭代器失效。 此外，如果OutEdgeList选择器是vecS，则此操作将使指向顶点 u 的边列表以及无向和双向情况下的顶点 v 的边列表的任何迭代器失效。 此外，对于有向图，这将使任何edge_iterator. 

void remove_edge(edge_descriptor e, adjacency_list& g)
失效。 从图中删除边e。 这与remove_edge(u, v, g)多重图的情况下的函数不同。 此remove_edge(e, g)函数删除单个边，而remove_edge(u, v, g)函数删除所有边 (u,v)。

此操作会使指向描述符e指向的同一边的任何未完成的边描述符和迭代器失效。 此外，此操作将使指向target(e, g)的边列表的任何迭代器失效。 此外，对于有向图，这将使任何edge_iterator图的

void remove_edge(out_edge_iterator iter, adjacency_list& g)
失效。 这与remove_edge(*iter, g)具有相同的效果。 不同之处在于，对于有向图，此函数具有恒定的时间复杂度，而remove_edge(e, g)具有 O(E/V) 的时间复杂度。
template <class Predicate>
void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
                        adjacency_list& g)
从图中删除顶点 u 的所有满足predicate条件的出边。 也就是说，如果谓词应用于边描述符时返回 true，则删除该边。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()的影响相同。

template <class Predicate>
void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
                       adjacency_list& g)
从图中删除顶点 v 的所有满足predicate条件的出边。 也就是说，如果谓词应用于边描述符时返回 true，则删除该边。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()的影响相同。

条件的入边。 此操作适用于无向图和双向adjacency_list图，但不适用于有向图。

template <class Predicate>
void remove_edge_if(Predicate predicate, adjacency_list& g)
从图中删除图中所有满足predicate条件的出边。 也就是说，如果谓词应用于边描述符时返回 true，则删除该边。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()的影响相同。

vertex_descriptor
add_vertex(adjacency_list& g)
的边。 将顶点添加到图中，并返回新顶点的顶点描述符。 
vertex_descriptor
add_vertex(const VertexProperties& p,
           adjacency_list& g)
使用指定的属性将顶点添加到图中。 返回新顶点的顶点描述符。
void clear_vertex(vertex_descriptor u, adjacency_list& g)
删除与顶点 u 的所有边。 顶点仍然出现在图的顶点集中。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()对于所有以u为源或目标的边。

void clear_out_edges(vertex_descriptor u, adjacency_list& g)
从顶点 u 删除所有出边。 顶点仍然出现在图的顶点集中。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()对于所有以u作为源。

此操作不适用于无向图（请改用clear_vertex()）。

void clear_in_edges(vertex_descriptor u, adjacency_list& g)
从顶点 u 删除所有入边。 顶点仍然出现在图的顶点集中。

对描述符和迭代器稳定性的影响与对每个删除的边调用remove_edge()对于所有以u作为目标。

此操作仅适用于双向图。

void remove_vertex(vertex_descriptor u, adjacency_list& g)
从图的顶点集中删除顶点 u。 假设删除顶点 u 时没有与顶点 u 关联的边。 确保这一点的 一种方法是预先调用clear_vertex()beforehand.

如果VertexList模板参数adjacency_listwasvecS，则此操作会使图的所有顶点描述符、边描述符和迭代器失效。 每个顶点的内置vertex_index_t属性都会重新编号，以便在操作后，顶点索引仍然形成连续范围[0, num_vertices(g))。 如果您使用基于内置顶点索引的外部属性存储，则需要调整外部存储。 另一种选择是不使用内置顶点索引，而是使用属性来添加您自己的顶点索引属性。 如果您需要频繁使用remove_vertex()函数，则listS选择器是VertexList的边数。 模板参数。

属性映射访问器

template <class PropertyTag>
property_map<adjacency_list, PropertyTag>::type
get(PropertyTag, adjacency_list& g)

template <class PropertyTag>
property_map<adjacency_list, Tag>::const_type
get(PropertyTag, const adjacency_list& g)
返回由PropertyTag。PropertyTag指定的顶点属性的属性映射对象。PropertyTag必须与图中 的属性之一匹配 模板参数。
template <class PropertyTag, class X>
typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
get(PropertyTag, const adjacency_list& g, X x)
这返回x，其中x的属性值。
template <class PropertyTag, class X, class Value>
void
put(PropertyTag, const adjacency_list& g, X x, const Value& value)
是顶点描述符或边描述符。 这将设置x的对。 返回一对出边迭代器，它们给出了从value. x的属性值。的属性值。Value必须可转换为 
template <class GraphProperties, class GraphPropertyTag>
typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(adjacency_list& g, GraphPropertyTag);
typename property_traits<property_map<adjacency_list, PropertyTag>::type>::value_type返回由GraphPropertyTagg。指定的属性，该属性附加到图对象graph_property
template <class GraphProperties, class GraphPropertyTag>
const typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(const adjacency_list& g, GraphPropertyTag);
typename property_traits<property_map<adjacency_list, PropertyTag>::type>::value_type返回由GraphPropertyTagg。指定的属性，该属性附加到图对象graph_property

属性类在

template<class SavingArchive>
SavingArchive& operator<<(SavingArchive& ar, const adjacency_list& graph);
序列化
将图序列化到存档中。 要求图的顶点和边属性是 Serializable。 包含 boost/graph/adj_list_serialize.hpp。
template<class LoadingArchive>
LoadingArchive& operator>>(LoadingArchive& ar, const adjacency_list& graph);
从存档中读取图。 要求图的顶点和边属性是 Serializable。
将图序列化到存档中。 要求图的顶点和边属性是 Serializable。 包含 boost/graph/adj_list_serialize.hpp。

另请参阅

adjacency_list_traits, property_map, graph_traits
版权所有 © 2000-2001 Jeremy Siek，印第安纳大学 (jsiek@osl.iu.edu)
Lie-Quan Lee，印第安纳大学 (llee@cs.indiana.edu)
Andrew Lumsdaine，印第安纳大学 (lums@osl.iu.edu)