python – NetworkX Graph对象的’Isomorphic’比较,而不是默认

发布时间：2020-12-16 21:37:22 所属栏目：Python 来源：网络整理

导读：我想使用NetworkX Graph对象作为 Python dict中的键.但是,我不希望比较的默认行为(即,通过对象的地址).相反,我希望同构图指代dict中相同元素的键. 这种行为是否已在某处实施？我找不到这个方向的任何信息. 如果我必须自己实施,以下评估是否现实？在一个类中

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

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

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

>在一个类中包装networkx.Graph.
>定义__eq__使其调用is_isomorphic.
>以某种方式定义__hash__(欢迎提出建议).

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

If a class defines mutable objects and implements an __eq__() method,it should not implement __hash__(),since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes,it will be in the wrong hash bucket).

解决方法

下面是一个子类化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,3)]
True
False
[(<__main__.myGraph object at 0xe47a90>,'G2'),(<__main__.myGraph object at 0x1643250>,'G3')]
[aric@hamerkop tmp]$python gc.py 
3713081631935493181 [(1,3)]
True
False
[(<__main__.myGraph object at 0x1fefad0>,(<__main__.myGraph object at 0x27ea290>,'G3')]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!