algorithm - 用于从图中删除循环的 Map Reduce 算法

Question

这个问题对于检测有向图中的循环有很好的答案。不幸的是，制作它的 Map Reduce 版本似乎并不容易。

具体来说，我对用于从有向图中删除循环的 Map Reduce 算法感兴趣。

我已经使用广度优先搜索 (BFS) 算法进行了评估，但我看到的一个问题是两个不同的边缘可能会同时被移除以切断一个循环。这种情况的影响是可以删除太多的边缘。重要的是要删除循环，同时尽量减少删除的边数。

有证据的解决方案是首选！

谢谢。

Answer 1

好吧，如果你想删除所有循环，那么你最终会得到一棵树。所以无论你使用什么算法，你都会删除|E| - (n -1) 条边。（如果它是正确的当然）

但是，问题是删除边是否会导致图不连通。为此，您需要对边缘进行排序（比如说字典顺序）。然后，您应该始终删除循环中最大的边。[我猜正确性的证明非常直接：只需使用 Kruskal 算法，发现它们将是相同的！]

任何生成树算法都可以为您解决问题。根据您要优化的内容（时间或消息复杂性或任何其他性能指标），您会发现不同的算法。BFS 是最好的时间。对于 c > 0 的小于 c(logn + m) 消息，没有算法可以解决该问题。

我喜欢用于 DAG 的一种算法称为 YO-YO。算法描述见：http ://www.site.uottawa.ca/~flocchin/CSI4509/8-yoyo11_fr.pdf

Answer 2

你需要一个迭代的 map reduce 来实现这个算法。有关以迭代 map reduce 为中心的 map-reduce 框架，请参见http://www.iterativemapreduce.org/ 。或http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm了解如何使用 Hadoop 通过图进行广度优先搜索的工作示例使用迭代映射减少。