python - 考虑传递等价性的无向图中高效寻找连通分量

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) 时间复杂度运行。通过自定义 foo(u,v) 有效查找所有连接组件的正确方法是什么(或者可能是任何 python 库中的现有函数)功能？

Answer 1

不清楚你真正想做什么，但这里有一个解决方案，它只检查每个等效组中的一个元素:

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