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. n

Solution 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.

Solution 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.