高效的散列子图算法？

Question

是否有对给定图的子图(由节点和边组成)进行散列的算法？类似地，我所说的特定图是一个分子网络，而散列网络子图的意图是看看是否给定一个不同的网络，是否有一个特定的子图与以前的散列子图相匹配。

我不关心查找所有子图本身的运行时。我关心的是给定一个特定的散列子图和另一个子图，我是否能够发现该子图是否是我在O(1)时见过的一个子图。

Answer 1

如果您的图是无圈的(具有可变分裂级别的树)，则可以在图的每个顶点(节点)中保留一些值，即“此子树的散列”。

计算子树的散列是很容易的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
}

Answer 2

假设顶点有整数in，我只会按某种定义的顺序(例如字典法)对子图中的边列表进行散列，使用通常用来散列一对整数的散列算法。该列表中的边表示为具有固有顺序的顶点对，因此，如果要表示的图实际上有无向边，则还需要按某种顺序(例如，从最小到最大)对每条边内的顶点排序。

Answer 3

没有高效的散列子图算法，否则图匹配将被认为是多项式的。

由于分子图具有有界连通性，因此存在一些特定的算法。

谷歌“典型分子签名”我在网上找到了这个工具