传递闭包python元组

Question

有人知道是否有用于计算元组传递闭包的python内置函数吗？

我有(1,2),(2,3),(3,4)形式的元组，我正在尝试获取(1,2),(2,3),(3,4),(1,3)(2,4)

谢谢。

Answer 1

我们可以从一个给定的“开始节点”执行“闭包”操作，方法是从当前“端点”重复获取“图形边”的并集，直到找不到新的端点。我们最多需要这样做（节点数-1）次，因为这是路径的最大长度。（这样做可以避免在有循环的情况下陷入无限递归；在一般情况下，这样做会浪费迭代，但是可以避免检查是否完成的工作，即在给定的迭代中没有进行任何更改。）

from collections import defaultdict

def transitive_closure(elements):
    edges = defaultdict(set)
    # map from first element of input tuples to "reachable" second elements
    for x, y in elements: edges[x].add(y)

    for _ in range(len(elements) - 1):
        edges = defaultdict(set, (
            (k, v.union(*(edges[i] for i in v)))
            for (k, v) in edges.items()
        ))

    return set((k, i) for (k, v) in edges.items() for i in v)

（实际上我测试过一次；）

Answer 2

没有可传递闭包的内置项。

不过，它们的实现非常简单。

我的看法是：

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

呼叫： transitive_closure([(1,2),(2,3),(3,4)])

结果： set([(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (2, 4)])

呼叫： transitive_closure([(1,2),(2,1)])

结果： set([(1, 2), (1, 1), (2, 1), (2, 2)])

Answer 3

只是一个快速的尝试：

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

执行它，我们会得到

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)])