哈希子圖的高效算法？

有散列給定圖的子圖（由節點和邊組成）的算法嗎？同樣，我所說的特定圖形是一個分子網絡，散列網絡子圖的目的是查看是否給定了不同的網絡，有一個特定的子圖與先前的散列子圖相匹配。哈希子圖的高效算法？

我不關心查找所有子圖本身的運行時間。我擔心給定一個特定的散列子圖和另一個子圖，我是否可以發現該子圖是否是我在O（1）時間之前見過的。

來源

2013-10-21 Quanquan Liu

你如何定義一個子？節點是相同的（身份），還是具有相同的值？ – Murph

已編輯。子圖由節點以及任何邊緣（有向或無向）組成。 –

哈希子圖將如何工作？我懷疑這可能會起作用。如果你的哈希方案工作，你可以簡單地解決圖形同構問題。 IIRC，圖同構很難。 –

如果你的圖是非循環的（具有可變分裂級的樹），你可以在圖的每個頂點（節點）保留一些值，即，它是「這個子樹的哈希」。

計算哈希樹容易BT遞歸算法，如：

// Initial value ~0 meaning "need to compute" 
uint32_t subtree_hash(node *p) { 
    for(int attempts = 0; p->hash == ~0; attempts++) { 
    p->hash = compute_hash(p->value) + attempts; 
    foreach node *child in (p->children) { 
     p->hash = ((p->hash >> 7) | (p->hash << (32 - 7))) + subtree_hash(child); 
    } 
    return p->hash; // never ~0 
}

來源

2013-10-21 20:53:32 maxihatop

我想你會想XOR所有孩子的subtree_hash，所以順序無關緊要。 – Murph

在原始請求中，訂單問題或無關緊要 - 未指定。所以，我默認假設 - 順序是重要的，因爲在最簡單的情況下（二叉樹），你不能總是改變rson而不影響樹結構。當然，如果順序不重要 - 需要禁用旋轉，並且只需添加值。 XOR並不是很好，例如，如果兩個孩子擁有相同的哈希值，他們的值就會從我們的結果中穿過。如果您使用添加，則會添加2倍的值。只輸出特定總和的最低位，但不是全部總和。 – maxihatop

假設頂點具有整數ID，我也只是湊邊的列表中子，在某些定義的順序（如詞典），使用通常用來散列整數對數組的散列算法。這個列表中的邊被表示爲具有固有順序的頂點對，所以如果要表示的圖實際上具有無向邊，則還需要按照某個順序對每個邊內的頂點對進行排序（例如，從最小到最大）。

來源

2013-10-21 22:19:26

對散列子圖沒有有效的算法，否則圖表匹配將被認爲是多項式。

由於分子圖具有有界連接性，因此存在一些特定算法。

谷歌搜索「的規範分子簽名」我發現這個網上tool

來源

2013-10-27 04:57:39 jimifiki

哈希子圖的高效算法？

回答

相關問題