python - 当只能进行相等比较时，对 python 列表中的唯一项进行分组

Question

我有一大堆从 networkx 创建的图表。模块。如果函数 is_isomorphic 则两个图 g1, g2 是“相同的” :

nx.is_isomorphic(g1,g2)

返回True。这不足以创建排序，因为我只能定义 g1==g2 ，因此我无法使用集合或字典对项目进行分组。有没有一种巧妙的方法来对图进行分组，以便同一组中的所有图都是同构的？

Answer 1

这是一种简单的方法:

groups = []
for graph in graphs:
    # check if this graph is isomorphic to any of our groups so far
    for group in groups:
        # we only need to check one graph from each group, since isomorphism is transitive
        if networkx.is_isomorphic(graph, group[0]):
            # if isomorphic, put this graph in this group
            group.append(graph)
            break
    else:
        # if none were isomorphic, make a new group
        groups.append([graph])

这将创建一个列表列表，每个子列表包含彼此同构的组。

对此进行可能的调整，可以在某些情况下提高性能。例如，您可以尝试首先根据图表拥有的节点数量(顺序)对图表进行分组(可能通过排序)。由于不同阶的图不能同构，因此您可以通过仅检查相同大小的图之间的同构来偷工减料。