枚举有向图的所有最小有向环 [英] Enumerating All Minimal Directed Cycles Of A Directed Graph

问题描述

我有一个有向图，而我的问题是枚举该图的所有 minimum （不能构造为其他周期的并集的周期）有向环。这与Tarjan算法输出的内容不同。例如，对于此Wikipedia页面的有向图，我想得到c< -> d和d <-> h作为两个独立的有向环。

I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the Tarjan algorithm outputs. For instance, for the directed graph at this wikipedia page, I would like to get c <-> d and d <-> h as two separated directed cycles.

如果问题不是多项式，我就不知道。我浏览了一篇论文枚举最小Dicut和强连通子图，该论文似乎得出结论，该问题是增量多项式（我不知道这是什么意思），但是我无法为本文提取算法。我也不确定最小的强连接组件是否等于我定义的最小周期。

I don't if this problem is polynomial or not. I ran over a paper "Enumerating Minimal Dicuts and Strongly Connected Subgraphs" that seems to conclude that this problem is incremental polynomial (I don't know what it means), but I am unable to extract an algorithm for this article. I am also not sure if a minimal strongly connected component is equivalent to a minimal cycle as I define it.

有人知道这个问题的答案吗？

Does someone knows the answer to this problem?

预先感谢！

推荐答案

如果我们正在寻找最短的路径

If we are looking for the shortest path cycle, it seems easy enough.

• 只需执行在所有节点上进行宽度优先搜索，以搜索从节点到其自身的最短路径。


• 如果找不到路径，则可以删除该节点，使其处于无周期状态


• 如果找到路径，则找到了最小周期之一（由于我们寻找了最短路径，因此可以确保此周期不会两个较短周期的并集）。
  
  
  
  
  • 将其中的所有节点折叠到一个大的新节点中，并根据需要调整边。
  
  
  • Just do a breadth first search on all nodes searching for the shortest path from a node to itself.
  • if you find no path, you can remove this node it is in no cycle
  • if you find a path, you have found one of your minimal cycles (as we looked for shortest path, we can ensure this cycle can't be the union of two shorter cycles).
    • Collapse all nodes in it in one big new node and adapt edges as necessary.

    继续，直到没有节点为止。

    Go on until there is no node any-more.

    当您处理完所有节点（顶点）后，

    When You you have treated all nodes (vertexes) you have the minimal cycles you where looking for... but there is a trick.

    如果有一个循环用仅初始集合中的节点可以将其保持原样。但是您必须将大节点转换为路径（循环之间的公共边），并且每个大节点都可能被数个这样的路径替换（对于1级的大节点，至少要2个，也就是说，它本身不包含大节点） ）。找到的循环的构建方式使您可以选择任何路径，并且仍然获得最小的循环集（将两个其他的并集无法获得任何循环），但是有几种可能的循环集。您可以添加约束以在大节点中选择路径时始终采用最短路径，但是仍然可以存在相同长度的路径。因此，这个问题的解决方案显然不是唯一的。

    If a cycle is expressed using only nodes from the initial set you can keep it "as is". But you have to translate "big nodes" to paths (common edges between cycles) and every big nodes may be replaced by several such path (at least 2 for a big node of level-1, that is that does not contains big nodes itself). The cycles found are constructed in such a way that you can choose any path and still get a minimal cycle set (no cycle can be get doing the union of two others), but there is several possible such sets. You can add a constraint to always take a shortest path when selecting a path in a big node, but there still can be paths of the same length. So the solution of this problem is clearly enough not unique.

    使用这种幼稚的方法，复杂度将是O（V.（E + V）），其中V是顶点和E的边数。 O（E + V）首先来自广度，最糟糕的是，您必须执行BFS V次。因此，它肯定是更好的多项式。我相信我所描述的实际上是普通情况下的O（log（V）。（E + V）），但我还没有证明（如果是真的）。​​

    With this naive approach complexity would be O(V.(E+V)) where V is the number of vertexes and E the number of edges. O(E+V) comes from breadth first and at worst you have to perform a BFS V times. Hence it is definitely polynomial of better. I believe what I described is really O(log(V).(E+V)) in the average case, but I didn't prove it yet (if it's true).

    这篇关于枚举有向图的所有最小有向环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！