transitive closure python tuples

Question

Does anyone know if there's a python builtin for computing transitive closure of tuples?

I have tuples of the form (1,2),(2,3),(3,4) and I'm trying to get (1,2),(2,3),(3,4),(1,3)(2,4)

Thanks.

Answer 1

There's no builtin for transitive closures.

They're quite simple to implement though.

Here's my take on it:

def transitive_closure(a):
    closure = set(a)
    while True:
        new_relations = set((x,w) for x,y in closure for q,w in closure if q == y)

        closure_until_now = closure | new_relations

        if closure_until_now == closure:
            break

        closure = closure_until_now

    return closure

call: transitive_closure([(1,2),(2,3),(3,4)])

result: set([(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (2, 4)])

call: transitive_closure([(1,2),(2,1)])

result: set([(1, 2), (1, 1), (2, 1), (2, 2)])

Answer 2

Just a quick attempt:

def transitive_closure(elements):
    elements = set([(x,y) if x < y else (y,x) for x,y in elements])

    relations = {}
    for x,y in elements:
        if x not in relations:
            relations[x] = []
        relations[x].append(y)

    closure = set()
    def build_closure(n):
        def f(k):
            for y in relations.get(k, []):
                closure.add((n, y))
                f(y)
        f(n)

    for k in relations.keys():
        build_closure(k)

    return closure

Executing it, we'll get

In [3]: transitive_closure([(1,2),(2,3),(3,4)])
Out[3]: set([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])