Comparing 2 graphs created by Boost Graph Library

Question

This may be a rather novice or even wrong question so please be forgiving. Is there a way to compare 2 graphs created using the Boost Graph Library => with 1 graph created in memory and the 2nd loaded from an archive (i.e. 2nd was serialized out previously)?

I don't see an operator== provided in BGL's documentation, but not sure if that means that I have to write both traversal and comparison. Any pointers to tutorials, reference pages or samples would be most helpful

Thanks in advance Ganesh

Answer 1

Boost.Graph can do this but not with the == operator: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html

It is a hard problem so it will take long for large graphs.

Answer 2

In the general case, Graph Equality is a problem which is not known to be tractable in polynomial time; in practical terms, this means it might be effectively impossible to solve in a reasonable amount of time (although it is not known to be NP-complete). However if you're concerned about vertex labels being equal as well, then it suffices to iterate over all edges in both graph and make sure each is in the other graph as well.

Edit: If the vertex labels (values associated with each vertex) are the same on both graphs, and are unique and comparable, we can check isomorphism in O(V lg V + E lg E) easily, like so:

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.