有向图中用于检测循环的多线程算法

Question

我正在寻找一种并发算法，它可以帮助我检测有向图中的循环。我知道顺序算法使用深度优先搜索和着色，但我认为在多线程环境下它会失败。以下是一个有向图的示例：A->(B,C), B->(D), D->(E), C->(E)，E->(F)。

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

希望以上内容清晰明了。该图中的边都是从上到下的有向边。

对于上述有向图，在并发执行期间可能会进行以下执行。

（我假设的着色方案是白色-未访问，灰色-dfs执行未完成，黑色-已完成执行和访问）

线程1执行Dfs(B)，最终将E染成灰色并执行dfs(E)（导致F）。在此完成之前，线程2执行dfs(C)。它意识到E是灰色的，并报告了一个明显不是的循环。

我检查了Tarjan算法也可以用于检测循环，但我认为在多线程环境下它的执行也不正确。

请有人能帮助我吗？

谢谢。

- Harsha

Answer 1

对于多线程的循环检测，最好使用Kahn算法的变体（用于拓扑排序）而不是DFS。这利用了以下事实：

1）如果有向图无环，则至少有一个顶点没有入边，至少有一个顶点没有出边；

2）没有入边或没有出边的顶点不能参与循环；所以

3）如果删除没有入边或没有出边的顶点，则剩下的有向图与原始图具有相同的循环。

因此，要进行并行循环检测，您可以：

1）首先，使用并行BFS构建一个数据结构，该数据结构跟踪每个顶点的入度和出度。

2）然后，同时删除具有入度或出度为0的顶点。请注意，删除顶点将递减相邻节点的入度或出度。

3）当没有要删除的顶点时，您剩下的所有涉及循环的顶点。如果没有，则原始图是无环的。

并行BFS（步骤1）和并行顶点删除（步骤2）都可以通过并行工作队列轻松完成。在步骤1中，当您第一次看到一个顶点时，请将处理相邻顶点的任务添加到队列中。在步骤2中，当您将顶点的入度或出度减少到0时，请添加一个任务以将其从图中删除。

请注意，如果仅删除入度为0的节点或出度为0的节点，则此算法同样有效，但并行性的机会会稍微降低。

- Matt Timmermans

Answer 2

正如Ira所说，让每个线程使用自己的颜色。

但是，如果您有固定数量的线程，请为每种颜色使用位图。 只要您的处理器支持原子位测试和设置（即x86上的BTST），您甚至不需要锁定，因为每个线程将测试和设置不同的位。

如果该位被设置，则该项将被着色为灰色。

附注：如果您需要更多的颜色，则可以使用更多的位。

- PAntoine

---

你可以访问所有其他线程的颜色（在位数组中）。因此，您可以检查它是否已被其他人访问。如果跳过其他线程访问过的那些（复制颜色），那么可能会起作用？您是否关心其他线程中的循环？ - PAntoine

我需要确保整个图没有环。跳过并不能完全帮助我，因为我认为它无法检测到一些循环。您能否详细说明您正在考虑的算法？ - Harsha

如果另一个线程已经给该项上色，则忽略它（或复制颜色），然后您可以继续处理下一项（我假设每个项都有一个处理步骤）。因此，实质上每个线程都像单线程一样遍历整个树。您可能需要另一种颜色来开始处理，作为信号量，以便两个项不会尝试处理同一项。 - PAntoine

我想不出一种安全地将图形分割而不至少遍历一次的方法。 - PAntoine

所以，如果我有一个像这样的循环 A->B->C->D->A，并且 A、B、C 和 D 是由不同的线程处理的，那么这个循环将不会被报告（至少如果我正确理解了您的解决方案）。 - Harsha

Answer 3

你应该可以轻易地找到解决循环侦测问题的分布式死锁检测算法。

我知道分布式不完全等同于多线程，但你仍然可以在那里找到一些线索。

编辑: 增加了一种受限制的解决方案。

- Pyra

---

感谢 @Pyra，我确实遇到了一个分布式算法，如果没有更好的选择，最终会尝试实现类似的东西，但我真的希望不必这样做。我的主要问题是，为了使分布式算法有效地工作（我猜测），应该尽量减少一个分布式组件（图形的）与另一个分布式组件之间的边缘，而这对于多线程实现来说并非如此（除非在算法开始之前进行一些分离）。 - Harsha

你可以解释一下你的想法吗？大多数分布式算法背后的范式是每个节点存储和处理信息，基于发送给它们的消息。使用线程，您可以轻松地假设您的线程行走的一步是发送的消息，并且当线程访问节点时执行的方法是该节点执行的算法。您的线程程序就像一个分布式算法，具有由线程遍历顺序指定的特定调度。 - Pyra

例如，一个简单的解决方案依赖于可用数据（可以确定哪些节点是根节点，可以访问前任节点上的信息）：每个节点都持有一个变量V，其值最初等于该节点的前任数。每个线程从图的一个根节点开始，并遍历整个图。在每个节点中，线程将V的值减1。如果V>0，则将此节点视为叶子节点，否则，线程可以探索其子节点。完成第一次遍历后，进行第二次遍历。如果任何节点的V>0，则存在循环。 - Pyra

关于我的第一条评论，我遇到了一个并行算法，其中图被分成多个处理器。每个处理器首先尝试在不考虑其他处理器的情况下找到自己内部的循环，并且之后一个处理器通过查看从一个并行处理器到另一个处理器的边来尝试找到一个循环。我可以尝试多线程处理，但是我必须尽量减少两个不同线程（或分布式示例中的处理器）之间的边数。 - Harsha

关于您的第一条信息，第二个例子：A和B是根节点，因此每个节点都启动一个线程。由于C有2个前驱节点，所以V(C)=2。两个线程都将访问C；无论哪个线程先进入C，都会将V(C)减1，使得V(C)=1。由于V(C)>0，这个线程将C视为叶子节点，返回到它来的地方，访问其他分支并返回。第二个线程进入C，发现V(C)=1并将其减少，因此V(C)=0。由于V(C)=0，它不被视为叶子节点，因此该线程继续前往D。V(D)=0且它是叶子节点，因此该线程返回，访问其他分支并返回。每个节点的V值均为0。 - Pyra