python - 在闭合图中寻找唯一环

Question

我终于设法编写了一个代码来识别当前配置下所有可能的循环。例如下图，下面是我程序的输入。

network2=Pipes.NetworkManager(vertices=[1,2,3,4],
                 nodes=[(1,2),(1,3),(1,4),(2,1),(2,3),
                        (2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)])

network2.search_loop()

现在，我很难从输出中过滤数据以找到唯一的循环。

这是结果:

starting search from 1
--------------------------------------------------------
the loop is complete [1, 2, 3, 1]
the loop is complete [1, 2, 3, 4, 1]
the loop is complete [1, 2, 4, 1]
the loop is complete [1, 2, 4, 3, 1]
the loop is complete [1, 3, 2, 1]
the loop is complete [1, 3, 2, 4, 1]
the loop is complete [1, 3, 4, 1]
the loop is complete [1, 3, 4, 2, 1]
the loop is complete [1, 4, 2, 1]
the loop is complete [1, 4, 2, 3, 1]
the loop is complete [1, 4, 3, 1]
the loop is complete [1, 4, 3, 2, 1]
--------------------------------------------------------
starting search from 2
--------------------------------------------------------
the loop is complete [2, 1, 3, 2]
the loop is complete [2, 1, 3, 4, 2]
the loop is complete [2, 1, 4, 2]
the loop is complete [2, 1, 4, 3, 2]
the loop is complete [2, 3, 1, 2]
the loop is complete [2, 3, 1, 4, 2]
the loop is complete [2, 3, 4, 1, 2]
the loop is complete [2, 3, 4, 2]
the loop is complete [2, 4, 1, 2]
the loop is complete [2, 4, 1, 3, 2]
the loop is complete [2, 4, 3, 1, 2]
the loop is complete [2, 4, 3, 2]
--------------------------------------------------------
starting search from 3
--------------------------------------------------------
the loop is complete [3, 1, 2, 3]
the loop is complete [3, 1, 2, 4, 3]
the loop is complete [3, 1, 4, 2, 3]
the loop is complete [3, 1, 4, 3]
the loop is complete [3, 2, 1, 3]
the loop is complete [3, 2, 1, 4, 3]
the loop is complete [3, 2, 4, 1, 3]
the loop is complete [3, 2, 4, 3]
the loop is complete [3, 4, 1, 2, 3]
the loop is complete [3, 4, 1, 3]
the loop is complete [3, 4, 2, 1, 3]
the loop is complete [3, 4, 2, 3]
--------------------------------------------------------
starting search from 4
--------------------------------------------------------
the loop is complete [4, 1, 2, 3, 4]
the loop is complete [4, 1, 2, 4]
the loop is complete [4, 1, 3, 2, 4]
the loop is complete [4, 1, 3, 4]
the loop is complete [4, 2, 1, 3, 4]
the loop is complete [4, 2, 1, 4]
the loop is complete [4, 2, 3, 1, 4]
the loop is complete [4, 2, 3, 4]
the loop is complete [4, 3, 1, 2, 4]
the loop is complete [4, 3, 1, 4]
the loop is complete [4, 3, 2, 1, 4]
the loop is complete [4, 3, 2, 4]
--------------------------------------------------------

我使用递归(还有什么可能是更好的选择？)来解决问题。现在，在我获得结果后，我发现很难过滤这些结果并找到独特的循环。我对图论的理解是有限的(我刚刚开始阅读它)。从这个已识别的循环中找到唯一循环的有效方法可能是什么？

感谢您的回答，该回答表明重复循环具有在反转时保持不变的特性。例如:

[1,2,3,1]
[1,3,2,1]
[2,3,1,2]

如果它从与上述情况中的第一个和第二个相同的顶点开始，则反转将表明它们是相同的循环，但在第三种情况下，虽然它与前两个相同的循环，但情况有点棘手。现在应该通过该循环中的第三个顶点完成反向操作。当形成循环的顶点数量增加时，这种复杂性会增加。因此，有什么算法可以有效地简化这个问题？我在这里看到了一些递归模式，但它仍然有点复杂，如果有人可以提出简单的解决方案，我会撒谎。

Answer 1

请注意，循环副本具有以下属性:如果您颠倒它的顺序，您将获得原始循环。

为了让您的生活更轻松，您可以决定将具有较小词典索引的循环用于您的解决方案。这意味着，如果您发现循环 1->3->2->1 和 1->2->3->1(根据您的定义，它们是相等的)，您将使用 1->2->3->1 来解决问题。

从这一点开始的最佳方法是反转您发现的每个循环，如果反转模式的词典索引比原始模式低，请忽略该循环。否则将其添加到解决方案中。

查字典索引的方法很简单，就是创建一个乱序的顶点数。

例如:将1->2->3->1翻译成1231和1->3->2->1 到 1321。 1231 小于 1321，因此 1->2->3->1 将被带到解决方案中， 1->3->2->1 将被忽略。

编辑:

为了消除不共享相同起点的重复循环(如在您的示例中，1->3->2->1 和 2->1-> 3->2，可以忽略第一个顶点索引不是循环中最小索引的任何循环。这里2->1->3->2可以忽略因为索引 2 不是循环中最小的。