algorithm - 散列子图的有效算法？

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

假设顶点具有整数 ID，我将使用通常用于散列整数对数组的任何散列算法，以某种定义的顺序（例如字典顺序）对子图中的边列表进行散列。此列表中的边表示为具有固有顺序的顶点对，因此如果您要表示的图形实际上具有无向边，您还需要以某种顺序对每条边内的顶点对进行排序（例如从最小到最大）。

Answer 3

没有用于散列子图的有效算法，否则图匹配将被称为多项式。

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

谷歌搜索“规范分子签名”我发现了这个在线工具