0
l1= [(1, 4), (1, 5), (2, 4), (3, 5)]
l2= [(3, 5), (1, 4), (2, 3), (3, 4), (2, 5), (4, 5)]

I have two edge list and I want to compare the edges in the two list and form a vector of the form [1,1,0,0,0,0].This is formed by comparing the edges of l1 with l2 and if an edge is present in l2 then 1 otherwise 0.The thing to ensure is that if the edge in the edge list is in the form (1,4) in l1 and (4,1) is present in l2 then also it should treat it as found.

edit-In the real dataset the vector size is in the range of 100,000

ubuntu_noob
  • 2,305
  • 6
  • 23
  • 64
  • did you consider representing your graphs as adjacency lists rather than lists of edges in the first place (i.e., as a list of lists/sets such that the i-th of these contains all neighbors of vertex i)? this allows for performing checks like the one you need efficiently. – paho Dec 02 '17 at 10:32

2 Answers2

1

it may be worth the one time cost of making l1 into a set, lookups are then very fast:
Python - convert list into dictionary in order to reduce complexity

set_l1 = set(l1)  # note different syntactic level from pho7's ans

[int(t in set_l1 or t[::-1] in set_l1) for t in l2]

Out[86]: [1, 1, 0, 0, 0, 0]
f5r5e5d
  • 3,656
  • 3
  • 14
  • 18
0

If l1 is not too long (such that time and memory are no issues), then you could do something like this:

l1_set = [set(e) for e in l1]
vec = [int(set(e) in l1_set) for e in l2]

Then vec is indeed [1, 1, 0, 0, 0, 0].

EDIT: Alternatively, you could represent your graphs as adjacency lists (rather than edge lists) in the first place:

l1 = [[], [4, 5], [4], [5], [], []]
l2 = [[], [4], [3, 5], [5, 4], [5], []]

This way, you could perform the required check without creating any kind of intermediate datastructure at all:

>>> [[int(vertex in l1[n] or n in l1[vertex]) for n in neighbors] for vertex, neighbors in enumerate(l2)]
[[], [1], [0, 0], [1, 0], [0], []]

If your graphs have many edges, though, then you might want to think about variations of this approach that represent graphs as lists of sets (as pointed out by f5r5e5d).

paho
  • 1,162
  • 9
  • 13