在具有自边的有向多重图中查找所有循环

Question

在 Golang 中是否有任何算法实现在具有自边的有向多重图中查找所有循环？我发现 Johnson's algo is the best solution for directed graphs and an implementation is given in gonum 但它只适用于有向图（不是多图）并且它不支持自边（实际上 gonum 中的有向图不支持自边）。我可以在 gonum 中做任何 short/clever hack 来使 johnson 对具有自边的有向多图进行工作吗？或者 Golang 中还有其他实现吗？

可以做的一件事是在自身边和同一对节点之间的重复边之间创建一个虚拟节点。这将删除所有自边，并且图形将是有向的，我可以在这里使用 Johnson 的。但是有没有更好的方法呢？

Answer 1

self edges：你只需要扫描图的每个节点并检查是否有self edges。如果有：将 X -> X 添加到循环列表
多图：第一个算法将生成作为顶点序列的路径 X1 -> X2 -> X3 -> ...。当你有这个列表时，遍历从 X1 到 X2 的所有可能边，然后遍历从 X2 到 X3 的所有可能边，等等......

“聪明”技巧：从你的多重图 G，创建一个新图 G2，其中 G 的边也出现作为顶点：

# if A and B are connected     # create the following 3 vertices and
# by a single edge in G :      # 2 edges in G2 :

   A ---w--> B                     A -> w -> B


# if A and B are connected     # create the following 4 vertices and
# by two edges in G :          # 4 edges in G2 :

     /--x--\                           /-> x --\
    A       B                        A          B
     \--y--/                           \-> y --/

# etc ...

然后运行您在 G2 上的循环枚举，并根据需要调整输出。

在具有自边的有向多重图中查找所有循环

Finding all cycles in a Directed Multigraph with self edges

go

graph

cycle