傳遞閉包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實現中會遇到同樣的問題。