CODEWITHSUNDEEP
pythongraphgraph-theory
Captastic
Captastic

Reputation: 1066

Removing similar, but not identical, lists from a list of lists in python

I am identifying loops in directional graphs. My function returns a list of lists which store the nodes in any loops found.

For instance in a graph where the nodes are connected like this:

(1,2)(2,3)(3,4)(3,5)(5,2)

a loop is found at 2 - 3 - 5 so the function would return:

[[2,3,5]]

There are occasions where there are multiple loops which would return something like:

[[2,3,4][6,7,8,9]]

This is great, but if there are multiple start points in a graph which join the same loop at different points, such as in the graph:

(1,2)(2,3)(3,4)(3,5)(5,2)(6,3)

both nodes 1 and 6 join the same loop at different points which would return:

[[2,3,5][3,5,2]]

So here there are two identical loops, which are not identical lists. I want to identify such duplication and remove all but one (it doesn't matter which).

Note, there may be cases where there are multiple loops, one which is duplicated, such as:

[[2,3,5][3,5,2][7,8,9,6]]

I've tried looking into itertools:

loops.sort()
list(loops for loops,_ in itertools.groupby(loops))

but that's not helped, and I'm not 100% sure that this is appropriate anyway. Any ideas? I'm on python 2.4. Thanks for any help.

Upvotes: 0

Views: 99

Answers (3)

Andy Hayden
Andy Hayden

Reputation: 375425

First you need to define what similar is, because it is stronger than set:

def is_similar(X,Y):
    n = len(X)
    return len(Y) == n and any( all( X[i] == Y[(i+j)%n] 
                                     for i in range(n) )
                                for j in range(1,n) ) #the 1 here so that identical lists are not similar

The distinction is important as the path (1,2,3,4) is different from the path (1,3,2,4), they do not correspond to the same loop.

def remove_similars(L):
     new_L = []
     for item in L:
         if not any( is_similar(item, l) for l in new_L ):
             new_L.append(item)
     return new_L

Upvotes: 1

DSM
DSM

Reputation: 353009

If you only care about the elements of each loop, and not the order, I would canonicalize each loop by sorting it, and then take the set:

>>> loops = [[2,3,5],[3,5,2],[7,8,9,6]]
>>> set(tuple(sorted(loop)) for loop in loops)
set([(2, 3, 5), (6, 7, 8, 9)])

In order to use set here you need to convert to a tuple. You could convert the tuples back to lists, or turn the final set back into a list (maybe even using sorted to get a canonical order), but whether you'd actually need to would depend upon what you'd be doing with it.

If you need to preserve path order, I'd canonicalize in a different way:

def rotated(l, n):
    return l[n:] + l[:n]

def canonicalize(l):
    m = min(l)
    where = l.index(m)
    return rotated(l, where)

and then

>>> loops = [[2,5,3], [5,3,2], [7,8,6,9]]
>>> set(tuple(canonicalize(loop)) for loop in loops)
set([(2, 5, 3), (6, 9, 7, 8)])

[Edit: note that this simple canonicalization only works if each vertex can only be visited once in a path.]

Upvotes: 3

Pierre GM
Pierre GM

Reputation: 20339

You could take a set of each of your lists. If two sets are equal, then you have a duplicated loop. You're losing the order of the nodes in the loop, though, but does it matter to you ?

Upvotes: 0

Related Questions