Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Removing duplicate edges from graph in Python list

Tags:

python

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]
like image 467
Abhishek Tumuluru Avatar asked Jul 24 '16 18:07

Abhishek Tumuluru


4 Answers

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, possibly un-normalized, 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(edge):
    n1, (n2, dist) = edge
    if n1 > n2: # use a custom compare function if desired
        n1, n2 = n2, n1
    return (n1, (n2, 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))])
like image 128
Michael Hoff Avatar answered Sep 21 '22 13:09

Michael Hoff


Reconstruct each edge to take its alternate form and check if the alternate form is already in a new set. If it is not then add to the set:

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

r = set()
for e, v in lst:
    if (v[0], (e, v[1])) in r:
        continue
    r.add((e, v))

print(list(r))
# [('i', ('e', 130)), ('g', ('a', 65)), ('g', ('d', 15))]
like image 30
Moses Koledoye Avatar answered Sep 22 '22 13:09

Moses Koledoye


The simplest solution to write would be simply to iterator and check equality of all of them:

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

new = []

for i in range(len(graph)):
    found_equal = False
    for e in range(i,len(graph)):
        if edge_equal(graph[i],graph[e]):
            found_equal = True
            break
    if not found_equal:
        new.append(graph[i])

print new
like image 25
James Avatar answered Sep 21 '22 13:09

James


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

for each in edges:
    try:
        edges.remove((each[1][0], (each[0], each[1][1])))
    except ValueError:
        pass

reverse the vectors and remove them as you traverse

like image 30
be_good_do_good Avatar answered Sep 21 '22 13:09

be_good_do_good