Abhishek Tumuluru Abhishek Tumuluru - 1 year ago 85
Python Question

Removing duplicate edges from graph in Python list

My program returns a list of tuples, which represent the edges of a graph, in the form of:

[(i, (e, 130)), (e, (i, 130)), (g, (a, 65)), (g, (d, 15)), (a, (g, 65))]

So, (i, (e, 130)) means that 'i' is connected to 'e' and is 130 units away.

Similarly, (e, (i, 130)) means that 'e' is connected to 'i' and is 130 units away.
So essentially, both these tuples represent the same thing.

How would I remove any one of them from this list?
Desired output:

[(i, (e, 130)), (g, (a, 65)), (g, (d, 15))]

I tried writing an equals function. Would this be of any help?

def edge_equal(edge_tuple1, edge_tuple2):
return edge_tuple1[0] == edge_tuple2[1][0] and edge_tuple2[0] == edge_tuple1[1][0]

Answer Source

If a tuple (n1, (n2, distance)) represents a bidirectional connection, I would introduce a normalization property which constraints the ordering of the two nodes in the tuple. This way, each possible edge has exactly one unique representation.

Consequently, a normalization function would map a given, potentially unnormalized, edge to the normalized variant. This function can then be used to normalize all given edges. Duplicates can now be eliminated in several ways. For instance, convert the list to a set.

def normalize(t):
    n1, (n2, dist) = t
    if n1 < n2: # use a custom compare function if desired
        return t
        return (n2, (n1, dist))

edges = [('i', ('e', 130)), ('e', ('i', 130)), ('g', ('a', 65)), ('g', ('d', 15)), ('a', ('g', 65))]

unique_edges = set(map(normalize, edges))

# set([('e', ('i', 130)), ('d', ('g', 15)), ('a', ('g', 65))])

The normalization function can also be formulated like this:

def normalize((n1, (n2, dist))):
    if n1 >= n2: 
        n1, n2 = n2, n1
    return n1, (n2, dist)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download