考虑传递等价,在无向图中有效地找到连通分量

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