boost - BGL 需要一个它自己不提供的模型？

Question

我想使用并行 MST 算法 dense_boruvka_minimum_spanning_tree从 boost 。

该算法接口(interface)的一个必需参数是“必须是顶点列表图和分布式边列表图模型”的图。我发现 the only model包含分布式边列表图概念的 boost 是Distributed Adjacency List .但是在 "Graph Concepts" 部分该模型明确表示

"[...] the distributed adjacency list does not model the Vertex List Graph or Edge List Graph concepts [...]

(我强调的)

此时我很困惑。我应该将数据结构传递给框架未提供的 boost 算法的接口(interface)？我是不是误会了什么？

注意:我是 boost 世界的新手。

Answer 1

Boost 图提供了围绕概念的通用算法，并且在历史上包含了非常少的图概念模型。人们通常会将他们的图表放在他们可以适应的一些现有数据结构中。

在这种情况下

At this point I am confused. I'm supposed to pass a data structure to the interface of a boost algorithm which is not provided by the framework?

一点都不奇怪。

---

DistributedAdjacencyList的概念只提供DistributedVertexListGraph当你需要时VertexListGraph .

关键区别突出显示在 DVLG 下:

A Distributed Vertex List Graph is a graph whose vertices are distributed across multiple processes or address spaces. The vertices and num_vertices functions retain the same signatures as in the Vertex List Graph concept, but return only the local set (and size of the local set) of vertices.

换句话说:DVLG 实际上已经只是一个 VLG，只是分布式的。

您要做的是使用 VertexListAdaptor 来“取消分发”DVLG。 :

The vertex list graph adaptor adapts any model of Distributed Vertex List Graph in a Vertex List Graph. In the former type of graph, the set of vertices is distributed across the process group, so no process has access to all vertices. In the latter type of graph, however, every process has access to every vertex in the graph. This is required by some distributed algorithms, such as the implementations of Minimum spanning tree algorithms.