algorithm - Giraph、Graphchi 或 Pregel 中的广度优先实现

Question

有谁知道在任何一个图形处理系统——Giraph、Pregel 或 Graphchi 中是否存在广度优先（来自多个来源）实现。

或者请告诉任何一个系统上的一些更简单的实现。

score 4 · Accepted Answer

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

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

它们之间的区别在于，一种是面向目标的，另一种是面向结构的。

虽然它们不是从多个起始顶点开始，但可以轻松修改代码以支持它:)

score 0 · Accepted Answer

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

对于 Giraph，这仍然是一个悬而未决的问题，可以在此功能请求中阅读。

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

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

尽管如此，KISS 建议对 k 个种子顶点简单地执行 k 次 BFS，直到遇到性能问题（由于 BFS 的线性运行时复杂性，这不太可能）。

2 回答 2