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)
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
我们可以从一个给定的“开始节点”执行“闭包”操作,方法是从当前“端点”重复获取“图形边”的并集,直到找不到新的端点。我们最多需要这样做(节点数-1)次,因为这是路径的最大长度。(这样做可以避免在有循环的情况下陷入无限递归;在一般情况下,这样做会浪费迭代,但是可以避免检查是否完成的工作,即在给定的迭代中没有进行任何更改。)
(实际上我测试过一次;)
没有可传递闭包的内置项。
不过,它们的实现非常简单。
我的看法是:
呼叫:
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)])
只是一个快速的尝试:
执行它,我们会得到
相关问题 更多 >
编程相关推荐