Find circular references of first order (bi-directional referencing)

Question

I have million of objects, each with an array smaller than 10 elements, which are the names of other objects in the dataset.
Basically

{
 a:[b,c,d,],
 b:[c,d,e],
 c:[a,e,f],
 ...
 e:[a,b,c]
}

will result in (a,c),(b,e),(c,e) As for each of this tuples element A points to element B and vice-versa, e.g b has e in his list, and e has b

Any ideas beside for elem in elems: {for elem in elems:{...}}?

Answer 1

You can pull this off in a single set comprehension, which filters down the key value pairs of your dictionary down to only those which have this bi-directional property:

input = {
  "a": ["b", "c", "d"],
  "b": ["c", "d", "e"],
  "c": ["a", "e", "f"],
  "e": ["a", "b", "c"],
}

all_arcs = {
    tuple(sorted((source, destination)))
        for (source, destinations) in input.items()
            for destination in destinations
                if destination in input and source in input[destination]
    }


print(all_arcs)

There's lots of room for improvement, but it's a decent start:

• I had to do a nasty tuple(sorted(...)) trick, so that if (a, e) and (e, a) exist, both sort down to (a, e), and by the uniqueness of sets, only one (a, e) pair remains.
• I'm doing linear searching of the arrays, which will get slow if the nodes each have many arcs.
• I'm also doing some excess checking (i.e. if we know (a, e) is a pair from when we visited key a, we don't need to check (e, a) once we reach key e.