Boost C++ 库

...世界上最受推崇、设计最专业的 C++ 库项目之一。 Herb SutterAndrei AlexandrescuC++ 编码标准

Boost 图库:邻接表 - Boost C++ 函数库

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

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

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

顶点表的模板参数adjacency_list类控制用于表示外部二维容器的容器类型。的出边表模板参数控制用于表示边列表的容器类型。对于出边表and顶点表的选择将决定图结构的空间复杂度,并决定各种图操作的时间复杂度。可能的选择和权衡在“选择 EdgelistVertexList”一节中讨论。

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

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

关于如何使用adjacency_list类的教程在“使用 adjacency_list”一节中。

示例

examples/family_tree.cpp 中的示例展示了如何用图表示族谱。

模板参数

Parameter描述Default
出边表 用于表示每个顶点的边列表的容器选择器。 vecS
顶点表 用于表示图的顶点列表的容器选择器。 vecS
有向 一个选择器,用于选择图是有向的、无向的,还是有向且具有双向边访问(访问出边和入边)的。选项包括directedS, undirectedSbidirectionalS. directedS
VertexProperties 用于指定内部属性存储。 no_property
EdgeProperties 用于指定内部属性存储。 no_property
GraphProperties 用于指定图对象的属性存储。 no_property
EdgeList 用于表示图的边列表的容器选择器。 listS

模型

VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.

定义位置

boost/graph/adjacency_list.hpp

此外,序列化功能位于 boost/graph/adj_list_serialize.hpp 中。

顶点和边属性

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

如果顶点表图的vecS,则图具有内置顶点索引,可通过vertex_index_t属性的属性映射访问。索引范围为[0, num_vertices(g))并且是连续的。当删除顶点时,索引会进行调整以保持这些属性。在使用这些索引访问外部属性存储时需要小心。顶点索引的属性映射是 可读属性映射 的模型。

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

在更改图结构(通过添加或删除边)时需要小心。根据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一起使用时,它会使图的所有迭代器和描述符(例如viandvi_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)**)的边描述符和迭代器的影响。

通常,如果您希望顶点和边描述符稳定(永不失效),则使用listSsetS作为顶点表and出边表的模板参数adjacency_list。如果您不太关心描述符和迭代器的稳定性,而更关心内存消耗和图遍历速度,则使用vecS作为顶点表和/或出边表模板参数。

下表总结了哪些操作会导致描述符和迭代器失效。在表中,EL出边表and的缩写,表示顶点表。“相邻迭代器”类别包括out_edge_iterator, in_edge_iteratoradjacency_iterator类型。有关描述符和迭代器失效的更详细说明,请参阅每个操作的文档。

表: 描述符和迭代器失效摘要。
函数 顶点描述符 边描述符 顶点迭代器 边迭代器 Adj Iter
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
and
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::vertex_descriptor

与 __________ 关联的顶点描述符的类型,它与 __________ 的类型相同adjacency_list.
graph_traits<adjacency_list>::edge_descriptor
and
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
and
adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::directed_category

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

这描述了图类是否允许插入并行边(具有相同源和目标的边)。两个标签是allow_parallel_edge_taganddisallow_parallel_edge_tag来填充。该setSandhash_setS变体不允许并行边,而其他变体允许并行边。
graph_traits<adjacency_list>::vertices_size_type
and
adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::vertices_size_type


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


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

用于处理图中与顶点相邻的边数量的类型。
property_map<adjacency_list, Property>::type
and
property_map<adjacency_list, Property>::const_type

图中顶点或边属性的属性映射类型。特定属性由Property模板参数指定,并且必须匹配VertexPropertiesEdgeProperties
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)来填充。该EdgeIteratorandEdgePropertyIterator必须是 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)
返回一个迭代器范围,提供对图的顶点集的访问使用标准和运行时支持库的调试版本。.
std::pair<edge_iterator, edge_iterator>
edges(const adjacency_list& g)
返回一个迭代器范围,提供对图的边集的访问使用标准和运行时支持库的调试版本。.
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u, const adjacency_list& g)
返回一个迭代器范围,提供对顶点相邻顶点的访问u在图使用标准和运行时支持库的调试版本。的两个图之间的等价顶点。例如,如果u -> v是图中的一条边,那么v将在此迭代器范围内。
std::pair<inv_adjacency_iterator, inv_adjacency_iterator>
inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& 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在图使用标准和运行时支持库的调试版本。。如果图是无向的,这个迭代器范围提供对顶点所有相邻边的访问u。对于有向图和无向图,对于出边e, source(e, g) == uandtarget(e, g) == v其中v是与 __________ 相邻的顶点u.
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const adjacency_list& g)
返回一个迭代器范围,提供对顶点入边的访问v在图使用标准和运行时支持库的调试版本。的邻接顶点的访问。此操作仅在bidirectionalS被指定给有向模板参数。对于入边e, target(e, g) == vandsource(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被指定给有向模板参数。
vertices_size_type
num_vertices(const adjacency_list& g)
返回图中的顶点数使用标准和运行时支持库的调试版本。.
edges_size_type
num_edges(const adjacency_list& 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到顶点**v**的边,则返回一对,包含这样的一条边和true。如果在**u**和**v**之间没有边uandv,则返回一对,包含一个任意的边描述符和false.
std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const adjacency_list& g)
。返回一对出边迭代器,给出从uv到**v**的所有平行边的范围。此函数仅在出边表作为adjacency_list是一个根据目标顶点对出边进行排序并允许平行边的容器时才起作用。multisetS选择器选择这样的容器。

结构修改


std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         adjacency_list& g)
将边*(u,v)*添加到图中,并返回新边的边描述符。对于不允许并行边的图,如果边已存在于图中,则不会添加重复边,并且bool标志将为false。当标志为false时,返回的边描述符指向已存在的边。

