在后端中止 Boost Graph DFS

Question

我正在尝试提高 Graph 算法的性能，但遇到了一些问题。

我的图表类型定义如下所示：¨

typedef boost::adjacency_list<boost::multisetS, boost::vecS, boost::directedS, boost::no_property, indexProperty> graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor_t;
typedef boost::graph_traits<graph_t>::edge_descriptor edge_descriptor_t;

我正在处理的图相当大，它有大约 580 万条边和 100 个顶点。

我正在做的是：

确定图的强连通分量
对每个组件执行深度优先搜索以检测图中的循环。

我通过在图中搜索后边来查找图中的循环。对于我检测到的每个周期，我必须执行一个更改图形的操作。（我必须从图中删除循环边）。删除循环后，我重新启动 DFS 以找到下一个循环。

我现在的问题是：

如何在后沿检测时终止 DFS？

我做了一些研究，发现了以下问题： following question on Whosebug

这里建议使用Boosts depth first visit。然而，在 documentation 它表示在调用 discover_vertex 之后立即调用终止函数。是否可以在调用 back_edge 后终止？

另外，是否可以直接使用depth_first_visit，而无需像上述问题那样复制boost源代码？

到目前为止，我所做的是在访问者中存储一个标志，一旦检测到循环，该标志就会设置为真，并在访问者中的每个函数调用上检查这个标志。这会向 dfs 添加很多不必要的函数调用，并且会花费很长时间。

感谢您的帮助！

澄清一下： 我使用的算法在 geeksforgeeks dot org/detect-cycle-in-a-graph 上有描述（抱歉，我不能 post 超过两个链接）

我在伪代码中所做的是：

 For each strongly connected component in g
   do
      perform dfs until first back edge
      perform some task on the cycle edges
      remove cycle edges from g
   until no cycle in DFS

@petr：为什么您认为不需要重新启动 dfs？

Answer 1

终止 boost::depth_first_search 的规范解决方案是抛出异常（您自己定义的类型）。然后您的代码可以捕获异常，做任何您想做的事，然后继续。

也就是说，我同意在每个后端重新启动 DFS 的担忧。如果你有一个强连接的组件，你可以只删除它的根顶点的所有边，并在结果图中找到 SCCs 吗？但无论如何，这是 algorithms.stackexchange.com 的主题，如果你想中止 DFS，异常是解决方案。

在后端中止 Boost Graph DFS

Abort Boost Graph DFS on Back Edge

c++

boost

graph

depth-first-search