NetworkX Graph对象的"同构"比较,而不是默认的"地址"比较

Question

我想将NetworkX Graph对象用作Python中的键dict.但是,我不希望比较的默认行为(即,通过对象的地址).相反,我希望同构图指代是相同元素的关键dict.

这种行为是否已在某处实施？我找不到这个方向的任何信息.

如果我必须自己实施,以下评估是否现实？

• 换networkx.Graph上课.
• 定义__eq__它调用is_isomorphic.
• __hash__以某种方式定义(欢迎建议).

我认为我必须使这个包装的Graph不可变,因为:

如果一个类定义了可变对象并实现了一个__eq__()方法,那么它就不应该实现__hash__(),因为hashable集合的实现要求一个键的哈希值是不可变的(如果对象的哈希值改变,它将在错误的哈希桶中).

Answer 1

这是一个对 networkx Graph 进行子类化并添加eq和hash函数的示例，如您所描述的。我不确定它是否解决了您的问题，但应该是一个开始。

import networkx as nx

class myGraph(nx.Graph):
    def __eq__(self, other):
        return nx.is_isomorphic(self, other)
    def __hash__(self):
        return hash(tuple(sorted(self.degree().values())))


if __name__ == '__main__':
    G1 = myGraph([(1,2)])
    G2 = myGraph([(2,3)])
    G3 = myGraph([(1,2),(2,3)])
    print G1.__hash__(), G1.edges()
    print G2.__hash__(), G2.edges()
    print G3.__hash__(), G3.edges()
    print G1 == G2
    print G1 == G3
    graphs = {}
    graphs[G1] = 'G1'
    graphs[G2] = 'G2'
    graphs[G3] = 'G3'
    print graphs.items()

输出类似：

3713081631935493181 [(1, 2)]
3713081631935493181 [(2, 3)]
2528504235175490287 [(1, 2), (2, 3)]
True
False
[(<__main__.myGraph object at 0xe47a90>, 'G2'), (<__main__.myGraph object at 0x1643250>, 'G3')]
[aric@hamerkop tmp]$ python gc.py 
3713081631935493181 [(1, 2)]
3713081631935493181 [(2, 3)]
2528504235175490287 [(1, 2), (2, 3)]
True
False
[(<__main__.myGraph object at 0x1fefad0>, 'G2'), (<__main__.myGraph object at 0x27ea290>, 'G3')]