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

我有大量的networkx模块创建的图形。如果函数g1, g2，则两个图is_isomorphic是“相同的”：

nx.is_isomorphic(g1,g2)

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

最佳答案

这是一种简单的方法：

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

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

可能会有一些调整，在某些情况下可以提高性能。例如，您可以尝试首先根据图具有的节点数（它们的顺序）对图进行分组（也许通过排序）。由于具有不同顺序的图不能是同构的，因此您可能仅通过检查大小相等的图之间的同构性就可以偷工减料。

关于python - 当只能进行相等比较时，将python列表中的唯一项分组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25345319/