使用Boost Graph Library创建的两个图形的比较

Question

这可能是一个初学者或甚至错误的问题，请多包涵。是否有一种方法可以比较使用Boost Graph Library创建的2个图表=>使用1个在内存中创建的图表和第二个从存档中加载（即第二个是之前序列化的）？

我在BGL的文档中没有看到提供operator==，但不确定这是否意味着我必须编写遍历和比较。任何指向教程、参考页面或示例的指针都将非常有帮助。

先行致谢 Ganesh

- ossandcad

Answer 1

Boost.Graph可以实现这个功能，但不能使用==运算符：http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html。由于这是一个难题，对于大型图形可能需要很长时间。

- stribika

---

谢谢stribika。这似乎提供了我所需要的东西。我的图表不是很大 - 很少超过30个节点，平均每个图表约有10个节点，每个子节点仅连接到一个父节点，从不连接到兄弟节点（有点像树形结构）。 - ossandcad

30可能太多了。文档上说它的时间复杂度是O(n!)，而30！大约是10^32。 - stribika

我曾经在拥有数千个节点的图上使用了同构算法。运行时间很大程度上取决于节点之间的连接方式（我们没有使用boost库，而是采用了自己的实现）。 - AProgrammer

感谢stribika，用聪明的胖子（霍默·辛普森）的话来说——哎呀！我没有意识到它的O（|V|！）部分。虽然你提供的链接说它是最坏情况下的时间复杂度，但我希望我的图的简单性——一个基本树不会达到那个复杂度。 - ossandcad

一棵树比普通图检查同构要简单得多，即使您没有标签来帮助您对节点进行排序，就像您另一个评论所暗示的那样。（使用唯一标签可能是最简单的方法） - AProgrammer

@stribika：如果你的图是“典型”的图，那么它就很难处理。事实上，在现实生活中，图并不是“典型”的。你不能从所有该大小的图的随机分布中获取它们。因此，寻找同构问题就不再是一个可怕的问题了。 - einpoklum

Answer 2

一般情况下，图相等性是一个不能在多项式时间内解决的问题；在实践中，这意味着在合理的时间内解决它可能是有效地不可能的（虽然不确定是否NP完全）。但是，如果您关心顶点标签也相等，那么只需在两个图形上迭代所有边，并确保每个边界也存在于另一个图形中即可。 编辑：如果两个图的顶点标签（与每个顶点相关联的值）相同，并且唯一且可比较，则可以轻松检查同构性，例如O（V lg V + E lg E）:

If |G1| != |G2|, the graphs are non-equal. Abort.

i = 0
For each vertex V in G1:
  G1_M[Label(V)] = V
  G1_I[V] = i
  i = i + 1

For each vertex V in G1:
  G1_E[V] = sort(map(λDestination -> G1_I[Destination]) Edges[V])

For each vertex V in G2:
  If G1_M[Label(V)] does not exist, the graphs are non-equal. Abort.
  G2_corresp[V] = G1_M[Label(V)]
  G2_I[V] = G1_I[G2_corresp[V]]

For each vertex V in G2:
  G1_E[V] = sort(map(λDestination -> G2_I[Destination]) Edges[V])
  Compare G1_E[G2_corresp[V]] and G2_E[V]. If non-equal, the graphs are non-equal. Abort.

If we get here, the graphs are equal.

- bdonlan

---

这意味着目前没有已知的多项式时间算法，因此在实际情况下它可能是NP完全问题 :) - bdonlan

有趣的是，它尚未被证明为NP完全问题，但也没有已知的多项式时间解决方案。 - stribika

如果每个节点存储的值都是唯一的，并且您可以使用它们作为键构建映射，则可以使用这些值创建同构，然后验证它是否适用于图形。这可以很容易地在对数线性时间内完成，或者如果您可以将标签用作哈希键，则可以在线性时间内完成。 - bdonlan

再次感谢bdonlan，据我所知，每个节点存储的值都是唯一的。你的意思是我应该创建一个以这些唯一节点为键的std::map，对吧？听起来很不错。绝对值得一试。 - ossandcad

我在这里添加了一些伪代码，表达我的意思。我假设我定义的所有映射都是std::maps，但在许多情况下，您可以将它们作为数据成员等以获得更好的效率。 - bdonlan