比较Boost Graph Library创建的2个图表

Question

这可能是一个相当新手甚至是错误的问题所以请原谅.有没有办法比较使用Boost Graph Library创建的2个图表=>在内存中创建的1个图表和从存档中加载的第2个图表(即第2个是先前序列化的)？

我没有在BGL的文档中看到运算符==,但不确定这是否意味着我必须同时编写遍历和比较.任何指向教程,参考页面或示例的指针都会非常有用

在此先感谢Ganesh

Answer 1

Boost.Graph可以这样做但不能使用==运算符:http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html

这是一个难题,所以大型图表需要很长时间.

Answer 2

在一般情况下,Graph Equality是一个在多项式时间内不易处理的问题; 实际上,这意味着在合理的时间内解决它可能是有效的(尽管不知道是 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.