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

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:{...}}`?

• "will result in (a,c),(a,e),(c,e) As for each of this tuples element A points to element B and vice-versa." i don't understand the relationship. Could you elaborate? Apr 19, 2020 at 20:21

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`.
• That's a bad idea, it's O(n^2), with the only parallel option is the inner loop. I thought a map-reduce option is possible. Apr 19, 2020 at 21:12
• @DsCpp No, it's not a bad. It might be a bad idea in whatever constraints you might have envisioned in your head, but didn't share in your post. You never said anything about parallelism being necessary. Linear time operations are possible (generate a set with all arcs, then do constant-time checks with it), but they take `O(node_count * avg_arcs_per_node)` (which you approximated to `O(n^2)`) extra space. We're not mind readers, without specifying what you're looking for, don't have high hopes for results aimed at simplicity and generality. Apr 19, 2020 at 21:16
• The avg_arcs_per_node is `O(1)`, Don't get me wrong, thank you very much for the fruitful discussion. As this is an engineering forum, I'll always prefer the best approach, even if one did not specify it is needed by the specs. Apr 19, 2020 at 21:18
• @DsCpp So then this is a linear time algorithm. You can't get better than that, asymptotically speaking. Apr 19, 2020 at 21:20
• "Best" is subjective. WHat's better? Using extra memory for a look up table to speed up lookups, or using less memory and taking more time? How does each impact cache performance? Which CPU architecture are we talking? What about latency constraints? How much are you willing to pay for developer time (maintenance, testing, code complexity) vs hardware (running a simple but more wasteful algorithm)? There is no "best". Apr 19, 2020 at 21:22