在封闭的图中寻找独特的循环(Finding unique loops in the closed g

我终于成功地编写代码，以确定所有的循环可能与当前的配置。例如，对于下面的图像，下面是输入到我的程序。

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是不是在环最小。

Answer 2:

一个简单的方法来做到这一点，以后你能保证你的循环是，是创建一套frozensets的。

>>> loop1 = [1,2,3,4,1]
>>> loop2 = [1,2,4,3,1]
>>> loop3 = [1,2,3,1]
>>> loops = [loop1,loop2,loop3]
>>> loops = set([frozenset(loop) for loop in loops])
>>> loops
set([frozenset([1, 2, 3, 4]), frozenset([1, 2, 3])])

这当然会迫使你的假设，在frozenset的第一项是开始和结束的顶点。