传递闭包python元组

Question

有谁知道是否有一个Python内置的计算传递元组闭包？

我有形式(1,2),(2,3),(3,4)的元组，我试图让(1,2),(2,3),(3,4),(1,3)(2,4)

感谢。

Answer 1

只是一个快速的尝试：

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

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

我们可以从给定的“开始节点”通过反复从当前“端点”获取“图边”的联合，直到找不到新的端点来执行“闭包”操作。我们最多需要这样做（节点数量为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 4

最理想的，但在概念上简单的解决方案：

def transitive_closure(a): 
    closure = set() 
    for x, _ in a: 
     closure |= set((x, y) for y in dfs(x, a)) 
    return closure 

def dfs(x, a): 
    """Yields single elements from a in depth-first order, starting from x""" 
    for y in [y for w, y in a if w == x]: 
     yield y 
     for z in dfs(y, a): 
      yield z 

时，有一个在关系的周期，即反身指出这将无法正常工作。

Answer 5

这里有一个基本相同，从@soulcheck的一个上邻接表的作品，而不是边列表：

def inplace_transitive_closure(g): 
    """g is an adjacency list graph implemented as a dict of sets""" 
    done = False 
    while not done: 
     done = True 
     for v0, v1s in g.items(): 
      old_len = len(v1s) 
      for v2s in [g[v1] for v1 in v1s]: 
       v1s |= v2s 
      done = done and len(v1s) == old_len 

Answer 6

如果你有很多tupels（5000多），你可能要考虑使用矩阵权力SciPy的代码（见http://www.ics.uci.edu/~irani/w15-6B/BoardNotes/MatrixMultiplication.pdf）

from scipy.sparse import csr_matrix as csr 

M  = csr(([True for tup in tups],([tup[0] for tup in tups],[tup[1] for tup in tups]))) 
M_ = M**n #this is the actual computation 
temp = M_.nonzero() 
tups_ = [(temp[0][i],temp[1][i]) for i in xrange(len(temp[0]))] 

在最好的情况下，您可以选择n明智的，如果你知道一些关于你们的关系/图 - 这是最长的路径可以多久。否则，你必须选择M.shape[0]，这可能会炸毁你的脸。

这条弯路也有它的限制，特别是你应该确定闭合不会太大（连通性不太强），但是你在python实现中会遇到同样的问题。