przechodniów python krotek zamknięcia

Question

Czy ktoś wie, czy istnieje python wbudowany do obliczania przechodni zamknięcie krotek?

mam krotki formularza (1,2),(2,3),(3,4) i próbuję dostać (1,2),(2,3),(3,4),(1,3)(2,4)

Dzięki.

Answer 1

Tylko szybka próba:

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 

Wykonywanie go dostaniemy

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

Nie ma wbudowane dla zamknięć przechodnich.

Są one jednak dość łatwe do wdrożenia.

Oto moje zdanie na jej temat:

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 

wezwanie: transitive_closure([(1,2),(2,3),(3,4)])

wynik: set([(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (2, 4)])

wezwanie: transitive_closure([(1,2),(2,1)])

wynik: set([(1, 2), (1, 1), (2, 1), (2, 2)])

Answer 3

Możemy wykonać operację "zamknięcia" z danego "węzła początkowego", powtarzając wielokrotnie połączenie "krawędzi wykresu" z bieżących "punktów końcowych", dopóki nie zostaną znalezione żadne nowe punkty końcowe. Musimy to zrobić co najwyżej (liczba węzłów - 1), ponieważ jest to maksymalna długość ścieżki. (Robienie rzeczy w ten sposób pozwala uniknąć utknięcia w nieskończonej rekursji, jeśli istnieje cykl, spowoduje to marnowanie iteracji w ogólnym przypadku, ale uniknie pracy sprawdzającej, czy jesteśmy skończeni, tj. Że nie wprowadzono żadnych zmian w danej iteracji.)

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) 

(I rzeczywiście przetestowane na raz;))

Answer 4

suboptimal, ale koncepcyjnie proste rozwiązanie:

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 

to nie będzie działać, gdy pojawia się cykl w relacji, czyli refleksyjnego punktu .

Answer 5

Oto jeden zasadniczo taki sam jak ten z @soulcheck który działa na listach sąsiedztwa zamiast list krawędzi:

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

Jeśli masz dużo trójek (ponad 5000), warto rozważyć przy użyciu kodu scipy dla potęg macierzy (patrz również 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]))] 

W najlepszym przypadku można wybrać n mądrze, jeśli wiesz trochę o swojej relacji/wykresu - czyli jak długo najdłuższa ścieżka może być . W przeciwnym razie musisz wybrać M.shape[0], który może wybuchnąć Ci w twarz.

Ten objazd ma swoje ograniczenia, w szczególności powinieneś być pewien, że zamknięcie nie jest zbyt duże (łączność nie jest zbyt silna), ale problem z tym problemem byłby w implementacji Pythona.