高效地查找考虑传递等价的无向图中的连通分量

Question

我有一组节点和一个名为foo(u,v)的函数，可以确定两个节点是否相等。这里的“相等”是指传递性等价：如果1==2且2==3，则1==3；同时，如果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)函数高效地查找所有连接组件？

- Max Segal

---

你无法避免 O(n^2) 的复杂度。你所能做的就是避免冗余比较。 - BlackBear

如果函数foo通过尊重所有节点之间的瞬态相等性来计算两个节点的相等性，那么为什么不让该函数一开始就处理冗余呢？或者反过来，该函数如何确保尊重所有节点之间的瞬态相等性？ - a_guest

如果您只能访问黑盒函数 foo，那么您的问题就是查找连通组件，我认为您最好的选择是 O(c n)，其中 n 是顶点数，c 是连通组件数。可以使用 并查集数据结构 来实现这种复杂度。这在组件数量较少的情况下很好，但在最坏情况下它与 O(n²) 相同。 - Stef

然而，如果您可以通过一个生成“类代表”的函数bar(u)来替换测试相等性的函数foo(u, v)，那么当且仅当foo(u, v) == True时，bar(u) == bar(v)，您可以通过将顶点存储到列表字典中，在线性时间内找到连接组件：d = defaultdict(list); for u in g.nodes: d[bar(u)].append(u)。 - Stef

实际上，在你只有一个黑盒函数 foo 的情况下，我提到了并查集数据结构，但在你的情况下，甚至不需要它来实现 O(c n) 复杂度，因为 foo 定义了等价类（这意味着每个连通分量都是完全连接的）。只需保留迄今为止找到的连通分量列表，并将每个新顶点 u 与每个连通分量的第一个顶点进行比较；如果存在，则将其添加到它所属的第一个连通分量中，否则将其作为新的连通分量添加。 - Stef

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

- ComplexGates

---

当节点之间没有连接时，该解决方案在最坏情况下仍为O(n^2)。 - Max Segal

是的，在最坏情况下它仍然是O(n^2)，但我不确定你是否可以避免这种情况，因为你如何表述等价关系搜索问题并不清楚。顺便问一下，你是否实际上有一个基础图结构，还是假设你需要一个来找到你的组件？正如你所问的那样，看起来你正在从关系中构建一个图，而不是相反。 - ComplexGates

Answer 2

你可以使用两个字典来跟踪哪些边在传递上相等或不相等。对于每个边组合，您可以在O(1)时间内进行一些简单的检查，以查看计算是否冗余。否则，您需要从第一原理进行计算，然后根据边是相等还是不相等，更新上述字典中的必要信息。您仍然需要进行C(n, 2)个相等性检查，因为这就是您迭代的组合数量，但对于其中的许多组合，决策可能会立即做出。 equal_edges 字典比较容易解释，所以我们从这里开始。1-2 边对是相等的，但由于 1 或 2 都不存在作为键（字典现在为空），我们创建集合 {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]中获取。这意味着对于一个传递不相等的对a-b，我们需要进行双重检查，即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

- Reti43

Answer 3

您可以使用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)

如果您不喜欢图表中的无限边，则可以选择：

• 在构建完图表后删除它们，
• 或者在无限图表的同时维护一个最终图表，在最后只保留最终图表。

- a_guest