NetworkX Graph對象的「同構」比較，而不是默認的「地址」比較

我想在Python dict中使用NetworkX Graph對象作爲鍵。但是，我不希望用於比較的默認行爲（即通過對象的地址）。相反，我希望同構圖表指的是dict中相同元素的鍵。NetworkX Graph對象的「同構」比較，而不是默認的「地址」比較

此行爲是否已在某處執行？我無法在這個方向找到任何信息。

如果我必須自己實施它，下面的評估是否現實？

將networkx.Graph包裝在一個類中。
定義__eq__，使其調用is_isomorphic。
Define __hash__莫名其妙（建議歡迎）。

我認爲我將不得不作出這個包裹圖形不變，because：

如果一個類定義了可變對象，並實現了__eq__()方法，它不應該實行__hash__()，因爲哈希的實施集合要求密鑰的哈希值是不可變的（如果對象的哈希值更改，它將位於錯誤的哈希桶中）。

來源

2013-12-11 user1661473

難道我理解正確的話，你想isophorphic圖形具有相同的哈希值（）值？如果是這樣可以幫助你解決這個問題嗎？ - http://en.wikipedia.org/wiki/Graph_canonization – Aric

@Aric如果我必須自己實現它，那麼是的，我希望同構圖具有相同的'__hash __（）'值。但是，圖形標準化可能是過度的。我想到的是獲得[有序度數序列]（http://en.wikipedia.org/wiki/Degree_sequence#Degree_sequence），然後對其進行哈希處理。這樣做，非同構圖可以具有相同的散列，但同構圖不能具有不同的散列。但在開始之前，我首先希望有人已經在某處完成了它:) – user1661473

如果你能找到一種方法來創建一個獨特的度數序列的整數，你可以使用它作爲一個hash（）函數。 – Aric

這裏是一個子類圖形networkx並添加當量和散列函數你描述的一個例子。我不確定它是否能解決您的問題，但應該是一個開始。

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')] 
[[email protected] 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')]

來源

2013-12-13 00:35:04 Aric

謝謝。我可能最終會做這樣的事情。如果有人遇到類似的問題，我建議在你的'myGraph'對象上調用'freeze'（因此使它們不可變），然後再將它們用作鍵。 – user1661473

NetworkX Graph對象的「同構」比較，而不是默認的「地址」比較

回答

相關問題