首页 文章

在后沿上中止增强图DFS

提问于
浏览
1

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

我的图形typedef如下所示:¨

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以找到下一个循环 .

我现在的问题是:

How can I terminate the DFS on back edge detection?

我做了一些研究,发现了以下问题:following question on stackoverflow

建议使用Boosts深度首次访问 . 但是,在documentation中它表示在调用discover_vertex之后立即调用终结器函数 . 调用back_edge后是否可以终止?

此外,是否可以直接使用depth_first_visit,而无需复制上述问题所提出的增强源代码?

我到目前为止所做的是在访问者中存储一个标志,一旦检测到一个循环就设置为true,并在访问者的每个函数调用中检查该标志 . 这为dfs增加了许多不必要的函数调用,并且需要永远 .

谢谢你的帮助!

To clarify: 我正在使用的算法在geeksforgeeks dot org / detect-cycle-in-a-graph中描述(抱歉,我不能发布两个以上的链接)

我在伪代码中做的是:

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?

1 回答

  • 1

    终止boost :: depth_first_search的规范解决方案是抛出异常(您自己定义的类型) . 然后,您的代码可以捕获异常,执行您想要的任何操作,然后继续 .

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

相关问题