Finding unique loops in the closed graph

I finally managed to write a code to identify all the loops possible with the current configuration. For example, for the image below, the following is the input to my program.

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()

Now, I have hard-time in filtering the data from my output to find the unique loop.

This is the result:

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]
--------------------------------------------------------

I used the recursion( what else might be the better choice?) to solve the problem. Now after I obtain the result, I am finding it difficult to filter those results and to find the unique loops. My understanding of graph theory is limited( I just started reading about it). What might be the effective way of finding the unique loop from this identified loops?

Thanks for one answer which suggested that duplicate loop has the property of staying the same when reversed. For eg:

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

Iff it starts from the same vertex as first and second one in above case, reversing will indicate that those are same loops but in the third case, although it is the same loop as the first two, the situation is little tricky. Now the reverse should be done through the third vertex in that loop. This complication will increase when the number of vertex forming the loop increases. As such, any algorithms that effectively simplifies this problem? I see some recursive pattern here but still it is little complicated and would lie to know if somebody can suggest simple solutions.

回答1:

Note that a loop duplicate has the property that if you reverse the order of it you'll get the original loop.

To make your life easy, you can decide that you'll take the loop that has the lesser lexicographic index to your solution. Which means, if you found the loops 1->3->2->1 and 1->2->3->1 (which are equal by your definition), you'll take 1->2->3->1 to the solution.

Best way to proceed from this point would be to reverse each loop you found, if the reverse mode has a lower lexicographic index than the original, ignore the loop. otherwise add it to the solution.

You can check the lexicographic index by a very simple method, just create a number out of the order of vertices.

For example: translate 1->2->3->1 to 1231 and 1->3->2->1 to 1321. 1231 is less than 1321, thus 1->2->3->1 will be taken to the solution and 1->3->2->1 will be ignored.

Edit:

In order to eliminate duplicated loops that don't share the same starting (like in your example, 1->3->2->1 and 2->1->3->2, you can ignore any loop for which the first vertex index is not the smallest index in the loop. here 2->1->3->2 can be ignored as the index 2 is not the smallest in the loop.

回答2:

An easy way to do this, after you can ensure you have the loop that is, is to create a set of 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])])

This of course would force you to assume that the first item in the frozenset is the start and end vertex.