NetworkX Graph对象的“同构"比较,而不是默认的“地址"比较 [英] 'Isomorphic' comparison of NetworkX Graph objects instead of the default 'address' comparison
问题描述
我想使用NetworkX Graph
对象作为Python dict
中的键.但是,我不希望默认行为进行比较(即按对象的地址).相反,我希望同构图被称为 dict
中相同元素的键.
I would like to use NetworkX Graph
objects as keys in a Python dict
. However, I do not want the default behavior for comparison (i.e., by the address of the object). Instead, I would like isomorphic graphs to refer to be keys to the same elements in the dict
.
此行为是否已在某处实现?我找不到这个方向的任何信息.
Is this behavior already implemented somewhere? I could not find any information in this direction.
如果我必须自己实施,以下评估是否现实?
If I have to implement it myself, is the following assessment realistic?
- 将
networkx.Graph
包装在一个类中. - 定义
__ eq __
,以使其调用is_isomorphic
. - 以某种方式定义
__ hash __
(欢迎提出建议).
- Wrap
networkx.Graph
in a class. - Define
__eq__
such that it callsis_isomorphic
. - Define
__hash__
somehow (suggestions welcomed).
I think that I would have to make this wrapped Graph immutable, because:
如果类定义了可变对象并实现了
__ eq __()
方法,则不应实现__ hash __()
,因为可哈希集合的实现要求键的哈希值是不可变的(如果对象的哈希值更改,它将位于错误的哈希存储桶中).
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图进行子类化并添加您描述的 eq 和 hash 函数的示例.我不确定它是否可以解决您的问题,但应该作为一个开始.
Here is an example of subclassing a networkx Graph and adding a eq and hash function as you describe. I'm not sure if it solves your problem but should be a start.
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')]
这篇关于NetworkX Graph对象的“同构"比较,而不是默认的“地址"比较的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!