Переходные кортежи python закрытия

Ответ 1

Там нет встроенных транзитивных замыканий.

Они довольно просты в реализации.

Вот мой пример:

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

Ответ 2

Просто быстрая попытка:

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

Ответ 3

Мы можем выполнить операцию "закрытия" из заданного "start node", повторно применяя объединение "графов графа" от текущих "конечных точек" до тех пор, пока не будут найдены новые конечные точки. Нам нужно сделать это максимум (количество узлов - 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)

(я на самом деле протестировал его один раз;))

Ответ 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

Это не будет работать, если в отношении есть цикл, т.е. рефлексивная точка.

Ответ 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

Ответ 6

Если у вас много тэгелей (более 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.