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

Question

是否有任何算法的实现，在Golang中具有自边缘的有向多图中查找所有周期？我发现约翰逊算法是有向图的最佳解决方案，并且实现是在gonum中给出的，但它仅适用于有向图（而不是多图），并且不支持自边缘（实际上gonum中的有向图不支持自边缘）。有没有一个简短/聪明的黑客，我可以在gonum中做约翰逊的工作与自我边缘的定向多图？还是在Golang中还有其他实现？可以做的一件事是在自边缘之间创建一个虚拟节点，并在同一对节点之间的重复边缘之间创建一个虚拟节点。这将删除所有自体边，图形将是有向的，我可以在这里使用约翰逊的。但是有更好的方法吗？

Answer 1

• 自边缘 ：您只需要扫描图形的每个节点并检查是否存在自我边缘。如果有 ：添加到循环列表X -> X

• 多图：第一种算法将生成路径作为顶点序列。当您有此列表时，请迭代从 到 的所有可能的边缘，然后从 到 的所有可能的边缘，依此类推...X1 -> X2 -> X3 -> ...X1X2X2X3

---

• “聪明”的黑客：从你的多图中，创建一个新的图，其中的边缘也显示为顶点：GG2G

# 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