广度优先在图、图或Pregel中的实现

Question

有没有人知道在图形处理系统中是否存在广度优先(来自多个来源)的实现- Giraph、Pregel或Graphchi。

或者请告诉我在这两个系统上的一些更简单的实现。

Answer 1

在Giraph用户邮件列表中，你可以找到一些关于BFS实现的讨论--我猜也是一个实现。

我过去曾对Giraph进行过这种类型的搜索，它们可以在以下位置获得：

https://github.com/MarcoLotz/GiraphBFSSO

https://github.com/MarcoLotz/GiraphBFSTO

它们之间的不同之处在于，一个是面向目标的，另一个是面向结构的。

尽管它们不是来自多个起始顶点，但可以很容易地修改代码以支持它:)

Answer 2

您正在寻找多种子广度优先搜索(BFS)算法。

对于Giraph，这仍然是一个开放的问题，可以在这个feature request中读到。

对于Pregel，你不能期望找到任何开放的算法，因为Pregel是Google的一个闭源图形系统。

我想最简单的方法就是使用Github中的代码，然后分别为每个源代码执行它。优化算法运行时复杂度的一个想法是对第一个种子顶点执行BFS，并将结果重用于后续的顶点种子(第一个BFS生成一个生成树，可以很容易地转换为任何给定种子顶点的BFS顺序)。

然而，KISS建议对k个种子顶点简单地执行k次BFS，直到遇到性能问题(由于BFS的线性运行时复杂性，这是不太可能的)。