Comparando 2 gráficos creados por Boost Graph Library

Question

Esto puede ser una pregunta bastante novedosa o incluso incorrecta, así que por favor, perdón. ¿Hay alguna manera de comparar 2 gráficos creados con Boost Graph Library => con 1 gráfico creado en la memoria y el 2º cargado desde un archivo (es decir, el 2º fue serializado anteriormente)?

No veo un operador == proporcionado en la documentación de BGL, pero no estoy seguro de si eso significa que tengo que escribir tanto transversal como de comparación. Cualquier punteros a tutoriales, páginas de referencia o muestras serían más útiles

Gracias de antemano Ganesh

Answer 1

Boost.Graph puede hacer esto, pero no con el operador ==: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html

es un problema difícil por lo que tomará mucho tiempo para grandes gráficos.

Answer 2

En el caso general, Graph Equality es un problema que no se sabe que es tratable en tiempo polinómico; en términos prácticos, esto significa que podría ser efectivamente imposible de resolver en un período de tiempo razonable (aunque no se sabe que es NP -completo). Sin embargo, si le preocupa que las etiquetas de los vértices también sean iguales, basta con recorrer todos los bordes en ambos gráficos y asegurarse de que cada uno esté en el otro gráfico también.

Editar: Si las etiquetas de vértice (valores asociados con cada vértice) son los mismos en ambos gráficos, y son únicos y comparable, podemos comprobar isomorfismo en O (V lg V + E lg E) fácilmente, como por lo que:

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.