Эффективно найти связные компоненты в неориентированном графе с учетом транзитивной эквивалентности

Question

У меня есть набор узлов и функция foo(u,v), которая может определить, равны ли два узла.Под «равным» я подразумеваю транзитивную эквивалентность: If 1==2 и 2==3, затем 1==3, а также: If 1==2 и 1!=4, затем 2!=4

Когда дан набор узлов, я могу найти все связанных компонентов в графе путем передачи каждой возможной комбинации узлов в foo(u,v) (которая возвращает заранее определенные результаты только для целей представления - это не настоящая функция! ) функционирование и построение необходимых ребер.Например:

import networkx as nx
import itertools
from matplotlib import pyplot as plt


def foo(u, v):
    # this function is simplified, in reality it will do a complex 
    # calculation to determine whether nodes are equal.
    EQUAL_EDGES = {(1, 2), (2, 3), (1, 3), (4, 5)}
    return (u, v) in EQUAL_EDGES


def main():
    g = nx.Graph()
    g.add_nodes_from(range(1, 5 + 1))
    for u, v in itertools.combinations(g.nodes, 2):
        are_equal = foo(u, v)
        print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
        if are_equal:
            g.add_edge(u, v)

    conn_comps = nx.connected_components(g)
    nx.draw(g, with_labels=True)
    plt.show()
    return conn_comps


if __name__ == '__main__':
    main()

проблема этого подхода заключается в том, что я получаю много избыточных проверок, которых я хотел бы избежать:

1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2==3  # redundant check, if 1==2 and 1==3 then 2==3 
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4 
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok

Я хочу избежать запуска в O (n ^2) временная сложность.Как правильно (или, возможно, существующей функцией в любой библиотеке Python) эффективно находить все подключенные компоненты с помощью пользовательской функции foo(u,v)?

Answer 1

Вы можете отслеживать, какие ребра транзитивно равны или неравны в двух соответствующих словарях.Для каждой комбинации ребер вы можете выполнить несколько простых проверок за O (1), чтобы увидеть, будет ли вычисление излишним.В противном случае вы выполняете вычисления по первым принципам, а затем, в зависимости от того, равны ли ребра или неравны, вы обновляете вышеупомянутые словари необходимой информацией.Вам все равно придется выполнить проверки на равенство C (n, 2), потому что именно столько комбинаций вы итерируете, но для нескольких из них решение может быть принято мгновенно.

Словарь equal_edges прощеобъяснить, так что давайте начнем с этого.Пара ребер 1-2 равна, но так как ни 1, ни 2 не существуют в качестве ключей (пока что dict пуст), мы создаем набор {1, 2} и присоединяем его к equal_edges[1] и equal_edges[2].Затем мы сталкиваемся с парой равных ребер 1-3.Поскольку equal_edges[1] теперь существует, мы добавляем 3 к его транзитивно равным узлам.Но так как этот набор является общим для обоих ребер 1 и 2, он обновляется в обоих местах.Мы также должны теперь прикрепить этот же набор к equal_edges[3].Все три ребра ссылаются на один и тот же набор в памяти, то есть {1, 2, 3}, поэтому мы не дублируем никакие данные.Теперь, когда дело доходит до проверки пары 2-3 равных ребер, либо 3 in equal_edges[2], либо 2 in equal_edges[3] позволяет нам обходить любые тяжелые вычисления.

Для unequal_edges логика несколько схожа, но мы должныТакже обратитесь к словарю equal_edges для транзитивно неравных краев.Например, пара ребер 1-4 неравна.Но так как 1 транзитивно равен 2 и 3, мы должны иметь unequal_edges[4] = equal_edges[1].Было бы излишним устанавливать unequal_edges[1] = {4}, или unequal_edges[2] = {4} и т. Д. Это потому, что эту информацию можно получить из unequal_edges[4].Это просто означает, что для транзитивно-неравной пары ab нам необходимо выполнить двойную проверку, то есть a in unequal_edges[b] or b in unequal_edges[a].

from itertools import combinations

equal_edges = {}
unequal_edges = {}

def update_equal_edges(a, b):
    def update_one(a, b):
        equal_edges[a].add(b)
        equal_edges[b] = equal_edges[a]
    exists_a = a in equal_edges
    exists_b = b in equal_edges
    if not (exists_a or exists_b):
        s = set((a, b))
        equal_edges[a] = s
        equal_edges[b] = s
    elif exists_a and not exists_b:
        update_one(a, b)
    elif exists_b and not exists_a:
        update_one(b, a)

def update_unequal_edges(a, b):
    exists_a = a in equal_edges
    exists_b = b in equal_edges
    if not (exists_a or exists_b):
        s = set((a, b))
        unequal_edges[a] = s
        unequal_edges[b] = s
    elif exists_a and not exists_b:
        unequal_edges[b] = equal_edges[a]
    elif exists_b and not exists_a:
        unequal_edges[a] = equal_edges[b]

def are_equal_edges(a, b):
    if a in equal_edges.get(b, []):
        print('{}=={} # redundant'.format(a, b))
        return True
    if (a in unequal_edges.get(b, [])) or (b in unequal_edges.get(a, [])):
        print('{}!={} # redundant'.format(a, b))
        return False
    # hardcoded equal edges which are the result
    # of some complex computations
    are_equal = (a, b) in {(1, 2), (1, 3), (4, 5)}
    if are_equal:
        update_equal_edges(a, b)
    else:
        update_unequal_edges(a, b)
    print('{}{}{} # ok'.format(a, '==' if are_equal else '!=', b))
    return are_equal

Операторы печати существуют для демонстрационных целей.Если вы запустите

for a, b in combinations(range(1, 6), 2):
    are_equal_edges(a, b)

, вы получите следующий результат

1==2 # ok
1==3 # ok
1!=4 # ok
1!=5 # ok
2==3 # redundant
2!=4 # redundant
2!=5 # redundant
3!=4 # redundant
3!=5 # redundant
4==5 # ok

Answer 2

Вы можете использовать 0 для представления равенства и math.inf для представления неравенства в качестве весов ребер.Затем для каждой пары узлов u, v вы можете вычислить длину пути от u до v и на основе результата решить, нужно ли запускать (тяжелую) проверку узла:

g = nx.Graph()
g.add_nodes_from(range(1, 6))
for u, v in it.combinations(g.nodes, 2):
    try:
        path = nx.shortest_path(g, u, v)
    except nx.NetworkXNoPath:
        new_weight = 0 if func(u, v) else math.inf
    else:
        weights = list(x['weight'] for x in it.starmap(g.get_edge_data, zip(path[:-1], path[1:])))
        if min(weights) == math.inf:
            new_weight = 0 if func(u, v) else math.inf
        elif max(weights) == math.inf:
            new_weight = math.inf
        else:
            new_weight = 0
    g.add_edge(u, v, weight=new_weight)

Если вам не нравятся эти бесконечные ребра в вашем графике, то вы можете:

• удалить их после построения графика,
• или сохранить окончательный граф параллельно сграф бесконечности и, в конце концов, просто оставьте последний.

Answer 3

Непонятно, что вы действительно пытаетесь сделать, но вот решение, которое проверяет только один элемент в каждой эквивалентной группе:

nodes2place = range(1, 6)
cclist = []

for u in nodes2place:
    node_was_placed=False
    for icc in range(len(cclist)):
        if foo(u, cclist[icc][0]):
            cclist[icc].append(u)
            node_was_placed=True
            break

    # node doesn't fit into existing cc so make a new one
    if not node_was_placed:
        cclist.append([u])