我想使用来自boost的并行MST算法dense_boruvka_minimum_spanning_tree。
该算法接口的一个必需参数是"必须是顶点列表图和分布式边缘列表图的模型"的图。我发现唯一包含分布式边缘列表图概念的提升模型是分布式邻接列表。然而,在该模型的"图概念"部分中明确指出
"[...]分布式邻接列表不对顶点列表图或边缘列表图概念进行建模 [...]
(我强调(
在这一点上,我很困惑。我应该将数据结构传递给框架未提供的提升算法的接口吗?我是不是误会了什么?
NB:我在助推器领域很新。
Boost graph提供了围绕概念的通用算法,并且历史上很少包含图概念模型。人们通常会将他们的图表已经存在于一些他们可以适应的现有数据结构中。
从这个角度来看
在这一点上,我很困惑。我应该将数据结构传递给框架未提供的提升算法的接口吗?
甚至没有那么奇怪。
DistributedAdjacencyList 的概念仅在您需要 VertexListGraph 时才提供 DistributedVertexListGraph。
关键区别在DVLG下突出显示:
分布式顶点列表图是其顶点分布在多个进程或地址空间中的图形。
vertices
和num_vertices
函数保留与顶点列表图概念中相同的签名,但仅返回顶点的局部集(和局部集的大小(。
换句话说:DVLG实际上已经只是一个VLG,只是分布式的。
您需要做的是使用VertexListAdaptor"取消分发"DVLG:
顶点列表图适配器适应顶点列表图中分布式顶点列表图的任何模型。在前一种类型的图中,顶点集分布在流程组中,因此没有进程可以访问所有顶点。然而,在后一种类型的图中,每个进程都可以访问图中的每个顶点。这是某些分布式算法所必需的,例如最小生成树算法的实现。
解决方案似乎是"VertexListAdaptor":http://www.boost.org/doc/libs/1_47_0/libs/graph_parallel/doc/html/vertex_list_adaptor.html