新边在出边列表中的位置通常是未指定的,尽管可以通过选择出边表来完成出边列表的排序。如果顶点表选择器是vecS,并且顶点描述符uv(它们是整数)的值大于图中当前顶点的数量,则图将被放大,使顶点数量变为std::max(u,v) + 1.

如果出边表选择器是vecS则此操作将使顶点 *u* 的任何out_edge_iterator失效。如果出边表是用户定义的容器,并且在调用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)
失效。p作为边内部属性存储的值。另请参阅前面的add_edge()将边*(u,v)*添加到图中并附加
void remove_edge(vertex_descriptor u, vertex_descriptor v,
                 adjacency_list& g)
非成员函数以获取更多详细信息。

从图中移除边*(u,v)*。出边表选择器是vecS此操作会导致任何指向边*(u,v)*的未决边描述符或迭代器失效。此外,如果edge_iterator.


void remove_edge(edge_descriptor e, adjacency_list& g)
从子图及其所有祖先中移除e,则此操作将使指向顶点*u*的边列表中的任何迭代器失效,在无向和双向情况下,也会使指向顶点*v*的边列表中的任何迭代器失效。此外,对于有向图,这会使任何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)
template <class Predicate>
void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
                        adjacency_list& g)
具有相同的效果。不同之处在于,对于有向图,此函数的时间复杂度为常数,而谓词的时间复杂度为*O(E/V)*。

从图中移除所有满足remove_edge()的顶点*u*的出边。也就是说,如果谓词应用于边描述符时返回 true,则移除该边。


template <class Predicate>
void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
                       adjacency_list& g)
对描述符和迭代器稳定性的影响与对每条被移除的边调用谓词的时间复杂度为*O(E/V)*。

从图中移除所有满足remove_edge()的顶点*u*的出边。也就是说,如果谓词应用于边描述符时返回 true,则移除该边。

相同。adjacency_list从图中移除所有满足


template <class Predicate>
void remove_edge_if(Predicate predicate, adjacency_list& g)
的顶点*v*的入边。此操作适用于无向和双向谓词的时间复杂度为*O(E/V)*。

从图中移除所有满足remove_edge()的顶点*u*的出边。也就是说,如果谓词应用于边描述符时返回 true,则移除该边。


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)
的边。

从图中移除所有满足remove_edge()向图中添加一个顶点,并返回新顶点的顶点描述符。u向图中添加一个具有指定属性的顶点。返回新顶点的顶点描述符。


void clear_out_edges(vertex_descriptor u, adjacency_list& g)
删除所有与顶点*u*相连的边。该顶点仍然存在于图的顶点集中。

从图中移除所有满足remove_edge()向图中添加一个顶点,并返回新顶点的顶点描述符。u的边,其源或目标是

。从顶点*u*删除所有出边。该顶点仍然存在于图的顶点集中。clear_vertex()作为源。此操作不适用于无向图(请改用


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

从图中移除所有满足remove_edge()向图中添加一个顶点,并返回新顶点的顶点描述符。u作为目标。此操作仅适用于双向图。

从图的顶点集中移除顶点*u*。假定在移除时没有与顶点*u*相连的边。确保这一点的一种方法是事先调用


void remove_vertex(vertex_descriptor u, adjacency_list& g)
clear_vertex()。如果是

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


属性映射访问器 (Property Map Accessors)


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必须匹配图的 __________ 中指定的属性之一VertexProperty模板参数。
template <class PropertyTag, class X>
typename property_traits<property_map<adjacency_list, PropertyTag>::const_type&gt::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)
这将设置 __________ 的属性值xvalue. x是顶点还是边描述符。必须可转换为typename property_traits<property_map<adjacency_list, PropertyTag>::type&gt::value_type
template <class GraphProperties, class GraphPropertyTag>
typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(adjacency_list& g, GraphPropertyTag);
返回由GraphPropertyTag指定并附加到图对象的属性使用标准和运行时支持库的调试版本。来填充。该graph_propertytraits 类定义在 boost/graph/adjacency_list.hpp 中。
template <class GraphProperties, class GraphPropertyTag>
const typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(const adjacency_list& g, GraphPropertyTag);
返回由GraphPropertyTag指定并附加到图对象的属性使用标准和运行时支持库的调试版本。来填充。该graph_propertytraits 类定义在 boost/graph/adjacency_list.hpp 中。

Serialization


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

另请参阅

adjacency_list_traits, property_map, graph_traits

版权所有 © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)
李列权,印第安纳大学 (llee@cs.indiana.edu)
Andrew Lumsdaine,印第安纳大学 (lums@osl.iu.edu)