transthon đóng cửa python tuples

Question

Có ai biết nếu có một con trăn xây dựng để tính toán đóng cửa transitive của tuple?

Tôi có tuples dạng (1,2),(2,3),(3,4) và tôi đang cố gắng để có được (1,2),(2,3),(3,4),(1,3)(2,4)

Cảm ơn.

Answer 1

Chỉ cần một nỗ lực nhanh chóng:

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 

Thi nó, chúng ta sẽ nhận được

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

Không có BUILTIN cho đóng cửa bắc cầu.

Chúng khá đơn giản để triển khai.

Dưới đây là quan điểm của tôi về nó:

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 

gọi: transitive_closure([(1,2),(2,3),(3,4)])

kết quả: set([(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (2, 4)])

gọi: transitive_closure([(1,2),(2,1)])

kết quả: set([(1, 2), (1, 1), (2, 1), (2, 2)])

Answer 3

Chúng tôi có thể thực hiện thao tác "đóng cửa" từ "nút bắt đầu" nhất định bằng cách liên tục lấy một liên kết "cạnh đồ thị" từ "điểm cuối" hiện tại cho đến khi không tìm thấy điểm cuối mới. Chúng ta cần phải làm điều này nhiều nhất (số nút - 1) lần, vì đây là chiều dài tối đa của một đường dẫn. (Làm mọi thứ theo cách này tránh bị kẹt trong đệ quy vô hạn nếu có chu kỳ, nó sẽ lãng phí sự lặp lại trong trường hợp chung, nhưng tránh việc kiểm tra xem chúng ta có thực hiện nghĩa là không có thay đổi nào được thực hiện trong một lần lặp lại không.)

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) 

(tôi thực sự thử nghiệm nó cho một lần;))

Answer 4

dưới mức tối ưu, nhưng khái niệm đơn giản giải pháp:

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 

này sẽ không hoạt động khi có một chu kỳ trong quan hệ, tức là một điểm phản .

Answer 5

Dưới đây là một cơ bản giống như một từ @soulcheck hoạt động trên danh sách kề chứ không phải là danh sách cạnh:

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

Nếu bạn có rất nhiều tupels (hơn 5000), bạn có thể muốn xem xét sử dụng mã scipy cho sức mạnh ma trận (xem thêm 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]))] 

Trong trường hợp tốt nhất, bạn có thể chọn một cách khôn ngoan n nếu bạn biết một chút thông tin về mối quan hệ của bạn/đồ thị - đó là bao lâu con đường dài nhất có thể . Nếu không, bạn phải chọn M.shape[0], điều này có thể thổi phồng vào mặt bạn.

Đường vòng này cũng có giới hạn của nó, đặc biệt bạn nên chắc chắn hơn mức đóng không quá lớn (kết nối không quá mạnh), nhưng bạn sẽ gặp vấn đề tương tự trong việc triển khai python.